Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

t-junctions #13

Open
pyalot opened this issue Jul 20, 2014 · 16 comments
Open

t-junctions #13

pyalot opened this issue Jul 20, 2014 · 16 comments

Comments

@pyalot
Copy link

pyalot commented Jul 20, 2014

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
Copy link
Author

pyalot commented Dec 4, 2014

This is still an issue.

@bhouston
Copy link

bhouston commented Jan 2, 2015

@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
Copy link

@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
Copy link

NateTG commented Feb 27, 2015

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
Copy link

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
Copy link
Author

pyalot commented Mar 4, 2015

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
Copy link

NateTG commented Mar 5, 2015

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
Copy link
Author

pyalot commented Mar 5, 2015

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
Copy link

NateTG commented Mar 5, 2015

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
Copy link

bhouston commented Mar 6, 2015

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
Copy link

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
Copy link

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
Copy link

bhouston commented Mar 9, 2015

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
Copy link

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

@z3dev
Copy link

z3dev commented Mar 20, 2017

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
Copy link

z3dev commented Mar 21, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

7 participants