ButterflySubdivision.cpp

Go to the documentation of this file.

#include "Subdiv/ButterflySubdivision.h"

#include "mesh/meshGroup.h"
#include "mesh/indexVertex.h"

ButterflySubdivision::ButterflySubdivision(double w) {

  weight = w;

}

/*****
 * getOpposingVertex(gmVector3&, gmVector3&, indexFace*, indexEdge*, int)
 *
 * returns info for the far vertex on the opposing face of this edge
 */
int ButterflySubdivision::getOpposingVertexInfo(gmVector3 &vertex,
                                                gmVector3 &normal,
                                                indexEdge* edge, 
                                                indexFace* face,
                                                U32 i) {

  if (edge->getNumberOfAdjFaces() == 2) {

    indexFace other_face;

    // don't grab the same face!
    if(face->getIndex() != edge->getFaceIndex(0)) {
      other_face = edge->getFace(0);
    } else {
      other_face = edge->getFace(1);
    }

    if (other_face.getVertexCount() != 3) {
      throw Nexception("ButterflySubdivision: requires triangular mesh!");
    }

    for(int j=0; j < 3; j++) {
      if (edge->getVertexA() != other_face.getVertex(j) &&
          edge->getVertexB() != other_face.getVertex(j)) {

        vertex = other_face.getVertex(j);
        normal = other_face.getNormal(j);
        return 1;

      }
    }

  }

  return 0;

} // end getOpposingVertex


/*****
 * divideEdge(indexEdge*, indexFace*, int)
 *
 * Returns a vertex which subdivides this edge using the standard scheme
 */
void ButterflySubdivision::divideEdge(gmVector3& vertex,
                                      gmVector3& normal,
                                      indexEdge* edge, 
                                      indexFace* face, 
                                      U32 i) {
  gmVector3 a,b,c,d,e,f,g,h;
  gmVector3 na,nb,nc,nd,ne,nf,ng,nh;

  bool valid_stencil = true;

  /* c---d---e
   *  \ / \ /
   *   a-->b
   *  / \ / \
   * f---g---h
   */

  a = edge->getVertexA(); na = edge->getNormalA();
  b = edge->getVertexB(); nb = edge->getNormalB();

  g = face->getVertex((i+2)%3); ng = face->getNormal((i+2)%3);
 
  if (!getOpposingVertexInfo(h, nh, &(face->getEdge((i+1)%3)), face, (i+1)%3))
    valid_stencil = false;
    
  if (!getOpposingVertexInfo(f, nf, &(face->getEdge((i+2)%3)), face, (i+2)%3))
    valid_stencil = false;
  
  // Now, move to the top
  
  getOpposingVertexInfo(d, nd, edge, face, i);

  if (edge->getNumberOfAdjFaces() == 2) {

    indexFace* top_face;

    if (face->getIndex() != edge->getFaceIndex(0)) {
      top_face = &(edge->getFace(0));
    } else {
      top_face = &(edge->getFace(1));
    }

    if (top_face->getVertexCount() != 3) {
      throw Nexception("ButterflySubdivision: requires triangular mesh!");
    }

    for(int k=0; k < 3; k++) {

      if ((edge->getVertexA() == top_face->getEdge(k).getVertexA()) &&
          (edge->getVertexB() == top_face->getEdge(k).getVertexB())) {

        if(!getOpposingVertexInfo(e, ne, &(top_face->getEdge((k+1)%3)), 
                              top_face, (k+1)%3))
          valid_stencil = false;

        if(!getOpposingVertexInfo(c, nc, &(top_face->getEdge((k+2)%3)), 
                              top_face, (k+2)%3))
          valid_stencil = false;

      } else if ((edge->getVertexA() == top_face->getEdge(k).getVertexB()) &&
                 (edge->getVertexB() == top_face->getEdge(k).getVertexA())) {

        if(!getOpposingVertexInfo(c, nc, &(top_face->getEdge((k+1)%3)), 
                              top_face, (k+1)%3))
          valid_stencil = false;

        if(!getOpposingVertexInfo(e, ne, &(top_face->getEdge((k+2)%3)), 
                              top_face, (k+2)%3))
          valid_stencil = false;

      }                                                                  

    } // end loop

  } else {
    
    valid_stencil = false;

  }

  // Now, all the vertices should be ready

  if (valid_stencil) {
    
    vertex =
      (a + b)*0.5 + 
      (d + g)*(0.125 + 2.0*weight) - 
      (c + e + f + h)*(0.0625 - weight);

    normal =
      (na + nb)*0.5 +
      (nd + ng)*(0.125 + 2.0*weight) -
      (nc + ne + nf + nh)*(0.0625 - weight);

  } else {
    
    vertex = (a + b)*0.5;
    normal = (na + nb)*0.5;

  }

}

