Mesh.cc

Go to the documentation of this file.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <esg/mesh/Mesh.h>

using namespace esg;

void Mesh::AppendVertex(Solid *S, Vert *V)
{
  Vert *LV;
  
  if (S->first_vertex==NULL) {
    S->first_vertex=V;
    V->next_vertex=V; V->previous_vertex=V;
    S->cover.xmin=S->cover.xmax=V->x;
    S->cover.ymin=S->cover.ymax=V->y;
    S->cover.zmin=S->cover.zmax=V->z;
  } else {
    LV=S->first_vertex->previous_vertex;
    V->previous_vertex=LV;
    V->next_vertex=LV->next_vertex;
    LV->next_vertex->previous_vertex=V;
    LV->next_vertex=V;

    if (V->x<S->cover.xmin) S->cover.xmin=V->x; else
      if (V->x>S->cover.xmax) S->cover.xmax=V->x;
    if (V->y<S->cover.ymin) S->cover.ymin=V->y; else
      if (V->y>S->cover.ymax) S->cover.ymax=V->y;
    if (V->z<S->cover.zmin) S->cover.zmin=V->z; else
      if (V->z>S->cover.zmax) S->cover.zmax=V->z;
  }
}

void Mesh::AppendEdge(Solid *S, Edge *E)
{
  Edge *LE;
  
  if (S->first_edge==NULL) {
    S->first_edge=E;
    E->next_edge=E; E->previous_edge=E;
  } else {
    LE=S->first_edge->previous_edge;
    E->previous_edge=LE;
    E->next_edge=LE->next_edge;
    LE->next_edge->previous_edge=E;
    LE->next_edge=E;
  }
}

void Mesh::AppendFace(Solid *S, Plane *NP)
{
  Plane *LP;
  
  if (S->first_plane!=NULL) {
    LP=S->first_plane->previous_plane;
    NP->next_plane=LP->next_plane;
    NP->previous_plane=LP;
    NP->next_plane->previous_plane=NP;
    LP->next_plane=NP;
  } else {
    NP->next_plane=NP; NP->previous_plane=NP;
    S->first_plane =NP;
  }
}

void Mesh::DeleteVertex(Solid *S, Vert *V)
{
  if (V!=NULL) {
    if (V->next_vertex==V) {
      S->first_vertex=NULL;
    } else {
      V->next_vertex->previous_vertex=V->previous_vertex;
      V->previous_vertex->next_vertex=V->next_vertex;
      if (S->first_vertex==V) S->first_vertex=V->next_vertex;
    }
    delete(V);
  }
}

void Mesh::DeleteEdge(Solid *S, Edge *E)
{
  if (E!=NULL) {
    if (E->next_edge==E) {
      S->first_edge=NULL; 
    } else {
      E->next_edge->previous_edge=E->previous_edge;
      E->previous_edge->next_edge=E->next_edge;

      if (S->first_edge==E) S->first_edge=E->next_edge;
    }
    delete(E);
  }
}

void Mesh::DeleteFace(Solid *S, Plane *NP)
{
  if (NP!=NULL) {
    if (NP->next_plane==NP) {
      S->first_plane=NULL; 
    } else {
      NP->next_plane->previous_plane=NP->previous_plane;
      NP->previous_plane->next_plane=NP->next_plane;
      if (S->first_plane==NP) S->first_plane=NP->next_plane;
    }
    delete(NP);
  }
};

void Mesh::MoveVertex(Solid *S, Solid *SM, Vert *V)
{
  if (V!=NULL) {
    if (V->next_vertex==V) {
      S->first_vertex=NULL;
    } else {
      V->next_vertex->previous_vertex=V->previous_vertex;
      V->previous_vertex->next_vertex=V->next_vertex;
      if (S->first_vertex==V) S->first_vertex=V->next_vertex;
    }
    AppendVertex(SM,V);
  }
}

void Mesh::MoveEdge(Solid *S, Solid *SM, Edge *E)
{
  if (E!=NULL) {
    if (E->next_edge==E) S->first_edge=NULL;
    else {
      E->next_edge->previous_edge=E->previous_edge;
      E->previous_edge->next_edge=E->next_edge;

      if (S->first_edge==E) S->first_edge=E->next_edge;
    }
    AppendEdge(SM,E);
  }
}

void Mesh::MoveFace(Solid *S, Solid *SM, Plane *NP)
{
  if (NP!=NULL) {
  if (NP->next_plane==NP)S->first_plane=NULL;
  else
    {
      NP->next_plane->previous_plane=NP->previous_plane;
      NP->previous_plane->next_plane=NP->next_plane;
      if (S->first_plane==NP) S->first_plane=NP->next_plane;
    }
    AppendFace(SM,NP);
  }
}

Mesh::Vert* Mesh::NewVertex(Solid *S, float xp, float yp, float zp)
{
    Vert *NV = MV(xp, yp, zp);
    AppendVertex(S,NV);    /* zarad na konec seznamu vrcholu */
    return NV;
}

