doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Surface_Polytope.cpp
Go to the documentation of this file.
1 /*
2 ===========================================================================
3 
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6 
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
8 
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13 
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21 
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23 
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25 
26 ===========================================================================
27 */
28 
29 #include "../precompiled.h"
30 #pragma hdrstop
31 
32 #define POLYTOPE_VERTEX_EPSILON 0.1f
33 
34 
35 /*
36 ====================
37 idSurface_Polytope::FromPlanes
38 ====================
39 */
40 void idSurface_Polytope::FromPlanes( const idPlane *planes, const int numPlanes ) {
41  int i, j, k, *windingVerts;
43  idDrawVert newVert;
44 
45  windingVerts = (int *) _alloca( MAX_POINTS_ON_WINDING * sizeof( int ) );
46  memset( &newVert, 0, sizeof( newVert ) );
47 
48  for ( i = 0; i < numPlanes; i++ ) {
49 
50  w.BaseForPlane( planes[i] );
51 
52  for ( j = 0; j < numPlanes; j++ ) {
53  if ( j == i ) {
54  continue;
55  }
56  if ( !w.ClipInPlace( -planes[j], ON_EPSILON, true ) ) {
57  break;
58  }
59  }
60  if ( !w.GetNumPoints() ) {
61  continue;
62  }
63 
64  for ( j = 0; j < w.GetNumPoints(); j++ ) {
65  for ( k = 0; k < verts.Num(); j++ ) {
66  if ( verts[k].xyz.Compare( w[j].ToVec3(), POLYTOPE_VERTEX_EPSILON ) ) {
67  break;
68  }
69  }
70  if ( k >= verts.Num() ) {
71  newVert.xyz = w[j].ToVec3();
72  k = verts.Append( newVert );
73  }
74  windingVerts[j] = k;
75  }
76 
77  for ( j = 2; j < w.GetNumPoints(); j++ ) {
78  indexes.Append( windingVerts[0] );
79  indexes.Append( windingVerts[j-1] );
80  indexes.Append( windingVerts[j] );
81  }
82  }
83 
85 }
86 
87 /*
88 ====================
89 idSurface_Polytope::SetupTetrahedron
90 ====================
91 */
93  idVec3 center, scale;
94  float c1, c2, c3;
95 
96  c1 = 0.4714045207f;
97  c2 = 0.8164965809f;
98  c3 = -0.3333333333f;
99 
100  center = bounds.GetCenter();
101  scale = bounds[1] - center;
102 
103  verts.SetNum( 4 );
104  verts[0].xyz = center + idVec3( 0.0f, 0.0f, scale.z );
105  verts[1].xyz = center + idVec3( 2.0f * c1 * scale.x, 0.0f, c3 * scale.z );
106  verts[2].xyz = center + idVec3( -c1 * scale.x, c2 * scale.y, c3 * scale.z );
107  verts[3].xyz = center + idVec3( -c1 * scale.x, -c2 * scale.y, c3 * scale.z );
108 
109  indexes.SetNum( 4*3 );
110  indexes[0*3+0] = 0;
111  indexes[0*3+1] = 1;
112  indexes[0*3+2] = 2;
113  indexes[1*3+0] = 0;
114  indexes[1*3+1] = 2;
115  indexes[1*3+2] = 3;
116  indexes[2*3+0] = 0;
117  indexes[2*3+1] = 3;
118  indexes[2*3+2] = 1;
119  indexes[3*3+0] = 1;
120  indexes[3*3+1] = 3;
121  indexes[3*3+2] = 2;
122 
124 }
125 
126 /*
127 ====================
128 idSurface_Polytope::SetupHexahedron
129 ====================
130 */
132  idVec3 center, scale;
133 
134  center = bounds.GetCenter();
135  scale = bounds[1] - center;
136 
137  verts.SetNum( 8 );
138  verts[0].xyz = center + idVec3( -scale.x, -scale.y, -scale.z );
139  verts[1].xyz = center + idVec3( scale.x, -scale.y, -scale.z );
140  verts[2].xyz = center + idVec3( scale.x, scale.y, -scale.z );
141  verts[3].xyz = center + idVec3( -scale.x, scale.y, -scale.z );
142  verts[4].xyz = center + idVec3( -scale.x, -scale.y, scale.z );
143  verts[5].xyz = center + idVec3( scale.x, -scale.y, scale.z );
144  verts[6].xyz = center + idVec3( scale.x, scale.y, scale.z );
145  verts[7].xyz = center + idVec3( -scale.x, scale.y, scale.z );
146 
147  indexes.SetNum( 12*3 );
148  indexes[ 0*3+0] = 0;
149  indexes[ 0*3+1] = 3;
150  indexes[ 0*3+2] = 2;
151  indexes[ 1*3+0] = 0;
152  indexes[ 1*3+1] = 2;
153  indexes[ 1*3+2] = 1;
154  indexes[ 2*3+0] = 0;
155  indexes[ 2*3+1] = 1;
156  indexes[ 2*3+2] = 5;
157  indexes[ 3*3+0] = 0;
158  indexes[ 3*3+1] = 5;
159  indexes[ 3*3+2] = 4;
160  indexes[ 4*3+0] = 0;
161  indexes[ 4*3+1] = 4;
162  indexes[ 4*3+2] = 7;
163  indexes[ 5*3+0] = 0;
164  indexes[ 5*3+1] = 7;
165  indexes[ 5*3+2] = 3;
166  indexes[ 6*3+0] = 6;
167  indexes[ 6*3+1] = 5;
168  indexes[ 6*3+2] = 1;
169  indexes[ 7*3+0] = 6;
170  indexes[ 7*3+1] = 1;
171  indexes[ 7*3+2] = 2;
172  indexes[ 8*3+0] = 6;
173  indexes[ 8*3+1] = 2;
174  indexes[ 8*3+2] = 3;
175  indexes[ 9*3+0] = 6;
176  indexes[ 9*3+1] = 3;
177  indexes[ 9*3+2] = 7;
178  indexes[10*3+0] = 6;
179  indexes[10*3+1] = 7;
180  indexes[10*3+2] = 4;
181  indexes[11*3+0] = 6;
182  indexes[11*3+1] = 4;
183  indexes[11*3+2] = 5;
184 
186 }
187 
188 /*
189 ====================
190 idSurface_Polytope::SetupOctahedron
191 ====================
192 */
194  idVec3 center, scale;
195 
196  center = bounds.GetCenter();
197  scale = bounds[1] - center;
198 
199  verts.SetNum( 6 );
200  verts[0].xyz = center + idVec3( scale.x, 0.0f, 0.0f );
201  verts[1].xyz = center + idVec3( -scale.x, 0.0f, 0.0f );
202  verts[2].xyz = center + idVec3( 0.0f, scale.y, 0.0f );
203  verts[3].xyz = center + idVec3( 0.0f, -scale.y, 0.0f );
204  verts[4].xyz = center + idVec3( 0.0f, 0.0f, scale.z );
205  verts[5].xyz = center + idVec3( 0.0f, 0.0f, -scale.z );
206 
207  indexes.SetNum( 8*3 );
208  indexes[0*3+0] = 4;
209  indexes[0*3+1] = 0;
210  indexes[0*3+2] = 2;
211  indexes[1*3+0] = 4;
212  indexes[1*3+1] = 2;
213  indexes[1*3+2] = 1;
214  indexes[2*3+0] = 4;
215  indexes[2*3+1] = 1;
216  indexes[2*3+2] = 3;
217  indexes[3*3+0] = 4;
218  indexes[3*3+1] = 3;
219  indexes[3*3+2] = 0;
220  indexes[4*3+0] = 5;
221  indexes[4*3+1] = 2;
222  indexes[4*3+2] = 0;
223  indexes[5*3+0] = 5;
224  indexes[5*3+1] = 1;
225  indexes[5*3+2] = 2;
226  indexes[6*3+0] = 5;
227  indexes[6*3+1] = 3;
228  indexes[6*3+2] = 1;
229  indexes[7*3+0] = 5;
230  indexes[7*3+1] = 0;
231  indexes[7*3+2] = 3;
232 
234 }
235 
236 /*
237 ====================
238 idSurface_Polytope::SetupDodecahedron
239 ====================
240 */
242 }
243 
244 /*
245 ====================
246 idSurface_Polytope::SetupIcosahedron
247 ====================
248 */
250 }
251 
252 /*
253 ====================
254 idSurface_Polytope::SetupCylinder
255 ====================
256 */
257 void idSurface_Polytope::SetupCylinder( const idBounds &bounds, const int numSides ) {
258 }
259 
260 /*
261 ====================
262 idSurface_Polytope::SetupCone
263 ====================
264 */
265 void idSurface_Polytope::SetupCone( const idBounds &bounds, const int numSides ) {
266 }
267 
268 /*
269 ====================
270 idSurface_Polytope::SplitPolytope
271 ====================
272 */
273 int idSurface_Polytope::SplitPolytope( const idPlane &plane, const float epsilon, idSurface_Polytope **front, idSurface_Polytope **back ) const {
274  int side, i, j, s, v0, v1, v2, edgeNum;
275  idSurface *surface[2];
276  idSurface_Polytope *polytopeSurfaces[2], *surf;
277  int *onPlaneEdges[2];
278 
279  onPlaneEdges[0] = (int *) _alloca( indexes.Num() / 3 * sizeof( int ) );
280  onPlaneEdges[1] = (int *) _alloca( indexes.Num() / 3 * sizeof( int ) );
281 
282  side = Split( plane, epsilon, &surface[0], &surface[1], onPlaneEdges[0], onPlaneEdges[1] );
283 
284  *front = polytopeSurfaces[0] = new idSurface_Polytope;
285  *back = polytopeSurfaces[1] = new idSurface_Polytope;
286 
287  for ( s = 0; s < 2; s++ ) {
288  if ( surface[s] ) {
289  polytopeSurfaces[s] = new idSurface_Polytope;
290  polytopeSurfaces[s]->SwapTriangles( *surface[s] );
291  delete surface[s];
292  surface[s] = NULL;
293  }
294  }
295 
296  *front = polytopeSurfaces[0];
297  *back = polytopeSurfaces[1];
298 
299  if ( side != SIDE_CROSS ) {
300  return side;
301  }
302 
303  // add triangles to close off the front and back polytope
304  for ( s = 0; s < 2; s++ ) {
305 
306  surf = polytopeSurfaces[s];
307 
308  edgeNum = surf->edgeIndexes[onPlaneEdges[s][0]];
309  v0 = surf->edges[abs(edgeNum)].verts[INTSIGNBITSET(edgeNum)];
310  v1 = surf->edges[abs(edgeNum)].verts[INTSIGNBITNOTSET(edgeNum)];
311 
312  for ( i = 1; onPlaneEdges[s][i] >= 0; i++ ) {
313  for ( j = i+1; onPlaneEdges[s][j] >= 0; j++ ) {
314  edgeNum = surf->edgeIndexes[onPlaneEdges[s][j]];
315  if ( v1 == surf->edges[abs(edgeNum)].verts[INTSIGNBITSET(edgeNum)] ) {
316  v1 = surf->edges[abs(edgeNum)].verts[INTSIGNBITNOTSET(edgeNum)];
317  idSwap( onPlaneEdges[s][i], onPlaneEdges[s][j] );
318  break;
319  }
320  }
321  }
322 
323  for ( i = 2; onPlaneEdges[s][i] >= 0; i++ ) {
324  edgeNum = surf->edgeIndexes[onPlaneEdges[s][i]];
325  v1 = surf->edges[abs(edgeNum)].verts[INTSIGNBITNOTSET(edgeNum)];
326  v2 = surf->edges[abs(edgeNum)].verts[INTSIGNBITSET(edgeNum)];
327  surf->indexes.Append( v0 );
328  surf->indexes.Append( v1 );
329  surf->indexes.Append( v2 );
330  }
331 
332  surf->GenerateEdgeIndexes();
333  }
334 
335  return side;
336 }
idList< idDrawVert > verts
Definition: Surface.h:96
#define SIDE_CROSS
Definition: Plane.h:50
idVec3 GetCenter(void) const
Definition: Bounds.h:211
void SetNum(int newnum, bool resize=true)
Definition: List.h:289
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:4804
idVec3 xyz
Definition: DrawVert.h:42
float z
Definition: Vector.h:320
case const int
Definition: Callbacks.cpp:52
void SetupIcosahedron(const idBounds &bounds)
Definition: Vector.h:316
GLdouble s
Definition: glext.h:2935
GLfloat v0
Definition: glext.h:3606
float x
Definition: Vector.h:318
int i
Definition: process.py:33
void SetupDodecahedron(const idBounds &bounds)
GLfloat GLfloat GLfloat v2
Definition: glext.h:3608
idList< int > edgeIndexes
Definition: Surface.h:99
int Split(const idPlane &plane, const float epsilon, idSurface **front, idSurface **back, int *frontOnPlaneEdges=NULL, int *backOnPlaneEdges=NULL) const
Definition: Surface.cpp:52
idList< int > indexes
Definition: Surface.h:97
int GetNumPoints(void) const
Definition: Winding.h:238
#define MAX_POINTS_ON_WINDING
Definition: Winding.h:279
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:3454
void SetupHexahedron(const idBounds &bounds)
#define INTSIGNBITNOTSET(i)
Definition: Math.h:72
idList< surfaceEdge_t > edges
Definition: Surface.h:98
#define NULL
Definition: Lib.h:88
float y
Definition: Vector.h:319
void SetupCylinder(const idBounds &bounds, const int numSides)
Definition: Plane.h:71
#define POLYTOPE_VERTEX_EPSILON
void SetupTetrahedron(const idBounds &bounds)
int SplitPolytope(const idPlane &plane, const float epsilon, idSurface_Polytope **front, idSurface_Polytope **back) const
ID_INLINE void idSwap(type &a, type &b)
Definition: List.h:77
GLfloat GLfloat v1
Definition: glext.h:3607
int Append(const type &obj)
Definition: List.h:646
void GenerateEdgeIndexes(void)
Definition: Surface.cpp:841
#define INTSIGNBITSET(i)
Definition: Math.h:71
void SwapTriangles(idSurface &surf)
Definition: Surface.h:201
tuple f
Definition: idal.py:89
#define ON_EPSILON
Definition: Plane.h:44
int Num(void) const
Definition: List.h:265
void SetupOctahedron(const idBounds &bounds)
void FromPlanes(const idPlane *planes, const int numPlanes)
void SetupCone(const idBounds &bounds, const int numSides)
void BaseForPlane(const idVec3 &normal, const float dist)
Definition: Winding.cpp:66
GLint j
Definition: qgl.h:264
bool ClipInPlace(const idPlane &plane, const float epsilon=ON_EPSILON, const bool keepOn=false)
Definition: Winding.cpp:349