Hot answers tagged

13

It's mainly used for frustum/occlusion culling and minimizing the collision checks between the objects. Not true. It's mainly used for programming convenience and hierarchial animation. There is no way culling and collision checks benefit from scene graphs. Quite the opposite, actually, since it's required to calculate and cache the world space data before ...


12

Basic chunking is a good way to start. You can move to more sophisticated data structures like octrees later, if you need. For now, simply divide your terrain into chunks of given dimensions when loading the model from disk. Depending on your data, you might either want to split your terrain into pillars on a plane spanning the full height, or in cubes in ...


8

Neither is needed. The choice of scene graphs or spatial partitioning or both is a matter of optimisation. And until you have a functioning game, you have nothing to optimise. So obsessing over this sort of detail now is counter-productive to the creation of your game. My advice: make the game, then measure which bits of it are slow, and finally fix ...


7

I tend to disagree with Trevor Powell's answer as there are clearly two different kinds of optimization here. One is optimization after the fact and to make the slow parts go fast, which is what he has touched on, but the other is designing your data structures and flow control to be at least reasonably efficient and sensible in the first place. The second ...


5

I'm not really good at fabricating N- statements, but the minimum search times for an object at child[0] of every child[0] should be close to the same +- a dimension. If the object falls at child[4] of every child[4] the calculation for the octtree could be as much as N^2(?) longer. Since you don't specify how/why the tree is being used, it's hard to give a ...


5

The thick black lines in the picture aren't an illustration of the connectivity of the dual grid: Those lines are the dual grid itself. The light blue lines show the squares of the quadtree but its not the quadtree that's marching. The lower left cell of the dual grid is a square. All the other cells in it are either square, some other quad or a "degenerate ...


5

Yes. There are times when it is needed still. Its really situational and depends on the details of your game and the other data structures you have in place. (And resolution of your Octtree and such) It's just a another tool in the toolbox but is definitely still used commonly. Just like you wouldn't hammer a screw in or hammer the ground for no reason, ...


4

Short Answer The Octree is favoured in games and rendering, because It supports visual level of detail, sensibly. It provides extremely tight compression of sparsely-populated spaces. (c.f. SVOs) At its lowest level it matches the uniformly-sized / -placed cells required for a voxel world. Other 3D accelerative structures may not do this, as explained ...


4

Yes. It's probably a good idea to stop subdividing your octree once you're down to some threshold number of meshes in the node, since at some point the cost of further subdivision can outweigh the cost of just drawing a few extra meshes. In fact, the other way around is necessary too: having a mesh in multiple nodes. If a mesh happens to be in a place ...


3

It might be helpful to think of the key variable as a stack that you're trying to count the depth of. Every iteration, you add 1 to the depth, return if the stack is empty, then pop 3 bits off the stack. The sentinel bit just marks where the stack ends. An example (imagine lots more zeros to the left): ... 001 000 010 111 # pop 111 ... 000 001 001 010 # ...


3

Note: This topic is way too large to be answered appropriately in a StackExchange answer. You will have to do your own further research / googling. Voxel Grids Fundamentally, you're trying to figure out a representation of a voxel grid. The simplest possible way to represent a 3D grid is a simple array, like map = new Voxel[width, height, depth], where ...


3