Mesh::Edge* Mesh::NewEdge(Solid *S, Vert *V1p, Vert *V2p,
                          Plane *P1p, Plane *P2p)
{
  Edge *NE = new Edge;
  
  pocet_hran++;
  
  NE->V1=V1p; NE->V2=V2p;
  NE->LeftLoop=P1p; NE->RightLoop=P2p;
  NE->jmeno_hrany=pocet_hran; NE->druh_hrany=VNITRNI;
  if (NE->LeftLoop->skalar<=0) NE->druh_hrany=OBRYSOVA;
  /* plocha LeftLoop neni videt */
  if (NE->RightLoop->skalar<=0) {
  /* plocha RightLoop neni videt */
    if (NE->druh_hrany==OBRYSOVA) NE->druh_hrany=ZAKRYTA;
      else NE->druh_hrany=OBRYSOVA;
  }
 P1p->any_edge=NE; P2p->any_edge=NE;
 AppendEdge(S,NE);
 
 return NE;
}

Mesh::Plane* Mesh::NewPlane(Solid *S,float a1,float b1,float c1,float d1)
{
  Plane *NP=new Plane;
  
  pocet_rovin++;
  NP->a=a1; NP->b=b1; NP->c=c1; NP->d=d1; NP->any_edge=NULL; NP->skalar=-c1;
  NP->jmeno_roviny=pocet_rovin;
  AppendFace(S,NP);
  return NP;
}

void Mesh::Copy_solid(Solid *Sorigin, Solid *Scopy)
{
  Vert *OV;
  Edge *OE;
  Plane *OP;
  
 /* zkopiruj vrcholy */  /* previous_vertex je pouzit jako new vertex address */
  OV=Sorigin->first_vertex;
  do {
     OV->previous_vertex=NewVertex(Scopy,OV->x,OV->y,OV->z);
     AppendVertex(Scopy,OV->previous_vertex);
     OV=OV->next_vertex;
  } while (OV!=Sorigin->first_vertex);

 /* zkopiruj roviny */
  OP=Sorigin->first_plane;
  do {
    OP->previous_plane=NewPlane(Scopy,OP->a,OP->b,OP->c,OP->d);
    AppendFace(Scopy,OP->previous_plane);
    OP=OP->next_plane;
  } while (OP!=Sorigin->first_plane);

 /* zkopiruj hrany */
  OE=Sorigin->first_edge;
  do {
    OE->previous_edge=NewEdge(Scopy,
        OE->V1->previous_vertex,
        OE->V2->previous_vertex,
        OE->LeftLoop->previous_plane,
        OE->RightLoop->previous_plane);
    AppendEdge(Scopy,OE->previous_edge);
    OE=OE->next_edge;
  } while (OE!=Sorigin->first_edge);

 /* oprav ukazatele hran */
  OE=Sorigin->first_edge;
  do {
    OE->previous_edge->LeftIn=OE->LeftIn->previous_edge;
    OE->previous_edge->RightOut=OE->RightOut->previous_edge;
    OE->previous_edge->LeftOut=OE->LeftOut->previous_edge;
    OE->previous_edge->RightIn=OE->RightIn->previous_edge;
    OE=OE->next_edge;
  } while (OE!=Sorigin->first_edge);
}

void Mesh::Delete_solid(Solid **S)
 /* predpokladam, ze teleso je vyrazeno ze sceny */
{
  Vert *CV,*NV;
  Edge *CE,*NE;
  Plane *CP,*NP;

  if (S!=NULL) {
    NV=(*S)->first_vertex;   /* rusim vrcholy */
    if (NV!=NULL)
      do {
        CV=NV; NV=NV->next_vertex; delete CV;
      } while (NV!=(*S)->first_vertex);
    
    NE=(*S)->first_edge;     /* rusim hrany */
    if (NE!=NULL)
      do {
        CE=NE; NE=NE->next_edge; delete CE;
      } while (NE!=(*S)->first_edge);

    NP=(*S)->first_plane;    /* rusim plochy */
    if (NP!=NULL)
      do {
        CP=NP; NP=NP->next_plane; delete CP;
      } while (NP!=(*S)->first_plane);
  }
  delete *S;
}

#define eps 0.01
int Mesh::Paralel_planes(float a, float b, float c,
                         float ar, float br, float cr,
                         int &same_orientation)
{
  int ParPla;
  
  same_orientation=0;
  ParPla= (fabs(b*cr-c*br)+fabs(c*ar-a*cr)+fabs(a*br-b*ar))<eps;
  if (ParPla) same_orientation= (a*ar+b*br+c*cr)>0;

  return ParPla;
}
#undef eps

void Mesh::Vertex_Plane_position(Solid &S,
                                 float ar, float br, float cr, float dr,
                                 int &Pozitiv,int &Negativ)
{
  Vert *NV;
  
  Pozitiv=0; Negativ=0;
 /* klasifikuj vsechny vrcholy vuci rovine ar.x+br.y+cr.z+dr==0 */
  NV=S.first_vertex;
  do {
    NV->fxyz=ar*NV->x+br*NV->y+cr*NV->z+dr;
    if (NV->fxyz>0) Pozitiv++; else
      if (NV->fxyz<0) Negativ++;
    NV=NV->next_vertex;
  } while (NV!=S.first_vertex);
}

