class HE_Subdivision{

  HE_Mesh divide(final HE_Mesh mesh, int rep){
    return mesh;
  }

  HE_Mesh divide(final HE_Mesh mesh){
    return divide(mesh,1);
  }

}

class CatmullClarkSubdivision extends HE_Subdivision{

  HE_Mesh divide(final HE_Mesh mesh, int rep){  
    HE_Mesh result=mesh.get();
    for(int r=0;r<rep;r++){ 
      if(!result.indicesUpdated) result.reindex();
      if(!result.faceCentersUpdated) result.setFaceCenters();
      ArrayList verticesToAdjust=new ArrayList();
      verticesToAdjust.addAll(result.vertices);

      int n= result.edges.size();
      for(int i=0;i<n;i++){
        HE_Edge origE=(HE_Edge)result.edges.get(i);
        HE_HalfEdge origHE1= origE.halfEdge;
        HE_HalfEdge origHE2= origHE1.pair;
        HE_Vertex v=new HE_Vertex(0,0,0,-1);
        HE_Vertex v1=origHE1.vert;
        HE_Vertex v2=origHE2.vert;
        HE_Vertex v3=(HE_Vertex)result.faceCenters.get(origHE1.face.id);
        HE_Vertex v4=(HE_Vertex)result.faceCenters.get(origHE2.face.id);    
        if(result.isFixed(origE)){
          v.x=0.5f*(v1.x+v2.x);
          v.y=0.5f*(v1.y+v2.y);
          v.z=0.5f*(v1.z+v2.z);
        }
        else{
          v.x=0.25f*(v1.x+v2.x+v3.x+v4.x);
          v.y=0.25f*(v1.y+v2.y+v3.y+v4.y);
          v.z=0.25f*(v1.z+v2.z+v3.z+v4.z);
        }
        result.vertices.add(v);
        HE_Edge newE= new HE_Edge();
        newE.visible=origE.visible;
        result.edges.add(newE);
        HE_HalfEdge newHE1=new HE_HalfEdge();
        result.halfEdges.add(newHE1);
        HE_HalfEdge newHE2=new HE_HalfEdge();
        result.halfEdges.add(newHE2);
        newHE1.vert=v;    
        newHE1.next=origHE1.next;
        newHE1.face=origHE1.face;
        newHE1.pair=origHE2;
        newHE1.edge=newE;
        origHE1.next=newHE1;
        origHE1.pair=newHE2;        
        newHE2.vert=v;
        newHE2.next=origHE2.next;
        newHE2.face=origHE2.face;
        newHE2.pair=origHE1;
        newHE2.edge=origE;
        origHE2.next=newHE2;
        origHE2.pair=newHE1;
        origHE2.edge=newE;
        newE.halfEdge=newHE1;
        v.halfEdge=newHE1;
      }
      int tot=0;
      for(int i=0;i<verticesToAdjust.size();i++){
        HE_Vertex P=(HE_Vertex)verticesToAdjust.get(i);
        if(!result.isFixed(P)){
          int N=0;
          float Fx=0;
          float Fy=0;
          float Fz=0;
          float Rx=0;
          float Ry=0;
          float Rz=0;
          HE_HalfEdge he=P.halfEdge;
          do{
            HE_Face face=he.face;
            HE_Vertex fv=(HE_Vertex)result.faceCenters.get(he.face.id);
            Fx+=fv.x;
            Fy+=fv.y;
            Fz+=fv.z;
            N++;
            HE_Vertex ev1=he.vert;
            HE_Vertex ev2=he.pair.vert;
            Rx+=0.5f*(ev1.x+ev2.x);
            Ry+=0.5f*(ev1.y+ev2.y);
            Rz+=0.5f*(ev1.z+ev2.z);
            he=he.pair;
            he=he.next;
          }
          while(he!=P.halfEdge);
          P.x=(Fx/N+2*Rx/N+(N-3)*P.x)/N;
          P.y=(Fy/N+2*Ry/N+(N-3)*P.y)/N;
          P.z=(Fz/N+2*Rz/N+(N-3)*P.z)/N;
        }
      }
      ArrayList newFaces=new ArrayList();
      for(int i=0;i<result.faces.size();i++){
        HE_Face face=(HE_Face)result.faces.get(i);
        HE_HalfEdge startHE = face.halfEdge;
        while(startHE.vert.id!=-1) startHE=startHE.next;
        HE_HalfEdge origHE1=startHE;
        do{
          HE_Face newFace=new HE_Face();       
          newFace.visible=face.visible;
          newFaces.add(newFace);
          newFace.fixed=face.fixed;
          newFace.halfEdge=origHE1;
          HE_HalfEdge origHE2=origHE1.next;
          HE_HalfEdge origHE3=origHE2.next;
          HE_HalfEdge newHE1=new HE_HalfEdge();
          HE_HalfEdge newHE2=new HE_HalfEdge();    
          result.halfEdges.add(newHE1);
          result.halfEdges.add(newHE2);
          origHE2.next=newHE1;
          newHE1.next=newHE2;
          newHE2.next=origHE1;
          newHE1.vert=origHE3.vert;
          HE_Vertex fv=(HE_Vertex)result.faceCenters.get(origHE1.face.id);
          newHE2.vert=fv;
          if(fv.halfEdge==null) fv.halfEdge=newHE2;
          newHE1.face=newFace;
          newHE2.face=newFace;
          origHE1.face=newFace;
          origHE2.face=newFace;
          origHE1=origHE3;
        }
        while(origHE1!=startHE);
      }
      result.pairHalfEdges();
      result.faces=newFaces;
      result.vertices.addAll(result.faceCenters);  
      result.clearSecondaries();

    }
    return result; 

  }  

}

