BOP_Interface.cpp

Go to the documentation of this file.

/*
 * ***** 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 <iostream>
#include <map>
#include "../extern/BOP_Interface.h"
#include "../../bsp/intern/BSP_CSGMesh_CFIterator.h"
#include "BOP_BSPTree.h"
#include "BOP_Mesh.h"
#include "BOP_Face2Face.h"
#include "BOP_Merge.h"
#include "BOP_Merge2.h"
#include "BOP_Chrono.h"

#if defined(BOP_ORIG_MERGE) && defined(BOP_NEW_MERGE) 
#include "../../../source/blender/blenkernel/BKE_global.h"
#endif

BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
                                   BOP_Faces* facesA,
                                   BOP_Faces* facesB,
                                   bool       invertMeshA,
                                   bool       invertMeshB);
BOP_Face3* BOP_createFace(BOP_Mesh* mesh, 
                          BOP_Index vertex1,
                          BOP_Index vertex2,
                          BOP_Index vertex3,
                          BOP_Index origFace);
void BOP_addMesh(BOP_Mesh*                     mesh,
                 BOP_Faces*                    meshFacesId,
                 CSG_FaceIteratorDescriptor&   face_it,
                 CSG_VertexIteratorDescriptor& vertex_it,
                 bool                          invert);
BSP_CSGMesh* BOP_newEmptyMesh();
BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  inputMesh, 
                            bool                       invert);
void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp);
void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted);
void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp);

BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
                                        BSP_CSGMesh**                 outputMesh,
                                        CSG_FaceIteratorDescriptor    obAFaces,
                                        CSG_VertexIteratorDescriptor  obAVertices,
                                        CSG_FaceIteratorDescriptor    obBFaces,
                                        CSG_VertexIteratorDescriptor  obBVertices)
{
    #ifdef BOP_DEBUG
    std::cout << "BEGIN BOP_performBooleanOperation" << std::endl;
    #endif

    // Set invert flags depending on boolean operation type:
    // INTERSECTION: A^B = and(A,B)
    // UNION:        A|B = not(and(not(A),not(B)))
    // DIFFERENCE:   A-B = and(A,not(B))
    bool invertMeshA = (opType == BOP_UNION);
    bool invertMeshB = (opType != BOP_INTERSECTION);
    bool invertMeshC = (opType == BOP_UNION);
    
    // Faces list for both objects, used by boolean op.
    BOP_Faces meshAFacesId;
    BOP_Faces meshBFacesId;
    
    // Build C-mesh, the output mesh
    BOP_Mesh meshC;

    // Add A-mesh into C-mesh
    BOP_addMesh(&meshC, &meshAFacesId, obAFaces, obAVertices, invertMeshA);

    // Add B-mesh into C-mesh
    BOP_addMesh(&meshC, &meshBFacesId, obBFaces, obBVertices, invertMeshB);

    // for now, allow operations on non-manifold (non-solid) meshes
#if 0
    if (!meshC.isClosedMesh())
        return BOP_NO_SOLID;
#endif

    // Perform the intersection boolean operation.
    BoolOpState result = BOP_intersectionBoolOp(&meshC, &meshAFacesId, &meshBFacesId, 
                                                invertMeshA, invertMeshB);

    // Invert the output mesh if is required
    *outputMesh = BOP_exportMesh(&meshC, invertMeshC);

    #ifdef BOP_DEBUG
    std::cout << "END BOP_performBooleanOperation" << std::endl;
    #endif
    
    return result;
}

BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
                                   BOP_Faces* facesA,
                                   BOP_Faces* facesB,
                                   bool       invertMeshA,
                                   bool       invertMeshB)
{
    #ifdef BOP_DEBUG
    BOP_Chrono chrono;
    float t = 0.0f;
    float c = 0.0f;
    chrono.start();  
    std::cout << "---" << std::endl;
    #endif

    // Create BSPs trees for mesh A & B
    BOP_BSPTree bspA;
    bspA.addMesh(meshC, *facesA);

    BOP_BSPTree bspB;
    bspB.addMesh(meshC, *facesB);

    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "Create BSP     " << c << std::endl;   
    #endif

    unsigned int numVertices = meshC->getNumVertexs();
    
    // mesh pre-filter
    BOP_simplifiedMeshFilter(meshC, facesA, &bspB, invertMeshB);
    if ((0.25*facesA->size()) > bspB.getDeep())
      BOP_meshFilter(meshC, facesA, &bspB);

    BOP_simplifiedMeshFilter(meshC, facesB, &bspA, invertMeshA);
    if ((0.25*facesB->size()) > bspA.getDeep())
      BOP_meshFilter(meshC, facesB, &bspA);
    
    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "mesh Filter    " << c << std::endl;   
    #endif

    // Face 2 Face
    BOP_Face2Face(meshC,facesA,facesB);

    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "Face2Face      " << c << std::endl;
    #endif

    // BSP classification
    BOP_meshClassify(meshC,facesA,&bspB);
    BOP_meshClassify(meshC,facesB,&bspA);
    
    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "Classification " << c << std::endl;
    #endif
    
    // Process overlapped faces
    BOP_removeOverlappedFaces(meshC,facesA,facesB);
    
    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "Remove overlap " << c << std::endl;
    #endif

    // Sew two meshes
    BOP_sew(meshC,facesA,facesB);

    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "Sew            " << c << std::endl;
    #endif

    // Merge faces
#ifdef BOP_ORIG_MERGE
#ifndef BOP_NEW_MERGE
    BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
#endif
#endif

#ifdef BOP_NEW_MERGE
#ifndef BOP_ORIG_MERGE
    BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
#else
    static int state = -1;
    if (G.rt == 100) {
        if( state != 1 ) {
            std::cout << "Boolean code using old merge technique." << std::endl;
            state = 1;
        }
        BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
    } else {
        if( state != 0 ) {
            std::cout << "Boolean code using new merge technique." << std::endl;
            state = 0;
        }
        BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
    }
#endif
#endif

    #ifdef BOP_DEBUG
    c = chrono.stamp(); t += c;
    std::cout << "Merge faces    " << c << std::endl;
    std::cout << "Total          " << t << std::endl;
    // Test integrity
    meshC->testMesh();
    #endif
    
    return BOP_OK;
}

void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
{
    BOP_IT_Faces it;
    BOP_TAG tag;
    
    it = faces->begin();
    while (it!=faces->end()) {
        BOP_Face *face = *it;
        MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
        MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
        MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
        if ((tag = bsp->classifyFace(p1,p2,p3,face->getPlane()))==OUT||tag==OUTON) {
            face->setTAG(BROKEN);
            it = faces->erase(it);
        }
        else if (tag == IN) {
            it = faces->erase(it);
        }else{
          it++;
        }
    }
}

void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted)
{
    BOP_IT_Faces it;
    
    it = faces->begin();
    while (it!=faces->end()) {
        BOP_Face *face = *it;
        MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
        MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
        MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
        if (bsp->filterFace(p1,p2,p3,face)==OUT) {
            if (!inverted) face->setTAG(BROKEN);
            it = faces->erase(it);
        }
        else {
            it++;
        }
    }
}

void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
{
    for(BOP_IT_Faces face=faces->begin();face!=faces->end();face++) {
        if ((*face)->getTAG()!=BROKEN) {
            MT_Point3 p1 = meshC->getVertex((*face)->getVertex(0))->getPoint();
            MT_Point3 p2 = meshC->getVertex((*face)->getVertex(1))->getPoint();
            MT_Point3 p3 = meshC->getVertex((*face)->getVertex(2))->getPoint();
            if (bsp->simplifiedClassifyFace(p1,p2,p3,(*face)->getPlane())!=IN) {
                (*face)->setTAG(BROKEN);
            }
        }
    }
}

BOP_Face3 *BOP_createFace3(BOP_Mesh* mesh, 
                           BOP_Index       vertex1, 
                           BOP_Index       vertex2, 
                           BOP_Index       vertex3, 
                           BOP_Index       origFace)
{
    MT_Point3 p1 = mesh->getVertex(vertex1)->getPoint();
    MT_Point3 p2 = mesh->getVertex(vertex2)->getPoint();
    MT_Point3 p3 = mesh->getVertex(vertex3)->getPoint();
    MT_Plane3 plane(p1,p2,p3);

    return new BOP_Face3(vertex1, vertex2, vertex3, plane, origFace);
}

void BOP_addMesh(BOP_Mesh*                     mesh,
                 BOP_Faces*                    meshFacesId,
                 CSG_FaceIteratorDescriptor&   face_it,
                 CSG_VertexIteratorDescriptor& vertex_it,
                 bool                          invert)
{
    unsigned int vtxIndexOffset = mesh->getNumVertexs();

    // The size of the vertex data array will be at least the number of faces.
    CSG_IVertex vertex;
    while (!vertex_it.Done(vertex_it.it)) {
        vertex_it.Fill(vertex_it.it,&vertex);
        MT_Point3 pos(vertex.position);
        mesh->addVertex(pos);
        vertex_it.Step(vertex_it.it);
    }

    CSG_IFace face;
    
    // now for the polygons.
    // we may need to decalare some memory for user defined face properties.

    BOP_Face3 *newface;
    
    while (!face_it.Done(face_it.it)) {
        face_it.Fill(face_it.it,&face);

        // Let's not rely on quads being coplanar - especially if they 
        // are coming out of that soup of code from blender...
        if (face.vertex_number == 4){
            // QUAD
            if (invert) {
                newface = BOP_createFace3(mesh,
                                          face.vertex_index[2] + vtxIndexOffset,
                                          face.vertex_index[0] + vtxIndexOffset,
                                          face.vertex_index[3] + vtxIndexOffset,
                                          face.orig_face);
                meshFacesId->push_back(newface);
                mesh->addFace(newface);
                newface = BOP_createFace3(mesh,
                                          face.vertex_index[2] + vtxIndexOffset,
                                          face.vertex_index[1] + vtxIndexOffset,
                                          face.vertex_index[0] + vtxIndexOffset,
                                          face.orig_face);
                meshFacesId->push_back(newface);
                mesh->addFace(newface);
            }
            else {
                newface = BOP_createFace3(mesh,
                                         face.vertex_index[0] + vtxIndexOffset,
                                         face.vertex_index[2] + vtxIndexOffset,
                                         face.vertex_index[3] + vtxIndexOffset,
                                         face.orig_face);
                meshFacesId->push_back(newface);
                mesh->addFace(newface);
                newface = BOP_createFace3(mesh,
                                         face.vertex_index[0] + vtxIndexOffset,
                                         face.vertex_index[1] + vtxIndexOffset,
                                         face.vertex_index[2] + vtxIndexOffset,
                                         face.orig_face);
                meshFacesId->push_back(newface);
                mesh->addFace(newface);
            }
        }
        else {
            // TRIANGLES
            if (invert) {
                newface = BOP_createFace3(mesh,
                                          face.vertex_index[2] + vtxIndexOffset,
                                          face.vertex_index[1] + vtxIndexOffset,
                                          face.vertex_index[0] + vtxIndexOffset,
                                          face.orig_face);
                meshFacesId->push_back(newface);
                mesh->addFace(newface);
            }
            else {
                newface = BOP_createFace3(mesh,
                                          face.vertex_index[0] + vtxIndexOffset,
                                          face.vertex_index[1] + vtxIndexOffset,
                                          face.vertex_index[2] + vtxIndexOffset,
                                          face.orig_face);
                meshFacesId->push_back(newface);
                mesh->addFace(newface);
            }
        }
        
        face_it.Step(face_it.it);
    }
}

BSP_CSGMesh* BOP_newEmptyMesh()
{
    BSP_CSGMesh* mesh = BSP_CSGMesh::New();
    if (mesh == NULL) return mesh;

    std::vector<BSP_MVertex>* vertices = new std::vector<BSP_MVertex>;
    
    mesh->SetVertices(vertices);

    return mesh;
}

BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  mesh, 
                            bool                       invert)
{
    BSP_CSGMesh* outputMesh = BOP_newEmptyMesh();

    if (outputMesh == NULL) return NULL;

    // vtx index dictionary, to translate indeces from input to output.
    std::map<int,unsigned int> dic;
    std::map<int,unsigned int>::iterator itDic;

    unsigned int count = 0;

    // Add a new face for each face in the input list
    BOP_Faces faces = mesh->getFaces();
    BOP_Vertexs vertexs = mesh->getVertexs();

    for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
        if ((*face)->getTAG()!=BROKEN){    
            // Add output face
            outputMesh->FaceSet().push_back(BSP_MFace());
            BSP_MFace& outFace = outputMesh->FaceSet().back();

            // Copy face
            outFace.m_verts.clear();
            outFace.m_plane = (*face)->getPlane();
            outFace.m_orig_face = (*face)->getOriginalFace();

            // invert face if is required
            if (invert) (*face)->invert();
            
            // Add the face vertex if not added yet
            for (unsigned int pos=0;pos<(*face)->size();pos++) {
                BSP_VertexInd outVtxId;
                BOP_Index idVertex = (*face)->getVertex(pos);
                itDic = dic.find(idVertex);
                if (itDic == dic.end()) {
                    // The vertex isn't added yet
                    outVtxId = BSP_VertexInd(outputMesh->VertexSet().size());
                    BSP_MVertex outVtx((mesh->getVertex(idVertex))->getPoint());
                    outVtx.m_edges.clear();
                    outputMesh->VertexSet().push_back(outVtx);
                    dic[idVertex] = outVtxId;
                    count++;
                }
                else {
                    // The vertex is added
                    outVtxId = BSP_VertexInd(itDic->second);
                }

                outFace.m_verts.push_back(outVtxId);
            }
        }
    }
    
    // Build the mesh edges using topological informtion
    outputMesh->BuildEdges();
    
    return outputMesh;
}