//Rudimentary plane class
class Plane{
  float A,B,C,D;

  Plane(final PVector p0, final PVector n){
    PVector norm=n.get();
    norm.normalize();
    A=norm.x;
    B=norm.y;
    C=norm.z;
    D=-A*p0.x-B*p0.y-C*p0.z;
  }

  Plane(final PVector p0, final PVector p1, final PVector p2){
    A=p0.y*(p1.z-p2.z)+p1.y*(p2.z-p0.z)+p2.y*(p0.z-p1.z);
    B=p0.z*(p1.x-p2.x)+p1.z*(p2.x-p0.x)+p2.z*(p0.x-p1.x);
    C=p0.x*(p1.y-p2.y)+p1.x*(p2.y-p0.y)+p2.x*(p0.y-p1.y);
    PVector norm=new PVector(A,B,C);
    norm.normalize();
    A=norm.x;
    B=norm.y;
    C=norm.z;
    D=-A*p0.x-B*p0.y-C*p0.z;
  }

  void flipNormal(){
    A*=-1;
    B*=-1;
    C*=-1;
    D*=-1;

  }

  //returns 1 if p is on same side as normal, -1 if on opposite side, 0 if on the plane
  float side(final PVector p){
    float tmp=A*p.x+B*p.y+C*p.z+D;
    if(tmp<-0.001f){
      tmp=-1f; 
    }
    else if(tmp>0.001f){
      tmp=1f; 
    }
    else{
      tmp=0f; 
    }
    return tmp;
  }
}

//Half-Edge Mesh
//Source: http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

class HE_Mesh{
  ArrayList vertices; 
  ArrayList faces;
  ArrayList halfEdges;
  ArrayList edges;

  HE_Mesh(){
    vertices=new ArrayList(); 
    faces=new ArrayList();
    halfEdges=new ArrayList();
    edges=new ArrayList();
  }

  HE_Face getFace(int i){
    return (HE_Face)faces.get(i);
  }

  HE_Vertex getVertex(int i){
    return (HE_Vertex)vertices.get(i);
  }

  HE_HalfEdge getHalfEdge(int i){
    return (HE_HalfEdge)halfEdges.get(i);
  }

  HE_Edge getEdge(int i){
    return (HE_Edge)edges.get(i); 
  }

  // draw as a triangular mesh.
  void draw(){
    Iterator faceItr = faces.iterator();
    while(faceItr.hasNext()){
      HE_Face face=(HE_Face)faceItr.next();
      HE_HalfEdge halfEdge=face.halfEdge;
      HE_Vertex midFace=new HE_Vertex(0,0,0,0);
      int c=0;
      do{
        HE_Vertex v=halfEdge.vert;
        midFace.x+=v.x;
        midFace.y+=v.y;
        midFace.z+=v.z;
        halfEdge=halfEdge.next;
        c++;
      }
      while(halfEdge!=face.halfEdge);
      midFace.x/=c;
      midFace.y/=c;
      midFace.z/=c;
      halfEdge=face.halfEdge;
      //If face has three vertices, ignore the midface vertex and just draw the triangle.
      //If the face has more than three vertices, draw as a series of triangles connecting the edges to the midface vertex.
      if(c==3){
        beginShape();
        do{              
          HE_Vertex v=halfEdge.vert; 
          vertex(v.x,v.y,v.z);
          halfEdge= halfEdge.next;
        } 
        while(halfEdge!=face.halfEdge);      
        endShape();
      }
      else{
        beginShape(TRIANGLE_STRIP);
        do{              
          HE_Vertex v=halfEdge.vert; 
          vertex(v.x,v.y,v.z);
          vertex(midFace.x,midFace.y,midFace.z);
          halfEdge= halfEdge.next;
          //v=halfEdge.vert; 
          //vertex(v.x,v.y,v.z);
        }
        while(halfEdge!=face.halfEdge);
        HE_Vertex v=halfEdge.vert; 
        vertex(v.x,v.y,v.z);
        endShape();
      }
    }
  }   