The point is that once you cull one octree node, you can stop culling and discard all of its children therein. Consider a binary search for example. Once you know that your key isn't in one part of the array, you can stop searching that part completely. The check itself isn't easier to compute, it just decreases the number of calls you may have to make (as ...


3

When you do newCentre = self.centre then that doesn't create a new array, but it uses the same object instead. If you modify newCentre, self.centre gets modified as well. It probably stays 0, because it's symmetric.


2

If all the tiles are approximately the same size, lie roughly on a flat plane, and the camera is always a set distance from the plane, simply calculate the tile that the camera is looking directly at and then cull any tile whose distanceSquared() from the looked at tile is greater than a value that would place it outside the FOV. When considering the '...


2

Figure Out a visible rectangle of tiles. Only draw that. Isometric vies complicate things, but only slightly. Simply start at the leftmost, topmost tile and draw that row. Then the next. You should be able to convert between screen and world space, so converting and visible spot on the screen aligned visible rect to tile coords should be straightforward....


2

You might want to take a look at sparse voxel octrees and you should be able to find some implementations. You want a dynamic VBO. Every frame, you work out which boxes in the octree you want to draw, calculate the position of the box's corners, add them to the dynamic vbo as vertices and create a supporting index buffer to detail which points join to which ...


2

I think you're overcomplicating things. If I understood correctly, you want to find all leaf-nodes within your octree and add these to a list of nodes that should be subdivided. I have no clue what you need the d and g parameter for.. something like this should work: void LoopNodes(gOctreeNode* node, std::vector<gOctreeNode*>& dnodes) { // ...


2

There are techniques based around traditional heightmaps, but instead of using a purely vertical height value, the textures contain a full 3D vector, indicating the displacement to apply to the vertex. This allows you to stretch around and reallocate areas of the terrain, creating overhangs and jutting parts of the terrain. Complemented with carefully ...


2

If you are looking for precise mesh collision detection then you need to compare each pair of faces that are in the same cube in the 3d grid. You are right about avoiding an octree. Build a 3d grid that contains both objects an populate it with faces and check faces that are in the same cubes in the grid for intersection. Please realize this is a slow (...


2

Octrees store data, indexed by a 3 dimensional position. That data could be a reference to an object, reference, bool, or whatever you need. Inserting items into an Octree is typically done from top down. You have a maximum number of items per cube, once that maximum is reached, the cube is split into 8 (hence the oct prefix in Octree). When splitting, the ...


1

If what you mean is that you need a nav-volume with fewer nodes because the oct-tree ends up leaving you with too many nodes, the main issue behind you problem is, of course, symmetry. Or better said, the fact octrees do not allow for asymmetric nodes. The result of that is empty space ends up being wastefully divided - either in the within a given level, ...


1

I'm not sure I'm answering the exact question, so I'm going answer in segments, and feel free to reply in comments if there's a misunderstanding about the particulars of a specific question. I have to define the initial bounding volume (and the larger it is, the more processing I need to do) This doesn't seem like it should be the case. Since the octree ...


1

What you would do is have a limited depth for your octree and allow multiple voxels per leaf. I used a depth of around 6-8 for spatial partitioning for collision detection but for voxels you'll probably need more; it's up to you. You'll also need a limit to stored voxels before splitting, say 10 for the sake of example. As your populate your octree when you ...


1

first you transform the cannon ball into the coordinate space of the ship. Then you act as if you want to add the ball's model to the octree and step down through the nodes. If the ball straddles a boundary line then go through both sides. Once you get into a leaf not then there is the bucket with faces to test with.


1

Implicit Functions and Surfaces An implicit function is simply a function that, from any point in N-dimensional space gives you a real number: forall x in R^N, f(x) -> R In your case, what you want is a 3D function that returns some real (i.e floating point) number: f(x, y, z) -> [-infinity, +infinity] The implicit part comes in when we ...


1

I have a few 2d implementations of dynamic spatial structures located here: https://github.com/ClickerMonkey/Steerio/tree/master/Java/src/org/magnos/steer/spatial As far as quad/octrees go, each iteration you check on everything in the database to see whether it has changed which node it belongs to. In my tree implementations I keep an entity in the ...


1

Like any data structure octrees come with pros. and cons. Octrees are hierarchical. This is usually a compelling reason to use them, if you don't need this property then you probably don't need octrees. Remember to always use the appropriate data structure when actually needed. You can use a uniform grid for your voxels engine, and it works. But you won't ...


1

For occlusion culling with an octree, you could build low-res hierarchical depth buffer first from potential occluders (taking max depth of 4 samples for lower-res LOD) and test the octree against it. You need to determine the octree node size in screen and pick the proper LOD to test against to reduce the test to 4 samples per octree node. The main issue ...


1

This approach works for diamond shaped isometric maps. 1) Find out what the top left tile on the screen is. 2) Depending on how you draw the map offset this by 2 tiles in both directions off the screen. So now you chosen a tile outside the viewport area. 3) Calculate how many horizontal rows and how many vertical rows need to be drawn so you end up on the ...


Only top voted, non community-wiki answers of a minimum length are eligible