We’re rewarding the question askers & reputations are being recalculated! Read more.

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 ...


10

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 ...


6

You should really just use one AABB for most objects. You could always check the object twice, first on a per-object basis and then on a per-bone basis if you want the extra precision.


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

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

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

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 ...


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

If your ray starts in an octree node, then it could, of course, hit something in that node. If you ignored the node in which the ray starts, you risk missing the closest hit. So, no, there is no reason not to do it because you should do it.


4

Actually, I don't think that octrees are the appropriate data structures for what you are trying to do, at least not if you are dealing with arbitrary polygons (which I assume you are). For sorting polygons (at least static ones), you may want to look into BSP (Binary Space Partitioning) trees instead, see http://www.gamers.org/dhs/helpdocs/bsp_faq.html ...


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

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 # ...


2

I understand now why I get holes. I'm using a bad AABB-triangle partial containment scheme: an AABB "partially contained" a triangle iff the AABB contained at least one a vertex of the triangle. E's are "empty", according to the bad "Triangle partially in AABB" detection scheme. I guess this means that if you want to push everything down to leaf nodes, you ...


2

Cyril Crassin just published his thesis on Gigavoxels: http://maverick.inria.fr/Publications/2011/Cra11/ I'm sure it's going to answer lots of your questions. Sorry for not being able to help you myself, I thought pointing you to this reference would be useful though.


2

That's exactly the way to do it, provided that's a leaf node. If not, you need to drill down to subsequent levels to raymarch there.


2

The thing is, your object octree's final structure is going to be different than your poly octree's structure, because the objects are larger than the polys in your soup. So I think it might be wise to aim for a separate octree. After all, octrees are an optimisational bit of architecture. If aiming for faster throughput, I would definitely duplicate the ...


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

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 ...


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

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 ...


2

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.


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 ...


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