Downgrade WARNING: PolySet -> Manifold conversion failed

[kintel]

We currently issue a warning if someone tries to specify a polyhedron which does not represent a manifold topology:

WARNING: PolySet -> Manifold conversion failed: NotManifold
Trying to repair and reconstruct mesh..

This warning feels a bit intimidating, and it also disrupts a bunch of existing designs and libraries (see e.g. discussion in #5134).

We should consider downgrading or silencing this warning in cases where merging co-incident vertices yields a valid manifold without having to repair/reorient the mesh.

Example: Closed extrusion where the first and last cross section is repeated:

polyhedron(points = [
  [2.02196e-17, 19.8, 1],
  [-2.02196e-17, 20.2, 1],
  [-2.02196e-17, 20.2, -1],
  [2.02196e-17, 19.8, -1],
  [10.8034, -1.52112, 1],
  [11.16, -1.70232, 1],
  [11.16, -1.70232, -1],
  [10.8034, -1.52112, -1],
  [-10.8034, -1.52112, 1],
  [-11.16, -1.70232, 1],
  [-11.16, -1.70232, -1],
  [-10.8034, -1.52112, -1],
  [2.02196e-17, 19.8, 1],
  [-2.02196e-17, 20.2, 1],
  [-2.02196e-17, 20.2, -1],
  [2.02196e-17, 19.8, -1]
],
  faces = [[0, 5, 4],
  [0, 1, 5],
  [1, 2, 5],
  [5, 2, 6],
  [2, 3, 6],
  [6, 3, 7],
  [3, 0, 7],
  [7, 0, 4],
  [4, 5, 8],
  [8, 5, 9],
  [5, 6, 9],
  [9, 6, 10],
  [6, 7, 10],
  [10, 7, 11],
  [7, 4, 11],
  [11, 4, 8],
  [8, 9, 12],
  [12, 9, 13],
  [9, 10, 13],
  [13, 10, 14],
  [10, 15, 14],
  [10, 11, 15],
  [11, 8, 15],
  [15, 8, 12]
],
  convexity = 2);

[adrianVmariano]

Is there a disadvantage to relying on OpenSCAD to merge duplicate vertices? (The one obvious disadvantage would be that it could in some circumstance produce an incorrect or invalid result.) I think I favor the idea of an informational comprehensible message that says "Duplicate vertices in model were merged" or something to that effect vs just being completely silent about the matter.

[kintel]

As of today, it's not just a question of duplicating vertices. If a non-manifold topology was specified we'll do a bunch of stuff to try to ingest it:

• Quantize vertices to a grid
• Triangulate all polygons
• If the geometry was convex, try to apply a convex hull
• reorient faces which were pointing the wrong way (could also happen due to quantization)

We could split that up into a naive vertex merge first, and if that fails, issue said warning and try to repair.

[adrianVmariano]

Are non-triangular polygons considered a fault? This has always been a point of uncertainty for us, as it seems like there are rare cases where non-triangular coplanar polygons fail, but usually they are OK. (I suppose there is the question about how accurately coplanar a non-triangular polygon is.)

[kintel]

Non-triangular polygons are OK, but there's always a chance that a polygon isn't planar. Triangulating ensures that. ..plus Manifold requires triangles.

[adrianVmariano]

What happens if you feed it a non-coplanar polygon?

[kintel]

We'll just make a decision for you how to combine the vertices into triangles.

[DougPollard]

I was worried when @kintel first mentioned the steps that would be taken if the polyhedron was non-manifold and wondered if it would be more efficient to just eliminate the duplicate vertices in BOSL. So I ran a simple test on a project I'm working on right now. I am generating a closed polyhedron via path_sweep() and vnf_polyhedron(), similar to my original example code, except much closer to planar in appearance. Then I merge a number of these into a nxn mesh to create a weave pattern. For now the result is basically planar but eventually this mesh itself will be wrapped around 3d shapes. Anyways, for a few values of n I ran this, accepting the current Manifold warnings, but successful rendering; and I ran it again except inserting vnf_merge_points() around each result of path_sweep() before passing to vnf_polyhedron. Every test was run after flushing caches.

       n       BOSL        Manifold
       6        40s            4.5s
       7        54s            5.5s
       8        70s            7.5s
       9        90s            9.5s

n of 6 means 36 polyhedrons merged, 7 is 49, etc. My finely calibrated eye says there's a linear relation between polyhedron count and time and, more importantly, Manifold appears consistently about 10x faster at eliminating the duplicates (and rendering) than getting BOSL to do the elimination first. BTW, when I eliminate the duplicates with vnf_merge_points the warning messages are gone.

[adrianVmariano]

The OpenSCAD language is horrible for efficient implementation of complicated algorithms due to the impossibility to (efficiently) implement data structures like priority queue that are essential to those algorithms. It's always going to be much faster for an operation to happen in OpenSCAD natively than to run in userspace.

The point merge process in BOSL2 attempts to speed the search by organizing the data into a tree. If this works really well then the point merge process will be O(n log n) but if it works less well it can still be O(n^2). But the speed of this operation definitely depends on how the data is distributed.

In your test results above, you list a BOSL2 time and a Manifold time, but I'm not sure I know what the times are exactly. To know how long manifold takes to deal with repeated vertices you'd need a manifold time with and without those repeated vertices. Did you do a test like that somehow? Because manifold is doing other stuff, not only dealing with manifold repair.

[DougPollard]

Yeah, I agree with all points. My test was really just a basic determination, from the user perspective, of which approach is currently best -- ask BOSL2 to clean up the duplicate vertices or let Manifold. The numbers were so overwhelming that I stopped there. It would be nice though, for the developers as well as users, to optimize the task when possible.

I'm not sure when cacheing comes in to play and how to defeat it in OpenSCAD. If we create a polyhedron with some duplicate vertices, then replicate that polyhedron 100 times with some slight transform, does OpenSCAD optimize (remove duplicate vertices) one copy of the polyhedron then reuse that result for the other 99? Or is the cache only used for identical data from one run to the next?

If cacheing is not a concern, then maybe the simple tests are

1. one polyhedron with duplicates removed by BOSL2 and 99 copies merged (ie, Manifold doesn't have to remove duplicates and the price paid for BOSL2 to do it is small, relative to the overall size of the render)
2. 100 copies merged of polyhedron with duplicates (ie, Manifold has to do the removal 100 times)
3. various ratios of clean-to-dirty, like 50 clean polyhedrons (from one single BOSL2 action) and 50 copies of non-clean, etc

This might provide some insight into how costly the duplicate removal process is in Manifold. It wouldn't answer the question of if that price varies by the number of duplicates per polyhedron or if it's relative constant, based simply on the overall size of the polyhedron. You've already indicated in BOSL2 that that same price does vary based on the specific data, but I'm not sure if that is based on the quantity of duplicates or on how well the order of the vertices fill a tree.

Where I'm heading with this long ramble is maybe there is a price to pay each time Manifold encounters a polyhedron with any duplicates, regardless of the quantity, and so it might behoove BOSL2 to avoid duplicates in certain "easy" cases but not to bother in hard cases. Lots of speculation at this point (that's probably wrong anyways!). Maybe I'll setup a test like this, unless someone tells me it's obviously wrong or meaningless.

[kintel]

Minor clarification: The mentioned repair isn't something done by Manifold, it's something OpenSCAD does to be able to pass valid meshes to Manifold.

Caching isn't properly implemented yet for Manifold. That's something we need to resolve before moving Manifold out of the experimental stage: #4825

[adrianVmariano]

With regards to BOSL2 cleaning up duplicate vertices, there are places where it could be done with no significant computational cost---"just" programming effort. The case of closed path_sweep is probably one such example, though there are some subtleties (specifically, if the object twists, the alignment between the vertices is not necessarily a direct mapping, which I think would actually be a major complication). The performance issue with vnf_merge_points arises from relying on a brute force approach that doesn't exploit topology. But it's a big change and a lot of effort to change things to exploit toplogy---the obvious thing would be to track where the boundaries of partial polyhedra are so that when they are merged, the points on the boundary are lined up and merged. This would be faster since it reduces the points that need to be checked to a presumably small boundary set. (In principle you could align one point and then follow the boundary, but that might be hard to implement efficiently.) There is definitely a question of whether any of these things are worth putting effort toward. I don't think we'd want to try to do the boundary tracking until we get real structures.

For testing purposes, you could test path sweeps with closed=true where you invoke vnf_merge_points or don't, and look at preview time difference, which should tell you how long BOSL2 takes to remove duplicate vertices. Then without invoking vnf_merge_points you can compare the render time for closed=true and closed=false. Since closed=false has no duplicate points but closed=true does have duplicate points, this should be a pretty good test of the render time required to remove the duplicate points to prepare the input for manifold.

[nophead]

If have just come across this warning in my threads library. I have two separate polyhedrons that are the starts and ends of the thread and I intersect them with a rotate_extruded polygon to chamfer or truncate them. I don't think there are any duplicated points in my polyhedra. Either operand of the intersection is fine on its own but together they give this warning.

[adrianVmariano]

Does the rule still apply that a single polyhedron doesn't invoke the geometry engine? That is, if you take one polyhedron and combine it with a cube do you get the warning?

[nophead]

The ends get unioned with the rest of the thread and that doesn't generate any warnings if I don't intersect them first.

[nophead]

I do get the warning if I union the ends with a cube.

[nophead]

The intersection is inside a render(). If I remove that I don't get the warning. I also only get 5 warnings for 8 threads of different sizes.

[nophead]

This is all in a preview. I never do a render of these, so I suppose the intersection is done by OpenCSG. It is only when I add the render it is done by manifold.

[kintel]

@nophead the warning is most likely a real indication that your mesh isn't a manifold topology and requires some sort of repair or vertex merge. I suggest you open a separate ticket and post the smallest example you can come up with, and we can help identify the root cause.

[nophead]

Wouldn't CGAL barf if I did an intersection with non-manifold polyhedra? Without manifold selected the rendered intersection works fine. The ends of the thread are just a simple sweep.

This is what the intersection looks like.

[nophead]

Well a simple nested for loop tells me there are lots of duplicated vertices, so I will investigate further.

[nophead]

It was a simple case of somebody passing a thread profile with a zero crest. That caused a duplicate point in the profile. Sorry for the noise.

[kintel]

Does the rule still apply that a single polyhedron doesn't invoke the geometry engine? That is, if you take one polyhedron and combine it with a cube do you get the warning?

It's more of an implementation detail. We convert to the geometry backend-specific format only when needed, and it's currently not needed for rendering a single polyhedron. You can force it to do this on the cmd-line for testing: openscad file.scad -o out.png --render=force

[kintel]

It was a simple case of somebody passing a thread profile with a zero crest. That caused a duplicate point in the profile. Sorry for the noise.

If you include the duplicate vertices in the mesh with their own indices, this should now work: The topology is manifold and degenerate triangles caused by duplicate vertex positions are tolerated. If you find odd corner cases feel free to provide an example :)

