{
int i;
bspDrawVert_t *v, *temp;
-
+
/* try to find an existing drawvert */
for( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
ClassifySurfaces( 1, ds );
}
+#define TINY_AREA 1.0f
+#define MAXAREA_MAXTRIES 8
+int MaxAreaIndexes(bspDrawVert_t *vert, int cnt, int *indexes)
+{
+ int r, s, t, bestR = 0, bestS = 1, bestT = 2;
+ int i, j, try;
+ double A, bestA = -1, V, bestV = -1;
+ vec3_t ab, ac, bc, cross;
+ bspDrawVert_t *buf;
+ double shiftWidth;
+
+ if(cnt < 3)
+ return 0;
+
+ /* calculate total area */
+ A = 0;
+ for(i = 1; i+1 < cnt; ++i)
+ {
+ VectorSubtract(vert[i].xyz, vert[0].xyz, ab);
+ VectorSubtract(vert[i+1].xyz, vert[0].xyz, ac);
+ CrossProduct(ab, ac, cross);
+ A += VectorLength(cross);
+ }
+ V = 0;
+ for(i = 0; i < cnt; ++i)
+ {
+ VectorSubtract(vert[(i+1)%cnt].xyz, vert[i].xyz, ab);
+ V += VectorLength(ab);
+ }
+
+ /* calculate shift width from the area sensibly, assuming the polygon
+ * fits about 25% of the screen in both dimensions
+ * we assume 1280x1024
+ * 1 pixel is then about sqrt(A) / (0.25 * screenwidth)
+ * 8 pixels are then about sqrt(A) / (0.25 * 1280) * 8
+ * 8 pixels are then about sqrt(A) * 0.025
+ * */
+ shiftWidth = sqrt(A) * 0.0125;
+ /* 3->1 6->2 12->3 ... */
+ if(A - ceil(log(cnt/1.5) / log(2)) * V * shiftWidth * 2 < 0)
+ {
+ /* printf("Small triangle detected (area %f, circumference %f), adjusting shiftWidth from %f to ", A, V, shiftWidth); */
+ shiftWidth = A / (ceil(log(cnt/1.5) / log(2)) * V * 2);
+ /* printf("%f\n", shiftWidth); */
+ }
+
+ /* find the triangle with highest area */
+ for(r = 0; r+2 < cnt; ++r)
+ for(s = r+1; s+1 < cnt; ++s)
+ for(t = s+1; t < cnt; ++t)
+ {
+ VectorSubtract(vert[s].xyz, vert[r].xyz, ab);
+ VectorSubtract(vert[t].xyz, vert[r].xyz, ac);
+ VectorSubtract(vert[t].xyz, vert[s].xyz, bc);
+ CrossProduct(ab, ac, cross);
+ A = VectorLength(cross);
+
+ V = A - (VectorLength(ab) - VectorLength(ac) - VectorLength(bc)) * shiftWidth;
+ /* value = A - circumference * shiftWidth, i.e. we back out by shiftWidth units from each side, to prevent too acute triangles */
+ /* this kind of simulates "number of shiftWidth*shiftWidth fragments in the triangle not touched by an edge" */
+
+ if(bestA < 0 || V > bestV)
+ {
+ bestA = A;
+ bestV = V;
+ bestR = r;
+ bestS = s;
+ bestT = t;
+ }
+ }
+
+ /*
+ if(bestV < 0)
+ printf("value was REALLY bad\n");
+ */
+
+ for(try = 0; try < MAXAREA_MAXTRIES; ++try)
+ {
+ if(try)
+ {
+ bestR = rand() % cnt;
+ bestS = rand() % cnt;
+ bestT = rand() % cnt;
+ if(bestR == bestS || bestR == bestT || bestS == bestT)
+ continue;
+ // bubblesort inline
+ // abc acb bac bca cab cba
+ if(bestR > bestS)
+ {
+ j = bestR;
+ bestR = bestS;
+ bestS = j;
+ }
+ // abc acb abc bca acb bca
+ if(bestS > bestT)
+ {
+ j = bestS;
+ bestS = bestT;
+ bestT = j;
+ }
+ // abc abc abc bac abc bac
+ if(bestR > bestS)
+ {
+ j = bestR;
+ bestR = bestS;
+ bestS = j;
+ }
+ // abc abc abc abc abc abc
+
+ VectorSubtract(vert[bestS].xyz, vert[bestR].xyz, ab);
+ VectorSubtract(vert[bestT].xyz, vert[bestR].xyz, ac);
+ CrossProduct(ab, ac, cross);
+ bestA = VectorLength(cross);
+ }
+
+ if(bestA < TINY_AREA)
+ /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
+ continue;
+
+ i = 0;
+ indexes[i++] = bestR;
+ indexes[i++] = bestS;
+ indexes[i++] = bestT;
+ /* uses 3 */
+
+ /* identify the other fragments */
+
+ /* full polygon without triangle (bestR,bestS,bestT) = three new polygons:
+ * 1. bestR..bestS
+ * 2. bestS..bestT
+ * 3. bestT..bestR
+ */
+
+ j = MaxAreaIndexes(vert + bestR, bestS - bestR + 1, indexes + i);
+ if(j < 0)
+ continue;
+ j += i;
+ for(; i < j; ++i)
+ indexes[i] += bestR;
+ /* uses 3*(bestS-bestR+1)-6 */
+ j = MaxAreaIndexes(vert + bestS, bestT - bestS + 1, indexes + i);
+ if(j < 0)
+ continue;
+ j += i;
+ for(; i < j; ++i)
+ indexes[i] += bestS;
+ /* uses 3*(bestT-bestS+1)-6 */
+
+ /* can'bestT recurse this one directly... therefore, buffering */
+ if(cnt + bestR - bestT + 1 >= 3)
+ {
+ buf = safe_malloc(sizeof(*vert) * (cnt + bestR - bestT + 1));
+ memcpy(buf, vert + bestT, sizeof(*vert) * (cnt - bestT));
+ memcpy(buf + (cnt - bestT), vert, sizeof(*vert) * (bestR + 1));
+ j = MaxAreaIndexes(buf, cnt + bestR - bestT + 1, indexes + i);
+ if(j < 0)
+ {
+ free(buf);
+ continue;
+ }
+ j += i;
+ for(; i < j; ++i)
+ indexes[i] = (indexes[i] + bestT) % cnt;
+ /* uses 3*(cnt+bestR-bestT+1)-6 */
+ free(buf);
+ }
+
+ /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
+ return i;
+ }
+
+ return -1;
+}
+
+/*
+MaxAreaFaceSurface() - divVerent
+creates a triangle list using max area indexes
+*/
+
+void MaxAreaFaceSurface(mapDrawSurface_t *ds)
+{
+ int n;
+ /* try to early out */
+ if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
+ return;
+
+ /* is this a simple triangle? */
+ if( ds->numVerts == 3 )
+ {
+ ds->numIndexes = 3;
+ ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
+ VectorSet( ds->indexes, 0, 1, 2 );
+ numMaxAreaSurfaces++;
+ return;
+ }
+
+ /* do it! */
+ ds->numIndexes = 3 * ds->numVerts - 6;
+ ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
+ n = MaxAreaIndexes(ds->verts, ds->numVerts, ds->indexes);
+ if(n < 0)
+ {
+ /* whatever we do, it's degenerate */
+ free(ds->indexes);
+ ds->numIndexes = 0;
+ StripFaceSurface(ds);
+ return;
+ }
+ ds->numIndexes = n;
+
+ /* add to count */
+ numMaxAreaSurfaces++;
+
+ /* classify it */
+ ClassifySurfaces( 1, ds );
+}
/*
Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
/* try all possible orderings of the points looking for a non-degenerate strip order */
+ ni = 0;
for( r = 0; r < ds->numVerts; r++ )
{
/* set rotation */
Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
+ Sys_Printf( "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
Sys_Printf( "%9d meta verts\n", numMetaVerts );
Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
{
case SURFACE_FACE:
case SURFACE_DECAL:
- StripFaceSurface( ds );
+ if(maxAreaFaceSurface)
+ MaxAreaFaceSurface( ds );
+ else
+ StripFaceSurface( ds );
SurfaceToMetaTriangles( ds );
break;
Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
+ Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
-/*
-PointTriangleIntersect()
-assuming that all points lie in plane, determine if pt
-is inside the triangle abc
-code originally (c) 2001 softSurfer (www.softsurfer.com)
-*/
-
-#define MIN_OUTSIDE_EPSILON -0.01f
-#define MAX_OUTSIDE_EPSILON 1.01f
-
-static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
-{
- vec3_t u, v, w;
- float uu, uv, vv, wu, wv, d;
-
-
- /* make vectors */
- VectorSubtract( b, a, u );
- VectorSubtract( c, a, v );
- VectorSubtract( pt, a, w );
-
- /* more setup */
- uu = DotProduct( u, u );
- uv = DotProduct( u, v );
- vv = DotProduct( v, v );
- wu = DotProduct( w, u );
- wv = DotProduct( w, v );
- d = uv * uv - uu * vv;
-
- /* calculate barycentric coordinates */
- bary[ 1 ] = (uv * wv - vv * wu) / d;
- if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
- return qfalse;
- bary[ 2 ] = (uv * wv - uu * wv) / d;
- if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
- return qfalse;
- bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
-
- /* point is in triangle */
- return qtrue;
-}
-
-
-
/*
CreateEdge()
sets up an edge structure from a plane and 2 points that the edge ab falls lies in
/* get vert */
VectorCopy( metaVerts[ j ].xyz, pt );
- /* debug code: darken verts */
- if( i == 0 )
- VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
-
/* determine if point lies in the triangle's plane */
dist = DotProduct( pt, plane ) - plane[ 3 ];
if( fabs( dist ) > TJ_PLANE_EPSILON )
amount = dist / edges[ k ].length;
#endif
- /* debug code: brighten this point */
- //% metaVerts[ j ].color[ 0 ][ 0 ] += 5;
- //% metaVerts[ j ].color[ 0 ][ 1 ] += 4;
- VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
- VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
-
-
/* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
a = &metaVerts[ tri->indexes[ k % 3 ] ];
b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
{
int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
float lmMax;
- vec3_t mins, maxs, p;
- qboolean inTexRange, es, et;
+ vec3_t mins, maxs;
+ qboolean inTexRange;
mapDrawSurface_t old;
}
#if MAX_BBOX_DISTANCE > 0
- VectorCopy( mins, ds->mins );
- VectorCopy( maxs, ds->maxs );
+ VectorCopy( ds->mins, mins );
+ VectorCopy( ds->maxs, maxs );
mins[0] -= MAX_BBOX_DISTANCE;
mins[1] -= MAX_BBOX_DISTANCE;
mins[2] -= MAX_BBOX_DISTANCE;
maxs[2] += MAX_BBOX_DISTANCE;
#define CHECK_1D(mins, v, maxs) ((mins) <= (v) && (v) <= (maxs))
#define CHECK_3D(mins, v, maxs) (CHECK_1D((mins)[0], (v)[0], (maxs)[0]) && CHECK_1D((mins)[1], (v)[1], (maxs)[1]) && CHECK_1D((mins)[2], (v)[2], (maxs)[2]))
- VectorCopy(p, metaVerts[ tri->indexes[ 0 ] ].xyz);
+ VectorCopy(metaVerts[ tri->indexes[ 0 ] ].xyz, p);
if(!CHECK_3D(mins, p, maxs))
{
- VectorCopy(p, metaVerts[ tri->indexes[ 1 ] ].xyz);
+ VectorCopy(metaVerts[ tri->indexes[ 1 ] ].xyz, p);
if(!CHECK_3D(mins, p, maxs))
{
- VectorCopy(p, metaVerts[ tri->indexes[ 2 ] ].xyz);
+ VectorCopy(metaVerts[ tri->indexes[ 2 ] ].xyz, p);
if(!CHECK_3D(mins, p, maxs))
return 0;
}
oldTexRange[ 1 ] = ds->texRange[ 1 ];
inTexRange = CalcSurfaceTextureRange( ds );
- es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
- et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
-
if( inTexRange == qfalse && ds->numIndexes > 0 )
{
memcpy( ds, &old, sizeof( *ds ) );
/* shader first */
- if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
+ if( ((const metaTriangle_t*) a)->si < ((const metaTriangle_t*) b)->si )
return 1;
- else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
+ else if( ((const metaTriangle_t*) a)->si > ((const metaTriangle_t*) b)->si )
return -1;
/* then fog */
- else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
+ else if( ((const metaTriangle_t*) a)->fogNum < ((const metaTriangle_t*) b)->fogNum )
return 1;
- else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
+ else if( ((const metaTriangle_t*) a)->fogNum > ((const metaTriangle_t*) b)->fogNum )
return -1;
/* then plane */
#if 0
- else if( npDegrees == 0.0f && ((metaTriangle_t*) a)->si->nonplanar == qfalse &&
- ((metaTriangle_t*) a)->planeNum >= 0 && ((metaTriangle_t*) a)->planeNum >= 0 )
+ else if( npDegrees == 0.0f && ((const metaTriangle_t*) a)->si->nonplanar == qfalse &&
+ ((const metaTriangle_t*) a)->planeNum >= 0 && ((const metaTriangle_t*) a)->planeNum >= 0 )
{
- if( ((metaTriangle_t*) a)->plane[ 3 ] < ((metaTriangle_t*) b)->plane[ 3 ] )
+ if( ((const metaTriangle_t*) a)->plane[ 3 ] < ((const metaTriangle_t*) b)->plane[ 3 ] )
return 1;
- else if( ((metaTriangle_t*) a)->plane[ 3 ] > ((metaTriangle_t*) b)->plane[ 3 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 3 ] > ((const metaTriangle_t*) b)->plane[ 3 ] )
return -1;
- else if( ((metaTriangle_t*) a)->plane[ 0 ] < ((metaTriangle_t*) b)->plane[ 0 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 0 ] < ((const metaTriangle_t*) b)->plane[ 0 ] )
return 1;
- else if( ((metaTriangle_t*) a)->plane[ 0 ] > ((metaTriangle_t*) b)->plane[ 0 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 0 ] > ((const metaTriangle_t*) b)->plane[ 0 ] )
return -1;
- else if( ((metaTriangle_t*) a)->plane[ 1 ] < ((metaTriangle_t*) b)->plane[ 1 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 1 ] < ((const metaTriangle_t*) b)->plane[ 1 ] )
return 1;
- else if( ((metaTriangle_t*) a)->plane[ 1 ] > ((metaTriangle_t*) b)->plane[ 1 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 1 ] > ((const metaTriangle_t*) b)->plane[ 1 ] )
return -1;
- else if( ((metaTriangle_t*) a)->plane[ 2 ] < ((metaTriangle_t*) b)->plane[ 2 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 2 ] < ((const metaTriangle_t*) b)->plane[ 2 ] )
return 1;
- else if( ((metaTriangle_t*) a)->plane[ 2 ] > ((metaTriangle_t*) b)->plane[ 2 ] )
+ else if( ((const metaTriangle_t*) a)->plane[ 2 ] > ((const metaTriangle_t*) b)->plane[ 2 ] )
return -1;
}
#endif
VectorSet( bMins, 999999, 999999, 999999 );
for( i = 0; i < 3; i++ )
{
- av = ((metaTriangle_t*) a)->indexes[ i ];
- bv = ((metaTriangle_t*) b)->indexes[ i ];
+ av = ((const metaTriangle_t*) a)->indexes[ i ];
+ bv = ((const metaTriangle_t*) b)->indexes[ i ];
for( j = 0; j < 3; j++ )
{
if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
projects / xonotic / netradiant.git / blobdiff