frustumCuller.hpp

/*
 * Copyright (c) 2006-2016, Visualization and Multimedia Lab,
 *                          University of Zurich <http://vmml.ifi.uzh.ch>,
 *                          Eyescale Software GmbH,
 *                          Blue Brain Project, EPFL
 *
 * This file is part of VMMLib <https://github.com/VMML/vmmlib/>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.  Redistributions in binary
 * form must reproduce the above copyright notice, this list of conditions and
 * the following disclaimer in the documentation and/or other materials provided
 * with the distribution.  Neither the name of the Visualization and Multimedia
 * Lab, University of Zurich nor the names of its contributors may be used to
 * endorse or promote products derived from this software without specific prior
 * written permission.
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef __VMML__FRUSTUMCULLER__HPP__
#define __VMML__FRUSTUMCULLER__HPP__

#include <vmmlib/aabb.hpp> // inline parameter
#include <vmmlib/matrix.hpp> // inline parameter
#include <vmmlib/vector.hpp> // member
#include <vmmlib/visibility.hpp> // return value

// - declaration -

namespace vmml
{

template< typename T > class FrustumCuller
{
public:
    typedef vector< 2, T > vec2;
    typedef vector< 3, T > vec3;
    typedef vector< 4, T > vec4;

    FrustumCuller() {}

    explicit FrustumCuller( const Matrix< 4, 4, T >& projModelView );

    FrustumCuller( const vec3& nlt, const vec3& nrt,
                   const vec3& nlb, const vec3& nrb,
                   const vec3& flt, const vec3& frt,
                   const vec3& flb, const vec3& frb );

    ~FrustumCuller(){}

    Visibility test( const vec4& sphere ) const;

    Visibility test( const AABB< T >& aabb ) const;

    const vec4& getNearPlane() const { return _nearPlane; }

    friend std::ostream& operator << (std::ostream& os, const FrustumCuller& f)
    {
        return os << "Frustum cull planes: " << std::endl
                  << "    left   " << f._leftPlane << std::endl
                  << "    right  " << f._rightPlane << std::endl
                  << "    top    " << f._topPlane << std::endl
                  << "    bottom " << f._bottomPlane << std::endl
                  << "    near   " << f._nearPlane << std::endl
                  << "    far    " << f._farPlane << std::endl;
    }

private:
    inline void _normalizePlane( vec4& plane ) const;
    inline Visibility _test( const vec4& plane, const vec3& middle,
                             const vec3& size_2 ) const;
    vec4    _leftPlane;
    vec4    _rightPlane;
    vec4    _bottomPlane;
    vec4    _topPlane;
    vec4    _nearPlane;
    vec4    _farPlane;

}; // class FrustumCuller
} // namespace vmml

// - implementation - //


namespace vmml
{

template < typename T >
FrustumCuller< T >::FrustumCuller( const Matrix< 4, 4, T >& projModelView )
{
    // See http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf pp.5
    const vec4& row0 = projModelView.getRow( 0 );
    const vec4& row1 = projModelView.getRow( 1 );
    const vec4& row2 = projModelView.getRow( 2 );
    const vec4& row3 = projModelView.getRow( 3 );

    _leftPlane   = row3 + row0;
    _rightPlane  = row3 - row0;
    _bottomPlane = row3 + row1;
    _topPlane    = row3 - row1;
    _nearPlane   = row3 + row2;
    _farPlane    = row3 - row2;

    _normalizePlane( _leftPlane );
    _normalizePlane( _rightPlane );
    _normalizePlane( _bottomPlane );
    _normalizePlane( _topPlane );
    _normalizePlane( _nearPlane );
    _normalizePlane( _farPlane );
}

template < typename T >
FrustumCuller< T >::FrustumCuller( const vec3& a, const vec3& b,
                                   const vec3& c, const vec3& d,
                                   const vec3& e, const vec3& f,
                                   const vec3& g, const vec3& h )
{
    //   e_____f
    //  /____ /|
    // | a b | |
    // | c d |/h
    //  -----
    // CCW winding
    _leftPlane   = compute_plane( c, a, e );
    _rightPlane  = compute_plane( f, b, d );
    _bottomPlane = compute_plane( h, d, c );
    _topPlane    = compute_plane( a, b, f );
    _nearPlane   = compute_plane( b, a, c );
    _farPlane    = compute_plane( g, e, f );
}

template < typename T >
inline void
FrustumCuller< T >::_normalizePlane( vector< 4, T >& plane ) const
{
    const vec3& v3 = plane.template get_sub_vector< 3, 0 >();
    const T len_i = 1.0 / v3.length();
    plane.x() *= len_i;
    plane.y() *= len_i;
    plane.z() *= len_i;
    plane.w() *= len_i;
}


template < typename T > Visibility
FrustumCuller< T >::test( const vector< 4, T >& sphere ) const
{
    Visibility visibility = VISIBILITY_FULL;

    // see http://www.flipcode.com/articles/article_frustumculling.shtml
    // distance = plane.normal . sphere.center + plane.distance
    // Test all planes:
    // - if sphere behind plane: not visible
    // - if sphere intersects one plane: partially visible
    // - else: fully visible

    T distance = _leftPlane.x() * sphere.x() + _leftPlane.y() * sphere.y() +
                 _leftPlane.z() * sphere.z() + _leftPlane.w();
    if( distance <= -sphere.w() )
        return VISIBILITY_NONE;
    if( distance < sphere.w() )
        visibility = VISIBILITY_PARTIAL;

    distance = _rightPlane.x() * sphere.x() + _rightPlane.y() * sphere.y() +
               _rightPlane.z() * sphere.z() + _rightPlane.w();
    if( distance <= -sphere.w() )
        return VISIBILITY_NONE;
    if( distance < sphere.w() )
        visibility = VISIBILITY_PARTIAL;

    distance = _bottomPlane.x() * sphere.x() + _bottomPlane.y() * sphere.y() +
               _bottomPlane.z() * sphere.z() + _bottomPlane.w();
    if( distance <= -sphere.w() )
        return VISIBILITY_NONE;
    if( distance < sphere.w() )
        visibility = VISIBILITY_PARTIAL;

    distance = _topPlane.x() * sphere.x() + _topPlane.y() * sphere.y() +
               _topPlane.z() * sphere.z() + _topPlane.w();
    if( distance <= -sphere.w() )
        return VISIBILITY_NONE;
    if( distance < sphere.w() )
        visibility = VISIBILITY_PARTIAL;

    distance = _nearPlane.x() * sphere.x() + _nearPlane.y() * sphere.y() +
               _nearPlane.z() * sphere.z() + _nearPlane.w();

    if( distance <= -sphere.w() )
        return VISIBILITY_NONE;
    if( distance < sphere.w() )
        visibility = VISIBILITY_PARTIAL;

    distance = _farPlane.x() * sphere.x() + _farPlane.y() * sphere.y() +
               _farPlane.z() * sphere.z() + _farPlane.w();
    if( distance <= -sphere.w() )
        return VISIBILITY_NONE;
    if( distance < sphere.w() )
        visibility = VISIBILITY_PARTIAL;

    return visibility;
}

template < typename T >
Visibility FrustumCuller< T >::_test( const vec4& plane, const vec3& middle,
                                      const vec3& extent ) const
{
    // http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html
    const T d = plane.dot( middle );
    const T n = extent.x() * fabs( plane.x( )) +
                extent.y() * fabs( plane.y( )) +
                extent.z() * fabs( plane.z( ));

    if( d - n >= 0 )
        return VISIBILITY_FULL;
    if( d + n > 0 )
        return VISIBILITY_PARTIAL;
    return VISIBILITY_NONE;
}

template < typename T >
Visibility FrustumCuller< T >::test( const AABB< T >& aabb ) const
{
    Visibility result = VISIBILITY_FULL;
    const vec3& middle = aabb.getCenter();
    const vec3& extent = aabb.getSize() * 0.5f;
    switch( _test( _leftPlane, middle, extent ))
    {
        case VISIBILITY_FULL: break;
        case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
        case VISIBILITY_NONE: return VISIBILITY_NONE;
    }

    switch( _test( _rightPlane, middle, extent ))
    {
        case VISIBILITY_FULL: break;
        case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
        case VISIBILITY_NONE: return VISIBILITY_NONE;
    }

    switch( _test( _bottomPlane, middle, extent ))
    {
        case VISIBILITY_FULL: break;
        case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
        case VISIBILITY_NONE: return VISIBILITY_NONE;
    }

    switch( _test( _topPlane, middle, extent ))
    {
        case VISIBILITY_FULL: break;
        case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
        case VISIBILITY_NONE: return VISIBILITY_NONE;
    }

    switch( _test( _nearPlane, middle, extent ))
    {
        case VISIBILITY_FULL: break;
        case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
        case VISIBILITY_NONE: return VISIBILITY_NONE;
    }

    switch( _test( _farPlane, middle, extent ))
    {
        case VISIBILITY_FULL: break;
        case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
        case VISIBILITY_NONE: return VISIBILITY_NONE;
    }

    return result;
}

} // namespace vmml

#endif // include protection