exact bounding box in octree nodes

[stefanmaierhofer]

Storing the exact bounding box per node would

• enable additional (more exact) culling
  • for rendering and LoD selection
  • for point queries, potential speedup
• add memory overhead of 24 bytes (Box3f, relative to high-precision offset) per node
  • that's about 50 MiB for a 1 billion points dataset, which is negligible compared to raw point data (at least 16 GiB)

[krauthaufen]

when computing this I suggest that we also calculate some measure for the average point distance for the LOD data since it may help guiding the LOD decisions and quadratic runtime should not be too bad when only considering the LOD points... However we need to come up with a meaningful measure for that since the distance may be quite different depending on the camera's point of view.

[krauthaufen]

I figured that we actually want an average of the minimal distances to neighbours and just found some papers solving the All nearest neighbour problem in O(N * log N).

[stefanmaierhofer]

could you please reference the papers?

[krauthaufen]

Since we create KdTrees for points anyway it should be straight forward to query the closest point for all contained points. (obviously skipping the point itself) The papers are basically concerned with efficient creation of such a spatial structure. These closest points could also be useful for creating a triangulated representation of pointclouds at runtime. However I currently have no idea what would actually be needed for that. Something like: https://www.cg.tuwien.ac.at/research/publications/2012/TR-186-2-12-01/

[stefanmaierhofer]

done