radiant/brush.h

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