class DooSabinSubdivision extends HE_Subdivision{
  float f;

  DooSabinSubdivision(){
    f=0.5f; 
  }

  DooSabinSubdivision(float ff){
    f=ff; 
  }

  HE_Mesh divide(final HE_Mesh mesh){    
    HE_Mesh result=new HE_Mesh();
    float locf=1-f;

    if(!mesh.faceCentersUpdated)mesh.setFaceCenters();    
    HE_Mesh tracker=mesh.get();
    //create inner vertices
    for(int i=0;i<mesh.faces.size();i++){
      HE_Face origF=(HE_Face)mesh.faces.get(i);
      HE_Face trackF=(HE_Face)tracker.faces.get(i);
      PVector fc=(PVector)mesh.faceCenters.get(i);
      HE_HalfEdge origHe=origF.halfEdge; 
      HE_HalfEdge trackHe=trackF.halfEdge; 
      do{
        HE_Vertex vo=origHe.vert;
        HE_Vertex vn=new HE_Vertex(fc.x+locf*(vo.x-fc.x),fc.y+locf*(vo.y-fc.y),fc.z+locf*(vo.z-fc.z),-1);  
        if(!result.vertices.contains(vn))result.vertices.add(vn);
        trackHe.vert=vn;
        origHe=origHe.next;
        trackHe=trackHe.next;       
      }
      while(origHe!=origF.halfEdge); 
    }
    
    for(int i=0;i<mesh.faces.size();i++){
      HE_Face trackF=(HE_Face)tracker.faces.get(i); 
      HE_HalfEdge trackHe=trackF.halfEdge; 
      HE_Face nf=new HE_Face();
      result.faces.add(nf);
      nf.visible=trackF.visible;
      nf.fixed=trackF.fixed;
      ArrayList newHalfEdges=new ArrayList();
      do{
        HE_Vertex v=trackHe.vert;
        HE_HalfEdge he=new HE_HalfEdge();
        newHalfEdges.add(he);
        he.vert=v;
        he.face=nf;
        if(nf.halfEdge==null) nf.halfEdge=he;
        trackHe=trackHe.next;       
      }
      while(trackHe!=trackF.halfEdge); 
      result.cycleHalfEdges(newHalfEdges,false);
      result.halfEdges.addAll(newHalfEdges);  
    }     
    for(int i=0;i<mesh.vertices.size();i++){
      HE_Vertex trackV=(HE_Vertex)tracker.vertices.get(i);
      HE_HalfEdge trackHe=trackV.halfEdge; 
      HE_Face nf=new HE_Face();
      result.faces.add(nf);
      nf.visible=true;
      nf.fixed=mesh.isFixed(trackV); 
      ArrayList newHalfEdges=new ArrayList();
      do{
        HE_Vertex v=trackHe.vert;
        HE_HalfEdge he=new HE_HalfEdge();
        newHalfEdges.add(he);
        he.vert=v;
        he.face=nf;      
        if(nf.halfEdge==null) nf.halfEdge=he;
        if(v.halfEdge==null) v.halfEdge=he;
        trackHe=trackHe.pair.next;       
      }
      while(trackHe!=trackV.halfEdge); 
      result.cycleHalfEdges(newHalfEdges,true);
      result.halfEdges.addAll(newHalfEdges);    
    }
    for(int i=0;i<mesh.edges.size();i++){
      HE_Edge trackE=(HE_Edge)tracker.edges.get(i);
      HE_HalfEdge trackHe1=trackE.halfEdge; 
      HE_HalfEdge trackHe2=trackE.halfEdge.pair; 
      HE_Face nf=new HE_Face();
      result.faces.add(nf);
      nf.visible=true;
      nf.fixed=mesh.isFixed(trackE); 
      HE_Vertex v4=trackHe1.vert;
      HE_Vertex v3=trackHe1.next.vert;
      HE_Vertex v2=trackHe2.vert;
      HE_Vertex v1=trackHe2.next.vert;
      HE_HalfEdge he1=new HE_HalfEdge();
      HE_HalfEdge he2=new HE_HalfEdge();
      HE_HalfEdge he3=new HE_HalfEdge();
      HE_HalfEdge he4=new HE_HalfEdge();
      nf.halfEdge=he1;
      he1.vert=v1;
      he1.face=nf;
      he1.next=he2;
      he2.vert=v2;
      he2.face=nf;
      he2.next=he3;
      he3.vert=v3;
      he3.face=nf;
      he3.next=he4;
      he4.vert=v4;
      he4.face=nf;
      he4.next=he1;
      result.halfEdges.add(he1);
      result.halfEdges.add(he2);
      result.halfEdges.add(he3);
      result.halfEdges.add(he4);
    }
    result.pairHalfEdges();
    for(int i=0;i<result.edges.size();i++){
      HE_Edge e=(HE_Edge)result.edges.get(i);
      if((e.halfEdge.face.visible)||(e.halfEdge.pair.face.visible)) e.visible=true;     
    }
    result.clearSecondaries();
    return result;  
  } 