void Mesh::Orient_Edge(Edge *E, Plane *F, Vert **Vin, Vert **Vout)
{
    if (F==E->LeftLoop){ *Vin=E->V1; *Vout=E->V2; }
                  else { *Vin=E->V2; *Vout=E->V1; }
}

Mesh::Edge* Mesh::Next_Edge_in_loop(Edge *CE, Vert **Vin, Vert **Vout)
{
  Edge *NE;
  
  /* Vin, Vout jsou vstupni a vystupni body hrany CE^, udavaji orientaci
    smycky na plose  */
  /* po provedeni funkce Next_edge_in_loop udavaji vstup a vystup na dalsi
    hrane */
      /* zkoumam hranu CE */
      /* volim dalsi hranu ve smycce pro rovinu NP */
  if (*Vin==CE->V1)  /* sleduji hrany LeftIn,LeftOut */
    NE=CE->LeftOut;
  else /* sleduj hrany RightOut,RightIn */
    NE=CE->RightOut;
  /* vime hranu, jeste nastavime spravnou orientaci Vin, Vout */
  if (*Vout==NE->V1)
    { *Vin=NE->V1; *Vout=NE->V2; }
  else
    { *Vin=NE->V2; *Vout=NE->V1; }
  return(NE);
}

Mesh::Edge* Mesh::Previous_Edge_in_loop(Edge *CE, Vert **Vin, Vert **Vout)
{
  Edge *NE;
  /* Vin, Vout jsou vstupni a vystupni body hrany CE^, udavaji orientaci
    smycky na plose  */
  /* po provedeni funkce Next_edge_in_loop udavaji vstup a vystup na dalsi
    hrane */
  /* couvam na predchozi hranu ve smycce */
  if (*Vin==CE->V1)
    NE=CE->LeftIn;
  else
    NE=CE->RightIn;

  /* vime hranu, jeste nastavime spravnou orientaci Vin, Vout */
  if (*Vin==NE->V2)
    { *Vin=NE->V1; *Vout=NE->V2; }
  else
    { *Vin=NE->V2; *Vout=NE->V1; }
  return(NE);
}

void Mesh::ClasifyEdges(Solid *S)
{
  Edge *NE;
  
  NE=S->first_edge;
  do {
    NE->druh_hrany=VNITRNI;
    if ((NE->LeftLoop->skalar<=0)) /* plocha LeftLoop neni videt */
      NE->druh_hrany=OBRYSOVA;
    if ((NE->RightLoop->skalar<=0))/* plocha RightLoop neni videt */
      {
        if (NE->druh_hrany==OBRYSOVA) NE->druh_hrany=ZAKRYTA;
        else NE->druh_hrany=OBRYSOVA;
      }
    NE=NE->next_edge;
  } while (NE!=S->first_edge);
}

Mesh::Vert* Mesh::MV(float xp, float yp, float zp)  /* make vertex */
{
  Vert *NV = new Vert;
  
  NV->x=xp; NV->y=yp; NV->z=zp;
  NV->jmeno_vrcholu=pocet_vrcholu++;
  NV->fxyz=0.0;
  return(NV);
}

Mesh::Plane* Mesh::MF(float a1, float b1, float c1, float d1)  //make plane
{
  Plane *NP = new Plane;
  
  pocet_rovin=pocet_rovin+1;
  NP->a=a1; NP->b=b1; NP->c=c1; NP->d=d1;
  NP->any_edge=NULL; NP->skalar=-(NP->c);
  NP->jmeno_roviny=pocet_rovin;
  return(NP);
}

/* make vertex, solid , face */
Mesh::Solid* Mesh::MVSF(Plane *F, Vert *V)
{
  Solid* S = new Solid;
  
  S->solid_name=0;
  S->first_vertex=NULL;
  S->first_edge=NULL;
  S->first_plane=NULL;
  S->next_solid=S;
  S->previous_solid=S;
  AppendVertex(S,V);
  AppendFace(S,F);
  return(S);
}


void Mesh::MEV(Solid *S, Vert *V1p, Vert *V2p, Edge **E, Plane *F)
{
  Vert *Vin, *Vout;
  Edge   *CE;
  
  /* zarad vrchol V2p do seznamu vrcholu */
  AppendVertex(S,V2p);

  *E = new Edge;
 
  pocet_hran=pocet_hran+1;
  (*E)->V1=V1p; (*E)->V2=V2p; (*E)->jmeno_hrany=pocet_hran;
  (*E)->LeftLoop=F; (*E)->RightLoop=F;
  (*E)->LeftIn=NULL; (*E)->RightOut=NULL;
  (*E)->LeftOut=NULL; (*E)->RightIn=NULL;

  if (F->any_edge==NULL)/* tato hrana je prvni */
    {
      (*E)->LeftIn=*E; (*E)->RightOut=*E; (*E)->LeftOut=*E; (*E)->RightIn=*E;
      F->any_edge=*E;
    }
  else
    /* na povrchu F nalezni hranu, ktera konci ve vrcholu V1 */
    {
      (*E)->LeftOut=*E; (*E)->RightIn=*E;  /* koncova smycka */
      CE=F->any_edge;
      Orient_Edge(CE,F,&Vin,&Vout);
      
      while (Vout!=V1p) { CE=Next_Edge_in_loop(CE,&Vin,&Vout); }
      if (CE->V1==Vin)    /* sleduji levou smycku */
        {
          if (CE->LeftOut->V1==Vout) CE->LeftOut->LeftIn=*E;
          else CE->LeftOut->RightIn=*E;
          (*E)->RightOut=CE->LeftOut; (*E)->LeftIn=CE; CE->LeftOut=*E;
        }
      else
        {
          if (CE->RightOut->V1==Vout) CE->RightOut->LeftIn=*E;
          else CE->RightOut->RightIn=*E;
          (*E)->RightOut=CE->RightOut; (*E)->LeftIn=CE; CE->RightOut=*E;
        }
    }
  AppendEdge(S,*E);
}

