Here is a demo I put together demonstrating how to implement a lasso tool with the three-mesh-bvh library I maintain. The code can be found in the selection.js file in example folder.
Depending on your use case performance may be good enough without an acceleration structure. Here’s a rough overview of the algorithm I used for finding the lasso selection for every triangle that intersects the lasso shape:
- Construct a list of screen space line segments that represent the lasso shape drawn by the user.
- For every triangle in the geometry check if any part is within the lasso. If it is then consider the triangle selected.
To determine whether a triangle intersects the lasso:
- Project the triangle vertices and edge segments into screen space.
- Check if any of the triangle vertices are within the lasso shape, which you can use the ray-crossing algorithm for. If any of the crossing numbers are different between the points or if any of the crossing counts are odd then the triangle intersects the lasso shape.
- Check if any of the triangle line segments intersect any of the lasso line segments. If they do then the triangle intersects the lasso shape.
- Otherwise the triangle has not been intersected.
Spatial index data structures can be used to quickly cull large sets of triangles by determining if parent bounds are entirely encapsulated by the lasso shape or do not intersect at all which can give a bit of a performance boost if needed.