Nef_3: Detecting invalid constructions

[GilesBathgate]

My goal is to be able to use Nef_3 with CGAL_NO_ASSERTIONS, and since I allow arbitrary input (in the form of STL/OBJ/AMF files, and the brace initialised polyhedron format in the issue examples) I wanted to document the tests needed to ensure a valid construction. If the construction is invalid, a fallback to the union of facet cycles (OFF_to_nef_3) can be used.

In the following issues, I present test cases that trigger assertions, and potential code for detecting the geometry that causes them:

• Nef_3 ss_circle.has_on(sp) assertion error. #7205
• Nef_3: e_below != SHalfedge_handle() assertion error. #7266
• Nef_3: e->incident_sface() != SFace_const_handle() assertion error. #7267
• Nef_3: it is not possible to decide which one is a visible facet (if any) assertion error #7271

[GilesBathgate]

In the examples, similar to the following simple container is used:

using Point = std::vector<double>;
using Points = std::vector<Point>;
using Facet = std::vector<Points::size_type>;
using Facets = std::vector<Facet>;
struct Polyhedron { Points points; Facets faces; };

It can be brace initialised like so:

Polyhedron polyhedron = { .points = {{0,0,0},{0,0,10},{0,10,10},{0,10,0},{10,0,10},{10,10,10},{10,10,0},{10,0,0}}, .faces = {{0,1,2,3},{1,4,5,2},{0,3,6,7},{3,2,5,6},{7,4,1,0},{6,5,4,7}}};

The reason for this syntax is that it's comparable to script based cad programs OpenSCAD and RapCAD

[GilesBathgate]

As has been mentioned here. Duplicated points can cause issues. The following function ensures the points are unique and are used at least once:

static bool valid_indexing(const Polyhedron& polyhedron)
{
	const auto& points = polyhedron.points;
	const auto& facets = polyhedron.faces;
	std::unordered_set<int> used(points.size());
	std::set<CGAL::Point_3<K>> unique;
	for(const auto& face: facets) {
		for(const auto& index: face) {
			const auto& p=points[index];
			unique.insert(CGAL::Point_3<K>(p[0],p[1],p[2]));
			used.insert(index);
		}
	}

	// used == unique == points
	return used.size()==unique.size()&&used.size()==points.size();
}

using builder.remove_unconnected_vertices(); is another option, but still allows duplicate points if they are used.