Constructive Solid Geometry (CSG) Support

[ThreeDfish]

CSG is a very important feature… other 3D frameworks have support for CSG built-in ( Babylon.js ), the only CSG I can find is the 7 years outdated plugin ( https://github.com/chandlerprall/ThreeCSG )

I propose that this plug-in gets updated for bufferGeometry and added to the three.js code base as an official plug-in for CSG support.

I am willing to contribute funds to see this happen.

[yomboprime]

I can give it a try this weekend... let me see how it goes.

[yomboprime]

Um, I've added a OrbitControls and inspecting the result it doesn't seem very correct. Are you sure this library is sufficiently tested?
Please make some tests on it before I try to 'Bufferize' it 😉

[moraxy]

Adding it to the core code base might be a bit complicated, the current version (v1 branch) is in TypeScript. Works fine with r100 (and even r103) thou: examples

[donmccurdy]

I don't think bundling it into the src/ folder is the right direction, but updating it to support BufferGeometry sounds promising. Whether the library is well-tested, I have no idea. :)

[yomboprime]

Adding it to the core code base might be a bit complicated, the current version (v1 branch) is in TypeScript. Works fine with r100 (and even r103) thou: examples

So it is actively developed. I didn't see that tag. And... it seems the v1 tag supports BufferGeometry! @ThreeDfish

[Mugen87]

I vote to not include CSG features into this repo. Better ThreeCSG is supported if necessary.

[looeee]

So it is actively developed. I didn't see that tag. And... it seems the v1 tag supports BufferGeometry! @ThreeDfish

I don't think so, this is the only mention of BufferGeometry in the v1 version:

function convertGeometryToTriangles(geometry) {
        if (isBufferGeometry(geometry)) {
            throw new Error('threecsg: Only Three.Geometry is supported.');
        }

[gkjohnson]

Has anyone tried contacting the owner of the ThreeCSG to see what their plans are or if they're open to taking PRs to support BufferGeometry? I'm a little interested in this, too.

[yomboprime]

It seems nobody asked there about BufferGeometry...

[Mugen87]

Why not shifting the conversation to https://github.com/chandlerprall/ThreeCSG? I bet @chandlerprall would be happy to see such an interest in his project 😊

[chandlerprall]

FWIW there is a newer v1 branch in ThreeCSG which is a complete re-write and cleanup. Need to optimize the plane selector algorithm and then it's ready to npm publish. I would be thrilled if anyone wants to contribute additional features (see also chandlerprall/ThreeCSG#51)

[peteroupc]

For your information:

Besides https://github.com/chandlerprall/ThreeCSG, the following CSG libraries were mentioned in the recent Discourse forum thread:

• https://evanw.github.io/csg.js/
• https://github.com/jscad/OpenJSCAD.org

I have no opinion on whether any of these three should serve as a basis for three.js's CSG support.

[manthrax]

I did another conversion of the madebyevan CSG library that ya'll may find useful.. it works with current three (103) and fixed some issues I had with the older module out there. It allows buffergeometries but only by converting them to geometries internally.

https://github.com/manthrax/THREE-CSGMesh

Hope this helps someone and feel free to give feedback/suggestions.

[Mugen87]

@manthrax Your project would be a good addition to the following thread in the three.js forum so people who are looking for a plugin will actually find it👍

https://discourse.threejs.org/t/looking-for-updated-plug-in-for-csg/6785

[gkjohnson]

Awesome! I'm not sure how feasible it is but I think any of these solutions would benefit from some examples that demonstrate the performance and real-time editing capabilities like a lot of engine editors have, now.

[looeee]

My personal preference is to keep CSG out of the library and develop it independently.

I agree with this, but it might be useful to have an official set of "related repos". I've created an organisation that we can use for this if we decide to go ahead. github.com/threejs is taken by @enricomarino, but github.com/three-js was there. I'll transfer ownership to whoever, just figured it was good to jump on the name!

So, this organisation is available of anybody want to create projects related to three.js that don't quite fit here.

https://github.com/three-js

[enricomarino]

I created the organisation https://github.com/threejs to host projects related to three.js.

Actually, at that time, I thought to split the "three.js" mono repo into multiple repos,
such as "threejs/core", "treejs/examples", "threejs/editor", "threejs/docs",
since the "mrdoob/three.js" has become very large and heavy to download...
but this is another story...

If you'd like to use it, the organisation is at your disposal!

[manthrax]

I've added a demo and a screenshot to the library:

https://github.com/manthrax/THREE-CSGMesh

Let me know if anyone needs help with it!

[manthrax]

@yomboprime @ThreeDfish
I've added a screenshot and a demo to the CSG library I ported. Let me know if you find it useful.
https://github.com/manthrax/THREE-CSGMesh

[yomboprime]

@yomboprime @ThreeDfish
I've added a screenshot and a demo to the CSG library I ported. Let me know if you find it useful.
https://github.com/manthrax/THREE-CSGMesh

@ThreeDfish If you are still interested I can make a CSG.toBufferGeometry function in this library. The CSG would still accept Geometry as input, but the output could be Geometry (for further boolean operations) or BufferGeometry (final output for rendering).
What do you think @manthrax ?

[looeee]

@enricomarino can you give me access to github.com/threejs ? I'd like to set up a repo with test models for the LWOLoader. BTW you're a hard person to find contact details for 😛

[manthrax]

@yomboprime I'm not sure what you're asking..

The version I ported accepts both BufferGeometry or Geometry meshes.. it outputs Geometry, which can be converted to BufferGeometry with

mesh.geometry = new THREE.BufferGeometry().fromGeometry(mesh.geometry)

So i don't know if there really is a need for an extra helper function since the conversion is pretty straightforward.

[donmccurdy]

The Geometry->BufferGeometry conversion is unfortunately pretty lossy – it will de-index indexed geometry and increase the vertex count, in addition to adding (white) vertex colors. Final output as BufferGeometry would probably be ideal.

[manthrax]

The CSG operation doesn't care about indexing. It operates on and outputs 3 unique verts per triangle no matter what.

It also doesn't handle vertex colors.

Optimizing the resulting mesh is something that can/should be done with other tools/helper functions, imho.

Otherwise it's just duplicating dumb functionality that should actually be in a separate library.

[manthrax]

I agree that there is definitely a space in terms of a utility for optimizing geometry in THREE.js. The problem applies to more than just BufferGeometry. But applying optimizations to large buffers, via js, at runtime, are chuggy operations.. and any techniques you apply to reduce the complexity, i.e. octtree/kdtree whatever.. get complicated pretty fast and require their own set of paramaterizations etc..

I feel like there is a tradeoff between code "complexity/flexibility/utility" vs "ultra optimized for the gpu" that in a non javascript setting, you would optimize for the latter, but in a js/web scenario, you would aim for the former, and only if you decide you need to pursue the latter, you would use something like wabasm to crunch the data.

Not to mention these CSG operations are already pretty slow.. The demo in my git is barely interactive with only 10 operations per frame on a box and a 8 subdiv sphere...

[manthrax]

That said.. i just looked at the babylon csg demo.. and I'm pretty sure it's a port of the exact same library,
And it's not being done in realtime in that demo either.
https://www.babylonjs.com/demos/csg/

Here is the version I've converted doing a simpler example in realtime:

http://vectorslave.com/csg/CSGDemo.html

[donmccurdy]

I agree that CSG operations are not especially a realtime-friendly, and that the library does not need to pretend they are. However, note that Geometry will eventually be removed from the three.js library, and moved into examples/js/* and examples/jsm/*. At that point, users will almost certainly have an easier time using BufferGeometry as their result. If the CSG code has an internal dependency on Geometry, that seems fine of course.

[SebiTimeWaster]

so i could not let it rest and looked into https://github.com/jscad/csg.js which is the core CSG library of https://openjscad.org/
i browserified it and wrote my own THREE BufferGeometry adapter and it is actually A LOT faster than the library that @manthrax based his code on. (and it supports vertex coloring)

for the same dice which uses spheres with 32 faces to cut out the eyes,
THREE-CSGMesh took 112 seconds,
jscad/csg took 2.5 seconds!!!

that's 45 times faster...

i'm thinking about creating a library out of it, let me know what you think about it...

[gkjohnson]

@SebiTimeWaster

Is it available in a repo anywhere? Looks like csg.js is MIT license, too.

@mrdoob

I am looking into adding a BufferGeometry optimizing version

Is it using THREE.Geometry at the moment?

Iooking at the codebase briefly it looks like yes it does still use THREE.Geometry but just on the input and output to convert it to and from an internal structure for CSG operations.

[SebiTimeWaster]

not yet, if there is interest i would create one...

[gkjohnson]

not yet, if there is interest i would create one...

Heh I think this thread is evidence of interest! But at least I'm interested in checking it out if you've got a faster version. I don't have an immediate need for it anymore but I may in the future. It would be nice to have go to library for CSG in three even if it's just a quick example for how to get started with csg.js in three.js.

[mrdoob]

not yet, if there is interest i would create one...

Yes, an official example/solution for csg would be great!

[SebiTimeWaster]

I'm on it...

[looeee]

I'm mostly done with a BufferGeometry port of @evanw's csg.js.
Needs a bit of tidying, which I'll find time for this week, then I'll share it here.

@mrdoob do you want a CSG library in this repo? If so I'll make a PR. Otherwise, I'll make a new repo for it.

@SebiTimeWaster I didn't see your comment before now, oops. The more the merrier I guess 😁

[gkjohnson]

@looeee is it a full port or just a wrapper? It looked like csg.js had to convert data to a lot of internal structures for CSG operations anyways, right? It seemed like you should just be able to convert to and from BufferGeometry on the way in and out.

[DefinitelyMaybe]

@looeee do you mean a new repo within here ?
would be interesting but I hazard a guess mrdoob ain't ready yet.

[donmccurdy]

I'm not sure this repository is the right place to maintain a full CSG library... perhaps add an example, using a minified build of the CSG library in examples/js(m)/libs/?

[SebiTimeWaster]

So, here is my take on the whole thing (it is based on https://github.com/jscad/csg.js):
https://github.com/SebiTimeWaster/three-csg
with an example (stress test):
https://sebitimewaster.github.io/three-csg/examples/example2.html

@looeee how about you implement the same stress test, then we can compare and optimize our code against each other...

[looeee]

@looeee is it a full port or just a wrapper?

I have one branch that is pretty much just a wrapper for csg.js with a few minor changes:

• modularized the code
• aligned function names to three.js and used Vector3 instead of a custom vector class,
• minor API improvements

That branch is complete, and I'll share it once I tidy it up a bit. However, it's sloooow.

I have another branch where I'm working on speed improvements. There's a lot that can be done here, mainly to do with calculating early outs to avoid as much processing as possible.

@SebiTimeWaster, I've taken a quick look at your code and you're doing something like this using bounding spheres for each polygon I think? I'll try recreating your example using my library when I find the time.

[manthrax]

@SebiTimeWaster can your csg implementation handle texture coordinates?

[looeee]

Here's how texture coordinates look in mine.

Here's the repo:
https://github.com/looeee/threejs-csg

There are two branches, master, which is pretty close to a wrapper of csg.js as I described above, and advanced. There I've expressed all the CSG operations using the LogicalOR and complement methods:

Union: (Left || Right)
Subtract: !(!Left || Right)
Intersect: !(!Left || !Right)

Doing that makes the operations a bit easier to reason about and also makes subtract and intersect slightly faster. There are also some experiments with doing a high-level bounding box based merge and cull before doing the full CSG operations, which gives some decent speedups when performing many operations at once.

A better approach, however, and what seems to be most used in other implementations, is to create a BVH of geometries and operations and traverse the tree to generate the final geometry.

@SebiTimeWaster for now I've decided to look into alternative CSG implementations rather than go further with this one. If there's anything useful from my repo feel free to take it.

EDIT: This tweet sums up my feelings exactly

[gkjohnson]

It looks like the source for the Realtime CSG plugin for Unity that I linked above has been posted on Github and is MIT licensed if anyone is interested in taking a deep dive into that:

https://github.com/LogicalError/realtime-CSG-for-unity

He also has some technical posts about his CSG plugin on his blog, too, if you go back bit:

https://sandervanrossen.blogspot.com/search?q=Realtime+CSG

There was also a newer GDC talk from him back in March this year on CSG:

https://www.youtube.com/watch?v=Iqmg4gblreo

I haven't messed around with his work in Unity myself but the performance in videos looks great.

[looeee]

There's also this one which is based on the Unity CSG but is a standalone C# app, it might be easier to understand. It's quite a bit older though so it may not be as developed.

https://github.com/LogicalError/Realtime-CSG-demo

Godot engine also has CSG which I tested out and it has very decent performance. docs / code.

There's also Carve CSG and xcsg (which uses Carve), and Cork.

I wonder if the best solution here would be to take one of these existing solutions (probably Carve since it's CPP and seems to be used in lots of other packages) and convert it to Wasm.

[gkjohnson]

I wonder if the best solution here would be to take one of these existing solutions (probably Carve since it's CPP and seems to be used in lots of other packages) and convert it to Wasm.

I'm less familiar with emscripten but that doesn't sound like a bad approach. It looks like Carve and Cork are GPL and LGPL licensed, though, so that's something to keep in mind.

[gkjohnson]

Apparently Blender has just updated it's boolean operations tool and according to this tweet uses approaches from this paper:

http://www.cs.columbia.edu/cg/mesh-arrangements/

[bmays87]

@looeee Your latest work looks good. I was considering generating obj files server side in Unity on the fly and sending them to three.js for rendering but the overhead just to generate an obj file and send it is immense. The work you are doing no doubt is the better approach. I keep wanting to get more involved with web assembly though, I wonder how easy it would be integrate with three.js.

[giladdarshan]

I've tested several CSG libraries (three-csg, ThreeBSP, three-csg-ts, etc) and all seem to have issues, I'm now using THREE-CSGMesh for the subtract and intersect functions only as the union function gave weird results when using cylinders.

For the union function I ended up writing my own using BufferGeometryUtils.mergeBufferGeometries:

function union(obj1, obj2) {
    try {
      if (arguments.length < 1) {
        return;
      }
      obj1.updateMatrix();
      obj2.updateMatrix();
      let geometriesArr = [];
      let obj1Geometry = obj1.geometry.clone();
      obj1Geometry.applyMatrix4(obj1.matrix);
      geometriesArr.push(obj1Geometry);
      obj1.geometry.dispose();
      obj1.material.dispose();
      let obj2Geometry = obj2.geometry.clone();
      obj2Geometry.applyMatrix4(obj2.matrix);
      geometriesArr.push(obj2Geometry);
      obj2.geometry.dispose();
      obj2.material.dispose();
      let newGeometry = BufferGeometryUtils.mergeBufferGeometries(geometriesArr);
      let newObj = new THREE.Mesh(newGeometry, new THREE.MeshBasicMaterial({color: 0xffff00}));
      return newObj;
    }
    catch(e) {
      console.error(e);
      return;
    }
  }

I'm now trying to figure out how to remove all the internal faces from the merged object.

[manthrax]

@giladdarshan possibly related to your request: manthrax/THREE-CSGMesh#13 (comment)

The mesh resulting from CSG operation should have 2 vertex groups.. the first group contains the triangles contributed by A and the second group, the triangles of B.

[napter]

It's been a while since there has been active discussion on this. Any idea which is the most robust/stable?

For those of you that have implemented a library, which did you go with? @SebiTimeWaster @looeee did you ever finish your stress tests?

[giladdarshan]

Hey @napter, I'm working on a new CSG library and should be making it public very soon, it works well from the testing that I did.
If you would like to test it beforehand let me know, could use more testers.

[svdHero]

I have the same question as @napter. Which library is recommended these days for CSG? The one by @SebiTimeWaster, @looeee or @manthrax? Is there any overview or short comparison between the three libraries listing pros and cons?

[looeee]

@svdHero the issue with all the CSG libraries listed here is that they are extremely slow. I stopped working on mine because I came to the conclusion that there was no way to make it real time without a BVH, which didn't exist at the time for three.js.

However, I believe since then @gkjohnson has written both a BVH library and a CSG implementation based on it. I don't know how complete the CSG part is, but if performance is important to you I expect this is an order of magnitude faster than anything else here so I would test that first.

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

[giladdarshan]

If anyone is interested, I've published the Octree based CSG library I have been working on - https://github.com/giladdarshan/OctreeCSG.

I will be working on adding examples for both basic usage and advanced (complex geometries, real time, etc).

[Mugen87]

I think this issue can be closed now after adding webgl_geometry_csg.