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 **, const 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, const char *Options)
 327 {
 328         struct triangulateio in, out;
 329         int    i, N;
 330         int    NumUsedNodes;
 331         int    *NodeTable;
 332         TRI    *ptri;
 333
 334         /* Define input points. */
 335
 336         for(i=0,NumUsedNodes=0; i<NumNodes; i++)
 337                 if(Node[i].used) NumUsedNodes++;
 338
 339         memset(&in, 0,sizeof(in));
 340         memset(&out,0,sizeof(out));
 341
 342         NodeTable = (int *) malloc(NumUsedNodes * sizeof(int));
 343
 344         in.numberofpoints = NumUsedNodes;
 345         in.numberofpointattributes = 0;
 346         in.pointlist = (REAL *) malloc(in.numberofpoints * 2 * sizeof(REAL));
 347         for(i=0,N=0; i<NumNodes; i++)
 348         {
 349                 if(Node[i].used)
 350                 {
 351                         switch(Plane)
 352                         {
 353                         case PLANE_XZ0:
 354                         case PLANE_XZ1:
 355                                 in.pointlist[N*2  ] = Node[i].p[0];
 356                                 in.pointlist[N*2+1] = Node[i].p[2];
 357                                 break;
 358                         case PLANE_YZ0:
 359                         case PLANE_YZ1:
 360                                 in.pointlist[N*2  ] = Node[i].p[1];
 361                                 in.pointlist[N*2+1] = Node[i].p[2];
 362                                 break;
 363                         default:
 364                                 in.pointlist[N*2  ] = Node[i].p[0];
 365                                 in.pointlist[N*2+1] = Node[i].p[1];
 366                         }
 367                         NodeTable[N] = i;
 368                         N++;
 369                 }
 370         }
 371         in.pointattributelist = (REAL *) NULL;
 372         in.pointmarkerlist    = (int *) NULL;
 373
 374         if(strstr(Options,"r"))
 375         {
 376                 int    *TriTable;
 377                 TriTable = (int *) malloc(NumNodes * sizeof(int));
 378                 for(i=0,N=0; i<NumNodes; i++)
 379                 {
 380                         if(Node[i].used)
 381                         {
 382                                 TriTable[i] = N;
 383                                 N++;
 384                         }
 385                 }
 386                 in.numberoftriangles          = NumTris[0];
 387                 in.numberofcorners            = 3;
 388                 in.numberoftriangleattributes = 0;
 389                 in.trianglelist               = (int *) malloc(in.numberofcorners * in.numberoftriangles * sizeof(int));
 390                 in.triangleattributelist      = (REAL *) NULL;
 391                 in.trianglearealist           = (REAL *) NULL;
 392                 ptri = *inTri;
 393                 for(i=0; i<in.numberoftriangles; i++)
 394                 {
 395                         in.trianglelist[i*in.numberofcorners  ] = TriTable[ptri[i].v[0]];
 396                         in.trianglelist[i*in.numberofcorners+1] = TriTable[ptri[i].v[1]];
 397                         in.trianglelist[i*in.numberofcorners+2] = TriTable[ptri[i].v[2]];
 398                 }
 399                 free(TriTable);
 400         }
 401         else
 402         {
 403                 in.numberoftriangles          = 0;
 404                 in.numberofcorners            = 3;
 405                 in.numberoftriangleattributes = 0;
 406                 in.trianglelist               = (int *) NULL;
 407                 in.triangleattributelist      = (REAL *) NULL;
 408                 in.trianglearealist           = (REAL *) NULL;
 409         }
 410
 411         in.numberofsegments   = 0;
 412         in.segmentlist        = (int *) NULL;
 413         in.segmentmarkerlist  = (int *) NULL;
 414
 415         in.numberofholes      = 0;
 416         in.holelist           = (REAL *) NULL;
 417
 418         in.numberofregions    = 0;
 419         in.regionlist         = (REAL *) NULL;
 420
 421         in.numberofedges      = 0;
 422         in.edgelist           = (int *) NULL;
 423         in.edgemarkerlist     = (int *) NULL;
 424         in.normlist           = (REAL *) NULL;
 425
 426         /* Make necessary initializations */
 427         out.pointlist          = (REAL *) NULL;  /* Not needed if -N switch used. */
 428         out.pointattributelist = (REAL *) NULL;  /* Not needed if -N switch used or
 429                                                     number of point attributes is zero: */
 430         out.pointmarkerlist    = (int *) NULL;   /* Not needed if -N or -B switch used. */
 431         out.trianglelist       = (int *) NULL;   /* Not needed if -E switch used. */
 432         out.triangleattributelist = (REAL *) NULL;   /* Not needed if -E switch used or
 433                                                         number of triangle attributes is
 434                                                     zero: */
 435         out.trianglearealist   = (REAL *) NULL;
 436         out.neighborlist       = (int *) NULL;   /* Needed only if -n switch used. */
 437         out.segmentlist        = (int *) NULL;   /* Needed only if segments are output
 438                                                     (-p or -c) and -P not used: */
 439         out.segmentmarkerlist  = (int *) NULL;   /* Needed only if segments are output
 440                                                     (-p or -c) and -P and -B not used: */
 441         out.edgelist           = (int *) NULL;   /* Needed only if -e switch used. */
 442         out.edgemarkerlist     = (int *) NULL;   /* Needed if -e used and -B not used. */
 443
 444         triangulate(Options, &in, &out, NULL);
 445
 446         NumTris[0] = out.numberoftriangles;
 447         *Tri = (TRI *) malloc(NumTris[0] * sizeof(TRI));
 448         ptri = *Tri;
 449
 450         for(i=0; i<NumTris[0]; i++)
 451         {
 452                 ptri[i].v[0] = NodeTable[out.trianglelist[i*out.numberofcorners  ]];
 453                 ptri[i].v[1] = NodeTable[out.trianglelist[i*out.numberofcorners+1]];
 454                 ptri[i].v[2] = NodeTable[out.trianglelist[i*out.numberofcorners+2]];
 455                 ptri[i].n[0] = out.neighborlist[i*3  ];
 456                 ptri[i].n[1] = out.neighborlist[i*3+1];
 457                 ptri[i].n[2] = out.neighborlist[i*3+2];
 458         }
 459
 460         /* Free all allocated arrays, including those allocated by Triangle. */
 461         if(in.pointlist)              free(in.pointlist);
 462         if(in.pointattributelist)     free(in.pointattributelist);
 463         if(in.pointmarkerlist)        free(in.pointmarkerlist);
 464         if(in.trianglelist)           free(in.trianglelist);
 465         if(in.triangleattributelist)  free(in.triangleattributelist);
 466         if(in.trianglearealist)       free(in.trianglearealist);
 467         if(in.neighborlist)           free(in.neighborlist);
 468         if(in.segmentlist)            free(in.segmentlist);
 469         if(in.segmentmarkerlist)      free(in.segmentmarkerlist);
 470         if(in.holelist)               free(in.holelist);
 471         if(in.regionlist)             free(in.regionlist);
 472         if(in.edgelist)               free(in.edgelist);
 473         if(in.edgemarkerlist)         free(in.edgemarkerlist);
 474         if(in.normlist)               free(in.normlist);
 475         if(out.pointlist)             free(out.pointlist);
 476         if(out.pointattributelist)    free(out.pointattributelist);
 477         if(out.pointmarkerlist)       free(out.pointmarkerlist);
 478         if(out.trianglelist)          free(out.trianglelist);
 479         if(out.triangleattributelist) free(out.triangleattributelist);
 480         if(out.trianglearealist)      free(out.trianglearealist);
 481         if(out.neighborlist)          free(out.neighborlist);
 482         if(out.segmentlist)           free(out.segmentlist);
 483         if(out.segmentmarkerlist)     free(out.segmentmarkerlist);
 484         if(out.holelist)              free(out.holelist);
 485         if(out.regionlist)            free(out.regionlist);
 486         if(out.edgelist)              free(out.edgelist);
 487         if(out.edgemarkerlist)        free(out.edgemarkerlist);
 488         if(out.normlist)              free(out.normlist);
 489
 490         free(NodeTable);
 491         return 0;
 492 }
 493
 494 void EdgeOnSide(int *v, int *edge, int *border)
 495 {
 496         int R;
 497         int k0, k1, N;
 498         float Ndv;
 499
 500         border[0] = -1;
 501
 502         if( (v[0] <= NV) && (v[1] <= NV) )
 503         {
 504                 edge[0]   = 0;
 505                 border[0] = 0;
 506         }
 507         if( (v[1] <= NV) && (v[2] <= NV) )
 508         {
 509                 edge[0]   = 1;
 510                 border[0] = 0;
 511         }
 512         if( (v[2] <= NV) && (v[0] <= NV) )
 513         {
 514                 edge[0]   = 2;
 515                 border[0] = 0;
 516         }
 517
 518         R = NH*NVP1;
 519
 520         if( (v[0] >= R) && (v[1] >= R) )
 521         {
 522                 edge[0]   = 0;
 523                 border[0] = 1;
 524         }
 525         if( (v[1] >= R) && (v[2] >= R) )
 526         {
 527                 edge[0]   = 1;
 528                 border[0] = 1;
 529         }
 530         if( (v[2] >= R) && (v[0] >= R) )
 531         {
 532                 edge[0]   = 2;
 533                 border[0] = 1;
 534         }
 535
 536         if(border[0] >= 0)
 537         {
 538                 k0  = edge[0];
 539                 k1  = (k0+1) % 3;
 540                 N   = Absolute(v[k0] - v[k1]);
 541                 Ndv = (float)(N*dv);
 542         }
 543         if( ((v[0] % NVP1) == 0)  && ((v[1] % NVP1) == 0) )
 544         {
 545                 if(border[0] >= 0)
 546                         if( Ndv > (Absolute(v[0] - v[1])*dh)) return;
 547                 edge[0]   = 0;
 548                 border[0] = 2;
 549                 return;
 550         }
 551         if( ((v[1] % NVP1) == 0)  && ((v[2] % NVP1) == 0) )
 552         {
 553                 if(border[0] >= 0)
 554                         if( Ndv > (Absolute(v[1] - v[2])*dh)) return;
 555                 edge[0]   = 1;
 556                 border[0] = 2;
 557                 return;
 558         }
 559         if( ((v[2] % NVP1) == 0)  && ((v[0] % NVP1) == 0) )
 560         {
 561                 if(border[0] >= 0)
 562                         if( Ndv > (Absolute(v[2] - v[0])*dh)) return;
 563                 edge[0]   = 2;
 564                 border[0] = 2;
 565                 return;
 566         }
 567
 568         if( ((v[0] % NVP1) == NV) && ((v[1] % NVP1) == NV) )
 569         {
 570                 if(border[0] >= 0)
 571                         if( Ndv > (Absolute(v[0] - v[1])*dh)) return;
 572                 edge[0]   = 0;
 573                 border[0] = 3;
 574                 return;
 575         }
 576         if( ((v[1] % NVP1) == NV) && ((v[2] % NVP1) == NV) )
 577         {
 578                 if(border[0] >= 0)
 579                         if( Ndv > (Absolute(v[1] - v[2])*dh)) return;
 580                 edge[0]   = 1;
 581                 border[0] = 3;
 582                 return;
 583         }
 584         if( ((v[2] % NVP1) == NV) && ((v[0] % NVP1) == NV) )
 585         {
 586                 if(border[0] >= 0)
 587                         if( Ndv > (Absolute(v[2] - v[0])*dh)) return;
 588                 edge[0]   = 2;
 589                 border[0] = 3;
 590                 return;
 591         }
 592         return;
 593 }
 594
 595 void CalcAngles(NODE *node, int *v, float *angle)
 596 {
 597         int i, j, k;
 598         vec l;
 599         vec x0, x1, x2, y0, y1, y2;
 600         vec2 vv[3];
 601         vec dot;
 602
 603         switch(Plane)
 604         {
 605         case PLANE_XZ0:
 606         case PLANE_XZ1:
 607                 i = 0;
 608                 j = 2;
 609                 break;
 610         case PLANE_YZ0:
 611         case PLANE_YZ1:
 612                 i = 1;
 613                 j = 2;
 614                 break;
 615         default:
 616                 i = 0;
 617                 j = 1;
 618         }
 619         x0 = node[v[0]].p[i];
 620         x1 = node[v[1]].p[i];
 621         x2 = node[v[2]].p[i];
 622         y0 = node[v[0]].p[j];
 623         y1 = node[v[1]].p[j];
 624         y2 = node[v[2]].p[j];
 625
 626         vv[0][0] = x1-x0;
 627         vv[0][1] = y1-y0;
 628         vv[1][0] = x2-x1;
 629         vv[1][1] = y2-y1;
 630         vv[2][0] = x0-x2;
 631         vv[2][1] = y0-y2;
 632
 633         for(k=0; k<3; k++)
 634         {
 635                 l = (vec)(sqrt( vv[k][0]*vv[k][0] + vv[k][1]*vv[k][1] ));
 636                 if(l > 0.)
 637                 {
 638                         vv[k][0] /= l;
 639                         vv[k][1] /= l;
 640                 }
 641         }
 642
 643         dot = -(vv[0][0]*vv[2][0] + vv[0][1]*vv[2][1]);
 644         angle[0] = (float)(acos(dot));
 645         dot = -(vv[1][0]*vv[0][0] + vv[1][1]*vv[0][1]);
 646         angle[1] = (float)(acos(dot));
 647         dot = -(vv[2][0]*vv[1][0] + vv[2][1]*vv[1][1]);
 648         angle[2] = (float)(acos(dot));
 649 }
 650 //=================================================================
 651 int Bisect(NODE *node, int border, int j0, int j1)
 652 {
 653         int k;
 654
 655         switch(border)
 656         {
 657         case 0:
 658                 k = (j0+j1)/2;
 659                 break;
 660         case 1:
 661                 k = (j0+j1)/2;
 662                 break;
 663         case 2:
 664                 k = (int)((j0+j1)/(2*NVP1)) * NVP1;
 665                 break;
 666         case 3:
 667                 k = (int)((j0+j1+2)/(2*NVP1)) * NVP1 - 1;
 668                 break;
 669         }
 670         return( ((k != j0) && (k != j1)) ? k : 0 );
 671 }
 672 //=================================================================
 673 int compare(TRITABLE *t1, TRITABLE *t2)
 674 {
 675         if(t1->error > t2->error) return -1;
 676         if(t1->error < t2->error) return  1;
 677         return 0;
 678 }
 679
 680 void MakeBrushes(int NumTris, NODE *Node, TRI *Tri,bool surf,
 681                                  int offset,char *texture0, char *texture1, char *texture2)
 682 {
 683         extern double backface;
 684         BRUSH   brush;
 685         int             contents;
 686         int             i, j;
 687         float   Steep;
 688         vec3_t  PlaneNormal,SurfNormal;
 689         bool    CheckAngle;
 690         vec3_t  t[2];
 691
 692         // if texture2 is identical to texture0, there's no need to
 693         // check surface angle
 694         if(!g_strcasecmp(texture0,texture2) || !strlen(texture2))
 695                 CheckAngle = FALSE;
 696         else
 697         {
 698                 CheckAngle = TRUE;
 699                 Steep = (float)cos((double)SlantAngle/57.2957795);
 700                 switch(Plane)
 701                 {
 702                 case PLANE_XY0: PlaneNormal[0]= 0.;PlaneNormal[1]= 0.;PlaneNormal[2]= 1.;break;
 703                 case PLANE_XY1: PlaneNormal[0]= 0.;PlaneNormal[1]= 0.;PlaneNormal[2]=-1.;break;
 704                 case PLANE_XZ0: PlaneNormal[0]= 0.;PlaneNormal[1]= 1.;PlaneNormal[2]= 1.;break;
 705                 case PLANE_XZ1: PlaneNormal[0]= 0.;PlaneNormal[1]=-1.;PlaneNormal[2]= 1.;break;
 706                 case PLANE_YZ0: PlaneNormal[0]= 1.;PlaneNormal[1]= 0.;PlaneNormal[2]= 1.;break;
 707                 case PLANE_YZ1: PlaneNormal[0]=-1.;PlaneNormal[1]= 0.;PlaneNormal[2]= 1.;break;
 708                 }
 709         }
 710
 711         contents = 0;
 712         if(surf)
 713         {
 714                 if(UseDetail) contents += CONTENTS_DETAIL;
 715                 if(UseLadder) contents += CONTENTS_LADDER;
 716         }
 717
 718         OpenFuncGroup();
 719         for(i=0; i<NumTris; i++)
 720         {
 721                 brush.Number   = i;
 722                 brush.NumFaces = 5;
 723                 // front
 724                 brush.face[0].v[0][0] = Node[Tri[i].v[0]].p[0];
 725                 brush.face[0].v[0][1] = Node[Tri[i].v[0]].p[1];
 726                 brush.face[0].v[0][2] = Node[Tri[i].v[0]].p[2];
 727
 728                 brush.face[0].v[1][0] = Node[Tri[i].v[2]].p[0];
 729                 brush.face[0].v[1][1] = Node[Tri[i].v[2]].p[1];
 730                 brush.face[0].v[1][2] = Node[Tri[i].v[2]].p[2];
 731
 732                 brush.face[0].v[2][0] = Node[Tri[i].v[1]].p[0];
 733                 brush.face[0].v[2][1] = Node[Tri[i].v[1]].p[1];
 734                 brush.face[0].v[2][2] = Node[Tri[i].v[1]].p[2];
 735
 736                 if(offset != 0)
 737                 {
 738                         switch(Plane)
 739                         {
 740                         case PLANE_XY0:
 741                                 brush.face[0].v[0][2] += offset;
 742                                 brush.face[0].v[1][2] += offset;
 743                                 brush.face[0].v[1][2] += offset;
 744                                 break;
 745                         case PLANE_XY1:
 746                                 brush.face[0].v[0][2] -= offset;
 747                                 brush.face[0].v[1][2] -= offset;
 748                                 brush.face[0].v[1][2] -= offset;
 749                                 break;
 750                         case PLANE_XZ0:
 751                                 brush.face[0].v[0][1] += offset;
 752                                 brush.face[0].v[1][1] += offset;
 753                                 brush.face[0].v[1][1] += offset;
 754                                 break;
 755                         case PLANE_XZ1:
 756                                 brush.face[0].v[0][1] -= offset;
 757                                 brush.face[0].v[1][1] -= offset;
 758                                 brush.face[0].v[1][1] -= offset;
 759                                 break;
 760                         case PLANE_YZ0:
 761                                 brush.face[0].v[0][0] += offset;
 762                                 brush.face[0].v[1][0] += offset;
 763                                 brush.face[0].v[1][0] += offset;
 764                                 break;
 765                         case PLANE_YZ1:
 766                                 brush.face[0].v[0][0] -= offset;
 767                                 brush.face[0].v[1][0] -= offset;
 768                                 brush.face[0].v[1][0] -= offset;
 769                                 break;
 770                         }
 771                 }
 772                 switch(Plane)
 773                 {
 774                 case PLANE_XZ0:
 775                 case PLANE_XZ1:
 776                         // back
 777                         brush.face[1].v[0][0] = Node[Tri[i].v[0]].p[0];
 778                         brush.face[1].v[0][1] = (float)backface;
 779                         brush.face[1].v[0][2] = Node[Tri[i].v[0]].p[2];
 780
 781                         brush.face[1].v[1][0] = Node[Tri[i].v[1]].p[0];
 782                         brush.face[1].v[1][1] = (float)backface;
 783                         brush.face[1].v[1][2] = Node[Tri[i].v[1]].p[2];
 784
 785                         brush.face[1].v[2][0] = Node[Tri[i].v[2]].p[0];
 786                         brush.face[1].v[2][1] = (float)backface;
 787                         brush.face[1].v[2][2] = Node[Tri[i].v[2]].p[2];
 788
 789                         // 0-1 side
 790                         brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
 791                         brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
 792                         brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
 793
 794                         brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
 795                         brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
 796                         brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
 797
 798                         brush.face[2].v[2][0] = Node[Tri[i].v[1]].p[0];
 799                         brush.face[2].v[2][1] = (float)backface;
 800                         brush.face[2].v[2][2] = Node[Tri[i].v[1]].p[2];
 801
 802                         // 1-2 side
 803                         brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
 804                         brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
 805                         brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
 806
 807                         brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
 808                         brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
 809                         brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
 810
 811                         brush.face[3].v[2][0] = Node[Tri[i].v[2]].p[0];
 812                         brush.face[3].v[2][1] = (float)backface;
 813                         brush.face[3].v[2][2] = Node[Tri[i].v[2]].p[2];
 814
 815                         // 2-0 side
 816                         brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
 817                         brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
 818                         brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
 819
 820                         brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
 821                         brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
 822                         brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
 823
 824                         brush.face[4].v[2][0] = Node[Tri[i].v[0]].p[0];
 825                         brush.face[4].v[2][1] = (float)backface;
 826                         brush.face[4].v[2][2] = Node[Tri[i].v[0]].p[2];
 827                         break;
 828                 case PLANE_YZ0:
 829                 case PLANE_YZ1:
 830                         // back
 831                         brush.face[1].v[0][0] = (float)backface;
 832                         brush.face[1].v[0][1] = Node[Tri[i].v[0]].p[1];
 833                         brush.face[1].v[0][2] = Node[Tri[i].v[0]].p[2];
 834
 835                         brush.face[1].v[1][0] = (float)backface;
 836                         brush.face[1].v[1][1] = Node[Tri[i].v[1]].p[1];
 837                         brush.face[1].v[1][2] = Node[Tri[i].v[1]].p[2];
 838
 839                         brush.face[1].v[2][0] = (float)backface;
 840                         brush.face[1].v[2][1] = Node[Tri[i].v[2]].p[1];
 841                         brush.face[1].v[2][2] = Node[Tri[i].v[2]].p[2];
 842
 843                         // 0-1 side
 844                         brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
 845                         brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
 846                         brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
 847
 848                         brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
 849                         brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
 850                         brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
 851
 852                         brush.face[2].v[2][0] = (float)backface;
 853                         brush.face[2].v[2][1] = Node[Tri[i].v[1]].p[1];
 854                         brush.face[2].v[2][2] = Node[Tri[i].v[1]].p[2];
 855
 856                         // 1-2 side
 857                         brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
 858                         brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
 859                         brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
 860
 861                         brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
 862                         brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
 863                         brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
 864
 865                         brush.face[3].v[2][0] = (float)backface;
 866                         brush.face[3].v[2][1] = Node[Tri[i].v[2]].p[1];
 867                         brush.face[3].v[2][2] = Node[Tri[i].v[2]].p[2];
 868
 869                         // 2-0 side
 870                         brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
 871                         brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
 872                         brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
 873
 874                         brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
 875                         brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
 876                         brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
 877
 878                         brush.face[4].v[2][0] = (float)backface;
 879                         brush.face[4].v[2][1] = Node[Tri[i].v[0]].p[1];
 880                         brush.face[4].v[2][2] = Node[Tri[i].v[0]].p[2];
 881                         break;
 882                 default:
 883                         // back
 884                         brush.face[1].v[0][0] = Node[Tri[i].v[0]].p[0];
 885                         brush.face[1].v[0][1] = Node[Tri[i].v[0]].p[1];
 886                         brush.face[1].v[0][2] = (float)backface;
 887
 888                         brush.face[1].v[1][0] = Node[Tri[i].v[1]].p[0];
 889                         brush.face[1].v[1][1] = Node[Tri[i].v[1]].p[1];
 890                         brush.face[1].v[1][2] = (float)backface;
 891
 892                         brush.face[1].v[2][0] = Node[Tri[i].v[2]].p[0];
 893                         brush.face[1].v[2][1] = Node[Tri[i].v[2]].p[1];
 894                         brush.face[1].v[2][2] = (float)backface;
 895
 896                         // 0-1 side
 897                         brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
 898                         brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
 899                         brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
 900
 901                         brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
 902                         brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
 903                         brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
 904
 905                         brush.face[2].v[2][0] = Node[Tri[i].v[1]].p[0];
 906                         brush.face[2].v[2][1] = Node[Tri[i].v[1]].p[1];
 907                         brush.face[2].v[2][2] = (float)backface;
 908
 909                         // 1-2 side
 910                         brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
 911                         brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
 912                         brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
 913
 914                         brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
 915                         brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
 916                         brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
 917
 918                         brush.face[3].v[2][0] = Node[Tri[i].v[2]].p[0];
 919                         brush.face[3].v[2][1] = Node[Tri[i].v[2]].p[1];
 920                         brush.face[3].v[2][2] = (float)backface;
 921
 922                         // 2-0 side
 923                         brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
 924                         brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
 925                         brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
 926
 927                         brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
 928                         brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
 929                         brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
 930
 931                         brush.face[4].v[2][0] = Node[Tri[i].v[0]].p[0];
 932                         brush.face[4].v[2][1] = Node[Tri[i].v[0]].p[1];
 933                         brush.face[4].v[2][2] = (float)backface;
 934                 }
 935
 936                 for(j=0; j<5; j++)
 937                 {
 938                         strcpy(brush.face[j].texture,
 939                                 (strlen(texture1) ? texture1 : texture0));
 940                         brush.face[j].Shift[0] = (float)TexOffset[0];
 941                         brush.face[j].Shift[1] = (float)TexOffset[1];
 942                         brush.face[j].Rotate   = 0.;
 943                         brush.face[j].Scale[0] = (float)TexScale[0];
 944                         brush.face[j].Scale[1] = (float)TexScale[1];
 945                         brush.face[j].Contents = contents;
 946                         if(surf)
 947                                 brush.face[j].Surface = 0;
 948                         else
 949                                 brush.face[j].Surface = SURF_HINT;
 950                         brush.face[j].Value    = 0;
 951                 }
 952
 953                 if(CheckAngle)
 954                 {
 955                         XYZVectorSubtract(brush.face[0].v[2],brush.face[0].v[0],t[0]);
 956                         XYZVectorSubtract(brush.face[0].v[1],brush.face[0].v[2],t[1]);
 957                         CrossProduct(t[0],t[1],SurfNormal);
 958                         VectorNormalize(SurfNormal,SurfNormal);
 959                         if(DotProduct(SurfNormal,PlaneNormal) < Steep)
 960                                 strcpy(brush.face[0].texture,texture2);
 961                         else
 962                                 strcpy(brush.face[0].texture,texture0);
 963                 }
 964                 else
 965                         strcpy(brush.face[0].texture,texture0);
 966
 967                 if(surf) brush.face[0].Value    = ArghRad2;
 968                 MakeBrush(&brush);
 969         }
 970         CloseFuncGroup();
 971
 972 } // end MakeBrushes
 973 //=================================================================
 974 void MapOut(int NumNodes,int NumTris, NODE *Node, TRI *Tri)
 975 {
 976         extern  double backface;
 977         extern  double xmin, xmax, ymin, ymax, zmin, zmax;
 978         BRUSH   brush;
 979         char    hint[32], skip[32];
 980         int             i, j;
 981         int             face;
 982         /*
 983         ghCursorCurrent = LoadCursor(NULL,IDC_WAIT);
 984         SetCursor(ghCursorCurrent);
 985         */
 986         UseDetail = 1; // this is temporary
 987         MakeBrushes(NumTris,Node,Tri,TRUE,0,Texture[Game][0],Texture[Game][1],Texture[Game][2]);
 988
 989         if(AddHints || GimpHints)
 990         {
 991                 switch(Game)
 992                 {
 993                 case SIN:
 994                         strcpy(hint,"generic/misc/hint");
 995                         strcpy(skip,"generic/misc/skip");
 996                         break;
 997                 case HALFLIFE:
 998                         strcpy(hint,"HINT");
 999                         strcpy(skip,"HINT");
1000                         break;
1001                 case HERETIC2:
1002                         strcpy(hint,"general/hint");
1003                         strcpy(skip,"general/skip");
1004                         break;
1005                 case KINGPIN:
1006                         strcpy(hint,"common/0_hint");
1007                         strcpy(skip,"common/0_skip");
1008                         break;
1009                 case QUAKE3:
1010                         strcpy(hint,"common/hint");
1011                         strcpy(skip,"common/skip");
1012                         break;
1013                 default:
1014                         strcpy(hint,"e1u1/hint");
1015                         strcpy(skip,"e1u1/skip");
1016                 }
1017         }
1018
1019         if( GimpHints )
1020                 MakeBrushes(NumTris,Node,Tri,FALSE,HINT_OFFSET,hint,hint,hint);
1021
1022         if( AddHints==1 )
1023         {
1024                 int   j0, j1, j2, k, k0, k1;
1025                 int   q[4];
1026                 int   w,h,h0,h1,t,OK;
1027                 float s[3];
1028                 double front;
1029                 int   MaxHints; // We don't want a whole slew of hint brushes, which we'd get
1030                                 // with low decimation values and our current placement scheme.
1031                                 // Limit number of hint brushes to number of undecimated grid
1032                                 // squares.
1033
1034                 switch(Plane)
1035                 {
1036                 case PLANE_XY1:
1037                         front  = LessThan(zmin,32.);
1038                         break;
1039                 case PLANE_XZ0:
1040                         front  = MoreThan(ymax,32.);
1041                         break;
1042                 case PLANE_XZ1:
1043                         front  = LessThan(ymin,32.);
1044                         break;
1045                 case PLANE_YZ0:
1046                         front  = MoreThan(xmax,32.);
1047                         break;
1048                 case PLANE_YZ1:
1049                         front  = LessThan(xmin,32.);
1050                         break;
1051                 default:
1052                         front  = MoreThan(zmax,32.);
1053                 }
1054
1055                 for(i=0; i<NumTris; i++)
1056                         Tri[i].flag = 0;
1057
1058                 switch(Plane)
1059                 {
1060                 case PLANE_XZ0:
1061                 case PLANE_XZ1:
1062                         j0 = 1;
1063                         j1 = 0;
1064                         j2 = 2;
1065                         break;
1066                 case PLANE_YZ0:
1067                 case PLANE_YZ1:
1068                         j0 = 0;
1069                         j1 = 1;
1070                         j2 = 2;
1071                         break;
1072                 default:
1073                         j0 = 2;
1074                         j1 = 0;
1075                         j2 = 1;
1076                 }
1077
1078                 brush.Number = 0;
1079                 brush.NumFaces = 6;
1080                 MaxHints = NH*NV-1;
1081                 for(w=1; w<min(16,NH) && brush.Number < MaxHints; w++)
1082                 {
1083                         for(h=max(1,w/2); h<min(16,NV) && brush.Number < MaxHints; h++)
1084                         {
1085                                 for(i=0; i<=NH-w && brush.Number < MaxHints; i++)
1086                                 {
1087                                         for(j=0; j<=NV-h && brush.Number < MaxHints; j++)
1088                                         {
1089                                                 q[0] = i*NVP1+j;
1090                                                 q[2] = q[0] + w*NVP1 + h;
1091                                                 switch(Plane)
1092                                                 {
1093                                                 case PLANE_XY1:
1094                                                 case PLANE_XZ0:
1095                                                 case PLANE_YZ1:
1096                                                         q[1] = q[0] + h;
1097                                                         q[3] = q[2] - h;
1098                                                         break;
1099                                                 default:
1100                                                         q[1] = q[2] - h;
1101                                                         q[3] = q[0] + h;
1102                                                 }
1103                                                 for(k=0, OK=1; k<NumTris && OK; k++)
1104                                                 {
1105                                                         if(Tri[k].min[j1] >= max(Node[q[0]].p[j1],Node[q[2]].p[j1])) continue;
1106                                                         if(Tri[k].min[j2] >= max(Node[q[0]].p[j2],Node[q[2]].p[j2])) continue;
1107                                                         if(Tri[k].max[j1] <= min(Node[q[0]].p[j1],Node[q[2]].p[j1])) continue;
1108                                                         if(Tri[k].max[j2] <= min(Node[q[0]].p[j2],Node[q[2]].p[j2])) continue;
1109
1110                                                         for(h0=0; h0<4 && OK; h0++)
1111                                                         {
1112                                                                 h1 = (h0+1)%4;
1113                                                                 for(t=0; t<3 && OK; t++)
1114                                                                 {
1115                                                                         s[t] = side(Node[q[h0]].p[j1],Node[q[h0]].p[j2],
1116                                                                                 Node[q[h1]].p[j1],Node[q[h1]].p[j2],
1117                                                                                 Node[Tri[k].v[t]].p[j1],Node[Tri[k].v[t]].p[j2]);
1118                                                                 }
1119                                                                 if((s[1] > 0 || s[2] > 0) && s[0] < 0) OK=0;
1120                                                                 if((s[2] > 0 || s[0] > 0) && s[1] < 0) OK=0;
1121                                                                 if((s[0] > 0 || s[1] > 0) && s[2] < 0) OK=0;
1122                                                         }
1123                                                 }
1124                                                 if(!OK) continue;
1125                                                 switch(Plane)
1126                                                 {
1127                                                 case PLANE_XZ0:
1128                                                 case PLANE_XZ1:
1129                                                         // front
1130                                                         brush.face[0].v[0][0] = Node[q[2]].p[0];
1131                                                         brush.face[0].v[0][1] = (float)front;
1132                                                         brush.face[0].v[0][2] = Node[q[2]].p[2];
1133
1134                                                         brush.face[0].v[1][0] = Node[q[1]].p[0];
1135                                                         brush.face[0].v[1][1] = (float)front;
1136                                                         brush.face[0].v[1][2] = Node[q[1]].p[2];
1137
1138                                                         brush.face[0].v[2][0] = Node[q[0]].p[0];
1139                                                         brush.face[0].v[2][1] = (float)front;
1140                                                         brush.face[0].v[2][2] = Node[q[0]].p[2];
1141
1142                                                         // back
1143                                                         brush.face[1].v[0][0] = Node[q[0]].p[0];
1144                                                         brush.face[1].v[0][1] = (float)backface;
1145                                                         brush.face[1].v[0][2] = Node[q[0]].p[2];
1146
1147                                                         brush.face[1].v[1][0] = Node[q[1]].p[0];
1148                                                         brush.face[1].v[1][1] = (float)backface;
1149                                                         brush.face[1].v[1][2] = Node[q[1]].p[2];
1150
1151                                                         brush.face[1].v[2][0] = Node[q[2]].p[0];
1152                                                         brush.face[1].v[2][1] = (float)backface;
1153                                                         brush.face[1].v[2][2] = Node[q[2]].p[2];
1154
1155                                                         for(k0=0; k0<brush.NumFaces-2; k0++)
1156                                                         {
1157                                                                 k =k0+2;
1158                                                                 k1=(k0+1) % (brush.NumFaces-2);
1159
1160                                                                 brush.face[k].v[0][0] = Node[q[k0]].p[0];
1161                                                                 brush.face[k].v[0][1] = (float)front;
1162                                                                 brush.face[k].v[0][2] = Node[q[k0]].p[2];
1163
1164                                                                 brush.face[k].v[1][0] = Node[q[k1]].p[0];
1165                                                                 brush.face[k].v[1][1] = (float)front;
1166                                                                 brush.face[k].v[1][2] = Node[q[k1]].p[2];
1167
1168                                                                 brush.face[k].v[2][0] = Node[q[k1]].p[0];
1169                                                                 brush.face[k].v[2][1] = (float)backface;
1170                                                                 brush.face[k].v[2][2] = Node[q[k1]].p[2];
1171                                                         }
1172                                                         break;
1173                                                 case PLANE_YZ0:
1174                                                 case PLANE_YZ1:
1175                                                         // front
1176                                                         brush.face[0].v[0][0] = (float)front;
1177                                                         brush.face[0].v[0][1] = Node[q[2]].p[1];
1178                                                         brush.face[0].v[0][2] = Node[q[2]].p[2];
1179
1180                                                         brush.face[0].v[1][0] = (float)front;
1181                                                         brush.face[0].v[1][1] = Node[q[1]].p[1];
1182                                                         brush.face[0].v[1][2] = Node[q[1]].p[2];
1183
1184                                                         brush.face[0].v[2][0] = (float)front;
1185                                                         brush.face[0].v[2][1] = Node[q[0]].p[1];
1186                                                         brush.face[0].v[2][2] = Node[q[0]].p[2];
1187
1188                                                         // back
1189                                                         brush.face[1].v[0][0] = (float)backface;
1190                                                         brush.face[1].v[0][1] = Node[q[0]].p[1];
1191                                                         brush.face[1].v[0][2] = Node[q[0]].p[2];
1192
1193                                                         brush.face[1].v[1][0] = (float)backface;
1194                                                         brush.face[1].v[1][1] = Node[q[1]].p[1];
1195                                                         brush.face[1].v[1][2] = Node[q[1]].p[2];
1196
1197                                                         brush.face[1].v[2][0] = (float)backface;
1198                                                         brush.face[1].v[2][1] = Node[q[2]].p[1];
1199                                                         brush.face[1].v[2][2] = Node[q[2]].p[2];
1200
1201                                                         for(k0=0; k0<brush.NumFaces-2; k0++)
1202                                                         {
1203                                                                 k =k0+2;
1204                                                                 k1=(k0+1) % (brush.NumFaces-2);
1205
1206                                                                 brush.face[k].v[0][0] = (float)front;
1207                                                                 brush.face[k].v[0][1] = Node[q[k0]].p[1];
1208                                                                 brush.face[k].v[0][2] = Node[q[k0]].p[2];
1209
1210                                                                 brush.face[k].v[1][0] = (float)front;
1211                                                                 brush.face[k].v[1][1] = Node[q[k1]].p[1];
1212                                                                 brush.face[k].v[1][2] = Node[q[k1]].p[2];
1213
1214                                                                 brush.face[k].v[2][0] = (float)backface;
1215                                                                 brush.face[k].v[2][1] = Node[q[k1]].p[1];
1216                                                                 brush.face[k].v[2][2] = Node[q[k1]].p[2];
1217                                                         }
1218                                                         break;
1219                                                 default:
1220                                                         // front
1221                                                         brush.face[0].v[0][0] = Node[q[2]].p[0];
1222                                                         brush.face[0].v[0][1] = Node[q[2]].p[1];
1223                                                         brush.face[0].v[0][2] = (float)front;
1224
1225                                                         brush.face[0].v[1][0] = Node[q[1]].p[0];
1226                                                         brush.face[0].v[1][1] = Node[q[1]].p[1];
1227                                                         brush.face[0].v[1][2] = (float)front;
1228
1229                                                         brush.face[0].v[2][0] = Node[q[0]].p[0];
1230                                                         brush.face[0].v[2][1] = Node[q[0]].p[1];
1231                                                         brush.face[0].v[2][2] = (float)front;
1232
1233                                                         // back
1234                                                         brush.face[1].v[0][0] = Node[q[0]].p[0];
1235                                                         brush.face[1].v[0][1] = Node[q[0]].p[1];
1236                                                         brush.face[1].v[0][2] = (float)backface;
1237
1238                                                         brush.face[1].v[1][0] = Node[q[1]].p[0];
1239                                                         brush.face[1].v[1][1] = Node[q[1]].p[1];
1240                                                         brush.face[1].v[1][2] = (float)backface;
1241
1242                                                         brush.face[1].v[2][0] = Node[q[2]].p[0];
1243                                                         brush.face[1].v[2][1] = Node[q[2]].p[1];
1244                                                         brush.face[1].v[2][2] = (float)backface;
1245
1246                                                         for(k0=0; k0<brush.NumFaces-2; k0++)
1247                                                         {
1248                                                                 k =k0+2;
1249                                                                 k1=(k0+1) % (brush.NumFaces-2);
1250
1251                                                                 brush.face[k].v[0][0] = Node[q[k0]].p[0];
1252                                                                 brush.face[k].v[0][1] = Node[q[k0]].p[1];
1253                                                                 brush.face[k].v[0][2] = (float)front;
1254
1255                                                                 brush.face[k].v[1][0] = Node[q[k1]].p[0];
1256                                                                 brush.face[k].v[1][1] = Node[q[k1]].p[1];
1257                                                                 brush.face[k].v[1][2] = (float)front;
1258
1259                                                                 brush.face[k].v[2][0] = Node[q[k1]].p[0];
1260                                                                 brush.face[k].v[2][1] = Node[q[k1]].p[1];
1261                                                                 brush.face[k].v[2][2] = (float)backface;
1262                                                         }
1263                                                         break;
1264                                                 } // switch (Plane)
1265                                                 for(face=0; face<6; face++)
1266                                                 {
1267                                                         strcpy(brush.face[face].texture,(face<=1 ? skip : hint));
1268                                                         brush.face[face].Shift[0] = 0;
1269                                                         brush.face[face].Shift[1] = 0;
1270                                                         brush.face[face].Rotate   = 0.;
1271                                                         brush.face[face].Scale[0] = 1;
1272                                                         brush.face[face].Scale[1] = 1;
1273                                                         brush.face[face].Contents = CONTENTS_DETAIL;
1274                                                         brush.face[face].Surface  = (face<=1 ? SURF_SKIP : SURF_HINT);
1275                                                         brush.face[face].Value    = 0;
1276                                                 }
1277                                                 if(!brush.Number) OpenFuncGroup();
1278                                                 MakeBrush(&brush);
1279                                                 brush.Number++;
1280                                         } // for(j=
1281                                 }     // for(i=
1282                         }         // for(h=
1283                 }             // for(w=
1284                 if(brush.Number) CloseFuncGroup();
1285         }
1286         /*
1287         ghCursorCurrent = ghCursorDefault;
1288         SetCursor(ghCursorCurrent);
1289         */
1290 }
1291 //===========================================================================
1292 int CheckBorders(int *NumNodesUsed, int NumNodes, NODE *Node, int *NumTris, TRI **pTri)
1293 {
1294         int border;
1295         int i, j, k0, k1, N;
1296         float angle[3];
1297         TRI *Tri;
1298
1299         N = NumNodesUsed[0];
1300         Tri = *pTri;
1301         for(i=0; i<NumTris[0]; i++)
1302         {
1303                 EdgeOnSide(Tri[i].v,&k0,&border);
1304                 if(border < 0) continue;
1305                 CalcAngles(Node, Tri[i].v, angle);
1306                 k1 = (k0+1) % 3;
1307                 if((angle[k0] < SLIVER_ANGLE) || (angle[k1] < SLIVER_ANGLE))
1308                 {
1309                         j = Bisect(Node, border, Tri[i].v[k0], Tri[i].v[k1]);
1310                         if(j >= 0)
1311                         {
1312                                 if(!Node[j].used)    // Shouldn't be used, but...
1313                                 {
1314                                         NumNodesUsed[0]++;
1315                                         Node[j].used++;
1316                                 }
1317                         }
1318                 }
1319         }
1320         if(NumNodesUsed[0] > N)
1321         {
1322                 free(*pTri);
1323                 tricall(NumNodes, Node, NumTris, NULL, pTri, "cnzBNPY");
1324                 Tri = *pTri;
1325         }
1326         return (NumNodesUsed[0] - N);
1327 }