libs/math/frustum.h

   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 #if !defined( INCLUDED_MATH_FRUSTUM_H )
  23 #define INCLUDED_MATH_FRUSTUM_H
  24
  25 /// \file
  26 /// \brief View-frustum data types and related operations.
  27
  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"
  33
  34 inline Matrix4 matrix4_frustum( float left, float right, float bottom, float top, float nearval, float farval ){
  35         return Matrix4(
  36                            static_cast<float>( ( 2 * nearval ) / ( right - left ) ),
  37                            0,
  38                            0,
  39                            0,
  40                            0,
  41                            static_cast<float>( ( 2 * nearval ) / ( top - bottom ) ),
  42                            0,
  43                            0,
  44                            static_cast<float>( ( right + left ) / ( right - left ) ),
  45                            static_cast<float>( ( top + bottom ) / ( top - bottom ) ),
  46                            static_cast<float>( -( farval + nearval ) / ( farval - nearval ) ),
  47                            -1,
  48                            0,
  49                            0,
  50                            static_cast<float>( -( 2 * farval * nearval ) / ( farval - nearval ) ),
  51                            0
  52                            );
  53 }
  54
  55
  56
  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
  66
  67 template<typename Index>
  68 class Vector4ClipLT
  69 {
  70 public:
  71 static bool compare( const Vector4& self ){
  72         return self[Index::VALUE] < self[3];
  73 }
  74 static double scale( const Vector4& self, const Vector4& other ){
  75         return ( self[Index::VALUE] - self[3] ) / ( other[3] - other[Index::VALUE] );
  76 }
  77 };
  78
  79 template<typename Index>
  80 class Vector4ClipGT
  81 {
  82 public:
  83 static bool compare( const Vector4& self ){
  84         return self[Index::VALUE] > -self[3];
  85 }
  86 static double scale( const Vector4& self, const Vector4& other ){
  87         return ( self[Index::VALUE] + self[3] ) / ( -other[3] - other[Index::VALUE] );
  88 }
  89 };
  90
  91 template<typename ClipPlane>
  92 class Vector4ClipPolygon
  93 {
  94 public:
  95 typedef Vector4* iterator;
  96 typedef const Vector4* const_iterator;
  97
  98 static std::size_t apply( const_iterator first, const_iterator last, iterator out ){
  99         const_iterator next = first, i = last - 1;
 100         iterator tmp( out );
 101         bool b0 = ClipPlane::compare( *i );
 102         while ( next != last )
 103         {
 104                 bool b1 = ClipPlane::compare( *next );
 105                 if ( b0 ^ b1 ) {
 106                         *out = vector4_subtracted( *next, *i );
 107
 108                         double scale = ClipPlane::scale( *i, *out );
 109
 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] ) );
 114
 115                         ++out;
 116                 }
 117
 118                 if ( b1 ) {
 119                         *out = *next;
 120                         ++out;
 121                 }
 122
 123                 i = next;
 124                 ++next;
 125                 b0 = b1;
 126         }
 127
 128         return out - tmp;
 129 }
 130 };
 131
 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 ) )
 138
 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
 143         }
 144         if ( CLIP_X_GT_W( clipped ) ) {
 145                 result &= ~c_CLIP_GT_X;                    // X > -W
 146         }
 147         if ( CLIP_Y_LT_W( clipped ) ) {
 148                 result &= ~c_CLIP_LT_Y;                    // Y < W
 149         }
 150         if ( CLIP_Y_GT_W( clipped ) ) {
 151                 result &= ~c_CLIP_GT_Y;                    // Y > -W
 152         }
 153         if ( CLIP_Z_LT_W( clipped ) ) {
 154                 result &= ~c_CLIP_LT_Z;                    // Z < W
 155         }
 156         if ( CLIP_Z_GT_W( clipped ) ) {
 157                 result &= ~c_CLIP_GT_Z;                    // Z > -W
 158         }
 159         return result;
 160 }
 161
 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];
 169         clipped[3] = 1;
 170         matrix4_transform_vector4( self, clipped );
 171         return homogenous_clip_point( clipped );
 172 }
 173
 174
 175 inline std::size_t homogenous_clip_triangle( Vector4 clipped[9] ){
 176         Vector4 buffer[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 );
 184 }
 185
 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];
 193         clipped[0][3] = 1;
 194         clipped[1][0] = p1[0];
 195         clipped[1][1] = p1[1];
 196         clipped[1][2] = p1[2];
 197         clipped[1][3] = 1;
 198         clipped[2][0] = p2[0];
 199         clipped[2][1] = p2[1];
 200         clipped[2][2] = p2[2];
 201         clipped[2][3] = 1;
 202
 203         matrix4_transform_vector4( self, clipped[0] );
 204         matrix4_transform_vector4( self, clipped[1] );
 205         matrix4_transform_vector4( self, clipped[2] );
 206
 207         return homogenous_clip_triangle( clipped );
 208 }
 209
 210 inline std::size_t homogenous_clip_line( Vector4 clipped[2] ){
 211         const Vector4& p0 = clipped[0];
 212         const Vector4& p1 = clipped[1];
 213
 214         // early out
 215         {
 216                 ClipResult mask0 = homogenous_clip_point( clipped[0] );
 217                 ClipResult mask1 = homogenous_clip_point( clipped[1] );
 218
 219                 if ( ( mask0 | mask1 ) == c_CLIP_PASS ) { // both points passed all planes
 220                         return 2;
 221                 }
 222
 223                 if ( mask0 & mask1 ) { // both points failed any one plane
 224                         return 0;
 225                 }
 226         }
 227
 228         {
 229                 const bool index = CLIP_X_LT_W( p0 );
 230                 if ( index ^ CLIP_X_LT_W( p1 ) ) {
 231                         Vector4 clip( vector4_subtracted( p1, p0 ) );
 232
 233                         double scale = ( p0[0] - p0[3] ) / ( clip[3] - clip[0] );
 234
 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] );
 239
 240                         clipped[index] = clip;
 241                 }
 242                 else if ( index == 0 ) {
 243                         return 0;
 244                 }
 245         }
 246
 247         {
 248                 const bool index = CLIP_X_GT_W( p0 );
 249                 if ( index ^ CLIP_X_GT_W( p1 ) ) {
 250                         Vector4 clip( vector4_subtracted( p1, p0 ) );
 251
 252                         double scale = ( p0[0] + p0[3] ) / ( -clip[3] - clip[0] );
 253
 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] );
 258
 259                         clipped[index] = clip;
 260                 }
 261                 else if ( index == 0 ) {
 262                         return 0;
 263                 }
 264         }
 265
 266         {
 267                 const bool index = CLIP_Y_LT_W( p0 );
 268                 if ( index ^ CLIP_Y_LT_W( p1 ) ) {
 269                         Vector4 clip( vector4_subtracted( p1, p0 ) );
 270
 271                         double scale = ( p0[1] - p0[3] ) / ( clip[3] - clip[1] );
 272
 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] );
 277
 278                         clipped[index] = clip;
 279                 }
 280                 else if ( index == 0 ) {
 281                         return 0;
 282                 }
 283         }
 284
 285         {
 286                 const bool index = CLIP_Y_GT_W( p0 );
 287                 if ( index ^ CLIP_Y_GT_W( p1 ) ) {
 288                         Vector4 clip( vector4_subtracted( p1, p0 ) );
 289
 290                         double scale = ( p0[1] + p0[3] ) / ( -clip[3] - clip[1] );
 291
 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] );
 296
 297                         clipped[index] = clip;
 298                 }
 299                 else if ( index == 0 ) {
 300                         return 0;
 301                 }
 302         }
 303
 304         {
 305                 const bool index = CLIP_Z_LT_W( p0 );
 306                 if ( index ^ CLIP_Z_LT_W( p1 ) ) {
 307                         Vector4 clip( vector4_subtracted( p1, p0 ) );
 308
 309                         double scale = ( p0[2] - p0[3] ) / ( clip[3] - clip[2] );
 310
 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] );
 315
 316                         clipped[index] = clip;
 317                 }
 318                 else if ( index == 0 ) {
 319                         return 0;
 320                 }
 321         }
 322
 323         {
 324                 const bool index = CLIP_Z_GT_W( p0 );
 325                 if ( index ^ CLIP_Z_GT_W( p1 ) ) {
 326                         Vector4 clip( vector4_subtracted( p1, p0 ) );
 327
 328                         double scale = ( p0[2] + p0[3] ) / ( -clip[3] - clip[2] );
 329
 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] );
 334
 335                         clipped[index] = clip;
 336                 }
 337                 else if ( index == 0 ) {
 338                         return 0;
 339                 }
 340         }
 341
 342         return 2;
 343 }
 344
 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];
 352         clipped[0][3] = 1;
 353         clipped[1][0] = p1[0];
 354         clipped[1][1] = p1[1];
 355         clipped[1][2] = p1[2];
 356         clipped[1][3] = 1;
 357
 358         matrix4_transform_vector4( self, clipped[0] );
 359         matrix4_transform_vector4( self, clipped[1] );
 360
 361         return homogenous_clip_line( clipped );
 362 }
 363
 364
 365
 366
 367 struct Frustum
 368 {
 369         Plane3 right, left, bottom, top, back, front;
 370
 371         Frustum(){
 372         }
 373         Frustum( const Plane3& _right,
 374                          const Plane3& _left,
 375                          const Plane3& _bottom,
 376                          const Plane3& _top,
 377                          const Plane3& _back,
 378                          const Plane3& _front )
 379                 : right( _right ), left( _left ), bottom( _bottom ), top( _top ), back( _back ), front( _front ){
 380         }
 381 };
 382
 383 inline Frustum frustum_transformed( const Frustum& frustum, const Matrix4& transform ){
 384         return Frustum(
 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 )
 391                            );
 392 }
 393
 394 inline Frustum frustum_inverse_transformed( const Frustum& frustum, const Matrix4& transform ){
 395         return Frustum(
 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 )
 402                            );
 403 }
 404
 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] ) ) {
 410                 return true;
 411         }
 412         return false;
 413 }
 414
 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 ) );
 417 }
 418
 419 inline Frustum frustum_from_viewproj( const Matrix4& viewproj ){
 420         return Frustum
 421                    (
 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] ) )
 428                    );
 429 }
 430
 431 struct VolumeIntersection
 432 {
 433         enum Value
 434         {
 435                 OUTSIDE,
 436                 INSIDE,
 437                 PARTIAL
 438         };
 439 };
 440
 441 typedef EnumeratedValue<VolumeIntersection> VolumeIntersectionValue;
 442
 443 const VolumeIntersectionValue c_volumeOutside( VolumeIntersectionValue::OUTSIDE );
 444 const VolumeIntersectionValue c_volumeInside( VolumeIntersectionValue::INSIDE );
 445 const VolumeIntersectionValue c_volumePartial( VolumeIntersectionValue::PARTIAL );
 446
 447 inline VolumeIntersectionValue frustum_test_aabb( const Frustum& frustum, const AABB& aabb ){
 448         VolumeIntersectionValue result = c_volumeInside;
 449
 450         switch ( aabb_classify_plane( aabb, frustum.right ) )
 451         {
 452         case 2:
 453                 return c_volumeOutside;
 454         case 1:
 455                 result = c_volumePartial;
 456         }
 457
 458         switch ( aabb_classify_plane( aabb, frustum.left ) )
 459         {
 460         case 2:
 461                 return c_volumeOutside;
 462         case 1:
 463                 result = c_volumePartial;
 464         }
 465
 466         switch ( aabb_classify_plane( aabb, frustum.bottom ) )
 467         {
 468         case 2:
 469                 return c_volumeOutside;
 470         case 1:
 471                 result = c_volumePartial;
 472         }
 473
 474         switch ( aabb_classify_plane( aabb, frustum.top ) )
 475         {
 476         case 2:
 477                 return c_volumeOutside;
 478         case 1:
 479                 result = c_volumePartial;
 480         }
 481
 482         switch ( aabb_classify_plane( aabb, frustum.back ) )
 483         {
 484         case 2:
 485                 return c_volumeOutside;
 486         case 1:
 487                 result = c_volumePartial;
 488         }
 489
 490         switch ( aabb_classify_plane( aabb, frustum.front ) )
 491         {
 492         case 2:
 493                 return c_volumeOutside;
 494         case 1:
 495                 result = c_volumePartial;
 496         }
 497
 498         return result;
 499 }
 500
 501 inline double plane_distance_to_point( const Plane3& plane, const Vector3& point ){
 502         return vector3_dot( plane.normal(), point ) + plane.d;
 503 }
 504
 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() ) ) );
 509 }
 510
 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 ) );
 515 }
 516
 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 );
 520
 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;
 528         }
 529         return c_volumeInside;
 530 }
 531
 532 inline bool plane3_test_point( const Plane3& plane, const Vector3& point ){
 533         return vector3_dot( point, plane.normal() ) + plane.dist() <= 0;
 534 }
 535
 536 inline bool plane3_test_line( const Plane3& plane, const Segment& segment ){
 537         return segment_classify_plane( segment, plane ) == 2;
 538 }
 539
 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 );
 547 }
 548
 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 );
 556 }
 557
 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;
 563 }
 564
 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 ) );
 567 }
 568
 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;
 575 }
 576
 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 );
 580         }
 581         else
 582         {
 583                 return Vector4( matrix4_transformed_point( transform, vector4_to_vector3( viewer ) ), viewer[3] );
 584         }
 585 }
 586
 587 inline bool viewer_test_transformed_plane( const Vector4& viewer, const Plane3& plane, const Matrix4& localToWorld ){
 588 #if 0
 589         return viewer_test_plane( viewer_from_transformed_viewer( viewer, matrix4_affine_inverse( localToWorld ) ), plane );
 590 #else
 591         return viewer_test_plane( viewer, plane3_transformed( plane, localToWorld ) );
 592 #endif
 593 }
 594
 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];
 603         }
 604         return viewer;
 605 }
 606
 607 #endif