  void drawVertices(){
    Iterator vertexItr = vertices.iterator();
    while(vertexItr.hasNext()){
      HE_Vertex v=(HE_Vertex)vertexItr.next();
      pushMatrix();
      translate(v.x,v.y,v.z);  
      box(5);
      popMatrix();
    }
    noFill();
  }

  void drawEdges(){
    Iterator eItr = edges.iterator();
    while(eItr.hasNext()){
      HE_Edge e=(HE_Edge)eItr.next();

      line(e.halfEdge.vert.x,e.halfEdge.vert.y,e.halfEdge.vert.z,e.halfEdge.pair.vert.x,e.halfEdge.pair.vert.y,e.halfEdge.pair.vert.z);
    }
  }

  void drawCurves(){
    Iterator faceItr = faces.iterator();
    while(faceItr.hasNext()){
      HE_Face face=(HE_Face)faceItr.next();
      HE_HalfEdge halfEdge=face.halfEdge;
      HE_Vertex u=halfEdge.vert;
      HE_Vertex v=halfEdge.next.vert;
      beginShape();
      vertex(0.5*(u.x+v.x),0.5*(u.y+v.y),0.5*(u.z+v.z));     
      do{
        u=halfEdge.next.vert;
        v=halfEdge.next.next.vert;      
        bezierVertex(u.x,u.y,u.z,u.x,u.y,u.z,0.5*(u.x+v.x),0.5*(u.y+v.y),0.5*(u.z+v.z));
        halfEdge=halfEdge.next;
      }
      while(halfEdge!=face.halfEdge);
      endShape(CLOSE);
    }
  }

  void buildMesh(float[][] simpleVertices, int[][] simpleFaces){
    vertices=new ArrayList(); 
    faces=new ArrayList();
    halfEdges=new ArrayList();
    edges=new ArrayList();

    //Add all input vertices to the mesh, the original index of the vertex is stored as an id.
    for(int i=0;i<simpleVertices.length;i++){  
      vertices.add(new HE_Vertex(simpleVertices[i][0],simpleVertices[i][1],simpleVertices[i][2],i)); 
    }

    //Create a loop of halfedges for each face. We assume the vertices are given in a consistent order.
    // To extend this for a non-ordered list, sort the vertices of the input vertices here.
    HE_HalfEdge he;
    for(int i=0;i<simpleFaces.length;i++){
      ArrayList faceEdges=new ArrayList();
      HE_Face hef=new HE_Face();
      faces.add(hef);
      //TODO: sort face vertices here
      for(int j=0;j<simpleFaces[i].length;j++){
        he=new HE_HalfEdge();
        faceEdges.add(he);
        he.face=hef;
        if (hef.halfEdge==null) hef.halfEdge=he;
        he.vert=(HE_Vertex)vertices.get(simpleFaces[i][j]);
        if(he.vert.halfEdge==null) he.vert.halfEdge=he;  
      }
      cycleHalfEdges(faceEdges,false);    
      halfEdges.addAll(faceEdges);
    }
    //associate each halfedge with its pair (belonging to adjacent face)
    pairHalfEdges(halfEdges);
    //associate each pair of halfedges to a physical edge
    createEdges(halfEdges,edges);
    reindex();
  }



