Surface_mesh version of CGALHybridPolyhedron

CGALPolyhedron_mesh.cc

// Portions of this file are Copyright 2021 Google LLC, and licensed under GPL2+. See COPYING.
#include "CGALHybridPolyhedron.h"

#ifdef FAST_CSG_AVAILABLE
#include <CGAL/boost/graph/convert_nef_polyhedron_to_polygon_mesh.h>
#include <CGAL/boost/graph/copy_face_graph.h>
#include <CGAL/boost/graph/helpers.h>
#include <CGAL/Cartesian_converter.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/orientation.h>
#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#if CGAL_VERSION_NR >= CGAL_VERSION_NUMBER(5, 1, 0)
#include <CGAL/Polygon_mesh_processing/manifoldness.h>
#else
#include <CGAL/Polygon_mesh_processing/repair.h>
#endif
#include <unordered_set>

#include "CGAL_Nef_polyhedron.h"
#include "cgalutils.h"
#include "feature.h"
#include "grid.h"
#include "hash.h"
#include "polyset.h"
#include "scoped_timer.h"

namespace PMP = CGAL::Polygon_mesh_processing;
namespace params = PMP::parameters;

CGALHybridPolyhedron::CGALHybridPolyhedron(const PolySet &ps)
{
#ifndef CGAL_PMP_SUPPORTS_POLYHEDRON
  static auto printedDisclaimer = false;
  if (!printedDisclaimer) {
    LOG(message_group::Warning, Location::NONE, "", "[fast-csg] CGAL " STRING(CGAL_VERSION) " support is experimental / has known bugs. Compile against latest version for best behaviour!");
    printedDisclaimer = true;
  }
#endif

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (!Feature::ExperimentalMesh.is_enabled())
		buildPolyhedron(ps);
	else
#endif
		buildMesh(ps);
}

void CGALHybridPolyhedron::buildMesh(const PolySet &ps)
{
#if 0 // DEBUG: is building the mesh what is broken right now? Use the polyhedron
  buildPolyhedron(ps);
  if (auto poly = getPolyhedron()) {
    auto mesh = make_shared<mesh_t>();
    CGAL::copy_face_graph(*poly, *mesh);
    data = mesh;
  }
  return;
#else
	SCOPED_PERFORMANCE_TIMER("CGALHybridPolyhedron::buildMesh(PolySet)");

	auto mesh = make_shared<mesh_t>();
	data = mesh;
	bboxes.add(CGALUtils::boundingBox<kernel_t>(ps));

	auto err = CGALUtils::createMeshFromPolySet(ps, *mesh);
	assert(!err);
	PMP::triangulate_faces(*mesh);

	if (!PMP::is_outward_oriented(*mesh, params::all_default())) {
		LOG(message_group::Warning, Location::NONE, "", "Fixing inverted faces orientation.");
		PMP::reverse_face_orientations(*mesh);
	}
	if (!ps.is_convex() && !Feature::ExperimentalTrustManifold.is_enabled()) {
		SCOPED_PERFORMANCE_TIMER("CGALHybridPolyhedron::buildMesh: manifoldness checks");

		if (PMP::duplicate_non_manifold_vertices(*mesh)) {
			LOG(message_group::Warning, Location::NONE, "",
					"Non-manifold, converting to nef polyhedron.");
			convertToNefPolyhedron();
		}
	}
#endif
}

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
void CGALHybridPolyhedron::buildPolyhedron(const PolySet &ps)
{
	SCOPED_PERFORMANCE_TIMER("CGALHybridPolyhedron::buildPolyhedron(PolySet)");

	auto polyhedron = make_shared<polyhedron_t>();
	data = polyhedron;
	bboxes.add(CGALUtils::boundingBox(ps));

	auto err = CGALUtils::createPolyhedronFromPolySet(ps, *polyhedron);
	assert(!err);
	PMP::triangulate_faces(*polyhedron);

	if (!PMP::is_outward_oriented(*polyhedron, params::all_default())) {
		LOG(message_group::Warning, Location::NONE, "", "Fixing inverted faces orientation.");
		PMP::reverse_face_orientations(*polyhedron);
	}
	if (!ps.is_manifold() && !ps.is_convex() && !Feature::ExperimentalTrustManifold.is_enabled()) {
		SCOPED_PERFORMANCE_TIMER("CGALHybridPolyhedron::buildPolyhedron: manifoldness checks");

		if (PMP::duplicate_non_manifold_vertices(*polyhedron)) {
			LOG(message_group::Warning, Location::NONE, "",
					"Non-manifold, converting to nef polyhedron.");
			convertToNefPolyhedron();
		}
	}
}
#endif

