Initial revision
[blender.git] / intern / bsp / intern / BSP_CSGNCMeshSplitter.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_CSGNCMeshSplitter.h"
33
34 #include "BSP_CSGMesh.h"
35 #include "BSP_MeshFragment.h"
36 #include "BSP_CSGException.h"
37 #include "MT_MinMax.h"
38 #include "MT_assert.h"
39 #include <vector>
40
41 using namespace std;
42
43 BSP_CSGNCMeshSplitter::
44 BSP_CSGNCMeshSplitter(
45 ){
46         //nothing to do
47 }
48
49 BSP_CSGNCMeshSplitter::
50 BSP_CSGNCMeshSplitter(
51         const BSP_CSGNCMeshSplitter & other
52 ){
53         //nothing to do
54 };
55
56
57         void
58 BSP_CSGNCMeshSplitter::
59 Split(
60         const MT_Plane3& plane,
61         BSP_MeshFragment *frag,
62         BSP_MeshFragment *in_frag,
63         BSP_MeshFragment *out_frag,
64         BSP_MeshFragment *on_frag,
65         BSP_MeshFragment *spanning_frag
66 ){
67         // First classify the vertices and the polygons of the
68         // incoming fragment.
69         frag->Classify(plane,in_frag,out_frag,on_frag,m_spanning_faces,m_tagged_verts);
70
71         SplitImp(*(frag->Mesh()),plane,m_spanning_faces,in_frag,out_frag,on_frag,m_tagged_verts);
72
73         m_spanning_faces.clear();
74         m_tagged_verts.clear();
75 }
76
77 /// Split the entire mesh with respect to the plane.
78
79         void
80 BSP_CSGNCMeshSplitter::
81 Split(
82         BSP_CSGMesh & mesh,
83         const MT_Plane3& plane,
84         BSP_MeshFragment *in_frag,
85         BSP_MeshFragment *out_frag,
86         BSP_MeshFragment *on_frag,
87         BSP_MeshFragment *spanning_frag
88 ){
89         BSP_MeshFragment::Classify(mesh, plane,in_frag,out_frag,on_frag,m_spanning_faces,m_tagged_verts);
90
91         SplitImp(mesh,plane,m_spanning_faces,in_frag,out_frag,on_frag,m_tagged_verts);
92         m_spanning_faces.clear();
93         m_tagged_verts.clear();
94 }
95
96
97 BSP_CSGNCMeshSplitter::
98 ~BSP_CSGNCMeshSplitter(
99 ){
100         //nothing to do
101 }
102
103         void
104 BSP_CSGNCMeshSplitter::
105 SplitImp(
106         BSP_CSGMesh & mesh,
107         const MT_Plane3& plane,
108         const std::vector<BSP_FaceInd> & spanning_faces,
109         BSP_MeshFragment *in_frag,
110         BSP_MeshFragment *out_frag,
111         BSP_MeshFragment *on_frag,
112         std::vector<BSP_VertexInd> & classified_verts
113 ){
114
115         // Just iterate through the spanning faces.
116         // Identify the spanning 'edges' and create new vertices 
117         // and split the polygons. We make no attempt to share 
118         // vertices or preserve edge connectivity or maintain any
119         // face properties etc.
120
121         // Assumes you have already classified the vertices.
122         // and generated a set of spanning faces.
123
124         vector<BSP_MVertex> & vertex_set = mesh.VertexSet();
125         vector<BSP_MFace> & face_set = mesh.FaceSet();
126
127         vector<BSP_FaceInd>::const_iterator sface_end = m_spanning_faces.end();
128         vector<BSP_FaceInd>::const_iterator sface_it = m_spanning_faces.begin();
129
130         for (;sface_it != sface_end; ++sface_it) {
131                 BSP_FaceInd f_in,f_out;
132                 SplitPolygon(plane,mesh,*sface_it,f_in,f_out);
133                 
134                 // Use the open tag to store the original index of the face.
135                 // This is originally -1.
136
137                 if (face_set[*sface_it].OpenTag() == -1) {
138                         face_set[f_in].SetOpenTag(*sface_it);
139                         face_set[f_out].SetOpenTag(*sface_it);
140                 } else {
141                         face_set[f_in].SetOpenTag(face_set[*sface_it].OpenTag());
142                         face_set[f_out].SetOpenTag(face_set[*sface_it].OpenTag());
143                 }
144
145                 in_frag->FaceSet().push_back(f_in);
146                 out_frag->FaceSet().push_back(f_out);
147         }
148         
149         vector<BSP_VertexInd>::const_iterator v_end = classified_verts.end();
150         vector<BSP_VertexInd>::const_iterator v_it = classified_verts.begin();
151
152         for (; v_it != v_end; ++v_it) {
153                 vertex_set[*v_it].SetOpenTag(e_unclassified);
154         }
155 }
156
157         void
158 BSP_CSGNCMeshSplitter::
159 SplitPolygon(
160         const MT_Plane3& plane,
161         BSP_CSGMesh & mesh,
162         BSP_FaceInd fi,
163         BSP_FaceInd &fin,
164         BSP_FaceInd &fout
165 ){
166
167         vector<BSP_MVertex> & vertex_set = mesh.VertexSet();
168         vector<BSP_MFace> & face_set = mesh.FaceSet();
169
170         BSP_FaceInd new_fi = face_set.size();
171         face_set.push_back(BSP_MFace());
172
173         BSP_MFace & face = face_set[fi];
174         BSP_MFace &new_face = face_set[new_fi];
175
176         vector<BSP_VertexInd>::const_iterator f_verts_it = face.m_verts.begin();
177         vector<BSP_VertexInd>::const_iterator f_verts_end = face.m_verts.end();
178         
179         MT_Point3 ptA = vertex_set[face.m_verts.back()].m_pos;
180         BSP_Classification prev_class = BSP_Classification(vertex_set[face.m_verts.back()].OpenTag());
181
182         for (; f_verts_it != f_verts_end;++f_verts_it) {
183
184                 BSP_Classification v_class = BSP_Classification(vertex_set[*f_verts_it].OpenTag());
185
186                 if (v_class == e_classified_on) {
187                         m_in_loop.push_back(*f_verts_it);
188                         m_out_loop.push_back(*f_verts_it);
189                         prev_class = e_classified_on;
190                         continue;
191                 } else 
192                 if (v_class == e_classified_in) {
193                         m_in_loop.push_back(*f_verts_it);
194                 } else 
195                 if (v_class == e_classified_out) {
196                         m_out_loop.push_back(*f_verts_it);
197                 }
198
199                 if ((prev_class != e_classified_on) &&
200                         (prev_class != v_class)) {
201                         // spanning edge
202
203                         const MT_Point3 & ptB = vertex_set[*f_verts_it].m_pos;
204
205                         // compute the intersection point of plane and ptA->ptB
206                         MT_Vector3 v = ptB - ptA;
207                         MT_Scalar sideA = plane.signedDistance(ptA);
208
209                         MT_Scalar epsilon = -sideA/plane.Normal().dot(v);
210                         MT_Point3 new_p = ptA + (v * epsilon);
211
212                         BSP_VertexInd new_vi(vertex_set.size());
213                         vertex_set.push_back(BSP_MVertex(new_p));
214
215                         m_in_loop.push_back(new_vi);
216                         m_out_loop.push_back(new_vi);
217                 }
218                 
219                 ptA = vertex_set[*f_verts_it].m_pos;
220                 prev_class = v_class;
221         }
222
223         // Ok should have 2 loops 1 representing the in_loop and
224         // 1 for the out_loop
225         
226         new_face.m_verts = m_out_loop;
227         face.m_verts = m_in_loop;
228
229         new_face.m_plane = face.m_plane;
230
231         // we don't bother maintaining any of the other 
232         // properties.
233         
234         fin = fi;
235         fout = new_fi;
236         
237         m_in_loop.clear();
238         m_out_loop.clear();
239 };
240
241