Missing features and bugs in compute_CSG

[BrunoLevy]

compute_CSG does not work on all file inputs

file	exact_nt	expansion_nt
example001.csg	OK	OK
example002.csg	OK	OK
example003.csg	OK	OK
example004.csg	OK	OK
example005.csg	OK	OK
example006.csg	OK	OK
example007.csg	OK	OK
example008.csg	OK	OK
example009.csg	OK	OK
example010.csg	OK	OK
example011.csg	OK	OK
example012.csg	OK	OK
example013.csg	OK	OK
example014.csg	OK	OK
example015.csg	OK	OK
example016.csg	OK	OK
example017.csg	OK	OK
example018.csg	OK	OK
example019.csg	OK	OK
example020.csg	the "snake" around the scene lacks resolution	idem
example021.csg	OK	unstable (sometimes OK, sometimes radial sort errors)
example022.csg	OK	radial sort error
example023.csg	OK	OK
example024.csg	OK	radial sort error

[BrunoLevy]

done
Still unclear to me the difference between union() and group() in a CSG file (so I'm doing a union in each group, but it may cost something ...).
Anyway, need to add meshwide bbox test to avoid doing too many intersection tests
(example006.csg now takes twice the time, for nothing...)

[BrunoLevy]

done
OK, back to the initial timing by keeping bboxes with objects, and using them to detect that there is no need of computing intersections if they do not overlap.

[BrunoLevy]

done
Implemented modifiers (!,#,%,*).
'#' required changing the configuration of stb_c_lexer (by default, it removes preprocessor directives !)

[BrunoLevy]

done
Something crazy happens with this file (pirate ship), especially with the coplanar triangles in the sails. Need to investigate. And also, OpenSCAD is faster on this one !

Problem was in computing approximate points / snap rounding: since points are in homogeneous coordinates, the same point can be represented in different ways and snapped to different floating-point numbers !!

[BrunoLevy]

done but to be understood
Sometimes radial sort reports coplanar facets, which should not occur since radial sort is done after intersection.
It happens in brio_splitter_round.stl from thingi10K, and also in pirateship.1.csg during compute_CSG.

Let us take a closer look at brio_splitter_round.stl

• visual inspection: difficult to see anything (the involved triangles are very skinny...)
• deactivate interval filters ? Nope
• How do we merge duplicated triangles after intersection ? Do we use inexact geometry ? Does not seem so.
• radial_3830 seems to be less degenerate than the others. We need a tool in Graphite to center the view on a picked point... Well, by visual inspection, one of the facets really looks like it has its three vertices aligned.
• Check for aligned vertices programatically using exact coordinates: bingo ! (it is nearly systematic, but not always, there is an occurence of ** in pirateship.1.csg that does not trigger the aligned vertices test, so there might be also another bug). Let us now take care of the triangle with three aligned vertices for now:

We are here: one of the previous phases of the algorithm creates a facet with three perfectly aligned vertices. So for the next step, we just need to check for such degenerate facets at different checkpoints in the algorithm.

• Oh, it seems we do not have the problem if normalize_ is set to false, but why is this so ??? (pirate_ship.1.csg is happy too !!!). Need to understand what's going on... pirate_ship.1.csg takes 11 seconds (and OpenSCAD takes 9 seconds on it).

• That's interesting, example006.csg with normalize_ set to false sometimes fails in classification for the difference operation. It is probably because a (random) ray traverses a vertex exactly. Need to handle this case properly...

[BrunoLevy]

done but to be understood
sotc.csg gives a different result in geogram and in OpenSCAD ( I get two spurious floating rings of cubes above and below the cylinder).

Did not see that problem again.

[BrunoLevy]

TODO infinite loop in connected component classification by ray-tracing

• example022.csg and Round_Ducting.csg (loooong, seems to be at line 1143 -> extracted it -> seems to be elsewhere in fact ...) go in an infinite retry loop when raytracing connected components (for example022.csg, it is in expansion_nt mode)

  • extracted Round_ducting_problem.csg. Sometimes I get the infinite loop, sometimes not.

• coordinate exponent scaling break facets coplanarity (even in exact_nt mode), why is this so ???

• dragon7.csg has the problem (but it is at the very end, after a looooonng computation)

[BrunoLevy]

WIPs:

• radial sort by-propagation Yay, unexpectingly this one was not a small thing
• re-factor radial sort by-propagation with a CIEL class
• ExactCDT2d
• Merge co-planar facets
• Parallel merge co-planar facets
• Correct orientation
• Faster component ray-tracing with AAABB, try 6 trivial directions first
• CSG profiler (for each line, gets line time and cumulated time)
• Finer verbosity control (in particular, Intersect and RadialSort on/off)
• 2D primitives, 2D CSG
• multistep linear extrusion
• circular extrusion
• extract STEP files using OpenSCAD. Possibly spawning an external process. Generate simple linear extrusion, convert it into STL using OpenSCAD, load the STL, discard the triangles with non-zero Z.

[BrunoLevy]

dragon7.csg creates a mesh with 0 facet in it, it is weird, it is a union (of three small meshes, probably cubes or something like that).
It is in fact cubes with size 0, it is used as an input to hull right after (ooohhh that's not elegant).

[BrunoLevy]

fractal_sierpinsky_spiral_4.csg has a 2D classification problem right at the end (assertion fail v1 != -1), we are not completely done with CoplanarFacets it seems !!

[BrunoLevy]

2D boolean operations start to fly, but we have some problems:

• example020.csg:
  • some curves are floating around: OK, need to call mesh_->edges.clear()
  • the nut and the bolt need the twist parameter of linear_extrude (and also multiple steps in extrusion)
  • the big "snake-like" shape around need mesh refinement (very large rotation)
• fractal_sierpinsky_spiral4.csg assertion fail v1 != index_t(-1) (or v2, v3), line 1927 of mesh_surface_intersection.cpp (meaning that in the classified triangles, one of them is incident to one of the corners of the quad surrounding the triangulation. Normally this should not happen...)
• cycloidalGear.csg, remove_isolated_vertices, index out of bounds. Yep, one of the polygons seems to have an index out of bounds. Fixed code to detect invalid vertices (bound was not correct). OpenSCAD ignores such vertices, but I prefer to consider this a fatal error.
• example015.csg assertion fail newk == k in CDT2d.cpp (probably compute_intersection() that is not correct !)
  mix() for vectors with homogeneous coordinates was wrong !
• globoidworm.csg misses some intersections and displays INTERNAL BORDER messages. (was multmatrix() for 2D meshes)
• module_recursion.csg triggers 'point outside boundary' (was multmatrix() for 2D meshes)
• hoopwing.csg has wrong orientation for one of the halves ??? (xform matrix with negative det ? but normally should not do that ?). Yes it is, and yes it does that, if the multmatrix() with the negative determinant matrix is the topmost operation.
• now keeps only the outer boundary for 2D CSG operations, but it seems that sometimes I get nothing, for instance with ambicylinder.csg and with 200_stars_with_support.csg (fixed: of course, I needed to keep the triangles when I have triangulated a contour right before linear_extrude() !
• example015.csg, support origin and scale in import()
• Lathe/Uprights.csg, 2D CSG goes crazy (select (!) first linear_extrude()) (was coming from missing optim of number representation after intersection in 2D exact triangulation)
• box.csg, some in/out classification errors in the honeycomb-like cover, but not always (!) Valgrind sees many things !! OK, it was multmatrix() that needed to take into account meshes of dim 2.

[BrunoLevy]

done (but todo: double check interval_nt for FPEs)
seems that I get sometimes an infinite loop in CDT2d with;

• Lathe/Transmission_v2/Idler_gear.csg)
• Lathe/Chuck/PlanetGears.csg
• Lathe/Transmission_v2/CenterGears.csg, FPE

So I extracted from Idler_gear.csg a minimalistic example with a small number of polygons: weird_wing_2d_simple.csg
It seems that it generates veeerry small numbers. It triggers FPE in interval arithmetics.
I deactivated the arithmetic filters in orient2d() and incircle2d(): still takes forever, and still triggers an FPE, much later, but this time in exact_nt::estimate() this one is easy to understand and to fix: (PCK::approximate(vec2HEx) -> ldexp() with too small exponent -> N.exp() -= D.exp(); D.exp() = 0.0).

With the filters deactivated, in debug mode, obtained the correct result (but took a super long amount of time). I guess that we are manipulating super long numbers under the hood.

Now works with weird_wing_2d_simple.csg with the filters activated. It is weird, because the only other change I've made is in PCK::approximate(), and the computation occurs before. But well, I could get a result before, and it was not looking correct, so it probably explains (result was already correct, but it is PCK::approximate() that was underflowing).

Also works with Idler_gear.csg, takes a HUGE amount of time (1256 seconds for just a tiny gear !!). I suspect mix() to be the culprit, with its D-N factor. Let's try to balance exponents between D and N -> nope (anyway we do things with N-D and things with D...)

Still need to understand where it is spending all the time ! (track very long numbers in exact_nt). sysprof says that exact_nt product is eating up all the time !

OK, Numeric::optimize_number_representation(Vec2HEx) was not implemented (stupid me).

And it is also better to take the original extremities of the constraints rather than the edge vertices passed to create_intersection().

[BrunoLevy]

fixed
Problems in evaluating number of segments,
examples:

• KleinBottle.csg
• Presentation/15_FamilyTreePendant.csg

[BrunoLevy]

understood surface was not closed, tiny mismatch between some vertices on sharp creases
FAT_KNOB.stl, simplify_coplanar_facets kills too many facets !!

• Facet group incident to facet 25 has wrong keep vertex attribute.
• Facet group incident to facet 25 has incorrect borders (many missing edges and vertices)
  Well, in fact surface is not closed ! (has tiny gaps, irregularly placed on sharp creases)
  Works by pre-merging vertices with tolerance (epsilon =1e-3)
  TODO Add diagnostic message when surface is not closed.

[BrunoLevy]

TODO sphere discretization is not exactly the same as in OpenSCAD: OpenSCAD does not generate poles, it generates a small polygon around each pole (shifted by half a period as compared to geogram).

[BrunoLevy]

Fixed
incircle2d with homogeneous coordinates with expansions and different w's seems to be broken (for instance, example005.csg, triangulation of the ceiling is obviously non-Delaunay). It may come from:

• operator+ / operator- combining vec2HE / vec3HE with different w factor
• expression of the predicate with different w factors, taking into account the signs of w

Investigating:

• Same result when deactivating interval filter.
• Same result when deactivating BIG_STACK
• Create simplest example that has the problem, starting from example005.csg and making it as simple as possible. It seems that it happens when there are points created from intersections.
• Do we have a clockwise/counterclockwise problem ? Double-checked formulas, I do not think so.
• Does it come from l = approx(x^2+y^2+z^2)/approx(w^2) instead of approx((x^2+y^2+z^2)/w^2) ?
• Does weird things with one single cylinder (but of course, these are cocyclic points))
• Let us see whether re-injecting the same formula in the exact predicates version gives the same result (do we have a formula error or a numerical precision problem ?). (Mostly) the correct result is obtained, this lets me think that the formula is correct, and that expansion_nt simply does not have sufficient range to implement incircle2d with generated points. It is only mostly the correct result probably because of the approximation (x^2+y^2).estimate() / (w^2).estimate(). But it is seemingly sufficient to ensure the uniqueness of the triangulation (at least experimentally)
• gotcha length_ is not in sync with points (not the same number of elements). Simply forget to clear it in ExactCDT2d::clear() (I'm stupid !!!)

Stats with simple example extracted from example005.csg:

Predicate stats for: incircle_2d_SOS_with_lengths(vec2HE)         
                         invocations :         7170                                     
                          filter hit :         6364 (88.76 %)                           
                               exact :          806 (11.24 %)                           
                                 SOS :          271 (3.78 %)  

[BrunoLevy]

Bug
Sometimes connected component classification by raytracing enters an infinite loop (example022.csg). Behavior also reported by Cedric. Happens with both expansion_nt and exact_nt

[BrunoLevy]

Bug
With expansion_nt, behavior is not reproducible, sometimes I get radial sort errors, sometimes not, on the same input files, depending also on whether I activate multithread or not.

• some of this behavoir came from the incircle2d bug mentioned above: length_ array was not cleared on ExactCDT2d::clear().
• but does not explain everything, we still have example021.csg that has unstable behavior with expansion_nt

[BrunoLevy]

Fixed
simplify_coplanar_facets() stops at chart boundary, we could do that through charts.
To do that, we need to re-connect the facets incident to manifold edges right after classification.
... but I'm calling mesh.facets.connect() and the end of classify(), so there is something weird here ! (maybe orientation is not correct). To figure out, save the result right at the end of classify...

Ah, OK, it is not classify(), it is remove_internal_facets() (and mesh_.facets.connect() was missing in there)

[BrunoLevy]

Bug
2D classification error after CDT in simplify_coplanar_facets() with:

• gallileo_rtg.stl
• 132432.stl
• 107543.stl
• 106838.stl

Investigation strategy:

• save input and triangulation output, examine
• created galileo_problem.stl with one of the gears-like shapes that has the problem, then I made two observations:
  • the set of borders of the set of coplanar facets is not a closed curve (!)
  • some segments of the set of borders do not appear as constraints in the CDT

Rewrote more elaborate data structure with 2D CIEL
Found something:

• 1_to_3_stages_kit.stl, same halfedge encountered in two different contours
• two indicent triangles that do not satisfy vertex indexing -> gotcha there are three triangles incident to the same edge, it comes from Mesh.facets.connect() that does not check for this type of configuration.

Understood something Some meshes have pairs of triangles sharing the same three vertices, and then Mesh.facets.find_adjacent(f1,f2) is ambiguous -> replaced it with Mesh.facets.find_edge(f,v1,v2).

Understood something else Sometimes I got triangles that are coplanar, but that have opposite orientation, then they should not be inserted in the same facet group. Note: this should not happen !!, because it means the result of the intersection still has intersecting triangles, this needs more investigation.

I think I sometimes also get sets of triangles considered to be coplanar along some edges and not along some other edges...