void Mesh::ReplaceEdge(Edge *E1, Edge *E, Edge *E2)
{
  if (E1->LeftIn==E) E1->LeftIn=E2;
  else
    if (E1->RightIn==E) E1->RightIn=E2;
    else
      if (E1->LeftOut==E) E1->LeftOut=E2;
      else
        if (E1->RightOut==E) E1->RightOut=E2;
}

void Mesh::SEMV(Solid *S, Edge *E1, Vert *V, Edge **E2)
{
  *E2 = new Edge;
  pocet_hran=pocet_hran+1;
  
  (*E2)->jmeno_hrany=pocet_hran;
  (*E2)->LeftLoop=E1->LeftLoop; (*E2)->RightLoop=E1->RightLoop;
  (*E2)->V1=V; (*E2)->V2=E1->V2; E1->V2=V;
  (*E2)->LeftOut=E1->LeftOut; (*E2)->LeftIn=E1;
  (*E2)->RightIn=E1->RightIn; (*E2)->RightOut=E1;
  E1->LeftOut=*E2;  E1->RightIn=*E2;
  
  ReplaceEdge((*E2)->LeftOut,E1,*E2); ReplaceEdge((*E2)->RightIn,E1,*E2);
  AppendEdge(S,*E2);  AppendVertex(S,V);
}

void Mesh::MEF(Solid *S,Vert *V1p,Vert *V2p,Plane *F1,Plane *F2,Edge **E)
{
    MEnotF(S,V1p,V2p,F1,F2,E);
    AppendFace(S,F2);
    return;
    
  Edge *CE, *NE, *L;
  Vert *Vin, *Vout, *Cin, *Nout;
  Vert *Nin  = NULL;
  Vert *Cout = NULL; 
  
  /* na povrchu F1 nalezni hranu CE, ktera konci ve vrcholu V2p */
  CE=NULL; NE=NULL;
  L=F1->any_edge;  Orient_Edge(L,F1,&Vin,&Vout);

  do {
    if (Vout==V2p) { CE=L; Cin=Vin; Cout=Vout; }
    if (Vin==V2p ) { NE=L; Nin=Vin; Nout=Vout; }
    L=Next_Edge_in_loop(L,&Vin,&Vout);
  } while ((CE == NULL) || (NE == NULL));

 *E = new Edge; pocet_hran=pocet_hran+1;
 (*E)->V1=V1p; (*E)->V2=V2p; (*E)->jmeno_hrany=pocet_hran;
 (*E)->LeftLoop=F1; (*E)->RightLoop=F1;
 (*E)->LeftIn=NULL; (*E)->RightOut=NULL;
 (*E)->LeftOut=NULL;(*E)->RightIn=NULL;

 if (F1->any_edge==NULL)/* tato hrana je prvni */
   {
     (*E)->LeftIn=*E; (*E)->RightOut=*E; (*E)->LeftOut=*E; (*E)->RightIn=*E;
     F1->any_edge=*E;
   }
 else
   /* na povrchu F1 nalezni hranu, ktera konci ve vrcholu V1 */
   {
     (*E)->LeftOut=*E; (*E)->RightIn=*E;  /* koncova smycka */
     L=F1->any_edge;
     Orient_Edge(L,F1,&Vin,&Vout);

     while (Vout!=V1p) { L=Next_Edge_in_loop(L,&Vin,&Vout); }
     if (L->V1==Vin)    /* sleduji levou smycku */
       {
         if (L->LeftOut->V1==Vout) L->LeftOut->LeftIn=*E;
             else L->LeftOut->RightIn=*E;
         (*E)->RightOut=L->LeftOut;  (*E)->LeftIn=L; L->LeftOut=*E;
       }
     else
       {
         if (L->RightOut->V1==Vout) L->RightOut->LeftIn=*E;
             else L->RightOut->RightIn=*E;
         (*E)->RightOut=L->RightOut;  (*E)->LeftIn=L; L->RightOut=*E;
       }
     }

     (*E)->LeftLoop=F2; (*E)->RightLoop=F1;
     F1->any_edge=*E; F2->any_edge=*E;
     (*E)->LeftOut=NE;  (*E)->RightIn=CE;

/* pripoj smycku */

     if (CE->V2 == Cout) CE->LeftOut=*E;  else CE->RightOut=*E;
     if (NE->V1 == Nin ) NE->LeftIn =*E;  else NE->RightIn =*E;

     L=*E; Vin=V1p; Vout=V2p;
     do {
       if (Vin==L->V1) L->LeftLoop=F2; else L->RightLoop=F2;
       L=Next_Edge_in_loop(L,&Vin,&Vout);
     } while (L!=(*E));

     AppendEdge(S,*E); AppendFace(S,F2);
}