  HE_Mesh get(){
    HE_Mesh result=new HE_Mesh();
    reindex();
    for(int i=0;i<vertices.size();i++){
      result.vertices.add(((HE_Vertex)vertices.get(i)).get());
    }
    for(int i=0;i<faces.size();i++){
      result.faces.add(new HE_Face());
    }
    for(int i=0;i<halfEdges.size();i++){
      result.halfEdges.add(new HE_HalfEdge());
    }
    for(int i=0;i<edges.size();i++){
      result.edges.add(new HE_Edge());
    }

    for(int i=0;i<vertices.size();i++){
      HE_Vertex sv=getVertex(i);
      HE_Vertex tv=result.getVertex(i);
      tv.halfEdge=result.getHalfEdge(sv.halfEdge.id);
    }
    for(int i=0;i<faces.size();i++){
      HE_Face sf=getFace(i);
      HE_Face tf=result.getFace(i);
      tf.id=i;
      tf.halfEdge=result.getHalfEdge(sf.halfEdge.id);
    }
    for(int i=0;i<edges.size();i++){
      HE_Edge se=getEdge(i);
      HE_Edge te=result.getEdge(i);
      te.halfEdge=result.getHalfEdge(se.halfEdge.id);
      te.id=i;
    }
    for(int i=0;i<halfEdges.size();i++){
      HE_HalfEdge she=getHalfEdge(i);
      HE_HalfEdge the=result.getHalfEdge(i);
      the.pair=result.getHalfEdge(she.pair.id);
      the.next=result.getHalfEdge(she.next.id);
      the.prev=result.getHalfEdge(she.prev.id);
      the.vert=result.getVertex(she.vert.id);
      the.face=result.getFace(she.face.id);
      the.edge=result.getEdge(she.edge.id);
      the.id=i;
    }
    return result;
  }

  HE_Mesh getDual(){
    HE_Mesh result=new HE_Mesh();
    reindex();
    for(int i=0;i<faces.size();i++){
      HE_Face f=getFace(i);
      HE_HalfEdge he=f.halfEdge;
      PVector faceCenter=new PVector();
      int n=0;
      do{
        faceCenter.add(he.vert);
        he=he.next;
        n++;
      }
      while(he!=f.halfEdge);
      faceCenter.div(n);
      result.vertices.add(new HE_Vertex(faceCenter.x,faceCenter.y,faceCenter.z,i));
    }

    for(int i=0;i<vertices.size();i++){
      HE_Vertex v=getVertex(i);
      HE_HalfEdge he=v.halfEdge;
      HE_Face f= he.face;
      ArrayList faceHalfEdges=new ArrayList();
      HE_Face nf=new HE_Face();
      result.faces.add(nf);
      do{
        HE_HalfEdge hen = new HE_HalfEdge();
        faceHalfEdges.add(hen);
        hen.face=nf;
        hen.vert=result.getVertex(f.id);
        if(hen.vert.halfEdge==null) hen.vert.halfEdge=hen;
        if (nf.halfEdge==null) nf.halfEdge=hen;
        he=he.pair.next;
        f=he.face;

      }
      while(he!=v.halfEdge);
      cycleHalfEdges(faceHalfEdges,false);    
      result.halfEdges.addAll(faceHalfEdges);

    }
    result.pairHalfEdges(result.halfEdges);
    result.createEdges(result.halfEdges,result.edges);
    result.reindex();

    return result;

  }

  void cycleHalfEdges(ArrayList halfEdges, boolean reverse){   
    HE_HalfEdge he;
    int n=halfEdges.size();
    if(!reverse){
      he=(HE_HalfEdge)halfEdges.get(0);
      he.next=(HE_HalfEdge)halfEdges.get(1);
      he.prev=(HE_HalfEdge)halfEdges.get(n-1);
      for(int j=1;j<n-1;j++){
        he=(HE_HalfEdge)halfEdges.get(j);
        he.next=(HE_HalfEdge)halfEdges.get(j+1);
        he.prev=(HE_HalfEdge)halfEdges.get(j-1);
      }
      he=(HE_HalfEdge)halfEdges.get(n-1);
      he.next=(HE_HalfEdge)halfEdges.get(0);
      he.prev=(HE_HalfEdge)halfEdges.get(n-2);
    }
    else{
      he=(HE_HalfEdge)halfEdges.get(0);
      he.prev=(HE_HalfEdge)halfEdges.get(1);
      he.next=(HE_HalfEdge)halfEdges.get(n-1);
      for(int j=1;j<n-1;j++){
        he=(HE_HalfEdge)halfEdges.get(j);
        he.prev=(HE_HalfEdge)halfEdges.get(j+1);
        he.next=(HE_HalfEdge)halfEdges.get(j-1);
      }
      he=(HE_HalfEdge)halfEdges.get(n-1);
      he.prev=(HE_HalfEdge)halfEdges.get(0);
      he.next=(HE_HalfEdge)halfEdges.get(n-2);

    }

  }

