Experimental: add "XactCylinder" to make a better patch cylinder
[xonotic/netradiant.git] / radiant / patch.h
1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
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 #if !defined(INCLUDED_PATCH_H)
23 #define INCLUDED_PATCH_H
24
25 /// \file
26 /// \brief The patch primitive.
27 ///
28 /// A 2-dimensional matrix of vertices that define a quadratic bezier surface.
29 /// The Boundary-Representation of this primitive is a triangle mesh.
30 /// The surface is recursively tesselated until the angle between each triangle
31 /// edge is smaller than a specified tolerance.
32
33
34 #include "nameable.h"
35 #include "ifilter.h"
36 #include "imap.h"
37 #include "ipatch.h"
38 #include "cullable.h"
39 #include "renderable.h"
40 #include "editable.h"
41 #include "selectable.h"
42
43 #include "debugging/debugging.h"
44
45 #include <set>
46 #include <limits>
47
48 #include "math/frustum.h"
49 #include "string/string.h"
50 #include "stream/stringstream.h"
51 #include "stream/textstream.h"
52 #include "xml/xmlelement.h"
53 #include "scenelib.h"
54 #include "transformlib.h"
55 #include "instancelib.h"
56 #include "selectionlib.h"
57 #include "traverselib.h"
58 #include "render.h"
59 #include "stringio.h"
60 #include "shaderlib.h"
61 #include "generic/callback.h"
62 #include "signal/signalfwd.h"
63 #include "texturelib.h"
64 #include "xml/ixml.h"
65 #include "dragplanes.h"
66
67 enum EPatchType
68 {
69   ePatchTypeQuake3,
70   ePatchTypeDoom3,
71 };
72
73 extern int g_PatchSubdivideThreshold;
74
75
76 #define MIN_PATCH_WIDTH 3
77 #define MIN_PATCH_HEIGHT 3
78
79 extern std::size_t MAX_PATCH_WIDTH;
80 extern std::size_t MAX_PATCH_HEIGHT;
81
82 #define MAX_PATCH_ROWCTRL (((MAX_PATCH_WIDTH-1)-1)/2)
83 #define MAX_PATCH_COLCTRL (((MAX_PATCH_HEIGHT-1)-1)/2)
84
85 enum EPatchCap
86 {
87   eCapBevel,
88   eCapEndCap,
89   eCapIBevel,
90   eCapIEndCap,
91   eCapCylinder,
92 };
93
94 enum EPatchPrefab
95 {
96   ePlane,
97   eBevel,
98   eEndCap,
99   eCylinder,
100   eDenseCylinder,
101   eVeryDenseCylinder,
102   eSqCylinder,
103   eCone,
104   eSphere,
105   eXactCylinder,
106 };
107
108 enum EMatrixMajor
109 {
110   ROW, COL,
111 };
112
113 struct BezierCurve
114 {
115   Vector3 crd;
116   Vector3 left;
117   Vector3 right;
118 };
119
120 const std::size_t BEZIERCURVETREE_MAX_INDEX = std::size_t(1) << (std::numeric_limits<std::size_t>::digits - 1);
121
122 struct BezierCurveTree
123 {
124   std::size_t index;
125   BezierCurveTree* left;
126   BezierCurveTree* right;
127 };
128
129 inline bool BezierCurveTree_isLeaf(const BezierCurveTree* node)
130 {
131   return node->left == 0 && node->right == 0;
132 }
133
134 void BezierCurveTree_Delete(BezierCurveTree *pCurve);
135
136
137 inline VertexPointer vertexpointer_arbitrarymeshvertex(const ArbitraryMeshVertex* array)
138 {
139   return VertexPointer(VertexPointer::pointer(&array->vertex), sizeof(ArbitraryMeshVertex));
140 }
141
142 typedef PatchControl* PatchControlIter;
143 typedef const PatchControl* PatchControlConstIter;
144
145 inline void copy_ctrl(PatchControlIter ctrl, PatchControlConstIter begin, PatchControlConstIter end)
146 {
147   std::copy(begin, end, ctrl);
148 }
149
150 const Colour4b colour_corner(0, 255, 0, 255);
151 const Colour4b colour_inside(255, 0, 255, 255);
152
153 class Patch;
154
155 class PatchFilter
156 {
157 public:
158   virtual bool filter(const Patch& patch) const = 0;
159 };
160
161 bool patch_filtered(Patch& patch);
162 void add_patch_filter(PatchFilter& filter, int mask, bool invert = false);
163
164 void Patch_addTextureChangedCallback(const SignalHandler& handler);
165 void Patch_textureChanged();
166
167 inline void BezierCurveTreeArray_deleteAll(Array<BezierCurveTree*>& curveTrees)
168 {
169   for(Array<BezierCurveTree*>::iterator i = curveTrees.begin(); i != curveTrees.end(); ++i)
170   {
171     BezierCurveTree_Delete(*i);
172   }
173 }
174
175 inline void PatchControlArray_invert(Array<PatchControl>& ctrl, std::size_t width, std::size_t height)
176 {
177   Array<PatchControl> tmp(width);
178
179   PatchControlIter from = ctrl.data() + (width * (height - 1));
180   PatchControlIter to = ctrl.data();
181   for(std::size_t h = 0; h != ((height - 1) >> 1); ++h, to += width, from -= width)
182   {
183     copy_ctrl(tmp.data(), to, to + width);
184     copy_ctrl(to, from, from + width);
185     copy_ctrl(from, tmp.data(), tmp.data() + width);
186   }
187 }
188
189 class PatchTesselation
190 {
191 public:
192   PatchTesselation()
193     : m_numStrips(0), m_lenStrips(0), m_nArrayWidth(0), m_nArrayHeight(0)
194   {
195   }
196   Array<ArbitraryMeshVertex> m_vertices;
197   Array<RenderIndex> m_indices;
198   std::size_t m_numStrips;
199   std::size_t m_lenStrips;
200
201   Array<std::size_t> m_arrayWidth;
202   std::size_t m_nArrayWidth;
203   Array<std::size_t> m_arrayHeight;
204   std::size_t m_nArrayHeight;
205
206   Array<BezierCurveTree*> m_curveTreeU;
207   Array<BezierCurveTree*> m_curveTreeV;
208 };
209
210 class RenderablePatchWireframe : public OpenGLRenderable
211 {
212   PatchTesselation& m_tess;
213 public:
214   RenderablePatchWireframe(PatchTesselation& tess) : m_tess(tess)
215   {
216   }
217   void render(RenderStateFlags state) const
218   {
219     {
220   #if NV_DRIVER_BUG
221       glVertexPointer(3, GL_FLOAT, 0, 0);
222       glDrawArrays(GL_TRIANGLE_FAN, 0, 0);
223   #endif
224
225       std::size_t n = 0;
226       glVertexPointer(3, GL_FLOAT, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->vertex);
227       for(std::size_t i = 0; i <= m_tess.m_curveTreeV.size(); ++i)
228       {
229         glDrawArrays(GL_LINE_STRIP, GLint(n), GLsizei(m_tess.m_nArrayWidth));
230
231         if(i == m_tess.m_curveTreeV.size()) break;
232
233         if(!BezierCurveTree_isLeaf(m_tess.m_curveTreeV[i]))
234           glDrawArrays(GL_LINE_STRIP, GLint(m_tess.m_curveTreeV[i]->index), GLsizei(m_tess.m_nArrayWidth));
235
236         n += (m_tess.m_arrayHeight[i]*m_tess.m_nArrayWidth);
237       
238       }
239     }
240
241     {
242       const ArbitraryMeshVertex* p = m_tess.m_vertices.data();
243       std::size_t n = m_tess.m_nArrayWidth * sizeof(ArbitraryMeshVertex);
244       for(std::size_t i = 0; i <= m_tess.m_curveTreeU.size(); ++i)
245       {
246         glVertexPointer(3, GL_FLOAT, GLsizei(n), &p->vertex);
247         glDrawArrays(GL_LINE_STRIP, 0, GLsizei(m_tess.m_nArrayHeight));
248
249         if(i == m_tess.m_curveTreeU.size()) break;
250
251         if(!BezierCurveTree_isLeaf(m_tess.m_curveTreeU[i]))
252         {
253           glVertexPointer(3, GL_FLOAT, GLsizei(n), &(m_tess.m_vertices.data() + (m_tess.m_curveTreeU[i]->index))->vertex);
254           glDrawArrays(GL_LINE_STRIP, 0, GLsizei(m_tess.m_nArrayHeight));
255         }
256
257         p += m_tess.m_arrayWidth[i];
258       }
259     }
260   }
261 };
262
263 class RenderablePatchFixedWireframe : public OpenGLRenderable
264 {
265   PatchTesselation& m_tess;
266 public:
267   RenderablePatchFixedWireframe(PatchTesselation& tess) : m_tess(tess)
268   {
269   }
270   void render(RenderStateFlags state) const
271   {
272     glVertexPointer(3, GL_FLOAT, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->vertex);
273     const RenderIndex* strip_indices = m_tess.m_indices.data();
274     for(std::size_t i = 0; i<m_tess.m_numStrips; i++, strip_indices += m_tess.m_lenStrips)
275     {
276       glDrawElements(GL_QUAD_STRIP, GLsizei(m_tess.m_lenStrips), RenderIndexTypeID, strip_indices);
277     }
278   }
279 };
280
281 class RenderablePatchSolid : public OpenGLRenderable
282 {
283   PatchTesselation& m_tess;
284 public:
285   RenderablePatchSolid(PatchTesselation& tess) : m_tess(tess)
286   {
287   }
288   void RenderNormals() const;
289   void render(RenderStateFlags state) const
290   {
291 #if 0
292     if((state & RENDER_FILL) == 0)
293     {
294       RenderablePatchWireframe(m_tess).render(state);
295     }
296     else
297 #endif
298     {
299       if((state & RENDER_BUMP) != 0)
300       {
301         if(GlobalShaderCache().useShaderLanguage())
302         {
303           glNormalPointer(GL_FLOAT, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->normal);
304           glVertexAttribPointerARB(c_attr_TexCoord0, 2, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->texcoord);
305           glVertexAttribPointerARB(c_attr_Tangent, 3, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->tangent);
306           glVertexAttribPointerARB(c_attr_Binormal, 3, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->bitangent);
307         }
308         else
309         {
310           glVertexAttribPointerARB(11, 3, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->normal);
311           glVertexAttribPointerARB(8, 2, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->texcoord);
312           glVertexAttribPointerARB(9, 3, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->tangent);
313           glVertexAttribPointerARB(10, 3, GL_FLOAT, 0, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->bitangent);
314         }
315       }
316       else
317       {
318         glNormalPointer(GL_FLOAT, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->normal);
319         glTexCoordPointer(2, GL_FLOAT, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->texcoord);
320       }
321       glVertexPointer(3, GL_FLOAT, sizeof(ArbitraryMeshVertex), &m_tess.m_vertices.data()->vertex);
322       const RenderIndex* strip_indices = m_tess.m_indices.data();
323       for(std::size_t i = 0; i<m_tess.m_numStrips; i++, strip_indices += m_tess.m_lenStrips)
324       {
325         glDrawElements(GL_QUAD_STRIP, GLsizei(m_tess.m_lenStrips), RenderIndexTypeID, strip_indices);
326       }
327     }
328  
329 #if defined(_DEBUG)
330     RenderNormals();
331 #endif
332   }
333 };
334
335 // parametric surface defined by quadratic bezier control curves
336 class Patch :
337   public XMLImporter,
338   public XMLExporter,
339   public TransformNode,
340   public Bounded,
341   public Cullable,
342   public Snappable,
343   public Undoable,
344   public Filterable,
345   public Nameable
346 {
347   class xml_state_t
348   {
349   public:
350     enum EState
351     {
352       eDefault,
353       ePatch,
354       eMatrix,
355       eShader,
356     };
357     xml_state_t(EState state)
358       : m_state(state)
359     {}
360     EState state() const
361     {
362       return m_state;
363     }
364     const char* content() const
365     {
366       return m_content.c_str();
367     }
368     std::size_t write(const char* buffer, std::size_t length)
369     {
370       return m_content.write(buffer, length);
371     }
372   private:
373     EState m_state;
374     StringOutputStream m_content;
375   };
376
377   std::vector<xml_state_t> m_xml_state;
378
379   typedef Array<PatchControl> PatchControlArray;
380
381   class SavedState : public UndoMemento
382   {
383   public:
384     SavedState(
385       std::size_t width,
386       std::size_t height,
387       const PatchControlArray& ctrl,
388       const char* shader,
389       bool patchDef3,
390       std::size_t subdivisions_x,
391       std::size_t subdivisions_y
392     ) :
393       m_width(width),
394       m_height(height),
395       m_shader(shader),
396       m_ctrl(ctrl),
397       m_patchDef3(patchDef3),
398       m_subdivisions_x(subdivisions_x),
399       m_subdivisions_y(subdivisions_y)
400     {
401     }
402
403     void release()
404     {
405       delete this;
406     }
407
408     std::size_t m_width, m_height;
409     CopiedString m_shader;
410     PatchControlArray m_ctrl;
411     bool m_patchDef3;
412     std::size_t m_subdivisions_x;
413     std::size_t m_subdivisions_y;
414   };
415
416 public:
417   class Observer
418   {
419   public:
420     virtual void allocate(std::size_t size) = 0;
421   };
422
423 private:
424   typedef UniqueSet<Observer*> Observers;
425   Observers m_observers;
426
427   scene::Node* m_node;
428
429   AABB m_aabb_local; // local bbox
430
431   CopiedString m_shader;
432   Shader* m_state;
433
434   std::size_t m_width;
435   std::size_t m_height;
436 public:
437   bool m_patchDef3;
438   std::size_t m_subdivisions_x;
439   std::size_t m_subdivisions_y;
440 private:
441   
442   UndoObserver* m_undoable_observer;
443   MapFile* m_map;
444
445   // dynamically allocated array of control points, size is m_width*m_height
446   PatchControlArray m_ctrl;
447   PatchControlArray m_ctrlTransformed;
448
449   PatchTesselation m_tess;
450   RenderablePatchSolid m_render_solid;
451   RenderablePatchWireframe m_render_wireframe;
452   RenderablePatchFixedWireframe m_render_wireframe_fixed;
453
454   static Shader* m_state_ctrl;
455   static Shader* m_state_lattice;
456   VertexBuffer<PointVertex> m_ctrl_vertices;
457   RenderableVertexBuffer m_render_ctrl;
458   IndexBuffer m_lattice_indices;
459   RenderableIndexBuffer m_render_lattice;
460
461   bool m_bOverlay;
462
463   bool m_transformChanged;
464   Callback m_evaluateTransform;
465   Callback m_boundsChanged;
466
467   void construct()
468   {
469     m_bOverlay = false;
470     m_width = m_height = 0;
471
472     m_patchDef3 = false;
473     m_subdivisions_x = 0;
474     m_subdivisions_y = 0;
475
476     check_shader();
477     captureShader();
478
479     m_xml_state.push_back(xml_state_t::eDefault);
480   }
481
482 public:
483   Callback m_lightsChanged;
484
485   static int m_CycleCapIndex;// = 0;
486   static EPatchType m_type;
487
488   STRING_CONSTANT(Name, "Patch");
489
490   Patch(scene::Node& node, const Callback& evaluateTransform, const Callback& boundsChanged) :
491     m_node(&node),
492     m_shader(texdef_name_default()),
493     m_state(0),
494     m_undoable_observer(0),
495     m_map(0),
496     m_render_solid(m_tess),
497     m_render_wireframe(m_tess),
498     m_render_wireframe_fixed(m_tess),
499     m_render_ctrl(GL_POINTS, m_ctrl_vertices),
500     m_render_lattice(GL_LINES, m_lattice_indices, m_ctrl_vertices),
501     m_transformChanged(false),
502     m_evaluateTransform(evaluateTransform),
503     m_boundsChanged(boundsChanged)
504   {
505     construct();
506   }
507   Patch(const Patch& other, scene::Node& node, const Callback& evaluateTransform, const Callback& boundsChanged) :
508     m_node(&node),
509     m_shader(texdef_name_default()),
510     m_state(0),
511     m_undoable_observer(0),
512     m_map(0),
513     m_render_solid(m_tess),
514     m_render_wireframe(m_tess),
515     m_render_wireframe_fixed(m_tess),
516     m_render_ctrl(GL_POINTS, m_ctrl_vertices),
517     m_render_lattice(GL_LINES, m_lattice_indices, m_ctrl_vertices),
518     m_transformChanged(false),
519     m_evaluateTransform(evaluateTransform),
520     m_boundsChanged(boundsChanged)
521   {
522     construct();
523
524     m_patchDef3 = other.m_patchDef3;
525     m_subdivisions_x = other.m_subdivisions_x;
526     m_subdivisions_y = other.m_subdivisions_y;
527     setDims(other.m_width, other.m_height);
528     copy_ctrl(m_ctrl.data(), other.m_ctrl.data(), other.m_ctrl.data()+(m_width*m_height));
529     SetShader(other.m_shader.c_str());
530     controlPointsChanged();
531   }
532
533   Patch(const Patch& other) :
534     XMLImporter(other),
535     XMLExporter(other),
536     TransformNode(other),
537     Bounded(other),
538     Cullable(other),
539     Snappable(),
540     Undoable(other),
541     Filterable(other),
542     Nameable(other),
543     m_state(0),
544     m_undoable_observer(0),
545     m_map(0),
546     m_render_solid(m_tess),
547     m_render_wireframe(m_tess),
548     m_render_wireframe_fixed(m_tess),
549     m_render_ctrl(GL_POINTS, m_ctrl_vertices),
550     m_render_lattice(GL_LINES, m_lattice_indices, m_ctrl_vertices),
551     m_transformChanged(false),
552     m_evaluateTransform(other.m_evaluateTransform),
553     m_boundsChanged(other.m_boundsChanged)
554   {
555     m_bOverlay = false;
556
557     m_patchDef3 = other.m_patchDef3;
558     m_subdivisions_x = other.m_subdivisions_x;
559     m_subdivisions_y = other.m_subdivisions_y;
560     setDims(other.m_width, other.m_height);
561     copy_ctrl(m_ctrl.data(), other.m_ctrl.data(), other.m_ctrl.data()+(m_width*m_height));
562     SetShader(other.m_shader.c_str());
563     controlPointsChanged();
564   }
565
566   ~Patch()
567   {
568     BezierCurveTreeArray_deleteAll(m_tess.m_curveTreeU);
569     BezierCurveTreeArray_deleteAll(m_tess.m_curveTreeV);
570
571     releaseShader();
572
573     ASSERT_MESSAGE(m_observers.empty(), "Patch::~Patch: observers still attached");
574   }
575
576   InstanceCounter m_instanceCounter;
577   void instanceAttach(const scene::Path& path)
578   {
579     if(++m_instanceCounter.m_count == 1)
580     {
581       m_state->incrementUsed();
582       m_map = path_find_mapfile(path.begin(), path.end());
583       m_undoable_observer = GlobalUndoSystem().observer(this);
584       GlobalFilterSystem().registerFilterable(*this);
585     }
586     else
587     {
588       ASSERT_MESSAGE(path_find_mapfile(path.begin(), path.end()) == m_map, "node is instanced across more than one file");
589     }
590   }
591   void instanceDetach(const scene::Path& path)
592   {
593     if(--m_instanceCounter.m_count == 0)
594     {
595       m_map = 0;
596       m_undoable_observer = 0;
597       GlobalUndoSystem().release(this);
598       GlobalFilterSystem().unregisterFilterable(*this);
599       m_state->decrementUsed();
600     }
601   }
602
603   const char* name() const
604   {
605     return "patch";
606   }
607   void attach(const NameCallback& callback)
608   {
609   }
610   void detach(const NameCallback& callback)
611   {
612   }
613
614   void attach(Observer* observer)
615   {
616     observer->allocate(m_width * m_height);
617     
618     m_observers.insert(observer);
619   }
620   void detach(Observer* observer)
621   {
622     m_observers.erase(observer);
623   }
624
625   void updateFiltered()
626   {
627     if(m_node != 0)
628     {
629       if(patch_filtered(*this))
630       {
631           m_node->enable(scene::Node::eFiltered);
632       }
633       else
634       {
635         m_node->disable(scene::Node::eFiltered);
636       }
637     }
638   }
639
640   void onAllocate(std::size_t size)
641   {
642     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
643     {
644       (*i)->allocate(size);
645     }
646   }
647  
648   const Matrix4& localToParent() const
649   {
650     return g_matrix4_identity;
651   }
652   const AABB& localAABB() const
653   {
654     return m_aabb_local;
655   }
656   VolumeIntersectionValue intersectVolume(const VolumeTest& test, const Matrix4& localToWorld) const
657   {
658     return test.TestAABB(m_aabb_local, localToWorld);
659   }
660   void render_solid(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
661   {
662     renderer.SetState(m_state, Renderer::eFullMaterials);
663     renderer.addRenderable(m_render_solid, localToWorld);
664   }
665   void render_wireframe(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
666   {
667     renderer.SetState(m_state, Renderer::eFullMaterials);
668     if(m_patchDef3)
669     {
670       renderer.addRenderable(m_render_wireframe_fixed, localToWorld);
671     }
672     else
673     {
674       renderer.addRenderable(m_render_wireframe, localToWorld);
675     }
676   }
677
678   void render_component(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
679   {
680     renderer.SetState(m_state_lattice, Renderer::eWireframeOnly);
681     renderer.SetState(m_state_lattice, Renderer::eFullMaterials);
682     renderer.addRenderable(m_render_lattice, localToWorld);
683
684     renderer.SetState(m_state_ctrl, Renderer::eWireframeOnly);
685     renderer.SetState(m_state_ctrl, Renderer::eFullMaterials);
686     renderer.addRenderable(m_render_ctrl, localToWorld);
687   }
688   void testSelect(Selector& selector, SelectionTest& test)
689   {
690     SelectionIntersection best;
691     IndexPointer::index_type* pIndex = m_tess.m_indices.data();
692     for(std::size_t s=0; s<m_tess.m_numStrips; s++)
693     {
694       test.TestQuadStrip(vertexpointer_arbitrarymeshvertex(m_tess.m_vertices.data()), IndexPointer(pIndex, m_tess.m_lenStrips), best);
695       pIndex += m_tess.m_lenStrips;
696     }
697     if(best.valid())
698     {
699       selector.addIntersection(best);
700     }
701   }
702   void transform(const Matrix4& matrix)
703   {
704     for(PatchControlIter i = m_ctrlTransformed.data(); i != m_ctrlTransformed.data() + m_ctrlTransformed.size(); ++i)
705     {
706       matrix4_transform_point(matrix, (*i).m_vertex);
707     }
708
709     if(matrix4_handedness(matrix) == MATRIX4_LEFTHANDED)
710     {
711       PatchControlArray_invert(m_ctrlTransformed, m_width, m_height);
712     }
713     UpdateCachedData();
714   }
715   void transformChanged()
716   {
717     m_transformChanged = true;
718     m_lightsChanged();
719     SceneChangeNotify();
720   }
721   typedef MemberCaller<Patch, &Patch::transformChanged> TransformChangedCaller;
722
723   void evaluateTransform()
724   {
725     if(m_transformChanged)
726     {
727       m_transformChanged = false;
728       revertTransform();
729       m_evaluateTransform();
730     }
731   }
732
733   void revertTransform()
734   {
735     m_ctrlTransformed = m_ctrl;
736   }
737   void freezeTransform()
738   {
739     undoSave();
740     evaluateTransform();
741     ASSERT_MESSAGE(m_ctrlTransformed.size() == m_ctrl.size(), "Patch::freeze: size mismatch");
742     std::copy(m_ctrlTransformed.begin(), m_ctrlTransformed.end(), m_ctrl.begin());
743   }
744
745   void controlPointsChanged()
746   {
747     transformChanged();
748     evaluateTransform();
749     UpdateCachedData();
750   }
751   bool isValid() const;
752
753   void snapto(float snap)
754   {
755     undoSave();
756
757     for(PatchControlIter i = m_ctrl.data(); i != m_ctrl.data() + m_ctrl.size(); ++i)
758     {
759       vector3_snap((*i).m_vertex, snap);
760     }
761
762     controlPointsChanged();
763   }
764
765
766
767
768   void RenderDebug(RenderStateFlags state) const;
769   void RenderNormals(RenderStateFlags state) const;
770
771   void pushElement(const XMLElement& element)
772   {
773     switch(m_xml_state.back().state())
774     {
775     case xml_state_t::eDefault:
776       ASSERT_MESSAGE(string_equal(element.name(), "patch"), "parse error");
777       m_xml_state.push_back(xml_state_t::ePatch);
778       break;
779     case xml_state_t::ePatch:
780       if(string_equal(element.name(), "matrix"))
781       {
782         setDims(atoi(element.attribute("width")), atoi(element.attribute("height")));
783         m_xml_state.push_back(xml_state_t::eMatrix);
784       }
785       else if(string_equal(element.name(), "shader"))
786       {
787         m_xml_state.push_back(xml_state_t::eShader);
788       }
789       break;
790     default:
791       ERROR_MESSAGE("parse error");
792     }
793
794   }
795   void popElement(const char* name)
796   {
797     switch(m_xml_state.back().state())
798     {
799     case xml_state_t::eDefault:
800       ERROR_MESSAGE("parse error");
801       break;
802     case xml_state_t::ePatch:
803       break;
804     case xml_state_t::eMatrix:
805       {
806         StringTokeniser content(m_xml_state.back().content());
807
808         for(PatchControlIter i = m_ctrl.data(), end = m_ctrl.data() + m_ctrl.size(); i != end; ++i)
809         {
810           (*i).m_vertex[0] = string_read_float(content.getToken());
811           (*i).m_vertex[1] = string_read_float(content.getToken());
812           (*i).m_vertex[2] = string_read_float(content.getToken());
813           (*i).m_texcoord[0] = string_read_float(content.getToken());
814           (*i).m_texcoord[1] = string_read_float(content.getToken());
815         }
816         controlPointsChanged();
817       }
818       break;
819     case xml_state_t::eShader:
820       {
821         SetShader(m_xml_state.back().content());
822       }
823       break;
824     default:
825       ERROR_MESSAGE("parse error");
826     }
827
828     ASSERT_MESSAGE(!m_xml_state.empty(), "popping empty stack");
829     m_xml_state.pop_back();
830   }
831   std::size_t write(const char* buffer, std::size_t length)
832   {
833     switch(m_xml_state.back().state())
834     {
835     case xml_state_t::eDefault:
836       break;
837     case xml_state_t::ePatch:
838       break;
839     case xml_state_t::eMatrix:
840     case xml_state_t::eShader:
841       return m_xml_state.back().write(buffer, length);
842       break;
843     default:
844       ERROR_MESSAGE("parse error");
845     }
846     return length;
847   }
848
849   void exportXML(XMLImporter& importer)
850   {
851     StaticElement patchElement("patch");
852     importer.pushElement(patchElement);
853
854     {
855       const StaticElement element("shader");
856       importer.pushElement(element);
857       importer.write(m_shader.c_str(), strlen(m_shader.c_str()));
858       importer.popElement(element.name());
859     }
860
861     {
862       char width[16], height[16];
863       sprintf(width, "%u", Unsigned(m_width));
864       sprintf(height, "%u", Unsigned(m_height));
865       StaticElement element("matrix");
866       element.insertAttribute("width", width);
867       element.insertAttribute("height", height);
868
869       importer.pushElement(element);
870       {
871         for(PatchControlIter i = m_ctrl.data(), end = m_ctrl.data() + m_ctrl.size(); i != end; ++i)
872         {
873           importer << (*i).m_vertex[0]
874             << ' ' << (*i).m_vertex[1]
875             << ' ' << (*i).m_vertex[2]
876             << ' ' << (*i).m_texcoord[0]
877             << ' ' << (*i).m_texcoord[1];
878         }
879       }
880       importer.popElement(element.name());
881     }
882
883     importer.popElement(patchElement.name());
884   }
885
886   void UpdateCachedData();
887
888   const char *GetShader() const
889   {
890     return m_shader.c_str();
891   }
892   void SetShader(const char* name)
893   {
894     ASSERT_NOTNULL(name);
895   
896     if(shader_equal(m_shader.c_str(), name))
897       return;
898
899     undoSave();
900
901     if(m_instanceCounter.m_count != 0)
902     {
903       m_state->decrementUsed();
904     }
905     releaseShader();
906     m_shader = name;
907     captureShader();
908     if(m_instanceCounter.m_count != 0)
909     {
910       m_state->incrementUsed();
911     }
912
913     check_shader();
914     Patch_textureChanged();
915   }
916   int getShaderFlags() const
917   {
918     if(m_state != 0)
919     {
920       return m_state->getFlags();
921     }
922     return 0;
923   }
924
925   typedef PatchControl* iterator;
926   typedef const PatchControl* const_iterator;
927
928   iterator begin()
929   {
930     return m_ctrl.data();
931   }
932   const_iterator begin() const
933   {
934     return m_ctrl.data();
935   }
936   iterator end()
937   {
938     return m_ctrl.data() + m_ctrl.size();
939   }
940   const_iterator end() const
941   {
942     return m_ctrl.data() + m_ctrl.size();
943   }
944
945   PatchControlArray& getControlPoints()
946   {
947     return m_ctrl;
948   }
949   PatchControlArray& getControlPointsTransformed()
950   {
951     return m_ctrlTransformed;
952   }
953
954   void setDims (std::size_t w, std::size_t h);
955   std::size_t getWidth() const
956   {
957     return m_width;
958   }
959   std::size_t getHeight() const
960   {
961     return m_height;
962   }
963   PatchControl& ctrlAt(std::size_t row, std::size_t col)
964   {
965     return m_ctrl[row*m_width+col];
966   } 
967   const PatchControl& ctrlAt(std::size_t row, std::size_t col) const
968   {
969     return m_ctrl[row*m_width+col];
970   } 
971  
972   void ConstructPrefab(const AABB& aabb, EPatchPrefab eType, int axis, std::size_t width = 3, std::size_t height = 3);
973   void constructPlane(const AABB& aabb, int axis, std::size_t width, std::size_t height);
974   void InvertMatrix();
975   void TransposeMatrix();
976   void Redisperse(EMatrixMajor mt);
977   void Smooth(EMatrixMajor mt);
978   void InsertRemove(bool bInsert, bool bColumn, bool bFirst);
979   Patch* MakeCap(Patch* patch, EPatchCap eType, EMatrixMajor mt, bool bFirst);
980   void ConstructSeam(EPatchCap eType, Vector3* p, std::size_t width);
981   
982   void FlipTexture(int nAxis);
983   void TranslateTexture(float s, float t);
984   void ScaleTexture(float s, float t);
985   void RotateTexture(float angle);
986   void SetTextureRepeat(float s, float t); // call with s=1 t=1 for FIT
987   void CapTexture();
988   void NaturalTexture();
989   void ProjectTexture(int nAxis);
990  
991   void undoSave()
992   {
993     if(m_map != 0)
994     {
995       m_map->changed();
996     }
997     if(m_undoable_observer != 0)
998     {
999       m_undoable_observer->save(this);
1000     }
1001   }
1002
1003   UndoMemento* exportState() const
1004   {
1005     return new SavedState(m_width, m_height, m_ctrl, m_shader.c_str(), m_patchDef3, m_subdivisions_x, m_subdivisions_y);
1006   }
1007   void importState(const UndoMemento* state)
1008   {
1009     undoSave();
1010
1011     const SavedState& other = *(static_cast<const SavedState*>(state));
1012
1013     // begin duplicate of SavedState copy constructor, needs refactoring
1014
1015     // copy construct
1016     {
1017       m_width = other.m_width;
1018       m_height = other.m_height;
1019       SetShader(other.m_shader.c_str());
1020       m_ctrl = other.m_ctrl;
1021       onAllocate(m_ctrl.size());
1022       m_patchDef3 = other.m_patchDef3;
1023       m_subdivisions_x = other.m_subdivisions_x;
1024       m_subdivisions_y = other.m_subdivisions_y;
1025     }
1026
1027     // end duplicate code
1028
1029     Patch_textureChanged();
1030
1031     controlPointsChanged();
1032   }
1033
1034   static void constructStatic(EPatchType type)
1035   {
1036     Patch::m_type = type;
1037     Patch::m_state_ctrl = GlobalShaderCache().capture("$POINT");
1038     Patch::m_state_lattice = GlobalShaderCache().capture("$LATTICE");
1039   }
1040
1041   static void destroyStatic()
1042   {
1043     GlobalShaderCache().release("$LATTICE");
1044     GlobalShaderCache().release("$POINT");
1045   }
1046 private:
1047   void captureShader()
1048   {
1049     m_state = GlobalShaderCache().capture(m_shader.c_str());
1050   }
1051
1052   void releaseShader()
1053   {
1054     GlobalShaderCache().release(m_shader.c_str());
1055   }
1056
1057   void check_shader()
1058   {
1059     if(!shader_valid(GetShader()))
1060     {
1061       globalErrorStream() << "patch has invalid texture name: '" << GetShader() << "'\n";
1062     }
1063   }
1064
1065   void InsertPoints(EMatrixMajor mt, bool bFirst);
1066   void RemovePoints(EMatrixMajor mt, bool bFirst);
1067   
1068   void AccumulateBBox();
1069   
1070   void TesselateSubMatrixFixed(ArbitraryMeshVertex* vertices, std::size_t strideX, std::size_t strideY, unsigned int nFlagsX, unsigned int nFlagsY, PatchControl* subMatrix[3][3]);
1071
1072   // uses binary trees representing bezier curves to recursively tesselate a bezier sub-patch
1073   void TesselateSubMatrix( const BezierCurveTree *BX, const BezierCurveTree *BY,
1074                            std::size_t offStartX, std::size_t offStartY,
1075                            std::size_t offEndX, std::size_t offEndY,
1076                            std::size_t nFlagsX, std::size_t nFlagsY,
1077                            Vector3& left, Vector3& mid, Vector3& right,
1078                            Vector2& texLeft, Vector2& texMid, Vector2& texRight,
1079                            bool bTranspose );
1080   
1081   // tesselates the entire surface
1082   void BuildTesselationCurves(EMatrixMajor major);
1083   void accumulateVertexTangentSpace(std::size_t index, Vector3 tangentX[6], Vector3 tangentY[6], Vector2 tangentS[6], Vector2 tangentT[6], std::size_t index0, std::size_t index1);
1084   void BuildVertexArray();
1085 };
1086
1087 inline bool Patch_importHeader(Patch& patch, Tokeniser& tokeniser)
1088 {
1089   tokeniser.nextLine();
1090   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "{"));
1091   return true;
1092 }
1093
1094 inline bool Patch_importShader(Patch& patch, Tokeniser& tokeniser)
1095 {
1096   // parse shader name
1097   tokeniser.nextLine();
1098   const char* texture = tokeniser.getToken();
1099   if(texture == 0)
1100   {
1101     Tokeniser_unexpectedError(tokeniser, texture, "#texture-name");
1102     return false;
1103   }
1104   if(string_equal(texture, "NULL"))
1105   {
1106     patch.SetShader(texdef_name_default());
1107   }
1108   else
1109   {
1110     StringOutputStream shader(string_length(GlobalTexturePrefix_get()) + string_length(texture));
1111     shader << GlobalTexturePrefix_get() << texture;
1112     patch.SetShader(shader.c_str());
1113   }
1114   return true;
1115 }
1116
1117 inline bool PatchDoom3_importShader(Patch& patch, Tokeniser& tokeniser)
1118 {
1119   // parse shader name
1120   tokeniser.nextLine();
1121   const char *shader = tokeniser.getToken();
1122   if(shader == 0)
1123   {
1124     Tokeniser_unexpectedError(tokeniser, shader, "#shader-name");
1125     return false;
1126   }
1127   if(string_equal(shader, "_emptyname"))
1128   {
1129     shader = texdef_name_default();
1130   }
1131   patch.SetShader(shader);
1132   return true;
1133 }
1134
1135 inline bool Patch_importParams(Patch& patch, Tokeniser& tokeniser)
1136 {
1137   tokeniser.nextLine();
1138   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "("));
1139
1140   // parse matrix dimensions
1141   {
1142     std::size_t c, r;
1143     RETURN_FALSE_IF_FAIL(Tokeniser_getSize(tokeniser, c));
1144     RETURN_FALSE_IF_FAIL(Tokeniser_getSize(tokeniser, r));
1145
1146     patch.setDims(c, r);
1147   }
1148
1149   if(patch.m_patchDef3)
1150   {
1151     RETURN_FALSE_IF_FAIL(Tokeniser_getSize(tokeniser, patch.m_subdivisions_x));
1152     RETURN_FALSE_IF_FAIL(Tokeniser_getSize(tokeniser, patch.m_subdivisions_y));
1153   }
1154
1155   // ignore contents/flags/value
1156   int tmp;
1157   RETURN_FALSE_IF_FAIL(Tokeniser_getInteger(tokeniser, tmp));
1158   RETURN_FALSE_IF_FAIL(Tokeniser_getInteger(tokeniser, tmp));
1159   RETURN_FALSE_IF_FAIL(Tokeniser_getInteger(tokeniser, tmp));
1160
1161   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, ")"));
1162   return true;
1163 }
1164
1165 inline bool Patch_importMatrix(Patch& patch, Tokeniser& tokeniser)
1166 {
1167   // parse matrix
1168   tokeniser.nextLine();
1169   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "("));
1170   {
1171     for(std::size_t c=0; c<patch.getWidth(); c++)
1172     {
1173       tokeniser.nextLine();
1174       RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "("));
1175       for(std::size_t r=0; r<patch.getHeight(); r++)
1176       {
1177         RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "("));
1178     
1179         RETURN_FALSE_IF_FAIL(Tokeniser_getFloat(tokeniser, patch.ctrlAt(r,c).m_vertex[0]));
1180         RETURN_FALSE_IF_FAIL(Tokeniser_getFloat(tokeniser, patch.ctrlAt(r,c).m_vertex[1]));
1181         RETURN_FALSE_IF_FAIL(Tokeniser_getFloat(tokeniser, patch.ctrlAt(r,c).m_vertex[2]));
1182         RETURN_FALSE_IF_FAIL(Tokeniser_getFloat(tokeniser, patch.ctrlAt(r,c).m_texcoord[0]));
1183         RETURN_FALSE_IF_FAIL(Tokeniser_getFloat(tokeniser, patch.ctrlAt(r,c).m_texcoord[1]));
1184
1185         RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, ")"));
1186       }
1187       RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, ")"));
1188     }
1189   }
1190   tokeniser.nextLine();
1191   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, ")"));
1192   return true;
1193 }
1194
1195 inline bool Patch_importFooter(Patch& patch, Tokeniser& tokeniser)
1196 {
1197   patch.controlPointsChanged();
1198
1199   tokeniser.nextLine();
1200   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "}"));
1201
1202   tokeniser.nextLine();
1203   RETURN_FALSE_IF_FAIL(Tokeniser_parseToken(tokeniser, "}"));
1204   return true;
1205 }
1206
1207 class PatchTokenImporter : public MapImporter
1208 {
1209   Patch& m_patch;
1210 public:
1211   PatchTokenImporter(Patch& patch) : m_patch(patch)
1212   {
1213   }
1214   bool importTokens(Tokeniser& tokeniser)
1215   {
1216     RETURN_FALSE_IF_FAIL(Patch_importHeader(m_patch, tokeniser));
1217     RETURN_FALSE_IF_FAIL(Patch_importShader(m_patch, tokeniser));
1218     RETURN_FALSE_IF_FAIL(Patch_importParams(m_patch, tokeniser));
1219     RETURN_FALSE_IF_FAIL(Patch_importMatrix(m_patch, tokeniser));
1220     RETURN_FALSE_IF_FAIL(Patch_importFooter(m_patch, tokeniser));
1221
1222     return true;
1223   }
1224 };
1225
1226 class PatchDoom3TokenImporter : public MapImporter
1227 {
1228   Patch& m_patch;
1229 public:
1230   PatchDoom3TokenImporter(Patch& patch) : m_patch(patch)
1231   {
1232   }
1233   bool importTokens(Tokeniser& tokeniser)
1234   {
1235     RETURN_FALSE_IF_FAIL(Patch_importHeader(m_patch, tokeniser));
1236     RETURN_FALSE_IF_FAIL(PatchDoom3_importShader(m_patch, tokeniser));
1237     RETURN_FALSE_IF_FAIL(Patch_importParams(m_patch, tokeniser));
1238     RETURN_FALSE_IF_FAIL(Patch_importMatrix(m_patch, tokeniser));
1239     RETURN_FALSE_IF_FAIL(Patch_importFooter(m_patch, tokeniser));
1240
1241     return true;
1242   }
1243 };
1244
1245 inline void Patch_exportHeader(const Patch& patch, TokenWriter& writer)
1246 {
1247   writer.writeToken("{");
1248   writer.nextLine();
1249   writer.writeToken(patch.m_patchDef3 ? "patchDef3" : "patchDef2");
1250   writer.nextLine();
1251   writer.writeToken("{");
1252   writer.nextLine();
1253 }
1254
1255 inline void Patch_exportShader(const Patch& patch, TokenWriter& writer)
1256 {
1257   // write shader name
1258   if(*(shader_get_textureName(patch.GetShader())) == '\0')
1259   {
1260     writer.writeToken("NULL");
1261   }
1262   else
1263   {
1264     writer.writeToken(shader_get_textureName(patch.GetShader()));
1265   }
1266   writer.nextLine();
1267 }
1268
1269 inline void PatchDoom3_exportShader(const Patch& patch, TokenWriter& writer)
1270 {
1271   // write shader name
1272   if(*(shader_get_textureName(patch.GetShader())) == '\0')
1273   {
1274     writer.writeString("_emptyname");
1275   }
1276   else
1277   {
1278     writer.writeString(patch.GetShader());
1279   }
1280   writer.nextLine();
1281 }
1282
1283 inline void Patch_exportParams(const Patch& patch, TokenWriter& writer)
1284 {
1285   // write matrix dimensions
1286   writer.writeToken("(");
1287   writer.writeUnsigned(patch.getWidth());
1288   writer.writeUnsigned(patch.getHeight());
1289   if(patch.m_patchDef3)
1290   {
1291     writer.writeUnsigned(patch.m_subdivisions_x);
1292     writer.writeUnsigned(patch.m_subdivisions_y);
1293   }
1294   writer.writeInteger(0);
1295   writer.writeInteger(0);
1296   writer.writeInteger(0);
1297   writer.writeToken(")");
1298   writer.nextLine();
1299 }
1300
1301 inline void Patch_exportMatrix(const Patch& patch, TokenWriter& writer)
1302 {
1303   // write matrix
1304   writer.writeToken("(");
1305   writer.nextLine();
1306   for(std::size_t c=0; c<patch.getWidth(); c++)
1307   {
1308     writer.writeToken("(");
1309     for(std::size_t r=0; r<patch.getHeight(); r++)
1310     {
1311       writer.writeToken("(");
1312
1313       writer.writeFloat(patch.ctrlAt(r,c).m_vertex[0]);
1314       writer.writeFloat(patch.ctrlAt(r,c).m_vertex[1]);
1315       writer.writeFloat(patch.ctrlAt(r,c).m_vertex[2]);
1316       writer.writeFloat(patch.ctrlAt(r,c).m_texcoord[0]);
1317       writer.writeFloat(patch.ctrlAt(r,c).m_texcoord[1]);
1318
1319       writer.writeToken(")");
1320     }
1321     writer.writeToken(")");
1322     writer.nextLine();
1323   }
1324   writer.writeToken(")");
1325   writer.nextLine();
1326 }
1327   
1328 inline void Patch_exportFooter(const Patch& patch, TokenWriter& writer)
1329 {
1330   writer.writeToken("}");
1331   writer.nextLine();
1332   writer.writeToken("}");
1333   writer.nextLine();
1334 }
1335
1336 class PatchTokenExporter : public MapExporter
1337 {
1338   const Patch& m_patch;
1339 public:
1340   PatchTokenExporter(Patch& patch) : m_patch(patch)
1341   {
1342   }
1343   void exportTokens(TokenWriter& writer) const
1344   {
1345     Patch_exportHeader(m_patch, writer);
1346     Patch_exportShader(m_patch, writer);
1347     Patch_exportParams(m_patch, writer);
1348     Patch_exportMatrix(m_patch, writer);
1349     Patch_exportFooter(m_patch, writer);
1350   }
1351 };
1352
1353 class PatchDoom3TokenExporter : public MapExporter
1354 {
1355   const Patch& m_patch;
1356 public:
1357   PatchDoom3TokenExporter(Patch& patch) : m_patch(patch)
1358   {
1359   }
1360   void exportTokens(TokenWriter& writer) const
1361   {
1362     Patch_exportHeader(m_patch, writer);
1363     PatchDoom3_exportShader(m_patch, writer);
1364     Patch_exportParams(m_patch, writer);
1365     Patch_exportMatrix(m_patch, writer);
1366     Patch_exportFooter(m_patch, writer);
1367   }
1368 };
1369
1370 class PatchControlInstance
1371 {
1372 public:
1373   PatchControl* m_ctrl;
1374   ObservedSelectable m_selectable;
1375
1376   PatchControlInstance(PatchControl* ctrl, const SelectionChangeCallback& observer)
1377     : m_ctrl(ctrl), m_selectable(observer)
1378   {
1379   }
1380
1381   void testSelect(Selector& selector, SelectionTest& test)
1382   {
1383     SelectionIntersection best;
1384     test.TestPoint(m_ctrl->m_vertex, best);
1385     if(best.valid())
1386     {
1387       Selector_add(selector, m_selectable, best);
1388     }
1389   }
1390   void snapto(float snap)
1391   {
1392     vector3_snap(m_ctrl->m_vertex, snap);
1393   }
1394 };
1395
1396
1397 class PatchInstance :
1398 public Patch::Observer,
1399 public scene::Instance,
1400 public Selectable,
1401 public Renderable,
1402 public SelectionTestable,
1403 public ComponentSelectionTestable,
1404 public ComponentEditable,
1405 public ComponentSnappable,
1406 public PlaneSelectable,
1407 public LightCullable
1408 {
1409   class TypeCasts
1410   {
1411     InstanceTypeCastTable m_casts;
1412   public:
1413     TypeCasts()
1414     {
1415       InstanceStaticCast<PatchInstance, Selectable>::install(m_casts);
1416       InstanceContainedCast<PatchInstance, Bounded>::install(m_casts);
1417       InstanceContainedCast<PatchInstance, Cullable>::install(m_casts);
1418       InstanceStaticCast<PatchInstance, Renderable>::install(m_casts);
1419       InstanceStaticCast<PatchInstance, SelectionTestable>::install(m_casts);
1420       InstanceStaticCast<PatchInstance, ComponentSelectionTestable>::install(m_casts);
1421       InstanceStaticCast<PatchInstance, ComponentEditable>::install(m_casts);
1422       InstanceStaticCast<PatchInstance, ComponentSnappable>::install(m_casts);
1423       InstanceStaticCast<PatchInstance, PlaneSelectable>::install(m_casts);
1424       InstanceIdentityCast<PatchInstance>::install(m_casts);
1425       InstanceContainedCast<PatchInstance, Transformable>::install(m_casts);
1426     }
1427     InstanceTypeCastTable& get()
1428     {
1429       return m_casts;
1430     }
1431   };
1432
1433
1434   Patch& m_patch;
1435   typedef std::vector<PatchControlInstance> PatchControlInstances;
1436   PatchControlInstances m_ctrl_instances;
1437
1438   ObservedSelectable m_selectable;
1439
1440   DragPlanes m_dragPlanes;
1441
1442   mutable RenderablePointVector m_render_selected;
1443   mutable AABB m_aabb_component;
1444
1445   static Shader* m_state_selpoint;
1446
1447   const LightList* m_lightList;
1448
1449   TransformModifier m_transform;
1450 public:
1451
1452   typedef LazyStatic<TypeCasts> StaticTypeCasts;
1453
1454   void lightsChanged()
1455   {
1456     m_lightList->lightsChanged();
1457   }
1458   typedef MemberCaller<PatchInstance, &PatchInstance::lightsChanged> LightsChangedCaller;
1459
1460   STRING_CONSTANT(Name, "PatchInstance");
1461
1462   PatchInstance(const scene::Path& path, scene::Instance* parent, Patch& patch) :
1463     Instance(path, parent, this, StaticTypeCasts::instance().get()),
1464     m_patch(patch),
1465     m_selectable(SelectedChangedCaller(*this)),
1466     m_dragPlanes(SelectedChangedComponentCaller(*this)),
1467     m_render_selected(GL_POINTS),
1468     m_transform(Patch::TransformChangedCaller(m_patch), ApplyTransformCaller(*this))
1469   {
1470     m_patch.instanceAttach(Instance::path());
1471     m_patch.attach(this);
1472
1473     m_lightList = &GlobalShaderCache().attach(*this);
1474     m_patch.m_lightsChanged = LightsChangedCaller(*this);
1475
1476     Instance::setTransformChangedCallback(LightsChangedCaller(*this));
1477   }
1478   ~PatchInstance()
1479   {
1480     Instance::setTransformChangedCallback(Callback());
1481
1482     m_patch.m_lightsChanged = Callback();
1483     GlobalShaderCache().detach(*this);
1484
1485     m_patch.detach(this);
1486     m_patch.instanceDetach(Instance::path());
1487   }
1488
1489   void selectedChanged(const Selectable& selectable)
1490   {
1491     GlobalSelectionSystem().getObserver(SelectionSystem::ePrimitive)(selectable);
1492     GlobalSelectionSystem().onSelectedChanged(*this, selectable);
1493
1494     Instance::selectedChanged();
1495   }
1496   typedef MemberCaller1<PatchInstance, const Selectable&, &PatchInstance::selectedChanged> SelectedChangedCaller;
1497
1498   void selectedChangedComponent(const Selectable& selectable)
1499   {
1500     GlobalSelectionSystem().getObserver(SelectionSystem::eComponent)(selectable);
1501     GlobalSelectionSystem().onComponentSelection(*this, selectable);
1502   }
1503   typedef MemberCaller1<PatchInstance, const Selectable&, &PatchInstance::selectedChangedComponent> SelectedChangedComponentCaller;
1504
1505   Patch& getPatch()
1506   {
1507     return m_patch;
1508   }
1509   Bounded& get(NullType<Bounded>)
1510   {
1511     return m_patch;
1512   }
1513   Cullable& get(NullType<Cullable>)
1514   {
1515     return m_patch;
1516   }
1517   Transformable& get(NullType<Transformable>)
1518   {
1519     return m_transform;
1520   }
1521
1522   static void constructStatic()
1523   {
1524     m_state_selpoint = GlobalShaderCache().capture("$SELPOINT");
1525   }
1526
1527   static void destroyStatic()
1528   {
1529     GlobalShaderCache().release("$SELPOINT");
1530   }
1531
1532
1533   void allocate(std::size_t size)
1534   {
1535     m_ctrl_instances.clear();
1536     m_ctrl_instances.reserve(size);
1537     for(Patch::iterator i = m_patch.begin(); i != m_patch.end(); ++i)
1538     {
1539       m_ctrl_instances.push_back(PatchControlInstance(&(*i), SelectedChangedComponentCaller(*this)));
1540     }
1541   }
1542
1543   void setSelected(bool select)
1544   {
1545     m_selectable.setSelected(select);
1546   }
1547   bool isSelected() const
1548   {
1549     return m_selectable.isSelected();
1550   }
1551
1552
1553   void update_selected() const
1554   {
1555     m_render_selected.clear();
1556     Patch::iterator ctrl = m_patch.getControlPointsTransformed().begin();
1557     for(PatchControlInstances::const_iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i, ++ctrl)
1558     {
1559       if((*i).m_selectable.isSelected())
1560       {
1561         const Colour4b colour_selected(0, 0, 255, 255);
1562         m_render_selected.push_back(PointVertex(reinterpret_cast<Vertex3f&>((*ctrl).m_vertex), colour_selected));
1563       }
1564     }
1565   }
1566
1567 #if 0
1568   void render(Renderer& renderer, const VolumeTest& volume) const
1569   {
1570     if(GlobalSelectionSystem().Mode() == SelectionSystem::eComponent
1571       && m_selectable.isSelected())
1572     {
1573       renderer.Highlight(Renderer::eFace, false);
1574
1575       m_patch.render(renderer, volume, localToWorld());
1576
1577       if(GlobalSelectionSystem().ComponentMode() == SelectionSystem::eVertex)
1578       {
1579         renderer.Highlight(Renderer::ePrimitive, false);
1580
1581         m_patch.render_component(renderer, volume, localToWorld());
1582
1583         renderComponentsSelected(renderer, volume);
1584       }
1585     }
1586     else
1587       m_patch.render(renderer, volume, localToWorld());
1588   }
1589 #endif
1590
1591   void renderSolid(Renderer& renderer, const VolumeTest& volume) const
1592   {
1593     m_patch.evaluateTransform();
1594     renderer.setLights(*m_lightList);
1595     m_patch.render_solid(renderer, volume, localToWorld());
1596
1597     renderComponentsSelected(renderer, volume);
1598   }
1599
1600   void renderWireframe(Renderer& renderer, const VolumeTest& volume) const
1601   {
1602     m_patch.evaluateTransform();
1603     m_patch.render_wireframe(renderer, volume, localToWorld());
1604
1605     renderComponentsSelected(renderer, volume);
1606   }
1607
1608   void renderComponentsSelected(Renderer& renderer, const VolumeTest& volume) const
1609   {
1610     m_patch.evaluateTransform();
1611     update_selected();
1612     if(!m_render_selected.empty())
1613     {
1614       renderer.Highlight(Renderer::ePrimitive, false);
1615       renderer.SetState(m_state_selpoint, Renderer::eWireframeOnly);
1616       renderer.SetState(m_state_selpoint, Renderer::eFullMaterials);
1617       renderer.addRenderable(m_render_selected, localToWorld());
1618     }
1619   }
1620   void renderComponents(Renderer& renderer, const VolumeTest& volume) const
1621   {
1622     m_patch.evaluateTransform();
1623     if(GlobalSelectionSystem().ComponentMode() == SelectionSystem::eVertex)
1624     {
1625       m_patch.render_component(renderer, volume, localToWorld());
1626     }
1627   }
1628
1629   void testSelect(Selector& selector, SelectionTest& test)
1630   {
1631     test.BeginMesh(localToWorld(), true);
1632     m_patch.testSelect(selector, test);
1633   }
1634
1635   void selectCtrl(bool select)
1636   {
1637     for(PatchControlInstances::iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i)
1638     {
1639       (*i).m_selectable.setSelected(select);
1640     }
1641   }
1642   bool isSelectedComponents() const
1643   {
1644     for(PatchControlInstances::const_iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i)
1645     {
1646       if((*i).m_selectable.isSelected())
1647       {
1648         return true;
1649       }
1650     }
1651     return false;
1652   }
1653   void setSelectedComponents(bool select, SelectionSystem::EComponentMode mode)
1654   {
1655     if(mode == SelectionSystem::eVertex)
1656     {
1657       selectCtrl(select);
1658     }
1659     else if(mode == SelectionSystem::eFace)
1660     {
1661       m_dragPlanes.setSelected(select);
1662     }
1663   }
1664   const AABB& getSelectedComponentsBounds() const
1665   {
1666     m_aabb_component = AABB();
1667
1668     for(PatchControlInstances::const_iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i)
1669     {
1670       if((*i).m_selectable.isSelected())
1671       {
1672         aabb_extend_by_point_safe(m_aabb_component, (*i).m_ctrl->m_vertex);
1673       }
1674     }
1675
1676     return m_aabb_component;
1677   }
1678
1679   void testSelectComponents(Selector& selector, SelectionTest& test, SelectionSystem::EComponentMode mode)
1680   {
1681     test.BeginMesh(localToWorld());
1682
1683     switch(mode)
1684     {
1685     case SelectionSystem::eVertex:
1686       {
1687         for(PatchControlInstances::iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i)
1688         {
1689           (*i).testSelect(selector, test);
1690         }
1691       }
1692       break;
1693     default:
1694       break;
1695     }
1696   }
1697
1698   bool selectedVertices()
1699   {
1700     for(PatchControlInstances::iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i)
1701     {
1702       if((*i).m_selectable.isSelected())
1703       {
1704         return true;
1705       }
1706     }
1707     return false;
1708   }
1709
1710   void transformComponents(const Matrix4& matrix)
1711   {
1712     if(selectedVertices())
1713     {
1714       PatchControlIter ctrl = m_patch.getControlPointsTransformed().begin();
1715       for(PatchControlInstances::iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i, ++ctrl)
1716       {
1717         if((*i).m_selectable.isSelected())
1718         {
1719           matrix4_transform_point(matrix, (*ctrl).m_vertex);
1720         }
1721       }
1722       m_patch.UpdateCachedData();
1723     }
1724
1725     if(m_dragPlanes.isSelected()) // this should only be true when the transform is a pure translation.
1726     {
1727       m_patch.transform(m_dragPlanes.evaluateTransform(vector4_to_vector3(matrix.t())));
1728     }
1729   }
1730
1731
1732   void selectPlanes(Selector& selector, SelectionTest& test, const PlaneCallback& selectedPlaneCallback)
1733   {
1734     test.BeginMesh(localToWorld());
1735
1736     m_dragPlanes.selectPlanes(m_patch.localAABB(), selector, test, selectedPlaneCallback);
1737   }
1738   void selectReversedPlanes(Selector& selector, const SelectedPlanes& selectedPlanes)
1739   {
1740     m_dragPlanes.selectReversedPlanes(m_patch.localAABB(), selector, selectedPlanes);
1741   }
1742
1743
1744   void snapComponents(float snap)
1745   {
1746     if(selectedVertices())
1747     {
1748       m_patch.undoSave();
1749       for(PatchControlInstances::iterator i = m_ctrl_instances.begin(); i != m_ctrl_instances.end(); ++i)
1750       {
1751         if((*i).m_selectable.isSelected())
1752         {
1753           (*i).snapto(snap);
1754         }
1755       }
1756       m_patch.controlPointsChanged();
1757     }
1758   }
1759
1760   void evaluateTransform()
1761   {
1762     Matrix4 matrix(m_transform.calculateTransform());
1763
1764     if(m_transform.getType() == TRANSFORM_PRIMITIVE)
1765     {
1766       m_patch.transform(matrix);
1767     }
1768     else
1769     {
1770       transformComponents(matrix);
1771     }
1772   }
1773   void applyTransform()
1774   {
1775     m_patch.revertTransform();
1776     evaluateTransform();
1777     m_patch.freezeTransform();
1778   }
1779   typedef MemberCaller<PatchInstance, &PatchInstance::applyTransform> ApplyTransformCaller;
1780
1781
1782   bool testLight(const RendererLight& light) const
1783   {
1784     return light.testAABB(worldAABB());
1785   }
1786 };
1787
1788
1789 template<typename TokenImporter, typename TokenExporter>
1790 class PatchNode :
1791   public scene::Node::Symbiot,
1792   public scene::Instantiable,
1793   public scene::Cloneable
1794 {
1795   typedef PatchNode<TokenImporter, TokenExporter> Self;
1796
1797   class TypeCasts
1798   {
1799     InstanceTypeCastTable m_casts;
1800   public:
1801     TypeCasts()
1802     {
1803       NodeStaticCast<PatchNode, scene::Instantiable>::install(m_casts);
1804       NodeStaticCast<PatchNode, scene::Cloneable>::install(m_casts);
1805       NodeContainedCast<PatchNode, Snappable>::install(m_casts);
1806       NodeContainedCast<PatchNode, TransformNode>::install(m_casts);
1807       NodeContainedCast<PatchNode, Patch>::install(m_casts);
1808       NodeContainedCast<PatchNode, XMLImporter>::install(m_casts);
1809       NodeContainedCast<PatchNode, XMLExporter>::install(m_casts);
1810       NodeContainedCast<PatchNode, MapImporter>::install(m_casts);
1811       NodeContainedCast<PatchNode, MapExporter>::install(m_casts);
1812       NodeContainedCast<PatchNode, Nameable>::install(m_casts);
1813     }
1814     InstanceTypeCastTable& get()
1815     {
1816       return m_casts;
1817     }
1818   };
1819
1820
1821   scene::Node m_node;
1822   InstanceSet m_instances;
1823   Patch m_patch;
1824   TokenImporter m_importMap;
1825   TokenExporter m_exportMap;
1826
1827 public:
1828
1829   typedef LazyStatic<TypeCasts> StaticTypeCasts;
1830
1831   Snappable& get(NullType<Snappable>)
1832   {
1833     return m_patch;
1834   }
1835   TransformNode& get(NullType<TransformNode>)
1836   {
1837     return m_patch;
1838   }
1839   Patch& get(NullType<Patch>)
1840   {
1841     return m_patch;
1842   }
1843   XMLImporter& get(NullType<XMLImporter>)
1844   {
1845     return m_patch;
1846   }
1847   XMLExporter& get(NullType<XMLExporter>)
1848   {
1849     return m_patch;
1850   }
1851   MapImporter& get(NullType<MapImporter>)
1852   {
1853     return m_importMap;
1854   }
1855   MapExporter& get(NullType<MapExporter>)
1856   {
1857     return m_exportMap;
1858   }
1859   Nameable& get(NullType<Nameable>)
1860   {
1861     return m_patch;
1862   }
1863
1864   PatchNode(bool patchDef3 = false) :
1865     m_node(this, this, StaticTypeCasts::instance().get()),
1866     m_patch(m_node, InstanceSetEvaluateTransform<PatchInstance>::Caller(m_instances), InstanceSet::BoundsChangedCaller(m_instances)),
1867     m_importMap(m_patch),
1868     m_exportMap(m_patch)
1869   {
1870     m_patch.m_patchDef3 = patchDef3;
1871   }
1872   PatchNode(const PatchNode& other) :
1873     scene::Node::Symbiot(other),
1874     scene::Instantiable(other),
1875     scene::Cloneable(other),
1876     m_node(this, this, StaticTypeCasts::instance().get()),
1877     m_patch(other.m_patch, m_node, InstanceSetEvaluateTransform<PatchInstance>::Caller(m_instances), InstanceSet::BoundsChangedCaller(m_instances)),
1878     m_importMap(m_patch),
1879     m_exportMap(m_patch)
1880   {
1881   }
1882   void release()
1883   {
1884     delete this;
1885   }
1886   scene::Node& node()
1887   {
1888     return m_node;
1889   }
1890   Patch& get()
1891   {
1892     return m_patch;
1893   }
1894   const Patch& get() const
1895   {
1896     return m_patch;
1897   }
1898   
1899   scene::Node& clone() const
1900   {
1901     return (new PatchNode(*this))->node();
1902   }
1903
1904   scene::Instance* create(const scene::Path& path, scene::Instance* parent)
1905   {
1906     return new PatchInstance(path, parent, m_patch);
1907   }
1908   void forEachInstance(const scene::Instantiable::Visitor& visitor)
1909   {
1910     m_instances.forEachInstance(visitor);
1911   }
1912   void insert(scene::Instantiable::Observer* observer, const scene::Path& path, scene::Instance* instance)
1913   {
1914     m_instances.insert(observer, path, instance);
1915   }
1916   scene::Instance* erase(scene::Instantiable::Observer* observer, const scene::Path& path)
1917   {
1918     return m_instances.erase(observer, path);
1919   }
1920 };
1921
1922
1923
1924 typedef PatchNode<PatchTokenImporter, PatchTokenExporter> PatchNodeQuake3;
1925 typedef PatchNode<PatchDoom3TokenImporter, PatchDoom3TokenExporter> PatchNodeDoom3;
1926
1927 inline Patch* Node_getPatch(scene::Node& node)
1928 {
1929   return NodeTypeCast<Patch>::cast(node);
1930 }
1931
1932 inline PatchInstance* Instance_getPatch(scene::Instance& instance)
1933 {
1934   return InstanceTypeCast<PatchInstance>::cast(instance);
1935 }
1936
1937 template<typename Functor>
1938 class PatchSelectedVisitor : public SelectionSystem::Visitor
1939 {
1940   const Functor& m_functor;
1941 public:
1942   PatchSelectedVisitor(const Functor& functor) : m_functor(functor)
1943   {
1944   }
1945   void visit(scene::Instance& instance) const
1946   {
1947     PatchInstance* patch = Instance_getPatch(instance);
1948     if(patch != 0)
1949     {
1950       m_functor(*patch);
1951     }
1952   }
1953 };
1954
1955 template<typename Functor>
1956 inline void Scene_forEachSelectedPatch(const Functor& functor)
1957 {
1958   GlobalSelectionSystem().foreachSelected(PatchSelectedVisitor<Functor>(functor));
1959 }
1960
1961
1962 template<typename Functor>
1963 class PatchVisibleSelectedVisitor : public SelectionSystem::Visitor
1964 {
1965   const Functor& m_functor;
1966 public:
1967   PatchVisibleSelectedVisitor(const Functor& functor) : m_functor(functor)
1968   {
1969   }
1970   void visit(scene::Instance& instance) const
1971   {
1972     PatchInstance* patch = Instance_getPatch(instance);
1973     if(patch != 0
1974       && instance.path().top().get().visible())
1975     {
1976       m_functor(*patch);
1977     }
1978   }
1979 };
1980
1981 template<typename Functor>
1982 inline void Scene_forEachVisibleSelectedPatchInstance(const Functor& functor)
1983 {
1984   GlobalSelectionSystem().foreachSelected(PatchVisibleSelectedVisitor<Functor>(functor));
1985 }
1986
1987 template<typename Functor>
1988 class PatchForEachWalker : public scene::Graph::Walker
1989 {
1990   const Functor& m_functor;
1991 public:
1992   PatchForEachWalker(const Functor& functor) : m_functor(functor)
1993   {
1994   }
1995   bool pre(const scene::Path& path, scene::Instance& instance) const
1996   {
1997     if(path.top().get().visible())
1998     {
1999       Patch* patch = Node_getPatch(path.top());
2000       if(patch != 0)
2001       {
2002         m_functor(*patch);
2003       }
2004     }
2005     return true;
2006   }
2007 };
2008
2009 template<typename Functor>
2010 inline void Scene_forEachVisiblePatch(const Functor& functor)
2011 {
2012   GlobalSceneGraph().traverse(PatchForEachWalker<Functor>(functor));
2013 }
2014
2015 template<typename Functor>
2016 class PatchForEachSelectedWalker : public scene::Graph::Walker
2017 {
2018   const Functor& m_functor;
2019 public:
2020   PatchForEachSelectedWalker(const Functor& functor) : m_functor(functor)
2021   {
2022   }
2023   bool pre(const scene::Path& path, scene::Instance& instance) const
2024   {
2025     if(path.top().get().visible())
2026     {
2027       Patch* patch = Node_getPatch(path.top());
2028       if(patch != 0
2029         && Instance_getSelectable(instance)->isSelected())
2030       {
2031         m_functor(*patch);
2032       }
2033     }
2034     return true;
2035   }
2036 };
2037
2038 template<typename Functor>
2039 inline void Scene_forEachVisibleSelectedPatch(const Functor& functor)
2040 {
2041   GlobalSceneGraph().traverse(PatchForEachSelectedWalker<Functor>(functor));
2042 }
2043
2044 template<typename Functor>
2045 class PatchForEachInstanceWalker : public scene::Graph::Walker
2046 {
2047   const Functor& m_functor;
2048 public:
2049   PatchForEachInstanceWalker(const Functor& functor) : m_functor(functor)
2050   {
2051   }
2052   bool pre(const scene::Path& path, scene::Instance& instance) const
2053   {
2054     if(path.top().get().visible())
2055     {
2056       PatchInstance* patch = Instance_getPatch(instance);
2057       if(patch != 0)
2058       {
2059         m_functor(*patch);
2060       }
2061     }
2062     return true;
2063   }
2064 };
2065
2066 template<typename Functor>
2067 inline void Scene_forEachVisiblePatchInstance(const Functor& functor)
2068 {
2069   GlobalSceneGraph().traverse(PatchForEachInstanceWalker<Functor>(functor));
2070 }
2071
2072 #endif