Remove Carve boolean

We've got quite comprehensive BMesh based implementation, which is way easier
for maintenance than abandoned Carve library.

After all the time BMesh implementation was working on the same level of
limitations about manifold meshes and touching edges than Carve. Is better
to focus on maintaining one boolean implementation now.

Reviewers: campbellbarton

Reviewed By: campbellbarton

Differential Revision: https://developer.blender.org/D3050

1 files changed, 0 insertions, 1107 deletions

diff --git a/extern/carve/lib/polyhedron.cpp b/extern/carve/lib/polyhedron.cpp
deleted file mode 100644
index d402fce36df..00000000000
--- a/extern/carve/lib/polyhedron.cpp
+++ /dev/null
@@ -1,1107 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#if defined(HAVE_CONFIG_H)
-#  include <carve_config.h>
-#endif
-
-#if defined(CARVE_DEBUG)
-#define DEBUG_CONTAINS_VERTEX
-#endif
-
-#include <carve/djset.hpp>
-
-#include <carve/geom.hpp>
-#include <carve/poly.hpp>
-
-#include <carve/octree_impl.hpp>
-
-#include <carve/timing.hpp>
-
-#include <algorithm>
-
-#include <carve/mesh.hpp>
-
-#ifdef HAVE_BOOST_LIBRARY
-#  include BOOST_INCLUDE(random.hpp)
-#else
-#  include <carve/random/random.h>
-#endif
-
-namespace {
-  bool emb_test(carve::poly::Polyhedron *poly,
-                std::map<int, std::set<int> > &embedding,
-                carve::geom3d::Vector v,
-                int m_id) {
-
-    std::map<int, carve::PointClass> result;
-#if defined(CARVE_DEBUG)
-    std::cerr << "test " << v << " (m_id:" << m_id << ")" << std::endl;
-#endif
-    poly->testVertexAgainstClosedManifolds(v, result, true);
-    std::set<int> inside;
-    for (std::map<int, carve::PointClass>::iterator j = result.begin();
-         j != result.end();
-         ++j) {
-      if ((*j).first == m_id) continue;
-      if ((*j).second == carve::POINT_IN) inside.insert((*j).first);
-      else if ((*j).second == carve::POINT_ON) {
-#if defined(CARVE_DEBUG)
-        std::cerr << " FAIL" << std::endl;
-#endif
-        return false;
-      }
-    }
-#if defined(CARVE_DEBUG)
-    std::cerr << " OK (inside.size()==" << inside.size() << ")" << std::endl;
-#endif
-    embedding[m_id] = inside;
-    return true;
-  }
-
-
-
-  struct order_faces {
-    bool operator()(const carve::poly::Polyhedron::face_t * const &a,
-                    const carve::poly::Polyhedron::face_t * const &b) const {
-      return std::lexicographical_compare(a->vbegin(), a->vend(), b->vbegin(), b->vend());
-    }
-  };
-
-
-
-}
-
-
-
-namespace carve {
-  namespace poly {
-
-
-
-    bool Polyhedron::initSpatialIndex() {
-      static carve::TimingName FUNC_NAME("Polyhedron::initSpatialIndex()");
-      carve::TimingBlock block(FUNC_NAME);
-
-      octree.setBounds(aabb);
-      octree.addFaces(faces);
-      octree.addEdges(edges);
-      octree.splitTree();
-
-      return true;
-    }
-
-
-
-    void Polyhedron::invertAll() {
-      for (size_t i = 0; i < faces.size(); ++i) {
-        faces[i].invert();
-      }
-
-      for (size_t i = 0; i < edges.size(); ++i) {
-        std::vector<const face_t *> &f = connectivity.edge_to_face[i];
-        for (size_t j = 0; j < (f.size() & ~1U); j += 2) {
-          std::swap(f[j], f[j+1]);
-        }
-      }
-
-      for (size_t i = 0; i < manifold_is_negative.size(); ++i) {
-        manifold_is_negative[i] = !manifold_is_negative[i];
-      }
-    }
-
-
-
-    void Polyhedron::invert(const std::vector<bool> &selected_manifolds) {
-      bool altered = false;
-      for (size_t i = 0; i < faces.size(); ++i) {
-        if (faces[i].manifold_id >= 0 &&
-            (unsigned)faces[i].manifold_id < selected_manifolds.size() &&
-            selected_manifolds[faces[i].manifold_id]) {
-          altered = true;
-          faces[i].invert();
-        }
-      }
-
-      if (altered) {
-        for (size_t i = 0; i < edges.size(); ++i) {
-          std::vector<const face_t *> &f = connectivity.edge_to_face[i];
-          for (size_t j = 0; j < (f.size() & ~1U); j += 2) {
-            int m_id = -1;
-            if (f[j]) m_id = f[j]->manifold_id;
-            if (f[j+1]) m_id = f[j+1]->manifold_id;
-            if (m_id >= 0 && (unsigned)m_id < selected_manifolds.size() && selected_manifolds[m_id]) {
-              std::swap(f[j], f[j+1]);
-            }
-          }
-        }
-
-        for (size_t i = 0; i < std::min(selected_manifolds.size(), manifold_is_negative.size()); ++i) {
-          manifold_is_negative[i] = !manifold_is_negative[i];
-        }
-      }
-    }
-
-
-
-    void Polyhedron::initVertexConnectivity() {
-      static carve::TimingName FUNC_NAME("static Polyhedron initVertexConnectivity()");
-      carve::TimingBlock block(FUNC_NAME);
-
-      // allocate space for connectivity info.
-      connectivity.vertex_to_edge.resize(vertices.size());
-      connectivity.vertex_to_face.resize(vertices.size());
-
-      std::vector<size_t> vertex_face_count;
-
-      vertex_face_count.resize(vertices.size());
-
-      // work out how many faces/edges each vertex is connected to, in
-      // order to save on array reallocs.
-      for (unsigned i = 0; i < faces.size(); ++i) {
-        face_t &f = faces[i];
-        for (unsigned j = 0; j < f.nVertices(); j++) {
-          vertex_face_count[vertexToIndex_fast(f.vertex(j))]++;
-        }
-      }
-
-      for (size_t i = 0; i < vertices.size(); ++i) {
-        connectivity.vertex_to_edge[i].reserve(vertex_face_count[i]);
-        connectivity.vertex_to_face[i].reserve(vertex_face_count[i]);
-      }
-
-      // record connectivity from vertex to edges.
-      for (size_t i = 0; i < edges.size(); ++i) {
-        size_t v1i = vertexToIndex_fast(edges[i].v1);
-        size_t v2i = vertexToIndex_fast(edges[i].v2);
-
-        connectivity.vertex_to_edge[v1i].push_back(&edges[i]);
-        connectivity.vertex_to_edge[v2i].push_back(&edges[i]);
-      }
-
-      // record connectivity from vertex to faces.
-      for (size_t i = 0; i < faces.size(); ++i) {
-        face_t &f = faces[i];
-        for (unsigned j = 0; j < f.nVertices(); j++) {
-          size_t vi = vertexToIndex_fast(f.vertex(j));
-          connectivity.vertex_to_face[vi].push_back(&f);
-        }
-      }
-    }
-
-
-
-    bool Polyhedron::initConnectivity() {
-      static carve::TimingName FUNC_NAME("Polyhedron::initConnectivity()");
-      carve::TimingBlock block(FUNC_NAME);
-
-      // temporary measure: initialize connectivity by creating a
-      // half-edge mesh, and then converting back.
-
-      std::vector<mesh::Vertex<3> > vertex_storage;
-      vertex_storage.reserve(vertices.size());
-      for (size_t i = 0; i < vertices.size(); ++i) {
-        vertex_storage.push_back(mesh::Vertex<3>(vertices[i].v));
-      }
-
-      std::vector<mesh::Face<3> *> mesh_faces;
-      std::unordered_map<const mesh::Face<3> *, size_t> face_map;
-      {
-        std::vector<mesh::Vertex<3> *> vert_ptrs;
-        for (size_t i = 0; i < faces.size(); ++i) {
-          const face_t &src = faces[i];
-          vert_ptrs.clear();
-          vert_ptrs.reserve(src.nVertices());
-          for (size_t j = 0; j < src.nVertices(); ++j) {
-            size_t vi = vertexToIndex_fast(src.vertex(j));
-            vert_ptrs.push_back(&vertex_storage[vi]);
-          }
-          mesh::Face<3> *face = new mesh::Face<3>(vert_ptrs.begin(), vert_ptrs.end());
-          mesh_faces.push_back(face);
-          face_map[face] = i;
-        }
-      }
-
-      std::vector<mesh::Mesh<3> *> meshes;
-      mesh::Mesh<3>::create(mesh_faces.begin(), mesh_faces.end(), meshes, mesh::MeshOptions());
-      mesh::MeshSet<3> *meshset = new mesh::MeshSet<3>(vertex_storage, meshes);
-
-      manifold_is_closed.resize(meshset->meshes.size());
-      manifold_is_negative.resize(meshset->meshes.size());
-
-      std::unordered_map<std::pair<size_t, size_t>, std::list<mesh::Edge<3> *> > edge_map;
-
-      if (meshset->vertex_storage.size()) {
-        mesh::Vertex<3> *Vbase = &meshset->vertex_storage[0];
-        for (size_t m = 0; m < meshset->meshes.size(); ++m) {
-          mesh::Mesh<3> *mesh = meshset->meshes[m];
-          manifold_is_closed[m] = mesh->isClosed();
-          for (size_t f = 0; f < mesh->faces.size(); ++f) {
-            mesh::Face<3> *src = mesh->faces[f];
-            mesh::Edge<3> *e = src->edge;
-            faces[face_map[src]].manifold_id = m;
-            do {
-              edge_map[std::make_pair(e->v1() - Vbase, e->v2() - Vbase)].push_back(e);
-              e = e->next;
-            } while (e != src->edge);
-          }
-        }
-      }
-
-      size_t n_edges = 0;
-      for (std::unordered_map<std::pair<size_t, size_t>, std::list<mesh::Edge<3> *> >::iterator i = edge_map.begin(); i != edge_map.end(); ++i) {
-        if ((*i).first.first < (*i).first.second || edge_map.find(std::make_pair((*i).first.second, (*i).first.first)) == edge_map.end()) {
-          n_edges++;
-        }
-      }
-
-      edges.clear();
-      edges.reserve(n_edges);
-      for (std::unordered_map<std::pair<size_t, size_t>, std::list<mesh::Edge<3> *> >::iterator i = edge_map.begin(); i != edge_map.end(); ++i) {
-        if ((*i).first.first < (*i).first.second || edge_map.find(std::make_pair((*i).first.second, (*i).first.first)) == edge_map.end()) {
-          edges.push_back(edge_t(&vertices[(*i).first.first], &vertices[(*i).first.second], this));
-        }
-      }
-
-      initVertexConnectivity();
-
-      for (size_t f = 0; f < faces.size(); ++f) {
-        face_t &face = faces[f];
-        size_t N = face.nVertices();
-        for (size_t v = 0; v < N; ++v) {
-          size_t v1i = vertexToIndex_fast(face.vertex(v));
-          size_t v2i = vertexToIndex_fast(face.vertex((v+1)%N));
-          std::vector<const edge_t *> found_edge;
-
-          CARVE_ASSERT(carve::is_sorted(connectivity.vertex_to_edge[v1i].begin(), connectivity.vertex_to_edge[v1i].end()));
-          CARVE_ASSERT(carve::is_sorted(connectivity.vertex_to_edge[v2i].begin(), connectivity.vertex_to_edge[v2i].end()));
-
-          std::set_intersection(connectivity.vertex_to_edge[v1i].begin(), connectivity.vertex_to_edge[v1i].end(),
-                                connectivity.vertex_to_edge[v2i].begin(), connectivity.vertex_to_edge[v2i].end(),
-                                std::back_inserter(found_edge));
-
-          CARVE_ASSERT(found_edge.size() == 1);
-
-          face.edge(v) = found_edge[0];
-        }
-      }
-
-      connectivity.edge_to_face.resize(edges.size());
-
-      for (size_t i = 0; i < edges.size(); ++i) {
-        size_t v1i = vertexToIndex_fast(edges[i].v1);
-        size_t v2i = vertexToIndex_fast(edges[i].v2);
-        std::list<mesh::Edge<3> *> &efwd = edge_map[std::make_pair(v1i, v2i)];
-        std::list<mesh::Edge<3> *> &erev = edge_map[std::make_pair(v1i, v2i)];
-
-        for (std::list<mesh::Edge<3> *>::iterator j = efwd.begin(); j != efwd.end(); ++j) {
-          mesh::Edge<3> *edge = *j;
-          if (face_map.find(edge->face) != face_map.end()) {
-            connectivity.edge_to_face[i].push_back(&faces[face_map[edge->face]]);
-            if (edge->rev == NULL) {
-              connectivity.edge_to_face[i].push_back(NULL);
-            } else {
-              connectivity.edge_to_face[i].push_back(&faces[face_map[edge->rev->face]]);
-            }
-          }
-        }
-        for (std::list<mesh::Edge<3> *>::iterator j = erev.begin(); j != erev.end(); ++j) {
-          mesh::Edge<3> *edge = *j;
-          if (face_map.find(edge->face) != face_map.end()) {
-            if (edge->rev == NULL) {
-              connectivity.edge_to_face[i].push_back(NULL);
-              connectivity.edge_to_face[i].push_back(&faces[face_map[edge->face]]);
-            }
-          }
-        }
-      }
-
-      delete meshset;
-
-      return true;
-    }
-
-
-
-    bool Polyhedron::calcManifoldEmbedding() {
-      // this could be significantly sped up using bounding box tests
-      // to work out what pairs of manifolds are embedding candidates.
-      // A per-manifold AABB could also be used to speed up
-      // testVertexAgainstClosedManifolds().
-
-      static carve::TimingName FUNC_NAME("Polyhedron::calcManifoldEmbedding()");
-      static carve::TimingName CME_V("Polyhedron::calcManifoldEmbedding() (vertices)");
-      static carve::TimingName CME_E("Polyhedron::calcManifoldEmbedding() (edges)");
-      static carve::TimingName CME_F("Polyhedron::calcManifoldEmbedding() (faces)");
-
-      carve::TimingBlock block(FUNC_NAME);
-
-      const unsigned MCOUNT = manifoldCount();
-      if (MCOUNT < 2) return true;
-
-      std::set<int> vertex_manifolds;
-      std::map<int, std::set<int> > embedding;
-
-      carve::Timing::start(CME_V);
-      for (size_t i = 0; i < vertices.size(); ++i) {
-        vertex_manifolds.clear();
-        if (vertexManifolds(&vertices[i], set_inserter(vertex_manifolds)) != 1) continue;
-        int m_id = *vertex_manifolds.begin();
-        if (embedding.find(m_id) == embedding.end()) {
-          if (emb_test(this, embedding, vertices[i].v, m_id) && embedding.size() == MCOUNT) {
-            carve::Timing::stop();
-            goto done;
-          }
-        }
-      }
-      carve::Timing::stop();
-
-      carve::Timing::start(CME_E);
-      for (size_t i = 0; i < edges.size(); ++i) {
-        if (connectivity.edge_to_face[i].size() == 2) {
-          int m_id;
-          const face_t *f1 = connectivity.edge_to_face[i][0];
-          const face_t *f2 = connectivity.edge_to_face[i][1];
-          if (f1) m_id = f1->manifold_id;
-          if (f2) m_id = f2->manifold_id;
-          if (embedding.find(m_id) == embedding.end()) {
-            if (emb_test(this, embedding, (edges[i].v1->v + edges[i].v2->v) / 2, m_id) && embedding.size() == MCOUNT) {
-              carve::Timing::stop();
-              goto done;
-            }
-          }
-        }
-      }
-      carve::Timing::stop();
-
-      carve::Timing::start(CME_F);
-      for (size_t i = 0; i < faces.size(); ++i) {
-        int m_id = faces[i].manifold_id;
-        if (embedding.find(m_id) == embedding.end()) {
-          carve::geom2d::P2 pv;
-          if (!carve::geom2d::pickContainedPoint(faces[i].projectedVertices(), pv)) continue;
-          carve::geom3d::Vector v = carve::poly::face::unproject(faces[i], pv);
-          if (emb_test(this, embedding, v, m_id) && embedding.size() == MCOUNT) {
-            carve::Timing::stop();
-            goto done;
-          }
-        }
-      }
-      carve::Timing::stop();
-
-      CARVE_FAIL("could not find test points");
-
-      // std::cerr << "could not find test points!!!" << std::endl;
-      // return true;
-    done:;
-      for (std::map<int, std::set<int> >::iterator i = embedding.begin(); i != embedding.end(); ++i) {
-#if defined(CARVE_DEBUG)
-        std::cerr << (*i).first << " : ";
-        std::copy((*i).second.begin(), (*i).second.end(), std::ostream_iterator<int>(std::cerr, ","));
-        std::cerr << std::endl;
-#endif
-        (*i).second.insert(-1);
-      }
-      std::set<int> parents, new_parents;
-      parents.insert(-1);
-
-      while (embedding.size()) {
-        new_parents.clear();
-        for (std::map<int, std::set<int> >::iterator i = embedding.begin(); i != embedding.end(); ++i) {
-          if ((*i).second.size() == 1) {
-            if (parents.find(*(*i).second.begin()) != parents.end()) {
-              new_parents.insert((*i).first);
-#if defined(CARVE_DEBUG)
-              std::cerr << "parent(" << (*i).first << "): " << *(*i).second.begin() << std::endl;
-#endif
-            } else {
-#if defined(CARVE_DEBUG)
-              std::cerr << "no parent: " << (*i).first << " (looking for: " << *(*i).second.begin() << ")" << std::endl;
-#endif
-            }
-          }
-        }
-        for (std::set<int>::const_iterator i = new_parents.begin(); i != new_parents.end(); ++i) {
-          embedding.erase(*i);
-        }
-        for (std::map<int, std::set<int> >::iterator i = embedding.begin(); i != embedding.end(); ++i) {
-          size_t n = 0;
-          for (std::set<int>::const_iterator j = parents.begin(); j != parents.end(); ++j) {
-            n += (*i).second.erase((*j));
-          }
-          CARVE_ASSERT(n != 0);
-        }
-        parents.swap(new_parents);
-      }
-
-      return true;
-    }
-
-
-
-    bool Polyhedron::init() {
-      static carve::TimingName FUNC_NAME("Polyhedron::init()");
-      carve::TimingBlock block(FUNC_NAME);
-  
-      aabb.fit(vertices.begin(), vertices.end(), vec_adapt_vertex_ref());
-
-      connectivity.vertex_to_edge.clear();
-      connectivity.vertex_to_face.clear();
-      connectivity.edge_to_face.clear();
-
-      if (!initConnectivity()) return false;
-      if (!initSpatialIndex()) return false;
-
-      return true;
-    }
-
-
-
-    void Polyhedron::faceRecalc() {
-      for (size_t i = 0; i < faces.size(); ++i) {
-        if (!faces[i].recalc()) {
-          std::ostringstream out;
-          out << "face " << i << " recalc failed";
-          throw carve::exception(out.str());
-        }
-      }
-    }
-
-
-
-    Polyhedron::Polyhedron(const Polyhedron &poly) {
-      faces.reserve(poly.faces.size());
-
-      for (size_t i = 0; i < poly.faces.size(); ++i) {
-        const face_t &src = poly.faces[i];
-        faces.push_back(src);
-      }
-      commonFaceInit(false); // calls setFaceAndVertexOwner() and init()
-    }
-
-
-
-    Polyhedron::Polyhedron(const Polyhedron &poly, const std::vector<bool> &selected_manifolds) {
-      size_t n_faces = 0;
-
-      for (size_t i = 0; i < poly.faces.size(); ++i) {
-        const face_t &src = poly.faces[i];
-        if (src.manifold_id >= 0 &&
-            (unsigned)src.manifold_id < selected_manifolds.size() &&
-            selected_manifolds[src.manifold_id]) {
-          n_faces++;
-        }
-      }
-
-      faces.reserve(n_faces);
-
-      for (size_t i = 0; i < poly.faces.size(); ++i) {
-        const face_t &src = poly.faces[i];
-        if (src.manifold_id >= 0 &&
-            (unsigned)src.manifold_id < selected_manifolds.size() &&
-            selected_manifolds[src.manifold_id]) {
-          faces.push_back(src);
-        }
-      }
-
-      commonFaceInit(false); // calls setFaceAndVertexOwner() and init()
-    }
-
-
-
-    Polyhedron::Polyhedron(const Polyhedron &poly, int m_id) {
-      size_t n_faces = 0;
-
-      for (size_t i = 0; i < poly.faces.size(); ++i) {
-        const face_t &src = poly.faces[i];
-        if (src.manifold_id == m_id) n_faces++;
-      }
-
-      faces.reserve(n_faces);
-
-      for (size_t i = 0; i < poly.faces.size(); ++i) {
-        const face_t &src = poly.faces[i];
-        if (src.manifold_id == m_id) faces.push_back(src);
-      }
-
-      commonFaceInit(false); // calls setFaceAndVertexOwner() and init()
-    }
-
-
-
-    Polyhedron::Polyhedron(const std::vector<carve::geom3d::Vector> &_vertices,
-                           int n_faces,
-                           const std::vector<int> &face_indices) {
-      // The polyhedron is defined by a vector of vertices, which we
-      // want to copy, and a face index list, from which we need to
-      // generate a set of Faces.
-
-      vertices.clear();
-      vertices.resize(_vertices.size());
-      for (size_t i = 0; i < _vertices.size(); ++i) {
-        vertices[i].v = _vertices[i];
-      }
-
-      faces.reserve(n_faces);
-  
-      std::vector<int>::const_iterator iter = face_indices.begin();
-      std::vector<const vertex_t *> v;
-      for (int i = 0; i < n_faces; ++i) {
-        int vertexCount = *iter++;
-    
-        v.clear();
-    
-        while (vertexCount--) {
-          CARVE_ASSERT(*iter >= 0);
-          CARVE_ASSERT((unsigned)*iter < vertices.size());
-          v.push_back(&vertices[*iter++]);
-        }
-        faces.push_back(face_t(v));
-      }
-
-      setFaceAndVertexOwner();
-
-      if (!init()) {
-        throw carve::exception("polyhedron creation failed");
-      }
-    }
-
-
-
-    Polyhedron::Polyhedron(std::vector<face_t> &_faces,
-                           std::vector<vertex_t> &_vertices,
-                           bool _recalc) {
-      faces.swap(_faces);
-      vertices.swap(_vertices);
-
-      setFaceAndVertexOwner();
-
-      if (_recalc) faceRecalc();
-
-      if (!init()) {
-        throw carve::exception("polyhedron creation failed");
-      }
-    }
-
-
-
-    Polyhedron::Polyhedron(std::vector<face_t> &_faces,
-                           bool _recalc) {
-      faces.swap(_faces);
-      commonFaceInit(_recalc); // calls setFaceAndVertexOwner() and init()
-    }
-
-
-
-    Polyhedron::Polyhedron(std::list<face_t> &_faces,
-                           bool _recalc) {
-      faces.reserve(_faces.size());
-      std::copy(_faces.begin(), _faces.end(), std::back_inserter(faces));
-      commonFaceInit(_recalc); // calls setFaceAndVertexOwner() and init()
-    }
-
-
-
-    void Polyhedron::collectFaceVertices(std::vector<face_t> &faces,
-                                         std::vector<vertex_t> &vertices,
-                                         std::unordered_map<const vertex_t *, const vertex_t *> &vmap) {
-      // Given a set of faces, copy all referenced vertices into a
-      // single vertex array and update the faces to point into that
-      // array. On exit, vmap contains a mapping from old pointer to
-      // new pointer.
-
-      vertices.clear();
-      vmap.clear();
-
-      for (size_t i = 0, il = faces.size(); i != il; ++i) {
-        face_t &f = faces[i];
-
-        for (size_t j = 0, jl = f.nVertices(); j != jl; ++j) {
-          vmap[f.vertex(j)] = NULL;
-        }
-      }
-
-      vertices.reserve(vmap.size());
-
-      for (std::unordered_map<const vertex_t *, const vertex_t *>::iterator i = vmap.begin(),
-             e = vmap.end();
-           i != e;
-           ++i) {
-        vertices.push_back(*(*i).first);
-        (*i).second = &vertices.back();
-      }
-
-      for (size_t i = 0, il = faces.size(); i != il; ++i) {
-        face_t &f = faces[i];
-
-        for (size_t j = 0, jl = f.nVertices(); j != jl; ++j) {
-          f.vertex(j) = vmap[f.vertex(j)];
-        }
-      }
-    }
-
-
-
-    void Polyhedron::collectFaceVertices(std::vector<face_t> &faces,
-                                         std::vector<vertex_t> &vertices) {
-      std::unordered_map<const vertex_t *, const vertex_t *> vmap;
-      collectFaceVertices(faces, vertices, vmap);
-    }
-
-
-
-    void Polyhedron::setFaceAndVertexOwner() {
-      for (size_t i = 0; i < vertices.size(); ++i) vertices[i].owner = this;
-      for (size_t i = 0; i < faces.size(); ++i) faces[i].owner = this;
-    }
-
-
-
-    void Polyhedron::commonFaceInit(bool _recalc) {
-      collectFaceVertices(faces, vertices);
-      setFaceAndVertexOwner();
-      if (_recalc) faceRecalc();
-
-      if (!init()) {
-        throw carve::exception("polyhedron creation failed");
-      }
-    }
-
-
-
-    Polyhedron::~Polyhedron() {
-    }
-
-
-
-    void Polyhedron::testVertexAgainstClosedManifolds(const carve::geom3d::Vector &v,
-                                                      std::map<int, PointClass> &result,
-                                                      bool ignore_orientation) const {
-
-      for (size_t i = 0; i < faces.size(); i++) {
-        if (!manifold_is_closed[faces[i].manifold_id]) continue; // skip open manifolds
-        if (faces[i].containsPoint(v)) {
-          result[faces[i].manifold_id] = POINT_ON;
-        }
-      }
-
-      double ray_len = aabb.extent.length() * 2;
-
-      std::vector<const face_t *> possible_faces;
-
-      std::vector<std::pair<const face_t *, carve::geom3d::Vector> > manifold_intersections;
-
-      boost::mt19937 rng;
-      boost::uniform_on_sphere<double> distrib(3);
-      boost::variate_generator<boost::mt19937 &, boost::uniform_on_sphere<double> > gen(rng, distrib);
-
-      for (;;) {
-        carve::geom3d::Vector ray_dir;
-        ray_dir = gen();
-
-        carve::geom3d::Vector v2 = v + ray_dir * ray_len;
-
-        bool failed = false;
-        carve::geom3d::LineSegment line(v, v2);
-        carve::geom3d::Vector intersection;
-
-        possible_faces.clear();
-        manifold_intersections.clear();
-        octree.findFacesNear(line, possible_faces);
-
-        for (unsigned i = 0; !failed && i < possible_faces.size(); i++) {
-          if (!manifold_is_closed[possible_faces[i]->manifold_id]) continue; // skip open manifolds
-          if (result.find(possible_faces[i]->manifold_id) != result.end()) continue; // already ON
-
-          switch (possible_faces[i]->lineSegmentIntersection(line, intersection)) {
-          case INTERSECT_FACE: {
-            manifold_intersections.push_back(std::make_pair(possible_faces[i], intersection));
-            break;
-          }
-          case INTERSECT_NONE: {
-            break;
-          }
-          default: {
-            failed = true;
-            break;
-          }
-          }
-        }
-
-        if (!failed) break;
-      }
-
-      std::vector<int> crossings(manifold_is_closed.size(), 0);
-
-      for (size_t i = 0; i < manifold_intersections.size(); ++i) {
-        const face_t *f = manifold_intersections[i].first;
-        crossings[f->manifold_id]++;
-      }
-
-      for (size_t i = 0; i < crossings.size(); ++i) {
-#if defined(CARVE_DEBUG)
-        std::cerr << "crossing: " << i << " = " << crossings[i] << " is_negative = " << manifold_is_negative[i] << std::endl;
-#endif
-        if (!manifold_is_closed[i]) continue;
-        if (result.find(i) != result.end()) continue;
-        PointClass pc = (crossings[i] & 1) ? POINT_IN : POINT_OUT;
-        if (!ignore_orientation && manifold_is_negative[i]) pc = (PointClass)-pc;
-        result[i] = pc;
-      }
-    }
-
-
-
-    PointClass Polyhedron::containsVertex(const carve::geom3d::Vector &v,
-                                          const face_t **hit_face,
-                                          bool even_odd,
-                                          int manifold_id) const {
-      if (hit_face) *hit_face = NULL;
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-      std::cerr << "{containsVertex " << v << "}" << std::endl;
-#endif
-
-      if (!aabb.containsPoint(v)) {
-#if defined(DEBUG_CONTAINS_VERTEX)
-        std::cerr << "{final:OUT(aabb short circuit)}" << std::endl;
-#endif
-        // XXX: if the top level manifolds are negative, this should be POINT_IN.
-        // for the moment, this only works for a single manifold.
-        if (manifold_is_negative.size() == 1 && manifold_is_negative[0]) return POINT_IN;
-        return POINT_OUT;
-      }
-
-      for (size_t i = 0; i < faces.size(); i++) {
-        if (manifold_id != -1 && manifold_id != faces[i].manifold_id) continue;
-
-        // XXX: Do allow the tested vertex to be ON an open
-        // manifold. This was here originally because of the
-        // possibility of an open manifold contained within a closed
-        // manifold.
-
-        // if (!manifold_is_closed[faces[i].manifold_id]) continue;
-
-        if (faces[i].containsPoint(v)) {
-#if defined(DEBUG_CONTAINS_VERTEX)
-          std::cerr << "{final:ON(hits face " << &faces[i] << ")}" << std::endl;
-#endif
-          if (hit_face) *hit_face = &faces[i];
-          return POINT_ON;
-        }
-      }
-
-      double ray_len = aabb.extent.length() * 2;
-
-      std::vector<const face_t *> possible_faces;
-
-      std::vector<std::pair<const face_t *, carve::geom3d::Vector> > manifold_intersections;
-
-      for (;;) {
-        double a1 = random() / double(RAND_MAX) * M_TWOPI;
-        double a2 = random() / double(RAND_MAX) * M_TWOPI;
-
-        carve::geom3d::Vector ray_dir = carve::geom::VECTOR(sin(a1) * sin(a2), cos(a1) * sin(a2), cos(a2));
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-        std::cerr << "{testing ray: " << ray_dir << "}" << std::endl;
-#endif
-
-        carve::geom3d::Vector v2 = v + ray_dir * ray_len;
-
-        bool failed = false;
-        carve::geom3d::LineSegment line(v, v2);
-        carve::geom3d::Vector intersection;
-
-        possible_faces.clear();
-        manifold_intersections.clear();
-        octree.findFacesNear(line, possible_faces);
-
-        for (unsigned i = 0; !failed && i < possible_faces.size(); i++) {
-          if (manifold_id != -1 && manifold_id != faces[i].manifold_id) continue;
-
-          if (!manifold_is_closed[possible_faces[i]->manifold_id]) continue;
-
-          switch (possible_faces[i]->lineSegmentIntersection(line, intersection)) {
-          case INTERSECT_FACE: {
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-            std::cerr << "{intersects face: " << possible_faces[i]
-                      << " dp: " << dot(ray_dir, possible_faces[i]->plane_eqn.N) << "}" << std::endl;
-#endif
-
-            if (!even_odd && fabs(dot(ray_dir, possible_faces[i]->plane_eqn.N)) < EPSILON) {
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-              std::cerr << "{failing(small dot product)}" << std::endl;
-#endif
-
-              failed = true;
-              break;
-            }
-            manifold_intersections.push_back(std::make_pair(possible_faces[i], intersection));
-            break;
-          }
-          case INTERSECT_NONE: {
-            break;
-          }
-          default: {
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-            std::cerr << "{failing(degenerate intersection)}" << std::endl;
-#endif
-            failed = true;
-            break;
-          }
-          }
-        }
-
-        if (!failed) {
-          if (even_odd) {
-            return (manifold_intersections.size() & 1) ? POINT_IN : POINT_OUT;
-          }
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-          std::cerr << "{intersections ok [count:"
-                    << manifold_intersections.size()
-                    << "], sorting}"
-                    << std::endl;
-#endif
-
-          carve::geom3d::sortInDirectionOfRay(ray_dir,
-                                              manifold_intersections.begin(),
-                                              manifold_intersections.end(),
-                                              carve::geom3d::vec_adapt_pair_second());
-
-          std::vector<int> crossings(manifold_is_closed.size(), 0);
-
-          for (size_t i = 0; i < manifold_intersections.size(); ++i) {
-            const face_t *f = manifold_intersections[i].first;
-            if (dot(ray_dir, f->plane_eqn.N) < 0.0) {
-              crossings[f->manifold_id]++;
-            } else {
-              crossings[f->manifold_id]--;
-            }
-          }
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-          for (size_t i = 0; i < crossings.size(); ++i) {
-            std::cerr << "{manifold " << i << " crossing count: " << crossings[i] << "}" << std::endl;
-          }
-#endif
-
-          for (size_t i = 0; i < manifold_intersections.size(); ++i) {
-            const face_t *f = manifold_intersections[i].first;
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-            std::cerr << "{intersection at "
-                      << manifold_intersections[i].second
-                      << " id: "
-                      << f->manifold_id
-                      << " count: "
-                      << crossings[f->manifold_id]
-                      << "}"
-                      << std::endl;
-#endif
-
-            if (crossings[f->manifold_id] < 0) {
-              // inside this manifold.
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-              std::cerr << "{final:IN}" << std::endl;
-#endif
-
-              return POINT_IN;
-            } else if (crossings[f->manifold_id] > 0) {
-              // outside this manifold, but it's an infinite manifold. (for instance, an inverted cube)
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-              std::cerr << "{final:OUT}" << std::endl;
-#endif
-
-              return POINT_OUT;
-            }
-          }
-
-#if defined(DEBUG_CONTAINS_VERTEX)
-          std::cerr << "{final:OUT(default)}" << std::endl;
-#endif
-
-          return POINT_OUT;
-        }
-      }
-    }
-
-
-
-    void Polyhedron::findEdgesNear(const carve::geom::aabb<3> &aabb,
-                                   std::vector<const edge_t *> &outEdges) const {
-      outEdges.clear();
-      octree.findEdgesNear(aabb, outEdges);
-    }
-
-
-
-    void Polyhedron::findEdgesNear(const carve::geom3d::LineSegment &line,
-                                   std::vector<const edge_t *> &outEdges) const {
-      outEdges.clear();
-      octree.findEdgesNear(line, outEdges);
-    }
-
-
-
-    void Polyhedron::findEdgesNear(const carve::geom3d::Vector &v,
-                                   std::vector<const edge_t *> &outEdges) const {
-      outEdges.clear();
-      octree.findEdgesNear(v, outEdges);
-    }
-
-
-
-    void Polyhedron::findEdgesNear(const face_t &face,
-                                   std::vector<const edge_t *> &edges) const {
-      edges.clear();
-      octree.findEdgesNear(face, edges);
-    }
-
-
-
-    void Polyhedron::findEdgesNear(const edge_t &edge,
-                                   std::vector<const edge_t *> &outEdges) const {
-      outEdges.clear();
-      octree.findEdgesNear(edge, outEdges);
-    }
-
-
-
-    void Polyhedron::findFacesNear(const carve::geom3d::LineSegment &line,
-                                   std::vector<const face_t *> &outFaces) const {
-      outFaces.clear();
-      octree.findFacesNear(line, outFaces);
-    }
-
-
-
-    void Polyhedron::findFacesNear(const carve::geom::aabb<3> &aabb,
-                                   std::vector<const face_t *> &outFaces) const {
-      outFaces.clear();
-      octree.findFacesNear(aabb, outFaces);
-    }
-
-
-
-    void Polyhedron::findFacesNear(const edge_t &edge,
-                                   std::vector<const face_t *> &outFaces) const {
-      outFaces.clear();
-      octree.findFacesNear(edge, outFaces);
-    }
-
-
-
-    void Polyhedron::transform(const carve::math::Matrix &xform) {
-      for (size_t i = 0; i < vertices.size(); i++) {
-        vertices[i].v = xform * vertices[i].v;
-      }
-      for (size_t i = 0; i < faces.size(); i++) {
-        faces[i].recalc();
-      }
-      init();
-    }
-
-
-
-    void Polyhedron::print(std::ostream &o) const {
-      o << "Polyhedron@" << this << " {" << std::endl;
-      for (std::vector<vertex_t >::const_iterator
-             i = vertices.begin(), e = vertices.end(); i != e; ++i) {
-        o << "  V@" << &(*i) << " " << (*i).v << std::endl;
-      }
-      for (std::vector<edge_t >::const_iterator
-             i = edges.begin(), e = edges.end(); i != e; ++i) {
-        o << "  E@" << &(*i) << " {" << std::endl;
-        o << "    V@" << (*i).v1 << " - " << "V@" << (*i).v2 << std::endl;
-        const std::vector<const face_t *> &faces = connectivity.edge_to_face[edgeToIndex_fast(&(*i))];
-        for (size_t j = 0; j < (faces.size() & ~1U); j += 2) {
-          o << "      fp: F@" << faces[j] << ", F@" << faces[j+1] << std::endl;
-        }
-        o << "  }" << std::endl;
-      }
-      for (std::vector<face_t >::const_iterator
-             i = faces.begin(), e = faces.end(); i != e; ++i) {
-        o << "  F@" << &(*i) << " {" << std::endl;
-        o << "    vertices {" << std::endl;
-        for (face_t::const_vertex_iter_t j = (*i).vbegin(), je = (*i).vend(); j != je; ++j) {
-          o << "      V@" << (*j) << std::endl;
-        }
-        o << "    }" << std::endl;
-        o << "    edges {" << std::endl;
-        for (face_t::const_edge_iter_t j = (*i).ebegin(), je = (*i).eend(); j != je; ++j) {
-          o << "      E@" << (*j) << std::endl;
-        }
-        carve::geom::plane<3> p = (*i).plane_eqn;
-        o << "    }" << std::endl;
-        o << "    normal " << (*i).plane_eqn.N << std::endl;
-        o << "    aabb " << (*i).aabb << std::endl;
-        o << "    plane_eqn ";
-        carve::geom::operator<< <3>(o, p);
-        o << std::endl;
-        o << "  }" << std::endl;
-      }
-
-      o << "}" << std::endl;
-    }
-
-
-
-    void Polyhedron::canonicalize() {
-      orderVertices();
-      for (size_t i = 0; i < faces.size(); i++) {
-        face_t &f = faces[i];
-        size_t j = std::distance(f.vbegin(),
-                                 std::min_element(f.vbegin(),
-                                                  f.vend()));
-        if (j) {
-          {
-            std::vector<const vertex_t *> temp;
-            temp.reserve(f.nVertices());
-            std::copy(f.vbegin() + j, f.vend(),       std::back_inserter(temp));
-            std::copy(f.vbegin(),     f.vbegin() + j, std::back_inserter(temp));
-            std::copy(temp.begin(),   temp.end(),     f.vbegin());
-          }
-          {
-            std::vector<const edge_t *> temp;
-            temp.reserve(f.nEdges());
-            std::copy(f.ebegin() + j, f.eend(),       std::back_inserter(temp));
-            std::copy(f.ebegin(),     f.ebegin() + j, std::back_inserter(temp));
-            std::copy(temp.begin(),   temp.end(),     f.ebegin());
-          }
-        }
-      }
-
-      std::vector<face_t *> face_ptrs;
-      face_ptrs.reserve(faces.size());
-      for (size_t i = 0; i < faces.size(); ++i) face_ptrs.push_back(&faces[i]);
-      std::sort(face_ptrs.begin(), face_ptrs.end(), order_faces());
-      std::vector<face_t> sorted_faces;
-      sorted_faces.reserve(faces.size());
-      for (size_t i = 0; i < faces.size(); ++i) sorted_faces.push_back(*face_ptrs[i]);
-      std::swap(faces, sorted_faces);
-    }
-
-  }
-}
-