doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Surface.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 
33 /*
34 =================
35 UpdateVertexIndex
36 =================
37 */
38 ID_INLINE int UpdateVertexIndex( int vertexIndexNum[2], int *vertexRemap, int *vertexCopyIndex, int vertNum ) {
39  int s = INTSIGNBITSET( vertexRemap[vertNum] );
40  vertexIndexNum[0] = vertexRemap[vertNum];
41  vertexRemap[vertNum] = vertexIndexNum[s];
42  vertexIndexNum[1] += s;
43  vertexCopyIndex[vertexRemap[vertNum]] = vertNum;
44  return vertexRemap[vertNum];
45 }
46 
47 /*
48 =================
49 idSurface::Split
50 =================
51 */
52 int idSurface::Split( const idPlane &plane, const float epsilon, idSurface **front, idSurface **back, int *frontOnPlaneEdges, int *backOnPlaneEdges ) const {
53  float * dists;
54  float f;
55  byte * sides;
56  int counts[3];
57  int * edgeSplitVertex;
58  int numEdgeSplitVertexes;
59  int * vertexRemap[2];
60  int vertexIndexNum[2][2];
61  int * vertexCopyIndex[2];
62  int * indexPtr[2];
63  int indexNum[2];
64  int * index;
65  int * onPlaneEdges[2];
66  int numOnPlaneEdges[2];
67  int maxOnPlaneEdges;
68  int i;
69  idSurface * surface[2];
70  idDrawVert v;
71 
72  dists = (float *) _alloca( verts.Num() * sizeof( float ) );
73  sides = (byte *) _alloca( verts.Num() * sizeof( byte ) );
74 
75  counts[0] = counts[1] = counts[2] = 0;
76 
77  // determine side for each vertex
78  for ( i = 0; i < verts.Num(); i++ ) {
79  dists[i] = f = plane.Distance( verts[i].xyz );
80  if ( f > epsilon ) {
81  sides[i] = SIDE_FRONT;
82  } else if ( f < -epsilon ) {
83  sides[i] = SIDE_BACK;
84  } else {
85  sides[i] = SIDE_ON;
86  }
87  counts[sides[i]]++;
88  }
89 
90  *front = *back = NULL;
91 
92  // if coplanar, put on the front side if the normals match
93  if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
94 
95  f = ( verts[indexes[1]].xyz - verts[indexes[0]].xyz ).Cross( verts[indexes[0]].xyz - verts[indexes[2]].xyz ) * plane.Normal();
96  if ( FLOATSIGNBITSET( f ) ) {
97  *back = new idSurface( *this );
98  return SIDE_BACK;
99  } else {
100  *front = new idSurface( *this );
101  return SIDE_FRONT;
102  }
103  }
104  // if nothing at the front of the clipping plane
105  if ( !counts[SIDE_FRONT] ) {
106  *back = new idSurface( *this );
107  return SIDE_BACK;
108  }
109  // if nothing at the back of the clipping plane
110  if ( !counts[SIDE_BACK] ) {
111  *front = new idSurface( *this );
112  return SIDE_FRONT;
113  }
114 
115  // allocate front and back surface
116  *front = surface[0] = new idSurface();
117  *back = surface[1] = new idSurface();
118 
119  edgeSplitVertex = (int *) _alloca( edges.Num() * sizeof( int ) );
120  numEdgeSplitVertexes = 0;
121 
122  maxOnPlaneEdges = 4 * counts[SIDE_ON];
123  counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
124 
125  // split edges
126  for ( i = 0; i < edges.Num(); i++ ) {
127  int v0 = edges[i].verts[0];
128  int v1 = edges[i].verts[1];
129  int sidesOr = ( sides[v0] | sides[v1] );
130 
131  // if both vertexes are on the same side or one is on the clipping plane
132  if ( !( sides[v0] ^ sides[v1] ) || ( sidesOr & SIDE_ON ) ) {
133  edgeSplitVertex[i] = -1;
134  counts[sidesOr & SIDE_BACK]++;
135  counts[SIDE_ON] += ( sidesOr & SIDE_ON ) >> 1;
136  } else {
137  f = dists[v0] / ( dists[v0] - dists[v1] );
138  v.LerpAll( verts[v0], verts[v1], f );
139  edgeSplitVertex[i] = numEdgeSplitVertexes++;
140  surface[0]->verts.Append( v );
141  surface[1]->verts.Append( v );
142  }
143  }
144 
145  // each edge is shared by at most two triangles, as such there can never be more indexes than twice the number of edges
146  surface[0]->indexes.Resize( ( ( counts[SIDE_FRONT] + counts[SIDE_ON] ) * 2 ) + ( numEdgeSplitVertexes * 4 ) );
147  surface[1]->indexes.Resize( ( ( counts[SIDE_BACK] + counts[SIDE_ON] ) * 2 ) + ( numEdgeSplitVertexes * 4 ) );
148 
149  // allocate indexes to construct the triangle indexes for the front and back surface
150  vertexRemap[0] = (int *) _alloca( verts.Num() * sizeof( int ) );
151  memset( vertexRemap[0], -1, verts.Num() * sizeof( int ) );
152  vertexRemap[1] = (int *) _alloca( verts.Num() * sizeof( int ) );
153  memset( vertexRemap[1], -1, verts.Num() * sizeof( int ) );
154 
155  vertexCopyIndex[0] = (int *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( int ) );
156  vertexCopyIndex[1] = (int *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( int ) );
157 
158  vertexIndexNum[0][0] = vertexIndexNum[1][0] = 0;
159  vertexIndexNum[0][1] = vertexIndexNum[1][1] = numEdgeSplitVertexes;
160 
161  indexPtr[0] = surface[0]->indexes.Ptr();
162  indexPtr[1] = surface[1]->indexes.Ptr();
163  indexNum[0] = surface[0]->indexes.Num();
164  indexNum[1] = surface[1]->indexes.Num();
165 
166  maxOnPlaneEdges += 4 * numEdgeSplitVertexes;
167  // allocate one more in case no triangles are actually split which may happen for a disconnected surface
168  onPlaneEdges[0] = (int *) _alloca( ( maxOnPlaneEdges + 1 ) * sizeof( int ) );
169  onPlaneEdges[1] = (int *) _alloca( ( maxOnPlaneEdges + 1 ) * sizeof( int ) );
170  numOnPlaneEdges[0] = numOnPlaneEdges[1] = 0;
171 
172  // split surface triangles
173  for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
174  int e0, e1, e2, v0, v1, v2, s, n;
175 
176  e0 = abs( edgeIndexes[i+0] );
177  e1 = abs( edgeIndexes[i+1] );
178  e2 = abs( edgeIndexes[i+2] );
179 
180  v0 = indexes[i+0];
181  v1 = indexes[i+1];
182  v2 = indexes[i+2];
183 
184  switch( ( INTSIGNBITSET( edgeSplitVertex[e0] ) | ( INTSIGNBITSET( edgeSplitVertex[e1] ) << 1 ) | ( INTSIGNBITSET( edgeSplitVertex[e2] ) << 2 ) ) ^ 7 ) {
185  case 0: { // no edges split
186  if ( ( sides[v0] & sides[v1] & sides[v2] ) & SIDE_ON ) {
187  // coplanar
188  f = ( verts[v1].xyz - verts[v0].xyz ).Cross( verts[v0].xyz - verts[v2].xyz ) * plane.Normal();
189  s = FLOATSIGNBITSET( f );
190  } else {
191  s = ( sides[v0] | sides[v1] | sides[v2] ) & SIDE_BACK;
192  }
193  n = indexNum[s];
194  onPlaneEdges[s][numOnPlaneEdges[s]] = n;
195  numOnPlaneEdges[s] += ( sides[v0] & sides[v1] ) >> 1;
196  onPlaneEdges[s][numOnPlaneEdges[s]] = n+1;
197  numOnPlaneEdges[s] += ( sides[v1] & sides[v2] ) >> 1;
198  onPlaneEdges[s][numOnPlaneEdges[s]] = n+2;
199  numOnPlaneEdges[s] += ( sides[v2] & sides[v0] ) >> 1;
200  index = indexPtr[s];
201  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
202  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
203  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
204  indexNum[s] = n;
205  break;
206  }
207  case 1: { // first edge split
208  s = sides[v0] & SIDE_BACK;
209  n = indexNum[s];
210  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
211  index = indexPtr[s];
212  index[n++] = edgeSplitVertex[e0];
213  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
214  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
215  indexNum[s] = n;
216  s ^= 1;
217  n = indexNum[s];
218  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
219  index = indexPtr[s];
220  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
221  index[n++] = edgeSplitVertex[e0];
222  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
223  indexNum[s] = n;
224  break;
225  }
226  case 2: { // second edge split
227  s = sides[v1] & SIDE_BACK;
228  n = indexNum[s];
229  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
230  index = indexPtr[s];
231  index[n++] = edgeSplitVertex[e1];
232  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
233  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
234  indexNum[s] = n;
235  s ^= 1;
236  n = indexNum[s];
237  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
238  index = indexPtr[s];
239  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
240  index[n++] = edgeSplitVertex[e1];
241  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
242  indexNum[s] = n;
243  break;
244  }
245  case 3: { // first and second edge split
246  s = sides[v1] & SIDE_BACK;
247  n = indexNum[s];
248  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
249  index = indexPtr[s];
250  index[n++] = edgeSplitVertex[e1];
251  index[n++] = edgeSplitVertex[e0];
252  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
253  indexNum[s] = n;
254  s ^= 1;
255  n = indexNum[s];
256  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
257  index = indexPtr[s];
258  index[n++] = edgeSplitVertex[e0];
259  index[n++] = edgeSplitVertex[e1];
260  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
261  index[n++] = edgeSplitVertex[e1];
262  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
263  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
264  indexNum[s] = n;
265  break;
266  }
267  case 4: { // third edge split
268  s = sides[v2] & SIDE_BACK;
269  n = indexNum[s];
270  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
271  index = indexPtr[s];
272  index[n++] = edgeSplitVertex[e2];
273  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
274  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
275  indexNum[s] = n;
276  s ^= 1;
277  n = indexNum[s];
278  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
279  index = indexPtr[s];
280  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
281  index[n++] = edgeSplitVertex[e2];
282  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
283  indexNum[s] = n;
284  break;
285  }
286  case 5: { // first and third edge split
287  s = sides[v0] & SIDE_BACK;
288  n = indexNum[s];
289  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
290  index = indexPtr[s];
291  index[n++] = edgeSplitVertex[e0];
292  index[n++] = edgeSplitVertex[e2];
293  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
294  indexNum[s] = n;
295  s ^= 1;
296  n = indexNum[s];
297  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
298  index = indexPtr[s];
299  index[n++] = edgeSplitVertex[e2];
300  index[n++] = edgeSplitVertex[e0];
301  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
302  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
303  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
304  index[n++] = edgeSplitVertex[e2];
305  indexNum[s] = n;
306  break;
307  }
308  case 6: { // second and third edge split
309  s = sides[v2] & SIDE_BACK;
310  n = indexNum[s];
311  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
312  index = indexPtr[s];
313  index[n++] = edgeSplitVertex[e2];
314  index[n++] = edgeSplitVertex[e1];
315  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
316  indexNum[s] = n;
317  s ^= 1;
318  n = indexNum[s];
319  onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
320  index = indexPtr[s];
321  index[n++] = edgeSplitVertex[e1];
322  index[n++] = edgeSplitVertex[e2];
323  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
324  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
325  index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
326  index[n++] = edgeSplitVertex[e2];
327  indexNum[s] = n;
328  break;
329  }
330  }
331  }
332 
333  surface[0]->indexes.SetNum( indexNum[0], false );
334  surface[1]->indexes.SetNum( indexNum[1], false );
335 
336  // copy vertexes
337  surface[0]->verts.SetNum( vertexIndexNum[0][1], false );
338  index = vertexCopyIndex[0];
339  for ( i = numEdgeSplitVertexes; i < surface[0]->verts.Num(); i++ ) {
340  surface[0]->verts[i] = verts[index[i]];
341  }
342  surface[1]->verts.SetNum( vertexIndexNum[1][1], false );
343  index = vertexCopyIndex[1];
344  for ( i = numEdgeSplitVertexes; i < surface[1]->verts.Num(); i++ ) {
345  surface[1]->verts[i] = verts[index[i]];
346  }
347 
348  // generate edge indexes
349  surface[0]->GenerateEdgeIndexes();
350  surface[1]->GenerateEdgeIndexes();
351 
352  if ( frontOnPlaneEdges ) {
353  memcpy( frontOnPlaneEdges, onPlaneEdges[0], numOnPlaneEdges[0] * sizeof( int ) );
354  frontOnPlaneEdges[numOnPlaneEdges[0]] = -1;
355  }
356 
357  if ( backOnPlaneEdges ) {
358  memcpy( backOnPlaneEdges, onPlaneEdges[1], numOnPlaneEdges[1] * sizeof( int ) );
359  backOnPlaneEdges[numOnPlaneEdges[1]] = -1;
360  }
361 
362  return SIDE_CROSS;
363 }
364 
365 /*
366 =================
367 idSurface::ClipInPlace
368 =================
369 */
370 bool idSurface::ClipInPlace( const idPlane &plane, const float epsilon, const bool keepOn ) {
371  float * dists;
372  float f;
373  byte * sides;
374  int counts[3];
375  int i;
376  int * edgeSplitVertex;
377  int * vertexRemap;
378  int vertexIndexNum[2];
379  int * vertexCopyIndex;
380  int * indexPtr;
381  int indexNum;
382  int numEdgeSplitVertexes;
383  idDrawVert v;
384  idList<idDrawVert> newVerts;
385  idList<int> newIndexes;
386 
387  dists = (float *) _alloca( verts.Num() * sizeof( float ) );
388  sides = (byte *) _alloca( verts.Num() * sizeof( byte ) );
389 
390  counts[0] = counts[1] = counts[2] = 0;
391 
392  // determine side for each vertex
393  for ( i = 0; i < verts.Num(); i++ ) {
394  dists[i] = f = plane.Distance( verts[i].xyz );
395  if ( f > epsilon ) {
396  sides[i] = SIDE_FRONT;
397  } else if ( f < -epsilon ) {
398  sides[i] = SIDE_BACK;
399  } else {
400  sides[i] = SIDE_ON;
401  }
402  counts[sides[i]]++;
403  }
404 
405  // if coplanar, put on the front side if the normals match
406  if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
407 
408  f = ( verts[indexes[1]].xyz - verts[indexes[0]].xyz ).Cross( verts[indexes[0]].xyz - verts[indexes[2]].xyz ) * plane.Normal();
409  if ( FLOATSIGNBITSET( f ) ) {
410  Clear();
411  return false;
412  } else {
413  return true;
414  }
415  }
416  // if nothing at the front of the clipping plane
417  if ( !counts[SIDE_FRONT] ) {
418  Clear();
419  return false;
420  }
421  // if nothing at the back of the clipping plane
422  if ( !counts[SIDE_BACK] ) {
423  return true;
424  }
425 
426  edgeSplitVertex = (int *) _alloca( edges.Num() * sizeof( int ) );
427  numEdgeSplitVertexes = 0;
428 
429  counts[SIDE_FRONT] = counts[SIDE_BACK] = 0;
430 
431  // split edges
432  for ( i = 0; i < edges.Num(); i++ ) {
433  int v0 = edges[i].verts[0];
434  int v1 = edges[i].verts[1];
435 
436  // if both vertexes are on the same side or one is on the clipping plane
437  if ( !( sides[v0] ^ sides[v1] ) || ( ( sides[v0] | sides[v1] ) & SIDE_ON ) ) {
438  edgeSplitVertex[i] = -1;
439  counts[(sides[v0]|sides[v1]) & SIDE_BACK]++;
440  } else {
441  f = dists[v0] / ( dists[v0] - dists[v1] );
442  v.LerpAll( verts[v0], verts[v1], f );
443  edgeSplitVertex[i] = numEdgeSplitVertexes++;
444  newVerts.Append( v );
445  }
446  }
447 
448  // each edge is shared by at most two triangles, as such there can never be
449  // more indexes than twice the number of edges
450  newIndexes.Resize( ( counts[SIDE_FRONT] << 1 ) + ( numEdgeSplitVertexes << 2 ) );
451 
452  // allocate indexes to construct the triangle indexes for the front and back surface
453  vertexRemap = (int *) _alloca( verts.Num() * sizeof( int ) );
454  memset( vertexRemap, -1, verts.Num() * sizeof( int ) );
455 
456  vertexCopyIndex = (int *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( int ) );
457 
458  vertexIndexNum[0] = 0;
459  vertexIndexNum[1] = numEdgeSplitVertexes;
460 
461  indexPtr = newIndexes.Ptr();
462  indexNum = newIndexes.Num();
463 
464  // split surface triangles
465  for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
466  int e0, e1, e2, v0, v1, v2;
467 
468  e0 = abs( edgeIndexes[i+0] );
469  e1 = abs( edgeIndexes[i+1] );
470  e2 = abs( edgeIndexes[i+2] );
471 
472  v0 = indexes[i+0];
473  v1 = indexes[i+1];
474  v2 = indexes[i+2];
475 
476  switch( ( INTSIGNBITSET( edgeSplitVertex[e0] ) | ( INTSIGNBITSET( edgeSplitVertex[e1] ) << 1 ) | ( INTSIGNBITSET( edgeSplitVertex[e2] ) << 2 ) ) ^ 7 ) {
477  case 0: { // no edges split
478  if ( ( sides[v0] | sides[v1] | sides[v2] ) & SIDE_BACK ) {
479  break;
480  }
481  if ( ( sides[v0] & sides[v1] & sides[v2] ) & SIDE_ON ) {
482  // coplanar
483  if ( !keepOn ) {
484  break;
485  }
486  f = ( verts[v1].xyz - verts[v0].xyz ).Cross( verts[v0].xyz - verts[v2].xyz ) * plane.Normal();
487  if ( FLOATSIGNBITSET( f ) ) {
488  break;
489  }
490  }
491  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
492  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
493  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
494  break;
495  }
496  case 1: { // first edge split
497  if ( !( sides[v0] & SIDE_BACK ) ) {
498  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
499  indexPtr[indexNum++] = edgeSplitVertex[e0];
500  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
501  } else {
502  indexPtr[indexNum++] = edgeSplitVertex[e0];
503  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
504  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
505  }
506  break;
507  }
508  case 2: { // second edge split
509  if ( !( sides[v1] & SIDE_BACK ) ) {
510  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
511  indexPtr[indexNum++] = edgeSplitVertex[e1];
512  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
513  } else {
514  indexPtr[indexNum++] = edgeSplitVertex[e1];
515  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
516  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
517  }
518  break;
519  }
520  case 3: { // first and second edge split
521  if ( !( sides[v1] & SIDE_BACK ) ) {
522  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
523  indexPtr[indexNum++] = edgeSplitVertex[e1];
524  indexPtr[indexNum++] = edgeSplitVertex[e0];
525  } else {
526  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
527  indexPtr[indexNum++] = edgeSplitVertex[e0];
528  indexPtr[indexNum++] = edgeSplitVertex[e1];
529  indexPtr[indexNum++] = edgeSplitVertex[e1];
530  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
531  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
532  }
533  break;
534  }
535  case 4: { // third edge split
536  if ( !( sides[v2] & SIDE_BACK ) ) {
537  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
538  indexPtr[indexNum++] = edgeSplitVertex[e2];
539  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
540  } else {
541  indexPtr[indexNum++] = edgeSplitVertex[e2];
542  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
543  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
544  }
545  break;
546  }
547  case 5: { // first and third edge split
548  if ( !( sides[v0] & SIDE_BACK ) ) {
549  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
550  indexPtr[indexNum++] = edgeSplitVertex[e0];
551  indexPtr[indexNum++] = edgeSplitVertex[e2];
552  } else {
553  indexPtr[indexNum++] = edgeSplitVertex[e0];
554  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
555  indexPtr[indexNum++] = edgeSplitVertex[e2];
556  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
557  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
558  indexPtr[indexNum++] = edgeSplitVertex[e2];
559  }
560  break;
561  }
562  case 6: { // second and third edge split
563  if ( !( sides[v2] & SIDE_BACK ) ) {
564  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
565  indexPtr[indexNum++] = edgeSplitVertex[e2];
566  indexPtr[indexNum++] = edgeSplitVertex[e1];
567  } else {
568  indexPtr[indexNum++] = edgeSplitVertex[e2];
569  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
570  indexPtr[indexNum++] = edgeSplitVertex[e1];
571  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
572  indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
573  indexPtr[indexNum++] = edgeSplitVertex[e2];
574  }
575  break;
576  }
577  }
578  }
579 
580  newIndexes.SetNum( indexNum, false );
581 
582  // copy vertexes
583  newVerts.SetNum( vertexIndexNum[1], false );
584  for ( i = numEdgeSplitVertexes; i < newVerts.Num(); i++ ) {
585  newVerts[i] = verts[vertexCopyIndex[i]];
586  }
587 
588  // copy back to this surface
589  indexes = newIndexes;
590  verts = newVerts;
591 
592  GenerateEdgeIndexes();
593 
594  return true;
595 }
596 
597 /*
598 =============
599 idSurface::IsConnected
600 =============
601 */
602 bool idSurface::IsConnected( void ) const {
603  int i, j, numIslands, numTris;
604  int queueStart, queueEnd;
605  int *queue, *islandNum;
606  int curTri, nextTri, edgeNum;
607  const int *index;
608 
609  numIslands = 0;
610  numTris = indexes.Num() / 3;
611  islandNum = (int *) _alloca16( numTris * sizeof( int ) );
612  memset( islandNum, -1, numTris * sizeof( int ) );
613  queue = (int *) _alloca16( numTris * sizeof( int ) );
614 
615  for ( i = 0; i < numTris; i++ ) {
616 
617  if ( islandNum[i] != -1 ) {
618  continue;
619  }
620 
621  queueStart = 0;
622  queueEnd = 1;
623  queue[0] = i;
624  islandNum[i] = numIslands;
625 
626  for ( curTri = queue[queueStart]; queueStart < queueEnd; curTri = queue[++queueStart] ) {
627 
628  index = &edgeIndexes[curTri * 3];
629 
630  for ( j = 0; j < 3; j++ ) {
631 
632  edgeNum = index[j];
633  nextTri = edges[abs(edgeNum)].tris[INTSIGNBITNOTSET(edgeNum)];
634 
635  if ( nextTri == -1 ) {
636  continue;
637  }
638 
639  nextTri /= 3;
640 
641  if ( islandNum[nextTri] != -1 ) {
642  continue;
643  }
644 
645  queue[queueEnd++] = nextTri;
646  islandNum[nextTri] = numIslands;
647  }
648  }
649  numIslands++;
650  }
651 
652  return ( numIslands == 1 );
653 }
654 
655 /*
656 =================
657 idSurface::IsClosed
658 =================
659 */
660 bool idSurface::IsClosed( void ) const {
661  for ( int i = 0; i < edges.Num(); i++ ) {
662  if ( edges[i].tris[0] < 0 || edges[i].tris[1] < 0 ) {
663  return false;
664  }
665  }
666  return true;
667 }
668 
669 /*
670 =============
671 idSurface::IsPolytope
672 =============
673 */
674 bool idSurface::IsPolytope( const float epsilon ) const {
675  int i, j;
676  idPlane plane;
677 
678  if ( !IsClosed() ) {
679  return false;
680  }
681 
682  for ( i = 0; i < indexes.Num(); i += 3 ) {
683  plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
684 
685  for ( j = 0; j < verts.Num(); j++ ) {
686  if ( plane.Side( verts[j].xyz, epsilon ) == SIDE_FRONT ) {
687  return false;
688  }
689  }
690  }
691  return true;
692 }
693 
694 /*
695 =============
696 idSurface::PlaneDistance
697 =============
698 */
699 float idSurface::PlaneDistance( const idPlane &plane ) const {
700  int i;
701  float d, min, max;
702 
703  min = idMath::INFINITY;
704  max = -min;
705  for ( i = 0; i < verts.Num(); i++ ) {
706  d = plane.Distance( verts[i].xyz );
707  if ( d < min ) {
708  min = d;
709  if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
710  return 0.0f;
711  }
712  }
713  if ( d > max ) {
714  max = d;
715  if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
716  return 0.0f;
717  }
718  }
719  }
720  if ( FLOATSIGNBITNOTSET( min ) ) {
721  return min;
722  }
723  if ( FLOATSIGNBITSET( max ) ) {
724  return max;
725  }
726  return 0.0f;
727 }
728 
729 /*
730 =============
731 idSurface::PlaneSide
732 =============
733 */
734 int idSurface::PlaneSide( const idPlane &plane, const float epsilon ) const {
735  bool front, back;
736  int i;
737  float d;
738 
739  front = false;
740  back = false;
741  for ( i = 0; i < verts.Num(); i++ ) {
742  d = plane.Distance( verts[i].xyz );
743  if ( d < -epsilon ) {
744  if ( front ) {
745  return SIDE_CROSS;
746  }
747  back = true;
748  continue;
749  }
750  else if ( d > epsilon ) {
751  if ( back ) {
752  return SIDE_CROSS;
753  }
754  front = true;
755  continue;
756  }
757  }
758 
759  if ( back ) {
760  return SIDE_BACK;
761  }
762  if ( front ) {
763  return SIDE_FRONT;
764  }
765  return SIDE_ON;
766 }
767 
768 /*
769 =================
770 idSurface::LineIntersection
771 =================
772 */
773 bool idSurface::LineIntersection( const idVec3 &start, const idVec3 &end, bool backFaceCull ) const {
774  float scale;
775 
776  RayIntersection( start, end - start, scale, false );
777  return ( scale >= 0.0f && scale <= 1.0f );
778 }
779 
780 /*
781 =================
782 idSurface::RayIntersection
783 =================
784 */
785 bool idSurface::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull ) const {
786  int i, i0, i1, i2, s0, s1, s2;
787  float d, s;
788  byte *sidedness;
789  idPluecker rayPl, pl;
790  idPlane plane;
791 
792  sidedness = (byte *)_alloca( edges.Num() * sizeof(byte) );
793  scale = idMath::INFINITY;
794 
795  rayPl.FromRay( start, dir );
796 
797  // ray sidedness for edges
798  for ( i = 0; i < edges.Num(); i++ ) {
799  pl.FromLine( verts[ edges[i].verts[1] ].xyz, verts[ edges[i].verts[0] ].xyz );
800  d = pl.PermutedInnerProduct( rayPl );
801  sidedness[ i ] = FLOATSIGNBITSET( d );
802  }
803 
804  // test triangles
805  for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
806  i0 = edgeIndexes[i+0];
807  i1 = edgeIndexes[i+1];
808  i2 = edgeIndexes[i+2];
809  s0 = sidedness[abs(i0)] ^ INTSIGNBITSET( i0 );
810  s1 = sidedness[abs(i1)] ^ INTSIGNBITSET( i1 );
811  s2 = sidedness[abs(i2)] ^ INTSIGNBITSET( i2 );
812 
813  if ( s0 & s1 & s2 ) {
814  plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
815  plane.RayIntersection( start, dir, s );
816  if ( idMath::Fabs( s ) < idMath::Fabs( scale ) ) {
817  scale = s;
818  }
819  } else if ( !backFaceCull && !(s0 | s1 | s2) ) {
820  plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
821  plane.RayIntersection( start, dir, s );
822  if ( idMath::Fabs( s ) < idMath::Fabs( scale ) ) {
823  scale = s;
824  }
825  }
826  }
827 
828  if ( idMath::Fabs( scale ) < idMath::INFINITY ) {
829  return true;
830  }
831  return false;
832 }
833 
834 /*
835 =================
836 idSurface::GenerateEdgeIndexes
837 
838  Assumes each edge is shared by at most two triangles.
839 =================
840 */
841 void idSurface::GenerateEdgeIndexes( void ) {
842  int i, j, i0, i1, i2, s, v0, v1, edgeNum;
843  int *index, *vertexEdges, *edgeChain;
844  surfaceEdge_t e[3];
845 
846  vertexEdges = (int *) _alloca16( verts.Num() * sizeof( int ) );
847  memset( vertexEdges, -1, verts.Num() * sizeof( int ) );
848  edgeChain = (int *) _alloca16( indexes.Num() * sizeof( int ) );
849 
850  edgeIndexes.SetNum( indexes.Num(), true );
851 
852  edges.Clear();
853 
854  // the first edge is a dummy
855  e[0].verts[0] = e[0].verts[1] = e[0].tris[0] = e[0].tris[1] = 0;
856  edges.Append( e[0] );
857 
858  for ( i = 0; i < indexes.Num(); i += 3 ) {
859  index = indexes.Ptr() + i;
860  // vertex numbers
861  i0 = index[0];
862  i1 = index[1];
863  i2 = index[2];
864  // setup edges each with smallest vertex number first
865  s = INTSIGNBITSET(i1 - i0);
866  e[0].verts[0] = index[s];
867  e[0].verts[1] = index[s^1];
868  s = INTSIGNBITSET(i2 - i1) + 1;
869  e[1].verts[0] = index[s];
870  e[1].verts[1] = index[s^3];
871  s = INTSIGNBITSET(i2 - i0) << 1;
872  e[2].verts[0] = index[s];
873  e[2].verts[1] = index[s^2];
874  // get edges
875  for ( j = 0; j < 3; j++ ) {
876  v0 = e[j].verts[0];
877  v1 = e[j].verts[1];
878  for ( edgeNum = vertexEdges[v0]; edgeNum >= 0; edgeNum = edgeChain[edgeNum] ) {
879  if ( edges[edgeNum].verts[1] == v1 ) {
880  break;
881  }
882  }
883  // if the edge does not yet exist
884  if ( edgeNum < 0 ) {
885  e[j].tris[0] = e[j].tris[1] = -1;
886  edgeNum = edges.Append( e[j] );
887  edgeChain[edgeNum] = vertexEdges[v0];
888  vertexEdges[v0] = edgeNum;
889  }
890  // update edge index and edge tri references
891  if ( index[j] == v0 ) {
892  assert( edges[edgeNum].tris[0] == -1 ); // edge may not be shared by more than two triangles
893  edges[edgeNum].tris[0] = i;
894  edgeIndexes[i+j] = edgeNum;
895  } else {
896  assert( edges[edgeNum].tris[1] == -1 ); // edge may not be shared by more than two triangles
897  edges[edgeNum].tris[1] = i;
898  edgeIndexes[i+j] = -edgeNum;
899  }
900  }
901  }
902 }
903 
904 /*
905 =================
906 idSurface::FindEdge
907 =================
908 */
909 int idSurface::FindEdge( int v1, int v2 ) const {
910  int i, firstVert, secondVert;
911 
912  if ( v1 < v2 ) {
913  firstVert = v1;
914  secondVert = v2;
915  } else {
916  firstVert = v2;
917  secondVert = v1;
918  }
919  for ( i = 1; i < edges.Num(); i++ ) {
920  if ( edges[i].verts[0] == firstVert ) {
921  if ( edges[i].verts[1] == secondVert ) {
922  break;
923  }
924  }
925  }
926  if ( i < edges.Num() ) {
927  return v1 < v2 ? i : -i;
928  }
929  return 0;
930 }
idMath::INFINITY
static const float INFINITY
Definition: Math.h:218
min
#define min(a, b)
idSurface::verts
idList< idDrawVert > verts
Definition: Surface.h:96
assert
assert(prefInfo.fullscreenBtn)
idPlane::FromPoints
bool FromPoints(const idVec3 &p1, const idVec3 &p2, const idVec3 &p3, bool fixDegenerate=true)
Definition: Plane.h:279
idPlane::Normal
const idVec3 & Normal(void) const
Definition: Plane.h:239
SIDE_CROSS
#define SIDE_CROSS
Definition: Plane.h:50
v
const GLdouble * v
Definition: glext.h:2936
idList::SetNum
void SetNum(int newnum, bool resize=true)
Definition: List.h:289
SIDE_BACK
#define SIDE_BACK
Definition: Plane.h:48
scale
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:4804
idPlane::Distance
float Distance(const idVec3 &v) const
Definition: Plane.h:324
n
GLenum GLsizei n
Definition: glext.h:3705
int
case const int
Definition: Callbacks.cpp:52
idVec3
Definition: Vector.h:316
float
case const float
Definition: Callbacks.cpp:62
idList::Ptr
type * Ptr(void)
Definition: List.h:596
surfaceEdge_s::verts
int verts[2]
Definition: Surface.h:44
idSurface::IsClosed
bool IsClosed(void) const
Definition: Surface.cpp:660
idSurface::Clear
void Clear(void)
Definition: Surface.h:189
s
GLdouble s
Definition: glext.h:2935
v0
GLfloat v0
Definition: glext.h:3606
process.i
int i
Definition: process.py:33
idPluecker::FromLine
void FromLine(const idVec3 &start, const idVec3 &end)
Definition: Pluecker.h:249
idSurface::ClipInPlace
bool ClipInPlace(const idPlane &plane, const float epsilon=ON_EPSILON, const bool keepOn=false)
Definition: Surface.cpp:370
idSurface::RayIntersection
bool RayIntersection(const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull=false) const
Definition: Surface.cpp:785
v2
GLfloat GLfloat GLfloat v2
Definition: glext.h:3608
idSurface::edgeIndexes
idList< int > edgeIndexes
Definition: Surface.h:99
FLOATSIGNBITSET
#define FLOATSIGNBITSET(f)
Definition: Math.h:68
idSurface::PlaneSide
int PlaneSide(const idPlane &plane, const float epsilon=ON_EPSILON) const
Definition: Surface.cpp:734
idSurface::PlaneDistance
float PlaneDistance(const idPlane &plane) const
Definition: Surface.cpp:699
idSurface::Split
int Split(const idPlane &plane, const float epsilon, idSurface **front, idSurface **back, int *frontOnPlaneEdges=NULL, int *backOnPlaneEdges=NULL) const
Definition: Surface.cpp:52
idSurface::indexes
idList< int > indexes
Definition: Surface.h:97
index
GLuint index
Definition: glext.h:3476
end
GLuint GLuint end
Definition: glext.h:2845
idMath::Fabs
static float Fabs(float f)
Definition: Math.h:779
INTSIGNBITNOTSET
#define INTSIGNBITNOTSET(i)
Definition: Math.h:72
surfaceEdge_s::tris
int tris[2]
Definition: Surface.h:45
idSurface::edges
idList< surfaceEdge_t > edges
Definition: Surface.h:98
NULL
#define NULL
Definition: Lib.h:88
idPlane
Definition: Plane.h:71
idDrawVert::LerpAll
void LerpAll(const idDrawVert &a, const idDrawVert &b, const float f)
Definition: DrawVert.h:87
idSurface::idSurface
idSurface(void)
Definition: Surface.h:111
idPluecker::PermutedInnerProduct
float PermutedInnerProduct(const idPluecker &a) const
Definition: Pluecker.h:316
idSurface::LineIntersection
bool LineIntersection(const idVec3 &start, const idVec3 &end, bool backFaceCull=false) const
Definition: Surface.cpp:773
idPluecker::FromRay
void FromRay(const idVec3 &start, const idVec3 &dir)
Definition: Pluecker.h:258
idPlane::RayIntersection
bool RayIntersection(const idVec3 &start, const idVec3 &dir, float &scale) const
Definition: Plane.h:359
idPlane::Side
int Side(const idVec3 &v, const float epsilon=0.0f) const
Definition: Plane.h:328
v1
GLfloat GLfloat v1
Definition: glext.h:3607
idSurface::IsConnected
bool IsConnected(void) const
Definition: Surface.cpp:602
UpdateVertexIndex
ID_INLINE int UpdateVertexIndex(int vertexIndexNum[2], int *vertexRemap, int *vertexCopyIndex, int vertNum)
Definition: Surface.cpp:38
idList::Append
int Append(const type &obj)
Definition: List.h:646
SIDE_ON
#define SIDE_ON
Definition: Plane.h:49
idSurface::GenerateEdgeIndexes
void GenerateEdgeIndexes(void)
Definition: Surface.cpp:841
INTSIGNBITSET
#define INTSIGNBITSET(i)
Definition: Math.h:71
idal.f
tuple f
Definition: idal.py:89
i2
GLint GLint i2
Definition: qgl.h:261
FLOATSIGNBITNOTSET
#define FLOATSIGNBITNOTSET(f)
Definition: Math.h:69
idList::Num
int Num(void) const
Definition: List.h:265
byte
unsigned char byte
Definition: Lib.h:75
idSurface::IsPolytope
bool IsPolytope(const float epsilon=0.1f) const
Definition: Surface.cpp:674
i1
GLint i1
Definition: qgl.h:261
j
GLint j
Definition: qgl.h:264
max
#define max(x, y)
Definition: os.h:70
SIDE_FRONT
#define SIDE_FRONT
Definition: Plane.h:47
idList::Resize
void Resize(int newsize)
Definition: List.h:360
start
GLuint start
Definition: glext.h:2845
surfaceEdge_s
Definition: Surface.h:43
idSurface::FindEdge
int FindEdge(int v1, int v2) const
Definition: Surface.cpp:909
This page is maintained by Wladimir van der Laan. Generated on Mon Nov 17 2014 12:23:21 for doom3-gpl by doxygen 1.8.6.