New files from new booleans
[blender.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 p1 first face point.
62  * @param p2 second face point.
63  * @param p3 third face point.
64  * @param plane face plane.
65  */
66 unsigned int BOP_BSPNode::addFace(const MT_Point3& p1, 
67                                                                   const MT_Point3& p2, 
68                                                                   const MT_Point3& p3, 
69                                                                   const MT_Plane3& plane)
70 {
71         unsigned int newDeep = 0;
72         BOP_TAG tag = BOP_createTAG(testPoint(p1), testPoint(p2), testPoint(p3));
73         if ((tag & IN_IN_IN) != 0) {
74                 if (m_inChild != NULL)
75                         newDeep = m_inChild->addFace(p1, p2, p3, plane) + 1;
76                 else {
77                         m_inChild = new BOP_BSPNode(plane);
78                         newDeep = 2;
79                 }    
80         }
81         
82         if ((tag & OUT_OUT_OUT) != 0){
83                 if (m_outChild != NULL)
84                         newDeep = max(newDeep, m_outChild->addFace(p1, p2, p3, plane) + 1);
85                 else {
86                         m_outChild = new BOP_BSPNode(plane);
87                         newDeep = max(newDeep,(unsigned int)2);
88                 }      
89         }
90         
91         // update the deep attribute
92         m_deep = MT_max(m_deep,newDeep);
93         
94         return m_deep;
95 }
96
97 /**
98  * Tests the point situation respect the node plane.
99  * @param p point to test.
100  * @return TAG result: IN, OUT or ON.
101  */
102 BOP_TAG BOP_BSPNode::testPoint(const MT_Point3& p) const
103 {
104   return BOP_createTAG(BOP_classify(p,m_plane));
105
106 }
107
108 /**
109  * Classifies a face using its coordinates and plane.
110  * @param p1 first point.
111  * @param p2 second point.
112  * @param p3 third point.
113  * @param plane face plane.
114  * @return TAG result: IN, OUT or IN&OUT.
115  */
116 BOP_TAG BOP_BSPNode::classifyFace(const MT_Point3& p1, 
117                                                                   const MT_Point3& p2, 
118                                                                   const MT_Point3& p3, 
119                                                                   const MT_Plane3& plane) const
120 {
121         // local variables
122         MT_Point3 auxp1, auxp2;
123         BOP_TAG auxtag1, auxtag2, auxtag3;
124
125         switch(BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3))) {
126                 // Classify the face on the IN side
127                 case IN_IN_IN : 
128                         return classifyFaceIN(p1, p2, p3, plane);
129                 case IN_IN_ON :
130                 case IN_ON_IN :
131                 case ON_IN_IN :
132                 case IN_ON_ON :
133                 case ON_IN_ON :
134                 case ON_ON_IN :
135                         return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
136         
137                 // Classify the face on the OUT side
138                 case OUT_OUT_OUT :
139                         return classifyFaceOUT(p1, p2, p3, plane);
140                 case OUT_OUT_ON :
141                 case OUT_ON_OUT :
142                 case ON_OUT_OUT :
143                 case ON_ON_OUT :
144                 case ON_OUT_ON :
145                 case OUT_ON_ON :
146                         return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
147         
148                 // Classify the ON face depending on it plane normal
149                 case ON_ON_ON :
150                         if (hasSameOrientation(plane))
151                                 return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
152                         else
153                                 return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
154
155                 // Classify the face IN/OUT and one vertex ON
156                 // becouse only one ON, only one way to subdivide the face
157                 case IN_OUT_ON :
158                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
159                         auxtag1 = classifyFaceIN( p1,    auxp1 , p3, plane);
160                         auxtag2 = classifyFaceOUT(auxp1, p2,     p3, plane);
161                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
162
163                 case OUT_IN_ON :
164                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
165                         auxtag1 = classifyFaceOUT(p1,    auxp1, p3, plane);
166                         auxtag2 = classifyFaceIN( auxp1, p2,    p3, plane);
167                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
168
169                 case IN_ON_OUT :
170                         auxp1 = BOP_intersectPlane(m_plane, p1, p3);
171                         auxtag1 = classifyFaceIN( p1, p2, auxp1, plane);
172                         auxtag2 = classifyFaceOUT(p2, p3, auxp1, plane);
173                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
174
175                 case OUT_ON_IN :
176                         auxp1 = BOP_intersectPlane(m_plane, p1, p3);
177                         auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane);
178                         auxtag2 = classifyFaceIN( p2, p3, auxp1, plane);
179                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
180
181                 case ON_IN_OUT :
182                         auxp1 = BOP_intersectPlane(m_plane, p2, p3);
183                         auxtag1 = classifyFaceIN( p1,    p2, auxp1, plane);
184                         auxtag2 = classifyFaceOUT(auxp1, p3, p1,    plane);
185                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
186
187                 case ON_OUT_IN :
188                         auxp1 = BOP_intersectPlane(m_plane, p2, p3);
189                         auxtag1 = classifyFaceOUT(p1,    p2, auxp1, plane);
190                         auxtag2 = classifyFaceIN( auxp1, p3, p1,    plane);
191                         return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
192
193                 // Classify IN/OUT face without ON vertices.
194                 // Two ways to divide the triangle, 
195                 // will chose the least degenerated sub-triangles.
196                 case IN_OUT_OUT :
197                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
198                         auxp2 = BOP_intersectPlane(m_plane, p1, p3);
199         
200                         // f1: p1 auxp1 , auxp1 auxp2
201                         auxtag1 = classifyFaceIN(p1, auxp1, auxp2, plane);
202         
203                         // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||  
204                         // f2: auxp1 p3, p3 auxp2;   f3: p2 p3 , p3 auxp1
205                         if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
206                                 auxtag2 = classifyFaceOUT(auxp1, p2, auxp2, plane);
207                                 auxtag3 = classifyFaceOUT(p2,    p3, auxp2, plane);
208                         }
209                         else {
210                                 auxtag2 = classifyFaceOUT(auxp1, p3, auxp2, plane);
211                                 auxtag3 = classifyFaceOUT(p2,    p3, auxp1, plane);
212                         }
213                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
214
215                 case OUT_IN_IN :
216                         auxp1 = BOP_intersectPlane(m_plane, p1, p2);
217                         auxp2 = BOP_intersectPlane(m_plane, p1, p3);
218         
219                         // f1: p1 auxp1 , auxp1 auxp2
220                         auxtag1 = classifyFaceOUT(p1, auxp1, auxp2, plane);
221         
222                         // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||
223                         // f2: auxp1 p3, p3 auxp2;  f3: p2 p3 , p3 auxp1
224                         if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
225                                 auxtag2 = classifyFaceIN(auxp1, p2, auxp2, plane);
226                                 auxtag3 = classifyFaceIN(p2, p3, auxp2, plane);
227                         }
228                         else {
229                                 auxtag2 = classifyFaceIN(auxp1, p3, auxp2, plane);
230                                 auxtag3 = classifyFaceIN(p2,    p3, auxp1, plane);
231                         }
232                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
233
234                 case OUT_IN_OUT :
235                         auxp1 = BOP_intersectPlane(m_plane, p2, p1);
236                         auxp2 = BOP_intersectPlane(m_plane, p2, p3);
237         
238                         // f1: auxp1 p2 , p2 auxp2
239                         auxtag1 = classifyFaceIN(auxp1, p2, auxp2, plane);
240         
241                         // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
242                         // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
243                         if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
244                                 auxtag2 = classifyFaceOUT(p1, auxp1, auxp2, plane);
245                                 auxtag3 = classifyFaceOUT(p1, auxp2, p3,    plane);
246                         }
247                         else {
248                                 auxtag2 = classifyFaceOUT(p3, auxp1, auxp2, plane);
249                                 auxtag3 = classifyFaceOUT(p1, auxp1, p3,    plane);
250                         }
251                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
252     
253                 case IN_OUT_IN :
254                         auxp1 = BOP_intersectPlane(m_plane, p2, p1);
255                         auxp2 = BOP_intersectPlane(m_plane, p2, p3);
256         
257                         // f1: auxp1 p2 , p2 auxp2
258                         auxtag1 = classifyFaceOUT(auxp1, p2, auxp2, plane);
259         
260                         // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
261                         // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
262                         if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
263                                 auxtag2 = classifyFaceIN(p1, auxp1, auxp2, plane);
264                                 auxtag3 = classifyFaceIN(p1, auxp2, p3,    plane);
265                         }
266                         else {
267                                 auxtag2 = classifyFaceIN(p3, auxp1, auxp2, plane);
268                                 auxtag3 = classifyFaceIN(p1, auxp1, p3,    plane);
269                         }
270                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
271         
272                 case OUT_OUT_IN :
273                         auxp1 = BOP_intersectPlane(m_plane, p3, p1);
274                         auxp2 = BOP_intersectPlane(m_plane, p3, p2);
275         
276                         // f1: auxp1 auxp2 , auxp2 p3
277                         auxtag1 = classifyFaceIN(auxp1, auxp2, p3, plane);
278         
279                         // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
280                         // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
281                         if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
282                                 auxtag2 = classifyFaceOUT(p1, p2,    auxp2, plane);
283                                 auxtag3 = classifyFaceOUT(p1, auxp2, auxp1, plane);
284                         }
285                         else {
286                                 auxtag2 = classifyFaceOUT(p1, p2,    auxp1, plane);
287                                 auxtag3 = classifyFaceOUT(p2, auxp2, auxp1, plane);
288                         }
289                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
290
291                 case IN_IN_OUT :
292                         auxp1 = BOP_intersectPlane(m_plane, p3, p1);
293                         auxp2 = BOP_intersectPlane(m_plane, p3, p2);
294         
295                         // f1: auxp1 auxp2 , auxp2 p3
296                         auxtag1 = classifyFaceOUT(auxp1, auxp2, p3, plane);
297         
298                         // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
299                         // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
300                         if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
301                                 auxtag2 = classifyFaceIN(p1, p2,    auxp2, plane);
302                                 auxtag3 = classifyFaceIN(p1, auxp2, auxp1, plane);
303                         }
304                         else {
305                                 auxtag2 = classifyFaceIN(p1, p2,    auxp1, plane);
306                                 auxtag3 = classifyFaceIN(p2, auxp2, auxp1, plane);
307                         }
308                         return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
309
310                 default:
311                         return UNCLASSIFIED;
312         }
313 }
314
315 /**
316  * Classifies a face through IN subtree.
317  * @param p1 firts face vertex.
318  * @param p2 second face vertex.
319  * @param p3 third face vertex.
320  * @param plane face plane.
321  */
322 BOP_TAG BOP_BSPNode::classifyFaceIN(const MT_Point3& p1, 
323                                                                         const MT_Point3& p2, 
324                                                                         const MT_Point3& p3, 
325                                                                         const MT_Plane3& plane) const
326 {
327         if (m_inChild != NULL)
328                 return m_inChild->classifyFace(p1, p2, p3, plane);
329         else
330                 return IN;
331 }
332
333 /**
334  * Classifies a face through OUT subtree.
335  * @param p1 firts face vertex.
336  * @param p2 second face vertex.
337  * @param p3 third face vertex.
338  * @param plane face plane.
339  */
340 BOP_TAG BOP_BSPNode::classifyFaceOUT(const MT_Point3& p1, 
341                                                                          const MT_Point3& p2, 
342                                                                          const MT_Point3& p3, 
343                                                                          const MT_Plane3& plane) const
344 {
345         if (m_outChild != NULL)
346                 return m_outChild->classifyFace(p1, p2, p3, plane);
347         else
348                 return OUT;
349 }
350
351 /**
352  * Simplified classification (optimized but requires that the face is not 
353  * INOUT; only works correctly with faces completely IN or OUT).
354  * @param p1 firts face vertex.
355  * @param p2 second face vertex.
356  * @param p3 third face vertex.
357  * @param plane face plane.
358  * @return TAG result: IN or OUT.
359  */
360 BOP_TAG BOP_BSPNode::simplifiedClassifyFace(const MT_Point3& p1, 
361                                                                                         const MT_Point3& p2, 
362                                                                                         const MT_Point3& p3, 
363                                                                                         const MT_Plane3& plane) const
364 {
365         MT_Point3 ret[3];
366
367         BOP_TAG tag = BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3));
368
369         if ((tag & IN_IN_IN) != 0) {
370                 if ((tag & OUT_OUT_OUT) != 0) {     
371                   if (splitTriangle(ret,m_plane,p1,p2,p3,tag)<0)
372                     return simplifiedClassifyFaceIN(ret[0],ret[1],ret[2],plane);
373                   else
374                     return simplifiedClassifyFaceOUT(ret[0],ret[1],ret[2],plane);
375                 }
376                 else {
377                         return simplifiedClassifyFaceIN(p1,p2,p3,plane);
378                 }
379         }
380         else {
381                 if ((tag & OUT_OUT_OUT) != 0) {
382                         return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
383                 }
384                 else {
385                         if (hasSameOrientation(plane)) {
386                                 return simplifiedClassifyFaceIN(p1,p2,p3,plane);
387                         }
388                         else {
389                                 return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
390                         }
391                 }
392         }
393         
394         return IN;
395 }
396
397 /**
398  * Simplified classify through IN subtree.
399  * @param p1 firts face vertex.
400  * @param p2 second face vertex.
401  * @param p3 third face vertex.
402  * @param plane face plane.
403  */
404 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceIN(const MT_Point3& p1, 
405                                                                                           const MT_Point3& p2, 
406                                                                                           const MT_Point3& p3, 
407                                                                                           const MT_Plane3& plane) const
408 {
409         if (m_inChild != NULL)
410                 return m_inChild->simplifiedClassifyFace(p1, p2, p3, plane);
411         else
412                 return IN;
413 }
414
415 /**
416  * Simplified classify through OUT subtree.
417  * @param p1 firts face vertex.
418  * @param p2 second face vertex.
419  * @param p3 third face vertex.
420  * @param plane face plane.
421  */
422 BOP_TAG BOP_BSPNode::simplifiedClassifyFaceOUT(const MT_Point3& p1, 
423                                                                                            const MT_Point3& p2, 
424                                                                                            const MT_Point3& p3, 
425                                                                                            const MT_Plane3& plane) const
426 {
427         if (m_outChild != NULL)
428                 return m_outChild->simplifiedClassifyFace(p1, p2, p3, plane);
429         else
430                 return OUT;
431 }
432
433 /**
434  * Determine if the input plane have the same orientation of the node plane.
435  * @param plane plane to test.
436  * @return TRUE if have the same orientation, FALSE otherwise.
437  */
438 bool BOP_BSPNode::hasSameOrientation(const MT_Plane3& plane) const
439 {
440         return (BOP_orientation(m_plane,plane)>0);
441 }
442
443 /**
444  * Comparation between both childrens.
445  * @return 0 equal deep, 1 inChild more deep than outChild and -1 otherwise.
446  */
447 int BOP_BSPNode::compChildren() const
448 {
449         unsigned int deep1 = (m_inChild == NULL?0:m_inChild->getDeep());
450         unsigned int deep2 = (m_outChild == NULL?0:m_outChild->getDeep());
451         
452         if (deep1 == deep2)
453                 return 0;
454         else if (deep1 < deep2)
455                 return -1;
456         else
457                 return 1;
458 }
459
460 /**
461  * Extract a subtriangle from input triangle, is used for simplified classification.
462  * The subtriangle is obtained spliting the input triangle by input plane.
463  * @param res output subtriangle result.
464  * @param plane spliter plane.
465  * @param p1 first triangle point.
466  * @param p2 second triangle point.
467  * @param p3 third triangle point.
468  * @param tag triangle orientation respect the plane.
469  */
470 int BOP_BSPNode::splitTriangle(MT_Point3* res, 
471                                                            const MT_Plane3& plane, 
472                                                            const MT_Point3& p1, 
473                                                            const MT_Point3& p2, 
474                                                            const MT_Point3& p3, 
475                                                            const BOP_TAG tag) const
476 {
477         switch (tag) {
478                 case IN_OUT_ON :
479                   if (compChildren()<0) {
480                     // f1: p1 new p3 || new = splitedge(p1,p2)
481                     res[0] = p1;
482                     res[1] = BOP_intersectPlane( plane, p1, p2 );
483                     res[2] = p3;
484                     return -1;
485                   }else{
486                     // f1: p2 new p3 || new = splitedge(p1,p2)
487                     res[0] = p2;
488                     res[1] = p3;
489                     res[2] = BOP_intersectPlane( plane, p1, p2 );
490                     return 1;
491                   }
492                 case OUT_IN_ON :
493                   if (compChildren()<0) {
494                     // f1: p2 new p3 || new = splitedge(p1,p2)
495                     res[0] = p2;
496                     res[1] = p3;
497                     res[2] = BOP_intersectPlane( plane, p1, p2 );
498                     return -1;
499                   }else{
500                     // f1: p1 new p3 || new = splitedge(p1,p2)
501                     res[0] = p1;
502                     res[1] = BOP_intersectPlane( plane, p1, p2 );
503                     res[2] = p3;
504                     return 1;
505                   }
506                 case IN_ON_OUT :
507                   if (compChildren()<0) {
508                     // f1: p1 p2 new || new = splitedge(p1,p3)
509                     res[0] = p1;
510                     res[1] = p2;
511                     res[2] = BOP_intersectPlane( plane, p1, p3 );
512                     return -1;
513                   }else{
514                     // f1: p2 p3 new || new = splitedge(p1,p3)
515                     res[0] = p2;
516                     res[1] = p3;
517                     res[2] = BOP_intersectPlane( plane, p1, p3 );
518                     return 1;
519                   }
520                 case OUT_ON_IN :
521                   if (compChildren()<0) {
522                     // f1: p2 p3 new || new = splitedge(p1,p3)
523                     res[0] = p2;
524                     res[1] = p3;
525                     res[2] = BOP_intersectPlane( plane, p1, p3 );
526                     return -1;
527                   }else{
528                     // f1: p1 p2 new || new = splitedge(p1,p3)
529                     res[0] = p1;
530                     res[1] = p2;
531                     res[2] = BOP_intersectPlane( plane, p1, p3 );
532                     return 1;
533                   }
534                 case ON_IN_OUT :
535                   if (compChildren()<0) {
536                     // f1: p1 p2 new || new = splitedge(p2,p3)
537                     res[0] = p1;
538                     res[1] = p2;
539                     res[2] = BOP_intersectPlane( plane, p2, p3 );
540                     return -1;
541                   }else{
542                     // f1: p1 p3 new || new = splitedge(p2,p3)
543                     res[0] = p1;
544                     res[1] = BOP_intersectPlane( plane, p2, p3 );
545                     res[2] = p3;
546                     return 1;
547                   }
548                 case ON_OUT_IN :
549                   if (compChildren()<0) {
550                     // f1: p1 p2 new || new = splitedge(p2,p3)
551                     res[0] = p1;
552                     res[1] = BOP_intersectPlane( plane, p2, p3 );
553                     res[2] = p3;
554                     return -1;
555                   }else{
556                     // f1: p1 p2 new || new = splitedge(p2,p3)
557                     res[0] = p1;
558                     res[1] = p2;
559                     res[2] = BOP_intersectPlane( plane, p2, p3 );
560                     return 1;
561                   }
562                 case IN_OUT_OUT :
563                   if (compChildren()<=0) {
564                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
565                     res[0] = p1;
566                     res[1] = BOP_intersectPlane( plane, p1, p2 );
567                     res[2] = BOP_intersectPlane( plane, p1, p3 );
568                     return -1;
569                   }else{
570                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
571                     res[0] = BOP_intersectPlane( plane, p1, p2 );
572                     res[1] = p2;
573                     res[2] = p3;
574                     return 1;
575                   }
576                 case OUT_IN_IN :
577                   if (compChildren()<0) {
578                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
579                     res[0] = BOP_intersectPlane( plane, p1, p2 );
580                     res[1] = p2;
581                     res[2] = p3;
582                     return -1;
583                   }else {
584                     // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
585                     res[0] = p1;
586                     res[1] = BOP_intersectPlane( plane, p1, p2 );
587                     res[2] = BOP_intersectPlane( plane, p1, p3 );
588                     return 1;
589                   }
590                 case OUT_IN_OUT :
591                   if (compChildren()<=0) {
592                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
593                     res[0] = BOP_intersectPlane( plane, p2, p1 );
594                     res[1] = p2;
595                     res[2] = BOP_intersectPlane( plane, p2, p3 );
596                     return -1;
597                   }else {
598                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
599                     res[0] = p1;
600                     res[1] = BOP_intersectPlane( plane, p2, p1 );
601                     res[2] = BOP_intersectPlane( plane, p2, p3 );
602                     return 1;
603                   }
604                 case IN_OUT_IN :
605                   if (compChildren()<0) {
606                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
607                     res[0] = p1;
608                     res[1] = BOP_intersectPlane( plane, p2, p1 );
609                     res[2] = BOP_intersectPlane( plane, p2, p3 );
610                     return -1;
611                   }else{
612                     // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
613                     res[0] = BOP_intersectPlane( plane, p2, p1 );
614                     res[1] = p2;
615                     res[2] = BOP_intersectPlane( plane, p2, p3 );
616                     return 1;
617                   }
618                 case OUT_OUT_IN :
619                   if (compChildren()<=0) {
620                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
621                     res[0] = BOP_intersectPlane( plane, p3, p1 );
622                     res[1] = BOP_intersectPlane( plane, p3, p2 );
623                     res[2] = p3;
624                     return -1;
625                   }else{
626                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
627                     res[0] = BOP_intersectPlane( plane, p3, p1 );
628                     res[1] = p1;
629                     res[2] = p2;
630                     return 1;
631                   }
632                 case IN_IN_OUT :
633                   if (compChildren()<0) {
634                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
635                     res[0] = BOP_intersectPlane( plane, p3, p1 );
636                     res[1] = p1;
637                     res[2] = p2;
638                     return -1;
639                   }else{
640                     // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
641                     res[0] = BOP_intersectPlane( plane, p3, p1 );
642                     res[1] = BOP_intersectPlane( plane, p3, p2 );
643                     res[2] = p3;
644                     return 1;
645                   }
646         default:
647           return 0;
648         }
649 }
650
651 /**
652  * Debug info.
653  */
654 void BOP_BSPNode::print(unsigned int deep)
655 {
656         for (unsigned int i = 0; i < deep; ++i)
657                 cout << "  ";
658         
659         cout << m_plane.x() << ", ";
660         cout << m_plane.y() << ", ";
661         cout << m_plane.z() << ", ";
662         cout << m_plane.w() << endl;
663         if (m_inChild != NULL) {
664                 cout << "IN:";
665                 m_inChild->print(deep + 1);
666         }
667         if (m_outChild != NULL) {
668                 cout << "OUT:";
669                 m_outChild->print(deep + 1);
670         }
671 }