minor refactoring
[xonotic/netradiant.git] / radiant / selection.cpp
1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
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 #include "selection.h"
23
24 #include "debugging/debugging.h"
25
26 #include <map>
27 #include <list>
28 #include <set>
29
30 #include "windowobserver.h"
31 #include "iundo.h"
32 #include "ientity.h"
33 #include "cullable.h"
34 #include "renderable.h"
35 #include "selectable.h"
36 #include "editable.h"
37
38 #include "math/frustum.h"
39 #include "signal/signal.h"
40 #include "generic/object.h"
41 #include "selectionlib.h"
42 #include "render.h"
43 #include "view.h"
44 #include "renderer.h"
45 #include "stream/stringstream.h"
46 #include "eclasslib.h"
47 #include "generic/bitfield.h"
48 #include "generic/static.h"
49 #include "pivot.h"
50 #include "stringio.h"
51 #include "container/container.h"
52
53 #include "grid.h"
54
55 struct Pivot2World
56 {
57   Matrix4 m_worldSpace;
58   Matrix4 m_viewpointSpace;
59   Matrix4 m_viewplaneSpace;
60   Vector3 m_axis_screen;
61
62   void update(const Matrix4& pivot2world, const Matrix4& modelview, const Matrix4& projection, const Matrix4& viewport)
63   {
64     Pivot2World_worldSpace(m_worldSpace, pivot2world, modelview, projection, viewport);
65     Pivot2World_viewpointSpace(m_viewpointSpace, m_axis_screen, pivot2world, modelview, projection, viewport);
66     Pivot2World_viewplaneSpace(m_viewplaneSpace, pivot2world, modelview, projection, viewport);
67   }
68 };
69
70
71 void point_for_device_point(Vector3& point, const Matrix4& device2object, const float x, const float y, const float z)
72 {
73   // transform from normalised device coords to object coords
74   point = vector4_projected(matrix4_transformed_vector4(device2object, Vector4(x, y, z, 1)));
75 }
76
77 void ray_for_device_point(Ray& ray, const Matrix4& device2object, const float x, const float y)
78 {
79     // point at x, y, zNear
80   point_for_device_point(ray.origin, device2object, x, y, -1);
81
82   // point at x, y, zFar
83   point_for_device_point(ray.direction, device2object, x, y, 1);
84
85   // construct ray
86   vector3_subtract(ray.direction, ray.origin);
87   vector3_normalise(ray.direction);
88 }
89
90 bool sphere_intersect_ray(const Vector3& origin, float radius, const Ray& ray, Vector3& intersection)
91 {
92   intersection = vector3_subtracted(origin, ray.origin);
93   const double a = vector3_dot(intersection, ray.direction);
94   const double d = radius * radius - (vector3_dot(intersection, intersection) - a * a);
95
96   if(d > 0)
97   {
98     intersection = vector3_added(ray.origin, vector3_scaled(ray.direction, a - sqrt(d)));
99     return true;
100   }
101   else
102   {
103     intersection = vector3_added( ray.origin, vector3_scaled(ray.direction, a));
104     return false;
105   }
106 }
107
108 void ray_intersect_ray(const Ray& ray, const Ray& other, Vector3& intersection)
109 {
110   intersection = vector3_subtracted(ray.origin, other.origin);
111   //float a = 1;//vector3_dot(ray.direction, ray.direction);        // always >= 0
112   double dot = vector3_dot(ray.direction, other.direction);
113   //float c = 1;//vector3_dot(other.direction, other.direction);        // always >= 0
114   double d = vector3_dot(ray.direction, intersection);
115   double e = vector3_dot(other.direction, intersection);
116   double D = 1 - dot*dot;//a*c - dot*dot;       // always >= 0
117
118   if (D < 0.000001)
119   {
120     // the lines are almost parallel
121     intersection = vector3_added(other.origin, vector3_scaled(other.direction, e));
122   }
123   else
124   {
125     intersection = vector3_added(other.origin, vector3_scaled(other.direction, (e - dot*d) / D));
126   }    
127 }
128
129 const Vector3 g_origin(0, 0, 0);
130 const float g_radius = 64;
131
132 void point_on_sphere(Vector3& point, const Matrix4& device2object, const float x, const float y)
133 {
134   Ray ray;
135   ray_for_device_point(ray, device2object, x, y);
136   sphere_intersect_ray(g_origin, g_radius, ray, point);
137 }
138
139 void point_on_axis(Vector3& point, const Vector3& axis, const Matrix4& device2object, const float x, const float y)
140 {
141   Ray ray;
142   ray_for_device_point(ray, device2object, x, y);
143   ray_intersect_ray(ray, Ray(Vector3(0, 0, 0), axis), point);
144 }
145
146 void point_on_plane(Vector3& point, const Matrix4& device2object, const float x, const float y)
147 {
148   Matrix4 object2device(matrix4_full_inverse(device2object));
149   point = vector4_projected(matrix4_transformed_vector4(device2object, Vector4(x, y, object2device[14] / object2device[15], 1)));
150 }
151
152 //! a and b are unit vectors .. returns angle in radians
153 inline float angle_between(const Vector3& a, const Vector3& b)
154 {
155   return static_cast<float>(2.0 * atan2(
156     vector3_length(vector3_subtracted(a, b)),
157     vector3_length(vector3_added(a, b))
158   ));
159 }
160
161
162 #if defined(_DEBUG)
163 class test_quat
164 {
165 public:
166   test_quat(const Vector3& from, const Vector3& to)
167   {
168     Vector4 quaternion(quaternion_for_unit_vectors(from, to));
169     Matrix4 matrix(matrix4_rotation_for_quaternion(quaternion_multiplied_by_quaternion(quaternion, c_quaternion_identity)));
170   }
171 private:
172 };
173
174 static test_quat bleh(g_vector3_axis_x, g_vector3_axis_y);
175 #endif
176
177 //! axis is a unit vector
178 inline void constrain_to_axis(Vector3& vec, const Vector3& axis)
179 {
180   vec = vector3_normalised(vector3_added(vec, vector3_scaled(axis, -vector3_dot(vec, axis))));
181 }
182
183 //! a and b are unit vectors .. a and b must be orthogonal to axis .. returns angle in radians
184 float angle_for_axis(const Vector3& a, const Vector3& b, const Vector3& axis)
185 {
186   if(vector3_dot(axis, vector3_cross(a, b)) > 0.0)
187     return angle_between(a, b);
188   else
189     return -angle_between(a, b);
190 }
191
192 float distance_for_axis(const Vector3& a, const Vector3& b, const Vector3& axis)
193 {
194   return static_cast<float>(vector3_dot(b, axis) - vector3_dot(a, axis));
195 }
196
197 class Manipulatable
198 {
199 public:
200   virtual void Construct(const Matrix4& device2manip, const float x, const float y) = 0;
201   virtual void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y) = 0;
202 };
203
204 void transform_local2object(Matrix4& object, const Matrix4& local, const Matrix4& local2object)
205 {
206   object = matrix4_multiplied_by_matrix4(
207     matrix4_multiplied_by_matrix4(local2object, local),
208     matrix4_full_inverse(local2object)
209   );
210 }
211
212 class Rotatable
213 {
214 public:
215   virtual void rotate(const Quaternion& rotation) = 0;
216 };
217
218 class RotateFree : public Manipulatable
219 {
220   Vector3 m_start;
221   Rotatable& m_rotatable;
222 public:
223   RotateFree(Rotatable& rotatable)
224     : m_rotatable(rotatable)
225   {
226   }
227   void Construct(const Matrix4& device2manip, const float x, const float y)
228   {
229     point_on_sphere(m_start, device2manip, x, y);
230     vector3_normalise(m_start);
231   }
232   void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y)
233   {
234     Vector3 current;
235
236     point_on_sphere(current, device2manip, x, y);
237     vector3_normalise(current);
238
239     m_rotatable.rotate(quaternion_for_unit_vectors(m_start, current));
240   }
241 };
242
243 class RotateAxis : public Manipulatable
244 {
245   Vector3 m_axis;
246   Vector3 m_start;
247   Rotatable& m_rotatable;
248 public:
249   RotateAxis(Rotatable& rotatable)
250     : m_rotatable(rotatable)
251   {
252   }
253   void Construct(const Matrix4& device2manip, const float x, const float y)
254   {
255     point_on_sphere(m_start, device2manip, x, y);
256     constrain_to_axis(m_start, m_axis);
257   }
258   /// \brief Converts current position to a normalised vector orthogonal to axis.
259   void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y)
260   {
261     Vector3 current;
262     point_on_sphere(current, device2manip, x, y);
263     constrain_to_axis(current, m_axis);
264
265     m_rotatable.rotate(quaternion_for_axisangle(m_axis, angle_for_axis(m_start, current, m_axis)));
266   }
267
268   void SetAxis(const Vector3& axis)
269   {
270     m_axis = axis;
271   }
272 };
273
274 void translation_local2object(Vector3& object, const Vector3& local, const Matrix4& local2object)
275 {
276   object = matrix4_get_translation_vec3(
277     matrix4_multiplied_by_matrix4(
278       matrix4_translated_by_vec3(local2object, local),
279       matrix4_full_inverse(local2object)
280     )
281   );
282 }
283
284 class Translatable
285 {
286 public:
287   virtual void translate(const Vector3& translation) = 0;
288 };
289
290 class TranslateAxis : public Manipulatable
291 {
292   Vector3 m_start;
293   Vector3 m_axis;
294   Translatable& m_translatable;
295 public:
296   TranslateAxis(Translatable& translatable)
297     : m_translatable(translatable)
298   {
299   }
300   void Construct(const Matrix4& device2manip, const float x, const float y)
301   {
302     point_on_axis(m_start, m_axis, device2manip, x, y);
303   }
304   void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y)
305   {
306     Vector3 current;
307     point_on_axis(current, m_axis, device2manip, x, y);
308     current = vector3_scaled(m_axis, distance_for_axis(m_start, current, m_axis));
309
310     translation_local2object(current, current, manip2object);
311     vector3_snap(current, GetGridSize());
312
313     m_translatable.translate(current);
314   }
315
316   void SetAxis(const Vector3& axis)
317   {
318     m_axis = axis;
319   }
320 };
321
322 class TranslateFree : public Manipulatable
323 {
324 private:
325   Vector3 m_start;
326   Translatable& m_translatable;
327 public:
328   TranslateFree(Translatable& translatable)
329     : m_translatable(translatable)
330   {
331   }
332   void Construct(const Matrix4& device2manip, const float x, const float y)
333   {
334     point_on_plane(m_start, device2manip, x, y);
335   }
336   void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y)
337   {
338     Vector3 current;
339     point_on_plane(current, device2manip, x, y);
340     current = vector3_subtracted(current, m_start);
341
342     translation_local2object(current, current, manip2object);
343     vector3_snap(current, GetGridSize());
344     
345     m_translatable.translate(current);
346   }
347 };
348
349
350 class Scalable
351 {
352 public:
353   virtual void scale(const Vector3& scaling) = 0;
354 };
355
356
357 class ScaleAxis : public Manipulatable
358 {
359 private:
360   Vector3 m_start;
361   Vector3 m_axis;
362   Scalable& m_scalable;
363 public:
364   ScaleAxis(Scalable& scalable)
365     : m_scalable(scalable)
366   {
367   }
368   void Construct(const Matrix4& device2manip, const float x, const float y)
369   {
370     point_on_axis(m_start, m_axis, device2manip, x, y);
371   }
372   void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y)
373   {
374     Vector3 current;
375     point_on_axis(current, m_axis, device2manip, x, y);
376     Vector3 delta = vector3_subtracted(current, m_start);
377
378     translation_local2object(delta, delta, manip2object);
379     vector3_snap(delta, GetGridSize());
380     
381     Vector3 start(vector3_snapped(m_start, GetGridSize()));
382     Vector3 scale(
383       start[0] == 0 ? 1 : 1 + delta[0] / start[0],
384       start[1] == 0 ? 1 : 1 + delta[1] / start[1],
385       start[2] == 0 ? 1 : 1 + delta[2] / start[2]
386     );
387     m_scalable.scale(scale);
388   }
389
390   void SetAxis(const Vector3& axis)
391   {
392     m_axis = axis;
393   }
394 };
395
396 class ScaleFree : public Manipulatable
397 {
398 private:
399   Vector3 m_start;
400   Scalable& m_scalable;
401 public:
402   ScaleFree(Scalable& scalable)
403     : m_scalable(scalable)
404   {
405   }
406   void Construct(const Matrix4& device2manip, const float x, const float y)
407   {
408     point_on_plane(m_start, device2manip, x, y);
409   }
410   void Transform(const Matrix4& manip2object, const Matrix4& device2manip, const float x, const float y)
411   {
412     Vector3 current;
413     point_on_plane(current, device2manip, x, y);
414     Vector3 delta = vector3_subtracted(current, m_start);
415
416     translation_local2object(delta, delta, manip2object);
417     vector3_snap(delta, GetGridSize());
418     
419     Vector3 start(vector3_snapped(m_start, GetGridSize()));
420     Vector3 scale(
421       start[0] == 0 ? 1 : 1 + delta[0] / start[0],
422       start[1] == 0 ? 1 : 1 + delta[1] / start[1],
423       start[2] == 0 ? 1 : 1 + delta[2] / start[2]
424     );
425     m_scalable.scale(scale);
426   }
427 };
428
429
430
431
432
433
434
435
436
437
438 class RenderableClippedPrimitive : public OpenGLRenderable
439 {
440   struct primitive_t
441   {
442     PointVertex m_points[9];
443     std::size_t m_count;
444   };
445   Matrix4 m_inverse;
446   std::vector<primitive_t> m_primitives;
447 public:
448   Matrix4 m_world;
449
450   void render(RenderStateFlags state) const
451   {
452     for(std::size_t i=0; i<m_primitives.size(); ++i)
453     {
454       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_primitives[i].m_points[0].colour);
455       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_primitives[i].m_points[0].vertex);
456       switch(m_primitives[i].m_count)
457       {
458       case 1: break;
459       case 2: glDrawArrays(GL_LINES, 0, GLsizei(m_primitives[i].m_count)); break;
460       default: glDrawArrays(GL_POLYGON, 0, GLsizei(m_primitives[i].m_count)); break;
461       }
462     }
463   }
464
465   void construct(const Matrix4& world2device)
466   {
467     m_inverse = matrix4_full_inverse(world2device);
468     m_world = g_matrix4_identity;
469   }
470
471   void insert(const Vector4 clipped[9], std::size_t count)
472   {
473     add_one();
474
475     m_primitives.back().m_count = count;
476     for(std::size_t i=0; i<count; ++i)
477     {
478       Vector3 world_point(vector4_projected(matrix4_transformed_vector4(m_inverse, clipped[i])));
479       m_primitives.back().m_points[i].vertex = vertex3f_for_vector3(world_point);
480     }
481   }
482
483   void destroy()
484   {
485     m_primitives.clear();
486   }
487 private:
488   void add_one()
489   {
490     m_primitives.push_back(primitive_t());
491
492     const Colour4b colour_clipped(255, 127, 0, 255);
493
494     for(std::size_t i=0; i<9; ++i)
495       m_primitives.back().m_points[i].colour = colour_clipped;
496   }
497 };
498
499 #if defined(_DEBUG)
500 #define DEBUG_SELECTION
501 #endif
502
503 #if defined(DEBUG_SELECTION)
504 Shader* g_state_clipped;
505 RenderableClippedPrimitive g_render_clipped;
506 #endif
507
508
509 #if 0
510 // dist_Point_to_Line(): get the distance of a point to a line.
511 //    Input:  a Point P and a Line L (in any dimension)
512 //    Return: the shortest distance from P to L
513 float
514 dist_Point_to_Line( Point P, Line L)
515 {
516     Vector v = L.P1 - L.P0;
517     Vector w = P - L.P0;
518
519     double c1 = dot(w,v);
520     double c2 = dot(v,v);
521     double b = c1 / c2;
522
523     Point Pb = L.P0 + b * v;
524     return d(P, Pb);
525 }
526 #endif
527
528 class Segment3D
529 {
530   typedef Vector3 point_type;
531 public:
532   Segment3D(const point_type& _p0, const point_type& _p1)
533     : p0(_p0), p1(_p1)
534   {
535   }
536
537   point_type p0, p1;
538 };
539
540 typedef Vector3 Point3D;
541
542 inline double vector3_distance_squared(const Point3D& a, const Point3D& b)
543 {
544   return vector3_length_squared(b - a);
545 }
546
547 // get the distance of a point to a segment.
548 Point3D segment_closest_point_to_point(const Segment3D& segment, const Point3D& point)
549 {
550   Vector3 v = segment.p1 - segment.p0;
551   Vector3 w = point - segment.p0;
552
553   double c1 = vector3_dot(w,v);
554   if ( c1 <= 0 )
555     return segment.p0;
556
557   double c2 = vector3_dot(v,v);
558   if ( c2 <= c1 )
559     return segment.p1;
560
561   return Point3D(segment.p0 + v * (c1 / c2));
562 }
563
564 double segment_dist_to_point_3d(const Segment3D& segment, const Point3D& point)
565 {
566   return vector3_distance_squared(point, segment_closest_point_to_point(segment, point));
567 }
568
569 typedef Vector3 point_t;
570 typedef const Vector3* point_iterator_t;
571
572 // crossing number test for a point in a polygon
573 // This code is patterned after [Franklin, 2000]
574 bool point_test_polygon_2d( const point_t& P, point_iterator_t start, point_iterator_t finish )
575 {
576   std::size_t crossings = 0;
577
578   // loop through all edges of the polygon
579   for(point_iterator_t prev = finish-1, cur = start; cur != finish; prev = cur, ++cur)
580   {    // edge from (*prev) to (*cur)
581     if ((((*prev)[1] <= P[1]) && ((*cur)[1] > P[1]))    // an upward crossing
582     || (((*prev)[1] > P[1]) && ((*cur)[1] <= P[1])))
583     { // a downward crossing
584       // compute the actual edge-ray intersect x-coordinate
585       float vt = (float)(P[1] - (*prev)[1]) / ((*cur)[1] - (*prev)[1]);
586       if (P[0] < (*prev)[0] + vt * ((*cur)[0] - (*prev)[0])) // P[0] < intersect
587       {
588         ++crossings;   // a valid crossing of y=P[1] right of P[0]
589       }
590     }
591   }
592   return (crossings & 0x1) != 0;    // 0 if even (out), and 1 if odd (in)
593 }
594
595 inline double triangle_signed_area_XY(const Vector3& p0, const Vector3& p1, const Vector3& p2)
596 {
597   return ((p1[0] - p0[0]) * (p2[1] - p0[1])) - ((p2[0] - p0[0]) * (p1[1] - p0[1]));
598 }
599
600 enum clipcull_t
601 {
602   eClipCullNone,
603   eClipCullCW,
604   eClipCullCCW,
605 };
606
607
608 inline SelectionIntersection select_point_from_clipped(Vector4& clipped)
609 {
610   return SelectionIntersection(clipped[2] / clipped[3], static_cast<float>(vector3_length_squared(Vector3(clipped[0] / clipped[3], clipped[1] / clipped[3], 0))));
611 }
612
613 void BestPoint(std::size_t count, Vector4 clipped[9], SelectionIntersection& best, clipcull_t cull)
614 {
615   Vector3 normalised[9];
616
617   {
618     for(std::size_t i=0; i<count; ++i)
619     {
620       normalised[i][0] = clipped[i][0] / clipped[i][3];
621       normalised[i][1] = clipped[i][1] / clipped[i][3];
622       normalised[i][2] = clipped[i][2] / clipped[i][3];
623     }
624   }
625
626   if(cull != eClipCullNone && count > 2)
627   {      
628     double signed_area = triangle_signed_area_XY(normalised[0], normalised[1], normalised[2]);
629
630     if((cull == eClipCullCW && signed_area > 0)
631       || (cull == eClipCullCCW && signed_area < 0))
632       return;
633   }
634
635   if(count == 2)
636   {
637     Segment3D segment(normalised[0], normalised[1]);
638     Point3D point = segment_closest_point_to_point(segment, Vector3(0, 0, 0));
639     assign_if_closer(best, SelectionIntersection(point.z(), 0));
640   }
641   else if(count > 2 && !point_test_polygon_2d(Vector3(0, 0, 0), normalised, normalised + count))
642   {
643     point_iterator_t end = normalised + count;
644     for(point_iterator_t previous = end-1, current = normalised; current != end; previous = current, ++current)
645     {
646       Segment3D segment(*previous, *current);
647       Point3D point = segment_closest_point_to_point(segment, Vector3(0, 0, 0));
648       float depth = point.z();
649       point.z() = 0;
650       float distance = static_cast<float>(vector3_length_squared(point));
651
652       assign_if_closer(best, SelectionIntersection(depth, distance));
653     }
654   }
655   else if(count > 2)
656   {
657     assign_if_closer(
658       best,
659       SelectionIntersection(
660       static_cast<float>(ray_distance_to_plane(
661           Ray(Vector3(0, 0, 0), Vector3(0, 0, 1)),
662           plane3_for_points(normalised[0], normalised[1], normalised[2])
663         )), 
664         0
665       )
666     );
667   }
668
669 #if defined(DEBUG_SELECTION)
670     if(count >= 2)
671       g_render_clipped.insert(clipped, count);
672 #endif
673 }
674
675 void LineStrip_BestPoint(const Matrix4& local2view, const PointVertex* vertices, const std::size_t size, SelectionIntersection& best)
676 {
677   Vector4 clipped[2];
678   for(std::size_t i = 0; (i + 1) < size; ++i)
679   {
680     const std::size_t count = matrix4_clip_line(local2view, vertex3f_to_vector3(vertices[i].vertex), vertex3f_to_vector3(vertices[i + 1].vertex), clipped);
681     BestPoint(count, clipped, best, eClipCullNone);
682   }
683 }
684
685 void LineLoop_BestPoint(const Matrix4& local2view, const PointVertex* vertices, const std::size_t size, SelectionIntersection& best)
686 {
687   Vector4 clipped[2];
688   for(std::size_t i = 0; i < size; ++i)
689   {
690     const std::size_t count = matrix4_clip_line(local2view, vertex3f_to_vector3(vertices[i].vertex), vertex3f_to_vector3(vertices[(i+1)%size].vertex), clipped);
691     BestPoint(count, clipped, best, eClipCullNone);
692   }
693 }
694
695 void Line_BestPoint(const Matrix4& local2view, const PointVertex vertices[2], SelectionIntersection& best)
696 {
697   Vector4 clipped[2];
698   const std::size_t count = matrix4_clip_line(local2view, vertex3f_to_vector3(vertices[0].vertex), vertex3f_to_vector3(vertices[1].vertex), clipped);
699   BestPoint(count, clipped, best, eClipCullNone);
700 }
701
702 void Circle_BestPoint(const Matrix4& local2view, clipcull_t cull, const PointVertex* vertices, const std::size_t size, SelectionIntersection& best)
703 {
704   Vector4 clipped[9];
705   for(std::size_t i=0; i<size; ++i)
706   {
707     const std::size_t count = matrix4_clip_triangle(local2view, g_vector3_identity, vertex3f_to_vector3(vertices[i].vertex), vertex3f_to_vector3(vertices[(i+1)%size].vertex), clipped);
708     BestPoint(count, clipped, best, cull);
709   }
710 }
711
712 void Quad_BestPoint(const Matrix4& local2view, clipcull_t cull, const PointVertex* vertices, SelectionIntersection& best)
713 {
714   Vector4 clipped[9];
715   {
716     const std::size_t count = matrix4_clip_triangle(local2view, vertex3f_to_vector3(vertices[0].vertex), vertex3f_to_vector3(vertices[1].vertex), vertex3f_to_vector3(vertices[3].vertex), clipped);
717     BestPoint(count, clipped, best, cull);
718   }
719   {
720     const std::size_t count = matrix4_clip_triangle(local2view, vertex3f_to_vector3(vertices[1].vertex), vertex3f_to_vector3(vertices[2].vertex), vertex3f_to_vector3(vertices[3].vertex), clipped);
721           BestPoint(count, clipped, best, cull);
722   }
723 }
724
725 struct FlatShadedVertex
726 {
727   Vertex3f vertex;
728   Colour4b colour;
729   Normal3f normal;
730
731   FlatShadedVertex()
732   {
733   }
734 };
735
736
737 typedef FlatShadedVertex* FlatShadedVertexIterator;
738 void Triangles_BestPoint(const Matrix4& local2view, clipcull_t cull, FlatShadedVertexIterator first, FlatShadedVertexIterator last, SelectionIntersection& best)
739 {
740   for(FlatShadedVertexIterator x(first), y(first+1), z(first+2); x != last; x += 3, y += 3, z +=3)
741   {
742     Vector4 clipped[9];
743     BestPoint(
744       matrix4_clip_triangle(
745         local2view,
746         reinterpret_cast<const Vector3&>((*x).vertex),
747         reinterpret_cast<const Vector3&>((*y).vertex),
748         reinterpret_cast<const Vector3&>((*z).vertex),
749         clipped
750       ),
751       clipped,
752       best,
753       cull
754     );
755   }
756 }
757
758
759 typedef std::multimap<SelectionIntersection, Selectable*> SelectableSortedSet;
760
761 class SelectionPool : public Selector
762 {
763   SelectableSortedSet m_pool;
764   SelectionIntersection m_intersection;
765   Selectable* m_selectable;
766
767 public:
768   void pushSelectable(Selectable& selectable)
769   {
770     m_intersection = SelectionIntersection();
771     m_selectable = &selectable;
772   }
773   void popSelectable()
774   {
775     addSelectable(m_intersection, m_selectable);
776     m_intersection = SelectionIntersection();
777   }
778   void addIntersection(const SelectionIntersection& intersection)
779   {
780     assign_if_closer(m_intersection, intersection);
781   }
782   void addSelectable(const SelectionIntersection& intersection, Selectable* selectable)
783   {
784     if(intersection.valid())
785     {
786       m_pool.insert(SelectableSortedSet::value_type(intersection, selectable));
787     }
788   }
789
790   typedef SelectableSortedSet::iterator iterator;
791
792   iterator begin()
793   {
794     return m_pool.begin();
795   }
796   iterator end()
797   {
798     return m_pool.end();
799   }
800
801   bool failed()
802   {
803     return m_pool.empty();
804   }
805 };
806
807
808 const Colour4b g_colour_sphere(0, 0, 0, 255);
809 const Colour4b g_colour_screen(0, 255, 255, 255);
810 const Colour4b g_colour_selected(255, 255, 0, 255);
811
812 inline const Colour4b& colourSelected(const Colour4b& colour, bool selected)
813 {
814   return (selected) ? g_colour_selected : colour;
815 }
816
817 template<typename remap_policy>
818 inline void draw_semicircle(const std::size_t segments, const float radius, PointVertex* vertices, remap_policy remap)
819 {
820   const double increment = c_pi / double(segments << 2);
821
822   std::size_t count = 0;
823   float x = radius;
824   float y = 0;
825   remap_policy::set(vertices[segments << 2].vertex, -radius, 0, 0);
826   while(count < segments)
827   {
828     PointVertex* i = vertices + count;
829     PointVertex* j = vertices + ((segments << 1) - (count + 1));
830
831     PointVertex* k = i + (segments << 1);
832     PointVertex* l = j + (segments << 1);
833
834 #if 0
835     PointVertex* m = i + (segments << 2);
836     PointVertex* n = j + (segments << 2);
837     PointVertex* o = k + (segments << 2);
838     PointVertex* p = l + (segments << 2);
839 #endif
840
841     remap_policy::set(i->vertex, x,-y, 0);
842     remap_policy::set(k->vertex,-y,-x, 0);
843 #if 0
844     remap_policy::set(m->vertex,-x, y, 0);
845     remap_policy::set(o->vertex, y, x, 0);
846 #endif
847
848     ++count;
849
850     {
851       const double theta = increment * count;
852       x = static_cast<float>(radius * cos(theta));
853       y = static_cast<float>(radius * sin(theta));
854     }
855
856     remap_policy::set(j->vertex, y,-x, 0);
857     remap_policy::set(l->vertex,-x,-y, 0);
858 #if 0
859     remap_policy::set(n->vertex,-y, x, 0);
860     remap_policy::set(p->vertex, x, y, 0);
861 #endif
862   }
863 }
864
865 class Manipulator
866 {
867 public:
868   virtual Manipulatable* GetManipulatable() = 0;
869   virtual void testSelect(const View& view, const Matrix4& pivot2world)
870   {
871   }
872   virtual void render(Renderer& renderer, const VolumeTest& volume, const Matrix4& pivot2world)
873   {
874   }
875   virtual void setSelected(bool select) = 0;
876   virtual bool isSelected() const = 0;
877 };
878
879
880 inline Vector3 normalised_safe(const Vector3& self)
881 {
882   if(vector3_equal(self, g_vector3_identity))
883   {
884     return g_vector3_identity;
885   }
886   return vector3_normalised(self);
887 }
888
889
890 class RotateManipulator : public Manipulator
891 {
892   struct RenderableCircle : public OpenGLRenderable
893   {
894     Array<PointVertex> m_vertices;
895
896     RenderableCircle(std::size_t size) : m_vertices(size)
897     {
898     }
899     void render(RenderStateFlags state) const
900     {
901       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_vertices.data()->colour);
902       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_vertices.data()->vertex);
903       glDrawArrays(GL_LINE_LOOP, 0, GLsizei(m_vertices.size()));
904     }
905     void setColour(const Colour4b& colour)
906     {
907       for(Array<PointVertex>::iterator i = m_vertices.begin(); i != m_vertices.end(); ++i)
908       {
909         (*i).colour = colour;
910       }
911     }
912   };
913
914   struct RenderableSemiCircle : public OpenGLRenderable
915   {
916     Array<PointVertex> m_vertices;
917
918     RenderableSemiCircle(std::size_t size) : m_vertices(size)
919     {
920     }
921     void render(RenderStateFlags state) const
922     {
923       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_vertices.data()->colour);
924       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_vertices.data()->vertex);
925       glDrawArrays(GL_LINE_STRIP, 0, GLsizei(m_vertices.size()));
926     }
927     void setColour(const Colour4b& colour)
928     {
929       for(Array<PointVertex>::iterator i = m_vertices.begin(); i != m_vertices.end(); ++i)
930       {
931         (*i).colour = colour;
932       }
933     }
934   };
935
936   RotateFree m_free;
937   RotateAxis m_axis;
938   Vector3 m_axis_screen;
939   RenderableSemiCircle m_circle_x;
940   RenderableSemiCircle m_circle_y;
941   RenderableSemiCircle m_circle_z;
942   RenderableCircle m_circle_screen;
943   RenderableCircle m_circle_sphere;
944   SelectableBool m_selectable_x;
945   SelectableBool m_selectable_y;
946   SelectableBool m_selectable_z;
947   SelectableBool m_selectable_screen;
948   SelectableBool m_selectable_sphere;
949   Pivot2World m_pivot;
950   Matrix4 m_local2world_x;
951   Matrix4 m_local2world_y;
952   Matrix4 m_local2world_z;
953   bool m_circle_x_visible;
954   bool m_circle_y_visible;
955   bool m_circle_z_visible;
956 public:
957   static Shader* m_state_outer;
958
959   RotateManipulator(Rotatable& rotatable, std::size_t segments, float radius) :
960     m_free(rotatable),
961     m_axis(rotatable),
962     m_circle_x((segments << 2) + 1),
963     m_circle_y((segments << 2) + 1),
964     m_circle_z((segments << 2) + 1),
965     m_circle_screen(segments<<3),
966     m_circle_sphere(segments<<3)
967   {
968     draw_semicircle(segments, radius, m_circle_x.m_vertices.data(), RemapYZX());
969     draw_semicircle(segments, radius, m_circle_y.m_vertices.data(), RemapZXY());
970     draw_semicircle(segments, radius, m_circle_z.m_vertices.data(), RemapXYZ());
971
972     draw_circle(segments, radius * 1.15f, m_circle_screen.m_vertices.data(), RemapXYZ());
973     draw_circle(segments, radius, m_circle_sphere.m_vertices.data(), RemapXYZ());
974   }
975
976
977   void UpdateColours()
978   {
979     m_circle_x.setColour(colourSelected(g_colour_x, m_selectable_x.isSelected()));
980     m_circle_y.setColour(colourSelected(g_colour_y, m_selectable_y.isSelected()));
981     m_circle_z.setColour(colourSelected(g_colour_z, m_selectable_z.isSelected()));
982     m_circle_screen.setColour(colourSelected(g_colour_screen, m_selectable_screen.isSelected()));
983     m_circle_sphere.setColour(colourSelected(g_colour_sphere, false));
984   }
985   
986   void updateCircleTransforms()
987   {
988     Vector3 localViewpoint(matrix4_transformed_direction(matrix4_transposed(m_pivot.m_worldSpace), vector4_to_vector3(m_pivot.m_viewpointSpace.z())));
989
990     m_circle_x_visible = !vector3_equal_epsilon(g_vector3_axis_x, localViewpoint, 1e-6f);
991     if(m_circle_x_visible)
992     {
993       m_local2world_x = g_matrix4_identity;
994       vector4_to_vector3(m_local2world_x.y()) = normalised_safe(
995         vector3_cross(g_vector3_axis_x, localViewpoint)
996       );
997       vector4_to_vector3(m_local2world_x.z()) = normalised_safe(
998         vector3_cross(vector4_to_vector3(m_local2world_x.x()), vector4_to_vector3(m_local2world_x.y()))
999       );
1000       matrix4_premultiply_by_matrix4(m_local2world_x, m_pivot.m_worldSpace);
1001     }
1002
1003     m_circle_y_visible = !vector3_equal_epsilon(g_vector3_axis_y, localViewpoint, 1e-6f);
1004     if(m_circle_y_visible)
1005     {
1006       m_local2world_y = g_matrix4_identity;
1007       vector4_to_vector3(m_local2world_y.z()) = normalised_safe(
1008         vector3_cross(g_vector3_axis_y, localViewpoint)
1009       );
1010       vector4_to_vector3(m_local2world_y.x()) = normalised_safe(
1011         vector3_cross(vector4_to_vector3(m_local2world_y.y()), vector4_to_vector3(m_local2world_y.z()))
1012       );
1013       matrix4_premultiply_by_matrix4(m_local2world_y, m_pivot.m_worldSpace);
1014     }
1015
1016     m_circle_z_visible = !vector3_equal_epsilon(g_vector3_axis_z, localViewpoint, 1e-6f);
1017     if(m_circle_z_visible)
1018     {
1019       m_local2world_z = g_matrix4_identity;
1020       vector4_to_vector3(m_local2world_z.x()) = normalised_safe(
1021         vector3_cross(g_vector3_axis_z, localViewpoint)
1022       );
1023       vector4_to_vector3(m_local2world_z.y()) = normalised_safe(
1024         vector3_cross(vector4_to_vector3(m_local2world_z.z()), vector4_to_vector3(m_local2world_z.x()))
1025       );
1026       matrix4_premultiply_by_matrix4(m_local2world_z, m_pivot.m_worldSpace);
1027     }
1028   }
1029
1030   void render(Renderer& renderer, const VolumeTest& volume, const Matrix4& pivot2world)
1031   {
1032     m_pivot.update(pivot2world, volume.GetModelview(), volume.GetProjection(), volume.GetViewport());
1033     updateCircleTransforms();
1034
1035     // temp hack
1036     UpdateColours();
1037
1038     renderer.SetState(m_state_outer, Renderer::eWireframeOnly);
1039     renderer.SetState(m_state_outer, Renderer::eFullMaterials);
1040
1041     renderer.addRenderable(m_circle_screen, m_pivot.m_viewpointSpace);
1042     renderer.addRenderable(m_circle_sphere, m_pivot.m_viewpointSpace);
1043
1044     if(m_circle_x_visible)
1045     {
1046       renderer.addRenderable(m_circle_x, m_local2world_x);
1047     }
1048     if(m_circle_y_visible)
1049     {
1050       renderer.addRenderable(m_circle_y, m_local2world_y);
1051     }
1052     if(m_circle_z_visible)
1053     {
1054       renderer.addRenderable(m_circle_z, m_local2world_z);
1055     }
1056   }
1057   void testSelect(const View& view, const Matrix4& pivot2world)
1058   {
1059     m_pivot.update(pivot2world, view.GetModelview(), view.GetProjection(), view.GetViewport());
1060     updateCircleTransforms();
1061
1062     SelectionPool selector;
1063
1064     {
1065       {
1066         Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_local2world_x));
1067
1068 #if defined(DEBUG_SELECTION)
1069         g_render_clipped.construct(view.GetViewMatrix());
1070 #endif
1071
1072         SelectionIntersection best;
1073         LineStrip_BestPoint(local2view, m_circle_x.m_vertices.data(), m_circle_x.m_vertices.size(), best);
1074         selector.addSelectable(best, &m_selectable_x);
1075       }
1076
1077       {
1078         Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_local2world_y));
1079
1080 #if defined(DEBUG_SELECTION)
1081         g_render_clipped.construct(view.GetViewMatrix());
1082 #endif
1083
1084         SelectionIntersection best;
1085         LineStrip_BestPoint(local2view, m_circle_y.m_vertices.data(), m_circle_y.m_vertices.size(), best);
1086         selector.addSelectable(best, &m_selectable_y);
1087       }
1088
1089       {
1090         Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_local2world_z));
1091
1092 #if defined(DEBUG_SELECTION)
1093         g_render_clipped.construct(view.GetViewMatrix());
1094 #endif
1095
1096         SelectionIntersection best;
1097         LineStrip_BestPoint(local2view, m_circle_z.m_vertices.data(), m_circle_z.m_vertices.size(), best);
1098         selector.addSelectable(best, &m_selectable_z);
1099       }
1100     }
1101
1102     {
1103       Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_pivot.m_viewpointSpace));
1104
1105       {
1106         SelectionIntersection best;
1107         LineLoop_BestPoint(local2view, m_circle_screen.m_vertices.data(), m_circle_screen.m_vertices.size(), best);
1108         selector.addSelectable(best, &m_selectable_screen); 
1109       }
1110
1111       {
1112         SelectionIntersection best;
1113         Circle_BestPoint(local2view, eClipCullCW, m_circle_sphere.m_vertices.data(), m_circle_sphere.m_vertices.size(), best);
1114         selector.addSelectable(best, &m_selectable_sphere); 
1115       }
1116     }
1117
1118     m_axis_screen = m_pivot.m_axis_screen;
1119
1120     if(!selector.failed())
1121     {
1122       (*selector.begin()).second->setSelected(true);
1123     }
1124   }
1125
1126   Manipulatable* GetManipulatable()
1127   {
1128     if(m_selectable_x.isSelected())
1129     {
1130       m_axis.SetAxis(g_vector3_axis_x);
1131       return &m_axis;
1132     }
1133     else if(m_selectable_y.isSelected())
1134     {
1135       m_axis.SetAxis(g_vector3_axis_y);
1136       return &m_axis;
1137     }
1138     else if(m_selectable_z.isSelected())
1139     {
1140       m_axis.SetAxis(g_vector3_axis_z);
1141       return &m_axis;
1142     }
1143     else if(m_selectable_screen.isSelected())
1144     {
1145       m_axis.SetAxis(m_axis_screen);
1146       return &m_axis;
1147     }
1148     else
1149       return &m_free;
1150   }
1151
1152   void setSelected(bool select)
1153   {
1154     m_selectable_x.setSelected(select);
1155     m_selectable_y.setSelected(select);
1156     m_selectable_z.setSelected(select);
1157     m_selectable_screen.setSelected(select);
1158   }
1159   bool isSelected() const
1160   {
1161     return m_selectable_x.isSelected()
1162       | m_selectable_y.isSelected()
1163       | m_selectable_z.isSelected()
1164       | m_selectable_screen.isSelected()
1165       | m_selectable_sphere.isSelected();
1166   }
1167 };
1168
1169 Shader* RotateManipulator::m_state_outer;
1170
1171
1172 const float arrowhead_length = 16;
1173 const float arrowhead_radius = 4;
1174
1175 inline void draw_arrowline(const float length, PointVertex* line, const std::size_t axis)
1176 {
1177   (*line++).vertex = vertex3f_identity;
1178   (*line).vertex = vertex3f_identity;
1179   vertex3f_to_array((*line).vertex)[axis] = length - arrowhead_length;
1180 }
1181
1182 template<typename VertexRemap, typename NormalRemap>
1183 inline void draw_arrowhead(const std::size_t segments, const float length, FlatShadedVertex* vertices, VertexRemap, NormalRemap)
1184 {
1185   std::size_t head_tris = (segments << 3);
1186   const double head_segment = c_2pi / head_tris;
1187   for(std::size_t i = 0; i < head_tris; ++i)
1188   {
1189     {
1190       FlatShadedVertex& point = vertices[i*6+0];
1191       VertexRemap::x(point.vertex) = length - arrowhead_length;
1192       VertexRemap::y(point.vertex) = arrowhead_radius * static_cast<float>(cos(i * head_segment));
1193       VertexRemap::z(point.vertex) = arrowhead_radius * static_cast<float>(sin(i * head_segment));
1194       NormalRemap::x(point.normal) = arrowhead_radius / arrowhead_length;
1195       NormalRemap::y(point.normal) = static_cast<float>(cos(i * head_segment));
1196       NormalRemap::z(point.normal) = static_cast<float>(sin(i * head_segment));
1197     }
1198     {
1199       FlatShadedVertex& point = vertices[i*6+1];
1200       VertexRemap::x(point.vertex) = length;
1201       VertexRemap::y(point.vertex) = 0;
1202       VertexRemap::z(point.vertex) = 0;
1203       NormalRemap::x(point.normal) = arrowhead_radius / arrowhead_length;
1204       NormalRemap::y(point.normal) = static_cast<float>(cos((i + 0.5) * head_segment));
1205       NormalRemap::z(point.normal) = static_cast<float>(sin((i + 0.5) * head_segment));
1206     }
1207     {
1208       FlatShadedVertex& point = vertices[i*6+2];
1209       VertexRemap::x(point.vertex) = length - arrowhead_length;
1210       VertexRemap::y(point.vertex) = arrowhead_radius * static_cast<float>(cos((i+1) * head_segment));
1211       VertexRemap::z(point.vertex) = arrowhead_radius * static_cast<float>(sin((i+1) * head_segment));
1212       NormalRemap::x(point.normal) = arrowhead_radius / arrowhead_length;
1213       NormalRemap::y(point.normal) = static_cast<float>(cos((i+1) * head_segment));
1214       NormalRemap::z(point.normal) = static_cast<float>(sin((i+1) * head_segment));
1215     }
1216
1217     {
1218       FlatShadedVertex& point = vertices[i*6+3];
1219       VertexRemap::x(point.vertex) = length - arrowhead_length;
1220       VertexRemap::y(point.vertex) = 0;
1221       VertexRemap::z(point.vertex) = 0;
1222       NormalRemap::x(point.normal) = -1;
1223       NormalRemap::y(point.normal) = 0;
1224       NormalRemap::z(point.normal) = 0;
1225     }
1226     {
1227       FlatShadedVertex& point = vertices[i*6+4];
1228       VertexRemap::x(point.vertex) = length - arrowhead_length;
1229       VertexRemap::y(point.vertex) = arrowhead_radius * static_cast<float>(cos(i * head_segment));
1230       VertexRemap::z(point.vertex) = arrowhead_radius * static_cast<float>(sin(i * head_segment));
1231       NormalRemap::x(point.normal) = -1;
1232       NormalRemap::y(point.normal) = 0;
1233       NormalRemap::z(point.normal) = 0;
1234     }
1235     {
1236       FlatShadedVertex& point = vertices[i*6+5];
1237       VertexRemap::x(point.vertex) = length - arrowhead_length;
1238       VertexRemap::y(point.vertex) = arrowhead_radius * static_cast<float>(cos((i+1) * head_segment));
1239       VertexRemap::z(point.vertex) = arrowhead_radius * static_cast<float>(sin((i+1) * head_segment));
1240       NormalRemap::x(point.normal) = -1;
1241       NormalRemap::y(point.normal) = 0;
1242       NormalRemap::z(point.normal) = 0;
1243     }
1244   }
1245 }
1246
1247 template<typename Triple>
1248 class TripleRemapXYZ
1249 {
1250 public:
1251   static float& x(Triple& triple)
1252   {
1253     return triple.x();
1254   }
1255   static float& y(Triple& triple)
1256   {
1257     return triple.y();
1258   }
1259   static float& z(Triple& triple)
1260   {
1261     return triple.z();
1262   }
1263 };
1264
1265 template<typename Triple>
1266 class TripleRemapYZX
1267 {
1268 public:
1269   static float& x(Triple& triple)
1270   {
1271     return triple.y();
1272   }
1273   static float& y(Triple& triple)
1274   {
1275     return triple.z();
1276   }
1277   static float& z(Triple& triple)
1278   {
1279     return triple.x();
1280   }
1281 };
1282
1283 template<typename Triple>
1284 class TripleRemapZXY
1285 {
1286 public:
1287   static float& x(Triple& triple)
1288   {
1289     return triple.z();
1290   }
1291   static float& y(Triple& triple)
1292   {
1293     return triple.x();
1294   }
1295   static float& z(Triple& triple)
1296   {
1297     return triple.y();
1298   }
1299 };
1300
1301 void vector3_print(const Vector3& v)
1302 {
1303   globalOutputStream() << "( " << v.x() << " " << v.y() << " " << v.z() << " )";
1304 }
1305
1306 class TranslateManipulator : public Manipulator
1307 {
1308   struct RenderableArrowLine : public OpenGLRenderable
1309   {
1310     PointVertex m_line[2];
1311
1312     RenderableArrowLine()
1313     {
1314     }
1315     void render(RenderStateFlags state) const
1316     {
1317       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_line[0].colour);
1318       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_line[0].vertex);
1319       glDrawArrays(GL_LINES, 0, 2);
1320     }
1321     void setColour(const Colour4b& colour)
1322     {
1323       m_line[0].colour = colour;
1324       m_line[1].colour = colour;
1325     }
1326   };
1327   struct RenderableArrowHead : public OpenGLRenderable
1328   {
1329     Array<FlatShadedVertex> m_vertices;
1330
1331     RenderableArrowHead(std::size_t size)
1332       : m_vertices(size)
1333     {
1334     }
1335     void render(RenderStateFlags state) const
1336     {
1337       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(FlatShadedVertex), &m_vertices.data()->colour);
1338       glVertexPointer(3, GL_FLOAT, sizeof(FlatShadedVertex), &m_vertices.data()->vertex);
1339       glNormalPointer(GL_FLOAT, sizeof(FlatShadedVertex), &m_vertices.data()->normal);
1340       glDrawArrays(GL_TRIANGLES, 0, GLsizei(m_vertices.size()));
1341     }
1342     void setColour(const Colour4b& colour)
1343     {
1344       for(Array<FlatShadedVertex>::iterator i = m_vertices.begin(); i != m_vertices.end(); ++i)
1345       {
1346         (*i).colour = colour;
1347       }
1348     }
1349   };
1350   struct RenderableQuad : public OpenGLRenderable
1351   {
1352     PointVertex m_quad[4];
1353     void render(RenderStateFlags state) const
1354     {
1355       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_quad[0].colour);
1356       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_quad[0].vertex);
1357       glDrawArrays(GL_LINE_LOOP, 0, 4);
1358     }
1359     void setColour(const Colour4b& colour)
1360     {
1361       m_quad[0].colour = colour;
1362       m_quad[1].colour = colour;
1363       m_quad[2].colour = colour;
1364       m_quad[3].colour = colour;
1365     }
1366   };
1367
1368   TranslateFree m_free;
1369   TranslateAxis m_axis;
1370   RenderableArrowLine m_arrow_x;
1371   RenderableArrowLine m_arrow_y;
1372   RenderableArrowLine m_arrow_z;
1373   RenderableArrowHead m_arrow_head_x;
1374   RenderableArrowHead m_arrow_head_y;
1375   RenderableArrowHead m_arrow_head_z;
1376   RenderableQuad m_quad_screen;
1377   SelectableBool m_selectable_x;
1378   SelectableBool m_selectable_y;
1379   SelectableBool m_selectable_z;
1380   SelectableBool m_selectable_screen;
1381   Pivot2World m_pivot;
1382 public:
1383   static Shader* m_state_wire;
1384   static Shader* m_state_fill;
1385
1386   TranslateManipulator(Translatable& translatable, std::size_t segments, float length) :
1387     m_free(translatable),
1388     m_axis(translatable),
1389     m_arrow_head_x(3 * 2 * (segments << 3)),
1390     m_arrow_head_y(3 * 2 * (segments << 3)),
1391     m_arrow_head_z(3 * 2 * (segments << 3))
1392   {
1393     draw_arrowline(length, m_arrow_x.m_line, 0);
1394     draw_arrowhead(segments, length, m_arrow_head_x.m_vertices.data(), TripleRemapXYZ<Vertex3f>(), TripleRemapXYZ<Normal3f>());
1395     draw_arrowline(length, m_arrow_y.m_line, 1);
1396     draw_arrowhead(segments, length, m_arrow_head_y.m_vertices.data(), TripleRemapYZX<Vertex3f>(), TripleRemapYZX<Normal3f>());
1397     draw_arrowline(length, m_arrow_z.m_line, 2);
1398     draw_arrowhead(segments, length, m_arrow_head_z.m_vertices.data(), TripleRemapZXY<Vertex3f>(), TripleRemapZXY<Normal3f>());
1399
1400     draw_quad(16, m_quad_screen.m_quad);
1401   }
1402
1403   void UpdateColours()
1404   {
1405     m_arrow_x.setColour(colourSelected(g_colour_x, m_selectable_x.isSelected()));
1406     m_arrow_head_x.setColour(colourSelected(g_colour_x, m_selectable_x.isSelected()));
1407     m_arrow_y.setColour(colourSelected(g_colour_y, m_selectable_y.isSelected()));
1408     m_arrow_head_y.setColour(colourSelected(g_colour_y, m_selectable_y.isSelected()));
1409     m_arrow_z.setColour(colourSelected(g_colour_z, m_selectable_z.isSelected()));
1410     m_arrow_head_z.setColour(colourSelected(g_colour_z, m_selectable_z.isSelected()));
1411     m_quad_screen.setColour(colourSelected(g_colour_screen, m_selectable_screen.isSelected()));
1412   }
1413
1414   bool manipulator_show_axis(const Pivot2World& pivot, const Vector3& axis)
1415   {
1416     return fabs(vector3_dot(pivot.m_axis_screen, axis)) < 0.95;
1417   }
1418
1419   void render(Renderer& renderer, const VolumeTest& volume, const Matrix4& pivot2world)
1420   {
1421     m_pivot.update(pivot2world, volume.GetModelview(), volume.GetProjection(), volume.GetViewport());
1422
1423     // temp hack
1424     UpdateColours();
1425
1426     Vector3 x = vector3_normalised(vector4_to_vector3(m_pivot.m_worldSpace.x()));
1427     bool show_x = manipulator_show_axis(m_pivot, x);
1428
1429     Vector3 y = vector3_normalised(vector4_to_vector3(m_pivot.m_worldSpace.y()));
1430     bool show_y = manipulator_show_axis(m_pivot, y);
1431
1432     Vector3 z = vector3_normalised(vector4_to_vector3(m_pivot.m_worldSpace.z()));
1433     bool show_z = manipulator_show_axis(m_pivot, z);
1434
1435     renderer.SetState(m_state_wire, Renderer::eWireframeOnly);
1436     renderer.SetState(m_state_wire, Renderer::eFullMaterials);
1437
1438     if(show_x)
1439     {
1440       renderer.addRenderable(m_arrow_x, m_pivot.m_worldSpace);
1441     }
1442     if(show_y)
1443     {
1444       renderer.addRenderable(m_arrow_y, m_pivot.m_worldSpace);
1445     }
1446     if(show_z)
1447     {
1448       renderer.addRenderable(m_arrow_z, m_pivot.m_worldSpace);
1449     }
1450
1451     renderer.addRenderable(m_quad_screen, m_pivot.m_viewplaneSpace);
1452
1453     renderer.SetState(m_state_fill, Renderer::eWireframeOnly);
1454     renderer.SetState(m_state_fill, Renderer::eFullMaterials);
1455
1456     if(show_x)
1457     {
1458       renderer.addRenderable(m_arrow_head_x, m_pivot.m_worldSpace);
1459     }
1460     if(show_y)
1461     {
1462       renderer.addRenderable(m_arrow_head_y, m_pivot.m_worldSpace);
1463     }
1464     if(show_z)
1465     {
1466       renderer.addRenderable(m_arrow_head_z, m_pivot.m_worldSpace);
1467     }
1468   }
1469   void testSelect(const View& view, const Matrix4& pivot2world)
1470   {
1471     m_pivot.update(pivot2world, view.GetModelview(), view.GetProjection(), view.GetViewport());
1472
1473     SelectionPool selector;
1474
1475     Vector3 x = vector3_normalised(vector4_to_vector3(m_pivot.m_worldSpace.x()));
1476     bool show_x = manipulator_show_axis(m_pivot, x);
1477
1478     Vector3 y = vector3_normalised(vector4_to_vector3(m_pivot.m_worldSpace.y()));
1479     bool show_y = manipulator_show_axis(m_pivot, y);
1480
1481     Vector3 z = vector3_normalised(vector4_to_vector3(m_pivot.m_worldSpace.z()));
1482     bool show_z = manipulator_show_axis(m_pivot, z);
1483
1484     {
1485       Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_pivot.m_viewpointSpace));
1486
1487       {
1488         SelectionIntersection best;
1489         Quad_BestPoint(local2view, eClipCullCW, m_quad_screen.m_quad, best);
1490         if(best.valid())
1491         {
1492           best = SelectionIntersection(0, 0);
1493           selector.addSelectable(best, &m_selectable_screen);
1494         }
1495       }
1496     }
1497
1498     {
1499       Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_pivot.m_worldSpace));
1500
1501 #if defined(DEBUG_SELECTION)
1502       g_render_clipped.construct(view.GetViewMatrix());
1503 #endif
1504
1505       if(show_x)
1506       {
1507         SelectionIntersection best;
1508         Line_BestPoint(local2view, m_arrow_x.m_line, best);
1509         Triangles_BestPoint(local2view, eClipCullCW, m_arrow_head_x.m_vertices.begin(), m_arrow_head_x.m_vertices.end(), best);
1510         selector.addSelectable(best, &m_selectable_x);
1511       }
1512
1513       if(show_y)
1514       {
1515         SelectionIntersection best;
1516         Line_BestPoint(local2view, m_arrow_y.m_line, best);
1517         Triangles_BestPoint(local2view, eClipCullCW, m_arrow_head_y.m_vertices.begin(), m_arrow_head_y.m_vertices.end(), best);
1518         selector.addSelectable(best, &m_selectable_y);
1519       }
1520
1521       if(show_z)
1522       {
1523         SelectionIntersection best;
1524         Line_BestPoint(local2view, m_arrow_z.m_line, best);
1525         Triangles_BestPoint(local2view, eClipCullCW, m_arrow_head_z.m_vertices.begin(), m_arrow_head_z.m_vertices.end(), best);
1526         selector.addSelectable(best, &m_selectable_z);
1527       }
1528     }
1529
1530     if(!selector.failed())
1531     {
1532       (*selector.begin()).second->setSelected(true);
1533     }
1534   }
1535
1536   Manipulatable* GetManipulatable()
1537   {
1538     if(m_selectable_x.isSelected())
1539     {
1540       m_axis.SetAxis(g_vector3_axis_x);
1541       return &m_axis;
1542     }
1543     else if(m_selectable_y.isSelected())
1544     {
1545       m_axis.SetAxis(g_vector3_axis_y);
1546       return &m_axis;
1547     }
1548     else if(m_selectable_z.isSelected())
1549     {
1550       m_axis.SetAxis(g_vector3_axis_z);
1551       return &m_axis;
1552     }
1553     else
1554     {
1555       return &m_free;
1556     }
1557   }
1558
1559   void setSelected(bool select)
1560   {
1561     m_selectable_x.setSelected(select);
1562     m_selectable_y.setSelected(select);
1563     m_selectable_z.setSelected(select);
1564     m_selectable_screen.setSelected(select);
1565   }
1566   bool isSelected() const
1567   {
1568     return m_selectable_x.isSelected()
1569       | m_selectable_y.isSelected()
1570       | m_selectable_z.isSelected()
1571       | m_selectable_screen.isSelected();
1572   }
1573 };
1574
1575 Shader* TranslateManipulator::m_state_wire;
1576 Shader* TranslateManipulator::m_state_fill;
1577
1578 class ScaleManipulator : public Manipulator
1579 {
1580   struct RenderableArrow : public OpenGLRenderable
1581   {
1582     PointVertex m_line[2];
1583
1584     void render(RenderStateFlags state) const
1585     {
1586       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_line[0].colour);
1587       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_line[0].vertex);
1588       glDrawArrays(GL_LINES, 0, 2);
1589     }
1590     void setColour(const Colour4b& colour)
1591     {
1592       m_line[0].colour = colour;
1593       m_line[1].colour = colour;
1594     }
1595   };
1596   struct RenderableQuad : public OpenGLRenderable
1597   {
1598     PointVertex m_quad[4];
1599     void render(RenderStateFlags state) const
1600     {
1601       glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &m_quad[0].colour);
1602       glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &m_quad[0].vertex);
1603       glDrawArrays(GL_QUADS, 0, 4);
1604     }
1605     void setColour(const Colour4b& colour)
1606     {
1607       m_quad[0].colour = colour;
1608       m_quad[1].colour = colour;
1609       m_quad[2].colour = colour;
1610       m_quad[3].colour = colour;
1611     }
1612   };
1613
1614   ScaleFree m_free;
1615   ScaleAxis m_axis;
1616   RenderableArrow m_arrow_x;
1617   RenderableArrow m_arrow_y;
1618   RenderableArrow m_arrow_z;
1619   RenderableQuad m_quad_screen;
1620   SelectableBool m_selectable_x;
1621   SelectableBool m_selectable_y;
1622   SelectableBool m_selectable_z;
1623   SelectableBool m_selectable_screen;
1624   Pivot2World m_pivot;
1625 public:
1626   ScaleManipulator(Scalable& scalable, std::size_t segments, float length) :
1627     m_free(scalable),
1628     m_axis(scalable)
1629   {
1630     draw_arrowline(length, m_arrow_x.m_line, 0);
1631     draw_arrowline(length, m_arrow_y.m_line, 1);
1632     draw_arrowline(length, m_arrow_z.m_line, 2);
1633
1634     draw_quad(16, m_quad_screen.m_quad);
1635   }
1636
1637   Pivot2World& getPivot()
1638   {
1639     return m_pivot;
1640   }
1641
1642   void UpdateColours()
1643   {
1644     m_arrow_x.setColour(colourSelected(g_colour_x, m_selectable_x.isSelected()));
1645     m_arrow_y.setColour(colourSelected(g_colour_y, m_selectable_y.isSelected()));
1646     m_arrow_z.setColour(colourSelected(g_colour_z, m_selectable_z.isSelected()));
1647     m_quad_screen.setColour(colourSelected(g_colour_screen, m_selectable_screen.isSelected()));
1648   }
1649
1650   void render(Renderer& renderer, const VolumeTest& volume, const Matrix4& pivot2world)
1651   {
1652     m_pivot.update(pivot2world, volume.GetModelview(), volume.GetProjection(), volume.GetViewport());
1653
1654     // temp hack
1655     UpdateColours();
1656
1657     renderer.addRenderable(m_arrow_x, m_pivot.m_worldSpace);
1658     renderer.addRenderable(m_arrow_y, m_pivot.m_worldSpace);
1659     renderer.addRenderable(m_arrow_z, m_pivot.m_worldSpace);
1660
1661     renderer.addRenderable(m_quad_screen, m_pivot.m_viewpointSpace);
1662   }
1663   void testSelect(const View& view, const Matrix4& pivot2world)
1664   {
1665     m_pivot.update(pivot2world, view.GetModelview(), view.GetProjection(), view.GetViewport());
1666
1667     SelectionPool selector;
1668
1669     {
1670       Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_pivot.m_worldSpace));
1671
1672 #if defined(DEBUG_SELECTION)
1673       g_render_clipped.construct(view.GetViewMatrix());
1674 #endif
1675
1676     {
1677         SelectionIntersection best;
1678         Line_BestPoint(local2view, m_arrow_x.m_line, best);
1679         selector.addSelectable(best, &m_selectable_x);
1680       }
1681
1682       {
1683         SelectionIntersection best;
1684         Line_BestPoint(local2view, m_arrow_y.m_line, best);
1685         selector.addSelectable(best, &m_selectable_y);
1686       }
1687
1688       {
1689         SelectionIntersection best;
1690         Line_BestPoint(local2view, m_arrow_z.m_line, best);
1691         selector.addSelectable(best, &m_selectable_z);
1692       }
1693     }
1694
1695     {
1696       Matrix4 local2view(matrix4_multiplied_by_matrix4(view.GetViewMatrix(), m_pivot.m_viewpointSpace));
1697
1698       {
1699         SelectionIntersection best;
1700         Quad_BestPoint(local2view, eClipCullCW, m_quad_screen.m_quad, best);
1701         selector.addSelectable(best, &m_selectable_screen);
1702       }
1703     }
1704
1705     if(!selector.failed())
1706     {
1707       (*selector.begin()).second->setSelected(true);
1708     }
1709   }
1710
1711   Manipulatable* GetManipulatable()
1712   {
1713     if(m_selectable_x.isSelected())
1714     {
1715       m_axis.SetAxis(g_vector3_axis_x);
1716       return &m_axis;
1717     }
1718     else if(m_selectable_y.isSelected())
1719     {
1720       m_axis.SetAxis(g_vector3_axis_y);
1721       return &m_axis;
1722     }
1723     else if(m_selectable_z.isSelected())
1724     {
1725       m_axis.SetAxis(g_vector3_axis_z);
1726       return &m_axis;
1727     }
1728     else
1729       return &m_free;
1730   }
1731
1732   void setSelected(bool select)
1733   {
1734     m_selectable_x.setSelected(select);
1735     m_selectable_y.setSelected(select);
1736     m_selectable_z.setSelected(select);
1737     m_selectable_screen.setSelected(select);
1738   }
1739   bool isSelected() const
1740   {
1741     return m_selectable_x.isSelected()
1742       | m_selectable_y.isSelected()
1743       | m_selectable_z.isSelected()
1744       | m_selectable_screen.isSelected();
1745   }
1746 };
1747
1748
1749 inline PlaneSelectable* Instance_getPlaneSelectable(scene::Instance& instance)
1750 {
1751   return InstanceTypeCast<PlaneSelectable>::cast(instance);
1752 }
1753
1754 class PlaneSelectableSelectPlanes : public scene::Graph::Walker
1755 {
1756   Selector& m_selector;
1757   SelectionTest& m_test;
1758   PlaneCallback m_selectedPlaneCallback;
1759 public:
1760   PlaneSelectableSelectPlanes(Selector& selector, SelectionTest& test, const PlaneCallback& selectedPlaneCallback)
1761     : m_selector(selector), m_test(test), m_selectedPlaneCallback(selectedPlaneCallback)
1762   {
1763   }
1764   bool pre(const scene::Path& path, scene::Instance& instance) const
1765   {
1766     if(path.top().get().visible())
1767     {
1768       Selectable* selectable = Instance_getSelectable(instance);
1769       if(selectable != 0 && selectable->isSelected())
1770       {
1771         PlaneSelectable* planeSelectable = Instance_getPlaneSelectable(instance);
1772         if(planeSelectable != 0)
1773         {
1774           planeSelectable->selectPlanes(m_selector, m_test, m_selectedPlaneCallback);
1775         }
1776       }
1777     }
1778     return true; 
1779   }
1780 };
1781
1782 class PlaneSelectableSelectReversedPlanes : public scene::Graph::Walker
1783 {
1784   Selector& m_selector;
1785   const SelectedPlanes& m_selectedPlanes;
1786 public:
1787   PlaneSelectableSelectReversedPlanes(Selector& selector, const SelectedPlanes& selectedPlanes)
1788     : m_selector(selector), m_selectedPlanes(selectedPlanes)
1789   {
1790   }
1791   bool pre(const scene::Path& path, scene::Instance& instance) const
1792   {
1793     if(path.top().get().visible())
1794     {
1795       Selectable* selectable = Instance_getSelectable(instance);
1796       if(selectable != 0 && selectable->isSelected())
1797       {
1798         PlaneSelectable* planeSelectable = Instance_getPlaneSelectable(instance);
1799         if(planeSelectable != 0)
1800         {
1801           planeSelectable->selectReversedPlanes(m_selector, m_selectedPlanes);
1802         }
1803       }
1804     }
1805     return true; 
1806   }
1807 };
1808
1809 void Scene_forEachPlaneSelectable_selectPlanes(scene::Graph& graph, Selector& selector, SelectionTest& test, const PlaneCallback& selectedPlaneCallback)
1810 {
1811   graph.traverse(PlaneSelectableSelectPlanes(selector, test, selectedPlaneCallback));
1812 }
1813
1814 void Scene_forEachPlaneSelectable_selectReversedPlanes(scene::Graph& graph, Selector& selector, const SelectedPlanes& selectedPlanes)
1815 {
1816   graph.traverse(PlaneSelectableSelectReversedPlanes(selector, selectedPlanes));
1817 }
1818
1819
1820 class PlaneLess
1821 {
1822 public:
1823   bool operator()(const Plane3& plane, const Plane3& other) const
1824   {
1825     if(plane.a < other.a)
1826     {
1827       return true;
1828     }
1829     if(other.a < plane.a)
1830     {
1831       return false;
1832     }
1833
1834     if(plane.b < other.b)
1835     {
1836       return true;
1837     }
1838     if(other.b < plane.b)
1839     {
1840       return false;
1841     }
1842
1843     if(plane.c < other.c)
1844     {
1845       return true;
1846     }
1847     if(other.c < plane.c)
1848     {
1849       return false;
1850     }
1851
1852     if(plane.d < other.d)
1853     {
1854       return true;
1855     }
1856     if(other.d < plane.d)
1857     {
1858       return false;
1859     }
1860
1861     return false;
1862   }
1863 };
1864
1865 typedef std::set<Plane3, PlaneLess> PlaneSet;
1866
1867 inline void PlaneSet_insert(PlaneSet& self, const Plane3& plane)
1868 {
1869   self.insert(plane);
1870 }
1871
1872 inline bool PlaneSet_contains(const PlaneSet& self, const Plane3& plane)
1873 {
1874   return self.find(plane) != self.end();
1875 }
1876
1877
1878 class SelectedPlaneSet : public SelectedPlanes
1879 {
1880   PlaneSet m_selectedPlanes;
1881 public:
1882   bool empty() const
1883   {
1884     return m_selectedPlanes.empty();
1885   }
1886
1887   void insert(const Plane3& plane)
1888   {
1889     PlaneSet_insert(m_selectedPlanes, plane);
1890   }
1891   bool contains(const Plane3& plane) const
1892   {
1893     return PlaneSet_contains(m_selectedPlanes, plane);
1894   }
1895   typedef MemberCaller1<SelectedPlaneSet, const Plane3&, &SelectedPlaneSet::insert> InsertCaller;
1896 };
1897
1898
1899 bool Scene_forEachPlaneSelectable_selectPlanes(scene::Graph& graph, Selector& selector, SelectionTest& test)
1900 {
1901   SelectedPlaneSet selectedPlanes;
1902
1903   Scene_forEachPlaneSelectable_selectPlanes(graph, selector, test, SelectedPlaneSet::InsertCaller(selectedPlanes));
1904   Scene_forEachPlaneSelectable_selectReversedPlanes(graph, selector, selectedPlanes);
1905
1906   return !selectedPlanes.empty();
1907 }
1908
1909 void Scene_Translate_Component_Selected(scene::Graph& graph, const Vector3& translation);
1910 void Scene_Translate_Selected(scene::Graph& graph, const Vector3& translation);
1911 void Scene_TestSelect_Primitive(Selector& selector, SelectionTest& test, const VolumeTest& volume);
1912 void Scene_TestSelect_Component(Selector& selector, SelectionTest& test, const VolumeTest& volume, SelectionSystem::EComponentMode componentMode);
1913 void Scene_TestSelect_Component_Selected(Selector& selector, SelectionTest& test, const VolumeTest& volume, SelectionSystem::EComponentMode componentMode);
1914 void Scene_SelectAll_Component(bool select, SelectionSystem::EComponentMode componentMode);
1915
1916 class ResizeTranslatable : public Translatable
1917 {
1918   void translate(const Vector3& translation)
1919   {
1920     Scene_Translate_Component_Selected(GlobalSceneGraph(), translation);
1921   }
1922 };
1923
1924 class DragTranslatable : public Translatable
1925 {
1926   void translate(const Vector3& translation)
1927   {
1928     if(GlobalSelectionSystem().Mode() == SelectionSystem::eComponent)
1929     {
1930       Scene_Translate_Component_Selected(GlobalSceneGraph(), translation);
1931     }
1932     else
1933     {
1934       Scene_Translate_Selected(GlobalSceneGraph(), translation);
1935     }
1936   }
1937 };
1938
1939 class SelectionVolume : public SelectionTest
1940 {
1941   Matrix4 m_local2view;
1942   const View& m_view;
1943   clipcull_t m_cull;
1944   Vector3 m_near;
1945   Vector3 m_far;
1946 public:
1947   SelectionVolume(const View& view)
1948     : m_view(view)
1949   {
1950   }
1951
1952   const VolumeTest& getVolume() const
1953   {
1954     return m_view;
1955   }
1956
1957   const Vector3& getNear() const
1958   {
1959     return m_near;
1960   }
1961   const Vector3& getFar() const
1962   {
1963     return m_far;
1964   }
1965
1966   void BeginMesh(const Matrix4& localToWorld, bool twoSided)
1967   {
1968     m_local2view = matrix4_multiplied_by_matrix4(m_view.GetViewMatrix(), localToWorld);
1969
1970     // Cull back-facing polygons based on winding being clockwise or counter-clockwise.
1971     // Don't cull if the view is wireframe and the polygons are two-sided.
1972     m_cull = twoSided && !m_view.fill() ? eClipCullNone : (matrix4_handedness(localToWorld) == MATRIX4_RIGHTHANDED) ? eClipCullCW : eClipCullCCW;
1973
1974     {
1975       Matrix4 screen2world(matrix4_full_inverse(m_local2view));
1976
1977       m_near = vector4_projected(
1978         matrix4_transformed_vector4(
1979           screen2world,
1980           Vector4(0, 0, -1, 1)
1981         )
1982       );
1983
1984       m_far = vector4_projected(
1985         matrix4_transformed_vector4(
1986           screen2world,
1987           Vector4(0, 0, 1, 1)
1988         )
1989       );
1990     }
1991
1992 #if defined(DEBUG_SELECTION)
1993     g_render_clipped.construct(m_view.GetViewMatrix());
1994 #endif
1995   }
1996   void TestPoint(const Vector3& point, SelectionIntersection& best)
1997   {
1998     Vector4 clipped;
1999     if(matrix4_clip_point(m_local2view, point, clipped) == c_CLIP_PASS)
2000     {
2001       best = select_point_from_clipped(clipped);
2002     }
2003   }
2004   void TestPolygon(const VertexPointer& vertices, std::size_t count, SelectionIntersection& best)
2005   {
2006     Vector4 clipped[9];
2007     for(std::size_t i=0; i+2<count; ++i)
2008     {
2009       BestPoint(
2010         matrix4_clip_triangle(
2011           m_local2view,
2012           reinterpret_cast<const Vector3&>(vertices[0]),
2013           reinterpret_cast<const Vector3&>(vertices[i+1]),
2014           reinterpret_cast<const Vector3&>(vertices[i+2]),
2015           clipped
2016         ),
2017         clipped,
2018         best,
2019         m_cull
2020       );
2021     }
2022   }
2023   void TestLineLoop(const VertexPointer& vertices, std::size_t count, SelectionIntersection& best)
2024   {
2025     if(count == 0)
2026       return;
2027     Vector4 clipped[9];
2028     for(VertexPointer::iterator i = vertices.begin(), end = i + count, prev = i + (count-1); i != end; prev = i, ++i)
2029     {
2030       BestPoint(
2031         matrix4_clip_line(
2032           m_local2view,
2033           reinterpret_cast<const Vector3&>((*prev)),
2034           reinterpret_cast<const Vector3&>((*i)),
2035           clipped
2036         ),
2037         clipped,
2038         best,
2039         m_cull
2040       );
2041     }
2042   }
2043   void TestLineStrip(const VertexPointer& vertices, std::size_t count, SelectionIntersection& best)
2044   {
2045     if(count == 0)
2046       return;
2047     Vector4 clipped[9];
2048     for(VertexPointer::iterator i = vertices.begin(), end = i + count, next = i + 1; next != end; i = next, ++next)
2049     {
2050       BestPoint(
2051         matrix4_clip_line(
2052           m_local2view,
2053           reinterpret_cast<const Vector3&>((*i)),
2054           reinterpret_cast<const Vector3&>((*next)),
2055           clipped
2056         ),
2057         clipped,
2058         best,
2059         m_cull
2060       );
2061     }
2062   }
2063   void TestLines(const VertexPointer& vertices, std::size_t count, SelectionIntersection& best)
2064   {
2065     if(count == 0)
2066       return;
2067     Vector4 clipped[9];
2068     for(VertexPointer::iterator i = vertices.begin(), end = i + count; i != end; i += 2)
2069     {
2070       BestPoint(
2071         matrix4_clip_line(
2072           m_local2view,
2073           reinterpret_cast<const Vector3&>((*i)),
2074           reinterpret_cast<const Vector3&>((*(i+1))),
2075           clipped
2076         ),
2077         clipped,
2078         best,
2079         m_cull
2080       );
2081     }
2082   }
2083   void TestTriangles(const VertexPointer& vertices, const IndexPointer& indices, SelectionIntersection& best)
2084   {
2085     Vector4 clipped[9];
2086     for(IndexPointer::iterator i(indices.begin()); i != indices.end(); i += 3)
2087     {
2088       BestPoint(
2089         matrix4_clip_triangle(
2090           m_local2view,
2091           reinterpret_cast<const Vector3&>(vertices[*i]),
2092           reinterpret_cast<const Vector3&>(vertices[*(i+1)]),
2093           reinterpret_cast<const Vector3&>(vertices[*(i+2)]),
2094           clipped
2095         ),
2096         clipped,
2097         best,
2098         m_cull
2099       );
2100     }
2101   }
2102   void TestQuads(const VertexPointer& vertices, const IndexPointer& indices, SelectionIntersection& best)
2103   {
2104     Vector4 clipped[9];
2105     for(IndexPointer::iterator i(indices.begin()); i != indices.end(); i += 4)
2106     {
2107       BestPoint(
2108         matrix4_clip_triangle(
2109           m_local2view,
2110           reinterpret_cast<const Vector3&>(vertices[*i]),
2111           reinterpret_cast<const Vector3&>(vertices[*(i+1)]),
2112           reinterpret_cast<const Vector3&>(vertices[*(i+3)]),
2113           clipped
2114         ),
2115         clipped,
2116         best,
2117         m_cull
2118       );
2119             BestPoint(
2120         matrix4_clip_triangle(
2121           m_local2view,
2122           reinterpret_cast<const Vector3&>(vertices[*(i+1)]),
2123           reinterpret_cast<const Vector3&>(vertices[*(i+2)]),
2124           reinterpret_cast<const Vector3&>(vertices[*(i+3)]),
2125           clipped
2126         ),
2127         clipped,
2128         best,
2129         m_cull
2130       );
2131     }
2132   }
2133   void TestQuadStrip(const VertexPointer& vertices, const IndexPointer& indices, SelectionIntersection& best)
2134   {
2135     Vector4 clipped[9];
2136     for(IndexPointer::iterator i(indices.begin()); i+2 != indices.end(); i += 2)
2137     {
2138       BestPoint(
2139         matrix4_clip_triangle(
2140           m_local2view,
2141           reinterpret_cast<const Vector3&>(vertices[*i]),
2142           reinterpret_cast<const Vector3&>(vertices[*(i+1)]),
2143           reinterpret_cast<const Vector3&>(vertices[*(i+2)]),
2144           clipped
2145         ),
2146         clipped,
2147         best,
2148         m_cull
2149       );
2150       BestPoint(
2151         matrix4_clip_triangle(
2152           m_local2view,
2153           reinterpret_cast<const Vector3&>(vertices[*(i+2)]),
2154           reinterpret_cast<const Vector3&>(vertices[*(i+1)]),
2155           reinterpret_cast<const Vector3&>(vertices[*(i+3)]),
2156           clipped
2157         ),
2158         clipped,
2159         best,
2160         m_cull
2161       );
2162     }
2163   }
2164 };
2165
2166 class SelectionCounter
2167 {
2168 public:
2169   typedef const Selectable& first_argument_type;
2170
2171   SelectionCounter(const SelectionChangeCallback& onchanged)
2172     : m_count(0), m_onchanged(onchanged)
2173   {
2174   }
2175   void operator()(const Selectable& selectable)
2176   {
2177     if(selectable.isSelected())
2178     {
2179       ++m_count;
2180     }
2181     else
2182     {
2183       ASSERT_MESSAGE(m_count != 0, "selection counter underflow");
2184       --m_count;
2185     }
2186
2187     m_onchanged(selectable);
2188   }
2189   bool empty() const
2190   {
2191     return m_count == 0;
2192   }
2193   std::size_t size() const
2194   {
2195     return m_count;
2196   }
2197 private:
2198   std::size_t m_count;
2199   SelectionChangeCallback m_onchanged;
2200 };
2201
2202 inline void ConstructSelectionTest(View& view, const rect_t selection_box)
2203 {
2204   view.EnableScissor(selection_box.min[0], selection_box.max[0], selection_box.min[1], selection_box.max[1]);
2205 }
2206
2207 inline const rect_t SelectionBoxForPoint(const float device_point[2], const float device_epsilon[2])
2208 {
2209   rect_t selection_box;
2210   selection_box.min[0] = device_point[0] - device_epsilon[0];
2211   selection_box.min[1] = device_point[1] - device_epsilon[1];
2212   selection_box.max[0] = device_point[0] + device_epsilon[0];
2213   selection_box.max[1] = device_point[1] + device_epsilon[1];
2214   return selection_box;
2215 }
2216
2217 inline const rect_t SelectionBoxForArea(const float device_point[2], const float device_delta[2])
2218 {
2219   rect_t selection_box;
2220   selection_box.min[0] = (device_delta[0] < 0) ? (device_point[0] + device_delta[0]) : (device_point[0]);
2221   selection_box.min[1] = (device_delta[1] < 0) ? (device_point[1] + device_delta[1]) : (device_point[1]);
2222   selection_box.max[0] = (device_delta[0] > 0) ? (device_point[0] + device_delta[0]) : (device_point[0]);
2223   selection_box.max[1] = (device_delta[1] > 0) ? (device_point[1] + device_delta[1]) : (device_point[1]);
2224   return selection_box;
2225 }
2226
2227 Quaternion construct_local_rotation(const Quaternion& world, const Quaternion& localToWorld)
2228 {
2229   return quaternion_normalised(quaternion_multiplied_by_quaternion(
2230     quaternion_normalised(quaternion_multiplied_by_quaternion(
2231       quaternion_inverse(localToWorld),
2232       world
2233     )),
2234     localToWorld
2235   ));
2236 }
2237
2238 inline void matrix4_assign_rotation(Matrix4& matrix, const Matrix4& other)
2239 {
2240   matrix[0] = other[0];
2241   matrix[1] = other[1];
2242   matrix[2] = other[2];
2243   matrix[4] = other[4];
2244   matrix[5] = other[5];
2245   matrix[6] = other[6];
2246   matrix[8] = other[8];
2247   matrix[9] = other[9];
2248   matrix[10] = other[10];
2249 }
2250
2251 void matrix4_assign_rotation_for_pivot(Matrix4& matrix, scene::Instance& instance)
2252 {
2253   Editable* editable = Node_getEditable(instance.path().top());
2254   if(editable != 0)
2255   {
2256     matrix4_assign_rotation(matrix, matrix4_multiplied_by_matrix4(instance.localToWorld(), editable->getLocalPivot()));
2257   }
2258   else
2259   {
2260     matrix4_assign_rotation(matrix, instance.localToWorld());
2261   }
2262 }
2263
2264 inline bool Instance_isSelectedComponents(scene::Instance& instance)
2265 {
2266   ComponentSelectionTestable* componentSelectionTestable = Instance_getComponentSelectionTestable(instance);
2267   return componentSelectionTestable != 0
2268     && componentSelectionTestable->isSelectedComponents();
2269 }
2270
2271 class TranslateSelected : public SelectionSystem::Visitor
2272 {
2273   const Vector3& m_translate;
2274 public:
2275   TranslateSelected(const Vector3& translate)
2276     : m_translate(translate)
2277   {
2278   }
2279   void visit(scene::Instance& instance) const
2280   {
2281     Transformable* transform = Instance_getTransformable(instance);
2282     if(transform != 0)
2283     {
2284       transform->setType(TRANSFORM_PRIMITIVE);
2285       transform->setTranslation(m_translate);
2286     }
2287   }
2288 };
2289
2290 void Scene_Translate_Selected(scene::Graph& graph, const Vector3& translation)
2291 {
2292   if(GlobalSelectionSystem().countSelected() != 0)
2293   {
2294     GlobalSelectionSystem().foreachSelected(TranslateSelected(translation));
2295   }
2296 }
2297
2298 Vector3 get_local_pivot(const Vector3& world_pivot, const Matrix4& localToWorld)
2299 {
2300   return Vector3(
2301     matrix4_transformed_point(
2302       matrix4_full_inverse(localToWorld),
2303       world_pivot
2304     )
2305   );
2306 }
2307
2308 void translation_for_pivoted_rotation(Vector3& parent_translation, const Quaternion& local_rotation, const Vector3& world_pivot, const Matrix4& localToWorld, const Matrix4& localToParent)
2309 {
2310   Vector3 local_pivot(get_local_pivot(world_pivot, localToWorld));
2311
2312   Vector3 translation(
2313     vector3_added(
2314       local_pivot,
2315       matrix4_transformed_point(
2316         matrix4_rotation_for_quaternion_quantised(local_rotation),
2317         vector3_negated(local_pivot)
2318       )
2319     )
2320   );
2321
2322   //globalOutputStream() << "translation: " << translation << "\n";
2323
2324   translation_local2object(parent_translation, translation, localToParent);
2325
2326   //globalOutputStream() << "parent_translation: " << parent_translation << "\n";
2327 }
2328
2329 void translation_for_pivoted_scale(Vector3& parent_translation, const Vector3& local_scale, const Vector3& world_pivot, const Matrix4& localToWorld, const Matrix4& localToParent)
2330 {
2331   Vector3 local_pivot(get_local_pivot(world_pivot, localToWorld));
2332
2333   Vector3 translation(
2334     vector3_added(
2335       local_pivot,
2336       vector3_scaled(
2337         vector3_negated(local_pivot),
2338         local_scale
2339       )
2340     )
2341   );
2342
2343   translation_local2object(parent_translation, translation, localToParent);
2344 }
2345
2346 class rotate_selected : public SelectionSystem::Visitor
2347 {
2348   const Quaternion& m_rotate;
2349   const Vector3& m_world_pivot;
2350 public:
2351   rotate_selected(const Quaternion& rotation, const Vector3& world_pivot)
2352     : m_rotate(rotation), m_world_pivot(world_pivot)
2353   {
2354   }
2355   void visit(scene::Instance& instance) const
2356   {
2357     TransformNode* transformNode = Node_getTransformNode(instance.path().top());
2358     if(transformNode != 0)
2359     {
2360       Transformable* transform = Instance_getTransformable(instance);
2361       if(transform != 0)
2362       {
2363         transform->setType(TRANSFORM_PRIMITIVE);
2364         transform->setScale(c_scale_identity);
2365         transform->setTranslation(c_translation_identity);
2366
2367         transform->setType(TRANSFORM_PRIMITIVE);
2368         transform->setRotation(m_rotate);
2369
2370         {
2371           Editable* editable = Node_getEditable(instance.path().top());
2372           const Matrix4& localPivot = editable != 0 ? editable->getLocalPivot() : g_matrix4_identity;
2373
2374           Vector3 parent_translation;
2375           translation_for_pivoted_rotation(
2376             parent_translation,
2377             m_rotate,
2378             m_world_pivot,
2379             matrix4_multiplied_by_matrix4(instance.localToWorld(), localPivot),
2380             matrix4_multiplied_by_matrix4(transformNode->localToParent(), localPivot)
2381           );
2382
2383           transform->setTranslation(parent_translation);
2384         }
2385       } 
2386     }
2387   }
2388 };
2389
2390 void Scene_Rotate_Selected(scene::Graph& graph, const Quaternion& rotation, const Vector3& world_pivot)
2391 {
2392   if(GlobalSelectionSystem().countSelected() != 0)
2393   {
2394     GlobalSelectionSystem().foreachSelected(rotate_selected(rotation, world_pivot));
2395   }
2396 }
2397
2398 class scale_selected : public SelectionSystem::Visitor
2399 {
2400   const Vector3& m_scale;
2401   const Vector3& m_world_pivot;
2402 public:
2403   scale_selected(const Vector3& scaling, const Vector3& world_pivot)
2404     : m_scale(scaling), m_world_pivot(world_pivot)
2405   {
2406   }
2407   void visit(scene::Instance& instance) const
2408   {
2409     TransformNode* transformNode = Node_getTransformNode(instance.path().top());
2410     if(transformNode != 0)
2411     {
2412       Transformable* transform = Instance_getTransformable(instance);
2413       if(transform != 0)
2414       {
2415         transform->setType(TRANSFORM_PRIMITIVE);
2416         transform->setScale(c_scale_identity);
2417         transform->setTranslation(c_translation_identity);
2418
2419         transform->setType(TRANSFORM_PRIMITIVE);
2420         transform->setScale(m_scale);
2421         {
2422           Editable* editable = Node_getEditable(instance.path().top());
2423           const Matrix4& localPivot = editable != 0 ? editable->getLocalPivot() : g_matrix4_identity;
2424     
2425           Vector3 parent_translation;
2426           translation_for_pivoted_scale(
2427             parent_translation,
2428             m_scale,
2429             m_world_pivot,
2430             matrix4_multiplied_by_matrix4(instance.localToWorld(), localPivot),
2431             matrix4_multiplied_by_matrix4(transformNode->localToParent(), localPivot)
2432           );
2433
2434           transform->setTranslation(parent_translation);
2435         }
2436       }
2437     }
2438   }
2439 };
2440
2441 void Scene_Scale_Selected(scene::Graph& graph, const Vector3& scaling, const Vector3& world_pivot)
2442 {
2443   if(GlobalSelectionSystem().countSelected() != 0)
2444   {
2445     GlobalSelectionSystem().foreachSelected(scale_selected(scaling, world_pivot));
2446   }
2447 }
2448
2449
2450 class translate_component_selected : public SelectionSystem::Visitor
2451 {
2452   const Vector3& m_translate;
2453 public:
2454   translate_component_selected(const Vector3& translate)
2455     : m_translate(translate)
2456   {
2457   }
2458   void visit(scene::Instance& instance) const
2459   {
2460     Transformable* transform = Instance_getTransformable(instance);
2461     if(transform != 0)
2462     {
2463       transform->setType(TRANSFORM_COMPONENT);
2464       transform->setTranslation(m_translate);
2465     }
2466   }
2467 };
2468
2469 void Scene_Translate_Component_Selected(scene::Graph& graph, const Vector3& translation)
2470 {
2471   if(GlobalSelectionSystem().countSelected() != 0)
2472   {
2473     GlobalSelectionSystem().foreachSelectedComponent(translate_component_selected(translation));
2474   }
2475 }
2476
2477 class rotate_component_selected : public SelectionSystem::Visitor
2478 {
2479   const Quaternion& m_rotate;
2480   const Vector3& m_world_pivot;
2481 public:
2482   rotate_component_selected(const Quaternion& rotation, const Vector3& world_pivot)
2483     : m_rotate(rotation), m_world_pivot(world_pivot)
2484   {
2485   }
2486   void visit(scene::Instance& instance) const
2487   {
2488     Transformable* transform = Instance_getTransformable(instance);
2489     if(transform != 0)
2490     {
2491       Vector3 parent_translation;
2492       translation_for_pivoted_rotation(parent_translation, m_rotate, m_world_pivot, instance.localToWorld(), Node_getTransformNode(instance.path().top())->localToParent());
2493
2494       transform->setType(TRANSFORM_COMPONENT);
2495       transform->setRotation(m_rotate);
2496       transform->setTranslation(parent_translation);
2497     }
2498   }
2499 };
2500
2501 void Scene_Rotate_Component_Selected(scene::Graph& graph, const Quaternion& rotation, const Vector3& world_pivot)
2502 {
2503   if(GlobalSelectionSystem().countSelectedComponents() != 0)
2504   {
2505     GlobalSelectionSystem().foreachSelectedComponent(rotate_component_selected(rotation, world_pivot));
2506   }
2507 }
2508
2509 class scale_component_selected : public SelectionSystem::Visitor
2510 {
2511   const Vector3& m_scale;
2512   const Vector3& m_world_pivot;
2513 public:
2514   scale_component_selected(const Vector3& scaling, const Vector3& world_pivot)
2515     : m_scale(scaling), m_world_pivot(world_pivot)
2516   {
2517   }
2518   void visit(scene::Instance& instance) const
2519   {
2520     Transformable* transform = Instance_getTransformable(instance);
2521     if(transform != 0)
2522     {
2523       Vector3 parent_translation;
2524       translation_for_pivoted_scale(parent_translation, m_scale, m_world_pivot, instance.localToWorld(), Node_getTransformNode(instance.path().top())->localToParent());
2525
2526       transform->setType(TRANSFORM_COMPONENT);
2527       transform->setScale(m_scale);
2528       transform->setTranslation(parent_translation);
2529     }
2530   }
2531 };
2532
2533 void Scene_Scale_Component_Selected(scene::Graph& graph, const Vector3& scaling, const Vector3& world_pivot)
2534 {
2535   if(GlobalSelectionSystem().countSelectedComponents() != 0)
2536   {
2537     GlobalSelectionSystem().foreachSelectedComponent(scale_component_selected(scaling, world_pivot));
2538   }
2539 }
2540
2541
2542 class BooleanSelector : public Selector
2543 {
2544   bool m_selected;
2545   SelectionIntersection m_intersection;
2546   Selectable* m_selectable;
2547 public:
2548   BooleanSelector() : m_selected(false)
2549   {
2550   }
2551
2552   void pushSelectable(Selectable& selectable)
2553   {
2554     m_intersection = SelectionIntersection();
2555     m_selectable = &selectable;
2556   }
2557   void popSelectable()
2558   {
2559     if(m_intersection.valid())
2560     {
2561       m_selected = true;
2562     }
2563     m_intersection = SelectionIntersection();
2564   }
2565   void addIntersection(const SelectionIntersection& intersection)
2566   {
2567     if(m_selectable->isSelected())
2568     {
2569       assign_if_closer(m_intersection, intersection);
2570     }
2571   }
2572
2573   bool isSelected()
2574   {
2575     return m_selected;
2576   }
2577 };
2578
2579 class BestSelector : public Selector
2580 {
2581   SelectionIntersection m_intersection;
2582   Selectable* m_selectable;
2583   SelectionIntersection m_bestIntersection;
2584   std::list<Selectable*> m_bestSelectable;
2585 public:
2586   BestSelector() : m_bestIntersection(SelectionIntersection()), m_bestSelectable(0)
2587   {
2588   }
2589
2590   void pushSelectable(Selectable& selectable)
2591   {
2592     m_intersection = SelectionIntersection();
2593     m_selectable = &selectable;
2594   }
2595   void popSelectable()
2596   {
2597     if(m_intersection.equalEpsilon(m_bestIntersection, 0.25f, 0.001f))
2598     {
2599       m_bestSelectable.push_back(m_selectable);
2600       m_bestIntersection = m_intersection;
2601     }
2602     else if(m_intersection < m_bestIntersection)
2603     {
2604       m_bestSelectable.clear();
2605       m_bestSelectable.push_back(m_selectable);
2606       m_bestIntersection = m_intersection;
2607     }
2608     m_intersection = SelectionIntersection();
2609   }
2610   void addIntersection(const SelectionIntersection& intersection)
2611   {
2612     assign_if_closer(m_intersection, intersection);
2613   }
2614
2615   std::list<Selectable*>& best()
2616   {
2617     return m_bestSelectable;
2618   }
2619 };
2620
2621 class DragManipulator : public Manipulator
2622 {
2623   TranslateFree m_freeResize;
2624   TranslateFree m_freeDrag;
2625   ResizeTranslatable m_resize;
2626   DragTranslatable m_drag;
2627   SelectableBool m_dragSelectable;
2628 public:
2629
2630   bool m_selected;
2631
2632   DragManipulator() : m_freeResize(m_resize), m_freeDrag(m_drag), m_selected(false)
2633   {
2634   }
2635
2636   Manipulatable* GetManipulatable()
2637   {
2638     return m_dragSelectable.isSelected() ? &m_freeDrag : &m_freeResize;
2639   }
2640
2641   void testSelect(const View& view, const Matrix4& pivot2world)
2642   {
2643     SelectionPool selector;
2644
2645     SelectionVolume test(view);
2646
2647     if(GlobalSelectionSystem().Mode() == SelectionSystem::ePrimitive)
2648     {
2649       BooleanSelector booleanSelector;
2650
2651       Scene_TestSelect_Primitive(booleanSelector, test, view);
2652
2653       if(booleanSelector.isSelected())
2654       {
2655         selector.addSelectable(SelectionIntersection(0, 0), &m_dragSelectable);
2656         m_selected = false;
2657       }
2658       else
2659       {
2660         m_selected = Scene_forEachPlaneSelectable_selectPlanes(GlobalSceneGraph(), selector, test);
2661       }
2662     }
2663     else
2664     {
2665       BestSelector bestSelector;
2666       Scene_TestSelect_Component_Selected(bestSelector, test, view, GlobalSelectionSystem().ComponentMode());
2667       for(std::list<Selectable*>::iterator i = bestSelector.best().begin(); i != bestSelector.best().end(); ++i)
2668       {
2669         if(!(*i)->isSelected())
2670         {
2671           GlobalSelectionSystem().setSelectedAllComponents(false);
2672         }
2673         m_selected = false;
2674         selector.addSelectable(SelectionIntersection(0, 0), (*i));
2675         m_dragSelectable.setSelected(true);
2676       }
2677     }
2678
2679     for(SelectionPool::iterator i = selector.begin(); i != selector.end(); ++i)
2680     {
2681       (*i).second->setSelected(true);
2682     }
2683   }
2684   
2685   void setSelected(bool select)
2686   {
2687     m_selected = select;
2688     m_dragSelectable.setSelected(select);
2689   }
2690   bool isSelected() const
2691   {
2692     return m_selected || m_dragSelectable.isSelected();
2693   }
2694 };
2695
2696 class ClipManipulator : public Manipulator
2697 {
2698 public:
2699
2700   Manipulatable* GetManipulatable()
2701   {
2702     ERROR_MESSAGE("clipper is not manipulatable");
2703     return 0;
2704   }
2705
2706   void setSelected(bool select)
2707   {
2708   }
2709   bool isSelected() const
2710   {
2711     return false;
2712   }
2713 };
2714
2715 class select_all : public scene::Graph::Walker
2716 {
2717   bool m_select;
2718 public:
2719   select_all(bool select)
2720     : m_select(select)
2721   {
2722   }
2723   bool pre(const scene::Path& path, scene::Instance& instance) const
2724   {
2725     Selectable* selectable = Instance_getSelectable(instance);
2726     if(selectable != 0)
2727     {
2728       selectable->setSelected(m_select);
2729     }
2730     return true;
2731   }
2732 };
2733
2734 class select_all_component : public scene::Graph::Walker
2735 {
2736   bool m_select;
2737   SelectionSystem::EComponentMode m_mode;
2738 public:
2739   select_all_component(bool select, SelectionSystem::EComponentMode mode)
2740     : m_select(select), m_mode(mode)
2741   {
2742   }
2743   bool pre(const scene::Path& path, scene::Instance& instance) const
2744   {
2745     ComponentSelectionTestable* componentSelectionTestable = Instance_getComponentSelectionTestable(instance);
2746     if(componentSelectionTestable)
2747     {
2748       componentSelectionTestable->setSelectedComponents(m_select, m_mode);
2749     }
2750     return true;
2751   }
2752 };
2753
2754 void Scene_SelectAll_Component(bool select, SelectionSystem::EComponentMode componentMode)
2755 {
2756   GlobalSceneGraph().traverse(select_all_component(select, componentMode));
2757 }
2758
2759
2760 // RadiantSelectionSystem
2761 class RadiantSelectionSystem :
2762   public SelectionSystem,
2763   public Translatable,
2764   public Rotatable,
2765   public Scalable,
2766   public Renderable
2767 {
2768   mutable Matrix4 m_pivot2world;
2769   Matrix4 m_pivot2world_start;
2770   Matrix4 m_manip2pivot_start;
2771   Translation m_translation;
2772   Rotation m_rotation;
2773   Scale m_scale;
2774 public:
2775   static Shader* m_state;
2776 private:
2777   EManipulatorMode m_manipulator_mode;
2778   Manipulator* m_manipulator;
2779
2780   // state
2781   bool m_undo_begun;
2782   EMode m_mode;
2783   EComponentMode m_componentmode;
2784
2785   SelectionCounter m_count_primitive;
2786   SelectionCounter m_count_component;
2787
2788   TranslateManipulator m_translate_manipulator;
2789   RotateManipulator m_rotate_manipulator;
2790   ScaleManipulator m_scale_manipulator;
2791   DragManipulator m_drag_manipulator;
2792   ClipManipulator m_clip_manipulator;
2793
2794   typedef SelectionList<scene::Instance> selection_t;
2795   selection_t m_selection;
2796   selection_t m_component_selection;
2797
2798   Signal1<const Selectable&> m_selectionChanged_callbacks;
2799
2800   void ConstructPivot() const;
2801   mutable bool m_pivotChanged;
2802   bool m_pivot_moving;
2803
2804   void Scene_TestSelect(Selector& selector, SelectionTest& test, const View& view, SelectionSystem::EMode mode, SelectionSystem::EComponentMode componentMode);
2805
2806   bool nothingSelected() const
2807   {
2808     return (Mode() == eComponent && m_count_component.empty())
2809       || (Mode() == ePrimitive && m_count_primitive.empty());
2810   }
2811
2812
2813 public:
2814   enum EModifier
2815   {
2816     eManipulator,
2817     eToggle,
2818     eReplace,
2819     eCycle,
2820   };
2821
2822   RadiantSelectionSystem() :
2823     m_undo_begun(false),
2824     m_mode(ePrimitive),
2825     m_componentmode(eDefault),
2826     m_count_primitive(SelectionChangedCaller(*this)),
2827     m_count_component(SelectionChangedCaller(*this)),
2828     m_translate_manipulator(*this, 2, 64),
2829     m_rotate_manipulator(*this, 8, 64),
2830     m_scale_manipulator(*this, 0, 64),
2831     m_pivotChanged(false),
2832     m_pivot_moving(false)
2833   {
2834     SetManipulatorMode(eTranslate);
2835     pivotChanged();
2836     addSelectionChangeCallback(PivotChangedSelectionCaller(*this));
2837     AddGridChangeCallback(PivotChangedCaller(*this));
2838   }
2839   void pivotChanged() const
2840   {
2841     m_pivotChanged = true;
2842     SceneChangeNotify();
2843   }
2844   typedef ConstMemberCaller<RadiantSelectionSystem, &RadiantSelectionSystem::pivotChanged> PivotChangedCaller;
2845   void pivotChangedSelection(const Selectable& selectable)
2846   {
2847     pivotChanged();
2848   }
2849   typedef MemberCaller1<RadiantSelectionSystem, const Selectable&, &RadiantSelectionSystem::pivotChangedSelection> PivotChangedSelectionCaller;
2850
2851   void SetMode(EMode mode)
2852   {
2853     if(m_mode != mode)
2854     {
2855       m_mode = mode;
2856       pivotChanged();
2857     }
2858   }
2859   EMode Mode() const
2860   {
2861     return m_mode;
2862   }
2863   void SetComponentMode(EComponentMode mode)
2864   {
2865     m_componentmode = mode;
2866   }
2867   EComponentMode ComponentMode() const
2868   {
2869     return m_componentmode;
2870   }
2871   void SetManipulatorMode(EManipulatorMode mode)
2872   {
2873     m_manipulator_mode = mode;
2874     switch(m_manipulator_mode)
2875     {
2876     case eTranslate: m_manipulator = &m_translate_manipulator; break;
2877     case eRotate: m_manipulator = &m_rotate_manipulator; break;
2878     case eScale: m_manipulator = &m_scale_manipulator; break;
2879     case eDrag: m_manipulator = &m_drag_manipulator; break;
2880     case eClip: m_manipulator = &m_clip_manipulator; break;
2881     }
2882     pivotChanged();
2883   }
2884   EManipulatorMode ManipulatorMode() const
2885   {
2886     return m_manipulator_mode;
2887   }
2888
2889   SelectionChangeCallback getObserver(EMode mode)
2890   {
2891     if(mode == ePrimitive)
2892     {
2893       return makeCallback1(m_count_primitive);
2894     }
2895     else
2896     {
2897       return makeCallback1(m_count_component);
2898     }
2899   }
2900   std::size_t countSelected() const
2901   {
2902     return m_count_primitive.size();
2903   }
2904   std::size_t countSelectedComponents() const
2905   {
2906     return m_count_component.size();
2907   }
2908   void onSelectedChanged(scene::Instance& instance, const Selectable& selectable)
2909   {
2910     if(selectable.isSelected())
2911     {
2912       m_selection.append(instance);
2913     }
2914     else
2915     {
2916       m_selection.erase(instance);
2917     }
2918
2919     ASSERT_MESSAGE(m_selection.size() == m_count_primitive.size(), "selection-tracking error");
2920   }
2921   void onComponentSelection(scene::Instance& instance, const Selectable& selectable)
2922   {
2923     if(selectable.isSelected())
2924     {
2925       m_component_selection.append(instance);
2926     }
2927     else
2928     {
2929       m_component_selection.erase(instance);
2930     }
2931
2932     ASSERT_MESSAGE(m_component_selection.size() == m_count_component.size(), "selection-tracking error");
2933   }
2934   scene::Instance& ultimateSelected() const
2935   {
2936     ASSERT_MESSAGE(m_selection.size() > 0, "no instance selected");
2937     return m_selection.back();
2938   }
2939   scene::Instance& penultimateSelected() const
2940   {
2941     ASSERT_MESSAGE(m_selection.size() > 1, "only one instance selected");
2942     return *(*(--(--m_selection.end())));
2943   }
2944   void setSelectedAll(bool selected)
2945   {
2946     GlobalSceneGraph().traverse(select_all(selected));
2947
2948     m_manipulator->setSelected(selected);
2949   }
2950   void setSelectedAllComponents(bool selected)
2951   {
2952     Scene_SelectAll_Component(selected, SelectionSystem::eVertex);
2953     Scene_SelectAll_Component(selected, SelectionSystem::eEdge);
2954     Scene_SelectAll_Component(selected, SelectionSystem::eFace);
2955
2956     m_manipulator->setSelected(selected);
2957   }
2958
2959   void foreachSelected(const Visitor& visitor) const
2960   {
2961     selection_t::const_iterator i = m_selection.begin();
2962     while(i != m_selection.end())
2963     {
2964       visitor.visit(*(*(i++)));
2965     }
2966   }
2967   void foreachSelectedComponent(const Visitor& visitor) const
2968   {
2969     selection_t::const_iterator i = m_component_selection.begin();
2970     while(i != m_component_selection.end())
2971     {
2972       visitor.visit(*(*(i++)));
2973     }
2974   }
2975
2976   void addSelectionChangeCallback(const SelectionChangeHandler& handler)
2977   {
2978     m_selectionChanged_callbacks.connectLast(handler);
2979   }
2980   void selectionChanged(const Selectable& selectable)
2981   {
2982     m_selectionChanged_callbacks(selectable);
2983   }
2984   typedef MemberCaller1<RadiantSelectionSystem, const Selectable&, &RadiantSelectionSystem::selectionChanged> SelectionChangedCaller;
2985
2986
2987   void startMove()
2988   {
2989     m_pivot2world_start = GetPivot2World();
2990   }
2991
2992   bool SelectManipulator(const View& view, const float device_point[2], const float device_epsilon[2])
2993   {
2994     if(!nothingSelected() || (ManipulatorMode() == eDrag && Mode() == eComponent))
2995     {
2996 #if defined (DEBUG_SELECTION)
2997       g_render_clipped.destroy();
2998 #endif
2999
3000       m_manipulator->setSelected(false);
3001
3002       if(!nothingSelected() || (ManipulatorMode() == eDrag && Mode() == eComponent))
3003       {
3004         View scissored(view);
3005         ConstructSelectionTest(scissored, SelectionBoxForPoint(device_point, device_epsilon));
3006         m_manipulator->testSelect(scissored, GetPivot2World());
3007       }
3008
3009       startMove();
3010
3011       m_pivot_moving = m_manipulator->isSelected();
3012
3013       if(m_pivot_moving)
3014       {
3015         Pivot2World pivot;
3016         pivot.update(GetPivot2World(), view.GetModelview(), view.GetProjection(), view.GetViewport());
3017
3018         m_manip2pivot_start = matrix4_multiplied_by_matrix4(matrix4_full_inverse(m_pivot2world_start), pivot.m_worldSpace);
3019
3020         Matrix4 device2manip;
3021         ConstructDevice2Manip(device2manip, m_pivot2world_start, view.GetModelview(), view.GetProjection(), view.GetViewport());
3022         m_manipulator->GetManipulatable()->Construct(device2manip, device_point[0], device_point[1]);
3023
3024         m_undo_begun = false;
3025       }
3026
3027       SceneChangeNotify();
3028     }
3029
3030     return m_pivot_moving;
3031   }
3032
3033   void deselectAll()
3034   {
3035     if(Mode() == eComponent)
3036     {
3037       setSelectedAllComponents(false);
3038     }
3039     else
3040     {
3041       setSelectedAll(false);
3042     }
3043   }
3044
3045   void SelectPoint(const View& view, const float device_point[2], const float device_epsilon[2], RadiantSelectionSystem::EModifier modifier, bool face)
3046   {
3047     ASSERT_MESSAGE(fabs(device_point[0]) <= 1.0f && fabs(device_point[1]) <= 1.0f, "point-selection error");
3048     if(modifier == eReplace)
3049     {
3050       if(face)
3051       {
3052         setSelectedAllComponents(false);
3053       }
3054       else
3055       {
3056         deselectAll();
3057       }
3058     }
3059
3060   #if defined (DEBUG_SELECTION)
3061     g_render_clipped.destroy();
3062   #endif
3063
3064     {
3065       View scissored(view);
3066       ConstructSelectionTest(scissored, SelectionBoxForPoint(device_point, device_epsilon));
3067
3068       SelectionVolume volume(scissored);
3069       SelectionPool selector;
3070       if(face)
3071       {
3072         Scene_TestSelect_Component(selector, volume, scissored, eFace);
3073       }
3074       else
3075       {
3076         Scene_TestSelect(selector, volume, scissored, Mode(), ComponentMode());
3077       }
3078
3079       if(!selector.failed())
3080       {
3081         switch(modifier)
3082         {
3083         case RadiantSelectionSystem::eToggle:
3084           {
3085             SelectableSortedSet::iterator best = selector.begin();
3086             // toggle selection of the object with least depth
3087             if((*best).second->isSelected())
3088               (*best).second->setSelected(false);
3089             else
3090               (*best).second->setSelected(true);
3091           }
3092           break;
3093           // if cycle mode not enabled, enable it
3094         case RadiantSelectionSystem::eReplace:
3095           {
3096             // select closest
3097             (*selector.begin()).second->setSelected(true);
3098           }
3099           break;
3100           // select the next object in the list from the one already selected
3101         case RadiantSelectionSystem::eCycle:
3102           {
3103             SelectionPool::iterator i = selector.begin();
3104             while(i != selector.end())
3105             {
3106               if((*i).second->isSelected())
3107               {
3108                 (*i).second->setSelected(false);
3109                 ++i;
3110                 if(i != selector.end())
3111                 {
3112                   i->second->setSelected(true);
3113                 }
3114                 else
3115                 {
3116                   selector.begin()->second->setSelected(true);
3117                 }
3118                 break;
3119               }
3120               ++i;
3121             }
3122           }
3123           break;
3124         default:
3125           break;
3126         }
3127       }
3128     }
3129   } 
3130
3131   void SelectArea(const View& view, const float device_point[2], const float device_delta[2], RadiantSelectionSystem::EModifier modifier, bool face)
3132   {
3133     if(modifier == eReplace)
3134     {
3135       if(face)
3136       {
3137         setSelectedAllComponents(false);
3138       }
3139       else
3140       {
3141         deselectAll();
3142       }
3143     }
3144
3145   #if defined (DEBUG_SELECTION)
3146       g_render_clipped.destroy();
3147   #endif
3148
3149     {
3150       View scissored(view);
3151       ConstructSelectionTest(scissored, SelectionBoxForArea(device_point, device_delta));
3152
3153       SelectionVolume volume(scissored);
3154       SelectionPool pool;
3155       if(face)
3156       {
3157         Scene_TestSelect_Component(pool, volume, scissored, eFace);
3158       }
3159       else
3160       {
3161         Scene_TestSelect(pool, volume, scissored, Mode(), ComponentMode());
3162       }
3163
3164       for(SelectionPool::iterator i = pool.begin(); i != pool.end(); ++i)
3165       {
3166         (*i).second->setSelected(!(modifier == RadiantSelectionSystem::eToggle && (*i).second->isSelected()));
3167       }
3168     }
3169   }
3170
3171
3172   void translate(const Vector3& translation)
3173   {
3174     if(!nothingSelected())
3175     {
3176       //ASSERT_MESSAGE(!m_pivotChanged, "pivot is invalid");
3177
3178       m_translation = translation;
3179
3180       m_pivot2world = m_pivot2world_start;
3181       matrix4_translate_by_vec3(m_pivot2world, translation);
3182
3183       if(Mode() == eComponent)
3184       {
3185         Scene_Translate_Component_Selected(GlobalSceneGraph(), m_translation);
3186       }
3187       else
3188       {
3189         Scene_Translate_Selected(GlobalSceneGraph(), m_translation);
3190       }
3191
3192       SceneChangeNotify();
3193     }
3194   }
3195   void outputTranslation(TextOutputStream& ostream)
3196   {
3197     ostream << " -xyz " << m_translation.x() << " " << m_translation.y() << " " << m_translation.z();
3198   }
3199   void rotate(const Quaternion& rotation)
3200   {
3201     if(!nothingSelected())
3202     {
3203       //ASSERT_MESSAGE(!m_pivotChanged, "pivot is invalid");
3204       
3205       m_rotation = rotation;
3206
3207       if(Mode() == eComponent)
3208       {
3209         Scene_Rotate_Component_Selected(GlobalSceneGraph(), m_rotation, vector4_to_vector3(m_pivot2world.t()));
3210
3211         matrix4_assign_rotation_for_pivot(m_pivot2world, m_component_selection.back());
3212       }
3213       else
3214       {
3215         Scene_Rotate_Selected(GlobalSceneGraph(), m_rotation, vector4_to_vector3(m_pivot2world.t()));
3216
3217         matrix4_assign_rotation_for_pivot(m_pivot2world, m_selection.back());
3218       }
3219
3220       SceneChangeNotify();
3221     }
3222   }
3223   void outputRotation(TextOutputStream& ostream)
3224   {
3225     ostream << " -eulerXYZ " << m_rotation.x() << " " << m_rotation.y() << " " << m_rotation.z();
3226   }
3227   void scale(const Vector3& scaling)
3228   {
3229     if(!nothingSelected())
3230     {
3231       m_scale = scaling;
3232
3233       if(Mode() == eComponent)
3234       {
3235         Scene_Scale_Component_Selected(GlobalSceneGraph(), m_scale, vector4_to_vector3(m_pivot2world.t()));
3236       }
3237       else
3238       {
3239         Scene_Scale_Selected(GlobalSceneGraph(), m_scale, vector4_to_vector3(m_pivot2world.t()));
3240       }
3241
3242       SceneChangeNotify();
3243     }
3244   }
3245   void outputScale(TextOutputStream& ostream)
3246   {
3247     ostream << " -scale " << m_scale.x() << " " << m_scale.y() << " " << m_scale.z();
3248   }
3249
3250   void rotateSelected(const Quaternion& rotation)
3251   {
3252     startMove();
3253     rotate(rotation);
3254     freezeTransforms();
3255   }
3256   void translateSelected(const Vector3& translation)
3257   {
3258     startMove();
3259     translate(translation);
3260     freezeTransforms();
3261   }
3262   void scaleSelected(const Vector3& scaling)
3263   {
3264     startMove();
3265     scale(scaling);
3266     freezeTransforms();
3267   }
3268
3269   void MoveSelected(const View& view, const float device_point[2])
3270   {
3271     if(m_manipulator->isSelected())
3272     {
3273       if(!m_undo_begun)
3274       {
3275         m_undo_begun = true;
3276         GlobalUndoSystem().start();
3277       }
3278
3279       Matrix4 device2manip;
3280       ConstructDevice2Manip(device2manip, m_pivot2world_start, view.GetModelview(), view.GetProjection(), view.GetViewport());
3281       m_manipulator->GetManipulatable()->Transform(m_manip2pivot_start, device2manip, device_point[0], device_point[1]);
3282     }
3283   }
3284
3285   /// \todo Support view-dependent nudge.
3286   void NudgeManipulator(const Vector3& nudge, const Vector3& view)
3287   {
3288     if(ManipulatorMode() == eTranslate || ManipulatorMode() == eDrag)
3289     {
3290       translateSelected(nudge);
3291     }
3292   }
3293
3294   void endMove();
3295   void freezeTransforms();
3296
3297   void renderSolid(Renderer& renderer, const VolumeTest& volume) const;
3298   void renderWireframe(Renderer& renderer, const VolumeTest& volume) const
3299   {
3300     renderSolid(renderer, volume);
3301   }
3302
3303   const Matrix4& GetPivot2World() const
3304   {
3305     ConstructPivot();
3306     return m_pivot2world;
3307   }
3308
3309   static void constructStatic()
3310   {
3311     m_state = GlobalShaderCache().capture("$POINT");
3312   #if defined(DEBUG_SELECTION)
3313     g_state_clipped = GlobalShaderCache().capture("$DEBUG_CLIPPED");
3314   #endif
3315     TranslateManipulator::m_state_wire = GlobalShaderCache().capture("$WIRE_OVERLAY");
3316     TranslateManipulator::m_state_fill = GlobalShaderCache().capture("$FLATSHADE_OVERLAY");
3317     RotateManipulator::m_state_outer = GlobalShaderCache().capture("$WIRE_OVERLAY");
3318   }
3319
3320   static void destroyStatic()
3321   {
3322   #if defined(DEBUG_SELECTION)
3323     GlobalShaderCache().release("$DEBUG_CLIPPED");
3324   #endif
3325     GlobalShaderCache().release("$WIRE_OVERLAY");
3326     GlobalShaderCache().release("$FLATSHADE_OVERLAY");
3327     GlobalShaderCache().release("$WIRE_OVERLAY");
3328     GlobalShaderCache().release("$POINT");
3329   }
3330 };
3331
3332 Shader* RadiantSelectionSystem::m_state = 0;
3333
3334
3335 namespace
3336 {
3337   RadiantSelectionSystem* g_RadiantSelectionSystem;
3338
3339   inline RadiantSelectionSystem& getSelectionSystem()
3340   {
3341     return *g_RadiantSelectionSystem;
3342   }
3343 }
3344
3345
3346
3347 class testselect_entity_visible : public scene::Graph::Walker
3348 {
3349   Selector& m_selector;
3350   SelectionTest& m_test;
3351 public:
3352   testselect_entity_visible(Selector& selector, SelectionTest& test)
3353     : m_selector(selector), m_test(test)
3354   {
3355   }
3356   bool pre(const scene::Path& path, scene::Instance& instance) const
3357   {
3358     Selectable* selectable = Instance_getSelectable(instance);
3359     if(selectable != 0
3360       && Node_isEntity(path.top()))
3361     {
3362       m_selector.pushSelectable(*selectable);
3363     }
3364
3365     SelectionTestable* selectionTestable = Instance_getSelectionTestable(instance);
3366     if(selectionTestable)
3367     {
3368       selectionTestable->testSelect(m_selector, m_test);
3369     }
3370
3371     return true;
3372   }
3373   void post(const scene::Path& path, scene::Instance& instance) const
3374   {
3375     Selectable* selectable = Instance_getSelectable(instance);
3376     if(selectable != 0
3377       && Node_isEntity(path.top()))
3378     {
3379       m_selector.popSelectable();
3380     }
3381   }
3382 };
3383
3384 class testselect_primitive_visible : public scene::Graph::Walker
3385 {
3386   Selector& m_selector;
3387   SelectionTest& m_test;
3388 public:
3389   testselect_primitive_visible(Selector& selector, SelectionTest& test)
3390     : m_selector(selector), m_test(test)
3391   {
3392   }
3393   bool pre(const scene::Path& path, scene::Instance& instance) const
3394   {
3395     Selectable* selectable = Instance_getSelectable(instance);
3396     if(selectable != 0)
3397     {
3398       m_selector.pushSelectable(*selectable);
3399     }
3400
3401     SelectionTestable* selectionTestable = Instance_getSelectionTestable(instance);
3402     if(selectionTestable)
3403     {
3404       selectionTestable->testSelect(m_selector, m_test);
3405     }
3406
3407     return true;
3408   }
3409   void post(const scene::Path& path, scene::Instance& instance) const
3410   {
3411     Selectable* selectable = Instance_getSelectable(instance);
3412     if(selectable != 0)
3413     {
3414       m_selector.popSelectable();
3415     }
3416   }
3417 };
3418
3419 class testselect_component_visible : public scene::Graph::Walker
3420 {
3421   Selector& m_selector;
3422   SelectionTest& m_test;
3423   SelectionSystem::EComponentMode m_mode;
3424 public:
3425   testselect_component_visible(Selector& selector, SelectionTest& test, SelectionSystem::EComponentMode mode)
3426     : m_selector(selector), m_test(test), m_mode(mode)
3427   {
3428   }
3429   bool pre(const scene::Path& path, scene::Instance& instance) const
3430   {
3431     ComponentSelectionTestable* componentSelectionTestable = Instance_getComponentSelectionTestable(instance);
3432     if(componentSelectionTestable)
3433     {
3434       componentSelectionTestable->testSelectComponents(m_selector, m_test, m_mode);
3435     }
3436
3437     return true;
3438   }
3439 };
3440
3441
3442 class testselect_component_visible_selected : public scene::Graph::Walker
3443 {
3444   Selector& m_selector;
3445   SelectionTest& m_test;
3446   SelectionSystem::EComponentMode m_mode;
3447 public:
3448   testselect_component_visible_selected(Selector& selector, SelectionTest& test, SelectionSystem::EComponentMode mode)
3449     : m_selector(selector), m_test(test), m_mode(mode)
3450   {
3451   }
3452   bool pre(const scene::Path& path, scene::Instance& instance) const
3453   {
3454     Selectable* selectable = Instance_getSelectable(instance);
3455     if(selectable != 0 && selectable->isSelected())
3456     {
3457       ComponentSelectionTestable* componentSelectionTestable = Instance_getComponentSelectionTestable(instance);
3458       if(componentSelectionTestable)
3459       {
3460         componentSelectionTestable->testSelectComponents(m_selector, m_test, m_mode);
3461       }
3462     }
3463
3464     return true;
3465   }
3466 };
3467
3468 void Scene_TestSelect_Primitive(Selector& selector, SelectionTest& test, const VolumeTest& volume)
3469 {
3470   Scene_forEachVisible(GlobalSceneGraph(), volume, testselect_primitive_visible(selector, test));
3471 }
3472
3473 void Scene_TestSelect_Component_Selected(Selector& selector, SelectionTest& test, const VolumeTest& volume, SelectionSystem::EComponentMode componentMode)
3474 {
3475   Scene_forEachVisible(GlobalSceneGraph(), volume, testselect_component_visible_selected(selector, test, componentMode));
3476 }
3477
3478 void Scene_TestSelect_Component(Selector& selector, SelectionTest& test, const VolumeTest& volume, SelectionSystem::EComponentMode componentMode)
3479 {
3480   Scene_forEachVisible(GlobalSceneGraph(), volume, testselect_component_visible(selector, test, componentMode));
3481 }
3482
3483 void RadiantSelectionSystem::Scene_TestSelect(Selector& selector, SelectionTest& test, const View& view, SelectionSystem::EMode mode, SelectionSystem::EComponentMode componentMode)
3484 {
3485   switch(mode)
3486   {
3487   case eEntity:
3488     {
3489       Scene_forEachVisible(GlobalSceneGraph(), view, testselect_entity_visible(selector, test));
3490     }
3491     break;
3492   case ePrimitive:
3493     Scene_TestSelect_Primitive(selector, test, view);
3494     break;
3495   case eComponent:
3496     Scene_TestSelect_Component_Selected(selector, test, view, componentMode);
3497     break;
3498   }
3499 }
3500
3501 class FreezeTransforms : public scene::Graph::Walker
3502 {
3503 public:
3504   bool pre(const scene::Path& path, scene::Instance& instance) const
3505   {
3506     TransformNode* transformNode = Node_getTransformNode(path.top());
3507     if(transformNode != 0)
3508     {
3509       Transformable* transform = Instance_getTransformable(instance);
3510       if(transform != 0)
3511       {
3512         transform->freezeTransform(); 
3513       }
3514     }
3515     return true;
3516   }
3517 };
3518
3519 void RadiantSelectionSystem::freezeTransforms()
3520 {
3521   GlobalSceneGraph().traverse(FreezeTransforms());
3522 }
3523
3524
3525 void RadiantSelectionSystem::endMove()
3526 {
3527   freezeTransforms();
3528
3529   if(Mode() == ePrimitive)
3530   {
3531     if(ManipulatorMode() == eDrag)
3532     {
3533       Scene_SelectAll_Component(false, SelectionSystem::eFace);
3534     }
3535   }
3536
3537   m_pivot_moving = false;
3538   pivotChanged();
3539
3540   SceneChangeNotify();
3541
3542   if(m_undo_begun)
3543   {
3544     StringOutputStream command;
3545
3546     if(ManipulatorMode() == eTranslate)
3547     {
3548       command << "translateTool";
3549       outputTranslation(command);
3550     }
3551     else if(ManipulatorMode() == eRotate)
3552     {
3553       command << "rotateTool";
3554       outputRotation(command);
3555     }
3556     else if(ManipulatorMode() == eScale)
3557     {
3558       command << "scaleTool";
3559       outputScale(command);
3560     }
3561     else if(ManipulatorMode() == eDrag)
3562     {
3563       command << "dragTool";
3564     }
3565
3566     GlobalUndoSystem().finish(command.c_str());
3567   }
3568
3569 }
3570
3571 inline AABB Instance_getPivotBounds(scene::Instance& instance)
3572 {
3573   Entity* entity = Node_getEntity(instance.path().top());
3574   if(entity != 0
3575     && (entity->getEntityClass().fixedsize
3576     || !node_is_group(instance.path().top())))
3577   {
3578     Editable* editable = Node_getEditable(instance.path().top());
3579     if(editable != 0)
3580     {
3581       return AABB(vector4_to_vector3(matrix4_multiplied_by_matrix4(instance.localToWorld(), editable->getLocalPivot()).t()), Vector3(0, 0, 0));
3582     }
3583     else
3584     {
3585       return AABB(vector4_to_vector3(instance.localToWorld().t()), Vector3(0, 0, 0));
3586     }
3587   }
3588
3589   return instance.worldAABB();
3590 }
3591
3592 class bounds_selected : public scene::Graph::Walker
3593 {
3594   AABB& m_bounds;
3595 public:
3596   bounds_selected(AABB& bounds)
3597     : m_bounds(bounds)
3598   {
3599     m_bounds = AABB();
3600   }
3601   bool pre(const scene::Path& path, scene::Instance& instance) const
3602   {
3603     Selectable* selectable = Instance_getSelectable(instance);
3604     if(selectable != 0
3605       && selectable->isSelected())
3606     {
3607       aabb_extend_by_aabb_safe(m_bounds, Instance_getPivotBounds(instance));
3608     }
3609     return true;
3610   }
3611 };
3612
3613 class bounds_selected_component : public scene::Graph::Walker
3614 {
3615   AABB& m_bounds;
3616 public:
3617   bounds_selected_component(AABB& bounds)
3618     : m_bounds(bounds)
3619   {
3620     m_bounds = AABB();
3621   }
3622   bool pre(const scene::Path& path, scene::Instance& instance) const
3623   {
3624     Selectable* selectable = Instance_getSelectable(instance);
3625     if(selectable != 0
3626       && selectable->isSelected())
3627     {
3628       ComponentEditable* componentEditable = Instance_getComponentEditable(instance);
3629       if(componentEditable)
3630       {
3631         aabb_extend_by_aabb_safe(m_bounds, aabb_for_oriented_aabb_safe(componentEditable->getSelectedComponentsBounds(), instance.localToWorld()));
3632       }
3633     }
3634     return true;
3635   }
3636 };
3637
3638 void Scene_BoundsSelected(scene::Graph& graph, AABB& bounds)
3639 {
3640   graph.traverse(bounds_selected(bounds));
3641 }
3642
3643 void Scene_BoundsSelectedComponent(scene::Graph& graph, AABB& bounds)
3644 {
3645   graph.traverse(bounds_selected_component(bounds));
3646 }
3647
3648 #if 0
3649 inline void pivot_for_node(Matrix4& pivot, scene::Node& node, scene::Instance& instance)
3650 {
3651   ComponentEditable* componentEditable = Instance_getComponentEditable(instance);
3652   if(GlobalSelectionSystem().Mode() == SelectionSystem::eComponent
3653     && componentEditable != 0)
3654   {
3655     pivot = matrix4_translation_for_vec3(componentEditable->getSelectedComponentsBounds().origin);
3656   }
3657   else
3658   {
3659     Bounded* bounded = Instance_getBounded(instance);
3660     if(bounded != 0)
3661     {
3662       pivot = matrix4_translation_for_vec3(bounded->localAABB().origin);
3663     }
3664     else
3665     {
3666       pivot = g_matrix4_identity;
3667     }
3668   }
3669 }
3670 #endif
3671
3672 void RadiantSelectionSystem::ConstructPivot() const
3673 {
3674   if(!m_pivotChanged || m_pivot_moving)
3675     return;
3676   m_pivotChanged = false;
3677
3678   Vector3 m_object_pivot;
3679
3680   if(!nothingSelected())
3681   {
3682     {
3683       AABB bounds;
3684       if(Mode() == eComponent)
3685       {
3686         Scene_BoundsSelectedComponent(GlobalSceneGraph(), bounds);
3687       }
3688       else
3689       {
3690         Scene_BoundsSelected(GlobalSceneGraph(), bounds);
3691       }
3692       m_object_pivot = bounds.origin;
3693     }
3694
3695     vector3_snap(m_object_pivot, GetGridSize());
3696     m_pivot2world = matrix4_translation_for_vec3(m_object_pivot);
3697
3698     switch(m_manipulator_mode)
3699     {
3700     case eTranslate:
3701       break;
3702     case eRotate:
3703       if(Mode() == eComponent)
3704       {
3705         matrix4_assign_rotation_for_pivot(m_pivot2world, m_component_selection.back());
3706       }
3707       else
3708       {
3709         matrix4_assign_rotation_for_pivot(m_pivot2world, m_selection.back());
3710       }
3711       break;
3712     case eScale:
3713       if(Mode() == eComponent)
3714       {
3715         matrix4_assign_rotation_for_pivot(m_pivot2world, m_component_selection.back());
3716       }
3717       else
3718       {
3719         matrix4_assign_rotation_for_pivot(m_pivot2world, m_selection.back());
3720       }
3721       break;
3722     default:
3723       break;
3724     }
3725   }
3726 }
3727
3728 void RadiantSelectionSystem::renderSolid(Renderer& renderer, const VolumeTest& volume) const
3729 {
3730   //if(view->TestPoint(m_object_pivot))
3731   if(!nothingSelected())
3732   {
3733     renderer.Highlight(Renderer::ePrimitive, false);
3734     renderer.Highlight(Renderer::eFace, false);
3735
3736     renderer.SetState(m_state, Renderer::eWireframeOnly);
3737     renderer.SetState(m_state, Renderer::eFullMaterials);
3738
3739     m_manipulator->render(renderer, volume, GetPivot2World());
3740   }
3741
3742 #if defined(DEBUG_SELECTION)
3743   renderer.SetState(g_state_clipped, Renderer::eWireframeOnly);
3744   renderer.SetState(g_state_clipped, Renderer::eFullMaterials);
3745   renderer.addRenderable(g_render_clipped, g_render_clipped.m_world);
3746 #endif
3747 }
3748
3749
3750 void SelectionSystem_OnBoundsChanged()
3751 {
3752   getSelectionSystem().pivotChanged();
3753 }
3754
3755
3756 SignalHandlerId SelectionSystem_boundsChanged;
3757
3758 void SelectionSystem_Construct()
3759 {
3760   RadiantSelectionSystem::constructStatic();
3761
3762   g_RadiantSelectionSystem = new RadiantSelectionSystem;
3763
3764   SelectionSystem_boundsChanged = GlobalSceneGraph().addBoundsChangedCallback(FreeCaller<SelectionSystem_OnBoundsChanged>());
3765
3766   GlobalShaderCache().attachRenderable(getSelectionSystem());
3767 }
3768
3769 void SelectionSystem_Destroy()
3770 {
3771   GlobalShaderCache().detachRenderable(getSelectionSystem());
3772
3773   GlobalSceneGraph().removeBoundsChangedCallback(SelectionSystem_boundsChanged);
3774
3775   delete g_RadiantSelectionSystem;
3776
3777   RadiantSelectionSystem::destroyStatic();
3778 }
3779
3780
3781
3782
3783 inline float screen_normalised(float pos, std::size_t size)
3784 {
3785   return ((2.0f * pos) / size) - 1.0f;
3786 }
3787
3788 typedef Vector2 DeviceVector;
3789
3790 inline DeviceVector window_to_normalised_device(WindowVector window, std::size_t width, std::size_t height)
3791 {
3792   return DeviceVector(screen_normalised(window.x(), width), screen_normalised(height - 1 - window.y(), height));
3793 }
3794
3795 inline float device_constrained(float pos)
3796 {
3797   return std::min(1.0f, std::max(-1.0f, pos));
3798 }
3799
3800 inline DeviceVector device_constrained(DeviceVector device)
3801 {
3802   return DeviceVector(device_constrained(device.x()), device_constrained(device.y()));
3803 }
3804
3805 inline float window_constrained(float pos, std::size_t origin, std::size_t size)
3806 {
3807   return std::min(static_cast<float>(origin + size), std::max(static_cast<float>(origin), pos));
3808 }
3809
3810 inline WindowVector window_constrained(WindowVector window, std::size_t x, std::size_t y, std::size_t width, std::size_t height)
3811 {
3812   return WindowVector(window_constrained(window.x(), x, width), window_constrained(window.y(), y, height));
3813 }
3814
3815 typedef Callback1<DeviceVector> MouseEventCallback;
3816
3817 Single<MouseEventCallback> g_mouseMovedCallback;
3818 Single<MouseEventCallback> g_mouseUpCallback;
3819
3820 #if 1
3821 const ButtonIdentifier c_button_select = c_buttonLeft;
3822 const ModifierFlags c_modifier_manipulator = c_modifierNone;
3823 const ModifierFlags c_modifier_toggle = c_modifierShift;
3824 const ModifierFlags c_modifier_replace = c_modifierShift | c_modifierAlt;
3825 const ModifierFlags c_modifier_face = c_modifierControl;
3826 #else
3827 const ButtonIdentifier c_button_select = c_buttonLeft;
3828 const ModifierFlags c_modifier_manipulator = c_modifierNone;
3829 const ModifierFlags c_modifier_toggle = c_modifierControl;
3830 const ModifierFlags c_modifier_replace = c_modifierNone;
3831 const ModifierFlags c_modifier_face = c_modifierShift;
3832 #endif
3833 const ModifierFlags c_modifier_toggle_face = c_modifier_toggle | c_modifier_face;
3834 const ModifierFlags c_modifier_replace_face = c_modifier_replace | c_modifier_face;
3835
3836 const ButtonIdentifier c_button_texture = c_buttonMiddle;
3837 const ModifierFlags c_modifier_apply_texture = c_modifierControl | c_modifierShift;
3838 const ModifierFlags c_modifier_copy_texture = c_modifierNone;
3839
3840 class Selector_
3841 {
3842   RadiantSelectionSystem::EModifier modifier_for_state(ModifierFlags state)
3843   {
3844     if(state == c_modifier_toggle || state == c_modifier_toggle_face)
3845     {
3846       return RadiantSelectionSystem::eToggle;
3847     }
3848     if(state == c_modifier_replace || state == c_modifier_replace_face)
3849     {
3850       return RadiantSelectionSystem::eReplace;
3851     }
3852     return RadiantSelectionSystem::eManipulator;
3853   }
3854
3855   rect_t getDeviceArea() const
3856   {
3857     DeviceVector delta(m_current - m_start);
3858     if(selecting() && fabs(delta.x()) > m_epsilon.x() && fabs(delta.y()) > m_epsilon.y())
3859     {
3860       return SelectionBoxForArea(&m_start[0], &delta[0]);
3861     }
3862     else
3863     {
3864       rect_t default_area = { { 0, 0, }, { 0, 0, }, };
3865       return default_area;
3866     }
3867   }
3868
3869 public:
3870   DeviceVector m_start;
3871   DeviceVector m_current;
3872   DeviceVector m_epsilon;
3873   std::size_t m_unmoved_replaces;
3874   ModifierFlags m_state;
3875   const View* m_view;
3876   RectangleCallback m_window_update;
3877
3878   Selector_() :