  //go through all the halfedges and find matching pairs
  void pairHalfEdges(ArrayList halfEdges){
    int n=halfEdges.size();
    for(int i=0;i<n;i++){
      HE_HalfEdge he=(HE_HalfEdge)halfEdges.get(i);
      if(he.pair==null){
        for(int j=0;j<n;j++){
          if(i!=j){
            HE_HalfEdge he2=(HE_HalfEdge)halfEdges.get(j);
            if((he2.pair==null)&&(he.vert==he2.next.vert)&&(he2.vert==he.next.vert)){
              he.pair=he2;
              he2.pair=he;
              break;              
            }
          }
        }
      }
    }

  }

  //associate each pair of halfedges to a physical edge.
  void createEdges(ArrayList halfEdges, ArrayList target){
    int n=halfEdges.size();
    for(int i=0;i<n;i++){
      HE_HalfEdge he=(HE_HalfEdge)halfEdges.get(i);     
      for(int j=0;j<n;j++){
        if(i!=j){
          HE_HalfEdge he2=(HE_HalfEdge)halfEdges.get(j);
          if(he.pair==he2){
            HE_Edge e=new HE_Edge();
            e.halfEdge=he;
            target.add(e);
            he.edge=e;
            he2.edge=e;
            break;              
          }
        }        
      }
    }
  }


  // check all edges for intersection wit a plan
  ArrayList retrieveSplitEdges(Plane P){
    ArrayList splitEdges=new ArrayList();
    for(int i=0;i<edges.size();i++){
      HE_Edge edge=getEdge(i);
      PVector intersection=planeEdgeIntersection(edge,P); 
      if(intersection!=null){    
        splitEdges.add(new SplitEdge(edge,intersection));
      }
    }
    return splitEdges;
  }

  void reindex(){
    for(int i=0;i<vertices.size();i++){
      ((HE_Vertex)vertices.get(i)).id=i;
    }
    for(int i=0;i<faces.size();i++){
      ((HE_Face)faces.get(i)).id=i;
    }
    for(int i=0;i<halfEdges.size();i++){
      ((HE_HalfEdge)halfEdges.get(i)).id=i;
    }
    for(int i=0;i<edges.size();i++){
      ((HE_Edge)edges.get(i)).id=i;
    }
  }


