1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
////////////////////////////////////////////////////////////////////////////////
//            Jaal:: Triangle-to-Quad Transformation Code 
//            ********************************************
//  Description:
//  Given a triangulated mesh, convert into All-Quads or Quad-Dominated Mesh.
//  using Maximum Tree Matching Algorithm.
//
//  Maximum Cardinality using Edmond's Algorithm may give perfect matching
//  but the algorithm is too expensive for large dataset and often perfect
//  matching is not required.
//
//  If the user requires All-Quad Meshing then all the unmatched triangles
//  using Tree Matching Algorithms are split and steiner points are created.
//  In most of the cases, number of Steiner points are less than 5% of the
//  total triangles present in the original mesh.
//
//  Chaman Singh Verma
//  University of Wisconsin Madison, USA,
//  Date: 15th Jan 2010.
//  
//  License: Free to download and modify. 

//  For more information, please follow the link
//
//  http://pages.cs.wisc.edu/~csverma/CS899_09/JQuad.html
//
////////////////////////////////////////////////////////////////////////////////

#ifndef Tri2Quad_H
#define Tri2Quad_H

#include "meshkit/Mesh.hpp"
#include "meshkit/DualGraph.hpp"
#include "meshkit/BinaryTree.hpp"
#include "meshkit/cycle.hpp"         // performance counter.

namespace Jaal {

class Tri2Quads
{
public:

  const static int ALL_QUADS = 0;
  const static int QUAD_DOMINATED = 1;

  static int verify(Mesh *m, const vector<FacePair> &matching);
  static Mesh* collapse_matched_triangles(Mesh *mesh, const vector<FacePair> &matching, int replace = 0);


  Tri2Quads()<--- Member variable 'Tri2Quads::maxfaceID' is not initialized in the constructor.
  {
    trimesh = NULL;
    btree = NULL;
    verbose = 1;
    required_topology = ALL_QUADS;
  }

  const vector<FacePair> &getMaximumDualMatching();

  Mesh* getQuadMesh(Mesh *tmesh, int replace = 0, int topo = ALL_QUADS);

  NodeSequence getSteinerNodes()  const;
  FaceSequence getInsertedFaces() const;
  FaceSequence getModifiedFaces() const;

private:
  Mesh *trimesh; // Input mesh.

  struct LVertex : public Vertex
  {
      LVertex( Vertex *v ) { vertex = v; }<--- Member variable 'LVertex::mate' is not initialized in the constructor.<--- Member variable 'LVertex::dual' is not initialized in the constructor.
      Vertex *vertex;
      Vertex  *mate;
      Face    *dual;
  };

  FaceSequence steinerFaces, modifiedFaces;
  NodeSequence steinerNodes;

  BinaryTree *btree;

  int required_topology;
  bool verbose;
  size_t maxfaceID;

  vector<FacePair> facematching;

  void splitParent(Face *parent, Face *child1, Face *child2);
  void splitParent(BinaryNode *p, BinaryNode *c1, BinaryNode *c2);

  int refine_boundary_triangle(Face *face);

  void percolateup();

  void matchnode(BinaryNode *v);
  void matchnodes(BinaryNode *child, BinaryNode *parent);
  void matchnodes(Vertex *child, Vertex *parent);

  BinaryNode* getChildofDegreeNParent(BNodeList &levelnodes, int nd);

  BinaryNode *getNextNode(BNodeList &levelnodes);
  void prunelevel(BNodeList &levelnodes);
  void maximum_tree_matching();

  void match_tree_walk(BinaryTree *tree, BinaryNode *u);
};

bool has_same_dual(const BinaryNode *nd1, const BinaryNode *nd2);

inline 
bool already_matched(const BinaryNode *node)
{
    return node->isMatched();
}

inline
void Tri2Quads::matchnodes(Vertex *child, Vertex *parent)
{
    child->setAttribute("DualMate", parent);
    parent->setAttribute("DualMate", child);
    child->setStatus(MeshEntity::REMOVE);
    parent->setStatus(MeshEntity::REMOVE);
}
///////////////////////////////////////////////////////////////////////////////////

inline 
void Tri2Quads::matchnodes(BinaryNode *child, BinaryNode *parent)
{
    if (parent->isMatched() && !child->isMatched())
    {
        cout << "Warning: parent is already matched " << endl;
    }

    if (!child->isMatched() && !parent->isMatched())
        matchnodes(child->getDualNode(), parent->getDualNode());

    btree->unlinkNode(child);
    btree->unlinkNode(parent);
}


} // namespace Jaal


#endif