|
Blender
V2.59
|
00001 /* 00002 * ***** BEGIN GPL LICENSE BLOCK ***** 00003 * 00004 * This program is free software; you can redistribute it and/or 00005 * modify it under the terms of the GNU General Public License 00006 * as published by the Free Software Foundation; either version 2 00007 * of the License, or (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software Foundation, 00016 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 00017 * 00018 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. 00019 * All rights reserved. 00020 * 00021 * The Original Code is: all of this file. 00022 * 00023 * Contributor(s): none yet. 00024 * 00025 * ***** END GPL LICENSE BLOCK ***** 00026 */ 00027 00033 #include <iostream> 00034 #include <map> 00035 #include "../extern/BOP_Interface.h" 00036 #include "../../bsp/intern/BSP_CSGMesh_CFIterator.h" 00037 #include "BOP_BSPTree.h" 00038 #include "BOP_Mesh.h" 00039 #include "BOP_Face2Face.h" 00040 #include "BOP_Merge.h" 00041 #include "BOP_Merge2.h" 00042 #include "BOP_Chrono.h" 00043 00044 #if defined(BOP_ORIG_MERGE) && defined(BOP_NEW_MERGE) 00045 #include "../../../source/blender/blenkernel/BKE_global.h" 00046 #endif 00047 00048 BoolOpState BOP_intersectionBoolOp(BOP_Mesh* meshC, 00049 BOP_Faces* facesA, 00050 BOP_Faces* facesB, 00051 bool invertMeshA, 00052 bool invertMeshB); 00053 BOP_Face3* BOP_createFace(BOP_Mesh* mesh, 00054 BOP_Index vertex1, 00055 BOP_Index vertex2, 00056 BOP_Index vertex3, 00057 BOP_Index origFace); 00058 void BOP_addMesh(BOP_Mesh* mesh, 00059 BOP_Faces* meshFacesId, 00060 CSG_FaceIteratorDescriptor& face_it, 00061 CSG_VertexIteratorDescriptor& vertex_it, 00062 bool invert); 00063 BSP_CSGMesh* BOP_newEmptyMesh(); 00064 BSP_CSGMesh* BOP_exportMesh(BOP_Mesh* inputMesh, 00065 bool invert); 00066 void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp); 00067 void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted); 00068 void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp); 00069 00081 BoolOpState BOP_performBooleanOperation(BoolOpType opType, 00082 BSP_CSGMesh** outputMesh, 00083 CSG_FaceIteratorDescriptor obAFaces, 00084 CSG_VertexIteratorDescriptor obAVertices, 00085 CSG_FaceIteratorDescriptor obBFaces, 00086 CSG_VertexIteratorDescriptor obBVertices) 00087 { 00088 #ifdef BOP_DEBUG 00089 cout << "BEGIN BOP_performBooleanOperation" << endl; 00090 #endif 00091 00092 // Set invert flags depending on boolean operation type: 00093 // INTERSECTION: A^B = and(A,B) 00094 // UNION: A|B = not(and(not(A),not(B))) 00095 // DIFFERENCE: A-B = and(A,not(B)) 00096 bool invertMeshA = (opType == BOP_UNION); 00097 bool invertMeshB = (opType != BOP_INTERSECTION); 00098 bool invertMeshC = (opType == BOP_UNION); 00099 00100 // Faces list for both objects, used by boolean op. 00101 BOP_Faces meshAFacesId; 00102 BOP_Faces meshBFacesId; 00103 00104 // Build C-mesh, the output mesh 00105 BOP_Mesh meshC; 00106 00107 // Add A-mesh into C-mesh 00108 BOP_addMesh(&meshC, &meshAFacesId, obAFaces, obAVertices, invertMeshA); 00109 00110 // Add B-mesh into C-mesh 00111 BOP_addMesh(&meshC, &meshBFacesId, obBFaces, obBVertices, invertMeshB); 00112 00113 // for now, allow operations on non-manifold (non-solid) meshes 00114 #if 0 00115 if (!meshC.isClosedMesh()) 00116 return BOP_NO_SOLID; 00117 #endif 00118 00119 // Perform the intersection boolean operation. 00120 BoolOpState result = BOP_intersectionBoolOp(&meshC, &meshAFacesId, &meshBFacesId, 00121 invertMeshA, invertMeshB); 00122 00123 // Invert the output mesh if is required 00124 *outputMesh = BOP_exportMesh(&meshC, invertMeshC); 00125 00126 #ifdef BOP_DEBUG 00127 cout << "END BOP_performBooleanOperation" << endl; 00128 #endif 00129 00130 return result; 00131 } 00132 00143 BoolOpState BOP_intersectionBoolOp(BOP_Mesh* meshC, 00144 BOP_Faces* facesA, 00145 BOP_Faces* facesB, 00146 bool invertMeshA, 00147 bool invertMeshB) 00148 { 00149 #ifdef BOP_DEBUG 00150 BOP_Chrono chrono; 00151 float t = 0.0f; 00152 float c = 0.0f; 00153 chrono.start(); 00154 cout << "---" << endl; 00155 #endif 00156 00157 // Create BSPs trees for mesh A & B 00158 BOP_BSPTree bspA; 00159 bspA.addMesh(meshC, *facesA); 00160 00161 BOP_BSPTree bspB; 00162 bspB.addMesh(meshC, *facesB); 00163 00164 #ifdef BOP_DEBUG 00165 c = chrono.stamp(); t += c; 00166 cout << "Create BSP " << c << endl; 00167 #endif 00168 00169 unsigned int numVertices = meshC->getNumVertexs(); 00170 00171 // mesh pre-filter 00172 BOP_simplifiedMeshFilter(meshC, facesA, &bspB, invertMeshB); 00173 if ((0.25*facesA->size()) > bspB.getDeep()) 00174 BOP_meshFilter(meshC, facesA, &bspB); 00175 00176 BOP_simplifiedMeshFilter(meshC, facesB, &bspA, invertMeshA); 00177 if ((0.25*facesB->size()) > bspA.getDeep()) 00178 BOP_meshFilter(meshC, facesB, &bspA); 00179 00180 #ifdef BOP_DEBUG 00181 c = chrono.stamp(); t += c; 00182 cout << "mesh Filter " << c << endl; 00183 #endif 00184 00185 // Face 2 Face 00186 BOP_Face2Face(meshC,facesA,facesB); 00187 00188 #ifdef BOP_DEBUG 00189 c = chrono.stamp(); t += c; 00190 cout << "Face2Face " << c << endl; 00191 #endif 00192 00193 // BSP classification 00194 BOP_meshClassify(meshC,facesA,&bspB); 00195 BOP_meshClassify(meshC,facesB,&bspA); 00196 00197 #ifdef BOP_DEBUG 00198 c = chrono.stamp(); t += c; 00199 cout << "Classification " << c << endl; 00200 #endif 00201 00202 // Process overlapped faces 00203 BOP_removeOverlappedFaces(meshC,facesA,facesB); 00204 00205 #ifdef BOP_DEBUG 00206 c = chrono.stamp(); t += c; 00207 cout << "Remove overlap " << c << endl; 00208 #endif 00209 00210 // Sew two meshes 00211 BOP_sew(meshC,facesA,facesB); 00212 00213 #ifdef BOP_DEBUG 00214 c = chrono.stamp(); t += c; 00215 cout << "Sew " << c << endl; 00216 #endif 00217 00218 // Merge faces 00219 #ifdef BOP_ORIG_MERGE 00220 #ifndef BOP_NEW_MERGE 00221 BOP_Merge::getInstance().mergeFaces(meshC,numVertices); 00222 #endif 00223 #endif 00224 00225 #ifdef BOP_NEW_MERGE 00226 #ifndef BOP_ORIG_MERGE 00227 BOP_Merge2::getInstance().mergeFaces(meshC,numVertices); 00228 #else 00229 static int state = -1; 00230 if (G.rt == 100) { 00231 if( state != 1 ) { 00232 cout << "Boolean code using old merge technique." << endl; 00233 state = 1; 00234 } 00235 BOP_Merge::getInstance().mergeFaces(meshC,numVertices); 00236 } else { 00237 if( state != 0 ) { 00238 cout << "Boolean code using new merge technique." << endl; 00239 state = 0; 00240 } 00241 BOP_Merge2::getInstance().mergeFaces(meshC,numVertices); 00242 } 00243 #endif 00244 #endif 00245 00246 #ifdef BOP_DEBUG 00247 c = chrono.stamp(); t += c; 00248 cout << "Merge faces " << c << endl; 00249 cout << "Total " << t << endl; 00250 // Test integrity 00251 meshC->testMesh(); 00252 #endif 00253 00254 return BOP_OK; 00255 } 00256 00263 void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp) 00264 { 00265 BOP_IT_Faces it; 00266 BOP_TAG tag; 00267 00268 it = faces->begin(); 00269 while (it!=faces->end()) { 00270 BOP_Face *face = *it; 00271 MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint(); 00272 MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint(); 00273 MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint(); 00274 if ((tag = bsp->classifyFace(p1,p2,p3,face->getPlane()))==OUT||tag==OUTON) { 00275 face->setTAG(BROKEN); 00276 it = faces->erase(it); 00277 } 00278 else if (tag == IN) { 00279 it = faces->erase(it); 00280 }else{ 00281 it++; 00282 } 00283 } 00284 } 00285 00293 void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted) 00294 { 00295 BOP_IT_Faces it; 00296 00297 it = faces->begin(); 00298 while (it!=faces->end()) { 00299 BOP_Face *face = *it; 00300 MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint(); 00301 MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint(); 00302 MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint(); 00303 if (bsp->filterFace(p1,p2,p3,face)==OUT) { 00304 if (!inverted) face->setTAG(BROKEN); 00305 it = faces->erase(it); 00306 } 00307 else { 00308 it++; 00309 } 00310 } 00311 } 00312 00319 void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp) 00320 { 00321 for(BOP_IT_Faces face=faces->begin();face!=faces->end();face++) { 00322 if ((*face)->getTAG()!=BROKEN) { 00323 MT_Point3 p1 = meshC->getVertex((*face)->getVertex(0))->getPoint(); 00324 MT_Point3 p2 = meshC->getVertex((*face)->getVertex(1))->getPoint(); 00325 MT_Point3 p3 = meshC->getVertex((*face)->getVertex(2))->getPoint(); 00326 if (bsp->simplifiedClassifyFace(p1,p2,p3,(*face)->getPlane())!=IN) { 00327 (*face)->setTAG(BROKEN); 00328 } 00329 } 00330 } 00331 } 00332 00342 BOP_Face3 *BOP_createFace3(BOP_Mesh* mesh, 00343 BOP_Index vertex1, 00344 BOP_Index vertex2, 00345 BOP_Index vertex3, 00346 BOP_Index origFace) 00347 { 00348 MT_Point3 p1 = mesh->getVertex(vertex1)->getPoint(); 00349 MT_Point3 p2 = mesh->getVertex(vertex2)->getPoint(); 00350 MT_Point3 p3 = mesh->getVertex(vertex3)->getPoint(); 00351 MT_Plane3 plane(p1,p2,p3); 00352 00353 return new BOP_Face3(vertex1, vertex2, vertex3, plane, origFace); 00354 } 00355 00364 void BOP_addMesh(BOP_Mesh* mesh, 00365 BOP_Faces* meshFacesId, 00366 CSG_FaceIteratorDescriptor& face_it, 00367 CSG_VertexIteratorDescriptor& vertex_it, 00368 bool invert) 00369 { 00370 unsigned int vtxIndexOffset = mesh->getNumVertexs(); 00371 00372 // The size of the vertex data array will be at least the number of faces. 00373 CSG_IVertex vertex; 00374 while (!vertex_it.Done(vertex_it.it)) { 00375 vertex_it.Fill(vertex_it.it,&vertex); 00376 MT_Point3 pos(vertex.position); 00377 mesh->addVertex(pos); 00378 vertex_it.Step(vertex_it.it); 00379 } 00380 00381 CSG_IFace face; 00382 00383 // now for the polygons. 00384 // we may need to decalare some memory for user defined face properties. 00385 00386 BOP_Face3 *newface; 00387 00388 while (!face_it.Done(face_it.it)) { 00389 face_it.Fill(face_it.it,&face); 00390 00391 // Let's not rely on quads being coplanar - especially if they 00392 // are coming out of that soup of code from blender... 00393 if (face.vertex_number == 4){ 00394 // QUAD 00395 if (invert) { 00396 newface = BOP_createFace3(mesh, 00397 face.vertex_index[2] + vtxIndexOffset, 00398 face.vertex_index[0] + vtxIndexOffset, 00399 face.vertex_index[3] + vtxIndexOffset, 00400 face.orig_face); 00401 meshFacesId->push_back(newface); 00402 mesh->addFace(newface); 00403 newface = BOP_createFace3(mesh, 00404 face.vertex_index[2] + vtxIndexOffset, 00405 face.vertex_index[1] + vtxIndexOffset, 00406 face.vertex_index[0] + vtxIndexOffset, 00407 face.orig_face); 00408 meshFacesId->push_back(newface); 00409 mesh->addFace(newface); 00410 } 00411 else { 00412 newface = BOP_createFace3(mesh, 00413 face.vertex_index[0] + vtxIndexOffset, 00414 face.vertex_index[2] + vtxIndexOffset, 00415 face.vertex_index[3] + vtxIndexOffset, 00416 face.orig_face); 00417 meshFacesId->push_back(newface); 00418 mesh->addFace(newface); 00419 newface = BOP_createFace3(mesh, 00420 face.vertex_index[0] + vtxIndexOffset, 00421 face.vertex_index[1] + vtxIndexOffset, 00422 face.vertex_index[2] + vtxIndexOffset, 00423 face.orig_face); 00424 meshFacesId->push_back(newface); 00425 mesh->addFace(newface); 00426 } 00427 } 00428 else { 00429 // TRIANGLES 00430 if (invert) { 00431 newface = BOP_createFace3(mesh, 00432 face.vertex_index[2] + vtxIndexOffset, 00433 face.vertex_index[1] + vtxIndexOffset, 00434 face.vertex_index[0] + vtxIndexOffset, 00435 face.orig_face); 00436 meshFacesId->push_back(newface); 00437 mesh->addFace(newface); 00438 } 00439 else { 00440 newface = BOP_createFace3(mesh, 00441 face.vertex_index[0] + vtxIndexOffset, 00442 face.vertex_index[1] + vtxIndexOffset, 00443 face.vertex_index[2] + vtxIndexOffset, 00444 face.orig_face); 00445 meshFacesId->push_back(newface); 00446 mesh->addFace(newface); 00447 } 00448 } 00449 00450 face_it.Step(face_it.it); 00451 } 00452 } 00453 00458 BSP_CSGMesh* BOP_newEmptyMesh() 00459 { 00460 BSP_CSGMesh* mesh = BSP_CSGMesh::New(); 00461 if (mesh == NULL) return mesh; 00462 00463 vector<BSP_MVertex>* vertices = new vector<BSP_MVertex>; 00464 00465 mesh->SetVertices(vertices); 00466 00467 return mesh; 00468 } 00469 00476 BSP_CSGMesh* BOP_exportMesh(BOP_Mesh* mesh, 00477 bool invert) 00478 { 00479 BSP_CSGMesh* outputMesh = BOP_newEmptyMesh(); 00480 00481 if (outputMesh == NULL) return NULL; 00482 00483 // vtx index dictionary, to translate indeces from input to output. 00484 map<int,unsigned int> dic; 00485 map<int,unsigned int>::iterator itDic; 00486 00487 unsigned int count = 0; 00488 00489 // Add a new face for each face in the input list 00490 BOP_Faces faces = mesh->getFaces(); 00491 BOP_Vertexs vertexs = mesh->getVertexs(); 00492 00493 for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) { 00494 if ((*face)->getTAG()!=BROKEN){ 00495 // Add output face 00496 outputMesh->FaceSet().push_back(BSP_MFace()); 00497 BSP_MFace& outFace = outputMesh->FaceSet().back(); 00498 00499 // Copy face 00500 outFace.m_verts.clear(); 00501 outFace.m_plane = (*face)->getPlane(); 00502 outFace.m_orig_face = (*face)->getOriginalFace(); 00503 00504 // invert face if is required 00505 if (invert) (*face)->invert(); 00506 00507 // Add the face vertex if not added yet 00508 for (unsigned int pos=0;pos<(*face)->size();pos++) { 00509 BSP_VertexInd outVtxId; 00510 BOP_Index idVertex = (*face)->getVertex(pos); 00511 itDic = dic.find(idVertex); 00512 if (itDic == dic.end()) { 00513 // The vertex isn't added yet 00514 outVtxId = BSP_VertexInd(outputMesh->VertexSet().size()); 00515 BSP_MVertex outVtx((mesh->getVertex(idVertex))->getPoint()); 00516 outVtx.m_edges.clear(); 00517 outputMesh->VertexSet().push_back(outVtx); 00518 dic[idVertex] = outVtxId; 00519 count++; 00520 } 00521 else { 00522 // The vertex is added 00523 outVtxId = BSP_VertexInd(itDic->second); 00524 } 00525 00526 outFace.m_verts.push_back(outVtxId); 00527 } 00528 } 00529 } 00530 00531 // Build the mesh edges using topological informtion 00532 outputMesh->BuildEdges(); 00533 00534 return outputMesh; 00535 }