  // Split the mesh in half, retain the part on the same side as the point "center".
  // Works only on a convex mesh !!!
  void splitMesh(Plane P,PVector center){
    float centerside=P.side(center);
    if (centerside!=0){// if center is on the plane, we can't decide which part to keep, ignore.
      ArrayList newVertices=new ArrayList();
      ArrayList newFaces=new ArrayList();
      ArrayList newHalfEdges=new ArrayList();
      ArrayList newEdges=new ArrayList();

      // get all split edges
      ArrayList splitEdges=retrieveSplitEdges(P);           

      //check if the plane cuts the mesh at all, at least one point should be on the other side of the plane.
      //compared to the first point
      float[] sides = new float[vertices.size()];
      boolean cut=false;         
      for(int i=0;i<vertices.size();i++){
        HE_Vertex v=getVertex(i);
        sides[i]=P.side(v);
        if(sides[0]*sides[i]<=0f) cut=true;
      }


        //loop through all faces.
        for(int i=0;i<faces.size();i++){
          HE_Face face=getFace(i);
          HE_HalfEdge halfEdge= face.halfEdge;      
          ArrayList newFaceVertices1=new ArrayList();// vertices on the correct side.
          ArrayList newFaceVertices2=new ArrayList();// vertices on the wrong side, not used right now.

          //for each face, loop through all vertices and retain the vertices on the correct side. If the edge
          //is cut, insert the new point in the appropriate place.   
          do{ 

              if(sides[halfEdge.vert.id]*centerside>=0f){
                newFaceVertices1.add(halfEdge.vert);
              }
              if(sides[halfEdge.vert.id]*centerside<=0f){
                newFaceVertices2.add(halfEdge.vert);
              }

            for(int j=0;j<splitEdges.size();j++){// loop through all split edges to check for the current edge.
              SplitEdge se=(SplitEdge)splitEdges.get(j);
              if(halfEdge.edge==se.edge){
                newFaceVertices1.add(se.splitVertex);
                newFaceVertices2.add(se.splitVertex);
                break;
              }
            }
            halfEdge = halfEdge.next;
          } 
          while(halfEdge!=face.halfEdge);

          //Create a new face form the vertices we retained,ignore degenerate faces with less than 3 vertices.
          //Add all face-related information to the data-structure.
          if(newFaceVertices1.size()>2){
            HE_Face newFace=new HE_Face();
            newFaces.add(newFace);
            ArrayList faceEdges=new ArrayList();
            for(int j=0;j<newFaceVertices1.size();j++){
              HE_Vertex v=(HE_Vertex)newFaceVertices1.get(j);
              if(!newVertices.contains(v)) newVertices.add(v);
              HE_HalfEdge newHalfEdge=new HE_HalfEdge();
              faceEdges.add(newHalfEdge);
              newHalfEdge.vert=v;

              v.halfEdge=newHalfEdge;
              newHalfEdge.face=newFace;
              if(newFace.halfEdge==null) newFace.halfEdge=newHalfEdge;
            }
            cycleHalfEdges(faceEdges,false);
            newHalfEdges.addAll(faceEdges); 
          }

        }

        //Add missing information to the datastructure
        int n=newHalfEdges.size();
        pairHalfEdges(newHalfEdges);
        createEdges(newHalfEdges,newEdges);

        //Cutting the mesh not only cuts the faces, it also creates one new planar face looping through all new cutpoints(in a convex mesh).
        //This hole in the mesh is identified by unpaired halfedges remaining after the pairibg operation.
        //This part needs to rethought to extend to concave meshes!!!
        ArrayList unpairedEdges=new ArrayList();
        for(int i=0;i<n;i++){
          HE_HalfEdge he=(HE_HalfEdge)newHalfEdges.get(i);
          if(he.pair==null) unpairedEdges.add(he);
        }
        if(unpairedEdges.size()>0){
          //Create a closed loop out of the collection of unpaired halfedges and associate a new face with this.
          //Easy to explain with a drawing, beyond my skill with words.
          HE_Face cutFace = new HE_Face(); 
          ArrayList faceEdges=new ArrayList();  
          HE_HalfEdge he =(HE_HalfEdge)unpairedEdges.get(0);
          HE_HalfEdge hen=he;

          do{
            hen=he.next.pair.next;        
            while(!unpairedEdges.contains(hen)) hen=hen.pair.next;
            HE_HalfEdge newhe=new HE_HalfEdge();
            faceEdges.add(newhe);
            if(cutFace.halfEdge==null) cutFace.halfEdge=newhe;
            newhe.vert=hen.vert;
            newhe.pair=he;
            he.pair=newhe;
            HE_Edge e=new HE_Edge();
            e.halfEdge=newhe;
            he.edge=e;
            newhe.edge=e;
            newEdges.add(e);
            newhe.face=cutFace;
            he=hen;
          } 
          while(hen!=(HE_HalfEdge)unpairedEdges.get(0));

          cycleHalfEdges(faceEdges, true);
          newHalfEdges.addAll(faceEdges); 
          newFaces.add(cutFace);
        }              
     
      // update the mesh
      vertices=newVertices;
      faces=newFaces;
      halfEdges=newHalfEdges;

      edges=newEdges;
      reindex();

    }
  }


void splitSurface(Plane P){
   
      ArrayList newVertices=new ArrayList();
      ArrayList newFaces=new ArrayList();
      ArrayList newHalfEdges=new ArrayList();
      ArrayList newEdges=new ArrayList();

      // get all split edges
      ArrayList splitEdges=retrieveSplitEdges(P);           

      //check if the plane cuts the mesh at all, at least one point should be on the other side of the plane.
      //compared to the first point
      float[] sides = new float[vertices.size()];
      boolean cut=false;         
      for(int i=0;i<vertices.size();i++){
        HE_Vertex v=getVertex(i);
        sides[i]=P.side(v);
        if(sides[0]*sides[i]<=0f) cut=true;
      }

        //loop through all faces.
        for(int i=0;i<faces.size();i++){
          HE_Face face=getFace(i);
          HE_HalfEdge halfEdge= face.halfEdge;      
          ArrayList newFaceVertices1=new ArrayList();
          ArrayList newFaceVertices2=new ArrayList();
          ArrayList currentFace=newFaceVertices1;
          //for each face, loop through all vertices and retain the vertices on the correct side. If the edge
          //is cut, insert the new point in the appropriate place.   
          do{ 
             
                currentFace.add(halfEdge.vert);
 

            for(int j=0;j<splitEdges.size();j++){// loop through all split edges to check for the current edge.
              SplitEdge se=(SplitEdge)splitEdges.get(j);
              if(halfEdge.edge==se.edge){
                newFaceVertices1.add(se.splitVertex);
                newFaceVertices2.add(se.splitVertex);
                if(currentFace==newFaceVertices1){
                  currentFace=newFaceVertices2;
                }
                else{
                  currentFace=newFaceVertices1;
                }
                break;
              }
            }
            halfEdge = halfEdge.next;
          } 
          while(halfEdge!=face.halfEdge);

          //Create a new face form the vertices we retained,ignore degenerate faces with less than 3 vertices.
          //Add all face-related information to the data-structure.

            HE_Face newFace=new HE_Face();
            newFaces.add(newFace);
            ArrayList faceEdges=new ArrayList();
            for(int j=0;j<newFaceVertices1.size();j++){
              HE_Vertex v=(HE_Vertex)newFaceVertices1.get(j);
              if(!newVertices.contains(v)) newVertices.add(v);
              HE_HalfEdge newHalfEdge=new HE_HalfEdge();
              faceEdges.add(newHalfEdge);
              newHalfEdge.vert=v;

              v.halfEdge=newHalfEdge;
              newHalfEdge.face=newFace;
              if(newFace.halfEdge==null) newFace.halfEdge=newHalfEdge;
            }
            cycleHalfEdges(faceEdges,false);
            newHalfEdges.addAll(faceEdges); 
            if(newFaceVertices2.size()>0){
            newFace=new HE_Face();
            newFaces.add(newFace);
            faceEdges=new ArrayList();
            for(int j=0;j<newFaceVertices2.size();j++){
              HE_Vertex v=(HE_Vertex)newFaceVertices2.get(j);
              if(!newVertices.contains(v)) newVertices.add(v);
              HE_HalfEdge newHalfEdge=new HE_HalfEdge();
              faceEdges.add(newHalfEdge);
              newHalfEdge.vert=v;

              v.halfEdge=newHalfEdge;
              newHalfEdge.face=newFace;
              if(newFace.halfEdge==null) newFace.halfEdge=newHalfEdge;
            }
            cycleHalfEdges(faceEdges,false);
            newHalfEdges.addAll(faceEdges); 
            }

        }

        //Add missing information to the datastructure
        pairHalfEdges(newHalfEdges);
        createEdges(newHalfEdges,newEdges);

                  

      
      // update the mesh
      vertices=newVertices;
      faces=newFaces;
      halfEdges=newHalfEdges;
      edges=newEdges;
      reindex();

    
  }

