BSP_CSGMesh.cpp

Go to the documentation of this file.

/*
 * $Id: BSP_CSGMesh.cpp 35145 2011-02-25 10:44:20Z jesterking $
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#include "BSP_CSGMesh.h"
#include "MT_assert.h"
#include "CTR_TaggedSetOps.h"
#include "MT_Plane3.h"
#include "BSP_CSGException.h"

// for insert_iterator
#include <iterator>

// for vector reverse
#include <iostream>
#include <algorithm>
using namespace std;

BSP_CSGMesh::
BSP_CSGMesh(
) :
        MEM_RefCountable()
{
        m_verts     = NULL;
        m_faces     = NULL;
        m_edges     = NULL;
}

        BSP_CSGMesh *
BSP_CSGMesh::
New(
){
        return new BSP_CSGMesh();
}

        BSP_CSGMesh *
BSP_CSGMesh::
NewCopy(
) const {

        BSP_CSGMesh *mesh = New();
        if (mesh == NULL) return NULL;

        mesh->m_bbox_max = m_bbox_max;
        mesh->m_bbox_min = m_bbox_min;

        if (m_edges != NULL) {
                mesh->m_edges = new vector<BSP_MEdge>(*m_edges);
                if (mesh->m_edges == NULL) {
                        delete mesh;
                        return NULL;
                }
        }
        if (m_verts != NULL) {
                mesh->m_verts = new vector<BSP_MVertex>(*m_verts);
                if (mesh->m_verts == NULL) {
                        if (m_edges != NULL) free(mesh->m_edges);
                        delete mesh;
                        return NULL;
                }
        }
        if (m_faces != NULL) {
                mesh->m_faces = new vector<BSP_MFace>(*m_faces);
                if (mesh->m_faces == NULL) {
                        delete mesh;
                        return NULL;
                }
        }

        return mesh;
}
        
        void
BSP_CSGMesh::
Invert(
){

        vector<BSP_MFace> & faces = FaceSet();

        vector<BSP_MFace>::const_iterator faces_end = faces.end();
        vector<BSP_MFace>::iterator faces_it = faces.begin();

        for (; faces_it != faces_end; ++faces_it) {     
                faces_it->Invert();
        }
}

        bool
BSP_CSGMesh::
SetVertices(
        vector<BSP_MVertex> *verts
){
        if (verts == NULL) return false;

        // create polygon and edge arrays and reserve some space.
        m_faces = new vector<BSP_MFace>;
        if (!m_faces) return false;

        m_faces->reserve(verts->size()/2);
        
        // previous verts get deleted here.
        m_verts = verts;
        return true;
}

                void
BSP_CSGMesh::
AddPolygon(
        const int * verts,
        int num_verts
){
        MT_assert(verts != NULL);
        MT_assert(num_verts >=3);

        if (verts == NULL || num_verts <3) return;

        // make a polyscone from these vertex indices.

        const BSP_FaceInd fi = m_faces->size();
        m_faces->push_back(BSP_MFace());                        
        BSP_MFace & face = m_faces->back();

        insert_iterator<vector<BSP_VertexInd> > insert_point(face.m_verts,face.m_verts.end()); 
        copy (verts,verts + num_verts,insert_point);

        // compute and store the plane equation for this face.

        MT_Plane3 face_plane = FacePlane(fi);   
        face.m_plane = face_plane;
};

// assumes that the face already has a plane equation
        void
BSP_CSGMesh::
AddPolygon(
        const BSP_MFace &face
){
        m_faces->push_back(face);                       
};


        bool
BSP_CSGMesh::
BuildEdges(
){

        if (m_faces == NULL) return false;

        if (m_edges != NULL) {
                DestroyEdges();
        }

        m_edges = new vector<BSP_MEdge>;

        if (m_edges == NULL) {
                return false;
        }
                

        //iterate through the face set and add edges for all polygon
        //edges
        
        vector<BSP_MFace>::const_iterator f_it_end = FaceSet().end();
        vector<BSP_MFace>::iterator f_it_begin = FaceSet().begin();
        vector<BSP_MFace>::iterator f_it = FaceSet().begin();

        vector<BSP_EdgeInd> dummy;

        for (;f_it != f_it_end; ++f_it) {

                BSP_MFace & face = *f_it;

                int vertex_num = face.m_verts.size();
                BSP_VertexInd prev_vi(face.m_verts[vertex_num-1]);

                for (int vert = 0; vert < vertex_num; ++vert) {

                        BSP_FaceInd fi(size_t (f_it - f_it_begin));
                        InsertEdge(prev_vi,face.m_verts[vert],fi,dummy);
                        prev_vi = face.m_verts[vert];
                }
                        
        }
        dummy.clear();
        return true;
}       
                
        void
BSP_CSGMesh::
DestroyEdges(
){
        if ( m_edges != NULL ) {
                delete m_edges;
                m_edges = NULL;
        }       
        
        // Run through the vertices
        // and clear their edge arrays.

        if (m_verts){

                vector<BSP_MVertex>::const_iterator vertex_end = VertexSet().end();
                vector<BSP_MVertex>::iterator vertex_it = VertexSet().begin();

                for (; vertex_it != vertex_end; ++vertex_it) {
                        vertex_it->m_edges.clear();
                }
        }
}


        BSP_EdgeInd
BSP_CSGMesh::
FindEdge(
        const BSP_VertexInd & v1,
        const BSP_VertexInd & v2
) const {
        
        vector<BSP_MVertex> &verts = VertexSet();
        vector<BSP_MEdge> &edges = EdgeSet();

        BSP_MEdge e;
        e.m_verts[0] = v1;
        e.m_verts[1] = v2;
        
        vector<BSP_EdgeInd> &v1_edges = verts[v1].m_edges;
        vector<BSP_EdgeInd>::const_iterator v1_end = v1_edges.end();
        vector<BSP_EdgeInd>::const_iterator v1_begin = v1_edges.begin();

        for (; v1_begin != v1_end; ++v1_begin) {
                if (edges[*v1_begin] == e) return *v1_begin;
        }
        
        return BSP_EdgeInd::Empty();
}

        void
BSP_CSGMesh::
InsertEdge(
        const BSP_VertexInd & v1,
        const BSP_VertexInd & v2,
        const BSP_FaceInd & f,
        vector<BSP_EdgeInd> &new_edges
){

        MT_assert(!v1.IsEmpty());
        MT_assert(!v2.IsEmpty());
        MT_assert(!f.IsEmpty());

        if (v1.IsEmpty() || v2.IsEmpty() || f.IsEmpty()) {
                BSP_CSGException e(e_mesh_error);
                throw (e);
        }

        vector<BSP_MVertex> &verts = VertexSet();
        vector<BSP_MEdge> &edges = EdgeSet();
        
        BSP_EdgeInd e;

        e = FindEdge(v1,v2);
        if (e.IsEmpty()) {
                // This edge does not exist -- make a new one 

                BSP_MEdge temp_e;
                temp_e.m_verts[0] = v1;
                temp_e.m_verts[1] = v2;

                e = m_edges->size();
                // set the face index from the edge back to this polygon.
                temp_e.m_faces.push_back(f);

                m_edges->push_back(temp_e);

                // add the edge index to it's vertices 
                verts[v1].AddEdge(e);
                verts[v2].AddEdge(e);

                new_edges.push_back(e);

        } else {

                // edge already exists
                // insure that there is no polygon already
                // attached to the other side of this edge
                // swap the empty face pointer in edge with f

                BSP_MEdge &edge = edges[e];

                // set the face index from the edge back to this polygon.
                edge.m_faces.push_back(f);
        }
}               


// geometry access

        vector<BSP_MVertex> &
BSP_CSGMesh::
VertexSet(
) const {
        return *m_verts;
}               

        vector<BSP_MFace> &
BSP_CSGMesh::
FaceSet(
) const {
        return *m_faces;
}

        vector<BSP_MEdge> &
BSP_CSGMesh::
EdgeSet(
) const {
        return *m_edges;
}

BSP_CSGMesh::
~BSP_CSGMesh(
){
        if ( m_verts != NULL ) delete m_verts;
        if ( m_faces != NULL ) delete m_faces;
        if ( m_edges != NULL ) delete m_edges;
}

// local geometry queries.

// face queries

        void
BSP_CSGMesh::
FaceVertices(
        const BSP_FaceInd & f,
        vector<BSP_VertexInd> &output
){
        vector<BSP_MFace> & face_set = FaceSet();
        output.insert(
                output.end(),
                face_set[f].m_verts.begin(),
                face_set[f].m_verts.end()
        );
}


        void
BSP_CSGMesh::
FaceEdges(
        const BSP_FaceInd & fi,
        vector<BSP_EdgeInd> &output
){
        // take intersection of the edges emminating from all the vertices
        // of this polygon;

        vector<BSP_MFace> &faces = FaceSet();
        vector<BSP_MEdge> &edges = EdgeSet();

        const BSP_MFace & f = faces[fi];

        // collect vertex edges;

        vector<BSP_VertexInd>::const_iterator face_verts_it = f.m_verts.begin();
        vector<BSP_VertexInd>::const_iterator face_verts_end = f.m_verts.end();

        vector< vector<BSP_EdgeInd> > vertex_edges(f.m_verts.size());
                
        int vector_slot = 0;

        for (;face_verts_it != face_verts_end; ++face_verts_it, ++vector_slot) {
                VertexEdges(*face_verts_it,vertex_edges[vector_slot]);
        }       

        int prev = vector_slot - 1; 

        // intersect pairs of edge sets 

        for (int i = 0; i < vector_slot;i++) {
                CTR_TaggedSetOps<BSP_EdgeInd,BSP_MEdge>::IntersectPair(vertex_edges[prev],vertex_edges[i],edges,output);        
                prev = i;
        }
        
        // should always have 3 or more unique edges per face.
        MT_assert(output.size() >=3);

        if (output.size() < 3) {
                BSP_CSGException e(e_mesh_error);
                throw(e);
        }
};
        
// edge queries

        void
BSP_CSGMesh::
EdgeVertices(
        const BSP_EdgeInd & e,
        vector<BSP_VertexInd> &output
){
        const vector<BSP_MEdge> &edges = EdgeSet();
        output.push_back(edges[e].m_verts[0]);
        output.push_back(edges[e].m_verts[1]);
} 

        void
BSP_CSGMesh::
EdgeFaces(
        const BSP_EdgeInd & e,
        vector<BSP_FaceInd> &output
){

        vector<BSP_MEdge> & edge_set = EdgeSet();
        output.insert(
                output.end(),
                edge_set[e].m_faces.begin(),
                edge_set[e].m_faces.end()
        );
        
}

// vertex queries

        void
BSP_CSGMesh::
VertexEdges(
        const BSP_VertexInd &v,
        vector<BSP_EdgeInd> &output
){

        vector<BSP_MVertex> & vertex_set = VertexSet();
        output.insert(
                output.end(),
                vertex_set[v].m_edges.begin(),
                vertex_set[v].m_edges.end()
        );
}

        void
BSP_CSGMesh::
VertexFaces(
        const BSP_VertexInd &vi,
        vector<BSP_FaceInd> &output
) {

        vector<BSP_MEdge> &edges = EdgeSet();
        vector<BSP_MFace> &faces = FaceSet();
        vector<BSP_MVertex> &verts = VertexSet();

        const vector<BSP_EdgeInd> &v_edges = verts[vi].m_edges;
        vector<BSP_EdgeInd>::const_iterator e_it = v_edges.begin();

        for (; e_it != v_edges.end(); ++e_it) {

                BSP_MEdge &e = edges[*e_it]; 

                // iterate through the faces of this edge - push unselected
                // edges to ouput and then select the edge

                vector<BSP_FaceInd>::const_iterator e_faces_end = e.m_faces.end();
                vector<BSP_FaceInd>::iterator e_faces_it = e.m_faces.begin();

                for (;e_faces_it != e_faces_end; ++e_faces_it) {

                        if (!faces[*e_faces_it].SelectTag()) {
                                output.push_back(*e_faces_it);
                                faces[*e_faces_it].SetSelectTag(true);
                        }
                }
        }

        // deselect selected faces.
        vector<BSP_FaceInd>::iterator f_it = output.begin();

        for (; f_it != output.end(); ++f_it) {
                faces[*f_it].SetSelectTag(false);
        }
}

        bool
BSP_CSGMesh::
SC_Face(
        BSP_FaceInd f
){



#if 0
        {
        // check area is greater than zero.

                vector<BSP_MVertex> & verts = VertexSet();

                vector<BSP_VertexInd> f_verts;
                FaceVertices(f,f_verts);

                MT_assert(f_verts.size() >= 3);

                BSP_VertexInd root = f_verts[0];
                
                MT_Scalar area = 0;

                for (int i=2; i < f_verts.size(); i++) {
                        MT_Vector3 a = verts[root].m_pos;
                        MT_Vector3 b = verts[f_verts[i-1]].m_pos;
                        MT_Vector3 c = verts[f_verts[i]].m_pos;

                        MT_Vector3 l1 = b-a;
                        MT_Vector3 l2 = c-b;

                        area += (l1.cross(l2)).length()/2;
                }

                MT_assert(!MT_fuzzyZero(area));
        }
#endif
        // Check coplanarity 
#if 0
        MT_Plane3 plane = FacePlane(f);

        const BSP_MFace & face = FaceSet()[f];
        vector<BSP_VertexInd>::const_iterator f_verts_it = face.m_verts.begin();
        vector<BSP_VertexInd>::const_iterator f_verts_end = face.m_verts.end();

        for (;f_verts_it != f_verts_end; ++f_verts_it) {
                MT_Scalar dist = plane.signedDistance(
                        VertexSet()[*f_verts_it].m_pos
                );

                MT_assert(fabs(dist) < BSP_SPLIT_EPSILON);
        }
#endif


        // Check connectivity

        vector<BSP_EdgeInd> f_edges;    
        FaceEdges(f,f_edges);

        MT_assert(f_edges.size() == FaceSet()[f].m_verts.size());

        unsigned int i;
        for (i = 0; i < f_edges.size(); ++i) {

                int matches = 0;
                for (unsigned int j = 0; j < EdgeSet()[f_edges[i]].m_faces.size(); j++) {

                        if (EdgeSet()[f_edges[i]].m_faces[j] == f) matches++;
                }

                MT_assert(matches == 1);

        }       
        return true;
}       

        MT_Plane3
BSP_CSGMesh::
FacePlane(
        const BSP_FaceInd & fi
) const{

        const BSP_MFace & f0 = FaceSet()[fi];   

        // Have to be a bit careful here coz the poly may have 
        // a lot of parallel edges. Should walk round the polygon
        // and check length of cross product.

        const MT_Vector3 & p1 = VertexSet()[f0.m_verts[0]].m_pos;
        const MT_Vector3 & p2 = VertexSet()[f0.m_verts[1]].m_pos;

        int face_size = f0.m_verts.size();
        MT_Vector3 n;

        for (int i = 2 ; i <face_size; i++) { 
                const MT_Vector3 & pi =  VertexSet()[f0.m_verts[i]].m_pos;
                
                MT_Vector3 l1 = p2-p1;
                MT_Vector3 l2 = pi-p2;
                n = l1.cross(l2);
                MT_Scalar length = n.length();

                if (!MT_fuzzyZero(length)) {
                        n = n * (1/length);
                        break;
                } 
        }
        return MT_Plane3(n,p1);
}

        void
BSP_CSGMesh::
ComputeFacePlanes(
){

        int fsize = FaceSet().size();
        int i=0;
        for (i = 0; i < fsize; i++) {
        
                FaceSet()[i].m_plane = FacePlane(i);
        }
};


        int
BSP_CSGMesh::
CountTriangles(
) const {

        // Each polygon of n sides can be partitioned into n-3 triangles.
        // So we just go through and sum this function of polygon size.
        
        vector<BSP_MFace> & face_set = FaceSet();

        vector<BSP_MFace>::const_iterator face_it = face_set.begin();
        vector<BSP_MFace>::const_iterator face_end = face_set.end();

        int sum = 0;

        for (;face_it != face_end; face_it++) {
        
                // Should be careful about degenerate faces here.
                sum += face_it->m_verts.size() - 2;
        }

        return sum;
}