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 : /** Helper class to perform OpenGL view frustum culling. */
46 : template <typename T>
47 : 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 : /** Construct a frustum culler using a 4x4 projection*model*view matrix. */
57 : explicit FrustumCuller(const Matrix<4, 4, T>& projModelView);
58 :
59 : /**
60 : * Construct a frustum culler using the eight frustum corner points.
61 : * Corner naming is n(ear)|f(ar), l(eft)|r(ight), t(op)|b(ottom)
62 : */
63 : FrustumCuller(const vec3& nlt, const vec3& nrt, const vec3& nlb,
64 : const vec3& nrb, const vec3& flt, const vec3& frt,
65 : const vec3& flb, const vec3& frb);
66 :
67 : /** Destruct this frustum culler. */
68 2 : ~FrustumCuller() {}
69 : /** @return the visibility of the given sphere */
70 : Visibility test(const vec4& sphere) const;
71 :
72 : /** @return the visibility of the axis-aligned bounding box */
73 : Visibility test(const AABB<T>& aabb) const;
74 :
75 : /** @return the plane equation of the current near plane. */
76 : const vec4& getNearPlane() const { return _nearPlane; }
77 : friend std::ostream& operator<<(std::ostream& os, const FrustumCuller& f)
78 : {
79 : return os << "Frustum cull planes: " << std::endl
80 : << " left " << f._leftPlane << std::endl
81 : << " right " << f._rightPlane << std::endl
82 : << " top " << f._topPlane << std::endl
83 : << " bottom " << f._bottomPlane << std::endl
84 : << " near " << f._nearPlane << std::endl
85 : << " far " << f._farPlane << std::endl;
86 : }
87 :
88 : private:
89 : inline void _normalizePlane(vec4& plane) const;
90 : inline Visibility _test(const vec4& plane, const vec3& middle,
91 : const vec3& size_2) const;
92 : vec4 _leftPlane;
93 : vec4 _rightPlane;
94 : vec4 _bottomPlane;
95 : vec4 _topPlane;
96 : vec4 _nearPlane;
97 : vec4 _farPlane;
98 :
99 : }; // class FrustumCuller
100 : } // namespace vmml
101 :
102 : // - implementation - //
103 :
104 : namespace vmml
105 : {
106 : /**
107 : * Setup the culler by extracting the frustum planes from the projection
108 : * matrix. The projection matrix should contain the viewing transformation.
109 : */
110 : template <typename T>
111 1 : FrustumCuller<T>::FrustumCuller(const Matrix<4, 4, T>& projModelView)
112 : {
113 : // See http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf pp.5
114 1 : const vec4& row0 = projModelView.getRow(0);
115 1 : const vec4& row1 = projModelView.getRow(1);
116 1 : const vec4& row2 = projModelView.getRow(2);
117 1 : const vec4& row3 = projModelView.getRow(3);
118 :
119 1 : _leftPlane = row3 + row0;
120 1 : _rightPlane = row3 - row0;
121 1 : _bottomPlane = row3 + row1;
122 1 : _topPlane = row3 - row1;
123 1 : _nearPlane = row3 + row2;
124 1 : _farPlane = row3 - row2;
125 :
126 1 : _normalizePlane(_leftPlane);
127 1 : _normalizePlane(_rightPlane);
128 1 : _normalizePlane(_bottomPlane);
129 1 : _normalizePlane(_topPlane);
130 1 : _normalizePlane(_nearPlane);
131 1 : _normalizePlane(_farPlane);
132 1 : }
133 :
134 : template <typename T>
135 1 : FrustumCuller<T>::FrustumCuller(const vec3& a, const vec3& b, const vec3& c,
136 : const vec3& d, const vec3& e, const vec3& f,
137 1 : const vec3& g, const vec3& h)
138 : {
139 : // e_____f
140 : // /____ /|
141 : // | a b | |
142 : // | c d |/h
143 : // -----
144 : // CCW winding
145 1 : _leftPlane = compute_plane(c, a, e);
146 1 : _rightPlane = compute_plane(f, b, d);
147 1 : _bottomPlane = compute_plane(h, d, c);
148 1 : _topPlane = compute_plane(a, b, f);
149 1 : _nearPlane = compute_plane(b, a, c);
150 1 : _farPlane = compute_plane(g, e, f);
151 1 : }
152 :
153 : template <typename T>
154 6 : inline void FrustumCuller<T>::_normalizePlane(vector<4, T>& plane) const
155 : {
156 6 : const vec3& v3 = plane.template get_sub_vector<3, 0>();
157 6 : const T len_i = 1.0 / v3.length();
158 6 : plane.x() *= len_i;
159 6 : plane.y() *= len_i;
160 6 : plane.z() *= len_i;
161 6 : plane.w() *= len_i;
162 6 : }
163 :
164 : template <typename T>
165 6 : Visibility FrustumCuller<T>::test(const vector<4, T>& sphere) const
166 : {
167 6 : Visibility visibility = VISIBILITY_FULL;
168 :
169 : // see http://www.flipcode.com/articles/article_frustumculling.shtml
170 : // distance = plane.normal . sphere.center + plane.distance
171 : // Test all planes:
172 : // - if sphere behind plane: not visible
173 : // - if sphere intersects one plane: partially visible
174 : // - else: fully visible
175 :
176 12 : T distance = _leftPlane.x() * sphere.x() + _leftPlane.y() * sphere.y() +
177 12 : _leftPlane.z() * sphere.z() + _leftPlane.w();
178 6 : if (distance <= -sphere.w())
179 0 : return VISIBILITY_NONE;
180 6 : if (distance < sphere.w())
181 4 : visibility = VISIBILITY_PARTIAL;
182 :
183 18 : distance = _rightPlane.x() * sphere.x() + _rightPlane.y() * sphere.y() +
184 12 : _rightPlane.z() * sphere.z() + _rightPlane.w();
185 6 : if (distance <= -sphere.w())
186 0 : return VISIBILITY_NONE;
187 6 : if (distance < sphere.w())
188 4 : visibility = VISIBILITY_PARTIAL;
189 :
190 18 : distance = _bottomPlane.x() * sphere.x() + _bottomPlane.y() * sphere.y() +
191 12 : _bottomPlane.z() * sphere.z() + _bottomPlane.w();
192 6 : if (distance <= -sphere.w())
193 0 : return VISIBILITY_NONE;
194 6 : if (distance < sphere.w())
195 4 : visibility = VISIBILITY_PARTIAL;
196 :
197 18 : distance = _topPlane.x() * sphere.x() + _topPlane.y() * sphere.y() +
198 12 : _topPlane.z() * sphere.z() + _topPlane.w();
199 6 : if (distance <= -sphere.w())
200 0 : return VISIBILITY_NONE;
201 6 : if (distance < sphere.w())
202 4 : visibility = VISIBILITY_PARTIAL;
203 :
204 18 : distance = _nearPlane.x() * sphere.x() + _nearPlane.y() * sphere.y() +
205 12 : _nearPlane.z() * sphere.z() + _nearPlane.w();
206 :
207 6 : if (distance <= -sphere.w())
208 2 : return VISIBILITY_NONE;
209 4 : if (distance < sphere.w())
210 2 : visibility = VISIBILITY_PARTIAL;
211 :
212 12 : distance = _farPlane.x() * sphere.x() + _farPlane.y() * sphere.y() +
213 8 : _farPlane.z() * sphere.z() + _farPlane.w();
214 4 : if (distance <= -sphere.w())
215 0 : return VISIBILITY_NONE;
216 4 : if (distance < sphere.w())
217 0 : visibility = VISIBILITY_PARTIAL;
218 :
219 4 : return visibility;
220 : }
221 :
222 : template <typename T>
223 34 : Visibility FrustumCuller<T>::_test(const vec4& plane, const vec3& middle,
224 : const vec3& extent) const
225 : {
226 : // http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html
227 34 : const T d = plane.dot(middle);
228 68 : const T n = extent.x() * fabs(plane.x()) + extent.y() * fabs(plane.y()) +
229 68 : extent.z() * fabs(plane.z());
230 :
231 34 : if (d - n >= 0)
232 14 : return VISIBILITY_FULL;
233 20 : if (d + n > 0)
234 18 : return VISIBILITY_PARTIAL;
235 2 : return VISIBILITY_NONE;
236 : }
237 :
238 : template <typename T>
239 6 : Visibility FrustumCuller<T>::test(const AABB<T>& aabb) const
240 : {
241 6 : Visibility result = VISIBILITY_FULL;
242 6 : const vec3& middle = aabb.getCenter();
243 6 : const vec3& extent = aabb.getSize() * 0.5f;
244 6 : switch (_test(_leftPlane, middle, extent))
245 : {
246 : case VISIBILITY_FULL:
247 2 : break;
248 : case VISIBILITY_PARTIAL:
249 4 : result = VISIBILITY_PARTIAL;
250 4 : break;
251 : case VISIBILITY_NONE:
252 0 : return VISIBILITY_NONE;
253 : }
254 :
255 6 : switch (_test(_rightPlane, middle, extent))
256 : {
257 : case VISIBILITY_FULL:
258 2 : break;
259 : case VISIBILITY_PARTIAL:
260 4 : result = VISIBILITY_PARTIAL;
261 4 : break;
262 : case VISIBILITY_NONE:
263 0 : return VISIBILITY_NONE;
264 : }
265 :
266 6 : switch (_test(_bottomPlane, middle, extent))
267 : {
268 : case VISIBILITY_FULL:
269 2 : break;
270 : case VISIBILITY_PARTIAL:
271 4 : result = VISIBILITY_PARTIAL;
272 4 : break;
273 : case VISIBILITY_NONE:
274 0 : return VISIBILITY_NONE;
275 : }
276 :
277 6 : switch (_test(_topPlane, middle, extent))
278 : {
279 : case VISIBILITY_FULL:
280 2 : break;
281 : case VISIBILITY_PARTIAL:
282 4 : result = VISIBILITY_PARTIAL;
283 4 : break;
284 : case VISIBILITY_NONE:
285 0 : return VISIBILITY_NONE;
286 : }
287 :
288 6 : switch (_test(_nearPlane, middle, extent))
289 : {
290 : case VISIBILITY_FULL:
291 2 : break;
292 : case VISIBILITY_PARTIAL:
293 2 : result = VISIBILITY_PARTIAL;
294 2 : break;
295 : case VISIBILITY_NONE:
296 2 : return VISIBILITY_NONE;
297 : }
298 :
299 4 : switch (_test(_farPlane, middle, extent))
300 : {
301 : case VISIBILITY_FULL:
302 4 : break;
303 : case VISIBILITY_PARTIAL:
304 0 : result = VISIBILITY_PARTIAL;
305 0 : break;
306 : case VISIBILITY_NONE:
307 0 : return VISIBILITY_NONE;
308 : }
309 :
310 4 : return result;
311 : }
312 :
313 : } // namespace vmml
314 :
315 : #endif // include protection
|
