exported stl object is not sliceable with slic3r about csg.js HOT 15 CLOSED

ok so the issue is that the triangle mesh that is created by csg.js does not respect the "Vertex-to-vertex rule" that is described on http://www.fabbers.com/tech/STL_Format

when I manually force this rule in the stl file (by re-organizing the triangles), the file is correctly handled by slic3r.

I found many references to this "vertex-to-vertex" rule and The following pdf - https://www.cs.cmu.edu/afs/cs/academic/class/15294-s15/lectures/stl/stl.pdf - gives 3 rules for STL generation

1. Triangles are flat (planar). To make a curved surface, use more triangles.
2. Every vertex belongs to at least two triangles.
3. No vertex can touch an edge of another triangle.

Looking at the file generated in the above example, It seems that rule number (3) is not respected by csg.js.

The good things is that these rules can be tested. Rule (2) is easy to test. Rule (3) needs a bit of thinking probably because we are supposed to detect when a vertex "touches" the inside of an edge, and this probably needs to be done with a level of precision because line interpolation is always subject to precision issues.

I'll take a look at csg.js to see if I can understand the way it decides to cut the mesh. For those who know the internals of csg.js, have you already studied this problem ?

from csg.js.

After a first look, I am not so sure anymore that csg.js is the problem. It seems that the polygons handled by CSG.js sometimes (always?) have 4 vertices. This is what seem to appear in the extrude method that creates sidepolygons with 4 vertices. I first thought that CSG.js was working on triangle meshes but that does not seem to be the case.

from csg.js.

After printing the list of CSG polygons after the subtract operation in the above example, the polygons are all rectangles. The upper face could be drawn as

eeeee
aaobb
qqqqq

where e, a, b and q are rectangles.

If we reason here on the "vertex-to-vertex" rule, the problem is already present because the e and q rectangles are adjacent to o and there is a vertical rectangle (the hole in the cube) that touches the inside of the borders of e and q

So either e and q should be split already at this stage, or it is at a later stage, when transforming the polygons into a triangular mesh, that they should be modified. Looking at the triangular mesh given by jscasd, it seems the rectangle are only split in 2. I'll check that later.

from csg.js.

Thanks for the information, I'll take a closer look tonight.
Yes CSG.js polys are n-gons, and are explicitely triangulated when needed (if I recall the details correctly)

No vertex can touch an edge of another triangle.

Ok then I believe I might know where the issue comes from : "canonicalization" ie elimination of redundant or semi redundant (read : same or very close vertices) is not done correctly

btw I looked at both csg.js & the binary stl serializer : https://github.com/jscad/io/blob/master/packages/stl-serializer/CSGToStlb.js#L14
The serializers just go over the polygon lists in a linear fashion, so the error is indeed present before that it seems

from csg.js.

Viewing the model in wireframe it would seem these un split triangles are the issue

from csg.js.

Yes, when looked at the csg stage, this face has 2 long rectangles and 2 small ones. At the stl stage, each rectangle is split in 2 by along diagonals.

This leads to the incorrect mesh you show on the wireframe. (btw, what did you use to generate the wireframe?)

from csg.js.

I tried to understand the csg.js code (which is indeed hairy..maybe for good reasons, but hard to follow).

What comes out of it is that the clipTo operation tries to optimize the number of plane cuts :

• it iterates over each polygon (P) in the big cube
• For a given P, it BSP-iterates over the polygons (p) of the small cube.
• When the plane of p cuts P, it separates P into 2 polygons : one (f) in the front of p, and one (b) in the back of p.
• Then, because the small cube is organized as a BSP, the next polygon in the iteration over the small cube is either on the front or back of p. For topological reasons, the algorithm will check for intersections between f and the small cube polygons in the front of p, between b and the small cube polygons in the back of p, but never between f and back or b and front.

This explains why the top face, after the hole is cut in the big cube, is cut the way it is :

• 1 long band along west of the hole + 1 the rest
• the rest is cut with 1 long band along the east of the hole + the rest
• the rest is cut with 1 small rectangle north of the hole + the rest
• the rest is cut with 1 small rectangle south of the home + the rest (the hole)

