diff options
Diffstat (limited to 'extern/carve/lib/intersect_face_division.cpp')
| -rw-r--r-- | extern/carve/lib/intersect_face_division.cpp | 1765 |
1 files changed, 0 insertions, 1765 deletions
diff --git a/extern/carve/lib/intersect_face_division.cpp b/extern/carve/lib/intersect_face_division.cpp deleted file mode 100644 index 6554ef500ed..00000000000 --- a/extern/carve/lib/intersect_face_division.cpp +++ /dev/null @@ -1,1765 +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 - -#include <carve/csg.hpp> -#include <carve/polyline.hpp> -#include <carve/debug_hooks.hpp> -#include <carve/timing.hpp> -#include <carve/triangulator.hpp> - -#include <list> -#include <set> -#include <iostream> - -#include <algorithm> - -#include "csg_detail.hpp" -#include "csg_data.hpp" - -#include "intersect_common.hpp" - - - -#if defined(CARVE_DEBUG_WRITE_PLY_DATA) -void writePLY(const std::string &out_file, const carve::line::PolylineSet *lines, bool ascii); -#endif - - - -namespace { - - - -#if defined(CARVE_DEBUG_WRITE_PLY_DATA) - template<typename iter_t> - void dumpFacesAndHoles(iter_t f_begin, iter_t f_end, - iter_t h_begin, iter_t h_end, - const std::string &fname) { - std::cerr << "dumping " << std::distance(f_begin, f_end) << " faces, " << std::distance(h_begin, h_end) << " holes." << std::endl; - std::map<carve::mesh::MeshSet<3>::vertex_t *, size_t> v_included; - - for (iter_t i = f_begin; i != f_end; ++i) { - for (size_t j = 0; j < (*i).size(); ++j) { - if (v_included.find((*i)[j]) == v_included.end()) { - size_t &p = v_included[(*i)[j]]; - p = v_included.size() - 1; - } - } - } - - for (iter_t i = h_begin; i != h_end; ++i) { - for (size_t j = 0; j < (*i).size(); ++j) { - if (v_included.find((*i)[j]) == v_included.end()) { - size_t &p = v_included[(*i)[j]]; - p = v_included.size() - 1; - } - } - } - - carve::line::PolylineSet fh; - fh.vertices.resize(v_included.size()); - for (std::map<carve::mesh::MeshSet<3>::vertex_t *, size_t>::const_iterator - i = v_included.begin(); i != v_included.end(); ++i) { - fh.vertices[(*i).second].v = (*i).first->v; - } - - { - std::vector<size_t> connected; - for (iter_t i = f_begin; i != f_end; ++i) { - connected.clear(); - for (size_t j = 0; j < (*i).size(); ++j) { - connected.push_back(v_included[(*i)[j]]); - } - fh.addPolyline(true, connected.begin(), connected.end()); - } - for (iter_t i = h_begin; i != h_end; ++i) { - connected.clear(); - for (size_t j = 0; j < (*i).size(); ++j) { - connected.push_back(v_included[(*i)[j]]); - } - fh.addPolyline(true, connected.begin(), connected.end()); - } - } - - ::writePLY(fname, &fh, true); - } -#endif - - - - template<typename T> - void populateVectorFromList(std::list<T> &l, std::vector<T> &v) { - v.clear(); - v.reserve(l.size()); - for (typename std::list<T>::iterator i = l.begin(); i != l.end(); ++i) { - v.push_back(T()); - std::swap(*i, v.back()); - } - l.clear(); - } - - template<typename T> - void populateListFromVector(std::vector<T> &v, std::list<T> &l) { - l.clear(); - for (size_t i = 0; i < v.size(); ++i) { - l.push_back(T()); - std::swap(v[i], l.back()); - } - v.clear(); - } - - - - struct GraphEdge { - GraphEdge *next; - GraphEdge *prev; - GraphEdge *loop_next; - carve::mesh::MeshSet<3>::vertex_t *src; - carve::mesh::MeshSet<3>::vertex_t *tgt; - double ang; - int visited; - - GraphEdge(carve::mesh::MeshSet<3>::vertex_t *_src, carve::mesh::MeshSet<3>::vertex_t *_tgt) : - next(NULL), prev(NULL), loop_next(NULL), - src(_src), tgt(_tgt), - ang(0.0), visited(-1) { - } - }; - - - - struct GraphEdges { - GraphEdge *edges; - carve::geom2d::P2 proj; - - GraphEdges() : edges(NULL), proj() { - } - }; - - - - struct Graph { - typedef std::unordered_map<carve::mesh::MeshSet<3>::vertex_t *, GraphEdges> graph_t; - - graph_t graph; - - Graph() : graph() { - } - - ~Graph() { - int c = 0; - - GraphEdge *edge; - for (graph_t::iterator i = graph.begin(), e = graph.end(); i != e; ++i) { - edge = (*i).second.edges; - while (edge) { - GraphEdge *temp = edge; - ++c; - edge = edge->next; - delete temp; - } - } - - if (c) { - std::cerr << "warning: " - << c - << " edges should have already been removed at graph destruction time" - << std::endl; - } - } - - const carve::geom2d::P2 &projection(carve::mesh::MeshSet<3>::vertex_t *v) const { - graph_t::const_iterator i = graph.find(v); - CARVE_ASSERT(i != graph.end()); - return (*i).second.proj; - } - - void computeProjection(carve::mesh::MeshSet<3>::face_t *face) { - for (graph_t::iterator i = graph.begin(), e = graph.end(); i != e; ++i) { - (*i).second.proj = face->project((*i).first->v); - } - for (graph_t::iterator i = graph.begin(), e = graph.end(); i != e; ++i) { - for (GraphEdge *e = (*i).second.edges; e; e = e->next) { - e->ang = carve::math::ANG(carve::geom2d::atan2(projection(e->tgt) - projection(e->src))); - } - } - } - - void print(std::ostream &out, const carve::csg::VertexIntersections *vi) const { - for (graph_t::const_iterator i = graph.begin(), e = graph.end(); i != e; ++i) { - out << (*i).first << (*i).first->v << '(' << projection((*i).first).x << ',' << projection((*i).first).y << ") :"; - for (const GraphEdge *e = (*i).second.edges; e; e = e->next) { - out << ' ' << e->tgt << e->tgt->v << '(' << projection(e->tgt).x << ',' << projection(e->tgt).y << ')'; - } - out << std::endl; - if (vi) { - carve::csg::VertexIntersections::const_iterator j = vi->find((*i).first); - if (j != vi->end()) { - out << " (int) "; - for (carve::csg::IObjPairSet::const_iterator - k = (*j).second.begin(), ke = (*j).second.end(); k != ke; ++k) { - if ((*k).first < (*k).second) { - out << (*k).first << ".." << (*k).second << "; "; - } - } - out << std::endl; - } - } - } - } - - void addEdge(carve::mesh::MeshSet<3>::vertex_t *v1, carve::mesh::MeshSet<3>::vertex_t *v2) { - GraphEdges &edges = graph[v1]; - GraphEdge *edge = new GraphEdge(v1, v2); - if (edges.edges) edges.edges->prev = edge; - edge->next = edges.edges; - edges.edges = edge; - } - - void removeEdge(GraphEdge *edge) { - if (edge->prev != NULL) { - edge->prev->next = edge->next; - } else { - if (edge->next != NULL) { - GraphEdges &edges = (graph[edge->src]); - edges.edges = edge->next; - } else { - graph.erase(edge->src); - } - } - if (edge->next != NULL) { - edge->next->prev = edge->prev; - } - delete edge; - } - - bool empty() const { - return graph.size() == 0; - } - - GraphEdge *pickStartEdge() { - // Try and find a vertex from which there is only one outbound edge. Won't always succeed. - for (graph_t::iterator i = graph.begin(); i != graph.end(); ++i) { - GraphEdges &ge = i->second; - if (ge.edges->next == NULL) { - return ge.edges; - } - } - return (*graph.begin()).second.edges; - } - - GraphEdge *outboundEdges(carve::mesh::MeshSet<3>::vertex_t *v) { - return graph[v].edges; - } - }; - - - - /** - * \brief Take a set of new edges and split a face based upon those edges. - * - * @param[in] face The face to be split. - * @param[in] edges - * @param[out] face_loops Output list of face loops - * @param[out] hole_loops Output list of hole loops - * @param vi - */ - static void splitFace(carve::mesh::MeshSet<3>::face_t *face, - const carve::csg::V2Set &edges, - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &face_loops, - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &hole_loops, - const carve::csg::VertexIntersections & /* vi */) { - Graph graph; - - for (carve::csg::V2Set::const_iterator - i = edges.begin(), e = edges.end(); - i != e; - ++i) { - carve::mesh::MeshSet<3>::vertex_t *v1 = ((*i).first), *v2 = ((*i).second); - if (carve::geom::equal(v1->v, v2->v)) std::cerr << "WARNING! " << v1->v << "==" << v2->v << std::endl; - graph.addEdge(v1, v2); - } - - graph.computeProjection(face); - - while (!graph.empty()) { - GraphEdge *edge; - GraphEdge *start; - start = edge = graph.pickStartEdge(); - - edge->visited = 0; - - int len = 0; - - for (;;) { - double in_ang = M_PI + edge->ang; - if (in_ang > M_TWOPI) in_ang -= M_TWOPI; - - GraphEdge *opts; - GraphEdge *out = NULL; - double best = M_TWOPI + 1.0; - - for (opts = graph.outboundEdges(edge->tgt); opts; opts = opts->next) { - if (opts->tgt == edge->src) { - if (out == NULL && opts->next == NULL) out = opts; - } else { - double out_ang = carve::math::ANG(in_ang - opts->ang); - - if (out == NULL || out_ang < best) { - out = opts; - best = out_ang; - } - } - } - - CARVE_ASSERT(out != NULL); - - edge->loop_next = out; - - if (out->visited >= 0) { - while (start != out) { - GraphEdge *e = start; - start = start->loop_next; - e->loop_next = NULL; - e->visited = -1; - } - len = edge->visited - out->visited + 1; - break; - } - - out->visited = edge->visited + 1; - edge = out; - } - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> loop(len); - std::vector<carve::geom2d::P2> projected(len); - - edge = start; - for (int i = 0; i < len; ++i) { - GraphEdge *next = edge->loop_next; - loop[i] = edge->src; - projected[i] = graph.projection(edge->src); - graph.removeEdge(edge); - edge = next; - } - - CARVE_ASSERT(edge == start); - - if (carve::geom2d::signedArea(projected) < 0) { - face_loops.push_back(std::vector<carve::mesh::MeshSet<3>::vertex_t *>()); - face_loops.back().swap(loop); - } else { - hole_loops.push_back(std::vector<carve::mesh::MeshSet<3>::vertex_t *>()); - hole_loops.back().swap(loop); - } - } - } - - - - /** - * \brief Determine the relationship between a face loop and a hole loop. - * - * Determine whether a face and hole share an edge, or a vertex, - * or do not touch. Find a hole vertex that is not part of the - * face, and a hole,face vertex pair that are coincident, if such - * a pair exists. - * - * @param[in] f A face loop. - * @param[in] f_sort A vector indexing \a f in address order - * @param[in] h A hole loop. - * @param[in] h_sort A vector indexing \a h in address order - * @param[out] f_idx Index of a face vertex that is shared with the hole. - * @param[out] h_idx Index of the hole vertex corresponding to \a f_idx. - * @param[out] unmatched_h_idx Index of a hole vertex that is not part of the face. - * @param[out] shares_vertex Boolean indicating that the face and the hole share a vertex. - * @param[out] shares_edge Boolean indicating that the face and the hole share an edge. - */ - static void compareFaceLoopAndHoleLoop(const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &f, - const std::vector<unsigned> &f_sort, - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &h, - const std::vector<unsigned> &h_sort, - unsigned &f_idx, - unsigned &h_idx, - int &unmatched_h_idx, - bool &shares_vertex, - bool &shares_edge) { - const size_t F = f.size(); - const size_t H = h.size(); - - shares_vertex = shares_edge = false; - unmatched_h_idx = -1; - - unsigned I, J; - for (I = J = 0; I < F && J < H;) { - unsigned i = f_sort[I], j = h_sort[J]; - if (f[i] == h[j]) { - shares_vertex = true; - f_idx = i; - h_idx = j; - if (f[(i + F - 1) % F] == h[(j + 1) % H]) { - shares_edge = true; - } - carve::mesh::MeshSet<3>::vertex_t *t = f[i]; - do { ++I; } while (I < F && f[f_sort[I]] == t); - do { ++J; } while (J < H && h[h_sort[J]] == t); - } else if (f[i] < h[j]) { - ++I; - } else { - unmatched_h_idx = j; - ++J; - } - } - if (J < H) { - unmatched_h_idx = h_sort[J]; - } - } - - - - /** - * \brief Compute an embedding for a set of face loops and hole loops. - * - * Because face and hole loops may be contained within each other, - * it must be determined which hole loops are directly contained - * within a face loop. - * - * @param[in] face The face from which these face and hole loops derive. - * @param[in] face_loops - * @param[in] hole_loops - * @param[out] containing_faces A vector which for each hole loop - * lists the indices of the face - * loops it is containined in. - * @param[out] hole_shared_vertices A map from a face,hole pair to - * a shared vertex pair. - */ - static void computeContainment(carve::mesh::MeshSet<3>::face_t *face, - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &face_loops, - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &hole_loops, - std::vector<std::vector<int> > &containing_faces, - std::map<int, std::map<int, std::pair<unsigned, unsigned> > > &hole_shared_vertices) { -#if defined(CARVE_DEBUG) - std::cerr << "input: " - << face_loops.size() << "faces, " - << hole_loops.size() << "holes." - << std::endl; -#endif - - std::vector<std::vector<carve::geom2d::P2> > face_loops_projected, hole_loops_projected; - std::vector<carve::geom::aabb<2> > face_loop_aabb, hole_loop_aabb; - std::vector<std::vector<unsigned> > face_loops_sorted, hole_loops_sorted; - - std::vector<double> face_loop_areas, hole_loop_areas; - - face_loops_projected.resize(face_loops.size()); - face_loops_sorted.resize(face_loops.size()); - face_loop_aabb.resize(face_loops.size()); - face_loop_areas.resize(face_loops.size()); - - hole_loops_projected.resize(hole_loops.size()); - hole_loops_sorted.resize(hole_loops.size()); - hole_loop_aabb.resize(hole_loops.size()); - hole_loop_areas.resize(hole_loops.size()); - - // produce a projection of each face loop onto a 2D plane, and an - // index vector which sorts vertices by address. - for (size_t m = 0; m < face_loops.size(); ++m) { - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &f_loop = (face_loops[m]); - face_loops_projected[m].reserve(f_loop.size()); - face_loops_sorted[m].reserve(f_loop.size()); - for (size_t n = 0; n < f_loop.size(); ++n) { - face_loops_projected[m].push_back(face->project(f_loop[n]->v)); - face_loops_sorted[m].push_back(n); - } - face_loop_areas.push_back(carve::geom2d::signedArea(face_loops_projected[m])); - - std::sort(face_loops_sorted[m].begin(), face_loops_sorted[m].end(), - carve::make_index_sort(face_loops[m].begin())); - face_loop_aabb[m].fit(face_loops_projected[m].begin(), face_loops_projected[m].end()); - } - - // produce a projection of each hole loop onto a 2D plane, and an - // index vector which sorts vertices by address. - for (size_t m = 0; m < hole_loops.size(); ++m) { - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &h_loop = (hole_loops[m]); - hole_loops_projected[m].reserve(h_loop.size()); - hole_loops_projected[m].reserve(h_loop.size()); - for (size_t n = 0; n < h_loop.size(); ++n) { - hole_loops_projected[m].push_back(face->project(h_loop[n]->v)); - hole_loops_sorted[m].push_back(n); - } - hole_loop_areas.push_back(carve::geom2d::signedArea(hole_loops_projected[m])); - - std::sort(hole_loops_sorted[m].begin(), hole_loops_sorted[m].end(), - carve::make_index_sort(hole_loops[m].begin())); - hole_loop_aabb[m].fit(hole_loops_projected[m].begin(), hole_loops_projected[m].end()); - } - - containing_faces.resize(hole_loops.size()); - - for (unsigned i = 0; i < hole_loops.size(); ++i) { - - for (unsigned j = 0; j < face_loops.size(); ++j) { - if (!face_loop_aabb[j].completelyContains(hole_loop_aabb[i])) { -#if defined(CARVE_DEBUG) - std::cerr << "face: " << j - << " hole: " << i - << " skipped test (aabb fail)" - << std::endl; -#endif - continue; - } - - unsigned f_idx, h_idx; - int unmatched_h_idx; - bool shares_vertex, shares_edge; - compareFaceLoopAndHoleLoop(face_loops[j], - face_loops_sorted[j], - hole_loops[i], - hole_loops_sorted[i], - f_idx, h_idx, - unmatched_h_idx, - shares_vertex, - shares_edge); - -#if defined(CARVE_DEBUG) - std::cerr << "face: " << j - << " hole: " << i - << " shares_vertex: " << shares_vertex - << " shares_edge: " << shares_edge - << std::endl; -#endif - - carve::geom3d::Vector test = hole_loops[i][0]->v; - carve::geom2d::P2 test_p = face->project(test); - - if (shares_vertex) { - hole_shared_vertices[i][j] = std::make_pair(h_idx, f_idx); - // Hole touches face. Should be able to connect it up - // trivially. Still need to record its containment, so that - // the assignment below works. - if (unmatched_h_idx != -1) { -#if defined(CARVE_DEBUG) - std::cerr << "using unmatched vertex: " << unmatched_h_idx << std::endl; -#endif - test = hole_loops[i][unmatched_h_idx]->v; - test_p = face->project(test); - } else { - // XXX: hole shares ALL vertices with face. Pick a point - // internal to the projected poly. - if (shares_edge) { - // Hole shares edge with face => face can't contain hole. - continue; - } - - // XXX: how is this possible? Doesn't share an edge, but - // also doesn't have any vertices that are not in - // common. Degenerate hole? - - // XXX: come up with a test case for this. - CARVE_FAIL("implement me"); - } - } - - - // XXX: use loop area to avoid some point-in-poly tests? Loop - // area is faster, but not sure which is more robust. - if (carve::geom2d::pointInPolySimple(face_loops_projected[j], test_p)) { -#if defined(CARVE_DEBUG) - std::cerr << "contains: " << i << " - " << j << std::endl; -#endif - containing_faces[i].push_back(j); - } else { -#if defined(CARVE_DEBUG) - std::cerr << "does not contain: " << i << " - " << j << std::endl; -#endif - } - } - -#if defined(CARVE_DEBUG) - if (containing_faces[i].size() == 0) { - //HOOK(drawFaceLoopWireframe(hole_loops[i], face->normal, 1.0, 0.0, 0.0, 1.0);); - std::cerr << "hole loop: "; - for (unsigned j = 0; j < hole_loops[i].size(); ++j) { - std::cerr << " " << hole_loops[i][j] << ":" << hole_loops[i][j]->v; - } - std::cerr << std::endl; - for (unsigned j = 0; j < face_loops.size(); ++j) { - //HOOK(drawFaceLoopWireframe(face_loops[j], face->normal, 0.0, 1.0, 0.0, 1.0);); - } - } -#endif - - // CARVE_ASSERT(containing_faces[i].size() >= 1); - } - } - - - - /** - * \brief Merge face loops and hole loops to produce a set of face loops without holes. - * - * @param[in] face The face from which these face loops derive. - * @param[in,out] f_loops A list of face loops. - * @param[in] h_loops A list of hole loops to be incorporated into face loops. - */ - static void mergeFacesAndHoles(carve::mesh::MeshSet<3>::face_t *face, - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &f_loops, - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &h_loops, - carve::csg::CSG::Hooks & /* hooks */) { - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > face_loops; - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > hole_loops; - - std::vector<std::vector<int> > containing_faces; - std::map<int, std::map<int, std::pair<unsigned, unsigned> > > hole_shared_vertices; - -#if defined(CARVE_DEBUG_WRITE_PLY_DATA) - dumpFacesAndHoles(f_loops.begin(), f_loops.end(), h_loops.begin(), h_loops.end(), "/tmp/pre_merge.ply"); -#endif - - { - // move input face and hole loops to temp vectors. - size_t m; - face_loops.resize(f_loops.size()); - m = 0; - for (std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> >::iterator - i = f_loops.begin(), ie = f_loops.end(); - i != ie; - ++i, ++m) { - face_loops[m].swap((*i)); - } - - hole_loops.resize(h_loops.size()); - m = 0; - for (std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> >::iterator - i = h_loops.begin(), ie = h_loops.end(); - i != ie; - ++i, ++m) { - hole_loops[m].swap((*i)); - } - f_loops.clear(); - h_loops.clear(); - } - - // work out the embedding of holes and faces. - computeContainment(face, face_loops, hole_loops, containing_faces, hole_shared_vertices); - - int unassigned = (int)hole_loops.size(); - - std::vector<std::vector<int> > face_holes; - face_holes.resize(face_loops.size()); - - for (unsigned i = 0; i < containing_faces.size(); ++i) { - if (containing_faces[i].size() == 0) { - std::map<int, std::map<int, std::pair<unsigned, unsigned> > >::iterator it = hole_shared_vertices.find(i); - if (it != hole_shared_vertices.end()) { - std::map<int, std::pair<unsigned, unsigned> >::iterator it2 = (*it).second.begin(); - int f = (*it2).first; - unsigned h_idx = (*it2).second.first; - unsigned f_idx = (*it2).second.second; - - // patch the hole into the face directly. because - // f_loop[f_idx] == h_loop[h_idx], we don't need to - // duplicate the f_loop vertex. - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &f_loop = face_loops[f]; - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &h_loop = hole_loops[i]; - - f_loop.insert(f_loop.begin() + f_idx + 1, h_loop.size(), NULL); - - unsigned p = f_idx + 1; - for (unsigned a = h_idx + 1; a < h_loop.size(); ++a, ++p) { - f_loop[p] = h_loop[a]; - } - for (unsigned a = 0; a <= h_idx; ++a, ++p) { - f_loop[p] = h_loop[a]; - } - -#if defined(CARVE_DEBUG) - std::cerr << "hook face " << f << " to hole " << i << "(vertex)" << std::endl; -#endif - } else { - std::cerr << "uncontained hole loop does not share vertices with any face loop!" << std::endl; - } - unassigned--; - } - } - - - // work out which holes are directly contained within which faces. - while (unassigned) { - std::set<int> removed; - - for (unsigned i = 0; i < containing_faces.size(); ++i) { - if (containing_faces[i].size() == 1) { - int f = containing_faces[i][0]; - face_holes[f].push_back(i); -#if defined(CARVE_DEBUG) - std::cerr << "hook face " << f << " to hole " << i << std::endl; -#endif - removed.insert(f); - unassigned--; - } - } - - if (!removed.size()) - throw carve::exception("Failed to merge holes"); - - for (std::set<int>::iterator f = removed.begin(); f != removed.end(); ++f) { - for (unsigned i = 0; i < containing_faces.size(); ++i) { - containing_faces[i].erase(std::remove(containing_faces[i].begin(), - containing_faces[i].end(), - *f), - containing_faces[i].end()); - } - } - } - -#if 0 - // use old templated projection code to patch holes into faces. - for (unsigned i = 0; i < face_loops.size(); ++i) { - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > face_hole_loops; - face_hole_loops.resize(face_holes[i].size()); - for (unsigned j = 0; j < face_holes[i].size(); ++j) { - face_hole_loops[j].swap(hole_loops[face_holes[i][j]]); - } - if (face_hole_loops.size()) { - - f_loops.push_back(carve::triangulate::incorporateHolesIntoPolygon( - carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project), - face_loops[i], - face_hole_loops)); - } else { - f_loops.push_back(face_loops[i]); - } - } - -#else - // use new 2d-only hole patching code. - for (size_t i = 0; i < face_loops.size(); ++i) { - if (!face_holes[i].size()) { - f_loops.push_back(face_loops[i]); - continue; - } - - std::vector<std::vector<carve::geom2d::P2> > projected_poly; - projected_poly.resize(face_holes[i].size() + 1); - projected_poly[0].reserve(face_loops[i].size()); - for (size_t j = 0; j < face_loops[i].size(); ++j) { - projected_poly[0].push_back(face->project(face_loops[i][j]->v)); - } - for (size_t j = 0; j < face_holes[i].size(); ++j) { - projected_poly[j+1].reserve(hole_loops[face_holes[i][j]].size()); - for (size_t k = 0; k < hole_loops[face_holes[i][j]].size(); ++k) { - projected_poly[j+1].push_back(face->project(hole_loops[face_holes[i][j]][k]->v)); - } - } - - std::vector<std::pair<size_t, size_t> > result = carve::triangulate::incorporateHolesIntoPolygon(projected_poly); - - f_loops.push_back(std::vector<carve::mesh::MeshSet<3>::vertex_t *>()); - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &out = f_loops.back(); - out.reserve(result.size()); - for (size_t j = 0; j < result.size(); ++j) { - if (result[j].first == 0) { - out.push_back(face_loops[i][result[j].second]); - } else { - out.push_back(hole_loops[face_holes[i][result[j].first-1]][result[j].second]); - } - } - } -#endif -#if defined(CARVE_DEBUG_WRITE_PLY_DATA) - dumpFacesAndHoles(f_loops.begin(), f_loops.end(), h_loops.begin(), h_loops.end(), "/tmp/post_merge.ply"); -#endif - - } - - - - /** - * \brief Assemble the base loop for a face. - * - * The base loop is the original face loop, including vertices - * created by intersections crossing any of its edges. - * - * @param[in] face The face to process. - * @param[in] vmap - * @param[in] face_split_edges - * @param[in] divided_edges A mapping from edge pointer to sets of - * ordered vertices corrsponding to the intersection points - * on that edge. - * @param[out] base_loop A vector of the vertices of the base loop. - */ - static bool assembleBaseLoop(carve::mesh::MeshSet<3>::face_t *face, - const carve::csg::detail::Data &data, - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop, - carve::csg::CSG::Hooks &hooks) { - base_loop.clear(); - - // XXX: assumes that face->edges is in the same order as - // face->vertices. (Which it is) - carve::mesh::MeshSet<3>::edge_t *e = face->edge; - size_t e_idx = 0; - bool face_edge_intersected = false; - do { - base_loop.push_back(carve::csg::map_vertex(data.vmap, e->vert)); - - carve::csg::detail::EVVMap::const_iterator ev = data.divided_edges.find(e); - - if (ev != data.divided_edges.end()) { - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &ev_vec = ((*ev).second); - - for (size_t k = 0, ke = ev_vec.size(); k < ke;) { - base_loop.push_back(ev_vec[k++]); - } - - if (ev_vec.size() && hooks.hasHook(carve::csg::CSG::Hooks::EDGE_DIVISION_HOOK)) { - carve::mesh::MeshSet<3>::vertex_t *v1 = e->vert; - carve::mesh::MeshSet<3>::vertex_t *v2; - for (size_t k = 0, ke = ev_vec.size(); k < ke;) { - v2 = ev_vec[k++]; - hooks.edgeDivision(e, e_idx, v1, v2); - v1 = v2; - } - v2 = e->v2(); - hooks.edgeDivision(e, e_idx, v1, v2); - } - - face_edge_intersected = true; - } - e = e->next; - ++e_idx; - } while (e != face->edge); - - return face_edge_intersected; - } - - - - // the crossing_data structure holds temporary information regarding - // paths, and their relationship to the loop of edges that forms the - // face perimeter. - struct crossing_data { - std::vector<carve::mesh::MeshSet<3>::vertex_t *> *path; - size_t edge_idx[2]; - - crossing_data(std::vector<carve::mesh::MeshSet<3>::vertex_t *> *p, size_t e1, size_t e2) : path(p) { - edge_idx[0] = e1; edge_idx[1] = e2; - } - - bool operator<(const crossing_data &c) const { - // the sort order for paths is in order of increasing initial - // position on the edge loop, but decreasing final position. - return edge_idx[0] < c.edge_idx[0] || (edge_idx[0] == c.edge_idx[0] && edge_idx[1] > c.edge_idx[1]); - } - }; - - - - bool processCrossingEdges(carve::mesh::MeshSet<3>::face_t *face, - const carve::csg::VertexIntersections &vertex_intersections, - carve::csg::CSG::Hooks &hooks, - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop, - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &paths, - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &face_loops_out) { - const size_t N = base_loop.size(); - std::vector<crossing_data> endpoint_indices; - - endpoint_indices.reserve(paths.size()); - - for (size_t i = 0; i < paths.size(); ++i) { - endpoint_indices.push_back(crossing_data(&paths[i], N, N)); - } - - // Step 1: - // locate endpoints of paths on the base loop. - for (size_t i = 0; i < N; ++i) { - for (size_t j = 0; j < paths.size(); ++j) { - // test beginning of path. - if (paths[j].front() == base_loop[i]) { - if (endpoint_indices[j].edge_idx[0] == N) { - endpoint_indices[j].edge_idx[0] = i; - } else { - // there is a duplicated vertex in the face perimeter. The - // path might attach to either of the duplicate instances - // so we have to work out which is the right one to attach - // to. We assume it's the index currently being examined, - // if the path heads in a direction that's internal to the - // angle made by the prior and next edges of the face - // perimeter. Otherwise, leave it as the currently - // selected index (until another duplicate is found, if it - // exists, and is tested). - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &p = *endpoint_indices[j].path; - const size_t pN = p.size(); - - carve::mesh::MeshSet<3>::vertex_t *a, *b, *c; - a = base_loop[(i+N-1)%N]; - b = base_loop[i]; - c = base_loop[(i+1)%N]; - - carve::mesh::MeshSet<3>::vertex_t *adj = (p[0] == base_loop[i]) ? p[1] : p[pN-2]; - - if (carve::geom2d::internalToAngle(face->project(c->v), - face->project(b->v), - face->project(a->v), - face->project(adj->v))) { - endpoint_indices[j].edge_idx[0] = i; - } - } - } - - // test end of path. - if (paths[j].back() == base_loop[i]) { - if (endpoint_indices[j].edge_idx[1] == N) { - endpoint_indices[j].edge_idx[1] = i; - } else { - // Work out which of the duplicated vertices is the right - // one to attach to, as above. - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &p = *endpoint_indices[j].path; - const size_t pN = p.size(); - - carve::mesh::MeshSet<3>::vertex_t *a, *b, *c; - a = base_loop[(i+N-1)%N]; - b = base_loop[i]; - c = base_loop[(i+1)%N]; - - carve::mesh::MeshSet<3>::vertex_t *adj = (p[0] == base_loop[i]) ? p[1] : p[pN-2]; - - if (carve::geom2d::internalToAngle(face->project(c->v), - face->project(b->v), - face->project(a->v), - face->project(adj->v))) { - endpoint_indices[j].edge_idx[1] = i; - } - } - } - } - } - -#if defined(CARVE_DEBUG) - std::cerr << "### N: " << N << std::endl; - for (size_t i = 0; i < paths.size(); ++i) { - std::cerr << "### path: " << i << " endpoints: " << endpoint_indices[i].edge_idx[0] << " - " << endpoint_indices[i].edge_idx[1] << std::endl; - } -#endif - - - // Step 2: - // divide paths up into those that connect to the base loop in two - // places (cross), and those that do not (noncross). - std::vector<crossing_data> cross, noncross; - cross.reserve(endpoint_indices.size() + 1); - noncross.reserve(endpoint_indices.size()); - - for (size_t i = 0; i < endpoint_indices.size(); ++i) { -#if defined(CARVE_DEBUG) - std::cerr << "### orienting path: " << i << " endpoints: " << endpoint_indices[i].edge_idx[0] << " - " << endpoint_indices[i].edge_idx[1] << std::endl; -#endif - if (endpoint_indices[i].edge_idx[0] != N && endpoint_indices[i].edge_idx[1] != N) { - // Orient each path correctly. Paths should progress from - // smaller perimeter index to larger, but if the path starts - // and ends at the same perimeter index, then the decision - // needs to be made based upon area. - if (endpoint_indices[i].edge_idx[0] == endpoint_indices[i].edge_idx[1]) { - // The path forms a loop that starts and ends at the same - // vertex of the perimeter. In this case, we need to orient - // the path so that the constructed loop has the right - // signed area. - double area = carve::geom2d::signedArea(endpoint_indices[i].path->begin() + 1, - endpoint_indices[i].path->end(), - carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project)); - if (area < 0) { - // XXX: Create test case to check that this is the correct sign for the area. - std::reverse(endpoint_indices[i].path->begin(), endpoint_indices[i].path->end()); - } - } else { - if (endpoint_indices[i].edge_idx[0] > endpoint_indices[i].edge_idx[1]) { - std::swap(endpoint_indices[i].edge_idx[0], endpoint_indices[i].edge_idx[1]); - std::reverse(endpoint_indices[i].path->begin(), endpoint_indices[i].path->end()); - } - } - } - - if (endpoint_indices[i].edge_idx[0] != N && - endpoint_indices[i].edge_idx[1] != N && - endpoint_indices[i].edge_idx[0] != endpoint_indices[i].edge_idx[1]) { - cross.push_back(endpoint_indices[i]); - } else { - noncross.push_back(endpoint_indices[i]); - } - } - - // Step 3: - // add a temporary crossing path that connects the beginning and the - // end of the base loop. this stops us from needing special case - // code to handle the left over loop after all the other crossing - // paths are considered. - std::vector<carve::mesh::MeshSet<3>::vertex_t *> base_loop_temp_path; - base_loop_temp_path.reserve(2); - base_loop_temp_path.push_back(base_loop.front()); - base_loop_temp_path.push_back(base_loop.back()); - - cross.push_back(crossing_data(&base_loop_temp_path, 0, base_loop.size() - 1)); -#if defined(CARVE_DEBUG) - std::cerr << "### crossing edge count (with sentinel): " << cross.size() << std::endl; -#endif - - // Step 4: - // sort paths by increasing beginning point and decreasing ending point. - std::sort(cross.begin(), cross.end()); - std::sort(noncross.begin(), noncross.end()); - - // Step 5: - // divide up the base loop based upon crossing paths. - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > divided_base_loop; - divided_base_loop.reserve(cross.size()); - std::vector<carve::mesh::MeshSet<3>::vertex_t *> out; - - for (size_t i = 0; i < cross.size(); ++i) { - size_t j; - for (j = i + 1; - j < cross.size() && - cross[i].edge_idx[0] == cross[j].edge_idx[0] && - cross[i].edge_idx[1] == cross[j].edge_idx[1]; - ++j) {} - if (j - i >= 2) { - // when there are multiple paths that begin and end at the - // same point, they need to be ordered so that the constructed - // loops have the right orientation. this means that the loop - // made by taking path(i+1) forward, then path(i) backward - // needs to have negative area. this combined area is equal to - // the area of path(i+1) minus the area of path(i). in turn - // this means that the loop made by path path(i+1) alone has - // to have smaller signed area than loop made by path(i). - // thus, we sort paths in order of decreasing area. - - std::vector<std::pair<double, std::vector<carve::mesh::MeshSet<3>::vertex_t *> *> > order; - order.reserve(j - i); - for (size_t k = i; k < j; ++k) { - double area = carve::geom2d::signedArea(cross[k].path->begin(), - cross[k].path->end(), - carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project)); -#if defined(CARVE_DEBUG) - std::cerr << "### k=" << k << " area=" << area << std::endl; -#endif - order.push_back(std::make_pair(-area, cross[k].path)); - } - std::sort(order.begin(), order.end()); - for (size_t k = i; k < j; ++k) { - cross[k].path = order[k-i].second; -#if defined(CARVE_DEBUG) - std::cerr << "### post-sort k=" << k << " cross[k].path->size()=" << cross[k].path->size() << std::endl; -#endif - } - } - } - - // Step 6: - for (size_t i = 0; i < cross.size(); ++i) { -#if defined(CARVE_DEBUG) - std::cerr << "### i=" << i << " working on edge: " << cross[i].edge_idx[0] << " - " << cross[i].edge_idx[1] << std::endl; -#endif - size_t e1_0 = cross[i].edge_idx[0]; - size_t e1_1 = cross[i].edge_idx[1]; - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &p1 = *cross[i].path; -#if defined(CARVE_DEBUG) - std::cerr << "### path size = " << p1.size() << std::endl; -#endif - - out.clear(); - - if (i < cross.size() - 1 && - cross[i+1].edge_idx[1] <= cross[i].edge_idx[1]) { -#if defined(CARVE_DEBUG) - std::cerr << "### complex case" << std::endl; -#endif - // complex case. crossing path with other crossing paths embedded within. - size_t pos = e1_0; - - size_t skip = i+1; - - while (pos != e1_1) { - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &p2 = *cross[skip].path; - size_t e2_0 = cross[skip].edge_idx[0]; - size_t e2_1 = cross[skip].edge_idx[1]; - - // copy up to the beginning of the next path. - std::copy(base_loop.begin() + pos, base_loop.begin() + e2_0, std::back_inserter(out)); - - CARVE_ASSERT(base_loop[e2_0] == p2[0]); - // copy the next path in the right direction. - std::copy(p2.begin(), p2.end() - 1, std::back_inserter(out)); - - // move to the position of the end of the path. - pos = e2_1; - - // advance to the next hit path. - do { - ++skip; - } while(skip != cross.size() && cross[skip].edge_idx[0] < e2_1); - - if (skip == cross.size()) break; - - // if the next hit path is past the start point of the current path, we're done. - if (cross[skip].edge_idx[0] >= e1_1) break; - } - - // copy up to the end of the path. - if (pos < e1_1) { - std::copy(base_loop.begin() + pos, base_loop.begin() + e1_1, std::back_inserter(out)); - } - - CARVE_ASSERT(base_loop[e1_1] == p1.back()); - std::copy(p1.rbegin(), p1.rend() - 1, std::back_inserter(out)); - } else { - size_t loop_size = (e1_1 - e1_0) + (p1.size() - 1); - out.reserve(loop_size); - - std::copy(base_loop.begin() + e1_0, base_loop.begin() + e1_1, std::back_inserter(out)); - std::copy(p1.rbegin(), p1.rend() - 1, std::back_inserter(out)); - - CARVE_ASSERT(out.size() == loop_size); - } - divided_base_loop.push_back(out); - -#if defined(CARVE_DEBUG) - { - std::vector<carve::geom2d::P2> projected; - projected.reserve(out.size()); - for (size_t n = 0; n < out.size(); ++n) { - projected.push_back(face->project(out[n]->v)); - } - - double A = carve::geom2d::signedArea(projected); - std::cerr << "### out area=" << A << std::endl; - CARVE_ASSERT(A <= 0); - } -#endif - } - - if (!noncross.size()) { - // If there are no non-crossing paths then we're done. - populateListFromVector(divided_base_loop, face_loops_out); - return true; - } - - // for each divided base loop, work out which noncrossing paths and - // loops are part of it. use the old algorithm to combine these into - // the divided base loop. if none, the divided base loop is just - // output. - std::vector<std::vector<carve::geom2d::P2> > proj; - std::vector<carve::geom::aabb<2> > proj_aabb; - proj.resize(divided_base_loop.size()); - proj_aabb.resize(divided_base_loop.size()); - - // calculate an aabb for each divided base loop, to avoid expensive - // point-in-poly tests. - for (size_t i = 0; i < divided_base_loop.size(); ++i) { - proj[i].reserve(divided_base_loop[i].size()); - for (size_t j = 0; j < divided_base_loop[i].size(); ++j) { - proj[i].push_back(face->project(divided_base_loop[i][j]->v)); - } - proj_aabb[i].fit(proj[i].begin(), proj[i].end()); - } - - for (size_t i = 0; i < divided_base_loop.size(); ++i) { - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> *> inc; - carve::geom2d::P2 test; - - // for each noncrossing path, choose an endpoint that isn't on the - // base loop as a test point. - for (size_t j = 0; j < noncross.size(); ++j) { - if (noncross[j].edge_idx[0] < N) { - if (noncross[j].path->front() == base_loop[noncross[j].edge_idx[0]]) { - // noncrossing paths may be loops that run from the edge, back to the same vertex. - if (noncross[j].path->front() == noncross[j].path->back()) { - CARVE_ASSERT(noncross[j].path->size() > 2); - test = face->project((*noncross[j].path)[1]->v); - } else { - test = face->project(noncross[j].path->back()->v); - } - } else { - test = face->project(noncross[j].path->front()->v); - } - } else { - test = face->project(noncross[j].path->front()->v); - } - - if (proj_aabb[i].intersects(test) && - carve::geom2d::pointInPoly(proj[i], test).iclass != carve::POINT_OUT) { - inc.push_back(noncross[j].path); - } - } - -#if defined(CARVE_DEBUG) - std::cerr << "### divided base loop:" << i << " inc.size()=" << inc.size() << std::endl; - std::cerr << "### inc = ["; - for (size_t j = 0; j < inc.size(); ++j) { - std::cerr << " " << inc[j]; - } - std::cerr << " ]" << std::endl; -#endif - - if (inc.size()) { - carve::csg::V2Set face_edges; - - for (size_t j = 0; j < divided_base_loop[i].size() - 1; ++j) { - face_edges.insert(std::make_pair(divided_base_loop[i][j], - divided_base_loop[i][j+1])); - } - - face_edges.insert(std::make_pair(divided_base_loop[i].back(), - divided_base_loop[i].front())); - - for (size_t j = 0; j < inc.size(); ++j) { - std::vector<carve::mesh::MeshSet<3>::vertex_t *> &path = *inc[j]; - for (size_t k = 0; k < path.size() - 1; ++k) { - face_edges.insert(std::make_pair(path[k], path[k+1])); - face_edges.insert(std::make_pair(path[k+1], path[k])); - } - } - - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > face_loops; - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > hole_loops; - - splitFace(face, face_edges, face_loops, hole_loops, vertex_intersections); - - if (hole_loops.size()) { - mergeFacesAndHoles(face, face_loops, hole_loops, hooks); - } - std::copy(face_loops.begin(), face_loops.end(), std::back_inserter(face_loops_out)); - } else { - face_loops_out.push_back(divided_base_loop[i]); - } - } - return true; - } - - - - void composeEdgesIntoPaths(const carve::csg::V2Set &edges, - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &extra_endpoints, - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &paths, - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &cuts, - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &loops) { - using namespace carve::csg; - - detail::VVSMap vertex_graph; - detail::VSet endpoints; - detail::VSet cut_endpoints; - - typedef std::vector<carve::mesh::MeshSet<3>::vertex_t *> vvec_t; - vvec_t path; - - std::list<vvec_t> path_list, cut_list, loop_list; - - // build graph from edges. - for (V2Set::const_iterator i = edges.begin(); i != edges.end(); ++i) { -#if defined(CARVE_DEBUG) - std::cerr << "### edge: " << (*i).first << " - " << (*i).second << std::endl; -#endif - vertex_graph[(*i).first].insert((*i).second); - vertex_graph[(*i).second].insert((*i).first); - } - - // find the endpoints in the graph. - // every vertex with number of incident edges != 2 is an endpoint. - for (detail::VVSMap::const_iterator i = vertex_graph.begin(); i != vertex_graph.end(); ++i) { - if ((*i).second.size() != 2) { -#if defined(CARVE_DEBUG) - std::cerr << "### endpoint: " << (*i).first << std::endl; -#endif - endpoints.insert((*i).first); - if ((*i).second.size() == 1) { - cut_endpoints.insert((*i).first); - } - } - } - - // every vertex on the perimeter of the face is also an endpoint. - for (size_t i = 0; i < extra_endpoints.size(); ++i) { - if (vertex_graph.find(extra_endpoints[i]) != vertex_graph.end()) { -#if defined(CARVE_DEBUG) - std::cerr << "### extra endpoint: " << extra_endpoints[i] << std::endl; -#endif - endpoints.insert(extra_endpoints[i]); - cut_endpoints.erase(extra_endpoints[i]); - } - } - - while (endpoints.size()) { - carve::mesh::MeshSet<3>::vertex_t *v = *endpoints.begin(); - detail::VVSMap::iterator p = vertex_graph.find(v); - if (p == vertex_graph.end()) { - endpoints.erase(endpoints.begin()); - continue; - } - - path.clear(); - path.push_back(v); - - for (;;) { - CARVE_ASSERT(p != vertex_graph.end()); - - // pick a connected vertex to move to. - if ((*p).second.size() == 0) break; - - carve::mesh::MeshSet<3>::vertex_t *n = *((*p).second.begin()); - detail::VVSMap::iterator q = vertex_graph.find(n); - - // remove the link. - (*p).second.erase(n); - (*q).second.erase(v); - - // move on. - v = n; - path.push_back(v); - - if ((*p).second.size() == 0) vertex_graph.erase(p); - if ((*q).second.size() == 0) { - vertex_graph.erase(q); - q = vertex_graph.end(); - } - - p = q; - - if (v == path[0] || p == vertex_graph.end() || endpoints.find(v) != endpoints.end()) break; - } - CARVE_ASSERT(endpoints.find(path.back()) != endpoints.end()); - - bool is_cut = - cut_endpoints.find(path.front()) != cut_endpoints.end() && - cut_endpoints.find(path.back()) != cut_endpoints.end(); - - if (is_cut) { - cut_list.push_back(vvec_t()); path.swap(cut_list.back()); - } else { - path_list.push_back(vvec_t()); path.swap(path_list.back()); - } - } - - populateVectorFromList(path_list, paths); - populateVectorFromList(cut_list, cuts); - - // now only loops should remain in the graph. - while (vertex_graph.size()) { - detail::VVSMap::iterator p = vertex_graph.begin(); - carve::mesh::MeshSet<3>::vertex_t *v = (*p).first; - CARVE_ASSERT((*p).second.size() == 2); - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> path; - path.clear(); - path.push_back(v); - - for (;;) { - CARVE_ASSERT(p != vertex_graph.end()); - // pick a connected vertex to move to. - - carve::mesh::MeshSet<3>::vertex_t *n = *((*p).second.begin()); - detail::VVSMap::iterator q = vertex_graph.find(n); - - // remove the link. - (*p).second.erase(n); - (*q).second.erase(v); - - // move on. - v = n; - path.push_back(v); - - if ((*p).second.size() == 0) vertex_graph.erase(p); - if ((*q).second.size() == 0) vertex_graph.erase(q); - - p = q; - - if (v == path[0]) break; - } - - loop_list.push_back(vvec_t()); path.swap(loop_list.back()); - } - - populateVectorFromList(loop_list, loops); - } - - - - template<typename T> - std::string ptrstr(const T *ptr) { - std::ostringstream s; - s << ptr; - return s.str().substr(1); - } - -#if 0 - void dumpAsGraph(carve::mesh::MeshSet<3>::face_t *face, - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop, - const carve::csg::V2Set &face_edges, - const carve::csg::V2Set &split_edges) { - std::map<carve::mesh::MeshSet<3>::vertex_t *, carve::geom2d::P2> proj; - - for (size_t i = 0; i < base_loop.size(); ++i) { - proj[base_loop[i]] = face->project(base_loop[i]->v); - } - for (carve::csg::V2Set::const_iterator i = split_edges.begin(); i != split_edges.end(); ++i) { - proj[(*i).first] = face->project((*i).first->v); - proj[(*i).second] = face->project((*i).second->v); - } - - { - carve::geom2d::P2 lo, hi; - std::map<carve::mesh::MeshSet<3>::vertex_t *, carve::geom2d::P2>::iterator i; - i = proj.begin(); - lo = hi = (*i).second; - for (; i != proj.end(); ++i) { - lo.x = std::min(lo.x, (*i).second.x); lo.y = std::min(lo.y, (*i).second.y); - hi.x = std::max(hi.x, (*i).second.x); hi.y = std::max(hi.y, (*i).second.y); - } - for (i = proj.begin(); i != proj.end(); ++i) { - (*i).second.x = ((*i).second.x - lo.x) / (hi.x - lo.x) * 10; - (*i).second.y = ((*i).second.y - lo.y) / (hi.y - lo.y) * 10; - } - } - - std::cerr << "graph G {\nnode [shape=circle,style=filled,fixedsize=true,width=\".1\",height=\".1\"];\nedge [len=4]\n"; - for (std::map<carve::mesh::MeshSet<3>::vertex_t *, carve::geom2d::P2>::iterator i = proj.begin(); i != proj.end(); ++i) { - std::cerr << " " << ptrstr((*i).first) << " [pos=\"" << (*i).second.x << "," << (*i).second.y << "!\"];\n"; - } - for (carve::csg::V2Set::const_iterator i = face_edges.begin(); i != face_edges.end(); ++i) { - std::cerr << " " << ptrstr((*i).first) << " -- " << ptrstr((*i).second) << ";\n"; - } - for (carve::csg::V2Set::const_iterator i = split_edges.begin(); i != split_edges.end(); ++i) { - std::cerr << " " << ptrstr((*i).first) << " -- " << ptrstr((*i).second) << " [color=\"blue\"];\n"; - } - std::cerr << "};\n"; - } -#endif - - void generateOneFaceLoop(carve::mesh::MeshSet<3>::face_t *face, - const carve::csg::detail::Data &data, - const carve::csg::VertexIntersections &vertex_intersections, - carve::csg::CSG::Hooks &hooks, - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &face_loops) { - using namespace carve::csg; - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> base_loop; - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > hole_loops; - - /*bool face_edge_intersected = */assembleBaseLoop(face, data, base_loop, hooks); - - detail::FV2SMap::const_iterator fse_iter = data.face_split_edges.find(face); - - face_loops.clear(); - - if (fse_iter == data.face_split_edges.end()) { - // simple case: input face is output face (possibly with the - // addition of vertices at intersections). - face_loops.push_back(base_loop); - return; - } - - // complex case: input face is split into multiple output faces. - V2Set face_edges; - - for (size_t j = 0, je = base_loop.size() - 1; j < je; ++j) { - face_edges.insert(std::make_pair(base_loop[j], base_loop[j + 1])); - } - face_edges.insert(std::make_pair(base_loop.back(), base_loop[0])); - - // collect the split edges (as long as they're not on the perimeter) - const detail::FV2SMap::mapped_type &fse = ((*fse_iter).second); - - // split_edges contains all of the edges created by intersections - // that aren't part of the perimeter of the face. - V2Set split_edges; - - for (detail::FV2SMap::mapped_type::const_iterator - j = fse.begin(), je = fse.end(); - j != je; - ++j) { - carve::mesh::MeshSet<3>::vertex_t *v1 = ((*j).first), *v2 = ((*j).second); - - if (face_edges.find(std::make_pair(v1, v2)) == face_edges.end() && - face_edges.find(std::make_pair(v2, v1)) == face_edges.end()) { - // If the edge isn't part of the face perimeter, add it to - // split_edges. - split_edges.insert(ordered_edge(v1, v2)); - } - } - - // face is unsplit. - if (!split_edges.size()) { - face_loops.push_back(base_loop); - return; - } - -#if defined(CARVE_DEBUG) - dumpAsGraph(face, base_loop, face_edges, split_edges); -#endif - -#if 0 - // old face splitting method. - for (V2Set::const_iterator i = split_edges.begin(); i != split_edges.end(); ++i) { - face_edges.insert(std::make_pair((*i).first, (*i).second)); - face_edges.insert(std::make_pair((*i).second, (*i).first)); - } - splitFace(face, face_edges, face_loops, hole_loops, vertex_intersections); - - if (hole_loops.size()) { - mergeFacesAndHoles(face, face_loops, hole_loops, hooks); - } - return; -#endif - -#if defined(CARVE_DEBUG) - std::cerr << "### split_edges.size(): " << split_edges.size() << std::endl; -#endif - if (split_edges.size() == 1) { - // handle the common case of a face that's split by a single edge. - carve::mesh::MeshSet<3>::vertex_t *v1 = split_edges.begin()->first; - carve::mesh::MeshSet<3>::vertex_t *v2 = split_edges.begin()->second; - - std::vector<carve::mesh::MeshSet<3>::vertex_t *>::iterator vi1 = std::find(base_loop.begin(), base_loop.end(), v1); - std::vector<carve::mesh::MeshSet<3>::vertex_t *>::iterator vi2 = std::find(base_loop.begin(), base_loop.end(), v2); - - if (vi1 != base_loop.end() && vi2 != base_loop.end()) { - // this is an inserted edge that connects two points on the base loop. nice and simple. - if (vi2 < vi1) std::swap(vi1, vi2); - - size_t loop1_size = vi2 - vi1 + 1; - size_t loop2_size = base_loop.size() + 2 - loop1_size; - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> l1; - std::vector<carve::mesh::MeshSet<3>::vertex_t *> l2; - - l1.reserve(loop1_size); - l2.reserve(loop2_size); - - std::copy(vi1, vi2+1, std::back_inserter(l1)); - std::copy(vi2, base_loop.end(), std::back_inserter(l2)); - std::copy(base_loop.begin(), vi1+1, std::back_inserter(l2)); - - CARVE_ASSERT(l1.size() == loop1_size); - CARVE_ASSERT(l2.size() == loop2_size); - - face_loops.push_back(l1); - face_loops.push_back(l2); - - return; - } - - // Consider handling cases where one end of the edge touches the - // perimeter, and where neither end does. - } - - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > paths; - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > cuts; - std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > loops; - - // Take the split edges and compose them into a set of paths and - // loops. Loops are edge paths that do not touch the boundary, or - // any other path or loop - they are holes cut out of the centre - // of the face. Paths are made up of all the other edge segments, - // and start and end at the face perimeter, or where they meet - // another path (sometimes both cases will be true). - composeEdgesIntoPaths(split_edges, base_loop, paths, cuts, loops); - -#if defined(CARVE_DEBUG) - std::cerr << "### paths.size(): " << paths.size() << std::endl; - std::cerr << "### cuts.size(): " << cuts.size() << std::endl; - std::cerr << "### loops.size(): " << loops.size() << std::endl; -#endif - - if (!paths.size()) { - // No complex paths. - face_loops.push_back(base_loop); - } else { - if (processCrossingEdges(face, vertex_intersections, hooks, base_loop, paths, face_loops)) { - // Worked. - } else { - // complex case - fall back to old edge tracing code. -#if defined(CARVE_DEBUG) - std::cerr << "### processCrossingEdges failed. Falling back to edge tracing code" << std::endl; -#endif - for (size_t i = 0; i < paths.size(); ++i) { - for (size_t j = 0; j < paths[i].size() - 1; ++j) { - face_edges.insert(std::make_pair(paths[i][j], paths[i][j+1])); - face_edges.insert(std::make_pair(paths[i][j+1], paths[i][j])); - } - } - splitFace(face, face_edges, face_loops, hole_loops, vertex_intersections); - } - } - - // Now merge cuts and loops into face loops. - - // every cut creates a hole. - for (size_t i = 0; i < cuts.size(); ++i) { - hole_loops.push_back(std::vector<carve::mesh::MeshSet<3>::vertex_t *>()); - hole_loops.back().reserve(2 * cuts[i].size() - 2); - std::copy(cuts[i].begin(), cuts[i].end(), std::back_inserter(hole_loops.back())); - if (cuts[i].size() > 2) { - std::copy(cuts[i].rbegin() + 1, cuts[i].rend() - 1, std::back_inserter(hole_loops.back())); - } - } - - // every loop creates a hole and a corresponding face. - for (size_t i = 0; i < loops.size(); ++i) { - hole_loops.push_back(std::vector<carve::mesh::MeshSet<3>::vertex_t *>()); - hole_loops.back().reserve(loops[i].size()-1); - std::copy(loops[i].begin(), loops[i].end()-1, std::back_inserter(hole_loops.back())); - - face_loops.push_back(std::vector<carve::mesh::MeshSet<3>::vertex_t *>()); - face_loops.back().reserve(loops[i].size()-1); - std::copy(loops[i].rbegin()+1, loops[i].rend(), std::back_inserter(face_loops.back())); - - std::vector<carve::geom2d::P2> projected; - projected.reserve(face_loops.back().size()); - for (size_t i = 0; i < face_loops.back().size(); ++i) { - projected.push_back(face->project(face_loops.back()[i]->v)); - } - - if (carve::geom2d::signedArea(projected) > 0.0) { - std::swap(face_loops.back(), hole_loops.back()); - } - } - - // if there are holes, then they need to be merged with faces. - if (hole_loops.size()) { - mergeFacesAndHoles(face, face_loops, hole_loops, hooks); - } - } -} - - - -/** - * \brief Build a set of face loops for all (split) faces of a Polyhedron. - * - * @param[in] poly The polyhedron to process - * @param[in] data Internal intersection data - * @param[out] face_loops_out The resulting face loops - * - * @return The number of edges generated. - */ -size_t carve::csg::CSG::generateFaceLoops(carve::mesh::MeshSet<3> *poly, - const detail::Data &data, - FaceLoopList &face_loops_out) { - static carve::TimingName FUNC_NAME("CSG::generateFaceLoops()"); - carve::TimingBlock block(FUNC_NAME); - size_t generated_edges = 0; - std::vector<carve::mesh::MeshSet<3>::vertex_t *> base_loop; - std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > face_loops; - - for (carve::mesh::MeshSet<3>::face_iter i = poly->faceBegin(); i != poly->faceEnd(); ++i) { - carve::mesh::MeshSet<3>::face_t *face = (*i); - -#if defined(CARVE_DEBUG) - double in_area = 0.0, out_area = 0.0; - - { - std::vector<carve::mesh::MeshSet<3>::vertex_t *> base_loop; - assembleBaseLoop(face, data, base_loop); - - { - std::vector<carve::geom2d::P2> projected; - projected.reserve(base_loop.size()); - for (size_t n = 0; n < base_loop.size(); ++n) { - projected.push_back(face->project(base_loop[n]->v)); - } - - in_area = carve::geom2d::signedArea(projected); - std::cerr << "### in_area=" << in_area << std::endl; - } - } -#endif - - generateOneFaceLoop(face, data, vertex_intersections, hooks, face_loops); - -#if defined(CARVE_DEBUG) - { - V2Set face_edges; - - std::vector<carve::mesh::MeshSet<3>::vertex_t *> base_loop; - assembleBaseLoop(face, data, base_loop); - - for (size_t j = 0, je = base_loop.size() - 1; j < je; ++j) { - face_edges.insert(std::make_pair(base_loop[j+1], base_loop[j])); - } - face_edges.insert(std::make_pair(base_loop[0], base_loop.back())); - for (std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> >::const_iterator fli = face_loops.begin(); fli != face_loops.end(); ++ fli) { - - { - std::vector<carve::geom2d::P2> projected; - projected.reserve((*fli).size()); - for (size_t n = 0; n < (*fli).size(); ++n) { - projected.push_back(face->project((*fli)[n]->v)); - } - - double area = carve::geom2d::signedArea(projected); - std::cerr << "### loop_area[" << std::distance((std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> >::const_iterator)face_loops.begin(), fli) << "]=" << area << std::endl; - out_area += area; - } - - const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &fl = *fli; - for (size_t j = 0, je = fl.size() - 1; j < je; ++j) { - face_edges.insert(std::make_pair(fl[j], fl[j+1])); - } - face_edges.insert(std::make_pair(fl.back(), fl[0])); - } - for (V2Set::const_iterator j = face_edges.begin(); j != face_edges.end(); ++j) { - if (face_edges.find(std::make_pair((*j).second, (*j).first)) == face_edges.end()) { - std::cerr << "### error: unmatched edge [" << (*j).first << "-" << (*j).second << "]" << std::endl; - } - } - std::cerr << "### out_area=" << out_area << std::endl; - if (out_area != in_area) { - std::cerr << "### error: area does not match. delta = " << (out_area - in_area) << std::endl; - // CARVE_ASSERT(fabs(out_area - in_area) < 1e-5); - } - } -#endif - - // now record all the resulting face loops. -#if defined(CARVE_DEBUG) - std::cerr << "### ======" << std::endl; -#endif - for (std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> >::const_iterator - f = face_loops.begin(), fe = face_loops.end(); - f != fe; - ++f) { -#if defined(CARVE_DEBUG) - std::cerr << "### loop:"; - for (size_t i = 0; i < (*f).size(); ++i) { - std::cerr << " " << (*f)[i]; - } - std::cerr << std::endl; -#endif - - face_loops_out.append(new FaceLoop(face, *f)); - generated_edges += (*f).size(); - } -#if defined(CARVE_DEBUG) - std::cerr << "### ======" << std::endl; -#endif - } - return generated_edges; -} |