Stack Overflow
Stack Overflow

Questions tagged [octree]

An octree is a tree data structure in which each node has eight child nodes. A major application of octrees is in 3d graphics as they are the primary structure used for storing voxel (volumetric pixel) data.

Wikipedia: "An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees."

Relevant topics include voxels and color quantization.
For more information see http://en.wikipedia.org/wiki/Octree

148 questions
84
votes
8 answers

When to use Binary Space Partitioning, Quadtree, Octree?

I have recently learned about binary space partitioning trees and their application to 3d graphics and collision detection. I have also briefly perused material relating to quadtrees and octrees. When would you use quadtrees over bsp trees, or…
Martin
  • 5,945
  • 7
  • 50
  • 77
23
votes
2 answers

Ray - Octree intersection algorithms

I'm looking for a good ray-octree intersection algorithm, which gives me the leafs the ray passes through in an iterative way. I'm planning on implementing it on the CPU, since I do not want to dive into CUDA just yet :) At the moment, my Voxel…
Jeroen Baert
  • 1,273
  • 2
  • 12
  • 28
16
votes
2 answers

Where do I store shapes in an octree?

A little background on design decisions thus far... I have developed an octree structure that can store points. I have chosen to limit the recursion of "generations" based on a certain base voxel size. Child nodes are only created when points are…
Phlucious
  • 3,704
  • 28
  • 61
13
votes
3 answers

kd-tree vs octree for 3d radius search

I'm trying to figure out which structure would be better for doing several radius search of points, a kd-tree or an octree? It was already mentioned in this question but there was no answer. It seems to me that since octrees have fixed sizes for the…
paghdv
  • 554
  • 1
  • 4
  • 14
10
votes
5 answers

How to compress pointer ? eg. arbitrary bit pointer

I'm coding a complex tree data structure, which stores lots of pointers. The pointers themselves occupy lots of space, and this is what I'm expecting to save. So I'm here to ask whether there are examples on this. E.g.: For 64-bit data type, can I…
tomriddle_1234
  • 3,145
  • 6
  • 41
  • 71
9
votes
1 answer

ios - Gamekit's GKOctree not finding elements

I'm trying to use GKOctree for efficient retrieval of object in 3D space. However the following code doesn't seem to work as expected: import GameplayKit let tree = GKOctree(boundingBox: GKBox( boxMin: vector_float3(x: -10, y: -10, z: -10), …
Guig
  • 9,891
  • 7
  • 64
  • 126
7
votes
1 answer

Octree raycasting/raytracing - best ray/leaf intersection without recursion

Could anyone provide a short & sweet explanation (or suggest a good tutorial) on how to cast a ray against a voxel octree without recursion? I have a complex model baked into an octree, and I need to find the best/closest leaf that intersects a…
3Dave
  • 28,657
  • 18
  • 88
  • 151
7
votes
2 answers

Access type flag of unknown void pointer based on two possible structs?

I am currently working on my own octree in C. The tree will contain a few billion objects, so memory efficiency is key. To achieve this I currently use one struct with a flag and a union, but I think it is not clean and it is wasting space for the…
Lightningstorms
  • 147
  • 1
  • 8
7
votes
4 answers

C++ Branching recursive struct?

I have the following. The struct is prototyped so it compiles fine. struct vertexNodeInfo { vector node; }; I'm trying to write an octree thingy. What I want to do is use a recursive function to continue adding a node to each…
Clonkex
  • 3,373
  • 7
  • 38
  • 55
6
votes
2 answers

Efficient storage for a sparse octree?

Can anyone suggest a fast, efficient method for storing and accessing a sparse octree? Preferably something that can be easily implemented in HLSL. (I'm working a raycasting/voxel app) In this instance, the tree can be precalculated, so I'm mostly…
3Dave
  • 28,657
  • 18
  • 88
  • 151
6
votes
2 answers

Octree implementation for triangular mesh and particles

I am currently working in an efficient calculation engine for particle simulation both in CPU and GPU. I have been working lately in octrees and I managed to write a working version of octree for particles in space and also efficiently handled their…
rawcoder
  • 113
  • 1
  • 9
6
votes
1 answer

Rearranging data for quadtree/octree

I am working on implementing a voxel octree raycaster, and the only thing left is rearranging the data to populate the leaf level of the octree, so that the data then can be averaged to build the lower levels of the tree. I'm thinking in 2D…
Victor Sand
  • 2,270
  • 1
  • 14
  • 32
6
votes
2 answers

QuadTree or Octree templatized implementation in C++

I'm going to write a templatized implementation of a KDTree, which for now should only work as Quadtree or Octree for a BarnesHut implementation. The crucial point here is the design, I would like to specify the number of dimension where the tree is…
linello
  • 8,451
  • 18
  • 63
  • 109
5
votes
2 answers

What's the algorithm for 2:1 balancing a linear octree?

I have a top-down procedure that builds a linear octree (e.g. with leaves arranged in an array and sorted by Morton encoding) from an high-level description of 3D objects. The problem is that, for my intended application, the resulting octree must…
gigabytes
  • 3,104
  • 19
  • 35
5
votes
1 answer

Algorithm for Octree for nearest neighbor search

Problem Statement: To find the nearest GRID ID of each of the particles using Octree. Fig[1]: Fig[2]: I have a system of particles(~6k, movable) for which I need to check which grid point (rigid; in picture) is nearest to. Somebody have…
Devashish Das
  • 241
  • 7
  • 19
1
2 3
…
9 10