/******************************************************************************* * CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps * * version 0.1 * * Copyright (C) 2009, IGG Team, LSIIT, University of Strasbourg * * * * This library is free software; you can redistribute it and/or modify it * * under the terms of the GNU Lesser General Public License as published by the * * Free Software Foundation; either version 2.1 of the License, or (at your * * option) any later version. * * * * This library is distributed in the hope that it will be useful, but WITHOUT * * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License * * for more details. * * * * You should have received a copy of the GNU Lesser General Public License * * along with this library; if not, write to the Free Software Foundation, * * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. * * * * Web site: http://cgogn.unistra.fr/ * * Contact information: cgogn@unistra.fr * * * *******************************************************************************/ #include "Topology/generic/traversor2.h" #include "Algo/Geometry/intersection.h" #include namespace CGoGN { namespace Algo { namespace Selection { /********************************************************* * Generic Collector *********************************************************/ template Collector::Collector(typename PFP::MAP& m) : map(m) {} template inline bool Collector::applyOnInsideVertices(FunctorType& f) { for(std::vector::iterator iv = insideVertices.begin(); iv != insideVertices.end(); ++iv) if(f(*iv)) return true ; return false ; } template inline bool Collector::applyOnInsideEdges(FunctorType& f) { for(std::vector::iterator iv = insideEdges.begin(); iv != insideEdges.end(); ++iv) if(f(*iv)) return true ; return false ; } template inline bool Collector::applyOnInsideFaces(FunctorType& f) { for(std::vector::iterator iv = insideFaces.begin(); iv != insideFaces.end(); ++iv) if(f(*iv)) return true ; return false ; } template inline bool Collector::applyOnBorder(FunctorType& f) { for(std::vector::iterator iv = border.begin(); iv != border.end(); ++iv) if(f(*iv)) return true ; return false ; } template std::ostream& operator<<(std::ostream &out, const Collector& c) { out << "Collector around " << c.centerDart << std::endl; out << "insideVertices (" << c.insideVertices.size() << ") = {"; for (unsigned int i = 0; i< c.insideVertices.size(); ++i) out << c.insideVertices[i] << " "; out << "}" << std::endl ; out << "insideEdges (" << c.insideEdges.size() << ") = {"; for (unsigned int i = 0; i< c.insideEdges.size(); ++i) out << c.insideEdges[i] << " "; out << "}" << std::endl ; out << "insideFaces (" << c.insideFaces.size() << ") = {"; for (unsigned int i = 0; i< c.insideFaces.size(); ++i) out << c.insideFaces[i] << " "; out << "}" << std::endl ; out << "border (" << c.border.size() << ") = {"; for (unsigned int i = 0; i< c.border.size(); ++i) out << c.border[i] << " "; out << "}" << std::endl; return out; } /********************************************************* * Collector One Ring *********************************************************/ template void Collector_OneRing::collectAll(Dart d) { this->init(d); this->insideEdges.reserve(16); this->insideFaces.reserve(16); this->border.reserve(16); this->insideVertices.push_back(this->centerDart); Traversor2VE te(this->map, this->centerDart) ; for(Dart it = te.begin(); it != te.end(); it = te.next()) this->insideEdges.push_back(it); Traversor2VF tf(this->map, this->centerDart) ; for(Dart it = tf.begin(); it != tf.end(); it = tf.next()) { this->insideFaces.push_back(it); this->border.push_back(this->map.phi1(it)); } } template void Collector_OneRing::collectBorder(Dart d) { this->init(d); this->border.reserve(12); Traversor2VF t(this->map, this->centerDart) ; for(Dart it = t.begin(); it != t.end(); it = t.next()) this->border.push_back(this->map.phi1(it)); } /********************************************************* * Collector Within Sphere *********************************************************/ template void Collector_WithinSphere::collectAll(Dart d) { typedef typename PFP::VEC3 VEC3; typedef typename PFP::REAL REAL; this->init(d); this->insideEdges.reserve(32); this->insideFaces.reserve(32); this->border.reserve(32); CellMarkerStore vm(this->map); // mark the collected inside-vertices CellMarkerStore em(this->map); // mark the collected inside-edges + border-edges CellMarkerStore fm(this->map); // mark the collected inside-faces + border-faces this->insideVertices.push_back(this->centerDart); vm.mark(this->centerDart); VEC3 centerPosition = this->position[d]; unsigned int i = 0; // for(std::vector::iterator iv = this->insideVertices.begin(); iv != this->insideVertices.end(); ++iv) while (i < this->insideVertices.size()) { Dart end = this->insideVertices[i]; Dart e = end; do { if (! em.isMarked(e) || ! fm.isMarked(e)) // are both tests useful ? { const Dart f = this->map.phi1(e); const Dart g = this->map.phi1(f); if (! Geom::isPointInSphere(this->position[f], centerPosition, this->radius)) { this->border.push_back(e); // add to border em.mark(e); fm.mark(e); // is it useful ? } else { if (! vm.isMarked(f)) { this->insideVertices.push_back(f); vm.mark(f); } if (! em.isMarked(e)) { this->insideEdges.push_back(e); em.mark(e); } if (! fm.isMarked(e) && Geom::isPointInSphere(this->position[g], centerPosition, this->radius)) { this->insideFaces.push_back(e); fm.mark(e); } } } e = this->map.phi2_1(e); } while (e != end); ++i; } } template void Collector_WithinSphere::collectBorder(Dart d) { typedef typename PFP::VEC3 VEC3; typedef typename PFP::REAL REAL; this->init(d); this->border.reserve(128); this->insideVertices.reserve(128); CellMarkerStore vm(this->map); // mark the collected inside-vertices CellMarkerStore em(this->map); // mark the collected inside-edges + border-edges this->insideVertices.push_back(this->centerDart); vm.mark(this->centerDart); VEC3 centerPosition = this->position[d]; unsigned int i = 0; while (i < this->insideVertices.size()) { Dart end = this->insideVertices[i]; Dart e = end; do { if ( ! em.isMarked(e) ) { const Dart f = this->map.phi1(e); if (! Geom::isPointInSphere(this->position[f], centerPosition, this->radius)) { this->border.push_back(e); // add to border } else { if (! vm.isMarked(f)) { this->insideVertices.push_back(f); vm.mark(f); } } em.mark(e); } e = this->map.phi2_1(e); } while (e != end); ++i; } this->insideVertices.clear(); } template void Collector_WithinSphere::computeArea() { area = 0; typename PFP::VEC3 centerPosition = this->position[this->centerDart]; for (std::vector::const_iterator it = this->insideFaces.begin(); it != this->insideFaces.end(); ++it) area += Algo::Geometry::triangleArea(this->map, *it, this->position); for (std::vector::const_iterator it = this->border.begin(); it != this->border.end(); ++it) { const Dart f = this->map.phi1(*it); // we know that f is outside const Dart g = this->map.phi1(f); if (Geom::isPointInSphere(this->position[g], centerPosition, this->radius)) { // only f is outside typename PFP::REAL alpha, beta; Algo::Geometry::intersectionSphereEdge(this->map, centerPosition, this->radius, *it, this->position, alpha); Algo::Geometry::intersectionSphereEdge(this->map, centerPosition, this->radius, this->map.phi2(f), this->position, beta); area += (alpha+beta - alpha*beta) * Algo::Geometry::triangleArea(this->map, *it, this->position); } else { // f and g are outside typename PFP::REAL alpha, beta; Algo::Geometry::intersectionSphereEdge(this->map, centerPosition, this->radius, *it, this->position, alpha); Algo::Geometry::intersectionSphereEdge(this->map, centerPosition, this->radius, this->map.phi2(g), this->position, beta); area += alpha * beta * Algo::Geometry::triangleArea(this->map, *it, this->position); } } } /********************************************************* * Collector Normal Angle (Vertices) *********************************************************/ template void Collector_NormalAngle::collectAll(Dart d) { typedef typename PFP::VEC3 VEC3; typedef typename PFP::REAL REAL; this->init(d); this->insideEdges.reserve(32); this->insideFaces.reserve(32); this->border.reserve(32); CellMarkerStore vm(this->map); // mark the collected inside-vertices CellMarkerStore em(this->map); // mark the collected inside-edges + border-edges CellMarkerStore fm(this->map); // mark the collected inside-faces + border-faces this->insideVertices.push_back(this->centerDart); vm.mark(this->centerDart); VEC3 centerNormal = this->normal[d]; unsigned int i = 0; while (i < this->insideVertices.size()) { Dart end = this->insideVertices[i]; Dart e = end; do { if (! em.isMarked(e) || ! fm.isMarked(e)) // are both tests useful ? { const Dart f = this->map.phi1(e); const Dart g = this->map.phi1(f); REAL a = Geom::angle(centerNormal, this->normal[f]); if (a > angleThreshold) { this->border.push_back(e); // add to border em.mark(e); fm.mark(e); // is it useful ? } else { if (! vm.isMarked(f)) { this->insideVertices.push_back(f); vm.mark(f); } if (! em.isMarked(e)) { this->insideEdges.push_back(e); em.mark(e); } REAL b = Geom::angle(centerNormal, this->normal[g]); if (! fm.isMarked(e) && b < angleThreshold) { this->insideFaces.push_back(e); fm.mark(e); } } } e = this->map.phi2_1(e); } while (e != end); ++i; } } template void Collector_NormalAngle::collectBorder(Dart d) { typedef typename PFP::VEC3 VEC3; typedef typename PFP::REAL REAL; this->init(d); this->border.reserve(128); this->insideVertices.reserve(128); CellMarkerStore vm(this->map); // mark the collected inside-vertices CellMarkerStore em(this->map); // mark the collected inside-edges + border-edges this->insideVertices.push_back(this->centerDart); vm.mark(this->centerDart); VEC3 centerNormal = this->normal[d]; unsigned int i = 0; while (i < this->insideVertices.size()) { Dart end = this->insideVertices[i]; Dart e = end; do { if ( ! em.isMarked(e) ) { const Dart f = this->map.phi1(e); REAL a = Geom::angle(centerNormal, this->normal[f]); if (a > angleThreshold) { this->border.push_back(e); // add to border } else { if (! vm.isMarked(f)) { this->insideVertices.push_back(f); vm.mark(f); } } em.mark(e); } e = this->map.phi2_1(e); } while (e != end); ++i; } this->insideVertices.clear(); } /********************************************************* * Collector Normal Angle (Triangles) *********************************************************/ template void Collector_NormalAngle_Triangles::collectAll(Dart d) { typedef typename PFP::VEC3 VEC3; typedef typename PFP::REAL REAL; this->init(d); this->insideVertices.reserve(32); this->insideEdges.reserve(32); this->insideFaces.reserve(32); this->border.reserve(32); CellMarkerStore fm(this->map); // mark the collected inside-faces + front-faces CellMarkerStore fminside(this->map); // mark the collected inside-faces std::queue front; front.push(this->centerDart); fm.mark(this->centerDart); VEC3 centerNormal = this->normal[this->centerDart]; while ( !front.empty() ) // collect inside faces { Dart f = front.front(); front.pop(); REAL a = Geom::angle(centerNormal, this->normal[f]); if (a < angleThreshold ) { // collect this face and add adjacent faces to the front this->insideFaces.push_back(f); fminside.mark(f); Traversor2FFaE t (this->map, f) ; for (Dart it = t.begin(); it != t.end(); it=t.next()) { if (!fm.isMarked(it)) { front.push(it); fm.mark(it); } } } } CellMarkerStore vm(this->map); // mark inside-vertices and border-vertices CellMarkerStore em(this->map); // mark inside-edges and border-edges std::vector::iterator f_it; for (f_it = this->insideFaces.begin(); f_it != this->insideFaces.end(); f_it++) { // collect insideVertices, insideEdges, and border Traversor2FE te (this->map, *f_it) ; for (Dart it = te.begin(); it != te.end(); it=te.next()) { // collect insideEdges and border if (!em.isMarked(it)) { em.mark(it); if (this->map.isBoundaryEdge(it)) this->border.push_back(it); else if ( fminside.isMarked(it) && fminside.isMarked(this->map.phi2(it)) ) this->insideEdges.push_back(it); else this->border.push_back(it); } } Traversor2FV tv (this->map, *f_it) ; for (Dart it = tv.begin(); it != tv.end(); it=tv.next()) { // collect insideVertices if (!vm.isMarked(it)) { vm.mark(it); if ( !this->map.isBoundaryVertex(it)) { Traversor2VF tf (this->map, it); Dart it2 = tf.begin(); while ( (it2 != tf.end()) && fminside.isMarked(it2)) it2=tf.next(); if (it2 == tf.end()) this->insideVertices.push_back(it); } } } } } template void Collector_NormalAngle_Triangles::collectBorder(Dart d) { typedef typename PFP::VEC3 VEC3; typedef typename PFP::REAL REAL; this->init(d); this->insideFaces.reserve(32); this->border.reserve(32); CellMarkerStore fm(this->map); // mark the collected inside-faces + front-faces CellMarkerStore fminside(this->map); // mark the collected inside-faces std::queue front; front.push(this->centerDart); fm.mark(this->centerDart); VEC3 centerNormal = this->normal[this->centerDart]; while ( !front.empty() ) // collect inside faces { Dart f = front.front(); front.pop(); REAL a = Geom::angle(centerNormal, this->normal[f]); if (a < angleThreshold ) { // collect this face and add adjacent faces to the front this->insideFaces.push_back(f); fminside.mark(f); Traversor2FFaE t (this->map, f) ; for (Dart it = t.begin(); it != t.end(); it=t.next()) { if (!fm.isMarked(it)) { front.push(it); fm.mark(it); } } } } CellMarkerStore em(this->map); // mark inside-edges and border-edges std::vector::iterator f_it; for (f_it = this->insideFaces.begin(); f_it != this->insideFaces.end(); f_it++) { // collect border (edges) Traversor2FE te (this->map, *f_it) ; for (Dart it = te.begin(); it != te.end(); it=te.next()) { if (!em.isMarked(it)) { em.mark(it); if (this->map.isBoundaryEdge(it)) this->border.push_back(it); else if ( !fminside.isMarked(it) || !fminside.isMarked(this->map.phi2(it)) ) this->border.push_back(it); } } } this->insideFaces.clear(); } /********************************************************* * Collector Dijkstra *********************************************************/ template void Collector_Dijkstra::collectAll(Dart dinit){ init(dinit); CellMarkerStore vmReached (this->map); vertexInfo[this->centerDart].it = front.insert(std::pair(0.0, this->centerDart)); vertexInfo[this->centerDart].valid = true; vmReached.mark(this->centerDart); while ( !front.empty() && front.begin()->first < this->maxDist) { Dart e = front.begin()->second; float d = front.begin()->first; front.erase(vertexInfo[e].it); vertexInfo[e].valid=false; this->insideVertices.push_back(e); Traversor2VVaE tv (this->map, e); for (Dart f = tv.begin(); f != tv.end(); f=tv.next()) { VertexInfo& vi (vertexInfo[f]); if (vmReached.isMarked(f)) { if (vi.valid) // probably useless but faster { float dist = d + edgeLength(f); if (dist < vi.it->first) { front.erase(vi.it); vi.it = front.insert(std::pair(dist, f)); } } } else { vi.it = front.insert(std::pair(d + edgeLength(f), f)); vi.valid=true; vmReached.mark(f); } } } } template void Collector_Dijkstra::collectBorder(Dart d){ } template inline float Collector_Dijkstra::edgeLength (Dart d){ typename PFP::VEC3 v = Algo::Geometry::vectorOutOfDart(this->map, d, this->position); return v.norm(); } } // namespace Selection } // namespace Algo } // namespace CGoGN