vmmlib  1.13.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 {
46 template <typename T>
48 {
49 public:
50  typedef vector<2, T> vec2;
51  typedef vector<3, T> vec3;
52  typedef vector<4, T> vec4;
53 
57  explicit FrustumCuller(const Matrix<4, 4, T>& projModelView);
58 
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 
70  Visibility test(const vec4& sphere) const;
71 
73  Visibility test(const AABB<T>& aabb) const;
74 
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 {
110 template <typename T>
112 {
113  // See http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf pp.5
114  const vec4& row0 = projModelView.getRow(0);
115  const vec4& row1 = projModelView.getRow(1);
116  const vec4& row2 = projModelView.getRow(2);
117  const vec4& row3 = projModelView.getRow(3);
118 
119  _leftPlane = row3 + row0;
120  _rightPlane = row3 - row0;
121  _bottomPlane = row3 + row1;
122  _topPlane = row3 - row1;
123  _nearPlane = row3 + row2;
124  _farPlane = row3 - row2;
125 
126  _normalizePlane(_leftPlane);
127  _normalizePlane(_rightPlane);
128  _normalizePlane(_bottomPlane);
129  _normalizePlane(_topPlane);
130  _normalizePlane(_nearPlane);
131  _normalizePlane(_farPlane);
132 }
133 
134 template <typename T>
135 FrustumCuller<T>::FrustumCuller(const vec3& a, const vec3& b, const vec3& c,
136  const vec3& d, const vec3& e, const vec3& f,
137  const vec3& g, const vec3& h)
138 {
139  // e_____f
140  // /____ /|
141  // | a b | |
142  // | c d |/h
143  // -----
144  // CCW winding
145  _leftPlane = compute_plane(c, a, e);
146  _rightPlane = compute_plane(f, b, d);
147  _bottomPlane = compute_plane(h, d, c);
148  _topPlane = compute_plane(a, b, f);
149  _nearPlane = compute_plane(b, a, c);
150  _farPlane = compute_plane(g, e, f);
151 }
152 
153 template <typename T>
154 inline void FrustumCuller<T>::_normalizePlane(vector<4, T>& plane) const
155 {
156  const vec3& v3 = plane.template get_sub_vector<3, 0>();
157  const T len_i = 1.0 / v3.length();
158  plane.x() *= len_i;
159  plane.y() *= len_i;
160  plane.z() *= len_i;
161  plane.w() *= len_i;
162 }
163 
164 template <typename T>
165 Visibility FrustumCuller<T>::test(const vector<4, T>& sphere) const
166 {
167  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  T distance = _leftPlane.x() * sphere.x() + _leftPlane.y() * sphere.y() +
177  _leftPlane.z() * sphere.z() + _leftPlane.w();
178  if (distance <= -sphere.w())
179  return VISIBILITY_NONE;
180  if (distance < sphere.w())
181  visibility = VISIBILITY_PARTIAL;
182 
183  distance = _rightPlane.x() * sphere.x() + _rightPlane.y() * sphere.y() +
184  _rightPlane.z() * sphere.z() + _rightPlane.w();
185  if (distance <= -sphere.w())
186  return VISIBILITY_NONE;
187  if (distance < sphere.w())
188  visibility = VISIBILITY_PARTIAL;
189 
190  distance = _bottomPlane.x() * sphere.x() + _bottomPlane.y() * sphere.y() +
191  _bottomPlane.z() * sphere.z() + _bottomPlane.w();
192  if (distance <= -sphere.w())
193  return VISIBILITY_NONE;
194  if (distance < sphere.w())
195  visibility = VISIBILITY_PARTIAL;
196 
197  distance = _topPlane.x() * sphere.x() + _topPlane.y() * sphere.y() +
198  _topPlane.z() * sphere.z() + _topPlane.w();
199  if (distance <= -sphere.w())
200  return VISIBILITY_NONE;
201  if (distance < sphere.w())
202  visibility = VISIBILITY_PARTIAL;
203 
204  distance = _nearPlane.x() * sphere.x() + _nearPlane.y() * sphere.y() +
205  _nearPlane.z() * sphere.z() + _nearPlane.w();
206 
207  if (distance <= -sphere.w())
208  return VISIBILITY_NONE;
209  if (distance < sphere.w())
210  visibility = VISIBILITY_PARTIAL;
211 
212  distance = _farPlane.x() * sphere.x() + _farPlane.y() * sphere.y() +
213  _farPlane.z() * sphere.z() + _farPlane.w();
214  if (distance <= -sphere.w())
215  return VISIBILITY_NONE;
216  if (distance < sphere.w())
217  visibility = VISIBILITY_PARTIAL;
218 
219  return visibility;
220 }
221 
222 template <typename T>
223 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  const T d = plane.dot(middle);
228  const T n = extent.x() * fabs(plane.x()) + extent.y() * fabs(plane.y()) +
229  extent.z() * fabs(plane.z());
230 
231  if (d - n >= 0)
232  return VISIBILITY_FULL;
233  if (d + n > 0)
234  return VISIBILITY_PARTIAL;
235  return VISIBILITY_NONE;
236 }
237 
238 template <typename T>
239 Visibility FrustumCuller<T>::test(const AABB<T>& aabb) const
240 {
241  Visibility result = VISIBILITY_FULL;
242  const vec3& middle = aabb.getCenter();
243  const vec3& extent = aabb.getSize() * 0.5f;
244  switch (_test(_leftPlane, middle, extent))
245  {
246  case VISIBILITY_FULL:
247  break;
248  case VISIBILITY_PARTIAL:
249  result = VISIBILITY_PARTIAL;
250  break;
251  case VISIBILITY_NONE:
252  return VISIBILITY_NONE;
253  }
254 
255  switch (_test(_rightPlane, middle, extent))
256  {
257  case VISIBILITY_FULL:
258  break;
259  case VISIBILITY_PARTIAL:
260  result = VISIBILITY_PARTIAL;
261  break;
262  case VISIBILITY_NONE:
263  return VISIBILITY_NONE;
264  }
265 
266  switch (_test(_bottomPlane, middle, extent))
267  {
268  case VISIBILITY_FULL:
269  break;
270  case VISIBILITY_PARTIAL:
271  result = VISIBILITY_PARTIAL;
272  break;
273  case VISIBILITY_NONE:
274  return VISIBILITY_NONE;
275  }
276 
277  switch (_test(_topPlane, middle, extent))
278  {
279  case VISIBILITY_FULL:
280  break;
281  case VISIBILITY_PARTIAL:
282  result = VISIBILITY_PARTIAL;
283  break;
284  case VISIBILITY_NONE:
285  return VISIBILITY_NONE;
286  }
287 
288  switch (_test(_nearPlane, middle, extent))
289  {
290  case VISIBILITY_FULL:
291  break;
292  case VISIBILITY_PARTIAL:
293  result = VISIBILITY_PARTIAL;
294  break;
295  case VISIBILITY_NONE:
296  return VISIBILITY_NONE;
297  }
298 
299  switch (_test(_farPlane, middle, extent))
300  {
301  case VISIBILITY_FULL:
302  break;
303  case VISIBILITY_PARTIAL:
304  result = VISIBILITY_PARTIAL;
305  break;
306  case VISIBILITY_NONE:
307  return VISIBILITY_NONE;
308  }
309 
310  return result;
311 }
312 
313 } // namespace vmml
314 
315 #endif // include protection
Helper class to perform OpenGL view frustum culling.
vector< 3, T > getSize() const
Definition: aabb.hpp:261
FrustumCuller()
Construct a new frustum culler.
const vec4 & getNearPlane() const
Definition: aabb.hpp:44
An axis-aligned bounding box.
Definition: aabb.hpp:47
Visibility test(const vec4 &sphere) const
~FrustumCuller()
Destruct this frustum culler.
vector< 3, T > getCenter() const
Definition: aabb.hpp:255
Matrix with R rows and C columns of element type T.
Definition: matrix.hpp:52