[adrianVmariano]

Do you mean duplicate vertices that have (degenerate) triangles that place them consistently into the mesh? Or do you mean duplicate vertices where the mesh assumes that the duplicate vertices are the same point even though they have different indices?

[kintel]

The first.

[adrianVmariano]

Has something changed about how duplicate vertices get treated? I'm not sure if this is related to the issue discussed here or is a separate matter, but someone reported an artifact that arose because two objects were unioned but they had a 1e-15 gap between them and this gap ended up appearing in the final model and lead to a render failure. The same model in the stable version rendered successfully.

[kintel]

If the issue isn't about gaps in a single polyhedron it's worth opening a new ticket.

[kintel]

The case of closed path_sweep is probably one such example, though there are some subtleties (specifically, if the object twists, the alignment between the vertices is not necessarily a direct mapping, which I think would actually be a major complication).

@adrianVmariano In this specific case, it sounds like you're relying on merging almost coincident vertices. That's an important detail to keep in mind,

[adrianVmariano]

Yeah, it's possible in the specific case of twisting path_sweep that round-off error in the rotation would mean the vertices wouldn't be exactly coincident, but off by machine epsilon. Will the duplicate vertex handling work in this case?

The situation described above involved 2d polygons with a 1e-15 error that was a result of a rotation, and it actually turns out that it happened in both versions of OpenSCAD but for some reason was easier to see in the dev version.

