Initial revision
[blender.git] / intern / bsp / intern / BSP_FragNode.cpp
1 /**
2  * $Id$
3  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30  */
31
32 #include "BSP_CSGMesh.h"
33
34 #include "BSP_FragNode.h"
35 #include "BSP_CSGISplitter.h"
36
37
38 BSP_FragNode::
39 BSP_FragNode(
40         const MT_Plane3 & plane,
41         BSP_CSGMesh *mesh
42 ):
43         m_plane(plane),
44         m_in_tree(mesh),
45         m_out_tree(mesh)
46 {
47 }
48
49 /**
50  * Public methods
51  * Should only be called by BSP_FragTree
52  */
53
54 BSP_FragNode::
55 ~BSP_FragNode(
56 ){
57         // nothing to do
58 }
59
60         MEM_SmartPtr<BSP_FragNode>
61 BSP_FragNode::
62 New(
63         const MT_Plane3 & plane,
64         BSP_CSGMesh *mesh
65 ){
66         return new BSP_FragNode(plane,mesh);
67 }
68
69
70         void
71 BSP_FragNode::
72 Build(
73         BSP_MeshFragment *frag,
74         BSP_CSGISplitter & splitter
75 ){
76         // we know there must be some polygons still in
77         // the fragment otherwise this node would not hve been
78         // constructed.
79
80         BSP_CSGMesh *mesh = frag->Mesh();
81
82         // split the incoming fragment by the plane
83         // generating in,out,on fragments which are
84         // passed down the in and out trees.
85
86         BSP_MeshFragment in_frag(mesh,e_classified_in),out_frag(mesh,e_classified_out);
87         MEM_SmartPtr<BSP_MeshFragment> on_frag = new BSP_MeshFragment(mesh,e_classified_on);
88         splitter.Split(m_plane,frag,&in_frag,&out_frag,on_frag,NULL);
89
90         // We are not interested in the on fragments.
91         on_frag.Delete();
92
93         m_in_tree.Build(&in_frag,splitter);
94         m_out_tree.Build(&out_frag,splitter);
95 }       
96
97         void
98 BSP_FragNode::
99 Push(
100         BSP_MeshFragment *in_frag,
101         BSP_MeshFragment *output,
102         const BSP_Classification keep,
103         const bool dominant,
104         BSP_CSGISplitter & splitter
105 ){              
106         BSP_CSGMesh *mesh = in_frag->Mesh();
107
108
109         MEM_SmartPtr<BSP_MeshFragment> inside_frag = new BSP_MeshFragment(mesh,e_classified_in);
110         MEM_SmartPtr<BSP_MeshFragment> outside_frag = new BSP_MeshFragment(mesh,e_classified_out);
111         MEM_SmartPtr<BSP_MeshFragment> on_frag = new BSP_MeshFragment(mesh,e_classified_on);
112
113         // deal with memory exceptions here.
114
115         splitter.Split(m_plane,in_frag,inside_frag,outside_frag,on_frag,NULL);
116
117         // deal with the on_fragments.
118
119         if (on_frag->FaceSet().size()) {
120         
121                 // The on fragment contains polygons that are outside both subtrees and polygons
122                 // that are inside one or more sub trees. If we are taking the union then we can                                
123                 // immediately add that first set of polygons to the ouput. We must then decide what
124                 // to do with potenially overlapping polygons from both objects. If we assume both 
125                 // objects are closed then we can identify the conflict zones as
126                 // polygons outside B- and inside B+ 
127                 // polygons outside B+ and inside B-
128                 
129                 // In these conflict zones we must choose a dominant object this is indicated
130                 // by the bool parameter to this function. If the object is not dominant then
131                 // we do nothing inside these conflict zones.
132                 // The first set should correspond with on polygons from object B with the same
133                 // orientation as this node. The second corresponding with polygons with opposite
134                 // orientation. 
135                 // We don't want to replace polygons from A with polygons of opposite orientation
136                 // from B. So we split up the on polygons of A into 2 sets according to their orientation.
137                 // We add to output (A- out B-) in B+ and (A+ out B+) in B- 
138         
139         
140 #if 1   
141
142                 if (keep == e_classified_out) {
143                         // we are doing a union operation.
144                         // Make sure that this is not a leaf node.
145                         if(m_in_tree.m_node != NULL || m_out_tree.m_node != NULL) {
146                                 BSP_MeshFragment frag_outBneg_outBpos(mesh,e_classified_on);
147                                 BSP_MeshFragment temp1(on_frag.Ref());
148                                 m_in_tree.Push(
149                                         &temp1,&frag_outBneg_outBpos,
150                                         e_classified_out,e_classified_on,
151                                         false,splitter
152                                 );
153                         
154                                 m_out_tree.Push(
155                                         &frag_outBneg_outBpos,output,e_classified_out,e_classified_on,
156                                         false,splitter
157                                 );
158                         }               
159 #if 1
160                         if (dominant) {
161                         
162                                 // Here we compute the intersection zones.
163                                 BSP_MeshFragment frag_on_pos(mesh,e_classified_on),frag_on_neg(mesh,e_classified_on);
164                                 on_frag->ClassifyOnFragments(m_plane,&frag_on_pos,&frag_on_neg);
165                         
166                                 BSP_MeshFragment temp1(mesh,e_classified_in);
167                                 
168                                 // push -ve fragments down inside tree, push result down outside
169                                 m_in_tree.Push(&frag_on_neg,&temp1,e_classified_out,e_classified_on,false,splitter);
170                                 m_out_tree.Push(&temp1,output,e_classified_in,e_classified_on,false,splitter);
171                                 temp1.FaceSet().clear();
172                 
173                                 // push +ve fragments down outside tree, push result down inside.
174                                 m_out_tree.Push(&frag_on_pos,&temp1,e_classified_out,e_classified_on,false,splitter);
175                                 m_in_tree.Push(&temp1,output,e_classified_in,e_classified_on,false,splitter);
176                         }
177 #endif
178                 } else if (keep == e_classified_in) {
179
180                         // we are doing an intersection
181                         
182                         // A = on_frag in X+ out X-
183                         // B = on_frag in X- out X+
184                         // C = on_frag in X- in X+
185                         
186                         // If X+ is NULL then A = F out X-, B = 0, C = F in X-
187                         // If X- is NULLL then A = 0, B = F out X+ , C = F in X+
188                         // If both NULL then A = C = 0, B = F
189                         
190                         // Conflicts only happen in A and B.
191                         // negative fragments only in A, positive fragments only in B, anything in C.
192                         // First compute F in C an add to ouput.
193                         
194                         BSP_MeshFragment frag_on_pos(mesh,e_classified_on),frag_on_neg(mesh,e_classified_on);
195                         on_frag->ClassifyOnFragments(m_plane,&frag_on_pos,&frag_on_neg);
196                                                 
197                         if (m_in_tree.m_node == NULL) {
198                                 if (m_out_tree.m_node == NULL) {
199                                         // pick stuff that points in the same direction as this node
200                                         // only if priority.
201                                         if (dominant) {
202                                                 // pass +ve frags into B = F.
203                                                 // trick just pass down in tree... just adds to output.
204                                                 m_in_tree.Push(&frag_on_pos,output,e_classified_in,e_classified_on,false,splitter);
205                                         }                                       
206                                 } else {
207                                         // A = 0, B= F out X+ , C = F in X+
208                                         if (dominant) {
209                                         //      m_out_tree.Push(&frag_on_pos,output,e_classified_out,e_classified_on,false,splitter);
210                                                 m_out_tree.Push(on_frag,output,e_classified_in,e_classified_on,false,splitter);
211                                         }
212                                 }
213                         } else {
214                                 if (m_out_tree.m_node == NULL) {
215                                         // A = F out X-, B=0, C = F in X-
216                                         if (dominant) {
217                                         //      m_in_tree.Push(&frag_on_neg,output,e_classified_out,e_classified_on,false,splitter);
218                                                 m_in_tree.Push(on_frag,output,e_classified_in,e_classified_on,false,splitter);
219                                         }
220                                 } else {
221                                         // The normals case
222                                         if (dominant) {
223                                                 BSP_MeshFragment temp1(mesh,e_classified_on);
224                                                 m_out_tree.Push(&frag_on_neg,&temp1,e_classified_in,e_classified_on,false,splitter);
225                                                 m_in_tree.Push(&temp1,output,e_classified_out,e_classified_on,false,splitter);
226                                                 temp1.FaceSet().clear();
227                                                 
228                                                 m_in_tree.Push(&frag_on_pos,&temp1,e_classified_in,e_classified_on,false,splitter);
229                                                 m_out_tree.Push(&temp1,output,e_classified_out,e_classified_on,false,splitter);
230                                         }
231                                         BSP_MeshFragment temp1(mesh,e_classified_on);
232                                         m_in_tree.Push(on_frag,&temp1,e_classified_in,e_classified_on,false,splitter);
233                                         m_out_tree.Push(&temp1,output,e_classified_in,e_classified_on,false,splitter);
234                                 }
235                         }
236                 }               
237                                         
238                                                         
239 #endif
240                 on_frag.Delete();
241         }
242
243         m_in_tree.Push(inside_frag,output,keep,e_classified_in,dominant,splitter);
244         m_out_tree.Push(outside_frag,output,keep,e_classified_out,dominant,splitter);
245 };
246
247         void
248 BSP_FragNode::
249 Classify(
250         BSP_MeshFragment * frag,
251         BSP_MeshFragment *in_frag,
252         BSP_MeshFragment *out_frag,
253         BSP_MeshFragment *on_frag,
254         BSP_CSGISplitter & splitter
255 ){
256
257         BSP_CSGMesh *mesh = frag->Mesh();
258
259         MEM_SmartPtr<BSP_MeshFragment> inside_frag = new BSP_MeshFragment(mesh,e_classified_in);
260         MEM_SmartPtr<BSP_MeshFragment> outside_frag = new BSP_MeshFragment(mesh,e_classified_out);
261         MEM_SmartPtr<BSP_MeshFragment> frag_on = new BSP_MeshFragment(mesh,e_classified_on);
262
263         splitter.Split(m_plane,frag,inside_frag,outside_frag,frag_on,NULL);
264
265         // copy the on fragments into the on_frag output.
266
267         if (frag_on->FaceSet().size()) {
268
269                 on_frag->FaceSet().insert(
270                         on_frag->FaceSet().end(),
271                         frag_on->FaceSet().begin(),
272                         frag_on->FaceSet().end()
273                 );
274         }               
275
276         frag_on.Delete();
277
278         // pass everything else down the tree.
279
280         m_in_tree.Classify(inside_frag,in_frag,out_frag,on_frag,e_classified_in,splitter);
281         m_out_tree.Classify(outside_frag,in_frag,out_frag,on_frag,e_classified_out,splitter);
282 }
283
284
285 /**
286  * Accessor methods
287  */
288
289         BSP_FragTree &
290 BSP_FragNode::
291 InTree(
292 ){
293         return m_in_tree;
294 }
295
296         BSP_FragTree &
297 BSP_FragNode::
298 OutTree(
299 ){
300         return m_out_tree;
301 }
302         
303         MT_Plane3&
304 BSP_FragNode::
305 Plane(
306 ){
307         return m_plane;
308 }
309
310
311
312
313