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, 823 deletions

diff --git a/extern/carve/lib/intersect_classify_edge.cpp b/extern/carve/lib/intersect_classify_edge.cpp
deleted file mode 100644
index 23cfa21b643..00000000000
--- a/extern/carve/lib/intersect_classify_edge.cpp
+++ /dev/null
@@ -1,823 +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(HAVE_STDINT_H)
-#include <stdint.h>
-#endif
-
-#include <carve/csg.hpp>
-#include <carve/debug_hooks.hpp>
-#include <carve/colour.hpp>
-
-#include <list>
-#include <set>
-#include <iostream>
-
-#include <algorithm>
-
-#include "csg_detail.hpp"
-
-#include "intersect_common.hpp"
-#include "intersect_classify_common.hpp"
-
-#define ANGLE_EPSILON 1e-6
-
-namespace carve {
-  namespace csg {
-
-    namespace {
-
-      inline bool single_bit_set(uint32_t v) {
-        v &= v - 1;
-        return v == 0;
-      }
-
-      struct EdgeSurface {
-        FaceLoop *fwd;
-        double fwd_ang;
-        FaceLoop *rev;
-        double rev_ang;
-
-        EdgeSurface() : fwd(NULL), fwd_ang(0.0), rev(NULL), rev_ang(0.0) { }
-      };
-
-
-      typedef std::map<const carve::mesh::MeshSet<3>::mesh_t *, EdgeSurface> GrpEdgeSurfMap;
-
-      typedef std::pair<FaceLoopGroup *, const carve::mesh::MeshSet<3>::mesh_t *> ClassificationKey;
-
-      struct ClassificationData {
-        uint32_t class_bits : 5;
-        uint32_t class_decided : 1;
-
-        int c[5];
-
-        ClassificationData() {
-          class_bits = FACE_ANY_BIT;
-          class_decided = 0;
-          memset(c, 0, sizeof(c));
-        }
-      };
-
-      struct hash_classification {
-        size_t operator()(const ClassificationKey &f) const {
-          return (size_t)f.first ^ (size_t)f.second;
-        }
-      };
-
-      typedef std::unordered_map<ClassificationKey, ClassificationData, hash_classification> Classification;
-
-
-      struct hash_group_ptr {
-        size_t operator()(const FaceLoopGroup * const &f) const {
-          return (size_t)f;
-        }
-      };
-
-
-      typedef std::pair<size_t, const carve::mesh::MeshSet<3>::vertex_t *> PerimKey;
-
-      struct hash_perim_key {
-        size_t operator()(const PerimKey &v) const {
-          return (size_t)v.first ^ (size_t)v.second;
-        }
-      };
-
-      typedef std::unordered_map<std::pair<size_t, const carve::mesh::MeshSet<3>::vertex_t *>,
-                                 std::unordered_set<FaceLoopGroup *, hash_group_ptr>,
-                                 hash_perim_key> PerimMap;
-
-
-
-      struct hash_group_pair {
-        size_t operator()(const std::pair<int, const FaceLoopGroup *> &v) const {
-          return (size_t)v.first ^ (size_t)v.second;
-        }
-      };
-
-      typedef std::unordered_map<const FaceLoopGroup *,
-                                 std::unordered_set<std::pair<int, const FaceLoopGroup *>, hash_group_pair>,
-                                 hash_group_ptr> CandidateOnMap;
-
-
-
-      static inline void remove(carve::mesh::MeshSet<3>::vertex_t *a,
-                                carve::mesh::MeshSet<3>::vertex_t *b,
-                                carve::csg::detail::VVSMap &shared_edge_graph) {
-        carve::csg::detail::VVSMap::iterator i = shared_edge_graph.find(a);
-        CARVE_ASSERT(i != shared_edge_graph.end());
-        size_t n = (*i).second.erase(b);
-        CARVE_ASSERT(n == 1);
-        if ((*i).second.size() == 0) shared_edge_graph.erase(i);
-      }
-
-
-
-      static inline void remove(V2 edge,
-                                carve::csg::detail::VVSMap &shared_edge_graph) {
-        remove(edge.first, edge.second, shared_edge_graph);
-        remove(edge.second, edge.first, shared_edge_graph);
-      }
-
-
-
-#if 0
-      static void walkGraphSegment(carve::csg::detail::VVSMap &shared_edge_graph,
-                                   const carve::csg::detail::VSet &branch_points,
-                                   V2 initial,
-                                   const carve::csg::detail::LoopEdges & /* a_edge_map */,
-                                   const carve::csg::detail::LoopEdges & /* b_edge_map */,
-                                   std::list<V2> &out) {
-        V2 curr;
-        curr = initial;
-        bool closed = false;
-
-        out.clear();
-        for (;;) {
-          // walk forward.
-          out.push_back(curr);
-          remove(curr, shared_edge_graph);
-
-          if (curr.second == initial.first) { closed = true; break; }
-          if (branch_points.find(curr.second) != branch_points.end()) break;
-          carve::csg::detail::VVSMap::const_iterator o = shared_edge_graph.find(curr.second);
-          if (o == shared_edge_graph.end()) break;
-          CARVE_ASSERT((*o).second.size() == 1);
-          curr.first = curr.second;
-          curr.second = *((*o).second.begin());
-          // test here that the set of incident groups hasn't changed.
-        }
-
-        if (!closed) {
-          // walk backward.
-          curr = initial;
-          for (;;) {
-            if (branch_points.find(curr.first) != branch_points.end()) break;
-            carve::csg::detail::VVSMap::const_iterator o = shared_edge_graph.find(curr.first);
-            if (o == shared_edge_graph.end()) break;
-            curr.second = curr.first;
-            curr.first = *((*o).second.begin());
-            // test here that the set of incident groups hasn't changed.
-
-            out.push_front(curr);
-            remove(curr, shared_edge_graph);
-          }
-        }
-
-#if defined(CARVE_DEBUG)
-        std::cerr << "intersection segment: " << out.size() << " edges." << std::endl;
-#if defined(DEBUG_DRAW_INTERSECTION_LINE)
-        {
-          static float H = 0.0, S = 1.0, V = 1.0;
-          float r, g, b;
-
-          H = fmod((H + .37), 1.0);
-          S = 0.5 + fmod((S - 0.37), 0.5);
-          carve::colour::HSV2RGB(H, S, V, r, g, b);
-
-          if (out.size() > 1) {
-            drawEdges(out.begin(), ++out.begin(),
-                      0.0, 0.0, 0.0, 1.0,
-                      r, g, b, 1.0,
-                      3.0);
-            drawEdges(++out.begin(), --out.end(),
-                      r, g, b, 1.0,
-                      r, g, b, 1.0,
-                      3.0);
-            drawEdges(--out.end(), out.end(),
-                      r, g, b, 1.0,
-                      1.0, 1.0, 1.0, 1.0,
-                      3.0);
-          } else {
-            drawEdges(out.begin(), out.end(),
-                      r, g, b, 1.0,
-                      r, g, b, 1.0,
-                      3.0);
-          }
-        }
-#endif
-#endif
-      }
-#endif
-
-
-      static carve::geom3d::Vector perpendicular(const carve::geom3d::Vector &v) {
-        if (fabs(v.x) < fabs(v.y)) {
-          if (fabs(v.x) < fabs(v.z)) {
-            return cross(v, carve::geom::VECTOR(1.0, 0.0, 0.0)).normalized();
-          } else {
-            return cross(v, carve::geom::VECTOR(0.0, 0.0, 1.0)).normalized();
-          }
-        } else {
-          if (fabs(v.y) < fabs(v.z)) {
-            return cross(v, carve::geom::VECTOR(0.0, 1.0, 0.0)).normalized();
-          } else {
-            return cross(v, carve::geom::VECTOR(1.0, 0.0, 1.0)).normalized();
-          }
-        }
-      }
-
-
-
-      static void classifyAB(const GrpEdgeSurfMap &a_edge_surfaces,
-                             const GrpEdgeSurfMap &b_edge_surfaces,
-                             Classification &classifications) {
-        // two faces in the a surface
-        for (GrpEdgeSurfMap::const_iterator ib = b_edge_surfaces.begin(), eb = b_edge_surfaces.end(); ib != eb; ++ib) {
-
-          if ((*ib).second.fwd) {
-            FaceLoopGroup *b_grp = ((*ib).second.fwd->group);
-
-            for (GrpEdgeSurfMap::const_iterator ia = a_edge_surfaces.begin(), ea = a_edge_surfaces.end(); ia != ea; ++ia) {
-
-              if ((*ia).second.fwd && (*ia).second.rev) {
-                const carve::mesh::MeshSet<3>::mesh_t *a_gid = (*ia).first;
-
-                ClassificationData &data = classifications[std::make_pair(b_grp, a_gid)];
-                if (data.class_decided) continue;
-
-                // an angle between (*ia).fwd_ang and (*ia).rev_ang is outside/above group a.
-                FaceClass fc;
-
-                if (fabs((*ib).second.fwd_ang - (*ia).second.fwd_ang) < ANGLE_EPSILON) {
-                  fc = FACE_ON_ORIENT_OUT;
-                } else if (fabs((*ib).second.fwd_ang - (*ia).second.rev_ang) < ANGLE_EPSILON) {
-                  fc = FACE_ON_ORIENT_IN;
-                } else {
-                  double a1 = (*ia).second.fwd_ang;
-                  double a2 = (*ia).second.rev_ang;
-                  if (a1 < a2) {
-                    if (a1 < (*ib).second.fwd_ang && (*ib).second.fwd_ang < a2) {
-                      fc = FACE_IN;
-                    } else {
-                      fc = FACE_OUT;
-                    }
-                  } else {
-                    if (a2 < (*ib).second.fwd_ang && (*ib).second.fwd_ang < a1) {
-                      fc = FACE_OUT;
-                    } else {
-                      fc = FACE_IN;
-                    }
-                  }
-                }
-                data.c[fc + 2]++;
-              }
-            }
-          }
-
-          if ((*ib).second.rev) {
-            FaceLoopGroup *b_grp = ((*ib).second.rev->group);
-
-            for (GrpEdgeSurfMap::const_iterator ia = a_edge_surfaces.begin(), ea = a_edge_surfaces.end(); ia != ea; ++ia) {
-
-              if ((*ia).second.fwd && (*ia).second.rev) {
-                const carve::mesh::MeshSet<3>::mesh_t *a_gid = (*ia).first;
-
-                ClassificationData &data = (classifications[std::make_pair(b_grp, a_gid)]);
-                if (data.class_decided) continue;
-
-                // an angle between (*ia).fwd_ang and (*ia).rev_ang is outside/above group a.
-                FaceClass fc;
-
-                if (fabs((*ib).second.rev_ang - (*ia).second.fwd_ang) < ANGLE_EPSILON) {
-                  fc = FACE_ON_ORIENT_IN;
-                } else if (fabs((*ib).second.rev_ang - (*ia).second.rev_ang) < ANGLE_EPSILON) {
-                  fc = FACE_ON_ORIENT_OUT;
-                } else {
-                  double a1 = (*ia).second.fwd_ang;
-                  double a2 = (*ia).second.rev_ang;
-                  if (a1 < a2) {
-                    if (a1 < (*ib).second.rev_ang && (*ib).second.rev_ang < a2) {
-                      fc = FACE_IN;
-                    } else {
-                      fc = FACE_OUT;
-                    }
-                  } else {
-                    if (a2 < (*ib).second.rev_ang && (*ib).second.rev_ang < a1) {
-                      fc = FACE_OUT;
-                    } else {
-                      fc = FACE_IN;
-                    }
-                  }
-                }
-                data.c[fc + 2]++;
-              }
-            }
-          }
-        }
-      }
-
-
-      static bool processForwardEdgeSurfaces(GrpEdgeSurfMap &edge_surfaces,
-                                             const std::list<FaceLoop *> &fwd,
-                                             const carve::geom3d::Vector &edge_vector,
-                                             const carve::geom3d::Vector &base_vector) {
-        for (std::list<FaceLoop *>::const_iterator i = fwd.begin(), e = fwd.end(); i != e; ++i) {
-          EdgeSurface &es = (edge_surfaces[(*i)->orig_face->mesh]);
-          if (es.fwd != NULL) return false;
-          es.fwd = (*i);
-          es.fwd_ang = carve::geom3d::antiClockwiseAngle((*i)->orig_face->plane.N, base_vector, edge_vector);
-        }
-        return true;
-      }
-
-      static bool processReverseEdgeSurfaces(GrpEdgeSurfMap &edge_surfaces,
-                                             const std::list<FaceLoop *> &rev,
-                                             const carve::geom3d::Vector &edge_vector,
-                                             const carve::geom3d::Vector &base_vector) {
-        for (std::list<FaceLoop *>::const_iterator i = rev.begin(), e = rev.end(); i != e; ++i) {
-          EdgeSurface &es = (edge_surfaces[(*i)->orig_face->mesh]);
-          if (es.rev != NULL) return false;
-          es.rev = (*i);
-          es.rev_ang = carve::geom3d::antiClockwiseAngle(-(*i)->orig_face->plane.N, base_vector, edge_vector);
-        }
-        return true;
-      }
-
-
-
-      static void processOneEdge(const V2 &edge,
-                                 const carve::csg::detail::LoopEdges &a_edge_map,
-                                 const carve::csg::detail::LoopEdges &b_edge_map,
-                                 Classification &a_classification,
-                                 Classification &b_classification) {
-        GrpEdgeSurfMap a_edge_surfaces;
-        GrpEdgeSurfMap b_edge_surfaces;
-
-        carve::geom3d::Vector edge_vector = (edge.second->v - edge.first->v).normalized();
-        carve::geom3d::Vector base_vector = perpendicular(edge_vector);
-
-        carve::csg::detail::LoopEdges::const_iterator ae_f = a_edge_map.find(edge);
-        carve::csg::detail::LoopEdges::const_iterator ae_r = a_edge_map.find(flip(edge));
-        CARVE_ASSERT(ae_f != a_edge_map.end() || ae_r != a_edge_map.end());
-
-        carve::csg::detail::LoopEdges::const_iterator be_f = b_edge_map.find(edge);
-        carve::csg::detail::LoopEdges::const_iterator be_r = b_edge_map.find(flip(edge));
-        CARVE_ASSERT(be_f != b_edge_map.end() || be_r != b_edge_map.end());
-
-        if (ae_f != a_edge_map.end() && !processForwardEdgeSurfaces(a_edge_surfaces, (*ae_f).second, edge_vector, base_vector)) return;
-        if (ae_r != a_edge_map.end() && !processReverseEdgeSurfaces(a_edge_surfaces, (*ae_r).second, edge_vector, base_vector)) return;
-        if (be_f != b_edge_map.end() && !processForwardEdgeSurfaces(b_edge_surfaces, (*be_f).second, edge_vector, base_vector)) return;
-        if (be_r != b_edge_map.end() && !processReverseEdgeSurfaces(b_edge_surfaces, (*be_r).second, edge_vector, base_vector)) return;
-
-        classifyAB(a_edge_surfaces, b_edge_surfaces, b_classification);
-        classifyAB(b_edge_surfaces, a_edge_surfaces, a_classification);
-      }
-
-
-
-#if 0
-      static void traceIntersectionGraph(const V2Set &shared_edges,
-                                         const FLGroupList & /* a_loops_grouped */,
-                                         const FLGroupList & /* b_loops_grouped */,
-                                         const carve::csg::detail::LoopEdges &a_edge_map,
-                                         const carve::csg::detail::LoopEdges &b_edge_map) {
-
-        carve::csg::detail::VVSMap shared_edge_graph;
-        carve::csg::detail::VSet branch_points;
-
-        // first, make the intersection graph.
-        for (V2Set::const_iterator i = shared_edges.begin(); i != shared_edges.end(); ++i) {
-          const V2Set::key_type &edge = (*i);
-          carve::csg::detail::VVSMap::mapped_type &out = (shared_edge_graph[edge.first]);
-          out.insert(edge.second);
-          if (out.size() == 3) branch_points.insert(edge.first);
-
-#if defined(CARVE_DEBUG) && defined(DEBUG_DRAW_INTERSECTION_LINE)
-          HOOK(drawEdge(edge.first, edge.second, 1, 1, 1, 1, 1, 1, 1, 1, 1.0););
-#endif
-        }
-#if defined(CARVE_DEBUG)
-        std::cerr << "graph nodes: " << shared_edge_graph.size() << std::endl;
-        std::cerr << "branch nodes: " << branch_points.size() << std::endl;
-#endif
-
-        std::list<V2> out;
-        while (shared_edge_graph.size()) {
-          carve::csg::detail::VVSMap::iterator i = shared_edge_graph.begin();
-          carve::mesh::MeshSet<3>::vertex_t *v1 = (*i).first;
-          carve::mesh::MeshSet<3>::vertex_t *v2 = *((*i).second.begin());
-          walkGraphSegment(shared_edge_graph, branch_points, V2(v1, v2), a_edge_map, b_edge_map, out);
-        }
-      }
-#endif
-
-      void hashByPerimeter(FLGroupList &grp, PerimMap &perim_map) {
-        for (FLGroupList::iterator i = grp.begin(); i != grp.end(); ++i) {
-          size_t perim_size = (*i).perimeter.size();
-          // can be the case for non intersecting groups. (and groups that intersect at a point?)
-          if (!perim_size) continue;
-          const carve::mesh::MeshSet<3>::vertex_t *perim_min = std::min_element((*i).perimeter.begin(), (*i).perimeter.end())->first;
-          perim_map[std::make_pair(perim_size, perim_min)].insert(&(*i));
-        }
-      }
-
-
-
-      bool same_edge_set_fwd(const V2Set &a, const V2Set &b) {
-        if (a.size() != b.size()) return false;
-        for (V2Set::const_iterator i = a.begin(), e = a.end(); i != e; ++i) {
-          if (b.find(*i) == b.end()) return false;
-        }
-        return true;
-      }
-
-
-
-      bool same_edge_set_rev(const V2Set &a, const V2Set &b) {
-        if (a.size() != b.size()) return false;
-        for (V2Set::const_iterator i = a.begin(), e = a.end(); i != e; ++i) {
-          if (b.find(std::make_pair((*i).second, (*i).first)) == b.end()) return false;
-        }
-        return true;
-      }
-
-
-
-      int same_edge_set(const V2Set &a, const V2Set &b) {
-        if (same_edge_set_fwd(a, b)) return +1;
-        if (same_edge_set_rev(a, b)) return -1;
-        return 0;
-      }
-
-
-
-      void generateCandidateOnSets(FLGroupList &a_grp,
-                                   FLGroupList &b_grp,
-                                   CandidateOnMap &candidate_on_map,
-                                   Classification &a_classification,
-                                   Classification &b_classification) {
-        PerimMap a_grp_by_perim, b_grp_by_perim;
-
-        hashByPerimeter(a_grp, a_grp_by_perim);
-        hashByPerimeter(b_grp, b_grp_by_perim);
-
-        for (PerimMap::iterator i = a_grp_by_perim.begin(), ie = a_grp_by_perim.end(); i != ie; ++i) {
-          PerimMap::iterator j = b_grp_by_perim.find((*i).first);
-          if (j == b_grp_by_perim.end()) continue;
-
-          for (PerimMap::mapped_type::iterator a = (*i).second.begin(), ae = (*i).second.end(); a != ae; ++a) {
-            for (PerimMap::mapped_type::iterator b = (*j).second.begin(), be = (*j).second.end(); b != be; ++b) {
-              int x = same_edge_set((*a)->perimeter, (*b)->perimeter);
-              if (!x) continue;
-              candidate_on_map[(*a)].insert(std::make_pair(x, (*b)));
-              if ((*a)->face_loops.count == 1 && (*b)->face_loops.count == 1) {
-                uint32_t fcb = x == +1 ? FACE_ON_ORIENT_OUT_BIT : FACE_ON_ORIENT_IN_BIT;
-
-#if defined(CARVE_DEBUG)
-                std::cerr << "paired groups: " << (*a) << ", " << (*b) << std::endl;
-#endif
-
-                ClassificationData &a_data = a_classification[std::make_pair((*a), (*b)->face_loops.head->orig_face->mesh)];
-                a_data.class_bits = fcb; a_data.class_decided = 1;
-
-                ClassificationData &b_data = b_classification[std::make_pair((*b), (*a)->face_loops.head->orig_face->mesh)];
-                b_data.class_bits = fcb; b_data.class_decided = 1;
-              }
-            }
-          }
-        }
-      }
-
-    }
-
-
-    static inline std::string CODE(const FaceLoopGroup *grp) {
-      const std::list<ClassificationInfo> &cinfo = (grp->classification);
-      if (cinfo.size() == 0) {
-        return "?";
-      }
-
-      FaceClass fc = FACE_UNCLASSIFIED;
-
-      for (std::list<ClassificationInfo>::const_iterator i = grp->classification.begin(), e = grp->classification.end(); i != e; ++i) {
-        if ((*i).intersected_mesh == NULL) {
-          // classifier only returns global info
-          fc = (*i).classification;
-          break;
-        }
-
-        if ((*i).intersectedMeshIsClosed()) {
-          if ((*i).classification == FACE_UNCLASSIFIED) continue;
-          if (fc == FACE_UNCLASSIFIED) {
-            fc = (*i).classification;
-          } else if (fc != (*i).classification) {
-            return "X";
-          }
-        }
-      }
-      if (fc == FACE_IN) return "I";
-      if (fc == FACE_ON_ORIENT_IN) return "<";
-      if (fc == FACE_ON_ORIENT_OUT) return ">";
-      if (fc == FACE_OUT) return "O";
-      return "*";
-    }
-
-    void CSG::classifyFaceGroupsEdge(const V2Set &shared_edges,
-                                     VertexClassification &vclass,
-                                     carve::mesh::MeshSet<3> *poly_a,
-                                     const face_rtree_t *poly_a_rtree,
-                                     FLGroupList &a_loops_grouped,
-                                     const detail::LoopEdges &a_edge_map,
-                                     carve::mesh::MeshSet<3> *poly_b,
-                                     const face_rtree_t *poly_b_rtree,
-                                     FLGroupList &b_loops_grouped,
-                                     const detail::LoopEdges &b_edge_map,
-                                     CSG::Collector &collector) {
-      Classification a_classification;
-      Classification b_classification;
-
-      CandidateOnMap candidate_on_map;
-
-#if defined(CARVE_DEBUG)
-      std::cerr << "a input loops (" << a_loops_grouped.size() << "): ";
-      for (FLGroupList::iterator i = a_loops_grouped.begin(); i != a_loops_grouped.end(); ++i) {
-        std::cerr << &*i << " ";
-      }
-      std::cerr << std::endl;
-      std::cerr << "b input loops (" << b_loops_grouped.size() << "): ";
-      for (FLGroupList::iterator i = b_loops_grouped.begin(); i != b_loops_grouped.end(); ++i) {
-        std::cerr << &*i << " ";
-      }
-      std::cerr << std::endl;
-#endif
-
-#if defined(DISPLAY_GRP_GRAPH)
-      // XXX: this is hopelessly inefficient.
-      std::map<const FaceLoopGroup *, std::set<const FaceLoopGroup *> > grp_graph_fwd, grp_graph_rev;
-      {
-        for (FLGroupList::iterator i = a_loops_grouped.begin(); i != a_loops_grouped.end(); ++i) {
-          FaceLoopGroup *src = &(*i);
-          for (V2Set::const_iterator k = src->perimeter.begin(); k != src->perimeter.end(); ++k) {
-            V2 fwd = *k;
-            V2 rev = std::make_pair(fwd.second, fwd.first);
-            for (FLGroupList::iterator j = a_loops_grouped.begin(); j != a_loops_grouped.end(); ++j) {
-              FaceLoopGroup *tgt = &(*j);
-              if (tgt->perimeter.find(fwd) != tgt->perimeter.end()) { grp_graph_fwd[src].insert(tgt); }
-              if (tgt->perimeter.find(rev) != tgt->perimeter.end()) { grp_graph_rev[src].insert(tgt); }
-            }
-            for (FLGroupList::iterator j = b_loops_grouped.begin(); j != b_loops_grouped.end(); ++j) {
-              FaceLoopGroup *tgt = &(*j);
-              if (tgt->perimeter.find(fwd) != tgt->perimeter.end()) { grp_graph_fwd[src].insert(tgt); }
-              if (tgt->perimeter.find(rev) != tgt->perimeter.end()) { grp_graph_rev[src].insert(tgt); }
-            }
-          }
-        }
-        for (FLGroupList::iterator i = b_loops_grouped.begin(); i != b_loops_grouped.end(); ++i) {
-          FaceLoopGroup *src = &(*i);
-          for (V2Set::const_iterator k = src->perimeter.begin(); k != src->perimeter.end(); ++k) {
-            V2 fwd = *k;
-            V2 rev = std::make_pair(fwd.second, fwd.first);
-            for (FLGroupList::iterator j = a_loops_grouped.begin(); j != a_loops_grouped.end(); ++j) {
-              FaceLoopGroup *tgt = &(*j);
-              if (tgt->perimeter.find(fwd) != tgt->perimeter.end()) { grp_graph_fwd[src].insert(tgt); }
-              if (tgt->perimeter.find(rev) != tgt->perimeter.end()) { grp_graph_rev[src].insert(tgt); }
-            }
-            for (FLGroupList::iterator j = b_loops_grouped.begin(); j != b_loops_grouped.end(); ++j) {
-              FaceLoopGroup *tgt = &(*j);
-              if (tgt->perimeter.find(fwd) != tgt->perimeter.end()) { grp_graph_fwd[src].insert(tgt); }
-              if (tgt->perimeter.find(rev) != tgt->perimeter.end()) { grp_graph_rev[src].insert(tgt); }
-            }
-          }
-        }
-      }
-#endif
-
-      generateCandidateOnSets(a_loops_grouped, b_loops_grouped, candidate_on_map, a_classification, b_classification);
-
-
-      for (V2Set::const_iterator i = shared_edges.begin(); i != shared_edges.end(); ++i) {
-        const V2 &edge = (*i);
-        processOneEdge(edge, a_edge_map, b_edge_map, a_classification, b_classification);
-      }
-
-
-      for (Classification::iterator i = a_classification.begin(), e = a_classification.end(); i != e; ++i) {
-        if (!(*i).second.class_decided) {
-          if ((*i).second.c[FACE_IN            + 2] == 0) (*i).second.class_bits &= ~ FACE_IN_BIT;
-          if ((*i).second.c[FACE_ON_ORIENT_IN  + 2] == 0) (*i).second.class_bits &= ~ FACE_ON_ORIENT_IN_BIT;
-          if ((*i).second.c[FACE_ON_ORIENT_OUT + 2] == 0) (*i).second.class_bits &= ~ FACE_ON_ORIENT_OUT_BIT;
-          if ((*i).second.c[FACE_OUT           + 2] == 0) (*i).second.class_bits &= ~ FACE_OUT_BIT;
-
-          // XXX: this is the wrong thing to do. It's intended just as a test.
-          if ((*i).second.class_bits == (FACE_IN_BIT | FACE_OUT_BIT)) {
-            if ((*i).second.c[FACE_OUT + 2] > (*i).second.c[FACE_IN + 2]) {
-              (*i).second.class_bits = FACE_OUT_BIT;
-            } else {
-              (*i).second.class_bits = FACE_IN_BIT;
-            }
-          }
-
-          if (single_bit_set((*i).second.class_bits)) (*i).second.class_decided = 1;
-        }
-      }
-
-      for (Classification::iterator i = b_classification.begin(), e = b_classification.end(); i != e; ++i) {
-        if (!(*i).second.class_decided) {
-          if ((*i).second.c[FACE_IN            + 2] == 0) (*i).second.class_bits &= ~ FACE_IN_BIT;
-          if ((*i).second.c[FACE_ON_ORIENT_IN  + 2] == 0) (*i).second.class_bits &= ~ FACE_ON_ORIENT_IN_BIT;
-          if ((*i).second.c[FACE_ON_ORIENT_OUT + 2] == 0) (*i).second.class_bits &= ~ FACE_ON_ORIENT_OUT_BIT;
-          if ((*i).second.c[FACE_OUT           + 2] == 0) (*i).second.class_bits &= ~ FACE_OUT_BIT;
-
-          // XXX: this is the wrong thing to do. It's intended just as a test.
-          if ((*i).second.class_bits == (FACE_IN_BIT | FACE_OUT_BIT)) {
-            if ((*i).second.c[FACE_OUT + 2] > (*i).second.c[FACE_IN + 2]) {
-              (*i).second.class_bits = FACE_OUT_BIT;
-            } else {
-              (*i).second.class_bits = FACE_IN_BIT;
-            }
-          }
-
-          if (single_bit_set((*i).second.class_bits)) (*i).second.class_decided = 1;
-        }
-      }
-
-
-#if defined(CARVE_DEBUG)
-      std::cerr << "poly a:" << std::endl;
-      for (Classification::iterator i = a_classification.begin(), e = a_classification.end(); i != e; ++i) {
-        FaceLoopGroup *grp = ((*i).first.first);
-
-        std::cerr << "  group: " << grp << " gid: " << (*i).first.second
-                  << "  "
-                  << ((*i).second.class_decided ? "+" : "-")
-                  << "  "
-                  << ((*i).second.class_bits & FACE_IN_BIT ? "I" : ".")
-                  << ((*i).second.class_bits & FACE_ON_ORIENT_IN_BIT ? "<" : ".")
-                  << ((*i).second.class_bits & FACE_ON_ORIENT_OUT_BIT ? ">" : ".")
-                  << ((*i).second.class_bits & FACE_OUT_BIT ? "O" : ".")
-                  << "  ["
-                  << std::setw(4) << (*i).second.c[0] << " "
-                  << std::setw(4) << (*i).second.c[1] << " "
-                  << std::setw(4) << (*i).second.c[2] << " "
-                  << std::setw(4) << (*i).second.c[3] << " "
-                  << std::setw(4) << (*i).second.c[4] << "]" << std::endl;
-      }
-
-      std::cerr << "poly b:" << std::endl;
-      for (Classification::iterator i = b_classification.begin(), e = b_classification.end(); i != e; ++i) {
-        FaceLoopGroup *grp = ((*i).first.first);
-
-        std::cerr << "  group: " << grp << " gid: " << (*i).first.second
-                  << "  "
-                  << ((*i).second.class_decided ? "+" : "-")
-                  << "  "
-                  << ((*i).second.class_bits & FACE_IN_BIT ? "I" : ".")
-                  << ((*i).second.class_bits & FACE_ON_ORIENT_IN_BIT ? "<" : ".")
-                  << ((*i).second.class_bits & FACE_ON_ORIENT_OUT_BIT ? ">" : ".")
-                  << ((*i).second.class_bits & FACE_OUT_BIT ? "O" : ".")
-                  << "  ["
-                  << std::setw(4) << (*i).second.c[0] << " "
-                  << std::setw(4) << (*i).second.c[1] << " "
-                  << std::setw(4) << (*i).second.c[2] << " "
-                  << std::setw(4) << (*i).second.c[3] << " "
-                  << std::setw(4) << (*i).second.c[4] << "]" << std::endl;
-      }
-#endif
-
-      for (Classification::iterator i = a_classification.begin(), e = a_classification.end(); i != e; ++i) {
-        FaceLoopGroup *grp = ((*i).first.first);
-
-        grp->classification.push_back(ClassificationInfo());
-        ClassificationInfo &info = grp->classification.back();
-
-        info.intersected_mesh = (*i).first.second;
-
-        if ((*i).second.class_decided) {
-          info.classification = class_bit_to_class((*i).second.class_bits);
-        } else {
-          info.classification = FACE_UNCLASSIFIED;
-        }
-      }
-
-      for (Classification::iterator i = b_classification.begin(), e = b_classification.end(); i != e; ++i) {
-        FaceLoopGroup *grp = ((*i).first.first);
-
-        grp->classification.push_back(ClassificationInfo());
-        ClassificationInfo &info = grp->classification.back();
-
-        info.intersected_mesh = (*i).first.second;
-
-        if ((*i).second.class_decided) {
-          info.classification = class_bit_to_class((*i).second.class_bits);
-        } else {
-          info.classification = FACE_UNCLASSIFIED;
-        }
-      }
-
-      for (FLGroupList::iterator i = a_loops_grouped.begin(); i != a_loops_grouped.end(); ++i) {
-        if ((*i).classification.size() == 0) {
-#if defined(CARVE_DEBUG)
-          std::cerr << " non intersecting group (poly a): " << &(*i) << std::endl;
-#endif
-          bool classified = false;
-          for (FaceLoop *fl = (*i).face_loops.head; !classified && fl != NULL; fl = fl->next) {
-            for (size_t fli = 0; !classified && fli < fl->vertices.size(); ++fli) {
-              if (vclass[fl->vertices[fli]].cls[1] == POINT_UNK) { 
-                vclass[fl->vertices[fli]].cls[1] = carve::mesh::classifyPoint(poly_b, poly_b_rtree, fl->vertices[fli]->v);
-              }
-              switch (vclass[fl->vertices[fli]].cls[1]) {
-                case POINT_IN:
-                  (*i).classification.push_back(ClassificationInfo(NULL, FACE_IN));
-                  classified = true;
-                  break;
-                case POINT_OUT:
-                  (*i).classification.push_back(ClassificationInfo(NULL, FACE_OUT));
-                  classified = true;
-                  break;
-                default:
-                  break;
-              }
-            }
-          }
-          if (!classified) {
-            throw carve::exception("non intersecting group is not IN or OUT! (poly_a)");
-          }
-        }
-      }
-
-      for (FLGroupList::iterator i = b_loops_grouped.begin(); i != b_loops_grouped.end(); ++i) {
-        if ((*i).classification.size() == 0) {
-#if defined(CARVE_DEBUG)
-          std::cerr << " non intersecting group (poly b): " << &(*i) << std::endl;
-#endif
-          bool classified = false;
-          for (FaceLoop *fl = (*i).face_loops.head; !classified && fl != NULL; fl = fl->next) {
-            for (size_t fli = 0; !classified && fli < fl->vertices.size(); ++fli) {
-              if (vclass[fl->vertices[fli]].cls[0] == POINT_UNK) { 
-                vclass[fl->vertices[fli]].cls[0] = carve::mesh::classifyPoint(poly_a, poly_a_rtree, fl->vertices[fli]->v);
-              }
-              switch (vclass[fl->vertices[fli]].cls[0]) {
-                case POINT_IN:
-                  (*i).classification.push_back(ClassificationInfo(NULL, FACE_IN));
-                  classified = true;
-                  break;
-                case POINT_OUT:
-                  (*i).classification.push_back(ClassificationInfo(NULL, FACE_OUT));
-                  classified = true;
-                  break;
-                default:
-                  break;
-              }
-            }
-          }
-          if (!classified) {
-            throw carve::exception("non intersecting group is not IN or OUT! (poly_b)");
-          }
-        }
-      }
-
-#if defined(DISPLAY_GRP_GRAPH)
-#define POLY(grp) (std::string((grp)->face_loops.head->orig_face->polyhedron == poly_a ? "[A:" : "[B:") + CODE(grp) + "]")
-
-      for (std::map<const FaceLoopGroup *, std::set<const FaceLoopGroup *> >::iterator i = grp_graph_fwd.begin(); i != grp_graph_fwd.end(); ++i) {
-        const FaceLoopGroup *grp = (*i).first;
-
-        std::cerr << "GRP: " << grp << POLY(grp) << std::endl;
-
-        std::set<const FaceLoopGroup *> &fwd_set = grp_graph_fwd[grp];
-        std::set<const FaceLoopGroup *> &rev_set = grp_graph_rev[grp];
-        std::cerr << "  FWD: ";
-        for (std::set<const FaceLoopGroup *>::const_iterator j = fwd_set.begin(); j != fwd_set.end(); ++j) {
-          std::cerr << " " << (*j) << POLY(*j);
-        }
-        std::cerr << std::endl;
-        std::cerr << "  REV: ";
-        for (std::set<const FaceLoopGroup *>::const_iterator j = rev_set.begin(); j != rev_set.end(); ++j) {
-          std::cerr << " " << (*j) << POLY(*j);
-        }
-        std::cerr << std::endl;
-      }
-#endif
-
-      for (FLGroupList::iterator i = a_loops_grouped.begin(); i != a_loops_grouped.end(); ++i) {
-        collector.collect(&*i, hooks);
-      }
-
-      for (FLGroupList::iterator i = b_loops_grouped.begin(); i != b_loops_grouped.end(); ++i) {
-        collector.collect(&*i, hooks);
-      }
-
-      // traceIntersectionGraph(shared_edges, a_loops_grouped, b_loops_grouped, a_edge_map, b_edge_map);
-    }
-
-  }
-}