[kintel]

It should work, but we may end up merging close vertices more aggressively than expected. We should come up with some nomenclature for how we deal with such geometry so we can document what you can expect.
I might end up splitting up the current repair functionality into multiple steps, and only issue a warning if the "regular" steps fail and we go into attempting a full mesh reorientation.

[adrianVmariano]

I think in most cases, duplicated vertices will be exact duplicates. The twisted path_sweep is one exception. I can imagine that someone building up some shape with beziers could get points differing by machine epsilon if they compute different patches that theoretically share the same boundary---and that's an example of a use case where it would be very difficult for us to change things to prevent the duplication of points.

[kintel]

The latest fix will silence this warning for identical vertex positions.
For almost identical vertices, we don't yet have a way of allowing fusing very close vertices without resorting to full vertex quantization.

[adrianVmariano]

So this means that identical duplicate vertices produce no message of any kind, and almost identical vertices work as before, producing a standard warning?

[kintel]

Exactly.

[kintel]

..but be aware that there is a subset of manifold objects not representable after merging vertices, things like:

• Two cubes touching each other
• Donut with a zero radius hole
• ..or any self-touching objects.

[adrianVmariano]

It appears that this still hasn't been acted upon, as someone complained in the forum that their render failed in BOSL2 due to this issue.

[kintel]