CGALHybridPolyhedron::CGALHybridPolyhedron(const CGAL_Nef_polyhedron3 &nef)
{
	SCOPED_PERFORMANCE_TIMER("Polyhedron(CGAL_Nef_polyhedron3)");

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (!Feature::ExperimentalMesh.is_enabled()) {
		auto polyhedron = make_shared<polyhedron_t>();
		CGAL_Polyhedron poly;
		nef.convert_to_polyhedron(poly);
		CGALUtils::copyPolyhedron(poly, *polyhedron);
		data = polyhedron;
	}
	else
#endif
	{
		typedef CGAL::Surface_mesh<CGAL_Kernel3::Point_3> alien_mesh_t;
		alien_mesh_t alien_mesh;
		CGAL::convert_nef_polyhedron_to_polygon_mesh(nef, alien_mesh, /* triangulate_all_faces */ true);

		auto mesh = make_shared<mesh_t>();
		CGALUtils::copyMesh(alien_mesh, *mesh);
		data = mesh;
	}
	bboxes.add(CGALUtils::boundingBox<CGAL_Kernel3>(nef));
}

CGALHybridPolyhedron::nef_polyhedron_t *CGALHybridPolyhedron::getNefPolyhedron() const
{
	auto pp = boost::get<shared_ptr<nef_polyhedron_t>>(&data);
	return pp ? pp->get() : nullptr;
}

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
CGALHybridPolyhedron::polyhedron_t *CGALHybridPolyhedron::getPolyhedron() const
{
	auto pp = boost::get<shared_ptr<polyhedron_t>>(&data);
	return pp ? pp->get() : nullptr;
}
#endif

CGALHybridPolyhedron::mesh_t *CGALHybridPolyhedron::getMesh() const
{
	auto pp = boost::get<shared_ptr<mesh_t>>(&data);
	return pp ? pp->get() : nullptr;
}

bool CGALHybridPolyhedron::isEmpty() const
{
	return numFacets() == 0;
}

size_t CGALHybridPolyhedron::numFacets() const
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (auto poly = getPolyhedron()) {
		return poly->size_of_facets();
	}
#endif
	if (auto nef = getNefPolyhedron()) {
		return nef->number_of_facets();
	}
	if (auto mesh = getMesh()) {
		return mesh->number_of_faces();
	}
	assert(!"Invalid Polyhedron.data state");
	return 0;
}

size_t CGALHybridPolyhedron::numVertices() const
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (auto poly = getPolyhedron()) {
		return poly->size_of_vertices();
	}
	else
#endif
			if (auto nef = getNefPolyhedron()) {
		return nef->number_of_vertices();
	}
	else if (auto mesh = getMesh()) {
		return mesh->number_of_vertices();
	}
	assert(!"Invalid Polyhedron.data state");
	return 0;
}

bool CGALHybridPolyhedron::isManifold() const
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (getPolyhedron()) {
		// We don't keep simple polyhedra if they're not manifold (see contructor)
		return true;
	}
	else
#endif
			if (getMesh()) {
		// We don't keep simple polyhedra if they're not manifold (see contructor)
		return true;
	}
	else if (auto nef = getNefPolyhedron()) {
		return nef->is_simple();
	}
	assert(!"Invalid Polyhedron.data state");
	return false;
}

