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