2 GenSurf plugin for GtkRadiant
3 Copyright (C) 2001 David Hyde, Loki software and qeradiant.com
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.
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.
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
23 #else /* not SINGLE */
25 #endif /* not SINGLE */
42 #define Absolute( a ) ( ( a ) >= 0.0 ? ( a ) : -( a ) )
44 void MakeDecimatedMap( int *NumNodes, int *NumTris, NODE **pNode, TRI **pTri ){
45 int compare( TRITABLE *, TRITABLE * );
46 int Bisect( NODE *, int, int, int );
47 void CalcAngles( NODE *, int *, float * );
48 void EdgeOnSide( int *, int *, int * );
49 int tricall( int, NODE *, int *, TRI * *, TRI * *, const char * );
50 int CheckBorders( int *,int,NODE *,int *,TRI * * );
61 if ( Decimate <= 0 ) {
65 ghCursorCurrent = LoadCursor(NULL,IDC_WAIT);
66 SetCursor(ghCursorCurrent);
68 dh = ( Hur - Hll ) / NH;
69 dv = ( Vur - Vll ) / NV;
72 NumNodes[0] = ( NH + 1 ) * ( NVP1 );
73 *pNode = (NODE *) malloc( NumNodes[0] * sizeof( NODE ) );
75 memset( Node,0,NumNodes[0] * sizeof( NODE ) );
77 // Copy [NH][NV] vertex array to our working node array
78 for ( i = 0,N = 0; i <= NH; i++ )
80 for ( j = 0; j <= NV; j++, N++ )
82 Node[N].p[0] = (float)xyz[i][j].p[0];
83 Node[N].p[1] = (float)xyz[i][j].p[1];
84 Node[N].p[2] = (float)xyz[i][j].p[2];
85 Node[N].fixed = xyz[i][j].fixed;
88 // Start things off with the corner values
91 Node[NH * NVP1].used = 1;
92 Node[NH * NVP1 + NV].used = 1;
94 tricall( NumNodes[0], Node, NumTris, NULL, pTri, "cnzBNPY" );
97 // Which coordinates are we triangulating on?
118 // TriTable stores the largest error in a triangle and the node where that
120 TriTable = (TRITABLE *) malloc( NH * NV * 2 * sizeof( TRITABLE ) );
121 NumNodesToSave = min( NumNodes[0], (int)( 0.01 * ( 100 - Decimate ) * ( NumNodes[0] - NumNodesUsed ) + NumNodesUsed ) );
123 while ( NumNodesUsed < NumNodesToSave )
125 for ( i = 0; i < NumTris[0]; i++ )
128 // For every node that's not currently used, find what triangle it
129 // lies on, and the error at this node
130 for ( i = 0, biggesterror = 0; i < NumNodes[0]; i++ )
132 if ( Node[i].used ) {
135 for ( j = 0, Node[i].tri = -1; ( j < NumTris[0] ) && ( Node[i].tri == -1 ); j++ )
137 if ( side( Node[i].p[j1], Node[i].p[j2],
138 Node[Tri[j].v[0]].p[j1],Node[Tri[j].v[0]].p[j2],
139 Node[Tri[j].v[1]].p[j1],Node[Tri[j].v[1]].p[j2] ) < 0. ) {
142 if ( side( Node[i].p[j1], Node[i].p[j2],
143 Node[Tri[j].v[1]].p[j1],Node[Tri[j].v[1]].p[j2],
144 Node[Tri[j].v[2]].p[j1],Node[Tri[j].v[2]].p[j2] ) < 0. ) {
147 if ( side( Node[i].p[j1], Node[i].p[j2],
148 Node[Tri[j].v[2]].p[j1],Node[Tri[j].v[2]].p[j2],
149 Node[Tri[j].v[0]].p[j1],Node[Tri[j].v[0]].p[j2] ) < 0. ) {
154 if ( Node[i].tri < 0 ) {
156 ghCursorCurrent = ghCursorDefault;
157 SetCursor(ghCursorCurrent);
159 g_FuncTable.m_pfnMessageBox( g_pRadiantWnd,
160 "Error: Couldn't find the triangle bounding a point.",
161 "Decimation Error", eMB_OK, eMB_ICONWARNING );
164 if ( !Tri[Node[i].tri].flag ) {
165 PlaneFromPoints( Node[Tri[Node[i].tri].v[0]].p,
166 Node[Tri[Node[i].tri].v[1]].p,
167 Node[Tri[Node[i].tri].v[2]].p,
168 &Tri[Node[i].tri].plane );
169 Tri[Node[i].tri].flag = 1;
172 Node[i].p[j0] - ( Tri[Node[i].tri].plane.dist -
173 Tri[Node[i].tri].plane.normal[j1] * Node[i].p[j1] -
174 Tri[Node[i].tri].plane.normal[j2] * Node[i].p[j2] ) /
175 Tri[Node[i].tri].plane.normal[j0];
176 biggesterror = max( biggesterror,Absolute( Node[i].error ) );
178 if ( biggesterror == 0 ) {
179 NumNodesToSave = NumNodesUsed;
183 // For all current triangles, build a list of worst-case nodes
184 memset( TriTable,0,NH * NV * 2 * sizeof( TRITABLE ) );
185 for ( i = 0; i < NumNodes[0]; i++ )
187 if ( Node[i].used ) {
190 if ( Absolute( Node[i].error ) > TriTable[Node[i].tri].error ) {
191 TriTable[Node[i].tri].error = (float)( Absolute( Node[i].error ) );
192 TriTable[Node[i].tri].node = i;
195 qsort( (void *)TriTable, (size_t)( NumTris[0] ), sizeof( TRITABLE ), ( int ( * )( const void *, const void * ) )compare );
196 for ( i = 0; i < NumTris[0] && NumNodesUsed < NumNodesToSave && TriTable[i].error > 0.5 * biggesterror; i++ )
198 if ( Node[TriTable[i].node].used ) {
199 continue; // shouldn't happen
202 Node[TriTable[i].node].used++;
205 tricall( NumNodes[0], Node, NumTris, NULL, pTri, "cnzBNPY" );
207 // Sliver-check along borders. Since borders are often linear, the errors
208 // along borders will often be zero, so no new points will be added. This
209 // tends to produce long, thin brushes. For all border triangles, check
210 // that minimum angle isn't less than SLIVER_ANGLE. If it is, add another
212 while ( CheckBorders( &NumNodesUsed,NumNodes[0],Node,NumTris,pTri ) > 0 )
219 // One last time (because we're pessimistic), check border triangles
220 // CheckBorders(&NumNodesUsed,NumNodes[0],Node,NumTris,pTri);
223 // Check that all fixed points are exact. If not, add them to the mix.
224 // First check to see if we have any fixed points that aren't already used.
225 for ( i = 0, N = 0; i < NumNodes[0] && !N; i++ )
227 if ( Node[i].used ) {
230 if ( Node[i].fixed ) {
235 // Zero out the flag member of all triangles, indicating that
236 // the plane equation has not been found.
237 for ( i = 0; i < NumTris[0]; i++ )
240 for ( i = 0; i < NumNodes[0]; i++ )
242 if ( Node[i].used ) {
245 if ( !Node[i].fixed ) {
249 for ( j = 0; j < NumTris[0] && Node[i].tri == -1; j++ )
251 if ( side( Node[i].p[j1], Node[i].p[j2],
252 Node[Tri[j].v[0]].p[j1],Node[Tri[j].v[0]].p[j2],
253 Node[Tri[j].v[1]].p[j1],Node[Tri[j].v[1]].p[j2] ) < 0. ) {
256 if ( side( Node[i].p[j1], Node[i].p[j2],
257 Node[Tri[j].v[1]].p[j1],Node[Tri[j].v[1]].p[j2],
258 Node[Tri[j].v[2]].p[j1],Node[Tri[j].v[2]].p[j2] ) < 0. ) {
261 if ( side( Node[i].p[j1], Node[i].p[j2],
262 Node[Tri[j].v[2]].p[j1],Node[Tri[j].v[2]].p[j2],
263 Node[Tri[j].v[0]].p[j1],Node[Tri[j].v[0]].p[j2] ) < 0. ) {
268 if ( Node[i].tri < 0 ) {
270 ghCursorCurrent = ghCursorDefault;
271 SetCursor(ghCursorCurrent);
273 g_FuncTable.m_pfnMessageBox( g_pRadiantWnd,
274 "Error: Couldn't find the triangle bounding a point.",
275 "Decimation Error", eMB_OK, eMB_ICONWARNING );
278 if ( !Tri[Node[i].tri].flag ) {
279 PlaneFromPoints( Node[Tri[Node[i].tri].v[0]].p,
280 Node[Tri[Node[i].tri].v[1]].p,
281 Node[Tri[Node[i].tri].v[2]].p,
282 &Tri[Node[i].tri].plane );
283 Tri[Node[i].tri].flag = 1;
286 Node[i].p[j0] - ( Tri[Node[i].tri].plane.dist -
287 Tri[Node[i].tri].plane.normal[j1] * Node[i].p[j1] -
288 Tri[Node[i].tri].plane.normal[j2] * Node[i].p[j2] ) /
289 Tri[Node[i].tri].plane.normal[j0];
290 if ( Absolute( Node[i].error ) > 0.5 ) {
294 tricall( NumNodes[0], Node, NumTris, NULL, pTri, "cnzBNPY" );
300 // Swap node orders for surfaces facing down, north or west so that
301 // they are counterclockwise when facing the surface
303 if ( ( Plane == PLANE_XY1 ) || ( Plane == PLANE_XZ0 ) || ( Plane == PLANE_YZ1 ) ) {
304 for ( i = 0; i < NumTris[0]; i++ )
307 Tri[i].v[1] = Tri[i].v[2];
312 // Store bounding box coords
313 for ( i = 0; i < NumTris[0]; i++ )
315 Tri[i].min[0] = Node[Tri[i].v[0]].p[0];
316 Tri[i].min[0] = min( Tri[i].min[0],Node[Tri[i].v[1]].p[0] );
317 Tri[i].min[0] = min( Tri[i].min[0],Node[Tri[i].v[2]].p[0] );
318 Tri[i].min[1] = Node[Tri[i].v[0]].p[1];
319 Tri[i].min[1] = min( Tri[i].min[1],Node[Tri[i].v[1]].p[1] );
320 Tri[i].min[1] = min( Tri[i].min[1],Node[Tri[i].v[2]].p[1] );
321 Tri[i].min[2] = Node[Tri[i].v[0]].p[2];
322 Tri[i].min[2] = min( Tri[i].min[2],Node[Tri[i].v[1]].p[2] );
323 Tri[i].min[2] = min( Tri[i].min[2],Node[Tri[i].v[2]].p[2] );
324 Tri[i].max[0] = Node[Tri[i].v[0]].p[0];
325 Tri[i].max[0] = max( Tri[i].max[0],Node[Tri[i].v[1]].p[0] );
326 Tri[i].max[0] = max( Tri[i].max[0],Node[Tri[i].v[2]].p[0] );
327 Tri[i].max[1] = Node[Tri[i].v[0]].p[1];
328 Tri[i].max[1] = max( Tri[i].max[1],Node[Tri[i].v[1]].p[1] );
329 Tri[i].max[1] = max( Tri[i].max[1],Node[Tri[i].v[2]].p[1] );
330 Tri[i].max[2] = Node[Tri[i].v[0]].p[2];
331 Tri[i].max[2] = max( Tri[i].max[2],Node[Tri[i].v[1]].p[2] );
332 Tri[i].max[2] = max( Tri[i].max[2],Node[Tri[i].v[2]].p[2] );
335 ghCursorCurrent = ghCursorDefault;
336 SetCursor(ghCursorCurrent);
339 /* end MakeDecimatedMap */
341 /*****************************************************************************/
343 /* tricall Takes an array of nodes, spits out an array of triangles */
345 /*****************************************************************************/
346 int tricall( int NumNodes, NODE *Node, int *NumTris, TRI **inTri, TRI **Tri, const char *Options ){
347 struct triangulateio in, out;
353 /* Define input points. */
355 for ( i = 0,NumUsedNodes = 0; i < NumNodes; i++ )
356 if ( Node[i].used ) {
360 memset( &in, 0,sizeof( in ) );
361 memset( &out,0,sizeof( out ) );
363 NodeTable = (int *) malloc( NumUsedNodes * sizeof( int ) );
365 in.numberofpoints = NumUsedNodes;
366 in.numberofpointattributes = 0;
367 in.pointlist = (REAL *) malloc( in.numberofpoints * 2 * sizeof( REAL ) );
368 for ( i = 0,N = 0; i < NumNodes; i++ )
370 if ( Node[i].used ) {
375 in.pointlist[N * 2 ] = Node[i].p[0];
376 in.pointlist[N * 2 + 1] = Node[i].p[2];
380 in.pointlist[N * 2 ] = Node[i].p[1];
381 in.pointlist[N * 2 + 1] = Node[i].p[2];
384 in.pointlist[N * 2 ] = Node[i].p[0];
385 in.pointlist[N * 2 + 1] = Node[i].p[1];
391 in.pointattributelist = (REAL *) NULL;
392 in.pointmarkerlist = (int *) NULL;
394 if ( strstr( Options,"r" ) ) {
396 TriTable = (int *) malloc( NumNodes * sizeof( int ) );
397 for ( i = 0,N = 0; i < NumNodes; i++ )
399 if ( Node[i].used ) {
404 in.numberoftriangles = NumTris[0];
405 in.numberofcorners = 3;
406 in.numberoftriangleattributes = 0;
407 in.trianglelist = (int *) malloc( in.numberofcorners * in.numberoftriangles * sizeof( int ) );
408 in.triangleattributelist = (REAL *) NULL;
409 in.trianglearealist = (REAL *) NULL;
411 for ( i = 0; i < in.numberoftriangles; i++ )
413 in.trianglelist[i * in.numberofcorners ] = TriTable[ptri[i].v[0]];
414 in.trianglelist[i * in.numberofcorners + 1] = TriTable[ptri[i].v[1]];
415 in.trianglelist[i * in.numberofcorners + 2] = TriTable[ptri[i].v[2]];
421 in.numberoftriangles = 0;
422 in.numberofcorners = 3;
423 in.numberoftriangleattributes = 0;
424 in.trianglelist = (int *) NULL;
425 in.triangleattributelist = (REAL *) NULL;
426 in.trianglearealist = (REAL *) NULL;
429 in.numberofsegments = 0;
430 in.segmentlist = (int *) NULL;
431 in.segmentmarkerlist = (int *) NULL;
433 in.numberofholes = 0;
434 in.holelist = (REAL *) NULL;
436 in.numberofregions = 0;
437 in.regionlist = (REAL *) NULL;
439 in.numberofedges = 0;
440 in.edgelist = (int *) NULL;
441 in.edgemarkerlist = (int *) NULL;
442 in.normlist = (REAL *) NULL;
444 /* Make necessary initializations */
445 out.pointlist = (REAL *) NULL; /* Not needed if -N switch used. */
446 out.pointattributelist = (REAL *) NULL; /* Not needed if -N switch used or
447 number of point attributes is zero: */
448 out.pointmarkerlist = (int *) NULL; /* Not needed if -N or -B switch used. */
449 out.trianglelist = (int *) NULL; /* Not needed if -E switch used. */
450 out.triangleattributelist = (REAL *) NULL; /* Not needed if -E switch used or
451 number of triangle attributes is
453 out.trianglearealist = (REAL *) NULL;
454 out.neighborlist = (int *) NULL; /* Needed only if -n switch used. */
455 out.segmentlist = (int *) NULL; /* Needed only if segments are output
456 (-p or -c) and -P not used: */
457 out.segmentmarkerlist = (int *) NULL; /* Needed only if segments are output
458 (-p or -c) and -P and -B not used: */
459 out.edgelist = (int *) NULL; /* Needed only if -e switch used. */
460 out.edgemarkerlist = (int *) NULL; /* Needed if -e used and -B not used. */
462 triangulate( Options, &in, &out, NULL );
464 NumTris[0] = out.numberoftriangles;
465 *Tri = (TRI *) malloc( NumTris[0] * sizeof( TRI ) );
468 for ( i = 0; i < NumTris[0]; i++ )
470 ptri[i].v[0] = NodeTable[out.trianglelist[i * out.numberofcorners ]];
471 ptri[i].v[1] = NodeTable[out.trianglelist[i * out.numberofcorners + 1]];
472 ptri[i].v[2] = NodeTable[out.trianglelist[i * out.numberofcorners + 2]];
473 ptri[i].n[0] = out.neighborlist[i * 3 ];
474 ptri[i].n[1] = out.neighborlist[i * 3 + 1];
475 ptri[i].n[2] = out.neighborlist[i * 3 + 2];
478 /* Free all allocated arrays, including those allocated by Triangle. */
479 if ( in.pointlist ) {
480 free( in.pointlist );
482 if ( in.pointattributelist ) {
483 free( in.pointattributelist );
485 if ( in.pointmarkerlist ) {
486 free( in.pointmarkerlist );
488 if ( in.trianglelist ) {
489 free( in.trianglelist );
491 if ( in.triangleattributelist ) {
492 free( in.triangleattributelist );
494 if ( in.trianglearealist ) {
495 free( in.trianglearealist );
497 if ( in.neighborlist ) {
498 free( in.neighborlist );
500 if ( in.segmentlist ) {
501 free( in.segmentlist );
503 if ( in.segmentmarkerlist ) {
504 free( in.segmentmarkerlist );
509 if ( in.regionlist ) {
510 free( in.regionlist );
515 if ( in.edgemarkerlist ) {
516 free( in.edgemarkerlist );
521 if ( out.pointlist ) {
522 free( out.pointlist );
524 if ( out.pointattributelist ) {
525 free( out.pointattributelist );
527 if ( out.pointmarkerlist ) {
528 free( out.pointmarkerlist );
530 if ( out.trianglelist ) {
531 free( out.trianglelist );
533 if ( out.triangleattributelist ) {
534 free( out.triangleattributelist );
536 if ( out.trianglearealist ) {
537 free( out.trianglearealist );
539 if ( out.neighborlist ) {
540 free( out.neighborlist );
542 if ( out.segmentlist ) {
543 free( out.segmentlist );
545 if ( out.segmentmarkerlist ) {
546 free( out.segmentmarkerlist );
548 if ( out.holelist ) {
549 free( out.holelist );
551 if ( out.regionlist ) {
552 free( out.regionlist );
554 if ( out.edgelist ) {
555 free( out.edgelist );
557 if ( out.edgemarkerlist ) {
558 free( out.edgemarkerlist );
560 if ( out.normlist ) {
561 free( out.normlist );
568 void EdgeOnSide( int *v, int *edge, int *border ){
575 if ( ( v[0] <= NV ) && ( v[1] <= NV ) ) {
579 if ( ( v[1] <= NV ) && ( v[2] <= NV ) ) {
583 if ( ( v[2] <= NV ) && ( v[0] <= NV ) ) {
590 if ( ( v[0] >= R ) && ( v[1] >= R ) ) {
594 if ( ( v[1] >= R ) && ( v[2] >= R ) ) {
598 if ( ( v[2] >= R ) && ( v[0] >= R ) ) {
603 if ( border[0] >= 0 ) {
606 N = Absolute( v[k0] - v[k1] );
607 Ndv = (float)( N * dv );
609 if ( ( ( v[0] % NVP1 ) == 0 ) && ( ( v[1] % NVP1 ) == 0 ) ) {
610 if ( border[0] >= 0 ) {
611 if ( Ndv > ( Absolute( v[0] - v[1] ) * dh ) ) {
619 if ( ( ( v[1] % NVP1 ) == 0 ) && ( ( v[2] % NVP1 ) == 0 ) ) {
620 if ( border[0] >= 0 ) {
621 if ( Ndv > ( Absolute( v[1] - v[2] ) * dh ) ) {
629 if ( ( ( v[2] % NVP1 ) == 0 ) && ( ( v[0] % NVP1 ) == 0 ) ) {
630 if ( border[0] >= 0 ) {
631 if ( Ndv > ( Absolute( v[2] - v[0] ) * dh ) ) {
640 if ( ( ( v[0] % NVP1 ) == NV ) && ( ( v[1] % NVP1 ) == NV ) ) {
641 if ( border[0] >= 0 ) {
642 if ( Ndv > ( Absolute( v[0] - v[1] ) * dh ) ) {
650 if ( ( ( v[1] % NVP1 ) == NV ) && ( ( v[2] % NVP1 ) == NV ) ) {
651 if ( border[0] >= 0 ) {
652 if ( Ndv > ( Absolute( v[1] - v[2] ) * dh ) ) {
660 if ( ( ( v[2] % NVP1 ) == NV ) && ( ( v[0] % NVP1 ) == NV ) ) {
661 if ( border[0] >= 0 ) {
662 if ( Ndv > ( Absolute( v[2] - v[0] ) * dh ) ) {
673 void CalcAngles( NODE *node, int *v, float *angle ){
676 vec x0, x1, x2, y0, y1, y2;
696 x0 = node[v[0]].p[i];
697 x1 = node[v[1]].p[i];
698 x2 = node[v[2]].p[i];
699 y0 = node[v[0]].p[j];
700 y1 = node[v[1]].p[j];
701 y2 = node[v[2]].p[j];
710 for ( k = 0; k < 3; k++ )
712 l = (vec)( sqrt( vv[k][0] * vv[k][0] + vv[k][1] * vv[k][1] ) );
719 dot = -( vv[0][0] * vv[2][0] + vv[0][1] * vv[2][1] );
720 angle[0] = (float)( acos( dot ) );
721 dot = -( vv[1][0] * vv[0][0] + vv[1][1] * vv[0][1] );
722 angle[1] = (float)( acos( dot ) );
723 dot = -( vv[2][0] * vv[1][0] + vv[2][1] * vv[1][1] );
724 angle[2] = (float)( acos( dot ) );
726 //=================================================================
727 int Bisect( NODE *node, int border, int j0, int j1 ){
739 k = (int)( ( j0 + j1 ) / ( 2 * NVP1 ) ) * NVP1;
742 k = (int)( ( j0 + j1 + 2 ) / ( 2 * NVP1 ) ) * NVP1 - 1;
745 return( ( ( k != j0 ) && ( k != j1 ) ) ? k : 0 );
747 //=================================================================
748 int compare( TRITABLE *t1, TRITABLE *t2 ){
749 if ( t1->error > t2->error ) {
752 if ( t1->error < t2->error ) {
758 void MakeBrushes( int NumTris, NODE *Node, TRI *Tri,bool surf,
759 int offset,char *texture0, char *texture1, char *texture2 ){
760 extern double backface;
765 vec3_t PlaneNormal,SurfNormal;
769 // if texture2 is identical to texture0, there's no need to
770 // check surface angle
771 if ( !g_strcasecmp( texture0,texture2 ) || !strlen( texture2 ) ) {
777 Steep = (float)cos( (double)SlantAngle / 57.2957795 );
780 case PLANE_XY0: PlaneNormal[0] = 0.; PlaneNormal[1] = 0.; PlaneNormal[2] = 1.; break;
781 case PLANE_XY1: PlaneNormal[0] = 0.; PlaneNormal[1] = 0.; PlaneNormal[2] = -1.; break;
782 case PLANE_XZ0: PlaneNormal[0] = 0.; PlaneNormal[1] = 1.; PlaneNormal[2] = 1.; break;
783 case PLANE_XZ1: PlaneNormal[0] = 0.; PlaneNormal[1] = -1.; PlaneNormal[2] = 1.; break;
784 case PLANE_YZ0: PlaneNormal[0] = 1.; PlaneNormal[1] = 0.; PlaneNormal[2] = 1.; break;
785 case PLANE_YZ1: PlaneNormal[0] = -1.; PlaneNormal[1] = 0.; PlaneNormal[2] = 1.; break;
792 contents += CONTENTS_DETAIL;
795 contents += CONTENTS_LADDER;
800 for ( i = 0; i < NumTris; i++ )
805 brush.face[0].v[0][0] = Node[Tri[i].v[0]].p[0];
806 brush.face[0].v[0][1] = Node[Tri[i].v[0]].p[1];
807 brush.face[0].v[0][2] = Node[Tri[i].v[0]].p[2];
809 brush.face[0].v[1][0] = Node[Tri[i].v[2]].p[0];
810 brush.face[0].v[1][1] = Node[Tri[i].v[2]].p[1];
811 brush.face[0].v[1][2] = Node[Tri[i].v[2]].p[2];
813 brush.face[0].v[2][0] = Node[Tri[i].v[1]].p[0];
814 brush.face[0].v[2][1] = Node[Tri[i].v[1]].p[1];
815 brush.face[0].v[2][2] = Node[Tri[i].v[1]].p[2];
821 brush.face[0].v[0][2] += offset;
822 brush.face[0].v[1][2] += offset;
823 brush.face[0].v[1][2] += offset;
826 brush.face[0].v[0][2] -= offset;
827 brush.face[0].v[1][2] -= offset;
828 brush.face[0].v[1][2] -= offset;
831 brush.face[0].v[0][1] += offset;
832 brush.face[0].v[1][1] += offset;
833 brush.face[0].v[1][1] += offset;
836 brush.face[0].v[0][1] -= offset;
837 brush.face[0].v[1][1] -= offset;
838 brush.face[0].v[1][1] -= offset;
841 brush.face[0].v[0][0] += offset;
842 brush.face[0].v[1][0] += offset;
843 brush.face[0].v[1][0] += offset;
846 brush.face[0].v[0][0] -= offset;
847 brush.face[0].v[1][0] -= offset;
848 brush.face[0].v[1][0] -= offset;
857 brush.face[1].v[0][0] = Node[Tri[i].v[0]].p[0];
858 brush.face[1].v[0][1] = (float)backface;
859 brush.face[1].v[0][2] = Node[Tri[i].v[0]].p[2];
861 brush.face[1].v[1][0] = Node[Tri[i].v[1]].p[0];
862 brush.face[1].v[1][1] = (float)backface;
863 brush.face[1].v[1][2] = Node[Tri[i].v[1]].p[2];
865 brush.face[1].v[2][0] = Node[Tri[i].v[2]].p[0];
866 brush.face[1].v[2][1] = (float)backface;
867 brush.face[1].v[2][2] = Node[Tri[i].v[2]].p[2];
870 brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
871 brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
872 brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
874 brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
875 brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
876 brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
878 brush.face[2].v[2][0] = Node[Tri[i].v[1]].p[0];
879 brush.face[2].v[2][1] = (float)backface;
880 brush.face[2].v[2][2] = Node[Tri[i].v[1]].p[2];
883 brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
884 brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
885 brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
887 brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
888 brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
889 brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
891 brush.face[3].v[2][0] = Node[Tri[i].v[2]].p[0];
892 brush.face[3].v[2][1] = (float)backface;
893 brush.face[3].v[2][2] = Node[Tri[i].v[2]].p[2];
896 brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
897 brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
898 brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
900 brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
901 brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
902 brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
904 brush.face[4].v[2][0] = Node[Tri[i].v[0]].p[0];
905 brush.face[4].v[2][1] = (float)backface;
906 brush.face[4].v[2][2] = Node[Tri[i].v[0]].p[2];
911 brush.face[1].v[0][0] = (float)backface;
912 brush.face[1].v[0][1] = Node[Tri[i].v[0]].p[1];
913 brush.face[1].v[0][2] = Node[Tri[i].v[0]].p[2];
915 brush.face[1].v[1][0] = (float)backface;
916 brush.face[1].v[1][1] = Node[Tri[i].v[1]].p[1];
917 brush.face[1].v[1][2] = Node[Tri[i].v[1]].p[2];
919 brush.face[1].v[2][0] = (float)backface;
920 brush.face[1].v[2][1] = Node[Tri[i].v[2]].p[1];
921 brush.face[1].v[2][2] = Node[Tri[i].v[2]].p[2];
924 brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
925 brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
926 brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
928 brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
929 brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
930 brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
932 brush.face[2].v[2][0] = (float)backface;
933 brush.face[2].v[2][1] = Node[Tri[i].v[1]].p[1];
934 brush.face[2].v[2][2] = Node[Tri[i].v[1]].p[2];
937 brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
938 brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
939 brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
941 brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
942 brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
943 brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
945 brush.face[3].v[2][0] = (float)backface;
946 brush.face[3].v[2][1] = Node[Tri[i].v[2]].p[1];
947 brush.face[3].v[2][2] = Node[Tri[i].v[2]].p[2];
950 brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
951 brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
952 brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
954 brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
955 brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
956 brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
958 brush.face[4].v[2][0] = (float)backface;
959 brush.face[4].v[2][1] = Node[Tri[i].v[0]].p[1];
960 brush.face[4].v[2][2] = Node[Tri[i].v[0]].p[2];
964 brush.face[1].v[0][0] = Node[Tri[i].v[0]].p[0];
965 brush.face[1].v[0][1] = Node[Tri[i].v[0]].p[1];
966 brush.face[1].v[0][2] = (float)backface;
968 brush.face[1].v[1][0] = Node[Tri[i].v[1]].p[0];
969 brush.face[1].v[1][1] = Node[Tri[i].v[1]].p[1];
970 brush.face[1].v[1][2] = (float)backface;
972 brush.face[1].v[2][0] = Node[Tri[i].v[2]].p[0];
973 brush.face[1].v[2][1] = Node[Tri[i].v[2]].p[1];
974 brush.face[1].v[2][2] = (float)backface;
977 brush.face[2].v[0][0] = Node[Tri[i].v[0]].p[0];
978 brush.face[2].v[0][1] = Node[Tri[i].v[0]].p[1];
979 brush.face[2].v[0][2] = Node[Tri[i].v[0]].p[2];
981 brush.face[2].v[1][0] = Node[Tri[i].v[1]].p[0];
982 brush.face[2].v[1][1] = Node[Tri[i].v[1]].p[1];
983 brush.face[2].v[1][2] = Node[Tri[i].v[1]].p[2];
985 brush.face[2].v[2][0] = Node[Tri[i].v[1]].p[0];
986 brush.face[2].v[2][1] = Node[Tri[i].v[1]].p[1];
987 brush.face[2].v[2][2] = (float)backface;
990 brush.face[3].v[0][0] = Node[Tri[i].v[1]].p[0];
991 brush.face[3].v[0][1] = Node[Tri[i].v[1]].p[1];
992 brush.face[3].v[0][2] = Node[Tri[i].v[1]].p[2];
994 brush.face[3].v[1][0] = Node[Tri[i].v[2]].p[0];
995 brush.face[3].v[1][1] = Node[Tri[i].v[2]].p[1];
996 brush.face[3].v[1][2] = Node[Tri[i].v[2]].p[2];
998 brush.face[3].v[2][0] = Node[Tri[i].v[2]].p[0];
999 brush.face[3].v[2][1] = Node[Tri[i].v[2]].p[1];
1000 brush.face[3].v[2][2] = (float)backface;
1003 brush.face[4].v[0][0] = Node[Tri[i].v[2]].p[0];
1004 brush.face[4].v[0][1] = Node[Tri[i].v[2]].p[1];
1005 brush.face[4].v[0][2] = Node[Tri[i].v[2]].p[2];
1007 brush.face[4].v[1][0] = Node[Tri[i].v[0]].p[0];
1008 brush.face[4].v[1][1] = Node[Tri[i].v[0]].p[1];
1009 brush.face[4].v[1][2] = Node[Tri[i].v[0]].p[2];
1011 brush.face[4].v[2][0] = Node[Tri[i].v[0]].p[0];
1012 brush.face[4].v[2][1] = Node[Tri[i].v[0]].p[1];
1013 brush.face[4].v[2][2] = (float)backface;
1016 for ( j = 0; j < 5; j++ )
1018 strcpy( brush.face[j].texture,
1019 ( strlen( texture1 ) ? texture1 : texture0 ) );
1020 brush.face[j].Shift[0] = (float)TexOffset[0];
1021 brush.face[j].Shift[1] = (float)TexOffset[1];
1022 brush.face[j].Rotate = 0.;
1023 brush.face[j].Scale[0] = (float)TexScale[0];
1024 brush.face[j].Scale[1] = (float)TexScale[1];
1025 brush.face[j].Contents = contents;
1027 brush.face[j].Surface = 0;
1030 brush.face[j].Surface = SURF_HINT;
1032 brush.face[j].Value = 0;
1036 XYZVectorSubtract( brush.face[0].v[2],brush.face[0].v[0],t[0] );
1037 XYZVectorSubtract( brush.face[0].v[1],brush.face[0].v[2],t[1] );
1038 CrossProduct( t[0],t[1],SurfNormal );
1039 VectorNormalize( SurfNormal,SurfNormal );
1040 if ( DotProduct( SurfNormal,PlaneNormal ) < Steep ) {
1041 strcpy( brush.face[0].texture,texture2 );
1044 strcpy( brush.face[0].texture,texture0 );
1048 strcpy( brush.face[0].texture,texture0 );
1052 brush.face[0].Value = ArghRad2;
1054 MakeBrush( &brush );
1058 } // end MakeBrushes
1059 //=================================================================
1060 void MapOut( int NumNodes,int NumTris, NODE *Node, TRI *Tri ){
1061 extern double backface;
1062 extern double xmin, xmax, ymin, ymax, zmin, zmax;
1064 char hint[32], skip[32];
1068 ghCursorCurrent = LoadCursor(NULL,IDC_WAIT);
1069 SetCursor(ghCursorCurrent);
1071 UseDetail = 1; // this is temporary
1072 MakeBrushes( NumTris,Node,Tri,TRUE,0,Texture[Game][0],Texture[Game][1],Texture[Game][2] );
1074 if ( AddHints || GimpHints ) {
1078 strcpy( hint,"generic/misc/hint" );
1079 strcpy( skip,"generic/misc/skip" );
1082 strcpy( hint,"HINT" );
1083 strcpy( skip,"HINT" );
1086 strcpy( hint,"general/hint" );
1087 strcpy( skip,"general/skip" );
1090 strcpy( hint,"common/0_hint" );
1091 strcpy( skip,"common/0_skip" );
1094 strcpy( hint,"common/hint" );
1095 strcpy( skip,"common/skip" );
1098 strcpy( hint,"e1u1/hint" );
1099 strcpy( skip,"e1u1/skip" );
1104 MakeBrushes( NumTris,Node,Tri,FALSE,HINT_OFFSET,hint,hint,hint );
1107 if ( AddHints == 1 ) {
1108 int j0, j1, j2, k, k0, k1;
1113 int MaxHints; // We don't want a whole slew of hint brushes, which we'd get
1114 // with low decimation values and our current placement scheme.
1115 // Limit number of hint brushes to number of undecimated grid
1121 front = LessThan( zmin,32. );
1124 front = MoreThan( ymax,32. );
1127 front = LessThan( ymin,32. );
1130 front = MoreThan( xmax,32. );
1133 front = LessThan( xmin,32. );
1136 front = MoreThan( zmax,32. );
1139 for ( i = 0; i < NumTris; i++ )
1164 MaxHints = NH * NV - 1;
1165 for ( w = 1; w < min( 16,NH ) && brush.Number < MaxHints; w++ )
1167 for ( h = max( 1,w / 2 ); h < min( 16,NV ) && brush.Number < MaxHints; h++ )
1169 for ( i = 0; i <= NH - w && brush.Number < MaxHints; i++ )
1171 for ( j = 0; j <= NV - h && brush.Number < MaxHints; j++ )
1173 q[0] = i * NVP1 + j;
1174 q[2] = q[0] + w * NVP1 + h;
1187 for ( k = 0, OK = 1; k < NumTris && OK; k++ )
1189 if ( Tri[k].min[j1] >= max( Node[q[0]].p[j1],Node[q[2]].p[j1] ) ) {
1192 if ( Tri[k].min[j2] >= max( Node[q[0]].p[j2],Node[q[2]].p[j2] ) ) {
1195 if ( Tri[k].max[j1] <= min( Node[q[0]].p[j1],Node[q[2]].p[j1] ) ) {
1198 if ( Tri[k].max[j2] <= min( Node[q[0]].p[j2],Node[q[2]].p[j2] ) ) {
1202 for ( h0 = 0; h0 < 4 && OK; h0++ )
1204 h1 = ( h0 + 1 ) % 4;
1205 for ( t = 0; t < 3 && OK; t++ )
1207 s[t] = side( Node[q[h0]].p[j1],Node[q[h0]].p[j2],
1208 Node[q[h1]].p[j1],Node[q[h1]].p[j2],
1209 Node[Tri[k].v[t]].p[j1],Node[Tri[k].v[t]].p[j2] );
1211 if ( ( s[1] > 0 || s[2] > 0 ) && s[0] < 0 ) {
1214 if ( ( s[2] > 0 || s[0] > 0 ) && s[1] < 0 ) {
1217 if ( ( s[0] > 0 || s[1] > 0 ) && s[2] < 0 ) {
1230 brush.face[0].v[0][0] = Node[q[2]].p[0];
1231 brush.face[0].v[0][1] = (float)front;
1232 brush.face[0].v[0][2] = Node[q[2]].p[2];
1234 brush.face[0].v[1][0] = Node[q[1]].p[0];
1235 brush.face[0].v[1][1] = (float)front;
1236 brush.face[0].v[1][2] = Node[q[1]].p[2];
1238 brush.face[0].v[2][0] = Node[q[0]].p[0];
1239 brush.face[0].v[2][1] = (float)front;
1240 brush.face[0].v[2][2] = Node[q[0]].p[2];
1243 brush.face[1].v[0][0] = Node[q[0]].p[0];
1244 brush.face[1].v[0][1] = (float)backface;
1245 brush.face[1].v[0][2] = Node[q[0]].p[2];
1247 brush.face[1].v[1][0] = Node[q[1]].p[0];
1248 brush.face[1].v[1][1] = (float)backface;
1249 brush.face[1].v[1][2] = Node[q[1]].p[2];
1251 brush.face[1].v[2][0] = Node[q[2]].p[0];
1252 brush.face[1].v[2][1] = (float)backface;
1253 brush.face[1].v[2][2] = Node[q[2]].p[2];
1255 for ( k0 = 0; k0 < brush.NumFaces - 2; k0++ )
1258 k1 = ( k0 + 1 ) % ( brush.NumFaces - 2 );
1260 brush.face[k].v[0][0] = Node[q[k0]].p[0];
1261 brush.face[k].v[0][1] = (float)front;
1262 brush.face[k].v[0][2] = Node[q[k0]].p[2];
1264 brush.face[k].v[1][0] = Node[q[k1]].p[0];
1265 brush.face[k].v[1][1] = (float)front;
1266 brush.face[k].v[1][2] = Node[q[k1]].p[2];
1268 brush.face[k].v[2][0] = Node[q[k1]].p[0];
1269 brush.face[k].v[2][1] = (float)backface;
1270 brush.face[k].v[2][2] = Node[q[k1]].p[2];
1276 brush.face[0].v[0][0] = (float)front;
1277 brush.face[0].v[0][1] = Node[q[2]].p[1];
1278 brush.face[0].v[0][2] = Node[q[2]].p[2];
1280 brush.face[0].v[1][0] = (float)front;
1281 brush.face[0].v[1][1] = Node[q[1]].p[1];
1282 brush.face[0].v[1][2] = Node[q[1]].p[2];
1284 brush.face[0].v[2][0] = (float)front;
1285 brush.face[0].v[2][1] = Node[q[0]].p[1];
1286 brush.face[0].v[2][2] = Node[q[0]].p[2];
1289 brush.face[1].v[0][0] = (float)backface;
1290 brush.face[1].v[0][1] = Node[q[0]].p[1];
1291 brush.face[1].v[0][2] = Node[q[0]].p[2];
1293 brush.face[1].v[1][0] = (float)backface;
1294 brush.face[1].v[1][1] = Node[q[1]].p[1];
1295 brush.face[1].v[1][2] = Node[q[1]].p[2];
1297 brush.face[1].v[2][0] = (float)backface;
1298 brush.face[1].v[2][1] = Node[q[2]].p[1];
1299 brush.face[1].v[2][2] = Node[q[2]].p[2];
1301 for ( k0 = 0; k0 < brush.NumFaces - 2; k0++ )
1304 k1 = ( k0 + 1 ) % ( brush.NumFaces - 2 );
1306 brush.face[k].v[0][0] = (float)front;
1307 brush.face[k].v[0][1] = Node[q[k0]].p[1];
1308 brush.face[k].v[0][2] = Node[q[k0]].p[2];
1310 brush.face[k].v[1][0] = (float)front;
1311 brush.face[k].v[1][1] = Node[q[k1]].p[1];
1312 brush.face[k].v[1][2] = Node[q[k1]].p[2];
1314 brush.face[k].v[2][0] = (float)backface;
1315 brush.face[k].v[2][1] = Node[q[k1]].p[1];
1316 brush.face[k].v[2][2] = Node[q[k1]].p[2];
1321 brush.face[0].v[0][0] = Node[q[2]].p[0];
1322 brush.face[0].v[0][1] = Node[q[2]].p[1];
1323 brush.face[0].v[0][2] = (float)front;
1325 brush.face[0].v[1][0] = Node[q[1]].p[0];
1326 brush.face[0].v[1][1] = Node[q[1]].p[1];
1327 brush.face[0].v[1][2] = (float)front;
1329 brush.face[0].v[2][0] = Node[q[0]].p[0];
1330 brush.face[0].v[2][1] = Node[q[0]].p[1];
1331 brush.face[0].v[2][2] = (float)front;
1334 brush.face[1].v[0][0] = Node[q[0]].p[0];
1335 brush.face[1].v[0][1] = Node[q[0]].p[1];
1336 brush.face[1].v[0][2] = (float)backface;
1338 brush.face[1].v[1][0] = Node[q[1]].p[0];
1339 brush.face[1].v[1][1] = Node[q[1]].p[1];
1340 brush.face[1].v[1][2] = (float)backface;
1342 brush.face[1].v[2][0] = Node[q[2]].p[0];
1343 brush.face[1].v[2][1] = Node[q[2]].p[1];
1344 brush.face[1].v[2][2] = (float)backface;
1346 for ( k0 = 0; k0 < brush.NumFaces - 2; k0++ )
1349 k1 = ( k0 + 1 ) % ( brush.NumFaces - 2 );
1351 brush.face[k].v[0][0] = Node[q[k0]].p[0];
1352 brush.face[k].v[0][1] = Node[q[k0]].p[1];
1353 brush.face[k].v[0][2] = (float)front;
1355 brush.face[k].v[1][0] = Node[q[k1]].p[0];
1356 brush.face[k].v[1][1] = Node[q[k1]].p[1];
1357 brush.face[k].v[1][2] = (float)front;
1359 brush.face[k].v[2][0] = Node[q[k1]].p[0];
1360 brush.face[k].v[2][1] = Node[q[k1]].p[1];
1361 brush.face[k].v[2][2] = (float)backface;
1365 for ( face = 0; face < 6; face++ )
1367 strcpy( brush.face[face].texture,( face <= 1 ? skip : hint ) );
1368 brush.face[face].Shift[0] = 0;
1369 brush.face[face].Shift[1] = 0;
1370 brush.face[face].Rotate = 0.;
1371 brush.face[face].Scale[0] = 1;
1372 brush.face[face].Scale[1] = 1;
1373 brush.face[face].Contents = CONTENTS_DETAIL;
1374 brush.face[face].Surface = ( face <= 1 ? SURF_SKIP : SURF_HINT );
1375 brush.face[face].Value = 0;
1377 if ( !brush.Number ) {
1380 MakeBrush( &brush );
1386 if ( brush.Number ) {
1391 ghCursorCurrent = ghCursorDefault;
1392 SetCursor(ghCursorCurrent);
1395 //===========================================================================
1396 int CheckBorders( int *NumNodesUsed, int NumNodes, NODE *Node, int *NumTris, TRI **pTri ){
1398 int i, j, k0, k1, N;
1402 N = NumNodesUsed[0];
1404 for ( i = 0; i < NumTris[0]; i++ )
1406 EdgeOnSide( Tri[i].v,&k0,&border );
1410 CalcAngles( Node, Tri[i].v, angle );
1411 k1 = ( k0 + 1 ) % 3;
1412 if ( ( angle[k0] < SLIVER_ANGLE ) || ( angle[k1] < SLIVER_ANGLE ) ) {
1413 j = Bisect( Node, border, Tri[i].v[k0], Tri[i].v[k1] );
1415 if ( !Node[j].used ) { // Shouldn't be used, but...
1422 if ( NumNodesUsed[0] > N ) {
1424 tricall( NumNodes, Node, NumTris, NULL, pTri, "cnzBNPY" );
1427 return ( NumNodesUsed[0] - N );