Hot answers tagged

6 votes
Accepted

Should I use octree or quadtree for my spacial data structures?

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] ...
  • 3,634
5 votes
Accepted

Marching cubes over an octree dual - how?

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 ...
5 votes
Accepted

Is Frustum culling still needed today?

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) ...
  • 2,363
3 votes

How can I calculate an octree node's depth from its location code?

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 ...
  • 13.3k
3 votes
Accepted

Need help with simple octree implementation

When you do newCentre = self.centre then that doesn't create a new array, but it uses the same object instead. If you modify ...
  • 14.6k
3 votes

How to read a sparse Octree sequentially, like a 3D array?

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 ...
  • 29.2k
3 votes
Accepted

Octree Terrain Destruction and LODs

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 ...
  • 4,433
2 votes

Determine wheter an octree node needs to be continue

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 ...
  • 10.5k
2 votes
Accepted

General Octree question: What do you actually store?

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 ...
  • 72.8k
2 votes

Using octrees as LOD system

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 ...
  • 117k
2 votes
Accepted

Implicit Functions and extracting an isosurface

Implicit Functions and Surfaces An implicit function is simply a function that, from any point in N-dimensional space gives you a real number: ...
  • 3,577
1 vote

How to read a sparse Octree sequentially, like a 3D array?

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 ...
  • 117k
1 vote
Accepted

How to construct a octree density from SDF for MC

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'...
  • 117k
1 vote
Accepted

Setting up an "Oct-Tree"

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 ...
  • 2,612
1 vote

How can I store point voxel terrain in octrees

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 ...
  • 1,363
1 vote

Drawbacks to an Octree and Quadtree hybrid?

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 ...
  • 109
1 vote
Accepted

Simplyfing/dissolving octree to simple boxes by adjacent octants with similar traits

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,...
  • 4,885
1 vote

Building an Octree for terrain generation

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 ...
  • 8,974
1 vote

How can I split up a large model into an octree codewise?

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

Octrees as data structure

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

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