  HE_Mesh divide(final HE_Mesh mesh, int rep){
    if(rep<1){
      return mesh.get();
    }
    else if(rep==1)
    {
      return divide(mesh); 
    }
    else{
      HE_Mesh result=divide(mesh);
      for(int i=1;i<rep;i++){
        result=divide(result); 
      }
      return result;
    }


  }

}


class LoopSubdivision extends HE_Subdivision{
  int type;

  LoopSubdivision(){
    type=0; 
  }

  LoopSubdivision(int tt){
    type=tt; 
  }

  HE_Mesh divide(HE_Mesh mesh ,int rep){
HE_Mesh result=mesh.get();
    for(int r=0;r<rep;r++){
      int origVertices=mesh.vertices.size();
      
      switch(type){
      case 0:
        PlanarQuadTriSubdivision subdiv0=new PlanarQuadTriSubdivision();
        result.subdivideSelf(subdiv0);
        break;
      case 1:
        PlanarQuadSubdivision subdiv1=new PlanarQuadSubdivision();
        result.subdivideSelf(subdiv1);
        break;
      case 2:
        PlanarMidEdgeSubdivision subdiv2=new PlanarMidEdgeSubdivision();
        result.subdivideSelf(subdiv2);
        break;
      case 3:
        PlanarMidFaceSubdivision subdiv3=new PlanarMidFaceSubdivision();
        result.subdivideSelf(subdiv3);
        break;
      default:
        PlanarQuadTriSubdivision subdivd=new PlanarQuadTriSubdivision();
        result.subdivideSelf(subdivd);
        break;

      }

      if(!result.indicesUpdated) result.reindex();
      PVector[] newPositions=new PVector[result.vertices.size()];
      for(int i=0;i<result.vertices.size();i++){
        newPositions[i]=new PVector();

      }

      for(int i=0;i<result.vertices.size();i++){
        HE_Vertex v=(HE_Vertex)result.vertices.get(i);
        HE_HalfEdge he=v.halfEdge;
        int c=0;
        do{
          HE_HalfEdge hen=he.next;
          newPositions[i].add(hen.vert);
          c++;
          he=he.pair.next;
        }

        while(he!=v.halfEdge);
        float beta=1.25f-sq(3f+2f*cos(TWO_PI/c))/32f;
        float alfa=c*(1f-beta)/beta;  
        newPositions[i].add(PVector.mult(v,alfa));
        newPositions[i].div(c+alfa);
      }  
      for(int i=0;i<result.vertices.size();i++){
        HE_Vertex v=(HE_Vertex)result.vertices.get(i);
        v.set(newPositions[i]);

      } 
      result.clearSecondaries();  
    }
    return result;

  }
}
class PlanarQuadSubdivision extends HE_Subdivision{
  HE_Mesh divide(final HE_Mesh mesh, int rep){
    HE_Mesh result=mesh.get(); 
    for(int r=0;r<rep;r++){
      if(!result.indicesUpdated) result.reindex();
      if(!result.faceCentersUpdated) result.setFaceCenters();
      int n= result.edges.size();
      for(int i=0;i<n;i++){
        HE_Edge origE=(HE_Edge)result.edges.get(i);
        HE_HalfEdge origHE1= origE.halfEdge;
        HE_HalfEdge origHE2= origHE1.pair;
        HE_Vertex v=new HE_Vertex(0,0,0,-1);
        HE_Vertex v1=origHE1.vert;
        HE_Vertex v2=origHE2.vert;
        v.x=0.5*(v1.x+v2.x);
        v.y=0.5*(v1.y+v2.y);
        v.z=0.5*(v1.z+v2.z);
        result.vertices.add(v);
        HE_Edge newE= new HE_Edge();
        newE.visible=origE.visible;
        result.edges.add(newE);
        HE_HalfEdge newHE1=new HE_HalfEdge();
        result.halfEdges.add(newHE1);
        HE_HalfEdge newHE2=new HE_HalfEdge();
        result.halfEdges.add(newHE2);
        newHE1.vert=v;    
        newHE1.next=origHE1.next;
        newHE1.face=origHE1.face;
        newHE1.pair=origHE2;
        newHE1.edge=newE;
        origHE1.next=newHE1;
        origHE1.pair=newHE2;        
        newHE2.vert=v;
        newHE2.next=origHE2.next;
        newHE2.face=origHE2.face;
        newHE2.pair=origHE1;
        newHE2.edge=origE;
        origHE2.next=newHE2;
        origHE2.pair=newHE1;
        origHE2.edge=newE;
        newE.halfEdge=newHE1;
        v.halfEdge=newHE1;
      }
      ArrayList newFaces=new ArrayList();
      for(int i=0;i<result.faces.size();i++){
        HE_Face face=(HE_Face)result.faces.get(i);
        HE_HalfEdge startHE = face.halfEdge;
        while(startHE.vert.id!=-1) startHE=startHE.next;
        HE_HalfEdge origHE1=startHE;
        do{
          HE_Face newFace=new HE_Face();
          newFace.visible=face.visible;       
          newFaces.add(newFace);
          newFace.halfEdge=origHE1;
          HE_HalfEdge origHE2=origHE1.next;
          HE_HalfEdge origHE3=origHE2.next;
          HE_HalfEdge newHE1=new HE_HalfEdge();
          HE_HalfEdge newHE2=new HE_HalfEdge();    
          result.halfEdges.add(newHE1);
          result.halfEdges.add(newHE2);
          origHE2.next=newHE1;
          newHE1.next=newHE2;
          newHE2.next=origHE1;
          newHE1.vert=origHE3.vert;
          HE_Vertex fv=(HE_Vertex)result.faceCenters.get(origHE1.face.id);
          newHE2.vert=fv;
          if(fv.halfEdge==null) fv.halfEdge=newHE2;
          newHE1.face=newFace;
          newHE2.face=newFace;
          origHE1.face=newFace;
          origHE2.face=newFace;
          origHE1=origHE3;
        }
        while(origHE1!=startHE);
      }
      result.pairHalfEdges();
      result.faces=newFaces;
      result.vertices.addAll(result.faceCenters);
      result.clearSecondaries();
    }
    return result;
  }

}