Note that this still only produces a warning - it should have no impact on the geometry creation
Can you provide a minimal breakage example?

[adrianVmariano]

As I previously noted, OpenSCAD is unusable unless "stop on first warning" is enabled, so yes, getting a warning blocks geometry creation. The person who raised the issue on the forum had enabled "stop on first warning". Also I don't think that there is currently any warning you can get that shouldn't actually be an error. This is the first such warning that I am aware of. Whenever my code stops on first warning the code is wrong or has bugs. Gibberish like translate(["yes","hello","four"]) cube(); is only a warning.

Here is a short example of the failure to create geometry due to round-off error in point locations:

include <BOSL2/std.scad> 
include <BOSL2/rounding.scad>

union(){
  rounded_prism(square(10), height=10, joint_top=1);
  cuboid(3);
}

Result:

Parsing design (AST generation)...
Compiling design (CSG Tree generation)...
Rendering Polygon Mesh using Manifold...
WARNING: PolySet -> Manifold conversion failed: NotManifold
Trying to repair and reconstruct mesh..
Rendering cancelled on first warning.
WARNING: No top level geometry to render

[kintel]

ok, let's try to further evaluate in which cases we can repair such geometry without losing data.
I'll add this ticket as a release blocker for now.

[adrianVmariano]

The kinds of geometry that BOSL2 creates should involve well-behaved duplication. They arise in this case because mating bezier patches are computed separately and then placed into a single polyhedron, so the shared edge has point pairs that don't exactly agree. At corners there will be more duplicates, but there shouldn't be anything weird with the topology, or any points that are extremely close but need to be kept separate to maintain the topology.

[kintel]

The devil is in the details: My current concern is that going through CGAL for repairs will remove all colors. The code paths used by BOSL most likely don't support colors, so this is probably not a concern for now. However, the internal code paths used to pass data to manifold does support colors. This means that we need to be a bit careful about how we perform such repairs, as well as which warnings should be considered informational and which indicate that data may be lost.

[adrianVmariano]

How does/will color support work?

Would there be a way to supply a polyhedron fixer that we could call from userspace to handle specific situations, e.g. to locate duplicate points in a polyhedron? This is expensive to do in userspace.

We can also consider ways in the future to track edges and merge them in userspace, which I think may be possible and would substantially reduce the performance penalty, but I don't want to attempt that until we have user-creatable structures. This would completely eliminate the problem for situations where we are just gluing edges together, which is maybe the only problem case? (I'm not sure if any other problem cases exist, but nothing comes to mind.)

[kintel]

Colors are per-triangle colors, but creation or queries of individual triangle colors are currently not exposed to user space, but are managed internally when doing CSG operations, import, export etc. of objects with colors.

Offering user space functions on 3D objects are a bit far off, so it's not in scope for this discussion.

[adrianVmariano]

I don't need user space 3d objects. I just need a function that takes a list of 3d points and identifies the approximate duplicates. If that operation was fast then we could just do it any time we have made a polyhedron with duplicated edges. Or there could be an option on polyhedron() to merge points that are closer than a specified epsilon.