PolygonalMesh.cc

Go to the documentation of this file.

#include <esg/Definitions.h>
#include <esg/mesh/PolygonalMesh.h>
#include <assert.h>
#include <iostream>

using namespace esg;

#ifndef LONGBITS
#define LONGBITS (sizeof(long int) * 8)
#endif

const unsigned PolygonalMesh::MAX_LOOP = 50;

Mesh::Vert* PolygonalMesh::_find_vertex(int index) 
{
    return _vertices[index];
}

void PolygonalMesh::_store_vertex(Vert* v)
{
    if (v) _vertices[v->jmeno_vrcholu] = v;
}


Vector3 PolygonalMesh::_plane_normal(const unsigned vIndices[],
                                   unsigned       i1,
                                   unsigned       i2,
                                   unsigned       i3) 
{
    Vector3 normal;
    Mesh::Vert *v;
    Vector3 v1, v2, v3;

    v = _find_vertex(vIndices[i1]);
    assert(v);
    v1.set(v->x, v->y, v->z);
    v = _find_vertex(vIndices[i2]);
    assert(v);
    v2.set(v->x, v->y, v->z);
    v = _find_vertex(vIndices[i3]);
    assert(v);
    v3.set(v->x, v->y, v->z);
    normal.cross(v2 - v1, v3 - v1);
    normal.normalize();

    return normal;
}

long int PolygonalMesh::_multiplex(unsigned i1, unsigned i2)
{
    if (i1 < i2)
        return (i1<<(LONGBITS/2))|i2;
    else
        return (i2<<(LONGBITS/2))|i1;
}

Mesh::Edge* PolygonalMesh::_find_edge(unsigned i1, unsigned i2)
{
    return _edges[_multiplex(i1,i2)];
}

void PolygonalMesh::_store_edge(Edge* e)
{
    _edges[_multiplex(e->V1->jmeno_vrcholu, e->V2->jmeno_vrcholu)] = e;
}

void PolygonalMesh::_erase_edge(unsigned i1, unsigned i2)
{
    _edges.erase(_edges.find(_multiplex(i1,i2)));
}

Mesh::Edge* PolygonalMesh::_append_new_edge(Mesh::Vert*  V1p,
                                          Mesh::Vert*  V2p,
                                          Mesh::Plane* F)
{
    Mesh::Edge  *E = new Edge;
 
    E->V1=V1p; E->V2=V2p; E->jmeno_hrany=++pocet_hran;
    E->LeftLoop=F; E->RightLoop=F;
    E->LeftIn = E; E->LeftOut = E;
    E->RightIn = E; E->RightOut = E;
    E->druh_hrany = TELESOVA; // new edge is always "solid's"

    _connect_edge(E,F);

    AppendEdge(pSolid,E);
    _store_edge(E); // add edge into the hash
    return E;
}

bool PolygonalMesh::_connect_edge(Mesh::Edge* E, Mesh::Plane* F)
{
    if (F->any_edge == NULL) { // first edge of plane
        F->any_edge = E;  // LeftLoop and RightLoop are already set
        return true;
    }
    
    Mesh::Vert  *Vin, *Vout;
    Mesh::Vert  *EVin, *EVout;
    Mesh::Edge  *CE = F->any_edge;
    Mesh::Vert  *VNin;
    Mesh::Vert  *VNout;
    Mesh::Edge  *CEN;
        
    Orient_Edge(E,F,&EVin,&EVout);
    Orient_Edge(CE,F,&Vin,&Vout);

    // find edge ending in the new one
    register unsigned loops = 0;
    while (Vout != EVin) {
        if (loops++ > MAX_LOOP) {
            std::cerr << "PolygonalMesh::_connect_edge(): Infinite loop detected" << std::endl;
            return false;
        }
        CE = Next_Edge_in_loop(CE,&Vin,&Vout);
    }

    // Get next neighbour in loop
    VNin  = Vin;
    VNout = Vout;
    CEN   = Next_Edge_in_loop(CE,&VNin,&VNout);

    // Insert new edge E in to the loop
    if (CE->LeftLoop == F) CE->LeftOut = E;
    else                   CE->RightOut = E;
    if (E->LeftLoop == F) { E->LeftIn   = CE; E->LeftOut = CEN; }
    else                  { E->RightIn = CE; E->RightOut = CEN; }
    if (CEN->LeftLoop == F) CEN->LeftIn   = E;
    else                    CEN->RightIn = E;

    return true;
}

