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