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