vmmlib  1.7.0
 All Classes Namespaces Functions Pages
frustum_culler.hpp
1 /*
2  * Copyright (c) 2006-2014, 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__FRUSTUM_CULLER__HPP__
34 #define __VMML__FRUSTUM_CULLER__HPP__
35 
36 #include <vmmlib/vector.hpp>
37 #include <vmmlib/matrix.hpp>
38 #include <vmmlib/visibility.hpp>
39 
40 // - declaration -
41 
42 namespace vmml
43 {
44 
46 template< class T >
47 class frustum_culler
48 {
49 public:
50  typedef vector< 2, T > vec2;
51  typedef vector< 3, T > vec3;
52  typedef vector< 4, T > vec4;
53 
54  // contructors
55  frustum_culler() {}
56  ~frustum_culler(){}
57 
59  void setup( const matrix< 4, 4, T >& proj_modelview );
60 
65  void setup( const vec3& nlt, const vec3& nrt,
66  const vec3& nlb, const vec3& nrb,
67  const vec3& flt, const vec3& frt,
68  const vec3& flb, const vec3& frb );
69 
70  Visibility test_sphere( const vec4& sphere ) const;
71  Visibility test_aabb( const vec2& x, const vec2& y, const vec2& z ) const;
72 
73  friend std::ostream& operator << (std::ostream& os, const frustum_culler& f)
74  {
75  return os << "Frustum cull planes: " << std::endl
76  << " left " << f._left_plane << std::endl
77  << " right " << f._right_plane << std::endl
78  << " top " << f._top_plane << std::endl
79  << " bottom " << f._bottom_plane << std::endl
80  << " near " << f._near_plane << std::endl
81  << " far " << f._far_plane << std::endl;
82  }
83 
84 private:
85  inline void _normalize_plane( vec4& plane ) const;
86  inline Visibility _test_aabb( const vec4& plane, const vec3& middle,
87  const vec3& size_2 ) const;
88 
89  vec4 _left_plane;
90  vec4 _right_plane;
91  vec4 _bottom_plane;
92  vec4 _top_plane;
93  vec4 _near_plane;
94  vec4 _far_plane;
95 
96 }; // class frustum_culler
97 
98 
99 #ifndef VMMLIB_NO_TYPEDEFS
100 
101 typedef frustum_culler< float > frustum_cullerf;
102 typedef frustum_culler< double > frustum_cullerd;
103 
104 #endif
105 
106 } // namespace vmml
107 
108 // - implementation - //
109 
110 
111 namespace vmml
112 {
113 
118 template < class T >
119 void frustum_culler< T >::setup( const matrix< 4, 4, T >& proj_modelview )
120 {
121  // See http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf pp.5
122 
123  const vec4& row0 = proj_modelview.get_row( 0 );
124  const vec4& row1 = proj_modelview.get_row( 1 );
125  const vec4& row2 = proj_modelview.get_row( 2 );
126  const vec4& row3 = proj_modelview.get_row( 3 );
127 
128  _left_plane = row3 + row0;
129  _right_plane = row3 - row0;
130  _bottom_plane = row3 + row1;
131  _top_plane = row3 - row1;
132  _near_plane = row3 + row2;
133  _far_plane = row3 - row2;
134 
135  _normalize_plane( _left_plane );
136  _normalize_plane( _right_plane );
137  _normalize_plane( _bottom_plane );
138  _normalize_plane( _top_plane );
139  _normalize_plane( _near_plane );
140  _normalize_plane( _far_plane );
141 }
142 
143 template < class T >
144 void frustum_culler< T >::setup( const vec3& a, const vec3& b,
145  const vec3& c, const vec3& d,
146  const vec3& e, const vec3& f,
147  const vec3& g, const vec3& h )
148 {
149  // e_____f
150  // /____ /|
151  // | a b | |
152  // | c d |/h
153  // -----
154  // CCW winding
155  _left_plane = compute_plane( c, a, e );
156  _right_plane = compute_plane( f, b, d );
157  _bottom_plane = compute_plane( h, d, c );
158  _top_plane = compute_plane( a, b, f );
159  _near_plane = compute_plane( b, a, c );
160  _far_plane = compute_plane( g, e, f );
161 }
162 
163 template < class T >
164 inline void
165 frustum_culler< T >::_normalize_plane( vector< 4, T >& plane ) const
166 {
167  const vec3& v3 = plane.template get_sub_vector< 3 >();
168  const T len_i = 1.0 / v3.length();
169  plane.x() *= len_i;
170  plane.y() *= len_i;
171  plane.z() *= len_i;
172  plane.w() *= len_i;
173 }
174 
175 
176 template < class T > Visibility
177 frustum_culler< T >::test_sphere( const vector< 4, T >& sphere ) const
178 {
179  Visibility visibility = VISIBILITY_FULL;
180 
181  // see http://www.flipcode.com/articles/article_frustumculling.shtml
182  // distance = plane.normal . sphere.center + plane.distance
183  // Test all planes:
184  // - if sphere behind plane: not visible
185  // - if sphere intersects one plane: partially visible
186  // - else: fully visible
187 
188  T distance = _left_plane.x() * sphere.x() + _left_plane.y() * sphere.y() +
189  _left_plane.z() * sphere.z() + _left_plane.w();
190  if( distance <= -sphere.w() )
191  return VISIBILITY_NONE;
192  if( distance < sphere.w() )
193  visibility = VISIBILITY_PARTIAL;
194 
195  distance = _right_plane.x() * sphere.x() + _right_plane.y() * sphere.y() +
196  _right_plane.z() * sphere.z() + _right_plane.w();
197  if( distance <= -sphere.w() )
198  return VISIBILITY_NONE;
199  if( distance < sphere.w() )
200  visibility = VISIBILITY_PARTIAL;
201 
202  distance = _bottom_plane.x() * sphere.x() + _bottom_plane.y() * sphere.y() +
203  _bottom_plane.z() * sphere.z() + _bottom_plane.w();
204  if( distance <= -sphere.w() )
205  return VISIBILITY_NONE;
206  if( distance < sphere.w() )
207  visibility = VISIBILITY_PARTIAL;
208 
209  distance = _top_plane.x() * sphere.x() + _top_plane.y() * sphere.y() +
210  _top_plane.z() * sphere.z() + _top_plane.w();
211  if( distance <= -sphere.w() )
212  return VISIBILITY_NONE;
213  if( distance < sphere.w() )
214  visibility = VISIBILITY_PARTIAL;
215 
216  distance = _near_plane.x() * sphere.x() + _near_plane.y() * sphere.y() +
217  _near_plane.z() * sphere.z() + _near_plane.w();
218 
219  if( distance <= -sphere.w() )
220  return VISIBILITY_NONE;
221  if( distance < sphere.w() )
222  visibility = VISIBILITY_PARTIAL;
223 
224  distance = _far_plane.x() * sphere.x() + _far_plane.y() * sphere.y() +
225  _far_plane.z() * sphere.z() + _far_plane.w();
226  if( distance <= -sphere.w() )
227  return VISIBILITY_NONE;
228  if( distance < sphere.w() )
229  visibility = VISIBILITY_PARTIAL;
230 
231  return visibility;
232 }
233 
234 template < class T >
235 Visibility frustum_culler< T >::_test_aabb( const vec4& plane,
236  const vec3& middle,
237  const vec3& extent ) const
238 {
239  // http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html
240  const T d = plane.dot( middle );
241  const T n = extent.x() * fabs( plane.x( )) +
242  extent.y() * fabs( plane.y( )) +
243  extent.z() * fabs( plane.z( ));
244 
245  if( d - n >= 0 )
246  return VISIBILITY_FULL;
247  if( d + n > 0 )
248  return VISIBILITY_PARTIAL;
249  return VISIBILITY_NONE;
250 }
251 
252 template < class T >
253 Visibility frustum_culler< T >::test_aabb( const vec2& x, const vec2& y,
254  const vec2& z ) const
255 {
256  Visibility result = VISIBILITY_FULL;
257  const vec3& middle = vec3( x[0] + x[1], y[0] + y[1], z[0] + z[1] ) * .5;
258  const vec3& extent = vec3( fabs(x[1] - x[0]), fabs(y[1] - y[0]),
259  fabs(z[1] - z[0]) ) * .5;
260  switch( _test_aabb( _left_plane, middle, extent ))
261  {
262  case VISIBILITY_FULL: break;
263  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
264  case VISIBILITY_NONE: return VISIBILITY_NONE;
265  }
266 
267  switch( _test_aabb( _right_plane, middle, extent ))
268  {
269  case VISIBILITY_FULL: break;
270  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
271  case VISIBILITY_NONE: return VISIBILITY_NONE;
272  }
273 
274  switch( _test_aabb( _bottom_plane, middle, extent ))
275  {
276  case VISIBILITY_FULL: break;
277  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
278  case VISIBILITY_NONE: return VISIBILITY_NONE;
279  }
280 
281  switch( _test_aabb( _top_plane, middle, extent ))
282  {
283  case VISIBILITY_FULL: break;
284  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
285  case VISIBILITY_NONE: return VISIBILITY_NONE;
286  }
287 
288  switch( _test_aabb( _near_plane, middle, extent ))
289  {
290  case VISIBILITY_FULL: break;
291  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
292  case VISIBILITY_NONE: return VISIBILITY_NONE;
293  }
294 
295  switch( _test_aabb( _far_plane, middle, extent ))
296  {
297  case VISIBILITY_FULL: break;
298  case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
299  case VISIBILITY_NONE: return VISIBILITY_NONE;
300  }
301 
302  return result;
303 }
304 
305 } // namespace vmml
306 
307 #endif // include protection
vmml::frustum_culler
Helper class for OpenGL view frustum culling.
Definition: frustum_culler.hpp:47
vmml::frustum_culler::setup
void setup(const matrix< 4, 4, T > &proj_modelview)
Set up the culling state using a 4x4 projection*modelView matrix.
Definition: frustum_culler.hpp:119