shared_ptr<const Geometry> CGALHybridPolyhedron::toGeometry() const
{
  if (Feature::ExperimentalFastCsgInaccurate.is_enabled()) {
	  return toPolySet();
  } else {
	  return toNefPolyhedron();
  }
}

shared_ptr<const PolySet> CGALHybridPolyhedron::toPolySet() const
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (auto poly = getPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Polyhedron -> PolySet");

		auto ps = make_shared<PolySet>(3, /* convex */ unknown, /* manifold */ false);
		auto err = CGALUtils::createPolySetFromPolyhedron(*poly, *ps);
		assert(!err);
		return ps;
	}
	else
#endif
			if (auto mesh = getMesh()) {
		SCOPED_PERFORMANCE_TIMER("Mesh -> PolySet");

		auto ps = make_shared<PolySet>(3, /* convex */ unknown, /* manifold */ false);
		auto err = CGALUtils::createPolySetFromMesh(*mesh, *ps);
		assert(!err);
		return ps;
	}
	else if (auto nef = getNefPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Nef -> PolySet");

		// TODO(ochafik): Convert to CGAL_Nef_polyhedron to keep things exact.
		auto ps = make_shared<PolySet>(3, /* convex */ unknown, /* manifold */ nef->is_simple());
		auto err = CGALUtils::createPolySetFromNefPolyhedron3(*nef, *ps);
		assert(!err);
		return ps;
	}
	else {
		assert(!"Invalid Polyhedron.data state");
		return nullptr;
	}
}

shared_ptr<const CGAL_Nef_polyhedron> CGALHybridPolyhedron::toNefPolyhedron() const
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (auto poly = getPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Polyhedron -> Nef");

		CGAL_Polyhedron alien_poly;
		CGALUtils::copyPolyhedron(*poly, alien_poly);
		return make_shared<CGAL_Nef_polyhedron>(make_shared<CGAL_Nef_polyhedron3>(alien_poly));
	}
#endif

	typedef CGAL::Surface_mesh<CGAL_Kernel3::Point_3> alien_mesh_t;

	if (auto mesh = getMesh()) {
		SCOPED_PERFORMANCE_TIMER("Mesh -> Nef (through polyhedron)");

#ifdef DEBUG
		assert(CGAL::is_closed(*mesh));
#endif
		polyhedron_t poly;
		CGAL::copy_face_graph(*mesh, poly);
		CGAL_Polyhedron alien_poly;
		CGALUtils::copyPolyhedron(poly, alien_poly);
		return make_shared<CGAL_Nef_polyhedron>(make_shared<CGAL_Nef_polyhedron3>(alien_poly));
		// alien_mesh_t alien_mesh;
		// CGALUtils::copyMesh(*mesh, alien_mesh);
		// return make_shared<CGAL_Nef_polyhedron>(make_shared<CGAL_Nef_polyhedron3>(alien_mesh));
	}
	else {
		auto nef = getNefPolyhedron();
		assert(nef);
		if (!nef) return nullptr;
		SCOPED_PERFORMANCE_TIMER("Nef -> Nef (through polyhedron)");

#if 1 // Use intermediate polyhedron to convert between our nef and the legacy nef.
		auto poly = make_shared<polyhedron_t>();
		nef->convert_to_polyhedron(*poly);

		CGAL_Polyhedron alien_poly;
		CGALUtils::copyPolyhedron(*poly, alien_poly);

		return make_shared<CGAL_Nef_polyhedron>(make_shared<CGAL_Nef_polyhedron3>(alien_poly));
#else // Buggy: Use intermediate surface mesh for conversion
		// Breaks with: `$fn=6; sphere(1); translate([0.5, 0, 0]) sphere(1);`
		alien_mesh_t alien_mesh;
		auto mesh = make_shared<mesh_t>();
		CGAL::convert_nef_polyhedron_to_polygon_mesh(*nef, *mesh, /* triangulate_all_faces */ true);
		CGALUtils::copyMesh(*mesh, alien_mesh);
		return make_shared<CGAL_Nef_polyhedron>(make_shared<CGAL_Nef_polyhedron3>(alien_mesh));
#endif
	}

	// if (auto mesh = getMesh()) {
	// 	CGALUtils::copyMesh(*mesh, alien_mesh);
	// }
	// else if (auto nef = getNefPolyhedron()) {
	// 	typedef CGAL::Surface_mesh<CGAL_Kernel3::Point_3> alien_mesh_t;
	//   alien_mesh_t alien_mesh;
	//   auto mesh = make_shared<mesh_t>();
	// 	CGAL::convert_nef_polyhedron_to_polygon_mesh(*nef, *mesh, /* triangulate_all_faces */ true);
	// 	CGALUtils::copyMesh(*mesh, alien_mesh);
	// }
	// else {
	// 	assert(!"Invalid Polyhedron.data state");
	// 	return nullptr;
	// }

	//
}