Mesh::Edge* PolygonalMesh::_split_edge(Mesh::Edge * E, Mesh::Vert * V)
{
    Mesh::Edge *NE = new Edge;
    
    NE = new Edge;
    NE->V1=E->V1; NE->V2=V; NE->jmeno_hrany=++pocet_hran;
    NE->LeftLoop=E->LeftLoop; NE->RightLoop=E->RightLoop;
    NE->druh_hrany = VNITRNI;

    NE->LeftIn  = E->LeftIn;
    NE->RightOut = E->RightOut;
    if (NE->LeftIn->V2 == NE->V1)  {
        NE->LeftIn->LeftOut = NE;
        if (NE->LeftIn->RightIn == E) NE->LeftIn->RightIn = NE;
    } else {
        NE->LeftIn->RightOut = NE;
        if (NE->LeftIn->LeftIn == E) NE->LeftIn->LeftIn = NE;
    }
    if (NE->RightOut->V2 == NE->V1) NE->RightOut->RightIn = NE;
    else                            NE->RightOut->LeftIn   = NE;
    NE->LeftOut = (NE->RightIn = E);
    E->LeftIn   = (E->RightOut = NE);
    
    _erase_edge(E->V1->jmeno_vrcholu, E->V2->jmeno_vrcholu);
    E->V1 = V;
    AppendEdge(pSolid,NE);
    _store_edge(E);
    _store_edge(NE);

    return NE;
}

Mesh::Plane* PolygonalMesh::_split_plane(Mesh::Plane * F,
                                         Mesh::Vert  * V1,
                                         Mesh::Vert  * V2)
{
    if (_find_edge(V1->jmeno_vrcholu, V2->jmeno_vrcholu)) return NULL;

    Mesh::Plane* NF = NewPlane(pSolid, F->a, F->b, F->c, F->d);
    Mesh::Edge*  E  = new Edge;
 
    E->V1=V1; E->V2=V2; E->jmeno_hrany=++pocet_hran;
    E->LeftLoop=F; E->RightLoop=NF;
    E->druh_hrany = VNITRNI;

    AppendEdge(pSolid,E);
    _store_edge(E); // add edge into the hash

    
    Mesh::Vert  *Vin, *Vout;
    Mesh::Edge  *CE = F->any_edge;
    Mesh::Edge  *CEN;

    // find edge ending in first point and its neighbour
    Orient_Edge(CE,F,&Vin,&Vout);
    while (Vout != V1) CE = Next_Edge_in_loop(CE,&Vin,&Vout);
    CEN   = Next_Edge_in_loop(CE,&Vin,&Vout);

    // Interconnect first part of new edge with its neigbours
    if (CE->LeftLoop == F)  CE->LeftOut   = E;
    else                    CE->RightOut   = E;
    if (CEN->LeftLoop == F) CEN->LeftIn   = E;
    else                    CEN->RightIn = E;
    E->LeftIn  = CE;
    E->RightOut = CEN;

    // Find edge ending in second point and its neighbour.
    // During the search re-set
    // planes of all edges (all these edges covers new plane)
    CE = CEN;
    while (Vout != V2) {
        if (CE->LeftLoop  == F) CE->LeftLoop  = NF;
        if (CE->RightLoop == F) CE->RightLoop = NF;
        CE = Next_Edge_in_loop(CE,&Vin,&Vout);
    }
    if (CE->LeftLoop  == F) CE->LeftLoop  = NF;
    if (CE->RightLoop == F) CE->RightLoop = NF;
    CEN = Next_Edge_in_loop(CE,&Vin,&Vout);

    // Interconnect second part of new edge with its neigbours
    if (CE->LeftLoop == NF)  CE->LeftOut   = E;
    else                     CE->RightOut   = E;
    if (CEN->LeftLoop == F)  CEN->LeftIn   = E;
    else                     CEN->RightIn = E;
    E->LeftOut  = CEN;
    E->RightIn = CE;

    F->any_edge = (NF->any_edge = E);

    return NF;
}

