}
#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;
+ int i, j, try;
double A, bestA = -1, V, bestV = -1;
vec3_t ab, ac, bc, cross;
bspDrawVert_t *buf;
}
}
- if(bestA < TINY_AREA)
- /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
- return 0;
+ /*
+ if(bestV < 0)
+ printf("value was REALLY bad\n");
+ */
- 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 = i + MaxAreaIndexes(vert + bestR, bestS - bestR + 1, indexes + i);
- for(; i < j; ++i)
- indexes[i] += bestR;
- /* uses 3*(bestS-bestR+1)-6 */
- j = i + MaxAreaIndexes(vert + bestS, bestT - bestS + 1, indexes + 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)
+ for(try = 0; try < MAXAREA_MAXTRIES; ++try)
{
- 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 = i + MaxAreaIndexes(buf, cnt + bestR - bestT + 1, indexes + i);
+ 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] = (indexes[i] + bestT) % cnt;
- /* uses 3*(cnt+bestR-bestT+1)-6 */
- free(buf);
- }
+ 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. */
+ /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
+ return i;
+ }
- return i;
+ return -1;
}
/*
void MaxAreaFaceSurface(mapDrawSurface_t *ds)
{
+ int n;
/* try to early out */
if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
return;
/* do it! */
ds->numIndexes = 3 * ds->numVerts - 6;
ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
- ds->numIndexes = MaxAreaIndexes(ds->verts, ds->numVerts, ds->indexes);
+ 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++;
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 */
-/*
-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;
+ vec3_t mins, maxs;
qboolean inTexRange, es, et;
mapDrawSurface_t old;
/* 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