 |
Blender V2.61 - r43446
|
BOP_Triangulator.cpp
Go to the documentation of this file.
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 "BOP_Triangulator.h" 00034 #include <iostream> 00035 00036 void BOP_addFace(BOP_Mesh* mesh, BOP_Faces *faces, BOP_Face* face, BOP_TAG tag); 00037 void BOP_splitQuad(BOP_Mesh* mesh, MT_Plane3 plane, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, 00038 BOP_Face* triangles[], BOP_Index original); 00039 BOP_Index BOP_getTriangleVertex(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4); 00040 BOP_Index BOP_getNearestVertex(BOP_Mesh* mesh, BOP_Index u, BOP_Index v1, BOP_Index v2); 00041 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5); 00042 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index w); 00043 void BOP_triangulateC_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 00044 BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5); 00045 void BOP_triangulateD_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 00046 BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5); 00047 00067 void BOP_triangulateA(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face * face, BOP_Index v, unsigned int e) 00068 { 00069 BOP_Face *face1, *face2; 00070 if (e == 1) { 00071 face1 = new BOP_Face3(face->getVertex(0), v, face->getVertex(2), face->getPlane(), 00072 face->getOriginalFace()); 00073 face2 = new BOP_Face3(v, face->getVertex(1), face->getVertex(2), face->getPlane(), 00074 face->getOriginalFace()); 00075 } 00076 else if (e == 2) { 00077 face1 = new BOP_Face3(face->getVertex(0), face->getVertex(1), v, face->getPlane(), 00078 face->getOriginalFace()); 00079 face2 = new BOP_Face3(face->getVertex(0), v, face->getVertex(2), face->getPlane(), 00080 face->getOriginalFace()); 00081 } 00082 else if (e == 3) { 00083 face1 = new BOP_Face3(face->getVertex(0), face->getVertex(1), v, face->getPlane(), 00084 face->getOriginalFace()); 00085 face2 = new BOP_Face3(face->getVertex(1), face->getVertex(2), v, face->getPlane(), 00086 face->getOriginalFace()); 00087 } 00088 else { 00089 return; 00090 } 00091 00092 BOP_addFace(mesh, faces, face1, face->getTAG()); 00093 BOP_addFace(mesh, faces, face2, face->getTAG()); 00094 face1->setSplit(face->getSplit()); 00095 face2->setSplit(face->getSplit()); 00096 00097 face->setTAG(BROKEN); 00098 face->freeBBox(); 00099 } 00100 00117 void BOP_triangulateB(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_Index v) 00118 { 00119 BOP_Face *face1 = new BOP_Face3(face->getVertex(0), face->getVertex(1), v, face->getPlane(), 00120 face->getOriginalFace()); 00121 BOP_Face *face2 = new BOP_Face3(face->getVertex(1), face->getVertex(2), v, face->getPlane(), 00122 face->getOriginalFace()); 00123 BOP_Face *face3 = new BOP_Face3(face->getVertex(2), face->getVertex(0), v, face->getPlane(), 00124 face->getOriginalFace()); 00125 00126 BOP_addFace(mesh,faces,face1,face->getTAG()); 00127 BOP_addFace(mesh,faces,face2,face->getTAG()); 00128 BOP_addFace(mesh,faces,face3,face->getTAG()); 00129 face1->setSplit(face->getSplit()); 00130 face2->setSplit(face->getSplit()); 00131 face3->setSplit(face->getSplit()); 00132 face->setTAG(BROKEN); 00133 face->freeBBox(); 00134 } 00135 00136 00154 void BOP_triangulateC(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_Index v1, BOP_Index v2) 00155 { 00156 if (!BOP_isInsideCircle(mesh, face->getVertex(0), v1, v2, face->getVertex(1), face->getVertex(2))) { 00157 BOP_triangulateC_split(mesh, faces, face, face->getVertex(0), face->getVertex(1), 00158 face->getVertex(2), v1, v2); 00159 } 00160 else if (!BOP_isInsideCircle(mesh, face->getVertex(1), v1, v2, face->getVertex(0), face->getVertex(2))) { 00161 BOP_triangulateC_split(mesh, faces, face, face->getVertex(1), face->getVertex(2), 00162 face->getVertex(0), v1, v2); 00163 } 00164 else if (!BOP_isInsideCircle(mesh, face->getVertex(2), v1, v2, face->getVertex(0), face->getVertex(1))) { 00165 BOP_triangulateC_split(mesh, faces, face, face->getVertex(2), face->getVertex(0), 00166 face->getVertex(1), v1, v2); 00167 } 00168 else { 00169 BOP_triangulateC_split(mesh, faces, face, face->getVertex(2), face->getVertex(0), 00170 face->getVertex(1), v1, v2); 00171 } 00172 } 00173 00186 void BOP_triangulateC_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 00187 BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5) 00188 { 00189 BOP_Index v = BOP_getTriangleVertex(mesh, v1, v2, v4, v5); 00190 BOP_Index w = (v == v4 ? v5 : v4); 00191 BOP_Face *face1 = new BOP_Face3(v1, v, w, face->getPlane(), face->getOriginalFace()); 00192 BOP_Face *face2 = new BOP_Face3(v1, v2, v, face->getPlane(), face->getOriginalFace()); 00193 BOP_Face *face3 = new BOP_Face3(v1, w, v3, face->getPlane(), face->getOriginalFace()); 00194 00195 // v1 v w defines the nice triangle in the correct order 00196 // v1 v2 v defines one lateral triangle in the correct order 00197 // v1 w v3 defines the other lateral triangle in the correct order 00198 // w v v2 v3 defines the quad in the correct order 00199 00200 BOP_addFace(mesh, faces, face1, face->getTAG()); 00201 BOP_addFace(mesh, faces, face2, face->getTAG()); 00202 BOP_addFace(mesh, faces, face3, face->getTAG()); 00203 00204 face1->setSplit(face->getSplit()); 00205 face2->setSplit(face->getSplit()); 00206 face3->setSplit(face->getSplit()); 00207 00208 BOP_Face *faces45[2]; 00209 00210 BOP_splitQuad(mesh, face->getPlane(), v2, v3, w, v, faces45, face->getOriginalFace()); 00211 BOP_addFace(mesh, faces, faces45[0], face->getTAG()); 00212 BOP_addFace(mesh, faces, faces45[1], face->getTAG()); 00213 faces45[0]->setSplit(face->getSplit()); 00214 faces45[1]->setSplit(face->getSplit()); 00215 00216 face->setTAG(BROKEN); 00217 face->freeBBox(); 00218 } 00219 00220 00239 void BOP_triangulateD(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_Index v1, 00240 BOP_Index v2, unsigned int e) 00241 { 00242 if (e == 1) { 00243 BOP_triangulateD_split(mesh, faces, face, face->getVertex(0), face->getVertex(1), 00244 face->getVertex(2), v1, v2); 00245 } 00246 else if (e == 2) { 00247 BOP_triangulateD_split(mesh, faces, face, face->getVertex(1), face->getVertex(2), 00248 face->getVertex(0), v1, v2); 00249 } 00250 else if (e == 3) { 00251 BOP_triangulateD_split(mesh, faces, face, face->getVertex(2), face->getVertex(0), 00252 face->getVertex(1), v1, v2); 00253 } 00254 } 00255 00267 void BOP_triangulateD_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 00268 BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5) 00269 { 00270 BOP_Index v = BOP_getNearestVertex(mesh, v1, v4, v5); 00271 BOP_Index w = (v == v4 ? v5 : v4); 00272 BOP_Face *face1 = new BOP_Face3(v1, v, v3, face->getPlane(), face->getOriginalFace()); 00273 BOP_Face *face2 = new BOP_Face3(v, w, v3, face->getPlane(), face->getOriginalFace()); 00274 BOP_Face *face3 = new BOP_Face3(w, v2, v3, face->getPlane(), face->getOriginalFace()); 00275 00276 BOP_addFace(mesh, faces, face1, face->getTAG()); 00277 BOP_addFace(mesh, faces, face2, face->getTAG()); 00278 BOP_addFace(mesh, faces, face3, face->getTAG()); 00279 face1->setSplit(face->getSplit()); 00280 face2->setSplit(face->getSplit()); 00281 face3->setSplit(face->getSplit()); 00282 00283 face->setTAG(BROKEN); 00284 face->freeBBox(); 00285 } 00286 00287 00307 void BOP_triangulateE(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 00308 BOP_Index v1, BOP_Index v2, unsigned int e1, unsigned int e2) 00309 { 00310 // Sort the edges to reduce the cases 00311 if (e1 > e2) { 00312 unsigned int aux = e1; 00313 e1 = e2; 00314 e2 = aux; 00315 aux = v1; 00316 v1 = v2; 00317 v2 = aux; 00318 } 00319 // e1 < e2! 00320 BOP_Face *face1; 00321 BOP_Face *faces23[2]; 00322 if (e1 == 1 && e2 == 2) { 00323 // the vertex is 2 00324 face1 = new BOP_Face3(face->getVertex(1), v2, v1, face->getPlane(), 00325 face->getOriginalFace()); 00326 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(2), face->getVertex(0), v1, v2, 00327 faces23, face->getOriginalFace()); 00328 } 00329 else if (e1 == 1 && e2 == 3) { 00330 // the vertex is 1 00331 face1 = new BOP_Face3(face->getVertex(0), v1, v2, face->getPlane(), 00332 face->getOriginalFace()); 00333 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(1), face->getVertex(2), v2, v1, 00334 faces23, face->getOriginalFace()); 00335 } 00336 else if (e1 == 2 && e2 == 3) { 00337 // the vertex is 3 00338 face1 = new BOP_Face3(face->getVertex(2), v2, v1, face->getPlane(), 00339 face->getOriginalFace()); 00340 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(0), face->getVertex(1), v1, v2, 00341 faces23, face->getOriginalFace()); 00342 } 00343 else { 00344 return; 00345 } 00346 00347 BOP_addFace(mesh, faces, face1, face->getTAG()); 00348 BOP_addFace(mesh, faces, faces23[0], face->getTAG()); 00349 BOP_addFace(mesh, faces, faces23[1], face->getTAG()); 00350 face1->setSplit(face->getSplit()); 00351 faces23[0]->setSplit(face->getSplit()); 00352 faces23[1]->setSplit(face->getSplit()); 00353 face->setTAG(BROKEN); 00354 face->freeBBox(); 00355 } 00356 00375 void BOP_triangulateF(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 00376 BOP_Index v1, BOP_Index v2, unsigned int e) 00377 { 00378 BOP_Face *faces12[2]; 00379 BOP_Face *faces34[2]; 00380 if (e == 1) { 00381 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(2), face->getVertex(0), v2, v1, 00382 faces12, face->getOriginalFace()); 00383 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(1), face->getVertex(2), v1, v2, 00384 faces34, face->getOriginalFace()); 00385 } 00386 else if (e == 2) { 00387 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(0), face->getVertex(1), v2, v1, 00388 faces12, face->getOriginalFace()); 00389 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(2), face->getVertex(0), v1, v2, 00390 faces34, face->getOriginalFace()); 00391 } 00392 else if (e==3) { 00393 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(1), face->getVertex(2), v2, v1, 00394 faces12, face->getOriginalFace()); 00395 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(0), face->getVertex(1), v1, v2, 00396 faces34, face->getOriginalFace()); 00397 } 00398 else { 00399 return; 00400 } 00401 00402 BOP_addFace(mesh, faces, faces12[0], face->getTAG()); 00403 BOP_addFace(mesh, faces, faces12[1], face->getTAG()); 00404 BOP_addFace(mesh, faces, faces34[0], face->getTAG()); 00405 BOP_addFace(mesh, faces, faces34[1], face->getTAG()); 00406 faces12[0]->setSplit(face->getSplit()); 00407 faces12[1]->setSplit(face->getSplit()); 00408 faces34[0]->setSplit(face->getSplit()); 00409 faces34[1]->setSplit(face->getSplit()); 00410 00411 face->setTAG(BROKEN); 00412 face->freeBBox(); 00413 } 00414 00422 void BOP_addFace(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_TAG tag) 00423 { 00424 BOP_Index av1 = face->getVertex(0); 00425 BOP_Index av2 = face->getVertex(1); 00426 BOP_Index av3 = face->getVertex(2); 00427 00428 /* 00429 * Before adding a new face to the face list, be sure it's not 00430 * already there. Duplicate faces have been found to cause at 00431 * least two instances of infinite loops. Also, some faces are 00432 * created which have the same vertex twice. Don't add these either. 00433 * 00434 * When someone has more time to look into this issue, it's possible 00435 * this code may be removed again. 00436 */ 00437 if( av1==av2 || av2==av3 || av3==av1 ) return; 00438 00439 for(unsigned int idxFace=0;idxFace<faces->size();idxFace++) { 00440 BOP_Face *faceA = (*faces)[idxFace]; 00441 BOP_Index bv1 = faceA->getVertex(0); 00442 BOP_Index bv2 = faceA->getVertex(1); 00443 BOP_Index bv3 = faceA->getVertex(2); 00444 00445 if( ( av1==bv1 && av2==bv2 && av3==bv3 ) || 00446 ( av1==bv1 && av2==bv3 && av3==bv2 ) || 00447 ( av1==bv2 && av2==bv1 && av3==bv3 ) || 00448 ( av1==bv2 && av2==bv3 && av3==bv1 ) || 00449 ( av1==bv3 && av2==bv2 && av3==bv1 ) || 00450 ( av1==bv3 && av2==bv1 && av3==bv3 ) ) 00451 return; 00452 } 00453 00454 face->setTAG(tag); 00455 faces->push_back(face); 00456 mesh->addFace(face); 00457 } 00458 00470 void BOP_splitQuad(BOP_Mesh* mesh, MT_Plane3 plane, BOP_Index v1, BOP_Index v2, 00471 BOP_Index v3, BOP_Index v4, BOP_Face* triangles[], BOP_Index original) 00472 { 00473 MT_Point3 p1 = mesh->getVertex(v1)->getPoint(); 00474 MT_Point3 p2 = mesh->getVertex(v2)->getPoint(); 00475 MT_Point3 p3 = mesh->getVertex(v3)->getPoint(); 00476 MT_Point3 p4 = mesh->getVertex(v4)->getPoint(); 00477 00478 int res = BOP_concave(p1,p2,p3,p4); 00479 00480 if (res==0) { 00481 MT_Plane3 plane1(p1, p2, p3); 00482 MT_Plane3 plane2(p1, p3, p4); 00483 00484 if (BOP_isInsideCircle(mesh, v1, v2, v4, v3) && 00485 BOP_orientation(plane1, plane) && 00486 BOP_orientation(plane2, plane)) { 00487 triangles[0] = new BOP_Face3(v1, v2, v3, plane, original); 00488 triangles[1] = new BOP_Face3(v1, v3, v4, plane, original); 00489 } 00490 else { 00491 triangles[0] = new BOP_Face3(v1, v2, v4, plane, original); 00492 triangles[1] = new BOP_Face3(v2, v3, v4, plane, original); 00493 } 00494 } 00495 else if (res==-1) { 00496 triangles[0] = new BOP_Face3(v1, v2, v4, plane, original); 00497 triangles[1] = new BOP_Face3(v2, v3, v4, plane, original); 00498 } 00499 else { 00500 triangles[0] = new BOP_Face3(v1, v2, v3, plane, original); 00501 triangles[1] = new BOP_Face3(v1, v3, v4, plane, original); 00502 } 00503 } 00504 00514 BOP_Index BOP_getTriangleVertex(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4) 00515 { 00516 if (BOP_isInsideCircle(mesh, v1, v2, v4, v3)) { 00517 return v3; 00518 } 00519 return v4; 00520 } 00521 00530 BOP_Index BOP_getNearestVertex(BOP_Mesh* mesh, BOP_Index u, BOP_Index v1, BOP_Index v2) 00531 { 00532 MT_Point3 q = mesh->getVertex(u)->getPoint(); 00533 MT_Point3 p1 = mesh->getVertex(v1)->getPoint(); 00534 MT_Point3 p2 = mesh->getVertex(v2)->getPoint(); 00535 if (BOP_comp(q.distance(p1), q.distance(p2)) > 0) return v2; 00536 else return v1; 00537 } 00538 00549 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5) 00550 { 00551 return BOP_isInsideCircle(mesh->getVertex(v1)->getPoint(), 00552 mesh->getVertex(v2)->getPoint(), 00553 mesh->getVertex(v3)->getPoint(), 00554 mesh->getVertex(v4)->getPoint(), 00555 mesh->getVertex(v5)->getPoint()); 00556 } 00557 00567 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index w) 00568 { 00569 return BOP_isInsideCircle(mesh->getVertex(v1)->getPoint(), 00570 mesh->getVertex(v2)->getPoint(), 00571 mesh->getVertex(v3)->getPoint(), 00572 mesh->getVertex(w)->getPoint()); 00573 }