Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
gkjohnson opened this issue May 20, 2021 · 4 comments
Open

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

gkjohnson opened this issue May 20, 2021 · 4 comments
Labels
help wanted Extra attention is needed
Milestone

Comments

@gkjohnson
Copy link
Owner

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 gkjohnson added the help wanted Extra attention is needed label May 20, 2021
@gkjohnson gkjohnson added this to the v0.x.x milestone May 20, 2021
@gkjohnson
Copy link
Owner Author

gkjohnson commented May 26, 2021

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:

  • Both BVHs will modify the index buffer which will break the other BVH
  • BufferGeometry.boundsTree is expected to be a MeshBVH
  • computeBoundsTree generate a MeshBVH

Some possible solutions:

  • A flag could be added to computeBoundsTree to indicate which type of bounds tree to generate (points or triangles).
  • Overridden raycast functions could check the BVH stride to determine whether it can be used for raycasting of the object type.
  • A single BVH could be allowed per BufferGeometry and possibly log a warning if the correct BVH is not generated when raycasting (that can be disabled). It seems unlikely that the same geometry object would be used for triangles / points / lines.
  • A flag could be added to computeBoundsTree to create a bounds tree with a cloned index buffer to avoid conflict.
  • An extra function could be added that generate a PointsBVH rather than a MeshBVH on the geometry.
geometry.boundsTree = new MeshBVH( {
  mode: POINTS, // TRIANGLES, LINES
} );

@gkjohnson gkjohnson modified the milestones: v0.x.x, v0.4.3 Jul 17, 2021
@gkjohnson
Copy link
Owner Author

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

  • computeTriangleBounds (could be optimized out completely for points)
  • partition
  • Raycast functions must account for render object type

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

  • Make a MeshBVHBase that implements stubs for expected functions.
  • Raycast / raycast first can be implemented (though maybe not as optimally) with shapecast.

@gkjohnson gkjohnson modified the milestones: v0.4.3, v0.x.x Aug 9, 2021
@gkjohnson
Copy link
Owner Author

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
Copy link
Owner Author

gkjohnson commented Aug 16, 2023

  • Add a TriangleBVH base class
  • Inherit with PointsBVH, LineBVH, MeshBVH
  • Points and line bvhs are based on triangles under the hood
  • only support raycast initially
  • support both screen and world intersection
  • rearrange the og index buffer based on bvh adjust
  • add field to compute options to which bvh to construct
  • webworker can implicitly use the right approach based on same options
  • continuous lines must be converted to segments (or does it? Can we have a "virtual" index that is resolved to the appropriate item by another function? This would be the "indirect" buffer)
  • Maybe "indirect" can "just work" without making a new index buffer?

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

@gkjohnson gkjohnson modified the milestones: v0.x.x, v0.6.4, v0.6.5 Aug 16, 2023
@gkjohnson gkjohnson modified the milestones: v0.6.6, v0.6.7, v0.6.8 Sep 3, 2023
@gkjohnson gkjohnson modified the milestones: v0.6.8, v0.6.9 Oct 10, 2023
@gkjohnson gkjohnson changed the title Add a built in "PointsBVH" class Add a built in "PointsBVH", "LineBVH" class Nov 8, 2023
@gkjohnson gkjohnson modified the milestones: v0.7.1, v0.7.2 Jan 30, 2024
@gkjohnson gkjohnson modified the milestones: v0.7.2, v0.7.3 Feb 12, 2024
@gkjohnson gkjohnson removed this from the v0.7.4 milestone Apr 10, 2024
@gkjohnson gkjohnson added this to the v0.7.5 milestone Apr 10, 2024
@gkjohnson gkjohnson modified the milestones: v0.7.5, v0.7.6 Jun 2, 2024
@gkjohnson gkjohnson modified the milestones: v0.7.6, v0.7.7 Jul 2, 2024
@gkjohnson gkjohnson modified the milestones: v0.7.7, v0.7.8, v0.7.9 Sep 9, 2024
@gkjohnson gkjohnson modified the milestones: v0.8.1, v0.8.2, v0.8.3 Sep 29, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

1 participant