Hot answers tagged

13

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


6

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

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


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


3

To skip all those unwanted nodes, I think what you're looking for is a sparse but contiguously-allocated octree, which can be easily indexed by (x, y, z). You also seem to want sequential ordering. For this, with a maximal tree i.e. what you call a regular tree, we use something like Morton ordering to rapidly and sequentially index into the 1D array ...


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.


3

The primary goal of LOD is to reduce the cost of drawing by not drawing unnecessarily fine detail. It is not usually about discarding information from RAM. In fact, in a conventional polygonal-model art style, it may mean using more memory to have low-detail and high-detail models ready to use as the camera moves. In your case, since you have destructible ...


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

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


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

As Kromster alludes, this apparent problem occurs because of the small scale of your example. Usually when we reach for sparse octrees, we have more than two levels of subdivision. Here's your same 2D quadtree example, but with 4 levels of subdivision instead of 2: You can see how, even in the worst case where we have a cluster of detailed content spanning ...


2

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

One strategy you can use is to make your leaf nodes "chunks" of cells. For example, Minecraft uses 16x16x16 cell chunks if I recall correctly. This gives you a coarser granularity for caching and a slightly shallower octree to manage, while keeping most of the benefits of skipping large empty areas. The chunks can also map to individual meshes/...


1

You use the octree to skip swaths of work. Anytime you find an octree node that's fully outside or fully inside the volume, you can skip iterating any cells inside it because you know the surface won't cross any of them, so marching cubes will no need to create any vertices or triangles in that entire cubic region. Your algorithm can be a depth-first ...


1

If you want div to represent the number of cubes then you need to ensure that div is a cube (as in, is an integer to the 3rd power). So 1, 8, 27, etc. Given that, you could do the following: #include <stdlib.h> #include <cmath> #include <assert.h> #include <vector> struct Vector3 { float x; float y; float z; }; ...


1

A k-d tree like Philipp suggested would likely be a good solution, but certainly more complicated to implement. Your proposed solution should work fine, but you may need to be clever with how you store your child indices/pointers, if your goal is to save space. If I were trying to solve this, given the limited information I have about your problem, I would ...


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

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

After unsuccessfully trying a couple of the packages mentioned above I found RTree, which is a wrapper around libspatialindex.


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


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