search

giladdarshan / OctreeCSG

MIT License
40 stars 3 forks source link

Create a test harness and tweak a memory leak #2

Closed manthrax closed 2 years ago

manthrax commented 2 years ago

Hi @giladdarshan

I hacked together a test harness showing the differences betw octtree csg and the brute force version.

You should be able to run it on chrome: /test/OTCSGDemo.html

You can toggle wireframe with W, and Space switches betw. occtree and brute force.

The octtree method looks really promising and generates a lot less triangles! (it does create t-junctions but I don't see any visible artifacts on rendering due to tjunctions though so for a lot of use cases it might not matter?)

I see some polygons dropping out at certain points in the octtree method.. might be missing an edge case there... image

There is some memory pressure from the octtree generation, and with these small examples, it doesn't outperform brute force by much, but I need to add more complex meshes, I think that is where the occtree will start to really kick in.

EDIT: I added a TorusKnotGeometry as a stress test, and the octtree runs about 4x faster than brute force! So definitely on to something here..

show statistics about octtree-csg vs brute force display memory, triangle counts, time taken, heap usage , wireframe

moved octrree map into the occtree class so it doesn't leak memory.

giladdarshan commented 2 years ago

Hey @manthrax, awesome, thank you!

I went over the changes in the OctreeCSG.js file, both maps can be removed as they are not used for anything, the only map currently being used (and if I'm not mistaken only for testing) is the one being created in the buildTree function and polygons being added to the map in the processTree function.

I used it in the split function because the original Octree class from the Three.js repo used box.intersectsTriangle(triangle) and caused the triangles to be in multiple sub-trees so I wanted to be able to track back from the polygon to all the trees it's a member of during the CSG operations. But since it's not ideal for CSG I decided to use box.containsPoint(triangle.getMidpoint(_v1)) which resulted in the polygons to be in only one sub-tree (as far as I know).

T-Junctions - I don't think there is a way around it when it comes to CSG if we want to keep the number of triangles to a minimum as we only split intersecting triangles and not each triangle with all the planes in the other object, but it sure is something to look into in the future.

Polygons dropping - I'm on the look out for examples where it happens, it seems like basic geometries that I've used in testing so maybe the positions is what causing the polygons to drop, I will test it out as well.

Will go over the test quickly and then merge it, I will remove the maps completely when I do cleanup.

Thank you!