culling, spatial indexing

[Andoryuuta]

From @slimsag on July 29, 2014 18:49

Azul3D should provide some means of culling and spatial indexing in the form of e.g. an Octree.

Copied from original issue: azul3d-legacy/issues#1

[dskinner]

(my email blew up with all the issue moves but anyway) @slimsag: did you already have thoughts of what this would look like? I've been doing a lot of reading in this area and recently implemented a linear octree using morton codes, though I'm guessing a more general pointer based approach would be more approriate here. Thoughts?

[emidoots]

Hey @dskinner sorry for the noise :( If you want an overview of what went on (inspired partly by you!), see #1.

Interesting, I've never heard of morton codes, how do they compare in general / what are their strengths? I did implement a pointer-based octree, and plan to move that code here sometime, but it was almost a year ago so I forgot how it worked / whether or not there were any existing issues. I also think it would be useful to have a generic abstraction on top of culling/spatial indexing because an 3D octree is not suitable for 2D games for example.

[dskinner]

morton codes are interesting in that they are regular numbers, say a uint64, that is 3 numbers encoded into a single number, say the XYZ, by interleaving the bits. At an extreme, you could do three 21bit numbers with an extra bit left over for a sign or w/e. Or if you want to encode levels you could account for that and reduce overall bits available to a component.

Anyway, the interesting property is that when a list of morton codes are naturally sorted, say lowest to highest, then the codes have locality. That property can make searching arbitrary trees pretty fast. If you're doing point based trees, then linear trees in general are parallelizable in that given any code you can traverse up and down the tree independent of any state by simply shifting bits and retrieve the XYZ components by deinterleaving the bits.

The downside here is that you have a limit on the size of data, for example only 21bits available to a 3D component. That places a limit on the number of available indices and how far you can subdivide for a point based tree, which is why I was thinking that may not be appropriate for a generic indexing structure for azul3d.

Regarding a generic interface for spatial indexing, I suppose it just depends on what that interface would provide but I imagine it would be rather limited. I recently purchased this book (http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469/ref=sr_1_fkmr1_1?ie=UTF8&qid=1457236091&sr=8-1-fkmr1&keywords=multidimensional+and+geospatial+data+structures) and was rather surprised at all the different minor variations in various data structures. Ultimately I think It comes down to what you want to get done and having parts one can compose together depending on the situation while still just having it work would be a worth-while goal. I just don't know what that'd look like :)