2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
\r
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
\r
5 This file is part of GtkRadiant.
\r
7 GtkRadiant is free software; you can redistribute it and/or modify
\r
8 it under the terms of the GNU General Public License as published by
\r
9 the Free Software Foundation; either version 2 of the License, or
\r
10 (at your option) any later version.
\r
12 GtkRadiant is distributed in the hope that it will be useful,
\r
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
15 GNU General Public License for more details.
\r
17 You should have received a copy of the GNU General Public License
\r
18 along with GtkRadiant; if not, write to the Free Software
\r
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
\r
21 ----------------------------------------------------------------------------------
\r
23 This code has been altered significantly from its original form, to support
\r
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
\r
26 ------------------------------------------------------------------------------- */
\r
41 typedef struct edgePoint_s {
\r
44 struct edgePoint_s *prev, *next;
\r
47 typedef struct edgeLine_s {
\r
57 edgePoint_t chain; // unused element of doubly linked list
\r
62 bspDrawVert_t *dv[2];
\r
65 #define MAX_ORIGINAL_EDGES 0x10000
\r
66 originalEdge_t originalEdges[MAX_ORIGINAL_EDGES];
\r
67 int numOriginalEdges;
\r
70 #define MAX_EDGE_LINES 0x10000
\r
71 edgeLine_t edgeLines[MAX_EDGE_LINES];
\r
74 int c_degenerateEdges;
\r
78 int c_natural, c_rotate, c_cant;
\r
80 // these should be whatever epsilon we actually expect,
\r
81 // plus SNAP_INT_TO_FLOAT
\r
82 #define LINE_POSITION_EPSILON 0.25
\r
83 #define POINT_ON_LINE_EPSILON 0.25
\r
86 ====================
\r
88 ====================
\r
90 void InsertPointOnEdge( vec3_t v, edgeLine_t *e ) {
\r
93 edgePoint_t *p, *scan;
\r
95 VectorSubtract( v, e->origin, delta );
\r
96 d = DotProduct( delta, e->dir );
\r
98 p = safe_malloc( sizeof(edgePoint_t) );
\r
100 VectorCopy( v, p->xyz );
\r
102 if ( e->chain.next == &e->chain ) {
\r
103 e->chain.next = e->chain.prev = p;
\r
104 p->next = p->prev = &e->chain;
\r
108 scan = e->chain.next;
\r
109 for ( ; scan != &e->chain ; scan = scan->next ) {
\r
110 d = p->intercept - scan->intercept;
\r
111 if ( d > -LINE_POSITION_EPSILON && d < LINE_POSITION_EPSILON ) {
\r
113 return; // the point is already set
\r
116 if ( p->intercept < scan->intercept ) {
\r
118 p->prev = scan->prev;
\r
120 scan->prev->next = p;
\r
127 p->prev = scan->prev;
\r
129 scan->prev->next = p;
\r
135 ====================
\r
137 ====================
\r
139 int AddEdge( vec3_t v1, vec3_t v2, qboolean createNonAxial ) {
\r
145 VectorSubtract( v2, v1, dir );
\r
146 d = VectorNormalize( dir, dir );
\r
148 // if we added a 0 length vector, it would make degenerate planes
\r
149 c_degenerateEdges++;
\r
153 if ( !createNonAxial ) {
\r
154 if ( fabs( dir[0] + dir[1] + dir[2] ) != 1.0 ) {
\r
155 if ( numOriginalEdges == MAX_ORIGINAL_EDGES ) {
\r
156 Error( "MAX_ORIGINAL_EDGES" );
\r
158 originalEdges[ numOriginalEdges ].dv[0] = (bspDrawVert_t *)v1;
\r
159 originalEdges[ numOriginalEdges ].dv[1] = (bspDrawVert_t *)v2;
\r
160 originalEdges[ numOriginalEdges ].length = d;
\r
161 numOriginalEdges++;
\r
166 for ( i = 0 ; i < numEdgeLines ; i++ ) {
\r
169 d = DotProduct( v1, e->normal1 ) - e->dist1;
\r
170 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
\r
173 d = DotProduct( v1, e->normal2 ) - e->dist2;
\r
174 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
\r
178 d = DotProduct( v2, e->normal1 ) - e->dist1;
\r
179 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
\r
182 d = DotProduct( v2, e->normal2 ) - e->dist2;
\r
183 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
\r
187 // this is the edge
\r
188 InsertPointOnEdge( v1, e );
\r
189 InsertPointOnEdge( v2, e );
\r
193 // create a new edge
\r
194 if ( numEdgeLines >= MAX_EDGE_LINES ) {
\r
195 Error( "MAX_EDGE_LINES" );
\r
198 e = &edgeLines[ numEdgeLines ];
\r
201 e->chain.next = e->chain.prev = &e->chain;
\r
203 VectorCopy( v1, e->origin );
\r
204 VectorCopy( dir, e->dir );
\r
206 MakeNormalVectors( e->dir, e->normal1, e->normal2 );
\r
207 e->dist1 = DotProduct( e->origin, e->normal1 );
\r
208 e->dist2 = DotProduct( e->origin, e->normal2 );
\r
210 InsertPointOnEdge( v1, e );
\r
211 InsertPointOnEdge( v2, e );
\r
213 return numEdgeLines - 1;
\r
220 adds a surface's edges
\r
223 void AddSurfaceEdges( mapDrawSurface_t *ds )
\r
228 for( i = 0; i < ds->numVerts; i++ )
\r
230 /* save the edge number in the lightmap field so we don't need to look it up again */
\r
231 ds->verts[i].lightmap[ 0 ][ 0 ] =
\r
232 AddEdge( ds->verts[ i ].xyz, ds->verts[ (i + 1) % ds->numVerts ].xyz, qfalse );
\r
240 determines if an edge is colinear
\r
243 qboolean ColinearEdge( vec3_t v1, vec3_t v2, vec3_t v3 )
\r
245 vec3_t midpoint, dir, offset, on;
\r
248 VectorSubtract( v2, v1, midpoint );
\r
249 VectorSubtract( v3, v1, dir );
\r
250 d = VectorNormalize( dir, dir );
\r
252 return qfalse; // degenerate
\r
255 d = DotProduct( midpoint, dir );
\r
256 VectorScale( dir, d, on );
\r
257 VectorSubtract( midpoint, on, offset );
\r
258 d = VectorLength ( offset );
\r
270 ====================
\r
273 Add colinear border edges, which will fix some classes of patch to
\r
275 ====================
\r
277 void AddPatchEdges( mapDrawSurface_t *ds ) {
\r
279 float *v1, *v2, *v3;
\r
281 for ( i = 0 ; i < ds->patchWidth - 2; i+=2 ) {
\r
282 v1 = ds->verts[ i ].xyz;
\r
283 v2 = ds->verts[ i + 1 ].xyz;
\r
284 v3 = ds->verts[ i + 2 ].xyz;
\r
286 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
\r
287 if ( ColinearEdge( v1, v2, v3 ) ) {
\r
288 AddEdge( v1, v3, qfalse );
\r
291 v1 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i ].xyz;
\r
292 v2 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 1 ].xyz;
\r
293 v3 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 2 ].xyz;
\r
295 // if v2 is on the v1 to v3 line, add an edge from v1 to v3
\r
296 if ( ColinearEdge( v1, v2, v3 ) ) {
\r
297 AddEdge( v1, v3, qfalse );
\r
301 for ( i = 0 ; i < ds->patchHeight - 2 ; i+=2 ) {
\r
302 v1 = ds->verts[ i * ds->patchWidth ].xyz;
\r
303 v2 = ds->verts[ ( i + 1 ) * ds->patchWidth ].xyz;
\r
304 v3 = ds->verts[ ( i + 2 ) * ds->patchWidth ].xyz;
\r
306 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
\r
307 if ( ColinearEdge( v1, v2, v3 ) ) {
\r
308 AddEdge( v1, v3, qfalse );
\r
311 v1 = ds->verts[ ( ds->patchWidth - 1 ) + i * ds->patchWidth ].xyz;
\r
312 v2 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 1 ) * ds->patchWidth ].xyz;
\r
313 v3 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 2 ) * ds->patchWidth ].xyz;
\r
315 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
\r
316 if ( ColinearEdge( v1, v2, v3 ) ) {
\r
317 AddEdge( v1, v3, qfalse );
\r
326 ====================
\r
327 FixSurfaceJunctions
\r
328 ====================
\r
330 #define MAX_SURFACE_VERTS 256
\r
331 void FixSurfaceJunctions( mapDrawSurface_t *ds ) {
\r
336 int counts[MAX_SURFACE_VERTS];
\r
337 int originals[MAX_SURFACE_VERTS];
\r
338 int firstVert[MAX_SURFACE_VERTS];
\r
339 bspDrawVert_t verts[MAX_SURFACE_VERTS], *v1, *v2;
\r
341 float start, end, frac, c;
\r
345 originalVerts = ds->numVerts;
\r
348 for ( i = 0 ; i < ds->numVerts ; i++ )
\r
351 firstVert[i] = numVerts;
\r
354 if ( numVerts == MAX_SURFACE_VERTS ) {
\r
355 Error( "MAX_SURFACE_VERTS" );
\r
357 verts[numVerts] = ds->verts[i];
\r
358 originals[numVerts] = i;
\r
361 // check to see if there are any t junctions before the next vert
\r
362 v1 = &ds->verts[i];
\r
363 v2 = &ds->verts[ (i+1) % ds->numVerts ];
\r
365 j = (int)ds->verts[i].lightmap[ 0 ][ 0 ];
\r
367 continue; // degenerate edge
\r
369 e = &edgeLines[ j ];
\r
371 VectorSubtract( v1->xyz, e->origin, delta );
\r
372 start = DotProduct( delta, e->dir );
\r
374 VectorSubtract( v2->xyz, e->origin, delta );
\r
375 end = DotProduct( delta, e->dir );
\r
378 if ( start < end ) {
\r
384 for ( ; p != &e->chain ; ) {
\r
385 if ( start < end ) {
\r
386 if ( p->intercept > end - ON_EPSILON ) {
\r
390 if ( p->intercept < end + ON_EPSILON ) {
\r
396 ( start < end && p->intercept > start + ON_EPSILON ) ||
\r
397 ( start > end && p->intercept < start - ON_EPSILON ) ) {
\r
398 // insert this point
\r
399 if ( numVerts == MAX_SURFACE_VERTS ) {
\r
400 Error( "MAX_SURFACE_VERTS" );
\r
403 /* take the exact intercept point */
\r
404 VectorCopy( p->xyz, verts[ numVerts ].xyz );
\r
406 /* interpolate the texture coordinates */
\r
407 frac = ( p->intercept - start ) / ( end - start );
\r
408 for ( j = 0 ; j < 2 ; j++ ) {
\r
409 verts[ numVerts ].st[j] = v1->st[j] +
\r
410 frac * ( v2->st[j] - v1->st[j] );
\r
413 /* copy the normal (FIXME: what about nonplanar surfaces? */
\r
414 VectorCopy( v1->normal, verts[ numVerts ].normal );
\r
416 /* ydnar: interpolate the color */
\r
417 for( k = 0; k < MAX_LIGHTMAPS; k++ )
\r
419 for( j = 0; j < 4; j++ )
\r
421 c = (float) v1->color[ k ][ j ] + frac * ((float) v2->color[ k ][ j ] - (float) v1->color[ k ][ j ]);
\r
422 verts[ numVerts ].color[ k ][ j ] = (byte) (c < 255.0f ? c : 255);
\r
427 originals[ numVerts ] = i;
\r
432 if ( start < end ) {
\r
440 c_addedVerts += numVerts - ds->numVerts;
\r
441 c_totalVerts += numVerts;
\r
444 // FIXME: check to see if the entire surface degenerated
\r
447 // rotate the points so that the initial vertex is between
\r
448 // two non-subdivided edges
\r
449 for ( i = 0 ; i < numVerts ; i++ ) {
\r
450 if ( originals[ (i+1) % numVerts ] == originals[ i ] ) {
\r
453 j = (i + numVerts - 1 ) % numVerts;
\r
454 k = (i + numVerts - 2 ) % numVerts;
\r
455 if ( originals[ j ] == originals[ k ] ) {
\r
462 // fine the way it is
\r
465 ds->numVerts = numVerts;
\r
466 ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );
\r
467 memcpy( ds->verts, verts, numVerts * sizeof( *ds->verts ) );
\r
471 if ( i == numVerts ) {
\r
472 // create a vertex in the middle to start the fan
\r
476 memset ( &verts[numVerts], 0, sizeof( verts[numVerts] ) );
\r
477 for ( i = 0 ; i < numVerts ; i++ ) {
\r
478 for ( j = 0 ; j < 10 ; j++ ) {
\r
479 verts[numVerts].xyz[j] += verts[i].xyz[j];
\r
482 for ( j = 0 ; j < 10 ; j++ ) {
\r
483 verts[numVerts].xyz[j] /= numVerts;
\r
490 // just rotate the vertexes
\r
495 ds->numVerts = numVerts;
\r
496 ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );
\r
498 for ( j = 0 ; j < ds->numVerts ; j++ ) {
\r
499 ds->verts[j] = verts[ ( j + i ) % ds->numVerts ];
\r
508 FixBrokenSurface() - ydnar
\r
509 removes nearly coincident verts from a planar winding surface
\r
510 returns qfalse if the surface is broken
\r
513 extern void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out );
\r
515 #define DEGENERATE_EPSILON 0.1
\r
519 qboolean FixBrokenSurface( mapDrawSurface_t *ds )
\r
521 qboolean valid = qtrue;
\r
522 bspDrawVert_t *dv1, *dv2, avg;
\r
530 if( ds->type != SURFACE_FACE )
\r
533 /* check all verts */
\r
534 for( i = 0; i < ds->numVerts; i++ )
\r
536 /* don't remove points if winding is a triangle */
\r
537 if( ds->numVerts == 3 )
\r
541 dv1 = &ds->verts[ i ];
\r
542 dv2 = &ds->verts[ (i + 1) % ds->numVerts ];
\r
544 /* degenerate edge? */
\r
545 VectorSubtract( dv1->xyz, dv2->xyz, avg.xyz );
\r
546 dist = VectorLength( avg.xyz );
\r
547 if( dist < DEGENERATE_EPSILON )
\r
550 Sys_FPrintf( SYS_VRB, "WARNING: Degenerate T-junction edge found, fixing...\n" );
\r
552 /* create an average drawvert */
\r
553 /* ydnar 2002-01-26: added nearest-integer welding preference */
\r
554 SnapWeldVector( dv1->xyz, dv2->xyz, avg.xyz );
\r
555 VectorAdd( dv1->normal, dv2->normal, avg.normal );
\r
556 VectorNormalize( avg.normal, avg.normal );
\r
557 avg.st[ 0 ] = (dv1->st[ 0 ] + dv2->st[ 0 ]) * 0.5f;
\r
558 avg.st[ 1 ] = (dv1->st[ 1 ] + dv2->st[ 1 ]) * 0.5f;
\r
560 /* lightmap st/colors */
\r
561 for( k = 0; k < MAX_LIGHTMAPS; k++ )
\r
563 avg.lightmap[ k ][ 0 ] = (dv1->lightmap[ k ][ 0 ] + dv2->lightmap[ k ][ 0 ]) * 0.5f;
\r
564 avg.lightmap[ k ][ 1 ] = (dv1->lightmap[ k ][ 1 ] + dv2->lightmap[ k ][ 1 ]) * 0.5f;
\r
565 for( j = 0; j < 4; j++ )
\r
566 avg.color[ k ][ j ] = (int) (dv1->color[ k ][ j ] + dv2->color[ k ][ j ]) >> 1;
\r
569 /* ydnar: der... */
\r
570 memcpy( dv1, &avg, sizeof( avg ) );
\r
572 /* move the remaining verts */
\r
573 for( k = i + 2; k < ds->numVerts; k++ )
\r
576 dv1 = &ds->verts[ k ];
\r
577 dv2 = &ds->verts[ k - 1 ];
\r
580 memcpy( dv2, dv1, sizeof( bspDrawVert_t ) );
\r
586 /* one last check and return */
\r
587 if( ds->numVerts < 3 )
\r
605 int EdgeCompare( const void *elem1, const void *elem2 ) {
\r
608 d1 = ((originalEdge_t *)elem1)->length;
\r
609 d2 = ((originalEdge_t *)elem2)->length;
\r
624 call after the surface list has been pruned
\r
627 void FixTJunctions( entity_t *ent )
\r
630 mapDrawSurface_t *ds;
\r
632 int axialEdgeLines;
\r
636 /* meta mode has its own t-junction code (currently not as good as this code) */
\r
641 Sys_FPrintf( SYS_VRB, "--- FixTJunctions ---\n" );
\r
643 numOriginalEdges = 0;
\r
645 // add all the edges
\r
646 // this actually creates axial edges, but it
\r
647 // only creates originalEdge_t structures
\r
648 // for non-axial edges
\r
649 for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ )
\r
651 /* get surface and early out if possible */
\r
652 ds = &mapDrawSurfs[ i ];
\r
653 si = ds->shaderInfo;
\r
654 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc || ds->numVerts == 0 )
\r
657 /* ydnar: gs mods: handle the various types of surfaces */
\r
660 /* handle brush faces */
\r
662 AddSurfaceEdges( ds );
\r
665 /* handle patches */
\r
666 case SURFACE_PATCH:
\r
667 AddPatchEdges( ds );
\r
670 /* fixme: make triangle surfaces t-junction */
\r
676 axialEdgeLines = numEdgeLines;
\r
678 // sort the non-axial edges by length
\r
679 qsort( originalEdges, numOriginalEdges, sizeof(originalEdges[0]), EdgeCompare );
\r
681 // add the non-axial edges, longest first
\r
682 // this gives the most accurate edge description
\r
683 for ( i = 0 ; i < numOriginalEdges ; i++ ) {
\r
684 e = &originalEdges[i];
\r
685 e->dv[ 0 ]->lightmap[ 0 ][ 0 ] = AddEdge( e->dv[ 0 ]->xyz, e->dv[ 1 ]->xyz, qtrue );
\r
688 Sys_FPrintf( SYS_VRB, "%9d axial edge lines\n", axialEdgeLines );
\r
689 Sys_FPrintf( SYS_VRB, "%9d non-axial edge lines\n", numEdgeLines - axialEdgeLines );
\r
690 Sys_FPrintf( SYS_VRB, "%9d degenerate edges\n", c_degenerateEdges );
\r
692 // insert any needed vertexes
\r
693 for( i = ent->firstDrawSurf; i < numMapDrawSurfs ; i++ )
\r
695 /* get surface and early out if possible */
\r
696 ds = &mapDrawSurfs[ i ];
\r
697 si = ds->shaderInfo;
\r
698 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc || ds->numVerts == 0 || ds->type != SURFACE_FACE )
\r
701 /* ydnar: gs mods: handle the various types of surfaces */
\r
704 /* handle brush faces */
\r
706 FixSurfaceJunctions( ds );
\r
707 if( FixBrokenSurface( ds ) == qfalse )
\r
710 ClearSurface( ds );
\r
714 /* fixme: t-junction triangle models and patches */
\r
720 /* emit some statistics */
\r
721 Sys_FPrintf( SYS_VRB, "%9d verts added for T-junctions\n", c_addedVerts );
\r
722 Sys_FPrintf( SYS_VRB, "%9d total verts\n", c_totalVerts );
\r
723 Sys_FPrintf( SYS_VRB, "%9d naturally ordered\n", c_natural );
\r
724 Sys_FPrintf( SYS_VRB, "%9d rotated orders\n", c_rotate );
\r
725 Sys_FPrintf( SYS_VRB, "%9d can't order\n", c_cant );
\r
726 Sys_FPrintf( SYS_VRB, "%9d broken (degenerate) surfaces removed\n", c_broken );
\r