radiant/brush.h

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