  void roundCorners(float d){
    ArrayList cutPlanes=new ArrayList();
    PVector center=new PVector();
    for(int i=0;i<vertices.size();i++){
      HE_Vertex v=(HE_Vertex)vertices.get(i);   
      center.add(v);
    } 
    center.div(vertices.size());
    for(int i=0;i<vertices.size();i++){
      HE_Vertex v=(HE_Vertex)vertices.get(i);   
      PVector n=PVector.sub(v,center);
      float distanceToVertex=n.mag();
      if(distanceToVertex>d){
        float ratio = (distanceToVertex-d)/distanceToVertex;
        PVector origin=PVector.mult(n,ratio);
        origin.add(center);
        cutPlanes.add(new Plane(origin,n));
      }
    }
    for(int i=0;i<cutPlanes.size();i++){
      Plane P=(Plane)cutPlanes.get(i);
      splitMesh(P,center);
    }
  }

void roundEdges(float d){
    ArrayList cutPlanes=new ArrayList();
    PVector center=new PVector();
    for(int i=0;i<vertices.size();i++){
      HE_Vertex v=(HE_Vertex)vertices.get(i);   
      center.add(v);
    } 
    center.div(vertices.size());
    
    for(int i=0;i<edges.size();i++){
      HE_Edge e=(HE_Edge)edges.get(i);   
      HE_Vertex v1=e.halfEdge.vert;
      HE_Vertex v2=e.halfEdge.pair.vert;
      HE_Vertex v=new HE_Vertex(0.5f*(v1.x+v2.x),0.5f*(v1.y+v2.y),0.5f*(v1.z+v2.z),0);

      PVector n=PVector.sub(v,center);
      float distanceToVertex=n.mag();
      if(distanceToVertex>d){
        float ratio = (distanceToVertex-d)/distanceToVertex;
        PVector origin=PVector.mult(n,ratio);
        origin.add(center);
        cutPlanes.add(new Plane(origin,n));
      }
    }
    for(int i=0;i<cutPlanes.size();i++){
      Plane P=(Plane)cutPlanes.get(i);
      splitMesh(P,center);
    }
  }

}



