1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 ----------------------------------------------------------------------------------
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
27 ------------------------------------------------------------------------------- */
42 typedef struct edgePoint_s {
45 struct edgePoint_s *prev, *next;
48 typedef struct edgeLine_s {
58 // unused element of doubly linked list
67 originalEdge_t *originalEdges = NULL;
69 int allocatedOriginalEdges = 0;
71 edgeLine_t *edgeLines = NULL;
73 int allocatedEdgeLines = 0;
75 int c_degenerateEdges;
79 int c_natural, c_rotate, c_cant;
81 // these should be whatever epsilon we actually expect,
82 // plus SNAP_INT_TO_FLOAT
83 #define LINE_POSITION_EPSILON 0.25
84 #define POINT_ON_LINE_EPSILON 0.25
91 void InsertPointOnEdge( vec3_t v, edgeLine_t *e ) {
94 edgePoint_t *p, *scan;
96 VectorSubtract( v, e->origin, delta );
97 d = DotProduct( delta, e->dir );
99 p = safe_malloc( sizeof( edgePoint_t ) );
101 VectorCopy( v, p->xyz );
103 if ( e->chain->next == e->chain ) {
104 e->chain->next = e->chain->prev = p;
105 p->next = p->prev = e->chain;
109 scan = e->chain->next;
110 for ( ; scan != e->chain ; scan = scan->next ) {
111 d = p->intercept - scan->intercept;
112 if ( d > -LINE_POSITION_EPSILON && d < LINE_POSITION_EPSILON ) {
114 return; // the point is already set
117 if ( p->intercept < scan->intercept ) {
119 p->prev = scan->prev;
121 scan->prev->next = p;
128 p->prev = scan->prev;
130 scan->prev->next = p;
140 int AddEdge( vec3_t v1, vec3_t v2, qboolean createNonAxial ) {
146 VectorSubtract( v2, v1, dir );
147 d = VectorNormalize( dir, dir );
149 // if we added a 0 length vector, it would make degenerate planes
154 if ( !createNonAxial ) {
155 if ( fabs( dir[0] + dir[1] + dir[2] ) != 1.0 ) {
156 AUTOEXPAND_BY_REALLOC( originalEdges, numOriginalEdges, allocatedOriginalEdges, 1024 );
157 originalEdges[ numOriginalEdges ].dv[0] = (bspDrawVert_t *)v1;
158 originalEdges[ numOriginalEdges ].dv[1] = (bspDrawVert_t *)v2;
159 originalEdges[ numOriginalEdges ].length = d;
165 for ( i = 0 ; i < numEdgeLines ; i++ ) {
168 d = DotProduct( v1, e->normal1 ) - e->dist1;
169 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
172 d = DotProduct( v1, e->normal2 ) - e->dist2;
173 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
177 d = DotProduct( v2, e->normal1 ) - e->dist1;
178 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
181 d = DotProduct( v2, e->normal2 ) - e->dist2;
182 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
187 InsertPointOnEdge( v1, e );
188 InsertPointOnEdge( v2, e );
193 AUTOEXPAND_BY_REALLOC( edgeLines, numEdgeLines, allocatedEdgeLines, 1024 );
195 e = &edgeLines[ numEdgeLines ];
198 e->chain = safe_malloc( sizeof( edgePoint_t ) );
199 e->chain->next = e->chain->prev = e->chain;
201 VectorCopy( v1, e->origin );
202 VectorCopy( dir, e->dir );
204 MakeNormalVectors( e->dir, e->normal1, e->normal2 );
205 e->dist1 = DotProduct( e->origin, e->normal1 );
206 e->dist2 = DotProduct( e->origin, e->normal2 );
208 InsertPointOnEdge( v1, e );
209 InsertPointOnEdge( v2, e );
211 return numEdgeLines - 1;
218 adds a surface's edges
221 void AddSurfaceEdges( mapDrawSurface_t *ds ){
225 for ( i = 0; i < ds->numVerts; i++ )
227 /* save the edge number in the lightmap field so we don't need to look it up again */
228 ds->verts[i].lightmap[ 0 ][ 0 ] =
229 AddEdge( ds->verts[ i ].xyz, ds->verts[ ( i + 1 ) % ds->numVerts ].xyz, qfalse );
237 determines if an edge is colinear
240 qboolean ColinearEdge( vec3_t v1, vec3_t v2, vec3_t v3 ){
241 vec3_t midpoint, dir, offset, on;
244 VectorSubtract( v2, v1, midpoint );
245 VectorSubtract( v3, v1, dir );
246 d = VectorNormalize( dir, dir );
248 return qfalse; // degenerate
251 d = DotProduct( midpoint, dir );
252 VectorScale( dir, d, on );
253 VectorSubtract( midpoint, on, offset );
254 d = VectorLength( offset );
269 Add colinear border edges, which will fix some classes of patch to
273 void AddPatchEdges( mapDrawSurface_t *ds ) {
277 for ( i = 0 ; i < ds->patchWidth - 2; i += 2 ) {
278 v1 = ds->verts[ i ].xyz;
279 v2 = ds->verts[ i + 1 ].xyz;
280 v3 = ds->verts[ i + 2 ].xyz;
282 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
283 if ( ColinearEdge( v1, v2, v3 ) ) {
284 AddEdge( v1, v3, qfalse );
287 v1 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i ].xyz;
288 v2 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 1 ].xyz;
289 v3 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 2 ].xyz;
291 // if v2 is on the v1 to v3 line, add an edge from v1 to v3
292 if ( ColinearEdge( v1, v2, v3 ) ) {
293 AddEdge( v1, v3, qfalse );
297 for ( i = 0 ; i < ds->patchHeight - 2 ; i += 2 ) {
298 v1 = ds->verts[ i * ds->patchWidth ].xyz;
299 v2 = ds->verts[ ( i + 1 ) * ds->patchWidth ].xyz;
300 v3 = ds->verts[ ( i + 2 ) * ds->patchWidth ].xyz;
302 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
303 if ( ColinearEdge( v1, v2, v3 ) ) {
304 AddEdge( v1, v3, qfalse );
307 v1 = ds->verts[ ( ds->patchWidth - 1 ) + i * ds->patchWidth ].xyz;
308 v2 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 1 ) * ds->patchWidth ].xyz;
309 v3 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 2 ) * ds->patchWidth ].xyz;
311 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
312 if ( ColinearEdge( v1, v2, v3 ) ) {
313 AddEdge( v1, v3, qfalse );
326 #define MAX_SURFACE_VERTS 256
327 void FixSurfaceJunctions( mapDrawSurface_t *ds ) {
331 int counts[MAX_SURFACE_VERTS];
332 int originals[MAX_SURFACE_VERTS];
333 bspDrawVert_t verts[MAX_SURFACE_VERTS], *v1, *v2;
335 float start, end, frac, c;
338 // zero the verts array, verts are tested to not be null in FindMetaVertex()
339 memset( verts, 0, sizeof( verts ) );
342 for ( i = 0 ; i < ds->numVerts ; i++ )
347 if ( numVerts == MAX_SURFACE_VERTS ) {
348 Error( "MAX_SURFACE_VERTS" );
350 verts[numVerts] = ds->verts[i];
351 originals[numVerts] = i;
354 // check to see if there are any t junctions before the next vert
356 v2 = &ds->verts[ ( i + 1 ) % ds->numVerts ];
358 j = (int)ds->verts[i].lightmap[ 0 ][ 0 ];
360 continue; // degenerate edge
364 VectorSubtract( v1->xyz, e->origin, delta );
365 start = DotProduct( delta, e->dir );
367 VectorSubtract( v2->xyz, e->origin, delta );
368 end = DotProduct( delta, e->dir );
378 for ( ; p != e->chain ; ) {
380 if ( p->intercept > end - ON_EPSILON ) {
385 if ( p->intercept < end + ON_EPSILON ) {
391 ( start < end && p->intercept > start + ON_EPSILON ) ||
392 ( start > end && p->intercept < start - ON_EPSILON ) ) {
394 if ( numVerts == MAX_SURFACE_VERTS ) {
395 Error( "MAX_SURFACE_VERTS" );
398 /* take the exact intercept point */
399 VectorCopy( p->xyz, verts[ numVerts ].xyz );
401 /* interpolate the texture coordinates */
402 frac = ( p->intercept - start ) / ( end - start );
403 for ( j = 0 ; j < 2 ; j++ ) {
404 verts[ numVerts ].st[j] = v1->st[j] +
405 frac * ( v2->st[j] - v1->st[j] );
408 /* copy the normal (FIXME: what about nonplanar surfaces? */
409 VectorCopy( v1->normal, verts[ numVerts ].normal );
411 /* ydnar: interpolate the color */
412 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
414 for ( j = 0; j < 4; j++ )
416 c = (float) v1->color[ k ][ j ] + frac * ( (float) v2->color[ k ][ j ] - (float) v1->color[ k ][ j ] );
417 verts[ numVerts ].color[ k ][ j ] = (byte) ( c < 255.0f ? c : 255 );
422 originals[ numVerts ] = i;
436 c_addedVerts += numVerts - ds->numVerts;
437 c_totalVerts += numVerts;
440 // FIXME: check to see if the entire surface degenerated
443 // rotate the points so that the initial vertex is between
444 // two non-subdivided edges
445 for ( i = 0 ; i < numVerts ; i++ ) {
446 if ( originals[ ( i + 1 ) % numVerts ] == originals[ i ] ) {
449 j = ( i + numVerts - 1 ) % numVerts;
450 k = ( i + numVerts - 2 ) % numVerts;
451 if ( originals[ j ] == originals[ k ] ) {
458 // fine the way it is
461 ds->numVerts = numVerts;
462 ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );
463 memcpy( ds->verts, verts, numVerts * sizeof( *ds->verts ) );
467 if ( i == numVerts ) {
468 // create a vertex in the middle to start the fan
472 memset ( &verts[numVerts], 0, sizeof( verts[numVerts] ) );
473 for ( i = 0 ; i < numVerts ; i++ ) {
474 for ( j = 0 ; j < 10 ; j++ ) {
475 verts[numVerts].xyz[j] += verts[i].xyz[j];
478 for ( j = 0 ; j < 10 ; j++ ) {
479 verts[numVerts].xyz[j] /= numVerts;
487 // just rotate the vertexes
492 ds->numVerts = numVerts;
493 ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );
495 for ( j = 0 ; j < ds->numVerts ; j++ ) {
496 ds->verts[j] = verts[ ( j + i ) % ds->numVerts ];
505 FixBrokenSurface() - ydnar
506 removes nearly coincident verts from a planar winding surface
507 returns qfalse if the surface is broken
510 extern void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out );
512 #define DEGENERATE_EPSILON 0.1
516 qboolean FixBrokenSurface( mapDrawSurface_t *ds ){
517 bspDrawVert_t *dv1, *dv2, avg;
526 if ( ds->type != SURFACE_FACE ) {
530 /* check all verts */
531 for ( i = 0; i < ds->numVerts; i++ )
534 dv1 = &ds->verts[ i ];
535 dv2 = &ds->verts[ ( i + 1 ) % ds->numVerts ];
537 /* degenerate edge? */
538 VectorSubtract( dv1->xyz, dv2->xyz, avg.xyz );
539 dist = VectorLength( avg.xyz );
540 if ( dist < DEGENERATE_EPSILON ) {
541 Sys_FPrintf( SYS_VRB, "WARNING: Degenerate T-junction edge found, fixing...\n" );
543 /* create an average drawvert */
544 /* ydnar 2002-01-26: added nearest-integer welding preference */
545 SnapWeldVector( dv1->xyz, dv2->xyz, avg.xyz );
546 VectorAdd( dv1->normal, dv2->normal, avg.normal );
547 VectorNormalize( avg.normal, avg.normal );
548 avg.st[ 0 ] = ( dv1->st[ 0 ] + dv2->st[ 0 ] ) * 0.5f;
549 avg.st[ 1 ] = ( dv1->st[ 1 ] + dv2->st[ 1 ] ) * 0.5f;
551 /* lightmap st/colors */
552 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
554 avg.lightmap[ k ][ 0 ] = ( dv1->lightmap[ k ][ 0 ] + dv2->lightmap[ k ][ 0 ] ) * 0.5f;
555 avg.lightmap[ k ][ 1 ] = ( dv1->lightmap[ k ][ 1 ] + dv2->lightmap[ k ][ 1 ] ) * 0.5f;
556 for ( j = 0; j < 4; j++ )
557 avg.color[ k ][ j ] = (int) ( dv1->color[ k ][ j ] + dv2->color[ k ][ j ] ) >> 1;
561 memcpy( dv1, &avg, sizeof( avg ) );
563 /* move the remaining verts */
564 for ( k = i + 2; k < ds->numVerts; k++ )
567 dv1 = &ds->verts[ k ];
568 dv2 = &ds->verts[ k - 1 ];
571 memcpy( dv2, dv1, sizeof( bspDrawVert_t ) );
575 /* after welding, we have to consider the same vertex again, as it now has a new neighbor dv2 */
578 /* should ds->numVerts have become 0, then i is now -1. In the next iteration, the loop will abort. */
582 /* one last check and return */
583 return ds->numVerts >= 3;
599 int EdgeCompare( const void *elem1, const void *elem2 ) {
602 d1 = ( (const originalEdge_t *)elem1 )->length;
603 d2 = ( (const originalEdge_t *)elem2 )->length;
618 call after the surface list has been pruned
621 void FixTJunctions( entity_t *ent ){
623 mapDrawSurface_t *ds;
629 /* meta mode has its own t-junction code (currently not as good as this code) */
634 Sys_FPrintf( SYS_VRB, "--- FixTJunctions ---\n" );
636 numOriginalEdges = 0;
639 // this actually creates axial edges, but it
640 // only creates originalEdge_t structures
641 // for non-axial edges
642 for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ )
644 /* get surface and early out if possible */
645 ds = &mapDrawSurfs[ i ];
647 if ( ( si->compileFlags & C_NODRAW ) || si->autosprite || si->notjunc || ds->numVerts == 0 ) {
651 /* ydnar: gs mods: handle the various types of surfaces */
654 /* handle brush faces */
656 AddSurfaceEdges( ds );
664 /* fixme: make triangle surfaces t-junction */
670 axialEdgeLines = numEdgeLines;
672 // sort the non-axial edges by length
673 qsort( originalEdges, numOriginalEdges, sizeof( originalEdges[0] ), EdgeCompare );
675 // add the non-axial edges, longest first
676 // this gives the most accurate edge description
677 for ( i = 0 ; i < numOriginalEdges ; i++ ) {
678 e = &originalEdges[i];
679 dv = e->dv[0]; // e might change during AddEdge
680 dv->lightmap[ 0 ][ 0 ] = AddEdge( e->dv[ 0 ]->xyz, e->dv[ 1 ]->xyz, qtrue );
683 Sys_FPrintf( SYS_VRB, "%9d axial edge lines\n", axialEdgeLines );
684 Sys_FPrintf( SYS_VRB, "%9d non-axial edge lines\n", numEdgeLines - axialEdgeLines );
685 Sys_FPrintf( SYS_VRB, "%9d degenerate edges\n", c_degenerateEdges );
687 // insert any needed vertexes
688 for ( i = ent->firstDrawSurf; i < numMapDrawSurfs ; i++ )
690 /* get surface and early out if possible */
691 ds = &mapDrawSurfs[ i ];
693 if ( ( si->compileFlags & C_NODRAW ) || si->autosprite || si->notjunc || ds->numVerts == 0 || ds->type != SURFACE_FACE ) {
697 /* ydnar: gs mods: handle the various types of surfaces */
700 /* handle brush faces */
702 FixSurfaceJunctions( ds );
703 if ( FixBrokenSurface( ds ) == qfalse ) {
709 /* fixme: t-junction triangle models and patches */
715 /* emit some statistics */
716 Sys_FPrintf( SYS_VRB, "%9d verts added for T-junctions\n", c_addedVerts );
717 Sys_FPrintf( SYS_VRB, "%9d total verts\n", c_totalVerts );
718 Sys_FPrintf( SYS_VRB, "%9d naturally ordered\n", c_natural );
719 Sys_FPrintf( SYS_VRB, "%9d rotated orders\n", c_rotate );
720 Sys_FPrintf( SYS_VRB, "%9d can't order\n", c_cant );
721 Sys_FPrintf( SYS_VRB, "%9d broken (degenerate) surfaces removed\n", c_broken );