Line data Source code
1 : /*
2 : * Copyright (c) 2006-2015, 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 :
45 : /** Helper class for OpenGL view frustum culling. */
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 1 : frustum_culler() {}
56 1 : ~frustum_culler(){}
57 :
58 : /** Set up the culling state using a 4x4 projection*modelView matrix. */
59 : void setup( const matrix< 4, 4, T >& proj_modelview );
60 :
61 : /**
62 : * Set up the culling state using the eight frustum corner points.
63 : * Corner naming is n(ear)|f(ar), l(eft)|r(ight), t(op)|b(ottom)
64 : */
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 :
114 : /**
115 : * Setup the culler by extracting the frustum planes from the projection
116 : * matrix. The projection matrix should contain the viewing transformation.
117 : */
118 : template < class T >
119 1 : 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 1 : const vec4& row0 = proj_modelview.get_row( 0 );
124 1 : const vec4& row1 = proj_modelview.get_row( 1 );
125 1 : const vec4& row2 = proj_modelview.get_row( 2 );
126 1 : const vec4& row3 = proj_modelview.get_row( 3 );
127 :
128 1 : _left_plane = row3 + row0;
129 1 : _right_plane = row3 - row0;
130 1 : _bottom_plane = row3 + row1;
131 1 : _top_plane = row3 - row1;
132 1 : _near_plane = row3 + row2;
133 1 : _far_plane = row3 - row2;
134 :
135 1 : _normalize_plane( _left_plane );
136 1 : _normalize_plane( _right_plane );
137 1 : _normalize_plane( _bottom_plane );
138 1 : _normalize_plane( _top_plane );
139 1 : _normalize_plane( _near_plane );
140 1 : _normalize_plane( _far_plane );
141 1 : }
142 :
143 : template < class T >
144 1 : 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 1 : _left_plane = compute_plane( c, a, e );
156 1 : _right_plane = compute_plane( f, b, d );
157 1 : _bottom_plane = compute_plane( h, d, c );
158 1 : _top_plane = compute_plane( a, b, f );
159 1 : _near_plane = compute_plane( b, a, c );
160 1 : _far_plane = compute_plane( g, e, f );
161 1 : }
162 :
163 : template < class T >
164 : inline void
165 6 : frustum_culler< T >::_normalize_plane( vector< 4, T >& plane ) const
166 : {
167 6 : const vec3& v3 = plane.template get_sub_vector< 3 >();
168 6 : const T len_i = 1.0 / v3.length();
169 6 : plane.x() *= len_i;
170 6 : plane.y() *= len_i;
171 6 : plane.z() *= len_i;
172 6 : plane.w() *= len_i;
173 6 : }
174 :
175 :
176 : template < class T > Visibility
177 6 : frustum_culler< T >::test_sphere( const vector< 4, T >& sphere ) const
178 : {
179 6 : 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 24 : T distance = _left_plane.x() * sphere.x() + _left_plane.y() * sphere.y() +
189 24 : _left_plane.z() * sphere.z() + _left_plane.w();
190 6 : if( distance <= -sphere.w() )
191 0 : return VISIBILITY_NONE;
192 6 : if( distance < sphere.w() )
193 4 : visibility = VISIBILITY_PARTIAL;
194 :
195 24 : distance = _right_plane.x() * sphere.x() + _right_plane.y() * sphere.y() +
196 18 : _right_plane.z() * sphere.z() + _right_plane.w();
197 6 : if( distance <= -sphere.w() )
198 0 : return VISIBILITY_NONE;
199 6 : if( distance < sphere.w() )
200 4 : visibility = VISIBILITY_PARTIAL;
201 :
202 24 : distance = _bottom_plane.x() * sphere.x() + _bottom_plane.y() * sphere.y() +
203 18 : _bottom_plane.z() * sphere.z() + _bottom_plane.w();
204 6 : if( distance <= -sphere.w() )
205 0 : return VISIBILITY_NONE;
206 6 : if( distance < sphere.w() )
207 4 : visibility = VISIBILITY_PARTIAL;
208 :
209 24 : distance = _top_plane.x() * sphere.x() + _top_plane.y() * sphere.y() +
210 18 : _top_plane.z() * sphere.z() + _top_plane.w();
211 6 : if( distance <= -sphere.w() )
212 0 : return VISIBILITY_NONE;
213 6 : if( distance < sphere.w() )
214 4 : visibility = VISIBILITY_PARTIAL;
215 :
216 24 : distance = _near_plane.x() * sphere.x() + _near_plane.y() * sphere.y() +
217 18 : _near_plane.z() * sphere.z() + _near_plane.w();
218 :
219 6 : if( distance <= -sphere.w() )
220 2 : return VISIBILITY_NONE;
221 4 : if( distance < sphere.w() )
222 2 : visibility = VISIBILITY_PARTIAL;
223 :
224 16 : distance = _far_plane.x() * sphere.x() + _far_plane.y() * sphere.y() +
225 12 : _far_plane.z() * sphere.z() + _far_plane.w();
226 4 : if( distance <= -sphere.w() )
227 0 : return VISIBILITY_NONE;
228 4 : if( distance < sphere.w() )
229 0 : visibility = VISIBILITY_PARTIAL;
230 :
231 4 : return visibility;
232 : }
233 :
234 : template < class T >
235 34 : 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 34 : const T d = plane.dot( middle );
241 68 : const T n = extent.x() * fabs( plane.x( )) +
242 68 : extent.y() * fabs( plane.y( )) +
243 136 : extent.z() * fabs( plane.z( ));
244 :
245 34 : if( d - n >= 0 )
246 14 : return VISIBILITY_FULL;
247 20 : if( d + n > 0 )
248 18 : return VISIBILITY_PARTIAL;
249 2 : return VISIBILITY_NONE;
250 : }
251 :
252 : template < class T >
253 6 : Visibility frustum_culler< T >::test_aabb( const vec2& x, const vec2& y,
254 : const vec2& z ) const
255 : {
256 6 : Visibility result = VISIBILITY_FULL;
257 6 : const vec3& middle = vec3( x[0] + x[1], y[0] + y[1], z[0] + z[1] ) * .5;
258 12 : const vec3& extent = vec3( fabs(x[1] - x[0]), fabs(y[1] - y[0]),
259 18 : fabs(z[1] - z[0]) ) * .5;
260 6 : switch( _test_aabb( _left_plane, middle, extent ))
261 : {
262 2 : case VISIBILITY_FULL: break;
263 4 : case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
264 0 : case VISIBILITY_NONE: return VISIBILITY_NONE;
265 : }
266 :
267 6 : switch( _test_aabb( _right_plane, middle, extent ))
268 : {
269 2 : case VISIBILITY_FULL: break;
270 4 : case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
271 0 : case VISIBILITY_NONE: return VISIBILITY_NONE;
272 : }
273 :
274 6 : switch( _test_aabb( _bottom_plane, middle, extent ))
275 : {
276 2 : case VISIBILITY_FULL: break;
277 4 : case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
278 0 : case VISIBILITY_NONE: return VISIBILITY_NONE;
279 : }
280 :
281 6 : switch( _test_aabb( _top_plane, middle, extent ))
282 : {
283 2 : case VISIBILITY_FULL: break;
284 4 : case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
285 0 : case VISIBILITY_NONE: return VISIBILITY_NONE;
286 : }
287 :
288 6 : switch( _test_aabb( _near_plane, middle, extent ))
289 : {
290 2 : case VISIBILITY_FULL: break;
291 2 : case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
292 2 : case VISIBILITY_NONE: return VISIBILITY_NONE;
293 : }
294 :
295 4 : switch( _test_aabb( _far_plane, middle, extent ))
296 : {
297 4 : case VISIBILITY_FULL: break;
298 0 : case VISIBILITY_PARTIAL: result = VISIBILITY_PARTIAL; break;
299 0 : case VISIBILITY_NONE: return VISIBILITY_NONE;
300 : }
301 :
302 4 : return result;
303 : }
304 :
305 : } // namespace vmml
306 :
307 : #endif // include protection
|
