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