class PlanarMidEdgeSubdivision extends HE_Subdivision{
  HE_Mesh divide(final HE_Mesh mesh,int rep){
    HE_Mesh result=mesh.get();
    for(int r=0;r<rep;r++){
      if(!result.indicesUpdated) result.reindex();
      int n= result.edges.size();
      for(int i=0;i<n;i++){
        HE_Edge origE=(HE_Edge)result.edges.get(i);
        HE_HalfEdge origHE1= origE.halfEdge;
        HE_HalfEdge origHE2= origHE1.pair;
        HE_Vertex v=new HE_Vertex(0,0,0,-1);
        HE_Vertex v1=origHE1.vert;
        HE_Vertex v2=origHE2.vert;
        v.x=0.5*(v1.x+v2.x);
        v.y=0.5*(v1.y+v2.y);
        v.z=0.5*(v1.z+v2.z);
        result.vertices.add(v);
        HE_Edge newE= new HE_Edge();
        newE.visible=origE.visible;
        result.edges.add(newE);
        HE_HalfEdge newHE1=new HE_HalfEdge();
        result.halfEdges.add(newHE1);
        HE_HalfEdge newHE2=new HE_HalfEdge();
        result.halfEdges.add(newHE2);
        newHE1.vert=v;    
        newHE1.next=origHE1.next;
        newHE1.face=origHE1.face;
        newHE1.pair=origHE2;
        newHE1.edge=newE;
        origHE1.next=newHE1;
        origHE1.pair=newHE2;        
        newHE2.vert=v;
        newHE2.next=origHE2.next;
        newHE2.face=origHE2.face;
        newHE2.pair=origHE1;
        newHE2.edge=origE;
        origHE2.next=newHE2;
        origHE2.pair=newHE1;
        origHE2.edge=newE;
        newE.halfEdge=newHE1;
        v.halfEdge=newHE1;
      }
      ArrayList newFaces=new ArrayList();
      for(int i=0;i<result.faces.size();i++){
        HE_Face face=(HE_Face)result.faces.get(i);
        HE_HalfEdge startHE = face.halfEdge;
        while(startHE.vert.id!=-1) startHE=startHE.next;
        HE_HalfEdge origHE1=startHE;
        HE_Face centerFace=new HE_Face();
        centerFace.visible=face.visible; 
        newFaces.add(centerFace);
        ArrayList faceHalfEdges=new ArrayList();
        do{
          HE_Face newFace=new HE_Face();
          newFace.visible=face.visible;       
          newFaces.add(newFace);
          newFace.halfEdge=origHE1;
          HE_HalfEdge origHE2=origHE1.next;
          HE_HalfEdge origHE3=origHE2.next;
          HE_HalfEdge newHE=new HE_HalfEdge();  
          HE_HalfEdge newHEp=new HE_HalfEdge(); 

          result.halfEdges.add(newHE);
          result.halfEdges.add(newHEp);
          faceHalfEdges.add(newHEp);
          origHE2.next=newHE;
          newHE.next=origHE1;
          newHE.vert=origHE3.vert;
          newHE.face=newFace;
          origHE1.face=newFace;
          origHE2.face=newFace;
          newHEp.vert=origHE1.vert;
          newHE.pair=newHEp;
          newHEp.pair=newHE;
          HE_Edge e = new HE_Edge();
          result.edges.add(e);
          e.halfEdge=newHE;
          newHE.edge=e;
          newHEp.edge=e;
          newHEp.face=centerFace;
          centerFace.halfEdge=newHEp;

          origHE1=origHE3;

        }
        while(origHE1!=startHE);
        result.cycleHalfEdges(faceHalfEdges,false);
      }
      result.pairHalfEdges();
      result.faces=newFaces;

      result.clearSecondaries();
    }
    return result;
  }
}


