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