t-junctions

[pyalot]

It'd be good to have a way to get rid of t-junctions in CSG.js, as these will introduce mesh cracks/pixel flickering because of the difference in floating point precision in a shader and a rasterizer.

[pyalot]

This is still an issue.

[bhouston]

@pyalot It seems that this library is unmaintained, and has been for years. Maybe someone should fork it and take it over. There are quite a number of bugs in it.

[alokmenghrajani]

@bhouston Do you have a suggestion for a better CSG library? I'm experimented with the creation of STL files (which I then printed on a 3d printer) from the output of this library. My test objects are of the form: shapeA.subtract(shapeB) where shapeA and shapeB are perfectly closed and made of lots of tiny triangles.

My result contained degenerated triangles and holes. I was able to fix things in a post processing step, but I would prefer to get accurate results in the first place. My initial idea is to modify this library to compute bounding boxes and limit the number of triangles which get modified in the subtraction computation. What do you think?

[NateTG]

Some other projects - like openjscad - seem to have a more developed version of this library. I'm not sure whether the changes address your issue though.

Also, what's a t-junction?

[alokmenghrajani]

Thanks, I'll try openjscad. I looked at the code, and it seems to have the same/very similar API, which is nice for me.

openjscad's code has a good explanation for t-junctions:
(source https://github.com/Spiritdude/OpenJSCAD.org/blob/master/csg.js#L1289)

Suppose we have two polygons ACDB and EDGF:
 A-----B
 |     |
 |     E--F
 |     |  |
 C-----D--G
Note that vertex E forms a T-junction on the side BD. In this case some STL slicers will complain
that the solid is not watertight. This is because the watertightness check is done by checking if
each side DE is matched by another side ED.
This function will return a new solid with ACDB replaced by ACDEB
Note that this can create polygons that are slightly non-convex (due to rounding errors). Therefore the result should
not be used for further CSG operations!

[pyalot]

It's possible in theory to fix t-junctions post-hoc (after CSG is trough). In practice this isn't feasible because it requires locating those vertices which fall inbetween two other vertices on an edge and devise a division strategy for the touched polygons. This is fairly expensive (O(n^2) expensive).

[NateTG]

This is fairly expensive (O(n^2) expensive).

Maybe I don't understant the interal format, but is it really that bad? If you walk the edges, seems like you should be able to make a list of 'unpaired' edges in O(edges), and then (assuming that there are no colinear overlapping t-junctions) patching them out should be O(t-junctions).

[pyalot]

In order to find splitting points you need to go over each edge and find each vertex that falls within that edge. So you're testing N vertices for being on M edges. This is essentially a spatial search. The same strategies to address spatial search acceleration do apply to this problem.

However, there's a second issue. Even if you have a fast algorithm to perform that function, that does not exclude that vertices might be identified as splitting, which actually are not. This can happen with degenerate geometry, when corners of primitives touch, etc. At the time that you would perform t-junction elimination, too little information is present to perform that task perfectly.

[NateTG]

In order to find splitting points you need to go over each edge and ...

I think that approach is more complicated than necessary.

In the description, a slicer checks for 'bad sides' by seeing if every side DE is matched by a side ED. That check for 'bad sides' can be done constructively in worst case O(sides log sides) time by making a sorted list of the sides and removing the 'good sides' from the list.

Assuming the underlying geometry is "manifold" every side that is involved in one of these 't-junctions' will be in that list of 'bad sides'. So you only need to check vertices and sides that are involved in that list. What's more, the t-junctions will form cycles of bad sides, which can be found by 'walking' through the sorted list of bad sides in O(t-junctions log t-junctions) time.

[bhouston]

What we could do is fork this to a repository and then start adding unit
tests for the problematic cases -- I was the one that wrote most of the
unit tests for ThreeJS's math library.

I can host it on github.com/Exocortex/csg.js and add you guys as full
contributors -- it won't be held by me personally. We've made some fixes
to csg.js privately as well.

-ben

Best regards,
Ben Houston (Cell: 613-762-4113, Skype: ben.exocortex, Twitter:
@exocortexcom)
https://Clara.io - Online 3D Modeling and Rendering

On Thu, Mar 5, 2015 at 10:26 AM, NateTG [email protected] wrote:

In order to find splitting points you need to go over each edge and ...

In the description, a slicer checks for 'bad sides' by seeing if every
side DE is matched by a side ED. That check for 'bad sides' can be done
constructively in worst case O(sides log sides) time by making a sorted
list of the sides and removing the 'good sides' from the list.

Assuming the underlying geometry is "manifold" every side that is
involved in one of these 't-junctions' will be in that list of 'bad sides'.
So you only need to check vertices and sides that are involved in that
list. What's more, the t-junctions will form cycles of bad sides, which can
be found by 'walking' through the sorted list of bad sides in O(t-junctions
log t-junctions) time.

—
Reply to this email directly or view it on GitHub
#13 (comment).

[waldyrious]

I'd suggest setting up a dedicated organization (e.g. github.com/csg.js/csg.js), to better indicate its status as the community-agreed canonical repo.

[alokmenghrajani]

I personally think it would make most sense to look for the same/similar problems in openjscad and create the unit tests there if needed.

[bhouston]

I've created a new repository fork here: https://github.com/csg-js/csg.js If anyone wants to join me, ask for admin rights. I only ask that you do not remove me as an admin.

[isaachadad]

I have been struggling with the same issue, and is extremely important for me.
Any update here?

[z3dev]

There's an organization now, which includes CSG.js library. See jscad/csg.js

All are welcome to contribute, and there a set of test case being developed as well. @dav-m85 is already contributing.

[z3dev]

JSCAD continues to grow, and has some great plans. Please contribute there.