class PlanarQuadTriSubdivision extends HE_Subdivision{

  HE_Mesh divide(final HE_Mesh mesh,int rep){

    HE_Mesh result=mesh.get();
    for(int r=0;r<rep;r++){//start of repetition loop;
      if(!result.indicesUpdated) result.reindex();
      if(!result.faceCentersUpdated) result.setFaceCenters();
      ArrayList triFaces=new ArrayList();
      for(int i=0;i<result.faces.size();i++){
        HE_Face face=(HE_Face)result.faces.get(i);
        if(face.halfEdge==face.halfEdge.next.next.next) triFaces.add(face);
      }

      int n= result.edges.size();
      for(int i=0;i<n;i++){
        HE_Edge origE=(HE_Edge)result.edges.get(i);
        HE_HalfEdge origHE1= origE.halfEdge;
        HE_HalfEdge origHE2= origHE1.pair;
        HE_Vertex v=new HE_Vertex(0,0,0,-1);
        HE_Vertex v1=origHE1.vert;
        HE_Vertex v2=origHE2.vert;
        v.x=0.5*(v1.x+v2.x);
        v.y=0.5*(v1.y+v2.y);
        v.z=0.5*(v1.z+v2.z);
        result.vertices.add(v);
        HE_Edge newE= new HE_Edge();
        newE.visible=origE.visible;
        result.edges.add(newE);
        HE_HalfEdge newHE1=new HE_HalfEdge();
        result.halfEdges.add(newHE1);
        HE_HalfEdge newHE2=new HE_HalfEdge();
        result.halfEdges.add(newHE2);
        newHE1.vert=v;    
        newHE1.next=origHE1.next;
        newHE1.face=origHE1.face;
        newHE1.pair=origHE2;
        newHE1.edge=newE;
        origHE1.next=newHE1;
        origHE1.pair=newHE2;        
        newHE2.vert=v;
        newHE2.next=origHE2.next;
        newHE2.face=origHE2.face;
        newHE2.pair=origHE1;
        newHE2.edge=origE;
        origHE2.next=newHE2;
        origHE2.pair=newHE1;
        origHE2.edge=newE;
        newE.halfEdge=newHE1;
        v.halfEdge=newHE1;
      }
      ArrayList newFaces=new ArrayList();
      for(int i=0;i<result.faces.size();i++){//start of face loop
        HE_Face face=(HE_Face)result.faces.get(i);
        HE_HalfEdge startHE = face.halfEdge;
        while(startHE.vert.id!=-1) startHE=startHE.next;

        if(triFaces.contains(face)){
          HE_HalfEdge origHE1=startHE;
          HE_Face centerFace=new HE_Face();
          centerFace.visible=face.visible; 
          newFaces.add(centerFace);
          ArrayList faceHalfEdges=new ArrayList();
          do{
            HE_Face newFace=new HE_Face();
            newFace.visible=face.visible;       
            newFaces.add(newFace);
            newFace.halfEdge=origHE1;
            HE_HalfEdge origHE2=origHE1.next;
            HE_HalfEdge origHE3=origHE2.next;
            HE_HalfEdge newHE=new HE_HalfEdge();  
            HE_HalfEdge newHEp=new HE_HalfEdge(); 
            result.halfEdges.add(newHE);
            result.halfEdges.add(newHEp);
            faceHalfEdges.add(newHEp);
            origHE2.next=newHE;
            newHE.next=origHE1;
            newHE.vert=origHE3.vert;
            newHE.face=newFace;
            origHE1.face=newFace;
            origHE2.face=newFace;
            newHEp.vert=origHE1.vert;
            newHE.pair=newHEp;
            newHEp.pair=newHE;
            HE_Edge e = new HE_Edge();
            result.edges.add(e);
            e.halfEdge=newHE;
            newHE.edge=e;
            newHEp.edge=e;
            newHEp.face=centerFace;
            centerFace.halfEdge=newHEp;
            origHE1=origHE3;
          }
          while(origHE1!=startHE);
          result.cycleHalfEdges(faceHalfEdges,false);
        }
        else
        {
          HE_HalfEdge origHE1=startHE;
          do{
            HE_Face newFace=new HE_Face();
            newFace.visible=face.visible;       
            newFaces.add(newFace);
            newFace.halfEdge=origHE1;
            HE_HalfEdge origHE2=origHE1.next;
            HE_HalfEdge origHE3=origHE2.next;
            HE_HalfEdge newHE1=new HE_HalfEdge();
            HE_HalfEdge newHE2=new HE_HalfEdge();    
            result.halfEdges.add(newHE1);
            result.halfEdges.add(newHE2);
            origHE2.next=newHE1;
            newHE1.next=newHE2;
            newHE2.next=origHE1;
            newHE1.vert=origHE3.vert;
            HE_Vertex fv=(HE_Vertex)result.faceCenters.get(origHE1.face.id);
            newHE2.vert=fv;
            if(fv.halfEdge==null) fv.halfEdge=newHE2;
            if(!result.vertices.contains(fv))result.vertices.add(fv);
            newHE1.face=newFace;
            newHE2.face=newFace;
            origHE1.face=newFace;
            origHE2.face=newFace;
            origHE1=origHE3;
          }
          while(origHE1!=startHE);
        }
      }//end of face loop
      result.pairHalfEdges();
      result.faces=newFaces;
      result.clearSecondaries();
    }// end of repetition loop
    return result;
  }
}


