Initial implementation of CGALRenderer

1 files changed, 487 insertions, 110 deletions

diff --git a/src/CGALRenderer.cc b/src/CGALRenderer.cc
index 2926023..d9f4c69 100644
--- a/src/CGALRenderer.cc
+++ b/src/CGALRenderer.cc
@@ -9,27 +9,28 @@
 
 #include "csgnode.h"
 #include "transformnode.h"
+#include "polyset.h"
+#include "dxfdata.h"
+#include "dxftess.h"
 
 #include <sstream>
 #include <iostream>
 #include <assert.h>
 #include <QRegExp>
 
-string CGALRenderer::getCGALMesh() const
+CGALRenderer *CGALRenderer::global_renderer = NULL;
+
+CGAL_Nef_polyhedron CGALRenderer::renderCGALMesh(const AbstractNode &node)
 {
-	assert(this->root); 
-	// FIXME: assert that cache contains root
-	return this->cache[mk_cache_id(*this->root)];
+	if (!isCached(node)) {
+		Traverser render(*this, node, Traverser::PRE_AND_POSTFIX);
+		render.execute();
+		assert(isCached(node));
+	}
+	return this->cache[mk_cache_id(node)];
 }
 
-// CGAL_Nef_polyhedron CGALRenderer::getCGALMesh() const
-// {
-// 	assert(this->root); 
-// // FIXME: assert that cache contains root
-// 	return this->cache[*this->root];
-// }
-
-bool CGALRenderer::isCached(const AbstractNode &node)
+bool CGALRenderer::isCached(const AbstractNode &node) const
 {
 	return this->cache.contains(mk_cache_id(node));
 }
@@ -38,82 +39,55 @@ bool CGALRenderer::isCached(const AbstractNode &node)
 	Modifies target by applying op to target and src:
 	target = target [op] src
  */