void Mesh::MEnotF(Solid *S, Vert *V1p, Vert *V2p,
                  Plane *F1, Plane *F2, Edge **E)
{
  Edge *CE, *NE, *L;
  Vert *Vin, *Vout, *Cin, *Nout;
  Vert *Nin  = NULL;
  Vert *Cout = NULL; 
  
  /* na povrchu F1 nalezni hranu CE, ktera konci ve vrcholu V2p */
  CE=NULL; NE=NULL;
  L=F1->any_edge; Orient_Edge(L,F1,&Vin,&Vout);

  do {
    if (Vout==V2p){ CE=L; Cin=Vin; Cout=Vout; }
    if (Vin==V2p ){ NE=L; Nin=Vin; Nout=Vout; }
    L=Next_Edge_in_loop(L,&Vin,&Vout);
  } while ((CE == NULL) || (NE == NULL));

 *E = new Edge; pocet_hran=pocet_hran+1;
 (*E)->V1=V1p; (*E)->V2=V2p; (*E)->jmeno_hrany=pocet_hran;
 (*E)->LeftLoop=F1; (*E)->RightLoop=F1;

 if (F1->any_edge==NULL)/* tato hrana je prvni */
   {
     (*E)->LeftIn=*E; (*E)->RightOut=*E; (*E)->LeftOut=*E; (*E)->RightIn=*E;
     F1->any_edge=*E;
   }
 else
   /* na povrchu F1 nalezni hranu, ktera konci ve vrcholu V1 */
   {
     (*E)->LeftOut=*E; (*E)->RightIn=*E;  /* koncova smycka */
     L=F1->any_edge;
     Orient_Edge(L,F1,&Vin,&Vout);

     while (Vout!=V1p) { L=Next_Edge_in_loop(L,&Vin,&Vout); }
     if (L->V1==Vin)    /* sleduji levou smycku */
       {
         if (L->LeftOut->V1==Vout) L->LeftOut->LeftIn=*E;
             else L->LeftOut->RightIn=*E;
         (*E)->RightOut=L->LeftOut; (*E)->LeftIn=L; L->LeftOut=*E;
       }
     else
       {
         if (L->RightOut->V1==Vout) L->RightOut->LeftIn=*E;
             else L->RightOut->RightIn=*E;
         (*E)->RightOut=L->RightOut; (*E)->LeftIn=L; L->RightOut=*E;
       }
     }

     (*E)->LeftLoop=F2; (*E)->RightLoop=F1;
     F1->any_edge=*E;   F2->any_edge=*E;
     (*E)->LeftOut=NE;  (*E)->RightIn=CE;

/* pripoj smycku */

     if (CE->V2 == Cout) CE->LeftOut=*E;  else CE->RightOut=*E;
     if (NE->V1 == Nin ) NE->LeftIn =*E;  else NE->RightIn =*E;

     L=*E; Vin=V1p; Vout=V2p;
     do {
       if (Vin==L->V1) L->LeftLoop=F2; else L->RightLoop=F2;
       L=Next_Edge_in_loop(L,&Vin,&Vout);
     } while (L!=(*E));

     AppendEdge(S,*E);
}

Mesh::Vert* Mesh::Vertex_of_cut(Vert *V1, Vert *V2)
{
  float t,xcut,ycut,zcut;
  Vert *VC;
  
  /* vim, ze hrana protina rezovou rovinu */
  /* protoze fxyz==a.x+b.y+c.z-d je jiz vypocteno a ulozeno
    u kazdeho vrcholu, nepotrebuji koeficienty roviny */
  t = V1->fxyz/(V1->fxyz-V2->fxyz);
  xcut=V1->x+(V2->x-V1->x)*t;
  ycut=V1->y+(V2->y-V1->y)*t;
  zcut=V1->z+(V2->z-V1->z)*t;
  VC=MV(xcut,ycut,zcut); VC->fxyz=0.0;
  return(VC);
}

Mesh::Plane* Mesh::This_loop(Edge *E, Vert *V)
{
  if (V == E->V1) return(E->LeftLoop); else return(E->RightLoop);
}

void Mesh::ConnectEdge(Edge *E1, Edge *E, Edge *E2, Plane *P)
{
  if (E1->LeftIn==E) { E1->LeftIn=E2; E1->LeftLoop=P; }
  else
    if (E1->RightIn==E) { E1->RightIn=E2; E1->RightLoop=P; }
    else
      if (E1->LeftOut==E) { E1->LeftOut=E2; E1->LeftLoop=P; }
      else
        if (E1->RightOut==E) { E1->RightOut=E2; E1->RightLoop=P; }
}

