vmmlib  1.12.0
Templatized C++ vector and matrix math library
frustumCuller.hpp
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 
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 
56 
58  explicit FrustumCuller( const Matrix< 4, 4, T >& projModelView );
59 
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 
71 
73  Visibility test( const vec4& sphere ) const;
74 
76  Visibility test( const AABB< T >& aabb ) const;
77 
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 
116 template < typename T >
118 {
119  // See http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf pp.5
120  const vec4& row0 = projModelView.getRow( 0 );
121  const vec4& row1 = projModelView.getRow( 1 );
122  const vec4& row2 = projModelView.getRow( 2 );
123  const vec4& row3 = projModelView.getRow( 3 );
124 
125  _leftPlane = row3 + row0;
126  _rightPlane = row3 - row0;
127  _bottomPlane = row3 + row1;
128  _topPlane = row3 - row1;
129  _nearPlane = row3 + row2;
130  _farPlane = row3 - row2;
131 
132  _normalizePlane( _leftPlane );
133  _normalizePlane( _rightPlane );
134  _normalizePlane( _bottomPlane );
135  _normalizePlane( _topPlane );
136  _normalizePlane( _nearPlane );
137  _normalizePlane( _farPlane );
138 }
139 
140 template < typename T >
142  const vec3& c, const vec3& d,
143  const vec3& e, const vec3& f,
144  const vec3& g, const vec3& h )
145 {
146  // e_____f
147  // /____ /|
148  // | a b | |
149  // | c d |/h
150  // -----
151  // CCW winding
152  _leftPlane = compute_plane( c, a, e );
153  _rightPlane = compute_plane( f, b, d );
154  _bottomPlane = compute_plane( h, d, c );
155  _topPlane = compute_plane( a, b, f );
156  _nearPlane = compute_plane( b, a, c );
157  _farPlane = compute_plane( g, e, f );
158 }
159 
160 template < typename T >
161 inline void
163 {
164  const vec3& v3 = plane.template get_sub_vector< 3, 0 >();
165  const T len_i = 1.0 / v3.length();
166  plane.x() *= len_i;
167  plane.y() *= len_i;
168  plane.z() *= len_i;
169  plane.w() *= len_i;
170 }
171 
172 
173 template < typename T > Visibility
175 {
176  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  T distance = _leftPlane.x() * sphere.x() + _leftPlane.y() * sphere.y() +
186  _leftPlane.z() * sphere.z() + _leftPlane.w();
187  if( distance <= -sphere.w() )
188  return VISIBILITY_NONE;
189  if( distance < sphere.w() )
190  visibility = VISIBILITY_PARTIAL;
191 
192  distance = _rightPlane.x() * sphere.x() + _rightPlane.y() * sphere.y() +
193  _rightPlane.z() * sphere.z() + _rightPlane.w();
194  if( distance <= -sphere.w() )
195  return VISIBILITY_NONE;
196  if( distance < sphere.w() )
197  visibility = VISIBILITY_PARTIAL;
198 
199  distance = _bottomPlane.x() * sphere.x() + _bottomPlane.y() * sphere.y() +
200  _bottomPlane.z() * sphere.z() + _bottomPlane.w();
201  if( distance <= -sphere.w() )
202  return VISIBILITY_NONE;
203  if( distance < sphere.w() )
204  visibility = VISIBILITY_PARTIAL;
205 
206  distance = _topPlane.x() * sphere.x() + _topPlane.y() * sphere.y() +
207  _topPlane.z() * sphere.z() + _topPlane.w();
208  if( distance <= -sphere.w() )
209  return VISIBILITY_NONE;
210  if( distance < sphere.w() )
211  visibility = VISIBILITY_PARTIAL;
212 
213  distance = _nearPlane.x() * sphere.x() + _nearPlane.y() * sphere.y() +
214  _nearPlane.z() * sphere.z() + _nearPlane.w();
215 
216  if( distance <= -sphere.w() )
217  return VISIBILITY_NONE;
218  if( distance < sphere.w() )
219  visibility = VISIBILITY_PARTIAL;
220 
221  distance = _farPlane.x() * sphere.x() + _farPlane.y() * sphere.y() +
222  _farPlane.z() * sphere.z() + _farPlane.w();
223  if( distance <= -sphere.w() )
224  return VISIBILITY_NONE;
225  if( distance < sphere.w() )
226  visibility = VISIBILITY_PARTIAL;
227 
228  return visibility;
229 }
230 
231 template < typename T >
232 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  const T d = plane.dot( middle );
237  const T n = extent.x() * fabs( plane.x( )) +
238  extent.y() * fabs( plane.y( )) +
239  extent.z() * fabs( plane.z( ));
240 
241  if( d - n >= 0 )
242  return VISIBILITY_FULL;
243  if( d + n > 0 )
244  return VISIBILITY_PARTIAL;
245  return VISIBILITY_NONE;
246 }
247 
248 template < typename T >
249 Visibility FrustumCuller< T >::test( const AABB< T >& aabb ) const
250 {
251  Visibility result = VISIBILITY_FULL;
252  const vec3& middle = aabb.getCenter();
253  const vec3& extent = aabb.getSize() * 0.5f;
254  switch( _test( _leftPlane, middle, extent ))
255  {
256  case VISIBILITY_FULL: break;
257  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
258  case VISIBILITY_NONE: return VISIBILITY_NONE;
259  }
260 
261  switch( _test( _rightPlane, middle, extent ))
262  {
263  case VISIBILITY_FULL: break;
264  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
265  case VISIBILITY_NONE: return VISIBILITY_NONE;
266  }
267 
268  switch( _test( _bottomPlane, middle, extent ))
269  {
270  case VISIBILITY_FULL: break;
271  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
272  case VISIBILITY_NONE: return VISIBILITY_NONE;
273  }
274 
275  switch( _test( _topPlane, middle, extent ))
276  {
277  case VISIBILITY_FULL: break;
278  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
279  case VISIBILITY_NONE: return VISIBILITY_NONE;
280  }
281 
282  switch( _test( _nearPlane, middle, extent ))
283  {
284  case VISIBILITY_FULL: break;
285  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
286  case VISIBILITY_NONE: return VISIBILITY_NONE;
287  }
288 
289  switch( _test( _farPlane, middle, extent ))
290  {
291  case VISIBILITY_FULL: break;
292  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
293  case VISIBILITY_NONE: return VISIBILITY_NONE;
294  }
295 
296  return result;
297 }
298 
299 } // namespace vmml
300 
301 #endif // include protection
Helper class to perform OpenGL view frustum culling.
vector< 3, T > getSize() const
Definition: aabb.hpp:220
FrustumCuller()
Construct a new frustum culler.
const vec4 & getNearPlane() const
heavily inspired by boost::enable_if http://www.boost.org, file: boost/utility/enable_if.hpp, Copyright 2003 Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine
Definition: aabb.hpp:40
An axis-aligned bounding box.
Definition: aabb.hpp:50
Visibility test(const vec4 &sphere) const
~FrustumCuller()
Destruct this frustum culler.
vector< 3, T > getCenter() const
Definition: aabb.hpp:215
Matrix with R rows and C columns of element type T.
Definition: matrix.hpp:51