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
|