a var was declared twice in the same function, just removing the
[blender-staging.git] / intern / boolop / intern / BOP_BSPNode.cpp
1 /**
2  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version. The Blender
8  * Foundation also sells licenses for use in proprietary software under
9  * the Blender License.  See http://www.blender.org/BL/ for information
10  * about this.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software Foundation,
19  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
20  *
21  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
22  * All rights reserved.
23  *
24  * The Original Code is: all of this file.
25  *
26  * Contributor(s): none yet.
27  *
28  * ***** END GPL/BL DUAL LICENSE BLOCK *****
29  */
30  
31 #include "BOP_MathUtils.h"
32 #include "BOP_BSPNode.h"
33 #include "MT_assert.h"
34 #include "MT_MinMax.h"
35 #include <iostream>
36 using namespace std;
37
38 /**
39  * Constructs a new BSP node.
40  * @param plane split plane.
41  */
42 BOP_BSPNode::BOP_BSPNode(const MT_Plane3& plane)
43 {
44         m_plane      = plane;
45         m_inChild    = NULL;
46         m_outChild   = NULL;
47         m_deep       = 1;
48 }
49
50 /**
51  * Destroys a BSP tree.
52  */
53 BOP_BSPNode::~BOP_BSPNode()
54 {
55         if (m_inChild!=NULL) delete m_inChild;
56         if (m_outChild!=NULL) delete m_outChild;
57 }
58
59 /**
60  * Adds a new face to this BSP tree.
61  * @param pts vector containing face points
62  * @param plane face plane.
63  */
64
65 unsigned int BOP_BSPNode::addFace(BOP_BSPPoints pts,
66                                                                   const MT_Plane3& plane )
67 {
68         unsigned int newDeep = 0;
69         BOP_TAG tag = ON;
70
71         // find out if any points on the "face" lie in either half-space
72         BOP_IT_BSPPoints ptsEnd = pts.end();
73         for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
74                 tag = (BOP_TAG) ((int) tag | (int)testPoint(*itp));
75         }
76  
77         if (tag == ON) { }              // face lies on hyperplane: do nothing
78         else if ((tag & IN) != 0 && (tag & OUT) == 0) { // face is entirely on inside
79                 if (m_inChild != NULL)
80                         newDeep = m_inChild->addFace(pts, plane) + 1;
81                 else {
82                         m_inChild = new BOP_BSPNode(plane);
83                         newDeep = 2;
84                 }    
85         } else if ((tag & OUT) != 0 && (tag & IN) == 0) { // face is entirely on outside
86                 if (m_outChild != NULL)
87                         newDeep = m_outChild->addFace(pts, plane) + 1;
88                 else {
89                         m_outChild = new BOP_BSPNode(plane);
90                         newDeep = 2;
91                 }      
92         } else { // face lies in both half-spaces: split it
93                 BOP_BSPPoints inside, outside;
94                 MT_Point3 lpoint= pts[pts.size()-1];
95                 BOP_TAG ltag = testPoint(lpoint);
96                 BOP_TAG tstate = ltag;
97
98                 // classify each line segment, looking for endpoints which lie on different
99                 // sides of the hyperplane.
100
101                 ptsEnd = pts.end();
102                 for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
103                         MT_Point3 npoint= *itp;
104                         BOP_TAG ntag = testPoint(npoint);
105
106                         if(ltag != ON) {        // last point not on hyperplane
107                                 if(tstate == IN) {
108                                         if (m_inChild != NULL) inside.push_back(lpoint);
109                                 } else {
110                                         if (m_outChild != NULL) outside.push_back(lpoint);
111                                 }
112                                 if(ntag != ON && ntag != tstate) {      // last, self in different half-spaces 
113                                         MT_Point3 mpoint = BOP_intersectPlane( m_plane, lpoint, npoint );
114                                         if (m_inChild != NULL) inside.push_back(mpoint);
115                                         if (m_outChild != NULL) outside.push_back(mpoint);
116                                         tstate = ntag;
117                                 }
118                         } else {                        // last point on hyperplane, so we're switching
119                                                                 // half-spaces
120                                                                 // boundary point belong to both faces
121                                 if (m_inChild != NULL) inside.push_back(lpoint);        
122                                 if (m_outChild != NULL) outside.push_back(lpoint);
123                                 tstate = ntag;  // state changes to new point tag
124                         }
125                         lpoint = npoint;        // save point, tag for next iteration
126                         ltag = ntag;
127                 }
128
129                 if (m_inChild != NULL)
130                         newDeep = m_inChild->addFace(inside, plane) + 1;
131                 else {
132                         m_inChild = new BOP_BSPNode(plane);
133                         newDeep = 2;
134                 }    
135                 if (m_outChild != NULL)
136                         newDeep = MT_max(newDeep, m_outChild->addFace(outside, plane) + 1);
137                 else {
138                         m_outChild = new BOP_BSPNode(plane);
139                         newDeep = MT_max(newDeep,(unsigned int)2);
140                 }      
141         }
142         
143         // update the deep attribute
144         m_deep = MT_max(m_deep,newDeep);
145         
146         return m_deep;
147 }
148
149 /**
150  * Tests the point situation respect the node plane.
151  * @param p point to test.
152  * @return TAG result: IN, OUT or ON.
153  */
154 BOP_TAG BOP_BSPNode::testPoint(const MT_Point3& p) const
155 {
156   return BOP_createTAG(BOP_classify(p,m_plane));
157
158 }
159
160 /**
161  * Classifies a face using its coordinates and plane.
162  * @param p1 first point.
163  * @param p2 second point.
164  * @param p3 third point.
165  * @param plane face plane.
166  * @return TAG result: IN, OUT or IN&OUT.
167  */
168 BOP_TAG BOP_BSPNode::classifyFace(const MT_Point3& p1, 
169                                                                   const MT_Point3& p2, 
170                                                                   const MT_Point3& p3, 
171                                                                   const MT_Plane3& plane) const
172 {
173         // local variables
174         MT_Point3 auxp1, auxp2;
175         BOP_TAG auxtag1, auxtag2, auxtag3;
176
177         switch(BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3))) {
178                 // Classify the face on the IN side
179                 case IN_IN_IN : 
180                         return classifyFaceIN(p1, p2, p3, plane);
181                 case IN_IN_ON :
182                 case IN_ON_IN :
183                 case ON_IN_IN :
184                 case IN_ON_ON :
185                 case ON_IN_ON :
186                 case ON_ON_IN :
187                         return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
188         
189                 // Classify the face on the OUT side
190                 case OUT_OUT_OUT :
191                         return classifyFaceOUT(p1, p2, p3, plane);
192                 case OUT_OUT_ON :
193                 case OUT_ON_OUT :
194                 case ON_OUT_OUT :
195                 case ON_ON_OUT :
196                 case ON_OUT_ON :
197                 case OUT_ON_ON :
198                         return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
199         
200                 // Classify the ON face depending on it plane normal
201                 case ON_ON_ON :
202                         if (hasSameOrientation(plane))
203                                 return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
204                         else
205                                 return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
206
207                 // Classify the face IN/OUT and one vertex ON
208                 // becouse only one ON, only one way to subdivide the face
209                 case IN_OUT_ON :
210                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
211                         auxtag1 = classifyFaceIN( p1,    auxp1 , p3, plane);
212                         auxtag2 = classifyFaceOUT(auxp1, p2,     p3, plane);
213                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
214
215                 case OUT_IN_ON :
216                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
217                         auxtag1 = classifyFaceOUT(p1,    auxp1, p3, plane);
218                         auxtag2 = classifyFaceIN( auxp1, p2,    p3, plane);
219                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
220
221                 case IN_ON_OUT :
222                         auxp1 = BOP_intersectPlane(m_plane, p1, p3);
223                         auxtag1 = classifyFaceIN( p1, p2, auxp1, plane);
224                         auxtag2 = classifyFaceOUT(p2, p3, auxp1, plane);
225                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
226
227                 case OUT_ON_IN :
228                         auxp1 = BOP_intersectPlane(m_plane, p1, p3);
229                         auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane);
230                         auxtag2 = classifyFaceIN( p2, p3, auxp1, plane);
231                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
232
233                 case ON_IN_OUT :
234                         auxp1 = BOP_intersectPlane(m_plane, p2, p3);
235                         auxtag1 = classifyFaceIN( p1,    p2, auxp1, plane);
236                         auxtag2 = classifyFaceOUT(auxp1, p3, p1,    plane);
237                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
238
239                 case ON_OUT_IN :
240                         auxp1 = BOP_intersectPlane(m_plane, p2, p3);
241                         auxtag1 = classifyFaceOUT(p1,    p2, auxp1, plane);
242                         auxtag2 = classifyFaceIN( auxp1, p3, p1,    plane);
243                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
244
245                 // Classify IN/OUT face without ON vertices.
246                 // Two ways to divide the triangle, 
247                 // will chose the least degenerated sub-triangles.
248                 case IN_OUT_OUT :
249                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
250                         auxp2 = BOP_intersectPlane(m_plane, p1, p3);
251         
252                         // f1: p1 auxp1 , auxp1 auxp2
253                         auxtag1 = classifyFaceIN(p1, auxp1, auxp2, plane);
254         
255                         // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||  
256                         // f2: auxp1 p3, p3 auxp2;   f3: p2 p3 , p3 auxp1
257                         if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
258                                 auxtag2 = classifyFaceOUT(auxp1, p2, auxp2, plane);
259                                 auxtag3 = classifyFaceOUT(p2,    p3, auxp2, plane);
260                         }
261                         else {
262                                 auxtag2 = classifyFaceOUT(auxp1, p3, auxp2, plane);
263                                 auxtag3 = classifyFaceOUT(p2,    p3, auxp1, plane);
264                         }
265                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
266
267                 case OUT_IN_IN :
268                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
269                         auxp2 = BOP_intersectPlane(m_plane, p1, p3);
270         
271                         // f1: p1 auxp1 , auxp1 auxp2
272                         auxtag1 = classifyFaceOUT(p1, auxp1, auxp2, plane);
273         
274                         // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||
275                         // f2: auxp1 p3, p3 auxp2;  f3: p2 p3 , p3 auxp1
276                         if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
277                                 auxtag2 = classifyFaceIN(auxp1, p2, auxp2, plane);
278                                 auxtag3 = classifyFaceIN(p2, p3, auxp2, plane);
279                         }
280                         else {
281                                 auxtag2 = classifyFaceIN(auxp1, p3, auxp2, plane);
282                                 auxtag3 = classifyFaceIN(p2,    p3, auxp1, plane);
283                         }
284                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
285
286                 case OUT_IN_OUT :
287                         auxp1 = BOP_intersectPlane(m_plane, p2, p1);
288                         auxp2 = BOP_intersectPlane(m_plane, p2, p3);
289         
290                         // f1: auxp1 p2 , p2 auxp2
291                         auxtag1 = classifyFaceIN(auxp1, p2, auxp2, plane);
292         
293                         // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
294                         // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
295                         if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
296                                 auxtag2 = classifyFaceOUT(p1, auxp1, auxp2, plane);
297                                 auxtag3 = classifyFaceOUT(p1, auxp2, p3,    plane);
298                         }
299                         else {
300                                 auxtag2 = classifyFaceOUT(p3, auxp1, auxp2, plane);
301                                 auxtag3 = classifyFaceOUT(p1, auxp1, p3,    plane);
302                         }
303                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
304     
305                 case IN_OUT_IN :
306                         auxp1 = BOP_intersectPlane(m_plane, p2, p1);
307                         auxp2 = BOP_intersectPlane(m_plane, p2, p3);
308         
309                         // f1: auxp1 p2 , p2 auxp2
310                         auxtag1 = classifyFaceOUT(auxp1, p2, auxp2, plane);
311         
312                         // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
313                         // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
314                         if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
315                                 auxtag2 = classifyFaceIN(p1, auxp1, auxp2, plane);
316                                 auxtag3 = classifyFaceIN(p1, auxp2, p3,    plane);
317                         }
318                         else {
319                                 auxtag2 = classifyFaceIN(p3, auxp1, auxp2, plane);
320                                 auxtag3 = classifyFaceIN(p1, auxp1, p3,    plane);
321                         }
322                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
323         
324                 case OUT_OUT_IN :
325                         auxp1 = BOP_intersectPlane(m_plane, p3, p1);
326                         auxp2 = BOP_intersectPlane(m_plane, p3, p2);
327         
328                         // f1: auxp1 auxp2 , auxp2 p3
329                         auxtag1 = classifyFaceIN(auxp1, auxp2, p3, plane);
330         
331                         // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
332                         // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
333                         if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
334                                 auxtag2 = classifyFaceOUT(p1, p2,    auxp2, plane);
335                                 auxtag3 = classifyFaceOUT(p1, auxp2, auxp1, plane);
336                         }
337                         else {
338                                 auxtag2 = classifyFaceOUT(p1, p2,    auxp1, plane);
339                                 auxtag3 = classifyFaceOUT(p2, auxp2, auxp1, plane);
340                         }
341                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
342
343                 case IN_IN_OUT :
344                         auxp1 = BOP_intersectPlane(m_plane, p3, p1);
345                         auxp2 = BOP_intersectPlane(m_plane, p3, p2);
346         
347                         // f1: auxp1 auxp2 , auxp2 p3
348                         auxtag1 = classifyFaceOUT(auxp1, auxp2, p3, plane);
349         
350                         // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
351                         // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
352                         if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
353                                 auxtag2 = classifyFaceIN(p1, p2,    auxp2, plane);
354                                 auxtag3 = classifyFaceIN(p1, auxp2, auxp1, plane);
355                         }
356                         else {
357                                 auxtag2 = classifyFaceIN(p1, p2,    auxp1, plane);
358                                 auxtag3 = classifyFaceIN(p2, auxp2, auxp1, plane);
359                         }
360                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
361
362                 default:
363                         return UNCLASSIFIED;
364         }
365 }
366
367 /**
368  * Classifies a face through IN subtree.
369  * @param p1 firts face vertex.
370  * @param p2 second face vertex.
371  * @param p3 third face vertex.
372  * @param plane face plane.
373  */
374 BOP_TAG BOP_BSPNode::classifyFaceIN(const MT_Point3& p1, 
375                                                                         const MT_Point3& p2, 
376                                                                         const MT_Point3& p3, 
377                                                                         const MT_Plane3& plane) const
378 {
379         if (m_inChild != NULL)
380                 return m_inChild->classifyFace(p1, p2, p3, plane);
381         else
382                 return IN;
383 }
384
385 /**
386  * Classifies a face through OUT subtree.
387  * @param p1 firts face vertex.
388  * @param p2 second face vertex.
389  * @param p3 third face vertex.
390  * @param plane face plane.
391  */
392 BOP_TAG BOP_BSPNode::classifyFaceOUT(const MT_Point3& p1, 
393                                                                          const MT_Point3& p2, 
394                                                                          const MT_Point3& p3, 
395                                                                          const MT_Plane3& plane) const
396 {
397         if (m_outChild != NULL)
398                 return m_outChild->classifyFace(p1, p2, p3, plane);
399         else
400                 return OUT;
401 }
402
403 /**
404  * Simplified classification (optimized but requires that the face is not 
405  * INOUT; only works correctly with faces completely IN or OUT).
406  * @param p1 firts face vertex.
407  * @param p2 second face vertex.
408  * @param p3 third face vertex.
409  * @param plane face plane.
410  * @return TAG result: IN or OUT.
411  */
412 BOP_TAG BOP_BSPNode::simplifiedClassifyFace(const MT_Point3& p1, 
413                                                                                         const MT_Point3& p2, 
414                                                                                         const MT_Point3& p3, 
415                                                                                         const MT_Plane3& plane) const
416 {
417         MT_Point3 ret[3];
418
419         BOP_TAG tag = BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3));
420
421         if ((tag & IN_IN_IN) != 0) {
422                 if ((tag & OUT_OUT_OUT) != 0) {     
423                   if (splitTriangle(ret,m_plane,p1,p2,p3,tag)<0)
424                     return simplifiedClassifyFaceIN(ret[0],ret[1],ret[2],plane);
425                   else
426                     return simplifiedClassifyFaceOUT(ret[0],ret[1],ret[2],plane);
427                 }
428                 else {
429                         return simplifiedClassifyFaceIN(p1,p2,p3,plane);
430                 }
431         }
432         else {
433                 if ((tag & OUT_OUT_OUT) != 0) {
434                         return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
435                 }
436                 else {
437                         if (hasSameOrientation(plane)) {
438                                 return simplifiedClassifyFaceIN(p1,p2,p3,plane);
439                         }
440                         else {
441                                 return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
442                         }
443                 }
444         }
445         
446         return IN;
447 }
448
449 /**
450  * Simplified classify through IN subtree.
451  * @param p1 firts face vertex.
452  * @param p2 second face vertex.
453  * @param p3 third face vertex.
454  * @param plane face plane.
455  */
456 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceIN(const MT_Point3& p1, 
457                                                                                           const MT_Point3& p2, 
458                                                                                           const MT_Point3& p3, 
459                                                                                           const MT_Plane3& plane) const
460 {
461         if (m_inChild != NULL)
462                 return m_inChild->simplifiedClassifyFace(p1, p2, p3, plane);
463         else
464                 return IN;
465 }
466
467 /**
468  * Simplified classify through OUT subtree.
469  * @param p1 firts face vertex.
470  * @param p2 second face vertex.
471  * @param p3 third face vertex.
472  * @param plane face plane.
473  */
474 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceOUT(const MT_Point3& p1, 
475                                                                                            const MT_Point3& p2, 
476                                                                                            const MT_Point3& p3, 
477                                                                                            const MT_Plane3& plane) const
478 {
479         if (m_outChild != NULL)
480                 return m_outChild->simplifiedClassifyFace(p1, p2, p3, plane);
481         else
482                 return OUT;
483 }
484
485 /**
486  * Determine if the input plane have the same orientation of the node plane.
487  * @param plane plane to test.
488  * @return TRUE if have the same orientation, FALSE otherwise.
489  */
490 bool BOP_BSPNode::hasSameOrientation(const MT_Plane3& plane) const
491 {
492         return (BOP_orientation(m_plane,plane)>0);
493 }
494
495 /**
496  * Comparation between both childrens.
497  * @return 0 equal deep, 1 inChild more deep than outChild and -1 otherwise.
498  */
499 int BOP_BSPNode::compChildren() const
500 {
501         unsigned int deep1 = (m_inChild == NULL?0:m_inChild->getDeep());
502         unsigned int deep2 = (m_outChild == NULL?0:m_outChild->getDeep());
503         
504         if (deep1 == deep2)
505                 return 0;
506         else if (deep1 < deep2)
507                 return -1;
508         else
509                 return 1;
510 }
511
512 /**
513  * Extract a subtriangle from input triangle, is used for simplified classification.
514  * The subtriangle is obtained spliting the input triangle by input plane.
515  * @param res output subtriangle result.
516  * @param plane spliter plane.
517  * @param p1 first triangle point.
518  * @param p2 second triangle point.
519  * @param p3 third triangle point.
520  * @param tag triangle orientation respect the plane.
521  */
522 int BOP_BSPNode::splitTriangle(MT_Point3* res, 
523                                                            const MT_Plane3& plane, 
524                                                            const MT_Point3& p1, 
525                                                            const MT_Point3& p2, 
526                                                            const MT_Point3& p3, 
527                                                            const BOP_TAG tag) const
528 {
529         switch (tag) {
530                 case IN_OUT_ON :
531                   if (compChildren()<0) {
532                     // f1: p1 new p3 || new = splitedge(p1,p2)
533                     res[0] = p1;
534                     res[1] = BOP_intersectPlane( plane, p1, p2 );
535                     res[2] = p3;
536                     return -1;
537                   }else{
538                     // f1: p2 new p3 || new = splitedge(p1,p2)
539                     res[0] = p2;
540                     res[1] = p3;
541                     res[2] = BOP_intersectPlane( plane, p1, p2 );
542                     return 1;
543                   }
544                 case OUT_IN_ON :
545                   if (compChildren()<0) {
546                     // f1: p2 new p3 || new = splitedge(p1,p2)
547                     res[0] = p2;
548                     res[1] = p3;
549                     res[2] = BOP_intersectPlane( plane, p1, p2 );
550                     return -1;
551                   }else{
552                     // f1: p1 new p3 || new = splitedge(p1,p2)
553                     res[0] = p1;
554                     res[1] = BOP_intersectPlane( plane, p1, p2 );
555                     res[2] = p3;
556                     return 1;
557                   }
558                 case IN_ON_OUT :
559                   if (compChildren()<0) {
560                     // f1: p1 p2 new || new = splitedge(p1,p3)
561                     res[0] = p1;
562                     res[1] = p2;
563                     res[2] = BOP_intersectPlane( plane, p1, p3 );
564                     return -1;
565                   }else{
566                     // f1: p2 p3 new || new = splitedge(p1,p3)
567                     res[0] = p2;
568                     res[1] = p3;
569                     res[2] = BOP_intersectPlane( plane, p1, p3 );
570                     return 1;
571                   }
572                 case OUT_ON_IN :
573                   if (compChildren()<0) {
574                     // f1: p2 p3 new || new = splitedge(p1,p3)
575                     res[0] = p2;
576                     res[1] = p3;
577                     res[2] = BOP_intersectPlane( plane, p1, p3 );
578                     return -1;
579                   }else{
580                     // f1: p1 p2 new || new = splitedge(p1,p3)
581                     res[0] = p1;
582                     res[1] = p2;
583                     res[2] = BOP_intersectPlane( plane, p1, p3 );
584                     return 1;
585                   }
586                 case ON_IN_OUT :
587                   if (compChildren()<0) {
588                     // f1: p1 p2 new || new = splitedge(p2,p3)
589                     res[0] = p1;
590                     res[1] = p2;
591                     res[2] = BOP_intersectPlane( plane, p2, p3 );
592                     return -1;
593                   }else{
594                     // f1: p1 p3 new || new = splitedge(p2,p3)
595                     res[0] = p1;
596                     res[1] = BOP_intersectPlane( plane, p2, p3 );
597                     res[2] = p3;
598                     return 1;
599                   }
600                 case ON_OUT_IN :
601                   if (compChildren()<0) {
602                     // f1: p1 p2 new || new = splitedge(p2,p3)
603                     res[0] = p1;
604                     res[1] = BOP_intersectPlane( plane, p2, p3 );
605                     res[2] = p3;
606                     return -1;
607                   }else{
608                     // f1: p1 p2 new || new = splitedge(p2,p3)
609                     res[0] = p1;
610                     res[1] = p2;
611                     res[2] = BOP_intersectPlane( plane, p2, p3 );
612                     return 1;
613                   }
614                 case IN_OUT_OUT :
615                   if (compChildren()<=0) {
616                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
617                     res[0] = p1;
618                     res[1] = BOP_intersectPlane( plane, p1, p2 );
619                     res[2] = BOP_intersectPlane( plane, p1, p3 );
620                     return -1;
621                   }else{
622                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
623                     res[0] = BOP_intersectPlane( plane, p1, p2 );
624                     res[1] = p2;
625                     res[2] = p3;
626                     return 1;
627                   }
628                 case OUT_IN_IN :
629                   if (compChildren()<0) {
630                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
631                     res[0] = BOP_intersectPlane( plane, p1, p2 );
632                     res[1] = p2;
633                     res[2] = p3;
634                     return -1;
635                   }else {
636                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
637                     res[0] = p1;
638                     res[1] = BOP_intersectPlane( plane, p1, p2 );
639                     res[2] = BOP_intersectPlane( plane, p1, p3 );
640                     return 1;
641                   }
642                 case OUT_IN_OUT :
643                   if (compChildren()<=0) {
644                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
645                     res[0] = BOP_intersectPlane( plane, p2, p1 );
646                     res[1] = p2;
647                     res[2] = BOP_intersectPlane( plane, p2, p3 );
648                     return -1;
649                   }else {
650                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
651                     res[0] = p1;
652                     res[1] = BOP_intersectPlane( plane, p2, p1 );
653                     res[2] = BOP_intersectPlane( plane, p2, p3 );
654                     return 1;
655                   }
656                 case IN_OUT_IN :
657                   if (compChildren()<0) {
658                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
659                     res[0] = p1;
660                     res[1] = BOP_intersectPlane( plane, p2, p1 );
661                     res[2] = BOP_intersectPlane( plane, p2, p3 );
662                     return -1;
663                   }else{
664                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
665                     res[0] = BOP_intersectPlane( plane, p2, p1 );
666                     res[1] = p2;
667                     res[2] = BOP_intersectPlane( plane, p2, p3 );
668                     return 1;
669                   }
670                 case OUT_OUT_IN :
671                   if (compChildren()<=0) {
672                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
673                     res[0] = BOP_intersectPlane( plane, p3, p1 );
674                     res[1] = BOP_intersectPlane( plane, p3, p2 );
675                     res[2] = p3;
676                     return -1;
677                   }else{
678                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
679                     res[0] = BOP_intersectPlane( plane, p3, p1 );
680                     res[1] = p1;
681                     res[2] = p2;
682                     return 1;
683                   }
684                 case IN_IN_OUT :
685                   if (compChildren()<0) {
686                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
687                     res[0] = BOP_intersectPlane( plane, p3, p1 );
688                     res[1] = p1;
689                     res[2] = p2;
690                     return -1;
691                   }else{
692                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
693                     res[0] = BOP_intersectPlane( plane, p3, p1 );
694                     res[1] = BOP_intersectPlane( plane, p3, p2 );
695                     res[2] = p3;
696                     return 1;
697                   }
698         default:
699           return 0;
700         }
701 }
702
703 /**
704  * Debug info.
705  */
706 void BOP_BSPNode::print(unsigned int deep)
707 {
708         cout << "(" << deep << "," << m_plane << ")," << endl;
709         if (m_inChild != NULL)
710                 m_inChild->print(deep + 1);
711         else
712                 cout << "(" << deep+1 << ",None)," << endl;
713         if (m_outChild != NULL)
714                 m_outChild->print(deep + 1);
715         else
716                 cout << "(" << deep+1 << ",None)," << endl;
717 }