void Mesh::KE(Edge *E, Vert *Vin, Plane *P1, Plane *P2)
{
  if (Vin==E->V1)
    {
      P2->any_edge=E->LeftOut; P1->any_edge=E->LeftIn;
      ConnectEdge(E->LeftOut,E,E->RightIn,P2);
      ConnectEdge(E->RightIn,E,E->LeftOut,P2);
      ConnectEdge(E->LeftIn,E,E->RightOut,P1);
      ConnectEdge(E->RightOut,E,E->LeftIn,P1);
    }
  else            /* hrany LeftIn, RightOut patri k odpadu */
    {
      P1->any_edge=E->LeftOut; P2->any_edge=E->LeftIn;
      ConnectEdge(E->LeftOut,E,E->RightIn,P1);
      ConnectEdge(E->RightIn,E,E->LeftOut,P1);
      ConnectEdge(E->LeftIn,E,E->RightOut,P2);
      ConnectEdge(E->RightOut,E,E->LeftIn,P2);
    }
}

void Mesh::SeparateSolids(Solid **NS, Solid **Odpad)
{
  Edge *NE, *PE;
  Plane *NP, *PP;
  Vert *NV, *PV;
  int konec;
  
/* zaklad telesa */
  *Odpad = new Solid;
  (*Odpad)->solid_name=0;
  (*Odpad)->first_vertex=NULL;
  (*Odpad)->first_edge=NULL;
  (*Odpad)->first_plane=NULL;
  
  NV=(*NS)->first_vertex;
  do {
    NV->valid=0;
    NV=NV->next_vertex;
  } while (NV!=(*NS)->first_vertex);

  NP=(*NS)->first_plane;
  do {
    NP->jmeno_roviny=-NP->jmeno_roviny;
    NP=NP->next_plane;
  } while (NP!=(*NS)->first_plane);

  PE=(*NS)->first_edge;
  do {
    NE=PE->next_edge;
    if (PE==(*NS)->first_edge->previous_edge) konec=1; else konec=0;
    if (PE->druh_hrany==TELESOVA)
    {
      PE->V1->valid=1; PE->V2->valid=1;
      PE->LeftLoop->jmeno_roviny=abs(PE->LeftLoop->jmeno_roviny);
      PE->RightLoop->jmeno_roviny=abs(PE->RightLoop->jmeno_roviny);
    }
    else
    {
      MoveEdge(*NS,*Odpad,PE);
    }
    PE=NE;
  } while (!konec);

   /* zrus vrcholy s ...Valid==false */
   PV=(*NS)->first_vertex;
   do {
    if (PV==(*NS)->first_vertex->previous_vertex) konec=1; else konec=0;
    NV=PV->next_vertex;
    if (!(PV->valid)) MoveVertex(*NS,*Odpad,PV);
    PV=NV;
   } while (!konec);

   /* zrus plochy se zapornym jmenem */
   PP=(*NS)->first_plane;
   do {
     if (PP==(*NS)->first_plane->previous_plane) konec=1; else konec=0;
     NP=PP->next_plane;
     if ((PP->jmeno_roviny<=0))
        {
        PP->jmeno_roviny=abs(PP->jmeno_roviny);
        MoveFace(*NS,*Odpad,PP);
        }
     PP=NP;
   } while (!konec);
}


//------------------------ public --------------------------

void Mesh::rotate(const Matrix3& rotMat)
{
  if (!pSolid) return;

  Vector3 v;
  Vert* pVert = pSolid->first_vertex;
  if (pVert)
      do {
          v.set(pVert->x, pVert->y, pVert->z);
          rotMat.transform(v);
          pVert->x = v.x;
          pVert->y = v.y;
          pVert->z = v.z;
          rotMat.transform(pVert->normal);
          pVert = pVert->next_vertex;
      } while (pVert != pSolid->first_vertex);

  Vector3 u;
  Plane* pPlane = pSolid->first_plane;
  if (pPlane)
      do {
          v.set(pPlane->a, pPlane->b, pPlane->c);
          rotMat.transform(v);
          pPlane->a = v.x;
          pPlane->b = v.y;
          pPlane->c = v.z;
          u.set(pPlane->any_edge->V1->x,
                pPlane->any_edge->V1->y,
                pPlane->any_edge->V1->z);
          pPlane->d = - u.dot(v);
          pPlane = pPlane->next_plane;
      } while (pPlane != pSolid->first_plane);
}

void Mesh::translate(const Vector3& tr)
{
  if (!pSolid) return;

  Vert* pVert = pSolid->first_vertex;
  if (pVert)
      do {
          pVert->x += tr.x;
          pVert->y += tr.y;
          pVert->z += tr.z;
          pVert->fxyz += tr.length();
          pVert = pVert->next_vertex;
      } while (pVert != pSolid->first_vertex);

  Vector3 u, v;
  Plane* pPlane = pSolid->first_plane;
  if (pPlane)
      do {
          v.set(pPlane->a, pPlane->b, pPlane->c);
          u.set(pPlane->any_edge->V1->x,
                pPlane->any_edge->V1->y,
                pPlane->any_edge->V1->z);
          pPlane->d = - u.dot(v);
          pPlane = pPlane->next_plane;
      } while (pPlane != pSolid->first_plane);
}

