CGAL
Nef_3: it is not possible to decide which one is a visible facet (if any) assertion error
Issue Details
Following on the investigation in #7205 this is an example with a different exception. The polyhedron is:
Polyhedron polyhedron = {.points = {{0,0,0},{0,-10,0},{10,0,0},{20,0,0},{10,10,0},{5,0,0}}, .faces = {{0,1,2},{4,3,5}}};
CGAL error: assertion violation!
Expression :
File : /usr/include/CGAL/Nef_3/SNC_const_decorator.h
Line : 276
Explanation: it is not possible to decide which one is a visible facet (if any)
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
File: /usr/include/CGAL/Nef_3/SNC_const_decorator.h
Line: 276
Explanation: it is not possible to decide which one is a visible facet (if any)
Source Code
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Modifier_base.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/Polyhedron_incremental_builder_3.h>
#include <vector>
#include <tuple>
using K=CGAL::Exact_predicates_exact_constructions_kernel;
using HalfedgeDS=CGAL::Polyhedron_3<K>::HalfedgeDS;
using Points = std::vector<CGAL::Point_3<K>>;
using Facet = std::vector<Points::size_type>;
using Facets = std::vector<Facet>;
struct Polyhedron { Points points; Facets faces; };
struct Builder : public CGAL::Modifier_base<HalfedgeDS>
{
const Polyhedron& polyhedron;
Builder(const Polyhedron& p) : polyhedron(p) {}
void operator()(HalfedgeDS& hds) override {
CGAL::Polyhedron_incremental_builder_3<HalfedgeDS> builder(hds,true);
const auto& points= polyhedron.points;
const auto& polygons = polyhedron.faces;
builder.begin_surface(points.size(),polygons.size());
for(const auto& p: points)
builder.add_vertex(p);
for(const auto& pg: polygons) {
if(builder.test_facet(pg.begin(),pg.end()))
builder.add_facet(pg.begin(),pg.end());
}
builder.end_surface();
builder.remove_unconnected_vertices();
}
};
int main()
{
Polyhedron polyhedron = {.points = {{0,0,0},{0,-10,0},{10,0,0},{20,0,0},{10,10,0},{5,0,0}}, .faces = {{0,1,2},{4,3,5}}};
Builder b{polyhedron};
CGAL::Polyhedron_3<K> P;
P.delegate(b);
CGAL::Nef_polyhedron_3<K> N(P);
}
Environment
- Operating system (Windows/Mac/Linux, 32/64 bits): Linux 64bit
- Compiler: clang++ version 14.0.0
- Release or debug mode: debug
- Specific flags used (if any):
- CGAL version: master
- Boost version: 1.74.0
- Other libraries versions if used (Eigen, TBB, etc.): None
This appears to be triggered by two triangles that share an edge but do not share any vertices.
However when I used the following which is also two triangles that share an edge but not any vertices it works:
Polyhedron polyhedron = {.points = {{0,0,0},{0,10,0},{10,0,0},{0,5,0},{-10,-5,0},{0,-5,0}}, .faces = {{0,1,2},{3,4,5}}};
In commit ebd5e00ba8e5041e64b415eb9421f89045591ac9 the value of true was passed to L.locate() which skips needless tests.
Applying the same change to the get_visible_facet method of SNC_const_decorator makes the assertion exception never occur.
@afabri However I am not sure if it would be correct to apply the same change here or not.
I keep running into a similar issue and landed here again. My problem in its minimal shape is about creating a Nef polyhedron of the infamous "two cubes sharing an edge" object.
As of CGAL-6.0.1, the below program fails in the Nef polyhedron constructor with the same error as @GilesBathgate posted above.
With the suggested patch to L.locate() in get_visible_facet() of SNC_const_decorator, my test program passes.
That might be one more reason to take a look at whether this is a good fix to make.
Full test program:
#include <array>
#include <vector>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/Surface_mesh/Surface_mesh.h>
using NT3 = CGAL::Gmpq;
using CGAL_Kernel3 = CGAL::Cartesian<NT3>;
using CGAL_Vertex = CGAL::Point_3<CGAL_Kernel3>;
struct Object {
std::vector<std::array<double, 3>> vertices;
std::vector<std::array<uint32_t, 3>> indices;
};
int main(int argc, char *argv[]) {
const Object touching_cubes = {
.vertices = {
{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {1, 1, 0},
{0, 0, 1}, {1, 0, 1}, {0, 1, 1}, {1, 1, 1},
{1, 1, 0}, {2, 1, 0}, {1, 2, 0}, {2, 2, 0},
{1, 1, 1}, {2, 1, 1}, {1, 2, 1}, {2, 2, 1},
},
.indices = {
{6,5,7},{6,4,5},
{0,3,1},{0,2,3},
{4,1,5},{4,0,1},
{5,3,7},{5,1,3},
{7,2,6},{7,3,2},
{6,0,4},{6,2,0},
{14,13,15},{14,12,13},
{8,11,9},{8,10,11},
{12,9,13},{12,8,9},
{13,11,15},{13,9,11},
{15,10,14},{15,11,10},
{14,8,12},{14,10,8},
}
};
using SurfaceMesh = CGAL::Surface_mesh<CGAL_Vertex>;
SurfaceMesh mesh;
for (const auto &v : touching_cubes.vertices) {
mesh.add_vertex({v[0], v[1], v[2]});
}
for (const auto &f : touching_cubes.indices) {
mesh.add_face(SurfaceMesh::Vertex_index(f[0]),
SurfaceMesh::Vertex_index(f[1]),
SurfaceMesh::Vertex_index(f[2]));
}
CGAL::Nef_polyhedron_3<CGAL_Kernel3> nef(mesh);
}
Edit: Corrected winding order of triangles
@afabri Any comments on this? My workaround for this issue is to nary_union every face in the mesh, which feels a bit expensive.
@sloriot As you seem to be the most active dev in the Nef_3 codebase: Any comments on this? We can put together a PR if you think it's a valuable exploration.
@kintel Did you perhaps want to create a PR that would allow my fix to be optional, maybe by specialising a decorator_trait or simply an additional boolean class template parameter?
@GilesBathgate Not sure how to achieve that for my issue: In my case, the assertion occurs when calling the CGAL::Nef_polyhedron_3() constructor with a CGAL::Surface_mesh of the same point type as argument.
I mean we would propose a fix to CGAL that has some tag in the traits, and you would instantiate Nef_polyhedron_3<traits> instead of the default Nef_polyhedron_3. Then the fix would only apply to a limited scope.
The alternative workaround to patching it in CGAL, would be to fix it in a project specific copy of the SNC_const_decorator.h, and inject that early into the header dependency chain. (utilizing the header guards)
I'm not too familiar with the internals, but yeah, making it 1. optional and 2. user-space would be good. Anyway, let's see if we hear back from @sloriot - in the meantime I'll try to find time to do some digging.
Btw., it's not 100% clear to me whether this could end up creating a Nef3 polyhedron which is somehow invalid. I need to write more tests to exercise that..
@kintel in my opinion the only blocker is https://github.com/CGAL/cgal/pull/7274#issuecomment-2855162598
Humm, double-checking: With your patch, nef.is_valid() returns false for my example above.
@kintel Although it is possible to have a valid "two cubes sharing an edge" nef, when constructed a different way?
Yes, there are so many way of creating such a Nef polyhedron. These are the 4 ways I'm currently exploring (the bolded one being the one I want to make work):
| Method | Can create Nef3 | Nef3 is valid | Notes |
|---|---|---|---|
| Union each individual face | OK | OK | Issue: Slow |
| Union of two Surface_mesh cubes, resulting object sharing an edge | OK | OK | Issue: Object are often only available as a single, already unioned, mesh |
| Single Surface_mesh contains two cubes sharing an edge (with distinct vertices)2 | OK1 | Fail | |
| Single Surface_mesh contains two cubes sharing an edge (with merged vertices)2 | OK1 | OK |
1Requires SNC_const_decorator patch
2Somehow, a mesh with merged vertices works. However, such a mesh doesn't contain an explicit topology, so someone has to guess. If we make the coincident vertices distinct (but with coincident positions), we can specify a manifold topology. In the context of OpenSCAD, the latter geometry is what is used.
@kintel So I also have this version that works in RapCAD, but I think this is because it has 2 less vertices:
polyhedron(points = [
[0,1,0],[0,0,0],[0,0,1],[0,1,1],
[1,0,1],[1,1,1],[1,0,0],[1,1,0],
[2,1,0],[2,1,1],[1,2,1],[2,2,1],
[1,2,0],[2,2,0]
],
faces = [
[0,1,2,3],
[3,2,4,5],
[6,1,0,7],
[7,0,3,5],
[5,7,8,9],
[10,5,9,11],
[12,7,5,10],
[8,7,12,13],
[9,8,13,11],
[13,12,10,11],
[1,6,4,2],
[6,7,5,4]
]);
cube(0.1);
It dosen't work in openscad though 😕 (if you remove the union with the 0.1 cube it works, because it bypasses the nef construction, but you can at least verify the topology is the same)
@kintel I think the 'success' in rapcad is due to it falling back to using union each individual face:
https://github.com/GilesBathgate/RapCAD/blob/master/src/cgalprimitive.cpp#L158
Your example is the last of the 4 in my list. It works in OpenSCAD when applying the SNC_const_decorator patch. We don't implement a face-union fallback. Perhaps we should, I just fear that the fallback will happen too often and that it will affect performance..
I'd honestly forgotten that I'd implemented the face-union fallback, but I only apply it for user defined polyhedra, or imported files. I try to detect and fix edge cases in https://github.com/GilesBathgate/RapCAD/blob/master/src/cgalsanitizer.cpp
I am detecting the fallback case before constructing the nef.
Either way, the original report, and your example in https://github.com/CGAL/cgal/issues/7271#issuecomment-2846101339 don't trigger the fallback. So I still get the assertion error it is not possible to decide which one is a visible facet (if any) in those cases in rapcad.
Understanding the cause and creating a robust fix for CGAL would be the preferred approach.
@kintel, sorry I missed this issue.
Looking at your input, it's 2 cube sharing an edge with duplicated vertices. So it's a self-intersection that Nef does not accept as input for a mesh. Using CGAL::OFF_to_nef_3 I can create the mesh without any issue. Side question, your cubes are inside-out, is it expected?
If you don't like the OFF_to_nef_3 API (because it's a stream), I can probably easily add a version taking a polygon soup.
@sloriot Yes, @kintel uses a technique similar to OFF_to_nef_3 in Union each individual face OK OK Issue: Slow
Likewise I use my equivalent https://github.com/GilesBathgate/RapCAD/blob/master/src/cgalprimitive.cpp#L158
EDIT: My implementation is actually on https://github.com/GilesBathgate/RapCAD/blob/master/src/cgalprimitive.cpp#L179
Re Slow: I haven't measured it, but it feels slow, especially once you get a lot of (5 digits+) facets. Then again, one of the main goals of this exercise is to perform a convex decomposition afterwards, so "slow" can be relative. Any anecdotes around performance of the various Nef construction methods would also be valuable!
@kintel I thought openscad was moving toward PMP for fast boolean operations? or is this already the case, and just complex operations like convex decomposition remain? Either way I like Nef. Its the diamond in the rough, as @afabri likes to call it. He and I did look into Nef performance, but this issue sounds like more of a robustness problem to me would you agree?
Providing an efficient way to fallback to the face-union approach or fixing the construction directly is still a desirable focus for me regarding the issue.
Side question, your cubes are inside-out, is it expected?
Wops, not intentional; I've edited the code above to fix. This doesn't affect any of the contents of this issue though.
@kintel I thought openscad was moving toward PMP for fast boolean operations? or is this already the case, and just complex operations like convex decomposition remain?
Yes, we support multiple backends now, but minkowski (which requires convex decomposition) is only implemented using Nef3 polyhedrons.
He and I did look into Nef performance, but this issue sounds like more of a robustness problem to me would you agree?
Yeah, it's about defining a robust bi-directional I/O mechanism between Nef3 and some mesh structure which allows us to represent common topologies of 3D objects.
I guess I could try to add a constructor for "clean" polygon soup, if you see that OFF_to_nef_3 is really too slow on a real case. Let me know @kintel. Note that you would need OFF_to_nef_3 only for non-manifold cases.
@sloriot is there a simple non-manifold check in CGAL::Surface_mesh, or CGAL::Polyhedron_incremental_builder_3 the input geometry in @kintel and my case might be user specified, or from an STL.
I would say that once you have a Surface_mesh, it is already too late because you must probably have duplicated some vertices to make the graph manifold, with a self-intersecting embedding. Even if you have duplicated vertices, it is possible to automatically fix that using repair_polygon_soup, and then you can use is_polygon_soup_a_polygon_mesh() to check for manifoldness of the polygon soup.
duplicated some vertices to make the graph manifold, with a self-intersecting embedding.
Yes, that's exactly what we're doing, to satisfy the definition of "manifold" used by e.g. 3MF.
We even ported Nef3 interop from Polyhedron to Surface_mesh in an attempt to allow Nef3 I/O, as Polyhedron doesn't seem to support representing such meshes at all.
Essentially, using vertices represented as floating point, it's not trivial to avoid self-intersections, so software in the 3D printing space, especially software using 3MF, are required to support self-intersecting geometry as long as the connectivity is manifold.
Thanks for the advice - this eliminates some areas of exploration.