class PlanarMidFaceSubdivision extends HE_Subdivision{

  float f;

  PlanarMidFaceSubdivision(){
    f=0.5f; 
  }

  PlanarMidFaceSubdivision(float ff){
    f=ff; 
  }

  HE_Mesh divide(final HE_Mesh mesh){

    float locf=1f-f;
    if(!mesh.faceCentersUpdated)mesh.setFaceCenters();   
    HE_Mesh result=new HE_Mesh();
    HE_Mesh tracker=mesh.get();
    for(int i=0;i<mesh.faces.size();i++){
      HE_Face origF=(HE_Face)mesh.faces.get(i);
      HE_Face trackF=(HE_Face)tracker.faces.get(i);
      PVector fc=(PVector)mesh.faceCenters.get(i);
      HE_HalfEdge origHe=origF.halfEdge; 
      HE_HalfEdge trackHe=trackF.halfEdge; 
      do{
        HE_Vertex vo=origHe.vert;
        HE_Vertex vn=new HE_Vertex(fc.x+locf*(vo.x-fc.x),fc.y+locf*(vo.y-fc.y),fc.z+locf*(vo.z-fc.z),-1);  
        if(!result.vertices.contains(vn))result.vertices.add(vn);
        if(!result.vertices.contains(vo))result.vertices.add(vo);
        trackHe.vert=vn;
        origHe=origHe.next;
        trackHe=trackHe.next;       
      }
      while(origHe!=origF.halfEdge); 
    } 
    for(int i=0;i<mesh.faces.size();i++){
      HE_Face trackF=(HE_Face)tracker.faces.get(i); 
      HE_HalfEdge trackHe=trackF.halfEdge; 
      HE_Face nf=new HE_Face();
      result.faces.add(nf);
      nf.visible=trackF.visible;
      nf.fixed=trackF.fixed;
      ArrayList newHalfEdges=new ArrayList();
      do{
        HE_Vertex v=trackHe.vert;
        HE_HalfEdge he=new HE_HalfEdge();
        newHalfEdges.add(he);
        he.vert=v;
        he.face=nf;
        if(nf.halfEdge==null) nf.halfEdge=he;
        trackHe=trackHe.next;       
      }
      while(trackHe!=trackF.halfEdge); 
      result.cycleHalfEdges(newHalfEdges,false);
      result.halfEdges.addAll(newHalfEdges);  
    }     

    for(int i=0;i<mesh.edges.size();i++){
      HE_Edge trackE=(HE_Edge)tracker.edges.get(i);
      HE_Edge origE=(HE_Edge)mesh.edges.get(i);
      HE_HalfEdge trackHe1=trackE.halfEdge; 
      HE_HalfEdge trackHe2=trackE.halfEdge.pair; 
      HE_HalfEdge origHe1=origE.halfEdge; 
      HE_HalfEdge origHe2=origE.halfEdge.pair;
      HE_Face nf=new HE_Face();
      result.faces.add(nf);
      nf.visible=true;
      HE_Vertex v4=trackHe1.vert;
      HE_Vertex v3=trackHe1.next.vert;
      HE_Vertex v2=origHe1.next.vert;
      HE_Vertex v1=origHe1.vert;
      HE_HalfEdge he1=new HE_HalfEdge();
      HE_HalfEdge he2=new HE_HalfEdge();
      HE_HalfEdge he3=new HE_HalfEdge();
      HE_HalfEdge he4=new HE_HalfEdge();
      nf.halfEdge=he1;
      he1.vert=v1;
      v1.halfEdge=he1;
      he1.face=nf;
      he1.next=he2;
      he2.vert=v2;
      v2.halfEdge=he2;
      he2.face=nf;
      he2.next=he3;
      he3.vert=v3;
      v3.halfEdge=he3;
      he3.face=nf;
      he3.next=he4;
      he4.vert=v4;
      v4.halfEdge=he4;
      he4.face=nf;
      he4.next=he1;
      result.halfEdges.add(he1);
      result.halfEdges.add(he2);
      result.halfEdges.add(he3);
      result.halfEdges.add(he4);
      nf=new HE_Face();
      result.faces.add(nf);
      nf.visible=true;
      v4=trackHe2.vert;
      v3=trackHe2.next.vert;
      v2=origHe2.next.vert;
      v1=origHe2.vert;
      he1=new HE_HalfEdge();
      he2=new HE_HalfEdge();
      he3=new HE_HalfEdge();
      he4=new HE_HalfEdge();
      nf.halfEdge=he1;
      he1.vert=v1;
      v1.halfEdge=he1;
      he1.face=nf;
      he1.next=he2;
      he2.vert=v2;
      v2.halfEdge=he2;
      he2.face=nf;
      he2.next=he3;
      he3.vert=v3;
      v3.halfEdge=he3;
      he3.face=nf;
      he3.next=he4;
      he4.vert=v4;
      v4.halfEdge=he4;
      he4.face=nf;
      he4.next=he1;
      result.halfEdges.add(he1);
      result.halfEdges.add(he2);
      result.halfEdges.add(he3);
      result.halfEdges.add(he4);


    }
    result.pairHalfEdges();
    for(int i=0;i<result.edges.size();i++){
      HE_Edge e=(HE_Edge)result.edges.get(i);
      if((e.halfEdge.face.visible)||(e.halfEdge.pair.face.visible)) e.visible=true;     
    }
    result.bodyCenterUpdated=false;
    result.faceCentersUpdated=false;
    result.faceNormalsUpdated=false;
    result.vertexNormalsUpdated=false;
    result.edgeCentersUpdated=false;
    result.edgeNormalsUpdated=false;
    result.indicesUpdated=false;


    return result;    
  }


  HE_Mesh divide(final HE_Mesh mesh, int rep){
    if(rep<1){
      return mesh.get();
    }
    else if(rep==1)
    {
      return divide(mesh); 
    }
    else{
      HE_Mesh result=divide(mesh);
      for(int i=1;i<rep;i++){
        result=divide(result); 
      }
      return result;
    }


  }

}