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