What's left before making the repo public

[giladdarshan]

Sharing the list of items I plan to work on before making the repo public:

• [x] Improve Performance

  • [X] Reduce the number of iterations over the Octrees during CSG operations
  • [X] Check option to reduce raycasting time - Three.js's raycasting checks against all triangles in the target geometry, need to validate raycasting correctness when using OctreeCSG.rayIntersect / OctreeCSG.raycastIntersect

• [x] Improve Memory Management

  • [x] Check for memory leaks and resolve them
  • [x] Properly dispose objects that can be disposed
  • [x] Reduce object data where possible

• [x] Support for CSG hierarchy of operations

• [x] More testing and test cases to ensure CSG is working properly

• [x] Code Cleanup

• [x] Interactive CSG

• [x] Documentation
  Todo list after the repo is public:

• [ ] Demos & Examples

• [ ] Research for better triangle-triangle intersection methods

• [ ] Research for better polygon (triangle) splitting (if needed)

• [ ] Support for Web Workers

• [ ] Check if using buffers instead of arrays and objects for polygon data (position, normal, uv, triangle, etc) improves performance and memory management

• [ ] Research improvements to the Winding number algorithm - Due to correctness issues with raycasting, I've started testing the Winding number algorithm, while it does seem to be much more precise, it has big performance impact. More research required.

Feel free to add anything that I missed.

[gkjohnson]

It's something to consider for the longer term but I think having a good variety of interactive demos and examples showing how the project can be used can help users imagine how to use the tool and fit into their work and help the project grow. For three-mesh-bvh the examples demonstrate less intuitive cases where a BVH can be used to solve different problems and users have subsequently used them as bases for their own work - physics engines, architectural floor plan generation, geometry vertex painting, point cloud intersection, etc. They can also serve as good stress test cases for more complex and realistic use.

Some use cases ideas that might be nice to think about for examples down the line:

• Interactive Editor: CSG can be used for blocking out level designs so having a pre-built level with stairs, ramps, etc along with rudimentary support for moving / adding / removing components to show how a real time editor could roughly be made.
• Level Design Editor / Interactive World: With levels made for games you could also show the ability to walk a character around or enable basic physics after a user has arranged items (a'la the three-mesh-bvh physics demo and character movement demo).
• Existing Model Modification: Show that this will work loaded solid geometry like the stanford bunny (ie make a swiss cheese bunny).
• Hierarchical Editing: Show editable hierarchical operations.
• 3Printable Parts: Consider artistic / 3d printing design use cases where users build up models to construct in real life - maybe include an "export as STL" button (this might be a use case where t junctions are not okay)
• Asynchronous Generation: Show how CSG can be generated in a WebWorker / asynchronously with a generator / debouncing after use interaction.

[gkjohnson]

Oh I also highly recommend separating classes out into separate files at some point to make them easier to find an follow in addition to adding automated tests & CI later down the line, as well.

[giladdarshan]

• Interactive Editor: CSG can be used for blocking out level designs so having a pre-built level with stairs, ramps, etc along with rudimentary support for moving / adding / removing components to show how a real time editor could roughly be made.
• Hierarchical Editing: Show editable hierarchical operations.

Good ideas, I saw the Unity demo you shared in the other thread for interactive CSG, it helped me understand what you mean, will add to the todo list.

• Level Design Editor / Interactive World: With levels made for games you could also show the ability to walk a character around or enable basic physics after a user has arranged items (a'la the three-mesh-bvh physics demo and character movement demo).

I'm debating about this one, should we keep this library (OctreeCSG) only for CSG and make sure it plays nice with other libraries like three-mesh-bvh, or, expand this library with other functionality besides CSG (physics, character movement, etc)?

• Existing Model Modification: Show that this will work loaded solid geometry like the stanford bunny (ie make a swiss cheese bunny).
• 3Printable Parts: Consider artistic / 3d printing design use cases where users build up models to construct in real life - maybe include an "export as STL" button (this might be a use case where t junctions are not okay)

These are actually my main use cases, I'm developing a web-based programmatic CAD (3dd.dev), the "Sculpt" functionality there is based on three-mesh-bvh and your sculpt demo :smile: I didn't push my updates to the website in a while, will try to get to it this week as I did some improvements there.

• Asynchronous Generation: Show how CSG can be generated in a WebWorker / asynchronously with a generator / debouncing after use interaction. Oh I also highly recommend separating classes out into separate files at some point to make them easier to find an follow in addition to adding automated tests & CI later down the line, as well.

I will need to research these subjects more as I don't have much knowledge in them, will add them to the long-term todo list.

[gkjohnson]

I'm debating about this one, should we keep this library (OctreeCSG) only for CSG and make sure it plays nice with other libraries like three-mesh-bvh, or, expand this library with other functionality besides CSG (physics, character movement, etc)?

You're probably right. One of my original interests in getting CSG working with BVH is so all of those demos would effectively come "for free" with whatever was built - so it's nice to keep a separation and focus on CSG here.

These are actually my main use cases, I'm developing a web-based programmatic CAD (3dd.dev), the "Sculpt" functionality there is based on three-mesh-bvh and your sculpt demo 😄

Oh awesome! The sculpt demo was very fun. And a procedural CAD editor sounds, great. I'm looking forward to seeing what happens with it!

I will need to research these subjects more as I don't have much knowledge in them, will add them to the long-term todo list.

Yes these use cases came a few revisions into three-mesh-bvh after the API and data structures, etc had settled.

• [ ] Code Cleanup

I don't want to step on any toes but I'm happy to help organize the project with something like a /src folder, separated files per class, and an exported index file if that's at all helpful. If a single built file is needed, as well, I can add a rollup script to build those out, too. After that I think it will be easier to dive in an take a deeper look at how things are working.

[giladdarshan]

Oh awesome! The sculpt demo was very fun. And a procedural CAD editor sounds, great. I'm looking forward to seeing what happens with it!

Thank you, hopefully I can convince myself to work on the readme page and then I will upload my local changes :sweat_smile:

I don't want to step on any toes but I'm happy to help organize the project with something like a /src folder, separated files per class, and an exported index file if that's at all helpful. If a single built file is needed, as well, I can add a rollup script to build those out, too. After that I think it will be easier to dive in an take a deeper look at how things are working.

Great, thank you for the offer! I think it's still a bit early for this step, I want to finish few things and cleanup before separating classes to different files as it's easier for me while debugging the different issues to navigate in one file. Will take you up on the offer closer to when converting the repo to public :)

[giladdarshan]

Updated the list, added a couple of items and marked some as complete. Screenshot of the CSG hierarchy of operations:

[giladdarshan]

Updated the repo with the changes to the library.

I've implemented Möller–Trumbore intersection algorithm for ray-triangle intersection tests instead of Three.js's built-in ray.intersectTriangle which is based on this algorithm. So far it proves to be more accurate for CSG operations. The algorithm being used can be toggled with OctreeCSG.rayIntersectTriangleType being set to either regular for Three.js's built-in algorithm, or, MollerTrumbore for Möller–Trumbore's algorithm (default).

To use Winding Number instead of Raycasting, the flag OctreeCSG.useWindingNumber can be set to true or false (default).

Added code example for CSG hierarchy of operations to the readme page.