search

elalish / manifold

Geometry library for topological robustness
Apache License 2.0
870 stars 94 forks source link

Further collider optimizations #982

Open pca006132 opened 6 days ago

pca006132 commented 6 days ago

Just some ideas for optimization:

  1. Wide BVH: The standard BVH (and in our current implementation) uses binary trees. We can use n-ary trees (for n = 4/8) instead to make the tree shallower and reduce the number of jumps, similar to a B-tree. (there are papers on this, e.g. https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.100/institut/Papers/QBVH.pdf)
  2. Reduce precision: While we use double precision coordinates, it may be worth it to use single precision floats for our BVH for smaller memory footprint and better performance. As long as we make sure it is overapproximating, i.e. round up/down for max/min, and maybe account for epsilon, it should be safe and will give us better performance for the general case. For the rare cases that exceed single precision floating point range, we can just always treat that as colliding, I don't think users use that anyway.
  3. Maybe try AVX for bounding box overlap check. This may improve performance.
elalish commented 6 days ago

What is AVX?

pca006132 commented 6 days ago

https://en.wikipedia.org/wiki/Advanced_Vector_Extensions

aarch64 has neon, but it would be harder for me to test that, have to pull out my minipc for that (running aarch64).