contrib/gtkgensurf/dec.cpp

   1 /*
   2    GenSurf plugin for GtkRadiant
   3    Copyright (C) 2001 David Hyde, Loki software and qeradiant.com
   4
   5    This library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    This library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with this library; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  */
  19
  20 #define SINGLE
  21 #ifdef SINGLE
  22 #define REAL float
  23 #else /* not SINGLE */
  24 #define REAL double
  25 #endif /* not SINGLE */
  26
  27 #include <stdlib.h>
  28 #include <stdio.h>
  29 #include <math.h>
  30 #include "gensurf.h"
  31 #include "triangle.h"
  32
  33 typedef struct {
  34     float error;
  35     int node;
  36 } TRITABLE;
  37
  38 double dh, dv;
  39 int NVP1;
  40
  41 #define Absolute(a)  ( ( a ) >= 0.0 ? ( a ) : -( a ) )
  42
  43 void MakeDecimatedMap(int *NumNodes, int *NumTris, NODE **pNode, TRI **pTri)
  44 {
  45     int compare(TRITABLE *, TRITABLE *);
  46     int Bisect(NODE *, int, int, int);
  47     void CalcAngles(NODE *, int *, float *);
  48     void EdgeOnSide(int *, int *, int *);
  49     int tricall(int, NODE *, int *, TRI **, TRI **, const char *);
  50     int CheckBorders(int *, int, NODE *, int *, TRI **);
  51
  52     float biggesterror;
  53     int i, j, N;
  54     int j0, j1, j2;
  55     int NumNodesToSave;
  56     int NumNodesUsed;
  57     NODE *Node;
  58     TRI *Tri;
  59     TRITABLE *TriTable;
  60
  61     if (Decimate <= 0) {
  62         return;
  63     }
  64     /*
  65        ghCursorCurrent = LoadCursor(NULL,IDC_WAIT);
  66        SetCursor(ghCursorCurrent);
  67      */
  68     dh = (Hur - Hll) / NH;
  69     dv = (Vur - Vll) / NV;
  70     NVP1 = NV + 1;
  71
  72     NumNodes[0] = (NH + 1) * (NVP1);
  73     *pNode = (NODE *) malloc(NumNodes[0] * sizeof(NODE));
  74     Node = *pNode;
  75     memset(Node, 0, NumNodes[0] * sizeof(NODE));
  76
  77     // Copy [NH][NV] vertex array to our working node array
  78     for (i = 0, N = 0; i <= NH; i++) {
  79         for (j = 0; j <= NV; j++, N++) {
  80             Node[N].p[0] = (float) xyz[i][j].p[0];
  81             Node[N].p[1] = (float) xyz[i][j].p[1];
  82             Node[N].p[2] = (float) xyz[i][j].p[2];
  83             Node[N].fixed = xyz[i][j].fixed;
  84         }
  85     }
  86     // Start things off with the corner values
  87     Node[0].used = 1;
  88     Node[NV].used = 1;
  89     Node[NH * NVP1].used = 1;
  90     Node[NH * NVP1 + NV].used = 1;
  91     NumNodesUsed = 4;
  92     tricall(NumNodes[0], Node, NumTris, NULL, pTri, "cnzBNPY");
  93     Tri = *pTri;
  94
  95     // Which coordinates are we triangulating on?
  96     switch (Plane) {
  97         case PLANE_XZ0:
  98         case PLANE_XZ1:
  99             j0 = 1;
 100             j1 = 0;
 101             j2 = 2;
 102             break;
 103         case PLANE_YZ0:
 104         case PLANE_YZ1:
 105             j0 = 0;
 106             j1 = 1;
 107             j2 = 2;
 108             break;
 109         default:
 110             j0 = 2;
 111             j1 = 0;
 112             j2 = 1;
 113     }
 114
 115     // TriTable stores the largest error in a triangle and the node where that
 116     // error occurs
 117     TriTable = (TRITABLE *) malloc(NH * NV * 2 * sizeof(TRITABLE));
 118     NumNodesToSave = min(NumNodes[0], (int) (0.01 * (100 - Decimate) * (NumNodes[0] - NumNodesUsed) + NumNodesUsed));
 119
 120     while (NumNodesUsed < NumNodesToSave) {
 121         for (i = 0; i < NumTris[0]; i++) {
 122             Tri[i].flag = 0;
 123         }
 124
 125         // For every node that's not currently used, find what triangle it
 126         // lies on, and the error at this node
 127         for (i = 0, biggesterror = 0; i < NumNodes[0]; i++) {
 128             if (Node[i].used) {
 129                 continue;
 130             }
 131             for (j = 0, Node[i].tri = -1; (j < NumTris[0]) && (Node[i].tri == -1); j++) {
 132                 if (side(Node[i].p[j1], Node[i].p[j2],
 133                          Node[Tri[j].v[0]].p[j1], Node[Tri[j].v[0]].p[j2],
 134                          Node[Tri[j].v[1]].p[j1], Node[Tri[j].v[1]].p[j2]) < 0.) {
 135                     continue;
 136                 }
 137                 if (side(Node[i].p[j1], Node[i].p[j2],
 138                          Node[Tri[j].v[1]].p[j1], Node[Tri[j].v[1]].p[j2],
 139                          Node[Tri[j].v[2]].p[j1], Node[Tri[j].v[2]].p[j2]) < 0.) {
 140                     continue;
 141                 }
 142                 if (side(Node[i].p[j1], Node[i].p[j2],
 143                          Node[Tri[j].v[2]].p[j1], Node[Tri[j].v[2]].p[j2],
 144                          Node[Tri[j].v[0]].p[j1], Node[Tri[j].v[0]].p[j2]) < 0.) {
 145                     continue;
 146                 }
 147                 Node[i].tri = j;
 148             }
 149             if (Node[i].tri < 0) {
 150                 /*
 151                    ghCursorCurrent = ghCursorDefault;
 152                    SetCursor(ghCursorCurrent);
 153                  */
 154                 g_FuncTable.m_pfnMessageBox(g_pRadiantWnd,
 155                                             "Error: Couldn't find the triangle bounding a point.",
 156                                             "Decimation Error", eMB_OK, eMB_ICONWARNING);
 157                 return;
 158             }
 159             if (!Tri[Node[i].tri].flag) {
 160                 PlaneFromPoints(Node[Tri[Node[i].tri].v[0]].p,
 161                                 Node[Tri[Node[i].tri].v[1]].p,
 162                                 Node[Tri[Node[i].tri].v[2]].p,
 163                                 &Tri[Node[i].tri].plane);
 164                 Tri[Node[i].tri].flag = 1;
 165             }
 166             Node[i].error =
 167                     Node[i].p[j0] - (Tri[Node[i].tri].plane.dist -
 168                                      Tri[Node[i].tri].plane.normal[j1] * Node[i].p[j1] -
 169                                      Tri[Node[i].tri].plane.normal[j2] * Node[i].p[j2]) /
 170                                     Tri[Node[i].tri].plane.normal[j0];
 171             biggesterror = max(biggesterror, Absolute(Node[i].error));
 172         }
 173         if (biggesterror == 0) {
 174             NumNodesToSave = NumNodesUsed;
 175         } else {
 176             // For all current triangles, build a list of worst-case nodes
 177             memset(TriTable, 0, NH * NV * 2 * sizeof(TRITABLE));
 178             for (i = 0; i < NumNodes[0]; i++) {
 179                 if (Node[i].used) {
 180                     continue;
 181                 }
 182                 if (Absolute(Node[i].error) > TriTable[Node[i].tri].error) {
 183                     TriTable[Node[i].tri].error = (float) (Absolute(Node[i].error));
 184                     TriTable[Node[i].tri].node = i;
 185                 }
 186             }
 187             qsort((void *) TriTable, (size_t)(NumTris[0]), sizeof(TRITABLE),
 188                   (int (*)(const void *, const void *)) compare);
 189             for (i = 0;
 190                  i < NumTris[0] && NumNodesUsed < NumNodesToSave && TriTable[i].error > 0.5 * biggesterror; i++) {
 191                 if (Node[TriTable[i].node].used) {
 192                     continue;                              // shouldn't happen
 193                 }
 194                 NumNodesUsed++;
 195                 Node[TriTable[i].node].used++;
 196             }
 197             free(Tri);
 198             tricall(NumNodes[0], Node, NumTris, NULL, pTri, "cnzBNPY");
 199             Tri = *pTri;
 200             // Sliver-check along borders. Since borders are often linear, the errors
 201             // along borders will often be zero, so no new points will be added. This
 202             // tends to produce long, thin brushes. For all border triangles, check
 203             // that minimum angle isn't less than SLIVER_ANGLE. If it is, add another
 204             // vertex.
 205             while (CheckBorders(&NumNodesUsed, NumNodes[0], Node, NumTris, pTri) > 0) {
 206             }
 207             Tri = *pTri;
 208         }
 209     }
 210     free(TriTable);
 211     // One last time (because we're pessimistic), check border triangles
 212 //      CheckBorders(&NumNodesUsed,NumNodes[0],Node,NumTris,pTri);
 213 //      Tri = *pTri;
 214
 215     // Check that all fixed points are exact. If not, add them to the mix.
 216     // First check to see if we have any fixed points that aren't already used.
 217     for (i = 0, N = 0; i < NumNodes[0] && !N; i++) {
 218         if (Node[i].used) {
 219             continue;
 220         }
 221         if (Node[i].fixed) {
 222             N++;
 223         }
 224     }
 225     if (N) {
 226         // Zero out the flag member of all triangles, indicating that
 227         // the plane equation has not been found.
 228         for (i = 0; i < NumTris[0]; i++) {
 229             Tri[i].flag = 0;
 230         }
 231
 232         for (i = 0; i < NumNodes[0]; i++) {
 233             if (Node[i].used) {
 234                 continue;
 235             }
 236             if (!Node[i].fixed) {
 237                 continue;
 238             }
 239             Node[i].tri = -1;
 240             for (j = 0; j < NumTris[0] && Node[i].tri == -1; j++) {
 241                 if (side(Node[i].p[j1], Node[i].p[j2],
 242                          Node[Tri[j].v[0]].p[j1], Node[Tri[j].v[0]].p[j2],
 243                          Node[Tri[j].v[1]].p[j1], Node[Tri[j].v[1]].p[j2]) < 0.) {
 244                     continue;
 245                 }
 246                 if (side(Node[i].p[j1], Node[i].p[j2],
 247                          Node[Tri[j].v[1]].p[j1], Node[Tri[j].v[1]].p[j2],
 248                          Node[Tri[j].v[2]].p[j1], Node[Tri[j].v[2]].p[j2]) < 0.) {
 249                     continue;
 250                 }
 251                 if (side(Node[i].p[j1], Node[i].p[j2],
 252                          Node[Tri[j].v[2]].p[j1], Node[Tri[j].v[2]].p[j2],
 253                          Node[Tri[j].v[0]].p[j1], Node[Tri[j].v[0]].p[j2]) < 0.) {
 254                     continue;
 255                 }
 256                 Node[i].tri = j;
 257             }
 258             if (Node[i].tri < 0) {
 259                 /*
 260                    ghCursorCurrent = ghCursorDefault;
 261                    SetCursor(ghCursorCurrent);
 262                  */
 263                 g_FuncTable.m_pfnMessageBox(g_pRadiantWnd,
 264                                             "Error: Couldn't find the triangle bounding a point.",
 265                                             "Decimation Error", eMB_OK, eMB_ICONWARNING);
 266                 return;
 267             }
 268             if (!Tri[Node[i].tri].flag) {
 269                 PlaneFromPoints(Node[Tri[Node[i].tri].v[0]].p,
 270                                 Node[Tri[Node[i].tri].v[1]].p,
 271                                 Node[Tri[Node[i].tri].v[2]].p,
 272                                 &Tri[Node[i].tri].plane);
 273                 Tri[Node[i].tri].flag = 1;
 274             }
 275             Node[i].error =
 276                     Node[i].p[j0] - (Tri[Node[i].tri].plane.dist -
 277                                      Tri[Node[i].tri].plane.normal[j1] * Node[i].p[j1] -
 278                                      Tri[Node[i].tri].plane.normal[j2] * Node[i].p[j2]) /
 279                                     Tri[Node[i].tri].plane.normal[j0];
 280             if (Absolute(Node[i].error) > 0.5) {
 281                 NumNodesUsed++;
 282                 Node[i].used++;
 283                 free(Tri);
 284                 tricall(NumNodes[0], Node, NumTris, NULL, pTri, "cnzBNPY");
 285                 Tri = *pTri;
 286             }
 287         }
 288     }
 289
 290     // Swap node orders for surfaces facing down, north or west so that
 291     // they are counterclockwise when facing the surface
 292
 293     if ((Plane == PLANE_XY1) || (Plane == PLANE_XZ0) || (Plane == PLANE_YZ1)) {
 294         for (i = 0; i < NumTris[0]; i++) {
 295             j = Tri[i].v[1];
 296             Tri[i].v[1] = Tri[i].v[2];
 297             Tri[i].v[2] = j;
 298         }
 299     }
 300
 301     // Store bounding box coords
 302     for (i = 0; i < NumTris[0]; i++) {
 303         Tri[i].min[0] = Node[Tri[i].v[0]].p[0];
 304         Tri[i].min[0] = min(Tri[i].min[0], Node[Tri[i].v[1]].p[0]);
 305         Tri[i].min[0] = min(Tri[i].min[0], Node[Tri[i].v[2]].p[0]);
 306         Tri[i].min[1] = Node[Tri[i].v[0]].p[1];
 307         Tri[i].min[1] = min(Tri[i].min[1], Node[Tri[i].v[1]].p[1]);
 308         Tri[i].min[1] = min(Tri[i].min[1], Node[Tri[i].v[2]].p[1]);
 309         Tri[i].min[2] = Node[Tri[i].v[0]].p[2];
 310         Tri[i].min[2] = min(Tri[i].min[2], Node[Tri[i].v[1]].p[2]);
 311         Tri[i].min[2] = min(Tri[i].min[2], Node[Tri[i].v[2]].p[2]);
 312         Tri[i].max[0] = Node[Tri[i].v[0]].p[0];
 313         Tri[i].max[0] = max(Tri[i].max[0], Node[Tri[i].v[1]].p[0]);
 314         Tri[i].max[0] = max(Tri[i].max[0], Node[Tri[i].v[2]].p[0]);
 315         Tri[i].max[1] = Node[Tri[i].v[0]].p[1];
 316         Tri[i].max[1] = max(Tri[i].max[1], Node[Tri[i].v[1]].p[1]);
 317         Tri[i].max[1] = max(Tri[i].max[1], Node[Tri[i].v[2]].p[1]);
 318         Tri[i].max[2] = Node[Tri[i].v[0]].p[2];
 319         Tri[i].max[2] = max(Tri[i].max[2], Node[Tri[i].v[1]].p[2]);
 320         Tri[i].max[2] = max(Tri[i].max[2], Node[Tri[i].v[2]].p[2]);
 321     }
 322     /*
 323        ghCursorCurrent = ghCursorDefault;
 324        SetCursor(ghCursorCurrent);
 325      */
 326 }
 327 /* end MakeDecimatedMap */
 328
 329 /*****************************************************************************/
 330 /*                                                                           */
 331 /*  tricall Takes an array of nodes, spits out an array of triangles         */
 332 /*                                                                           */
 333 /*****************************************************************************/
 334 int tricall(int NumNodes, NODE *Node, int *NumTris, TRI **inTri, TRI **Tri, const char *Options)
 335 {
 336     struct triangulateio in, out;
 337     int i, N;
 338     int NumUsedNodes;
 339     int *NodeTable;
 340     TRI *ptri;
 341
 342     /* Define input points. */
 343
 344     for (i = 0, NumUsedNodes = 0; i < NumNodes; i++) {
 345         if (Node[i].used) {
 346             NumUsedNodes++;
 347         }
 348     }
 349
 350     memset(&in, 0, sizeof(in));
 351     memset(&out, 0, sizeof(out));
 352
 353     NodeTable = (int *) malloc(NumUsedNodes * sizeof(int));
 354
 355     in.numberofpoints = NumUsedNodes;
 356     in.numberofpointattributes = 0;
 357     in.pointlist = (REAL *) malloc(in.numberofpoints * 2 * sizeof(REAL));
 358     for (i = 0, N = 0; i < NumNodes; i++) {
 359         if (Node[i].used) {
 360             switch (Plane) {
 361                 case PLANE_XZ0:
 362                 case PLANE_XZ1:
 363                     in.pointlist[N * 2] = Node[i].p[0];
 364                     in.pointlist[N * 2 + 1] = Node[i].p[2];
 365                     break;
 366                 case PLANE_YZ0:
 367                 case PLANE_YZ1:
 368                     in.pointlist[N * 2] = Node[i].p[1];
 369                     in.pointlist[N * 2 + 1] = Node[i].p[2];
 370                     break;
 371                 default:
 372                     in.pointlist[N * 2] = Node[i].p[0];
 373                     in.pointlist[N * 2 + 1] = Node[i].p[1];
 374             }
 375             NodeTable[N] = i;
 376             N++;
 377         }
 378     }
 379     in.pointattributelist = (REAL *) NULL;
 380     in.pointmarkerlist = (int *) NULL;
 381
 382     if (strstr(Options, "r")) {
 383         int *TriTable;
 384         TriTable = (int *) malloc(NumNodes * sizeof(int));
 385         for (i = 0, N = 0; i < NumNodes; i++) {
 386             if (Node[i].used) {
 387                 TriTable[i] = N;
 388                 N++;
 389             }
 390         }
 391         in.numberoftriangles = NumTris[0];
 392         in.numberofcorners = 3;
 393         in.numberoftriangleattributes = 0;
 394         in.trianglelist = (int *) malloc(in.numberofcorners * in.numberoftriangles * sizeof(int));
 395         in.triangleattributelist = (REAL *) NULL;
 396         in.trianglearealist = (REAL *) NULL;
 397         ptri = *inTri;
 398         for (i = 0; i < in.numberoftriangles; i++) {
 399             in.trianglelist[i * in.numberofcorners] = TriTable[ptri[i].v[0]];
 400             in.trianglelist[i * in.numberofcorners + 1] = TriTable[ptri[i].v[1]];
 401             in.trianglelist[i * in.numberofcorners + 2] = TriTable[ptri[i].v[2]];
 402         }
 403         free(TriTable);
 404     } else {
 405         in.numberoftriangles = 0;
 406         in.numberofcorners = 3;
 407         in.numberoftriangleattributes = 0;
 408         in.trianglelist = (int *) NULL;
 409         in.triangleattributelist = (REAL *) NULL;
 410         in.trianglearealist = (REAL *) NULL;
 411     }
 412
 413     in.numberofsegments = 0;
 414     in.segmentlist = (int *) NULL;
 415     in.segmentmarkerlist = (int *) NULL;
 416
 417     in.numberofholes = 0;
 418     in.holelist = (REAL *) NULL;
 419
 420     in.numberofregions = 0;
 421     in.regionlist = (REAL *) NULL;
 422
 423     in.numberofedges = 0;
 424     in.edgelist = (int *) NULL;
 425     in.edgemarkerlist = (int *) NULL;
 426     in.normlist = (REAL *) NULL;
 427
 428     /* Make necessary initializations */
 429     out.pointlist = (REAL *) NULL;  /* Not needed if -N switch used. */
 430     out.pointattributelist = (REAL *) NULL;  /* Not needed if -N switch used or
 431                                                     number of point attributes is zero: */
 432     out.pointmarkerlist = (int *) NULL;   /* Not needed if -N or -B switch used. */
 433     out.trianglelist = (int *) NULL;   /* Not needed if -E switch used. */
 434     out.triangleattributelist = (REAL *) NULL;   /* Not needed if -E switch used or
 435                                                         number of triangle attributes is
 436                                                         zero: */
 437     out.trianglearealist = (REAL *) NULL;
 438     out.neighborlist = (int *) NULL;   /* Needed only if -n switch used. */
 439     out.segmentlist = (int *) NULL;   /* Needed only if segments are output
 440                                                     (-p or -c) and -P not used: */
 441     out.segmentmarkerlist = (int *) NULL;   /* Needed only if segments are output
 442                                                     (-p or -c) and -P and -B not used: */
 443     out.edgelist = (int *) NULL;   /* Needed only if -e switch used. */
 444     out.edgemarkerlist = (int *) NULL;   /* Needed if -e used and -B not used. */
 445
 446     triangulate(Options, &in, &out, NULL);
 447
 448     NumTris[0] = out.numberoftriangles;
 449     *Tri = (TRI *) malloc(NumTris[0] * sizeof(TRI));
 450     ptri = *Tri;
 451
 452     for (i = 0; i < NumTris[0]; i++) {
 453         ptri[i].v[0] = NodeTable[out.trianglelist[i * out.numberofcorners]];
 454         ptri[i].v[1] = NodeTable[out.trianglelist[i * out.numberofcorners + 1]];
 455         ptri[i].v[2] = NodeTable[out.trianglelist[i * out.numberofcorners + 2]];
 456         ptri[i].n[0] = out.neighborlist[i * 3];
 457         ptri[i].n[1] = out.neighborlist[i * 3 + 1];
 458         ptri[i].n[2] = out.neighborlist[i * 3 + 2];
 459     }
 460
 461     /* Free all allocated arrays, including those allocated by Triangle. */
 462     if (in.pointlist) {
 463         free(in.pointlist);
 464     }
 465     if (in.pointattributelist) {
 466         free(in.pointattributelist);
 467     }
 468     if (in.pointmarkerlist) {
 469         free(in.pointmarkerlist);
 470     }
 471     if (in.trianglelist) {
 472         free(in.trianglelist);
 473     }
 474     if (in.triangleattributelist) {
 475         free(in.triangleattributelist);
 476     }
 477     if (in.trianglearealist) {
 478         free(in.trianglearealist);
 479     }
 480     if (in.neighborlist) {
 481         free(in.neighborlist);
 482     }
 483     if (in.segmentlist) {
 484         free(in.segmentlist);
 485     }
 486     if (in.segmentmarkerlist) {
 487         free(in.segmentmarkerlist);
 488     }
 489     if (in.holelist) {
 490         free(in.holelist);
 491     }
 492     if (in.regionlist) {
 493         free(in.regionlist);
 494     }
 495     if (in.edgelist) {
 496         free(in.edgelist);
 497     }
 498     if (in.edgemarkerlist) {
 499         free(in.edgemarkerlist);
 500     }
 501     if (in.normlist) {
 502         free(in.normlist);
 503     }
 504     if (out.pointlist) {
 505         free(out.pointlist);
 506     }
 507     if (out.pointattributelist) {
 508         free(out.pointattributelist);
 509     }
 510     if (out.pointmarkerlist) {
 511         free(out.pointmarkerlist);
 512     }
 513     if (out.trianglelist) {
 514         free(out.trianglelist);
 515     }
 516     if (out.triangleattributelist) {
 517         free(out.triangleattributelist);
 518     }
 519     if (out.trianglearealist) {
 520         free(out.trianglearealist);
 521     }
 522     if (out.neighborlist) {
 523         free(out.neighborlist);
 524     }
 525     if (out.segmentlist) {
 526         free(out.segmentlist);
 527     }
 528     if (out.segmentmarkerlist) {
 529         free(out.segmentmarkerlist);
 530     }
 531     if (out.holelist) {
 532         free(out.holelist);
 533     }
 534     if (out.regionlist) {
 535         free(out.regionlist);
 536     }
 537     if (out.edgelist) {
 538         free(out.edgelist);
 539     }
 540     if (out.edgemarkerlist) {
 541         free(out.edgemarkerlist);
 542     }
 543     if (out.normlist) {
 544         free(out.normlist);
 545     }
 546
 547     free(NodeTable);
 548     return 0;
 549 }
 550
 551 void EdgeOnSide(int *v, int *edge, int *border)
 552 {
 553     int R;
 554     int k0, k1, N;
 555     float Ndv;
 556
 557     border[0] = -1;
 558
 559     if ((v[0] <= NV) && (v[1] <= NV)) {
 560         edge[0] = 0;
 561         border[0] = 0;
 562     }
 563     if ((v[1] <= NV) && (v[2] <= NV)) {
 564         edge[0] = 1;
 565         border[0] = 0;
 566     }
 567     if ((v[2] <= NV) && (v[0] <= NV)) {
 568         edge[0] = 2;
 569         border[0] = 0;
 570     }
 571
 572     R = NH * NVP1;
 573
 574     if ((v[0] >= R) && (v[1] >= R)) {
 575         edge[0] = 0;
 576         border[0] = 1;
 577     }
 578     if ((v[1] >= R) && (v[2] >= R)) {
 579         edge[0] = 1;
 580         border[0] = 1;
 581     }
 582     if ((v[2] >= R) && (v[0] >= R)) {
 583         edge[0] = 2;
 584         border[0] = 1;
 585     }
 586
 587     if (border[0] >= 0) {
 588         k0 = edge[0];
 589         k1 = (k0 + 1) % 3;
 590         N = Absolute(v[k0] - v[k1]);
 591         Ndv = (float) (N * dv);
 592     }
 593     if (((v[0] % NVP1) == 0) && ((v[1] % NVP1) == 0)) {
 594         if (border[0] >= 0) {
 595             if (Ndv > (Absolute(v[0] - v[1]) * dh)) {
 596                 return;
 597             }
 598         }
 599         edge[0] = 0;
 600         border[0] = 2;
 601         return;
 602     }
 603     if (((v[1] % NVP1) == 0) && ((v[2] % NVP1) == 0)) {
 604         if (border[0] >= 0) {
 605             if (Ndv > (Absolute(v[1] - v[2]) * dh)) {
 606                 return;
 607             }
 608         }
 609         edge[0] = 1;
 610         border[0] = 2;
 611         return;
 612     }
 613     if (((v[2] % NVP1) == 0) && ((v[0] % NVP1) == 0)) {
 614         if (border[0] >= 0) {
 615             if (Ndv > (Absolute(v[2] - v[0]) * dh)) {
 616                 return;
 617             }
 618         }
 619         edge[0] = 2;
 620         border[0] = 2;
 621         return;
 622     }
 623
 624     if (((v[0] % NVP1) == NV) && ((v[1] % NVP1) == NV)) {
 625         if (border[0] >= 0) {
 626             if (Ndv > (Absolute(v[0] - v[1]) * dh)) {
 627                 return;
 628             }
 629         }
 630         edge[0] = 0;
 631         border[0] = 3;
 632         return;
 633     }
 634     if (((v[1] % NVP1) == NV) && ((v[2] % NVP1) == NV)) {
 635         if (border[0] >= 0) {
 636             if (Ndv > (Absolute(v[1] - v[2]) * dh)) {
 637                 return;
 638             }
 639         }
 640         edge[0] = 1;
 641         border[0] = 3;
 642         return;
 643     }
 644     if (((v[2] % NVP1) == NV) && ((v[0] % NVP1) == NV)) {
 645         if (border[0] >= 0) {
 646             if (Ndv > (Absolute(v[2] - v[0]) * dh)) {
 647                 return;
 648             }
 649         }
 650         edge[0] = 2;
 651         border[0] = 3;
 652         return;
 653     }
 654     return;
 655 }
 656
 657 void CalcAngles(NODE *node, int *v, float *angle)
 658 {
 659     int i, j, k;
 660     vec l;
 661     vec x0, x1, x2, y0, y1, y2;
 662     vec2 vv[3];
 663     vec dot;
 664
 665     switch (Plane) {
 666         case PLANE_XZ0:
 667         case PLANE_XZ1:
 668             i = 0;
 669             j = 2;
 670             break;
 671         case PLANE_YZ0:
 672         case PLANE_YZ1:
 673             i = 1;
 674             j = 2;
 675             break;
 676         default:
 677             i = 0;
 678             j = 1;
 679     }
 680     x0 = node[v[0]].p[i];
 681     x1 = node[v[1]].p[i];
 682     x2 = node[v[2]].p[i];
 683     y0 = node[v[0]].p[j];
 684     y1 = node[v[1]].p[j];
 685     y2 = node[v[2]].p[j];
 686
 687     vv[0][0] = x1 - x0;
 688     vv[0][1] = y1 - y0;
 689     vv[1][0] = x2 - x1;
 690     vv[1][1] = y2 - y1;
 691     vv[2][0] = x0 - x2;
 692     vv[2][1] = y0 - y2;
 693
 694     for (k = 0; k < 3; k++) {
 695         l = (vec) (sqrt(vv[k][0] * vv[k][0] + vv[k][1] * vv[k][1]));
 696         if (l > 0.) {
 697             vv[k][0] /= l;
 698             vv[k][1] /= l;
 699         }
 700     }
 701
 702     dot = -(vv[0][0] * vv[2][0] + vv[0][1] * vv[2][1]);
 703     angle[0] = (float) (acos(dot));
 704     dot = -(vv[1][0] * vv[0][0] + vv[1][1] * vv[0][1]);
 705     angle[1] = (float) (acos(dot));
 706     dot = -(vv[2][0] * vv[1][0] + vv[2][1] * vv[1][1]);
 707     angle[2] = (float) (acos(dot));
 708 }
 709
 710 //=================================================================
 711 int Bisect(NODE *node, int border, int j0, int j1)
 712 {
 713     int k;
 714
 715     switch (border) {
 716         case 0:
 717             k = (j0 + j1) / 2;
 718             break;
 719         case 1:
 720             k = (j0 + j1) / 2;
 721             break;
 722         case 2:
 723             k = (int) ((j0 + j1) / (2 * NVP1)) * NVP1;
 724             break;
 725         case 3:
 726             k = (int) ((j0 + j1 + 2) / (2 * NVP1)) * NVP1 - 1;
 727             break;
 728     }
 729     return (((k != j0) && (k != j1)) ? k : 0);
 730 }
 731
 732 //=================================================================
 733 int compare(TRITABLE *t1, TRITABLE *t2)
 734 {
 735     if (t1->error > t2->error) {
 736         return -1;
 737     }
 738     if (t1->error < t2->error) {
 739         return 1;
 740     }
 741     return 0;
 742 }
 743
 744 void MakeBrushes(int NumTris, NODE *Node, TRI *Tri, bool surf,
 745                  int offset, char *texture0, char *texture1, char *texture2)
 746 {
 747     extern double backface;
 748     BRUSH brush;
 749     int contents;
 750     int i, j;
 751     float Steep;
 752     vec3_t PlaneNormal, SurfNormal;
 753     bool CheckAngle;
 754     vec3_t t[2];
 755
 756     // if texture2 is identical to texture0, there's no need to
 757     // check surface angle
 758     if (!g_strcasecmp(texture0, texture2) || !strlen(texture2)) {
 759         CheckAngle = FALSE;
 760     } else {
 761         CheckAngle = TRUE;
 762         Steep = (float) cos((double) SlantAngle / 57.2957795);
 763         switch (Plane) {
 764             case PLANE_XY0:
 765                 PlaneNormal[0] = 0.;
 766                 PlaneNormal[1] = 0.;
 767                 PlaneNormal[2] = 1.;
 768                 break;
 769             case PLANE_XY1:
 770                 PlaneNormal[0] = 0.;
 771                 PlaneNormal[1] = 0.;
 772                 PlaneNormal[2] = -1.;
 773                 break;
 774             case PLANE_XZ0:
 775                 PlaneNormal[0] = 0.;
 776                 PlaneNormal[1] = 1.;
 777                 PlaneNormal[2] = 1.;
 778                 break;
 779             case PLANE_XZ1:
 780                 PlaneNormal[0] = 0.;
 781                 PlaneNormal[1] = -1.;
 782                 PlaneNormal[2] = 1.;
 783                 break;
 784             case PLANE_YZ0:
 785                 PlaneNormal[0] = 1.;
 786                 PlaneNormal[1] = 0.;
 787                 PlaneNormal[2] = 1.;
 788                 break;
 789             case PLANE_YZ1:
 790                 PlaneNormal[0] = -1.;
 791                 PlaneNormal[1] = 0.;
 792                 PlaneNormal[2] = 1.;
 793                 break;
 794         }
 795     }
 796
 797     contents = 0;
 798     if (surf) {
 799         if (UseDetail) {
 800             contents += CONTENTS_DETAIL;
 801         }
 802         if (UseLadder) {
 803             contents += CONTENTS_LADDER;
 804         }
 805     }
 806
 807     OpenFuncGroup();
 808     for (i = 0; i < NumTris; i++) {
 809         brush.Number = i;
 810         brush.NumFaces = 5;
 811         // front
 812         brush.face[0].v[0][0] = Node[Tri[i].v[0]].p[0];
 813         brush.face[0].v[0][1] = Node[Tri[i].v[0]].p[1];
 814         brush.face[0].v[0][2] = Node[Tri[i].v[0]].p[2];
 815
 816         brush.face[0].v[1][0] = Node[Tri[i].v[2]].p[0];
 817         brush.face[0].v[1][1] = Node[Tri[i].v[2]].p[1];
 818         brush.face[0].v[1][2] = Node[Tri[i].v[2]].p[2];
 819
 820         brush.face[0].v[2][0] = Node[Tri[i].v[1]].p[0];
 821         brush.face[0].v[2][1] = Node[Tri[i].v[1]].p[1];
 822         brush.face[0].v[2][2] = Node[Tri[i].v[1]].p[2];
 823
 824         if (offset != 0) {
 825             switch (Plane) {
 826                 case PLANE_XY0:
 827                     brush.face[0].v[0][2] += offset;
 828                     brush.face[0].v[1][2] += offset;
 829                     brush.face[0].v[1][2] += offset;
 830                     break;
 831                 case PLANE_XY1:
 832                     brush.face[0].v[0][2] -= offset;
 833                     brush.face[0].v[1][2] -= offset;
 834                     brush.face[0].v[1][2] -= offset;
 835                     break;
 836                 case PLANE_XZ0:
 837                     brush.face[0].v[0][1] += offset;
 838                     brush.face[0].v[1][1] += offset;
 839                     brush.face[0].v[1][1] += offset;
 840                     break;
 841                 case PLANE_XZ1:
 842                     brush.face[0].v[0][1] -= offset;
 843                     brush.face[0].v[1][1] -= offset;
 844                     brush.face[0].v[1][1] -= offset;
 845                     break;
 846                 case PLANE_YZ0:
 847                     brush.face[0].v[0][0] += offset;
 848                     brush.face[0].v[1][0] += offset;
 849                     brush.face[0].v[1][0] += offset;
 850                     break;
 851                 case PLANE_YZ1:
 852                     brush.face[0].v[0][0] -= offset;
 853                     brush.face[0].v[1][0] -= offset;
 854                     brush.face[0].v[1][0] -= offset;
 855                     break;
 856             }
 857         }
 858         switch (Plane) {
 859             case PLANE_XZ0:
 860             case PLANE_XZ1:
 861                 // back
 862                 brush.face[1].v[0][0] = Node[Tri[i].v[0]].p[0];
 863                 brush.face[1].v[0][1] = (float) backface;
 864                 brush.face[1].v[0][2] = Node[Tri[i].v[0]].p[2];
 865
 866                 brush.face[1].v[1][0] = Node[Tri[i].v[1]].p[0];
 867                 brush.face[1].v[1][1] = (float) backface;
 868                 brush.face[1].v[1][2] = Node[Tri[i].v[1]].p[2];
 869
 870                 brush.face[1].v[2][0] = Node[Tri[i].v[2]].p[0];
 871                 brush.face[1].v[2][1] = (float) backface;
 872                 brush.face[1].v[2][2] = Node[Tri[i].v[2]].p[2];
 873
 874                 // 0-1 side
 875                 brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
 876                 brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
 877                 brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
 878
 879                 brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
 880                 brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
 881                 brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
 882
 883                 brush.face[2].v[2][0] = Node[Tri[i].v[1]].p[0];
 884                 brush.face[2].v[2][1] = (float) backface;
 885                 brush.face[2].v[2][2] = Node[Tri[i].v[1]].p[2];
 886
 887                 // 1-2 side
 888                 brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
 889                 brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
 890                 brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
 891
 892                 brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
 893                 brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
 894                 brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
 895
 896                 brush.face[3].v[2][0] = Node[Tri[i].v[2]].p[0];
 897                 brush.face[3].v[2][1] = (float) backface;
 898                 brush.face[3].v[2][2] = Node[Tri[i].v[2]].p[2];
 899
 900                 // 2-0 side
 901                 brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
 902                 brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
 903                 brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
 904
 905                 brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
 906                 brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
 907                 brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
 908
 909                 brush.face[4].v[2][0] = Node[Tri[i].v[0]].p[0];
 910                 brush.face[4].v[2][1] = (float) backface;
 911                 brush.face[4].v[2][2] = Node[Tri[i].v[0]].p[2];
 912                 break;
 913             case PLANE_YZ0:
 914             case PLANE_YZ1:
 915                 // back
 916                 brush.face[1].v[0][0] = (float) backface;
 917                 brush.face[1].v[0][1] = Node[Tri[i].v[0]].p[1];
 918                 brush.face[1].v[0][2] = Node[Tri[i].v[0]].p[2];
 919
 920                 brush.face[1].v[1][0] = (float) backface;
 921                 brush.face[1].v[1][1] = Node[Tri[i].v[1]].p[1];
 922                 brush.face[1].v[1][2] = Node[Tri[i].v[1]].p[2];
 923
 924                 brush.face[1].v[2][0] = (float) backface;
 925                 brush.face[1].v[2][1] = Node[Tri[i].v[2]].p[1];
 926                 brush.face[1].v[2][2] = Node[Tri[i].v[2]].p[2];
 927
 928                 // 0-1 side
 929                 brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
 930                 brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
 931                 brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
 932
 933                 brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
 934                 brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
 935                 brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
 936
 937                 brush.face[2].v[2][0] = (float) backface;
 938                 brush.face[2].v[2][1] = Node[Tri[i].v[1]].p[1];
 939                 brush.face[2].v[2][2] = Node[Tri[i].v[1]].p[2];
 940
 941                 // 1-2 side
 942                 brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
 943                 brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
 944                 brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
 945
 946                 brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
 947                 brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
 948                 brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
 949
 950                 brush.face[3].v[2][0] = (float) backface;
 951                 brush.face[3].v[2][1] = Node[Tri[i].v[2]].p[1];
 952                 brush.face[3].v[2][2] = Node[Tri[i].v[2]].p[2];
 953
 954                 // 2-0 side
 955                 brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
 956                 brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
 957                 brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
 958
 959                 brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
 960                 brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
 961                 brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
 962
 963                 brush.face[4].v[2][0] = (float) backface;
 964                 brush.face[4].v[2][1] = Node[Tri[i].v[0]].p[1];
 965                 brush.face[4].v[2][2] = Node[Tri[i].v[0]].p[2];
 966                 break;
 967             default:
 968                 // back
 969                 brush.face[1].v[0][0] = Node[Tri[i].v[0]].p[0];
 970                 brush.face[1].v[0][1] = Node[Tri[i].v[0]].p[1];
 971                 brush.face[1].v[0][2] = (float) backface;
 972
 973                 brush.face[1].v[1][0] = Node[Tri[i].v[1]].p[0];
 974                 brush.face[1].v[1][1] = Node[Tri[i].v[1]].p[1];
 975                 brush.face[1].v[1][2] = (float) backface;
 976
 977                 brush.face[1].v[2][0] = Node[Tri[i].v[2]].p[0];
 978                 brush.face[1].v[2][1] = Node[Tri[i].v[2]].p[1];
 979                 brush.face[1].v[2][2] = (float) backface;
 980
 981                 // 0-1 side
 982                 brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
 983                 brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
 984                 brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
 985
 986                 brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
 987                 brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
 988                 brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
 989
 990                 brush.face[2].v[2][0] = Node[Tri[i].v[1]].p[0];
 991                 brush.face[2].v[2][1] = Node[Tri[i].v[1]].p[1];
 992                 brush.face[2].v[2][2] = (float) backface;
 993
 994                 // 1-2 side
 995                 brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
 996                 brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
 997                 brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
 998
 999                 brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
1000                 brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
1001                 brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
1002
1003                 brush.face[3].v[2][0] = Node[Tri[i].v[2]].p[0];
1004                 brush.face[3].v[2][1] = Node[Tri[i].v[2]].p[1];
1005                 brush.face[3].v[2][2] = (float) backface;
1006
1007                 // 2-0 side
1008                 brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
1009                 brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
1010                 brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
1011
1012                 brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
1013                 brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
1014                 brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
1015
1016                 brush.face[4].v[2][0] = Node[Tri[i].v[0]].p[0];
1017                 brush.face[4].v[2][1] = Node[Tri[i].v[0]].p[1];
1018                 brush.face[4].v[2][2] = (float) backface;
1019         }
1020
1021         for (j = 0; j < 5; j++) {
1022             strcpy(brush.face[j].texture,
1023                    (strlen(texture1) ? texture1 : texture0));
1024             brush.face[j].Shift[0] = (float) TexOffset[0];
1025             brush.face[j].Shift[1] = (float) TexOffset[1];
1026             brush.face[j].Rotate = 0.;
1027             brush.face[j].Scale[0] = (float) TexScale[0];
1028             brush.face[j].Scale[1] = (float) TexScale[1];
1029             brush.face[j].Contents = contents;
1030             if (surf) {
1031                 brush.face[j].Surface = 0;
1032             } else {
1033                 brush.face[j].Surface = SURF_HINT;
1034             }
1035             brush.face[j].Value = 0;
1036         }
1037
1038         if (CheckAngle) {
1039             XYZVectorSubtract(brush.face[0].v[2], brush.face[0].v[0], t[0]);
1040             XYZVectorSubtract(brush.face[0].v[1], brush.face[0].v[2], t[1]);
1041             CrossProduct(t[0], t[1], SurfNormal);
1042             VectorNormalize(SurfNormal, SurfNormal);
1043             if (DotProduct(SurfNormal, PlaneNormal) < Steep) {
1044                 strcpy(brush.face[0].texture, texture2);
1045             } else {
1046                 strcpy(brush.face[0].texture, texture0);
1047             }
1048         } else {
1049             strcpy(brush.face[0].texture, texture0);
1050         }
1051
1052         if (surf) {
1053             brush.face[0].Value = ArghRad2;
1054         }
1055         MakeBrush(&brush);
1056     }
1057     CloseFuncGroup();
1058
1059 } // end MakeBrushes
1060 //=================================================================
1061 void MapOut(int NumNodes, int NumTris, NODE *Node, TRI *Tri)
1062 {
1063     extern double backface;
1064     extern double xmin, xmax, ymin, ymax, zmin, zmax;
1065     BRUSH brush;
1066     char hint[32], skip[32];
1067     int i, j;
1068     int face;
1069     /*
1070        ghCursorCurrent = LoadCursor(NULL,IDC_WAIT);
1071        SetCursor(ghCursorCurrent);
1072      */
1073     UseDetail = 1; // this is temporary
1074     MakeBrushes(NumTris, Node, Tri, TRUE, 0, Texture[Game][0], Texture[Game][1], Texture[Game][2]);
1075
1076     if (AddHints || GimpHints) {
1077         switch (Game) {
1078             case SIN:
1079                 strcpy(hint, "generic/misc/hint");
1080                 strcpy(skip, "generic/misc/skip");
1081                 break;
1082             case HALFLIFE:
1083                 strcpy(hint, "HINT");
1084                 strcpy(skip, "HINT");
1085                 break;
1086             case HERETIC2:
1087                 strcpy(hint, "general/hint");
1088                 strcpy(skip, "general/skip");
1089                 break;
1090             case KINGPIN:
1091                 strcpy(hint, "common/0_hint");
1092                 strcpy(skip, "common/0_skip");
1093                 break;
1094             case QUAKE3:
1095                 strcpy(hint, "common/hint");
1096                 strcpy(skip, "common/skip");
1097                 break;
1098             default:
1099                 strcpy(hint, "e1u1/hint");
1100                 strcpy(skip, "e1u1/skip");
1101         }
1102     }
1103
1104     if (GimpHints) {
1105         MakeBrushes(NumTris, Node, Tri, FALSE, HINT_OFFSET, hint, hint, hint);
1106     }
1107
1108     if (AddHints == 1) {
1109         int j0, j1, j2, k, k0, k1;
1110         int q[4];
1111         int w, h, h0, h1, t, OK;
1112         float s[3];
1113         double front;
1114         int MaxHints;   // We don't want a whole slew of hint brushes, which we'd get
1115         // with low decimation values and our current placement scheme.
1116         // Limit number of hint brushes to number of undecimated grid
1117         // squares.
1118
1119         switch (Plane) {
1120             case PLANE_XY1:
1121                 front = LessThan(zmin, 32.);
1122                 break;
1123             case PLANE_XZ0:
1124                 front = MoreThan(ymax, 32.);
1125                 break;
1126             case PLANE_XZ1:
1127                 front = LessThan(ymin, 32.);
1128                 break;
1129             case PLANE_YZ0:
1130                 front = MoreThan(xmax, 32.);
1131                 break;
1132             case PLANE_YZ1:
1133                 front = LessThan(xmin, 32.);
1134                 break;
1135             default:
1136                 front = MoreThan(zmax, 32.);
1137         }
1138
1139         for (i = 0; i < NumTris; i++) {
1140             Tri[i].flag = 0;
1141         }
1142
1143         switch (Plane) {
1144             case PLANE_XZ0:
1145             case PLANE_XZ1:
1146                 j0 = 1;
1147                 j1 = 0;
1148                 j2 = 2;
1149                 break;
1150             case PLANE_YZ0:
1151             case PLANE_YZ1:
1152                 j0 = 0;
1153                 j1 = 1;
1154                 j2 = 2;
1155                 break;
1156             default:
1157                 j0 = 2;
1158                 j1 = 0;
1159                 j2 = 1;
1160         }
1161
1162         brush.Number = 0;
1163         brush.NumFaces = 6;
1164         MaxHints = NH * NV - 1;
1165         for (w = 1; w < min(16, NH) && brush.Number < MaxHints; w++) {
1166             for (h = max(1, w / 2); h < min(16, NV) && brush.Number < MaxHints; h++) {
1167                 for (i = 0; i <= NH - w && brush.Number < MaxHints; i++) {
1168                     for (j = 0; j <= NV - h && brush.Number < MaxHints; j++) {
1169                         q[0] = i * NVP1 + j;
1170                         q[2] = q[0] + w * NVP1 + h;
1171                         switch (Plane) {
1172                             case PLANE_XY1:
1173                             case PLANE_XZ0:
1174                             case PLANE_YZ1:
1175                                 q[1] = q[0] + h;
1176                                 q[3] = q[2] - h;
1177                                 break;
1178                             default:
1179                                 q[1] = q[2] - h;
1180                                 q[3] = q[0] + h;
1181                         }
1182                         for (k = 0, OK = 1; k < NumTris && OK; k++) {
1183                             if (Tri[k].min[j1] >= max(Node[q[0]].p[j1], Node[q[2]].p[j1])) {
1184                                 continue;
1185                             }
1186                             if (Tri[k].min[j2] >= max(Node[q[0]].p[j2], Node[q[2]].p[j2])) {
1187                                 continue;
1188                             }
1189                             if (Tri[k].max[j1] <= min(Node[q[0]].p[j1], Node[q[2]].p[j1])) {
1190                                 continue;
1191                             }
1192                             if (Tri[k].max[j2] <= min(Node[q[0]].p[j2], Node[q[2]].p[j2])) {
1193                                 continue;
1194                             }
1195
1196                             for (h0 = 0; h0 < 4 && OK; h0++) {
1197                                 h1 = (h0 + 1) % 4;
1198                                 for (t = 0; t < 3 && OK; t++) {
1199                                     s[t] = side(Node[q[h0]].p[j1], Node[q[h0]].p[j2],
1200                                                 Node[q[h1]].p[j1], Node[q[h1]].p[j2],
1201                                                 Node[Tri[k].v[t]].p[j1], Node[Tri[k].v[t]].p[j2]);
1202                                 }
1203                                 if ((s[1] > 0 || s[2] > 0) && s[0] < 0) {
1204                                     OK = 0;
1205                                 }
1206                                 if ((s[2] > 0 || s[0] > 0) && s[1] < 0) {
1207                                     OK = 0;
1208                                 }
1209                                 if ((s[0] > 0 || s[1] > 0) && s[2] < 0) {
1210                                     OK = 0;
1211                                 }
1212                             }
1213                         }
1214                         if (!OK) {
1215                             continue;
1216                         }
1217                         switch (Plane) {
1218                             case PLANE_XZ0:
1219                             case PLANE_XZ1:
1220                                 // front
1221                                 brush.face[0].v[0][0] = Node[q[2]].p[0];
1222                                 brush.face[0].v[0][1] = (float) front;
1223                                 brush.face[0].v[0][2] = Node[q[2]].p[2];
1224
1225                                 brush.face[0].v[1][0] = Node[q[1]].p[0];
1226                                 brush.face[0].v[1][1] = (float) front;
1227                                 brush.face[0].v[1][2] = Node[q[1]].p[2];
1228
1229                                 brush.face[0].v[2][0] = Node[q[0]].p[0];
1230                                 brush.face[0].v[2][1] = (float) front;
1231                                 brush.face[0].v[2][2] = Node[q[0]].p[2];
1232
1233                                 // back
1234                                 brush.face[1].v[0][0] = Node[q[0]].p[0];
1235                                 brush.face[1].v[0][1] = (float) backface;
1236                                 brush.face[1].v[0][2] = Node[q[0]].p[2];
1237
1238                                 brush.face[1].v[1][0] = Node[q[1]].p[0];
1239                                 brush.face[1].v[1][1] = (float) backface;
1240                                 brush.face[1].v[1][2] = Node[q[1]].p[2];
1241
1242                                 brush.face[1].v[2][0] = Node[q[2]].p[0];
1243                                 brush.face[1].v[2][1] = (float) backface;
1244                                 brush.face[1].v[2][2] = Node[q[2]].p[2];
1245
1246                                 for (k0 = 0; k0 < brush.NumFaces - 2; k0++) {
1247                                     k = k0 + 2;
1248                                     k1 = (k0 + 1) % (brush.NumFaces - 2);
1249
1250                                     brush.face[k].v[0][0] = Node[q[k0]].p[0];
1251                                     brush.face[k].v[0][1] = (float) front;
1252                                     brush.face[k].v[0][2] = Node[q[k0]].p[2];
1253
1254                                     brush.face[k].v[1][0] = Node[q[k1]].p[0];
1255                                     brush.face[k].v[1][1] = (float) front;
1256                                     brush.face[k].v[1][2] = Node[q[k1]].p[2];
1257
1258                                     brush.face[k].v[2][0] = Node[q[k1]].p[0];
1259                                     brush.face[k].v[2][1] = (float) backface;
1260                                     brush.face[k].v[2][2] = Node[q[k1]].p[2];
1261                                 }
1262                                 break;
1263                             case PLANE_YZ0:
1264                             case PLANE_YZ1:
1265                                 // front
1266                                 brush.face[0].v[0][0] = (float) front;
1267                                 brush.face[0].v[0][1] = Node[q[2]].p[1];
1268                                 brush.face[0].v[0][2] = Node[q[2]].p[2];
1269
1270                                 brush.face[0].v[1][0] = (float) front;
1271                                 brush.face[0].v[1][1] = Node[q[1]].p[1];
1272                                 brush.face[0].v[1][2] = Node[q[1]].p[2];
1273
1274                                 brush.face[0].v[2][0] = (float) front;
1275                                 brush.face[0].v[2][1] = Node[q[0]].p[1];
1276                                 brush.face[0].v[2][2] = Node[q[0]].p[2];
1277
1278                                 // back
1279                                 brush.face[1].v[0][0] = (float) backface;
1280                                 brush.face[1].v[0][1] = Node[q[0]].p[1];
1281                                 brush.face[1].v[0][2] = Node[q[0]].p[2];
1282
1283                                 brush.face[1].v[1][0] = (float) backface;
1284                                 brush.face[1].v[1][1] = Node[q[1]].p[1];
1285                                 brush.face[1].v[1][2] = Node[q[1]].p[2];
1286
1287                                 brush.face[1].v[2][0] = (float) backface;
1288                                 brush.face[1].v[2][1] = Node[q[2]].p[1];
1289                                 brush.face[1].v[2][2] = Node[q[2]].p[2];
1290
1291                                 for (k0 = 0; k0 < brush.NumFaces - 2; k0++) {
1292                                     k = k0 + 2;
1293                                     k1 = (k0 + 1) % (brush.NumFaces - 2);
1294
1295                                     brush.face[k].v[0][0] = (float) front;
1296                                     brush.face[k].v[0][1] = Node[q[k0]].p[1];
1297                                     brush.face[k].v[0][2] = Node[q[k0]].p[2];
1298
1299                                     brush.face[k].v[1][0] = (float) front;
1300                                     brush.face[k].v[1][1] = Node[q[k1]].p[1];
1301                                     brush.face[k].v[1][2] = Node[q[k1]].p[2];
1302
1303                                     brush.face[k].v[2][0] = (float) backface;
1304                                     brush.face[k].v[2][1] = Node[q[k1]].p[1];
1305                                     brush.face[k].v[2][2] = Node[q[k1]].p[2];
1306                                 }
1307                                 break;
1308                             default:
1309                                 // front
1310                                 brush.face[0].v[0][0] = Node[q[2]].p[0];
1311                                 brush.face[0].v[0][1] = Node[q[2]].p[1];
1312                                 brush.face[0].v[0][2] = (float) front;
1313
1314                                 brush.face[0].v[1][0] = Node[q[1]].p[0];
1315                                 brush.face[0].v[1][1] = Node[q[1]].p[1];
1316                                 brush.face[0].v[1][2] = (float) front;
1317
1318                                 brush.face[0].v[2][0] = Node[q[0]].p[0];
1319                                 brush.face[0].v[2][1] = Node[q[0]].p[1];
1320                                 brush.face[0].v[2][2] = (float) front;
1321
1322                                 // back
1323                                 brush.face[1].v[0][0] = Node[q[0]].p[0];
1324                                 brush.face[1].v[0][1] = Node[q[0]].p[1];
1325                                 brush.face[1].v[0][2] = (float) backface;
1326
1327                                 brush.face[1].v[1][0] = Node[q[1]].p[0];
1328                                 brush.face[1].v[1][1] = Node[q[1]].p[1];
1329                                 brush.face[1].v[1][2] = (float) backface;
1330
1331                                 brush.face[1].v[2][0] = Node[q[2]].p[0];
1332                                 brush.face[1].v[2][1] = Node[q[2]].p[1];
1333                                 brush.face[1].v[2][2] = (float) backface;
1334
1335                                 for (k0 = 0; k0 < brush.NumFaces - 2; k0++) {
1336                                     k = k0 + 2;
1337                                     k1 = (k0 + 1) % (brush.NumFaces - 2);
1338
1339                                     brush.face[k].v[0][0] = Node[q[k0]].p[0];
1340                                     brush.face[k].v[0][1] = Node[q[k0]].p[1];
1341                                     brush.face[k].v[0][2] = (float) front;
1342
1343                                     brush.face[k].v[1][0] = Node[q[k1]].p[0];
1344                                     brush.face[k].v[1][1] = Node[q[k1]].p[1];
1345                                     brush.face[k].v[1][2] = (float) front;
1346
1347                                     brush.face[k].v[2][0] = Node[q[k1]].p[0];
1348                                     brush.face[k].v[2][1] = Node[q[k1]].p[1];
1349                                     brush.face[k].v[2][2] = (float) backface;
1350                                 }
1351                                 break;
1352                         } // switch (Plane)
1353                         for (face = 0; face < 6; face++) {
1354                             strcpy(brush.face[face].texture, (face <= 1 ? skip : hint));
1355                             brush.face[face].Shift[0] = 0;
1356                             brush.face[face].Shift[1] = 0;
1357                             brush.face[face].Rotate = 0.;
1358                             brush.face[face].Scale[0] = 1;
1359                             brush.face[face].Scale[1] = 1;
1360                             brush.face[face].Contents = CONTENTS_DETAIL;
1361                             brush.face[face].Surface = (face <= 1 ? SURF_SKIP : SURF_HINT);
1362                             brush.face[face].Value = 0;
1363                         }
1364                         if (!brush.Number) {
1365                             OpenFuncGroup();
1366                         }
1367                         MakeBrush(&brush);
1368                         brush.Number++;
1369                     } // for(j=
1370                 }     // for(i=
1371             }         // for(h=
1372         }             // for(w=
1373         if (brush.Number) {
1374             CloseFuncGroup();
1375         }
1376     }
1377     /*
1378        ghCursorCurrent = ghCursorDefault;
1379        SetCursor(ghCursorCurrent);
1380      */
1381 }
1382
1383 //===========================================================================
1384 int CheckBorders(int *NumNodesUsed, int NumNodes, NODE *Node, int *NumTris, TRI **pTri)
1385 {
1386     int border;
1387     int i, j, k0, k1, N;
1388     float angle[3];
1389     TRI *Tri;
1390
1391     N = NumNodesUsed[0];
1392     Tri = *pTri;
1393     for (i = 0; i < NumTris[0]; i++) {
1394         EdgeOnSide(Tri[i].v, &k0, &border);
1395         if (border < 0) {
1396             continue;
1397         }
1398         CalcAngles(Node, Tri[i].v, angle);
1399         k1 = (k0 + 1) % 3;
1400         if ((angle[k0] < SLIVER_ANGLE) || (angle[k1] < SLIVER_ANGLE)) {
1401             j = Bisect(Node, border, Tri[i].v[k0], Tri[i].v[k1]);
1402             if (j >= 0) {
1403                 if (!Node[j].used) {  // Shouldn't be used, but...
1404                     NumNodesUsed[0]++;
1405                     Node[j].used++;
1406                 }
1407             }
1408         }
1409     }
1410     if (NumNodesUsed[0] > N) {
1411         free(*pTri);
1412         tricall(NumNodes, Node, NumTris, NULL, pTri, "cnzBNPY");
1413         Tri = *pTri;
1414     }
1415     return (NumNodesUsed[0] - N);
1416 }