-void
-CGALRenderer::process(string &target, const string &src, CGALRenderer::CsgOp op)
+void CGALRenderer::process(CGAL_Nef_polyhedron &target, const CGAL_Nef_polyhedron &src, CsgOp op)
 {
-// 	if (target.dim != 2 && target.dim != 3) {
-// 		assert(false && "Dimension of Nef polyhedron must be 2 or 3");
-// 	}
-
-	switch (op) {
-	case UNION:
-		target += "+" + src;
-		break;
-	case INTERSECTION:
-		target += "*" + src;
-		break;
-	case DIFFERENCE:
-		target += "-" + src;
-		break;
-	case MINKOWSKI:
-		target += "M" + src;
-		break;
+ 	if (target.dim != 2 && target.dim != 3) {
+ 		assert(false && "Dimension of Nef polyhedron must be 2 or 3");
+ 	}
+
+	if (target.dim == 2) {
+		switch (op) {
+		case UNION:
+			target.p2 += src.p2;
+			break;
+		case INTERSECTION:
+			target.p2 *= src.p2;
+			break;
+		case DIFFERENCE:
+			target.p2 -= src.p2;
+			break;
+		case MINKOWSKI:
+			target.p2 = minkowski2(target.p2, src.p2);
+			break;
+		}
+	}
+	else if (target.dim == 3) {
+		switch (op) {
+		case UNION:
+			target.p3 += src.p3;
+			break;
+		case INTERSECTION:
+			target.p3 *= src.p3;
+			break;
+		case DIFFERENCE:
+			target.p3 -= src.p3;
+			break;
+		case MINKOWSKI:
+			target.p3 = minkowski3(target.p3, src.p3);
+			break;
+		}
 	}
 }
 
-// /*!
-// 	Modifies target by applying op to target and src:
-// 	target = target [op] src
-//  */
-// void process(CGAL_Nef_polyhedron &target, const CGAL_Nef_polyhedron &src, CsgOp op)
-// {
-// 	if (target.dim == 2) {
-// 		switch (op) {
-// 		case UNION:
-// 			target.p2 += src.p2;
-// 			break;
-// 		case INTERSECTION:
-// 			target.p2 *= src.p2;
-// 			break;
-// 		case DIFFERENCE:
-// 			target.p2 -= src.p2;
-// 			break;
-// 		case MINKOWSKI:
-// 			target.p2 = minkowski2(target.p2, src.p2);
-// 			break;
-// 		}
-// 	}
-// 	else if (target.dim == 3) {
-// 		switch (op) {
-// 		case UNION:
-// 			target.p3 += src.p3;
-// 			break;
-// 		case INTERSECTION:
-// 			target.p3 *= src.p3;
-// 			break;
-// 		case DIFFERENCE:
-// 			target.p3 -= src.p3;
-// 			break;
-// 		case MINKOWSKI:
-// 			target.p3 = minkowski3(target.p3, src.p3);
-// 			break;
-// 		}
-// 	}
-// 	else {
-// 		assert(false && "Dimention of Nef polyhedron must be 2 or 3");
-// 	}
-// }
-
+/*!
+	FIXME: Let caller insert into the cache since caller might modify the result
+  (e.g. transform)
+*/
 void CGALRenderer::applyToChildren(const AbstractNode &node, CGALRenderer::CsgOp op)
 {
-	std::stringstream stream;
-	stream << typeid(node).name();
-	stream << "<" << node.index() << ">";
-	string N = stream.str();
+	CGAL_Nef_polyhedron N;
 	if (this->visitedchildren[node.index()].size() > 0) {
-		// FIXME: assert that cache contains nodes in code below
 		bool first = true;
-//		CGAL_Nef_polyhedron N;
 		for (ChildList::const_iterator iter = this->visitedchildren[node.index()].begin();
 				 iter != this->visitedchildren[node.index()].end();
 				 iter++) {
@@ -121,16 +95,17 @@ void CGALRenderer::applyToChildren(const AbstractNode &node, CGALRenderer::CsgOp
 			const QString &chcacheid = iter->second;
 			// FIXME: Don't use deep access to modinst members
 			if (chnode->modinst->tag_background) continue;
+			assert(isCached(*chnode));
 			if (first) {
-				N += "(" + this->cache[chcacheid];
-// 				if (N.dim != 0) first = false; // FIXME: when can this happen?
-				first = false;
+				N = this->cache[chcacheid];
+				// If the first child(ren) are empty (e.g. echo) nodes, 
+				// ignore them (reset first flag)
+ 				if (N.dim != 0) first = false;
 			} else {
 				process(N, this->cache[chcacheid], op);
 			}
 			chnode->progress_report();
 		}
-		N += ")";
 	}
 	QString cacheid = mk_cache_id(node);
 	this->cache.insert(cacheid, N);
@@ -153,6 +128,7 @@ Response CGALRenderer::visit(const State &state, const AbstractNode &node)
 	return ContinueTraversal;
 }
 
+#if 0
 Response CGALRenderer::visit(const State &state, const AbstractIntersectionNode &node)
 {
 	if (state.isPrefix() && isCached(node)) return PruneTraversal;
@@ -186,6 +162,7 @@ Response CGALRenderer::visit(const State &state, const CsgNode &node)
 	}
 	return ContinueTraversal;
 }
+#endif
 
 Response CGALRenderer::visit(const State &state, const TransformNode &node)
 {
@@ -194,7 +171,43 @@ Response CGALRenderer::visit(const State &state, const TransformNode &node)
 		if (!isCached(node)) {
 			// First union all children
 			applyToChildren(node, UNION);
-			// FIXME: Then apply transform
+
+			// Then apply transform
+			QString cacheid = mk_cache_id(node);
+			CGAL_Nef_polyhedron N = this->cache[cacheid];
+			assert(N.dim >= 2 && N.dim <= 3);
+			if (N.dim == 2) {
+				// Unfortunately CGAL provides no transform method for CGAL_Nef_polyhedron2
+				// objects. So we convert in to our internal 2d data format, transform it,
+				// tesselate it and create a new CGAL_Nef_polyhedron2 from it.. What a hack!
+				
+				CGAL_Aff_transformation2 t(
+					node.m[0], node.m[4], node.m[12],
+					node.m[1], node.m[5], node.m[13], node.m[15]);
+				
+				DxfData dd(N);
+				for (int i=0; i < dd.points.size(); i++) {
+					CGAL_Kernel2::Point_2 p = CGAL_Kernel2::Point_2(dd.points[i].x, dd.points[i].y);
+					p = t.transform(p);
+					dd.points[i].x = to_double(p.x());
+					dd.points[i].y = to_double(p.y());
+				}
+				
+				PolySet ps;
+				ps.is2d = true;
+				dxf_tesselate(&ps, &dd, 0, true, false, 0);
+				
+				N = renderCGALMesh(ps);
+				ps.refcount = 0;
+			}
+			else if (N.dim == 3) {
+				CGAL_Aff_transformation t(
+					node.m[0], node.m[4], node.m[ 8], node.m[12],
+					node.m[1], node.m[5], node.m[ 9], node.m[13],
+					node.m[2], node.m[6], node.m[10], node.m[14], node.m[15]);
+				N.p3.transform(t);
+			}
+			this->cache.insert(cacheid, N);
 		}
 		addToParent(state, node);
 	}
@@ -215,35 +228,27 @@ Response CGALRenderer::visit(const State &state, const AbstractPolyNode &node)
 	if (state.isPrefix() && isCached(node)) return PruneTraversal;
 	if (state.isPostfix()) {
 		if (!isCached(node)) {
+			// First union all children
+			applyToChildren(node, UNION);
 
-	// FIXME: Manage caching
-	// FIXME: Will generate one single Nef polyhedron (no csg ops necessary)
- 
-// 	PolySet *ps = render_polyset(RENDER_CGAL);
-// 	try {
-// 		CGAL_Nef_polyhedron N = ps->renderCSGMesh();
-// 		cgal_nef_cache.insert(cache_id, new cgal_nef_cache_entry(N), N.weight());
-// 		print_messages_pop();
-// 		progress_report();
-		
-// 		ps->unlink();
-// 		return N;
-// 	}
-// 	catch (...) { // Don't leak the PolySet on ProgressCancelException
-// 		ps->unlink();
-// 		throw;
-// 	}
-
-			string N = typeid(node).name();
-			QString cacheid = mk_cache_id(node);
-			this->cache.insert(cacheid, N);
-		
-// 		std::cout << "Insert: " << N << "\n";
-// 		std::cout << "Node: " << cacheid.toStdString() << "\n\n";
+			// Then apply polyset operation
+			PolySet *ps = node.render_polyset(AbstractPolyNode::RENDER_CGAL);
+			try {
+				CGAL_Nef_polyhedron N = renderCGALMesh(*ps);
+//				print_messages_pop();
+				node.progress_report();
+				
+				ps->unlink();
+				QString cacheid = mk_cache_id(node);
+				this->cache.insert(cacheid, N);
+			}
+			catch (...) { // Don't leak the PolySet on ProgressCancelException
+				ps->unlink();
+				throw;
+			}
 		}
 		addToParent(state, node);
 	}
-
 	return ContinueTraversal;
 }
 
