radiant/brush: use std::shared_ptr
[xonotic/netradiant.git] / 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         FacePlane& operator=(const FacePlane&) = default;
658
659         class SavedState
660         {
661         public:
662                 PlanePoints m_planepts;
663                 Plane3 m_plane;
664
665                 SavedState( const FacePlane& facePlane ){
666                         if ( facePlane.isDoom3Plane() ) {
667                                 m_plane = facePlane.m_plane;
668                         }
669                         else
670                         {
671                                 planepts_assign( m_planepts, facePlane.planePoints() );
672                         }
673                 }
674
675                 void exportState( FacePlane& facePlane ) const {
676                         if ( facePlane.isDoom3Plane() ) {
677                                 facePlane.m_plane = m_plane;
678                                 facePlane.updateTranslated();
679                         }
680                         else
681                         {
682                                 planepts_assign( facePlane.planePoints(), m_planepts );
683                                 facePlane.MakePlane();
684                         }
685                 }
686         };
687
688         FacePlane() : m_funcStaticOrigin( 0, 0, 0 ){
689         }
690
691         FacePlane( const FacePlane& other ) : m_funcStaticOrigin( 0, 0, 0 ){
692                 if ( !isDoom3Plane() ) {
693                         planepts_assign( m_planepts, other.m_planepts );
694                         MakePlane();
695                 }
696                 else
697                 {
698                         m_plane = other.m_plane;
699                         updateTranslated();
700                 }
701         }
702
703         void MakePlane(){
704                 if ( !isDoom3Plane() ) {
705 #if 0
706                         if ( check_plane_is_integer( m_planepts ) ) {
707                                 globalErrorStream() << "non-integer planepts: ";
708                                 planepts_print( m_planepts, globalErrorStream() );
709                                 globalErrorStream() << "\n";
710                         }
711 #endif
712                         m_planeCached = plane3_for_points( m_planepts );
713                 }
714         }
715
716         void reverse(){
717                 if ( !isDoom3Plane() ) {
718                         vector3_swap( m_planepts[0], m_planepts[2] );
719                         MakePlane();
720                 }
721                 else
722                 {
723                         m_planeCached = plane3_flipped( m_plane );
724                         updateSource();
725                 }
726         }
727
728         void transform( const Matrix4& matrix, bool mirror ){
729                 if ( !isDoom3Plane() ) {
730
731 #if 0
732                         bool off = check_plane_is_integer( planePoints() );
733 #endif
734
735                         matrix4_transform_point( matrix, m_planepts[0] );
736                         matrix4_transform_point( matrix, m_planepts[1] );
737                         matrix4_transform_point( matrix, m_planepts[2] );
738
739                         if ( mirror ) {
740                                 reverse();
741                         }
742
743 #if 0
744                         if ( check_plane_is_integer( planePoints() ) ) {
745                                 if ( !off ) {
746                                         globalErrorStream() << "caused by transform\n";
747                                 }
748                         }
749 #endif
750                         MakePlane();
751                 }
752                 else
753                 {
754                         m_planeCached = Plane3_applyTransform( m_planeCached, matrix );
755                         updateSource();
756                 }
757         }
758
759         void offset( float offset ){
760                 if ( !isDoom3Plane() ) {
761                         Vector3 move( vector3_scaled( m_planeCached.normal(), -offset ) );
762
763                         vector3_subtract( m_planepts[0], move );
764                         vector3_subtract( m_planepts[1], move );
765                         vector3_subtract( m_planepts[2], move );
766
767                         MakePlane();
768                 }
769                 else
770                 {
771                         m_planeCached.d += offset;
772                         updateSource();
773                 }
774         }
775
776         void updateTranslated(){
777                 m_planeCached = Plane3_applyTranslation( m_plane, m_funcStaticOrigin );
778         }
779
780         void updateSource(){
781                 m_plane = Plane3_applyTranslation( m_planeCached, vector3_negated( m_funcStaticOrigin ) );
782         }
783
784
785         PlanePoints& planePoints(){
786                 return m_planepts;
787         }
788
789         const PlanePoints& planePoints() const {
790                 return m_planepts;
791         }
792
793         const Plane3& plane3() const {
794                 return m_planeCached;
795         }
796
797         void setDoom3Plane( const Plane3& plane ){
798                 m_plane = plane;
799                 updateTranslated();
800         }
801
802         const Plane3& getDoom3Plane() const {
803                 return m_plane;
804         }
805
806         void copy( const FacePlane& other ){
807                 if ( !isDoom3Plane() ) {
808                         planepts_assign( m_planepts, other.m_planepts );
809                         MakePlane();
810                 }
811                 else
812                 {
813                         m_planeCached = other.m_plane;
814                         updateSource();
815                 }
816         }
817
818         void copy( const Vector3& p0, const Vector3& p1, const Vector3& p2 ){
819                 if ( !isDoom3Plane() ) {
820                         m_planepts[0] = p0;
821                         m_planepts[1] = p1;
822                         m_planepts[2] = p2;
823                         MakePlane();
824                 }
825                 else
826                 {
827                         m_planeCached = plane3_for_points( p2, p1, p0 );
828                         updateSource();
829                 }
830         }
831 };
832
833 inline void Winding_testSelect( Winding& winding, SelectionTest& test, SelectionIntersection& best ){
834         test.TestPolygon( VertexPointer( reinterpret_cast<VertexPointer::pointer>( &winding.points.data()->vertex ), sizeof( WindingVertex ) ), winding.numpoints, best );
835 }
836
837 const double GRID_MIN = 0.125;
838
839 inline double quantiseInteger( double f ){
840         return float_to_integer( f );
841 }
842
843 inline double quantiseFloating( double f ){
844         return float_snapped( f, 1.f / ( 1 << 16 ) );
845 }
846
847 typedef double ( *QuantiseFunc )( double f );
848
849 class Face;
850
851 class FaceFilter
852 {
853 public:
854         virtual bool filter( const Face& face ) const = 0;
855 };
856
857 bool face_filtered( Face& face );
858
859 void add_face_filter( FaceFilter& filter, int mask, bool invert = false );
860
861 void Brush_addTextureChangedCallback( const SignalHandler& callback );
862
863 void Brush_textureChanged();
864
865
866 extern bool g_brush_texturelock_enabled;
867
868 class FaceObserver
869 {
870 public:
871         virtual void planeChanged() = 0;
872         virtual void connectivityChanged() = 0;
873         virtual void shaderChanged() = 0;
874         virtual void evaluateTransform() = 0;
875 };
876
877 class Face :
878         public OpenGLRenderable,
879         public Filterable,
880         public Undoable,
881         public FaceShaderObserver
882 {
883 std::size_t m_refcount;
884
885 class SavedState : public UndoMemento
886 {
887 public:
888 FacePlane::SavedState m_planeState;
889 FaceTexdef::SavedState m_texdefState;
890 FaceShader::SavedState m_shaderState;
891
892 SavedState( const Face& face ) : m_planeState( face.getPlane() ), m_texdefState( face.getTexdef() ), m_shaderState( face.getShader() ){
893 }
894
895 void exportState( Face& face ) const {
896         m_planeState.exportState( face.getPlane() );
897         m_shaderState.exportState( face.getShader() );
898         m_texdefState.exportState( face.getTexdef() );
899 }
900
901 void release(){
902         delete this;
903 }
904 };
905
906 public:
907 static QuantiseFunc m_quantise;
908 static EBrushType m_type;
909
910 PlanePoints m_move_planepts;
911 PlanePoints m_move_planeptsTransformed;
912 private:
913 FacePlane m_plane;
914 FacePlane m_planeTransformed;
915 FaceShader m_shader;
916 FaceTexdef m_texdef;
917 TextureProjection m_texdefTransformed;
918
919 Winding m_winding;
920 Vector3 m_centroid;
921 bool m_filtered;
922
923 FaceObserver* m_observer;
924 UndoObserver* m_undoable_observer;
925 MapFile* m_map;
926
927 // assignment not supported
928 Face& operator=( const Face& other );
929
930 // copy-construction not supported
931 Face( const Face& other );
932
933 public:
934
935 Face( FaceObserver* observer ) :
936         m_refcount( 0 ),
937         m_shader( texdef_name_default() ),
938         m_texdef( m_shader, TextureProjection(), false ),
939         m_filtered( false ),
940         m_observer( observer ),
941         m_undoable_observer( 0 ),
942         m_map( 0 ){
943         m_shader.attach( *this );
944         m_plane.copy( Vector3( 0, 0, 0 ), Vector3( 64, 0, 0 ), Vector3( 0, 64, 0 ) );
945         m_texdef.setBasis( m_plane.plane3().normal() );
946         planeChanged();
947 }
948
949 Face(
950         const Vector3& p0,
951         const Vector3& p1,
952         const Vector3& p2,
953         const char* shader,
954         const TextureProjection& projection,
955         FaceObserver* observer
956         ) :
957         m_refcount( 0 ),
958         m_shader( shader ),
959         m_texdef( m_shader, projection ),
960         m_observer( observer ),
961         m_undoable_observer( 0 ),
962         m_map( 0 ){
963         m_shader.attach( *this );
964         m_plane.copy( p0, p1, p2 );
965         m_texdef.setBasis( m_plane.plane3().normal() );
966         planeChanged();
967         updateFiltered();
968 }
969
970 Face( const Face& other, FaceObserver* observer ) :
971         m_refcount( 0 ),
972         m_shader( other.m_shader.getShader(), other.m_shader.m_flags ),
973         m_texdef( m_shader, other.getTexdef().normalised() ),
974         m_observer( observer ),
975         m_undoable_observer( 0 ),
976         m_map( 0 ){
977         m_shader.attach( *this );
978         m_plane.copy( other.m_plane );
979         planepts_assign( m_move_planepts, other.m_move_planepts );
980         m_texdef.setBasis( m_plane.plane3().normal() );
981         planeChanged();
982         updateFiltered();
983 }
984
985 ~Face(){
986         m_shader.detach( *this );
987 }
988
989 void planeChanged(){
990         revertTransform();
991         m_observer->planeChanged();
992 }
993
994 void realiseShader(){
995         m_observer->shaderChanged();
996 }
997
998 void unrealiseShader(){
999 }
1000
1001 void instanceAttach( MapFile* map ){
1002         m_shader.instanceAttach();
1003         m_map = map;
1004         m_undoable_observer = GlobalUndoSystem().observer( this );
1005         GlobalFilterSystem().registerFilterable( *this );
1006 }
1007 void instanceDetach( MapFile* map ){
1008         GlobalFilterSystem().unregisterFilterable( *this );
1009         m_undoable_observer = 0;
1010         GlobalUndoSystem().release( this );
1011         m_map = 0;
1012         m_shader.instanceDetach();
1013 }
1014
1015 void render( RenderStateFlags state ) const {
1016         Winding_Draw( m_winding, m_planeTransformed.plane3().normal(), state );
1017 }
1018
1019 void updateFiltered(){
1020         m_filtered = face_filtered( *this );
1021 }
1022
1023 bool isFiltered() const {
1024         return m_filtered;
1025 }
1026
1027 void undoSave(){
1028         if ( m_map != 0 ) {
1029                 m_map->changed();
1030         }
1031         if ( m_undoable_observer != 0 ) {
1032                 m_undoable_observer->save( this );
1033         }
1034 }
1035
1036 // undoable
1037 UndoMemento* exportState() const {
1038         return new SavedState( *this );
1039 }
1040
1041 void importState( const UndoMemento* data ){
1042         undoSave();
1043
1044         static_cast<const SavedState*>( data )->exportState( *this );
1045
1046         planeChanged();
1047         m_observer->connectivityChanged();
1048         texdefChanged();
1049         m_observer->shaderChanged();
1050         updateFiltered();
1051 }
1052
1053 void IncRef(){
1054         ++m_refcount;
1055 }
1056
1057 void DecRef(){
1058         if ( --m_refcount == 0 ) {
1059                 delete this;
1060         }
1061 }
1062
1063 void flipWinding(){
1064         m_plane.reverse();
1065         planeChanged();
1066 }
1067
1068 bool intersectVolume( const VolumeTest& volume, const Matrix4& localToWorld ) const {
1069         return volume.TestPlane( Plane3( plane3().normal(), -plane3().dist() ), localToWorld );
1070 }
1071
1072 void render( Renderer& renderer, const Matrix4& localToWorld ) const {
1073         renderer.SetState( m_shader.state(), Renderer::eFullMaterials );
1074         renderer.addRenderable( *this, localToWorld );
1075 }
1076
1077 void transform( const Matrix4& matrix, bool mirror ){
1078         if ( g_brush_texturelock_enabled ) {
1079                 Texdef_transformLocked( m_texdefTransformed, m_shader.width(), m_shader.height(), m_plane.plane3(), matrix );
1080         }
1081
1082         m_planeTransformed.transform( matrix, mirror );
1083
1084 #if 0
1085         ASSERT_MESSAGE( projectionaxis_for_normal( normal ) == projectionaxis_for_normal( plane3().normal() ), "bleh" );
1086 #endif
1087         m_observer->planeChanged();
1088
1089         if ( g_brush_texturelock_enabled ) {
1090                 Brush_textureChanged();
1091         }
1092 }
1093
1094 void assign_planepts( const PlanePoints planepts ){
1095         m_planeTransformed.copy( planepts[0], planepts[1], planepts[2] );
1096         m_observer->planeChanged();
1097 }
1098
1099 /// \brief Reverts the transformable state of the brush to identity.
1100 void revertTransform(){
1101         m_planeTransformed = m_plane;
1102         planepts_assign( m_move_planeptsTransformed, m_move_planepts );
1103         m_texdefTransformed = m_texdef.m_projection;
1104 }
1105
1106 void freezeTransform(){
1107         undoSave();
1108         m_plane = m_planeTransformed;
1109         planepts_assign( m_move_planepts, m_move_planeptsTransformed );
1110         m_texdef.m_projection = m_texdefTransformed;
1111 }
1112
1113 void update_move_planepts_vertex( std::size_t index, PlanePoints planePoints ){
1114         std::size_t numpoints = getWinding().numpoints;
1115         ASSERT_MESSAGE( index < numpoints, "update_move_planepts_vertex: invalid index" );
1116
1117         std::size_t opposite = Winding_Opposite( getWinding(), index );
1118         std::size_t adjacent = Winding_wrap( getWinding(), opposite + numpoints - 1 );
1119         planePoints[0] = getWinding()[opposite].vertex;
1120         planePoints[1] = getWinding()[index].vertex;
1121         planePoints[2] = getWinding()[adjacent].vertex;
1122         // winding points are very inaccurate, so they must be quantised before using them to generate the face-plane
1123         planepts_quantise( planePoints, GRID_MIN );
1124 }
1125
1126 void snapto( float snap ){
1127         if ( contributes() ) {
1128 #if 0
1129                 ASSERT_MESSAGE( plane3_valid( m_plane.plane3() ), "invalid plane before snap to grid" );
1130                 planepts_snap( m_plane.planePoints(), snap );
1131                 ASSERT_MESSAGE( plane3_valid( m_plane.plane3() ), "invalid plane after snap to grid" );
1132 #else
1133                 PlanePoints planePoints;
1134                 update_move_planepts_vertex( 0, planePoints );
1135                 vector3_snap( planePoints[0], snap );
1136                 vector3_snap( planePoints[1], snap );
1137                 vector3_snap( planePoints[2], snap );
1138                 assign_planepts( planePoints );
1139                 freezeTransform();
1140 #endif
1141                 SceneChangeNotify();
1142                 if ( !plane3_valid( m_plane.plane3() ) ) {
1143                         globalErrorStream() << "WARNING: invalid plane after snap to grid\n";
1144                 }
1145         }
1146 }
1147
1148 void testSelect( SelectionTest& test, SelectionIntersection& best ){
1149         Winding_testSelect( m_winding, test, best );
1150 }
1151
1152 void testSelect_centroid( SelectionTest& test, SelectionIntersection& best ){
1153         test.TestPoint( m_centroid, best );
1154 }
1155
1156 void shaderChanged(){
1157         EmitTextureCoordinates();
1158         Brush_textureChanged();
1159         m_observer->shaderChanged();
1160         updateFiltered();
1161         planeChanged();
1162         SceneChangeNotify();
1163 }
1164
1165 const char* GetShader() const {
1166         return m_shader.getShader();
1167 }
1168
1169 void SetShader( const char* name ){
1170         undoSave();
1171         m_shader.setShader( name );
1172         shaderChanged();
1173 }
1174
1175 void revertTexdef(){
1176         m_texdefTransformed = m_texdef.m_projection;
1177 }
1178
1179 void texdefChanged(){
1180         revertTexdef();
1181         EmitTextureCoordinates();
1182         Brush_textureChanged();
1183 }
1184
1185 void GetTexdef( TextureProjection& projection ) const {
1186         projection = m_texdef.normalised();
1187 }
1188
1189 void SetTexdef( const TextureProjection& projection ){
1190         undoSave();
1191         m_texdef.setTexdef( projection );
1192         texdefChanged();
1193 }
1194
1195 void GetFlags( ContentsFlagsValue& flags ) const {
1196         flags = m_shader.getFlags();
1197 }
1198
1199 void SetFlags( const ContentsFlagsValue& flags ){
1200         undoSave();
1201         m_shader.setFlags( flags );
1202         m_observer->shaderChanged();
1203         updateFiltered();
1204 }
1205
1206 void ShiftTexdef( float s, float t ){
1207         undoSave();
1208         m_texdef.shift( s, t );
1209         texdefChanged();
1210 }
1211
1212 void ScaleTexdef( float s, float t ){
1213         undoSave();
1214         m_texdef.scale( s, t );
1215         texdefChanged();
1216 }
1217
1218 void RotateTexdef( float angle ){
1219         undoSave();
1220         m_texdef.rotate( angle );
1221         texdefChanged();
1222 }
1223
1224 void FitTexture( float s_repeat, float t_repeat ){
1225         undoSave();
1226         m_texdef.fit( m_plane.plane3().normal(), m_winding, s_repeat, t_repeat );
1227         texdefChanged();
1228 }
1229
1230 void EmitTextureCoordinates(){
1231         Texdef_EmitTextureCoordinates( m_texdefTransformed, m_shader.width(), m_shader.height(), m_winding, plane3().normal(), g_matrix4_identity );
1232 }
1233
1234
1235 const Vector3& centroid() const {
1236         return m_centroid;
1237 }
1238
1239 void construct_centroid(){
1240         Winding_Centroid( m_winding, plane3(), m_centroid );
1241 }
1242
1243 const Winding& getWinding() const {
1244         return m_winding;
1245 }
1246
1247 Winding& getWinding(){
1248         return m_winding;
1249 }
1250
1251 const Plane3& plane3() const {
1252         m_observer->evaluateTransform();
1253         return m_planeTransformed.plane3();
1254 }
1255
1256 FacePlane& getPlane(){
1257         return m_plane;
1258 }
1259
1260 const FacePlane& getPlane() const {
1261         return m_plane;
1262 }
1263
1264 FaceTexdef& getTexdef(){
1265         return m_texdef;
1266 }
1267
1268 const FaceTexdef& getTexdef() const {
1269         return m_texdef;
1270 }
1271
1272 FaceShader& getShader(){
1273         return m_shader;
1274 }
1275
1276 const FaceShader& getShader() const {
1277         return m_shader;
1278 }
1279
1280 bool isDetail() const {
1281         return ( m_shader.m_flags.m_contentFlags & BRUSH_DETAIL_MASK ) != 0;
1282 }
1283
1284 void setDetail( bool detail ){
1285         undoSave();
1286         if ( detail && !isDetail() ) {
1287                 m_shader.m_flags.m_contentFlags |= BRUSH_DETAIL_MASK;
1288         }
1289         else if ( !detail && isDetail() ) {
1290                 m_shader.m_flags.m_contentFlags &= ~BRUSH_DETAIL_MASK;
1291         }
1292         m_observer->shaderChanged();
1293 }
1294
1295 bool contributes() const {
1296         return m_winding.numpoints > 2;
1297 }
1298
1299 bool is_bounded() const {
1300         for ( Winding::const_iterator i = m_winding.begin(); i != m_winding.end(); ++i )
1301         {
1302                 if ( ( *i ).adjacent == c_brush_maxFaces ) {
1303                         return false;
1304                 }
1305         }
1306         return true;
1307 }
1308 };
1309
1310
1311 class FaceVertexId
1312 {
1313         std::size_t m_face;
1314         std::size_t m_vertex;
1315
1316 public:
1317         FaceVertexId( std::size_t face, std::size_t vertex )
1318                 : m_face( face ), m_vertex( vertex ){
1319         }
1320
1321         std::size_t getFace() const {
1322                 return m_face;
1323         }
1324
1325         std::size_t getVertex() const {
1326                 return m_vertex;
1327         }
1328 };
1329
1330 typedef std::size_t faceIndex_t;
1331
1332 struct EdgeRenderIndices
1333 {
1334         RenderIndex first;
1335         RenderIndex second;
1336
1337         EdgeRenderIndices()
1338                 : first( 0 ), second( 0 ){
1339         }
1340
1341         EdgeRenderIndices( const RenderIndex _first, const RenderIndex _second )
1342                 : first( _first ), second( _second ){
1343         }
1344 };
1345
1346 struct EdgeFaces
1347 {
1348         faceIndex_t first;
1349         faceIndex_t second;
1350
1351         EdgeFaces()
1352                 : first( c_brush_maxFaces ), second( c_brush_maxFaces ){
1353         }
1354
1355         EdgeFaces( const faceIndex_t _first, const faceIndex_t _second )
1356                 : first( _first ), second( _second ){
1357         }
1358 };
1359
1360 class RenderableWireframe : public OpenGLRenderable
1361 {
1362 public:
1363 void render( RenderStateFlags state ) const {
1364 #if 1
1365         glColorPointer( 4, GL_UNSIGNED_BYTE, sizeof( PointVertex ), &m_vertices->colour );
1366         glVertexPointer( 3, GL_FLOAT, sizeof( PointVertex ), &m_vertices->vertex );
1367         glDrawElements( GL_LINES, GLsizei( m_size << 1 ), RenderIndexTypeID, m_faceVertex.data() );
1368 #else
1369         glBegin( GL_LINES );
1370         for ( std::size_t i = 0; i < m_size; ++i )
1371         {
1372                 glVertex3fv( &m_vertices[m_faceVertex[i].first].vertex.x );
1373                 glVertex3fv( &m_vertices[m_faceVertex[i].second].vertex.x );
1374         }
1375         glEnd();
1376 #endif
1377 }
1378
1379 Array<EdgeRenderIndices> m_faceVertex;
1380 std::size_t m_size;
1381 const PointVertex* m_vertices;
1382 };
1383
1384 class Brush;
1385
1386 typedef std::vector<Brush*> brush_vector_t;
1387
1388 class BrushFilter
1389 {
1390 public:
1391         virtual bool filter( const Brush& brush ) const = 0;
1392 };
1393
1394 bool brush_filtered( Brush& brush );
1395
1396 void add_brush_filter( BrushFilter& filter, int mask, bool invert = false );
1397
1398
1399 /// \brief Returns true if 'self' takes priority when building brush b-rep.
1400 inline bool plane3_inside( const Plane3& self, const Plane3& other, bool selfIsLater ){
1401         if ( vector3_equal_epsilon( self.normal(), other.normal(), 0.001 ) ) {
1402                 // same plane? prefer the one with smaller index
1403                 if ( self.dist() == other.dist() ) {
1404                         return selfIsLater;
1405                 }
1406                 return self.dist() < other.dist();
1407         }
1408         return true;
1409 }
1410
1411 typedef std::vector<std::shared_ptr<Face>> Faces;
1412
1413 /// \brief Returns the unique-id of the edge adjacent to \p faceVertex in the edge-pair for the set of \p faces.
1414 inline FaceVertexId next_edge( const Faces& faces, FaceVertexId faceVertex ){
1415         std::size_t adjacent_face = faces[faceVertex.getFace()]->getWinding()[faceVertex.getVertex()].adjacent;
1416         std::size_t adjacent_vertex = Winding_FindAdjacent( faces[adjacent_face]->getWinding(), faceVertex.getFace() );
1417
1418         ASSERT_MESSAGE( adjacent_vertex != c_brush_maxFaces, "connectivity data invalid" );
1419         if ( adjacent_vertex == c_brush_maxFaces ) {
1420                 return faceVertex;
1421         }
1422
1423         return FaceVertexId( adjacent_face, adjacent_vertex );
1424 }
1425
1426 /// \brief Returns the unique-id of the vertex adjacent to \p faceVertex in the vertex-ring for the set of \p faces.
1427 inline FaceVertexId next_vertex( const Faces& faces, FaceVertexId faceVertex ){
1428         FaceVertexId nextEdge = next_edge( faces, faceVertex );
1429         return FaceVertexId( nextEdge.getFace(), Winding_next( faces[nextEdge.getFace()]->getWinding(), nextEdge.getVertex() ) );
1430 }
1431
1432 class SelectableEdge
1433 {
1434         Vector3 getEdge() const {
1435                 const Winding& winding = getFace().getWinding();
1436                 return vector3_mid( winding[m_faceVertex.getVertex()].vertex, winding[Winding_next( winding, m_faceVertex.getVertex() )].vertex );
1437         }
1438
1439 public:
1440         Faces& m_faces;
1441         FaceVertexId m_faceVertex;
1442
1443         SelectableEdge( Faces& faces, FaceVertexId faceVertex )
1444                 : m_faces( faces ), m_faceVertex( faceVertex ){
1445         }
1446
1447         SelectableEdge& operator=( const SelectableEdge& other ){
1448                 m_faceVertex = other.m_faceVertex;
1449                 return *this;
1450         }
1451
1452         Face& getFace() const {
1453                 return *m_faces[m_faceVertex.getFace()];
1454         }
1455
1456         void testSelect( SelectionTest& test, SelectionIntersection& best ){
1457                 test.TestPoint( getEdge(), best );
1458         }
1459 };
1460
1461 class SelectableVertex
1462 {
1463         Vector3 getVertex() const {
1464                 return getFace().getWinding()[m_faceVertex.getVertex()].vertex;
1465         }
1466
1467 public:
1468         Faces& m_faces;
1469         FaceVertexId m_faceVertex;
1470
1471         SelectableVertex( Faces& faces, FaceVertexId faceVertex )
1472                 : m_faces( faces ), m_faceVertex( faceVertex ){
1473         }
1474
1475         SelectableVertex& operator=( const SelectableVertex& other ){
1476                 m_faceVertex = other.m_faceVertex;
1477                 return *this;
1478         }
1479
1480         Face& getFace() const {
1481                 return *m_faces[m_faceVertex.getFace()];
1482         }
1483
1484         void testSelect( SelectionTest& test, SelectionIntersection& best ){
1485                 test.TestPoint( getVertex(), best );
1486         }
1487 };
1488
1489 class BrushObserver
1490 {
1491 public:
1492         virtual void reserve( std::size_t size ) = 0;
1493         virtual void clear() = 0;
1494         virtual void push_back( Face& face ) = 0;
1495         virtual void pop_back() = 0;
1496         virtual void erase( std::size_t index ) = 0;
1497         virtual void connectivityChanged() = 0;
1498         virtual void edge_clear() = 0;
1499         virtual void edge_push_back( SelectableEdge& edge ) = 0;
1500         virtual void vertex_clear() = 0;
1501         virtual void vertex_push_back( SelectableVertex& vertex ) = 0;
1502         virtual void DEBUG_verify() const = 0;
1503 };
1504
1505 class BrushVisitor
1506 {
1507 public:
1508         virtual void visit( Face& face ) const = 0;
1509 };
1510
1511 class Brush :
1512         public TransformNode,
1513         public Bounded,
1514         public Cullable,
1515         public Snappable,
1516         public Undoable,
1517         public FaceObserver,
1518         public Filterable,
1519         public Nameable,
1520         public BrushDoom3
1521 {
1522 private:
1523         scene::Node* m_node;
1524         typedef UniqueSet<BrushObserver*> Observers;
1525         Observers m_observers;
1526         UndoObserver* m_undoable_observer;
1527         MapFile* m_map;
1528
1529         // state
1530         Faces m_faces;
1531         // ----
1532
1533         // cached data compiled from state
1534         Array<PointVertex> m_faceCentroidPoints;
1535         RenderablePointArray m_render_faces;
1536
1537         Array<PointVertex> m_uniqueVertexPoints;
1538         typedef std::vector<SelectableVertex> SelectableVertices;
1539         SelectableVertices m_select_vertices;
1540         RenderablePointArray m_render_vertices;
1541
1542         Array<PointVertex> m_uniqueEdgePoints;
1543         typedef std::vector<SelectableEdge> SelectableEdges;
1544         SelectableEdges m_select_edges;
1545         RenderablePointArray m_render_edges;
1546
1547         Array<EdgeRenderIndices> m_edge_indices;
1548         Array<EdgeFaces> m_edge_faces;
1549
1550         AABB m_aabb_local;
1551         // ----
1552
1553         Callback<void()> m_evaluateTransform;
1554         Callback<void()> m_boundsChanged;
1555
1556         mutable bool m_planeChanged;   // b-rep evaluation required
1557         mutable bool m_transformChanged;   // transform evaluation required
1558         // ----
1559
1560 public:
1561         STRING_CONSTANT( Name, "Brush" );
1562
1563         Callback<void()> m_lightsChanged;
1564
1565         // static data
1566         static Shader* m_state_point;
1567         // ----
1568
1569         static EBrushType m_type;
1570         static double m_maxWorldCoord;
1571
1572         Brush( scene::Node& node, const Callback<void()>& evaluateTransform, const Callback<void()>& boundsChanged ) :
1573                 m_node( &node ),
1574                 m_undoable_observer( 0 ),
1575                 m_map( 0 ),
1576                 m_render_faces( m_faceCentroidPoints, GL_POINTS ),
1577                 m_render_vertices( m_uniqueVertexPoints, GL_POINTS ),
1578                 m_render_edges( m_uniqueEdgePoints, GL_POINTS ),
1579                 m_evaluateTransform( evaluateTransform ),
1580                 m_boundsChanged( boundsChanged ),
1581                 m_planeChanged( false ),
1582                 m_transformChanged( false ){
1583                 planeChanged();
1584         }
1585         Brush( const Brush& other, scene::Node& node, const Callback<void()>& evaluateTransform, const Callback<void()>& boundsChanged ) :
1586                 m_node( &node ),
1587                 m_undoable_observer( 0 ),
1588                 m_map( 0 ),
1589                 m_render_faces( m_faceCentroidPoints, GL_POINTS ),
1590                 m_render_vertices( m_uniqueVertexPoints, GL_POINTS ),
1591                 m_render_edges( m_uniqueEdgePoints, GL_POINTS ),
1592                 m_evaluateTransform( evaluateTransform ),
1593                 m_boundsChanged( boundsChanged ),
1594                 m_planeChanged( false ),
1595                 m_transformChanged( false ){
1596                 copy( other );
1597         }
1598
1599         Brush( const Brush& other ) :
1600                 TransformNode( other ),
1601                 Bounded( other ),
1602                 Cullable( other ),
1603                 Snappable(),
1604                 Undoable( other ),
1605                 FaceObserver( other ),
1606                 Filterable( other ),
1607                 Nameable( other ),
1608                 BrushDoom3( other ),
1609                 m_node( 0 ),
1610                 m_undoable_observer( 0 ),
1611                 m_map( 0 ),
1612                 m_render_faces( m_faceCentroidPoints, GL_POINTS ),
1613                 m_render_vertices( m_uniqueVertexPoints, GL_POINTS ),
1614                 m_render_edges( m_uniqueEdgePoints, GL_POINTS ),
1615                 m_planeChanged( false ),
1616                 m_transformChanged( false ){
1617                 copy( other );
1618         }
1619
1620         ~Brush(){
1621                 ASSERT_MESSAGE( m_observers.empty(), "Brush::~Brush: observers still attached" );
1622         }
1623
1624         // assignment not supported
1625         Brush& operator=( const Brush& other );
1626
1627         void setDoom3GroupOrigin( const Vector3& origin ){
1628                 //globalOutputStream() << "func_static origin before: " << m_funcStaticOrigin << " after: " << origin << "\n";
1629                 for ( Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1630                 {
1631                         ( *i )->getPlane().m_funcStaticOrigin = origin;
1632                         ( *i )->getPlane().updateTranslated();
1633                         ( *i )->planeChanged();
1634                 }
1635                 planeChanged();
1636         }
1637
1638         void attach( BrushObserver& observer ){
1639                 for ( Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1640                 {
1641                         observer.push_back( *( *i ) );
1642                 }
1643
1644                 for ( SelectableEdges::iterator i = m_select_edges.begin(); i != m_select_edges.end(); ++i )
1645                 {
1646                         observer.edge_push_back( *i );
1647                 }
1648
1649                 for ( SelectableVertices::iterator i = m_select_vertices.begin(); i != m_select_vertices.end(); ++i )
1650                 {
1651                         observer.vertex_push_back( *i );
1652                 }
1653
1654                 m_observers.insert( &observer );
1655         }
1656
1657         void detach( BrushObserver& observer ){
1658                 m_observers.erase( &observer );
1659         }
1660
1661         void forEachFace( const BrushVisitor& visitor ) const {
1662                 for ( Faces::const_iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1663                 {
1664                         visitor.visit( *( *i ) );
1665                 }
1666         }
1667
1668         void forEachFace_instanceAttach( MapFile* map ) const {
1669                 for ( Faces::const_iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1670                 {
1671                         ( *i )->instanceAttach( map );
1672                 }
1673         }
1674
1675         void forEachFace_instanceDetach( MapFile* map ) const {
1676                 for ( Faces::const_iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1677                 {
1678                         ( *i )->instanceDetach( map );
1679                 }
1680         }
1681
1682         InstanceCounter m_instanceCounter;
1683
1684         void instanceAttach( const scene::Path& path ){
1685                 if ( ++m_instanceCounter.m_count == 1 ) {
1686                         m_map = path_find_mapfile( path.begin(), path.end() );
1687                         m_undoable_observer = GlobalUndoSystem().observer( this );
1688                         GlobalFilterSystem().registerFilterable( *this );
1689                         forEachFace_instanceAttach( m_map );
1690                 }
1691                 else
1692                 {
1693                         ASSERT_MESSAGE( path_find_mapfile( path.begin(), path.end() ) == m_map, "node is instanced across more than one file" );
1694                 }
1695         }
1696
1697         void instanceDetach( const scene::Path& path ){
1698                 if ( --m_instanceCounter.m_count == 0 ) {
1699                         forEachFace_instanceDetach( m_map );
1700                         GlobalFilterSystem().unregisterFilterable( *this );
1701                         m_map = 0;
1702                         m_undoable_observer = 0;
1703                         GlobalUndoSystem().release( this );
1704                 }
1705         }
1706
1707         // nameable
1708         const char* name() const {
1709                 return "brush";
1710         }
1711
1712         void attach( const NameCallback& callback ){
1713         }
1714
1715         void detach( const NameCallback& callback ){
1716         }
1717
1718         // filterable
1719         void updateFiltered(){
1720                 if ( m_node != 0 ) {
1721                         if ( brush_filtered( *this ) ) {
1722                                 m_node->enable( scene::Node::eFiltered );
1723                         }
1724                         else
1725                         {
1726                                 m_node->disable( scene::Node::eFiltered );
1727                         }
1728                 }
1729         }
1730
1731         // observer
1732         void planeChanged(){
1733                 m_planeChanged = true;
1734                 aabbChanged();
1735                 m_lightsChanged();
1736         }
1737
1738         void shaderChanged(){
1739                 updateFiltered();
1740                 planeChanged();
1741         }
1742
1743         void evaluateBRep() const {
1744                 if ( m_planeChanged ) {
1745                         m_planeChanged = false;
1746                         const_cast<Brush*>( this )->buildBRep();
1747                 }
1748         }
1749
1750         void transformChanged(){
1751                 m_transformChanged = true;
1752                 planeChanged();
1753         }
1754
1755         typedef MemberCaller<Brush, void(), &Brush::transformChanged> TransformChangedCaller;
1756
1757         void evaluateTransform(){
1758                 if ( m_transformChanged ) {
1759                         m_transformChanged = false;
1760                         revertTransform();
1761                         m_evaluateTransform();
1762                 }
1763         }
1764
1765         const Matrix4& localToParent() const {
1766                 return g_matrix4_identity;
1767         }
1768
1769         void aabbChanged(){
1770                 m_boundsChanged();
1771         }
1772
1773         const AABB& localAABB() const {
1774                 evaluateBRep();
1775                 return m_aabb_local;
1776         }
1777
1778         VolumeIntersectionValue intersectVolume( const VolumeTest& test, const Matrix4& localToWorld ) const {
1779                 return test.TestAABB( m_aabb_local, localToWorld );
1780         }
1781
1782         void renderComponents( SelectionSystem::EComponentMode mode, Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld ) const {
1783                 switch ( mode )
1784                 {
1785                 case SelectionSystem::eVertex:
1786                         renderer.addRenderable( m_render_vertices, localToWorld );
1787                         break;
1788                 case SelectionSystem::eEdge:
1789                         renderer.addRenderable( m_render_edges, localToWorld );
1790                         break;
1791                 case SelectionSystem::eFace:
1792                         renderer.addRenderable( m_render_faces, localToWorld );
1793                         break;
1794                 default:
1795                         break;
1796                 }
1797         }
1798
1799         void transform( const Matrix4& matrix ){
1800                 bool mirror = matrix4_handedness( matrix ) == MATRIX4_LEFTHANDED;
1801
1802                 for ( Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1803                 {
1804                         ( *i )->transform( matrix, mirror );
1805                 }
1806         }
1807
1808         void snapto( float snap ){
1809                 for ( Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1810                 {
1811                         ( *i )->snapto( snap );
1812                 }
1813         }
1814
1815         void revertTransform(){
1816                 for ( Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1817                 {
1818                         ( *i )->revertTransform();
1819                 }
1820         }
1821
1822         void freezeTransform(){
1823                 for ( Faces::iterator i = m_faces.begin(); i != m_faces.end(); ++i )
1824                 {
1825                         ( *i )->freezeTransform();
1826                 }
1827         }
1828
1829         /// \brief Returns the absolute index of the \p faceVertex.
1830         std::size_t absoluteIndex( FaceVertexId faceVertex ){
1831                 std::size_t index = 0;
1832                 for ( std::size_t i = 0; i < faceVertex.getFace(); ++i )
1833                 {
1834                         index += m_faces[i]->getWinding().numpoints;
1835                 }
1836                 return index + faceVertex.getVertex();
1837         }
1838
1839         void appendFaces( const Faces& other ){
1840                 clear();
1841                 for ( Faces::const_iterator i = other.begin(); i != other.end(); ++i )
1842                 {
1843                         push_back( *i );
1844                 }
1845         }
1846
1847         /// \brief The undo memento for a brush stores only the list of face references - the faces are not copied.
1848         class BrushUndoMemento : public UndoMemento
1849         {
1850         public:
1851                 BrushUndoMemento( const Faces& faces ) : m_faces( faces ){
1852         }
1853
1854         void release(){
1855                 delete this;
1856         }
1857
1858         Faces m_faces;
1859         };
1860
1861         void undoSave(){
1862                 if ( m_map != 0 ) {
1863                         m_map->changed();
1864                 }
1865                 if ( m_undoable_observer != 0 ) {
1866                         m_undoable_observer->save( this );
1867                 }
1868         }
1869
1870         UndoMemento* exportState() const {
1871                 return new BrushUndoMemento( m_faces );
1872         }
1873
1874         void importState( const UndoMemento* state ){
1875                 undoSave();
1876                 appendFaces( static_cast<const BrushUndoMemento*>( state )->m_faces );
1877                 planeChanged();
1878
1879                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
1880                 {
1881                         ( *i )->DEBUG_verify();
1882                 }
1883         }
1884
1885         bool isDetail(){
1886                 return !m_faces.empty() && m_faces.front()->isDetail();
1887         }
1888
1889         /// \brief Appends a copy of \p face to the end of the face list.
1890         std::shared_ptr<Face> addFace( const Face& face ){
1891                 if ( m_faces.size() == c_brush_maxFaces ) {
1892                         return 0;
1893                 }
1894                 undoSave();
1895                 push_back( std::make_shared<Face>( face, this ) );
1896                 m_faces.back()->setDetail( isDetail() );
1897                 planeChanged();
1898                 return m_faces.back();
1899         }
1900
1901         /// \brief Appends a new face constructed from the parameters to the end of the face list.
1902         std::shared_ptr<Face> addPlane( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection ){
1903                 if ( m_faces.size() == c_brush_maxFaces ) {
1904                         return 0;
1905                 }
1906                 undoSave();
1907                 push_back( std::make_shared<Face>( p0, p1, p2, shader, projection, this ) );
1908                 m_faces.back()->setDetail( isDetail() );
1909                 planeChanged();
1910                 return m_faces.back();
1911         }
1912
1913         static void constructStatic( EBrushType type ){
1914                 m_type = type;
1915                 Face::m_type = type;
1916                 FacePlane::m_type = type;
1917
1918                 g_bp_globals.m_texdefTypeId = TEXDEFTYPEID_QUAKE;
1919                 if ( m_type == eBrushTypeQuake3BP || m_type == eBrushTypeDoom3 || m_type == eBrushTypeQuake4 ) {
1920                         g_bp_globals.m_texdefTypeId = TEXDEFTYPEID_BRUSHPRIMITIVES;
1921                         // g_brush_texturelock_enabled = true; // bad idea, this overrides user setting
1922                 }
1923                 else if ( m_type == eBrushTypeHalfLife ) {
1924                         g_bp_globals.m_texdefTypeId = TEXDEFTYPEID_HALFLIFE;
1925                         // g_brush_texturelock_enabled = true; // bad idea, this overrides user setting
1926                 }
1927
1928                 Face::m_quantise = ( m_type == eBrushTypeQuake ) ? quantiseInteger : quantiseFloating;
1929
1930                 m_state_point = GlobalShaderCache().capture( "$POINT" );
1931         }
1932
1933         static void destroyStatic(){
1934                 GlobalShaderCache().release( "$POINT" );
1935         }
1936
1937         std::size_t DEBUG_size(){
1938                 return m_faces.size();
1939         }
1940
1941         typedef Faces::const_iterator const_iterator;
1942
1943         const_iterator begin() const {
1944                 return m_faces.begin();
1945         }
1946
1947         const_iterator end() const {
1948                 return m_faces.end();
1949         }
1950
1951         std::shared_ptr<Face> back(){
1952                 return m_faces.back();
1953         }
1954
1955         const std::shared_ptr<Face> back() const {
1956                 return m_faces.back();
1957         }
1958
1959         void reserve( std::size_t count ){
1960                 m_faces.reserve( count );
1961                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
1962                 {
1963                         ( *i )->reserve( count );
1964                 }
1965         }
1966
1967         void push_back( Faces::value_type face ){
1968                 m_faces.push_back( face );
1969                 if ( m_instanceCounter.m_count != 0 ) {
1970                         m_faces.back()->instanceAttach( m_map );
1971                 }
1972                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
1973                 {
1974                         ( *i )->push_back( *face );
1975                         ( *i )->DEBUG_verify();
1976                 }
1977         }
1978
1979         void pop_back(){
1980                 if ( m_instanceCounter.m_count != 0 ) {
1981                         m_faces.back()->instanceDetach( m_map );
1982                 }
1983                 m_faces.pop_back();
1984                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
1985                 {
1986                         ( *i )->pop_back();
1987                         ( *i )->DEBUG_verify();
1988                 }
1989         }
1990
1991         void erase( std::size_t index ){
1992                 if ( m_instanceCounter.m_count != 0 ) {
1993                         m_faces[index]->instanceDetach( m_map );
1994                 }
1995                 m_faces.erase( m_faces.begin() + index );
1996                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
1997                 {
1998                         ( *i )->erase( index );
1999                         ( *i )->DEBUG_verify();
2000                 }
2001         }
2002
2003         void connectivityChanged(){
2004                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
2005                 {
2006                         ( *i )->connectivityChanged();
2007                 }
2008         }
2009
2010
2011         void clear(){
2012                 undoSave();
2013                 if ( m_instanceCounter.m_count != 0 ) {
2014                         forEachFace_instanceDetach( m_map );
2015                 }
2016                 m_faces.clear();
2017                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
2018                 {
2019                         ( *i )->clear();
2020                         ( *i )->DEBUG_verify();
2021                 }
2022         }
2023
2024         std::size_t size() const {
2025                 return m_faces.size();
2026         }
2027
2028         bool empty() const {
2029                 return m_faces.empty();
2030         }
2031
2032         /// \brief Returns true if any face of the brush contributes to the final B-Rep.
2033         bool hasContributingFaces() const {
2034                 for ( const_iterator i = begin(); i != end(); ++i )
2035                 {
2036                         if ( ( *i )->contributes() ) {
2037                                 return true;
2038                         }
2039                 }
2040                 return false;
2041         }
2042
2043         /// \brief Removes faces that do not contribute to the brush. This is useful for cleaning up after CSG operations on the brush.
2044         /// 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.
2045         void removeEmptyFaces(){
2046                 evaluateBRep();
2047
2048                 {
2049                         std::size_t i = 0;
2050                         while ( i < m_faces.size() )
2051                         {
2052                                 if ( !m_faces[i]->contributes() ) {
2053                                         erase( i );
2054                                         planeChanged();
2055                                 }
2056                                 else
2057                                 {
2058                                         ++i;
2059                                 }
2060                         }
2061                 }
2062         }
2063
2064         /// \brief Constructs \p winding from the intersection of \p plane with the other planes of the brush.
2065         void windingForClipPlane( Winding& winding, const Plane3& plane ) const {
2066                 FixedWinding buffer[2];
2067                 bool swap = false;
2068
2069                 // get a poly that covers an effectively infinite area
2070                 Winding_createInfinite( buffer[swap], plane, m_maxWorldCoord + 1 );
2071
2072                 // chop the poly by all of the other faces
2073                 {
2074                         for ( std::size_t i = 0; i < m_faces.size(); ++i )
2075                         {
2076                                 const Face& clip = *m_faces[i];
2077
2078                                 if ( plane3_equal( clip.plane3(), plane )
2079                                          || !plane3_valid( clip.plane3() ) || !plane_unique( i )
2080                                          || plane3_opposing( plane, clip.plane3() ) ) {
2081                                         continue;
2082                                 }
2083
2084                                 buffer[!swap].clear();
2085
2086 #if BRUSH_CONNECTIVITY_DEBUG
2087                                 globalOutputStream() << "clip vs face: " << i << "\n";
2088 #endif
2089
2090                                 {
2091                                         // flip the plane, because we want to keep the back side
2092                                         Plane3 clipPlane( vector3_negated( clip.plane3().normal() ), -clip.plane3().dist() );
2093                                         Winding_Clip( buffer[swap], plane, clipPlane, i, buffer[!swap] );
2094                                 }
2095
2096 #if BRUSH_CONNECTIVITY_DEBUG
2097                                 for ( FixedWinding::Points::iterator k = buffer[!swap].points.begin(), j = buffer[!swap].points.end() - 1; k != buffer[!swap].points.end(); j = k, ++k )
2098                                 {
2099                                         if ( vector3_length_squared( vector3_subtracted( ( *k ).vertex, ( *j ).vertex ) ) < 1 ) {
2100                                                 globalOutputStream() << "v: " << std::distance( buffer[!swap].points.begin(), j ) << " tiny edge adjacent to face " << ( *j ).adjacent << "\n";
2101                                         }
2102                                 }
2103 #endif
2104
2105                                 //ASSERT_MESSAGE(buffer[!swap].numpoints != 1, "created single-point winding");
2106
2107                                 swap = !swap;
2108                         }
2109                 }
2110
2111                 Winding_forFixedWinding( winding, buffer[swap] );
2112
2113 #if BRUSH_CONNECTIVITY_DEBUG
2114                 Winding_printConnectivity( winding );
2115
2116                 for ( Winding::iterator i = winding.begin(), j = winding.end() - 1; i != winding.end(); j = i, ++i )
2117                 {
2118                         if ( vector3_length_squared( vector3_subtracted( ( *i ).vertex, ( *j ).vertex ) ) < 1 ) {
2119                                 globalOutputStream() << "v: " << std::distance( winding.begin(), j ) << " tiny edge adjacent to face " << ( *j ).adjacent << "\n";
2120                         }
2121                 }
2122 #endif
2123         }
2124
2125         void update_wireframe( RenderableWireframe& wire, const bool* faces_visible ) const {
2126                 wire.m_faceVertex.resize( m_edge_indices.size() );
2127                 wire.m_vertices = m_uniqueVertexPoints.data();
2128                 wire.m_size = 0;
2129                 for ( std::size_t i = 0; i < m_edge_faces.size(); ++i )
2130                 {
2131                         if ( faces_visible[m_edge_faces[i].first]
2132                                  || faces_visible[m_edge_faces[i].second] ) {
2133                                 wire.m_faceVertex[wire.m_size++] = m_edge_indices[i];
2134                         }
2135                 }
2136         }
2137
2138
2139         void update_faces_wireframe( Array<PointVertex>& wire, const bool* faces_visible ) const {
2140                 std::size_t count = 0;
2141                 for ( std::size_t i = 0; i < m_faceCentroidPoints.size(); ++i )
2142                 {
2143                         if ( faces_visible[i] ) {
2144                                 ++count;
2145                         }
2146                 }
2147
2148                 wire.resize( count );
2149                 Array<PointVertex>::iterator p = wire.begin();
2150                 for ( std::size_t i = 0; i < m_faceCentroidPoints.size(); ++i )
2151                 {
2152                         if ( faces_visible[i] ) {
2153                                 *p++ = m_faceCentroidPoints[i];
2154                         }
2155                 }
2156         }
2157
2158         /// \brief Makes this brush a deep-copy of the \p other.
2159         void copy( const Brush& other ){
2160                 for ( Faces::const_iterator i = other.m_faces.begin(); i != other.m_faces.end(); ++i )
2161                 {
2162                         addFace( *( *i ) );
2163                 }
2164                 planeChanged();
2165         }
2166
2167         private:
2168         void edge_push_back( FaceVertexId faceVertex ){
2169                 m_select_edges.push_back( SelectableEdge( m_faces, faceVertex ) );
2170                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
2171                 {
2172                         ( *i )->edge_push_back( m_select_edges.back() );
2173                 }
2174         }
2175
2176         void edge_clear(){
2177                 m_select_edges.clear();
2178                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
2179                 {
2180                         ( *i )->edge_clear();
2181                 }
2182         }
2183
2184         void vertex_push_back( FaceVertexId faceVertex ){
2185                 m_select_vertices.push_back( SelectableVertex( m_faces, faceVertex ) );
2186                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
2187                 {
2188                         ( *i )->vertex_push_back( m_select_vertices.back() );
2189                 }
2190         }
2191
2192         void vertex_clear(){
2193                 m_select_vertices.clear();
2194                 for ( Observers::iterator i = m_observers.begin(); i != m_observers.end(); ++i )
2195                 {
2196                         ( *i )->vertex_clear();
2197                 }
2198         }
2199
2200         /// \brief Returns true if the face identified by \p index is preceded by another plane that takes priority over it.
2201         bool plane_unique( std::size_t index ) const {
2202                 // duplicate plane
2203                 for ( std::size_t i = 0; i < m_faces.size(); ++i )
2204                 {
2205                         if ( index != i && !plane3_inside( m_faces[index]->plane3(), m_faces[i]->plane3(), index < i ) ) {
2206                                 return false;
2207                         }
2208                 }
2209                 return true;
2210         }
2211
2212         /// \brief Removes edges that are smaller than the tolerance used when generating brush windings.
2213         void removeDegenerateEdges(){
2214                 for ( std::size_t i = 0; i < m_faces.size(); ++i )
2215                 {
2216                         Winding& winding = m_faces[i]->getWinding();
2217                         for ( Winding::iterator j = winding.begin(); j != winding.end(); )
2218                         {
2219                                 std::size_t index = std::distance( winding.begin(), j );
2220                                 std::size_t next = Winding_next( winding, index );
2221                                 if ( Edge_isDegenerate( winding[index].vertex, winding[next].vertex ) ) {
2222 #if BRUSH_DEGENERATE_DEBUG
2223                                         globalOutputStream() << "Brush::buildWindings: face " << i << ": degenerate edge adjacent to " << winding[index].adjacent << "\n";
2224 #endif
2225                                         Winding& other = m_faces[winding[index].adjacent]->getWinding();
2226                                         std::size_t adjacent = Winding_FindAdjacent( other, i );
2227                                         if ( adjacent != c_brush_maxFaces ) {
2228                                                 other.erase( other.begin() + adjacent );
2229                                         }
2230                                         winding.erase( j );
2231                                 }
2232                                 else
2233                                 {
2234                                         ++j;
2235                                 }
2236                         }
2237                 }
2238         }
2239
2240         /// \brief Invalidates faces that have only two vertices in their winding, while preserving edge-connectivity information.
2241         void removeDegenerateFaces(){
2242                 // save adjacency info for degenerate faces
2243                 for ( std::size_t i = 0; i < m_faces.size(); ++i )
2244                 {
2245                         Winding& degen = m_faces[i]->getWinding();
2246
2247                         if ( degen.numpoints == 2 ) {
2248 #if BRUSH_DEGENERATE_DEBUG
2249                                 globalOutputStream() << "Brush::buildWindings: face " << i << ": degenerate winding adjacent to " << degen[0].adjacent << ", " << degen[1].adjacent << "\n";
2250 #endif
2251                                 // this is an "edge" face, where the plane touches the edge of the brush
2252                                 {
2253                                         Winding& winding = m_faces[degen[0].adjacent]->getWinding();
2254                                         std::size_t index = Winding_FindAdjacent( winding, i );
2255                                         if ( index != c_brush_maxFaces ) {
2256 #if BRUSH_DEGENERATE_DEBUG
2257                                                 globalOutputStream() << "Brush::buildWindings: face " << degen[0].adjacent << ": remapping adjacent " << winding[index].adjacent << " to " << degen[1].adjacent << "\n";
2258 #endif
2259                                                 winding[index].adjacent = degen[1].adjacent;
2260                                         }
2261                                 }
2262
2263                                 {
2264                                         Winding& winding = m_faces[degen[1].adjacent]->getWinding();
2265                                         std::size_t index = Winding_FindAdjacent( winding, i );
2266                                         if ( index != c_brush_maxFaces ) {
2267 #if BRUSH_DEGENERATE_DEBUG
2268                                                 globalOutputStream() << "Brush::buildWindings: face " << degen[1].adjacent << ": remapping adjacent " << winding[index].adjacent << " to " << degen[0].adjacent << "\n";
2269 #endif
2270                                                 winding[index].adjacent = degen[0].adjacent;
2271                                         }
2272                                 }
2273
2274                                 degen.resize( 0 );
2275                         }
2276                 }
2277         }
2278
2279         /// \brief Removes edges that have the same adjacent-face as their immediate neighbour.
2280         void removeDuplicateEdges(){
2281                 // verify face connectivity graph
2282                 for ( std::size_t i = 0; i < m_faces.size(); ++i )
2283                 {
2284                         //if(m_faces[i]->contributes())
2285                         {
2286                                 Winding& winding = m_faces[i]->getWinding();
2287                                 for ( std::size_t j = 0; j != winding.numpoints; )
2288                                 {
2289                                         std::size_t next = Winding_next( winding, j );
2290                                         if ( winding[j].adjacent == winding[next].adjacent ) {
2291 #if BRUSH_DEGENERATE_DEBUG
2292                                                 globalOutputStream() << "Brush::buildWindings: face " << i << ": removed duplicate edge adjacent to face " << winding[j].adjacent << "\n";
2293 #endif
2294                                                 winding.erase( winding.begin() + next );
2295                                         }
2296                                         else
2297                                         {
2298                                                 ++j;
2299                                         }
2300                                 }
2301                         }
2302                 }
2303         }
2304
2305         /// \brief Removes edges that do not have a matching pair in their adjacent-face.
2306         void verifyConnectivityGraph(){
2307                 // verify face connectivity graph
2308                 for ( std::size_t i = 0; i < m_faces.size(); ++i )
2309                 {
2310                         //if(m_faces[i]->contributes())
2311                         {
2312                                 Winding& winding = m_faces[i]->getWinding();
2313                                 for ( Winding::iterator j = winding.begin(); j != winding.end(); )
2314                                 {
2315 #if BRUSH_CONNECTIVITY_DEBUG
2316                                         globalOutputStream() << "Brush::buildWindings: face " << i << ": adjacent to face " << ( *j ).adjacent << "\n";
2317 #endif
2318                                         // remove unidirectional graph edges
2319                                         if ( ( *j ).adjacent == c_brush_maxFaces
2320                                                  || Winding_FindAdjacent( m_faces[( *j ).adjacent]->getWinding(), i ) == c_brush_maxFaces ) {
2321 #if BRUSH_CONNECTIVITY_DEBUG
2322                                                 globalOutputStream() << "Brush::buildWindings: face " << i << ": removing unidirectional connectivity graph edge adjacent to face " << ( *j ).adjacent << "\n";
2323 #endif
2324                                                 winding.erase( j );
2325                                         }
2326                                         else
2327                                         {
2328                                                 ++j;
2329                                         }
2330                                 }
2331                         }
2332                 }
2333         }
2334
2335         /// \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.
2336         bool isBounded(){
2337                 for ( const_iterator i = begin(); i != end(); ++i )
2338                 {
2339                         if ( !( *i )->is_bounded() ) {
2340                                 return false;
2341                         }
2342                 }
2343                 return true;
2344         }
2345
2346         /// \brief Constructs the polygon windings for each face of the brush. Also updates the brush bounding-box and face texture-coordinates.
2347         bool buildWindings(){
2348
2349                 {
2350                         m_aabb_local = AABB();
2351
2352                         for ( std::size_t i = 0; i < m_faces.size(); ++i )
2353                         {
2354                                 Face& f = *m_faces[i];
2355
2356                                 if ( !plane3_valid( f.plane3() ) || !plane_unique( i ) ) {
2357                                         f.getWinding().resize( 0 );
2358                                 }
2359                                 else
2360                                 {
2361 #if BRUSH_CONNECTIVITY_DEBUG
2362                                         globalOutputStream() << "face: " << i << "\n";
2363 #endif
2364                                         windingForClipPlane( f.getWinding(), f.plane3() );
2365
2366                                         // update brush bounds
2367                                         const Winding& winding = f.getWinding();
2368                                         for ( Winding::const_iterator i = winding.begin(); i != winding.end(); ++i )
2369                                         {
2370                                                 aabb_extend_by_point_safe( m_aabb_local, ( *i ).vertex );
2371                                         }
2372
2373                                         // update texture coordinates
2374                                         f.EmitTextureCoordinates();
2375                                 }
2376                         }
2377                 }
2378
2379                 bool degenerate = !isBounded();
2380
2381                 if ( !degenerate ) {
2382                         // clean up connectivity information.
2383                         // these cleanups must be applied in a specific order.
2384                         removeDegenerateEdges();
2385                         removeDegenerateFaces();
2386                         removeDuplicateEdges();
2387                         verifyConnectivityGraph();
2388                 }
2389
2390                 return degenerate;
2391         }
2392
2393         /// \brief Constructs the face windings and updates anything that depends on them.
2394         void buildBRep();
2395 };
2396
2397
2398 class FaceInstance;
2399
2400 class FaceInstanceSet
2401 {
2402         typedef SelectionList<FaceInstance> FaceInstances;
2403         FaceInstances m_faceInstances;
2404 public:
2405         void insert( FaceInstance& faceInstance ){
2406                 m_faceInstances.append( faceInstance );
2407         }
2408
2409         void erase( FaceInstance& faceInstance ){
2410                 m_faceInstances.erase( faceInstance );
2411         }
2412
2413         template<typename Functor>
2414         void foreach( Functor functor ){
2415                 for ( FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i )
2416                 {
2417                         functor( *( *i ) );
2418                 }
2419         }
2420
2421         bool empty() const {
2422                 return m_faceInstances.empty();
2423         }
2424
2425         FaceInstance& last() const {
2426                 return m_faceInstances.back();
2427         }
2428 };
2429
2430 extern FaceInstanceSet g_SelectedFaceInstances;
2431
2432 typedef std::list<std::size_t> VertexSelection;
2433
2434 inline VertexSelection::iterator VertexSelection_find( VertexSelection& self, std::size_t value ){
2435         return std::find( self.begin(), self.end(), value );
2436 }
2437
2438 inline VertexSelection::const_iterator VertexSelection_find( const VertexSelection& self, std::size_t value ){
2439         return std::find( self.begin(), self.end(), value );
2440 }
2441
2442 inline VertexSelection::iterator VertexSelection_insert( VertexSelection& self, std::size_t value ){
2443         VertexSelection::iterator i = VertexSelection_find( self, value );
2444         if ( i == self.end() ) {
2445                 self.push_back( value );
2446                 return --self.end();
2447         }
2448         return i;
2449 }
2450
2451 inline void VertexSelection_erase( VertexSelection& self, std::size_t value ){
2452         VertexSelection::iterator i = VertexSelection_find( self, value );
2453         if ( i != self.end() ) {
2454                 self.erase( i );
2455         }
2456 }
2457
2458 inline bool triangle_reversed( std::size_t x, std::size_t y, std::size_t z ){
2459         return !( ( x < y && y < z ) || ( z < x && x < y ) || ( y < z && z < x ) );
2460 }
2461
2462 template<typename Element>
2463 inline Vector3 triangle_cross( const BasicVector3<Element>& x, const BasicVector3<Element> y, const BasicVector3<Element>& z ){
2464         return vector3_cross( y - x, z - x );
2465 }
2466
2467 template<typename Element>
2468 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 ){
2469         return vector3_dot( triangle_cross( x1, y1, z1 ), triangle_cross( x2, y2, z2 ) ) > 0;
2470 }
2471
2472
2473 typedef const Plane3* PlanePointer;
2474 typedef PlanePointer* PlanesIterator;
2475
2476 class VectorLightList : public LightList
2477 {
2478         typedef std::vector<const RendererLight*> Lights;
2479         Lights m_lights;
2480 public:
2481         void addLight( const RendererLight& light ){
2482                 m_lights.push_back( &light );
2483         }
2484
2485         void clear(){
2486                 m_lights.clear();
2487         }
2488
2489         void evaluateLights() const {
2490         }
2491
2492         void lightsChanged() const {
2493         }
2494
2495         void forEachLight( const RendererLightCallback& callback ) const {
2496                 for ( Lights::const_iterator i = m_lights.begin(); i != m_lights.end(); ++i )
2497                 {
2498                         callback( *( *i ) );
2499                 }
2500         }
2501 };
2502
2503 class FaceInstance
2504 {
2505         Face* m_face;
2506         ObservedSelectable m_selectable;
2507         ObservedSelectable m_selectableVertices;
2508         ObservedSelectable m_selectableEdges;
2509         SelectionChangeCallback m_selectionChanged;
2510
2511         VertexSelection m_vertexSelection;
2512         VertexSelection m_edgeSelection;
2513
2514 public:
2515         mutable VectorLightList m_lights;
2516
2517         FaceInstance( Face& face, const SelectionChangeCallback& observer ) :
2518                 m_face( &face ),
2519                 m_selectable( SelectedChangedCaller( *this ) ),
2520                 m_selectableVertices( observer ),
2521                 m_selectableEdges( observer ),
2522                 m_selectionChanged( observer ){
2523         }
2524
2525         FaceInstance( const FaceInstance& other ) :
2526                 m_face( other.m_face ),
2527                 m_selectable( SelectedChangedCaller( *this ) ),
2528                 m_selectableVertices( other.m_selectableVertices ),
2529                 m_selectableEdges( other.m_selectableEdges ),
2530                 m_selectionChanged( other.m_selectionChanged ){
2531         }
2532
2533         FaceInstance& operator=( const FaceInstance& other ){
2534                 m_face = other.m_face;
2535                 return *this;
2536         }
2537
2538         Face& getFace(){
2539                 return *m_face;
2540         }
2541
2542         const Face& getFace() const {
2543                 return *m_face;
2544         }
2545
2546         void selectedChanged( const Selectable& selectable ){
2547                 if ( selectable.isSelected() ) {
2548                         g_SelectedFaceInstances.insert( *this );
2549                 }
2550                 else
2551                 {
2552                         g_SelectedFaceInstances.erase( *this );
2553                 }
2554                 m_selectionChanged( selectable );
2555         }
2556
2557         typedef MemberCaller<FaceInstance, void(const Selectable&), &FaceInstance::selectedChanged> SelectedChangedCaller;
2558
2559         bool selectedVertices() const {
2560                 return !m_vertexSelection.empty();
2561         }
2562
2563         bool selectedEdges() const {
2564                 return !m_edgeSelection.empty();
2565         }
2566
2567         bool isSelected() const {
2568                 return m_selectable.isSelected();
2569         }
2570
2571         bool selectedComponents() const {
2572                 return selectedVertices() || selectedEdges() || isSelected();
2573         }
2574
2575         bool selectedComponents( SelectionSystem::EComponentMode mode ) const {
2576                 switch ( mode )
2577                 {
2578                 case SelectionSystem::eVertex:
2579                         return selectedVertices();
2580                 case SelectionSystem::eEdge:
2581                         return selectedEdges();
2582                 case SelectionSystem::eFace:
2583                         return isSelected();
2584                 default:
2585                         return false;
2586                 }
2587         }
2588
2589         void setSelected( SelectionSystem::EComponentMode mode, bool select ){
2590                 switch ( mode )
2591                 {
2592                 case SelectionSystem::eFace:
2593                         m_selectable.setSelected( select );
2594                         break;
2595                 case SelectionSystem::eVertex:
2596                         ASSERT_MESSAGE( !select, "select-all not supported" );
2597
2598                         m_vertexSelection.clear();
2599                         m_selectableVertices.setSelected( false );
2600                         break;
2601                 case SelectionSystem::eEdge:
2602                         ASSERT_MESSAGE( !select, "select-all not supported" );
2603
2604                         m_edgeSelection.clear();
2605                         m_selectableEdges.setSelected( false );
2606                         break;
2607                 default:
2608                         break;
2609                 }
2610         }
2611
2612         template<typename Functor>
2613         void SelectedVertices_foreach( Functor functor ) const {
2614                 for ( VertexSelection::const_iterator i = m_vertexSelection.begin(); i != m_vertexSelection.end(); ++i )
2615                 {
2616                         std::size_t index = Winding_FindAdjacent( getFace().getWinding(), *i );
2617                         if ( index != c_brush_maxFaces ) {
2618                                 functor( getFace().getWinding()[index].vertex );
2619                         }
2620                 }
2621         }
2622
2623         template<typename Functor>
2624         void SelectedEdges_foreach( Functor functor ) const {
2625                 for ( VertexSelection::const_iterator i = m_edgeSelection.begin(); i != m_edgeSelection.end(); ++i )
2626                 {
2627                         std::size_t index = Winding_FindAdjacent( getFace().getWinding(), *i );
2628                         if ( index != c_brush_maxFaces ) {
2629                                 const Winding& winding = getFace().getWinding();
2630                                 std::size_t adjacent = Winding_next( winding, index );
2631                                 functor( vector3_mid( winding[index].vertex, winding[adjacent].vertex ) );
2632                         }
2633                 }
2634         }
2635
2636         template<typename Functor>
2637         void SelectedFaces_foreach( Functor functor ) const {
2638                 if ( isSelected() ) {
2639                         functor( centroid() );
2640                 }
2641         }
2642
2643         template<typename Functor>
2644         void SelectedComponents_foreach( Functor functor ) const {
2645                 SelectedVertices_foreach( functor );
2646                 SelectedEdges_foreach( functor );
2647                 SelectedFaces_foreach( functor );
2648         }
2649
2650         void iterate_selected( AABB& aabb ) const {
2651                 SelectedComponents_foreach([&](const Vector3 &point) {
2652                         aabb_extend_by_point_safe(aabb, point);
2653                 });
2654         }
2655
2656         void iterate_selected( RenderablePointVector& points ) const {
2657                 SelectedComponents_foreach([&](const Vector3 &point) {
2658                         const Colour4b colour_selected(0, 0, 255, 255);
2659                         points.push_back(pointvertex_for_windingpoint(point, colour_selected));
2660                 });
2661         }
2662
2663         bool intersectVolume( const VolumeTest& volume, const Matrix4& localToWorld ) const {
2664                 return m_face->intersectVolume( volume, localToWorld );
2665         }
2666
2667         void render( Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld ) const {
2668                 if ( !m_face->isFiltered() && m_face->contributes() && intersectVolume( volume, localToWorld ) ) {
2669                         renderer.PushState();
2670                         if ( selectedComponents() ) {
2671                                 renderer.Highlight( Renderer::eFace );
2672                         }
2673                         m_face->render( renderer, localToWorld );
2674                         renderer.PopState();
2675                 }
2676         }
2677
2678         void testSelect( SelectionTest& test, SelectionIntersection& best ){
2679                 if ( !m_face->isFiltered() ) {
2680                         m_face->testSelect( test, best );
2681                 }
2682         }
2683
2684         void testSelect( Selector& selector, SelectionTest& test ){
2685                 SelectionIntersection best;
2686                 testSelect( test, best );
2687                 if ( best.valid() ) {
2688                         Selector_add( selector, m_selectable, best );
2689                 }
2690         }
2691
2692         void testSelect_centroid( Selector& selector, SelectionTest& test ){
2693                 if ( m_face->contributes() && !m_face->isFiltered() ) {
2694                         SelectionIntersection best;
2695                         m_face->testSelect_centroid( test, best );
2696                         if ( best.valid() ) {
2697                                 Selector_add( selector, m_selectable, best );
2698                         }
2699                 }
2700         }
2701
2702         void selectPlane( Selector& selector, const Line& line, PlanesIterator first, PlanesIterator last, const PlaneCallback& selectedPlaneCallback ){
2703                 for ( Winding::const_iterator i = getFace().getWinding().begin(); i != getFace().getWinding().end(); ++i )
2704                 {
2705                         Vector3 v( vector3_subtracted( line_closest_point( line, ( *i ).vertex ), ( *i ).vertex ) );
2706                         double dot = vector3_dot( getFace().plane3().normal(), v );
2707                         if ( dot <= 0 ) {
2708                                 return;
2709                         }
2710                 }
2711
2712                 Selector_add( selector, m_selectable );
2713
2714                 selectedPlaneCallback( getFace().plane3() );
2715         }
2716
2717         void selectReversedPlane( Selector& selector, const SelectedPlanes& selectedPlanes ){
2718                 if ( selectedPlanes.contains( plane3_flipped( getFace().plane3() ) ) ) {
2719                         Selector_add( selector, m_selectable );
2720                 }
2721         }
2722
2723         void transformComponents( const Matrix4& matrix ){
2724                 if ( isSelected() ) {
2725                         m_face->transform( matrix, false );
2726                 }
2727                 if ( selectedVertices() ) {
2728                         if ( m_vertexSelection.size() == 1 ) {
2729                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[1] );
2730                                 m_face->assign_planepts( m_face->m_move_planeptsTransformed );
2731                         }
2732                         else if ( m_vertexSelection.size() == 2 ) {
2733                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[1] );
2734                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[2] );
2735                                 m_face->assign_planepts( m_face->m_move_planeptsTransformed );
2736                         }
2737                         else if ( m_vertexSelection.size() >= 3 ) {
2738                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[0] );
2739                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[1] );
2740                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[2] );
2741                                 m_face->assign_planepts( m_face->m_move_planeptsTransformed );
2742                         }
2743                 }
2744                 if ( selectedEdges() ) {
2745                         if ( m_edgeSelection.size() == 1 ) {
2746                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[0] );
2747                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[1] );
2748                                 m_face->assign_planepts( m_face->m_move_planeptsTransformed );
2749                         }
2750                         else if ( m_edgeSelection.size() >= 2 ) {
2751                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[0] );
2752                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[1] );
2753                                 matrix4_transform_point( matrix, m_face->m_move_planeptsTransformed[2] );
2754                                 m_face->assign_planepts( m_face->m_move_planeptsTransformed );
2755                         }
2756                 }
2757         }
2758
2759         void snapto( float snap ){
2760                 m_face->snapto( snap );
2761         }
2762
2763         void snapComponents( float snap ){
2764                 if ( isSelected() ) {
2765                         snapto( snap );
2766                 }
2767                 if ( selectedVertices() ) {
2768                         vector3_snap( m_face->m_move_planepts[0], snap );
2769                         vector3_snap( m_face->m_move_planepts[1], snap );
2770                         vector3_snap( m_face->m_move_planepts[2], snap );
2771                         m_face->assign_planepts( m_face->m_move_planepts );
2772                         planepts_assign( m_face->m_move_planeptsTransformed, m_face->m_move_planepts );
2773                         m_face->freezeTransform();
2774                 }
2775                 if ( selectedEdges() ) {
2776                         vector3_snap( m_face->m_move_planepts[0], snap );
2777                         vector3_snap( m_face->m_move_planepts[1], snap );
2778                         vector3_snap( m_face->m_move_planepts[2], snap );
2779                         m_face->assign_planepts( m_face->m_move_planepts );
2780                         planepts_assign( m_face->m_move_planeptsTransformed, m_face->m_move_planepts );
2781                         m_face->freezeTransform();
2782                 }
2783         }
2784
2785         void update_move_planepts_vertex( std::size_t index ){
2786                 m_face->update_move_planepts_vertex( index, m_face->m_move_planepts );
2787         }
2788
2789         void update_move_planepts_vertex2( std::size_t index, std::size_t other ){
2790                 const std::size_t numpoints = m_face->getWinding().numpoints;
2791                 ASSERT_MESSAGE( index < numpoints, "select_vertex: invalid index" );
2792
2793                 const std::size_t opposite = Winding_Opposite( m_face->getWinding(), index, other );
2794
2795                 if ( triangle_reversed( index, other, opposite ) ) {
2796                         std::swap( index, other );
2797                 }
2798
2799                 ASSERT_MESSAGE(
2800                         triangles_same_winding(
2801                                 m_face->getWinding()[opposite].vertex,
2802                                 m_face->getWinding()[index].vertex,
2803                                 m_face->getWinding()[other].vertex,
2804                                 m_face->getWinding()[0].vertex,
2805                                 m_face->getWinding()[1].vertex,
2806                                 m_face->getWinding()[2].vertex
2807                                 ),
2808                         "update_move_planepts_vertex2: error"
2809                         );
2810
2811                 m_face->m_move_planepts[0] = m_face->getWinding()[opposite].vertex;
2812                 m_face->m_move_planepts[1] = m_face->getWinding()[index].vertex;
2813                 m_face->m_move_planepts[2] = m_face->getWinding()[other].vertex;
2814                 planepts_quantise( m_face->m_move_planepts, GRID_MIN ); // winding points are very inaccurate
2815         }
2816
2817         void update_selection_vertex(){
2818                 if ( m_vertexSelection.size() == 0 ) {
2819                         m_selectableVertices.setSelected( false );
2820                 }
2821                 else
2822                 {
2823                         m_selectableVertices.setSelected( true );
2824
2825                         if ( m_vertexSelection.size() == 1 ) {
2826                                 std::size_t index = Winding_FindAdjacent( getFace().getWinding(), *m_vertexSelection.begin() );
2827
2828                                 if ( index != c_brush_maxFaces ) {
2829                                         update_move_planepts_vertex( index );
2830                                 }
2831                         }
2832                         else if ( m_vertexSelection.size() == 2 ) {
2833                                 std::size_t index = Winding_FindAdjacent( getFace().getWinding(), *m_vertexSelection.begin() );
2834                                 std::size_t other = Winding_FindAdjacent( getFace().getWinding(), *( ++m_vertexSelection.begin() ) );
2835
2836                                 if ( index != c_brush_maxFaces
2837                                          && other != c_brush_maxFaces ) {
2838                                         update_move_planepts_vertex2( index, other );
2839                                 }
2840                         }
2841                 }
2842         }
2843
2844         void select_vertex( std::size_t index, bool select ){
2845                 if ( select ) {
2846                         VertexSelection_insert( m_vertexSelection, getFace().getWinding()[index].adjacent );
2847                 }
2848                 else
2849                 {
2850                         VertexSelection_erase( m_vertexSelection, getFace().getWinding()[index].adjacent );
2851                 }
2852
2853                 SceneChangeNotify();
2854                 update_selection_vertex();
2855         }
2856
2857         bool selected_vertex( std::size_t index ) const {
2858                 return VertexSelection_find( m_vertexSelection, getFace().getWinding()[index].adjacent ) != m_vertexSelection.end();
2859         }
2860
2861         void update_move_planepts_edge( std::size_t index ){
2862                 std::size_t numpoints = m_face->getWinding().numpoints;
2863                 ASSERT_MESSAGE( index < numpoints, "select_edge: invalid index" );
2864
2865                 std::size_t adjacent = Winding_next( m_face->getWinding(), index );
2866                 std::size_t opposite = Winding_Opposite( m_face->getWinding(), index );
2867                 m_face->m_move_planepts[0] = m_face->getWinding()[index].vertex;
2868                 m_face->m_move_planepts[1] = m_face->getWinding()[adjacent].vertex;
2869                 m_face->m_move_planepts[2] = m_face->getWinding()[opposite].vertex;
2870                 planepts_quantise( m_face->m_move_planepts, GRID_MIN ); // winding points are very inaccurate
2871         }
2872
2873         void update_selection_edge(){
2874                 if ( m_edgeSelection.size() == 0 ) {
2875                         m_selectableEdges.setSelected( false );
2876                 }
2877                 else
2878                 {
2879                         m_selectableEdges.setSelected( true );
2880
2881                         if ( m_edgeSelection.size() == 1 ) {
2882                                 std::size_t index = Winding_FindAdjacent( getFace().getWinding(), *m_edgeSelection.begin() );
2883
2884                                 if ( index != c_brush_maxFaces ) {
2885                                         update_move_planepts_edge( index );
2886                                 }
2887                         }
2888                 }
2889         }
2890
2891         void select_edge( std::size_t index, bool select ){
2892                 if ( select ) {
2893                         VertexSelection_insert( m_edgeSelection, getFace().getWinding()[index].adjacent );
2894                 }
2895                 else
2896                 {
2897                         VertexSelection_erase( m_edgeSelection, getFace().getWinding()[index].adjacent );
2898                 }
2899
2900                 SceneChangeNotify();
2901                 update_selection_edge();
2902         }
2903
2904         bool selected_edge( std::size_t index ) const {
2905                 return VertexSelection_find( m_edgeSelection, getFace().getWinding()[index].adjacent ) != m_edgeSelection.end();
2906         }
2907
2908         const Vector3& centroid() const {
2909                 return m_face->centroid();
2910         }
2911
2912         void connectivityChanged(){
2913                 // This occurs when a face is added or removed.
2914                 // The current vertex and edge selections no longer valid and must be cleared.
2915                 m_vertexSelection.clear();
2916                 m_selectableVertices.setSelected( false );
2917                 m_edgeSelection.clear();
2918                 m_selectableEdges.setSelected( false );
2919         }
2920 };
2921
2922 class BrushClipPlane : public OpenGLRenderable
2923 {
2924         Plane3 m_plane;
2925         Winding m_winding;
2926         static Shader* m_state;
2927 public:
2928         static void constructStatic(){
2929                 m_state = GlobalShaderCache().capture( "$CLIPPER_OVERLAY" );
2930         }
2931
2932         static void destroyStatic(){
2933                 GlobalShaderCache().release( "$CLIPPER_OVERLAY" );
2934         }
2935
2936         void setPlane( const Brush& brush, const Plane3& plane ){
2937                 m_plane = plane;
2938                 if ( plane3_valid( m_plane ) ) {
2939                         brush.windingForClipPlane( m_winding, m_plane );
2940                 }
2941                 else
2942                 {
2943                         m_winding.resize( 0 );
2944                 }
2945         }
2946
2947         void render( RenderStateFlags state ) const {
2948                 if ( ( state & RENDER_FILL ) != 0 ) {
2949                         Winding_Draw( m_winding, m_plane.normal(), state );
2950                 }
2951                 else
2952                 {
2953                         Winding_DrawWireframe( m_winding );
2954
2955                         // also draw a line indicating the direction of the cut
2956                         Vector3 lineverts[2];
2957                         Winding_Centroid( m_winding, m_plane, lineverts[0] );
2958                         lineverts[1] = vector3_added( lineverts[0], vector3_scaled( m_plane.normal(), Brush::m_maxWorldCoord * 4 ) );
2959
2960                         glVertexPointer( 3, GL_FLOAT, sizeof( Vector3 ), &lineverts[0] );
2961                         glDrawArrays( GL_LINES, 0, GLsizei( 2 ) );
2962                 }
2963         }
2964
2965         void render( Renderer& renderer, const VolumeTest& volume, const Matrix4& localToWorld ) const {
2966                 renderer.SetState( m_state, Renderer::eWireframeOnly );
2967                 renderer.SetState( m_state, Renderer::eFullMaterials );
2968                 renderer.addRenderable( *this, localToWorld );
2969         }
2970 };
2971
2972 inline void Face_addLight( const FaceInstance& face, const Matrix4& localToWorld, const RendererLight& light ){
2973         const Plane3& facePlane = face.getFace().plane3();
2974         const Vector3& origin = light.aabb().origin;
2975         Plane3 tmp( plane3_transformed( Plane3( facePlane.normal(), -facePlane.dist() ), localToWorld ) );
2976         if ( !plane3_test_point( tmp, origin )
2977                  || !plane3_test_point( tmp, vector3_added( origin, light.offset() ) ) ) {
2978                 face.m_lights.addLight( light );
2979         }
2980 }
2981
2982
2983 typedef std::vector<FaceInstance> FaceInstances;
2984
2985 class EdgeInstance : public Selectable
2986 {
2987         FaceInstances& m_faceInstances;
2988         SelectableEdge* m_edge;
2989
2990         void select_edge( bool select ){
2991                 FaceVertexId faceVertex = m_edge->m_faceVertex;
2992                 m_faceInstances[faceVertex.getFace()].select_edge( faceVertex.getVertex(), select );
2993                 faceVertex = next_edge( m_edge->m_faces, faceVertex );
2994                 m_faceInstances[faceVertex.getFace()].select_edge( faceVertex.getVertex(), select );
2995         }
2996
2997         bool selected_edge() const {
2998                 FaceVertexId faceVertex = m_edge->m_faceVertex;
2999                 if ( !m_faceInstances[faceVertex.getFace()].selected_edge( faceVertex.getVertex() ) ) {
3000                         return false;
3001                 }
3002                 faceVertex = next_edge( m_edge->m_faces, faceVertex );
3003                 if ( !m_faceInstances[faceVertex.getFace()].selected_edge( faceVertex.getVertex() ) ) {
3004                         return false;
3005                 }
3006
3007                 return true;
3008         }
3009
3010 public:
3011         EdgeInstance( FaceInstances& faceInstances, SelectableEdge& edge )
3012                 : m_faceInstances( faceInstances ), m_edge( &edge ){
3013         }
3014         EdgeInstance& operator=( const EdgeInstance& other ){
3015                 m_edge = other.m_edge;
3016                 return *this;
3017         }
3018
3019         void setSelected( bool select ){
3020                 select_edge( select );
3021         }
3022
3023         bool isSelected() const {
3024                 return selected_edge();
3025         }
3026
3027
3028         void testSelect( Selector& selector, SelectionTest& test ){
3029                 SelectionIntersection best;
3030                 m_edge->testSelect( test, best );
3031                 if ( best.valid() ) {
3032                         Selector_add( selector, *this, best );
3033                 }
3034         }
3035 };
3036
3037 class VertexInstance : public Selectable
3038 {
3039         FaceInstances& m_faceInstances;
3040         SelectableVertex* m_vertex;
3041
3042         void select_vertex( bool select ){
3043                 FaceVertexId faceVertex = m_vertex->m_faceVertex;
3044                 do
3045                 {
3046                         m_faceInstances[faceVertex.getFace()].select_vertex( faceVertex.getVertex(), select );
3047                         faceVertex = next_vertex( m_vertex->m_faces, faceVertex );
3048                 }
3049                 while ( faceVertex.getFace() != m_vertex->m_faceVertex.getFace() );
3050         }
3051
3052         bool selected_vertex() const {
3053                 FaceVertexId faceVertex = m_vertex->m_faceVertex;
3054                 do
3055                 {
3056                         if ( !m_faceInstances[faceVertex.getFace()].selected_vertex( faceVertex.getVertex() ) ) {
3057                                 return false;
3058                         }
3059                         faceVertex = next_vertex( m_vertex->m_faces, faceVertex );
3060                 }
3061                 while ( faceVertex.getFace() != m_vertex->m_faceVertex.getFace() );
3062                 return true;
3063         }
3064
3065         public:
3066         VertexInstance( FaceInstances& faceInstances, SelectableVertex& vertex )
3067                 : m_faceInstances( faceInstances ), m_vertex( &vertex ){
3068         }
3069         VertexInstance& operator=( const VertexInstance& other ){
3070                 m_vertex = other.m_vertex;
3071                 return *this;
3072         }
3073
3074         void setSelected( bool select ){
3075                 select_vertex( select );
3076         }
3077
3078         bool isSelected() const {
3079                 return selected_vertex();
3080         }
3081
3082         void testSelect( Selector& selector, SelectionTest& test ){
3083                 SelectionIntersection best;
3084                 m_vertex->testSelect( test, best );
3085                 if ( best.valid() ) {
3086                         Selector_add( selector, *this, best );
3087                 }
3088         }
3089 };
3090
3091 class BrushInstanceVisitor
3092 {
3093 public:
3094         virtual void visit( FaceInstance& face ) const = 0;
3095 };
3096
3097 class BrushInstance :
3098         public BrushObserver,
3099         public scene::Instance,
3100         public Selectable,
3101         public Renderable,
3102         public SelectionTestable,
3103         public ComponentSelectionTestable,
3104         public ComponentEditable,
3105         public ComponentSnappable,
3106         public PlaneSelectable,
3107         public LightCullable
3108 {
3109         class TypeCasts
3110         {
3111                 InstanceTypeCastTable m_casts;
3112         public:
3113                 TypeCasts(){
3114                         InstanceStaticCast<BrushInstance, Selectable>::install( m_casts );
3115                         InstanceContainedCast<BrushInstance, Bounded>::install( m_casts );
3116                         InstanceContainedCast<BrushInstance, Cullable>::install( m_casts );
3117                         InstanceStaticCast<BrushInstance, Renderable>::install( m_casts );
3118                         InstanceStaticCast<BrushInstance, SelectionTestable>::install( m_casts );
3119                         InstanceStaticCast<BrushInstance, ComponentSelectionTestable>::install( m_casts );
3120                         InstanceStaticCast<BrushInstance, ComponentEditable>::install( m_casts );
3121                         InstanceStaticCast<BrushInstance, ComponentSnappable>::install( m_casts );
3122                         InstanceStaticCast<BrushInstance, PlaneSelectable>::install( m_casts );
3123                         InstanceIdentityCast<BrushInstance>::install( m_casts );
3124                         InstanceContainedCast<BrushInstance, Transformable>::install( m_casts );
3125                 }
3126
3127                 InstanceTypeCastTable& get(){
3128                         return m_casts;
3129                 }
3130         };
3131
3132
3133         Brush& m_brush;
3134
3135         FaceInstances m_faceInstances;
3136
3137         typedef std::vector<EdgeInstance> EdgeInstances;
3138         EdgeInstances m_edgeInstances;
3139         typedef std::vector<VertexInstance> VertexInstances;
3140         VertexInstances m_vertexInstances;
3141
3142         ObservedSelectable m_selectable;
3143
3144         mutable RenderableWireframe m_render_wireframe;
3145         mutable RenderablePointVector m_render_selected;
3146         mutable AABB m_aabb_component;
3147         mutable Array<PointVertex> m_faceCentroidPointsCulled;
3148         RenderablePointArray m_render_faces_wireframe;
3149         mutable bool m_viewChanged;   // requires re-evaluation of view-dependent cached data
3150
3151         BrushClipPlane m_clipPlane;
3152
3153         static Shader* m_state_selpoint;
3154
3155         const LightList* m_lightList;
3156
3157         TransformModifier m_transform;
3158
3159         BrushInstance( const BrushInstance& other ); // NOT COPYABLE
3160         BrushInstance& operator=( const BrushInstance& other ); // NOT ASSIGNABLE
3161
3162 public:
3163         static Counter* m_counter;
3164
3165         typedef LazyStatic<TypeCasts> StaticTypeCasts;
3166
3167         void lightsChanged(){
3168                 m_lightList->lightsChanged();
3169         }
3170
3171         typedef MemberCaller<BrushInstance, void(), &BrushInstance::lightsChanged> LightsChangedCaller;
3172
3173         STRING_CONSTANT( Name, "BrushInstance" );
3174
3175         BrushInstance( const scene::Path& path, scene::Instance* parent, Brush& brush ) :
3176                 Instance( path, parent, this, StaticTypeCasts::instance().get() ),
3177                 m_brush( brush ),
3178                 m_selectable( SelectedChangedCaller( *this ) ),
3179                 m_render_selected( GL_POINTS ),
3180                 m_render_faces_wireframe( m_faceCentroidPointsCulled, GL_POINTS ),
3181                 m_viewChanged( false ),
3182                 m_transform( Brush::TransformChangedCaller( m_brush ), ApplyTransformCaller( *this ) ){
3183                 m_brush.instanceAttach( Instance::path() );
3184                 m_brush.attach( *this );
3185                 m_counter->increment();
3186
3187                 m_lightList = &GlobalShaderCache().attach( *this );
3188                 m_brush.m_lightsChanged = LightsChangedCaller( *this ); ///\todo Make this work with instancing.
3189
3190                 Instance::setTransformChangedCallback( LightsChangedCaller( *this ) );
3191         }
3192
3193         ~BrushInstance(){
3194                 Instance::setTransformChangedCallback( Callback<void()>() );
3195
3196                 m_brush.m_lightsChanged = Callback<void()>();
3197                 GlobalShaderCache().detach( *this );
3198
3199                 m_counter->decrement();
3200                 m_brush.detach( *this );
3201                 m_brush.instanceDetach( Instance::path() );
3202         }
3203
3204         Brush& getBrush(){
3205                 return m_brush;
3206         }
3207         const Brush& getBrush() const {
3208                 return m_brush;
3209         }
3210
3211         Bounded& get( NullType<Bounded>){
3212                 return m_brush;
3213         }
3214
3215         Cullable& get( NullType<Cullable>){
3216                 return m_brush;
3217         }
3218
3219         Transformable& get( NullType<Transformable>){
3220                 return m_transform;
3221         }
3222
3223         void selectedChanged( const Selectable& selectable ){
3224                 GlobalSelectionSystem().getObserver ( SelectionSystem::ePrimitive )( selectable );
3225                 GlobalSelectionSystem().onSelectedChanged( *this, selectable );
3226
3227                 Instance::selectedChanged();
3228         }
3229         typedef MemberCaller<BrushInstance, void(const Selectable&), &BrushInstance::selectedChanged> SelectedChangedCaller;
3230
3231         void selectedChangedComponent( const Selectable& selectable ){
3232                 GlobalSelectionSystem().getObserver ( SelectionSystem::eComponent )( selectable );
3233                 GlobalSelectionSystem().onComponentSelection( *this, selectable );
3234         }
3235         typedef MemberCaller<BrushInstance, void(const Selectable&), &BrushInstance::selectedChangedComponent> SelectedChangedComponentCaller;
3236
3237         const BrushInstanceVisitor& forEachFaceInstance( const BrushInstanceVisitor& visitor ){
3238                 for ( FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i )
3239                 {
3240                         visitor.visit( *i );
3241                 }
3242                 return visitor;
3243         }
3244
3245         static void constructStatic(){
3246                 m_state_selpoint = GlobalShaderCache().capture( "$SELPOINT" );
3247         }
3248
3249         static void destroyStatic(){
3250                 GlobalShaderCache().release( "$SELPOINT" );
3251         }
3252
3253         void clear(){
3254                 m_faceInstances.clear();
3255         }
3256
3257         void reserve( std::size_t size ){
3258                 m_faceInstances.reserve( size );
3259         }
3260
3261         void push_back( Face& face ){
3262                 m_faceInstances.push_back( FaceInstance( face, SelectedChangedComponentCaller( *this ) ) );
3263         }
3264
3265         void pop_back(){
3266                 ASSERT_MESSAGE( !m_faceInstances.empty(), "erasing invalid element" );
3267                 m_faceInstances.pop_back();
3268         }
3269
3270         void erase( std::size_t index ){
3271                 ASSERT_MESSAGE( index < m_faceInstances.size(), "erasing invalid element" );
3272                 m_faceInstances.erase( m_faceInstances.begin() + index );
3273         }
3274
3275         void connectivityChanged(){
3276                 for ( FaceInstances::iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i )
3277                 {
3278                         ( *i ).connectivityChanged();
3279                 }
3280         }
3281
3282         void edge_clear(){
3283                 m_edgeInstances.clear();
3284         }
3285
3286         void edge_push_back( SelectableEdge& edge ){
3287                 m_edgeInstances.push_back( EdgeInstance( m_faceInstances, edge ) );
3288         }
3289
3290         void vertex_clear(){
3291                 m_vertexInstances.clear();
3292         }
3293
3294         void vertex_push_back( SelectableVertex& vertex ){
3295                 m_vertexInstances.push_back( VertexInstance( m_faceInstances, vertex ) );
3296         }
3297
3298         void DEBUG_verify() const {
3299                 ASSERT_MESSAGE( m_faceInstances.size() == m_brush.DEBUG_size(), "FATAL: mismatch" );
3300         }
3301
3302         bool isSelected() const {
3303                 return m_selectable.isSelected();
3304         }
3305
3306         void setSelected( bool select ){
3307                 m_selectable.setSelected( select );
3308         }
3309
3310         void update_selected() const {
3311                 m_render_selected.clear();
3312                 for ( FaceInstances::const_iterator i = m_faceInstances.begin(); i != m_faceInstances.end(); ++i )
3313                 {
3314                         if ( ( *i ).getFace().contributes() ) {
3315                                 ( *i