search

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.56k stars 268 forks source link

CSG: using the library for Constructive Solid Geometry #281

Closed kirill-osipov closed 2 years ago

kirill-osipov commented 3 years ago

Is it possible to use the library for CSG similar way as was done in CSG.js

gkjohnson commented 3 years ago

Hello! What's the motivation for your question? It's possible that a structure like this could be used to improve CSG operation performance but I haven't done work in that vein myself. There is a three.js issue here that discusses CSG operations but I believe most referenced solutions are ports or adaptations of CSG.js.

kirill-osipov commented 3 years ago

Yes. Performance of libraries based on CSG.js is not enough for usage models with 200+ polygons in real-time.

gkjohnson commented 3 years ago

I am not an expert in CSG so I can't confidently recommend anything specific. My understanding is that CSG typically uses different data structures for processing operations.

kirill-osipov commented 3 years ago

CSG.js uses BSP and as was said, using BSP as algorithm for splitting was a terrible idea. But, for example, as I can see Godot uses BVH

gkjohnson commented 3 years ago

Interesting -- I didn't know Godot was using a BVH for its CSG. It seems like there should be a better way to do it but a BVH should be able to be used to speed up some of the steps to running something like a brute force process for the geometry operations.

I haven't looked into Godot's implementation but some quick first thoughts on how I'd do something like this with a BVH:

  1. Collect all triangles that intersect between meshes A and B
  2. Split all intersecting triangles on the intersection planes with the other triangles
  3. For each triangle in the new split triangle sets use something like the ray-crossing algorithm determine whether or not that triangle center is inside or outside the other mesh and include or discard it depending on whether union, difference, or intersection are being used.
  4. Construct a new geometry from the triangles.
  5. Repeat!

The ray-crossing algorithm may require care when dealing with vertex and edge crossings to ensure a single edge is not double counted but in theory it seems like that should work. And of course the BVH can be used to improve the performance of steps 1 and 3 of the process. That's what comes to mind at first, at least. I'm sure there's more to consider.

I don't plan to work on this but if you're interested in pursuing it I'd be happy to offer guidance in getting a new example page going to show a basic CSG demo if you want to work on that!

kirill-osipov commented 3 years ago

Thank you for your comprehensive reply. I think I can take it.

gkjohnson commented 3 years ago

Awesome! I'll be interested to see what you come up with -- and if you wind up working to make an example page in this repo and would like some help feel free to make draft PR!

rayanarfawi commented 2 years ago

This would be really useful

gkjohnson commented 2 years ago

I've created a repo with a CSG implementation using three-mesh-bvh here:

https://github.com/gkjohnson/three-bvh-csg