@@ -284,3 +289,375 @@ QString CGALRenderer::mk_cache_id(const AbstractNode &node) const
 	cache_id.remove('\n');
 	return cache_id;
 }
+
+#if 0
+/*!
+	Static function to render CGAL meshes.
+	NB! This is just a support function used for development and debugging
+*/
+CGAL_Nef_polyhedron CGALRenderer::renderCGALMesh(const AbstractPolyNode &node)
+{
+	// FIXME: Lookup Nef polyhedron in cache.
+
+	// 	print_messages_push();
+	
+	PolySet *ps = node.render_polyset(AbstractPolyNode::RENDER_CGAL);
+	try {
+		CGAL_Nef_polyhedron N = ps->renderCSGMesh();
+		// FIXME: Insert into cache
+		// print_messages_pop();
+		node.progress_report();
+		
+		ps->unlink();
+		return N;
+	}
+	catch (...) { // Don't leak the PolySet on ProgressCancelException
+		ps->unlink();
+		throw;
+	}
+}
+#endif
+
+#ifdef ENABLE_CGAL
+
+#undef GEN_SURFACE_DEBUG
+
+class CGAL_Build_PolySet : public CGAL::Modifier_base<CGAL_HDS>
+{
+public:
+	typedef CGAL_HDS::Vertex::Point Point;
+
+	const PolySet &ps;
+	CGAL_Build_PolySet(const PolySet &ps) : ps(ps) { }
+
+	void operator()(CGAL_HDS& hds)
+	{
+		CGAL_Polybuilder B(hds, true);
+
+		QList<PolySet::Point> vertices;
+		Grid3d<int> vertices_idx(GRID_FINE);
+
+		for (int i = 0; i < ps.polygons.size(); i++) {
+			const PolySet::Polygon *poly = &ps.polygons[i];
+			for (int j = 0; j < poly->size(); j++) {
+				const PolySet::Point *p = &poly->at(j);
+				if (!vertices_idx.has(p->x, p->y, p->z)) {
+					vertices_idx.data(p->x, p->y, p->z) = vertices.size();
+					vertices.append(*p);
+				}
+			}
+		}
+
+		B.begin_surface(vertices.size(), ps.polygons.size());
+#ifdef GEN_SURFACE_DEBUG
+		printf("=== CGAL Surface ===\n");
+#endif
+
+		for (int i = 0; i < vertices.size(); i++) {
+			const PolySet::Point *p = &vertices[i];
+			B.add_vertex(Point(p->x, p->y, p->z));
+#ifdef GEN_SURFACE_DEBUG
+			printf("%d: %f %f %f\n", i, p->x, p->y, p->z);
+#endif
+		}
+
+		for (int i = 0; i < ps.polygons.size(); i++) {
+			const PolySet::Polygon *poly = &ps.polygons[i];
+			QHash<int,int> fc;
+			bool facet_is_degenerated = false;
+			for (int j = 0; j < poly->size(); j++) {
+				const PolySet::Point *p = &poly->at(j);
+				int v = vertices_idx.data(p->x, p->y, p->z);
+				if (fc[v]++ > 0)
+					facet_is_degenerated = true;
+			}
+			
+			if (!facet_is_degenerated)
+				B.begin_facet();
+#ifdef GEN_SURFACE_DEBUG
+			printf("F:");
+#endif
+			for (int j = 0; j < poly->size(); j++) {
+				const PolySet::Point *p = &poly->at(j);
+#ifdef GEN_SURFACE_DEBUG
+				printf(" %d (%f,%f,%f)", vertices_idx.data(p->x, p->y, p->z), p->x, p->y, p->z);
+#endif
+				if (!facet_is_degenerated)
+					B.add_vertex_to_facet(vertices_idx.data(p->x, p->y, p->z));
+			}
+#ifdef GEN_SURFACE_DEBUG
+			if (facet_is_degenerated)
+				printf(" (degenerated)");
+			printf("\n");
+#endif
+			if (!facet_is_degenerated)
+				B.end_facet();
+		}
+
+#ifdef GEN_SURFACE_DEBUG
+		printf("====================\n");
+#endif
+		B.end_surface();
+
+		#undef PointKey
+	}
+};
+
+#endif /* ENABLE_CGAL */
+
+CGAL_Nef_polyhedron CGALRenderer::renderCGALMesh(const PolySet &ps)
+{
+	if (ps.is2d)
+	{
+#if 0
+		// This version of the code causes problems in some cases.
+		// Example testcase: import_dxf("testdata/polygon8.dxf");
+		//
+		typedef std::list<CGAL_Nef_polyhedron2::Point> point_list_t;
+		typedef point_list_t::iterator point_list_it;
+		std::list< point_list_t > pdata_point_lists;
+		std::list < std::pair < point_list_it, point_list_it > > pdata;
+		Grid2d<CGAL_Nef_polyhedron2::Point> grid(GRID_COARSE);
+
+		for (int i = 0; i < ps.polygons.size(); i++) {
+			pdata_point_lists.push_back(point_list_t());
+			for (int j = 0; j < ps.polygons[i].size(); j++) {
+				double x = ps.polygons[i][j].x;
+				double y = ps.polygons[i][j].y;
+				CGAL_Nef_polyhedron2::Point p;
+				if (grid.has(x, y)) {
+					p = grid.data(x, y);
+				} else {
+					p = CGAL_Nef_polyhedron2::Point(x, y);
+					grid.data(x, y) = p;
+				}
+				pdata_point_lists.back().push_back(p);
+			}
+			pdata.push_back(std::make_pair(pdata_point_lists.back().begin(),
+					pdata_point_lists.back().end()));
+		}
+
+		CGAL_Nef_polyhedron2 N(pdata.begin(), pdata.end(), CGAL_Nef_polyhedron2::POLYGONS);
+		return CGAL_Nef_polyhedron(N);
+#endif
+#if 0
+		// This version of the code works fine but is pretty slow.
+		//
+		CGAL_Nef_polyhedron2 N;
+		Grid2d<CGAL_Nef_polyhedron2::Point> grid(GRID_COARSE);
+
+		for (int i = 0; i < ps.polygons.size(); i++) {
+			std::list<CGAL_Nef_polyhedron2::Point> plist;
+			for (int j = 0; j < ps.polygons[i].size(); j++) {
+				double x = ps.polygons[i][j].x;
+				double y = ps.polygons[i][j].y;
+				CGAL_Nef_polyhedron2::Point p;
+				if (grid.has(x, y)) {
+					p = grid.data(x, y);
+				} else {
+					p = CGAL_Nef_polyhedron2::Point(x, y);
+					grid.data(x, y) = p;
+				}
+				plist.push_back(p);
+			}
+			N += CGAL_Nef_polyhedron2(plist.begin(), plist.end(), CGAL_Nef_polyhedron2::INCLUDED);
+		}
+
+		return CGAL_Nef_polyhedron(N);
+#endif
+#if 1
+		// This version of the code does essentially the same thing as the 2nd
+		// version but merges some triangles before sending them to CGAL. This adds
+		// complexity but speeds up things..
+		//
+		struct PolyReducer
+		{
+			Grid2d<int> grid;
+			QHash< QPair<int,int>, QPair<int,int> > egde_to_poly;
+			QHash< int, CGAL_Nef_polyhedron2::Point > points;
+			QHash< int, QList<int> > polygons;
+			int poly_n;
+
+			void add_edges(int pn)
+			{
+				for (int j = 1; j <= this->polygons[pn].size(); j++) {
+					int a = this->polygons[pn][j-1];
+					int b = this->polygons[pn][j % this->polygons[pn].size()];
+					if (a > b) { a = a^b; b = a^b; a = a^b; }
+					if (this->egde_to_poly[QPair<int,int>(a, b)].first == 0)
+						this->egde_to_poly[QPair<int,int>(a, b)].first = pn;
+					else if (this->egde_to_poly[QPair<int,int>(a, b)].second == 0)
+						this->egde_to_poly[QPair<int,int>(a, b)].second = pn;
+					else
+						abort();
+				}
+			}
+
+			void del_poly(int pn)
+			{
+				for (int j = 1; j <= this->polygons[pn].size(); j++) {
+					int a = this->polygons[pn][j-1];
+					int b = this->polygons[pn][j % this->polygons[pn].size()];
+					if (a > b) { a = a^b; b = a^b; a = a^b; }
+					if (this->egde_to_poly[QPair<int,int>(a, b)].first == pn)
+						this->egde_to_poly[QPair<int,int>(a, b)].first = 0;
+					if (this->egde_to_poly[QPair<int,int>(a, b)].second == pn)
+						this->egde_to_poly[QPair<int,int>(a, b)].second = 0;
+				}
+				this->polygons.remove(pn);
+			}
+
+			PolyReducer(const PolySet &ps) : grid(GRID_COARSE), poly_n(1)
+			{
+				int point_n = 1;
+				for (int i = 0; i < ps.polygons.size(); i++) {
+					for (int j = 0; j < ps.polygons[i].size(); j++) {
+						double x = ps.polygons[i][j].x;
+						double y = ps.polygons[i][j].y;
+						if (this->grid.has(x, y)) {
+							this->polygons[this->poly_n].append(this->grid.data(x, y));
+						} else {
+							this->grid.align(x, y) = point_n;
+							this->polygons[this->poly_n].append(point_n);
+							this->points[point_n] = CGAL_Nef_polyhedron2::Point(x, y);
+							point_n++;
+						}
+					}
+					add_edges(this->poly_n);
+					this->poly_n++;
+				}
+			}
+
+			int merge(int p1, int p1e, int p2, int p2e)
+			{
+				for (int i = 1; i < this->polygons[p1].size(); i++) {
+					int j = (p1e + i) % this->polygons[p1].size();
+					this->polygons[this->poly_n].append(this->polygons[p1][j]);
+				}
+				for (int i = 1; i < this->polygons[p2].size(); i++) {
+					int j = (p2e + i) % this->polygons[p2].size();
+					this->polygons[this->poly_n].append(this->polygons[p2][j]);
+				}
+				del_poly(p1);
+				del_poly(p2);
+				add_edges(this->poly_n);
+				return this->poly_n++;
+			}
+
+			void reduce()
+			{
+				QList<int> work_queue;
+				QHashIterator< int, QList<int> > it(polygons);
+				while (it.hasNext()) {
+					it.next();
+					work_queue.append(it.key());
+				}
+				while (!work_queue.isEmpty()) {
+					int poly1_n = work_queue.first();
+					work_queue.removeFirst();
+					if (!this->polygons.contains(poly1_n))
+						continue;
+					for (int j = 1; j <= this->polygons[poly1_n].size(); j++) {
+						int a = this->polygons[poly1_n][j-1];
+						int b = this->polygons[poly1_n][j % this->polygons[poly1_n].size()];
+						if (a > b) { a = a^b; b = a^b; a = a^b; }
+						if (this->egde_to_poly[QPair<int,int>(a, b)].first != 0 &&
+								this->egde_to_poly[QPair<int,int>(a, b)].second != 0) {
+							int poly2_n = this->egde_to_poly[QPair<int,int>(a, b)].first +
+									this->egde_to_poly[QPair<int,int>(a, b)].second - poly1_n;
+							int poly2_edge = -1;
+							for (int k = 1; k <= this->polygons[poly2_n].size(); k++) {
+								int c = this->polygons[poly2_n][k-1];
+								int d = this->polygons[poly2_n][k % this->polygons[poly2_n].size()];
+								if (c > d) { c = c^d; d = c^d; c = c^d; }
+								if (a == c && b == d) {
+									poly2_edge = k-1;
+									continue;
+								}
+								int poly3_n = this->egde_to_poly[QPair<int,int>(c, d)].first +
+										this->egde_to_poly[QPair<int,int>(c, d)].second - poly2_n;
+								if (poly3_n < 0)
+									continue;
+								if (poly3_n == poly1_n)
+									goto next_poly1_edge;
+							}
+							work_queue.append(merge(poly1_n, j-1, poly2_n, poly2_edge));
+							goto next_poly1;
+						}
+					next_poly1_edge:;
+					}
+				next_poly1:;
+				}
+			}
+
+			CGAL_Nef_polyhedron2 toNef()
+			{
+				CGAL_Nef_polyhedron2 N;
+
+				QHashIterator< int, QList<int> > it(polygons);
+				while (it.hasNext()) {
+					it.next();
+					std::list<CGAL_Nef_polyhedron2::Point> plist;
+					for (int j = 0; j < it.value().size(); j++) {
+						int p = it.value()[j];
+						plist.push_back(points[p]);
+					}
+					N += CGAL_Nef_polyhedron2(plist.begin(), plist.end(), CGAL_Nef_polyhedron2::INCLUDED);
+				}
+
+				return N;
+			}
+		};
+
+		PolyReducer pr(ps);
+		// printf("Number of polygons before reduction: %d\n", pr.polygons.size());
+		pr.reduce();
+		// printf("Number of polygons after reduction: %d\n", pr.polygons.size());
+		return CGAL_Nef_polyhedron(pr.toNef());
+#endif
+#if 0
+		// This is another experimental version. I should run faster than the above,
+		// is a lot simpler and has only one known weakness: Degenerate polygons, which
+		// get repaired by GLUTess, might trigger a CGAL crash here. The only
+		// known case for this is triangle-with-duplicate-vertex.dxf
+		// FIXME: If we just did a projection, we need to recreate the border!
+		if (ps.polygons.size() > 0) assert(ps.borders.size() > 0);
+		CGAL_Nef_polyhedron2 N;
+		Grid2d<CGAL_Nef_polyhedron2::Point> grid(GRID_COARSE);
+
+		for (int i = 0; i < ps.borders.size(); i++) {
+			std::list<CGAL_Nef_polyhedron2::Point> plist;
+			for (int j = 0; j < ps.borders[i].size(); j++) {
+				double x = ps.borders[i][j].x;
+				double y = ps.borders[i][j].y;
+				CGAL_Nef_polyhedron2::Point p;
+				if (grid.has(x, y)) {
+					p = grid.data(x, y);
+				} else {
+					p = CGAL_Nef_polyhedron2::Point(x, y);
+					grid.data(x, y) = p;
+				}
+				plist.push_back(p);		
+			}
+			// FIXME: If a border (path) has a duplicate vertex in dxf,
+			// the CGAL_Nef_polyhedron2 constructor will crash.
+			N ^= CGAL_Nef_polyhedron2(plist.begin(), plist.end(), CGAL_Nef_polyhedron2::INCLUDED);
+		}
+
+		return CGAL_Nef_polyhedron(N);
+
+#endif
+	}
+	else
+	{
+		CGAL_Polyhedron P;
+		CGAL_Build_PolySet builder(ps);
+		P.delegate(builder);
+#if 0
+		std::cout << P;
+#endif
+		CGAL_Nef_polyhedron3 N(P);
+		return CGAL_Nef_polyhedron(N);
+	}
+	return CGAL_Nef_polyhedron();
+}