+#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 );
+}