bool PolygonalMesh::_get_facet_topology(Vert*          vertices[],
                                      Edge*          edges[],
                                      unsigned       num,
                                      const unsigned vIndices[],
                                      const Vector3  normals[])
{
    bool duplicate = false;
    
    for (register unsigned i = 0; i < num; i++) {
        vertices[i] = _find_vertex(vIndices[i]);
        if (!vertices[i]) {
            fprintf(stderr,"PolygonalMesh Error: Index of vertex out of range\n");
            return false;
        }
        
        // find an existing vertices with diferent normals => duplicate vertex
        if (normals) {
            if (vertices[i]->hasValidNormal() &&
                !vertices[i]->normal.equals(normals[i]))
                duplicate = true;
            else
                vertices[i]->normal.set(normals[i]);
        }
    }

    // find edges already shared by two planes => duplicate edge
    for (register unsigned i = 0; i < num && !duplicate; i++) {
        edges[i] = _find_edge(vertices[i]->jmeno_vrcholu,
                              vertices[(i+1)%num]->jmeno_vrcholu);
        if (edges[i] && edges[i]->LeftLoop != edges[i]->RightLoop) 
                duplicate = true;
    }

    if (duplicate) {
        for (register unsigned i = 0; i < num; i++) {
            // duplicate only already used vertices - those having
            // valid normal, or vertices of already shared edges
            if (vertices[i]->hasValidNormal() ||
                (edges[i] && edges[i]->LeftLoop != edges[i]->RightLoop)) {
                Vert* v = NewVertex(pSolid,
                                    vertices[i]->x,
                                    vertices[i]->y,
                                    vertices[i]->z);
                if (normals) v->normal.set(normals[i]);
                else         v->normal.set(vertices[i]->normal);
                vertices[i] = v;
                _store_vertex(vertices[i]);
            }
            edges[i] = NULL; // all edges will be new
        }
    }
    
    return true;
}


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

PolygonalMesh::PolygonalMesh(const Vector3  vertices[],
                             unsigned       nvi,
                             const unsigned vIndices[])
{
    if (! vertices || nvi == 0) {
        fprintf(stderr,"PolygonalMesh Error: Surface without vertices\n");
        return;
    }

    // create solid:
    pSolid                 = new Solid;
    pSolid->solid_name     = 0;
    pSolid->first_vertex   = NULL;
    pSolid->first_edge     = NULL;
    pSolid->first_plane    = NULL;
    pSolid->next_solid     = pSolid;
    pSolid->previous_solid = pSolid;

    // create list of vertices:
    for (register unsigned i = 0; i < nvi; i++) {
        // new_vertex->jmeno_vrcholu = i
        if (vIndices) {
            Vert* v = NewVertex(pSolid,
                                vertices[vIndices[i]].x,
                                vertices[vIndices[i]].y,
                                vertices[vIndices[i]].z);
            _store_vertex(v);
        } else {
            Vert* v = NewVertex(pSolid,
                                vertices[i].x,
                                vertices[i].y,
                                vertices[i].z);
            _store_vertex(v);
        }
    }

    pActSolid = pSolid;
    pActVert  = pSolid->first_vertex;
}

#define __NEW_FACET_FAILED(r) { \
   cerr << "PolygonalMesh::addFacet(): Can't append facet - " << (r) << ":" << endl; \
   for (unsigned i = 0; i < nVert; i++) { \
       cerr << "    v" << i << ": "; \
       cerr << _find_vertex(vIndices[i])->x << " " ; \
       cerr << _find_vertex(vIndices[i])->y << " " ; \
       cerr << _find_vertex(vIndices[i])->z << endl; \
   } \
   delete [] fVertices; \
   delete [] fEdges; \
   return false; \
}

bool PolygonalMesh::addFacet(const unsigned vIndices[],
                           const Vector3  normals[],
                           unsigned       nVert,
                           const Vector3& normal)
{
    Vert** fVertices = new Vert* [nVert];
    Edge** fEdges    = new Edge* [nVert];

    for (register unsigned i = 0; i < nVert; i++) {
        fVertices[i] = NULL;
        fEdges[i]    = NULL;
    }
    
    if (!_get_facet_topology(fVertices, fEdges, nVert, vIndices, normals))
        __NEW_FACET_FAILED("Bad topology");

    // init plane
    Mesh::Plane* p = NewPlane(pSolid,
                              normal.x,normal.y,normal.z,
                              -normal.dot(Vector3(fVertices[0]->x,
                                                  fVertices[0]->y,
                                                  fVertices[0]->z)));

    // append edges to plane and interconnect them
    for (unsigned i = 0; i < nVert; i++) {
        if (!fEdges[i]) { // edge does not exists yet
            fEdges[i]=_append_new_edge(fVertices[i],fVertices[(i+1)%nVert],p);
            if (!fEdges[i]) __NEW_FACET_FAILED("Appending new edge");
        } else {
            fEdges[i]->RightLoop  = p;
            fEdges[i]->druh_hrany = VNITRNI;
            if (!_connect_edge(fEdges[i], p))
                __NEW_FACET_FAILED("Connecting new edge");
        }
    }

    delete [] fVertices;
    delete [] fEdges;

    return true;
}

#undef __NEW_FACET_FAILED

bool PolygonalMesh::addFacet(const unsigned vIndices[],
                           const Vector3  normals[],
                           unsigned       nVert)
{
    return addFacet(vIndices,
                    normals,
                    nVert,
                    _plane_normal(vIndices, 0, 1, nVert-1));
}

---