tjunction.c File Reference

#include "qbsp.h"

Include dependency graph for tjunction.c:

Go to the source code of this file.

Data Structures
struct	edgeLine_s
struct	edgePoint_s
struct	originalEdge_t
Defines
#define	LINE_POSITION_EPSILON   0.25
#define	MAX_EDGE_LINES   0x10000
#define	MAX_ORIGINAL_EDGES   0x10000
#define	MAX_SURFACE_VERTS   256
#define	POINT_ON_LINE_EPSILON   0.25
Typedefs
typedef edgeLine_s	edgeLine_t
typedef edgePoint_s	edgePoint_t
Functions
int	AddEdge (vec3_t v1, vec3_t v2, qboolean createNonAxial)
void	AddPatchEdges (mapDrawSurface_t *ds)
void	AddSurfaceEdges (mapDrawSurface_t *ds)
qboolean	ColinearEdge (vec3_t v1, vec3_t v2, vec3_t v3)
int	EdgeCompare (const void *elem1, const void *elem2)
void	FixSurfaceJunctions (mapDrawSurface_t *ds)
void	FixTJunctions (entity_t *ent)
void	InsertPointOnEdge (vec3_t v, edgeLine_t *e)
Variables
int	c_addedVerts
int	c_cant
int	c_degenerateEdges
int	c_natural
int	c_rotate
int	c_totalVerts
edgeLine_t	edgeLines [MAX_EDGE_LINES]
int	numEdgeLines
int	numOriginalEdges
originalEdge_t	originalEdges [MAX_ORIGINAL_EDGES]

---

Define Documentation

#define LINE_POSITION_EPSILON   0.25

Definition at line 65 of file tjunction.c. Referenced by InsertPointOnEdge().

#define MAX_EDGE_LINES   0x10000

Definition at line 53 of file tjunction.c.

#define MAX_ORIGINAL_EDGES   0x10000

Definition at line 48 of file tjunction.c.

#define MAX_SURFACE_VERTS   256

Definition at line 304 of file tjunction.c.

#define POINT_ON_LINE_EPSILON   0.25

Definition at line 66 of file tjunction.c. Referenced by AddEdge().

---

Typedef Documentation

typedef struct edgeLine_s edgeLine_t

Referenced by AddEdge(), FixSurfaceJunctions(), and InsertPointOnEdge().

typedef struct edgePoint_s edgePoint_t

Referenced by FixSurfaceJunctions(), and InsertPointOnEdge().

---

Function Documentation

int AddEdge (  vec3_t  v1, vec3_t  v2, qboolean  createNonAxial )

