gkjohnson / three-mesh-bvh

A BVH implementation to speed up raycasting and enable spatial queries against three.js meshes.
https://gkjohnson.github.io/three-mesh-bvh/example/bundle/raycast.html
MIT License
2.38k stars 247 forks source link

Add a built in "PointsBVH", "LineBVH" class #243

Open gkjohnson opened 3 years ago

gkjohnson commented 3 years ago

Upgrade the logic in point cloud example to be officially supported and adjust the BVH building logic to support points and improve the memory footprint over the example workaround that uses degenerate triangles and a duplicated geometry.

It might be possible to make a minimal change in the BVH building that will consider a "range" of points when sorting indices for the bounds. For "triangles" the range or stride is 3 but maybe it could be made variable so points (1) and lines (2) could be used.

gkjohnson commented 3 years ago

One bit of complexity here when assigning a BVH to the geometry is that the same geometry can be used for a Points or a Mesh object leading to a conflict when building a mesh BVH vs a points BVH:

Some possible solutions:

geometry.boundsTree = new MeshBVH( {
  mode: POINTS, // TRIANGLES, LINES
} );
gkjohnson commented 2 years ago

The following functions must be changes to consider the stride of the element (1 for points, 2 for line segments, 3 for triangles):

The MeshBVH functions that assume triangles must also be implemented for points / lines:

gkjohnson commented 2 years ago

Perhaps an abstraction layer around primitives can be made such that no performance is lost -- or a fast path is provided for supported primitives. Another good use case would be to encapsulate arbitrary n-gons in an arbitrary javascript structure for something like CSG.

gkjohnson commented 10 months ago

Note that the item bound ranges only need to be retrieved on build and refit.

~Question: how to dispose? Have "dispose all" argument?~ Dispose shouldn't be needed