radiant/brush.h

   1 /*
   2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22 #if !defined(INCLUDED_BRUSH_H)
  23 #define INCLUDED_BRUSH_H
  24
  25 /// \file
  26 /// \brief The brush primitive.
  27 ///
  28 /// A collection of planes that define a convex polyhedron.
  29 /// The Boundary-Representation of this primitive is a manifold polygonal mesh.
  30 /// Each face polygon is represented by a list of vertices in a \c Winding.
  31 /// Each vertex is associated with another face that is adjacent to the edge
  32 /// formed by itself and the next vertex in the winding. This information can
  33 /// be used to find edge-pairs and vertex-rings.
  34
  35
  36 #include "debugging/debugging.h"
  37
  38 #include "itexdef.h"
  39 #include "iundo.h"
  40 #include "iselection.h"
  41 #include "irender.h"
  42 #include "imap.h"
  43 #include "ibrush.h"
  44 #include "igl.h"
  45 #include "ifilter.h"
  46 #include "nameable.h"
  47 #include "moduleobserver.h"
  48
  49 #include <set>
  50
  51 #include "cullable.h"
  52 #include "renderable.h"
  53 #include "selectable.h"
  54 #include "editable.h"
  55 #include "mapfile.h"
  56
  57 #include "math/frustum.h"
  58 #include "selectionlib.h"
  59 #include "render.h"
  60 #include "texturelib.h"
  61 #include "container/container.h"
  62 #include "generic/bitfield.h"
  63 #include "signal/signalfwd.h"
  64
  65 #include "winding.h"
  66 #include "brush_primit.h"
  67
  68 const unsigned int BRUSH_DETAIL_FLAG = 27;
  69 const unsigned int BRUSH_DETAIL_MASK = (1 << BRUSH_DETAIL_FLAG);
  70
  71 enum EBrushType
  72 {
  73   eBrushTypeQuake,
  74   eBrushTypeQuake2,
  75   eBrushTypeQuake3,
  76   eBrushTypeQuake3BP,
  77   eBrushTypeDoom3,
  78   eBrushTypeQuake4,
  79   eBrushTypeHalfLife,
  80 };
  81
  82
  83 #define BRUSH_CONNECTIVITY_DEBUG 0
  84 #define BRUSH_DEGENERATE_DEBUG 0
  85
  86 template<typename TextOuputStreamType>
  87 inline TextOuputStreamType& ostream_write(TextOuputStreamType& ostream, const Matrix4& m)
  88 {
  89   return ostream << "(" << m[0] << " " << m[1] << " " << m[2] << " " << m[3] << ", "
  90     << m[4] << " " << m[5] << " " << m[6] << " " << m[7] << ", "
  91     << m[8] << " " << m[9] << " " << m[10] << " " << m[11] << ", "
  92     << m[12] << " " << m[13] << " " << m[14] << " " << m[15] << ")";
  93 }
  94
  95 inline void print_vector3(const Vector3& v)
  96 {
  97   globalOutputStream() << "( " << v.x() << " " << v.y() << " " << v.z() << " )\n";
  98 }
  99
 100 inline void print_3x3(const Matrix4& m)
 101 {
 102   globalOutputStream() << "( " << m.xx() << " " << m.xy() << " " << m.xz() << " ) "
 103     << "( " << m.yx() << " " << m.yy() << " " << m.yz() << " ) "
 104     << "( " << m.zx() << " " << m.zy() << " " << m.zz() << " )\n";
 105 }
 106
 107
 108
 109 inline bool texdef_sane(const texdef_t& texdef)
 110 {
 111   return fabs(texdef.shift[0]) < (1 << 16)
 112     && fabs(texdef.shift[1]) < (1 << 16);
 113 }
 114
 115 inline void Winding_DrawWireframe(const Winding& winding)
 116 {
 117   glVertexPointer(3, GL_FLOAT, sizeof(WindingVertex), &winding.points.data()->vertex);
 118   glDrawArrays(GL_LINE_LOOP, 0, GLsizei(winding.numpoints));
 119 }
 120
 121 inline void Winding_Draw(const Winding& winding, const Vector3& normal, RenderStateFlags state)
 122 {
 123   glVertexPointer(3, GL_FLOAT, sizeof(WindingVertex), &winding.points.data()->vertex);
 124
 125   if((state & RENDER_BUMP) != 0)
 126   {
 127     Vector3 normals[c_brush_maxFaces];
 128     typedef Vector3* Vector3Iter;
 129     for(Vector3Iter i = normals, end = normals + winding.numpoints; i != end; ++i)
 130     {
 131       *i = normal;
 132     }
 133     if(GlobalShaderCache().useShaderLanguage())
 134     {
 135       glNormalPointer(GL_FLOAT, sizeof(Vector3), normals);
 136       glVertexAttribPointerARB(c_attr_TexCoord0, 2, GL_FLOAT, 0, sizeof(WindingVertex), &winding.points.data()->texcoord);
 137       glVertexAttribPointerARB(c_attr_Tangent, 3, GL_FLOAT, 0, sizeof(WindingVertex), &winding.points.data()->tangent);
 138       glVertexAttribPointerARB(c_attr_Binormal, 3, GL_FLOAT, 0, sizeof(WindingVertex), &winding.points.data()->bitangent);
 139     }
 140     else
 141     {
 142       glVertexAttribPointerARB(11, 3, GL_FLOAT, 0, sizeof(Vector3), normals);
 143       glVertexAttribPointerARB(8, 2, GL_FLOAT, 0, sizeof(WindingVertex), &winding.points.data()->texcoord);
 144       glVertexAttribPointerARB(9, 3, GL_FLOAT, 0, sizeof(WindingVertex), &winding.points.data()->tangent);
 145       glVertexAttribPointerARB(10, 3, GL_FLOAT, 0, sizeof(WindingVertex), &winding.points.data()->bitangent);
 146     }
 147   }
 148   else
 149   {
 150     if (state & RENDER_LIGHTING)
 151     {
 152       Vector3 normals[c_brush_maxFaces];
 153       typedef Vector3* Vector3Iter;
 154       for(Vector3Iter i = normals, last = normals + winding.numpoints; i != last; ++i)
 155       {
 156         *i = normal;
 157       }
 158       glNormalPointer(GL_FLOAT, sizeof(Vector3), normals);
 159     }
 160
 161     if (state & RENDER_TEXTURE)
 162     {
 163       glTexCoordPointer(2, GL_FLOAT, sizeof(WindingVertex), &winding.points.data()->texcoord);
 164     }
 165   }
 166 #if 0
 167   if (state & RENDER_FILL)
 168   {
 169     glDrawArrays(GL_TRIANGLE_FAN, 0, GLsizei(winding.numpoints));
 170   }
 171   else
 172   {
 173     glDrawArrays(GL_LINE_LOOP, 0, GLsizei(winding.numpoints));
 174   }
 175 #else
 176   glDrawArrays(GL_POLYGON, 0, GLsizei(winding.numpoints));
 177 #endif
 178
 179 #if 0
 180   const Winding& winding = winding;
 181
 182   if(state & RENDER_FILL)
 183   {
 184     glBegin(GL_POLYGON);
 185   }
 186   else
 187   {
 188     glBegin(GL_LINE_LOOP);
 189   }
 190
 191   if (state & RENDER_LIGHTING)
 192     glNormal3fv(normal);
 193
 194   for(int i = 0; i < winding.numpoints; ++i)
 195   {
 196     if (state & RENDER_TEXTURE)
 197       glTexCoord2fv(&winding.points[i][3]);
 198     glVertex3fv(winding.points[i]);
 199   }
 200   glEnd();
 201 #endif
 202 }
 203
 204
 205 #include "shaderlib.h"
 206
 207 typedef DoubleVector3 PlanePoints[3];
 208
 209 inline bool planepts_equal(const PlanePoints planepts, const PlanePoints other)
 210 {
 211   return planepts[0] == other[0] && planepts[1] == other[1] && planepts[2] == other[2];
 212 }
 213
 214 inline void planepts_assign(PlanePoints planepts, const PlanePoints other)
 215 {
 216   planepts[0] = other[0];
 217   planepts[1] = other[1];
 218   planepts[2] = other[2];
 219 }
 220
 221 inline void planepts_quantise(PlanePoints planepts, double snap)
 222 {
 223   vector3_snap(planepts[0], snap);
 224   vector3_snap(planepts[1], snap);
 225   vector3_snap(planepts[2], snap);
 226 }
 227
 228 inline float vector3_max_component(const Vector3& vec3)
 229 {
 230   return std::max(fabsf(vec3[0]), std::max(fabsf(vec3[1]), fabsf(vec3[2])));
 231 }
 232
 233 inline void edge_snap(Vector3& edge, double snap)
 234 {
 235   float scale = static_cast<float>(ceil(fabs(snap / vector3_max_component(edge))));
 236   if(scale > 0.0f)
 237   {
 238     vector3_scale(edge, scale);
 239   }
 240   vector3_snap(edge, snap);
 241 }
 242
 243 inline void planepts_snap(PlanePoints planepts, double snap)
 244 {
 245   Vector3 edge01(vector3_subtracted(planepts[1], planepts[0]));
 246   Vector3 edge12(vector3_subtracted(planepts[2], planepts[1]));
 247   Vector3 edge20(vector3_subtracted(planepts[0], planepts[2]));
 248
 249   double length_squared_01 = vector3_dot(edge01, edge01);
 250   double length_squared_12 = vector3_dot(edge12, edge12);
 251   double length_squared_20 = vector3_dot(edge20, edge20);
 252
 253   vector3_snap(planepts[0], snap);
 254
 255   if(length_squared_01 < length_squared_12)
 256   {
 257     if(length_squared_12 < length_squared_20)
 258     {
 259       edge_snap(edge01, snap);
 260       edge_snap(edge12, snap);
 261       planepts[1] = vector3_added(planepts[0], edge01);
 262       planepts[2] = vector3_added(planepts[1], edge12);
 263     }
 264     else
 265     {
 266       edge_snap(edge20, snap);
 267       edge_snap(edge01, snap);
 268       planepts[1] = vector3_added(planepts[0], edge20);
 269       planepts[2] = vector3_added(planepts[1], edge01);
 270     }
 271   }
 272   else
 273   {
 274     if(length_squared_01 < length_squared_20)
 275     {
 276       edge_snap(edge01, snap);
 277       edge_snap(edge12, snap);
 278       planepts[1] = vector3_added(planepts[0], edge01);
 279       planepts[2] = vector3_added(planepts[1], edge12);
 280     }
 281     else
 282     {
 283       edge_snap(edge12, snap);
 284       edge_snap(edge20, snap);
 285       planepts[1] = vector3_added(planepts[0], edge12);
 286       planepts[2] = vector3_added(planepts[1], edge20);
 287     }
 288   }
 289 }
 290
 291 inline PointVertex pointvertex_for_planept(const DoubleVector3& point, const Colour4b& colour)
 292 {
 293   return PointVertex(
 294     Vertex3f(
 295       static_cast<float>(point.x()),
 296       static_cast<float>(point.y()),
 297       static_cast<float>(point.z())
 298     ),
 299     colour
 300   );
 301 }
 302
 303 inline PointVertex pointvertex_for_windingpoint(const Vector3& point, const Colour4b& colour)
 304 {
 305   return PointVertex(
 306     vertex3f_for_vector3(point),
 307     colour
 308   );
 309 }
 310
 311 inline bool check_plane_is_integer(const PlanePoints& planePoints)
 312 {
 313   return !float_is_integer(planePoints[0][0])
 314     || !float_is_integer(planePoints[0][1])
 315     || !float_is_integer(planePoints[0][2])
 316     || !float_is_integer(planePoints[1][0])
 317     || !float_is_integer(planePoints[1][1])
 318     || !float_is_integer(planePoints[1][2])
 319     || !float_is_integer(planePoints[2][0])
 320     || !float_is_integer(planePoints[2][1])
 321     || !float_is_integer(planePoints[2][2]);
 322 }
 323
 324 inline void brush_check_shader(const char* name)
 325 {
 326   if(!shader_valid(name))
 327   {
 328     globalErrorStream() << "brush face has invalid texture name: '" << name << "'\n";
 329   }
 330 }
 331
 332 class FaceShaderObserver
 333 {
 334 public:
 335   virtual void realiseShader() = 0;
 336   virtual void unrealiseShader() = 0;
 337 };
 338
 339 class FaceShaderObserverRealise
 340 {
 341 public:
 342   void operator()(FaceShaderObserver& observer) const
 343   {
 344     observer.realiseShader();
 345   }
 346 };
 347
 348 class FaceShaderObserverUnrealise
 349 {
 350 public:
 351   void operator()(FaceShaderObserver& observer) const
 352   {
 353     observer.unrealiseShader();
 354   }
 355 };
 356
 357 typedef ReferencePair<FaceShaderObserver> FaceShaderObserverPair;
 358
 359
 360 class ContentsFlagsValue
 361 {
 362 public:
 363   ContentsFlagsValue()
 364   {
 365   }
 366   ContentsFlagsValue(int surfaceFlags, int contentFlags, int value, bool specified) :
 367     m_surfaceFlags(surfaceFlags),
 368     m_contentFlags(contentFlags),
 369     m_value(value),
 370     m_specified(specified)
 371   {
 372   }
 373   int m_surfaceFlags;
 374   int m_contentFlags;
 375   int m_value;
 376   bool m_specified;
 377 };
 378
 379 inline void ContentsFlagsValue_assignMasked(ContentsFlagsValue& flags, const ContentsFlagsValue& other)
 380 {
 381   bool detail = bitfield_enabled(flags.m_contentFlags, BRUSH_DETAIL_MASK);
 382   flags = other;
 383   if(detail)
 384   {
 385     flags.m_contentFlags = bitfield_enable(flags.m_contentFlags, BRUSH_DETAIL_MASK);
 386   }
 387   else
 388   {
 389     flags.m_contentFlags = bitfield_disable(flags.m_contentFlags, BRUSH_DETAIL_MASK);
 390   }
 391 }
 392
 393
 394 class FaceShader : public ModuleObserver
 395 {
 396 public:
 397   class SavedState
 398   {
 399   public:
 400     CopiedString m_shader;
 401     ContentsFlagsValue m_flags;
 402
 403     SavedState(const FaceShader& faceShader)
 404     {
 405       m_shader = faceShader.getShader();
 406       m_flags = faceShader.m_flags;
 407     }
 408
 409     void exportState(FaceShader& faceShader) const
 410     {
 411       faceShader.setShader(m_shader.c_str());
 412       faceShader.setFlags(m_flags);
 413     }
 414   };
 415
 416   CopiedString m_shader;
 417   Shader* m_state;
 418   ContentsFlagsValue m_flags;
 419   FaceShaderObserverPair m_observers;
 420   bool m_instanced;
 421   bool m_realised;
 422
 423   FaceShader(const char* shader, const ContentsFlagsValue& flags = ContentsFlagsValue(0, 0, 0, false)) :
 424     m_shader(shader),
 425     m_state(0),
 426     m_flags(flags),
 427     m_instanced(false),
 428     m_realised(false)
 429   {
 430     captureShader();
 431   }
 432   ~FaceShader()
 433   {
 434     releaseShader();
 435   }
 436   // copy-construction not supported
 437   FaceShader(const FaceShader& other);
 438
 439   void instanceAttach()
 440   {
 441     m_instanced = true;
 442     m_state->incrementUsed();
 443   }
 444   void instanceDetach()
 445   {
 446     m_state->decrementUsed();
 447     m_instanced = false;
 448   }
 449
 450   void captureShader()
 451   {
 452     ASSERT_MESSAGE(m_state == 0, "shader cannot be captured");
 453     brush_check_shader(m_shader.c_str());
 454     m_state = GlobalShaderCache().capture(m_shader.c_str());
 455     m_state->attach(*this);
 456   }
 457   void releaseShader()
 458   {
 459     ASSERT_MESSAGE(m_state != 0, "shader cannot be released");
 460     m_state->detach(*this);
 461     GlobalShaderCache().release(m_shader.c_str());
 462     m_state = 0;
 463   }
 464
 465   void realise()
 466   {
 467     ASSERT_MESSAGE(!m_realised, "FaceTexdef::realise: already realised");
 468     m_realised = true;
 469     m_observers.forEach(FaceShaderObserverRealise());
 470   }
 471   void unrealise()
 472   {
 473     ASSERT_MESSAGE(m_realised, "FaceTexdef::unrealise: already unrealised");
 474     m_observers.forEach(FaceShaderObserverUnrealise());
 475     m_realised = false;
 476   }
 477
 478   void attach(FaceShaderObserver& observer)
 479   {
 480     m_observers.attach(observer);
 481     if(m_realised)
 482     {
 483       observer.realiseShader();
 484     }
 485   }
 486
 487   void detach(FaceShaderObserver& observer)
 488   {
 489     if(m_realised)
 490     {
 491       observer.unrealiseShader();
 492     }
 493     m_observers.detach(observer);
 494   }
 495
 496   const char* getShader() const
 497   {
 498     return m_shader.c_str();
 499   }
 500   void setShader(const char* name)
 501   {
 502     if(m_instanced)
 503     {
 504       m_state->decrementUsed();
 505     }
 506     releaseShader();
 507     m_shader = name;
 508     captureShader();
 509     if(m_instanced)
 510     {
 511       m_state->incrementUsed();
 512     }
 513   }
 514   ContentsFlagsValue getFlags() const
 515   {
 516     ASSERT_MESSAGE(m_realised, "FaceShader::getFlags: flags not valid when unrealised");
 517     if(!m_flags.m_specified)
 518     {
 519       return ContentsFlagsValue(
 520         m_state->getTexture().surfaceFlags,
 521         m_state->getTexture().contentFlags,
 522         m_state->getTexture().value,
 523         true
 524       );
 525     }
 526     return m_flags;
 527   }
 528   void setFlags(const ContentsFlagsValue& flags)
 529   {
 530     ASSERT_MESSAGE(m_realised, "FaceShader::setFlags: flags not valid when unrealised");
 531     ContentsFlagsValue_assignMasked(m_flags, flags);
 532   }
 533
 534   Shader* state() const
 535   {
 536     return m_state;
 537   }
 538
 539   std::size_t width() const
 540   {
 541     if(m_realised)
 542     {
 543       return m_state->getTexture().width;
 544     }
 545     return 1;
 546   }
 547   std::size_t height() const
 548   {
 549     if(m_realised)
 550     {
 551       return m_state->getTexture().height;
 552     }
 553     return 1;
 554   }
 555   unsigned int shaderFlags() const
 556   {
 557     if(m_realised)
 558     {
 559       return m_state->getFlags();
 560     }
 561     return 0;
 562   }
 563 };
 564
 565
 566
 567
 568 class FaceTexdef : public FaceShaderObserver
 569 {
 570   // not copyable
 571   FaceTexdef(const FaceTexdef& other);
 572   // not assignable
 573   FaceTexdef& operator=(const FaceTexdef& other);
 574 public:
 575   class SavedState
 576   {
 577   public:
 578     TextureProjection m_projection;
 579
 580     SavedState(const FaceTexdef& faceTexdef)
 581     {
 582       m_projection = faceTexdef.m_projection;
 583     }
 584
 585     void exportState(FaceTexdef& faceTexdef) const
 586     {
 587       Texdef_Assign(faceTexdef.m_projection, m_projection);
 588     }
 589   };
 590
 591   FaceShader& m_shader;
 592   TextureProjection m_projection;
 593   bool m_projectionInitialised;
 594   bool m_scaleApplied;
 595
 596   FaceTexdef(
 597     FaceShader& shader,
 598     const TextureProjection& projection,
 599     bool projectionInitialised = true
 600   ) :
 601     m_shader(shader),
 602     m_projection(projection),
 603     m_projectionInitialised(projectionInitialised),
 604     m_scaleApplied(false)
 605   {
 606     m_shader.attach(*this);
 607   }
 608   ~FaceTexdef()
 609   {
 610     m_shader.detach(*this);
 611   }
 612
 613   void addScale()
 614   {
 615     ASSERT_MESSAGE(!m_scaleApplied, "texture scale aready added");
 616     m_scaleApplied = true;
 617     m_projection.m_brushprimit_texdef.addScale(m_shader.width(), m_shader.height());
 618   }
 619   void removeScale()
 620   {
 621     ASSERT_MESSAGE(m_scaleApplied, "texture scale aready removed");
 622     m_scaleApplied = false;
 623     m_projection.m_brushprimit_texdef.removeScale(m_shader.width(), m_shader.height());
 624   }
 625
 626   void realiseShader()
 627   {
 628     if(m_projectionInitialised && !m_scaleApplied)
 629     {
 630       addScale();
 631     }
 632   }
 633   void unrealiseShader()
 634   {
 635     if(m_projectionInitialised && m_scaleApplied)
 636     {
 637       removeScale();
 638     }
 639   }
 640
 641   void setTexdef(const TextureProjection& projection)
 642   {
 643     removeScale();
 644     Texdef_Assign(m_projection, projection);
 645     addScale();
 646   }
 647
 648   void shift(float s, float t)
 649   {
 650     ASSERT_MESSAGE(texdef_sane(m_projection.m_texdef), "FaceTexdef::shift: bad texdef");
 651     removeScale();
 652     Texdef_Shift(m_projection, s, t);
 653     addScale();
 654   }
 655
 656   void scale(float s, float t)
 657   {
 658     removeScale();
 659     Texdef_Scale(m_projection, s, t);
 660     addScale();
 661   }
 662
 663   void rotate(float angle)
 664   {
 665     removeScale();
 666     Texdef_Rotate(m_projection, angle);
 667     addScale();
 668   }
 669
 670   void fit(const Vector3& normal, const Winding& winding, float s_repeat, float t_repeat)
 671   {
 672     Texdef_FitTexture(m_projection, m_shader.width(), m_shader.height(), normal, winding, s_repeat, t_repeat);
 673   }
 674
 675   void emitTextureCoordinates(Winding& winding, const Vector3& normal, const Matrix4& localToWorld)
 676   {
 677     Texdef_EmitTextureCoordinates(m_projection, m_shader.width(), m_shader.height(), winding, normal, localToWorld);
 678   }
 679
 680   void transform(const Plane3& plane, const Matrix4& matrix)
 681   {
 682     removeScale();
 683     Texdef_transformLocked(m_projection, m_shader.width(), m_shader.height(), plane, matrix);
 684     addScale();
 685   }
 686
 687   TextureProjection normalised() const
 688   {
 689     brushprimit_texdef_t tmp(m_projection.m_brushprimit_texdef);
 690     tmp.removeScale(m_shader.width(), m_shader.height());
 691     return TextureProjection(m_projection.m_texdef, tmp, m_projection.m_basis_s, m_projection.m_basis_t);
 692   }
 693   void setBasis(const Vector3& normal)
 694   {
 695     Matrix4 basis;
 696     Normal_GetTransform(normal, basis);
 697     m_projection.m_basis_s = Vector3(basis.xx(), basis.yx(), basis.zx());
 698     m_projection.m_basis_t = Vector3(-basis.xy(), -basis.yy(), -basis.zy());
 699   }
 700 };
 701
 702 inline void planepts_print(const PlanePoints& planePoints, TextOutputStream& ostream)
 703 {
 704   ostream << "( " << planePoints[0][0] << " " << planePoints[0][1] << " " << planePoints[0][2] << " ) "
 705     << "( " << planePoints[1][0] << " " << planePoints[1][1] << " " << planePoints[1][2] << " ) "
 706     << "( " << planePoints[2][0] << " " << planePoints[2][1] << " " << planePoints[2][2] << " )";
 707 }
 708
 709
 710 inline Plane3 Plane3_applyTranslation(const Plane3& plane, const Vector3& translation)
 711 {
 712   Plane3 tmp(plane3_translated(Plane3(plane.normal(), -plane.dist()), translation));
 713   return Plane3(tmp.normal(), -tmp.dist());
 714 }
 715
 716 inline Plane3 Plane3_applyTransform(const Plane3& plane, const Matrix4& matrix)
 717 {
 718   Plane3 tmp(plane3_transformed(Plane3(plane.normal(), -plane.dist()), matrix));
 719   return Plane3(tmp.normal(), -tmp.dist());
 720 }
 721
 722 class FacePlane
 723 {
 724   PlanePoints m_planepts;
 725   Plane3 m_planeCached;
 726   Plane3 m_plane;
 727 public:
 728   Vector3 m_funcStaticOrigin;
 729
 730   static EBrushType m_type;
 731
 732   static bool isDoom3Plane()
 733   {
 734     return FacePlane::m_type == eBrushTypeDoom3 || FacePlane::m_type == eBrushTypeQuake4;
 735   }
 736
 737   class SavedState
 738   {
 739   public:
 740     PlanePoints m_planepts;
 741     Plane3 m_plane;
 742
 743     SavedState(const FacePlane& facePlane)
 744     {
 745       if(facePlane.isDoom3Plane())
 746       {
 747         m_plane = facePlane.m_plane;
 748       }
 749       else
 750       {
 751         planepts_assign(m_planepts, facePlane.planePoints());
 752       }
 753     }
 754
 755     void exportState(FacePlane& facePlane) const
 756     {
 757       if(facePlane.isDoom3Plane())
 758       {
 759         facePlane.m_plane = m_plane;
 760         facePlane.updateTranslated();
 761       }
 762       else
 763       {
 764         planepts_assign(facePlane.planePoints(), m_planepts);
 765         facePlane.MakePlane();
 766       }
 767     }
 768   };
 769
 770   FacePlane() : m_funcStaticOrigin(0, 0, 0)
 771   {
 772   }
 773   FacePlane(const FacePlane& other) : m_funcStaticOrigin(0, 0, 0)
 774   {
 775     if(!isDoom3Plane())
 776     {
 777       planepts_assign(m_planepts, other.m_planepts);
 778       MakePlane();
 779     }
 780     else
 781     {
 782       m_plane = other.m_plane;
 783       updateTranslated();
 784     }
 785   }
 786
 787   void MakePlane()
 788   {
 789     if(!isDoom3Plane())
 790     {
 791 #if 0
 792       if(check_plane_is_integer(m_planepts))
 793       {
 794         globalErrorStream() << "non-integer planepts: ";
 795         planepts_print(m_planepts, globalErrorStream());
 796         globalErrorStream() << "\n";
 797       }
 798 #endif
 799       m_planeCached = plane3_for_points(m_planepts);
 800     }
 801   }
 802
 803   void reverse()
 804   {
 805     if(!isDoom3Plane())
 806     {
 807       vector3_swap(m_planepts[0], m_planepts[2]);
 808       MakePlane();
 809     }
 810     else
 811     {
 812       m_planeCached = plane3_flipped(m_plane);
 813       updateSource();
 814     }
 815   }
 816   void transform(const Matrix4& matrix, bool mirror)
 817   {
 818     if(!isDoom3Plane())
 819     {
 820
 821 #if 0
 822       bool off = check_plane_is_integer(planePoints());
 823 #endif
 824
 825       matrix4_transform_point(matrix, m_planepts[0]);
 826       matrix4_transform_point(matrix, m_planepts[1]);
 827       matrix4_transform_point(matrix, m_planepts[2]);
 828
 829       if(mirror)
 830       {
 831         reverse();
 832       }
 833
 834 #if 0
 835       if(check_plane_is_integer(planePoints()))
 836       {
 837         if(!off)
 838         {
 839           globalErrorStream() << "caused by transform\n";
 840         }
 841       }
 842 #endif
 843       MakePlane();
 844     }
 845     else
 846     {
 847       m_planeCached = Plane3_applyTransform(m_planeCached, matrix);
 848       updateSource();
 849     }
 850   }
 851   void offset(float offset)
 852   {
 853     if(!isDoom3Plane())
 854     {
 855       Vector3 move(vector3_scaled(m_planeCached.normal(), -offset));
 856
 857       vector3_subtract(m_planepts[0], move);
 858       vector3_subtract(m_planepts[1], move);
 859       vector3_subtract(m_planepts[2], move);
 860
 861       MakePlane();
 862     }
 863     else
 864     {
 865       m_planeCached.d += offset;
 866       updateSource();
 867     }
 868   }
 869
 870   void updateTranslated()
 871   {
 872     m_planeCached = Plane3_applyTranslation(m_plane, m_funcStaticOrigin);
 873   }
 874   void updateSource()
 875   {
 876     m_plane = Plane3_applyTranslation(m_planeCached, vector3_negated(m_funcStaticOrigin));
 877   }
 878
 879
 880   PlanePoints& planePoints()
 881   {
 882     return m_planepts;
 883   }
 884   const PlanePoints& planePoints() const
 885   {
 886     return m_planepts;
 887   }
 888   const Plane3& plane3() const
 889   {
 890     return m_planeCached;
 891   }
 892   void setDoom3Plane(const Plane3& plane)
 893   {
 894     m_plane = plane;
 895     updateTranslated();
 896   }
 897   const Plane3& getDoom3Plane() const
 898   {
 899     return m_plane;
 900   }
 901
 902   void copy(const FacePlane& other)
 903   {
 904     if(!isDoom3Plane())
 905     {
 906       planepts_assign(m_planepts, other.m_planepts);
 907       MakePlane();
 908     }
 909     else
 910     {
 911       m_planeCached = other.m_plane;
 912       updateSource();
 913     }
 914   }
 915   void copy(const Vector3& p0, const Vector3& p1, const Vector3& p2)
 916   {
 917     if(!isDoom3Plane())
 918     {
 919       m_planepts[0] = p0;
 920       m_planepts[1] = p1;
 921       m_planepts[2] = p2;
 922       MakePlane();
 923     }
 924     else
 925     {
 926       m_planeCached = plane3_for_points(p2, p1, p0);
 927       updateSource();
 928     }
 929   }
 930 };
 931
 932 inline void Winding_testSelect(Winding& winding, SelectionTest& test, SelectionIntersection& best)
 933 {
 934   test.TestPolygon(VertexPointer(reinterpret_cast<VertexPointer::pointer>(&winding.points.data()->vertex), sizeof(WindingVertex)), winding.numpoints, best);
 935 }
 936
 937 const double GRID_MIN = 0.125;
 938
 939 inline double quantiseInteger(double f)
 940 {
 941   return float_to_integer(f);
 942 }
 943
 944 inline double quantiseFloating(double f)
 945 {
 946   return float_snapped(f, 1.f / (1 << 16));
 947 }
 948
 949 typedef double (*QuantiseFunc)(double f);
 950
 951 class Face;
 952
 953 class FaceFilter
 954 {
 955 public:
 956   virtual bool filter(const Face& face) const = 0;
 957 };
 958
 959 bool face_filtered(Face& face);
 960 void add_face_filter(FaceFilter& filter, int mask, bool invert = false);
 961
 962 void Brush_addTextureChangedCallback(const SignalHandler& callback);
 963 void Brush_textureChanged();
 964
 965
 966 extern bool g_brush_texturelock_enabled;
 967
 968 class FaceObserver
 969 {
 970 public:
 971   virtual void planeChanged() = 0;
 972   virtual void connectivityChanged() = 0;
 973   virtual void shaderChanged() = 0;
 974   virtual void evaluateTransform() = 0;
 975 };
 976
 977 class Face :
 978 public OpenGLRenderable,
 979 public Filterable,
 980 public Undoable,
 981 public FaceShaderObserver
 982 {
 983   std::size_t m_refcount;
 984
 985   class SavedState : public UndoMemento
 986   {
 987   public:
 988     FacePlane::SavedState m_planeState;
 989     FaceTexdef::SavedState m_texdefState;
 990     FaceShader::SavedState m_shaderState;
 991
 992     SavedState(const Face& face) : m_planeState(face.getPlane()), m_texdefState(face.getTexdef()), m_shaderState(face.getShader())
 993     {
 994     }
 995
 996     void exportState(Face& face) const
 997     {
 998       m_planeState.exportState(face.getPlane());
 999       m_shaderState.exportState(face.getShader());
1000       m_texdefState.exportState(face.getTexdef());
1001     }
1002
1003     void release()
1004     {
1005       delete this;
1006     }
1007   };
1008
1009 public:
1010   static QuantiseFunc m_quantise;
1011   static EBrushType m_type;
1012
1013   PlanePoints m_move_planepts;
1014   PlanePoints m_move_planeptsTransformed;
1015 private:
1016   FacePlane m_plane;
1017   FacePlane m_planeTransformed;
1018   FaceShader m_shader;
1019   FaceTexdef m_texdef;
1020   TextureProjection m_texdefTransformed;
1021
1022   Winding m_winding;
1023   Vector3 m_centroid;
1024   bool m_filtered;
1025
1026   FaceObserver* m_observer;
1027   UndoObserver* m_undoable_observer;
1028   MapFile* m_map;
1029
1030   // assignment not supported
1031   Face& operator=(const Face& other);
1032   // copy-construction not supported
1033   Face(const Face& other);
1034
1035 public:
1036
1037   Face(FaceObserver* observer) :
1038     m_refcount(0),
1039     m_shader(texdef_name_default()),
1040     m_texdef(m_shader, TextureProjection(), false),
1041     m_filtered(false),
1042     m_observer(observer),
1043     m_undoable_observer(0),
1044     m_map(0)
1045   {
1046     m_shader.attach(*this);
1047     m_plane.copy(Vector3(0, 0, 0), Vector3(64, 0, 0), Vector3(0, 64, 0));
1048     m_texdef.setBasis(m_plane.plane3().normal());
1049     planeChanged();
1050   }
1051   Face(
1052     const Vector3& p0,
1053     const Vector3& p1,
1054     const Vector3& p2,
1055     const char* shader,
1056     const TextureProjection& projection,
1057     FaceObserver* observer
1058   ) :
1059     m_refcount(0),
1060     m_shader(shader),
1061     m_texdef(m_shader, projection),
1062     m_observer(observer),
1063     m_undoable_observer(0),
1064     m_map(0)
1065   {
1066     m_shader.attach(*this);
1067     m_plane.copy(p0, p1, p2);
1068     m_texdef.setBasis(m_plane.plane3().normal());
1069     planeChanged();
1070     updateFiltered();
1071   }
1072   Face(const Face& other, FaceObserver* observer) :
1073     m_refcount(0),
1074     m_shader(other.m_shader.getShader(), other.m_shader.m_flags),
1075     m_texdef(m_shader, other.getTexdef().normalised()),
1076     m_observer(observer),
1077     m_undoable_observer(0),
1078     m_map(0)
1079   {
1080     m_shader.attach(*this);
1081     m_plane.copy(other.m_plane);
1082     planepts_assign(m_move_planepts, other.m_move_planepts);
1083     m_texdef.setBasis(m_plane.plane3().normal());
1084     planeChanged();
1085     updateFiltered();
1086   }
1087   ~Face()
1088   {
1089     m_shader.detach(*this);
1090   }
1091
1092   void planeChanged()
1093   {
1094     revertTransform();
1095     m_observer->planeChanged();
1096   }
1097
1098   void realiseShader()
1099   {
1100     m_observer->shaderChanged();
1101   }
1102   void unrealiseShader()
1103   {
1104   }
1105
1106   void instanceAttach(MapFile* map)
1107   {
1108     m_shader.instanceAttach();
1109     m_map = map;
1110     m_undoable_observer = GlobalUndoSystem().observer(this);
1111     GlobalFilterSystem().registerFilterable(*this);
1112   }
1113   void instanceDetach(MapFile* map)
1114   {
1115     GlobalFilterSystem().unregisterFilterable(*this);
1116     m_undoable_observer = 0;
1117     GlobalUndoSystem().release(this);
1118     m_map = 0;
1119     m_shader.instanceDetach();
1120   }
1121
1122   void render(RenderStateFlags state) const
1123   {
1124     Winding_Draw(m_winding, m_planeTransformed.plane3().normal(), state);
1125   }
1126
1127   void updateFiltered()
1128   {
1129     m_filtered = face_filtered(*this);
1130   }
1131   bool isFiltered() const
1132   {
1133     return m_filtered;
1134   }
1135
1136   void undoSave()
1137   {
1138     if(m_map != 0)
1139     {
1140       m_map->changed();
1141     }
1142     if(m_undoable_observer != 0)
1143     {
1144       m_undoable_observer->save(this);
1145     }
1146   }
1147
1148   // undoable
1149   UndoMemento* exportState() const
1150   {
1151     return new SavedState(*this);
1152   }
1153   void importState(const UndoMemento* data)
1154   {
1155     undoSave();
1156
1157     static_cast<const SavedState*>(data)->exportState(*this);
1158
1159     planeChanged();
1160     m_observer->connectivityChanged();
1161     texdefChanged();
1162     m_observer->shaderChanged();
1163     updateFiltered();
1164   }
1165
1166   void IncRef()
1167   {
1168     ++m_refcount;
1169   }
1170   void DecRef()
1171   {
1172     if(--m_refcount == 0)
1173       delete this;
1174   }
1175
1176   void flipWinding()
1177   {
1178     m_plane.reverse();
1179     planeChanged();
1180   }
1181
1182   bool intersectVolume(const VolumeTest& volume, const Matrix4& localToWorld) const
1183   {
1184     return volume.TestPlane(Plane3(plane3().normal(), -plane3().dist()), localToWorld);
1185   }
1186
1187   void render(Renderer& renderer, const Matrix4& localToWorld) const
1188   {
1189     renderer.SetState(m_shader.state(), Renderer::eFullMaterials);
1190     renderer.addRenderable(*this, localToWorld);
1191   }
1192
1193   void transform(const Matrix4& matrix, bool mirror)
1194   {
1195     if(g_brush_texturelock_enabled)
1196     {
1197       Texdef_transformLocked(m_texdefTransformed, m_shader.width(), m_shader.height(), m_plane.plane3(), matrix);
1198     }
1199
1200     m_planeTransformed.transform(matrix, mirror);
1201
1202 #if 0
1203     ASSERT_MESSAGE(projectionaxis_for_normal(normal) == projectionaxis_for_normal(plane3().normal()), "bleh");
1204 #endif
1205     m_observer->planeChanged();
1206   }
1207
1208   void assign_planepts(const PlanePoints planepts)
1209   {
1210     m_planeTransformed.copy(planepts[0], planepts[1], planepts[2]);
1211     m_observer->planeChanged();
1212   }
1213
1214   /// \brief Reverts the transformable state of the brush to identity.
1215   void revertTransform()
1216   {
1217     m_planeTransformed = m_plane;
1218     planepts_assign(m_move_planeptsTransformed, m_move_planepts);
1219     m_texdefTransformed = m_texdef.m_projection;
1220   }
1221   void freezeTransform()
1222   {
1223     undoSave();
1224     m_plane = m_planeTransformed;
1225     planepts_assign(m_move_planepts, m_move_planeptsTransformed);
1226     m_texdef.m_projection = m_texdefTransformed;
1227   }
1228
1229   void update_move_planepts_vertex(std::size_t index, PlanePoints planePoints)
1230   {
1231     std::size_t numpoints = getWinding().numpoints;
1232     ASSERT_MESSAGE(index < numpoints, "update_move_planepts_vertex: invalid index");
1233
1234     std::size_t opposite = Winding_Opposite(getWinding(), index);
1235     std::size_t adjacent = Winding_wrap(getWinding(), opposite+numpoints-1);
1236     planePoints[0] = getWinding()[opposite].vertex;
1237     planePoints[1] = getWinding()[index].vertex;
1238     planePoints[2] = getWinding()[adjacent].vertex;
1239     // winding points are very inaccurate, so they must be quantised before using them to generate the face-plane
1240     planepts_quantise(planePoints, GRID_MIN);
1241   }
1242
1243   void snapto(float snap)
1244   {
1245     if(contributes())
1246     {
1247 #if 0
1248       ASSERT_MESSAGE(plane3_valid(m_plane.plane3()), "invalid plane before snap to grid");
1249       planepts_snap(m_plane.planePoints(), snap);
1250       ASSERT_MESSAGE(plane3_valid(m_plane.plane3()), "invalid plane after snap to grid");
1251 #else
1252       PlanePoints planePoints;
1253       update_move_planepts_vertex(0, planePoints);
1254       vector3_snap(planePoints[0], snap);
1255       vector3_snap(planePoints[1], snap);
1256       vector3_snap(planePoints[2], snap);
1257       assign_planepts(planePoints);
1258       freezeTransform();
1259 #endif
1260       SceneChangeNotify();
1261       if(!plane3_valid(m_plane.plane3()))
1262       {
1263         globalErrorStream() << "WARNING: invalid plane after snap to grid\n";
1264       }
1265     }
1266   }
1267
1268   void testSelect(SelectionTest& test, SelectionIntersection& best)
1269   {
1270     Winding_testSelect(m_winding, test, best);
1271   }
1272
1273   void testSelect_centroid(SelectionTest& test, SelectionIntersection& best)
1274   {
1275     test.TestPoint(m_centroid, best);
1276   }
1277
1278   void shaderChanged()
1279   {
1280     EmitTextureCoordinates();
1281     Brush_textureChanged();
1282     m_observer->shaderChanged();
1283     updateFiltered();
1284         planeChanged();
1285     SceneChangeNotify();
1286   }
1287
1288   const char* GetShader() const
1289   {
1290     return m_shader.getShader();
1291   }
1292   void SetShader(const char* name)
1293   {
1294     undoSave();
1295     m_shader.setShader(name);
1296     shaderChanged();
1297   }
1298
1299   void revertTexdef()
1300   {
1301     m_texdefTransformed = m_texdef.m_projection;
1302   }
1303   void texdefChanged()
1304   {
1305     revertTexdef();
1306     EmitTextureCoordinates();
1307     Brush_textureChanged();
1308   }
1309
1310   void GetTexdef(TextureProjection& projection) const
1311   {
1312     projection = m_texdef.normalised();
1313   }
1314   void SetTexdef(const TextureProjection& projection)
1315   {
1316     undoSave();
1317     m_texdef.setTexdef(projection);
1318     texdefChanged();
1319   }
1320
1321   void GetFlags(ContentsFlagsValue& flags) const
1322   {
1323     flags = m_shader.getFlags();
1324   }
1325   void SetFlags(const ContentsFlagsValue& flags)
1326   {
1327     undoSave();
1328     m_shader.setFlags(flags);
1329     m_observer->shaderChanged();
1330     updateFiltered();
1331   }
1332
1333   void ShiftTexdef(float s, float t)
1334   {
1335     undoSave();
1336     m_texdef.shift(s, t);
1337     texdefChanged();
1338   }
1339
1340   void ScaleTexdef(float s, float t)
1341   {
1342     undoSave();
1343     m_texdef.scale(s, t);
1344     texdefChanged();
1345   }
1346
1347   void RotateTexdef(float angle)
1348   {
1349     undoSave();
1350     m_texdef.rotate(angle);
1351     texdefChanged();
1352   }
1353
1354   void FitTexture(float s_repeat, float t_repeat)
1355   {
1356     undoSave();
1357     m_texdef.fit(m_plane.plane3().normal(), m_winding, s_repeat, t_repeat);
1358     texdefChanged();
1359   }
1360
1361   void EmitTextureCoordinates()
1362   {
1363     Texdef_EmitTextureCoordinates(m_texdefTransformed, m_shader.width(), m_shader.height(), m_winding, plane3().normal(), g_matrix4_identity);
1364   }
1365
1366
1367   const Vector3& centroid() const
1368   {
1369     return m_centroid;
1370   }
1371
1372   void construct_centroid()
1373   {
1374     Winding_Centroid(m_winding, plane3(), m_centroid);
1375   }
1376
1377   const Winding& getWinding() const
1378   {
1379     return m_winding;
1380   }
1381   Winding& getWinding()
1382   {
1383     return m_winding;
1384   }
1385
1386   const Plane3& plane3() const
1387   {
1388     m_observer->evaluateTransform();
1389     return m_planeTransformed.plane3();
1390   }
1391   FacePlane& getPlane()
1392   {
1393     return m_plane;
1394   }
1395   const FacePlane& getPlane() const
1396   {
1397     return m_plane;
1398   }
1399   FaceTexdef& getTexdef()
1400   {
1401     return m_texdef;
1402   }
1403   const FaceTexdef& getTexdef() const
1404   {
1405     return m_texdef;
1406   }
1407   FaceShader& getShader()
1408   {
1409     return m_shader;
1410   }
1411   const FaceShader& getShader() const
1412   {
1413     return m_shader;
1414   }
1415
1416   bool isDetail() const
1417   {
1418     return (m_shader.m_flags.m_contentFlags & BRUSH_DETAIL_MASK) != 0;
1419   }
1420   void setDetail(bool detail)
1421   {
1422     undoSave();
1423     if(detail && !isDetail())
1424     {
1425       m_shader.m_flags.m_contentFlags |= BRUSH_DETAIL_MASK;
1426     }
1427     else if(!detail && isDetail())
1428     {
1429       m_shader.m_flags.m_contentFlags &= ~BRUSH_DETAIL_MASK;
1430     }
1431     m_observer->shaderChanged();
1432   }
1433
1434   bool contributes() const
1435   {
1436     return m_winding.numpoints > 2;
1437   }
1438   bool is_bounded() const
1439   {
1440     for(Winding::const_iterator i = m_winding.begin(); i != m_winding.end(); ++i)
1441     {
1442       if((*i).adjacent == c_brush_maxFaces)
1443       {
1444         return false;
1445       }
1446     }
1447     return true;
1448   }
1449 };
1450
1451
1452 class FaceVertexId
1453 {
1454   std::size_t m_face;
1455   std::size_t m_vertex;
1456
1457 public:
1458   FaceVertexId(std::size_t face, std::size_t vertex)
1459     : m_face(face), m_vertex(vertex)
1460   {
1461   }
1462
1463   std::size_t getFace() const
1464   {
1465     return m_face;
1466   }
1467   std::size_t getVertex() const
1468   {
1469     return m_vertex;
1470   }
1471 };
1472
1473 typedef std::size_t faceIndex_t;
1474
1475 struct EdgeRenderIndices
1476 {
1477   RenderIndex first;
1478   RenderIndex second;
1479
1480   EdgeRenderIndices()
1481     : first(0), second(0)
1482   {
1483   }
1484   EdgeRenderIndices(const RenderIndex _first, const RenderIndex _second)
1485     : first(_first), second(_second)
1486   {
1487   }
1488 };
1489
1490 struct EdgeFaces
1491 {
1492   faceIndex_t first;
1493   faceIndex_t second;
1494
1495   EdgeFaces()
1496     : first(c_brush_maxFaces), second(c_brush_maxFaces)
1497   {
1498   }
1499   EdgeFaces(const faceIndex_t _first, const faceIndex_t _second)
1500     : first(_first), second(_second)
1501   {
1502   }
1503 };
1504
1505 class RenderableWireframe : public OpenGLRenderable
1506 {
1507 public:
1508   void render(RenderStateFlags state) const
1509   {
1510 #if 1
1511     glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_vertices->colour);
1512     glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_vertices->vertex);
1513     glDrawElements(GL_LINES, GLsizei(m_size<<1), RenderIndexTypeID, m_faceVertex.data());
1514 #else
1515     glBegin(GL_LINES);
1516     for(std::size_t i = 0; i < m_size; ++i)
1517     {
1518       glVertex3fv(&m_vertices[m_faceVertex[i].first].vertex.x);
1519       glVertex3fv(&m_vertices[m_faceVertex[i].second].vertex.x);
1520     }
1521     glEnd();
1522 #endif
1523   }
1524
1525   Array<EdgeRenderIndices> m_faceVertex;
1526   std::size_t m_size;
1527   const PointVertex* m_vertices;
1528 };
1529
1530 class Brush;
1531 typedef std::vector<Brush*> brush_vector_t;
1532
1533 class BrushFilter
1534 {
1535 public:
1536   virtual bool filter(const Brush& brush) const = 0;
1537 };
1538
1539 bool brush_filtered(Brush& brush);
1540 void add_brush_filter(BrushFilter& filter, int mask, bool invert = false);
1541
1542
1543 /// \brief Returns true if 'self' takes priority when building brush b-rep.
1544 inline bool plane3_inside(const Plane3& self, const Plane3& other)
1545 {
1546   if(vector3_equal_epsilon(self.normal(), other.normal(), 0.001))
1547   {
1548     return self.dist() < other.dist();
1549   }
1550   return true;
1551 }
1552
1553 typedef SmartPointer<Face> FaceSmartPointer;
1554 typedef std::vector<FaceSmartPointer> Faces;
1555
1556 /// \brief Returns the unique-id of the edge adjacent to \p faceVertex in the edge-pair for the set of \p faces.
1557 inline FaceVertexId next_edge(const Faces& faces, FaceVertexId faceVertex)
1558 {
1559   std::size_t adjacent_face = faces[faceVertex.getFace()]->getWinding()[faceVertex.getVertex()].adjacent;
1560   std::size_t adjacent_vertex = Winding_FindAdjacent(faces[adjacent_face]->getWinding(), faceVertex.getFace());
1561
1562   ASSERT_MESSAGE(adjacent_vertex != c_brush_maxFaces, "connectivity data invalid");
1563   if(adjacent_vertex == c_brush_maxFaces)
1564   {
1565     return faceVertex;
1566   }
1567
1568   return FaceVertexId(adjacent_face, adjacent_vertex);
1569 }
1570
1571 /// \brief Returns the unique-id of the vertex adjacent to \p faceVertex in the vertex-ring for the set of \p faces.
1572 inline FaceVertexId next_vertex(const Faces& faces, FaceVertexId faceVertex)
1573 {
1574   FaceVertexId nextEdge = next_edge(faces, faceVertex);
1575   return FaceVertexId(nextEdge.getFace(), Winding_next(faces[nextEdge.getFace()]->getWinding(), nextEdge.getVertex()));
1576 }
1577
1578 class SelectableEdge
1579 {
1580   Vector3 getEdge() const
1581   {
1582     const Winding& winding = getFace().getWinding();
1583     return vector3_mid(winding[m_faceVertex.getVertex()].vertex, winding[Winding_next(winding, m_faceVertex.getVertex())].vertex);
1584   }
1585
1586 public:
1587   Faces& m_faces;
1588   FaceVertexId m_faceVertex;
1589
1590   SelectableEdge(Faces& faces, FaceVertexId faceVertex)
1591     : m_faces(faces), m_faceVertex(faceVertex)
1592   {
1593   }
1594   SelectableEdge& operator=(const SelectableEdge& other)
1595   {
1596     m_faceVertex = other.m_faceVertex;
1597     return *this;
1598   }
1599
1600   Face& getFace() const
1601   {
1602     return *m_faces[m_faceVertex.getFace()];
1603   }
1604
1605   void testSelect(SelectionTest& test, SelectionIntersection& best)
1606   {
1607     test.TestPoint(getEdge(), best);
1608   }
1609 };
1610
1611 class SelectableVertex
1612 {
1613   Vector3 getVertex() const
1614   {
1615     return getFace().getWinding()[m_faceVertex.getVertex()].vertex;
1616   }
1617
1618 public:
1619   Faces& m_faces;
1620   FaceVertexId m_faceVertex;
1621
1622   SelectableVertex(Faces& faces, FaceVertexId faceVertex)
1623     : m_faces(faces), m_faceVertex(faceVertex)
1624   {
1625   }
1626   SelectableVertex& operator=(const SelectableVertex& other)
1627   {
1628     m_faceVertex = other.m_faceVertex;
1629     return *this;
1630   }
1631
1632   Face& getFace() const
1633   {
1634     return *m_faces[m_faceVertex.getFace()];
1635   }
1636
1637   void testSelect(SelectionTest& test, SelectionIntersection& best)
1638   {
1639     test.TestPoint(getVertex(), best);
1640   }
1641 };
1642
1643 class BrushObserver
1644 {
1645 public:
1646   virtual void reserve(std::size_t size) = 0;
1647   virtual void clear() = 0;
1648   virtual void push_back(Face& face) = 0;
1649   virtual void pop_back() = 0;
1650   virtual void erase(std::size_t index) = 0;
1651   virtual void connectivityChanged() = 0;
1652
1653   virtual void edge_clear() = 0;
1654   virtual void edge_push_back(SelectableEdge& edge) = 0;
1655
1656   virtual void vertex_clear() = 0;
1657   virtual void vertex_push_back(SelectableVertex& vertex) = 0;
1658
1659   virtual void DEBUG_verify() const = 0;
1660 };
1661
1662 class BrushVisitor
1663 {
1664 public:
1665   virtual void visit(Face& face) const = 0;
1666 };
1667
1668 class Brush :
1669   public TransformNode,
1670   public Bounded,
1671   public Cullable,
1672   public Snappable,
1673   public Undoable,
1674   public FaceObserver,
1675   public Filterable,
1676   public Nameable,
1677   public BrushDoom3
1678 {
1679 private:
1680   scene::Node* m_node;
1681   typedef UniqueSet<BrushObserver*> Observers;
1682   Observers m_observers;
1683   UndoObserver* m_undoable_observer;
1684   MapFile* m_map;
1685
1686   // state
1687   Faces m_faces;
1688   // ----
1689
1690   // cached data compiled from state
1691   Array<PointVertex> m_faceCentroidPoints;
1692   RenderablePointArray m_render_faces;
1693
1694   Array<PointVertex> m_uniqueVertexPoints;
1695   typedef std::vector<SelectableVertex> SelectableVertices;
1696   SelectableVertices m_select_vertices;
1697   RenderablePointArray m_render_vertices;
1698
1699   Array<PointVertex> m_uniqueEdgePoints;
1700   typedef std::vector<SelectableEdge> SelectableEdges;
1701   SelectableEdges m_select_edges;
1702   RenderablePointArray m_render_edges;
1703
1704   Array<EdgeRenderIndices> m_edge_indices;
1705   Array<EdgeFaces> m_edge_faces;
1706
1707   AABB m_aabb_local;
1708   // ----
1709
1710   Callback m_evaluateTransform;
1711   Callback m_boundsChanged;
1712
1713   mutable bool m_planeChanged; // b-rep evaluation required
1714   mutable bool m_transformChanged; // transform evaluation required
1715   // ----
1716
1717 public:
1718   STRING_CONSTANT(Name, "Brush");
1719
1720   Callback m_lightsChanged;
1721
1722   // static data
1723   static Shader* m_state_point;
1724   // ----
1725
1726   static EBrushType m_type;
1727   static double m_maxWorldCoord;
1728
1729   Brush(scene::Node& node, const Callback& evaluateTransform, const Callback& boundsChanged) :
1730     m_node(&node),
1731     m_undoable_observer(0),
1732     m_map(0),
1733     m_render_faces(m_faceCentroidPoints, GL_POINTS),
1734     m_render_vertices(m_uniqueVertexPoints, GL_POINTS),
1735     m_render_edges(m_uniqueEdgePoints, GL_POINTS),
1736     m_evaluateTransform(evaluateTransform),
1737     m_boundsChanged(boundsChanged),
1738     m_planeChanged(false),
1739     m_transformChanged(false)
1740   {
1741     planeChanged();
1742   }
1743   Brush(const Brush& other, scene::Node& node, const Callback& evaluateTransform, const Callback& boundsChanged) :
1744     m_node(&node),
1745     m_undoable_observer(0),
1746     m_map(0),
1747     m_render_faces(m_faceCentroidPoints, GL_POINTS),
1748     m_render_vertices(m_uniqueVertexPoints, GL_POINTS),
1749     m_render_edges(m_uniqueEdgePoints, GL_POINTS),
1750     m_evaluateTransform(evaluateTransform),
1751     m_boundsChanged(boundsChanged),
1752     m_planeChanged(false),
1753     m_transformChanged(false)
1754   {
1755     copy(other);
1756   }
1757   Brush(const Brush& other) :
1758     TransformNode(other),
1759     Bounded(other),
1760     Cullable(other),
1761     Snappable(),
1762     Undoable(other),
1763     FaceObserver(other),
1764     Filterable(other),
1765     Nameable(other),
1766     BrushDoom3(other),
1767     m_node(0),
1768     m_undoable_observer(0),
1769     m_map(0),
1770     m_render_faces(m_faceCentroidPoints, GL_POINTS),
1771     m_render_vertices(m_uniqueVertexPoints, GL_POINTS),
1772     m_render_edges(m_uniqueEdgePoints, GL_POINTS),
1773     m_planeChanged(false),
1774     m_transformChanged(false)
1775   {
1776     copy(other);
1777   }
1778   ~Brush()
1779   {
1780     ASSERT_MESSAGE(m_observers.empty(), "Brush::~Brush: observers still attached");
1781   }
1782
1783   // assignment not supported
1784   Brush& operator=(const Brush& other);
1785
1786   void setDoom3GroupOrigin(const Vector3& origin)
1787   {
1788     //globalOutputStream() << "func_static origin before: " << m_funcStaticOrigin << " after: " << origin << "\n";
1789     for(Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1790     {
1791       (*i)->getPlane().m_funcStaticOrigin = origin;
1792       (*i)->getPlane().updateTranslated();
1793       (*i)->planeChanged();
1794     }
1795     planeChanged();
1796   }
1797
1798   void attach(BrushObserver& observer)
1799   {
1800     for(Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1801     {
1802       observer.push_back(*(*i));
1803     }
1804
1805     for(SelectableEdges::iterator i = m_select_edges.begin(); i !=m_select_edges.end(); ++i)
1806     {
1807       observer.edge_push_back(*i);
1808     }
1809
1810     for(SelectableVertices::iterator i = m_select_vertices.begin(); i != m_select_vertices.end(); ++i)
1811     {
1812       observer.vertex_push_back(*i);
1813     }
1814
1815     m_observers.insert(&observer);
1816   }
1817   void detach(BrushObserver& observer)
1818   {
1819     m_observers.erase(&observer);
1820   }
1821
1822   void forEachFace(const BrushVisitor& visitor) const
1823   {
1824     for(Faces::const_iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1825     {
1826       visitor.visit(*(*i));
1827     }
1828   }
1829
1830   void forEachFace_instanceAttach(MapFile* map) const
1831   {
1832     for(Faces::const_iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1833     {
1834       (*i)->instanceAttach(map);
1835     }
1836   }
1837   void forEachFace_instanceDetach(MapFile* map) const
1838   {
1839     for(Faces::const_iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1840     {
1841       (*i)->instanceDetach(map);
1842     }
1843   }
1844
1845   InstanceCounter m_instanceCounter;
1846   void instanceAttach(const scene::Path& path)
1847   {
1848     if(++m_instanceCounter.m_count == 1)
1849     {
1850       m_map = path_find_mapfile(path.begin(), path.end());
1851       m_undoable_observer = GlobalUndoSystem().observer(this);
1852       GlobalFilterSystem().registerFilterable(*this);
1853       forEachFace_instanceAttach(m_map);
1854     }
1855     else
1856     {
1857       ASSERT_MESSAGE(path_find_mapfile(path.begin(), path.end()) == m_map, "node is instanced across more than one file");
1858     }
1859   }
1860   void instanceDetach(const scene::Path& path)
1861   {
1862     if(--m_instanceCounter.m_count == 0)
1863     {
1864       forEachFace_instanceDetach(m_map);
1865       GlobalFilterSystem().unregisterFilterable(*this);
1866       m_map = 0;
1867       m_undoable_observer = 0;
1868       GlobalUndoSystem().release(this);
1869     }
1870   }
1871
1872   // nameable
1873   const char* name() const
1874   {
1875     return "brush";
1876   }
1877   void attach(const NameCallback& callback)
1878   {
1879   }
1880   void detach(const NameCallback& callback)
1881   {
1882   }
1883
1884   // filterable
1885   void updateFiltered()
1886   {
1887     if(m_node != 0)
1888     {
1889       if(brush_filtered(*this))
1890       {
1891         m_node->enable(scene::Node::eFiltered);
1892       }
1893       else
1894       {
1895         m_node->disable(scene::Node::eFiltered);
1896       }
1897     }
1898   }
1899
1900   // observer
1901   void planeChanged()
1902   {
1903     m_planeChanged = true;
1904     aabbChanged();
1905     m_lightsChanged();
1906   }
1907   void shaderChanged()
1908   {
1909     updateFiltered();
1910         planeChanged();
1911   }
1912
1913   void evaluateBRep() const
1914   {
1915     if(m_planeChanged)
1916     {
1917       m_planeChanged = false;
1918       const_cast<Brush*>(this)->buildBRep();
1919     }
1920   }
1921
1922   void transformChanged()
1923   {
1924     m_transformChanged = true;
1925     planeChanged();
1926   }
1927   typedef MemberCaller<Brush, &Brush::transformChanged> TransformChangedCaller;
1928
1929   void evaluateTransform()
1930   {
1931     if(m_transformChanged)
1932     {
1933       m_transformChanged = false;
1934       revertTransform();
1935       m_evaluateTransform();
1936     }
1937   }
1938   const Matrix4& localToParent() const
1939   {
1940     return g_matrix4_identity;
1941   }
1942   void aabbChanged()
1943   {
1944     m_boundsChanged();
1945   }
1946   const AABB& localAABB() const
1947   {
1948     evaluateBRep();
1949     return m_aabb_local;
1950   }
1951
1952   VolumeIntersectionValue intersectVolume(const VolumeTest& test, const Matrix4& localToWorld) const
1953   {
1954     return test.TestAABB(m_aabb_local, localToWorld);
1955   }
1956
1957   void renderComponents(SelectionSystem::EComponentMode mode, Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
1958   {
1959     switch(mode)
1960     {
1961     case SelectionSystem::eVertex:
1962       renderer.addRenderable(m_render_vertices, localToWorld);
1963       break;
1964     case SelectionSystem::eEdge:
1965       renderer.addRenderable(m_render_edges, localToWorld);
1966       break;
1967     case SelectionSystem::eFace:
1968       renderer.addRenderable(m_render_faces, localToWorld);
1969       break;
1970     default:
1971       break;
1972     }
1973   }
1974
1975   void transform(const Matrix4& matrix)
1976   {
1977     bool mirror = matrix4_handedness(matrix) == MATRIX4_LEFTHANDED;
1978
1979     for(Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1980     {
1981       (*i)->transform(matrix, mirror);
1982     }
1983   }
1984   void snapto(float snap)
1985   {
1986     for(Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1987     {
1988       (*i)->snapto(snap);
1989     }
1990   }
1991   void revertTransform()
1992   {
1993     for(Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i)
1994     {
1995       (*i)->revertTransform();
1996     }
1997   }
1998   void freezeTransform()
1999   {
2000     for(Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i)
2001     {
2002       (*i)->freezeTransform();
2003     }
2004   }
2005
2006   /// \brief Returns the absolute index of the \p faceVertex.
2007   std::size_t absoluteIndex(FaceVertexId faceVertex)
2008   {
2009     std::size_t index = 0;
2010     for(std::size_t i = 0; i < faceVertex.getFace(); ++i)
2011     {
2012       index += m_faces[i]->getWinding().numpoints;
2013     }
2014     return index + faceVertex.getVertex();
2015   }
2016
2017   void appendFaces(const Faces& other)
2018   {
2019     clear();
2020     for(Faces::const_iterator i = other.begin(); i != other.end(); ++i)
2021     {
2022       push_back(*i);
2023     }
2024   }
2025
2026   /// \brief The undo memento for a brush stores only the list of face references - the faces are not copied.
2027   class BrushUndoMemento : public UndoMemento
2028   {
2029   public:
2030     BrushUndoMemento(const Faces& faces) : m_faces(faces)
2031     {
2032     }
2033     void release()
2034     {
2035       delete this;
2036     }
2037
2038     Faces m_faces;
2039   };
2040
2041   void undoSave()
2042   {
2043     if(m_map != 0)
2044     {
2045       m_map->changed();
2046     }
2047     if(m_undoable_observer != 0)
2048     {
2049       m_undoable_observer->save(this);
2050     }
2051   }
2052
2053   UndoMemento* exportState() const
2054   {
2055     return new BrushUndoMemento(m_faces);
2056   }
2057
2058   void importState(const UndoMemento* state)
2059   {
2060     undoSave();
2061     appendFaces(static_cast<const BrushUndoMemento*>(state)->m_faces);
2062     planeChanged();
2063
2064     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2065     {
2066       (*i)->DEBUG_verify();
2067     }
2068   }
2069
2070   bool isDetail()
2071   {
2072     return !m_faces.empty() && m_faces.front()->isDetail();
2073   }
2074
2075   /// \brief Appends a copy of \p face to the end of the face list.
2076   Face* addFace(const Face& face)
2077   {
2078     if(m_faces.size() == c_brush_maxFaces)
2079     {
2080       return 0;
2081     }
2082     undoSave();
2083     push_back(FaceSmartPointer(new Face(face, this)));
2084     m_faces.back()->setDetail(isDetail());
2085     planeChanged();
2086     return m_faces.back();
2087   }
2088
2089   /// \brief Appends a new face constructed from the parameters to the end of the face list.
2090   Face* addPlane(const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection)
2091   {
2092     if(m_faces.size() == c_brush_maxFaces)
2093     {
2094       return 0;
2095     }
2096     undoSave();
2097     push_back(FaceSmartPointer(new Face(p0, p1, p2, shader, projection, this)));
2098     m_faces.back()->setDetail(isDetail());
2099     planeChanged();
2100     return m_faces.back();
2101   }
2102
2103   static void constructStatic(EBrushType type)
2104   {
2105     m_type = type;
2106     Face::m_type = type;
2107     FacePlane::m_type = type;
2108
2109     g_bp_globals.m_texdefTypeId = TEXDEFTYPEID_QUAKE;
2110     if(m_type == eBrushTypeQuake3BP || m_type == eBrushTypeDoom3 || m_type == eBrushTypeQuake4)
2111     {
2112       g_bp_globals.m_texdefTypeId = TEXDEFTYPEID_BRUSHPRIMITIVES;
2113       g_brush_texturelock_enabled = true;
2114     }
2115     else if(m_type == eBrushTypeHalfLife)
2116     {
2117       g_bp_globals.m_texdefTypeId = TEXDEFTYPEID_HALFLIFE;
2118       g_brush_texturelock_enabled = true;
2119     }
2120
2121     Face::m_quantise = (m_type == eBrushTypeQuake) ? quantiseInteger : quantiseFloating;
2122
2123     m_state_point = GlobalShaderCache().capture("$POINT");
2124   }
2125   static void destroyStatic()
2126   {
2127     GlobalShaderCache().release("$POINT");
2128   }
2129
2130   std::size_t DEBUG_size()
2131   {
2132     return m_faces.size();
2133   }
2134
2135   typedef Faces::const_iterator const_iterator;
2136
2137   const_iterator begin() const
2138   {
2139     return m_faces.begin();
2140   }
2141   const_iterator end() const
2142   {
2143     return m_faces.end();
2144   }
2145
2146   Face* back()
2147   {
2148     return m_faces.back();
2149   }
2150   const Face* back() const
2151   {
2152     return m_faces.back();
2153   }
2154   void reserve(std::size_t count)
2155   {
2156     m_faces.reserve(count);
2157     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2158     {
2159       (*i)->reserve(count);
2160     }
2161   }
2162   void push_back(Faces::value_type face)
2163   {
2164     m_faces.push_back(face);
2165     if(m_instanceCounter.m_count != 0)
2166     {
2167       m_faces.back()->instanceAttach(m_map);
2168     }
2169     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2170     {
2171       (*i)->push_back(*face);
2172       (*i)->DEBUG_verify();
2173     }
2174   }
2175   void pop_back()
2176   {
2177     if(m_instanceCounter.m_count != 0)
2178     {
2179       m_faces.back()->instanceDetach(m_map);
2180     }
2181     m_faces.pop_back();
2182     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2183     {
2184       (*i)->pop_back();
2185       (*i)->DEBUG_verify();
2186     }
2187   }
2188   void erase(std::size_t index)
2189   {
2190     if(m_instanceCounter.m_count != 0)
2191     {
2192       m_faces[index]->instanceDetach(m_map);
2193     }
2194     m_faces.erase(m_faces.begin() + index);
2195     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2196     {
2197       (*i)->erase(index);
2198       (*i)->DEBUG_verify();
2199     }
2200   }
2201   void connectivityChanged()
2202   {
2203     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2204     {
2205       (*i)->connectivityChanged();
2206     }
2207   }
2208
2209
2210   void clear()
2211   {
2212     undoSave();
2213     if(m_instanceCounter.m_count != 0)
2214     {
2215       forEachFace_instanceDetach(m_map);
2216     }
2217     m_faces.clear();
2218     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2219     {
2220       (*i)->clear();
2221       (*i)->DEBUG_verify();
2222     }
2223   }
2224   std::size_t size() const
2225   {
2226     return m_faces.size();
2227   }
2228   bool empty() const
2229   {
2230     return m_faces.empty();
2231   }
2232
2233   /// \brief Returns true if any face of the brush contributes to the final B-Rep.
2234   bool hasContributingFaces() const
2235   {
2236     for(const_iterator i = begin(); i != end(); ++i)
2237     {
2238       if((*i)->contributes())
2239       {
2240         return true;
2241       }
2242     }
2243     return false;
2244   }
2245
2246   /// \brief Removes faces that do not contribute to the brush. This is useful for cleaning up after CSG operations on the brush.
2247   /// Note: removal of empty faces is not performed during direct brush manipulations, because it would make a manipulation irreversible if it created an empty face.
2248   void removeEmptyFaces()
2249   {
2250     evaluateBRep();
2251
2252     {
2253       std::size_t i = 0;
2254       while(i < m_faces.size())
2255       {
2256         if(!m_faces[i]->contributes())
2257         {
2258           erase(i);
2259           planeChanged();
2260         }
2261         else
2262         {
2263           ++i;
2264         }
2265       }
2266     }
2267   }
2268
2269   /// \brief Constructs \p winding from the intersection of \p plane with the other planes of the brush.
2270   void windingForClipPlane(Winding& winding, const Plane3& plane) const
2271   {
2272     FixedWinding buffer[2];
2273     bool swap = false;
2274
2275     // get a poly that covers an effectively infinite area
2276     Winding_createInfinite(buffer[swap], plane, m_maxWorldCoord + 1);
2277
2278     // chop the poly by all of the other faces
2279     {
2280       for (std::size_t i = 0;  i < m_faces.size(); ++i)
2281       {
2282         const Face& clip = *m_faces[i];
2283
2284         if(plane3_equal(clip.plane3(), plane)
2285           || !plane3_valid(clip.plane3()) || !plane_unique(i)
2286           || plane3_opposing(plane, clip.plane3()))
2287         {
2288           continue;
2289         }
2290
2291         buffer[!swap].clear();
2292
2293 #if BRUSH_CONNECTIVITY_DEBUG
2294         globalOutputStream() << "clip vs face: " << i << "\n";
2295 #endif
2296
2297         {
2298           // flip the plane, because we want to keep the back side
2299           Plane3 clipPlane(vector3_negated(clip.plane3().normal()), -clip.plane3().dist());
2300           Winding_Clip(buffer[swap], plane, clipPlane, i, buffer[!swap]);
2301         }
2302
2303 #if BRUSH_CONNECTIVITY_DEBUG
2304         for(FixedWinding::Points::iterator k = buffer[!swap].points.begin(), j = buffer[!swap].points.end() - 1; k != buffer[!swap].points.end(); j = k, ++k)
2305         {
2306           if(vector3_length_squared(vector3_subtracted((*k).vertex, (*j).vertex)) < 1)
2307           {
2308             globalOutputStream() << "v: " << std::distance(buffer[!swap].points.begin(), j) << " tiny edge adjacent to face " << (*j).adjacent << "\n";
2309           }
2310         }
2311 #endif
2312
2313         //ASSERT_MESSAGE(buffer[!swap].numpoints != 1, "created single-point winding");
2314
2315         swap = !swap;
2316       }
2317     }
2318
2319     Winding_forFixedWinding(winding, buffer[swap]);
2320
2321 #if BRUSH_CONNECTIVITY_DEBUG
2322     Winding_printConnectivity(winding);
2323
2324     for(Winding::iterator i = winding.begin(), j = winding.end() - 1; i != winding.end(); j = i, ++i)
2325     {
2326       if(vector3_length_squared(vector3_subtracted((*i).vertex, (*j).vertex)) < 1)
2327       {
2328         globalOutputStream() << "v: " << std::distance(winding.begin(), j) << " tiny edge adjacent to face " << (*j).adjacent << "\n";
2329       }
2330     }
2331 #endif
2332   }
2333
2334   void update_wireframe(RenderableWireframe& wire, const bool* faces_visible) const
2335   {
2336     wire.m_faceVertex.resize(m_edge_indices.size());
2337     wire.m_vertices = m_uniqueVertexPoints.data();
2338     wire.m_size = 0;
2339     for(std::size_t i = 0; i < m_edge_faces.size(); ++i)
2340     {
2341       if(faces_visible[m_edge_faces[i].first]
2342         || faces_visible[m_edge_faces[i].second])
2343       {
2344         wire.m_faceVertex[wire.m_size++] = m_edge_indices[i];
2345       }
2346     }
2347   }
2348
2349
2350   void update_faces_wireframe(Array<PointVertex>& wire, const bool* faces_visible) const
2351   {
2352     std::size_t count = 0;
2353     for(std::size_t i = 0; i < m_faceCentroidPoints.size(); ++i)
2354     {
2355       if(faces_visible[i])
2356       {
2357         ++count;
2358       }
2359     }
2360
2361     wire.resize(count);
2362     Array<PointVertex>::iterator p = wire.begin();
2363     for(std::size_t i = 0; i < m_faceCentroidPoints.size(); ++i)
2364     {
2365       if(faces_visible[i])
2366       {
2367         *p++ = m_faceCentroidPoints[i];
2368       }
2369     }
2370   }
2371
2372   /// \brief Makes this brush a deep-copy of the \p other.
2373   void copy(const Brush& other)
2374   {
2375     for(Faces::const_iterator i = other.m_faces.begin(); i != other.m_faces.end(); ++i)
2376     {
2377       addFace(*(*i));
2378     }
2379     planeChanged();
2380   }
2381
2382 private:
2383   void edge_push_back(FaceVertexId faceVertex)
2384   {
2385     m_select_edges.push_back(SelectableEdge(m_faces, faceVertex));
2386     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2387     {
2388       (*i)->edge_push_back(m_select_edges.back());
2389     }
2390   }
2391   void edge_clear()
2392   {
2393     m_select_edges.clear();
2394     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2395     {
2396       (*i)->edge_clear();
2397     }
2398   }
2399   void vertex_push_back(FaceVertexId faceVertex)
2400   {
2401     m_select_vertices.push_back(SelectableVertex(m_faces, faceVertex));
2402     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2403     {
2404       (*i)->vertex_push_back(m_select_vertices.back());
2405     }
2406   }
2407   void vertex_clear()
2408   {
2409     m_select_vertices.clear();
2410     for(Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i)
2411     {
2412       (*i)->vertex_clear();
2413     }
2414   }
2415
2416   /// \brief Returns true if the face identified by \p index is preceded by another plane that takes priority over it.
2417   bool plane_unique(std::size_t index) const
2418   {
2419     // duplicate plane
2420     for(std::size_t i = 0; i < m_faces.size(); ++i)
2421     {
2422       if(index != i && !plane3_inside(m_faces[index]->plane3(), m_faces[i]->plane3()))
2423       {
2424         return false;
2425       }
2426     }
2427     return true;
2428   }
2429
2430   /// \brief Removes edges that are smaller than the tolerance used when generating brush windings.
2431   void removeDegenerateEdges()
2432   {
2433     for (std::size_t i = 0;  i < m_faces.size(); ++i)
2434     {
2435       Winding& winding = m_faces[i]->getWinding();
2436       for(Winding::iterator j = winding.begin(); j != winding.end();)
2437       {
2438         std::size_t index = std::distance(winding.begin(), j);
2439         std::size_t next = Winding_next(winding, index);
2440         if(Edge_isDegenerate(winding[index].vertex, winding[next].vertex))
2441         {
2442 #if BRUSH_DEGENERATE_DEBUG
2443           globalOutputStream() << "Brush::buildWindings: face " << i << ": degenerate edge adjacent to " << winding[index].adjacent << "\n";
2444 #endif
2445           Winding& other = m_faces[winding[index].adjacent]->getWinding();
2446           std::size_t adjacent = Winding_FindAdjacent(other, i);
2447           if(adjacent != c_brush_maxFaces)
2448           {
2449             other.erase(other.begin() + adjacent);
2450           }
2451           winding.erase(j);
2452         }
2453         else
2454         {
2455           ++j;
2456         }
2457       }
2458     }
2459   }
2460
2461   /// \brief Invalidates faces that have only two vertices in their winding, while preserving edge-connectivity information.
2462   void removeDegenerateFaces()
2463   {
2464     // save adjacency info for degenerate faces
2465     for (std::size_t i = 0;  i < m_faces.size(); ++i)
2466     {
2467       Winding& degen = m_faces[i]->getWinding();
2468
2469       if(degen.numpoints == 2)
2470       {
2471 #if BRUSH_DEGENERATE_DEBUG
2472         globalOutputStream() << "Brush::buildWindings: face " << i << ": degenerate winding adjacent to " << degen[0].adjacent << ", " << degen[1].adjacent << "\n";
2473 #endif
2474         // this is an "edge" face, where the plane touches the edge of the brush
2475         {
2476           Winding& winding = m_faces[degen[0].adjacent]->getWinding();
2477           std::size_t index = Winding_FindAdjacent(winding, i);
2478           if(index != c_brush_maxFaces)
2479           {
2480 #if BRUSH_DEGENERATE_DEBUG
2481             globalOutputStream() << "Brush::buildWindings: face " << degen[0].adjacent << ": remapping adjacent " << winding[index].adjacent << " to " << degen[1].adjacent << "\n";
2482 #endif
2483             winding[index].adjacent = degen[1].adjacent;
2484           }
2485         }
2486
2487         {
2488           Winding& winding = m_faces[degen[1].adjacent]->getWinding();
2489           std::size_t index = Winding_FindAdjacent(winding, i);
2490           if(index != c_brush_maxFaces)
2491           {
2492 #if BRUSH_DEGENERATE_DEBUG
2493             globalOutputStream() << "Brush::buildWindings: face " << degen[1].adjacent << ": remapping adjacent " << winding[index].adjacent << " to " << degen[0].adjacent << "\n";
2494 #endif
2495             winding[index].adjacent = degen[0].adjacent;
2496           }
2497         }
2498
2499         degen.resize(0);
2500       }
2501     }
2502   }
2503
2504   /// \brief Removes edges that have the same adjacent-face as their immediate neighbour.
2505   void removeDuplicateEdges()
2506   {
2507     // verify face connectivity graph
2508     for(std::size_t i = 0; i < m_faces.size(); ++i)
2509     {
2510       //if(m_faces[i]->contributes())
2511       {
2512         Winding& winding = m_faces[i]->getWinding();
2513         for(std::size_t j = 0; j != winding.numpoints;)
2514         {
2515           std::size_t next = Winding_next(winding, j);
2516           if(winding[j].adjacent == winding[next].adjacent)
2517           {
2518 #if BRUSH_DEGENERATE_DEBUG
2519             globalOutputStream() << "Brush::buildWindings: face " << i << ": removed duplicate edge adjacent to face " << winding[j].adjacent << "\n";
2520 #endif
2521             winding.erase(winding.begin() + next);
2522           }
2523           else
2524           {
2525             ++j;
2526           }
2527         }
2528       }
2529     }
2530   }
2531
2532   /// \brief Removes edges that do not have a matching pair in their adjacent-face.
2533   void verifyConnectivityGraph()
2534   {
2535     // verify face connectivity graph
2536     for(std::size_t i = 0; i < m_faces.size(); ++i)
2537     {
2538       //if(m_faces[i]->contributes())
2539       {
2540         Winding& winding = m_faces[i]->getWinding();
2541         for(Winding::iterator j = winding.begin(); j != winding.end();)
2542         {
2543 #if BRUSH_CONNECTIVITY_DEBUG
2544           globalOutputStream() << "Brush::buildWindings: face " << i << ": adjacent to face " << (*j).adjacent << "\n";
2545 #endif
2546           // remove unidirectional graph edges
2547           if((*j).adjacent == c_brush_maxFaces
2548             || Winding_FindAdjacent(m_faces[(*j).adjacent]->getWinding(), i) == c_brush_maxFaces)
2549           {
2550 #if BRUSH_CONNECTIVITY_DEBUG
2551             globalOutputStream() << "Brush::buildWindings: face " << i << ": removing unidirectional connectivity graph edge adjacent to face " << (*j).adjacent << "\n";
2552 #endif
2553             winding.erase(j);
2554           }
2555           else
2556           {
2557             ++j;
2558           }
2559         }
2560       }
2561     }
2562   }
2563
2564   /// \brief Returns true if the brush is a finite volume. A brush without a finite volume extends past the maximum world bounds and is not valid.
2565   bool isBounded()
2566   {
2567     for(const_iterator i = begin(); i != end(); ++i)
2568     {
2569       if(!(*i)->is_bounded())
2570       {
2571         return false;
2572       }
2573     }
2574     return true;
2575   }
2576
2577   /// \brief Constructs the polygon windings for each face of the brush. Also updates the brush bounding-box and face texture-coordinates.
2578   bool buildWindings()
2579   {
2580
2581     {
2582       m_aabb_local = AABB();
2583
2584       for (std::size_t i = 0;  i < m_faces.size(); ++i)
2585       {
2586         Face& f = *m_faces[i];
2587
2588         if(!plane3_valid(f.plane3()) || !plane_unique(i))
2589         {
2590           f.getWinding().resize(0);
2591         }
2592         else
2593         {
2594 #if BRUSH_CONNECTIVITY_DEBUG
2595           globalOutputStream() << "face: " << i << "\n";
2596 #endif
2597           windingForClipPlane(f.getWinding(), f.plane3());
2598
2599           // update brush bounds
2600           const Winding& winding = f.getWinding();
2601           for(Winding::const_iterator i = winding.begin(); i != winding.end(); ++i)
2602           {
2603             aabb_extend_by_point_safe(m_aabb_local, (*i).vertex);
2604           }
2605
2606           // update texture coordinates
2607           f.EmitTextureCoordinates();
2608         }
2609       }
2610     }
2611
2612     bool degenerate = !isBounded();
2613
2614     if(!degenerate)
2615     {
2616       // clean up connectivity information.
2617       // these cleanups must be applied in a specific order.
2618       removeDegenerateEdges();
2619       removeDegenerateFaces();
2620       removeDuplicateEdges();
2621       verifyConnectivityGraph();
2622     }
2623
2624     return degenerate;
2625   }
2626
2627   /// \brief Constructs the face windings and updates anything that depends on them.
2628   void buildBRep();
2629 };
2630
2631
2632
2633 class FaceInstance;
2634
2635 class FaceInstanceSet
2636 {
2637   typedef SelectionList<FaceInstance> FaceInstances;
2638   FaceInstances m_faceInstances;
2639 public:
2640   void insert(FaceInstance& faceInstance)
2641   {
2642     m_faceInstances.append(faceInstance);
2643   }
2644   void erase(FaceInstance& faceInstance)
2645   {
2646     m_faceInstances.erase(faceInstance);
2647   }
2648
2649   template<typename Functor>
2650   void foreach(Functor functor)
2651   {
2652     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
2653     {
2654       functor(*(*i));
2655     }
2656   }
2657
2658   bool empty() const
2659   {
2660     return m_faceInstances.empty();
2661   }
2662   FaceInstance& last() const
2663   {
2664     return m_faceInstances.back();
2665   }
2666 };
2667
2668 extern FaceInstanceSet g_SelectedFaceInstances;
2669
2670 typedef std::list<std::size_t> VertexSelection;
2671
2672 inline VertexSelection::iterator VertexSelection_find(VertexSelection& self, std::size_t value)
2673 {
2674   return std::find(self.begin(), self.end(), value);
2675 }
2676
2677 inline VertexSelection::const_iterator VertexSelection_find(const VertexSelection& self, std::size_t value)
2678 {
2679   return std::find(self.begin(), self.end(), value);
2680 }
2681
2682 inline VertexSelection::iterator VertexSelection_insert(VertexSelection& self, std::size_t value)
2683 {
2684   VertexSelection::iterator i = VertexSelection_find(self, value);
2685   if(i == self.end())
2686   {
2687     self.push_back(value);
2688     return --self.end();
2689   }
2690   return i;
2691 }
2692 inline void VertexSelection_erase(VertexSelection& self, std::size_t value)
2693 {
2694   VertexSelection::iterator i = VertexSelection_find(self, value);
2695   if(i != self.end())
2696   {
2697     self.erase(i);
2698   }
2699 }
2700
2701 inline bool triangle_reversed(std::size_t x, std::size_t y, std::size_t z)
2702 {
2703   return !((x < y && y < z) || (z < x && x < y) || (y < z && z < x));
2704 }
2705 template<typename Element>
2706 inline Vector3 triangle_cross(const BasicVector3<Element>& x, const BasicVector3<Element> y, const BasicVector3<Element>& z)
2707 {
2708   return vector3_cross(y - x, z - x);
2709 }
2710 template<typename Element>
2711 inline bool triangles_same_winding(const BasicVector3<Element>& x1, const BasicVector3<Element> y1, const BasicVector3<Element>& z1, const BasicVector3<Element>& x2, const BasicVector3<Element> y2, const BasicVector3<Element>& z2)
2712 {
2713   return vector3_dot(triangle_cross(x1, y1, z1), triangle_cross(x2, y2, z2)) > 0;
2714 }
2715
2716
2717 typedef const Plane3* PlanePointer;
2718 typedef PlanePointer* PlanesIterator;
2719
2720 class VectorLightList : public LightList
2721 {
2722   typedef std::vector<const RendererLight*> Lights;
2723   Lights m_lights;
2724 public:
2725   void addLight(const RendererLight& light)
2726   {
2727     m_lights.push_back(&light);
2728   }
2729   void clear()
2730   {
2731     m_lights.clear();
2732   }
2733   void evaluateLights() const
2734   {
2735   }
2736   void lightsChanged() const
2737   {
2738   }
2739   void forEachLight(const RendererLightCallback& callback) const
2740   {
2741     for(Lights::const_iterator i = m_lights.begin(); i != m_lights.end(); ++i)
2742     {
2743       callback(*(*i));
2744     }
2745   }
2746 };
2747
2748 class FaceInstance
2749 {
2750   Face* m_face;
2751   ObservedSelectable m_selectable;
2752   ObservedSelectable m_selectableVertices;
2753   ObservedSelectable m_selectableEdges;
2754   SelectionChangeCallback m_selectionChanged;
2755
2756   VertexSelection m_vertexSelection;
2757   VertexSelection m_edgeSelection;
2758
2759 public:
2760   mutable VectorLightList m_lights;
2761
2762   FaceInstance(Face& face, const SelectionChangeCallback& observer) :
2763     m_face(&face),
2764     m_selectable(SelectedChangedCaller(*this)),
2765     m_selectableVertices(observer),
2766     m_selectableEdges(observer),
2767     m_selectionChanged(observer)
2768   {
2769   }
2770   FaceInstance(const FaceInstance& other) :
2771     m_face(other.m_face),
2772     m_selectable(SelectedChangedCaller(*this)),
2773     m_selectableVertices(other.m_selectableVertices),
2774     m_selectableEdges(other.m_selectableEdges),
2775     m_selectionChanged(other.m_selectionChanged)
2776   {
2777   }
2778   FaceInstance& operator=(const FaceInstance& other)
2779   {
2780     m_face = other.m_face;
2781     return *this;
2782   }
2783
2784   Face& getFace()
2785   {
2786     return *m_face;
2787   }
2788   const Face& getFace() const
2789   {
2790     return *m_face;
2791   }
2792
2793   void selectedChanged(const Selectable& selectable)
2794   {
2795     if(selectable.isSelected())
2796     {
2797       g_SelectedFaceInstances.insert(*this);
2798     }
2799     else
2800     {
2801       g_SelectedFaceInstances.erase(*this);
2802     }
2803     m_selectionChanged(selectable);
2804   }
2805   typedef MemberCaller1<FaceInstance, const Selectable&, &FaceInstance::selectedChanged> SelectedChangedCaller;
2806
2807   bool selectedVertices() const
2808   {
2809     return !m_vertexSelection.empty();
2810   }
2811   bool selectedEdges() const
2812   {
2813     return !m_edgeSelection.empty();
2814   }
2815   bool isSelected() const
2816   {
2817     return m_selectable.isSelected();
2818   }
2819
2820   bool selectedComponents() const
2821   {
2822     return selectedVertices() || selectedEdges() || isSelected();
2823   }
2824   bool selectedComponents(SelectionSystem::EComponentMode mode) const
2825   {
2826     switch(mode)
2827     {
2828     case SelectionSystem::eVertex:
2829       return selectedVertices();
2830     case SelectionSystem::eEdge:
2831       return selectedEdges();
2832     case SelectionSystem::eFace:
2833       return isSelected();
2834     default:
2835       return false;
2836     }
2837   }
2838   void setSelected(SelectionSystem::EComponentMode mode, bool select)
2839   {
2840     switch(mode)
2841     {
2842     case SelectionSystem::eFace:
2843       m_selectable.setSelected(select);
2844       break;
2845     case SelectionSystem::eVertex:
2846       ASSERT_MESSAGE(!select, "select-all not supported");
2847
2848       m_vertexSelection.clear();
2849       m_selectableVertices.setSelected(false);
2850       break;
2851     case SelectionSystem::eEdge:
2852       ASSERT_MESSAGE(!select, "select-all not supported");
2853
2854       m_edgeSelection.clear();
2855       m_selectableEdges.setSelected(false);
2856       break;
2857     default:
2858       break;
2859     }
2860   }
2861
2862   template<typename Functor>
2863   void SelectedVertices_foreach(Functor functor) const
2864   {
2865     for(VertexSelection::const_iterator i = m_vertexSelection.begin(); i != m_vertexSelection.end(); ++i)
2866     {
2867       std::size_t index = Winding_FindAdjacent(getFace().getWinding(), *i);
2868       if(index != c_brush_maxFaces)
2869       {
2870         functor(getFace().getWinding()[index].vertex);
2871       }
2872     }
2873   }
2874   template<typename Functor>
2875   void SelectedEdges_foreach(Functor functor) const
2876   {
2877     for(VertexSelection::const_iterator i = m_edgeSelection.begin(); i != m_edgeSelection.end(); ++i)
2878     {
2879       std::size_t index = Winding_FindAdjacent(getFace().getWinding(), *i);
2880       if(index != c_brush_maxFaces)
2881       {
2882         const Winding& winding = getFace().getWinding();
2883         std::size_t adjacent = Winding_next(winding, index);
2884         functor(vector3_mid(winding[index].vertex, winding[adjacent].vertex));
2885       }
2886     }
2887   }
2888   template<typename Functor>
2889   void SelectedFaces_foreach(Functor functor) const
2890   {
2891     if(isSelected())
2892     {
2893       functor(centroid());
2894     }
2895   }
2896
2897   template<typename Functor>
2898   void SelectedComponents_foreach(Functor functor) const
2899   {
2900     SelectedVertices_foreach(functor);
2901     SelectedEdges_foreach(functor);
2902     SelectedFaces_foreach(functor);
2903   }
2904
2905   void iterate_selected(AABB& aabb) const
2906   {
2907     SelectedComponents_foreach(AABBExtendByPoint(aabb));
2908   }
2909
2910   class RenderablePointVectorPushBack
2911   {
2912     RenderablePointVector& m_points;
2913   public:
2914     RenderablePointVectorPushBack(RenderablePointVector& points) : m_points(points)
2915     {
2916     }
2917     void operator()(const Vector3& point) const
2918     {
2919       const Colour4b colour_selected(0, 0, 255, 255);
2920       m_points.push_back(pointvertex_for_windingpoint(point, colour_selected));
2921     }
2922   };
2923
2924   void iterate_selected(RenderablePointVector& points) const
2925   {
2926     SelectedComponents_foreach(RenderablePointVectorPushBack(points));
2927   }
2928
2929   bool intersectVolume(const VolumeTest& volume, const Matrix4& localToWorld) const
2930   {
2931     return m_face->intersectVolume(volume, localToWorld);
2932   }
2933
2934   void render(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
2935   {
2936     if(!m_face->isFiltered() && m_face->contributes() && intersectVolume(volume, localToWorld))
2937     {
2938       renderer.PushState();
2939       if(selectedComponents())
2940       {
2941         renderer.Highlight(Renderer::eFace);
2942       }
2943       m_face->render(renderer, localToWorld);
2944       renderer.PopState();
2945     }
2946   }
2947
2948   void testSelect(SelectionTest& test, SelectionIntersection& best)
2949   {
2950     if(!m_face->isFiltered())
2951     {
2952       m_face->testSelect(test, best);
2953     }
2954   }
2955   void testSelect(Selector& selector, SelectionTest& test)
2956   {
2957     SelectionIntersection best;
2958     testSelect(test, best);
2959     if(best.valid())
2960     {
2961       Selector_add(selector, m_selectable, best);
2962     }
2963   }
2964   void testSelect_centroid(Selector& selector, SelectionTest& test)
2965   {
2966     if(m_face->contributes() && !m_face->isFiltered())
2967     {
2968       SelectionIntersection best;
2969       m_face->testSelect_centroid(test, best);
2970       if(best.valid())
2971       {
2972         Selector_add(selector, m_selectable, best);
2973       }
2974     }
2975   }
2976
2977   void selectPlane(Selector& selector, const Line& line, PlanesIterator first, PlanesIterator last, const PlaneCallback& selectedPlaneCallback)
2978   {
2979     for(Winding::const_iterator i = getFace().getWinding().begin(); i != getFace().getWinding().end(); ++i)
2980     {
2981       Vector3 v(vector3_subtracted(line_closest_point(line, (*i).vertex), (*i).vertex));
2982       double dot = vector3_dot(getFace().plane3().normal(), v);
2983       if(dot <= 0)
2984       {
2985         return;
2986       }
2987     }
2988
2989     Selector_add(selector, m_selectable);
2990
2991     selectedPlaneCallback(getFace().plane3());
2992   }
2993   void selectReversedPlane(Selector& selector, const SelectedPlanes& selectedPlanes)
2994   {
2995     if(selectedPlanes.contains(plane3_flipped(getFace().plane3())))
2996     {
2997       Selector_add(selector, m_selectable);
2998     }
2999   }
3000
3001   void transformComponents(const Matrix4& matrix)
3002   {
3003     if(isSelected())
3004     {
3005       m_face->transform(matrix, false);
3006     }
3007     if(selectedVertices())
3008     {
3009       if(m_vertexSelection.size() == 1)
3010       {
3011         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[1]);
3012         m_face->assign_planepts(m_face->m_move_planeptsTransformed);
3013       }
3014       else if(m_vertexSelection.size() == 2)
3015       {
3016         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[1]);
3017         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[2]);
3018         m_face->assign_planepts(m_face->m_move_planeptsTransformed);
3019       }
3020       else if(m_vertexSelection.size() >= 3)
3021       {
3022         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[0]);
3023         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[1]);
3024         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[2]);
3025         m_face->assign_planepts(m_face->m_move_planeptsTransformed);
3026       }
3027     }
3028     if(selectedEdges())
3029     {
3030       if(m_edgeSelection.size() == 1)
3031       {
3032         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[0]);
3033         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[1]);
3034         m_face->assign_planepts(m_face->m_move_planeptsTransformed);
3035       }
3036       else if(m_edgeSelection.size() >= 2)
3037       {
3038         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[0]);
3039         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[1]);
3040         matrix4_transform_point(matrix, m_face->m_move_planeptsTransformed[2]);
3041         m_face->assign_planepts(m_face->m_move_planeptsTransformed);
3042       }
3043     }
3044   }
3045
3046   void snapto(float snap)
3047   {
3048     m_face->snapto(snap);
3049   }
3050
3051   void snapComponents(float snap)
3052   {
3053     if(isSelected())
3054     {
3055       snapto(snap);
3056     }
3057     if(selectedVertices())
3058     {
3059       vector3_snap(m_face->m_move_planepts[0], snap);
3060       vector3_snap(m_face->m_move_planepts[1], snap);
3061       vector3_snap(m_face->m_move_planepts[2], snap);
3062       m_face->assign_planepts(m_face->m_move_planepts);
3063       planepts_assign(m_face->m_move_planeptsTransformed, m_face->m_move_planepts);
3064       m_face->freezeTransform();
3065     }
3066     if(selectedEdges())
3067     {
3068       vector3_snap(m_face->m_move_planepts[0], snap);
3069       vector3_snap(m_face->m_move_planepts[1], snap);
3070       vector3_snap(m_face->m_move_planepts[2], snap);
3071       m_face->assign_planepts(m_face->m_move_planepts);
3072       planepts_assign(m_face->m_move_planeptsTransformed, m_face->m_move_planepts);
3073       m_face->freezeTransform();
3074     }
3075   }
3076   void update_move_planepts_vertex(std::size_t index)
3077   {
3078     m_face->update_move_planepts_vertex(index, m_face->m_move_planepts);
3079   }
3080   void update_move_planepts_vertex2(std::size_t index, std::size_t other)
3081   {
3082     const std::size_t numpoints = m_face->getWinding().numpoints;
3083     ASSERT_MESSAGE(index < numpoints, "select_vertex: invalid index");
3084
3085     const std::size_t opposite = Winding_Opposite(m_face->getWinding(), index, other);
3086
3087     if(triangle_reversed(index, other, opposite))
3088     {
3089       std::swap(index, other);
3090     }
3091
3092     ASSERT_MESSAGE(
3093       triangles_same_winding(
3094         m_face->getWinding()[opposite].vertex,
3095         m_face->getWinding()[index].vertex,
3096         m_face->getWinding()[other].vertex,
3097         m_face->getWinding()[0].vertex,
3098         m_face->getWinding()[1].vertex,
3099         m_face->getWinding()[2].vertex
3100       ),
3101       "update_move_planepts_vertex2: error"
3102     );
3103
3104     m_face->m_move_planepts[0] = m_face->getWinding()[opposite].vertex;
3105     m_face->m_move_planepts[1] = m_face->getWinding()[index].vertex;
3106     m_face->m_move_planepts[2] = m_face->getWinding()[other].vertex;
3107     planepts_quantise(m_face->m_move_planepts, GRID_MIN); // winding points are very inaccurate
3108   }
3109   void update_selection_vertex()
3110   {
3111     if(m_vertexSelection.size() == 0)
3112     {
3113       m_selectableVertices.setSelected(false);
3114     }
3115     else
3116     {
3117       m_selectableVertices.setSelected(true);
3118
3119       if(m_vertexSelection.size() == 1)
3120       {
3121         std::size_t index = Winding_FindAdjacent(getFace().getWinding(), *m_vertexSelection.begin());
3122
3123         if(index != c_brush_maxFaces)
3124         {
3125           update_move_planepts_vertex(index);
3126         }
3127       }
3128       else if(m_vertexSelection.size() == 2)
3129       {
3130         std::size_t index = Winding_FindAdjacent(getFace().getWinding(), *m_vertexSelection.begin());
3131         std::size_t other = Winding_FindAdjacent(getFace().getWinding(), *(++m_vertexSelection.begin()));
3132
3133         if(index != c_brush_maxFaces
3134           && other != c_brush_maxFaces)
3135         {
3136           update_move_planepts_vertex2(index, other);
3137         }
3138       }
3139     }
3140   }
3141   void select_vertex(std::size_t index, bool select)
3142   {
3143     if(select)
3144     {
3145       VertexSelection_insert(m_vertexSelection, getFace().getWinding()[index].adjacent);
3146     }
3147     else
3148     {
3149       VertexSelection_erase(m_vertexSelection, getFace().getWinding()[index].adjacent);
3150     }
3151
3152     SceneChangeNotify();
3153     update_selection_vertex();
3154   }
3155
3156   bool selected_vertex(std::size_t index) const
3157   {
3158     return VertexSelection_find(m_vertexSelection, getFace().getWinding()[index].adjacent) != m_vertexSelection.end();
3159   }
3160
3161   void update_move_planepts_edge(std::size_t index)
3162   {
3163     std::size_t numpoints = m_face->getWinding().numpoints;
3164     ASSERT_MESSAGE(index < numpoints, "select_edge: invalid index");
3165
3166     std::size_t adjacent = Winding_next(m_face->getWinding(), index);
3167     std::size_t opposite = Winding_Opposite(m_face->getWinding(), index);
3168     m_face->m_move_planepts[0] = m_face->getWinding()[index].vertex;
3169     m_face->m_move_planepts[1] = m_face->getWinding()[adjacent].vertex;
3170     m_face->m_move_planepts[2] = m_face->getWinding()[opposite].vertex;
3171     planepts_quantise(m_face->m_move_planepts, GRID_MIN); // winding points are very inaccurate
3172   }
3173   void update_selection_edge()
3174   {
3175     if(m_edgeSelection.size() == 0)
3176     {
3177       m_selectableEdges.setSelected(false);
3178     }
3179     else
3180     {
3181       m_selectableEdges.setSelected(true);
3182
3183       if(m_edgeSelection.size() == 1)
3184       {
3185         std::size_t index = Winding_FindAdjacent(getFace().getWinding(), *m_edgeSelection.begin());
3186
3187         if(index != c_brush_maxFaces)
3188         {
3189           update_move_planepts_edge(index);
3190         }
3191       }
3192     }
3193   }
3194   void select_edge(std::size_t index, bool select)
3195   {
3196     if(select)
3197     {
3198       VertexSelection_insert(m_edgeSelection, getFace().getWinding()[index].adjacent);
3199     }
3200     else
3201     {
3202       VertexSelection_erase(m_edgeSelection, getFace().getWinding()[index].adjacent);
3203     }
3204
3205     SceneChangeNotify();
3206     update_selection_edge();
3207   }
3208
3209   bool selected_edge(std::size_t index) const
3210   {
3211     return VertexSelection_find(m_edgeSelection, getFace().getWinding()[index].adjacent) != m_edgeSelection.end();
3212   }
3213
3214   const Vector3& centroid() const
3215   {
3216     return m_face->centroid();
3217   }
3218
3219   void connectivityChanged()
3220   {
3221     // This occurs when a face is added or removed.
3222     // The current vertex and edge selections no longer valid and must be cleared.
3223     m_vertexSelection.clear();
3224     m_selectableVertices.setSelected(false);
3225     m_edgeSelection.clear();
3226     m_selectableEdges.setSelected(false);
3227   }
3228 };
3229
3230 class BrushClipPlane : public OpenGLRenderable
3231 {
3232   Plane3 m_plane;
3233   Winding m_winding;
3234   static Shader* m_state;
3235 public:
3236   static void constructStatic()
3237   {
3238     m_state = GlobalShaderCache().capture("$CLIPPER_OVERLAY");
3239   }
3240   static void destroyStatic()
3241   {
3242     GlobalShaderCache().release("$CLIPPER_OVERLAY");
3243   }
3244
3245   void setPlane(const Brush& brush, const Plane3& plane)
3246   {
3247     m_plane = plane;
3248     if(plane3_valid(m_plane))
3249     {
3250       brush.windingForClipPlane(m_winding, m_plane);
3251     }
3252     else
3253     {
3254       m_winding.resize(0);
3255     }
3256   }
3257
3258   void render(RenderStateFlags state) const
3259   {
3260     if((state & RENDER_FILL) != 0)
3261     {
3262       Winding_Draw(m_winding, m_plane.normal(), state);
3263     }
3264     else
3265     {
3266       Winding_DrawWireframe(m_winding);
3267     }
3268   }
3269
3270   void render(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
3271   {
3272     renderer.SetState(m_state, Renderer::eWireframeOnly);
3273     renderer.SetState(m_state, Renderer::eFullMaterials);
3274     renderer.addRenderable(*this, localToWorld);
3275   }
3276 };
3277
3278 inline void Face_addLight(const FaceInstance& face, const Matrix4& localToWorld, const RendererLight& light)
3279 {
3280   const Plane3& facePlane = face.getFace().plane3();
3281   const Vector3& origin = light.aabb().origin;
3282   Plane3 tmp(plane3_transformed(Plane3(facePlane.normal(), -facePlane.dist()), localToWorld));
3283   if(!plane3_test_point(tmp, origin)
3284     || !plane3_test_point(tmp, vector3_added(origin, light.offset())))
3285   {
3286     face.m_lights.addLight(light);
3287   }
3288 }
3289
3290
3291
3292 typedef std::vector<FaceInstance> FaceInstances;
3293
3294 class EdgeInstance : public Selectable
3295 {
3296   FaceInstances& m_faceInstances;
3297   SelectableEdge* m_edge;
3298
3299   void select_edge(bool select)
3300   {
3301     FaceVertexId faceVertex = m_edge->m_faceVertex;
3302     m_faceInstances[faceVertex.getFace()].select_edge(faceVertex.getVertex(), select);
3303     faceVertex = next_edge(m_edge->m_faces, faceVertex);
3304     m_faceInstances[faceVertex.getFace()].select_edge(faceVertex.getVertex(), select);
3305   }
3306   bool selected_edge() const
3307   {
3308     FaceVertexId faceVertex = m_edge->m_faceVertex;
3309     if(!m_faceInstances[faceVertex.getFace()].selected_edge(faceVertex.getVertex()))
3310     {
3311       return false;
3312     }
3313     faceVertex = next_edge(m_edge->m_faces, faceVertex);
3314     if(!m_faceInstances[faceVertex.getFace()].selected_edge(faceVertex.getVertex()))
3315     {
3316       return false;
3317     }
3318
3319     return true;
3320   }
3321
3322 public:
3323   EdgeInstance(FaceInstances& faceInstances, SelectableEdge& edge)
3324     : m_faceInstances(faceInstances), m_edge(&edge)
3325   {
3326   }
3327   EdgeInstance& operator=(const EdgeInstance& other)
3328   {
3329     m_edge = other.m_edge;
3330     return *this;
3331   }
3332
3333   void setSelected(bool select)
3334   {
3335     select_edge(select);
3336   }
3337   bool isSelected() const
3338   {
3339     return selected_edge();
3340   }
3341
3342
3343   void testSelect(Selector& selector, SelectionTest& test)
3344   {
3345     SelectionIntersection best;
3346     m_edge->testSelect(test, best);
3347     if(best.valid())
3348     {
3349       Selector_add(selector, *this, best);
3350     }
3351   }
3352 };
3353
3354 class VertexInstance : public Selectable
3355 {
3356   FaceInstances& m_faceInstances;
3357   SelectableVertex* m_vertex;
3358
3359   void select_vertex(bool select)
3360   {
3361     FaceVertexId faceVertex = m_vertex->m_faceVertex;
3362     do
3363     {
3364       m_faceInstances[faceVertex.getFace()].select_vertex(faceVertex.getVertex(), select);
3365       faceVertex = next_vertex(m_vertex->m_faces, faceVertex);
3366     }
3367     while(faceVertex.getFace() != m_vertex->m_faceVertex.getFace());
3368   }
3369   bool selected_vertex() const
3370   {
3371     FaceVertexId faceVertex = m_vertex->m_faceVertex;
3372     do
3373     {
3374       if(!m_faceInstances[faceVertex.getFace()].selected_vertex(faceVertex.getVertex()))
3375       {
3376         return false;
3377       }
3378       faceVertex = next_vertex(m_vertex->m_faces, faceVertex);
3379     }
3380     while(faceVertex.getFace() != m_vertex->m_faceVertex.getFace());
3381     return true;
3382   }
3383
3384 public:
3385   VertexInstance(FaceInstances& faceInstances, SelectableVertex& vertex)
3386     : m_faceInstances(faceInstances), m_vertex(&vertex)
3387   {
3388   }
3389   VertexInstance& operator=(const VertexInstance& other)
3390   {
3391     m_vertex = other.m_vertex;
3392     return *this;
3393   }
3394
3395   void setSelected(bool select)
3396   {
3397     select_vertex(select);
3398   }
3399   bool isSelected() const
3400   {
3401     return selected_vertex();
3402   }
3403
3404   void testSelect(Selector& selector, SelectionTest& test)
3405   {
3406     SelectionIntersection best;
3407     m_vertex->testSelect(test, best);
3408     if(best.valid())
3409     {
3410       Selector_add(selector, *this, best);
3411     }
3412   }
3413 };
3414
3415 class BrushInstanceVisitor
3416 {
3417 public:
3418   virtual void visit(FaceInstance& face) const = 0;
3419 };
3420
3421 class BrushInstance :
3422 public BrushObserver,
3423 public scene::Instance,
3424 public Selectable,
3425 public Renderable,
3426 public SelectionTestable,
3427 public ComponentSelectionTestable,
3428 public ComponentEditable,
3429 public ComponentSnappable,
3430 public PlaneSelectable,
3431 public LightCullable
3432 {
3433   class TypeCasts
3434   {
3435     InstanceTypeCastTable m_casts;
3436   public:
3437     TypeCasts()
3438     {
3439       InstanceStaticCast<BrushInstance, Selectable>::install(m_casts);
3440       InstanceContainedCast<BrushInstance, Bounded>::install(m_casts);
3441       InstanceContainedCast<BrushInstance, Cullable>::install(m_casts);
3442       InstanceStaticCast<BrushInstance, Renderable>::install(m_casts);
3443       InstanceStaticCast<BrushInstance, SelectionTestable>::install(m_casts);
3444       InstanceStaticCast<BrushInstance, ComponentSelectionTestable>::install(m_casts);
3445       InstanceStaticCast<BrushInstance, ComponentEditable>::install(m_casts);
3446       InstanceStaticCast<BrushInstance, ComponentSnappable>::install(m_casts);
3447       InstanceStaticCast<BrushInstance, PlaneSelectable>::install(m_casts);
3448       InstanceIdentityCast<BrushInstance>::install(m_casts);
3449       InstanceContainedCast<BrushInstance, Transformable>::install(m_casts);
3450     }
3451     InstanceTypeCastTable& get()
3452     {
3453       return m_casts;
3454     }
3455   };
3456
3457
3458   Brush& m_brush;
3459
3460   FaceInstances m_faceInstances;
3461
3462   typedef std::vector<EdgeInstance> EdgeInstances;
3463   EdgeInstances m_edgeInstances;
3464   typedef std::vector<VertexInstance> VertexInstances;
3465   VertexInstances m_vertexInstances;
3466
3467   ObservedSelectable m_selectable;
3468
3469   mutable RenderableWireframe m_render_wireframe;
3470   mutable RenderablePointVector m_render_selected;
3471   mutable AABB m_aabb_component;
3472   mutable Array<PointVertex> m_faceCentroidPointsCulled;
3473   RenderablePointArray m_render_faces_wireframe;
3474   mutable bool m_viewChanged; // requires re-evaluation of view-dependent cached data
3475
3476   BrushClipPlane m_clipPlane;
3477
3478   static Shader* m_state_selpoint;
3479
3480   const LightList* m_lightList;
3481
3482   TransformModifier m_transform;
3483
3484   BrushInstance(const BrushInstance& other); // NOT COPYABLE
3485   BrushInstance& operator=(const BrushInstance& other); // NOT ASSIGNABLE
3486 public:
3487   static Counter* m_counter;
3488
3489   typedef LazyStatic<TypeCasts> StaticTypeCasts;
3490
3491   void lightsChanged()
3492   {
3493     m_lightList->lightsChanged();
3494   }
3495   typedef MemberCaller<BrushInstance, &BrushInstance::lightsChanged> LightsChangedCaller;
3496
3497   STRING_CONSTANT(Name, "BrushInstance");
3498
3499   BrushInstance(const scene::Path& path, scene::Instance* parent, Brush& brush) :
3500     Instance(path, parent, this, StaticTypeCasts::instance().get()),
3501     m_brush(brush),
3502     m_selectable(SelectedChangedCaller(*this)),
3503     m_render_selected(GL_POINTS),
3504     m_render_faces_wireframe(m_faceCentroidPointsCulled, GL_POINTS),
3505     m_viewChanged(false),
3506     m_transform(Brush::TransformChangedCaller(m_brush), ApplyTransformCaller(*this))
3507   {
3508     m_brush.instanceAttach(Instance::path());
3509     m_brush.attach(*this);
3510     m_counter->increment();
3511
3512     m_lightList = &GlobalShaderCache().attach(*this);
3513     m_brush.m_lightsChanged = LightsChangedCaller(*this); ///\todo Make this work with instancing.
3514
3515     Instance::setTransformChangedCallback(LightsChangedCaller(*this));
3516   }
3517   ~BrushInstance()
3518   {
3519     Instance::setTransformChangedCallback(Callback());
3520
3521     m_brush.m_lightsChanged = Callback();
3522     GlobalShaderCache().detach(*this);
3523
3524     m_counter->decrement();
3525     m_brush.detach(*this);
3526     m_brush.instanceDetach(Instance::path());
3527   }
3528
3529   Brush& getBrush()
3530   {
3531     return m_brush;
3532   }
3533   const Brush& getBrush() const
3534   {
3535     return m_brush;
3536   }
3537
3538   Bounded& get(NullType<Bounded>)
3539   {
3540     return m_brush;
3541   }
3542   Cullable& get(NullType<Cullable>)
3543   {
3544     return m_brush;
3545   }
3546   Transformable& get(NullType<Transformable>)
3547   {
3548     return m_transform;
3549   }
3550
3551   void selectedChanged(const Selectable& selectable)
3552   {
3553     GlobalSelectionSystem().getObserver(SelectionSystem::ePrimitive)(selectable);
3554     GlobalSelectionSystem().onSelectedChanged(*this, selectable);
3555
3556     Instance::selectedChanged();
3557   }
3558   typedef MemberCaller1<BrushInstance, const Selectable&, &BrushInstance::selectedChanged> SelectedChangedCaller;
3559
3560   void selectedChangedComponent(const Selectable& selectable)
3561   {
3562     GlobalSelectionSystem().getObserver(SelectionSystem::eComponent)(selectable);
3563     GlobalSelectionSystem().onComponentSelection(*this, selectable);
3564   }
3565   typedef MemberCaller1<BrushInstance, const Selectable&, &BrushInstance::selectedChangedComponent> SelectedChangedComponentCaller;
3566
3567   const BrushInstanceVisitor& forEachFaceInstance(const BrushInstanceVisitor& visitor)
3568   {
3569     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3570     {
3571       visitor.visit(*i);
3572     }
3573     return visitor;
3574   }
3575
3576   static void constructStatic()
3577   {
3578     m_state_selpoint = GlobalShaderCache().capture("$SELPOINT");
3579   }
3580   static void destroyStatic()
3581   {
3582     GlobalShaderCache().release("$SELPOINT");
3583   }
3584
3585   void clear()
3586   {
3587     m_faceInstances.clear();
3588   }
3589   void reserve(std::size_t size)
3590   {
3591     m_faceInstances.reserve(size);
3592   }
3593
3594   void push_back(Face& face)
3595   {
3596     m_faceInstances.push_back(FaceInstance(face, SelectedChangedComponentCaller(*this)));
3597   }
3598   void pop_back()
3599   {
3600     ASSERT_MESSAGE(!m_faceInstances.empty(), "erasing invalid element");
3601     m_faceInstances.pop_back();
3602   }
3603   void erase(std::size_t index)
3604   {
3605     ASSERT_MESSAGE(index < m_faceInstances.size(), "erasing invalid element");
3606     m_faceInstances.erase(m_faceInstances.begin() + index);
3607   }
3608   void connectivityChanged()
3609   {
3610     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3611     {
3612       (*i).connectivityChanged();
3613     }
3614   }
3615
3616   void edge_clear()
3617   {
3618     m_edgeInstances.clear();
3619   }
3620   void edge_push_back(SelectableEdge& edge)
3621   {
3622     m_edgeInstances.push_back(EdgeInstance(m_faceInstances, edge));
3623   }
3624
3625   void vertex_clear()
3626   {
3627     m_vertexInstances.clear();
3628   }
3629   void vertex_push_back(SelectableVertex& vertex)
3630   {
3631     m_vertexInstances.push_back(VertexInstance(m_faceInstances, vertex));
3632   }
3633
3634   void DEBUG_verify() const
3635   {
3636     ASSERT_MESSAGE(m_faceInstances.size() == m_brush.DEBUG_size(), "FATAL: mismatch");
3637   }
3638
3639   bool isSelected() const
3640   {
3641     return m_selectable.isSelected();
3642   }
3643   void setSelected(bool select)
3644   {
3645     m_selectable.setSelected(select);
3646   }
3647
3648   void update_selected() const
3649   {
3650     m_render_selected.clear();
3651     for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3652     {
3653       if((*i).getFace().contributes())
3654       {
3655         (*i).iterate_selected(m_render_selected);
3656       }
3657     }
3658   }
3659
3660   void evaluateViewDependent(const VolumeTest& volume, const Matrix4& localToWorld) const
3661   {
3662     if(m_viewChanged)
3663     {
3664       m_viewChanged = false;
3665
3666       bool faces_visible[c_brush_maxFaces];
3667       {
3668         bool* j = faces_visible;
3669         for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i, ++j)
3670         {
3671           *j = (*i).intersectVolume(volume, localToWorld);
3672         }
3673       }
3674
3675       m_brush.update_wireframe(m_render_wireframe, faces_visible);
3676       m_brush.update_faces_wireframe(m_faceCentroidPointsCulled, faces_visible);
3677     }
3678   }
3679
3680   void renderComponentsSelected(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
3681   {
3682     m_brush.evaluateBRep();
3683
3684     update_selected();
3685     if(!m_render_selected.empty())
3686     {
3687       renderer.Highlight(Renderer::ePrimitive, false);
3688       renderer.SetState(m_state_selpoint, Renderer::eWireframeOnly);
3689       renderer.SetState(m_state_selpoint, Renderer::eFullMaterials);
3690       renderer.addRenderable(m_render_selected, localToWorld);
3691     }
3692   }
3693
3694   void renderComponents(Renderer& renderer, const VolumeTest& volume) const
3695   {
3696     m_brush.evaluateBRep();
3697
3698     const Matrix4& localToWorld = Instance::localToWorld();
3699
3700     renderer.SetState(m_brush.m_state_point, Renderer::eWireframeOnly);
3701     renderer.SetState(m_brush.m_state_point, Renderer::eFullMaterials);
3702
3703     if(volume.fill() && GlobalSelectionSystem().ComponentMode() == SelectionSystem::eFace)
3704     {
3705       evaluateViewDependent(volume, localToWorld);
3706       renderer.addRenderable(m_render_faces_wireframe, localToWorld);
3707     }
3708     else
3709     {
3710       m_brush.renderComponents(GlobalSelectionSystem().ComponentMode(), renderer, volume, localToWorld);
3711     }
3712   }
3713
3714   void renderClipPlane(Renderer& renderer, const VolumeTest& volume) const
3715   {
3716     if(GlobalSelectionSystem().ManipulatorMode() == SelectionSystem::eClip && isSelected())
3717     {
3718       m_clipPlane.render(renderer, volume, localToWorld());
3719     }
3720   }
3721
3722   void renderCommon(Renderer& renderer, const VolumeTest& volume) const
3723   {
3724     bool componentMode = GlobalSelectionSystem().Mode() == SelectionSystem::eComponent;
3725
3726     if(componentMode && isSelected())
3727     {
3728       renderComponents(renderer, volume);
3729     }
3730
3731     if(parentSelected())
3732     {
3733       if(!componentMode)
3734       {
3735         renderer.Highlight(Renderer::eFace);
3736       }
3737       renderer.Highlight(Renderer::ePrimitive);
3738     }
3739   }
3740
3741   void renderSolid(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
3742   {
3743     //renderCommon(renderer, volume);
3744
3745     m_lightList->evaluateLights();
3746
3747     for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3748     {
3749       renderer.setLights((*i).m_lights);
3750       (*i).render(renderer, volume, localToWorld);
3751     }
3752
3753     renderComponentsSelected(renderer, volume, localToWorld);
3754   }
3755
3756   void renderWireframe(Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld) const
3757   {
3758     //renderCommon(renderer, volume);
3759
3760     evaluateViewDependent(volume, localToWorld);
3761
3762     if(m_render_wireframe.m_size != 0)
3763     {
3764       renderer.addRenderable(m_render_wireframe, localToWorld);
3765     }
3766
3767     renderComponentsSelected(renderer, volume, localToWorld);
3768   }
3769
3770   void renderSolid(Renderer& renderer, const VolumeTest& volume) const
3771   {
3772     m_brush.evaluateBRep();
3773
3774     renderClipPlane(renderer, volume);
3775
3776     renderSolid(renderer, volume, localToWorld());
3777   }
3778
3779   void renderWireframe(Renderer& renderer, const VolumeTest& volume) const
3780   {
3781     m_brush.evaluateBRep();
3782
3783     renderClipPlane(renderer, volume);
3784
3785     renderWireframe(renderer, volume, localToWorld());
3786   }
3787
3788   void viewChanged() const
3789   {
3790     m_viewChanged = true;
3791   }
3792
3793   void testSelect(Selector& selector, SelectionTest& test)
3794   {
3795     test.BeginMesh(localToWorld());
3796
3797     SelectionIntersection best;
3798     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3799     {
3800       (*i).testSelect(test, best);
3801     }
3802     if(best.valid())
3803     {
3804       selector.addIntersection(best);
3805     }
3806   }
3807
3808   bool isSelectedComponents() const
3809   {
3810     for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3811     {
3812       if((*i).selectedComponents())
3813       {
3814         return true;
3815       }
3816     }
3817     return false;
3818   }
3819   void setSelectedComponents(bool select, SelectionSystem::EComponentMode mode)
3820   {
3821     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3822     {
3823       (*i).setSelected(mode, select);
3824     }
3825   }
3826   void testSelectComponents(Selector& selector, SelectionTest& test, SelectionSystem::EComponentMode mode)
3827   {
3828     test.BeginMesh(localToWorld());
3829
3830     switch(mode)
3831     {
3832     case SelectionSystem::eVertex:
3833       {
3834         for(VertexInstances::iterator i = m_vertexInstances.begin(); i != m_vertexInstances.end(); ++i)
3835         {
3836           (*i).testSelect(selector, test);
3837         }
3838       }
3839       break;
3840     case SelectionSystem::eEdge:
3841       {
3842         for(EdgeInstances::iterator i = m_edgeInstances.begin(); i != m_edgeInstances.end(); ++i)
3843         {
3844           (*i).testSelect(selector, test);
3845         }
3846       }
3847       break;
3848     case SelectionSystem::eFace:
3849       {
3850         if(test.getVolume().fill())
3851         {
3852           for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3853           {
3854             (*i).testSelect(selector, test);
3855           }
3856         }
3857         else
3858         {
3859           for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3860           {
3861             (*i).testSelect_centroid(selector, test);
3862           }
3863         }
3864       }
3865       break;
3866     default:
3867       break;
3868     }
3869   }
3870
3871   void selectPlanes(Selector& selector, SelectionTest& test, const PlaneCallback& selectedPlaneCallback)
3872   {
3873     test.BeginMesh(localToWorld());
3874
3875     PlanePointer brushPlanes[c_brush_maxFaces];
3876     PlanesIterator j = brushPlanes;
3877
3878     for(Brush::const_iterator i = m_brush.begin(); i != m_brush.end(); ++i)
3879     {
3880       *j++ = &(*i)->plane3();
3881     }
3882
3883     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3884     {
3885       (*i).selectPlane(selector, Line(test.getNear(), test.getFar()), brushPlanes, j, selectedPlaneCallback);
3886     }
3887   }
3888   void selectReversedPlanes(Selector& selector, const SelectedPlanes& selectedPlanes)
3889   {
3890     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3891     {
3892       (*i).selectReversedPlane(selector, selectedPlanes);
3893     }
3894   }
3895
3896
3897   void transformComponents(const Matrix4& matrix)
3898   {
3899     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3900     {
3901       (*i).transformComponents(matrix);
3902     }
3903   }
3904   const AABB& getSelectedComponentsBounds() const
3905   {
3906     m_aabb_component = AABB();
3907
3908     for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3909     {
3910       (*i).iterate_selected(m_aabb_component);
3911     }
3912
3913     return m_aabb_component;
3914   }
3915
3916   void snapComponents(float snap)
3917   {
3918     for(FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3919     {
3920       (*i).snapComponents(snap);
3921     }
3922   }
3923   void evaluateTransform()
3924   {
3925     Matrix4 matrix(m_transform.calculateTransform());
3926     //globalOutputStream() << "matrix: " << matrix << "\n";
3927
3928     if(m_transform.getType() == TRANSFORM_PRIMITIVE)
3929     {
3930       m_brush.transform(matrix);
3931     }
3932     else
3933     {
3934       transformComponents(matrix);
3935     }
3936   }
3937   void applyTransform()
3938   {
3939     m_brush.revertTransform();
3940     evaluateTransform();
3941     m_brush.freezeTransform();
3942   }
3943   typedef MemberCaller<BrushInstance, &BrushInstance::applyTransform> ApplyTransformCaller;
3944
3945   void setClipPlane(const Plane3& plane)
3946   {
3947     m_clipPlane.setPlane(m_brush, plane);
3948   }
3949
3950   bool testLight(const RendererLight& light) const
3951   {
3952     return light.testAABB(worldAABB());
3953   }
3954   void insertLight(const RendererLight& light)
3955   {
3956     const Matrix4& localToWorld = Instance::localToWorld();
3957     for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3958     {
3959       Face_addLight(*i, localToWorld, light);
3960     }
3961   }
3962   void clearLights()
3963   {
3964     for(FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i)
3965     {
3966       (*i).m_lights.clear();
3967     }
3968   }
3969 };
3970
3971 inline BrushInstance* Instance_getBrush(scene::Instance& instance)
3972 {
3973   return InstanceTypeCast<BrushInstance>::cast(instance);
3974 }
3975
3976
3977 template<typename Functor>
3978 class BrushSelectedVisitor : public SelectionSystem::Visitor
3979 {
3980   const Functor& m_functor;
3981 public:
3982   BrushSelectedVisitor(const Functor& functor) : m_functor(functor)
3983   {
3984   }
3985   void visit(scene::Instance& instance) const
3986   {
3987     BrushInstance* brush = Instance_getBrush(instance);
3988     if(brush != 0)
3989     {
3990       m_functor(*brush);
3991     }
3992   }
3993 };
3994
3995 template<typename Functor>
3996 inline const Functor& Scene_forEachSelectedBrush(const Functor& functor)
3997 {
3998   GlobalSelectionSystem().foreachSelected(BrushSelectedVisitor<Functor>(functor));
3999   return functor;
4000 }
4001
4002 template<typename Functor>
4003 class BrushVisibleSelectedVisitor : public SelectionSystem::Visitor
4004 {
4005   const Functor& m_functor;
4006 public:
4007   BrushVisibleSelectedVisitor(const Functor& functor) : m_functor(functor)
4008   {
4009   }
4010   void visit(scene::Instance& instance) const
4011   {
4012     BrushInstance* brush = Instance_getBrush(instance);
4013     if(brush != 0
4014       && instance.path().top().get().visible())
4015     {
4016       m_functor(*brush);
4017     }
4018   }
4019 };
4020
4021 template<typename Functor>
4022 inline const Functor& Scene_forEachVisibleSelectedBrush(const Functor& functor)
4023 {
4024   GlobalSelectionSystem().foreachSelected(BrushVisibleSelectedVisitor<Functor>(functor));
4025   return functor;
4026 }
4027
4028 class BrushForEachFace
4029 {
4030   const BrushInstanceVisitor& m_visitor;
4031 public:
4032   BrushForEachFace(const BrushInstanceVisitor& visitor) : m_visitor(visitor)
4033   {
4034   }
4035   void operator()(BrushInstance& brush) const
4036   {
4037     brush.forEachFaceInstance(m_visitor);
4038   }
4039 };
4040
4041 template<class Functor>
4042 class FaceInstanceVisitFace : public BrushInstanceVisitor
4043 {
4044   const Functor& functor;
4045 public:
4046   FaceInstanceVisitFace(const Functor& functor)
4047     : functor(functor)
4048   {
4049   }
4050   void visit(FaceInstance& face) const
4051   {
4052     functor(face.getFace());
4053   }
4054 };
4055
4056 template<typename Functor>
4057 inline const Functor& Brush_forEachFace(BrushInstance& brush, const Functor& functor)
4058 {
4059   brush.forEachFaceInstance(FaceInstanceVisitFace<Functor>(functor));
4060   return functor;
4061 }
4062
4063 template<class Functor>
4064 class FaceVisitAll : public BrushVisitor
4065 {
4066   const Functor& functor;
4067 public:
4068   FaceVisitAll(const Functor& functor)
4069     : functor(functor)
4070   {
4071   }
4072   void visit(Face& face) const
4073   {
4074     functor(face);
4075   }
4076 };
4077
4078 template<typename Functor>
4079 inline const Functor& Brush_forEachFace(const Brush& brush, const Functor& functor)
4080 {
4081   brush.forEachFace(FaceVisitAll<Functor>(functor));
4082   return functor;
4083 }
4084
4085 template<typename Functor>
4086 inline const Functor& Brush_forEachFace(Brush& brush, const Functor& functor)
4087 {
4088   brush.forEachFace(FaceVisitAll<Functor>(functor));
4089   return functor;
4090 }
4091
4092 template<class Functor>
4093 class FaceInstanceVisitAll : public BrushInstanceVisitor
4094 {
4095   const Functor& functor;
4096 public:
4097   FaceInstanceVisitAll(const Functor& functor)
4098     : functor(functor)
4099   {
4100   }
4101   void visit(FaceInstance& face) const
4102   {
4103     functor(face);
4104   }
4105 };
4106
4107 template<typename Functor>
4108 inline const Functor& Brush_ForEachFaceInstance(BrushInstance& brush, const Functor& functor)
4109 {
4110   brush.forEachFaceInstance(FaceInstanceVisitAll<Functor>(functor));
4111   return functor;
4112 }
4113
4114 template<typename Functor>
4115 inline const Functor& Scene_forEachBrush(scene::Graph& graph, const Functor& functor)
4116 {
4117   graph.traverse(InstanceWalker< InstanceApply<BrushInstance, Functor> >(functor));
4118   return functor;
4119 }
4120
4121 template<typename Type, typename Functor>
4122 class InstanceIfVisible : public Functor
4123 {
4124 public:
4125   InstanceIfVisible(const Functor& functor) : Functor(functor)
4126   {
4127   }
4128   void operator()(scene::Instance& instance)
4129   {
4130     if(instance.path().top().get().visible())
4131     {
4132       Functor::operator()(instance);
4133     }
4134   }
4135 };
4136
4137 template<typename Functor>
4138 class BrushVisibleWalker : public scene::Graph::Walker
4139 {
4140   const Functor& m_functor;
4141 public:
4142   BrushVisibleWalker(const Functor& functor) : m_functor(functor)
4143   {
4144   }
4145   bool pre(const scene::Path& path, scene::Instance& instance) const
4146   {
4147     if(path.top().get().visible())
4148     {
4149       BrushInstance* brush = Instance_getBrush(instance);
4150       if(brush != 0)
4151       {
4152         m_functor(*brush);
4153       }
4154     }
4155     return true;
4156   }
4157 };
4158
4159 template<typename Functor>
4160 inline const Functor& Scene_forEachVisibleBrush(scene::Graph& graph, const Functor& functor)
4161 {
4162   graph.traverse(BrushVisibleWalker<Functor>(functor));
4163   return functor;
4164 }
4165
4166 template<typename Functor>
4167 inline const Functor& Scene_ForEachBrush_ForEachFace(scene::Graph& graph, const Functor& functor)
4168 {
4169   Scene_forEachBrush(graph, BrushForEachFace(FaceInstanceVisitFace<Functor>(functor)));
4170   return functor;
4171 }
4172
4173 // d1223m
4174 template<typename Functor>
4175 inline const Functor& Scene_ForEachBrush_ForEachFaceInstance(scene::Graph& graph, const Functor& functor)
4176 {
4177   Scene_forEachBrush(graph, BrushForEachFace(FaceInstanceVisitAll<Functor>(functor)));
4178   return functor;
4179 }
4180
4181 template<typename Functor>
4182 inline const Functor& Scene_ForEachSelectedBrush_ForEachFace(scene::Graph& graph, const Functor& functor)
4183 {
4184   Scene_forEachSelectedBrush(BrushForEachFace(FaceInstanceVisitFace<Functor>(functor)));
4185   return functor;
4186 }
4187
4188 template<typename Functor>
4189 inline const Functor& Scene_ForEachSelectedBrush_ForEachFaceInstance(scene::Graph& graph, const Functor& functor)
4190 {
4191   Scene_forEachSelectedBrush(BrushForEachFace(FaceInstanceVisitAll<Functor>(functor)));
4192   return functor;
4193 }
4194
4195 template<typename Functor>
4196 class FaceVisitorWrapper
4197 {
4198   const Functor& functor;
4199 public:
4200   FaceVisitorWrapper(const Functor& functor) : functor(functor)
4201   {
4202   }
4203
4204   void operator()(FaceInstance& faceInstance) const
4205   {
4206     functor(faceInstance.getFace());
4207   }
4208 };
4209
4210 template<typename Functor>
4211 inline const Functor& Scene_ForEachSelectedBrushFace(scene::Graph& graph, const Functor& functor)
4212 {
4213   g_SelectedFaceInstances.foreach(FaceVisitorWrapper<Functor>(functor));
4214   return functor;
4215 }
4216
4217
4218 #endif