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