contrib/gtkgensurf/dec.cpp

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