Questions about the output geometry

[pca006132]

Considering the input geometry may not be manifold, I wonder if there is manifoldness guarantee for the output? It is not clear from the paper you referred to, and it seems that this implementation is quite different from the original paper (performance seems much better compared to the claims in the paper).

E.g. If the input is a manifold, will the output be manifold? Will the output contain self-intersections? If the input is non-manifold, will this make the output manifold?

[unageek]

The output may not be manifold even if the inputs are manifold. Consider two tetrahedra sharing one of their edges. If you take the union of them, the result is non-manifold.

There will be no self-intersection in the output if the inputs do not have self-intersections. The algorithm is not designed to handle self-intersections.

[pca006132]

The output may not be manifold even if the inputs are manifold. Consider two tetrahedra sharing one of their edges. If you take the union of them, the result is non-manifold.

Yeah, but for things like 3mf and the manifold library, they only care about the topological definition of manifoldness, i.e. every edge of every triangle must contain the same two vertices (by index) as exactly one other triangle edge, and the start and end vertices must switch places between these two edges.

Is it possible to guarantee the output of this library to have this property?

[unageek]

Is it possible to guarantee the output of this library to have this property?

No, you cannot find such representation in general.

Here is a counter-example (mesh in OBJ format), please take a look:

v -2 -1 -1
v -2 -1 1
v -2 1 -1
v -2 1 1
v -1 0 0
v 2 -1 -1
v 2 -1 1
v 2 1 -1
v 2 1 1
v 1 0 0
f 1 2 4 3
f 1 6 7 2
f 3 4 9 8
f 1 3 5
f 1 5 10 6
f 3 8 10 5
f 2 5 4
f 2 7 10 5
f 4 5 10 9
f 6 10 7
f 8 9 10

[pca006132]

Is it possible to guarantee the output of this library to have this property?

No, you cannot find such representation in general.

Here is a counter-example (mesh in OBJ format), please take a look:

v -2 -1 -1
v -2 -1 1
v -2 1 -1
v -2 1 1
v -1 0 0
v 2 -1 -1
v 2 -1 1
v 2 1 -1
v 2 1 1
v 1 0 0
f 1 2 4 3
f 1 6 7 2
f 3 4 9 8
f 1 3 5
f 1 5 10 6
f 3 8 10 5
f 2 5 4
f 2 7 10 5
f 4 5 10 9
f 6 10 7
f 8 9 10

I think for manifold (the library), we handle this by duplicating the vertices and edges. The same edge in 3D is viewed as multiple distinct edges. This causes the geometry to be self-intersecting, but it is valid if you allow perturbation by a tiny amount, and it satisfies the ε-valid requirement in manifold.

[unageek]

The same edge in 3D is viewed as multiple distinct edges.

OK, but I am not sure how to duplicate the non-manifold edge in the above mesh to obtain a manifold representation. Could you modify the mesh in this way, please?

[pca006132]

The same edge in 3D is viewed as multiple distinct edges.

OK, but I am not sure how to duplicate the non-manifold edge in the above mesh to obtain a manifold representation. Could you modify the mesh in this way, please?

@@ -8,14 +8,15 @@
 v 2 1 -1
 v 2 1 1
 v 1 0 0
+v 1 0 0
 f 1 2 4 3
 f 1 6 7 2
 f 3 4 9 8
 f 1 3 5
 f 1 5 10 6
-f 3 8 10 5
-f 2 5 4
-f 2 7 10 5
-f 4 5 10 9
 f 6 10 7
-f 8 9 10
+f 2 7 10 5
+f 2 5 4
+f 3 8 11 5
+f 4 5 11 9
+f 8 9 11

But thinking about it, I think CGAL has a function to do this (https://doc.cgal.org/latest/Polygon_mesh_processing/group__PMP__orientation__grp.html#gad380465ee62d858d27fab4cfda6c1764). Not sure how robust the function is, though.

[pca006132]

Possibly unrelated: I wonder if this approach can be used for mesh union of multiple meshes or intersection. It seems that the approach is not limited to binary operations.

Btw, impressive work! The original paper seems a lot slower than this implementation, considering their benchmark result is only a few times faster than nef-polyhedra in CGAL.

[unageek]

Thank you for the modified example. I stupidly didn't come up with that representation. Do you know if every non-manifold mesh has such representation?

[pca006132]

Thank you for the modified example. I stupidly didn't come up with that representation. Do you know if every non-manifold mesh has such representation?

I think this should be true, but I am not sure if there is a proof for this. Probably need to read some papers.