void CGALHybridPolyhedron::clear()
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (!Feature::ExperimentalMesh.is_enabled())
		data = make_shared<polyhedron_t>();
	else
#endif
		data = make_shared<mesh_t>();
	bboxes.clear();
}

bool CGALHybridPolyhedron::needsNefForOperationWith(const CGALHybridPolyhedron &other) const
{
	return !isManifold() || !other.isManifold() || sharesAnyVertexWith(other);
}

void CGALHybridPolyhedron::operator+=(CGALHybridPolyhedron &other)
{
#if 0 // DEBUG
  meshBinOp("union", other, [&](mesh_t &destinationMesh, mesh_t &otherMesh) {
    PMP::corefine_and_compute_union(destinationMesh, otherMesh, destinationMesh);
  });
  bboxes += other.bboxes;
  return;
#endif

	if (!bboxes.intersects(other.bboxes) && isManifold() && other.isManifold()) {
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
		if (!Feature::ExperimentalMesh.is_enabled())
			polyBinOp("fast union", other, [&](polyhedron_t &destinationPoly, polyhedron_t &otherPoly) {
				CGALUtils::copyPolyhedron(otherPoly, destinationPoly);
			});
		else
#endif
			meshBinOp("fast union", other, [&](mesh_t &destinationMesh, mesh_t &otherMesh) {
				CGALUtils::copyMesh(otherMesh, destinationMesh);
			});
	}
	else {
		if (needsNefForOperationWith(other))
			nefPolyBinOp("union", other,
									 [&](nef_polyhedron_t &destinationNef, nef_polyhedron_t &otherNef) {
										 destinationNef += otherNef;
									 });
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
		else if (!Feature::ExperimentalMesh.is_enabled())
			polyBinOp("union", other, [&](polyhedron_t &destinationPoly, polyhedron_t &otherPoly) {
				PMP::corefine_and_compute_union(destinationPoly, otherPoly, destinationPoly);
			});
#endif
		else
			meshBinOp("union", other, [&](mesh_t &destinationMesh, mesh_t &otherMesh) {
				PMP::corefine_and_compute_union(destinationMesh, otherMesh, destinationMesh);
			});
	}
	bboxes += other.bboxes;
}

void CGALHybridPolyhedron::operator*=(CGALHybridPolyhedron &other)
{
	if (!bboxes.intersects(other.bboxes)) {
		printf("Empty intersection difference!\n");
		clear();
		return;
	}

	if (needsNefForOperationWith(other))
		nefPolyBinOp("intersection", other,
								 [&](nef_polyhedron_t &destinationNef, nef_polyhedron_t &otherNef) {
									 destinationNef *= otherNef;
								 });
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	else if (!Feature::ExperimentalMesh.is_enabled())
		polyBinOp("intersection", other, [&](polyhedron_t &destinationPoly, polyhedron_t &otherPoly) {
			PMP::corefine_and_compute_intersection(destinationPoly, otherPoly, destinationPoly);
		});
#endif
	else
		meshBinOp("intersection", other, [&](mesh_t &destinationMesh, mesh_t &otherMesh) {
			PMP::corefine_and_compute_intersection(destinationMesh, otherMesh, destinationMesh);
		});
	bboxes *= other.bboxes;
}