When these rectangles are exported as STL, the algorithm simply creates 2 triangles along a diagonal.

I don't know if there is a simple modification of the algorithm that could improve the situation.

from csg.js.

This issue may be related to the fixTJunctions method that was introduced, since we could consider the "problems" in the current partition could correspond with the definition of TJunctions in the code.

So this would be a post-operation to call on the CSG tree to "fix" things before the STL export.

from csg.js.

And this fixes the issue :-)

So I simply called the fixTJunctions() method just before the STL generation and it fixed my problem in slic3r.

Well I learned a lot in the process (and now I understand why the CSG.js refactoring is a lot of work ;-)

I really like openjscad ! thanks a lot for migrating it to npm it.

thank you @kaosat-dev for your help on the issue I probably would have stopped digging without your orientation.

I'll close the issue to avoid keeping open issues. Maybe we would need a documentation section of the CSG/STL impedance mismatch and potential issues (but maybe it already exists)

from csg.js.

wow thanks for the very in-depth analysis @jeromew ! (and sorry for the slow reply)
Mind if I put this somewhere in the documentation ?
(to view the stl I just used the first google result :)

About fixTJunctions and the stl output : ahhhh of course, I feel so daft now, Tjunctions are exactly what we are seeing in the issue ! Well done !

I personally really dislike this state of things: fixTJunctions feels like an implementation detail : perhaps all writers (stl & co) should call fixTJunctions on the input object to make sure we always get a coherent triangulated mesh.

Thanks for the kind words :) and I hope you will stick around, the more people with in -depth knowledge and the willingness to dig into the code we have , the better we can improve things !

About the CSG.js refactoring/ upgrade: I am still on the fence between creating a new implementation from scratch that respects the current API to a large extent or trying to improve the current code base haha

from csg.js.

Feel free to use the analysis somewhere if you know of a good place for this.

It is hard to know what would be the good path regarding the refactoring. Rewriting from scratch is neary alway much longer than anticipated. I haven't looked at the code coverage of the tests (cf something like https://www.npmjs.com/package/istanbul). Starting a full rewrite without a near-100% coverage is risky because corner cases keep popping up and the rewrite sometimes ends up as complex as the initial code ;-)

Before any full rewrite, csg.js would probably need more tests / more understanding of its inner workings

Based on a shared API there could be competing engines that try to optimize the operations but it is hard to know if this could become a reality.

The modularization that you have started is already a great start for refactoring and separation of concerns of the different modules.

from csg.js.

Both Mark and I agree that the test cases are insufficient at this time. There are some gaps that we need to close.

And of course, we would appreciate some contributions. :)

from csg.js.

We are actually running Istambul to get code coverage together with the tests, you can check the results out in the various PRs in the travis CI tests: theoretical coverage is in the 70% ballpark , although given all the things that recently broke without breaking tests, take that with a BIG pinch of salt.

But that aside , yes , we all agree that we need more testing & understanding :)
I did a quite extensive re-factoring in coffeescript a few years back, and had good understanding of the innards, but that is a bit lost :)
I agree that a full rewrite would take longer, but I also have the case on some projects where we favored progressive updates to the code base, and it turned out to be a really bad idea (huge technical debt, endless changes on brittle basis).

The whole maths base of JSCAD is also bothering me a lot , because it is quite filmsy , and done better in other libs (three.js, gl-matrix etc).

Based on a shared API there could be competing engines that try to optimize the operations

That was my original plan for this summer: creating different experimental 'back-ends'/ cores , including some based on wasm & webgl for really fast and more reliable numerical operations, but my rather crappy personal situation might prevent that.

from csg.js.

yes as an opensource project it is always hard to start projects with a tunnel effect risk and it can be hard at times to make commitments. I hope you sort out your situation.

replacing the math base with an existing library might be a first good goal to benefit from an optimized layer on this rather than re-invent the wheel.

I agree that in-place refactoring needs a milestones because otherwise many partial things happen simultaneously and you end up with increasing the technical debt.

from csg.js.

Maybe we should close this thread and open another one specific to a choice of libraries that could help decrease the csg.js footprint ?

from csg.js.