2 Copyright (C) 2001-2006, William Joseph.
5 This file is part of GtkRadiant.
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.
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.
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
22 #if !defined( INCLUDED_MATH_FRUSTUM_H )
23 #define INCLUDED_MATH_FRUSTUM_H
26 /// \brief View-frustum data types and related operations.
28 #include "generic/enumeration.h"
29 #include "math/matrix.h"
30 #include "math/plane.h"
31 #include "math/aabb.h"
32 #include "math/line.h"
34 inline Matrix4 matrix4_frustum( float left, float right, float bottom, float top, float nearval, float farval ){
36 static_cast<float>( ( 2 * nearval ) / ( right - left ) ),
41 static_cast<float>( ( 2 * nearval ) / ( top - bottom ) ),
44 static_cast<float>( ( right + left ) / ( right - left ) ),
45 static_cast<float>( ( top + bottom ) / ( top - bottom ) ),
46 static_cast<float>( -( farval + nearval ) / ( farval - nearval ) ),
50 static_cast<float>( -( 2 * farval * nearval ) / ( farval - nearval ) ),
57 typedef unsigned char ClipResult;
58 const ClipResult c_CLIP_PASS = 0x00; // 000000
59 const ClipResult c_CLIP_LT_X = 0x01; // 000001
60 const ClipResult c_CLIP_GT_X = 0x02; // 000010
61 const ClipResult c_CLIP_LT_Y = 0x04; // 000100
62 const ClipResult c_CLIP_GT_Y = 0x08; // 001000
63 const ClipResult c_CLIP_LT_Z = 0x10; // 010000
64 const ClipResult c_CLIP_GT_Z = 0x20; // 100000
65 const ClipResult c_CLIP_FAIL = 0x3F; // 111111
67 template<typename Index>
71 static bool compare( const Vector4& self ){
72 return self[Index::VALUE] < self[3];
74 static double scale( const Vector4& self, const Vector4& other ){
75 return ( self[Index::VALUE] - self[3] ) / ( other[3] - other[Index::VALUE] );
79 template<typename Index>
83 static bool compare( const Vector4& self ){
84 return self[Index::VALUE] > -self[3];
86 static double scale( const Vector4& self, const Vector4& other ){
87 return ( self[Index::VALUE] + self[3] ) / ( -other[3] - other[Index::VALUE] );
91 template<typename ClipPlane>
92 class Vector4ClipPolygon
95 typedef Vector4* iterator;
96 typedef const Vector4* const_iterator;
98 static std::size_t apply( const_iterator first, const_iterator last, iterator out ){
99 const_iterator next = first, i = last - 1;
101 bool b0 = ClipPlane::compare( *i );
102 while ( next != last )
104 bool b1 = ClipPlane::compare( *next );
106 *out = vector4_subtracted( *next, *i );
108 double scale = ClipPlane::scale( *i, *out );
110 ( *out )[0] = static_cast<float>( ( *i )[0] + scale * ( ( *out )[0] ) );
111 ( *out )[1] = static_cast<float>( ( *i )[1] + scale * ( ( *out )[1] ) );
112 ( *out )[2] = static_cast<float>( ( *i )[2] + scale * ( ( *out )[2] ) );
113 ( *out )[3] = static_cast<float>( ( *i )[3] + scale * ( ( *out )[3] ) );
132 #define CLIP_X_LT_W( p ) ( Vector4ClipLT< IntegralConstant<0> >::compare( p ) )
133 #define CLIP_X_GT_W( p ) ( Vector4ClipGT< IntegralConstant<0> >::compare( p ) )
134 #define CLIP_Y_LT_W( p ) ( Vector4ClipLT< IntegralConstant<1> >::compare( p ) )
135 #define CLIP_Y_GT_W( p ) ( Vector4ClipGT< IntegralConstant<1> >::compare( p ) )
136 #define CLIP_Z_LT_W( p ) ( Vector4ClipLT< IntegralConstant<2> >::compare( p ) )
137 #define CLIP_Z_GT_W( p ) ( Vector4ClipGT< IntegralConstant<2> >::compare( p ) )
139 inline ClipResult homogenous_clip_point( const Vector4& clipped ){
140 ClipResult result = c_CLIP_FAIL;
141 if ( CLIP_X_LT_W( clipped ) ) {
142 result &= ~c_CLIP_LT_X; // X < W
144 if ( CLIP_X_GT_W( clipped ) ) {
145 result &= ~c_CLIP_GT_X; // X > -W
147 if ( CLIP_Y_LT_W( clipped ) ) {
148 result &= ~c_CLIP_LT_Y; // Y < W
150 if ( CLIP_Y_GT_W( clipped ) ) {
151 result &= ~c_CLIP_GT_Y; // Y > -W
153 if ( CLIP_Z_LT_W( clipped ) ) {
154 result &= ~c_CLIP_LT_Z; // Z < W
156 if ( CLIP_Z_GT_W( clipped ) ) {
157 result &= ~c_CLIP_GT_Z; // Z > -W
162 /// \brief Clips \p point by canonical matrix \p self.
163 /// Stores the result in \p clipped.
164 /// Returns a bitmask indicating which clip-planes the point was outside.
165 inline ClipResult matrix4_clip_point( const Matrix4& self, const Vector3& point, Vector4& clipped ){
166 clipped[0] = point[0];
167 clipped[1] = point[1];
168 clipped[2] = point[2];
170 matrix4_transform_vector4( self, clipped );
171 return homogenous_clip_point( clipped );
175 inline std::size_t homogenous_clip_triangle( Vector4 clipped[9] ){
177 std::size_t count = 3;
178 count = Vector4ClipPolygon< Vector4ClipLT< IntegralConstant<0> > >::apply( clipped, clipped + count, buffer );
179 count = Vector4ClipPolygon< Vector4ClipGT< IntegralConstant<0> > >::apply( buffer, buffer + count, clipped );
180 count = Vector4ClipPolygon< Vector4ClipLT< IntegralConstant<1> > >::apply( clipped, clipped + count, buffer );
181 count = Vector4ClipPolygon< Vector4ClipGT< IntegralConstant<1> > >::apply( buffer, buffer + count, clipped );
182 count = Vector4ClipPolygon< Vector4ClipLT< IntegralConstant<2> > >::apply( clipped, clipped + count, buffer );
183 return Vector4ClipPolygon< Vector4ClipGT< IntegralConstant<2> > >::apply( buffer, buffer + count, clipped );
186 /// \brief Transforms and clips the triangle formed by \p p0, \p p1, \p p2 by the canonical matrix \p self.
187 /// Stores the resulting polygon in \p clipped.
188 /// Returns the number of points in the resulting polygon.
189 inline std::size_t matrix4_clip_triangle( const Matrix4& self, const Vector3& p0, const Vector3& p1, const Vector3& p2, Vector4 clipped[9] ){
190 clipped[0][0] = p0[0];
191 clipped[0][1] = p0[1];
192 clipped[0][2] = p0[2];
194 clipped[1][0] = p1[0];
195 clipped[1][1] = p1[1];
196 clipped[1][2] = p1[2];
198 clipped[2][0] = p2[0];
199 clipped[2][1] = p2[1];
200 clipped[2][2] = p2[2];
203 matrix4_transform_vector4( self, clipped[0] );
204 matrix4_transform_vector4( self, clipped[1] );
205 matrix4_transform_vector4( self, clipped[2] );
207 return homogenous_clip_triangle( clipped );
210 inline std::size_t homogenous_clip_line( Vector4 clipped[2] ){
211 const Vector4& p0 = clipped[0];
212 const Vector4& p1 = clipped[1];
216 ClipResult mask0 = homogenous_clip_point( clipped[0] );
217 ClipResult mask1 = homogenous_clip_point( clipped[1] );
219 if ( ( mask0 | mask1 ) == c_CLIP_PASS ) { // both points passed all planes
223 if ( mask0 & mask1 ) { // both points failed any one plane
229 const bool index = CLIP_X_LT_W( p0 );
230 if ( index ^ CLIP_X_LT_W( p1 ) ) {
231 Vector4 clip( vector4_subtracted( p1, p0 ) );
233 double scale = ( p0[0] - p0[3] ) / ( clip[3] - clip[0] );
235 clip[0] = static_cast<float>( p0[0] + scale * clip[0] );
236 clip[1] = static_cast<float>( p0[1] + scale * clip[1] );
237 clip[2] = static_cast<float>( p0[2] + scale * clip[2] );
238 clip[3] = static_cast<float>( p0[3] + scale * clip[3] );
240 clipped[index] = clip;
242 else if ( index == 0 ) {
248 const bool index = CLIP_X_GT_W( p0 );
249 if ( index ^ CLIP_X_GT_W( p1 ) ) {
250 Vector4 clip( vector4_subtracted( p1, p0 ) );
252 double scale = ( p0[0] + p0[3] ) / ( -clip[3] - clip[0] );
254 clip[0] = static_cast<float>( p0[0] + scale * clip[0] );
255 clip[1] = static_cast<float>( p0[1] + scale * clip[1] );
256 clip[2] = static_cast<float>( p0[2] + scale * clip[2] );
257 clip[3] = static_cast<float>( p0[3] + scale * clip[3] );
259 clipped[index] = clip;
261 else if ( index == 0 ) {
267 const bool index = CLIP_Y_LT_W( p0 );
268 if ( index ^ CLIP_Y_LT_W( p1 ) ) {
269 Vector4 clip( vector4_subtracted( p1, p0 ) );
271 double scale = ( p0[1] - p0[3] ) / ( clip[3] - clip[1] );
273 clip[0] = static_cast<float>( p0[0] + scale * clip[0] );
274 clip[1] = static_cast<float>( p0[1] + scale * clip[1] );
275 clip[2] = static_cast<float>( p0[2] + scale * clip[2] );
276 clip[3] = static_cast<float>( p0[3] + scale * clip[3] );
278 clipped[index] = clip;
280 else if ( index == 0 ) {
286 const bool index = CLIP_Y_GT_W( p0 );
287 if ( index ^ CLIP_Y_GT_W( p1 ) ) {
288 Vector4 clip( vector4_subtracted( p1, p0 ) );
290 double scale = ( p0[1] + p0[3] ) / ( -clip[3] - clip[1] );
292 clip[0] = static_cast<float>( p0[0] + scale * clip[0] );
293 clip[1] = static_cast<float>( p0[1] + scale * clip[1] );
294 clip[2] = static_cast<float>( p0[2] + scale * clip[2] );
295 clip[3] = static_cast<float>( p0[3] + scale * clip[3] );
297 clipped[index] = clip;
299 else if ( index == 0 ) {
305 const bool index = CLIP_Z_LT_W( p0 );
306 if ( index ^ CLIP_Z_LT_W( p1 ) ) {
307 Vector4 clip( vector4_subtracted( p1, p0 ) );
309 double scale = ( p0[2] - p0[3] ) / ( clip[3] - clip[2] );
311 clip[0] = static_cast<float>( p0[0] + scale * clip[0] );
312 clip[1] = static_cast<float>( p0[1] + scale * clip[1] );
313 clip[2] = static_cast<float>( p0[2] + scale * clip[2] );
314 clip[3] = static_cast<float>( p0[3] + scale * clip[3] );
316 clipped[index] = clip;
318 else if ( index == 0 ) {
324 const bool index = CLIP_Z_GT_W( p0 );
325 if ( index ^ CLIP_Z_GT_W( p1 ) ) {
326 Vector4 clip( vector4_subtracted( p1, p0 ) );
328 double scale = ( p0[2] + p0[3] ) / ( -clip[3] - clip[2] );
330 clip[0] = static_cast<float>( p0[0] + scale * clip[0] );
331 clip[1] = static_cast<float>( p0[1] + scale * clip[1] );
332 clip[2] = static_cast<float>( p0[2] + scale * clip[2] );
333 clip[3] = static_cast<float>( p0[3] + scale * clip[3] );
335 clipped[index] = clip;
337 else if ( index == 0 ) {
345 /// \brief Transforms and clips the line formed by \p p0, \p p1 by the canonical matrix \p self.
346 /// Stores the resulting line in \p clipped.
347 /// Returns the number of points in the resulting line.
348 inline std::size_t matrix4_clip_line( const Matrix4& self, const Vector3& p0, const Vector3& p1, Vector4 clipped[2] ){
349 clipped[0][0] = p0[0];
350 clipped[0][1] = p0[1];
351 clipped[0][2] = p0[2];
353 clipped[1][0] = p1[0];
354 clipped[1][1] = p1[1];
355 clipped[1][2] = p1[2];
358 matrix4_transform_vector4( self, clipped[0] );
359 matrix4_transform_vector4( self, clipped[1] );
361 return homogenous_clip_line( clipped );
369 Plane3 right, left, bottom, top, back, front;
373 Frustum( const Plane3& _right,
375 const Plane3& _bottom,
378 const Plane3& _front )
379 : right( _right ), left( _left ), bottom( _bottom ), top( _top ), back( _back ), front( _front ){
383 inline Frustum frustum_transformed( const Frustum& frustum, const Matrix4& transform ){
385 plane3_transformed( frustum.right, transform ),
386 plane3_transformed( frustum.left, transform ),
387 plane3_transformed( frustum.bottom, transform ),
388 plane3_transformed( frustum.top, transform ),
389 plane3_transformed( frustum.back, transform ),
390 plane3_transformed( frustum.front, transform )
394 inline Frustum frustum_inverse_transformed( const Frustum& frustum, const Matrix4& transform ){
396 plane3_inverse_transformed( frustum.right, transform ),
397 plane3_inverse_transformed( frustum.left, transform ),
398 plane3_inverse_transformed( frustum.bottom, transform ),
399 plane3_inverse_transformed( frustum.top, transform ),
400 plane3_inverse_transformed( frustum.back, transform ),
401 plane3_inverse_transformed( frustum.front, transform )
405 inline bool viewproj_test_point( const Matrix4& viewproj, const Vector3& point ){
406 Vector4 hpoint( matrix4_transformed_vector4( viewproj, Vector4( point, 1.0f ) ) );
407 if ( fabs( hpoint[0] ) < fabs( hpoint[3] )
408 && fabs( hpoint[1] ) < fabs( hpoint[3] )
409 && fabs( hpoint[2] ) < fabs( hpoint[3] ) ) {
415 inline bool viewproj_test_transformed_point( const Matrix4& viewproj, const Vector3& point, const Matrix4& localToWorld ){
416 return viewproj_test_point( viewproj, matrix4_transformed_point( localToWorld, point ) );
419 inline Frustum frustum_from_viewproj( const Matrix4& viewproj ){
422 plane3_normalised( Plane3( viewproj[ 3] - viewproj[ 0], viewproj[ 7] - viewproj[ 4], viewproj[11] - viewproj[ 8], viewproj[15] - viewproj[12] ) ),
423 plane3_normalised( Plane3( viewproj[ 3] + viewproj[ 0], viewproj[ 7] + viewproj[ 4], viewproj[11] + viewproj[ 8], viewproj[15] + viewproj[12] ) ),
424 plane3_normalised( Plane3( viewproj[ 3] + viewproj[ 1], viewproj[ 7] + viewproj[ 5], viewproj[11] + viewproj[ 9], viewproj[15] + viewproj[13] ) ),
425 plane3_normalised( Plane3( viewproj[ 3] - viewproj[ 1], viewproj[ 7] - viewproj[ 5], viewproj[11] - viewproj[ 9], viewproj[15] - viewproj[13] ) ),
426 plane3_normalised( Plane3( viewproj[ 3] - viewproj[ 2], viewproj[ 7] - viewproj[ 6], viewproj[11] - viewproj[10], viewproj[15] - viewproj[14] ) ),
427 plane3_normalised( Plane3( viewproj[ 3] + viewproj[ 2], viewproj[ 7] + viewproj[ 6], viewproj[11] + viewproj[10], viewproj[15] + viewproj[14] ) )
431 struct VolumeIntersection
441 typedef EnumeratedValue<VolumeIntersection> VolumeIntersectionValue;
443 const VolumeIntersectionValue c_volumeOutside( VolumeIntersectionValue::OUTSIDE );
444 const VolumeIntersectionValue c_volumeInside( VolumeIntersectionValue::INSIDE );
445 const VolumeIntersectionValue c_volumePartial( VolumeIntersectionValue::PARTIAL );
447 inline VolumeIntersectionValue frustum_test_aabb( const Frustum& frustum, const AABB& aabb ){
448 VolumeIntersectionValue result = c_volumeInside;
450 switch ( aabb_classify_plane( aabb, frustum.right ) )
453 return c_volumeOutside;
455 result = c_volumePartial;
458 switch ( aabb_classify_plane( aabb, frustum.left ) )
461 return c_volumeOutside;
463 result = c_volumePartial;
466 switch ( aabb_classify_plane( aabb, frustum.bottom ) )
469 return c_volumeOutside;
471 result = c_volumePartial;
474 switch ( aabb_classify_plane( aabb, frustum.top ) )
477 return c_volumeOutside;
479 result = c_volumePartial;
482 switch ( aabb_classify_plane( aabb, frustum.back ) )
485 return c_volumeOutside;
487 result = c_volumePartial;
490 switch ( aabb_classify_plane( aabb, frustum.front ) )
493 return c_volumeOutside;
495 result = c_volumePartial;
501 inline double plane_distance_to_point( const Plane3& plane, const Vector3& point ){
502 return vector3_dot( plane.normal(), point ) + plane.d;
505 inline double plane_distance_to_oriented_extents( const Plane3& plane, const Vector3& extents, const Matrix4& orientation ){
506 return fabs( extents[0] * vector3_dot( plane.normal(), vector4_to_vector3( orientation.x() ) ) )
507 + fabs( extents[1] * vector3_dot( plane.normal(), vector4_to_vector3( orientation.y() ) ) )
508 + fabs( extents[2] * vector3_dot( plane.normal(), vector4_to_vector3( orientation.z() ) ) );
511 /// \brief Return false if \p aabb with \p orientation is partially or completely outside \p plane.
512 inline bool plane_contains_oriented_aabb( const Plane3& plane, const AABB& aabb, const Matrix4& orientation ){
513 double dot = plane_distance_to_point( plane, aabb.origin );
514 return !( dot > 0 || -dot < plane_distance_to_oriented_extents( plane, aabb.extents, orientation ) );
517 inline VolumeIntersectionValue frustum_intersects_transformed_aabb( const Frustum& frustum, const AABB& aabb, const Matrix4& localToWorld ){
518 AABB aabb_world( aabb );
519 matrix4_transform_point( localToWorld, aabb_world.origin );
521 if ( plane_contains_oriented_aabb( frustum.right, aabb_world, localToWorld )
522 || plane_contains_oriented_aabb( frustum.left, aabb_world, localToWorld )
523 || plane_contains_oriented_aabb( frustum.bottom, aabb_world, localToWorld )
524 || plane_contains_oriented_aabb( frustum.top, aabb_world, localToWorld )
525 || plane_contains_oriented_aabb( frustum.back, aabb_world, localToWorld )
526 || plane_contains_oriented_aabb( frustum.front, aabb_world, localToWorld ) ) {
527 return c_volumeOutside;
529 return c_volumeInside;
532 inline bool plane3_test_point( const Plane3& plane, const Vector3& point ){
533 return vector3_dot( point, plane.normal() ) + plane.dist() <= 0;
536 inline bool plane3_test_line( const Plane3& plane, const Segment& segment ){
537 return segment_classify_plane( segment, plane ) == 2;
540 inline bool frustum_test_point( const Frustum& frustum, const Vector3& point ){
541 return !plane3_test_point( frustum.right, point )
542 && !plane3_test_point( frustum.left, point )
543 && !plane3_test_point( frustum.bottom, point )
544 && !plane3_test_point( frustum.top, point )
545 && !plane3_test_point( frustum.back, point )
546 && !plane3_test_point( frustum.front, point );
549 inline bool frustum_test_line( const Frustum& frustum, const Segment& segment ){
550 return !plane3_test_line( frustum.right, segment )
551 && !plane3_test_line( frustum.left, segment )
552 && !plane3_test_line( frustum.bottom, segment )
553 && !plane3_test_line( frustum.top, segment )
554 && !plane3_test_line( frustum.back, segment )
555 && !plane3_test_line( frustum.front, segment );
558 inline bool viewer_test_plane( const Vector4& viewer, const Plane3& plane ){
559 return ( ( plane.a * viewer[0] )
560 + ( plane.b * viewer[1] )
561 + ( plane.c * viewer[2] )
562 + ( plane.d * viewer[3] ) ) > 0;
565 inline Vector3 triangle_cross( const Vector3& p0, const Vector3& p1, const Vector3& p2 ){
566 return vector3_cross( vector3_subtracted( p1, p0 ), vector3_subtracted( p1, p2 ) );
569 inline bool viewer_test_triangle( const Vector4& viewer, const Vector3& p0, const Vector3& p1, const Vector3& p2 ){
570 Vector3 cross( triangle_cross( p0, p1, p2 ) );
571 return ( ( viewer[0] * cross[0] )
572 + ( viewer[1] * cross[1] )
573 + ( viewer[2] * cross[2] )
574 + ( viewer[3] * 0 ) ) > 0;
577 inline Vector4 viewer_from_transformed_viewer( const Vector4& viewer, const Matrix4& transform ){
578 if ( viewer[3] == 0 ) {
579 return Vector4( matrix4_transformed_direction( transform, vector4_to_vector3( viewer ) ), 0 );
583 return Vector4( matrix4_transformed_point( transform, vector4_to_vector3( viewer ) ), viewer[3] );
587 inline bool viewer_test_transformed_plane( const Vector4& viewer, const Plane3& plane, const Matrix4& localToWorld ){
589 return viewer_test_plane( viewer_from_transformed_viewer( viewer, matrix4_affine_inverse( localToWorld ) ), plane );
591 return viewer_test_plane( viewer, plane3_transformed( plane, localToWorld ) );
595 inline Vector4 viewer_from_viewproj( const Matrix4& viewproj ){
596 // get viewer pos in object coords
597 Vector4 viewer( matrix4_transformed_vector4( matrix4_full_inverse( viewproj ), Vector4( 0, 0, -1, 0 ) ) );
598 if ( viewer[3] != 0 ) { // non-affine matrix
599 viewer[0] /= viewer[3];
600 viewer[1] /= viewer[3];
601 viewer[2] /= viewer[3];
602 viewer[3] /= viewer[3];