void CGALHybridPolyhedron::operator-=(CGALHybridPolyhedron &other)
{
	if (!bboxes.intersects(other.bboxes)) {
		printf("Non intersecting difference!\n");
		return;
	}

	// Note: we don't need to change the bbox.
	if (needsNefForOperationWith(other))
		nefPolyBinOp("intersection", other,
								 [&](nef_polyhedron_t &destinationNef, nef_polyhedron_t &otherNef) {
									 destinationNef -= otherNef;
								 });
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	else if (!Feature::ExperimentalMesh.is_enabled())
		polyBinOp("difference", other, [&](polyhedron_t &destinationPoly, polyhedron_t &otherPoly) {
			PMP::corefine_and_compute_difference(destinationPoly, otherPoly, destinationPoly);
		});
#endif
	else
		meshBinOp("difference", other, [&](mesh_t &destinationMesh, mesh_t &otherMesh) {
			PMP::corefine_and_compute_difference(destinationMesh, otherMesh, destinationMesh);
		});
}

void CGALHybridPolyhedron::minkowski(CGALHybridPolyhedron &other)
{
	nefPolyBinOp("minkowski", other,
							 [&](nef_polyhedron_t &destinationNef, nef_polyhedron_t &otherNef) {
								 destinationNef = CGAL::minkowski_sum_3(destinationNef, otherNef);
							 });
}

void CGALHybridPolyhedron::foreachVertexUntilTrue(const std::function<bool(const point_t &pt)> &f) const
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (auto poly = getPolyhedron()) {
		polyhedron_t::Vertex_const_iterator vi;
		CGAL_forall_vertices(vi, *poly)
		{
			if (f(vi->point())) return;
		}
	}
	else
#endif
			if (auto mesh = getMesh()) {
		for (auto v : mesh->vertices()) {
			if (f(mesh->point(v))) return;
		}
	}
	else if (auto nef = getNefPolyhedron()) {
		nef_polyhedron_t::Vertex_const_iterator vi;
		CGAL_forall_vertices(vi, *nef)
		{
			if (f(vi->point())) return;
		}
	}
	else {
		assert(!"Invalid Polyhedron.data state");
	}
}

bool CGALHybridPolyhedron::sharesAnyVertexWith(const CGALHybridPolyhedron &other) const
{
	if (other.numVertices() < numVertices()) {
		// The other has less vertices to index!
		return other.sharesAnyVertexWith(*this);
	}

	SCOPED_PERFORMANCE_TIMER("sharesAnyVertexWith");

	std::unordered_set<point_t> vertices;
	foreachVertexUntilTrue([&](const auto &p) {
		vertices.insert(p);
		return false;
	});

	assert(!vertices.empty());

	auto foundCollision = false;
	other.foreachVertexUntilTrue(
			[&](const auto &p) { return foundCollision = vertices.find(p) != vertices.end(); });

	// printf("foundCollision: %s (%lu vertices)\n", foundCollision ? "yes" : "no", vertices.size());
	return foundCollision;
}

void CGALHybridPolyhedron::nefPolyBinOp(const std::string &opName, CGALHybridPolyhedron &other,
																	const std::function<void(nef_polyhedron_t &destinationNef,
																													 nef_polyhedron_t &otherNef)> &operation)
{
	SCOPED_PERFORMANCE_TIMER(std::string("nef ") + opName);

	auto &destinationNef = convertToNefPolyhedron();
	auto &otherNef = other.convertToNefPolyhedron();

	auto manifoldBefore = isManifold() && other.isManifold();
	operation(destinationNef, otherNef);

	auto manifoldNow = isManifold();
	if (manifoldNow != manifoldBefore) {
		LOG(message_group::Echo, Location::NONE, "",
				"Nef operation got %1$s operands and produced a %2$s result",
				manifoldBefore ? "manifold" : "non-manifold", manifoldNow ? "manifold" : "non-manifold");
	}
}

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
void CGALHybridPolyhedron::polyBinOp(
		const std::string &opName, CGALHybridPolyhedron &other,
		const std::function<void(polyhedron_t &destinationPoly, polyhedron_t &otherPoly)> &operation)
{
	SCOPED_PERFORMANCE_TIMER(std::string("polyhedron ") + opName);

	operation(convertToPolyhedron(), other.convertToPolyhedron());
}
#endif

