MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
geometry.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015, Simon Fuhrmann
3 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
4 * All rights reserved.
5 *
6 * This software may be modified and distributed under the terms
7 * of the BSD 3-Clause license. See the LICENSE.txt file for details.
8 */
9
10#ifndef MATH_GEOMETRY_HEADER
11#define MATH_GEOMETRY_HEADER
12
13#include "math/defines.h"
14#include "math/vector.h"
15#include "math/matrix.h"
16#include "math/matrix_tools.h"
17
20
26template <typename T>
29 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
30 math::Vector<T,3> const& d);
31
36template <typename T>
37float
39 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
40 math::Vector<T,3> const& d);
41
51template <typename T>
52float
54 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
55 math::Vector<T,3> const& d, math::Vector<T,3> const& p);
56
61template <typename T>
62float
64 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
65 math::Vector<T,3> const& d);
66
71template <typename T>
72T
74 math::Vector<T,3> const& b, math::Vector<T,3> const& c);
75
80template <typename T>
81T
83 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
84 math::Vector<T,3> const& d);
85
91template <typename T>
92T
94 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
95 math::Vector<T,3> const& d);
96
101template <typename T>
104 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
105 math::Vector<T,3> const& d, math::Vector<T,3> const& p);
106
113template <typename T>
114bool
116 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
117 math::Vector<T,3> const& d, T const& cos_angle);
118
121
122/* ------------------------ Implementation ------------------------ */
123
126
127template <typename T>
130 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
131 math::Vector<T,3> const& d)
132{
133 math::Vector<T,3> ba(b - a);
134 math::Vector<T,3> ca(c - a);
135 math::Vector<T,3> da(d - a);
136 math::Vector<T,3> x1(ba.cross(ca));
137 math::Vector<T,3> x2(da.cross(ba));
138 math::Vector<T,3> x3(ca.cross(da));
139
140 math::Vector<T,3> ret = x1 * da.square_norm() + x2 * ca.square_norm()
141 + x3 * ba.square_norm();
142 ret = a + ret / (ba.dot(x3) * T(2));
143
144 return ret;
145}
146
147/* ---------------------------------------------------------------- */
148
149template <typename T>
150float
152 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
153 math::Vector<T,3> const& d)
154{
155 math::Vector<T,3> ba(b - a);
156 math::Vector<T,3> ca(c - a);
157 math::Vector<T,3> da(d - a);
158 T vol6 = std::abs(ba.dot(ca.cross(da)));
159 return (ba.dot(ba) * ca.cross(da) + ca.dot(ca) * da.cross(ba)
160 + da.dot(da) * ba.cross(ca)).norm() / (vol6 * T(2));
161}
162
163/* ---------------------------------------------------------------- */
164
165template <typename T>
166float
168 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
169 math::Vector<T,3> const& d)
170{
171 math::Vector<T,3> va(b - a);
172 math::Vector<T,3> vb(c - a);
173 math::Vector<T,3> vc(d - a);
174 T vol6 = std::abs(va.dot(vb.cross(vc)));
175 return vol6 / (vb.cross(vc).norm() + vc.cross(va).norm()
176 + va.cross(vb).norm()
177 + (vb.cross(vc) + vc.cross(va) + va.cross(vb)).norm());
178}
179
180/* ---------------------------------------------------------------- */
181
182template <typename T>
183float
185 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
186 math::Vector<T,3> const& d, math::Vector<T,3> const& p)
187{
188 math::Vector<T,3> ba(b - a);
189 math::Vector<T,3> ca(c - a);
190 math::Vector<T,3> da(d - a);
191 math::Vector<T,3> x1(ba.cross(ca));
192 math::Vector<T,3> x2(da.cross(ba));
193 math::Vector<T,3> x3(ca.cross(da));
194
195 math::Vector<T,3> num(x1 * da.square_norm() + x2 * ca.square_norm()
196 + x3 * ba.square_norm());
197 T denom = ba.dot(x3) * T(2);
198
199 T square_radius = num.square_norm() / (denom * denom);
200 T point_sdist = (p - (a + num / denom)).square_norm();
201 return square_radius - point_sdist;
202}
203
204/* ---------------------------------------------------------------- */
205
206template <typename T>
207T
209 math::Vector<T,3> const& b, math::Vector<T,3> const& c)
210{
211 return (b - a).cross(c - a).norm() / T(2);
212}
213
214/* ---------------------------------------------------------------- */
215
216template <typename T>
217inline T
219 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
220 math::Vector<T,3> const& d)
221{
222#if 1
223 /* Efficient calculation using determinat identity from
224 * http://mathworld.wolfram.com/DeterminantIdentities.html
225 */
226 return (c - a).dot((b - a).cross(d - c)) / T(6);
227#else
228 /* Calculation using generic matrix determinant. */
229 math::Vector<T,3> v[3] = { a - d, b - d, c - d };
231 for (int i = 0; i < 9; ++i)
232 m[i] = v[i % 3][i / 3];
233 return matrix_determinant(m) / T(6);
234#endif
235}
236
237/* ---------------------------------------------------------------- */
238
239template <typename T>
240inline T
242 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
243 math::Vector<T,3> const& d)
244{
245 return (c - a).dot((b - a).cross(d - c));
246}
247
248/* ---------------------------------------------------------------- */
249
250template <typename T>
253 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
254 math::Vector<T,3> const& d, math::Vector<T,3> const& p)
255{
256#if 0
257 /* Calculation using the areas of sub-tetrahedra. */
258 /* This version appears to be slower. */
259 T tet = tetrahedron_volume(a, b, c, d);
260 return math::Vector<T,3>(tetrahedron_volume(p, b, c, d) / tet,
261 tetrahedron_volume(p, a, d, c) / tet,
262 tetrahedron_volume(p, a, b, d) / tet);
263#else
264 /* Calculation using inverse M as in x = M*b <=> b = (M^-1)*x. */
265 math::Vector<T,3> v[3] = { a - d, b - d, c - d };
267 for (int i = 0; i < 9; ++i)
268 m[i] = v[i % 3][i / 3];
269 return matrix_inverse(m) * (p - d);
270#endif
271}
272
273/* ---------------------------------------------------------------- */
274
275template <typename T>
276bool
278 math::Vector<T,3> const& b, math::Vector<T,3> const& c,
279 math::Vector<T,3> const& d, T const& cos_angle)
280{
281 /*
282 * http://www.gamedev.net/community/forums/topic.asp?topic_id=408739
283 *
284 * To test if four points P0, P1, P2, P3 are coplanar, you can
285 * create three vectors: V0 = P1-P0, V1 = P2-P0, V2 = P3-P0.
286 * Then compute the triple scalar product: Dot(Cross(V0,V1), V2).
287 * If the result is near 0, then they might be coplanar. However,
288 * they could be collinear. To check for that, do Cross(V0,V1) and
289 * Cross(V0,V2). If both results are near zero, then they're collinear.
290 */
291 math::Vector<T,3> e1(b - a);
292 math::Vector<T,3> e2(c - a);
293 math::Vector<T,3> e3(d - a);
294 T x = std::abs(e1.normalized().dot(e2.cross(e3).normalized()));
295 return x <= cos_angle;
296}
297
300
301#endif /* MATH_GEOMETRY_HEADER */
Matrix class for arbitrary dimensions and types.
Definition matrix.h:54
Vector class for arbitrary dimensions and types.
Definition vector.h:87
T square_norm(void) const
Computes the squared norm of the vector (much cheaper).
Definition vector.h:441
Vector< T, N > cross(Vector< T, N > const &other) const
Cross product between this and another vector.
Definition vector.h:549
T dot(Vector< T, N > const &other) const
Dot (or scalar) product between self and another vector.
Definition vector.h:542
Vector< T, N > normalized(void) const
Returns a normalized copy of self.
Definition vector.h:456
#define MATH_GEOM_NAMESPACE_BEGIN
Definition defines.h:21
#define MATH_NAMESPACE_BEGIN
Definition defines.h:15
#define MATH_NAMESPACE_END
Definition defines.h:16
#define MATH_GEOM_NAMESPACE_END
Definition defines.h:22
bool points_coplanar(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d, T const &cos_angle)
Tests whether four points are coplanar.
Definition geometry.h:277
T tetrahedron_orientation(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d)
Calculates the orientation of the given tetrahedron.
Definition geometry.h:241
math::Vector< T, 3 > tetrahedron_bary(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d, math::Vector< T, 3 > const &p)
Calculates the barycentric coordinates of point 'p' with respect to the tetrahedron given by vertices...
Definition geometry.h:252
float circumsphere_radius(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d)
Returns the circumsphere radius of the sphere defined by a, b, c, d.
Definition geometry.h:151
T triangle_area(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c)
Calculates the area of the given triangle.
Definition geometry.h:208
float circumsphere_test(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d, math::Vector< T, 3 > const &p)
Tests whether vertex 'p' is contained in the circumsphere defined by the four vertices a,...
Definition geometry.h:184
T tetrahedron_volume(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d)
Calculates the volume of the given tetraheron.
Definition geometry.h:218
float insphere_radius(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d)
Returns the insphere radius of the tetrahedron defined by a, b, c, d.
Definition geometry.h:167
math::Vector< T, 3 > circumsphere_center(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c, math::Vector< T, 3 > const &d)
Returns the center of the circumsphere defined by the four given vertices.
Definition geometry.h:129
Matrix< T, N, N > matrix_inverse(Matrix< T, N, N > const &mat)
Calculates the inverse of the given matrix.
T matrix_determinant(Matrix< T, N, N > const &mat)
Calculates the determinant of the given matrix.