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