void CGALHybridPolyhedron::meshBinOp(
		const std::string &opName, CGALHybridPolyhedron &other,
		const std::function<void(mesh_t &destinationMesh, mesh_t &otherMesh)> &operation)
{
	SCOPED_PERFORMANCE_TIMER(std::string("mesh ") + opName);

#ifdef DEBUG
	assert(CGAL::is_closed(convertToMesh()));
	assert(CGAL::is_closed(other.convertToMesh()));
#endif

	operation(convertToMesh(), other.convertToMesh());

#ifdef DEBUG
	assert(CGAL::is_closed(*getMesh()));
#endif

	getMesh()->collect_garbage();
}

CGALHybridPolyhedron::nef_polyhedron_t &CGALHybridPolyhedron::convertToNefPolyhedron()
{
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	if (auto poly = getPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Polyhedron -> Nef");

		auto nef = make_shared<nef_polyhedron_t>(*poly);
		data = nef;
		return *nef;
	}
	else
#endif
			if (auto mesh = getMesh()) {
		SCOPED_PERFORMANCE_TIMER("Mesh -> Nef");

		auto nef = make_shared<nef_polyhedron_t>(*mesh);
		data = nef;
		return *nef;
	}
	else if (auto nef = getNefPolyhedron()) {
		return *nef;
	}
	else {
		throw "Bad data state";
	}
}

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
CGALHybridPolyhedron::polyhedron_t &CGALHybridPolyhedron::convertToPolyhedron()
{
	if (auto poly = getPolyhedron()) {
		return *poly;
	}
	else if (auto nef = getNefPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Nef -> Polyhedron");

		auto poly = make_shared<polyhedron_t>();
		nef->convert_to_polyhedron(*poly);
		data = poly;
		return *poly;
	}
	else {
		throw "Bad data state";
	}
}
#endif

CGALHybridPolyhedron::mesh_t &CGALHybridPolyhedron::convertToMesh()
{
	if (auto mesh = getMesh()) {
		return *mesh;
	}
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	else if (auto poly = getPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Polyhedron -> Mesh");

		auto mesh = make_shared<mesh_t>();
		CGAL::copy_face_graph(*poly, *mesh);
		data = mesh;
		return *mesh;
	}
#endif
	else if (auto nef = getNefPolyhedron()) {
		SCOPED_PERFORMANCE_TIMER("Nef -> Mesh");

		auto mesh = make_shared<mesh_t>();
		CGAL::convert_nef_polyhedron_to_polygon_mesh(*nef, *mesh, /* triangulate_all_faces */ true);
		data = mesh;
		return *mesh;
	}
	else {
		throw "Bad data state";
	}
}

std::shared_ptr<CGALHybridPolyhedron> CGALHybridPolyhedron::fromGeometry(const Geometry &geom)
{
	if (auto poly = dynamic_cast<const CGALHybridPolyhedron *>(&geom)) {
		return make_shared<CGALHybridPolyhedron>(*poly);
	}
	else if (auto ps = dynamic_cast<const PolySet *>(&geom)) {
		return make_shared<CGALHybridPolyhedron>(*ps);
	}
	else if (auto nef = dynamic_cast<const CGAL_Nef_polyhedron *>(&geom)) {
		assert(nef->p3);
		return nef->p3 ? make_shared<CGALHybridPolyhedron>(*nef->p3) : nullptr;
	}
	else {
		assert(!"Unsupported geometry format");
		return nullptr;
	}
}

