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