|
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_MathUtils.h" 00034 #include "BOP_BSPNode.h" 00035 #include "MT_assert.h" 00036 #include "MT_MinMax.h" 00037 #include <iostream> 00038 using namespace std; 00039 00044 BOP_BSPNode::BOP_BSPNode(const MT_Plane3& plane) 00045 { 00046 m_plane = plane; 00047 m_inChild = NULL; 00048 m_outChild = NULL; 00049 m_deep = 1; 00050 } 00051 00055 BOP_BSPNode::~BOP_BSPNode() 00056 { 00057 if (m_inChild!=NULL) delete m_inChild; 00058 if (m_outChild!=NULL) delete m_outChild; 00059 } 00060 00067 unsigned int BOP_BSPNode::addFace(const BOP_BSPPoints& pts, 00068 const MT_Plane3& plane ) 00069 { 00070 unsigned int newDeep = 0; 00071 BOP_TAG tag = ON; 00072 00073 // find out if any points on the "face" lie in either half-space 00074 BOP_IT_BSPPoints ptsEnd = pts.end(); 00075 for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){ 00076 tag = (BOP_TAG) ((int) tag | (int)testPoint(*itp)); 00077 } 00078 00079 if (tag == ON) { } // face lies on hyperplane: do nothing 00080 else if ((tag & IN) != 0 && (tag & OUT) == 0) { // face is entirely on inside 00081 if (m_inChild != NULL) 00082 newDeep = m_inChild->addFace(pts, plane) + 1; 00083 else { 00084 m_inChild = new BOP_BSPNode(plane); 00085 newDeep = 2; 00086 } 00087 } else if ((tag & OUT) != 0 && (tag & IN) == 0) { // face is entirely on outside 00088 if (m_outChild != NULL) 00089 newDeep = m_outChild->addFace(pts, plane) + 1; 00090 else { 00091 m_outChild = new BOP_BSPNode(plane); 00092 newDeep = 2; 00093 } 00094 } else { // face lies in both half-spaces: split it 00095 BOP_BSPPoints inside, outside; 00096 MT_Point3 lpoint= pts[pts.size()-1]; 00097 BOP_TAG ltag = testPoint(lpoint); 00098 BOP_TAG tstate = ltag; 00099 00100 // classify each line segment, looking for endpoints which lie on different 00101 // sides of the hyperplane. 00102 00103 ptsEnd = pts.end(); 00104 for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){ 00105 MT_Point3 npoint= *itp; 00106 BOP_TAG ntag = testPoint(npoint); 00107 00108 if(ltag != ON) { // last point not on hyperplane 00109 if(tstate == IN) { 00110 if (m_inChild != NULL) inside.push_back(lpoint); 00111 } else { 00112 if (m_outChild != NULL) outside.push_back(lpoint); 00113 } 00114 if(ntag != ON && ntag != tstate) { // last, self in different half-spaces 00115 MT_Point3 mpoint = BOP_intersectPlane( m_plane, lpoint, npoint ); 00116 if (m_inChild != NULL) inside.push_back(mpoint); 00117 if (m_outChild != NULL) outside.push_back(mpoint); 00118 tstate = ntag; 00119 } 00120 } else { // last point on hyperplane, so we're switching 00121 // half-spaces 00122 // boundary point belong to both faces 00123 if (m_inChild != NULL) inside.push_back(lpoint); 00124 if (m_outChild != NULL) outside.push_back(lpoint); 00125 tstate = ntag; // state changes to new point tag 00126 } 00127 lpoint = npoint; // save point, tag for next iteration 00128 ltag = ntag; 00129 } 00130 00131 if (m_inChild != NULL) 00132 newDeep = m_inChild->addFace(inside, plane) + 1; 00133 else { 00134 m_inChild = new BOP_BSPNode(plane); 00135 newDeep = 2; 00136 } 00137 if (m_outChild != NULL) 00138 newDeep = MT_max(newDeep, m_outChild->addFace(outside, plane) + 1); 00139 else { 00140 m_outChild = new BOP_BSPNode(plane); 00141 newDeep = MT_max(newDeep,(unsigned int)2); 00142 } 00143 } 00144 00145 // update the deep attribute 00146 m_deep = MT_max(m_deep,newDeep); 00147 00148 return m_deep; 00149 } 00150 00156 BOP_TAG BOP_BSPNode::testPoint(const MT_Point3& p) const 00157 { 00158 return BOP_createTAG(BOP_classify(p,m_plane)); 00159 00160 } 00161 00170 BOP_TAG BOP_BSPNode::classifyFace(const MT_Point3& p1, 00171 const MT_Point3& p2, 00172 const MT_Point3& p3, 00173 const MT_Plane3& plane) const 00174 { 00175 // local variables 00176 MT_Point3 auxp1, auxp2; 00177 BOP_TAG auxtag1, auxtag2, auxtag3; 00178 00179 switch(BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3))) { 00180 // Classify the face on the IN side 00181 case IN_IN_IN : 00182 return classifyFaceIN(p1, p2, p3, plane); 00183 case IN_IN_ON : 00184 case IN_ON_IN : 00185 case ON_IN_IN : 00186 case IN_ON_ON : 00187 case ON_IN_ON : 00188 case ON_ON_IN : 00189 return BOP_addON(classifyFaceIN(p1, p2, p3, plane)); 00190 00191 // Classify the face on the OUT side 00192 case OUT_OUT_OUT : 00193 return classifyFaceOUT(p1, p2, p3, plane); 00194 case OUT_OUT_ON : 00195 case OUT_ON_OUT : 00196 case ON_OUT_OUT : 00197 case ON_ON_OUT : 00198 case ON_OUT_ON : 00199 case OUT_ON_ON : 00200 return BOP_addON(classifyFaceOUT(p1, p2, p3, plane)); 00201 00202 // Classify the ON face depending on it plane normal 00203 case ON_ON_ON : 00204 if (hasSameOrientation(plane)) 00205 return BOP_addON(classifyFaceIN(p1, p2, p3, plane)); 00206 else 00207 return BOP_addON(classifyFaceOUT(p1, p2, p3, plane)); 00208 00209 // Classify the face IN/OUT and one vertex ON 00210 // becouse only one ON, only one way to subdivide the face 00211 case IN_OUT_ON : 00212 auxp1 = BOP_intersectPlane(m_plane, p1, p2); 00213 auxtag1 = classifyFaceIN( p1, auxp1 , p3, plane); 00214 auxtag2 = classifyFaceOUT(auxp1, p2, p3, plane); 00215 return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT); 00216 00217 case OUT_IN_ON : 00218 auxp1 = BOP_intersectPlane(m_plane, p1, p2); 00219 auxtag1 = classifyFaceOUT(p1, auxp1, p3, plane); 00220 auxtag2 = classifyFaceIN( auxp1, p2, p3, plane); 00221 return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT); 00222 00223 case IN_ON_OUT : 00224 auxp1 = BOP_intersectPlane(m_plane, p1, p3); 00225 auxtag1 = classifyFaceIN( p1, p2, auxp1, plane); 00226 auxtag2 = classifyFaceOUT(p2, p3, auxp1, plane); 00227 return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT); 00228 00229 case OUT_ON_IN : 00230 auxp1 = BOP_intersectPlane(m_plane, p1, p3); 00231 auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane); 00232 auxtag2 = classifyFaceIN( p2, p3, auxp1, plane); 00233 return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT); 00234 00235 case ON_IN_OUT : 00236 auxp1 = BOP_intersectPlane(m_plane, p2, p3); 00237 auxtag1 = classifyFaceIN( p1, p2, auxp1, plane); 00238 auxtag2 = classifyFaceOUT(auxp1, p3, p1, plane); 00239 return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT); 00240 00241 case ON_OUT_IN : 00242 auxp1 = BOP_intersectPlane(m_plane, p2, p3); 00243 auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane); 00244 auxtag2 = classifyFaceIN( auxp1, p3, p1, plane); 00245 return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT); 00246 00247 // Classify IN/OUT face without ON vertices. 00248 // Two ways to divide the triangle, 00249 // will chose the least degenerated sub-triangles. 00250 case IN_OUT_OUT : 00251 auxp1 = BOP_intersectPlane(m_plane, p1, p2); 00252 auxp2 = BOP_intersectPlane(m_plane, p1, p3); 00253 00254 // f1: p1 auxp1 , auxp1 auxp2 00255 auxtag1 = classifyFaceIN(p1, auxp1, auxp2, plane); 00256 00257 // f2: auxp1 p2 , p2 auxp2; f3: p2 p3 , p3 auxp2 || 00258 // f2: auxp1 p3, p3 auxp2; f3: p2 p3 , p3 auxp1 00259 if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) { 00260 auxtag2 = classifyFaceOUT(auxp1, p2, auxp2, plane); 00261 auxtag3 = classifyFaceOUT(p2, p3, auxp2, plane); 00262 } 00263 else { 00264 auxtag2 = classifyFaceOUT(auxp1, p3, auxp2, plane); 00265 auxtag3 = classifyFaceOUT(p2, p3, auxp1, plane); 00266 } 00267 return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT); 00268 00269 case OUT_IN_IN : 00270 auxp1 = BOP_intersectPlane(m_plane, p1, p2); 00271 auxp2 = BOP_intersectPlane(m_plane, p1, p3); 00272 00273 // f1: p1 auxp1 , auxp1 auxp2 00274 auxtag1 = classifyFaceOUT(p1, auxp1, auxp2, plane); 00275 00276 // f2: auxp1 p2 , p2 auxp2; f3: p2 p3 , p3 auxp2 || 00277 // f2: auxp1 p3, p3 auxp2; f3: p2 p3 , p3 auxp1 00278 if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) { 00279 auxtag2 = classifyFaceIN(auxp1, p2, auxp2, plane); 00280 auxtag3 = classifyFaceIN(p2, p3, auxp2, plane); 00281 } 00282 else { 00283 auxtag2 = classifyFaceIN(auxp1, p3, auxp2, plane); 00284 auxtag3 = classifyFaceIN(p2, p3, auxp1, plane); 00285 } 00286 return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT); 00287 00288 case OUT_IN_OUT : 00289 auxp1 = BOP_intersectPlane(m_plane, p2, p1); 00290 auxp2 = BOP_intersectPlane(m_plane, p2, p3); 00291 00292 // f1: auxp1 p2 , p2 auxp2 00293 auxtag1 = classifyFaceIN(auxp1, p2, auxp2, plane); 00294 00295 // f2: p1 auxp1 , auxp1 auxp2; f3: p1 auxp2 , auxp2 p3 || 00296 // f2: p3 auxp1, auxp1 auxp2 f3:p1 auxp1, auxp1 p3 00297 if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) { 00298 auxtag2 = classifyFaceOUT(p1, auxp1, auxp2, plane); 00299 auxtag3 = classifyFaceOUT(p1, auxp2, p3, plane); 00300 } 00301 else { 00302 auxtag2 = classifyFaceOUT(p3, auxp1, auxp2, plane); 00303 auxtag3 = classifyFaceOUT(p1, auxp1, p3, plane); 00304 } 00305 return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT); 00306 00307 case IN_OUT_IN : 00308 auxp1 = BOP_intersectPlane(m_plane, p2, p1); 00309 auxp2 = BOP_intersectPlane(m_plane, p2, p3); 00310 00311 // f1: auxp1 p2 , p2 auxp2 00312 auxtag1 = classifyFaceOUT(auxp1, p2, auxp2, plane); 00313 00314 // f2: p1 auxp1 , auxp1 auxp2; f3: p1 auxp2 , auxp2 p3 || 00315 // f2: p3 auxp1, auxp1 auxp2 f3:p1 auxp1, auxp1 p3 00316 if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) { 00317 auxtag2 = classifyFaceIN(p1, auxp1, auxp2, plane); 00318 auxtag3 = classifyFaceIN(p1, auxp2, p3, plane); 00319 } 00320 else { 00321 auxtag2 = classifyFaceIN(p3, auxp1, auxp2, plane); 00322 auxtag3 = classifyFaceIN(p1, auxp1, p3, plane); 00323 } 00324 return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT); 00325 00326 case OUT_OUT_IN : 00327 auxp1 = BOP_intersectPlane(m_plane, p3, p1); 00328 auxp2 = BOP_intersectPlane(m_plane, p3, p2); 00329 00330 // f1: auxp1 auxp2 , auxp2 p3 00331 auxtag1 = classifyFaceIN(auxp1, auxp2, p3, plane); 00332 00333 // f2: p1 p2 , p2 auxp2; f3:p1 auxp2 , auxp2 auxp1 || 00334 // f2: p1 p2, p2 auxp1; f3:p2 auxp2, auxp2 auxp1 00335 if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) { 00336 auxtag2 = classifyFaceOUT(p1, p2, auxp2, plane); 00337 auxtag3 = classifyFaceOUT(p1, auxp2, auxp1, plane); 00338 } 00339 else { 00340 auxtag2 = classifyFaceOUT(p1, p2, auxp1, plane); 00341 auxtag3 = classifyFaceOUT(p2, auxp2, auxp1, plane); 00342 } 00343 return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT); 00344 00345 case IN_IN_OUT : 00346 auxp1 = BOP_intersectPlane(m_plane, p3, p1); 00347 auxp2 = BOP_intersectPlane(m_plane, p3, p2); 00348 00349 // f1: auxp1 auxp2 , auxp2 p3 00350 auxtag1 = classifyFaceOUT(auxp1, auxp2, p3, plane); 00351 00352 // f2: p1 p2 , p2 auxp2; f3:p1 auxp2 , auxp2 auxp1 || 00353 // f2: p1 p2, p2 auxp1; f3:p2 auxp2, auxp2 auxp1 00354 if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) { 00355 auxtag2 = classifyFaceIN(p1, p2, auxp2, plane); 00356 auxtag3 = classifyFaceIN(p1, auxp2, auxp1, plane); 00357 } 00358 else { 00359 auxtag2 = classifyFaceIN(p1, p2, auxp1, plane); 00360 auxtag3 = classifyFaceIN(p2, auxp2, auxp1, plane); 00361 } 00362 return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT); 00363 00364 default: 00365 return UNCLASSIFIED; 00366 } 00367 } 00368 00376 BOP_TAG BOP_BSPNode::classifyFaceIN(const MT_Point3& p1, 00377 const MT_Point3& p2, 00378 const MT_Point3& p3, 00379 const MT_Plane3& plane) const 00380 { 00381 if (m_inChild != NULL) 00382 return m_inChild->classifyFace(p1, p2, p3, plane); 00383 else 00384 return IN; 00385 } 00386 00394 BOP_TAG BOP_BSPNode::classifyFaceOUT(const MT_Point3& p1, 00395 const MT_Point3& p2, 00396 const MT_Point3& p3, 00397 const MT_Plane3& plane) const 00398 { 00399 if (m_outChild != NULL) 00400 return m_outChild->classifyFace(p1, p2, p3, plane); 00401 else 00402 return OUT; 00403 } 00404 00414 BOP_TAG BOP_BSPNode::simplifiedClassifyFace(const MT_Point3& p1, 00415 const MT_Point3& p2, 00416 const MT_Point3& p3, 00417 const MT_Plane3& plane) const 00418 { 00419 MT_Point3 ret[3]; 00420 00421 BOP_TAG tag = BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3)); 00422 00423 if ((tag & IN_IN_IN) != 0) { 00424 if ((tag & OUT_OUT_OUT) != 0) { 00425 if (splitTriangle(ret,m_plane,p1,p2,p3,tag)<0) 00426 return simplifiedClassifyFaceIN(ret[0],ret[1],ret[2],plane); 00427 else 00428 return simplifiedClassifyFaceOUT(ret[0],ret[1],ret[2],plane); 00429 } 00430 else { 00431 return simplifiedClassifyFaceIN(p1,p2,p3,plane); 00432 } 00433 } 00434 else { 00435 if ((tag & OUT_OUT_OUT) != 0) { 00436 return simplifiedClassifyFaceOUT(p1,p2,p3,plane); 00437 } 00438 else { 00439 if (hasSameOrientation(plane)) { 00440 return simplifiedClassifyFaceIN(p1,p2,p3,plane); 00441 } 00442 else { 00443 return simplifiedClassifyFaceOUT(p1,p2,p3,plane); 00444 } 00445 } 00446 } 00447 00448 return IN; 00449 } 00450 00458 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceIN(const MT_Point3& p1, 00459 const MT_Point3& p2, 00460 const MT_Point3& p3, 00461 const MT_Plane3& plane) const 00462 { 00463 if (m_inChild != NULL) 00464 return m_inChild->simplifiedClassifyFace(p1, p2, p3, plane); 00465 else 00466 return IN; 00467 } 00468 00476 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceOUT(const MT_Point3& p1, 00477 const MT_Point3& p2, 00478 const MT_Point3& p3, 00479 const MT_Plane3& plane) const 00480 { 00481 if (m_outChild != NULL) 00482 return m_outChild->simplifiedClassifyFace(p1, p2, p3, plane); 00483 else 00484 return OUT; 00485 } 00486 00492 bool BOP_BSPNode::hasSameOrientation(const MT_Plane3& plane) const 00493 { 00494 return (BOP_orientation(m_plane,plane)>0); 00495 } 00496 00501 int BOP_BSPNode::compChildren() const 00502 { 00503 unsigned int deep1 = (m_inChild == NULL?0:m_inChild->getDeep()); 00504 unsigned int deep2 = (m_outChild == NULL?0:m_outChild->getDeep()); 00505 00506 if (deep1 == deep2) 00507 return 0; 00508 else if (deep1 < deep2) 00509 return -1; 00510 else 00511 return 1; 00512 } 00513 00524 int BOP_BSPNode::splitTriangle(MT_Point3* res, 00525 const MT_Plane3& plane, 00526 const MT_Point3& p1, 00527 const MT_Point3& p2, 00528 const MT_Point3& p3, 00529 const BOP_TAG tag) const 00530 { 00531 switch (tag) { 00532 case IN_OUT_ON : 00533 if (compChildren()<0) { 00534 // f1: p1 new p3 || new = splitedge(p1,p2) 00535 res[0] = p1; 00536 res[1] = BOP_intersectPlane( plane, p1, p2 ); 00537 res[2] = p3; 00538 return -1; 00539 }else{ 00540 // f1: p2 new p3 || new = splitedge(p1,p2) 00541 res[0] = p2; 00542 res[1] = p3; 00543 res[2] = BOP_intersectPlane( plane, p1, p2 ); 00544 return 1; 00545 } 00546 case OUT_IN_ON : 00547 if (compChildren()<0) { 00548 // f1: p2 new p3 || new = splitedge(p1,p2) 00549 res[0] = p2; 00550 res[1] = p3; 00551 res[2] = BOP_intersectPlane( plane, p1, p2 ); 00552 return -1; 00553 }else{ 00554 // f1: p1 new p3 || new = splitedge(p1,p2) 00555 res[0] = p1; 00556 res[1] = BOP_intersectPlane( plane, p1, p2 ); 00557 res[2] = p3; 00558 return 1; 00559 } 00560 case IN_ON_OUT : 00561 if (compChildren()<0) { 00562 // f1: p1 p2 new || new = splitedge(p1,p3) 00563 res[0] = p1; 00564 res[1] = p2; 00565 res[2] = BOP_intersectPlane( plane, p1, p3 ); 00566 return -1; 00567 }else{ 00568 // f1: p2 p3 new || new = splitedge(p1,p3) 00569 res[0] = p2; 00570 res[1] = p3; 00571 res[2] = BOP_intersectPlane( plane, p1, p3 ); 00572 return 1; 00573 } 00574 case OUT_ON_IN : 00575 if (compChildren()<0) { 00576 // f1: p2 p3 new || new = splitedge(p1,p3) 00577 res[0] = p2; 00578 res[1] = p3; 00579 res[2] = BOP_intersectPlane( plane, p1, p3 ); 00580 return -1; 00581 }else{ 00582 // f1: p1 p2 new || new = splitedge(p1,p3) 00583 res[0] = p1; 00584 res[1] = p2; 00585 res[2] = BOP_intersectPlane( plane, p1, p3 ); 00586 return 1; 00587 } 00588 case ON_IN_OUT : 00589 if (compChildren()<0) { 00590 // f1: p1 p2 new || new = splitedge(p2,p3) 00591 res[0] = p1; 00592 res[1] = p2; 00593 res[2] = BOP_intersectPlane( plane, p2, p3 ); 00594 return -1; 00595 }else{ 00596 // f1: p1 p3 new || new = splitedge(p2,p3) 00597 res[0] = p1; 00598 res[1] = BOP_intersectPlane( plane, p2, p3 ); 00599 res[2] = p3; 00600 return 1; 00601 } 00602 case ON_OUT_IN : 00603 if (compChildren()<0) { 00604 // f1: p1 p2 new || new = splitedge(p2,p3) 00605 res[0] = p1; 00606 res[1] = BOP_intersectPlane( plane, p2, p3 ); 00607 res[2] = p3; 00608 return -1; 00609 }else{ 00610 // f1: p1 p2 new || new = splitedge(p2,p3) 00611 res[0] = p1; 00612 res[1] = p2; 00613 res[2] = BOP_intersectPlane( plane, p2, p3 ); 00614 return 1; 00615 } 00616 case IN_OUT_OUT : 00617 if (compChildren()<=0) { 00618 // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3) 00619 res[0] = p1; 00620 res[1] = BOP_intersectPlane( plane, p1, p2 ); 00621 res[2] = BOP_intersectPlane( plane, p1, p3 ); 00622 return -1; 00623 }else{ 00624 // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3) 00625 res[0] = BOP_intersectPlane( plane, p1, p2 ); 00626 res[1] = p2; 00627 res[2] = p3; 00628 return 1; 00629 } 00630 case OUT_IN_IN : 00631 if (compChildren()<0) { 00632 // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3) 00633 res[0] = BOP_intersectPlane( plane, p1, p2 ); 00634 res[1] = p2; 00635 res[2] = p3; 00636 return -1; 00637 }else { 00638 // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3) 00639 res[0] = p1; 00640 res[1] = BOP_intersectPlane( plane, p1, p2 ); 00641 res[2] = BOP_intersectPlane( plane, p1, p3 ); 00642 return 1; 00643 } 00644 case OUT_IN_OUT : 00645 if (compChildren()<=0) { 00646 // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3) 00647 res[0] = BOP_intersectPlane( plane, p2, p1 ); 00648 res[1] = p2; 00649 res[2] = BOP_intersectPlane( plane, p2, p3 ); 00650 return -1; 00651 }else { 00652 // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3) 00653 res[0] = p1; 00654 res[1] = BOP_intersectPlane( plane, p2, p1 ); 00655 res[2] = BOP_intersectPlane( plane, p2, p3 ); 00656 return 1; 00657 } 00658 case IN_OUT_IN : 00659 if (compChildren()<0) { 00660 // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3) 00661 res[0] = p1; 00662 res[1] = BOP_intersectPlane( plane, p2, p1 ); 00663 res[2] = BOP_intersectPlane( plane, p2, p3 ); 00664 return -1; 00665 }else{ 00666 // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3) 00667 res[0] = BOP_intersectPlane( plane, p2, p1 ); 00668 res[1] = p2; 00669 res[2] = BOP_intersectPlane( plane, p2, p3 ); 00670 return 1; 00671 } 00672 case OUT_OUT_IN : 00673 if (compChildren()<=0) { 00674 // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2) 00675 res[0] = BOP_intersectPlane( plane, p3, p1 ); 00676 res[1] = BOP_intersectPlane( plane, p3, p2 ); 00677 res[2] = p3; 00678 return -1; 00679 }else{ 00680 // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2) 00681 res[0] = BOP_intersectPlane( plane, p3, p1 ); 00682 res[1] = p1; 00683 res[2] = p2; 00684 return 1; 00685 } 00686 case IN_IN_OUT : 00687 if (compChildren()<0) { 00688 // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2) 00689 res[0] = BOP_intersectPlane( plane, p3, p1 ); 00690 res[1] = p1; 00691 res[2] = p2; 00692 return -1; 00693 }else{ 00694 // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2) 00695 res[0] = BOP_intersectPlane( plane, p3, p1 ); 00696 res[1] = BOP_intersectPlane( plane, p3, p2 ); 00697 res[2] = p3; 00698 return 1; 00699 } 00700 default: 00701 return 0; 00702 } 00703 } 00704 00708 void BOP_BSPNode::print(unsigned int deep) 00709 { 00710 cout << "(" << deep << "," << m_plane << ")," << endl; 00711 if (m_inChild != NULL) 00712 m_inChild->print(deep + 1); 00713 else 00714 cout << "(" << deep+1 << ",None)," << endl; 00715 if (m_outChild != NULL) 00716 m_outChild->print(deep + 1); 00717 else 00718 cout << "(" << deep+1 << ",None)," << endl; 00719 }