#endif // FAST_CSG_AVAILABLE

CGALPolyhedron_mesh.h

// Portions of this file are Copyright 2021 Google LLC, and licensed under GPL2+. See COPYING.
#pragma once

#include <CGAL/version.h>
#include "cgal.h"

#define STRING2(x) #x
#define STRING(x) STRING2(x)

#if CGAL_VERSION_NR >= CGAL_VERSION_NUMBER(4, 14, 0)
#define FAST_CSG_AVAILABLE
#if CGAL_VERSION_NR >= CGAL_VERSION_NUMBER(5, 1, 0)
#define CGAL_PMP_SUPPORTS_POLYHEDRON
#else
#pragma message("[fast-csg] Polygon Mesh Processing in CGAL " STRING( \
		CGAL_VERSION) " does not handle CGAL::Polyhedron_3 well: defaulting to CGAL::Surface_mesh, which is still in development / has known bugs!")
#endif
#else
#pragma message("[fast-csg] No support for fast-csg with CGAL " STRING( \
		CGAL_VERSION) ". Please compile against CGAL 5.2 or later for the best results.")
#endif

#ifdef FAST_CSG_AVAILABLE

#include <CGAL/Surface_mesh.h>
#include <boost/variant.hpp>
#include "bounding_boxes.h"

class Geometry;
class PolySet;
class CGAL_Nef_polyhedron;

/*! A mutable polyhedron backed by a CGAL::Polyhedron_3 and fast Polygon Mesh
 * Processing (PMP) CSG functions when possible (manifold cases), or by a
 * CGAL::Nef_polyhedron_3 when it's not (non manifold cases). Experimental
 * backing by a CGAL::Surface_mesh is also available but has known crashes
 * and bugs (but it allows using CGAL versions as early as 4.14, otherwise
 * need CGAL 5.1).
 *
 * Note that even `cube(1); translate([1, 0, 0]) cube(1)` is considered
 * non-manifold because of shared vertices. PMP seems to be fine with edges
 * that share segments with others, so long as there's no shared vertex.
 *
 * Also, keeps track of the bounding boxes of past operations to fast-track
 * unions of disjoint bodies.
 *
 * TODO(ochafik): Turn this into a regular Geometry and handle it everywhere
 * the CGAL_Nef_polyhedron is handled.
 */
class CGALHybridPolyhedron
{
	// https://doc.cgal.org/latest/Kernel_d/structCGAL_1_1Epeck__d.html
	typedef CGAL::Epeck kernel_t;
	// typedef CGAL::Lazy_kernel<CGAL::Simple_cartesian<CGAL::Gmpq>> kernel_t;
	// typedef CGAL::Lazy_kernel<CGAL::Cartesian<CGAL::Gmpq>> kernel_t;
	typedef CGAL::Point_3<kernel_t> point_t;
	typedef CGAL::Surface_mesh<kernel_t::Point_3> mesh_t;
	typedef CGAL::Nef_polyhedron_3<kernel_t> nef_polyhedron_t;
	typedef CGAL::Polyhedron_3<kernel_t> polyhedron_t;

	// This contains data either as a polyhedron, or as a nef polyhedron.
	//
	// We stick to nef polyhedra in presence of non-manifold geometry (detected in
	// operations where the operands share any vertex), which breaks the
	// algorithms of Polygon Mesh Processing library that operate on normal
	// (non-nef) polyhedra.
	boost::variant<
#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
			std::shared_ptr<polyhedron_t>,
#endif
			std::shared_ptr<mesh_t>, std::shared_ptr<nef_polyhedron_t>>
			data;
	// Keeps track of the bounding boxes of the solid components of this polyhedron.
	// This allows fast unions with disjoint polyhedra.
	// TODO(ochafik): Switch to our kernel!
	BoundingBoxes<CGAL_Kernel3> bboxes;

public:
	/*! Builds a polyhedron using the provided, untrusted PolySet.
	 * Face orientation is checked (and reversed if needed), faces are
	 * triangulated (requirement of Polygon Mesh Processing functions),
	 * and we check manifoldness (we use a nef polyhedra for non-manifold cases).
	 */
	CGALHybridPolyhedron(const PolySet &ps);