void Mesh::transform(const Matrix4& trMat)
{
  if (!pSolid) return;

  Vector3 v;
  Matrix3 rotMat;

  trMat.get(rotMat);

  Vert* pVert = pSolid->first_vertex;
  if (pVert)
      do {
          v.set(pVert->x, pVert->y, pVert->z);
          trMat.transform(v);
          pVert->x = v.x;
          pVert->y = v.y;
          pVert->z = v.z;
          rotMat.transform(pVert->normal);
          pVert->fxyz = - pVert->normal.dot(v);
          pVert = pVert->next_vertex;
      } while (pVert != pSolid->first_vertex);

  Vector3 u;
  Plane* pPlane = pSolid->first_plane;
  if (pPlane)
      do {
          v.set(pPlane->a, pPlane->b, pPlane->c);
          rotMat.transform(v);
          pPlane->a = v.x;
          pPlane->b = v.y;
          pPlane->c = v.z;
          u.set(pPlane->any_edge->V1->x,
                pPlane->any_edge->V1->y,
                pPlane->any_edge->V1->z);
          pPlane->d = - u.dot(v);
          pPlane = pPlane->next_plane;
      } while (pPlane != pSolid->first_plane);
}

void Mesh::scale(float scX, float scY, float scZ)
{
    if (!pSolid) return;

    Vert* pVert = pSolid->first_vertex;
    if (pVert)
        do {
            pVert->x *= scX;
            pVert->y *= scY;
            pVert->z *= scZ;
            pVert = pVert->next_vertex;
        } while (pVert != pSolid->first_vertex);
}

void Mesh::resetActSolid()
{
  pActSolid = pSolid;
}

int Mesh::goToNextSolid()
{
  if (!pActSolid) return 0;
  if (pActSolid->next_solid == pSolid) return 0; // Last solid in list
  pActSolid = pActSolid->next_solid;
  return 1;
}

void Mesh::resetActPlane()
{
  pActPlane = pActSolid->first_plane;
}

Mesh::Plane* Mesh::getActPlane()
{
  return pActPlane;
}

int Mesh::goToNextPlane()
{
  if (pActPlane->next_plane == pSolid->first_plane) return 0;
  pActPlane = pActPlane->next_plane;
  return 1;
}

void Mesh::resetActEdge()
{
  pActEdge = pActPlane->any_edge;
}

int Mesh::goToNextEdge()
{
    Vert *Vin, *Vout;

    Orient_Edge(pActEdge, pActPlane, &Vin, &Vout);
    pActEdge = Next_Edge_in_loop(pActEdge, &Vin, &Vout);
    
    if (pActEdge == pActPlane->any_edge) return 0; // loop finished
    else return 1;
}

Vertex3 Mesh::getActVert1(bool orient)
{
    if (orient) {
        if (pActEdge->LeftLoop == pActPlane) 
            return Vertex3(pActEdge->V1->x, pActEdge->V1->y, pActEdge->V1->z);
        else if (pActEdge->RightLoop == pActPlane) 
            return Vertex3(pActEdge->V2->x, pActEdge->V2->y, pActEdge->V2->z);
        else {
            fprintf(stderr,"Mesh error: Actual face mismatch the actual edge\n");
            return Vertex3(0,0,0);
        }
    } else {
        return Vertex3(pActEdge->V1->x, pActEdge->V1->y, pActEdge->V1->z);
    }
}

Vertex3 Mesh::getActVert2(bool orient)
{
    if (orient) {
        if (pActEdge->LeftLoop == pActPlane) 
            return Vertex3(pActEdge->V2->x, pActEdge->V2->y, pActEdge->V2->z);
        else if (pActEdge->RightLoop == pActPlane) 
            return Vertex3(pActEdge->V1->x, pActEdge->V1->y, pActEdge->V1->z);
        else {
            fprintf(stderr,"Mesh error: Actual face mismatch the actual edge\n");
            return Vertex3(0,0,0);
        }
    } else 
        return Vertex3(pActEdge->V2->x, pActEdge->V2->y, pActEdge->V2->z);
}

Vertex3 Mesh::getActVert()
{
    if (pActVert) return Vertex3(pActVert->x, pActVert->y, pActVert->z);
    else {
        fprintf(stderr,"Mesh error: getActVert() called but no actual vertex set\n");
        return Vertex3(0,0,0);
    }
}

Vertex3 Mesh::getActVertNormal1(bool orient)
{
    if (orient) {
        if (pActEdge->LeftLoop == pActPlane)
            return pActEdge->V1->normal;
        else if (pActEdge->RightLoop == pActPlane)
            return pActEdge->V2->normal;
        else {
            fprintf(stderr,"Mesh error: Actual face mismatch actual edge\n");
            return Vertex3(0,0,0);
        }
    } else
        return pActEdge->V1->normal;
}

