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