	/*! Builds a polyhedron using a legacy nef polyhedron object.
	 * This transitional method will disappear when this CGALHybridPolyhedron object is
	 * fully integrated and replaces all of CGAL_Nef_polyhedron's uses.
	 */
	CGALHybridPolyhedron(const CGAL_Nef_polyhedron3 &nef);

	bool isEmpty() const;
	size_t numFacets() const;
	size_t numVertices() const;
	bool isManifold() const;
	void clear();
	/*! TODO(ochafik): Make this class inherit Geometry, plug the gaps and drop this method. */
	std::shared_ptr<const Geometry> toGeometry() const;
	std::shared_ptr<const PolySet> toPolySet() const;
	std::shared_ptr<const CGAL_Nef_polyhedron> toNefPolyhedron() const;

	/*! In-place union (this may also mutate/corefine the other polyhedron). */
	void operator+=(CGALHybridPolyhedron &other);
	/*! In-place intersection (this may also mutate/corefine the other polyhedron). */
	void operator*=(CGALHybridPolyhedron &other);
	/*! In-place difference (this may also mutate/corefine the other polyhedron). */
	void operator-=(CGALHybridPolyhedron &other);
	/*! In-place minkowksi operation. If the other polyhedron is non-convex,
	 * it is also modified during the computation, i.e., it is decomposed into convex pieces.
	 */
	void minkowski(CGALHybridPolyhedron &other);

	static std::shared_ptr<CGALHybridPolyhedron> fromGeometry(const Geometry &geom);

private:
	/*! Iterate over all vertices' points until the function returns true (for done). */
	void foreachVertexUntilTrue(const std::function<bool(const point_t &pt)> &f) const;
	bool sharesAnyVertexWith(const CGALHybridPolyhedron &other) const;
	bool needsNefForOperationWith(const CGALHybridPolyhedron &other) const;

	/*! Runs a binary operation that operates on nef polyhedra, stores the result in
	 * the first one and potentially mutates (e.g. corefines) the second. */
	void nefPolyBinOp(const std::string &opName, CGALHybridPolyhedron &other,
										const std::function<void(nef_polyhedron_t &destinationNef,
																						 nef_polyhedron_t &otherNef)> &operation);

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	/*! Runs a binary operation that operates on polyhedra, stores the result in
	 * the first one and potentially mutates (e.g. corefines) the second. */
	void polyBinOp(
			const std::string &opName, CGALHybridPolyhedron &other,
			const std::function<void(polyhedron_t &destinationPoly, polyhedron_t &otherPoly)> &operation);
#endif

	/*! Runs a binary operation that operates on polyhedra, stores the result in
	 * the first one and potentially mutates (e.g. corefines) the second. */
	void meshBinOp(const std::string &opName, CGALHybridPolyhedron &other,
								 const std::function<void(mesh_t &destinationMesh, mesh_t &otherMesh)> &operation);

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	polyhedron_t &convertToPolyhedron();
#endif
	nef_polyhedron_t &convertToNefPolyhedron();
	mesh_t &convertToMesh();

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	/*! Returns the polyhedron if that's what's in the current data, or else nullptr.
	 * Do NOT make this public. */
	polyhedron_t *getPolyhedron() const;
#endif
	/*! Returns the nef polyhedron if that's what's in the current data, or else nullptr.
	 * Do NOT make this public. */
	nef_polyhedron_t *getNefPolyhedron() const;
	mesh_t *getMesh() const;

#ifdef CGAL_PMP_SUPPORTS_POLYHEDRON
	void buildPolyhedron(const PolySet &ps);
#endif
	void buildMesh(const PolySet &ps);
};

#endif // FAST_CSG_AVAILABLE