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