include headers in cmake source, added a script to check for consistency, reporting...
[blender.git] / intern / bsp / intern / BSP_MeshPrimitives.h
1 /**
2  * $Id$
3  * ***** BEGIN GPL 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.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): none yet.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 #ifndef NAN_INCLUDED_BSP_MeshPrimitives
30 #define NAN_INCLUDED_BSP_MeshPrimitives
31
32 #include "CTR_TaggedIndex.h"
33 #include "MT_Vector3.h"
34 #include "MT_Plane3.h"
35
36 #include <vector>
37
38 typedef CTR_TaggedIndex<24,0x00ffffff> BSP_VertexInd;
39 typedef CTR_TaggedIndex<24,0x00ffffff> BSP_EdgeInd;
40 typedef CTR_TaggedIndex<24,0x00ffffff> BSP_FaceInd;
41 typedef CTR_TaggedIndex<24,0x00ffffff> BSP_FragInd;
42
43
44 typedef std::vector<BSP_VertexInd> BSP_VertexList;
45 typedef std::vector<BSP_EdgeInd> BSP_EdgeList;
46 typedef std::vector<BSP_FaceInd> BSP_FaceList;
47
48 /** 
49  * Enum representing classification of primitives 
50  * with respect to a hyperplane.
51  */
52
53 enum BSP_Classification{
54         e_unclassified = 0,
55         e_classified_in = 1,
56         e_classified_out = 2,
57         e_classified_on = 4,
58         e_classified_spanning = 7
59 };
60
61 /**
62  * @section Mesh linkage
63  * The mesh is linked in a similar way to the decimation mesh,
64  * although the primitives are a little more general and not
65  * limited to manifold meshes.
66  * Vertices -> (2+)Edges
67  * Edges -> (1+)Polygons
68  * Edges -> (2)Vertices.
69  * Polygons -> (3+)Vertices.
70  *
71  * this structure allows for arbitrary polygons (assumed to be convex).
72  * Edges can point to more than 2 polygons (non-manifold)
73  *
74  * We also define 2 different link types between edges and their
75  * neighbouring polygons. A weak link and a strong link.
76  * A weak link means the polygon is in a different mesh fragment
77  * to the other polygon. A strong link means the polygon is in the
78  * same fragment.
79  * This is not entirely consistent as it means edges have to be associated
80  * with fragments, in reality only polygons will be - edges and vertices
81  * will live in global pools. I guess we should mark edges as being on plane
82  * boundaries. This leaves a problem with non-manifold edges because for example
83  * 3 of 4 possible edges could lie in 1 fragment and the remaining edge lie in
84  * another, there is no way to work out then from one polygon which neighbouring
85  * polygons are in the same/different mesh fragment.
86  *
87  * By definition an edge will only ever lie on 1 hyperplane. We can then just
88  * tag neighbouring polygons with one of 3 tags to group them.
89  */
90
91 class BSP_MVertex {
92 public :
93         MT_Point3 m_pos;
94         BSP_EdgeList m_edges;
95         
96         /**
97          * TODO 
98          * Is this boolean necessary or can we nick a few bits of m_edges[0]
99          * for example?
100          * The only problem with this is that if the vertex is degenerate then
101          * m_edges[0] may not exist. If the algorithm guarentees that this is 
102          * not the case then it should be changed.
103          */
104
105         bool m_select_tag;
106         int m_open_tag;
107
108         BSP_MVertex(
109         );
110
111         BSP_MVertex(
112                 const MT_Point3 & pos
113         );
114
115                 BSP_MVertex &
116         operator = (
117                 const BSP_MVertex & other
118         ) {
119                 m_pos = other.m_pos;
120                 m_edges = other.m_edges;
121                 m_select_tag = other.m_select_tag;
122                 m_open_tag = other.m_open_tag;
123                 return (*this);
124         };
125
126                 bool
127         RemoveEdge(
128                 BSP_EdgeInd e
129         );      
130
131                 void
132         AddEdge(
133                 BSP_EdgeInd e
134         );
135
136                 void
137         SwapEdge(
138                 BSP_EdgeInd e_old,
139                 BSP_EdgeInd e_new
140         );
141
142         /** 
143          * These operations are ONLY valid when the
144          * vertex has some edges associated with it.
145          * This is left to the user to guarentee.
146          * Also note that these tag's are not guarenteed
147          * to survive after a call to RemoveEdge(),
148          * because we use edges for the open tag.
149          */
150
151                 int
152         OpenTag(
153         ) const;
154
155                 void
156         SetOpenTag(
157                 int tag
158         );
159                 
160                 bool
161         SelectTag(
162         ) const;
163
164                 void
165         SetSelectTag(
166                 bool tag        
167         );
168 };
169
170 class BSP_MEdge {
171 public :
172         BSP_VertexInd m_verts[2];
173         BSP_FaceList m_faces;
174
175         BSP_MEdge(
176         );
177
178         bool operator == (
179                 BSP_MEdge & rhs
180         );
181
182                 void
183         SwapFace(
184                 BSP_FaceInd old_f,
185                 BSP_FaceInd new_f
186         );
187
188         BSP_VertexInd
189         OpVertex(
190                 BSP_VertexInd vi
191         ) const;
192
193                 bool
194         SelectTag(
195         ) const;
196
197                 void
198         SetSelectTag(
199                 bool tag        
200         );
201         
202         /**
203          * We use one of the vertex indices for tag informtaion.
204          * This means these tags will not survive if you change 
205          * the vertex indices.
206          */
207
208                 int
209         OpenTag(
210         ) const;
211
212                 void
213         SetOpenTag(
214                 int tag
215         ) ;
216 };
217
218 class BSP_MFace {
219 public :
220
221         BSP_VertexList m_verts;
222
223         // We also store the plane equation of this
224         // face. Generating on the fly during tree
225         // construction can lead to a lot of numerical errors.
226         // because the polygon size can get very small.
227
228         MT_Plane3 m_plane;
229
230         int m_open_tag;
231         unsigned int m_orig_face;
232
233         BSP_MFace(
234         );
235
236         // Invert the face , done by reversing the vertex order 
237         // and inverting the face normal.
238
239                 void
240         Invert(
241         );
242
243         /**
244          * Tagging
245          * We use the tag from m_verts[1] for the select tag
246          * and the the tag from m_verts[0] for the open tag.
247          * There is always a chance that the polygon contains
248          * no vertices but this should be checked at construction
249          * time.
250          * Also note that changing the vertex indices of this polygon
251          * will likely remove tagging information.
252          *
253          */
254
255                 bool
256         SelectTag(
257         ) const;
258
259                 void
260         SetSelectTag(
261                 bool tag        
262         );      
263
264                 int
265         OpenTag(
266         ) const;
267
268                 void
269         SetOpenTag(
270                 int tag
271         ) ;
272
273 };
274
275 #endif
276