LCOV - code coverage report
Current view: top level - vmmlib - frustumCuller.hpp (source / functions) Hit Total Coverage
Test: vmmlib Lines: 102 114 89.5 %
Date: 2017-05-16 00:10:45 Functions: 7 7 100.0 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (c) 2006-2016, Visualization and Multimedia Lab,
       3             :  *                          University of Zurich <http://vmml.ifi.uzh.ch>,
       4             :  *                          Eyescale Software GmbH,
       5             :  *                          Blue Brain Project, EPFL
       6             :  *
       7             :  * This file is part of VMMLib <https://github.com/VMML/vmmlib/>
       8             :  *
       9             :  * Redistribution and use in source and binary forms, with or without
      10             :  * modification, are permitted provided that the following conditions are met:
      11             :  *
      12             :  * Redistributions of source code must retain the above copyright notice, this
      13             :  * list of conditions and the following disclaimer.  Redistributions in binary
      14             :  * form must reproduce the above copyright notice, this list of conditions and
      15             :  * the following disclaimer in the documentation and/or other materials provided
      16             :  * with the distribution.  Neither the name of the Visualization and Multimedia
      17             :  * Lab, University of Zurich nor the names of its contributors may be used to
      18             :  * endorse or promote products derived from this software without specific prior
      19             :  * written permission.
      20             :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
      21             :  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      22             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      23             :  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
      24             :  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
      25             :  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
      26             :  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
      27             :  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
      28             :  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
      29             :  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
      30             :  * POSSIBILITY OF SUCH DAMAGE.
      31             :  */
      32             : 
      33             : #ifndef __VMML__FRUSTUMCULLER__HPP__
      34             : #define __VMML__FRUSTUMCULLER__HPP__
      35             : 
      36             : #include <vmmlib/aabb.hpp> // inline parameter
      37             : #include <vmmlib/matrix.hpp> // inline parameter
      38             : #include <vmmlib/vector.hpp> // member
      39             : #include <vmmlib/visibility.hpp> // return value
      40             : 
      41             : // - declaration -
      42             : 
      43             : namespace vmml
      44             : {
      45             : 
      46             : /** Helper class to perform OpenGL view frustum culling. */
      47             : template< typename T > class FrustumCuller
      48             : {
      49             : public:
      50             :     typedef vector< 2, T > vec2;
      51             :     typedef vector< 3, T > vec3;
      52             :     typedef vector< 4, T > vec4;
      53             : 
      54             :     /** Construct a new frustum culler */
      55             :     FrustumCuller() {}
      56             : 
      57             :     /** Construct a frustum culler using a 4x4 projection*model*view matrix. */
      58             :     explicit FrustumCuller( const Matrix< 4, 4, T >& projModelView );
      59             : 
      60             :     /**
      61             :      * Construct a frustum culler using the eight frustum corner points.
      62             :      * Corner naming is n(ear)|f(ar), l(eft)|r(ight), t(op)|b(ottom)
      63             :      */
      64             :     FrustumCuller( const vec3& nlt, const vec3& nrt,
      65             :                    const vec3& nlb, const vec3& nrb,
      66             :                    const vec3& flt, const vec3& frt,
      67             :                    const vec3& flb, const vec3& frb );
      68             : 
      69             :     /** Destruct this frustum culler. */
      70           2 :     ~FrustumCuller(){}
      71             : 
      72             :     /** @return the visibility of the given sphere */
      73             :     Visibility test( const vec4& sphere ) const;
      74             : 
      75             :     /** @return the visibility of the axis-aligned bounding box */
      76             :     Visibility test( const AABB< T >& aabb ) const;
      77             : 
      78             :     /** @return the plane equation of the current near plane. */
      79             :     const vec4& getNearPlane() const { return _nearPlane; }
      80             : 
      81             :     friend std::ostream& operator << (std::ostream& os, const FrustumCuller& f)
      82             :     {
      83             :         return os << "Frustum cull planes: " << std::endl
      84             :                   << "    left   " << f._leftPlane << std::endl
      85             :                   << "    right  " << f._rightPlane << std::endl
      86             :                   << "    top    " << f._topPlane << std::endl
      87             :                   << "    bottom " << f._bottomPlane << std::endl
      88             :                   << "    near   " << f._nearPlane << std::endl
      89             :                   << "    far    " << f._farPlane << std::endl;
      90             :     }
      91             : 
      92             : private:
      93             :     inline void _normalizePlane( vec4& plane ) const;
      94             :     inline Visibility _test( const vec4& plane, const vec3& middle,
      95             :                              const vec3& size_2 ) const;
      96             :     vec4    _leftPlane;
      97             :     vec4    _rightPlane;
      98             :     vec4    _bottomPlane;
      99             :     vec4    _topPlane;
     100             :     vec4    _nearPlane;
     101             :     vec4    _farPlane;
     102             : 
     103             : }; // class FrustumCuller
     104             : } // namespace vmml
     105             : 
     106             : // - implementation - //
     107             : 
     108             : 
     109             : namespace vmml
     110             : {
     111             : 
     112             : /**
     113             :  * Setup the culler by extracting the frustum planes from the projection
     114             :  * matrix. The projection matrix should contain the viewing transformation.
     115             :  */
     116             : template < typename T >
     117           1 : FrustumCuller< T >::FrustumCuller( const Matrix< 4, 4, T >& projModelView )
     118             : {
     119             :     // See http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf pp.5
     120           1 :     const vec4& row0 = projModelView.getRow( 0 );
     121           1 :     const vec4& row1 = projModelView.getRow( 1 );
     122           1 :     const vec4& row2 = projModelView.getRow( 2 );
     123           1 :     const vec4& row3 = projModelView.getRow( 3 );
     124             : 
     125           1 :     _leftPlane   = row3 + row0;
     126           1 :     _rightPlane  = row3 - row0;
     127           1 :     _bottomPlane = row3 + row1;
     128           1 :     _topPlane    = row3 - row1;
     129           1 :     _nearPlane   = row3 + row2;
     130           1 :     _farPlane    = row3 - row2;
     131             : 
     132           1 :     _normalizePlane( _leftPlane );
     133           1 :     _normalizePlane( _rightPlane );
     134           1 :     _normalizePlane( _bottomPlane );
     135           1 :     _normalizePlane( _topPlane );
     136           1 :     _normalizePlane( _nearPlane );
     137           1 :     _normalizePlane( _farPlane );
     138           1 : }
     139             : 
     140             : template < typename T >
     141           1 : FrustumCuller< T >::FrustumCuller( const vec3& a, const vec3& b,
     142             :                                    const vec3& c, const vec3& d,
     143             :                                    const vec3& e, const vec3& f,
     144           1 :                                    const vec3& g, const vec3& h )
     145             : {
     146             :     //   e_____f
     147             :     //  /____ /|
     148             :     // | a b | |
     149             :     // | c d |/h
     150             :     //  -----
     151             :     // CCW winding
     152           1 :     _leftPlane   = compute_plane( c, a, e );
     153           1 :     _rightPlane  = compute_plane( f, b, d );
     154           1 :     _bottomPlane = compute_plane( h, d, c );
     155           1 :     _topPlane    = compute_plane( a, b, f );
     156           1 :     _nearPlane   = compute_plane( b, a, c );
     157           1 :     _farPlane    = compute_plane( g, e, f );
     158           1 : }
     159             : 
     160             : template < typename T >
     161             : inline void
     162           6 : FrustumCuller< T >::_normalizePlane( vector< 4, T >& plane ) const
     163             : {
     164           6 :     const vec3& v3 = plane.template get_sub_vector< 3, 0 >();
     165           6 :     const T len_i = 1.0 / v3.length();
     166           6 :     plane.x() *= len_i;
     167           6 :     plane.y() *= len_i;
     168           6 :     plane.z() *= len_i;
     169           6 :     plane.w() *= len_i;
     170           6 : }
     171             : 
     172             : 
     173             : template < typename T > Visibility
     174           6 : FrustumCuller< T >::test( const vector< 4, T >& sphere ) const
     175             : {
     176           6 :     Visibility visibility = VISIBILITY_FULL;
     177             : 
     178             :     // see http://www.flipcode.com/articles/article_frustumculling.shtml
     179             :     // distance = plane.normal . sphere.center + plane.distance
     180             :     // Test all planes:
     181             :     // - if sphere behind plane: not visible
     182             :     // - if sphere intersects one plane: partially visible
     183             :     // - else: fully visible
     184             : 
     185          12 :     T distance = _leftPlane.x() * sphere.x() + _leftPlane.y() * sphere.y() +
     186          12 :                  _leftPlane.z() * sphere.z() + _leftPlane.w();
     187           6 :     if( distance <= -sphere.w() )
     188           0 :         return VISIBILITY_NONE;
     189           6 :     if( distance < sphere.w() )
     190           4 :         visibility = VISIBILITY_PARTIAL;
     191             : 
     192          18 :     distance = _rightPlane.x() * sphere.x() + _rightPlane.y() * sphere.y() +
     193          12 :                _rightPlane.z() * sphere.z() + _rightPlane.w();
     194           6 :     if( distance <= -sphere.w() )
     195           0 :         return VISIBILITY_NONE;
     196           6 :     if( distance < sphere.w() )
     197           4 :         visibility = VISIBILITY_PARTIAL;
     198             : 
     199          18 :     distance = _bottomPlane.x() * sphere.x() + _bottomPlane.y() * sphere.y() +
     200          12 :                _bottomPlane.z() * sphere.z() + _bottomPlane.w();
     201           6 :     if( distance <= -sphere.w() )
     202           0 :         return VISIBILITY_NONE;
     203           6 :     if( distance < sphere.w() )
     204           4 :         visibility = VISIBILITY_PARTIAL;
     205             : 
     206          18 :     distance = _topPlane.x() * sphere.x() + _topPlane.y() * sphere.y() +
     207          12 :                _topPlane.z() * sphere.z() + _topPlane.w();
     208           6 :     if( distance <= -sphere.w() )
     209           0 :         return VISIBILITY_NONE;
     210           6 :     if( distance < sphere.w() )
     211           4 :         visibility = VISIBILITY_PARTIAL;
     212             : 
     213          18 :     distance = _nearPlane.x() * sphere.x() + _nearPlane.y() * sphere.y() +
     214          12 :                _nearPlane.z() * sphere.z() + _nearPlane.w();
     215             : 
     216           6 :     if( distance <= -sphere.w() )
     217           2 :         return VISIBILITY_NONE;
     218           4 :     if( distance < sphere.w() )
     219           2 :         visibility = VISIBILITY_PARTIAL;
     220             : 
     221          12 :     distance = _farPlane.x() * sphere.x() + _farPlane.y() * sphere.y() +
     222           8 :                _farPlane.z() * sphere.z() + _farPlane.w();
     223           4 :     if( distance <= -sphere.w() )
     224           0 :         return VISIBILITY_NONE;
     225           4 :     if( distance < sphere.w() )
     226           0 :         visibility = VISIBILITY_PARTIAL;
     227             : 
     228           4 :     return visibility;
     229             : }
     230             : 
     231             : template < typename T >
     232          34 : Visibility FrustumCuller< T >::_test( const vec4& plane, const vec3& middle,
     233             :                                       const vec3& extent ) const
     234             : {
     235             :     // http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html
     236          34 :     const T d = plane.dot( middle );
     237          68 :     const T n = extent.x() * fabs( plane.x( )) +
     238          68 :                 extent.y() * fabs( plane.y( )) +
     239          68 :                 extent.z() * fabs( plane.z( ));
     240             : 
     241          34 :     if( d - n >= 0 )
     242          14 :         return VISIBILITY_FULL;
     243          20 :     if( d + n > 0 )
     244          18 :         return VISIBILITY_PARTIAL;
     245           2 :     return VISIBILITY_NONE;
     246             : }
     247             : 
     248             : template < typename T >
     249           6 : Visibility FrustumCuller< T >::test( const AABB< T >& aabb ) const
     250             : {
     251           6 :     Visibility result = VISIBILITY_FULL;
     252           6 :     const vec3& middle = aabb.getCenter();
     253           6 :     const vec3& extent = aabb.getSize() * 0.5f;
     254           6 :     switch( _test( _leftPlane, middle, extent ))
     255             :     {
     256           2 :         case VISIBILITY_FULL: break;
     257           4 :         case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
     258           0 :         case VISIBILITY_NONE: return VISIBILITY_NONE;
     259             :     }
     260             : 
     261           6 :     switch( _test( _rightPlane, middle, extent ))
     262             :     {
     263           2 :         case VISIBILITY_FULL: break;
     264           4 :         case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
     265           0 :         case VISIBILITY_NONE: return VISIBILITY_NONE;
     266             :     }
     267             : 
     268           6 :     switch( _test( _bottomPlane, middle, extent ))
     269             :     {
     270           2 :         case VISIBILITY_FULL: break;
     271           4 :         case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
     272           0 :         case VISIBILITY_NONE: return VISIBILITY_NONE;
     273             :     }
     274             : 
     275           6 :     switch( _test( _topPlane, middle, extent ))
     276             :     {
     277           2 :         case VISIBILITY_FULL: break;
     278           4 :         case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
     279           0 :         case VISIBILITY_NONE: return VISIBILITY_NONE;
     280             :     }
     281             : 
     282           6 :     switch( _test( _nearPlane, middle, extent ))
     283             :     {
     284           2 :         case VISIBILITY_FULL: break;
     285           2 :         case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
     286           2 :         case VISIBILITY_NONE: return VISIBILITY_NONE;
     287             :     }
     288             : 
     289           4 :     switch( _test( _farPlane, middle, extent ))
     290             :     {
     291           4 :         case VISIBILITY_FULL: break;
     292           0 :         case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
     293           0 :         case VISIBILITY_NONE: return VISIBILITY_NONE;
     294             :     }
     295             : 
     296           4 :     return result;
     297             : }
     298             : 
     299             : } // namespace vmml
     300             : 
     301             : #endif // include protection

Generated by: LCOV version 1.11