Initial revision
[blender.git] / intern / bsp / intern / BSP_MeshFragment.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_MeshFragment.h"
33
34 #include "BSP_CSGMesh.h"
35 #include "MT_Plane3.h"
36 #include <math.h>
37
38 using namespace std;
39
40
41 BSP_MeshFragment::
42 BSP_MeshFragment(
43         BSP_CSGMesh *mesh,
44         BSP_Classification classification
45 ):
46         m_mesh(mesh),
47         m_classification(classification)
48 {
49         MT_assert(m_mesh != NULL);
50         //nothing to do
51 }
52
53 const 
54         vector<BSP_FaceInd> &
55 BSP_MeshFragment::
56 FaceSet(
57 ) const {
58         return m_faces;
59 }
60
61         vector<BSP_FaceInd> &
62 BSP_MeshFragment::
63 FaceSet(
64 ) {
65         return m_faces;
66 }
67
68         BSP_CSGMesh *
69 BSP_MeshFragment::
70 Mesh(
71 ){
72         return m_mesh;
73 }
74
75         BSP_CSGMesh *
76 BSP_MeshFragment::
77 Mesh(
78 ) const {
79         return m_mesh;
80 }
81
82         BSP_Classification 
83 BSP_MeshFragment::
84 ClassifyPolygon(
85         const MT_Plane3 &plane,
86         const BSP_MFace & face,
87         std::vector<BSP_MVertex>::const_iterator verts,
88         vector<BSP_VertexInd> & visited_verts
89 ){
90
91         vector<BSP_VertexInd>::const_iterator f_vi_end = face.m_verts.end();
92         vector<BSP_VertexInd>::const_iterator f_vi_it = face.m_verts.begin();
93
94         BSP_Classification p_class = e_unclassified;
95
96         int on_count = 0;
97
98         for (;f_vi_it != f_vi_end; ++f_vi_it) {
99
100                 BSP_MVertex & vert = const_cast<BSP_MVertex &>(verts[int(*f_vi_it)]);   
101
102                 if (BSP_Classification(vert.OpenTag()) == e_unclassified)
103                 {
104                         MT_Scalar sdistance = plane.signedDistance(vert.m_pos);
105                         MT_Scalar fsdistance = fabs(sdistance);
106
107                         if (fabs(sdistance) <= BSP_SPLIT_EPSILON) {
108                                 // this vertex is on
109                                 vert.SetOpenTag(e_classified_on);       
110                         } else 
111                         if (sdistance > MT_Scalar(0)) {
112                                 vert.SetOpenTag(e_classified_out);
113                         } else {
114                                 vert.SetOpenTag(e_classified_in);
115                         }
116                         visited_verts.push_back(*f_vi_it);
117                 }
118                 BSP_Classification v_class = BSP_Classification(vert.OpenTag());
119
120                 if (v_class == e_classified_on) on_count++;
121
122
123                 if (p_class == e_unclassified || p_class == e_classified_on) {
124                         p_class = v_class;
125                 } else 
126                 if (p_class == e_classified_spanning) {
127                 } else 
128                 if (p_class == e_classified_in) {
129                         if (v_class == e_classified_out) {      
130                                 p_class = e_classified_spanning;
131                         }
132                 } else {
133                         if (v_class == e_classified_in) {
134                                 p_class = e_classified_spanning;
135                         }
136                 }
137         }
138
139         if (on_count > 2) p_class = e_classified_on;
140
141         return p_class;
142 }
143
144
145 // Classify this mesh fragment with respect
146 // to plane. The index sets of this fragment
147 // are consumed by this action. Vertices
148 // are tagged with a classification enum.
149
150         void
151 BSP_MeshFragment::
152 Classify(
153         const MT_Plane3 & plane,
154         BSP_MeshFragment * in_frag,
155         BSP_MeshFragment * out_frag,
156         BSP_MeshFragment * on_frag,
157         vector<BSP_FaceInd> & spanning_faces,
158         vector<BSP_VertexInd> & visited_verts
159 ){
160
161         vector<BSP_MVertex> & vertex_set = m_mesh->VertexSet();
162         vector<BSP_MFace> & face_set = m_mesh->FaceSet();
163         
164         // Now iterate through the polygons and classify.
165
166         vector<BSP_FaceInd>::const_iterator fi_end = m_faces.end();
167         vector<BSP_FaceInd>::iterator fi_it = m_faces.begin();
168                         
169         vector<BSP_FaceInd> & face_in_set = in_frag->FaceSet();
170         vector<BSP_FaceInd> & face_out_set = out_frag->FaceSet();
171         vector<BSP_FaceInd> & face_on_set = on_frag->FaceSet();
172         
173         for (;fi_it != fi_end; ++fi_it) {
174                         
175                 BSP_Classification p_class = ClassifyPolygon(
176                         plane,
177                         face_set[*fi_it],
178                         vertex_set.begin(),
179                         visited_verts
180                 );
181                 // p_class now holds the classification for this polygon.
182                 // assign to the appropriate bucket.
183
184                 if (p_class == e_classified_in) {
185                         face_in_set.push_back(*fi_it);
186                 } else 
187                 if (p_class == e_classified_out) {
188                         face_out_set.push_back(*fi_it);
189                 } else
190                 if (p_class == e_classified_on) {
191                         face_on_set.push_back(*fi_it);
192                 } else {
193                         spanning_faces.push_back(*fi_it);
194                         // This is assigned later when we split the polygons in two.
195                 }
196         }
197
198         m_faces.clear();
199
200 }               
201
202         void
203 BSP_MeshFragment::
204 Classify(
205         BSP_CSGMesh & mesh,
206         const MT_Plane3 & plane,
207         BSP_MeshFragment * in_frag,
208         BSP_MeshFragment * out_frag,
209         BSP_MeshFragment * on_frag,
210         vector<BSP_FaceInd> & spanning_faces,
211         vector<BSP_VertexInd> & visited_verts
212 ){
213
214         vector<BSP_MVertex> & vertex_set = mesh.VertexSet();
215         vector<BSP_MFace> & face_set = mesh.FaceSet();
216         
217         // Now iterate through the polygons and classify.
218
219         int fi_end = mesh.FaceSet().size();
220         int fi_it = 0;
221                         
222         vector<BSP_FaceInd> & face_in_set = in_frag->FaceSet();
223         vector<BSP_FaceInd> & face_out_set = out_frag->FaceSet();
224         vector<BSP_FaceInd> & face_on_set = on_frag->FaceSet();
225         
226         for (;fi_it != fi_end; ++fi_it) {
227                         
228                 BSP_Classification p_class = ClassifyPolygon(
229                         plane,
230                         face_set[fi_it],
231                         vertex_set.begin(),
232                         visited_verts
233                 );
234                 // p_class now holds the classification for this polygon.
235                 // assign to the appropriate bucket.
236
237                 if (p_class == e_classified_in) {
238                         face_in_set.push_back(fi_it);
239                 } else 
240                 if (p_class == e_classified_out) {
241                         face_out_set.push_back(fi_it);
242                 } else
243                 if (p_class == e_classified_on) {
244                         face_on_set.push_back(fi_it);
245                 } else {
246                         spanning_faces.push_back(fi_it);
247                 }
248         }
249
250 }
251         void
252 BSP_MeshFragment::
253 ClassifyOnFragments(
254         const MT_Plane3 &plane,
255         BSP_MeshFragment *pos_frag,
256         BSP_MeshFragment *neg_frag
257 ){
258
259         vector<BSP_MFace> & face_set = m_mesh->FaceSet();
260         vector<BSP_FaceInd>::const_iterator fi_end = m_faces.end();
261         vector<BSP_FaceInd>::iterator fi_it = m_faces.begin();
262
263         MT_Scalar d = plane.Scalar();
264
265         for (;fi_it != fi_end; ++fi_it) {
266                 if (fabs(d + face_set[*fi_it].m_plane.Scalar()) > BSP_SPLIT_EPSILON) {
267                         pos_frag->FaceSet().push_back(*fi_it);
268                 } else {
269                         neg_frag->FaceSet().push_back(*fi_it);
270                 }
271         }       
272 }
273
274 BSP_MeshFragment::
275 ~BSP_MeshFragment(
276 ){
277 }
278
279