class HE_HalfEdge{
  int id;
  HE_Vertex vert;
  HE_HalfEdge pair;
  HE_Face face;
  HE_HalfEdge next;
  HE_HalfEdge prev;
  HE_Edge edge;

  HE_HalfEdge (){
  }
}


class HE_Edge{
  int id;
  HE_HalfEdge halfEdge;

  HE_Edge (){
  }
}

//Paul Bourke, http://local.wasp.uwa.edu.au/~pbourke/geometry/planeline/
PVector planeEdgeIntersection(final HE_Edge e, final Plane P){
  PVector p0=e.halfEdge.vert;
  PVector p1=e.halfEdge.pair.vert;
  float denom=P.A*(p0.x-p1.x)+P.B*(p0.y-p1.y)+P.C*(p0.z-p1.z);
  if ((denom<0.001f)&&(denom>-0.001f)) return null;
  float u=(P.A*p0.x+P.B*p0.y+P.C*p0.z+P.D)/denom;
  if ((u<0.00f)||(u>1.0f)) return null;
  return new PVector(p0.x+u*(p1.x-p0.x),p0.y+u*(p1.y-p0.y),p0.z+u*(p1.z-p0.z));
}

class HE_Vertex extends PVector{
  int id;
  HE_HalfEdge halfEdge;

  HE_Vertex(float x, float y, float z, int id){
    super(x,y,z); 
    this.id=id;
  }

  HE_Vertex get(){
    return new HE_Vertex(x,y,z,id);   

  }
}

class HE_Face{
  int id;
  HE_HalfEdge halfEdge; 

  HE_Face(){
  }
}

class SplitEdge{
  HE_Edge edge;
  HE_Vertex splitVertex;

  SplitEdge(){

  } 
  SplitEdge(HE_Edge e, PVector p){
    edge=e;
    splitVertex=new HE_Vertex(p.x,p.y,p.z,0);
  }  
}