Open BrunoLevy opened 10 months ago
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...)
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.
done Implemented modifiers (!,#,%,*). '#' required changing the configuration of stb_c_lexer (by default, it removes preprocessor directives !)
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 !!
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
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.**
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...
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.
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)
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)
WIPs:
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).
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 !!
2D boolean operations start to fly, but we have some problems:
example020.csg
:
mesh_->edges.clear()
twist
parameter of linear_extrude
(and also multiple steps in extrusion)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. 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.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
, FPESo 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()
.
fixed Problems in evaluating number of segments, examples:
KleinBottle.csg
Presentation/15_FamilyTreePendant.csg
understood surface was not closed, tiny mismatch between some vertices on sharp creases
FAT_KNOB.stl
, simplify_coplanar_facets
kills too many facets !!
keep vertex
attribute.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).
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
factorw
factors, taking into account the signs of w
Investigating:
example005.csg
and making it as simple as possible. It seems that it happens when there are points created from intersections.l = approx(x^2+y^2+z^2)/approx(w^2)
instead of approx((x^2+y^2+z^2)/w^2)
?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)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 %)
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
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.
incircle2d
bug mentioned above: length_
array was not cleared on ExactCDT2d::clear()
.example021.csg
that has unstable behavior with expansion_nt
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)
Bug
2D classification error after CDT in simplify_coplanar_facets()
with:
gallileo_rtg.stl
132432.stl
107543.stl
106838.stl
Investigation strategy:
galileo_problem.stl
with one of the gears-like shapes that has the problem, then I made two observations:
Rewrote more elaborate data structure with 2D CIEL Found something:
1_to_3_stages_kit.stl
, same halfedge encountered in two different contoursMesh.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...
compute_CSG
does not work on all file inputs