← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty

« back to all changes in this revision

Viewing changes to intern/boolop/intern/BOP_BSPNode.cpp

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

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