Vertex3 Mesh::getActVertNormal2(bool orient) 
{
    if (orient) {
        if (pActEdge->LeftLoop == pActPlane)
            return pActEdge->V2->normal;
        else if (pActEdge->RightLoop == pActPlane)
            return pActEdge->V1->normal;
        else {
            fprintf(stderr,"Mesh error: Actual face mismatch actual edge\n");
            return Vertex3(0,0,0);
        }
    } else
        return pActEdge->V2->normal;
}

Vertex3 Mesh::getActVertNormal()
{
    if (pActVert) return pActVert->normal;
    else {
        fprintf(stderr,"Mesh error: getActVertNormal() called but no actual vertex defined\n");
        return Vertex3(0,0,0);
    }
}

int Mesh::getActVertID1(bool orient)
{
    if (orient) {
        if (pActEdge->LeftLoop == pActPlane) 
            return pActEdge->V1->jmeno_vrcholu;
        else if (pActEdge->RightLoop == pActPlane) 
            return pActEdge->V2->jmeno_vrcholu;
        else {
            fprintf(stderr,"Mesh error: Actual face mismatch actual edge\n");
            return -1;
        }
    } else 
        return pActEdge->V1->jmeno_vrcholu;
}

int Mesh::getActVertID2(bool orient)
{
    if (orient) {
        if (pActEdge->LeftLoop == pActPlane) 
            return pActEdge->V2->jmeno_vrcholu;
        else if (pActEdge->RightLoop == pActPlane) 
            return pActEdge->V1->jmeno_vrcholu;
        else {
            fprintf(stderr,"Mesh error: Actual face mismatch actual edge\n");
            return -1;
        }
    } else 
        return pActEdge->V2->jmeno_vrcholu;
}

int Mesh::getActVertID()
{
    if (pActVert) return pActVert->jmeno_vrcholu;
    else {
        fprintf(stderr,"Mesh error: getActVertColor() called but no actual vertex defined\n");
        return -1;
    }
}

int Mesh::getActPlaneID()
{
    if (pActPlane) return pActPlane->jmeno_roviny;
    else {
        fprintf(stderr,"Mesh error: getActPlaneID() called but no actual plane defined\n");
        return -1;
    }
}

Vertex3 Mesh::getActPlaneNormal() const
{
    if (pActPlane) return Vertex3(pActPlane->a,pActPlane->b,pActPlane->c);
    else {
        fprintf(stderr,"Mesh error: getActPlaneNormal() called but no actual plane defined\n");
        return Vertex3(0,0,0);
    }
}

Vector3 Mesh::getActPlaneCentroid()
{
    if (!pActPlane) return Vector3(MAX_VEC_VALUE,MAX_VEC_VALUE,MAX_VEC_VALUE);

    Vector3  ret;
    unsigned n = 0;
    Edge *   e = pActEdge;

    resetActEdge();
    do {
        if (n == 0) ret.set(getActVert1(true));
        else ret.add(getActVert1(true));
    } while (++n && goToNextEdge());
    ret.scale(1.0/n);

    pActEdge = e;
    return ret;
}

double Mesh::getActPlaneArea() 
{
    if (!pActPlane) return MINDOUBLE;

    double   area;
    Edge *   e = pActEdge;
    Vector3  v0, v1;
    unsigned n = 0;

    resetActEdge();
    do {
        if (n == 0) {
            v0.set(getActVert1(true));
            v0.sub(getActVert2(true));
        }
        if (n == 1) {
            v1.set(getActVert2(true));
            v1.sub(getActVert1(true));
        }
    } while (++n && goToNextEdge());

    area = v0.dot(v1);
    if (n == 3) area /= 2.0;
    else if (n != 4) {
        fprintf(stderr,"Mesh::getActPlaneArea(): only three or four edges supported\n");
    }

    pActEdge = e;

    return area;
}

void Mesh::resetEdgeWalkInSolid()
{
  pActEdge = pActSolid->first_edge;
}

int Mesh::stepInEdgeWalkInSolid()
{
  if (pActEdge->next_edge == pActSolid->first_edge) return 0;
  pActEdge = pActEdge->next_edge;
  return 1;
}

void Mesh::resetVertWalkInSolid()
{
  pActVert = pActSolid->first_vertex;
}

bool Mesh::stepInVertWalkInSolid()
{
  if (pActVert->next_vertex == pActSolid->first_vertex) return false;
  pActVert = pActVert->next_vertex;
  return true;
}

void Mesh::turnInsideOut(void)
{
    Solid * pActSolid = pSolid;
    do {
        Plane * pActPlane = pActSolid->first_plane;
        if (pActPlane)
            do {
                pActPlane->a      *= -1;
                pActPlane->b      *= -1;
                pActPlane->c      *= -1;
                pActPlane->d      *= -1;
                pActPlane->skalar *= -1;
                pActPlane = pActPlane->next_plane;
            } while (pActPlane != pActSolid->first_plane);
        Vert * pActVert = pActSolid->first_vertex;
        if (pActVert)
            do {
                pActVert->normal.negate();
                pActVert = pActVert->next_vertex;
            } while (pActVert != pActSolid->first_vertex);
        pActSolid = pActSolid->next_solid;
    } while (pActSolid != pSolid);
}

---