Definition at line 122 of file tjunction.c. References c_degenerateEdges, edgeLine_s::chain, d, edgeLine_s::dir, edgeLine_s::dist1, edgeLine_s::dist2, DotProduct, originalEdge_t::dv, e, edgeLine_t, edgeLines, Error(), fabs(), i, InsertPointOnEdge(), originalEdge_t::length, MakeNormalVectors(), edgePoint_s::next, edgeLine_s::normal1, edgeLine_s::normal2, numEdgeLines, numOriginalEdges, edgeLine_s::origin, originalEdges, POINT_ON_LINE_EPSILON, edgePoint_s::prev, v1, v2, vec3_t, VectorCopy, VectorNormalize(), and VectorSubtract. Referenced by AddPatchEdges(), AddSurfaceEdges(), and FixTJunctions(). { int i; edgeLine_t *e; float d; vec3_t dir; VectorSubtract( v2, v1, dir ); d = VectorNormalize( dir, dir ); if ( d < 0.1 ) { // if we added a 0 length vector, it would make degenerate planes c_degenerateEdges++; return -1; } if ( !createNonAxial ) { if ( fabs( dir[0] + dir[1] + dir[2] ) != 1.0 ) { if ( numOriginalEdges == MAX_ORIGINAL_EDGES ) { Error( "MAX_ORIGINAL_EDGES" ); } originalEdges[ numOriginalEdges ].dv[0] = (drawVert_t *)v1; originalEdges[ numOriginalEdges ].dv[1] = (drawVert_t *)v2; originalEdges[ numOriginalEdges ].length = d; numOriginalEdges++; return -1; } } for ( i = 0 ; i < numEdgeLines ; i++ ) { e = &edgeLines[i]; d = DotProduct( v1, e->normal1 ) - e->dist1; if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) { continue; } d = DotProduct( v1, e->normal2 ) - e->dist2; if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) { continue; } d = DotProduct( v2, e->normal1 ) - e->dist1; if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) { continue; } d = DotProduct( v2, e->normal2 ) - e->dist2; if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) { continue; } // this is the edge InsertPointOnEdge( v1, e ); InsertPointOnEdge( v2, e ); return i; } // create a new edge if ( numEdgeLines >= MAX_EDGE_LINES ) { Error( "MAX_EDGE_LINES" ); } e = &edgeLines[ numEdgeLines ]; numEdgeLines++; e->chain.next = e->chain.prev = &e->chain; VectorCopy( v1, e->origin ); VectorCopy( dir, e->dir ); MakeNormalVectors( e->dir, e->normal1, e->normal2 ); e->dist1 = DotProduct( e->origin, e->normal1 ); e->dist2 = DotProduct( e->origin, e->normal2 ); InsertPointOnEdge( v1, e ); InsertPointOnEdge( v2, e ); return numEdgeLines - 1; }

Here is the call graph for this function:

void AddPatchEdges (  mapDrawSurface_t *  ds  )

Definition at line 251 of file tjunction.c. References AddEdge(), ColinearEdge(), i, mapDrawSurface_t, drawsurf_s::patchHeight, drawsurf_s::patchWidth, qfalse, v1, v2, drawsurf_s::verts, and drawVert_t::xyz. Referenced by FixTJunctions(). { int i; float *v1, *v2, *v3; for ( i = 0 ; i < ds->patchWidth - 2; i+=2 ) { v1 = ds->verts[ i ].xyz; v2 = ds->verts[ i + 1 ].xyz; v3 = ds->verts[ i + 2 ].xyz; // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3 if ( ColinearEdge( v1, v2, v3 ) ) { AddEdge( v1, v3, qfalse ); } v1 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i ].xyz; v2 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 1 ].xyz; v3 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 2 ].xyz; // if v2 is on the v1 to v3 line, add an edge from v1 to v3 if ( ColinearEdge( v1, v2, v3 ) ) { AddEdge( v1, v3, qfalse ); } } for ( i = 0 ; i < ds->patchHeight - 2 ; i+=2 ) { v1 = ds->verts[ i * ds->patchWidth ].xyz; v2 = ds->verts[ ( i + 1 ) * ds->patchWidth ].xyz; v3 = ds->verts[ ( i + 2 ) * ds->patchWidth ].xyz; // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3 if ( ColinearEdge( v1, v2, v3 ) ) { AddEdge( v1, v3, qfalse ); } v1 = ds->verts[ ( ds->patchWidth - 1 ) + i * ds->patchWidth ].xyz; v2 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 1 ) * ds->patchWidth ].xyz; v3 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 2 ) * ds->patchWidth ].xyz; // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3 if ( ColinearEdge( v1, v2, v3 ) ) { AddEdge( v1, v3, qfalse ); } } }

Here is the call graph for this function:

void AddSurfaceEdges (  mapDrawSurface_t *  ds  )

Definition at line 204 of file tjunction.c. References AddEdge(), i, drawVert_t::lightmap, mapDrawSurface_t, drawsurf_s::numVerts, qfalse, drawsurf_s::verts, and drawVert_t::xyz. Referenced by FixTJunctions(). { int i; for ( i = 0 ; i < ds->numVerts ; i++ ) { // save the edge number in the lightmap field // so we don't need to look it up again ds->verts[i].lightmap[0] = AddEdge( ds->verts[i].xyz, ds->verts[(i+1) % ds->numVerts].xyz, qfalse ); } }

Here is the call graph for this function:

qboolean ColinearEdge (  vec3_t  v1, vec3_t  v2, vec3_t  v3 )

Definition at line 220 of file tjunction.c. References d, DotProduct, offset, qboolean, v1, v2, vec3_t, VectorLength(), VectorNormalize(), VectorScale, and VectorSubtract. Referenced by AddPatchEdges(). { vec3_t midpoint, dir, offset, on; float d; VectorSubtract( v2, v1, midpoint ); VectorSubtract( v3, v1, dir ); d = VectorNormalize( dir, dir ); if ( d == 0 ) { return qfalse; // degenerate } d = DotProduct( midpoint, dir ); VectorScale( dir, d, on ); VectorSubtract( midpoint, on, offset ); d = VectorLength ( offset ); if ( d < 0.1 ) { return qtrue; } return qfalse; }

Here is the call graph for this function:

int EdgeCompare (  const void *  elem1, const void *  elem2 )

Definition at line 468 of file tjunction.c. Referenced by FixTJunctions(). { float d1, d2; d1 = ((originalEdge_t *)elem1)->length; d2 = ((originalEdge_t *)elem2)->length; if ( d1 < d2 ) { return -1; } if ( d2 > d1 ) { return 1; } return 0; }

void FixSurfaceJunctions (  mapDrawSurface_t *  ds  )

Definition at line 305 of file tjunction.c. References c_addedVerts, c_cant, c_natural, c_rotate, c_totalVerts, edgeLine_s::chain, edgeLine_s::dir, DotProduct, e, edgeLine_t, edgeLines, edgePoint_t, Error(), i, edgePoint_s::intercept, j, k, drawVert_t::lightmap, malloc(), mapDrawSurface_t, memcpy(), edgePoint_s::next, drawVert_t::normal, drawsurf_s::numVerts, edgeLine_s::origin, p, edgePoint_s::prev, drawVert_t::st, v1, v2, vec3_t, VectorCopy, VectorSubtract, drawsurf_s::verts, edgePoint_s::xyz, and drawVert_t::xyz. Referenced by FixTJunctions(). { int i, j, k; edgeLine_t *e; edgePoint_t *p; int originalVerts; int counts[MAX_SURFACE_VERTS]; int originals[MAX_SURFACE_VERTS]; int firstVert[MAX_SURFACE_VERTS]; drawVert_t verts[MAX_SURFACE_VERTS], *v1, *v2; int numVerts; float start, end, frac; vec3_t delta; originalVerts = ds->numVerts; numVerts = 0; for ( i = 0 ; i < ds->numVerts ; i++ ) { counts[i] = 0; firstVert[i] = numVerts; // copy first vert if ( numVerts == MAX_SURFACE_VERTS ) { Error( "MAX_SURFACE_VERTS" ); } verts[numVerts] = ds->verts[i]; originals[numVerts] = i; numVerts++; // check to see if there are any t junctions before the next vert v1 = &ds->verts[i]; v2 = &ds->verts[ (i+1) % ds->numVerts ]; j = (int)ds->verts[i].lightmap[0]; if ( j == -1 ) { continue; // degenerate edge } e = &edgeLines[ j ]; VectorSubtract( v1->xyz, e->origin, delta ); start = DotProduct( delta, e->dir ); VectorSubtract( v2->xyz, e->origin, delta ); end = DotProduct( delta, e->dir ); if ( start < end ) { p = e->chain.next; } else { p = e->chain.prev; } for ( ; p != &e->chain ; ) { if ( start < end ) { if ( p->intercept > end - ON_EPSILON ) { break; } } else { if ( p->intercept < end + ON_EPSILON ) { break; } } if ( ( start < end && p->intercept > start + ON_EPSILON ) || ( start > end && p->intercept < start - ON_EPSILON ) ) { // insert this point if ( numVerts == MAX_SURFACE_VERTS ) { Error( "MAX_SURFACE_VERTS" ); } // take the exact intercept point VectorCopy( p->xyz, verts[ numVerts ].xyz ); // copy the normal VectorCopy( v1->normal, verts[ numVerts ].normal ); // interpolate the texture coordinates frac = ( p->intercept - start ) / ( end - start ); for ( j = 0 ; j < 2 ; j++ ) { verts[ numVerts ].st[j] = v1->st[j] + frac * ( v2->st[j] - v1->st[j] ); } originals[numVerts] = i; numVerts++; counts[i]++; } if ( start < end ) { p = p->next; } else { p = p->prev; } } } c_addedVerts += numVerts - ds->numVerts; c_totalVerts += numVerts; // FIXME: check to see if the entire surface degenerated // after snapping // rotate the points so that the initial vertex is between // two non-subdivided edges for ( i = 0 ; i < numVerts ; i++ ) { if ( originals[ (i+1) % numVerts ] == originals[ i ] ) { continue; } j = (i + numVerts - 1 ) % numVerts; k = (i + numVerts - 2 ) % numVerts; if ( originals[ j ] == originals[ k ] ) { continue; } break; } if ( i == 0 ) { // fine the way it is c_natural++; ds->numVerts = numVerts; ds->verts = malloc( numVerts * sizeof( *ds->verts ) ); memcpy( ds->verts, verts, numVerts * sizeof( *ds->verts ) ); return; } if ( i == numVerts ) { // create a vertex in the middle to start the fan c_cant++; /* memset ( &verts[numVerts], 0, sizeof( verts[numVerts] ) ); for ( i = 0 ; i < numVerts ; i++ ) { for ( j = 0 ; j < 10 ; j++ ) { verts[numVerts].xyz[j] += verts[i].xyz[j]; } } for ( j = 0 ; j < 10 ; j++ ) { verts[numVerts].xyz[j] /= numVerts; } i = numVerts; numVerts++; */ } else { // just rotate the vertexes c_rotate++; } ds->numVerts = numVerts; ds->verts = malloc( numVerts * sizeof( *ds->verts ) ); for ( j = 0 ; j < ds->numVerts ; j++ ) { ds->verts[j] = verts[ ( j + i ) % ds->numVerts ]; } }

Here is the call graph for this function:

void FixTJunctions (  entity_t *  ent  )

Definition at line 491 of file tjunction.c. References AddEdge(), AddPatchEdges(), AddSurfaceEdges(), shaderInfo_s::autosprite, c_addedVerts, c_cant, c_degenerateEdges, c_natural, c_rotate, c_totalVerts, originalEdge_t::dv, e, EdgeCompare(), entity_t::firstDrawSurf, FixSurfaceJunctions(), i, drawVert_t::lightmap, mapDrawSurface_t, mapDrawSurfs, drawsurf_s::miscModel, shaderInfo_s::notjunc, numEdgeLines, numOriginalEdges, originalEdges, drawsurf_s::patch, qprintf(), qsort(), qtrue, drawsurf_s::shaderInfo, and drawVert_t::xyz. Referenced by ProcessSubModel(), and ProcessWorldModel(). { int i; mapDrawSurface_t *ds; int axialEdgeLines; originalEdge_t *e; qprintf("----- FixTJunctions -----\n"); numEdgeLines = 0; numOriginalEdges = 0; // add all the edges // this actually creates axial edges, but it // only creates originalEdge_t structures // for non-axial edges for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) { ds = &mapDrawSurfs[i]; if ( ds->patch ) { AddPatchEdges( ds ); } else if ( ds->shaderInfo->autosprite || ds->shaderInfo->notjunc || ds->miscModel ) { // miscModels don't add tjunctions } else { AddSurfaceEdges( ds ); } } axialEdgeLines = numEdgeLines; // sort the non-axial edges by length qsort( originalEdges, numOriginalEdges, sizeof(originalEdges[0]), EdgeCompare ); // add the non-axial edges, longest first // this gives the most accurate edge description for ( i = 0 ; i < numOriginalEdges ; i++ ) { e = &originalEdges[i]; e->dv[0]->lightmap[0] = AddEdge( e->dv[0]->xyz, e->dv[1]->xyz, qtrue ); } qprintf( "%6i axial edge lines\n", axialEdgeLines ); qprintf( "%6i non-axial edge lines\n", numEdgeLines - axialEdgeLines ); qprintf( "%6i degenerate edges\n", c_degenerateEdges ); // insert any needed vertexes for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) { ds = &mapDrawSurfs[i]; if ( ds->patch ) { continue; } if ( ds->shaderInfo->autosprite || ds->shaderInfo->notjunc || ds->miscModel ) { continue; } FixSurfaceJunctions( ds ); } qprintf( "%6i verts added for tjunctions\n", c_addedVerts ); qprintf( "%6i total verts\n", c_totalVerts ); qprintf( "%6i naturally ordered\n", c_natural ); qprintf( "%6i rotated orders\n", c_rotate ); qprintf( "%6i can't order\n", c_cant ); }

Here is the call graph for this function:

void InsertPointOnEdge (  vec3_t  v, edgeLine_t *  e )

Definition at line 73 of file tjunction.c. References edgeLine_s::chain, d, edgeLine_s::dir, DotProduct, e, edgeLine_t, edgePoint_t, free(), edgePoint_s::intercept, LINE_POSITION_EPSILON, malloc(), edgePoint_s::next, edgeLine_s::origin, p, edgePoint_s::prev, v, vec3_t, VectorCopy, VectorSubtract, and edgePoint_s::xyz. Referenced by AddEdge(). { vec3_t delta; float d; edgePoint_t *p, *scan; VectorSubtract( v, e->origin, delta ); d = DotProduct( delta, e->dir ); p = malloc( sizeof(edgePoint_t) ); p->intercept = d; VectorCopy( v, p->xyz ); if ( e->chain.next == &e->chain ) { e->chain.next = e->chain.prev = p; p->next = p->prev = &e->chain; return; } scan = e->chain.next; for ( ; scan != &e->chain ; scan = scan->next ) { d = p->intercept - scan->intercept; if ( d > -LINE_POSITION_EPSILON && d < LINE_POSITION_EPSILON ) { free( p ); return; // the point is already set } if ( p->intercept < scan->intercept ) { // insert here p->prev = scan->prev; p->next = scan; scan->prev->next = p; scan->prev = p; return; } } // add at the end p->prev = scan->prev; p->next = scan; scan->prev->next = p; scan->prev = p; }

Here is the call graph for this function:

---

Variable Documentation

int c_addedVerts

Definition at line 58 of file tjunction.c. Referenced by FixSurfaceJunctions(), and FixTJunctions().

int c_cant

Definition at line 61 of file tjunction.c. Referenced by FixSurfaceJunctions(), and FixTJunctions().

int c_degenerateEdges

Definition at line 57 of file tjunction.c. Referenced by AddEdge(), and FixTJunctions().

int c_natural

Definition at line 61 of file tjunction.c. Referenced by FixSurfaceJunctions(), and FixTJunctions().

int c_rotate

Definition at line 61 of file tjunction.c. Referenced by FixSurfaceJunctions(), and FixTJunctions().

int c_totalVerts

Definition at line 59 of file tjunction.c. Referenced by FixSurfaceJunctions(), and FixTJunctions().

edgeLine_t edgeLines[MAX_EDGE_LINES]

Definition at line 54 of file tjunction.c. Referenced by AddEdge(), and FixSurfaceJunctions().

int numEdgeLines

Definition at line 55 of file tjunction.c. Referenced by AddEdge(), and FixTJunctions().

int numOriginalEdges

Definition at line 50 of file tjunction.c. Referenced by AddEdge(), and FixTJunctions().

originalEdge_t originalEdges[MAX_ORIGINAL_EDGES]

Definition at line 49 of file tjunction.c. Referenced by AddEdge(), and FixTJunctions().

---