doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
optimize.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 "../../../idlib/precompiled.h"
30 #pragma hdrstop
31 
32 //#pragma optimize( "", off )
33 
34 #include "dmap.h"
35 #ifdef WIN32
36 #include <windows.h>
37 #include <GL/gl.h>
38 #endif
39 
40 /*
41 
42  New vertexes will be created where edges cross.
43 
44  optimization requires an accurate t junction fixer.
45 
46 
47 
48 */
49 
50 idBounds optBounds;
51 
52 #define MAX_OPT_VERTEXES 0x10000
53 int numOptVerts;
54 optVertex_t optVerts[MAX_OPT_VERTEXES];
55 
56 #define MAX_OPT_EDGES 0x40000
57 static int numOptEdges;
58 static optEdge_t optEdges[MAX_OPT_EDGES];
59 
60 static bool IsTriangleValid( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 );
61 static bool IsTriangleDegenerate( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 );
62 
63 static idRandom orandom;
64 
65 /*
66 ==============
67 ValidateEdgeCounts
68 ==============
69 */
70 static void ValidateEdgeCounts( optIsland_t *island ) {
71  optVertex_t *vert;
72  optEdge_t *e;
73  int c;
74 
75  for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
76  c = 0;
77  for ( e = vert->edges ; e ; ) {
78  c++;
79  if ( e->v1 == vert ) {
80  e = e->v1link;
81  } else if ( e->v2 == vert ) {
82  e = e->v2link;
83  } else {
84  common->Error( "ValidateEdgeCounts: mislinked" );
85  }
86  }
87  if ( c != 2 && c != 0 ) {
88  // this can still happen at diamond intersections
89 // common->Printf( "ValidateEdgeCounts: %i edges\n", c );
90  }
91  }
92 }
93 
94 
95 /*
96 ====================
97 AllocEdge
98 ====================
99 */
100 static optEdge_t *AllocEdge( void ) {
101  optEdge_t *e;
102 
103  if ( numOptEdges == MAX_OPT_EDGES ) {
104  common->Error( "MAX_OPT_EDGES" );
105  }
106  e = &optEdges[ numOptEdges ];
107  numOptEdges++;
108  memset( e, 0, sizeof( *e ) );
109 
110  return e;
111 }
112 
113 /*
114 ====================
115 RemoveEdgeFromVert
116 ====================
117 */
118 static void RemoveEdgeFromVert( optEdge_t *e1, optVertex_t *vert ) {
119  optEdge_t **prev;
120  optEdge_t *e;
121 
122  if ( !vert ) {
123  return;
124  }
125  prev = &vert->edges;
126  while ( *prev ) {
127  e = *prev;
128  if ( e == e1 ) {
129  if ( e1->v1 == vert ) {
130  *prev = e1->v1link;
131  } else if ( e1->v2 == vert ) {
132  *prev = e1->v2link;
133  } else {
134  common->Error( "RemoveEdgeFromVert: vert not found" );
135  }
136  return;
137  }
138 
139  if ( e->v1 == vert ) {
140  prev = &e->v1link;
141  } else if ( e->v2 == vert ) {
142  prev = &e->v2link;
143  } else {
144  common->Error( "RemoveEdgeFromVert: vert not found" );
145  }
146  }
147 }
148 
149 /*
150 ====================
151 UnlinkEdge
152 ====================
153 */
154 static void UnlinkEdge( optEdge_t *e, optIsland_t *island ) {
155  optEdge_t **prev;
156 
157  RemoveEdgeFromVert( e, e->v1 );
158  RemoveEdgeFromVert( e, e->v2 );
159 
160  for ( prev = &island->edges ; *prev ; prev = &(*prev)->islandLink ) {
161  if ( *prev == e ) {
162  *prev = e->islandLink;
163  return;
164  }
165  }
166 
167  common->Error( "RemoveEdgeFromIsland: couldn't free edge" );
168 }
169 
170 
171 /*
172 ====================
173 LinkEdge
174 ====================
175 */
176 static void LinkEdge( optEdge_t *e ) {
177  e->v1link = e->v1->edges;
178  e->v1->edges = e;
179 
180  e->v2link = e->v2->edges;
181  e->v2->edges = e;
182 }
183 
184 #ifdef __linux__
185 
186 optVertex_t *FindOptVertex( idDrawVert *v, optimizeGroup_t *opt );
187 
188 #else
189 
190 /*
191 ================
192 FindOptVertex
193 ================
194 */
195 static optVertex_t *FindOptVertex( idDrawVert *v, optimizeGroup_t *opt ) {
196  int i;
197  float x, y;
198  optVertex_t *vert;
199 
200  // deal with everything strictly as 2D
201  x = v->xyz * opt->axis[0];
202  y = v->xyz * opt->axis[1];
203 
204  // should we match based on the t-junction fixing hash verts?
205  for ( i = 0 ; i < numOptVerts ; i++ ) {
206  if ( optVerts[i].pv[0] == x && optVerts[i].pv[1] == y ) {
207  return &optVerts[i];
208  }
209  }
210 
211  if ( numOptVerts >= MAX_OPT_VERTEXES ) {
212  common->Error( "MAX_OPT_VERTEXES" );
213  return NULL;
214  }
215 
216  numOptVerts++;
217 
218  vert = &optVerts[i];
219  memset( vert, 0, sizeof( *vert ) );
220  vert->v = *v;
221  vert->pv[0] = x;
222  vert->pv[1] = y;
223  vert->pv[2] = 0;
224 
225  optBounds.AddPoint( vert->pv );
226 
227  return vert;
228 }
229 
230 #endif
231 
232 /*
233 ================
234 DrawAllEdges
235 ================
236 */
237 static void DrawAllEdges( void ) {
238  int i;
239 
240  if ( !dmapGlobals.drawflag ) {
241  return;
242  }
243 
244  Draw_ClearWindow();
245 
246  qglBegin( GL_LINES );
247  for ( i = 0 ; i < numOptEdges ; i++ ) {
248  if ( optEdges[i].v1 == NULL ) {
249  continue;
250  }
251  qglColor3f( 1, 0, 0 );
252  qglVertex3fv( optEdges[i].v1->pv.ToFloatPtr() );
253  qglColor3f( 0, 0, 0 );
254  qglVertex3fv( optEdges[i].v2->pv.ToFloatPtr() );
255  }
256  qglEnd();
257  qglFlush();
258 
259 // GLimp_SwapBuffers();
260 }
261 
262 /*
263 ================
264 DrawVerts
265 ================
266 */
267 static void DrawVerts( optIsland_t *island ) {
268  optVertex_t *vert;
269 
270  if ( !dmapGlobals.drawflag ) {
271  return;
272  }
273 
274  qglEnable( GL_BLEND );
275  qglBlendFunc( GL_ONE, GL_ONE );
276  qglColor3f( 0.3f, 0.3f, 0.3f );
277  qglPointSize( 3 );
278  qglBegin( GL_POINTS );
279  for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
280  qglVertex3fv( vert->pv.ToFloatPtr() );
281  }
282  qglEnd();
283  qglDisable( GL_BLEND );
284  qglFlush();
285 }
286 
287 /*
288 ================
289 DrawEdges
290 ================
291 */
292 static void DrawEdges( optIsland_t *island ) {
293  optEdge_t *edge;
294 
295  if ( !dmapGlobals.drawflag ) {
296  return;
297  }
298 
299  Draw_ClearWindow();
300 
301  qglBegin( GL_LINES );
302  for ( edge = island->edges ; edge ; edge = edge->islandLink ) {
303  if ( edge->v1 == NULL ) {
304  continue;
305  }
306  qglColor3f( 1, 0, 0 );
307  qglVertex3fv( edge->v1->pv.ToFloatPtr() );
308  qglColor3f( 0, 0, 0 );
309  qglVertex3fv( edge->v2->pv.ToFloatPtr() );
310  }
311  qglEnd();
312  qglFlush();
313 
314 // GLimp_SwapBuffers();
315 }
316 
317 //=================================================================
318 
319 /*
320 =================
321 VertexBetween
322 =================
323 */
324 static bool VertexBetween( const optVertex_t *p1, const optVertex_t *v1, const optVertex_t *v2 ) {
325  idVec3 d1, d2;
326  float d;
327 
328  d1 = p1->pv - v1->pv;
329  d2 = p1->pv - v2->pv;
330  d = d1 * d2;
331  if ( d < 0 ) {
332  return true;
333  }
334  return false;
335 }
336 
337 
338 /*
339 ====================
340 EdgeIntersection
341 
342 Creates a new optVertex_t where the line segments cross.
343 This should only be called if PointsStraddleLine returned true
344 
345 Will return NULL if the lines are colinear
346 ====================
347 */
348 static optVertex_t *EdgeIntersection( const optVertex_t *p1, const optVertex_t *p2,
349  const optVertex_t *l1, const optVertex_t *l2, optimizeGroup_t *opt ) {
350  float f;
351  idDrawVert *v;
352  idVec3 dir1, dir2, cross1, cross2;
353 
354  dir1 = p1->pv - l1->pv;
355  dir2 = p1->pv - l2->pv;
356  cross1 = dir1.Cross( dir2 );
357 
358  dir1 = p2->pv - l1->pv;
359  dir2 = p2->pv - l2->pv;
360  cross2 = dir1.Cross( dir2 );
361 
362  if ( cross1[2] - cross2[2] == 0 ) {
363  return NULL;
364  }
365 
366  f = cross1[2] / ( cross1[2] - cross2[2] );
367 
368  // FIXME: how are we freeing this, since it doesn't belong to a tri?
369  v = (idDrawVert *)Mem_Alloc( sizeof( *v ) );
370  memset( v, 0, sizeof( *v ) );
371 
372  v->xyz = p1->v.xyz * ( 1.0 - f ) + p2->v.xyz * f;
373  v->normal = p1->v.normal * ( 1.0 - f ) + p2->v.normal * f;
374  v->normal.Normalize();
375  v->st[0] = p1->v.st[0] * ( 1.0 - f ) + p2->v.st[0] * f;
376  v->st[1] = p1->v.st[1] * ( 1.0 - f ) + p2->v.st[1] * f;
377 
378  return FindOptVertex( v, opt );
379 }
380 
381 
382 /*
383 ====================
384 PointsStraddleLine
385 
386 Colinear is considdered crossing.
387 ====================
388 */
389 static bool PointsStraddleLine( optVertex_t *p1, optVertex_t *p2, optVertex_t *l1, optVertex_t *l2 ) {
390  bool t1, t2;
391 
392  t1 = IsTriangleDegenerate( l1, l2, p1 );
393  t2 = IsTriangleDegenerate( l1, l2, p2 );
394  if ( t1 && t2 ) {
395  // colinear case
396  float s1, s2, s3, s4;
397  bool positive, negative;
398 
399  s1 = ( p1->pv - l1->pv ) * ( l2->pv - l1->pv );
400  s2 = ( p2->pv - l1->pv ) * ( l2->pv - l1->pv );
401  s3 = ( p1->pv - l2->pv ) * ( l2->pv - l1->pv );
402  s4 = ( p2->pv - l2->pv ) * ( l2->pv - l1->pv );
403 
404  if ( s1 > 0 || s2 > 0 || s3 > 0 || s4 > 0 ) {
405  positive = true;
406  } else {
407  positive = false;
408  }
409  if ( s1 < 0 || s2 < 0 || s3 < 0 || s4 < 0 ) {
410  negative = true;
411  } else {
412  negative = false;
413  }
414 
415  if ( positive && negative ) {
416  return true;
417  }
418  return false;
419  } else if ( p1 != l1 && p1 != l2 && p2 != l1 && p2 != l2 ) {
420  // no shared verts
421  t1 = IsTriangleValid( l1, l2, p1 );
422  t2 = IsTriangleValid( l1, l2, p2 );
423  if ( t1 && t2 ) {
424  return false;
425  }
426 
427  t1 = IsTriangleValid( l1, p1, l2 );
428  t2 = IsTriangleValid( l1, p2, l2 );
429  if ( t1 && t2 ) {
430  return false;
431  }
432 
433  return true;
434  } else {
435  // a shared vert, not colinear, so not crossing
436  return false;
437  }
438 }
439 
440 
441 /*
442 ====================
443 EdgesCross
444 ====================
445 */
446 static bool EdgesCross( optVertex_t *a1, optVertex_t *a2, optVertex_t *b1, optVertex_t *b2 ) {
447  // if both verts match, consider it to be crossed
448  if ( a1 == b1 && a2 == b2 ) {
449  return true;
450  }
451  if ( a1 == b2 && a2 == b1 ) {
452  return true;
453  }
454  // if only one vert matches, it might still be colinear, which
455  // would be considered crossing
456 
457  // if both lines' verts are on opposite sides of the other
458  // line, it is crossed
459  if ( !PointsStraddleLine( a1, a2, b1, b2 ) ) {
460  return false;
461  }
462  if ( !PointsStraddleLine( b1, b2, a1, a2 ) ) {
463  return false;
464  }
465 
466  return true;
467 }
468 
469 /*
470 ====================
471 TryAddNewEdge
472 
473 ====================
474 */
475 static bool TryAddNewEdge( optVertex_t *v1, optVertex_t *v2, optIsland_t *island ) {
476  optEdge_t *e;
477 
478  // if the new edge crosses any other edges, don't add it
479  for ( e = island->edges ; e ; e = e->islandLink ) {
480  if ( EdgesCross( e->v1, e->v2, v1, v2 ) ) {
481  return false;
482  }
483  }
484 
485  if ( dmapGlobals.drawflag ) {
486  qglBegin( GL_LINES );
487  qglColor3f( 0, ( 128 + orandom.RandomInt( 127 ) )/ 255.0, 0 );
488  qglVertex3fv( v1->pv.ToFloatPtr() );
489  qglVertex3fv( v2->pv.ToFloatPtr() );
490  qglEnd();
491  qglFlush();
492  }
493  // add it
494  e = AllocEdge();
495 
496  e->islandLink = island->edges;
497  island->edges = e;
498  e->v1 = v1;
499  e->v2 = v2;
500 
501  e->created = true;
502 
503  // link the edge to its verts
504  LinkEdge( e );
505 
506  return true;
507 }
508 
509 typedef struct {
510  optVertex_t *v1, *v2;
511  float length;
512 } edgeLength_t;
513 
514 
515 static int LengthSort( const void *a, const void *b ) {
516  const edgeLength_t *ea, *eb;
517 
518  ea = (const edgeLength_t *)a;
519  eb = (const edgeLength_t *)b;
520  if ( ea->length < eb->length ) {
521  return -1;
522  }
523  if ( ea->length > eb->length ) {
524  return 1;
525  }
526  return 0;
527 }
528 
529 /*
530 ==================
531 AddInteriorEdges
532 
533 Add all possible edges between the verts
534 ==================
535 */
536 static void AddInteriorEdges( optIsland_t *island ) {
537  int c_addedEdges;
538  optVertex_t *vert, *vert2;
539  int c_verts;
540  edgeLength_t *lengths;
541  int numLengths;
542  int i;
543 
544  DrawVerts( island );
545 
546  // count the verts
547  c_verts = 0;
548  for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
549  if ( !vert->edges ) {
550  continue;
551  }
552  c_verts++;
553  }
554 
555  // allocate space for all the lengths
556  lengths = (edgeLength_t *)Mem_Alloc( sizeof( *lengths ) * c_verts * c_verts / 2 );
557  numLengths = 0;
558  for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
559  if ( !vert->edges ) {
560  continue;
561  }
562  for ( vert2 = vert->islandLink ; vert2 ; vert2 = vert2->islandLink ) {
563  idVec3 dir;
564 
565  if ( !vert2->edges ) {
566  continue;
567  }
568  lengths[numLengths].v1 = vert;
569  lengths[numLengths].v2 = vert2;
570  dir = ( vert->pv - vert2->pv ) ;
571  lengths[numLengths].length = dir.Length();
572  numLengths++;
573  }
574  }
575 
576 
577  // sort by length, shortest first
578  qsort( lengths, numLengths, sizeof( lengths[0] ), LengthSort );
579 
580  // try to create them in that order
581  c_addedEdges = 0;
582  for ( i = 0 ; i < numLengths ; i++ ) {
583  if ( TryAddNewEdge( lengths[i].v1, lengths[i].v2, island ) ) {
584  c_addedEdges++;
585  }
586  }
587 
588  if ( dmapGlobals.verbose ) {
589  common->Printf( "%6i tested segments\n", numLengths );
590  common->Printf( "%6i added interior edges\n", c_addedEdges );
591  }
592 
593  Mem_Free( lengths );
594 }
595 
596 
597 
598 //==================================================================
599 
600 /*
601 ====================
602 RemoveIfColinear
603 
604 ====================
605 */
606 #define COLINEAR_EPSILON 0.1
607 static void RemoveIfColinear( optVertex_t *ov, optIsland_t *island ) {
608  optEdge_t *e, *e1, *e2;
609  optVertex_t *v1, *v2, *v3;
610  idVec3 dir1, dir2;
611  float len, dist;
612  idVec3 point;
613  idVec3 offset;
614  float off;
615 
616  v2 = ov;
617 
618  // we must find exactly two edges before testing for colinear
619  e1 = NULL;
620  e2 = NULL;
621  for ( e = ov->edges ; e ; ) {
622  if ( !e1 ) {
623  e1 = e;
624  } else if ( !e2 ) {
625  e2 = e;
626  } else {
627  return; // can't remove a vertex with three edges
628  }
629  if ( e->v1 == v2 ) {
630  e = e->v1link;
631  } else if ( e->v2 == v2 ) {
632  e = e->v2link;
633  } else {
634  common->Error( "RemoveIfColinear: mislinked edge" );
635  }
636  }
637 
638  // can't remove if no edges
639  if ( !e1 ) {
640  return;
641  }
642 
643  if ( !e2 ) {
644  // this may still happen legally when a tiny triangle is
645  // the only thing in a group
646  common->Printf( "WARNING: vertex with only one edge\n" );
647  return;
648  }
649 
650  if ( e1->v1 == v2 ) {
651  v1 = e1->v2;
652  } else if ( e1->v2 == v2 ) {
653  v1 = e1->v1;
654  } else {
655  common->Error( "RemoveIfColinear: mislinked edge" );
656  }
657  if ( e2->v1 == v2 ) {
658  v3 = e2->v2;
659  } else if ( e2->v2 == v2 ) {
660  v3 = e2->v1;
661  } else {
662  common->Error( "RemoveIfColinear: mislinked edge" );
663  }
664 
665  if ( v1 == v3 ) {
666  common->Error( "RemoveIfColinear: mislinked edge" );
667  }
668 
669  // they must point in opposite directions
670  dist = ( v3->pv - v2->pv ) * ( v1->pv - v2->pv );
671  if ( dist >= 0 ) {
672  return;
673  }
674 
675  // see if they are colinear
676  VectorSubtract( v3->v.xyz, v1->v.xyz, dir1 );
677  len = dir1.Normalize();
678  VectorSubtract( v2->v.xyz, v1->v.xyz, dir2 );
679  dist = DotProduct( dir2, dir1 );
680  VectorMA( v1->v.xyz, dist, dir1, point );
681  VectorSubtract( point, v2->v.xyz, offset );
682  off = offset.Length();
683 
684  if ( off > COLINEAR_EPSILON ) {
685  return;
686  }
687 
688  if ( dmapGlobals.drawflag ) {
689  qglBegin( GL_LINES );
690  qglColor3f( 1, 1, 0 );
691  qglVertex3fv( v1->pv.ToFloatPtr() );
692  qglVertex3fv( v2->pv.ToFloatPtr() );
693  qglEnd();
694  qglFlush();
695  qglBegin( GL_LINES );
696  qglColor3f( 0, 1, 1 );
697  qglVertex3fv( v2->pv.ToFloatPtr() );
698  qglVertex3fv( v3->pv.ToFloatPtr() );
699  qglEnd();
700  qglFlush();
701  }
702 
703  // replace the two edges with a single edge
704  UnlinkEdge( e1, island );
705  UnlinkEdge( e2, island );
706 
707  // v2 should have no edges now
708  if ( v2->edges ) {
709  common->Error( "RemoveIfColinear: didn't remove properly" );
710  }
711 
712 
713  // if there is an existing edge that already
714  // has these exact verts, we have just collapsed a
715  // sliver triangle out of existance, and all the edges
716  // can be removed
717  for ( e = island->edges ; e ; e = e->islandLink ) {
718  if ( ( e->v1 == v1 && e->v2 == v3 )
719  || ( e->v1 == v3 && e->v2 == v1 ) ) {
720  UnlinkEdge( e, island );
721  RemoveIfColinear( v1, island );
722  RemoveIfColinear( v3, island );
723  return;
724  }
725  }
726 
727  // if we can't add the combined edge, link
728  // the originals back in
729  if ( !TryAddNewEdge( v1, v3, island ) ) {
730  e1->islandLink = island->edges;
731  island->edges = e1;
732  LinkEdge( e1 );
733 
734  e2->islandLink = island->edges;
735  island->edges = e2;
736  LinkEdge( e2 );
737  return;
738  }
739 
740  // recursively try to combine both verts now,
741  // because things may have changed since the last combine test
742  RemoveIfColinear( v1, island );
743  RemoveIfColinear( v3, island );
744 }
745 
746 /*
747 ====================
748 CombineColinearEdges
749 ====================
750 */
751 static void CombineColinearEdges( optIsland_t *island ) {
752  int c_edges;
753  optVertex_t *ov;
754  optEdge_t *e;
755 
756  c_edges = 0;
757  for ( e = island->edges ; e ; e = e->islandLink ) {
758  c_edges++;
759  }
760  if ( dmapGlobals.verbose ) {
761  common->Printf( "%6i original exterior edges\n", c_edges );
762  }
763 
764  for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
765  RemoveIfColinear( ov, island );
766  }
767 
768  c_edges = 0;
769  for ( e = island->edges ; e ; e = e->islandLink ) {
770  c_edges++;
771  }
772  if ( dmapGlobals.verbose ) {
773  common->Printf( "%6i optimized exterior edges\n", c_edges );
774  }
775 }
776 
777 
778 //==================================================================
779 
780 /*
781 ===================
782 FreeOptTriangles
783 
784 ===================
785 */
786 static void FreeOptTriangles( optIsland_t *island ) {
787  optTri_t *opt, *next;
788 
789  for ( opt = island->tris ; opt ; opt = next ) {
790  next = opt->next;
791  Mem_Free( opt );
792  }
793 
794  island->tris = NULL;
795 }
796 
797 
798 /*
799 =================
800 IsTriangleValid
801 
802 empty area will be considered invalid.
803 Due to some truly aweful epsilon issues, a triangle can switch between
804 valid and invalid depending on which order you look at the verts, so
805 consider it invalid if any one of the possibilities is invalid.
806 =================
807 */
808 static bool IsTriangleValid( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 ) {
809  idVec3 d1, d2, normal;
810 
811  d1 = v2->pv - v1->pv;
812  d2 = v3->pv - v1->pv;
813  normal = d1.Cross( d2 );
814  if ( normal[2] <= 0 ) {
815  return false;
816  }
817 
818  d1 = v3->pv - v2->pv;
819  d2 = v1->pv - v2->pv;
820  normal = d1.Cross( d2 );
821  if ( normal[2] <= 0 ) {
822  return false;
823  }
824 
825  d1 = v1->pv - v3->pv;
826  d2 = v2->pv - v3->pv;
827  normal = d1.Cross( d2 );
828  if ( normal[2] <= 0 ) {
829  return false;
830  }
831 
832  return true;
833 }
834 
835 
836 /*
837 =================
838 IsTriangleDegenerate
839 
840 Returns false if it is either front or back facing
841 =================
842 */
843 static bool IsTriangleDegenerate( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 ) {
844 #if 1
845  idVec3 d1, d2, normal;
846 
847  d1 = v2->pv - v1->pv;
848  d2 = v3->pv - v1->pv;
849  normal = d1.Cross( d2 );
850  if ( normal[2] == 0 ) {
851  return true;
852  }
853  return false;
854 #else
855  return (bool)!IsTriangleValid( v1, v2, v3 );
856 #endif
857 }
858 
859 
860 /*
861 ==================
862 PointInTri
863 
864 Tests if a 2D point is inside an original triangle
865 ==================
866 */
867 static bool PointInTri( const idVec3 &p, const mapTri_t *tri, optIsland_t *island ) {
868  idVec3 d1, d2, normal;
869 
870  // the normal[2] == 0 case is not uncommon when a square is triangulated in
871  // the opposite manner to the original
872 
873  d1 = tri->optVert[0]->pv - p;
874  d2 = tri->optVert[1]->pv - p;
875  normal = d1.Cross( d2 );
876  if ( normal[2] < 0 ) {
877  return false;
878  }
879 
880  d1 = tri->optVert[1]->pv - p;
881  d2 = tri->optVert[2]->pv - p;
882  normal = d1.Cross( d2 );
883  if ( normal[2] < 0 ) {
884  return false;
885  }
886 
887  d1 = tri->optVert[2]->pv - p;
888  d2 = tri->optVert[0]->pv - p;
889  normal = d1.Cross( d2 );
890  if ( normal[2] < 0 ) {
891  return false;
892  }
893 
894  return true;
895 }
896 
897 
898 /*
899 ====================
900 LinkTriToEdge
901 
902 ====================
903 */
904 static void LinkTriToEdge( optTri_t *optTri, optEdge_t *edge ) {
905  if ( ( edge->v1 == optTri->v[0] && edge->v2 == optTri->v[1] )
906  || ( edge->v1 == optTri->v[1] && edge->v2 == optTri->v[2] )
907  || ( edge->v1 == optTri->v[2] && edge->v2 == optTri->v[0] ) ) {
908  if ( edge->backTri ) {
909  common->Printf( "Warning: LinkTriToEdge: already in use\n" );
910  return;
911  }
912  edge->backTri = optTri;
913  return;
914  }
915  if ( ( edge->v1 == optTri->v[1] && edge->v2 == optTri->v[0] )
916  || ( edge->v1 == optTri->v[2] && edge->v2 == optTri->v[1] )
917  || ( edge->v1 == optTri->v[0] && edge->v2 == optTri->v[2] ) ) {
918  if ( edge->frontTri ) {
919  common->Printf( "Warning: LinkTriToEdge: already in use\n" );
920  return;
921  }
922  edge->frontTri = optTri;
923  return;
924  }
925  common->Error( "LinkTriToEdge: edge not found on tri" );
926 }
927 
928 /*
929 ===============
930 CreateOptTri
931 ===============
932 */
933 static void CreateOptTri( optVertex_t *first, optEdge_t *e1, optEdge_t *e2, optIsland_t *island ) {
934  optEdge_t *opposite;
935  optVertex_t *second, *third;
936  optTri_t *optTri;
937  mapTri_t *tri;
938 
939  if ( e1->v1 == first ) {
940  second = e1->v2;
941  } else if ( e1->v2 == first ) {
942  second = e1->v1;
943  } else {
944  common->Error( "CreateOptTri: mislinked edge" );
945  }
946 
947  if ( e2->v1 == first ) {
948  third = e2->v2;
949  } else if ( e2->v2 == first ) {
950  third = e2->v1;
951  } else {
952  common->Error( "CreateOptTri: mislinked edge" );
953  }
954 
955  if ( !IsTriangleValid( first, second, third ) ) {
956  common->Error( "CreateOptTri: invalid" );
957  }
958 
959 //DrawEdges( island );
960 
961  // identify the third edge
962  if ( dmapGlobals.drawflag ) {
963  qglColor3f(1,1,0);
964  qglBegin( GL_LINES );
965  qglVertex3fv( e1->v1->pv.ToFloatPtr() );
966  qglVertex3fv( e1->v2->pv.ToFloatPtr() );
967  qglEnd();
968  qglFlush();
969  qglColor3f(0,1,1);
970  qglBegin( GL_LINES );
971  qglVertex3fv( e2->v1->pv.ToFloatPtr() );
972  qglVertex3fv( e2->v2->pv.ToFloatPtr() );
973  qglEnd();
974  qglFlush();
975  }
976 
977  for ( opposite = second->edges ; opposite ; ) {
978  if ( opposite != e1 && ( opposite->v1 == third || opposite->v2 == third ) ) {
979  break;
980  }
981  if ( opposite->v1 == second ) {
982  opposite = opposite->v1link;
983  } else if ( opposite->v2 == second ) {
984  opposite = opposite->v2link;
985  } else {
986  common->Error( "BuildOptTriangles: mislinked edge" );
987  }
988  }
989 
990  if ( !opposite ) {
991  common->Printf( "Warning: BuildOptTriangles: couldn't locate opposite\n" );
992  return;
993  }
994 
995  if ( dmapGlobals.drawflag ) {
996  qglColor3f(1,0,1);
997  qglBegin( GL_LINES );
998  qglVertex3fv( opposite->v1->pv.ToFloatPtr() );
999  qglVertex3fv( opposite->v2->pv.ToFloatPtr() );
1000  qglEnd();
1001  qglFlush();
1002  }
1003 
1004  // create new triangle
1005  optTri = (optTri_t *)Mem_Alloc( sizeof( *optTri ) );
1006  optTri->v[0] = first;
1007  optTri->v[1] = second;
1008  optTri->v[2] = third;
1009  optTri->midpoint = ( optTri->v[0]->pv + optTri->v[1]->pv + optTri->v[2]->pv ) * ( 1.0f / 3.0f );
1010  optTri->next = island->tris;
1011  island->tris = optTri;
1012 
1013  if ( dmapGlobals.drawflag ) {
1014  qglColor3f( 1, 1, 1 );
1015  qglPointSize( 4 );
1016  qglBegin( GL_POINTS );
1017  qglVertex3fv( optTri->midpoint.ToFloatPtr() );
1018  qglEnd();
1019  qglFlush();
1020  }
1021 
1022  // find the midpoint, and scan through all the original triangles to
1023  // see if it is inside any of them
1024  for ( tri = island->group->triList ; tri ; tri = tri->next ) {
1025  if ( PointInTri( optTri->midpoint, tri, island ) ) {
1026  break;
1027  }
1028  }
1029  if ( tri ) {
1030  optTri->filled = true;
1031  } else {
1032  optTri->filled = false;
1033  }
1034  if ( dmapGlobals.drawflag ) {
1035  if ( optTri->filled ) {
1036  qglColor3f( ( 128 + orandom.RandomInt( 127 ) )/ 255.0, 0, 0 );
1037  } else {
1038  qglColor3f( 0, ( 128 + orandom.RandomInt( 127 ) ) / 255.0, 0 );
1039  }
1040  qglBegin( GL_TRIANGLES );
1041  qglVertex3fv( optTri->v[0]->pv.ToFloatPtr() );
1042  qglVertex3fv( optTri->v[1]->pv.ToFloatPtr() );
1043  qglVertex3fv( optTri->v[2]->pv.ToFloatPtr() );
1044  qglEnd();
1045  qglColor3f( 1, 1, 1 );
1046  qglBegin( GL_LINE_LOOP );
1047  qglVertex3fv( optTri->v[0]->pv.ToFloatPtr() );
1048  qglVertex3fv( optTri->v[1]->pv.ToFloatPtr() );
1049  qglVertex3fv( optTri->v[2]->pv.ToFloatPtr() );
1050  qglEnd();
1051  qglFlush();
1052  }
1053 
1054  // link the triangle to it's edges
1055  LinkTriToEdge( optTri, e1 );
1056  LinkTriToEdge( optTri, e2 );
1057  LinkTriToEdge( optTri, opposite );
1058 }
1059 
1060 // debugging tool
1061 static void ReportNearbyVertexes( const optVertex_t *v, const optIsland_t *island ) {
1062  const optVertex_t *ov;
1063  float d;
1064  idVec3 vec;
1065 
1066  common->Printf( "verts near 0x%p (%f, %f)\n", v, v->pv[0], v->pv[1] );
1067  for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
1068  if ( ov == v ) {
1069  continue;
1070  }
1071 
1072  vec = ov->pv - v->pv;
1073 
1074  d = vec.Length();
1075  if ( d < 1 ) {
1076  common->Printf( "0x%p = (%f, %f)\n", ov, ov->pv[0], ov->pv[1] );
1077  }
1078  }
1079 }
1080 
1081 /*
1082 ====================
1083 BuildOptTriangles
1084 
1085 Generate a new list of triangles from the optEdeges
1086 ====================
1087 */
1088 static void BuildOptTriangles( optIsland_t *island ) {
1089  optVertex_t *ov, *second, *third, *middle;
1090  optEdge_t *e1, *e1Next, *e2, *e2Next, *check, *checkNext;
1091 
1092  // free them
1093  FreeOptTriangles( island );
1094 
1095  // clear the vertex emitted flags
1096  for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
1097  ov->emited = false;
1098  }
1099 
1100  // clear the edge triangle links
1101  for ( check = island->edges ; check ; check = check->islandLink ) {
1102  check->frontTri = check->backTri = NULL;
1103  }
1104 
1105  // check all possible triangle made up out of the
1106  // edges coming off the vertex
1107  for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
1108  if ( !ov->edges ) {
1109  continue;
1110  }
1111 
1112 #if 0
1113 if ( dmapGlobals.drawflag && ov == (optVertex_t *)0x1845a60 ) {
1114 for ( e1 = ov->edges ; e1 ; e1 = e1Next ) {
1115  qglBegin( GL_LINES );
1116  qglColor3f( 0,1,0 );
1117  qglVertex3fv( e1->v1->pv.ToFloatPtr() );
1118  qglVertex3fv( e1->v2->pv.ToFloatPtr() );
1119  qglEnd();
1120  qglFlush();
1121  if ( e1->v1 == ov ) {
1122  e1Next = e1->v1link;
1123  } else if ( e1->v2 == ov ) {
1124  e1Next = e1->v2link;
1125  }
1126 }
1127 }
1128 #endif
1129  for ( e1 = ov->edges ; e1 ; e1 = e1Next ) {
1130  if ( e1->v1 == ov ) {
1131  second = e1->v2;
1132  e1Next = e1->v1link;
1133  } else if ( e1->v2 == ov ) {
1134  second = e1->v1;
1135  e1Next = e1->v2link;
1136  } else {
1137  common->Error( "BuildOptTriangles: mislinked edge" );
1138  }
1139 
1140  // if the vertex has already been used, it can't be used again
1141  if ( second->emited ) {
1142  continue;
1143  }
1144 
1145  for ( e2 = ov->edges ; e2 ; e2 = e2Next ) {
1146  if ( e2->v1 == ov ) {
1147  third = e2->v2;
1148  e2Next = e2->v1link;
1149  } else if ( e2->v2 == ov ) {
1150  third = e2->v1;
1151  e2Next = e2->v2link;
1152  } else {
1153  common->Error( "BuildOptTriangles: mislinked edge" );
1154  }
1155  if ( e2 == e1 ) {
1156  continue;
1157  }
1158 
1159  // if the vertex has already been used, it can't be used again
1160  if ( third->emited ) {
1161  continue;
1162  }
1163 
1164  // if the triangle is backwards or degenerate, don't use it
1165  if ( !IsTriangleValid( ov, second, third ) ) {
1166  continue;
1167  }
1168 
1169  // see if any other edge bisects these two, which means
1170  // this triangle shouldn't be used
1171  for ( check = ov->edges ; check ; check = checkNext ) {
1172  if ( check->v1 == ov ) {
1173  middle = check->v2;
1174  checkNext = check->v1link;
1175  } else if ( check->v2 == ov ) {
1176  middle = check->v1;
1177  checkNext = check->v2link;
1178  } else {
1179  common->Error( "BuildOptTriangles: mislinked edge" );
1180  }
1181 
1182  if ( check == e1 || check == e2 ) {
1183  continue;
1184  }
1185 
1186  if ( IsTriangleValid( ov, second, middle )
1187  && IsTriangleValid( ov, middle, third ) ) {
1188  break; // should use the subdivided ones
1189  }
1190  }
1191 
1192  if ( check ) {
1193  continue; // don't use it
1194  }
1195 
1196  // the triangle is valid
1197  CreateOptTri( ov, e1, e2, island );
1198  }
1199  }
1200 
1201  // later vertexes will not emit triangles that use an
1202  // edge that this vert has already used
1203  ov->emited = true;
1204  }
1205 }
1206 
1207 
1208 
1209 /*
1210 ====================
1211 RegenerateTriangles
1212 
1213 Add new triangles to the group's regeneratedTris
1214 ====================
1215 */
1216 static void RegenerateTriangles( optIsland_t *island ) {
1217  optTri_t *optTri;
1218  mapTri_t *tri;
1219  int c_out;
1220 
1221  c_out = 0;
1222 
1223  for ( optTri = island->tris ; optTri ; optTri = optTri->next ) {
1224  if ( !optTri->filled ) {
1225  continue;
1226  }
1227 
1228  // create a new mapTri_t
1229  tri = AllocTri();
1230 
1231  tri->material = island->group->material;
1232  tri->mergeGroup = island->group->mergeGroup;
1233 
1234  tri->v[0] = optTri->v[0]->v;
1235  tri->v[1] = optTri->v[1]->v;
1236  tri->v[2] = optTri->v[2]->v;
1237 
1238  idPlane plane;
1239  PlaneForTri( tri, plane );
1240  if ( plane.Normal() * dmapGlobals.mapPlanes[ island->group->planeNum ].Normal() <= 0 ) {
1241  // this can happen reasonably when a triangle is nearly degenerate in
1242  // optimization planar space, and winds up being degenerate in 3D space
1243  common->Printf( "WARNING: backwards triangle generated!\n" );
1244  // discard it
1245  FreeTri( tri );
1246  continue;
1247  }
1248 
1249  c_out++;
1250  tri->next = island->group->regeneratedTris;
1251  island->group->regeneratedTris = tri;
1252  }
1253 
1254  FreeOptTriangles( island );
1255 
1256  if ( dmapGlobals.verbose ) {
1257  common->Printf( "%6i tris out\n", c_out );
1258  }
1259 }
1260 
1261 //===========================================================================
1262 
1263 /*
1264 ====================
1265 RemoveInteriorEdges
1266 
1267 Edges that have triangles of the same type (filled / empty)
1268 on both sides will be removed
1269 ====================
1270 */
1271 static void RemoveInteriorEdges( optIsland_t *island ) {
1272  int c_interiorEdges;
1273  int c_exteriorEdges;
1274  optEdge_t *e, *next;
1275  bool front, back;
1276 
1277  c_exteriorEdges = 0;
1278  c_interiorEdges = 0;
1279  for ( e = island->edges ; e ; e = next ) {
1280  // we might remove the edge, so get the next link now
1281  next = e->islandLink;
1282 
1283  if ( !e->frontTri ) {
1284  front = false;
1285  } else {
1286  front = e->frontTri->filled;
1287  }
1288  if ( !e->backTri ) {
1289  back = false;
1290  } else {
1291  back = e->backTri->filled;
1292  }
1293 
1294  if ( front == back ) {
1295  // free the edge
1296  UnlinkEdge( e, island );
1297  c_interiorEdges++;
1298  continue;
1299  }
1300 
1301  c_exteriorEdges++;
1302  }
1303 
1304  if ( dmapGlobals.verbose ) {
1305  common->Printf( "%6i original interior edges\n", c_interiorEdges );
1306  common->Printf( "%6i original exterior edges\n", c_exteriorEdges );
1307  }
1308 }
1309 
1310 //==================================================================================
1311 
1312 typedef struct {
1313  optVertex_t *v1, *v2;
1314 } originalEdges_t;
1315 
1316 /*
1317 =================
1318 AddEdgeIfNotAlready
1319 =================
1320 */
1321 void AddEdgeIfNotAlready( optVertex_t *v1, optVertex_t *v2 ) {
1322  optEdge_t *e;
1323 
1324  // make sure that there isn't an identical edge already added
1325  for ( e = v1->edges ; e ; ) {
1326  if ( ( e->v1 == v1 && e->v2 == v2 ) || ( e->v1 == v2 && e->v2 == v1 ) ) {
1327  return; // already added
1328  }
1329  if ( e->v1 == v1 ) {
1330  e = e->v1link;
1331  } else if ( e->v2 == v1 ) {
1332  e = e->v2link;
1333  } else {
1334  common->Error( "SplitEdgeByList: bad edge link" );
1335  }
1336  }
1337 
1338  // this edge is a keeper
1339  e = AllocEdge();
1340  e->v1 = v1;
1341  e->v2 = v2;
1342 
1343  e->islandLink = NULL;
1344 
1345  // link the edge to its verts
1346  LinkEdge( e );
1347 }
1348 
1349 
1350 
1351 /*
1352 =================
1353 DrawOriginalEdges
1354 =================
1355 */
1356 static void DrawOriginalEdges( int numOriginalEdges, originalEdges_t *originalEdges ) {
1357  int i;
1358 
1359  if ( !dmapGlobals.drawflag ) {
1360  return;
1361  }
1362  Draw_ClearWindow();
1363 
1364  qglBegin( GL_LINES );
1365  for ( i = 0 ; i < numOriginalEdges ; i++ ) {
1366  qglColor3f( 1, 0, 0 );
1367  qglVertex3fv( originalEdges[i].v1->pv.ToFloatPtr() );
1368  qglColor3f( 0, 0, 0 );
1369  qglVertex3fv( originalEdges[i].v2->pv.ToFloatPtr() );
1370  }
1371  qglEnd();
1372  qglFlush();
1373 }
1374 
1375 
1376 typedef struct edgeCrossing_s {
1377  struct edgeCrossing_s *next;
1378  optVertex_t *ov;
1379 } edgeCrossing_t;
1380 
1381 static originalEdges_t *originalEdges;
1382 static int numOriginalEdges;
1383 
1384 /*
1385 =================
1386 AddOriginalTriangle
1387 =================
1388 */
1389 static void AddOriginalTriangle( optVertex_t *v[3] ) {
1390  optVertex_t *v1, *v2;
1391 
1392  // if this triangle is backwards (possible with epsilon issues)
1393  // ignore it completely
1394  if ( !IsTriangleValid( v[0], v[1], v[2] ) ) {
1395  common->Printf( "WARNING: backwards triangle in input!\n" );
1396  return;
1397  }
1398 
1399  for ( int i = 0 ; i < 3 ; i++ ) {
1400  v1 = v[i];
1401  v2 = v[(i+1)%3];
1402 
1403  if ( v1 == v2 ) {
1404  // this probably shouldn't happen, because the
1405  // tri would be degenerate
1406  continue;
1407  }
1408  int j;
1409  // see if there is an existing one
1410  for ( j = 0 ; j < numOriginalEdges ; j++ ) {
1411  if ( originalEdges[j].v1 == v1 && originalEdges[j].v2 == v2 ) {
1412  break;
1413  }
1414  if ( originalEdges[j].v2 == v1 && originalEdges[j].v1 == v2 ) {
1415  break;
1416  }
1417  }
1418 
1419  if ( j == numOriginalEdges ) {
1420  // add it
1421  originalEdges[j].v1 = v1;
1422  originalEdges[j].v2 = v2;
1423  numOriginalEdges++;
1424  }
1425  }
1426 }
1427 
1428 /*
1429 =================
1430 AddOriginalEdges
1431 =================
1432 */
1433 static void AddOriginalEdges( optimizeGroup_t *opt ) {
1434  mapTri_t *tri;
1435  optVertex_t *v[3];
1436  int numTris;
1437 
1438  if ( dmapGlobals.verbose ) {
1439  common->Printf( "----\n" );
1440  common->Printf( "%6i original tris\n", CountTriList( opt->triList ) );
1441  }
1442 
1443  optBounds.Clear();
1444 
1445  // allocate space for max possible edges
1446  numTris = CountTriList( opt->triList );
1447  originalEdges = (originalEdges_t *)Mem_Alloc( numTris * 3 * sizeof( *originalEdges ) );
1448  numOriginalEdges = 0;
1449 
1450  // add all unique triangle edges
1451  numOptVerts = 0;
1452  numOptEdges = 0;
1453  for ( tri = opt->triList ; tri ; tri = tri->next ) {
1454  v[0] = tri->optVert[0] = FindOptVertex( &tri->v[0], opt );
1455  v[1] = tri->optVert[1] = FindOptVertex( &tri->v[1], opt );
1456  v[2] = tri->optVert[2] = FindOptVertex( &tri->v[2], opt );
1457 
1458  AddOriginalTriangle( v );
1459  }
1460 }
1461 
1462 /*
1463 =====================
1464 SplitOriginalEdgesAtCrossings
1465 =====================
1466 */
1467 void SplitOriginalEdgesAtCrossings( optimizeGroup_t *opt ) {
1468  int i, j, k, l;
1469  int numOriginalVerts;
1470  edgeCrossing_t **crossings;
1471 
1472  numOriginalVerts = numOptVerts;
1473  // now split any crossing edges and create optEdges
1474  // linked to the vertexes
1475 
1476  // debug drawing bounds
1477  dmapGlobals.drawBounds = optBounds;
1478 
1479  dmapGlobals.drawBounds[0][0] -= 2;
1480  dmapGlobals.drawBounds[0][1] -= 2;
1481  dmapGlobals.drawBounds[1][0] += 2;
1482  dmapGlobals.drawBounds[1][1] += 2;
1483 
1484  // generate crossing points between all the original edges
1485  crossings = (edgeCrossing_t **)Mem_ClearedAlloc( numOriginalEdges * sizeof( *crossings ) );
1486 
1487  for ( i = 0 ; i < numOriginalEdges ; i++ ) {
1488  if ( dmapGlobals.drawflag ) {
1489  DrawOriginalEdges( numOriginalEdges, originalEdges );
1490  qglBegin( GL_LINES );
1491  qglColor3f( 0, 1, 0 );
1492  qglVertex3fv( originalEdges[i].v1->pv.ToFloatPtr() );
1493  qglColor3f( 0, 0, 1 );
1494  qglVertex3fv( originalEdges[i].v2->pv.ToFloatPtr() );
1495  qglEnd();
1496  qglFlush();
1497  }
1498  for ( j = i+1 ; j < numOriginalEdges ; j++ ) {
1499  optVertex_t *v1, *v2, *v3, *v4;
1500  optVertex_t *newVert;
1501  edgeCrossing_t *cross;
1502 
1503  v1 = originalEdges[i].v1;
1504  v2 = originalEdges[i].v2;
1505  v3 = originalEdges[j].v1;
1506  v4 = originalEdges[j].v2;
1507 
1508  if ( !EdgesCross( v1, v2, v3, v4 ) ) {
1509  continue;
1510  }
1511 
1512  // this is the only point in optimization where
1513  // completely new points are created, and it only
1514  // happens if there is overlapping coplanar
1515  // geometry in the source triangles
1516  newVert = EdgeIntersection( v1, v2, v3, v4, opt );
1517 
1518  if ( !newVert ) {
1519 //common->Printf( "lines %i (%i to %i) and %i (%i to %i) are colinear\n", i, v1 - optVerts, v2 - optVerts,
1520 // j, v3 - optVerts, v4 - optVerts ); // !@#
1521  // colinear, so add both verts of each edge to opposite
1522  if ( VertexBetween( v3, v1, v2 ) ) {
1523  cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
1524  cross->ov = v3;
1525  cross->next = crossings[i];
1526  crossings[i] = cross;
1527  }
1528 
1529  if ( VertexBetween( v4, v1, v2 ) ) {
1530  cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
1531  cross->ov = v4;
1532  cross->next = crossings[i];
1533  crossings[i] = cross;
1534  }
1535 
1536  if ( VertexBetween( v1, v3, v4 ) ) {
1537  cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
1538  cross->ov = v1;
1539  cross->next = crossings[j];
1540  crossings[j] = cross;
1541  }
1542 
1543  if ( VertexBetween( v2, v3, v4 ) ) {
1544  cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
1545  cross->ov = v2;
1546  cross->next = crossings[j];
1547  crossings[j] = cross;
1548  }
1549 
1550  continue;
1551  }
1552 #if 0
1553 if ( newVert && newVert != v1 && newVert != v2 && newVert != v3 && newVert != v4 ) {
1554 common->Printf( "lines %i (%i to %i) and %i (%i to %i) cross at new point %i\n", i, v1 - optVerts, v2 - optVerts,
1555  j, v3 - optVerts, v4 - optVerts, newVert - optVerts );
1556 } else if ( newVert ) {
1557 common->Printf( "lines %i (%i to %i) and %i (%i to %i) intersect at old point %i\n", i, v1 - optVerts, v2 - optVerts,
1558  j, v3 - optVerts, v4 - optVerts, newVert - optVerts );
1559 }
1560 #endif
1561  if ( newVert != v1 && newVert != v2 ) {
1562  cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
1563  cross->ov = newVert;
1564  cross->next = crossings[i];
1565  crossings[i] = cross;
1566  }
1567 
1568  if ( newVert != v3 && newVert != v4 ) {
1569  cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
1570  cross->ov = newVert;
1571  cross->next = crossings[j];
1572  crossings[j] = cross;
1573  }
1574 
1575  }
1576  }
1577 
1578 
1579  // now split each edge by its crossing points
1580  // colinear edges will have duplicated edges added, but it won't hurt anything
1581  for ( i = 0 ; i < numOriginalEdges ; i++ ) {
1582  edgeCrossing_t *cross, *nextCross;
1583  int numCross;
1584  optVertex_t **sorted;
1585 
1586  numCross = 0;
1587  for ( cross = crossings[i] ; cross ; cross = cross->next ) {
1588  numCross++;
1589  }
1590  numCross += 2; // account for originals
1591  sorted = (optVertex_t **)Mem_Alloc( numCross * sizeof( *sorted ) );
1592  sorted[0] = originalEdges[i].v1;
1593  sorted[1] = originalEdges[i].v2;
1594  j = 2;
1595  for ( cross = crossings[i] ; cross ; cross = nextCross ) {
1596  nextCross = cross->next;
1597  sorted[j] = cross->ov;
1598  Mem_Free( cross );
1599  j++;
1600  }
1601 
1602  // add all possible fragment combinations that aren't divided
1603  // by another point
1604  for ( j = 0 ; j < numCross ; j++ ) {
1605  for ( k = j+1 ; k < numCross ; k++ ) {
1606  for ( l = 0 ; l < numCross ; l++ ) {
1607  if ( sorted[l] == sorted[j] || sorted[l] == sorted[k] ) {
1608  continue;
1609  }
1610  if ( sorted[j] == sorted[k] ) {
1611  continue;
1612  }
1613  if ( VertexBetween( sorted[l], sorted[j], sorted[k] ) ) {
1614  break;
1615  }
1616  }
1617  if ( l == numCross ) {
1618 //common->Printf( "line %i fragment from point %i to %i\n", i, sorted[j] - optVerts, sorted[k] - optVerts );
1619  AddEdgeIfNotAlready( sorted[j], sorted[k] );
1620  }
1621  }
1622  }
1623 
1624  Mem_Free( sorted );
1625  }
1626 
1627 
1628  Mem_Free( crossings );
1629  Mem_Free( originalEdges );
1630 
1631  // check for duplicated edges
1632  for ( i = 0 ; i < numOptEdges ; i++ ) {
1633  for ( j = i+1 ; j < numOptEdges ; j++ ) {
1634  if ( ( optEdges[i].v1 == optEdges[j].v1 && optEdges[i].v2 == optEdges[j].v2 )
1635  || ( optEdges[i].v1 == optEdges[j].v2 && optEdges[i].v2 == optEdges[j].v1 ) ) {
1636  common->Printf( "duplicated optEdge\n" );
1637  }
1638  }
1639  }
1640 
1641  if ( dmapGlobals.verbose ) {
1642  common->Printf( "%6i original edges\n", numOriginalEdges );
1643  common->Printf( "%6i edges after splits\n", numOptEdges );
1644  common->Printf( "%6i original vertexes\n", numOriginalVerts );
1645  common->Printf( "%6i vertexes after splits\n", numOptVerts );
1646  }
1647 }
1648 
1649 //=================================================================
1650 
1651 
1652 /*
1653 ===================
1654 CullUnusedVerts
1655 
1656 Unlink any verts with no edges, so they
1657 won't be used in the retriangulation
1658 ===================
1659 */
1660 static void CullUnusedVerts( optIsland_t *island ) {
1661  optVertex_t **prev, *vert;
1662  int c_keep, c_free;
1663  optEdge_t *edge;
1664 
1665  c_keep = 0;
1666  c_free = 0;
1667 
1668  for ( prev = &island->verts ; *prev ; ) {
1669  vert = *prev;
1670 
1671  if ( !vert->edges ) {
1672  // free it
1673  *prev = vert->islandLink;
1674  c_free++;
1675  } else {
1676  edge = vert->edges;
1677  if ( ( edge->v1 == vert && !edge->v1link )
1678  || ( edge->v2 == vert && !edge->v2link ) ) {
1679  // is is occasionally possible to get a vert
1680  // with only a single edge when colinear optimizations
1681  // crunch down a complex sliver
1682  UnlinkEdge( edge, island );
1683  // free it
1684  *prev = vert->islandLink;
1685  c_free++;
1686  } else {
1687  prev = &vert->islandLink;
1688  c_keep++;
1689  }
1690  }
1691  }
1692 
1693  if ( dmapGlobals.verbose ) {
1694  common->Printf( "%6i verts kept\n", c_keep );
1695  common->Printf( "%6i verts freed\n", c_free );
1696  }
1697 }
1698 
1699 
1700 
1701 /*
1702 ====================
1703 OptimizeIsland
1704 
1705 At this point, all needed vertexes are already in the
1706 list, including any that were added at crossing points.
1707 
1708 Interior and colinear vertexes will be removed, and
1709 a new triangulation will be created.
1710 ====================
1711 */
1712 static void OptimizeIsland( optIsland_t *island ) {
1713  // add space-filling fake edges so we have a complete
1714  // triangulation of a convex hull before optimization
1715  AddInteriorEdges( island );
1716  DrawEdges( island );
1717 
1718  // determine all the possible triangles, and decide if
1719  // the are filled or empty
1720  BuildOptTriangles( island );
1721 
1722  // remove interior vertexes that have filled triangles
1723  // between all their edges
1724  RemoveInteriorEdges( island );
1725  DrawEdges( island );
1726 
1727  ValidateEdgeCounts( island );
1728 
1729  // remove vertexes that only have two colinear edges
1730  CombineColinearEdges( island );
1731  CullUnusedVerts( island );
1732  DrawEdges( island );
1733 
1734  // add new internal edges between the remaining exterior edges
1735  // to give us a full triangulation again
1736  AddInteriorEdges( island );
1737  DrawEdges( island );
1738 
1739  // determine all the possible triangles, and decide if
1740  // the are filled or empty
1741  BuildOptTriangles( island );
1742 
1743  // make mapTri_t out of the filled optTri_t
1744  RegenerateTriangles( island );
1745 }
1746 
1747 /*
1748 ================
1749 AddVertexToIsland_r
1750 ================
1751 */
1752 static void AddVertexToIsland_r( optVertex_t *vert, optIsland_t *island ) {
1753  optEdge_t *e;
1754 
1755  // we can't just check islandLink, because the
1756  // last vert will have a NULL
1757  if ( vert->addedToIsland ) {
1758  return;
1759  }
1760  vert->addedToIsland = true;
1761  vert->islandLink = island->verts;
1762  island->verts = vert;
1763 
1764  for ( e = vert->edges ; e ; ) {
1765  if ( !e->addedToIsland ) {
1766  e->addedToIsland = true;
1767 
1768  e->islandLink = island->edges;
1769  island->edges = e;
1770  }
1771 
1772  if ( e->v1 == vert ) {
1773  AddVertexToIsland_r( e->v2, island );
1774  e = e->v1link;
1775  continue;
1776  }
1777  if ( e->v2 == vert ) {
1778  AddVertexToIsland_r( e->v1, island );
1779  e = e->v2link;
1780  continue;
1781  }
1782  common->Error( "AddVertexToIsland_r: mislinked vert" );
1783  }
1784 
1785 }
1786 
1787 /*
1788 ====================
1789 SeparateIslands
1790 
1791 While the algorithm should theoretically handle any collection
1792 of triangles, there are speed and stability benefits to making
1793 it work on as small a list as possible, so separate disconnected
1794 collections of edges and process separately.
1795 
1796 FIXME: we need to separate the source triangles before
1797 doing this, because PointInSourceTris() can give a bad answer if
1798 the source list has triangles not used in the optimization
1799 ====================
1800 */
1801 static void SeparateIslands( optimizeGroup_t *opt ) {
1802  int i;
1803  optIsland_t island;
1804  int numIslands;
1805 
1806  DrawAllEdges();
1807 
1808  numIslands = 0;
1809  for ( i = 0 ; i < numOptVerts ; i++ ) {
1810  if ( optVerts[i].addedToIsland ) {
1811  continue;
1812  }
1813  numIslands++;
1814  memset( &island, 0, sizeof( island ) );
1815  island.group = opt;
1816  AddVertexToIsland_r( &optVerts[i], &island );
1817  OptimizeIsland( &island );
1818  }
1819  if ( dmapGlobals.verbose ) {
1820  common->Printf( "%6i islands\n", numIslands );
1821  }
1822 }
1823 
1824 static void DontSeparateIslands( optimizeGroup_t *opt ) {
1825  int i;
1826  optIsland_t island;
1827 
1828  DrawAllEdges();
1829 
1830  memset( &island, 0, sizeof( island ) );
1831  island.group = opt;
1832 
1833  // link everything together
1834  for ( i = 0 ; i < numOptVerts ; i++ ) {
1835  optVerts[i].islandLink = island.verts;
1836  island.verts = &optVerts[i];
1837  }
1838 
1839  for ( i = 0 ; i < numOptEdges ; i++ ) {
1840  optEdges[i].islandLink = island.edges;
1841  island.edges = &optEdges[i];
1842  }
1843 
1844  OptimizeIsland( &island );
1845 }
1846 
1847 
1848 /*
1849 ====================
1850 PointInSourceTris
1851 
1852 This is a sloppy bounding box check
1853 ====================
1854 */
1855 static bool PointInSourceTris( float x, float y, float z, optimizeGroup_t *opt ) {
1856  mapTri_t *tri;
1857  idBounds b;
1858  idVec3 p;
1859 
1860  if ( !opt->material->IsDrawn() ) {
1861  return false;
1862  }
1863 
1864  p[0] = x;
1865  p[1] = y;
1866  p[2] = z;
1867  for ( tri = opt->triList ; tri ; tri = tri->next ) {
1868  b.Clear();
1869  b.AddPoint( tri->v[0].xyz );
1870  b.AddPoint( tri->v[1].xyz );
1871  b.AddPoint( tri->v[2].xyz );
1872 
1873  if ( b.ContainsPoint( p ) ) {
1874  return true;
1875  }
1876  }
1877  return false;
1878 }
1879 
1880 /*
1881 ====================
1882 OptimizeOptList
1883 ====================
1884 */
1885 static void OptimizeOptList( optimizeGroup_t *opt ) {
1886  optimizeGroup_t *oldNext;
1887 
1888  // fix the t junctions among this single list
1889  // so we can match edges
1890  // can we avoid doing this if colinear vertexes break edges?
1891  oldNext = opt->nextGroup;
1892  opt->nextGroup = NULL;
1893  FixAreaGroupsTjunctions( opt );
1894  opt->nextGroup = oldNext;
1895 
1896  // create the 2D vectors
1897  dmapGlobals.mapPlanes[opt->planeNum].Normal().NormalVectors( opt->axis[0], opt->axis[1] );
1898 
1899  AddOriginalEdges( opt );
1900  SplitOriginalEdgesAtCrossings( opt );
1901 
1902 #if 0
1903  // seperate any discontinuous areas for individual optimization
1904  // to reduce the scope of the problem
1905  SeparateIslands( opt );
1906 #else
1907  DontSeparateIslands( opt );
1908 #endif
1909 
1910  // now free the hash verts
1911  FreeTJunctionHash();
1912 
1913  // free the original list and use the new one
1914  FreeTriList( opt->triList );
1915  opt->triList = opt->regeneratedTris;
1916  opt->regeneratedTris = NULL;
1917 }
1918 
1919 
1920 /*
1921 ==================
1922 SetGroupTriPlaneNums
1923 
1924 Copies the group planeNum to every triangle in each group
1925 ==================
1926 */
1927 void SetGroupTriPlaneNums( optimizeGroup_t *groups ) {
1928  mapTri_t *tri;
1929  optimizeGroup_t *group;
1930 
1931  for ( group = groups ; group ; group = group->nextGroup ) {
1932  for ( tri = group->triList ; tri ; tri = tri->next ) {
1933  tri->planeNum = group->planeNum;
1934  }
1935  }
1936 }
1937 
1938 
1939 /*
1940 ===================
1941 OptimizeGroupList
1942 
1943 This will also fix tjunctions
1944 
1945 ===================
1946 */
1947 void OptimizeGroupList( optimizeGroup_t *groupList ) {
1948  int c_in, c_edge, c_tjunc2;
1949  optimizeGroup_t *group;
1950 
1951  if ( !groupList ) {
1952  return;
1953  }
1954 
1955  c_in = CountGroupListTris( groupList );
1956 
1957  // optimize and remove colinear edges, which will
1958  // re-introduce some t junctions
1959  for ( group = groupList ; group ; group = group->nextGroup ) {
1960  OptimizeOptList( group );
1961  }
1962  c_edge = CountGroupListTris( groupList );
1963 
1964  // fix t junctions again
1965  FixAreaGroupsTjunctions( groupList );
1966  FreeTJunctionHash();
1967  c_tjunc2 = CountGroupListTris( groupList );
1968 
1969  SetGroupTriPlaneNums( groupList );
1970 
1971  common->Printf( "----- OptimizeAreaGroups Results -----\n" );
1972  common->Printf( "%6i tris in\n", c_in );
1973  common->Printf( "%6i tris after edge removal optimization\n", c_edge );
1974  common->Printf( "%6i tris after final t junction fixing\n", c_tjunc2 );
1975 }
1976 
1977 
1978 /*
1979 ==================
1980 OptimizeEntity
1981 ==================
1982 */
1983 void OptimizeEntity( uEntity_t *e ) {
1984  int i;
1985 
1986  common->Printf( "----- OptimizeEntity -----\n" );
1987  for ( i = 0 ; i < e->numAreas ; i++ ) {
1988  OptimizeGroupList( e->areas[i].groups );
1989  }
1990 }
originalEdges_t::v1
optVertex_t * v1
Definition: optimize.cpp:1313
idVec3::Normalize
float Normalize(void)
Definition: Vector.h:646
cross
void cross(float a[], float b[], float c[])
Definition: Model_lwo.cpp:3889
AddEdgeIfNotAlready
void AddEdgeIfNotAlready(optVertex_t *v1, optVertex_t *v2)
Definition: optimize.cpp:1321
idPlane::Normal
const idVec3 & Normal(void) const
Definition: Plane.h:239
optVertex_s::edges
struct optEdge_s * edges
Definition: dmap.h:415
qglDisable
#define qglDisable
Definition: qgl_linked.h:92
mapTri_s::next
struct mapTri_s * next
Definition: dmap.h:60
edgeLength_t::length
float length
Definition: optimize.cpp:511
v
const GLdouble * v
Definition: glext.h:2936
optVertex_s::emited
bool emited
Definition: dmap.h:418
idVec3::ToFloatPtr
const float * ToFloatPtr(void) const
Definition: Vector.h:719
VectorSubtract
#define VectorSubtract(a, b, c)
Definition: Vector.h:1995
edgeLength_t
Definition: optimize.cpp:509
originalEdges_t
Definition: optimize.cpp:1312
idDrawVert::xyz
idVec3 xyz
Definition: DrawVert.h:42
mapTri_s::mergeGroup
void * mergeGroup
Definition: dmap.h:63
y
GLenum GLint GLint y
Definition: glext.h:2849
FindOptVertex
optVertex_t * FindOptVertex(idDrawVert *v, optimizeGroup_t *opt)
Definition: optimize_gcc.cpp:51
optTri_s::filled
bool filled
Definition: dmap.h:435
qglBegin
#define qglBegin
Definition: qgl_linked.h:33
optEdge_s::v1
optVertex_t * v1
Definition: dmap.h:422
optVertex_s::islandLink
struct optVertex_s * islandLink
Definition: dmap.h:416
idVec3
Definition: Vector.h:316
FreeTri
void FreeTri(mapTri_t *tri)
Definition: tritools.cpp:58
uEntity_t::areas
uArea_t * areas
Definition: dmap.h:54
qglVertex3fv
#define qglVertex3fv
Definition: qgl_linked.h:350
idBounds::Clear
void Clear(void)
Definition: Bounds.h:201
dmapGlobals_t::verbose
bool verbose
Definition: dmap.h:248
optTri_s::v
optVertex_t * v[3]
Definition: dmap.h:434
optVertex_s::addedToIsland
bool addedToIsland
Definition: dmap.h:417
len
GLenum GLsizei len
Definition: glext.h:3472
idVec3::Cross
idVec3 Cross(const idVec3 &a) const
Definition: Vector.h:619
SetGroupTriPlaneNums
void SetGroupTriPlaneNums(optimizeGroup_t *groups)
Definition: optimize.cpp:1927
optEdge_s::created
bool created
Definition: dmap.h:425
x
GLenum GLint x
Definition: glext.h:2849
process.i
int i
Definition: process.py:33
offset
GLintptr offset
Definition: glext.h:3113
optEdge_s::backTri
struct optTri_s * backTri
Definition: dmap.h:427
idMaterial::IsDrawn
bool IsDrawn(void) const
Definition: Material.h:378
mapTri_s::planeNum
int planeNum
Definition: dmap.h:65
qglEnable
#define qglEnable
Definition: qgl_linked.h:101
dmapGlobals_t::mapPlanes
idPlaneSet mapPlanes
Definition: dmap.h:239
prepare.l
list l
Definition: prepare.py:17
optIsland_t
Definition: dmap.h:438
FreeTriList
void FreeTriList(mapTri_t *a)
Definition: tritools.cpp:89
Draw_ClearWindow
void Draw_ClearWindow(void)
Definition: gldraw.cpp:273
optVertex_s::pv
idVec3 pv
Definition: dmap.h:414
optTri_s::midpoint
idVec3 midpoint
Definition: dmap.h:433
mapTri_s::v
idDrawVert v[3]
Definition: dmap.h:67
uArea_t::groups
struct optimizeGroup_s * groups
Definition: dmap.h:42
optEdge_s::frontTri
struct optTri_s * frontTri
Definition: dmap.h:427
idBounds::AddPoint
bool AddPoint(const idVec3 &v)
Definition: Bounds.h:226
OptimizeEntity
void OptimizeEntity(uEntity_t *e)
Definition: optimize.cpp:1983
idDrawVert::st
idVec2 st
Definition: DrawVert.h:43
v2
GLfloat GLfloat GLfloat v2
Definition: glext.h:3608
idRandom::RandomInt
int RandomInt(void)
Definition: Random.h:70
optimizeGroup_s::axis
idVec3 axis[2]
Definition: dmap.h:209
c
const GLubyte * c
Definition: glext.h:4677
idVec3::Length
float Length(void) const
Definition: Vector.h:631
optimizeGroup_s::regeneratedTris
mapTri_t * regeneratedTris
Definition: dmap.h:208
common
idCommon * common
Definition: Common.cpp:206
NULL
#define NULL
Definition: Lib.h:88
optimizeGroup_s
Definition: dmap.h:188
qglEnd
#define qglEnd
Definition: qgl_linked.h:103
PlaneForTri
void PlaneForTri(const mapTri_t *tri, idPlane &plane)
Definition: tritools.cpp:385
qglColor3f
#define qglColor3f
Definition: qgl_linked.h:50
idPlane
Definition: Plane.h:71
dmapGlobals_t::drawflag
bool drawflag
Definition: dmap.h:265
edgeCrossing_t
struct edgeCrossing_s edgeCrossing_t
optEdge_s::v1link
struct optEdge_s * v1link
Definition: dmap.h:428
mapTri_s::optVert
struct optVertex_s * optVert[3]
Definition: dmap.h:69
originalEdges_t::v2
optVertex_t * v2
Definition: optimize.cpp:1313
optimizeGroup_s::planeNum
int planeNum
Definition: dmap.h:195
FixAreaGroupsTjunctions
void FixAreaGroupsTjunctions(optimizeGroup_t *groupList)
Definition: tritjunction.cpp:466
Mem_Free
void Mem_Free(void *ptr)
Definition: Heap.cpp:1087
idDrawVert::normal
idVec3 normal
Definition: DrawVert.h:44
dmapGlobals_t::drawBounds
idBounds drawBounds
Definition: dmap.h:264
a
GLubyte GLubyte GLubyte a
Definition: glext.h:4662
idCommon::Printf
virtual void Printf(const char *fmt,...) id_attribute((format(printf
edgeLength_t::v2
optVertex_t * v2
Definition: optimize.cpp:510
AllocTri
mapTri_t * AllocTri(void)
Definition: tritools.cpp:45
optimizeGroup_s::mergeGroup
void * mergeGroup
Definition: dmap.h:200
qglPointSize
#define qglPointSize
Definition: qgl_linked.h:228
v1
GLfloat GLfloat v1
Definition: glext.h:3607
edgeCrossing_s::next
struct edgeCrossing_s * next
Definition: optimize.cpp:1377
b
GLubyte GLubyte b
Definition: glext.h:4662
optBounds
idBounds optBounds
Definition: optimize.cpp:50
MAX_OPT_EDGES
#define MAX_OPT_EDGES
Definition: optimize.cpp:56
qglFlush
#define qglFlush
Definition: qgl_linked.h:119
optTri_s
Definition: dmap.h:431
v3
GLfloat GLfloat GLfloat GLfloat v3
Definition: glext.h:3609
CountGroupListTris
int CountGroupListTris(const optimizeGroup_t *groupList)
Definition: tritjunction.cpp:450
edgeCrossing_s::ov
optVertex_t * ov
Definition: optimize.cpp:1378
mapTri_s
Definition: dmap.h:59
optEdge_s::islandLink
struct optEdge_s * islandLink
Definition: dmap.h:423
MAX_OPT_VERTEXES
#define MAX_OPT_VERTEXES
Definition: optimize.cpp:52
FreeTJunctionHash
void FreeTJunctionHash(void)
Definition: tritjunction.cpp:273
mapTri_s::material
const idMaterial * material
Definition: dmap.h:62
idal.f
tuple f
Definition: idal.py:89
SplitOriginalEdgesAtCrossings
void SplitOriginalEdgesAtCrossings(optimizeGroup_t *opt)
Definition: optimize.cpp:1467
uEntity_t
Definition: dmap.h:46
optIsland_t::group
optimizeGroup_t * group
Definition: dmap.h:439
optIsland_t::verts
optVertex_t * verts
Definition: dmap.h:440
optimizeGroup_s::triList
mapTri_t * triList
Definition: dmap.h:207
COLINEAR_EPSILON
#define COLINEAR_EPSILON
Definition: optimize.cpp:606
CountTriList
int CountTriList(const mapTri_t *list)
Definition: tritools.cpp:125
optIsland_t::tris
optTri_t * tris
Definition: dmap.h:442
optEdge_s::addedToIsland
bool addedToIsland
Definition: dmap.h:424
optimizeGroup_s::nextGroup
struct optimizeGroup_s * nextGroup
Definition: dmap.h:189
qglBlendFunc
#define qglBlendFunc
Definition: qgl_linked.h:36
optVertex_s::v
idDrawVert v
Definition: dmap.h:413
Mem_ClearedAlloc
void * Mem_ClearedAlloc(const int size)
Definition: Heap.cpp:1149
optVerts
optVertex_t optVerts[MAX_OPT_VERTEXES]
Definition: optimize.cpp:54
DotProduct
#define DotProduct(a, b)
Definition: Vector.h:1994
optimizeGroup_s::material
const idMaterial * material
Definition: dmap.h:197
Mem_Alloc
void * Mem_Alloc(const int size)
Definition: Heap.cpp:1067
numOptVerts
int numOptVerts
Definition: optimize.cpp:53
j
GLint j
Definition: qgl.h:264
optEdge_s
Definition: dmap.h:421
VectorMA
#define VectorMA(v, s, b, o)
Definition: Vector.h:1998
first
GLint * first
Definition: glext.h:3036
optTri_s::next
struct optTri_s * next
Definition: dmap.h:432
dmapGlobals
dmapGlobals_t dmapGlobals
Definition: dmap.cpp:34
edgeLength_t::v1
optVertex_t * v1
Definition: optimize.cpp:510
idCommon::Error
virtual void Error(const char *fmt,...) id_attribute((format(printf
p
GLfloat GLfloat p
Definition: glext.h:4674
z
GLdouble GLdouble z
Definition: glext.h:3067
optEdge_s::v2
optVertex_t * v2
Definition: dmap.h:422
idBounds::ContainsPoint
bool ContainsPoint(const idVec3 &p) const
Definition: Bounds.h:353
optIsland_t::edges
optEdge_t * edges
Definition: dmap.h:441
optVertex_s
Definition: dmap.h:412
optEdge_s::v2link
struct optEdge_s * v2link
Definition: dmap.h:428
OptimizeGroupList
void OptimizeGroupList(optimizeGroup_t *groupList)
Definition: optimize.cpp:1947
uEntity_t::numAreas
int numAreas
Definition: dmap.h:53
edgeCrossing_s
Definition: optimize.cpp:1376
This page is maintained by Wladimir van der Laan. Generated on Mon Nov 17 2014 12:23:29 for doom3-gpl by doxygen 1.8.6.