1 #include "adjacency_list/graph.h" 2 #include <stdlib.h> 3 4 #ifndef GRAPHBUILDER_H 5 #define GRAPHBUILDER_H 6 7 namespace vcg { 8 namespace tri { 9 10 //the class is templated also on the FunctorType, that is used to compute edge weights 11 //so the dual graph can be built assigning other weight values. 12 template<class MeshType, class FunctorType> 13 class GraphBuilder 14 { 15 public: 16 typedef typename MeshType::VertexType VertexType; 17 typedef typename MeshType::VertexPointer VertexPointer; 18 typedef typename MeshType::FaceType FaceType; 19 typedef typename MeshType::FacePointer FacePointer; 20 typedef typename MeshType::EdgePointer EdgePointer; 21 typedef typename MeshType::VertexIterator VertexIterator; 22 typedef typename MeshType::FaceIterator FaceIterator; 23 typedef typename MeshType::CoordType Point3f; 24 typedef typename MeshType::ScalarType ScalarType; 25 typedef typename face::Pos<FaceType> PosType; 26 27 /*main function to be called from outside: builds the graph and fires the maxflow/mincut alogrith*/ Compute(MeshType & m,FunctorType & wf,FacePointer startFace,FacePointer endFace)28 static void Compute(MeshType &m, FunctorType &wf, FacePointer startFace, FacePointer endFace) 29 { 30 assert(startFace!=NULL && endFace!=NULL && !startFace->IsD() && !endFace->IsD()); 31 Graph *g = GraphBuilder<MeshType, FunctorType>::BuildGraph(m, wf, startFace, endFace); 32 double flowVal = g->maxflow(); 33 qDebug("Flow %f",flowVal); 34 GraphBuilder<MeshType, FunctorType>::ColorFaces(m, *g, startFace, endFace); 35 assert(vcg::tri::HasPerFaceAttribute(m,"NodeID")); 36 vcg::tri::Allocator<MeshType>::DeletePerFaceAttribute(m,"NodeID"); 37 delete g; 38 } 39 40 /* Builds the dual graph. 41 * the startFace will be connected to the source 42 * the endFace will be connected to the sink 43 * wf is used to compute edge weights 44 */ BuildGraph(MeshType & m,FunctorType & wf,FacePointer startFace,FacePointer endFace)45 static Graph * BuildGraph(MeshType &m, FunctorType &wf, FacePointer startFace, FacePointer endFace) 46 { 47 vcg::tri::UpdateFlags<MeshType>::FaceClearV(m); 48 tri::Allocator<MeshType>::CompactEveryVector(m); 49 Graph *g = new Graph(); 50 std::vector<FacePointer> faceVec; 51 52 //use a per-face attribute to keep the face-node mapping 53 //and initialize to NULL 54 typename MeshType::template PerFaceAttributeHandle <Graph::node_id> nfH 55 = tri::Allocator<MeshType>::template AddPerFaceAttribute<Graph::node_id>(m, std::string("NodeID")); 56 for(FaceIterator fit = m.face.begin(); fit!=m.face.end(); fit++) 57 nfH[fit] = NULL; 58 /* 59 * Surf the mesh face by face and build the graph 60 * using FF adiacency and marking a face when visiting it 61 * Start adding nodes to the graph: 62 * link upper face to the source 63 * link lower face to the sink 64 */ 65 nfH[startFace] = g->add_node(); 66 g->set_tweights(nfH[startFace], std::numeric_limits<ScalarType>::max(), 0); 67 //link lower face to the sink 68 nfH[endFace] = g->add_node(); 69 g->set_tweights(nfH[endFace], 0, std::numeric_limits<ScalarType>::max()); 70 faceVec.push_back(endFace); 71 //push startFace in the vector: begin visiting the mesh from there 72 faceVec.push_back(startFace); 73 startFace->SetV(); 74 75 //add a node for each face 76 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) 77 { 78 if(nfH[fi] == NULL) 79 nfH[fi] = g->add_node(); 80 } 81 82 //add edges 83 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) 84 { 85 for (int i=0; i<3; i++) 86 { 87 if(!face::IsBorder(*fi,i)) 88 { 89 PosType pf(&*fi, i); 90 //using the functor operator () to compute edge capability 91 double cap = wf(pf); 92 assert(cap>=0); 93 //add edges (in the dual graph) between adjacent faces 94 //an edge is added in both directions with "cap" and "rev_cap"=0 flow capacities 95 g->add_edge(nfH[fi], nfH[fi->FFp(i)], cap, 0); 96 } 97 } 98 } 99 return g; 100 } 101 102 /* 103 Red-coloring Source faces and 104 Green-coloring Sink faces 105 */ ColorFaces(MeshType & m,Graph & g,FacePointer startFace,FacePointer endFace)106 static void ColorFaces(MeshType &m, Graph &g, FacePointer startFace, FacePointer endFace){ 107 108 assert(vcg::tri::HasPerFaceAttribute(m,"NodeID")); 109 110 typename MeshType:: template PerFaceAttributeHandle<Graph::node_id> nfH 111 = vcg::tri::Allocator<MeshType>::template FindPerFaceAttribute<Graph::node_id>(m,"NodeID"); 112 113 for(FaceIterator fit=m.face.begin(); fit!=m.face.end(); fit++) 114 { 115 assert(nfH[fit]!=NULL); 116 if(!fit->IsD()){ 117 if(g.what_segment(nfH[fit]) == Graph::SOURCE){ 118 fit->C()=Color4b::Red; 119 } 120 else if(g.what_segment(nfH[fit]) == Graph::SINK) 121 fit->C()=Color4b::Green; 122 } 123 } 124 } 125 }; 126 127 128 } //end namespace 129 } //end namespace 130 131 132 #endif // GRAPHBUILDER_H 133