MeshKit  1.0
Tri2Quad.hpp
Go to the documentation of this file.
00001 
00002 //            Jaal:: Triangle-to-Quad Transformation Code 
00003 //            ********************************************
00004 //  Description:
00005 //  Given a triangulated mesh, convert into All-Quads or Quad-Dominated Mesh.
00006 //  using Maximum Tree Matching Algorithm.
00007 //
00008 //  Maximum Cardinality using Edmond's Algorithm may give perfect matching
00009 //  but the algorithm is too expensive for large dataset and often perfect
00010 //  matching is not required.
00011 //
00012 //  If the user requires All-Quad Meshing then all the unmatched triangles
00013 //  using Tree Matching Algorithms are split and steiner points are created.
00014 //  In most of the cases, number of Steiner points are less than 5% of the
00015 //  total triangles present in the original mesh.
00016 //
00017 //  Chaman Singh Verma
00018 //  University of Wisconsin Madison, USA,
00019 //  Date: 15th Jan 2010.
00020 //  
00021 //  License: Free to download and modify. 
00022 
00023 //  For more information, please follow the link
00024 //
00025 //  http://pages.cs.wisc.edu/~csverma/CS899_09/JQuad.html
00026 //
00028 
00029 #ifndef Tri2Quad_H
00030 #define Tri2Quad_H
00031 
00032 #include "Mesh.hpp"
00033 #include "DualGraph.hpp"
00034 #include "BinaryTree.hpp"
00035 #include "cycle.hpp"         // performance counter. 
00036 
00037 namespace Jaal {
00038 
00039 class Tri2Quads
00040 {
00041 public:
00042 
00043   const static int ALL_QUADS = 0;
00044   const static int QUAD_DOMINATED = 1;
00045 
00046   static int verify(Mesh *m, const vector<FacePair> &matching);
00047   static Mesh* collapse_matched_triangles(Mesh *mesh, const vector<FacePair> &matching, int replace = 0);
00048 
00049 
00050   Tri2Quads()
00051   {
00052     trimesh = NULL;
00053     btree = NULL;
00054     verbose = 1;
00055     required_topology = ALL_QUADS;
00056   }
00057 
00058   const vector<FacePair> &getMaximumDualMatching();
00059 
00060   Mesh* getQuadMesh(Mesh *tmesh, int replace = 0, int topo = ALL_QUADS);
00061 
00062   NodeSequence getSteinerNodes()  const;
00063   FaceSequence getInsertedFaces() const;
00064   FaceSequence getModifiedFaces() const;
00065 
00066 private:
00067   Mesh *trimesh; // Input mesh.
00068 
00069   struct LVertex : public Vertex
00070   {
00071       LVertex( Vertex *v ) { vertex = v; }
00072       Vertex *vertex;
00073       Vertex  *mate;
00074       Face    *dual;
00075   };
00076 
00077   FaceSequence steinerFaces, modifiedFaces;
00078   NodeSequence steinerNodes;
00079 
00080   BinaryTree *btree;
00081 
00082   int required_topology;
00083   bool verbose;
00084   size_t maxfaceID;
00085 
00086   vector<FacePair> facematching;
00087 
00088   void splitParent(Face *parent, Face *child1, Face *child2);
00089   void splitParent(BinaryNode *p, BinaryNode *c1, BinaryNode *c2);
00090 
00091   int refine_boundary_triangle(Face *face);
00092 
00093   void percolateup();
00094 
00095   void matchnode(BinaryNode *v);
00096   void matchnodes(BinaryNode *child, BinaryNode *parent);
00097   void matchnodes(Vertex *child, Vertex *parent);
00098 
00099   BinaryNode* getChildofDegreeNParent(BNodeList &levelnodes, int nd);
00100 
00101   BinaryNode *getNextNode(BNodeList &levelnodes);
00102   void prunelevel(BNodeList &levelnodes);
00103   void maximum_tree_matching();
00104 
00105   void match_tree_walk(BinaryTree *tree, BinaryNode *u);
00106 };
00107 
00108 bool has_same_dual(const BinaryNode *nd1, const BinaryNode *nd2);
00109 
00110 inline 
00111 bool already_matched(const BinaryNode *node)
00112 {
00113     return node->isMatched();
00114 }
00115 
00116 inline
00117 void Tri2Quads::matchnodes(Vertex *child, Vertex *parent)
00118 {
00119     child->setAttribute("DualMate", parent);
00120     parent->setAttribute("DualMate", child);
00121     child->setStatus(MeshEntity::REMOVE);
00122     parent->setStatus(MeshEntity::REMOVE);
00123 }
00125 
00126 inline 
00127 void Tri2Quads::matchnodes(BinaryNode *child, BinaryNode *parent)
00128 {
00129     if (parent->isMatched() && !child->isMatched())
00130     {
00131         cout << "Warning: parent is already matched " << endl;
00132     }
00133 
00134     if (!child->isMatched() && !parent->isMatched())
00135         matchnodes(child->getDualNode(), parent->getDualNode());
00136 
00137     btree->unlinkNode(child);
00138     btree->unlinkNode(parent);
00139 }
00140 
00141 
00142 } // namespace Jaal
00143 
00144 
00145 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines