more eol-style
[xonotic/netradiant.git] / radiant / pmesh.cpp
1 /*
2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20 */
21
22 // 
23 // Preliminary patch stuff
24 //
25 // 
26
27 #include "stdafx.h"
28 #include "gtkmisc.h"
29
30 #include "gtkr_list.h"
31
32 // externs
33 extern void MemFile_fprintf(MemStream* pMemFile, const char* pText, ...);
34 extern face_t *Face_Alloc( void );
35 extern void DrawAlternatePoint(vec3_t v, float scale);
36
37 void _Write3DMatrix (FILE *f, int y, int x, int z, float *m);
38 void _Write3DMatrix (MemStream *f, int y, int x, int z, float *m);
39
40 void Patch_InitialiseLODPointers(patchMesh_t *p)
41 {
42         int i;
43         int rowcount = ((MAX_PATCH_WIDTH-1)/2) * MAX_PATCH_HEIGHT;
44         for (i=0; i<rowcount; i++)
45                 p->rowLOD[i] = NULL;
46         int colcount = ((MAX_PATCH_HEIGHT-1)/2) * MAX_PATCH_WIDTH;
47         for (i=0; i<colcount; i++)
48                 p->colLOD[i] = NULL;
49 }
50
51 patchMesh_t* Patch_Alloc()
52 {
53   patchMesh_t *pPatch = (patchMesh_t *)malloc(sizeof(patchMesh_t));
54   pPatch->pShader = NULL;
55   pPatch->pSymbiot = NULL; // Hydra: added missing initialiser.
56         // spog - initialise patch LOD pointers
57   Patch_InitialiseLODPointers(pPatch);
58   pPatch->drawLists = NULL;
59   pPatch->bDirty = true;
60   pPatch->nListID = -1;
61   pPatch->bSelected = false;
62   pPatch->bOverlay = false;
63   pPatch->bDirty = true;
64   pPatch->LODUpdated = false;
65
66   int i;
67   for (i=0; i<(((MAX_PATCH_WIDTH-1)-1)/2); i++)
68     pPatch->rowDirty[i] = false;
69   for (i=0; i<(((MAX_PATCH_HEIGHT-1)-1)/2); i++)
70     pPatch->colDirty[i] = false;
71
72   return pPatch;
73 }
74
75 patchMesh_t* MakeNewPatch()
76 {
77   patchMesh_t *pm = reinterpret_cast<patchMesh_t*>(qmalloc(sizeof(patchMesh_t)));
78
79   // spog - initialise patch LOD pointers
80   Patch_InitialiseLODPointers(pm);
81   pm->drawLists = NULL;
82   pm->bDirty = true;
83
84   return pm;
85 }
86
87 // FIXME: this needs to be dynamic
88 //#define       MAX_PATCH_MESHES        4096
89 //patchMesh_t           patchMeshes[MAX_PATCH_MESHES];
90 //int numPatchMeshes = 0;
91
92 // used for a save spot
93 patchMesh_t patchSave;
94
95 // Tracks the selected patch for point manipulation/update. FIXME: Need to revert back to a generalized 
96 // brush approach
97 //--int  g_nSelectedPatch = -1;  
98
99 // HACK: for tracking which view generated the click
100 // as we dont want to deselect a point on a same point
101 // click if it is from a different view
102 int  g_nPatchClickedView = -1;
103 bool g_bSameView = false;
104
105 //typedef enum XFormType { TRANSLATE, SCALE, ROTATE };
106
107
108 // globals
109 bool g_bPatchShowBounds = true;
110 bool g_bPatchWireFrame = false;
111 bool g_bPatchWeld = true;
112 bool g_bPatchDrillDown = true;
113 //bool g_bPatchInsertMode = false;
114 bool g_bPatchBendMode = false;
115 int  g_nPatchBendState = -1;
116 int  g_nPatchInsertState = -1;
117 int  g_nBendOriginIndex = 0;
118 vec3_t g_vBendOrigin;
119
120 bool g_bPatchAxisOnRow = true;
121 int  g_nPatchAxisIndex = 0;
122 bool g_bPatchLowerEdge = true;
123
124 vec3_t g_vCycleCapNormal;
125 // cycles when we use Patch_CycleCapSelected
126 VIEWTYPE g_nCycleCapIndex = XY;
127
128 // BEND states
129 enum
130 {
131   BEND_SELECT_ROTATION = 0,
132   BEND_SELECT_ORIGIN,
133   BEND_SELECT_EDGE,
134   BEND_BENDIT,
135   BEND_STATE_COUNT
136 };
137
138 const char *g_pBendStateMsg[] =
139 {
140   "Use TAB to cycle through available bend axis. Press ENTER when the desired one is highlighted.",
141   "Use TAB to cycle through available rotation axis. This will LOCK around that point. You may also use Shift + Middle Click to select an arbitrary point. Press ENTER when the desired one is highlighted",
142   "Use TAB to choose which side to bend. Press ENTER when the desired one is highlighted.",
143   "Use the MOUSE to bend the patch. It uses the same ui rules as Free Rotation. Press ENTER to accept the bend, press ESC to abandon it and exit Bend mode",
144   ""
145 };
146
147 // INSERT states
148 enum
149 {
150   INSERT_SELECT_EDGE = 0,
151   INSERT_STATE_COUNT
152 };
153
154 const char* g_pInsertStateMsg[] =
155 {
156   "Use TAB to cycle through available rows/columns for insertion/deletion. Press INS to insert at the highlight, DEL to remove the pair"
157 };
158
159
160 float *g_InversePoints[1024];
161
162 const float fFullBright = 1.0;
163 const float fLowerLimit = .50;
164 const float fDec = .05f;
165 void _SetColor(face_t* f, float fColor[3])
166 {
167   return;
168   fColor[0] = f->d_color[0];
169   fColor[1] = f->d_color[1];
170   fColor[2] = f->d_color[2];
171   qglColor3fv(fColor);
172 }
173
174
175 void _DecColor(float fColor[3])
176 {
177   return;
178   fColor[0] -= fDec;
179   fColor[1] -= fDec ;
180   fColor[2] -= fDec;
181   for (int i = 0; i < 3; i++)
182   {
183     if (fColor[i] <= fLowerLimit)
184     {
185       fColor[0] = fFullBright;
186       fColor[1] = fFullBright;
187       fColor[2] = fFullBright;
188       break;
189     }
190   }
191         qglColor3fv(fColor);
192 }
193
194 vec_t __VectorNormalize (vec3_t in, vec3_t out)
195 {
196         vec_t   length, ilength;
197
198         length = sqrt (in[0]*in[0] + in[1]*in[1] + in[2]*in[2]);
199         if (length == 0)
200         {
201                 VectorClear (out);
202                 return 0;
203         }
204
205         ilength = 1.0/length;
206         out[0] = in[0]*ilength;
207         out[1] = in[1]*ilength;
208         out[2] = in[2]*ilength;
209
210         return length;
211 }
212
213
214 void Patch_SetType(patchMesh_t *p, int nType)
215 {
216   p->type = (p->type & PATCH_STYLEMASK) | nType;
217 }
218
219 void Patch_SetStyle(patchMesh_t *p, int nStyle)
220 {
221   p->type = (p->type & PATCH_TYPEMASK) | nStyle;
222 }
223
224 /*
225 ==================
226 Patch_MemorySize
227 ==================
228 */
229 int Patch_MemorySize(patchMesh_t *p)
230 {
231   //    return _msize(p);
232   return 0;
233 }
234
235
236 /*
237 ===============
238 InterpolateInteriorPoints
239 ===============
240 */
241 void InterpolateInteriorPoints( patchMesh_t *p ) 
242 {
243         int             i, j, k;
244         int             next, prev;
245
246         for ( i = 0 ; i < p->width ; i += 2 ) 
247   {
248
249     next = ( i == p->width - 1 ) ? 1 : ( i + 1 ) % p->width;
250     prev = ( i == 0 ) ? p->width - 2 : i - 1;
251
252 #if 0
253                 if ( i == 0 ) 
254     {
255                         next = ( i + 1 ) % p->width;
256                         prev = p->width - 2;                  // joined wrap case
257                 } 
258     else if ( i == p->width - 1 ) 
259     {
260                         next = 1;
261                         prev = i - 1;
262                 } 
263     else 
264     {
265                         next = ( i + 1 ) % p->width;
266                         prev = i - 1;
267                 }
268 #endif
269
270                 for ( j = 0 ; j < p->height ; j++ ) 
271     {
272                         for ( k = 0 ; k < 3 ; k++ ) 
273       {
274                                 p->ctrl[i][j].xyz[k] = ( p->ctrl[next][j].xyz[k] + p->ctrl[prev][j].xyz[k] ) * 0.5;
275                         }
276                 }
277         }
278 }
279
280 /*
281 =================
282 MakeMeshNormals
283
284 =================
285 */
286 int     neighbors[8][2] = {
287         {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
288 };
289
290 void Patch_MeshNormals(patchMesh_t *in ) 
291 {
292         int             i, j, k, dist;
293         vec3_t  normal;
294         vec3_t  sum;
295         int             count;
296         vec3_t  base;
297         vec3_t  delta;
298         int             x, y;
299         drawVert_t      *dv;
300         vec3_t          around[8], temp;
301         qboolean        good[8];
302         qboolean        wrapWidth, wrapHeight;
303         float           len;
304
305         wrapWidth = false;
306         for ( i = 0 ; i < in->height ; i++ ) 
307         {
308
309                 VectorSubtract( in->ctrl[0][i].xyz, 
310                                       in->ctrl[in->width-1][i].xyz, delta );
311                 len = VectorLength( delta );
312                 if ( len > 1.0 ) 
313                 {
314                         break;
315                 }
316         }
317         if ( i == in->height ) 
318         {
319                 wrapWidth = true;
320         }
321
322         wrapHeight = false;
323         for ( i = 0 ; i < in->width ; i++ ) 
324         {
325                 VectorSubtract( in->ctrl[i][0].xyz, 
326                                       in->ctrl[i][in->height-1].xyz, delta );
327                 len = VectorLength( delta );
328                 if ( len > 1.0 ) 
329                 {
330                         break;
331                 }
332         }
333         if ( i == in->width) 
334         {
335                 wrapHeight = true;
336         }
337
338
339         for ( i = 0 ; i < in->width ; i++ ) 
340         {
341                 for ( j = 0 ; j < in->height ; j++ ) 
342                 {
343                         count = 0;
344                         //--dv = reinterpret_cast<drawVert_t*>(in.ctrl[j*in.width+i]);
345                         dv = &in->ctrl[i][j];
346                         VectorCopy( dv->xyz, base );
347                         for ( k = 0 ; k < 8 ; k++ ) 
348                         {
349                                 VectorClear( around[k] );
350                                 good[k] = false;
351
352                                 for ( dist = 1 ; dist <= 3 ; dist++ ) 
353                                 {
354                                         x = i + neighbors[k][0] * dist;
355                                         y = j + neighbors[k][1] * dist;
356                                         if ( wrapWidth ) 
357                                         {
358                                                 if ( x < 0 ) 
359                                                 {
360                                                         x = in->width - 1 + x;
361                                                 } 
362                                                 else if ( x >= in->width ) 
363                                                 {
364                                                         x = 1 + x - in->width;
365                                                 }
366                                         }
367                                         if ( wrapHeight ) 
368                                         {
369                                                 if ( y < 0 ) 
370                                                 {
371                                                         y = in->height - 1 + y;
372                                                 } 
373                                                 else if ( y >= in->height ) 
374                                                 {
375                                                         y = 1 + y - in->height;
376                                                 }
377                                         }
378
379                                         if ( x < 0 || x >= in->width || y < 0 || y >= in->height ) 
380                                         {
381                                                 break;                                  // edge of patch
382                                         }
383                                         //--VectorSubtract( in.ctrl[y*in.width+x]->xyz, base, temp );
384                                         VectorSubtract( in->ctrl[x][y].xyz, base, temp );
385                                         if ( __VectorNormalize( temp, temp ) == 0 ) 
386                                         {
387                                                 continue;                               // degenerate edge, get more dist
388                                         } 
389                                         else                 
390                                         {
391                                                 good[k] = true;
392                                                 VectorCopy( temp, around[k] );
393                                                 break;                                  // good edge
394                                         }
395                                 }
396                         }
397
398                         VectorClear( sum );
399                         for ( k = 0 ; k < 8 ; k++ ) 
400                         {
401                                 if ( !good[k] || !good[(k+1)&7] ) 
402                                 {
403                                         continue;       // didn't get two points
404                                 }
405                                 CrossProduct( around[(k+1)&7], around[k], normal );
406                                 if ( __VectorNormalize( normal, normal ) == 0 ) 
407                                 {
408                                         continue;
409                                 }
410                                 VectorAdd( normal, sum, sum );
411                                 count++;
412                         }
413                         if ( count == 0 ) 
414                         {
415         //printf("bad normal\n");
416                                 count = 1;
417         //continue;
418                         }
419                         __VectorNormalize( sum, dv->normal );
420                 }
421         }
422 }
423
424
425
426
427 /*
428 ==================
429 Patch_CalcBounds
430 ==================
431 */
432 void Patch_CalcBounds(patchMesh_t *p, vec3_t& vMin, vec3_t& vMax)
433 {
434   vMin[0] = vMin[1] = vMin[2] = 99999;
435   vMax[0] = vMax[1] = vMax[2] = -99999;
436
437   p->bDirty = true;
438   for (int w = 0; w < p->width; w++)
439   {
440     for (int h = 0; h < p->height; h++)
441     {
442       for (int j = 0; j < 3; j++)
443       {
444         float f = p->ctrl[w][h].xyz[j];
445         if (f < vMin[j])
446           vMin[j] = f;
447         if (f > vMax[j])
448           vMax[j] = f;
449       }
450     }
451   }
452 }
453
454 /*
455 ==================
456 Brush_RebuildBrush
457 ==================
458 */
459 void Brush_RebuildBrush(brush_t *b, vec3_t vMins, vec3_t vMaxs)
460 {
461   //
462   // Total hack job 
463   // Rebuilds a brush
464         int             i, j;
465         face_t  *f, *next;
466         vec3_t  pts[4][2];
467   texdef_t      texdef;
468         // free faces
469
470   for (j = 0; j < 3; j++)
471   {
472     if ((int)vMins[j] == (int)vMaxs[j])
473     {
474       vMins[j] -= 4;
475       vMaxs[j] += 4;
476     }
477   }
478
479   
480   for (f=b->brush_faces ; f ; f=next)
481         {
482                 next = f->next;
483     if (f)
484       texdef = f->texdef;
485     Face_Free( f );
486         }
487
488   b->brush_faces = NULL;
489
490   // left the last face so we can use its texdef
491
492         for (i=0 ; i<3 ; i++)
493                 if (vMaxs[i] < vMins[i])
494                         Error ("Brush_RebuildBrush: backwards");
495
496         pts[0][0][0] = vMins[0];
497         pts[0][0][1] = vMins[1];
498         
499         pts[1][0][0] = vMins[0];
500         pts[1][0][1] = vMaxs[1];
501         
502         pts[2][0][0] = vMaxs[0];
503         pts[2][0][1] = vMaxs[1];
504         
505         pts[3][0][0] = vMaxs[0];
506         pts[3][0][1] = vMins[1];
507         
508         for (i=0 ; i<4 ; i++)
509         {
510                 pts[i][0][2] = vMins[2];
511                 pts[i][1][0] = pts[i][0][0];
512                 pts[i][1][1] = pts[i][0][1];
513                 pts[i][1][2] = vMaxs[2];
514         }
515
516         for (i=0 ; i<4 ; i++)
517         {
518                 f = Face_Alloc();
519                 f->texdef = texdef;
520                 f->texdef.flags &= ~SURF_KEEP;
521                 f->texdef.contents &= ~CONTENTS_KEEP;
522 //              f->texdef.flags |= SURF_PATCH; 
523                 f->next = b->brush_faces;
524                 b->brush_faces = f;
525                 j = (i+1)%4;
526
527                 VectorCopy (pts[j][1], f->planepts[0]);
528                 VectorCopy (pts[i][1], f->planepts[1]);
529                 VectorCopy (pts[i][0], f->planepts[2]);
530         }
531         
532         f = Face_Alloc();
533         f->texdef = texdef;
534   f->texdef.flags &= ~SURF_KEEP;
535         f->texdef.contents &= ~CONTENTS_KEEP;
536 //  f->texdef.flags |= SURF_PATCH; 
537         f->next = b->brush_faces;
538         b->brush_faces = f;
539
540         VectorCopy (pts[0][1], f->planepts[0]);
541         VectorCopy (pts[1][1], f->planepts[1]);
542         VectorCopy (pts[2][1], f->planepts[2]);
543
544         f = Face_Alloc();
545         f->texdef = texdef;
546   f->texdef.flags &= ~SURF_KEEP;
547         f->texdef.contents &= ~CONTENTS_KEEP;
548 //  f->texdef.flags |= SURF_PATCH; 
549         f->next = b->brush_faces;
550         b->brush_faces = f;
551
552         VectorCopy (pts[2][0], f->planepts[0]);
553         VectorCopy (pts[1][0], f->planepts[1]);
554         VectorCopy (pts[0][0], f->planepts[2]);
555
556   Brush_Build(b);
557 }
558
559 void WINAPI Patch_Rebuild(patchMesh_t *p)
560 {
561   vec3_t vMin, vMax;
562   Patch_CalcBounds(p, vMin, vMax);
563   Brush_RebuildBrush(p->pSymbiot, vMin, vMax);
564   p->bDirty = true;
565 }
566
567 /*
568 ==================
569 AddBrushForPatch
570 ==================
571  adds a patch brush and ties it to this patch id
572 */
573 brush_t* AddBrushForPatch(patchMesh_t *pm, bool bLinkToWorld )
574 {
575   // find the farthest points in x,y,z
576   vec3_t vMin, vMax;
577   Patch_CalcBounds(pm, vMin, vMax);
578
579   for (int j = 0; j < 3; j++)
580   {
581     if (vMin[j] == vMax[j])
582     {
583       vMin[j] -= 4;
584       vMax[j] += 4;
585     }
586   }
587
588   brush_t *b = Brush_Create(vMin, vMax, &g_qeglobals.d_texturewin.texdef);
589
590   // FIXME: this entire type of linkage needs to be fixed
591   b->patchBrush = true;
592   b->pPatch = pm;
593   pm->pSymbiot = b;
594   pm->bSelected = false;
595   pm->bOverlay = false;
596   pm->bDirty = true;
597   pm->nListID = -1;
598
599   if (bLinkToWorld)
600   {
601     Brush_AddToList (b, &active_brushes);
602           Entity_LinkBrush (world_entity, b);
603     Brush_Build(b);
604   }
605
606   return b;
607 }
608
609 void Patch_SetPointIntensities(int n)
610 {
611 #if 0
612         patchMesh_t     *p = patchMeshes[n];
613   for (int i = 0; i < p->width; i++)
614   {
615     for (int j = 0; j < p->height; j++)
616     {
617
618     }
619   }
620 #endif
621 }
622
623 // very approximate widths and heights
624
625 /*
626 ==================
627 Patch_Width
628 ==================
629 */
630 float Patch_Width(patchMesh_t *p)
631 {
632   float f = 0;
633   for (int i = 0; i < p->width-1; i++)
634   {
635     vec3_t vTemp;
636     VectorSubtract(p->ctrl[i][0].xyz, p->ctrl[i+1][0].xyz, vTemp);
637     f += VectorLength(vTemp);
638   }
639   return f;
640 }
641
642 float Patch_WidthDistanceTo(patchMesh_t *p, int j)
643 {
644   float f = 0;
645   for (int i = 0; i < j; i++)
646   {
647     vec3_t vTemp;
648     VectorSubtract(p->ctrl[i][0].xyz, p->ctrl[i+1][0].xyz, vTemp);
649     f += VectorLength(vTemp);
650   }
651   return f;
652 }
653
654
655
656 /*
657 ==================
658 Patch_Height
659 ==================
660 */
661 float Patch_Height(patchMesh_t *p)
662 {
663   float f = 0;
664   for (int i = 0; i < p->height-1; i++)
665   {
666     vec3_t vTemp;
667     VectorSubtract(p->ctrl[0][i].xyz, p->ctrl[0][i+1].xyz, vTemp);
668     f += VectorLength(vTemp);
669   }
670   return f;
671 }
672
673 float Patch_HeightDistanceTo(patchMesh_t *p, int j)
674 {
675   float f = 0;
676   for (int i = p->height-1; i > j; i--)
677   {
678     vec3_t vTemp;
679     VectorSubtract(p->ctrl[0][i].xyz, p->ctrl[0][i-1].xyz, vTemp); // reverse order for T coords
680     f += VectorLength(vTemp);
681   }
682   return f;
683 }
684
685
686
687 /*
688 ==================
689 Patch_Naturalize
690 ==================
691 texture = TotalTexture * LengthToThisControlPoint / TotalControlPointLength
692
693 dist( this control point to first control point ) / dist ( last control pt to first)
694 */
695 void WINAPI Patch_Naturalize(patchMesh_t *p)
696 {
697   int nWidth = (int)(p->d_texture->width * g_pGameDescription->mTextureDefaultScale);
698   int nHeight = (int)(p->d_texture->height * g_pGameDescription->mTextureDefaultScale);
699   float fPWidth = Patch_Width(p);
700   float fPHeight = Patch_Height(p);
701   float xAccum = 0.0f;
702
703   for ( int i = 0; i < p->width ; i++ ) 
704   {
705         float yAccum = 0.0f;
706         for ( int j = p->height-1; j >= 0 ; j-- ) 
707         {
708           p->ctrl[i][j].st[0] = (fPWidth / nWidth) * xAccum / fPWidth;
709           p->ctrl[i][j].st[1] = (fPHeight / nHeight) * yAccum / fPHeight;
710            yAccum = Patch_HeightDistanceTo(p,j-1);
711           //p->ctrl[i][j][3] = (fPWidth / nWidth) * (float)i / (p->width - 1);
712           //p->ctrl[i][j][4] = (fPHeight/ nHeight) * (float)j / (p->height - 1);
713         }
714         xAccum = Patch_WidthDistanceTo(p,i+1);
715   }
716   p->bDirty = true;
717 }
718
719 /*
720   if (bIBevel)
721   {
722     VectorCopy(p->ctrl[1][0], p->ctrl[1][1]);
723   }
724
725   if (bIEndcap)
726   {
727     VectorCopy(p->ctrl[3][0], p->ctrl[4][1]);
728     VectorCopy(p->ctrl[2][0], p->ctrl[3][1]);
729     VectorCopy(p->ctrl[2][0], p->ctrl[2][1]);
730     VectorCopy(p->ctrl[2][0], p->ctrl[1][1]);
731     VectorCopy(p->ctrl[1][0], p->ctrl[0][1]);
732     VectorCopy(p->ctrl[1][0], p->ctrl[0][2]);
733     VectorCopy(p->ctrl[1][0], p->ctrl[1][2]);
734     VectorCopy(p->ctrl[2][0], p->ctrl[2][2]);
735     VectorCopy(p->ctrl[3][0], p->ctrl[3][2]);
736     VectorCopy(p->ctrl[3][0], p->ctrl[4][2]);
737   }
738 */
739
740 int Index3By[][2] =
741 {
742   {0,0},
743   {1,0},
744   {2,0},
745   {2,1},
746   {2,2},
747   {1,2},
748   {0,2},
749   {0,1},
750   {0,0},
751   {0,0},
752   {0,0},
753   {0,0},
754   {0,0},
755   {0,0},
756   {0,0}
757 };
758
759 int Index5By[][2] =
760 {
761   {0,0},
762   {1,0},
763   {2,0},
764   {3,0},
765   {4,0},
766   {4,1},
767   {4,2},
768   {4,3},
769   {4,4},
770   {3,4},
771   {2,4},
772   {1,4},
773   {0,4},
774   {0,3},
775   {0,2},
776   {0,1}
777 };
778
779
780
781 int Interior3By[][2] =
782 {
783   {1,1}
784 };
785
786 int Interior5By[][2] =
787 {
788   {1,1},
789   {2,1},
790   {3,1},
791   {1,2},
792   {2,2},
793   {3,2},
794   {1,3},
795   {2,3},
796   {3,3}
797 };
798
799 int Interior3ByCount = sizeof(Interior3By) / sizeof(int[2]);
800 int Interior5ByCount = sizeof(Interior5By) / sizeof(int[2]);
801
802 extern int Plane_FromPoints(vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane);
803 // the bFaceCycle only means we are going through a patch cycling loop
804 // then we rely on g_vCycleCapNormal to compute the cap
805
806 void Patch_CapTexture(patchMesh_t *p, bool bFaceCycle = false)
807 {
808         vec3_t vProjection, vX, vY;
809         qtexture_t *texture = p->pShader->getTexture();
810         plane_t Plane1, Plane2, Plane3;
811         bool bThing=true;
812
813         if (bFaceCycle)
814                 VectorCopy (g_vCycleCapNormal, vProjection);
815
816         else
817         {
818                 VectorClear ( vProjection );
819
820                 // find normal for plane from first 3 corner points
821                 if (!Plane_FromPoints(p->ctrl[0][0].xyz,p->ctrl[0][p->height-1].xyz,p->ctrl[p->width-1][p->height-1].xyz,&Plane1))
822                 {
823                         VectorClear ( Plane3.normal );
824                         bThing = false;
825                 }
826                 
827                 // find normal for plane from next 3 corner points
828                 if (!Plane_FromPoints(p->ctrl[p->width-1][p->height-1].xyz,p->ctrl[p->width-1][0].xyz,p->ctrl[0][0].xyz,&Plane2))
829                 {
830                         if (bThing)
831                         {       
832                                 VectorCopy ( Plane1.normal, Plane3.normal );
833                                 Plane3.dist = Plane1.dist;
834                         }
835                 }
836
837                 else
838                 {
839                         if (bThing)
840                                 // find average plane for all 4 corner points
841                         {
842                                 for (int n = 0; n <= 2; n++)
843                                 {
844                                         Plane3.normal[n] = (Plane1.normal[n] + Plane2.normal[n]) / 2;
845                                 }
846                                 Plane3.dist = (Plane1.dist + Plane2.dist) / 2;
847                         }
848                         else
849                         {
850                                 VectorCopy ( Plane2.normal, Plane3.normal );
851                                 Plane3.dist = Plane2.dist;
852                         }
853                 }
854
855                 // get best axis for projection from average plane
856                 //Sys_Printf("surface normal1: (%f,%f,%f)\n",Plane1.normal[0],Plane1.normal[1],Plane1.normal[0]);
857                 //Sys_Printf("surface normal2: (%f,%f,%f)\n",Plane2.normal[0],Plane2.normal[1],Plane2.normal[0]);
858                 //Sys_Printf("surface normal3: (%f,%f,%f)\n",Plane3.normal[0],Plane3.normal[1],Plane3.normal[0]);
859                 TextureAxisFromPlane(&Plane3, vX, vY);
860         }
861
862         for (int w = 0; w < p->width; w++)
863         {
864                 for (int h = 0; h < p->height; h++)
865                 {
866                         if (vProjection[2] == 1.0f || (vX[0] == 1.0f && vY[1] == -1.0f))
867                         {
868                                 p->ctrl[w][h].st[0] = p->ctrl[w][h].xyz[0] / (texture->width * g_pGameDescription->mTextureDefaultScale);
869                                 p->ctrl[w][h].st[1] = p->ctrl[w][h].xyz[1] / (texture->height * g_pGameDescription->mTextureDefaultScale) * -1;
870                         }
871                         else if (vProjection[0] == 1.0f || (vX[1] == 1.0f && vY[2] == -1.0f))
872                         {
873                                 p->ctrl[w][h].st[0] = p->ctrl[w][h].xyz[1] / (texture->width * g_pGameDescription->mTextureDefaultScale);
874                                 p->ctrl[w][h].st[1] = p->ctrl[w][h].xyz[2] / (texture->height * g_pGameDescription->mTextureDefaultScale) * -1;
875                         }
876                         else if (vProjection[1] == 1.0f || (vX[0] == 1.0f && vY[2] == -1.0f))
877                         {
878                                 p->ctrl[w][h].st[0] = p->ctrl[w][h].xyz[0] / (texture->width * g_pGameDescription->mTextureDefaultScale);
879                                 p->ctrl[w][h].st[1] = p->ctrl[w][h].xyz[2] / (texture->height * g_pGameDescription->mTextureDefaultScale) * -1;
880                         }
881                         //Sys_Printf("(%i,%i) (%f,%f,%f) (%f,%f) %f\n",w,h,
882                         //      p->ctrl[w][h].xyz[0],p->ctrl[w][h].xyz[1],p->ctrl[w][h].xyz[2],
883                         //      p->ctrl[w][h].st[0],p->ctrl[w][h].st[1],p->ctrl[w][h].normal);
884                 }
885         }
886         // make sure it will rebuild
887         p->bDirty = true;
888 }
889
890 void FillPatch(patchMesh_t *p, vec3_t v)
891 {
892   for (int i = 0; i < p->width; i++)
893   {
894     for (int j = 0; j < p->height; j++)
895     {
896       VectorCopy(v, p->ctrl[i][j].xyz);
897     }
898   }
899 }
900
901 // temporarily moved function to allow use in Cap() and CapSpecial()
902 void patchInvert(patchMesh_t *p)
903 {
904   drawVert_t vertTemp;
905   p->bDirty = true;
906         for ( int i = 0 ; i < p->width ; i++ ) 
907   {
908     for (int j = 0; j < p->height / 2; j++)
909     {
910       memcpy(&vertTemp, &p->ctrl[i][p->height - 1- j], sizeof (drawVert_t));
911       memcpy(&p->ctrl[i][p->height - 1 - j], &p->ctrl[i][j], sizeof(drawVert_t));
912       memcpy(&p->ctrl[i][j], &vertTemp, sizeof(drawVert_t));
913                 }
914         }
915 }
916
917 brush_t* Cap(patchMesh_t *pParent, bool bByColumn, bool bFirst)
918 {
919   brush_t *b;
920   patchMesh_t *p;
921   vec3_t vMin, vMax;
922   int i, j;
923
924   bool bSmall = true;
925   // make a generic patch
926   if (pParent->width <= 9)
927   {
928     b = Patch_GenericMesh(3, 3, 2, false);
929   }
930   else
931   {
932     b = Patch_GenericMesh(5, 5, 2, false);
933     bSmall = false;
934   }
935
936   if (!b)
937   {
938     Sys_Printf("Unable to cap. You may need to ungroup the patch.\n");
939     return NULL;
940   }
941
942   p = b->pPatch;
943   p->type |= PATCH_CAP;
944
945   vMin[0] = vMin[1] = vMin[2] = 9999;
946   vMax[0] = vMax[1] = vMax[2] = -9999;
947
948   // we seam the column edge, FIXME: this might need to be able to seem either edge
949   // 
950   int nSize = (bByColumn) ? pParent->width : pParent->height;
951   int nIndex = (bFirst) ? 0 : (bByColumn) ? pParent->height-1 : pParent->width-1;
952
953   FillPatch(p, pParent->ctrl[0][nIndex].xyz);
954
955   for (i = 0; i < nSize; i++)
956   {
957     if (bByColumn)
958     {
959       if (bSmall)
960       {
961         VectorCopy(pParent->ctrl[i][nIndex].xyz, p->ctrl[Index3By[i][0]][Index3By[i][1]].xyz);
962       }
963       else
964       {
965         VectorCopy(pParent->ctrl[i][nIndex].xyz, p->ctrl[Index5By[i][0]][Index5By[i][1]].xyz);
966       }
967     }
968     else
969     {
970       if (bSmall)
971       {
972         VectorCopy(pParent->ctrl[nIndex][i].xyz, p->ctrl[Index3By[i][0]][Index3By[i][1]].xyz);
973       }
974       else
975       {
976         VectorCopy(pParent->ctrl[nIndex][i].xyz, p->ctrl[Index5By[i][0]][Index5By[i][1]].xyz);
977       }
978     }
979   
980     for (j = 0; j < 3; j++)
981     {
982       float f = (bSmall) ? p->ctrl[Index3By[i][0]][Index3By[i][1]].xyz[j] : p->ctrl[Index5By[i][0]][Index5By[i][1]].xyz[j];
983       if (f < vMin[j])
984         vMin[j] = f;
985       if (f > vMax[j])
986         vMax[j] = f;
987     }
988   }
989
990   vec3_t vTemp;
991   for (j = 0; j < 3; j++)
992   {
993     vTemp[j] = vMin[j] + fabs((vMax[j] - vMin[j]) * 0.5);
994   }
995   int nCount = (bSmall) ? Interior3ByCount : Interior5ByCount;
996   for (j = 0; j < nCount; j++)
997   {
998     if (bSmall)
999     {
1000       VectorCopy(vTemp, p->ctrl[Interior3By[j][0]][Interior3By[j][1]].xyz);
1001     }
1002     else
1003     {
1004       VectorCopy(vTemp, p->ctrl[Interior5By[j][0]][Interior5By[j][1]].xyz);
1005     }
1006   }
1007
1008   if (bFirst)
1009           patchInvert(p);
1010   /*
1011   {
1012     drawVert_t vertTemp;
1013     for (i = 0; i < p->width; i++)
1014     {
1015       for (j = 0; j < p->height / 2; j++)
1016       {
1017         memcpy(&vertTemp, &p->ctrl[i][p->height - 1- j], sizeof (drawVert_t));
1018         memcpy(&p->ctrl[i][p->height - 1 - j], &p->ctrl[i][j], sizeof(drawVert_t));
1019         memcpy(&p->ctrl[i][j], &vertTemp, sizeof(drawVert_t));
1020       }
1021     }
1022   }
1023   */
1024
1025   Patch_Rebuild(p);
1026   Patch_CapTexture(p);
1027   return p->pSymbiot;
1028 }
1029
1030 brush_t* CapSpecial(patchMesh_t *pParent, int nType, bool bFirst)
1031 {
1032
1033   brush_t *b;
1034   patchMesh_t *p;
1035   vec3_t vMin, vMax, vTemp;
1036   int i, j;
1037
1038   if (nType == IENDCAP)
1039     b = Patch_GenericMesh(5, 3, 2, false);
1040   else
1041     b = Patch_GenericMesh(3, 3, 2, false);
1042
1043   if (!b)
1044   {
1045     Sys_Printf("Unable to cap. Make sure you ungroup before re-capping.");
1046     return NULL;
1047   }
1048
1049   p = b->pPatch;
1050   p->type |= PATCH_CAP;
1051
1052   vMin[0] = vMin[1] = vMin[2] = 9999;
1053   vMax[0] = vMax[1] = vMax[2] = -9999;
1054
1055   //  int nSize = pParent->width;
1056   int nIndex = (bFirst) ? 0 : pParent->height-1;
1057
1058   // parent bounds are used for some things
1059   Patch_CalcBounds(pParent, vMin, vMax);
1060
1061   for (j = 0; j < 3; j++)
1062   {
1063     vTemp[j] = vMin[j] + fabs((vMax[j] - vMin[j]) * 0.5);
1064   }
1065   
1066   if (nType == IBEVEL)
1067   {
1068     VectorCopy(pParent->ctrl[0][nIndex].xyz, p->ctrl[0][0].xyz);
1069     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[0][2].xyz);
1070     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[0][1].xyz);
1071     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[2][2].xyz);
1072     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[1][0].xyz);
1073     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[1][1].xyz);
1074     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[1][2].xyz);
1075     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[2][0].xyz);
1076     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[2][1].xyz);
1077   }
1078   else if (nType == BEVEL)
1079   {
1080     vec3_t p1, p2, p3, p4; //, temp, dir;
1081
1082     VectorCopy(pParent->ctrl[0][nIndex].xyz, p3);
1083     VectorCopy(pParent->ctrl[1][nIndex].xyz, p1);
1084     VectorCopy(pParent->ctrl[2][nIndex].xyz, p2);
1085         
1086         //Sys_Printf("CapSpecial() p1: %f %f %f\n",p1[0],p1[1],p1[2]);
1087         //Sys_Printf("CapSpecial() p2: %f %f %f\n",p2[0],p2[1],p2[2]);
1088         //Sys_Printf("CapSpecial() p3: %f %f %f\n",p3[0],p3[1],p3[2]);
1089         
1090         VectorSubtract(p2, p1, p4);
1091         VectorAdd(p3, p4, p4);
1092         // spog - use opposite-point-on-parallelogram to find p4
1093         /*
1094     VectorSubtract(p3, p2, dir);
1095     VectorNormalize(dir);
1096     VectorSubtract(p1, p2, temp);
1097     vec_t dist = _DotProduct(temp, dir);
1098     VectorScale(dir, dist, temp);
1099     VectorAdd(p2, temp, temp);
1100     VectorSubtract(temp, p1, temp);
1101     VectorScale(temp, 2, temp);
1102     VectorAdd(p1, temp, p4);
1103         */
1104
1105         //Sys_Printf("CapSpecial() p1: %f %f %f\n",p1[0],p1[1],p1[2]);
1106         //Sys_Printf("CapSpecial() p2: %f %f %f\n",p2[0],p2[1],p2[2]);
1107         //Sys_Printf("CapSpecial() p3: %f %f %f\n",p3[0],p3[1],p3[2]);
1108         //Sys_Printf("CapSpecial() p4: %f %f %f\n",p4[0],p4[1],p4[2]);
1109
1110     VectorCopy(p4, p->ctrl[0][0].xyz);
1111     VectorCopy(p4, p->ctrl[1][0].xyz);
1112     VectorCopy(p4, p->ctrl[0][1].xyz);
1113     VectorCopy(p4, p->ctrl[1][1].xyz);
1114     VectorCopy(p4, p->ctrl[0][2].xyz);
1115     VectorCopy(p4, p->ctrl[1][2].xyz);
1116     VectorCopy(p2, p->ctrl[2][0].xyz);
1117     VectorCopy(p1, p->ctrl[2][1].xyz);
1118     VectorCopy(p3, p->ctrl[2][2].xyz);
1119
1120   }
1121   else if (nType == ENDCAP)
1122   {
1123     VectorAdd(pParent->ctrl[4][nIndex].xyz, pParent->ctrl[0][nIndex].xyz, vTemp);
1124     VectorScale(vTemp, 0.5, vTemp);
1125     VectorCopy(pParent->ctrl[0][nIndex].xyz, p->ctrl[0][0].xyz);
1126                                                    VectorCopy(vTemp, p->ctrl[1][0].xyz);
1127     VectorCopy(pParent->ctrl[4][nIndex].xyz, p->ctrl[2][0].xyz);
1128
1129     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[0][2].xyz);
1130     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[1][2].xyz);
1131     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[2][2].xyz);
1132     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[1][1].xyz);
1133     
1134     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[0][1].xyz);
1135     VectorCopy(pParent->ctrl[3][nIndex].xyz, p->ctrl[2][1].xyz);
1136   }
1137   else
1138   {
1139     VectorCopy(pParent->ctrl[4][nIndex].xyz, p->ctrl[0][0].xyz);
1140     VectorCopy(pParent->ctrl[3][nIndex].xyz, p->ctrl[1][0].xyz);
1141     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[2][0].xyz);
1142     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[3][0].xyz);
1143     VectorCopy(pParent->ctrl[0][nIndex].xyz, p->ctrl[4][0].xyz);
1144     
1145     VectorCopy(pParent->ctrl[3][nIndex].xyz, p->ctrl[0][1].xyz);
1146     VectorCopy(pParent->ctrl[3][nIndex].xyz, p->ctrl[1][1].xyz);
1147     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[2][1].xyz);
1148     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[3][1].xyz);
1149     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[4][1].xyz);
1150
1151     VectorCopy(pParent->ctrl[3][nIndex].xyz, p->ctrl[0][2].xyz);
1152     VectorCopy(pParent->ctrl[3][nIndex].xyz, p->ctrl[1][2].xyz);
1153     VectorCopy(pParent->ctrl[2][nIndex].xyz, p->ctrl[2][2].xyz);
1154     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[3][2].xyz);
1155     VectorCopy(pParent->ctrl[1][nIndex].xyz, p->ctrl[4][2].xyz);
1156   }
1157
1158
1159   if (!bFirst)
1160   {
1161     drawVert_t vertTemp;
1162     for (i = 0; i < p->width; i++)
1163     {
1164       for (j = 0; j < p->height / 2; j++)
1165       {
1166         memcpy(&vertTemp, &p->ctrl[i][p->height - 1- j], sizeof (drawVert_t));
1167         memcpy(&p->ctrl[i][p->height - 1 - j], &p->ctrl[i][j], sizeof(drawVert_t));
1168         memcpy(&p->ctrl[i][j], &vertTemp, sizeof(drawVert_t));
1169       }
1170     }
1171   }
1172
1173   //--Patch_CalcBounds(p, vMin, vMax);
1174   //--Brush_RebuildBrush(p->pSymbiot, vMin, vMax);
1175   Patch_Rebuild(p);
1176   Patch_CapTexture(p);
1177   return p->pSymbiot;
1178 }
1179
1180 void Patch_CapCurrent()
1181 {
1182   patchMesh_t *pParent = NULL;
1183   brush_t *b[4];
1184   brush_t *pCap = NULL;
1185   b[0] = b[1] = b[2] = b[3] = NULL;
1186   int nIndex = 0;
1187   bool b_GroupResult = TRUE;
1188   
1189   if (!QE_SingleBrush(true))
1190   {
1191     Sys_Printf("Patch_CapCurrent: you must have a single patch selected\n");
1192     return;
1193   }
1194   
1195   
1196   for (brush_t *pb = selected_brushes.next ; pb != NULL && pb != &selected_brushes ; pb = pb->next)
1197   {
1198     if (pb->patchBrush)
1199     {
1200       pParent = pb->pPatch;
1201       // decide which if any ends we are going to cap
1202       // if any of these compares hit, it is a closed patch and as such
1203       // the generic capping will work.. if we do not find a closed edge 
1204       // then we need to ask which kind of cap to add
1205       if (VectorCompare(pParent->ctrl[0][0].xyz, pParent->ctrl[pParent->width-1][0].xyz))
1206       {
1207         pCap = Cap(pParent, true, false);
1208         if (pCap != NULL)
1209         {
1210           b[nIndex++] = pCap;
1211         }
1212       }
1213       if (VectorCompare(pParent->ctrl[0][pParent->height-1].xyz, pParent->ctrl[pParent->width-1][pParent->height-1].xyz))
1214       {
1215         pCap = Cap(pParent, true, true);
1216         if (pCap != NULL)
1217         {
1218           b[nIndex++] = pCap;
1219         }
1220       }
1221       if (VectorCompare(pParent->ctrl[0][0].xyz, pParent->ctrl[0][pParent->height-1].xyz))
1222       {
1223         pCap = Cap(pParent, false, false);
1224         if (pCap != NULL)
1225         {
1226           b[nIndex++] = pCap;
1227         }
1228       }
1229       if (VectorCompare(pParent->ctrl[pParent->width-1][0].xyz, pParent->ctrl[pParent->width-1][pParent->height-1].xyz))
1230       {
1231         pCap = Cap(pParent, false, true);
1232         if (pCap != NULL)
1233         {
1234           b[nIndex++] = pCap;
1235         }
1236       }
1237     }
1238   }
1239   
1240   if (pParent)
1241   {
1242     // if we did not cap anything with the above tests
1243     if (nIndex == 0)
1244     {
1245       int type;
1246       
1247       if (DoCapDlg (&type, &b_GroupResult) == IDOK)
1248       {
1249         b[nIndex++] = CapSpecial(pParent, type, false);
1250         b[nIndex++] = CapSpecial(pParent, type, true);
1251       }
1252     }
1253     
1254     if (nIndex > 0)
1255     {
1256       while (nIndex > 0)
1257       {
1258         nIndex--;
1259         if (b[nIndex])
1260         {
1261           Select_Brush(b[nIndex]);
1262         }
1263       }
1264       // Gef: Added toggle for capped patch func_group
1265       if(b_GroupResult) {
1266         entity_t *e = Entity_Alloc();
1267         SetKeyValue(e, "classname", "func_group");
1268         SetKeyValue(e, "type", "patchCapped");
1269         Select_GroupEntity(e);
1270         Entity_AddToList(e, &entities);
1271       }
1272     }
1273   }
1274 }
1275
1276 /*
1277 ===============
1278 BrushToPatchMesh
1279 ===============
1280 */
1281 void Patch_BrushToMesh(bool bCone, bool bBevel, bool bEndcap, bool bSquare, int nHeight)
1282 {
1283         brush_t         *b;
1284         patchMesh_t     *p;
1285         int                     i,j;
1286
1287         if (!QE_SingleBrush())
1288                 return;
1289
1290         b = selected_brushes.next;
1291
1292         p = MakeNewPatch();
1293
1294         p->d_texture = b->brush_faces->d_texture;
1295         p->pShader = b->brush_faces->pShader;
1296
1297   p->height = nHeight;
1298
1299   p->type = PATCH_CYLINDER;
1300   if (bBevel & !bSquare)
1301   {
1302     p->type = PATCH_BEVEL;
1303     p->width = 3;
1304     int nStep = (int)((b->maxs[2] - b->mins[2]) / (p->height-1));
1305     int nStart = (int)(b->mins[2]);
1306     for (i = 0; i < p->height; i++)
1307     {
1308             p->ctrl[0][i].xyz[0] =  b->mins[0];
1309             p->ctrl[0][i].xyz[1] =  b->mins[1];
1310       p->ctrl[0][i].xyz[2] = nStart;
1311
1312             p->ctrl[1][i].xyz[0] =  b->maxs[0];
1313             p->ctrl[1][i].xyz[1] =  b->mins[1];
1314       p->ctrl[1][i].xyz[2] = nStart;
1315
1316             p->ctrl[2][i].xyz[0] =  b->maxs[0];
1317             p->ctrl[2][i].xyz[1] =  b->maxs[1];
1318       p->ctrl[2][i].xyz[2] = nStart;
1319       nStart += nStep;
1320     }
1321   }
1322   else if (bEndcap & !bSquare)
1323   {
1324     p->type = PATCH_ENDCAP;
1325     p->width = 5;
1326     int nStep = (int)((b->maxs[2] - b->mins[2]) / (p->height-1));
1327     int nStart = (int)(b->mins[2]);
1328     for (i = 0; i < p->height; i++)
1329     {
1330       p->ctrl[0][i].xyz[0] =  b->mins[0];
1331       p->ctrl[0][i].xyz[1] =  b->mins[1];
1332       p->ctrl[0][i].xyz[2] = nStart;
1333
1334       p->ctrl[1][i].xyz[0] =  b->mins[0];
1335       p->ctrl[1][i].xyz[1] =  b->maxs[1];
1336       p->ctrl[1][i].xyz[2] = nStart;
1337
1338       p->ctrl[2][i].xyz[0] =  b->mins[0] + ((b->maxs[0] - b->mins[0]) * 0.5);
1339       p->ctrl[2][i].xyz[1] =  b->maxs[1];
1340       p->ctrl[2][i].xyz[2] = nStart;
1341            
1342       p->ctrl[3][i].xyz[0] =  b->maxs[0];
1343       p->ctrl[3][i].xyz[1] =  b->maxs[1];
1344       p->ctrl[3][i].xyz[2] = nStart;
1345
1346       p->ctrl[4][i].xyz[0] =  b->maxs[0];
1347       p->ctrl[4][i].xyz[1] =  b->mins[1];
1348       p->ctrl[4][i].xyz[2] = nStart;
1349       nStart += nStep;
1350     }
1351   }
1352   else
1353   {
1354     p->width = 9;
1355     p->ctrl[1][0].xyz[0] =  b->mins[0];
1356     p->ctrl[1][0].xyz[1] =  b->mins[1];
1357
1358     p->ctrl[3][0].xyz[0] =  b->maxs[0];
1359     p->ctrl[3][0].xyz[1] =  b->mins[1];
1360
1361     p->ctrl[5][0].xyz[0] =  b->maxs[0];
1362     p->ctrl[5][0].xyz[1] =  b->maxs[1];
1363
1364     p->ctrl[7][0].xyz[0] =  b->mins[0];
1365     p->ctrl[7][0].xyz[1] =  b->maxs[1];
1366
1367     for ( i = 1 ; i < p->width - 1 ; i += 2 ) 
1368     {
1369
1370       p->ctrl[i][0].xyz[2] =  b->mins[2];
1371
1372                   VectorCopy( p->ctrl[i][0].xyz, p->ctrl[i][2].xyz );
1373
1374                   p->ctrl[i][2].xyz[2] =  b->maxs[2];
1375
1376                   p->ctrl[i][1].xyz[0] = ( p->ctrl[i][0].xyz[0] + p->ctrl[i][2].xyz[0] ) * 0.5;
1377                   p->ctrl[i][1].xyz[1] = ( p->ctrl[i][0].xyz[1] + p->ctrl[i][2].xyz[1] ) * 0.5;
1378                   p->ctrl[i][1].xyz[2] = ( p->ctrl[i][0].xyz[2] + p->ctrl[i][2].xyz[2] ) * 0.5;
1379           }
1380           InterpolateInteriorPoints( p );
1381
1382     if (bSquare)
1383     {
1384       if (bBevel || bEndcap)
1385       {
1386         if (bBevel)
1387         {
1388           for (i = 0; i < p->height; i++)
1389           {
1390             VectorCopy(p->ctrl[1][i].xyz, p->ctrl[2][i].xyz);
1391             VectorCopy(p->ctrl[7][i].xyz, p->ctrl[6][i].xyz);
1392           }
1393         }
1394         else
1395         {
1396           for (i = 0; i < p->height; i++)
1397           {
1398             VectorCopy(p->ctrl[5][i].xyz, p->ctrl[4][i].xyz);
1399             VectorCopy(p->ctrl[1][i].xyz, p->ctrl[2][i].xyz);
1400             VectorCopy(p->ctrl[7][i].xyz, p->ctrl[6][i].xyz);
1401             VectorCopy(p->ctrl[8][i].xyz, p->ctrl[7][i].xyz);
1402           }
1403         }
1404       }
1405       else
1406       {
1407         for (i = 0; i < p->width-1; i ++)
1408         {
1409           for (j = 0; j < p->height; j++)
1410           {
1411             VectorCopy(p->ctrl[i+1][j].xyz, p->ctrl[i][j].xyz);
1412           }
1413         }
1414         for (j = 0; j < p->height; j++)
1415         {
1416           VectorCopy(p->ctrl[0][j].xyz, p->ctrl[8][j].xyz);
1417         }
1418       }
1419     }
1420   }
1421
1422
1423   Patch_Naturalize(p);
1424
1425   if (bCone)
1426   {
1427     p->type = PATCH_CONE;
1428     float xc = (b->maxs[0] + b->mins[0]) * 0.5; 
1429     float yc = (b->maxs[1] + b->mins[1]) * 0.5; 
1430
1431     for ( i = 0 ; i < p->width ; i ++)
1432     {
1433       p->ctrl[i][2].xyz[0] = xc;
1434       p->ctrl[i][2].xyz[1] = yc;
1435     }
1436   }
1437   
1438   b = AddBrushForPatch(p);
1439
1440   Select_Delete();
1441   Select_Brush(b);
1442
1443 }
1444
1445 /*
1446 ==================
1447 Patch_GenericMesh
1448 ==================
1449 */
1450 brush_t* Patch_GenericMesh(int nWidth, int nHeight, int nOrientation, bool bDeleteSource, bool bOverride)
1451 {
1452   int i,j;
1453
1454   if (nHeight < 3 || nHeight > 15 || nWidth < 3 || nWidth > 15)
1455   {
1456     Sys_Printf("Invalid patch width or height.\n");
1457     return NULL;
1458   }
1459
1460         if (! bOverride && !QE_SingleBrush())
1461   {
1462     Sys_Printf("Error: you must have a single brush selected\n");
1463                 return NULL;
1464   }
1465
1466   patchMesh_t* p = MakeNewPatch();
1467   p->pShader = g_qeglobals.d_texturewin.pShader;
1468   p->d_texture = g_qeglobals.d_texturewin.pShader->getTexture();
1469
1470         p->width = nWidth;
1471         p->height = nHeight;
1472   p->type = PATCH_GENERIC;
1473
1474   int nFirst = 0;
1475   int nSecond = 1;
1476   if (nOrientation == 0)
1477   {
1478     nFirst = 1;
1479     nSecond = 2;
1480   }
1481   else if (nOrientation == 1)
1482   {
1483     nSecond = 2;
1484   }
1485
1486         brush_t *b = selected_brushes.next;
1487         // set the workzone to this brush, use it later to create the patch points
1488         UpdateWorkzone_ForBrush( b );
1489
1490   int xStep = (int)(b->mins[nFirst]);
1491   float xAdj = fabs((b->maxs[nFirst] - b->mins[nFirst]) / (nWidth - 1));
1492   float yAdj = fabs((b->maxs[nSecond] - b->mins[nSecond]) / (nHeight - 1));
1493
1494   for (i = 0; i < nWidth; i++)
1495   {
1496     int yStep = (int)(b->mins[nSecond]);
1497     for (j = 0; j < nHeight; j++)
1498     {
1499       p->ctrl[i][j].xyz[nFirst] = xStep;
1500       p->ctrl[i][j].xyz[nSecond] = yStep;
1501       // create patch based on workzone
1502       p->ctrl[i][j].xyz[nOrientation] = g_qeglobals.d_work_max[nOrientation];
1503       yStep += (int)yAdj;
1504     }
1505     xStep += (int)xAdj;
1506   }
1507
1508   Patch_Naturalize(p);
1509
1510   b = AddBrushForPatch(p);
1511   if (bDeleteSource)
1512   {
1513     Select_Delete();
1514     Select_Brush(b);
1515   }
1516
1517   return b;
1518   //g_qeglobals.d_select_mode = sel_curvepoint;
1519 }
1520
1521 /*
1522 ==================
1523 PointInMoveList
1524 ==================
1525 */
1526 int PointInMoveList(float *pf)
1527 {
1528   for (int i = 0; i < g_qeglobals.d_num_move_points; i++)
1529   {
1530     if (pf == &g_qeglobals.d_move_points[i][0])
1531       return i;
1532   }
1533   return -1;
1534 }
1535
1536 /*
1537 ==================
1538 PointValueInMoveList
1539 ==================
1540 */
1541 int PointValueInMoveList(vec3_t v)
1542 {
1543   for (int i = 0; i < g_qeglobals.d_num_move_points; i++)
1544   {
1545     if (VectorCompare(v, g_qeglobals.d_move_points[i]))
1546       return i;
1547   }
1548   return -1;
1549 }
1550
1551
1552 /*
1553 ==================
1554 RemovePointFromMoveList
1555 ==================
1556 */
1557 void RemovePointFromMoveList(vec3_t v)
1558 {
1559   int n;
1560   while ( (n = PointValueInMoveList(v)) >= 0)
1561   {
1562     for (int i = n; i < g_qeglobals.d_num_move_points-1; i++)
1563     {
1564       g_qeglobals.d_move_points[i] = g_qeglobals.d_move_points[i+1];
1565     }
1566     g_qeglobals.d_num_move_points--;
1567   }
1568 }
1569
1570 /*
1571 ==================
1572 ColumnSelected
1573 ==================
1574 */
1575 bool ColumnSelected(patchMesh_t* p, int nCol)
1576 {
1577   for (int i = 0; i < p->height; i++)
1578   {
1579     if (PointInMoveList(p->ctrl[nCol][i].xyz) == -1)
1580       return false;
1581   }
1582   return true;
1583 }
1584
1585 /*
1586 ==================
1587 AddPoint
1588 ==================
1589 */
1590 void AddPoint(patchMesh_t* p, vec3_t v, bool bWeldOrDrill = true)
1591 {
1592   int nDim1 = (g_pParentWnd->ActiveXY()->GetViewType() == YZ) ? 1 : 0;
1593   int nDim2 = (g_pParentWnd->ActiveXY()->GetViewType() == XY) ? 1 : 2;
1594   g_qeglobals.d_move_points[g_qeglobals.d_num_move_points++] = v;
1595   if ((g_bPatchWeld || g_bPatchDrillDown) && bWeldOrDrill)
1596   {
1597           for ( int i = 0 ; i < p->width ; i++ ) 
1598     {
1599                   for ( int j = 0 ; j < p->height ; j++ ) 
1600       {
1601         if (g_bPatchWeld)
1602         {
1603           if ( VectorCompare(v, p->ctrl[i][j].xyz)
1604             && PointInMoveList(p->ctrl[i][j].xyz) == -1)
1605           {
1606             g_qeglobals.d_move_points[g_qeglobals.d_num_move_points++] = p->ctrl[i][j].xyz;
1607             continue;
1608           }
1609         }
1610         if (g_bPatchDrillDown && g_nPatchClickedView != W_CAMERA)
1611         {
1612           if ( (fabs(v[nDim1] - p->ctrl[i][j].xyz[nDim1]) <= EQUAL_EPSILON) 
1613              &&(fabs(v[nDim2] - p->ctrl[i][j].xyz[nDim2]) <= EQUAL_EPSILON)) 
1614           {
1615             if (PointInMoveList(p->ctrl[i][j].xyz) == -1)
1616             {
1617               g_qeglobals.d_move_points[g_qeglobals.d_num_move_points++] = p->ctrl[i][j].xyz;
1618               continue;
1619             }
1620           }
1621         }
1622       }
1623     }
1624   }
1625 }
1626
1627 /*
1628 ==================
1629 SelectRow
1630 ==================
1631 */
1632 void SelectRow(patchMesh_t* p, int nRow, bool bMulti)
1633 {
1634   if (!bMulti)
1635     g_qeglobals.d_num_move_points = 0;
1636   for (int i = 0; i < p->width; i++)
1637   {
1638     AddPoint(p, p->ctrl[i][nRow].xyz, false);
1639   }
1640   //Sys_Printf("Selected Row %d\n", nRow);
1641 }
1642
1643 /*
1644 ==================
1645 SelectColumn
1646 ==================
1647 */
1648 void SelectColumn(patchMesh_t* p, int nCol, bool bMulti)
1649 {
1650   if (!bMulti)
1651     g_qeglobals.d_num_move_points = 0;
1652   for (int i = 0; i < p->height; i++)
1653   {
1654     AddPoint(p, p->ctrl[nCol][i].xyz, false);
1655   }
1656   //Sys_Printf("Selected Col %d\n", nCol);
1657 }
1658
1659
1660 /*
1661 ==================
1662 AddPatchMovePoint
1663 ==================
1664 */
1665 void AddPatchMovePoint(vec3_t v, bool bMulti, bool bFull)
1666 {
1667   if (!g_bSameView && !bMulti && !bFull)
1668   {
1669     g_bSameView = true;
1670     //return; // was causing odd behaviour on patch vertex selection
1671   }
1672
1673         for (brush_t *pb = selected_brushes.next ; pb != &selected_brushes ; pb = pb->next)
1674         {
1675     if (pb->patchBrush)
1676     {
1677             patchMesh_t* p = pb->pPatch;
1678             for ( int i = 0 ; i < p->width ; i++ ) 
1679       {
1680                     for ( int j = 0 ; j < p->height ; j++ ) 
1681         {
1682           if (VectorCompare(v, p->ctrl[i][j].xyz))
1683           {
1684             if (PointInMoveList(p->ctrl[i][j].xyz) == -1)
1685             {
1686               if (bFull)        // if we want the full row/col this is on
1687               {
1688                 SelectColumn(p, i, bMulti);
1689               }
1690               else
1691               {
1692                 if (!bMulti)
1693                   g_qeglobals.d_num_move_points = 0;
1694                 AddPoint(p, p->ctrl[i][j].xyz);
1695                 //Sys_Printf("Selected col:row %d:%d\n", i, j);
1696               }
1697               //--if (!bMulti)
1698               return;
1699             }
1700             else
1701             {
1702               if (bFull)
1703               {
1704                 if (ColumnSelected(p, i))
1705                 {
1706                   SelectRow(p, j, bMulti);
1707                 }
1708                 else
1709                 {
1710                   SelectColumn(p, i, bMulti);
1711                 }
1712                 return;
1713               }
1714                           //if (!bMulti)
1715                           //{
1716               //    g_qeglobals.d_num_move_points = 0;
1717               //    AddPoint(p, p->ctrl[i][j].xyz);
1718                           //}
1719               if (bMulti)// if (g_bSameView) // this is not having desired effect
1720               {
1721                 RemovePointFromMoveList(v);
1722                 return;
1723               }
1724             }
1725           }
1726                     }
1727             }
1728     }
1729   }
1730 }
1731
1732 /*
1733 ==================
1734 Patch_UpdateSelected
1735 ==================
1736 */
1737 void Patch_UpdateSelected(vec3_t vMove)
1738 {
1739         int i;//, j;
1740         for (i=0 ; i < g_qeglobals.d_num_move_points ; i++)
1741         {
1742                 VectorAdd (g_qeglobals.d_move_points[i], vMove, g_qeglobals.d_move_points[i]);
1743                 if (g_qeglobals.d_num_move_points == 1)
1744                 {
1745                 }
1746         }
1747         
1748         //--patchMesh_t* p = &patchMeshes[g_nSelectedPatch];
1749         for (brush_t *pb = selected_brushes.next ; pb != &selected_brushes ; pb = pb->next)
1750         {
1751                 if (pb->patchBrush)
1752                 {
1753                         patchMesh_t* p = pb->pPatch;
1754                         
1755 #if 0 //moving to SelectCurvePointByRay
1756                         g_qeglobals.d_numpoints = 0;
1757                         for (i = 0 ; i < p->width ; i++ ) 
1758                         {
1759                                 for ( j = 0 ; j < p->height ; j++ ) 
1760                                 {
1761                                         VectorCopy (p->ctrl[i][j].xyz, g_qeglobals.d_points[g_qeglobals.d_numpoints]);
1762                                         if (g_qeglobals.d_numpoints < MAX_POINTS-1)
1763                                         {
1764                                                 g_qeglobals.d_numpoints++;
1765                                         }
1766                                 }
1767                         }
1768 #endif                  
1769                         vec3_t vMin, vMax;
1770                         Patch_CalcBounds(p, vMin, vMax);
1771                         Brush_RebuildBrush(p->pSymbiot, vMin, vMax);
1772                 }
1773         }
1774   //Brush_Free(p->pSymbiot);
1775   //Select_Brush(AddBrushForPatch(g_nSelectedPatch));
1776 }
1777
1778
1779
1780 /*
1781 ===============
1782 SampleSinglePatch
1783 ===============
1784 */
1785 void SampleSinglePatch (float ctrl[3][3][5], float u, float v, float out[5]) {
1786         float   vCtrl[3][5];
1787         int             vPoint;
1788         int             axis;
1789
1790         // find the control points for the v coordinate
1791         for (vPoint = 0 ; vPoint < 3 ; vPoint++) 
1792         {
1793                 for (axis = 0 ; axis < 5 ; axis++) 
1794                 {
1795                         float   a, b, c;
1796                         float   qA, qB, qC;
1797
1798                         a = ctrl[0][vPoint][axis];
1799                         b = ctrl[1][vPoint][axis];
1800                         c = ctrl[2][vPoint][axis];
1801                         qA = a - 2 * b + c;
1802                         qB = 2 * b - 2 * a;
1803                         qC = a;
1804
1805                         vCtrl[vPoint][axis] = qA * u * u + qB * u + qC;
1806                 }
1807         }
1808
1809         // interpolate the v value
1810         for (axis = 0 ; axis < 5 ; axis++) 
1811         {
1812                 float   a, b, c;
1813                 float   qA, qB, qC;
1814
1815                 a = vCtrl[0][axis];
1816                 b = vCtrl[1][axis];
1817                 c = vCtrl[2][axis];
1818                 qA = a - 2 * b + c;
1819                 qB = 2 * b - 2 * a;
1820                 qC = a;
1821
1822                 out[axis] = qA * v * v + qB * v + qC;
1823         }
1824 }
1825
1826 //spog - Curve LOD stuff starts
1827
1828 float ShadeForNormal(vec3_t normal)
1829 {
1830   float f;
1831
1832         vec3_t L;
1833         L[0] = 1.0f;
1834         L[1] = 1.0f;
1835         L[2] = 1.0f;
1836
1837   
1838         // quick diffuse shading
1839   f = DotProduct(L, normal);
1840
1841   // range 0.5 to 1.0
1842         f = (f+1)/4.0f;
1843   //if (f < 0.0f) f = 0.0f;
1844
1845         f += 0.5f;
1846         
1847   return f;
1848 }
1849
1850 void ShadeVertex (drawVert_t &p)
1851 {
1852         p.lightmap[0] = ShadeForNormal(p.normal);
1853 }
1854
1855
1856 void Patch_DrawNormals(patchMesh_t *patch)
1857 {
1858         int row, col;
1859         vec3_t vNormal;
1860
1861         qglBegin (GL_LINES);
1862         for (col=0; col<patch->width; col++)
1863         {
1864                 for (row=0; row<patch->height; row++)
1865                 {
1866                         VectorAdd(patch->ctrl[col][row].xyz, patch->ctrl[col][row].normal, vNormal);
1867                         qglVertex3fv (patch->ctrl[col][row].xyz);
1868                         qglVertex3fv (vNormal);
1869                 }
1870         }
1871         qglEnd ();
1872 }
1873
1874
1875 // take an array of three drawVerts, and the addresses of three more drawVerts
1876 // interpolate new XYZST values from the three drawVerts, these are:
1877 // the left sub-control-point, the right sub-control-point and the midpoint of the curve respectively
1878 // store these values in the drawVerts passed to the function
1879 void Patch_CurveSplit(drawVert_t *vCurve[3], drawVert_t &pLeft, drawVert_t &pRight, drawVert_t &pMid, float u)
1880 {
1881         int i;
1882         //float u = 0.5f;
1883 //      float a, b;
1884         drawVert_t v1, v2, v3;
1885 //      vec3_t v4;
1886         
1887         for (i=0; i<3; i++)
1888         {
1889                  // xyz
1890                 v1.xyz[i] = vCurve[1]->xyz[i] - vCurve[0]->xyz[i];
1891                 v2.xyz[i] = vCurve[2]->xyz[i] - vCurve[1]->xyz[i];
1892                 v1.xyz[i] *= u;
1893                 v2.xyz[i] *= u;
1894                 pLeft.xyz[i] = vCurve[0]->xyz[i] + v1.xyz[i];
1895                 pRight.xyz[i] = vCurve[1]->xyz[i] + v2.xyz[i];
1896
1897                 v3.xyz[i] = pRight.xyz[i] - pLeft.xyz[i];
1898                 v3.xyz[i] *= u;
1899                 pMid.xyz[i] = pLeft.xyz[i] + v3.xyz[i];
1900
1901                 // normal (weighted average) // no, that's b0rked
1902                 //a = 1 / u; // total
1903                 //b = u * a; // component 2
1904                 //a = u - b; // component 1
1905                 //pMid.normal[i] = u * ((vCurve[0]->normal[i] * b) + (vCurve[2]->normal[i] * a));
1906
1907                 if (i==2) continue;
1908
1909                 // st
1910                 v1.st[i] = vCurve[1]->st[i] - vCurve[0]->st[i];
1911                 v2.st[i] = vCurve[2]->st[i] - vCurve[1]->st[i];
1912                 v1.st[i] *= u;
1913                 v2.st[i] *= u;
1914                 pLeft.st[i] = vCurve[0]->st[i] + v1.st[i];
1915                 pRight.st[i] = vCurve[1]->st[i] + v2.st[i];
1916
1917                 v3.st[i] = pRight.st[i] - pLeft.st[i];
1918                 v3.st[i] *= u;
1919                 pMid.st[i] = pLeft.st[i] + v3.st[i];
1920         }
1921 }
1922
1923 // take an array of three points, return an index representing the curvature of those three points
1924 // return zero if the curve is a straight line, unless the midpoint is not between the endpoints
1925 float Patch_CurveIndex(vec3_t vCurve[])
1926 {
1927         vec3_t vTemp, v1, v2, v3, vClear;
1928 //      int i;
1929         float width, angle;
1930         float index, dot;
1931
1932         VectorClear(vClear);
1933                 
1934         VectorSubtract(vCurve[2], vCurve[0], vTemp);
1935         VectorSubtract(vCurve[1], vCurve[0], v1);
1936         VectorSubtract(vCurve[2], vCurve[1], v2);
1937
1938         if (VectorCompare(v1, vClear) || VectorCompare(vTemp, v1)) // return 0 if 1->2 == 0 or 1->2 == 1->3
1939                 return 0.0f;
1940
1941         VectorNormalize(v1, v1);
1942         VectorNormalize(v2, v2);
1943         if (VectorCompare(v1, v2))
1944                 return 0.0f;
1945         
1946         VectorCopy(vTemp, v3);
1947         width = VectorNormalize(v3, v3);
1948
1949         if (VectorCompare(v1, v3) && VectorCompare(v2, v3))
1950                 return 0.0f;
1951         
1952         dot = DotProduct(v1, v2);
1953
1954         angle = acos(dot) / Q_PI;
1955
1956         index = width * angle;
1957
1958         return index;
1959 }
1960
1961
1962 // create a new tree root, give it the coordinate values of the drawVert
1963 // return a pointer to the new tree root
1964 BTNode_t *BTree_Create(drawVert_t info)
1965 {
1966         BTNode_t *BTree = new BTNode_t;
1967         BTree->left = BTree->right = NULL;
1968         VectorCopy(info.xyz, BTree->info.xyz);
1969         VectorCopy(info.xyz, BTree->vMid.xyz);
1970         for (int i=0; i<2; i++)
1971         {
1972                 BTree->info.st[i] = info.st[i];
1973                 BTree->vMid.st[i] = info.st[i];
1974         }
1975         return BTree;
1976 }
1977
1978 // take ownership of the subtree
1979 // delete the entire subtree
1980 // return a NULL pointer
1981 BTNode_t *BTree_Delete(BTNode_t *pBT)
1982 {
1983         if (pBT != NULL)
1984         {
1985                 BTree_Delete(pBT->left);
1986                 BTree_Delete(pBT->right);
1987                 delete pBT;
1988         }
1989         return NULL;
1990 }
1991
1992 // NOT currently used
1993 BTNode_t *BTree_Clear(BTNode_t *pBT, bool bFirst = true)
1994 {
1995         if (pBT != NULL)
1996         {
1997                 BTree_Clear(pBT->left, false);
1998                 BTree_Clear(pBT->right, false);
1999                 if (!bFirst) delete pBT;
2000         }
2001         return pBT;
2002 }
2003
2004 // take a pointer to the last item added to the list (this can also be a NULL pointer)
2005 // take a pointer to the root of a subtree, and the patch points to the left and right of it
2006 // add a new item to the subtree list, and add the subtree and its adjacent points to the new item
2007 // return a pointer to the last item added to the subtree list
2008 BTreeList_t *BTree_AddToList(BTreeList_t *pBTList, BTNode_t *pBT, drawVert_t &pLeft, drawVert_t &pRight)
2009 {
2010         BTreeList_t *newBTList = new BTreeList_t;
2011         newBTList->next = pBTList;
2012         newBTList->pBT = pBT;
2013         VectorCopy(pLeft.xyz, newBTList->vLeft.xyz);
2014         VectorCopy(pRight.xyz, newBTList->vRight.xyz);
2015         VectorCopy(pLeft.normal, newBTList->vLeft.normal);
2016         VectorCopy(pRight.normal, newBTList->vRight.normal);
2017         for (int i=0; i<2; i++)
2018         {
2019                 newBTList->vLeft.st[i] = pLeft.st[i];
2020                 newBTList->vRight.st[i] = pRight.st[i];
2021         }
2022         return newBTList;
2023 }
2024
2025 // NOT currently used, subtrees are now stored on the patch
2026 // take ownership of the subtree list
2027 // delete the entire list and the subtrees it points to
2028 // return a NULL pointer
2029 BTreeList_t *BTree_DeleteList(BTreeList_t *pBTList)
2030 {
2031         if (pBTList != NULL)
2032         {
2033                 BTree_DeleteList(pBTList->next);
2034                 pBTList->pBT = BTree_Delete(pBTList->pBT);
2035                 delete pBTList;
2036         }
2037         return NULL;
2038 }
2039
2040 // take ownership of the subtree list
2041 // delete the entire subtree list, but not the subtrees themselves
2042 // return a NULL pointer
2043 BTreeList_t *BTree_DeletePointerList(BTreeList_t *pBTList)
2044 {
2045         if (pBTList != NULL)
2046         {
2047                 BTree_DeletePointerList(pBTList->next);
2048                 delete pBTList;
2049         }
2050         return NULL;
2051 }
2052
2053 // take a pointer to the last item added to the list of subtree lists
2054 // add a subtree list to the list
2055 // return a pointer to the last item added
2056 BTListList_t *BTree_AddListToList(BTListList_t *pBTListList, BTreeList_t *pBTList)
2057 {
2058         BTListList_t *newBTListList = new BTListList_t;
2059         newBTListList->next = pBTListList;
2060         newBTListList->list = pBTList;
2061         return newBTListList;
2062 }
2063
2064
2065 // take ownership of the list of subtree lists
2066 // delete the entire list of lists, but not the subtrees themselves
2067 // return a NULL pointer
2068 BTListList_t *BTree_DeleteListFromList(BTListList_t *pBTListList)
2069 {
2070         if (pBTListList != NULL)
2071         {
2072                 BTree_DeleteListFromList(pBTListList->next);
2073                 pBTListList->list = BTree_DeletePointerList(pBTListList->list);
2074                 delete pBTListList;
2075         }
2076         return NULL;
2077 }
2078
2079 // take a pointer to the last item in the list
2080 // add a NULL linker subtree to the list, setting the "flipped" flag using the left curvepoint normal .. er.. hacky?
2081 BTreeList_t *BTree_AddLinkToList(BTreeList_t *pBTList, bool bFlipped = false)
2082 {
2083         BTreeList_t *linkBTList = new BTreeList_t;
2084         linkBTList->pBT = NULL;
2085         linkBTList->next = pBTList;
2086         linkBTList->vLeft.normal[0] = (bFlipped) ? 1.0f : 0.0f;
2087         return linkBTList;
2088 }
2089
2090
2091 // take an array of three points and the address of a vector
2092 // store midpoint of the bezier curve formed by the three points, in the vector
2093 void Patch_BezierInterpolate(vec3_t vCurve[], vec3_t &pMid)
2094 {
2095         vec3_t vTemp;
2096         int i;
2097         VectorSubtract(vCurve[2], vCurve[0], vTemp); // Start->End
2098         for (i=0; i<3; i++)
2099                 vTemp[i] /= 2;
2100         VectorAdd(vCurve[0], vTemp, vTemp); // midpoint of Start->End
2101
2102         VectorSubtract(vTemp, vCurve[1], vTemp); // Mid->(midpoint of Start->End)
2103         for (i=0; i<3; i++)
2104                 vTemp[i] /= 2;
2105         VectorAdd(vCurve[1], vTemp, pMid); // midpoint of Mid->(midpoint of Start->End)
2106 }
2107
2108
2109 // take a pointer to the list of subtrees, and a threshold value
2110 // generate REAL surface curvature for the subtree curves, using bezier interpolation
2111 // if any of the real curves has an index greater than the threshold, return true 
2112 bool Patch_MostCurvedRow(BTreeList_t *pBTList, int threshold)
2113 {
2114         BTreeList_t *p;
2115         float index;//, bestindex = 0;
2116         vec3_t vCurve[3];
2117         vec3_t vRow[3];
2118 //      int i;
2119
2120         for (p = pBTList; p != NULL; p = p->next->next)
2121         {
2122                 // this row
2123                 VectorCopy(p->vLeft.xyz, vCurve[0]);
2124                 VectorCopy(p->pBT->info.xyz, vCurve[1]);
2125                 VectorCopy(p->vRight.xyz, vCurve[2]);
2126                 
2127                 index = Patch_CurveIndex(vCurve);
2128                 if (index > threshold)
2129                         return true;
2130
2131                 if (p->next == NULL)
2132                         break;
2133
2134                 if (p->next->pBT == NULL) continue;
2135
2136                 VectorCopy(p->vLeft.xyz, vCurve[0]);
2137                 VectorCopy(p->next->vLeft.xyz, vCurve[1]);
2138                 VectorCopy(p->next->next->vLeft.xyz, vCurve[2]);
2139                 Patch_BezierInterpolate(vCurve, vRow[0]);
2140
2141                 VectorCopy(p->pBT->info.xyz, vCurve[0]);
2142                 VectorCopy(p->next->pBT->info.xyz, vCurve[1]);
2143                 VectorCopy(p->next->next->pBT->info.xyz, vCurve[2]);
2144                 Patch_BezierInterpolate(vCurve, vRow[1]);
2145
2146                 VectorCopy(p->vRight.xyz, vCurve[0]);
2147                 VectorCopy(p->next->vRight.xyz, vCurve[1]);
2148                 VectorCopy(p->next->next->vRight.xyz, vCurve[2]);
2149                 Patch_BezierInterpolate(vCurve, vRow[2]);
2150
2151                 index = Patch_CurveIndex(vRow);
2152                 if (index > threshold)
2153                         return true;
2154         }
2155         return false;
2156 }
2157
2158
2159 // take a pointer to a list of subtrees.. each subtree in the list is a 3-point bezier curve formed by two endpoints owned by the list, and a midpoint subtree node owned by a patch.
2160 // if any of the subtrees are curved above a threshold, create a left and right subsubtree for each subtree in the list.
2161 // if a NULL linker subtree is found, check for an orientation flip - ie. an inverted LOD-match - and create a NULL subsubtree with the same orientation flip
2162 // this effectively generates trees for multiple patches at the same time.. the subtrees are always owned by their respective patches though
2163 void BTree_ListCurveRecurse(BTreeList_t *pBTList)
2164 {
2165         BTreeList_t *p;
2166         BTreeList_t *leftBTList, *rightBTList;
2167         //drawVert_t pLeft, pRight, pMid;
2168         drawVert_t *vCurve[3];
2169         int threshold;
2170         //int i;
2171         bool bFlipped = false;
2172
2173   if (g_PrefsDlg.m_nSubdivisions >= 1)
2174     threshold = g_PrefsDlg.m_nSubdivisions;
2175         
2176         leftBTList = rightBTList = NULL;
2177         
2178         if (Patch_MostCurvedRow(pBTList, threshold)) // split all subtrees in list if any subtree is above threshold
2179         {
2180                 //Sys_Printf("| ");
2181                 // traverse nodes in list
2182                 for (p = pBTList; p != NULL; p=p->next)
2183                 {
2184                         if (p->pBT == NULL) 
2185                         {
2186                                 leftBTList = BTree_AddLinkToList(leftBTList, (p->vLeft.normal[0] == 1.0f));
2187                                 rightBTList = BTree_AddLinkToList(rightBTList, (p->vLeft.normal[0] == 1.0f));
2188                                 if (p->vLeft.normal[0] == 1.0f) bFlipped = (!bFlipped) ? true : false; // switch bFlipped if true
2189                                 continue;
2190                         }
2191
2192                         // create left node for this subtree
2193                         BTNode_t *newLeft = new BTNode_t;
2194                         p->pBT->left = newLeft;
2195                         newLeft->left = newLeft->right = NULL;
2196                         
2197                         // create right node for this subtree
2198                         BTNode_t *newRight = new BTNode_t;
2199                         p->pBT->right = newRight;
2200                         newRight->left = newRight->right = NULL;
2201
2202                         // split this node
2203                         vCurve[0] = &p->vLeft;
2204                         vCurve[1] = &p->pBT->info;
2205                         vCurve[2] = &p->vRight;
2206                         Patch_CurveSplit(vCurve, newLeft->info, newRight->info, p->pBT->vMid, 0.5);
2207
2208                         memcpy(&newLeft->vMid, &newLeft->info, sizeof(drawVert_t));
2209                         memcpy(&newRight->vMid, &newRight->info, sizeof(drawVert_t));
2210                         
2211                         
2212                         if (!bFlipped)
2213                         {
2214                                 // add new left subtree to left subtree list
2215                                 leftBTList = BTree_AddToList(leftBTList, newLeft, p->vLeft, p->pBT->vMid);
2216                                 
2217                                 // add new right subtree to right subtree list
2218                                 rightBTList = BTree_AddToList(rightBTList, newRight, p->pBT->vMid, p->vRight);
2219                         }
2220                         else
2221                         {
2222                                 // add new left subtree to right subtree list
2223                                 rightBTList = BTree_AddToList(rightBTList, newLeft, p->vLeft, p->pBT->vMid);
2224                                 
2225                                 // add new right subtree to left subtree list
2226                                 leftBTList = BTree_AddToList(leftBTList, newRight, p->pBT->vMid, p->vRight);
2227                         }
2228                 }
2229
2230                 // continue tree left
2231                 BTree_ListCurveRecurse(leftBTList);
2232                 leftBTList = BTree_DeletePointerList(leftBTList);
2233
2234                 // continue tree right
2235                 BTree_ListCurveRecurse(rightBTList);
2236                 rightBTList = BTree_DeletePointerList(rightBTList);
2237         }
2238 }
2239
2240 // take mins and maxs values from two brushes
2241 // return true if they intersect on every axis
2242 bool TouchingAABBs(vec3_t mins1, vec3_t maxs1, vec3_t mins2, vec3_t maxs2)
2243 {
2244         //bool xyz[3];
2245         vec3_t v1, v2, p1, p2, T;
2246         for (int i=0; i<3; i++)
2247         {
2248                 v1[i] = maxs1[i] - mins1[i];
2249                 v2[i] = maxs2[i] - mins2[i];
2250                 v1[i] /=2;
2251                 v2[i] /=2;
2252                 p1[i] = mins1[i] + v1[i];
2253                 p2[i] = mins2[i] + v2[i];
2254                 // p1 == origin of aabb1
2255                 // p2 == origin of aabb1
2256                 // v1 == displacement of aabb1
2257                 // v1 == displacement of aabb2
2258                 T[i] = p2[i] - p1[i]; // T == vector from aabb1 to aabb2
2259                 if ( fabs(T[i]) > (fabs(v1[i]) + fabs(v2[i])) )
2260                         return false;
2261         }
2262         return true;
2263 }
2264
2265 // take a pointer to the last item added to pBTList, a pointer to the patch, a row index (start) and a column index
2266 // generate a row of row-curve tree roots, owned by the patch and add the entire column of row-curves to the list, using the row index to decide the order to add
2267 // return a pointer to the last item added to the list
2268 BTreeList_t *Patch_CreateBTListForRows(BTreeList_t *pBTList, patchMesh_t *patch, int start, int col)
2269 {
2270         int row, pos;
2271         patch->colDirty[(col-1)/2] = true;
2272                                                 
2273         if (start == 0)
2274         {
2275                 for (row=0; row<patch->height; row++)
2276                 {
2277                         pos = (((col-1)/2)*patch->height)+row;
2278                         patch->rowLOD[pos] = BTree_Delete(patch->rowLOD[pos]);
2279                         patch->rowLOD[pos] = BTree_Create(patch->ctrl[col][row]);
2280                         pBTList = BTree_AddToList(pBTList, patch->rowLOD[pos], patch->ctrl[col-1][row], patch->ctrl[col+1][row]);
2281                 }
2282         }
2283         else
2284         {
2285                 for (row=patch->height-1; row>=0; row--)
2286                 {
2287                         pos = (((col-1)/2)*patch->height)+row;
2288                         patch->rowLOD[pos] = BTree_Delete(patch->rowLOD[pos]);
2289                         patch->rowLOD[pos] = BTree_Create(patch->ctrl[col][row]);
2290                         pBTList = BTree_AddToList(pBTList, patch->rowLOD[pos], patch->ctrl[col-1][row], patch->ctrl[col+1][row]);
2291                 }
2292         }
2293         return pBTList;
2294 }
2295
2296 // take a pointer to the last item added to pBTList, a pointer to the patch, a row index and a column index (start)
2297 // generate a row of column-curve tree roots, owned by the patch and add the entire row of column-curves to the list, using the column index to decide the order to add
2298 // return a pointer to the last item added to the list
2299 BTreeList_t *Patch_CreateBTListForCols(BTreeList_t *pBTList, patchMesh_t *patch, int row, int start)
2300 {
2301         int col, pos;
2302         patch->rowDirty[(row-1)/2] = true;
2303
2304         if (start == 0)
2305         {
2306                 for (col=0; col<patch->width; col++)
2307                 {
2308                         pos = (((row-1)/2)*patch->width)+col;
2309                         patch->colLOD[pos] = BTree_Delete(patch->colLOD[pos]);
2310                         patch->colLOD[pos] = BTree_Create(patch->ctrl[col][row]);
2311                         pBTList = BTree_AddToList(pBTList, patch->colLOD[pos], patch->ctrl[col][row-1], patch->ctrl[col][row+1]);
2312                 }
2313         }
2314         else
2315         {
2316                 for (col=patch->width-1; col>=0; col--)
2317                 {
2318                         pos = (((row-1)/2)*patch->width)+col;
2319                         patch->colLOD[pos] = BTree_Delete(patch->colLOD[pos]);
2320                         patch->colLOD[pos] = BTree_Create(patch->ctrl[col][row]);
2321                         pBTList = BTree_AddToList(pBTList, patch->colLOD[pos], patch->ctrl[col][row-1], patch->ctrl[col][row+1]);
2322                 }
2323
2324         }
2325         return pBTList;
2326 }
2327
2328 bool BTree_IsInList(BTreeList_t *pBTList, BTNode_t *pBT)
2329 {
2330         BTreeList_t *p;
2331         if (pBTList == NULL) return false;
2332
2333         for (p=pBTList; p != NULL; p=p->next)
2334         {
2335                 if (p->pBT != NULL)
2336                 {
2337                         if (p->pBT == pBT)
2338         return true;
2339                 }
2340         }
2341         return false;
2342 }
2343
2344 int Patch_DegenCurve(vec3_t &start, vec3_t &mid, vec3_t &end)
2345 {
2346   if (VectorCompare(start, mid) || VectorCompare(end, mid))
2347   {
2348     if (VectorCompare(start, end)) return 2;
2349     else return 1;
2350   }
2351   else return 0;
2352 }
2353
2354 // take a pointer to the last item added to the list, and a pointer to a patch (this patch is the owner of the three drawverts)
2355 // take the addresses of three drawVerts, and compare them with the edges of all patches that touch the patch
2356 // if they match an edge, add the tree roots for that section of the matched patch to the list, and recurse for the opposite edge of that patch section. Also, set the matched patch Dirty, so that its drawlists will be rebuilt
2357 // return a pointer to the last item added
2358 BTreeList_t *Patch_FindLODMatches(patchMesh_t *patch, BTreeList_t *pBTList, drawVert_t &pMid, drawVert_t &pLeft, drawVert_t &pRight)
2359 {
2360         brush_t *pb, *brushlist;
2361         int row, col, i;//, pos;
2362         vec3_t vTemp, v1, v2;//, vClear;
2363   bool bAlreadyAdded;
2364
2365         //Sys_Printf("Patch_FindLODMatches: called\n");
2366
2367         if (VectorCompare(pMid.xyz, pLeft.xyz) && VectorCompare(pMid.xyz, pRight.xyz))
2368                 return pBTList;
2369
2370         //VectorClear(vClear);
2371         VectorSubtract(pRight.xyz, pLeft.xyz, vTemp);
2372         VectorSubtract(pMid.xyz, pLeft.xyz, v1);
2373         VectorSubtract(pRight.xyz, pMid.xyz, v2);
2374
2375         //if (VectorCompare(v1, vClear) || VectorCompare(vTemp, v1)) // return null if 1->2 == 0 or 1->2 == 1->3
2376         //      return pBTList;
2377
2378         VectorNormalize(v1, v1);
2379         VectorNormalize(v2, v2);
2380         if (VectorCompare(v1, v2))
2381                 return pBTList;
2382
2383         VectorNormalize(vTemp, vTemp);
2384         if (VectorCompare(v1, vTemp) && VectorCompare(v2, vTemp))
2385                 return pBTList;
2386
2387         brushlist = &active_brushes;
2388         for (i=0; i<2; i++)
2389         {
2390                 for (pb = brushlist->next; pb != brushlist; pb=pb->next)
2391                 {
2392                         if (!pb->patchBrush || pb->pPatch == patch)
2393                                 continue;
2394
2395                         // ignore this patch if its AABB does not touch the subject patch
2396                         if (!TouchingAABBs(patch->pSymbiot->maxs, patch->pSymbiot->mins, pb->maxs, pb->mins))
2397                                 continue;
2398
2399       // all columns of curves
2400                         for (col=1; col<pb->pPatch->width; col+=2)
2401                         {
2402                                 if (pb->pPatch->colDirty[(col-1)/2]) continue;
2403
2404                                 bAlreadyAdded = false;
2405
2406                           // top and bottom curves of this column
2407                                 for (row=0; row<pb->pPatch->height; row+=pb->pPatch->height-1)
2408                                 {
2409           if (bAlreadyAdded)
2410             continue;
2411           //if (!BTree_IsInList(pBTList, pb->pPatch->rowLOD[(((col-1)/2)*patch->height)+row]))
2412           //  continue;
2413                                         // ignore this curve if it shares no mid ctrl point with the test curve
2414                                         if (!VectorCompare (pb->pPatch->ctrl[col][row].xyz, pMid.xyz))
2415                                                 continue;
2416                                         // ignore this curve if it is degenerate
2417                                         if (VectorCompare (pb->pPatch->ctrl[col][row].xyz, pb->pPatch->ctrl[col-1][row].xyz) || VectorCompare (pb->pPatch->ctrl[col][row].xyz, pb->pPatch->ctrl[col+1][row].xyz))
2418                                                 continue;
2419                                         // if curve matches the test curve directly
2420                                         if (VectorCompare (pb->pPatch->ctrl[col-1][row].xyz, pLeft.xyz) && VectorCompare (pb->pPatch->ctrl[col+1][row].xyz, pRight.xyz))
2421                                         {
2422                                                 // add a blank link as separator
2423                                                 pBTList = BTree_AddLinkToList(pBTList);
2424                                                 // add this entire column, if top, top-to-bottom, else bottom to top
2425                                                 pBTList = Patch_CreateBTListForRows(pBTList, pb->pPatch, row, col);
2426                                                 // continue checking from last curve added to list
2427                                           pBTList = Patch_FindLODMatches(pb->pPatch, pBTList, pBTList->pBT->info, pBTList->vLeft, pBTList->vRight);
2428                                                 // set flag
2429                                                 pb->pPatch->LODUpdated = true;
2430             bAlreadyAdded = true;
2431                                         }
2432                                         // if curve matches test curve but flipped
2433                                         else if (VectorCompare (pb->pPatch->ctrl[col-1][row].xyz, pRight.xyz) && VectorCompare (pb->pPatch->ctrl[col+1][row].xyz, pLeft.xyz))
2434                                         {
2435                                                 pBTList = BTree_AddLinkToList(pBTList, true); // flip
2436                                                 pBTList = Patch_CreateBTListForRows(pBTList, pb->pPatch, row, col);
2437                                                 pBTList = Patch_FindLODMatches(pb->pPatch, pBTList, pBTList->pBT->info, pBTList->vLeft, pBTList->vRight);                               
2438                                                 pb->pPatch->LODUpdated = true;
2439             bAlreadyAdded = true;
2440                                         }
2441                                 }
2442                         }
2443
2444                         // all rows of curves
2445                         for (row=1; row<pb->pPatch->height; row+=2)
2446                         {
2447                                 if (pb->pPatch->rowDirty[(row-1)/2]) continue;
2448
2449                                 bAlreadyAdded = false;
2450
2451                           for (col=0; col<pb->pPatch->width; col+=pb->pPatch->width-1)
2452                                 {
2453           if (bAlreadyAdded)
2454             continue;
2455           //if (BTree_IsInList(pBTList, pb->pPatch->colLOD[(((row-1)/2)*patch->width)+col]))
2456           //  continue;
2457                                         if (!VectorCompare (pb->pPatch->ctrl[col][row].xyz, pMid.xyz))
2458                                                 continue;
2459                                         if (VectorCompare (pb->pPatch->ctrl[col][row].xyz, pb->pPatch->ctrl[col][row-1].xyz) || VectorCompare (pb->pPatch->ctrl[col][row].xyz, pb->pPatch->ctrl[col][row+1].xyz))
2460                                                 continue;
2461                                         if (VectorCompare (pb->pPatch->ctrl[col][row-1].xyz, pLeft.xyz) && VectorCompare (pb->pPatch->ctrl[col][row+1].xyz, pRight.xyz))
2462                                         {
2463                                                 pBTList = BTree_AddLinkToList(pBTList);
2464                                                 pBTList = Patch_CreateBTListForCols(pBTList, pb->pPatch, row, col);
2465                                                 pBTList = Patch_FindLODMatches(pb->pPatch, pBTList, pBTList->pBT->info, pBTList->vLeft, pBTList->vRight);
2466                                                 pb->pPatch->LODUpdated = true;
2467             bAlreadyAdded = true;
2468                                         }
2469                                         else if (VectorCompare (pb->pPatch->ctrl[col][row-1].xyz, pRight.xyz) && VectorCompare (pb->pPatch->ctrl[col][row+1].xyz, pLeft.xyz))
2470                                         {
2471                                                 pBTList = BTree_AddLinkToList(pBTList, true); // flip
2472                                                 pBTList = Patch_CreateBTListForCols(pBTList, pb->pPatch, row, col);
2473                                                 pBTList = Patch_FindLODMatches(pb->pPatch, pBTList, pBTList->pBT->info, pBTList->vLeft, pBTList->vRight);
2474             pb->pPatch->LODUpdated = true;
2475             bAlreadyAdded = true;
2476                                         }
2477                                 }
2478                         }
2479                 }
2480                 brushlist = &selected_brushes;
2481         }
2482         return pBTList;
2483 }
2484
2485 // take a pointer to a patch
2486 // create tree roots for all the rows and columns of curves in the patch, the patch takes ownership of these new tree roots
2487 // generate lists of pointers to all the trees in all the patches in the map which need to match the LOD of trees owned by this patch
2488 // store all the lists in a list of lists
2489 // recursively generate the rest of every tree in each list in the list
2490 void Patch_CreateLODTrees(patchMesh_t *patch)
2491 {
2492         BTreeList_t *pBTList;
2493         int col, row, pos;//, rowcount, colcount;
2494         BTListList_t *pLists;
2495
2496         //Sys_Printf("Patch_CreateMatchedLODTrees: called\n");
2497
2498         BTListList_t *LODLists;
2499         LODLists = NULL;
2500         
2501         pBTList = NULL;
2502
2503         patch->bDirty = false;
2504         patch->LODUpdated = true;
2505         
2506         for(col=1; col<patch->width; col+=2)
2507         {
2508                 if (patch->colDirty[(col-1)/2]) continue;
2509                 else patch->colDirty[(col-1)/2] = true;
2510
2511                 // create list for rows of current patch
2512                 for(row=0; row<patch->height; row++)
2513                 {
2514                         pos = (((col-1)/2)*patch->height)+row;
2515                         patch->rowLOD[pos] = BTree_Delete(patch->rowLOD[pos]);
2516                         patch->rowLOD[pos] = BTree_Create(patch->ctrl[col][row]);
2517                         pBTList = BTree_AddToList(pBTList, patch->rowLOD[pos], patch->ctrl[col-1][row], patch->ctrl[col+1][row]);
2518                 }
2519         
2520                 //create connection list for first row
2521                 pBTList = Patch_FindLODMatches(patch, pBTList, patch->ctrl[col][0], patch->ctrl[col-1][0], patch->ctrl[col+1][0]);
2522                 //create connection list for last row
2523                 pBTList = Patch_FindLODMatches(patch, pBTList, patch->ctrl[col][row-1], patch->ctrl[col-1][row-1], patch->ctrl[col+1][row-1]);
2524
2525                 LODLists = BTree_AddListToList(LODLists, pBTList);
2526                 pBTList = NULL;
2527         }
2528
2529         pBTList = NULL;
2530         for(row=1; row<patch->height; row+=2)
2531         {
2532                 if (patch->rowDirty[(row-1)/2]) continue;
2533                 else patch->rowDirty[(row-1)/2] = true;
2534
2535                 // create list for cols of current patch
2536                 for(col=0; col<patch->width; col++)
2537                 {
2538                         pos = (((row-1)/2)*patch->width)+col;
2539                         patch->colLOD[pos] = BTree_Delete(patch->colLOD[pos]);
2540                         patch->colLOD[pos] = BTree_Create(patch->ctrl[col][row]);
2541                         pBTList = BTree_AddToList(pBTList, patch->colLOD[pos], patch->ctrl[col][row-1], patch->ctrl[col][row+1]);
2542                 }
2543
2544                 //create connection list for first col
2545                 pBTList = Patch_FindLODMatches(patch, pBTList, patch->ctrl[0][row], patch->ctrl[0][row-1], patch->ctrl[0][row+1]);
2546                 //create connection list for last col
2547                 pBTList = Patch_FindLODMatches(patch, pBTList, patch->ctrl[col-1][row], patch->ctrl[col-1][row-1], patch->ctrl[col-1][row+1]);
2548
2549                 LODLists = BTree_AddListToList(LODLists, pBTList);
2550                 pBTList = NULL;
2551         }
2552
2553         for (pLists = LODLists; pLists != NULL; pLists=pLists->next)
2554                 BTree_ListCurveRecurse(pLists->list);
2555         LODLists = BTree_DeleteListFromList(LODLists);
2556 }
2557
2558 int Patch_GetCVTangent(vec3_t &v1, vec3_t &p1, vec3_t &p2, vec3_t &p3)
2559 {
2560         if (VectorCompare(p1, p2))
2561         {
2562                 if (VectorCompare(p1, p3))
2563                 {
2564                         return 2;
2565                 }
2566                 else VectorSubtract(p3, p1, v1);
2567     return 1;
2568         }
2569         else VectorSubtract(p2, p1, v1);
2570   return 0;
2571 }
2572
2573 void Patch_CVNormal(vec3_t ctrl[3][3], vec3_t &normal)
2574 {
2575         vec3_t v1, v2, vTemp1, vTemp2;
2576   int a, b;
2577         
2578   a = Patch_GetCVTangent(v1, ctrl[0][0], ctrl[1][0], ctrl[2][0]);
2579         b = Patch_GetCVTangent(v2, ctrl[0][0], ctrl[0][1], ctrl[0][2]);
2580
2581         //Sys_Printf("p1: (%1.1f %1.1f %1.1f) p2: (%1.1f %1.1f %1.1f) p2: (%1.1f %1.1f %1.1f)\n",
2582         //      ctrl[0][0][0], ctrl[0][0][1], ctrl[0][0][2], ctrl[0][2][0], ctrl[0][2][1], ctrl[0][2][2], ctrl[2][0][0], ctrl[2][0][1], ctrl[2][0][2]);
2583         
2584   if (a == 2)
2585   {
2586     a = Patch_GetCVTangent(v1, ctrl[0][0], ctrl[1][1], ctrl[1][2]);
2587   }
2588   if (b == 2)
2589   {
2590     b = Patch_GetCVTangent(v2, ctrl[0][0], ctrl[1][1], ctrl[2][1]);
2591   }
2592  
2593   if (a == 2)
2594   {
2595     a = Patch_GetCVTangent(v1, ctrl[0][0], ctrl[2][1], ctrl[2][2]);
2596   }
2597   if (b == 2)
2598   {
2599     b = Patch_GetCVTangent(v2, ctrl[0][0], ctrl[1][2], ctrl[2][2]);
2600   }  
2601
2602         CrossProduct(v1, v2, normal);
2603
2604   
2605   if (normal[0] == 0.0f && normal[1] == 0.0f && normal[2] == 0.0f)
2606   {
2607     // more degenerate cases
2608     vec3_t pMid;
2609     vec3_t vCurve[3];
2610     /*
2611     if (VectorCompare(ctrl[0][0], ctrl[2][0])) // endcap left
2612     {
2613       if (VectorCompare(ctrl[0][2], ctrl[1][2]))
2614       {
2615         VectorSubtract(ctrl[2][2], ctrl[0][0], v2);
2616       }
2617       else if (VectorCompare(ctrl[1][2], ctrl[2][2]))
2618       {
2619         VectorSubtract(ctrl[0][2], ctrl[0][0], v2);
2620       }
2621       else
2622       a = Patch_DegenCurve(ctrl[0][2], ctrl[1][2], ctrl[2][2]);
2623       if (a == 0)
2624       {
2625         VectorCopy(ctrl[0][2], vCurve[0]);
2626         VectorCopy(ctrl[1][2], vCurve[1]);
2627         VectorCopy(ctrl[2][2], vCurve[2]);
2628         Patch_BezierInterpolate(vCurve, pMid);
2629                           VectorSubtract(pMid, ctrl[0][0], v1);
2630       }
2631       
2632       
2633                 }
2634           else if (VectorCompare(ctrl[0][0], ctrl[0][2])) // endcap right
2635                 {
2636       
2637       if (VectorCompare(ctrl[2][0], ctrl[2][1]))
2638       {
2639         VectorSubtract(ctrl[2][2], ctrl[0][0], v2);
2640       }
2641       else if (VectorCompare(ctrl[2][1], ctrl[2][2]))
2642       {
2643         VectorSubtract(ctrl[2][0], ctrl[0][0], v2);
2644       }
2645       else
2646       
2647       b = Patch_DegenCurve(ctrl[2][0], ctrl[2][1], ctrl[2][2]);
2648       if (b == 0)
2649       {
2650                     VectorCopy(ctrl[2][0], vCurve[0]);
2651         VectorCopy(ctrl[2][1], vCurve[1]);
2652         VectorCopy(ctrl[2][2], vCurve[2]);
2653         Patch_BezierInterpolate(vCurve, pMid);
2654                           VectorSubtract(pMid, ctrl[0][0], v2);
2655       }
2656       
2657                 }
2658     */
2659     if (VectorCompare(ctrl[0][0], ctrl[2][0])) // bottom degen
2660     {
2661       Patch_GetCVTangent(v1, ctrl[0][0], ctrl[2][1], ctrl[2][2]);
2662     }
2663     else if (VectorCompare(ctrl[0][0], ctrl[0][2])) // left degen
2664     {
2665       Patch_GetCVTangent(v2, ctrl[0][0], ctrl[1][2], ctrl[2][2]);
2666     }
2667     else if (VectorCompare(ctrl[0][2], ctrl[2][2])) // top degen
2668     {
2669       VectorSubtract(ctrl[2][0], ctrl[0][0], v1);
2670     }
2671     else if (VectorCompare(ctrl[2][0], ctrl[2][2])) // right degen
2672     {
2673       VectorSubtract(ctrl[0][2], ctrl[0][0], v2);
2674     }
2675     else // tangents parallel
2676     {
2677       VectorCopy(v1, vTemp1);
2678       VectorCopy(v2, vTemp2);
2679       VectorNormalize(vTemp1, vTemp1);
2680       VectorNormalize(vTemp2, vTemp2);
2681       if (VectorCompare(vTemp1, vTemp2)) // parallel same way
2682       {
2683         VectorSubtract(ctrl[2][0], ctrl[0][0], vTemp1);
2684         VectorNormalize(vTemp1, vTemp1);
2685         if (VectorCompare(vTemp1, vTemp2))
2686         {
2687           VectorSubtract(ctrl[0][2], ctrl[0][0], v2);
2688         }
2689         else
2690         {
2691           VectorCopy(vTemp1, v1);
2692         }
2693       }
2694       else // parallel opposite way
2695       {
2696                     VectorCopy(ctrl[2][0], vCurve[0]);
2697         VectorCopy(ctrl[1][1], vCurve[1]);
2698         VectorCopy(ctrl[0][2], vCurve[2]);
2699         Patch_BezierInterpolate(vCurve, pMid);
2700                           VectorSubtract(pMid, ctrl[0][0], v2);
2701                   }
2702     }
2703
2704     CrossProduct(v1, v2, normal);
2705   }
2706 }
2707
2708 void Patch_CalcCVNormals(patchMesh_t *patch)
2709 {
2710         int row, col, i, j, n;
2711         vec3_t ctrl[3][3];
2712         vec3_t normals[4];
2713
2714         for (col=0; col<patch->width; col+=2)
2715         {
2716                 for (row=0; row<patch->height; row+=2)
2717                 {
2718                         n=0;
2719                         if (col+1 != patch->width && row+1 != patch->height)
2720                         {
2721                                 for (i=0; i<3; i++)
2722                                         for (j=0; j<3; j++)
2723                                                 VectorCopy (patch->ctrl[col+i][row+j].xyz, ctrl[i][j]);
2724
2725                                 Patch_CVNormal(ctrl, normals[n]);
2726         VectorNormalize(normals[n], normals[n]);
2727                                 n++;
2728                         }
2729
2730                         if (col-1 >= 0 && row-1 >= 0)
2731                         {
2732                                 for (i=0; i<3; i++)
2733                                         for (j=0; j<3; j++)
2734                                                 VectorCopy (patch->ctrl[col-i][row-j].xyz, ctrl[i][j]);
2735
2736                                 Patch_CVNormal(ctrl, normals[n]);
2737         VectorNormalize(normals[n], normals[n]);
2738                                 n++;
2739                         }
2740                         if (col-1 >= 0 && row+1 != patch->height)
2741                         {
2742                                 for (i=0; i<3; i++)
2743                                         for (j=0; j<3; j++)
2744                                                 VectorCopy (patch->ctrl[col-i][row+j].xyz, ctrl[j][i]);
2745
2746                                 Patch_CVNormal(ctrl, normals[n]);
2747         VectorNormalize(normals[n], normals[n]);
2748                                 n++;
2749                         }
2750                         if (col+1 != patch->width && row-1 >= 0)
2751                         {
2752                                 for (i=0; i<3; i++)
2753                                         for (j=0; j<3; j++)
2754                                                 VectorCopy (patch->ctrl[col+i][row-j].xyz, ctrl[j][i]);
2755
2756                                 Patch_CVNormal(ctrl, normals[n]);
2757         VectorNormalize(normals[n], normals[n]);
2758                                 n++;
2759                         }
2760
2761                         for (i=0; i<3; i++)
2762                         {
2763                                 if (n == 1) patch->ctrl[col][row].normal[i] = normals[0][i];
2764                                 if (n == 2) patch->ctrl[col][row].normal[i] = (normals[0][i] + normals[1][i]) / n;
2765                                 //if (n == 3) patch->ctrl[col][row].normal[i] = (normals[0][i] + normals[1][i] + normals[2][i]) / n;
2766                                 if (n == 4) patch->ctrl[col][row].normal[i] = (normals[0][i] + normals[1][i] + normals[2][i] + normals[3][i]) / n;
2767                         }
2768                         VectorNormalize(patch->ctrl[col][row].normal, patch->ctrl[col][row].normal);
2769                         //if (!g_PrefsDlg.m_bGLLighting)
2770                         //      ShadeVertex(patch->ctrl[col][row]);
2771                 }
2772         }
2773 }
2774
2775
2776 void BTree_SetNormals(BTNode_t *pBT, vec3_t &normal)
2777 {
2778         if (pBT != NULL)
2779         {
2780                 if (pBT->left != NULL && pBT->right != NULL)
2781                 {
2782                         VectorCopy(normal, pBT->vMid.normal);
2783                         //if (!g_PrefsDlg.m_bGLLighting)
2784                         //      ShadeVertex(pBT->vMid);
2785                 }
2786                 BTree_SetNormals(pBT->left, normal);
2787                 BTree_SetNormals(pBT->right, normal);
2788         }
2789 }
2790
2791
2792 void NormalFromPoints(vec3_t p1, vec3_t p2, vec3_t p3, vec3_t &normal, bool flip = false)
2793 {
2794   vec3_t v1, v2;
2795
2796   if (flip)
2797   {
2798     VectorSubtract(p2, p3, v1); //p3->p2
2799           VectorSubtract(p1, p2, v2); //p2->p1
2800   }
2801   else
2802   {
2803     VectorSubtract(p2, p1, v1); //p1->p2
2804           VectorSubtract(p3, p2, v2); //p2->p3
2805   }
2806         CrossProduct(v1, v2, normal);
2807 }
2808
2809
2810 void BTree_GenerateNormals(BTNode_t *pBTMid, BTNode_t *pBTLeft, BTNode_t *pBTRight, bool avg, bool flat, bool nomid, bool noleft, bool noright, /*bool endcap, vec3_t &n1, vec3_t &n2,*/ bool flip)
2811 {
2812         if (pBTMid != NULL)
2813         {
2814                 if (pBTMid->left != NULL && pBTMid->right != NULL)
2815                 {
2816                         vec3_t normal;
2817      
2818       if (noleft) // left curve is degenerate
2819       {
2820         if (nomid) // mid curve is degenerate
2821         {
2822           NormalFromPoints(pBTRight->right->info.xyz, pBTRight->vMid.xyz, pBTMid->vMid.xyz, normal, flip);
2823                 NormalFromPoints(pBTRight->right->info.xyz, pBTRight->vMid.xyz, pBTMid->vMid.xyz, pBTRight->vMid.normal, flip);
2824         }
2825         //else if (endcap)
2826         //{
2827         //  VectorCopy(n1, normal);
2828         //  NormalFromPoints(pBTRight->right->info.xyz, pBTRight->vMid.xyz, pBTMid->vMid.xyz, pBTRight->vMid.normal, flip);
2829         //}
2830         else
2831         {
2832           NormalFromPoints(pBTMid->left->info.xyz, pBTLeft->vMid.xyz, pBTMid->vMid.xyz, normal, flip);
2833                 NormalFromPoints(pBTRight->right->info.xyz, pBTRight->vMid.xyz, pBTMid->vMid.xyz, pBTRight->vMid.normal, flip);
2834         }
2835       }
2836       else if (noright) // right curve is degenerate
2837       {
2838         if (nomid) // mid curve is degenerate
2839         {
2840           NormalFromPoints(pBTLeft->left->info.xyz, pBTLeft->vMid.xyz, pBTMid->vMid.xyz, normal, flip);
2841                 NormalFromPoints(pBTLeft->left->info.xyz, pBTLeft->vMid.xyz, pBTMid->vMid.xyz, pBTRight->vMid.normal, flip);
2842         }
2843         //else if (endcap)
2844         //{
2845         //  NormalFromPoints(pBTLeft->left->info.xyz, pBTLeft->vMid.xyz, pBTMid->vMid.xyz, normal, flip);
2846         //  VectorCopy(n2, pBTRight->vMid.normal);
2847         //}
2848         else
2849         {
2850           NormalFromPoints(pBTLeft->left->info.xyz, pBTLeft->vMid.xyz, pBTMid->vMid.xyz, normal, flip);
2851                 NormalFromPoints(pBTMid->right->info.xyz, pBTRight->vMid.xyz, pBTMid->vMid.xyz, pBTRight->vMid.normal, flip);
2852         }
2853       }
2854       else
2855       {
2856         if (flat) // all curves are semi-degenerate (flat) or degenerate
2857         {
2858           NormalFromPoints(pBTLeft->left->info.xyz, pBTLeft->vMid.xyz, pBTRight->vMid.xyz, normal, flip);
2859                 NormalFromPoints(pBTRight->right->info.xyz, pBTRight->vMid.xyz, pBTLeft->vMid.xyz, pBTRight->vMid.normal, flip);
2860         }
2861         else
2862         {
2863                       NormalFromPoints(pBTLeft->left->info.xyz, pBTLeft->vMid.xyz, pBTMid->vMid.xyz, normal, flip);
2864                 NormalFromPoints(pBTRight->right->info.xyz, pBTRight->vMid.xyz, pBTMid->vMid.xyz, pBTRight->vMid.normal, flip);
2865         }
2866       }
2867
2868       VectorNormalize(normal, normal);
2869                         if (avg)
2870                                 for (int i=0; i<3; i++)
2871                                         pBTLeft->vMid.normal[i] = (normal[i] + pBTLeft->vMid.normal[i]) / 2.0f;
2872                         else VectorCopy(normal, pBTLeft->vMid.normal);
2873      
2874                         VectorNormalize(pBTLeft->vMid.normal, pBTLeft->vMid.normal);
2875       VectorNormalize(pBTRight->vMid.normal, pBTRight->vMid.normal);
2876
2877                 }
2878                 BTree_GenerateNormals(pBTMid->left, pBTLeft->left, pBTRight->left, avg, flat, nomid, noleft, noright, /*endcap, n1, n2,*/ flip);
2879                 BTree_GenerateNormals(pBTMid->right, pBTLeft->right, pBTRight->right, avg, flat, nomid, noleft, noright, /*endcap, n1, n2,*/ flip);
2880         }
2881 }
2882
2883
2884
2885 void Patch_GenerateLODNormals(patchMesh_t *patch)
2886 {
2887   int col, row, rowpos, colpos, i;
2888   BTNode_t *tree[2][3];
2889   int degen[2][3];
2890   bool rowAvg, colAvg;
2891
2892   for(col=0; col+2<patch->width; col+=2)
2893         {
2894                 for(row=0; row+2<patch->height; row+=2)
2895                 {
2896       if (!patch->colDirty[col/2] && !patch->rowDirty[row/2]) continue;  
2897  
2898                 rowpos = ((col/2)*patch->height)+row;
2899       colpos = ((row/2)*patch->width)+col;
2900       
2901       if (row==0) rowAvg = false;
2902       else rowAvg = true;
2903       if (col==0) colAvg = false;
2904       else colAvg = true;
2905
2906       for (i=0; i<3; i++)
2907       {
2908         tree[0][i] = patch->rowLOD[rowpos+i];
2909         tree[1][i] = patch->colLOD[colpos+i];
2910         
2911         degen[0][i] = Patch_DegenCurve(patch->ctrl[col][row+i].xyz, patch->ctrl[col+1][row+i].xyz, patch->ctrl[col+2][row+i].xyz);
2912         degen[1][i] = Patch_DegenCurve(patch->ctrl[col+i][row].xyz, patch->ctrl[col+i][row+1].xyz, patch->ctrl[col+i][row+2].xyz);
2913       }
2914
2915       BTree_GenerateNormals(tree[0][1], tree[0][0], tree[0][2], rowAvg, (degen[1][0] && degen[1][1] && degen[1][2]), degen[0][1] == 2, degen[0][0] == 2, degen[0][2] == 2, /*degen[1][1], patch->ctrl[col][row].normal, patch->ctrl[col][row+2].normal,*/ false);
2916       BTree_GenerateNormals(tree[1][1], tree[1][0], tree[1][2], colAvg, (degen[0][0] && degen[0][1] && degen[0][2]), degen[1][1] == 2, degen[1][0] == 2, degen[1][2] == 2, /*degen[0][1], patch->ctrl[col][row].normal, patch->ctrl[col+2][row].normal,*/ true);
2917     }
2918   }
2919 }
2920
2921
2922 void Patch_ClearLODFlags(patchMesh_t *p)
2923 {
2924         int i;
2925
2926         for (i=0;i<(p->width-1)/2; i++)
2927                 p->colDirty[i] = false;
2928
2929         for (i=0;i<(p->height-1)/2; i++)
2930                 p->rowDirty[i] = false;
2931 }
2932
2933 // reset the lodDirty flags owned by all patches in the map
2934 // create new LOD trees for all dirty patches, matched with all other patches in the map
2935 void Patch_LODMatchAll()
2936 {
2937         brush_t *pb, *brushlist;
2938         int i;
2939
2940         // create LOD tree roots and LOD tree lists for all patches that are dirty
2941
2942         brushlist = &active_brushes;
2943         for (i=0; i<2; i++)
2944         {
2945                 for (pb = brushlist->next; pb && (pb != brushlist); pb=pb->next)
2946                 {
2947       // create lod for selected patches when patches are filtered
2948                         if (pb->bFiltered && (pb->patchBrush && !pb->pPatch->bSelected))
2949                                 continue;
2950                         if (!pb->patchBrush)
2951                                 continue;
2952                         if (!pb->pPatch->bDirty)
2953                                 continue;
2954
2955       Patch_CalcCVNormals(pb->pPatch);
2956                         Patch_CreateLODTrees(pb->pPatch);
2957                 }
2958                 brushlist = &selected_brushes;
2959         }
2960
2961         brushlist = &active_brushes;
2962         for (i=0; i<2; i++)
2963         {
2964                 for (pb = brushlist->next; pb && (pb != brushlist); pb=pb->next)
2965                 {
2966                         if (!pb->patchBrush)
2967                                 continue;
2968
2969       if (pb->pPatch->LODUpdated)
2970                           Patch_GenerateLODNormals(pb->pPatch);
2971
2972       Patch_ClearLODFlags(pb->pPatch);
2973     }
2974                 brushlist = &selected_brushes;
2975         }
2976
2977 }
2978
2979 void Vertex_TransformTexture(drawVert_t *pVert, float fx, float fy, transformtype xform)
2980 {
2981   switch(xform)
2982   {
2983   case TRANSLATE:
2984     pVert->st[0] += fx;
2985     pVert->st[1] += fy;
2986     break;
2987   case SCALE:
2988     pVert->st[0] *= fx;
2989     pVert->st[1] *= fy;
2990     break;
2991   case ROTATE:
2992     float x = pVert->st[0];
2993     float y = pVert->st[1];
2994     pVert->st[0] = x * fx - y * fy;
2995     pVert->st[1] = y * fx + x * fy;
2996   }
2997 }
2998
2999 void BTree_TransformTexture(BTNode_t *pBT, float fx, float fy, transformtype xform)
3000 {
3001         if (pBT != NULL)
3002         {       // PreOrder traversal
3003                 Vertex_TransformTexture(&pBT->info, fx, fy, xform);
3004     Vertex_TransformTexture(&pBT->vMid, fx, fy, xform);
3005                 BTree_TransformTexture(pBT->left, fx, fy, xform);
3006                 BTree_TransformTexture(pBT->right, fx, fy, xform);
3007         }
3008 }
3009
3010 void Patch_TransformLODTexture(patchMesh_t *p, float fx, float fy, transformtype xform)
3011 {
3012         int col, row;
3013
3014         for(col=1; col<p->width; col+=2)
3015                 for(row=0; row<p->height; row++)
3016                         BTree_TransformTexture(p->rowLOD[(((col-1)/2)*p->height)+row], fx, fy, xform);
3017
3018         for(row=1; row<p->height; row+=2)
3019                 for(col=0; col<p->width; col++)
3020                         BTree_TransformTexture(p->colLOD[(((row-1)/2)*p->width)+col], fx, fy, xform);
3021 }
3022
3023 void Patch_AddBTreeToDrawListInOrder(list<drawVert_t> *drawList, BTNode_t *pBT)
3024 {
3025         if (pBT != NULL) //traverse InOrder
3026         {
3027                 Patch_AddBTreeToDrawListInOrder(drawList, pBT->left);
3028                 if (pBT->left != NULL && pBT->right != NULL)
3029                         drawList->push_back(pBT->vMid);
3030                 Patch_AddBTreeToDrawListInOrder(drawList, pBT->right);
3031         }
3032 }
3033
3034 void Patch_InterpolateListFromRowBT(list<drawVert_t> *drawList, BTNode_t *rowBT, BTNode_t *rowBTLeft, drawVert_t *vCurve[], float u, float n, float v)
3035 {
3036         if (rowBT != NULL)
3037         {
3038                 Patch_InterpolateListFromRowBT(drawList, rowBT->left, rowBTLeft->left, vCurve, u-n, n*0.5f, v);
3039                 if (rowBT->left != NULL && rowBT->right != NULL)
3040                 {
3041                         vec3_t v1, v2;
3042                         drawVert_t newVert, vTemp1, vTemp2;
3043                         Patch_CurveSplit(vCurve, vTemp1, vTemp2, newVert, u);
3044                         for (int i=0; i<3; i++)
3045                         {
3046                                 v1[i] = rowBT->vMid.xyz[i] - rowBTLeft->vMid.xyz[i]; // left -> mid
3047                                 v1[i] = rowBTLeft->vMid.xyz[i] + (v1[i] * v);
3048                                 v1[i] = newVert.xyz[i] - v1[i];
3049                         }
3050                         VectorSubtract(vTemp1.xyz, newVert.xyz, v2);
3051                         CrossProduct(v1, v2, newVert.normal);
3052                         VectorNormalize(newVert.normal, newVert.normal);
3053                         //if (!g_PrefsDlg.m_bGLLighting)
3054                         //      ShadeVertex(newVert);
3055                         drawList->push_back(newVert);
3056                 }
3057                 Patch_InterpolateListFromRowBT(drawList, rowBT->right, rowBTLeft->right, vCurve, u+n, n*0.5f, v);
3058         }
3059 }
3060
3061 void Patch_TraverseColBTInOrder(list<list<drawVert_t>*>::iterator& iter, BTNode_t *colBTLeft, BTNode_t *colBT, BTNode_t *colBTRight, BTNode_t *rowBT, BTNode_t *rowBTLeft, float v, float n)
3062 {
3063         if (colBT != NULL)
3064         {
3065                  //traverse subtree In Order
3066                 Patch_TraverseColBTInOrder(iter, colBTLeft->left, colBT->left, colBTRight->left, rowBT, rowBTLeft, v-n, n*0.5f);
3067                 if (colBT->left != NULL && colBT->right != NULL)
3068                 {
3069                         drawVert_t *vCurve[3];
3070                         vCurve[0] = &colBTLeft->vMid;
3071                         vCurve[1] = &colBT->vMid;
3072                         vCurve[2] = &colBTRight->vMid;
3073                         Patch_InterpolateListFromRowBT((*iter), rowBT, rowBTLeft, vCurve, 0.5f, 0.25f, v);
3074
3075                         (*iter)->push_back(colBTRight->vMid);
3076                         iter++;
3077                 }
3078                 Patch_TraverseColBTInOrder(iter, colBTLeft->right, colBT->right, colBTRight->right, rowBT, rowBTLeft, v+n, n*0.5f);
3079         }
3080 }
3081
3082
3083 void Patch_StartDrawLists(list<list<drawVert_t>*> *drawLists, BTNode_t *colBT)
3084 {
3085         if (colBT != NULL)
3086         {
3087                  //traverse subtree In Order
3088                 Patch_StartDrawLists(drawLists, colBT->left);
3089                 if (colBT->left != NULL && colBT->right != NULL)
3090                 {
3091                         list<drawVert_t> *newList = new list<drawVert_t>;
3092                         drawLists->push_back(newList); // add empty list to back
3093                         drawLists->back()->push_back(colBT->vMid);
3094                 }
3095                 Patch_StartDrawLists(drawLists, colBT->right);
3096         }
3097 }
3098
3099 typedef list<drawVert_t> drawList_t;
3100 typedef list<list<drawVert_t>*> drawLists_t;
3101
3102 void Patch_CreateDrawLists(patchMesh_t *patch)
3103 {
3104   int col, row, colpos, rowpos;
3105
3106         drawLists_t *drawLists = new drawLists_t;
3107
3108         drawLists_t::iterator iter1, iter2;
3109
3110         for (row=0; row<patch->height; row+=2)
3111         {
3112                 colpos = (row/2)*patch->width;
3113                 drawList_t *newList = new drawList_t;
3114                 drawLists->push_back(newList); // add a new empty list to back
3115                 drawLists->back()->push_back(patch->ctrl[0][row]); // fill list at back
3116
3117                 if (row+1 == patch->height)
3118                         continue;
3119                 Patch_StartDrawLists(drawLists, patch->colLOD[colpos]);
3120         }
3121
3122         iter1 = drawLists->begin();
3123         for (row=0; row<patch->height; row+=2)
3124         {
3125                 iter2 = iter1;
3126                 for (col=0; col+1<patch->width; col+=2)
3127                 {
3128                         iter1 = iter2;
3129                         colpos = ((row/2)*patch->width)+col;
3130                         rowpos = ((col/2)*patch->height)+row;
3131
3132       Patch_AddBTreeToDrawListInOrder((*iter1), patch->rowLOD[rowpos]);
3133                         (*iter1)->push_back(patch->ctrl[col+2][row]);
3134                         
3135                         if (row+1 == patch->height)
3136                                 continue;
3137                 
3138                         iter1++;        
3139
3140       Patch_TraverseColBTInOrder(iter1, patch->colLOD[colpos], patch->colLOD[colpos+1], patch->colLOD[colpos+2], patch->rowLOD[rowpos+1], patch->rowLOD[rowpos], 0.5, 0.25);
3141                 }
3142         }
3143
3144   patch->drawLists = drawLists;
3145 }
3146
3147
3148 void Patch_DeleteDrawLists(patchMesh_t *patch)
3149 {
3150   drawLists_t *drawLists;
3151   drawLists_t::iterator iter;
3152
3153   if (patch->drawLists == NULL)
3154     return;
3155
3156   drawLists = (drawLists_t *)patch->drawLists;
3157
3158         for (iter=drawLists->begin(); iter != drawLists->end(); iter++)
3159         {
3160                 delete (*iter);
3161         }
3162
3163   delete drawLists;
3164   patch->drawLists = NULL;
3165 }
3166
3167
3168 void Patch_DrawLODPatchMesh(patchMesh_t *patch)
3169 {
3170         drawLists_t *drawLists;
3171
3172         drawLists_t::iterator iterLists, iterListsNext;
3173         drawList_t::iterator iterList, iterListNext;
3174
3175   //int nGLState = g_pParentWnd->GetCamera()->Camera()->draw_glstate;
3176
3177   if (patch->drawLists == NULL)
3178     return;
3179
3180   drawLists = (drawLists_t *)patch->drawLists;
3181
3182         iterListsNext=drawLists->begin();
3183         iterListsNext++;
3184         for (iterLists=drawLists->begin(); iterLists != drawLists->end() && iterListsNext != drawLists->end(); iterLists++, iterListsNext++)
3185   {
3186                 // traverse two drawlists at once to draw a strip
3187     //if (nGLState & DRAW_GL_LINE)
3188                   qglBegin(GL_QUAD_STRIP);
3189     //else
3190     //  qglBegin(GL_TRIANGLE_STRIP);
3191                 for (iterList=(*iterLists)->begin(), iterListNext=(*iterListsNext)->begin(); iterList != (*iterLists)->end() && iterListNext != (*iterListsNext)->end(); iterList++, iterListNext++)
3192                 {
3193                         //if (g_PrefsDlg.m_bGLLighting)
3194                                 qglNormal3fv((*iterList).normal);
3195                         //else if (bShade && !g_PrefsDlg.m_bDisplayLists)
3196                         //      qglColor3f((*iterList).lightmap[0], (*iterList).lightmap[0], (*iterList).lightmap[0]);
3197
3198                         qglTexCoord2fv((*iterList).st);
3199                         qglVertex3fv((*iterList).xyz);
3200
3201                   //if (g_PrefsDlg.m_bGLLighting)
3202                                 qglNormal3fv((*iterListNext).normal);
3203                         //else if (bShade && !g_PrefsDlg.m_bDisplayLists)
3204                         //      qglColor3f((*iterListNext).lightmap[0], (*iterListNext).lightmap[0], (*iterListNext).lightmap[0]);
3205
3206                         qglTexCoord2fv((*iterListNext).st);
3207                         qglVertex3fv((*iterListNext).xyz);
3208     }
3209                 qglEnd();
3210   }
3211 /*
3212 #ifdef _DEBUG
3213   vec3_t vNormal;
3214   for (iterLists=drawLists->begin(); iterLists != drawLists->end(); iterLists++)
3215   {
3216                 qglBegin (GL_LINES); // draw normals
3217                 //qglColor3f(1,1,1);
3218                 for (iterList=(*iterLists)->begin(); iterList != (*iterLists)->end(); iterList++)
3219                 {
3220                         VectorAdd((*iterList).xyz, (*iterList).normal, vNormal);
3221                         qglVertex3fv ((*iterList).xyz);
3222                         qglVertex3fv (vNormal);
3223                 }
3224                 qglEnd ();
3225   }
3226
3227         Patch_DrawNormals(patch);
3228
3229 #endif
3230   */
3231 }
3232
3233 /*
3234 // fast memory-efficient ray-triangle intersection - MollerTrumbore97 
3235
3236 #define EPSILON 0.000001
3237 #define CROSS(dest,v1,v2) {dest[0]=v1[1]*v2[2]-v1[2]*v2[1];dest[1]=v1[2]*v2[0]-v1[0]*v2[2];dest[2]=v1[0]*v2[1]-v1[1]*v2[0];}
3238 #define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
3239 #define SUB(dest,v1,v2) {dest[0]=v1[0]-v2[0];dest[1]=v1[1]-v2[1];dest[2]=v1[2]-v2[2];}
3240
3241 int intersect_triangle(float orig[3], float dir[3],
3242                    float vert0[3], float vert1[3], float vert2[3],
3243                    double *t, double *u, double *v)
3244 {
3245    double edge1[3], edge2[3], tvec[3], pvec[3], qvec[3];
3246    double det,inv_det;
3247
3248    // find vectors for two edges sharing vert0
3249    SUB(edge1, vert1, vert0);
3250    SUB(edge2, vert2, vert0);
3251
3252    // begin calculating determinant - also used to calculate U parameter 
3253    CROSS(pvec, dir, edge2);
3254
3255    // if determinant is near zero, ray lies in plane of triangle
3256    det = DOT(edge1, pvec);
3257
3258 #ifdef TEST_CULL           // define TEST_CULL if culling is desired
3259    if (det < EPSILON)
3260       return 0;
3261
3262    // calculate distance from vert0 to ray origin
3263    SUB(tvec, orig, vert0);
3264
3265    // calculate U parameter and test bounds
3266    *u = DOT(tvec, pvec);
3267    if (*u < 0.0 || *u > det)
3268       return 0;
3269
3270    // prepare to test V parameter
3271    CROSS(qvec, tvec, edge1);
3272
3273     // calculate V parameter and test bounds
3274    *v = DOT(dir, qvec);
3275    if (*v < 0.0 || *u + *v > det)
3276       return 0;
3277
3278    // calculate t, scale parameters, ray intersects triangle
3279    *t = DOT(edge2, qvec);
3280    inv_det = 1.0 / det;
3281    *t *= inv_det;
3282    *u *= inv_det;
3283    *v *= inv_det;
3284 #else                    // the non-culling branch
3285    if (det > -EPSILON && det < EPSILON)
3286      return 0;
3287    inv_det = 1.0 / det;
3288
3289    // calculate distance from vert0 to ray origin
3290    SUB(tvec, orig, vert0);
3291
3292    // calculate U parameter and test bounds
3293    *u = DOT(tvec, pvec) * inv_det;
3294    if (*u < 0.0 || *u > 1.0)
3295      return 0;
3296
3297    // prepare to test V parameter
3298    CROSS(qvec, tvec, edge1);
3299
3300    // calculate V parameter and test bounds
3301    *v = DOT(dir, qvec) * inv_det;
3302    if (*v < 0.0 || *u + *v > 1.0)
3303      return 0;
3304
3305    // calculate t, ray intersects triangle
3306    *t = DOT(edge2, qvec) * inv_det;
3307 #endif
3308    return 1;
3309 }
3310 */
3311
3312 int Triangle_Ray(float orig[3], float dir[3], bool bCullBack,
3313                  float vert0[3], float vert1[3], float vert2[3],
3314                  double *t, double *u, double *v)
3315 {
3316   float edge1[3], edge2[3], tvec[3], pvec[3], qvec[3];
3317   double det,inv_det;
3318   
3319   /* find vectors for two edges sharing vert0 */
3320   VectorSubtract(vert1, vert0, edge1);
3321   VectorSubtract(vert2, vert0, edge2);
3322   
3323   /* begin calculating determinant - also used to calculate U parameter */
3324   CrossProduct(dir, edge2, pvec);
3325   
3326   /* if determinant is near zero, ray lies in plane of triangle */
3327   det = DotProduct(edge1, pvec);
3328   
3329   if (bCullBack)
3330   {
3331     if (det < 0.000001)
3332       return 0;
3333     
3334     // calculate distance from vert0 to ray origin
3335     VectorSubtract(orig, vert0, tvec);
3336     
3337     // calculate U parameter and test bounds
3338     *u = DotProduct(tvec, pvec);
3339     if (*u < 0.0 || *u > det)
3340       return 0;
3341     
3342     // prepare to test V parameter
3343     CrossProduct(tvec, edge1, qvec);
3344     
3345     // calculate V parameter and test bounds
3346     *v = DotProduct(dir, qvec);
3347     if (*v < 0.0 || *u + *v > det)
3348       return 0;
3349     
3350     // calculate t, scale parameters, ray intersects triangle
3351     *t = DotProduct(edge2, qvec);
3352     inv_det = 1.0 / det;
3353     *t *= inv_det;
3354     *u *= inv_det;
3355     *v *= inv_det;
3356   }
3357   else
3358   {
3359     /* the non-culling branch */
3360     if (det > -0.000001 && det < 0.000001)
3361       return 0;
3362     inv_det = 1.0 / det;
3363     
3364     /* calculate distance from vert0 to ray origin */
3365     VectorSubtract(orig, vert0, tvec);
3366     
3367     /* calculate U parameter and test bounds */
3368     *u = DotProduct(tvec, pvec) * inv_det;
3369     if (*u < 0.0 || *u > 1.0)
3370       return 0;
3371     
3372     /* prepare to test V parameter */
3373     CrossProduct(tvec, edge1, qvec);
3374     
3375     /* calculate V parameter and test bounds */
3376     *v = DotProduct(dir, qvec) * inv_det;
3377     if (*v < 0.0 || *u + *v > 1.0)
3378       return 0;
3379     
3380     /* calculate t, ray intersects triangle */
3381     *t = DotProduct(edge2, qvec) * inv_det;
3382   }
3383   return 1;
3384 }
3385
3386 bool Patch_Ray(patchMesh_t *patch, vec3_t origin, vec3_t dir, double *t, double *u, double *v)
3387 {
3388         drawLists_t *drawLists;
3389
3390         drawLists_t::iterator iterLists, iterListsNext;
3391         drawList_t::iterator i1, i2, i3, i4;
3392
3393 //  vec3_t tris[2][3];
3394   bool bIntersect = false;
3395   float tBest = FLT_MAX;
3396
3397   if (patch->drawLists == NULL)
3398     return false;
3399
3400   drawLists = (drawLists_t *)patch->drawLists;
3401
3402         iterListsNext=drawLists->begin();
3403         iterListsNext++;
3404         for (iterLists=drawLists->begin(); iterLists != drawLists->end() && iterListsNext != drawLists->end(); iterLists++, iterListsNext++)
3405   {
3406                 // traverse two drawlists at once with two iterators each to triangulate
3407     i1 = i3 = (*iterLists)->begin();
3408     i2 = i4 = (*iterListsNext)->begin();
3409     i3++;
3410     i4++;
3411                 while (i3 != (*iterLists)->end() && i4 != (*iterListsNext)->end())
3412                 {
3413       if (Triangle_Ray(origin, dir, false, (*i1).xyz, (*i2).xyz, (*i3).xyz, t, u, v))
3414       {
3415         bIntersect = true;
3416         if (*t < tBest)
3417           tBest = *t;
3418       }      
3419       if (Triangle_Ray(origin, dir, false, (*i3).xyz, (*i4).xyz, (*i2).xyz, t, u, v))
3420       {
3421         bIntersect = true;
3422         if (*t < tBest)
3423           tBest = *t;
3424       }
3425       i1++;
3426       i2++;
3427       i3++;
3428       i4++;
3429                 }
3430   }
3431   if (bIntersect)
3432   {
3433     *t = tBest;
3434     return true;
3435   }
3436   else
3437   {
3438     *t = 0;
3439     return false;
3440   }
3441 }
3442
3443 // spog - curve LOD stuff ends
3444
3445 /*
3446 =================
3447 DrawPatchMesh
3448 =================
3449 */
3450 void DrawPatchMesh(patchMesh_t *pm)
3451 {
3452   if (g_PrefsDlg.m_bDisplayLists)
3453   {
3454     if (pm->bDirty || pm->nListID <= 0 || pm->LODUpdated)
3455     {
3456       if (pm->nListID <= 0)
3457         pm->nListID = qglGenLists(1);
3458       if (pm->nListID > 0)
3459       {
3460         qglNewList(pm->nListID, GL_COMPILE_AND_EXECUTE);
3461       }
3462
3463       Patch_DeleteDrawLists(pm);
3464       Patch_CreateDrawLists(pm);
3465         
3466                   Patch_DrawLODPatchMesh(pm);
3467
3468       if (pm->nListID > 0)
3469       {
3470         qglEndList();
3471             }
3472
3473             pm->bDirty = false;
3474             pm->LODUpdated = false;
3475     }
3476     else
3477     {
3478       qglCallList(pm->nListID);
3479     }
3480   }
3481   else
3482   {
3483     if (pm->bDirty || pm->LODUpdated)
3484     {
3485       Patch_DeleteDrawLists(pm);
3486       Patch_CreateDrawLists(pm);
3487       pm->bDirty = false;