|
Blender
V2.59
|
00001 /* 00002 * 00003 * $Id: BOP_Face2Face.cpp 35143 2011-02-25 10:32:33Z jesterking $ 00004 * 00005 * ***** BEGIN GPL LICENSE BLOCK ***** 00006 * 00007 * This program is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU General Public License 00009 * as published by the Free Software Foundation; either version 2 00010 * of the License, or (at your option) any later version. 00011 * 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program; if not, write to the Free Software Foundation, 00019 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 00020 * 00021 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. 00022 * All rights reserved. 00023 * 00024 * The Original Code is: all of this file. 00025 * 00026 * Contributor(s): Marc Freixas, Ken Hughes 00027 * 00028 * ***** END GPL LICENSE BLOCK ***** 00029 */ 00030 00036 #include "BOP_Face2Face.h" 00037 #include "BOP_BBox.h" 00038 00039 // TAGS for segment classification in x-segment creation 00040 // sA -> point of sA 00041 // sB -> point of sB 00042 // sX -> point of sA and SB 00043 #define sA_sB 12 00044 #define sB_sA 21 00045 #define sX_sA 31 00046 #define sA_sX 13 00047 #define sX_sB 32 00048 #define sB_sX 23 00049 #define sX_sX 33 00050 00051 #define sA_sA_sB 112 00052 #define sB_sB_sA 221 00053 #define sB_sA_sA 211 00054 #define sA_sB_sB 122 00055 #define sA_sB_sA 121 00056 #define sB_sA_sB 212 00057 #define sA_sX_sB 132 00058 #define sB_sX_sA 231 00059 #define sX_sA_sB 312 00060 #define sX_sB_sA 321 00061 #define sA_sB_sX 123 00062 #define sB_sA_sX 213 00063 00064 #define sA_sA_sB_sB 1122 00065 #define sB_sB_sA_sA 2211 00066 #define sA_sB_sA_sB 1212 00067 #define sB_sA_sB_sA 2121 00068 #define sA_sB_sB_sA 1221 00069 #define sB_sA_sA_sB 2112 00070 00071 void BOP_intersectCoplanarFaces(BOP_Mesh* mesh, 00072 BOP_Faces* facesB, 00073 BOP_Face* faceA, 00074 BOP_Face* faceB, 00075 bool invert); 00076 00077 void BOP_intersectCoplanarFaces(BOP_Mesh* mesh, 00078 BOP_Faces* facesB, 00079 BOP_Face* faceB, 00080 BOP_Segment sA, 00081 MT_Plane3 planeA, 00082 bool invert); 00083 00084 void BOP_intersectNonCoplanarFaces(BOP_Mesh* mesh, 00085 BOP_Faces* facesA, 00086 BOP_Faces* facesB, 00087 BOP_Face* faceA, 00088 BOP_Face* faceB); 00089 00090 void BOP_getPoints(BOP_Mesh* mesh, 00091 BOP_Face* faceA, 00092 BOP_Segment& sA, 00093 MT_Plane3 planeB, 00094 MT_Point3* points, 00095 unsigned int* faces, 00096 unsigned int& size, 00097 unsigned int faceValue); 00098 00099 void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB); 00100 00101 void BOP_createXS(BOP_Mesh* mesh, 00102 BOP_Face* faceA, 00103 BOP_Face* faceB, 00104 BOP_Segment sA, 00105 BOP_Segment sB, 00106 bool invert, 00107 BOP_Segment* segments); 00108 00109 void BOP_createXS(BOP_Mesh* mesh, 00110 BOP_Face* faceA, 00111 BOP_Face* faceB, 00112 MT_Plane3 planeA, 00113 MT_Plane3 planeB, 00114 BOP_Segment sA, 00115 BOP_Segment sB, 00116 bool invert, 00117 BOP_Segment* segments); 00118 00119 BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 00120 MT_Point3 point, 00121 unsigned int cfgA, 00122 unsigned int cfgB, 00123 BOP_Index vA, 00124 BOP_Index vB, 00125 bool invert); 00126 00127 BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v); 00128 00129 void triangulate(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face *face, BOP_Segment s); 00130 00131 BOP_Face *BOP_getOppositeFace(BOP_Mesh* mesh, 00132 BOP_Faces* faces, 00133 BOP_Face* face, 00134 BOP_Edge* edge); 00135 00136 bool BOP_overlap(MT_Vector3 normal, 00137 MT_Point3 p1, 00138 MT_Point3 p2, 00139 MT_Point3 p3, 00140 MT_Point3 q1, 00141 MT_Point3 q2, 00142 MT_Point3 q3); 00143 00144 void BOP_mergeVertexs(BOP_Mesh *mesh, unsigned int firstFace); 00145 00146 00162 void BOP_Face2Face(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB) 00163 { 00164 for(unsigned int idxFaceA=0;idxFaceA<facesA->size();idxFaceA++) { 00165 BOP_Face *faceA = (*facesA)[idxFaceA]; 00166 MT_Plane3 planeA = faceA->getPlane(); 00167 MT_Point3 p1 = mesh->getVertex(faceA->getVertex(0))->getPoint(); 00168 MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint(); 00169 MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint(); 00170 00171 /* get (or create) bounding box for face A */ 00172 if( faceA->getBBox() == NULL ) 00173 faceA->setBBox(p1,p2,p3); 00174 BOP_BBox *boxA = faceA->getBBox(); 00175 00176 /* start checking B faces with the previously stored split index */ 00177 00178 for(unsigned int idxFaceB=faceA->getSplit(); 00179 idxFaceB<facesB->size() && (faceA->getTAG() != BROKEN) && (faceA->getTAG() != PHANTOM);) { 00180 BOP_Face *faceB = (*facesB)[idxFaceB]; 00181 faceA->setSplit(idxFaceB); 00182 if ((faceB->getTAG() != BROKEN) && (faceB->getTAG() != PHANTOM)) { 00183 00184 /* get (or create) bounding box for face B */ 00185 if( faceB->getBBox() == NULL ) 00186 faceB->setBBox(mesh->getVertex(faceB->getVertex(0))->getPoint(), 00187 mesh->getVertex(faceB->getVertex(1))->getPoint(), 00188 mesh->getVertex(faceB->getVertex(2))->getPoint()); 00189 BOP_BBox *boxB = faceB->getBBox(); 00190 00191 if (boxA->intersect(*boxB)) { 00192 MT_Plane3 planeB = faceB->getPlane(); 00193 if (BOP_containsPoint(planeB,p1) && 00194 BOP_containsPoint(planeB,p2) && 00195 BOP_containsPoint(planeB,p3)) { 00196 if (BOP_orientation(planeB,planeA)>0) { 00197 BOP_intersectCoplanarFaces(mesh,facesB,faceA,faceB,false); 00198 } 00199 } 00200 else { 00201 BOP_intersectNonCoplanarFaces(mesh,facesA,facesB,faceA,faceB); 00202 } 00203 } 00204 } 00205 idxFaceB++; 00206 } 00207 } 00208 00209 00210 // Clean broken faces from facesA 00211 BOP_IT_Faces it; 00212 it = facesA->begin(); 00213 while (it != facesA->end()) { 00214 BOP_Face *face = *it; 00215 if (face->getTAG() == BROKEN) it = facesA->erase(it); 00216 else it++; 00217 } 00218 /* 00219 it = facesB->begin(); 00220 while (it != facesB->end()) { 00221 BOP_Face *face = *it; 00222 if (face->getTAG() == BROKEN) it = facesB->erase(it); 00223 else it++; 00224 } 00225 */ 00226 } 00227 00234 void BOP_sew(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB) 00235 { 00236 for(unsigned int idxFaceB = 0; idxFaceB < facesB->size(); idxFaceB++) { 00237 BOP_Face *faceB = (*facesB)[idxFaceB]; 00238 MT_Plane3 planeB = faceB->getPlane(); 00239 MT_Point3 p1 = mesh->getVertex(faceB->getVertex(0))->getPoint(); 00240 MT_Point3 p2 = mesh->getVertex(faceB->getVertex(1))->getPoint(); 00241 MT_Point3 p3 = mesh->getVertex(faceB->getVertex(2))->getPoint(); 00242 00243 for(unsigned int idxFaceA = 0; 00244 idxFaceA < facesA->size() && 00245 faceB->getTAG() != BROKEN && 00246 faceB->getTAG() != PHANTOM; 00247 idxFaceA++) { 00248 BOP_Face *faceA = (*facesA)[idxFaceA]; 00249 if ((faceA->getTAG() != BROKEN)&&(faceA->getTAG() != PHANTOM)) { 00250 MT_Plane3 planeA = faceA->getPlane(); 00251 if (BOP_containsPoint(planeA,p1) && 00252 BOP_containsPoint(planeA,p2) && 00253 BOP_containsPoint(planeA,p3)) { 00254 if (BOP_orientation(planeA,planeB) > 0) { 00255 BOP_intersectCoplanarFaces(mesh,facesA,faceB,faceA,true); 00256 } 00257 } 00258 } 00259 } 00260 } 00261 } 00262 00271 void BOP_intersectCoplanarFaces(BOP_Mesh* mesh, 00272 BOP_Faces* facesB, 00273 BOP_Face* faceA, 00274 BOP_Face* faceB, 00275 bool invert) 00276 { 00277 unsigned int oldSize = facesB->size(); 00278 unsigned int originalFaceB = faceB->getOriginalFace(); 00279 00280 MT_Point3 p1 = mesh->getVertex(faceA->getVertex(0))->getPoint(); 00281 MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint(); 00282 MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint(); 00283 00284 MT_Vector3 normal(faceA->getPlane().x(),faceA->getPlane().y(),faceA->getPlane().z()); 00285 00286 MT_Vector3 p1p2 = p2-p1; 00287 00288 MT_Plane3 plane1((p1p2.cross(normal).normalized()),p1); 00289 00290 BOP_Segment sA; 00291 sA.m_cfg1 = BOP_Segment::createVertexCfg(1); 00292 sA.m_v1 = faceA->getVertex(0); 00293 sA.m_cfg2 = BOP_Segment::createVertexCfg(2); 00294 sA.m_v2 = faceA->getVertex(1); 00295 00296 BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane1,invert); 00297 00298 MT_Vector3 p2p3 = p3-p2; 00299 MT_Plane3 plane2((p2p3.cross(normal).normalized()),p2); 00300 00301 sA.m_cfg1 = BOP_Segment::createVertexCfg(2); 00302 sA.m_v1 = faceA->getVertex(1); 00303 sA.m_cfg2 = BOP_Segment::createVertexCfg(3); 00304 sA.m_v2 = faceA->getVertex(2); 00305 00306 if (faceB->getTAG() == BROKEN) { 00307 for(unsigned int idxFace = oldSize; idxFace < facesB->size(); idxFace++) { 00308 BOP_Face *face = (*facesB)[idxFace]; 00309 if (face->getTAG() != BROKEN && originalFaceB == face->getOriginalFace()) 00310 BOP_intersectCoplanarFaces(mesh,facesB,face,sA,plane2,invert); 00311 } 00312 } 00313 else { 00314 BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane2,invert); 00315 } 00316 00317 MT_Vector3 p3p1 = p1-p3; 00318 MT_Plane3 plane3((p3p1.cross(normal).safe_normalized()),p3); 00319 00320 sA.m_cfg1 = BOP_Segment::createVertexCfg(3); 00321 sA.m_v1 = faceA->getVertex(2); 00322 sA.m_cfg2 = BOP_Segment::createVertexCfg(1); 00323 sA.m_v2 = faceA->getVertex(0); 00324 00325 if (faceB->getTAG() == BROKEN) { 00326 for(unsigned int idxFace = oldSize; idxFace < facesB->size(); idxFace++) { 00327 BOP_Face *face = (*facesB)[idxFace]; 00328 if (face->getTAG() != BROKEN && originalFaceB == face->getOriginalFace()) 00329 BOP_intersectCoplanarFaces(mesh,facesB,face,sA,plane3,invert); 00330 } 00331 } 00332 else { 00333 BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane3,invert); 00334 } 00335 } 00336 00346 void BOP_intersectCoplanarFaces(BOP_Mesh* mesh, 00347 BOP_Faces* facesB, 00348 BOP_Face* faceB, 00349 BOP_Segment sA, 00350 MT_Plane3 planeA, 00351 bool invert) 00352 { 00353 BOP_Segment sB = BOP_splitFace(planeA,mesh,faceB); 00354 00355 if (BOP_Segment::isDefined(sB.m_cfg1)) { 00356 BOP_Segment xSegment[2]; 00357 BOP_createXS(mesh,NULL,faceB,planeA,MT_Plane3(),sA,sB,invert,xSegment); 00358 if (BOP_Segment::isDefined(xSegment[1].m_cfg1)) { 00359 unsigned int sizefaces = mesh->getNumFaces(); 00360 triangulate(mesh,facesB,faceB,xSegment[1]); 00361 BOP_mergeVertexs(mesh,sizefaces); 00362 } 00363 } 00364 } 00365 00373 void BOP_intersectNonCoplanarFaces(BOP_Mesh *mesh, 00374 BOP_Faces *facesA, 00375 BOP_Faces *facesB, 00376 BOP_Face *faceA, 00377 BOP_Face *faceB) 00378 { 00379 // Obtain segments of faces A and B from the intersection with their planes 00380 BOP_Segment sA = BOP_splitFace(faceB->getPlane(),mesh,faceA); 00381 BOP_Segment sB = BOP_splitFace(faceA->getPlane(),mesh,faceB); 00382 00383 if (BOP_Segment::isDefined(sA.m_cfg1) && BOP_Segment::isDefined(sB.m_cfg1)) { 00384 // There is an intesection, build the X-segment 00385 BOP_Segment xSegment[2]; 00386 BOP_createXS(mesh,faceA,faceB,sA,sB,false,xSegment); 00387 00388 unsigned int sizefaces = mesh->getNumFaces(); 00389 triangulate(mesh,facesA,faceA,xSegment[0]); 00390 BOP_mergeVertexs(mesh,sizefaces); 00391 00392 sizefaces = mesh->getNumFaces(); 00393 triangulate(mesh,facesB,faceB,xSegment[1]); 00394 BOP_mergeVertexs(mesh,sizefaces); 00395 } 00396 } 00397 00403 void BOP_mergeVertexs(BOP_Mesh *mesh, unsigned int firstFace) 00404 { 00405 unsigned int numFaces = mesh->getNumFaces(); 00406 for(unsigned int idxFace = firstFace; idxFace < numFaces; idxFace++) { 00407 BOP_Face *face = mesh->getFace(idxFace); 00408 if ((face->getTAG() != BROKEN) && (face->getTAG() != PHANTOM)) { 00409 MT_Point3 vertex1 = mesh->getVertex(face->getVertex(0))->getPoint(); 00410 MT_Point3 vertex2 = mesh->getVertex(face->getVertex(1))->getPoint(); 00411 MT_Point3 vertex3 = mesh->getVertex(face->getVertex(2))->getPoint(); 00412 if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle 00413 face->setTAG(PHANTOM); 00414 } 00415 } 00416 } 00417 00429 void BOP_getPoints(BOP_Mesh* mesh, 00430 BOP_Face* faceA, 00431 BOP_Segment& sA, 00432 MT_Plane3 planeB, 00433 MT_Point3* points, 00434 unsigned int* faces, 00435 unsigned int& size, 00436 unsigned int faceValue) 00437 { 00438 MT_Point3 p1,p2; 00439 00440 if (BOP_Segment::isDefined(sA.m_cfg1)) { 00441 if (BOP_Segment::isEdge(sA.m_cfg1)) { 00442 // the new point becomes of split faceA edge 00443 p1 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg1)); 00444 } 00445 else if (BOP_Segment::isVertex(sA.m_cfg1)) { 00446 // the new point becomes of vertex faceA 00447 p1 = mesh->getVertex(BOP_Segment::getVertex(sA.m_v1))->getPoint(); 00448 } 00449 00450 if (BOP_Segment::isDefined(sA.m_cfg2)) { 00451 if (BOP_Segment::isEdge(sA.m_cfg2)) { 00452 p2 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg2)); 00453 } 00454 else if (BOP_Segment::isVertex(sA.m_cfg2)) { 00455 p2 = mesh->getVertex(BOP_Segment::getVertex(sA.m_v2))->getPoint(); 00456 } 00457 points[size] = p1; 00458 points[size+1] = p2; 00459 faces[size] = faceValue; 00460 faces[size+1] = faceValue; 00461 size += 2; 00462 } 00463 00464 else { 00465 points[size] = p1; 00466 faces[size] = faceValue; 00467 size++; 00468 } 00469 } 00470 } 00471 00479 void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB) { 00480 MT_Point3 sortedPoints[4]; 00481 unsigned int sortedFaces[4], position[4]; 00482 unsigned int i; 00483 if (size == 2) { 00484 00485 // Trivial case, only test the merge ... 00486 if (BOP_fuzzyZero(points[0].distance(points[1]))) { 00487 face[0] = 3; 00488 size--; 00489 } 00490 } 00491 else { 00492 // size is 3 or 4 00493 // Get segment extreme points 00494 MT_Scalar maxDistance = -1; 00495 for(i=0;i<size-1;i++){ 00496 for(unsigned int j=i+1;j<size;j++){ 00497 MT_Scalar distance = points[i].distance(points[j]); 00498 if (distance > maxDistance){ 00499 maxDistance = distance; 00500 position[0] = i; 00501 position[size-1] = j; 00502 } 00503 } 00504 } 00505 00506 // Get segment inner points 00507 position[1] = position[2] = size; 00508 for(i=0;i<size;i++){ 00509 if ((i != position[0]) && (i != position[size-1])){ 00510 if (position[1] == size) position[1] = i; 00511 else position[2] = i; 00512 } 00513 } 00514 00515 // Get inner points 00516 if (position[2] < size) { 00517 MT_Scalar d1 = points[position[1]].distance(points[position[0]]); 00518 MT_Scalar d2 = points[position[2]].distance(points[position[0]]); 00519 if (d1 > d2) { 00520 unsigned int aux = position[1]; 00521 position[1] = position[2]; 00522 position[2] = aux; 00523 } 00524 } 00525 00526 // Sort data 00527 for(i=0;i<size;i++) { 00528 sortedPoints[i] = points[position[i]]; 00529 sortedFaces[i] = face[position[i]]; 00530 } 00531 00532 invertA = false; 00533 invertB = false; 00534 if (face[1] == 1) { 00535 00536 // invertAø? 00537 for(i=0;i<size;i++) { 00538 if (position[i] == 1) { 00539 invertA = true; 00540 break; 00541 } 00542 else if (position[i] == 0) break; 00543 } 00544 00545 // invertBø? 00546 if (size == 4) { 00547 for(i=0;i<size;i++) { 00548 if (position[i] == 3) { 00549 invertB = true; 00550 break; 00551 } 00552 else if (position[i] == 2) break; 00553 } 00554 } 00555 } 00556 else if (face[1] == 2) { 00557 // invertBø? 00558 for(i=0;i<size;i++) { 00559 if (position[i] == 2) { 00560 invertB = true; 00561 break; 00562 } 00563 else if (position[i] == 1) break; 00564 } 00565 } 00566 00567 00568 // Merge data 00569 MT_Scalar d1 = sortedPoints[1].distance(sortedPoints[0]); 00570 MT_Scalar d2 = sortedPoints[1].distance(sortedPoints[2]); 00571 if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[0]) { 00572 if (BOP_fuzzyZero(d2) && sortedFaces[1] != sortedFaces[2]) { 00573 if (d1 < d2) { 00574 // merge 0 and 1 00575 sortedFaces[0] = 3; 00576 for(i = 1; i<size-1;i++) { 00577 sortedPoints[i] = sortedPoints[i+1]; 00578 sortedFaces[i] = sortedFaces[i+1]; 00579 } 00580 size--; 00581 if (size == 3) { 00582 // merge 1 and 2 ??? 00583 d1 = sortedPoints[1].distance(sortedPoints[2]); 00584 if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[2]) { 00585 // merge! 00586 sortedFaces[1] = 3; 00587 size--; 00588 } 00589 } 00590 } 00591 else { 00592 // merge 1 and 2 00593 sortedFaces[1] = 3; 00594 for(i = 2; i<size-1;i++) { 00595 sortedPoints[i] = sortedPoints[i+1]; 00596 sortedFaces[i] = sortedFaces[i+1]; 00597 } 00598 size--; 00599 } 00600 } 00601 else { 00602 // merge 0 and 1 00603 sortedFaces[0] = 3; 00604 for(i = 1; i<size-1;i++) { 00605 sortedPoints[i] = sortedPoints[i+1]; 00606 sortedFaces[i] = sortedFaces[i+1]; 00607 } 00608 size--; 00609 if (size == 3) { 00610 // merge 1 i 2 ??? 00611 d1 = sortedPoints[1].distance(sortedPoints[2]); 00612 if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[2]) { 00613 // merge! 00614 sortedFaces[1] = 3; 00615 size--; 00616 } 00617 } 00618 } 00619 } 00620 else { 00621 if (BOP_fuzzyZero(d2) && sortedFaces[1] != sortedFaces[2]) { 00622 // merge 1 and 2 00623 sortedFaces[1] = 3; 00624 for(i = 2; i<size-1;i++) { 00625 sortedPoints[i] = sortedPoints[i+1]; 00626 sortedFaces[i] = sortedFaces[i+1]; 00627 } 00628 size--; 00629 } 00630 else if (size == 4) { 00631 d1 = sortedPoints[2].distance(sortedPoints[3]); 00632 if (BOP_fuzzyZero(d1) && sortedFaces[2] != sortedFaces[3]) { 00633 // merge 2 and 3 00634 sortedFaces[2] = 3; 00635 size--; 00636 } 00637 } 00638 } 00639 00640 // Merge initial points ... 00641 for(i=0;i<size;i++) { 00642 points[i] = sortedPoints[i]; 00643 face[i] = sortedFaces[i]; 00644 } 00645 00646 } 00647 } 00648 00649 00660 void BOP_createXS(BOP_Mesh* mesh, 00661 BOP_Face* faceA, 00662 BOP_Face* faceB, 00663 BOP_Segment sA, 00664 BOP_Segment sB, 00665 bool invert, 00666 BOP_Segment* segments) { 00667 BOP_createXS(mesh, faceA, faceB, faceA->getPlane(), faceB->getPlane(), 00668 sA, sB, invert, segments); 00669 } 00670 00683 void BOP_createXS(BOP_Mesh* mesh, 00684 BOP_Face* faceA, 00685 BOP_Face* faceB, 00686 MT_Plane3 planeA, 00687 MT_Plane3 planeB, 00688 BOP_Segment sA, 00689 BOP_Segment sB, 00690 bool invert, 00691 BOP_Segment* segments) 00692 { 00693 MT_Point3 points[4]; // points of the segments 00694 unsigned int face[4]; // relative face indexs (1 => faceA, 2 => faceB) 00695 unsigned int size = 0; // size of points and relative face indexs 00696 00697 BOP_getPoints(mesh, faceA, sA, planeB, points, face, size, 1); 00698 BOP_getPoints(mesh, faceB, sB, planeA, points, face, size, 2); 00699 00700 bool invertA = false; 00701 bool invertB = false; 00702 BOP_mergeSort(points,face,size,invertA,invertB); 00703 00704 if (invertA) sA.invert(); 00705 if (invertB) sB.invert(); 00706 00707 // Compute the configuration label 00708 unsigned int label = 0; 00709 for(unsigned int i =0; i < size; i++) { 00710 label = face[i]+label*10; 00711 } 00712 00713 if (size == 1) { 00714 // Two coincident points 00715 segments[0].m_cfg1 = sA.m_cfg1; 00716 segments[1].m_cfg1 = sB.m_cfg1; 00717 00718 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 00719 sA.m_v1, sB.m_v1, invert); 00720 segments[1].m_v1 = segments[0].m_v1; 00721 segments[0].m_cfg2 = segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00722 } 00723 else if (size == 2) { 00724 switch(label) { 00725 // Two non-coincident points 00726 case sA_sB: 00727 case sB_sA: 00728 segments[0].m_cfg1 = 00729 segments[1].m_cfg1 = 00730 segments[0].m_cfg2 = 00731 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00732 break; 00733 00734 // Two coincident points and one non-coincident of sA 00735 case sA_sX: 00736 segments[0].m_cfg1 = sA.m_cfg2; 00737 segments[1].m_cfg1 = sB.m_cfg1; 00738 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1, 00739 sA.m_v2, sB.m_v1, invert); 00740 segments[1].m_v1 = segments[0].m_v1; 00741 00742 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00743 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00744 break; 00745 case sX_sA: 00746 segments[0].m_cfg1 = sA.m_cfg1; 00747 segments[1].m_cfg1 = sB.m_cfg1; 00748 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 00749 sA.m_v1, sB.m_v1, invert); 00750 segments[1].m_v1 = segments[0].m_v1; 00751 00752 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00753 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00754 break; 00755 00756 // Two coincident points and one non-coincident of sB 00757 case sB_sX: 00758 segments[0].m_cfg1 = sA.m_cfg1; 00759 segments[1].m_cfg1 = sB.m_cfg2; 00760 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 00761 sA.m_v1, sB.m_v2, invert); 00762 segments[1].m_v1 = segments[0].m_v1; 00763 00764 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00765 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00766 break; 00767 case sX_sB: 00768 segments[0].m_cfg1 = sA.m_cfg1; 00769 segments[1].m_cfg1 = sB.m_cfg1; 00770 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 00771 sA.m_v1, sB.m_v1, invert); 00772 segments[1].m_v1 = segments[0].m_v1; 00773 00774 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00775 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00776 break; 00777 00778 // coincident points 2-2 00779 case sX_sX: 00780 segments[0].m_cfg1 = sA.m_cfg1; 00781 segments[1].m_cfg1 = sB.m_cfg1; 00782 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 00783 sA.m_v1, sB.m_v1, invert); 00784 segments[1].m_v1 = segments[0].m_v1; 00785 00786 segments[0].m_cfg2 = sA.m_cfg2; 00787 segments[1].m_cfg2 = sB.m_cfg2; 00788 segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg2, 00789 sA.m_v2, sB.m_v2, invert); 00790 segments[1].m_v2 = segments[0].m_v2; 00791 break; 00792 00793 default: 00794 break; 00795 } 00796 } 00797 else if (size == 3) { 00798 switch(label) { 00799 case sA_sA_sB: 00800 case sB_sA_sA: 00801 case sA_sB_sB: 00802 case sB_sB_sA: 00803 segments[0].m_cfg1 = 00804 segments[1].m_cfg1 = 00805 segments[0].m_cfg2 = 00806 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00807 break; 00808 00809 case sA_sB_sA: 00810 segments[1].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1); 00811 segments[1].m_cfg1 = sB.m_cfg1; 00812 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00813 segments[0].m_cfg1 = sA.getConfig(); 00814 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00815 segments[0].m_v1 = segments[1].m_v1; 00816 break; 00817 00818 case sB_sA_sB: 00819 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1); 00820 segments[0].m_cfg1 = sA.m_cfg1; 00821 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00822 segments[1].m_cfg1 = sB.getConfig(); 00823 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00824 segments[1].m_v1 = segments[0].m_v1; 00825 break; 00826 00827 case sA_sX_sB: 00828 segments[0].m_cfg1 = sA.m_cfg2; 00829 segments[1].m_cfg1 = sB.m_cfg1; 00830 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1, 00831 sA.m_v2, sB.m_v1, invert); 00832 segments[1].m_v1 = segments[0].m_v1; 00833 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00834 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00835 break; 00836 00837 case sB_sX_sA: 00838 segments[0].m_cfg1 = sA.m_cfg1; 00839 segments[1].m_cfg1 = sB.m_cfg2; 00840 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 00841 sA.m_v1, sB.m_v2, invert); 00842 segments[1].m_v1 = segments[0].m_v1; 00843 segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00844 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00845 break; 00846 00847 case sX_sA_sB: 00848 segments[0].m_cfg1 = sA.m_cfg1; 00849 segments[1].m_cfg1 = sB.m_cfg1; 00850 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 00851 sA.m_v1, sB.m_v1, invert); 00852 segments[1].m_v1 = segments[0].m_v1; 00853 00854 segments[0].m_cfg2 = sA.m_cfg2; 00855 segments[1].m_cfg2 = sB.getConfig(); 00856 segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sA.m_v2); 00857 segments[1].m_v2 = segments[0].m_v2; 00858 break; 00859 00860 case sX_sB_sA: 00861 segments[0].m_cfg1 = sA.m_cfg1; 00862 segments[1].m_cfg1 = sB.m_cfg1; 00863 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 00864 sA.m_v1, sB.m_v1, invert); 00865 segments[1].m_v1 = segments[0].m_v1; 00866 00867 segments[0].m_cfg2 = sA.getConfig(); 00868 segments[1].m_cfg2 = sB.m_cfg2; 00869 segments[0].m_v2 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg2,sB.m_v2); 00870 segments[1].m_v2 = segments[0].m_v2; 00871 break; 00872 00873 case sA_sB_sX: 00874 segments[0].m_cfg1 = sA.getConfig(); 00875 segments[1].m_cfg1 = sB.m_cfg1; 00876 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1); 00877 segments[1].m_v1 = segments[0].m_v1; 00878 00879 segments[0].m_cfg2 = sA.m_cfg2; 00880 segments[1].m_cfg2 = sB.m_cfg2; 00881 segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2, 00882 sA.m_v2, sB.m_v2, invert); 00883 segments[1].m_v2 = segments[0].m_v2; 00884 break; 00885 00886 case sB_sA_sX: 00887 segments[0].m_cfg1 = sA.m_cfg1; 00888 segments[1].m_cfg1 = sB.getConfig(); 00889 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1); 00890 segments[1].m_v1 = segments[0].m_v1; 00891 00892 segments[0].m_cfg2 = sA.m_cfg2; 00893 segments[1].m_cfg2 = sB.m_cfg2; 00894 segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2, 00895 sA.m_v2, sB.m_v2, invert); 00896 segments[1].m_v2 = segments[0].m_v2; 00897 break; 00898 00899 default: 00900 break; 00901 } 00902 } 00903 else { 00904 // 4! 00905 switch(label) { 00906 case sA_sA_sB_sB: 00907 case sB_sB_sA_sA: 00908 segments[0].m_cfg1 = 00909 segments[1].m_cfg1 = 00910 segments[0].m_cfg2 = 00911 segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg(); 00912 break; 00913 00914 case sA_sB_sA_sB: 00915 segments[0].m_cfg1 = sA.getConfig(); 00916 segments[1].m_cfg1 = sB.m_cfg1; 00917 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1); 00918 segments[1].m_v1 = segments[0].m_v1; 00919 00920 segments[0].m_cfg2 = sA.m_cfg2; 00921 segments[1].m_cfg2 = sB.getConfig(); 00922 segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2); 00923 segments[1].m_v2 = segments[0].m_v2; 00924 break; 00925 00926 case sB_sA_sB_sA: 00927 segments[0].m_cfg1 = sA.m_cfg1; 00928 segments[1].m_cfg1 = sB.getConfig(); 00929 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1); 00930 segments[1].m_v1 = segments[0].m_v1; 00931 00932 segments[0].m_cfg2 = sA.getConfig(); 00933 segments[1].m_cfg2 = sB.m_cfg2; 00934 segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2); 00935 segments[1].m_v2 = segments[0].m_v2; 00936 break; 00937 00938 case sA_sB_sB_sA: 00939 segments[0].m_cfg1 = sA.getConfig(); 00940 segments[1].m_cfg1 = sB.m_cfg1; 00941 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1); 00942 segments[1].m_v1 = segments[0].m_v1; 00943 00944 segments[0].m_cfg2 = segments[0].m_cfg1; 00945 segments[1].m_cfg2 = sB.m_cfg2; 00946 segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2); 00947 segments[1].m_v2 = segments[0].m_v2; 00948 break; 00949 00950 case sB_sA_sA_sB: 00951 segments[0].m_cfg1 = sA.m_cfg1; 00952 segments[1].m_cfg1 = sB.getConfig(); 00953 segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1); 00954 segments[1].m_v1 = segments[0].m_v1; 00955 00956 segments[0].m_cfg2 = sA.m_cfg2; 00957 segments[1].m_cfg2 = segments[1].m_cfg1; 00958 segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2); 00959 segments[1].m_v2 = segments[0].m_v2; 00960 break; 00961 00962 default: 00963 break; 00964 } 00965 } 00966 00967 segments[0].sort(); 00968 segments[1].sort(); 00969 } 00970 00982 BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 00983 MT_Point3 point, 00984 unsigned int cfgA, 00985 unsigned int cfgB, 00986 BOP_Index vA, 00987 BOP_Index vB, 00988 bool invert) 00989 { 00990 if (BOP_Segment::isVertex(cfgA)) { // exists vertex index on A 00991 if (BOP_Segment::isVertex(cfgB)) { // exists vertex index on B 00992 // unify vertex indexs 00993 if (invert) 00994 return mesh->replaceVertexIndex(vA,vB); 00995 else 00996 return mesh->replaceVertexIndex(vB,vA); 00997 } 00998 else 00999 return vA; 01000 } 01001 else {// does not exist vertex index on A 01002 if (BOP_Segment::isVertex(cfgB)) // exists vertex index on B 01003 return vB; 01004 else {// does not exist vertex index on B 01005 return mesh->addVertex(point); 01006 } 01007 } 01008 } 01009 01017 BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v) 01018 { 01019 if (BOP_Segment::isVertex(cfg)) // vertex existent 01020 return v; 01021 else { 01022 return mesh->addVertex(point); 01023 } 01024 } 01025 01026 /******************************************************************************/ 01027 /*** TRIANGULATE ***/ 01028 /******************************************************************************/ 01029 01037 void triangulate(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face *face, BOP_Segment s) 01038 { 01039 if (BOP_Segment::isUndefined(s.m_cfg1)) { 01040 // Nothing to do 01041 } 01042 else if (BOP_Segment::isVertex(s.m_cfg1)) { 01043 // VERTEX(v1) + VERTEX(v2) => nothing to do 01044 } 01045 else if (BOP_Segment::isEdge(s.m_cfg1)) { 01046 if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) { 01047 // EDGE(v1) + VERTEX(v2) 01048 BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1)); 01049 BOP_triangulateA(mesh,faces,face,s.m_v1,BOP_Segment::getEdge(s.m_cfg1)); 01050 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge); 01051 if (opposite != NULL) { 01052 unsigned int e; 01053 opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e); 01054 BOP_triangulateA(mesh, faces, opposite, s.m_v1, e); 01055 } 01056 } 01057 else { 01058 // EDGE(v1) + EDGE(v2) 01059 if (BOP_Segment::getEdge(s.m_cfg1) == BOP_Segment::getEdge(s.m_cfg2)) { 01060 // EDGE(v1) == EDGE(v2) 01061 BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1)); 01062 BOP_triangulateD(mesh, faces, face, s.m_v1, s.m_v2, 01063 BOP_Segment::getEdge(s.m_cfg1)); 01064 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge); 01065 if (opposite != NULL) { 01066 unsigned int e; 01067 opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e); 01068 BOP_triangulateD(mesh, faces, opposite, s.m_v1, s.m_v2, e); 01069 } 01070 } 01071 else { // EDGE(v1) != EDGE(v2) 01072 BOP_Edge *edge1 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1)); 01073 BOP_Edge *edge2 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2)); 01074 BOP_triangulateE(mesh, faces, face, s.m_v1, s.m_v2, 01075 BOP_Segment::getEdge(s.m_cfg1), 01076 BOP_Segment::getEdge(s.m_cfg2)); 01077 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge1); 01078 if (opposite != NULL) { 01079 unsigned int e; 01080 opposite->getEdgeIndex(edge1->getVertex1(), edge1->getVertex2(),e); 01081 BOP_triangulateA(mesh, faces, opposite, s.m_v1, e); 01082 } 01083 opposite = BOP_getOppositeFace(mesh,faces,face,edge2); 01084 if (opposite != NULL) { 01085 unsigned int e; 01086 opposite->getEdgeIndex(edge2->getVertex1(), edge2->getVertex2(),e); 01087 BOP_triangulateA(mesh, faces, opposite, s.m_v2, e); 01088 } 01089 } 01090 } 01091 } 01092 else if (BOP_Segment::isIn(s.m_cfg1)) { 01093 if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) { 01094 // IN(v1) + VERTEX(v2) 01095 BOP_triangulateB(mesh,faces,face,s.m_v1); 01096 } 01097 else if (BOP_Segment::isEdge(s.m_cfg2)) { 01098 // IN(v1) + EDGE(v2) 01099 BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2)); 01100 BOP_triangulateF(mesh,faces,face,s.m_v1,s.m_v2,BOP_Segment::getEdge(s.m_cfg2)); 01101 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge); 01102 if (opposite != NULL) { 01103 unsigned int e; 01104 opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e); 01105 BOP_triangulateA(mesh, faces, opposite, s.m_v2, e); 01106 } 01107 } 01108 else // IN(v1) + IN(v2) 01109 BOP_triangulateC(mesh,faces,face,s.m_v1,s.m_v2); 01110 } 01111 } 01112 01119 bool BOP_containsFace(BOP_Faces *faces, BOP_Face *face) 01120 { 01121 const BOP_IT_Faces facesEnd = faces->end(); 01122 for(BOP_IT_Faces it=faces->begin();it!=facesEnd;it++) 01123 { 01124 if (*it == face) 01125 return true; 01126 } 01127 01128 return false; 01129 } 01130 01139 BOP_Face *BOP_getOppositeFace(BOP_Mesh* mesh, 01140 BOP_Faces* faces, 01141 BOP_Face* face, 01142 BOP_Edge* edge) 01143 { 01144 if (edge == NULL) 01145 return NULL; 01146 01147 BOP_Indexs auxfaces = edge->getFaces(); 01148 const BOP_IT_Indexs auxfacesEnd = auxfaces.end(); 01149 for(BOP_IT_Indexs it = auxfaces.begin(); it != auxfacesEnd; it++) { 01150 BOP_Face *auxface = mesh->getFace(*it); 01151 if ((auxface != face) && (auxface->getTAG()!=BROKEN) && 01152 BOP_containsFace(faces,auxface)) { 01153 return auxface; 01154 } 01155 } 01156 01157 return NULL; 01158 } 01159 01160 /******************************************************************************/ 01161 /*** OVERLAPPING ***/ 01162 /******************************************************************************/ 01163 01170 void BOP_removeOverlappedFaces(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB) 01171 { 01172 for(unsigned int i=0;i<facesA->size();i++) { 01173 BOP_Face *faceI = (*facesA)[i]; 01174 if (faceI->getTAG()==BROKEN) continue; 01175 bool overlapped = false; 01176 MT_Point3 p1 = mesh->getVertex(faceI->getVertex(0))->getPoint(); 01177 MT_Point3 p2 = mesh->getVertex(faceI->getVertex(1))->getPoint(); 01178 MT_Point3 p3 = mesh->getVertex(faceI->getVertex(2))->getPoint(); 01179 for(unsigned int j=0;j<facesB->size();) { 01180 BOP_Face *faceJ = (*facesB)[j]; 01181 if (faceJ->getTAG()!=BROKEN) { 01182 MT_Plane3 planeJ = faceJ->getPlane(); 01183 if (BOP_containsPoint(planeJ,p1) && BOP_containsPoint(planeJ,p2) 01184 && BOP_containsPoint(planeJ,p3)) { 01185 MT_Point3 q1 = mesh->getVertex(faceJ->getVertex(0))->getPoint(); 01186 MT_Point3 q2 = mesh->getVertex(faceJ->getVertex(1))->getPoint(); 01187 MT_Point3 q3 = mesh->getVertex(faceJ->getVertex(2))->getPoint(); 01188 if (BOP_overlap(MT_Vector3(planeJ.x(),planeJ.y(),planeJ.z()), 01189 p1,p2,p3,q1,q2,q3)) { 01190 facesB->erase(facesB->begin()+j,facesB->begin()+(j+1)); 01191 faceJ->setTAG(BROKEN); 01192 overlapped = true; 01193 } 01194 else j++; 01195 } 01196 else j++; 01197 }else j++; 01198 } 01199 if (overlapped) faceI->setTAG(OVERLAPPED); 01200 } 01201 } 01202 01214 bool BOP_overlap(MT_Vector3 normal, MT_Point3 p1, MT_Point3 p2, MT_Point3 p3, 01215 MT_Point3 q1, MT_Point3 q2, MT_Point3 q3) 01216 { 01217 MT_Vector3 p1p2 = p2-p1; 01218 MT_Plane3 plane1(p1p2.cross(normal),p1); 01219 01220 MT_Vector3 p2p3 = p3-p2; 01221 MT_Plane3 plane2(p2p3.cross(normal),p2); 01222 01223 MT_Vector3 p3p1 = p1-p3; 01224 MT_Plane3 plane3(p3p1.cross(normal),p3); 01225 01226 BOP_TAG tag1 = BOP_createTAG(BOP_classify(q1,plane1)); 01227 BOP_TAG tag2 = BOP_createTAG(BOP_classify(q1,plane2)); 01228 BOP_TAG tag3 = BOP_createTAG(BOP_classify(q1,plane3)); 01229 BOP_TAG tagQ1 = BOP_createTAG(tag1,tag2,tag3); 01230 if (tagQ1 == IN_IN_IN) return true; 01231 01232 tag1 = BOP_createTAG(BOP_classify(q2,plane1)); 01233 tag2 = BOP_createTAG(BOP_classify(q2,plane2)); 01234 tag3 = BOP_createTAG(BOP_classify(q2,plane3)); 01235 BOP_TAG tagQ2 = BOP_createTAG(tag1,tag2,tag3); 01236 if (tagQ2 == IN_IN_IN) return true; 01237 01238 tag1 = BOP_createTAG(BOP_classify(q3,plane1)); 01239 tag2 = BOP_createTAG(BOP_classify(q3,plane2)); 01240 tag3 = BOP_createTAG(BOP_classify(q3,plane3)); 01241 BOP_TAG tagQ3 = BOP_createTAG(tag1,tag2,tag3); 01242 if (tagQ3 == IN_IN_IN) return true; 01243 01244 if ((tagQ1 & OUT_OUT_OUT) == 0 && (tagQ2 & OUT_OUT_OUT) == 0 && 01245 (tagQ3 & OUT_OUT_OUT) == 0) return true; 01246 else return false; 01247 }