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