/*****
 * divideFace(indexFace*, Mesh*)
 *
 * Subdivides a single face
 */
void ButterflySubdivision::divideFace(indexFace* face, Mesh* m) {

  gmVector3 vertex;
  gmVector3 normal;

  for (U32 i=0; i < 3; i++) {

    indexEdge &edge = face->getEdge(i);

    if(!edge.hasArbitraryIndex()) {

      divideEdge(vertex, normal, &edge, face, i);
      edge.setArbitraryIndex(m->addVertex(vertex));
      indexVertex &v = m->getIndexVertex(edge.getArbitraryIndex());
      v.setNormalIndex(m->addNormal(normal));

    }

  }

} // end divideFace

/*****
 * subdivide (Mesh*, U32)
 *
 * Does one subdivision step on the entire mesh level defined by base
 */
void ButterflySubdivision::subdivide(Mesh* m, U32 base) {

  U32 group;
  group = m->addGroup();

  // Extract the group (level) to be subdivided
  MeshGroup &base_mesh = m->getGroup(base);

  // Loop through faces to subdivide
  base_mesh.rewindFaceList();
  while (indexFace *face = base_mesh.facePostIncrement()) {

    U32 edge_count = face->getEdgeCount();

    // Assuming triangular mesh
    if (edge_count != 3) {
      throw Nexception("ButterflySubdivision: requires triangular mesh!");
    } 

    divideFace(face, m);

  } // end while

  // Loop through faces to compose new mesh
  base_mesh.rewindFaceList();
  while(U32 *findex = base_mesh.faceIndexPostIncrement()) {

    indexFace* face = &m->getFace(*findex);

    U32 new_vertices[3];
    U32 old_vertices[3];
    U32 new_normals[3];
    U32 old_normals[3];

    // Get "old" vertices
    U32 vertex_count = face->getVertexCount();
        U32 i; // VC++ wants declarator in only the first for loop
    for (i=0; i < vertex_count; i++) {

      old_vertices[i] = face->getVertexIndex(i);
      old_normals[i] = face->getNormalIndex(i);

    }

    // Get new vertices
    U32 edge_count = face->getEdgeCount();
    for(i=0; i < edge_count; i++) {

      indexEdge &edge = face->getEdge(i);
      new_vertices[i] = edge.getArbitraryIndex();
      new_normals[i] = m->getIndexVertex(edge.getArbitraryIndex()).getNormalIndex();
      
    }      

    // Stich 'em in

    indexFace face0;
    face0.addVertex(old_vertices[0], old_normals[0]);
    face0.addVertex(new_vertices[0], new_normals[0]);
    face0.addVertex(new_vertices[2], new_normals[2]);

    indexFace face1;
    face1.addVertex(old_vertices[1], old_normals[1]);
    face1.addVertex(new_vertices[1], new_normals[1]);
    face1.addVertex(new_vertices[0], new_normals[0]);

    indexFace face2;
    face2.addVertex(old_vertices[2], old_normals[2]);
    face2.addVertex(new_vertices[2], new_normals[2]);
    face2.addVertex(new_vertices[1], new_normals[1]);

    indexFace face3;
    face3.addVertex(new_vertices[0], new_normals[0]);
    face3.addVertex(new_vertices[1], new_normals[1]);
    face3.addVertex(new_vertices[2], new_normals[2]);
    
    m->addFace(face0);
    m->addFace(face1);
    m->addFace(face2);
    m->addFace(face3);

  } // end while

} // end subdivide

/*****
 * compute(int)
 *
 * Computes subdivision to the nth level from the base
 */
void ButterflySubdivision::compute(int n) {

  U32 base=0;

  // Step through the levels currently in the mesh
  m_mesh.rewindGroupList();
  while (m_mesh.groupPostIncrement()) base++;

  // Subdivide until desired level is reached
  for(U32 i=base; i<n; i++) {

    // Subdivide the mesh using level i as the base for one step
    subdivide(&m_mesh, i);

  }

} // end compute

---