| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2000-2022 Inria | ||
| 3 | * All rights reserved. | ||
| 4 | * | ||
| 5 | * Redistribution and use in source and binary forms, with or without | ||
| 6 | * modification, are permitted provided that the following conditions are met: | ||
| 7 | * | ||
| 8 | * * Redistributions of source code must retain the above copyright notice, | ||
| 9 | * this list of conditions and the following disclaimer. | ||
| 10 | * * Redistributions in binary form must reproduce the above copyright notice, | ||
| 11 | * this list of conditions and the following disclaimer in the documentation | ||
| 12 | * and/or other materials provided with the distribution. | ||
| 13 | * * Neither the name of the ALICE Project-Team nor the names of its | ||
| 14 | * contributors may be used to endorse or promote products derived from this | ||
| 15 | * software without specific prior written permission. | ||
| 16 | * | ||
| 17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
| 26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
| 27 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 28 | * | ||
| 29 | * Contact: Bruno Levy | ||
| 30 | * | ||
| 31 | * https://www.inria.fr/fr/bruno-levy | ||
| 32 | * | ||
| 33 | * Inria, | ||
| 34 | * Domaine de Voluceau, | ||
| 35 | * 78150 Le Chesnay - Rocquencourt | ||
| 36 | * FRANCE | ||
| 37 | * | ||
| 38 | */ | ||
| 39 | |||
| 40 | #ifndef GEOGRAM_BASIC_GEOMETRY | ||
| 41 | #define GEOGRAM_BASIC_GEOMETRY | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/basic/matrix.h> | ||
| 45 | |||
| 46 | /** | ||
| 47 | * \file geogram/basic/geometry.h | ||
| 48 | * \brief Geometric functions in 2d and 3d | ||
| 49 | */ | ||
| 50 | |||
| 51 | namespace GEO { | ||
| 52 | |||
| 53 | /************************************************************************/ | ||
| 54 | |||
| 55 | /** | ||
| 56 | * \brief Represents points and vectors in 2d. | ||
| 57 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 58 | */ | ||
| 59 | typedef vecng<2, Numeric::float64> vec2; | ||
| 60 | |||
| 61 | /** | ||
| 62 | * \brief Represents points and vectors in 3d. | ||
| 63 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 64 | */ | ||
| 65 | typedef vecng<3, Numeric::float64> vec3; | ||
| 66 | |||
| 67 | /** | ||
| 68 | * \brief Represents points and vectors in 4d. | ||
| 69 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 70 | */ | ||
| 71 | typedef vecng<4, Numeric::float64> vec4; | ||
| 72 | |||
| 73 | /** | ||
| 74 | * \brief Represents points and vectors in 2d with | ||
| 75 | * single-precision coordinates. | ||
| 76 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 77 | */ | ||
| 78 | typedef vecng<2, Numeric::float32> vec2f; | ||
| 79 | |||
| 80 | /** | ||
| 81 | * \brief Represents points and vectors in 3d with | ||
| 82 | * single-precision coordinates. | ||
| 83 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 84 | */ | ||
| 85 | typedef vecng<3, Numeric::float32> vec3f; | ||
| 86 | |||
| 87 | /** | ||
| 88 | * \brief Represents points and vectors in 4d with | ||
| 89 | * single-precision coordinates. | ||
| 90 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 91 | */ | ||
| 92 | typedef vecng<4, Numeric::float32> vec4f; | ||
| 93 | |||
| 94 | |||
| 95 | /** | ||
| 96 | * \brief Represents points and vectors in 2d with | ||
| 97 | * integer coordinates. | ||
| 98 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 99 | */ | ||
| 100 | typedef vecng<2, Numeric::int32> vec2i; | ||
| 101 | |||
| 102 | /** | ||
| 103 | * \brief Represents points and vectors in 3d with | ||
| 104 | * integer coordinates. | ||
| 105 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 106 | */ | ||
| 107 | typedef vecng<3, Numeric::int32> vec3i; | ||
| 108 | |||
| 109 | /** | ||
| 110 | * \brief Represents points and vectors in 4d with | ||
| 111 | * integer coordinates. | ||
| 112 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 113 | */ | ||
| 114 | typedef vecng<4, Numeric::int32> vec4i; | ||
| 115 | |||
| 116 | /** | ||
| 117 | * \brief Represents points and vectors in 2d with | ||
| 118 | * unsigned integer coordinates. | ||
| 119 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 120 | */ | ||
| 121 | typedef vecng<2, Numeric::uint32> vec2u; | ||
| 122 | |||
| 123 | /** | ||
| 124 | * \brief Represents points and vectors in 3d with | ||
| 125 | * unsigned integer coordinates. | ||
| 126 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 127 | */ | ||
| 128 | typedef vecng<3, Numeric::uint32> vec3u; | ||
| 129 | |||
| 130 | /** | ||
| 131 | * \brief Represents points and vectors in 4d with | ||
| 132 | * unsigned integer coordinates. | ||
| 133 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 134 | */ | ||
| 135 | typedef vecng<4, Numeric::uint32> vec4u; | ||
| 136 | |||
| 137 | /** | ||
| 138 | * \brief Represents a 2x2 matrix. | ||
| 139 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 140 | */ | ||
| 141 | typedef Matrix<2, Numeric::float64> mat2; | ||
| 142 | |||
| 143 | /** | ||
| 144 | * \brief Represents a 3x3 matrix. | ||
| 145 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 146 | */ | ||
| 147 | typedef Matrix<3, Numeric::float64> mat3; | ||
| 148 | |||
| 149 | /** | ||
| 150 | * \brief Represents a 4x4 matrix. | ||
| 151 | * \details Syntax is (mostly) compatible with GLSL. | ||
| 152 | */ | ||
| 153 | typedef Matrix<4, Numeric::float64> mat4; | ||
| 154 | |||
| 155 | /************************************************************************/ | ||
| 156 | |||
| 157 | /** | ||
| 158 | * \brief Computes the determinant of a 2x2 matrix | ||
| 159 | * \param[in] M a const reference to the matrix | ||
| 160 | * \return the determinant | ||
| 161 | */ | ||
| 162 | inline double det(const mat2& M) { | ||
| 163 | return det2x2( | ||
| 164 | M(0,0), M(0,1), | ||
| 165 | M(1,0), M(1,1) | ||
| 166 | ); | ||
| 167 | } | ||
| 168 | |||
| 169 | /** | ||
| 170 | * \brief Computes the determinant of a 3x3 matrix | ||
| 171 | * \param[in] M a const reference to the matrix | ||
| 172 | * \return the determinant | ||
| 173 | */ | ||
| 174 | inline double det(const mat3& M) { | ||
| 175 | return det3x3( | ||
| 176 | M(0,0), M(0,1), M(0,2), | ||
| 177 | M(1,0), M(1,1), M(1,2), | ||
| 178 | M(2,0), M(2,1), M(2,2) | ||
| 179 | ); | ||
| 180 | } | ||
| 181 | |||
| 182 | /** | ||
| 183 | * \brief Computes the determinant of a 4x4 matrix | ||
| 184 | * \param[in] M a const reference to the matrix | ||
| 185 | * \return the determinant | ||
| 186 | */ | ||
| 187 | 258 | inline double det(const mat4& M) { | |
| 188 | 258 | return det4x4( | |
| 189 | M(0,0), M(0,1), M(0,2), M(0,3), | ||
| 190 | M(1,0), M(1,1), M(1,2), M(1,3), | ||
| 191 | M(2,0), M(2,1), M(2,2), M(2,3), | ||
| 192 | M(3,0), M(3,1), M(3,2), M(3,3) | ||
| 193 | 258 | ); | |
| 194 | } | ||
| 195 | |||
| 196 | /************************************************************************/ | ||
| 197 | |||
| 198 | /** | ||
| 199 | * \brief Geometric functions and utilities. | ||
| 200 | */ | ||
| 201 | namespace Geom { | ||
| 202 | |||
| 203 | /** | ||
| 204 | * \brief Computes the barycenter of two points in 3d. | ||
| 205 | * \param[in] p1 first point | ||
| 206 | * \param[in] p2 second point | ||
| 207 | * \return the barycenter of \p p1 and \p p2 | ||
| 208 | */ | ||
| 209 | inline vec3 barycenter(const vec3& p1, const vec3& p2) { | ||
| 210 | return vec3( | ||
| 211 | 0.5 * (p1.x + p2.x), | ||
| 212 | 0.5 * (p1.y + p2.y), | ||
| 213 | 0.5 * (p1.z + p2.z) | ||
| 214 | ); | ||
| 215 | } | ||
| 216 | |||
| 217 | /** | ||
| 218 | * \brief Computes the barycenter of two points in 2d. | ||
| 219 | * \param[in] p1 first point | ||
| 220 | * \param[in] p2 second point | ||
| 221 | * \return the barycenter of \p p1 and \p p2 | ||
| 222 | */ | ||
| 223 | inline vec2 barycenter(const vec2& p1, const vec2& p2) { | ||
| 224 | return vec2( | ||
| 225 | ✗ | 0.5 * (p1.x + p2.x), | |
| 226 | ✗ | 0.5 * (p1.y + p2.y) | |
| 227 | ); | ||
| 228 | } | ||
| 229 | |||
| 230 | /** | ||
| 231 | * \brief Computes the barycenter of three points in 3d. | ||
| 232 | * \param[in] p1 first point | ||
| 233 | * \param[in] p2 second point | ||
| 234 | * \param[in] p3 third point | ||
| 235 | * \return the barycenter of \p p1, \p p2 and \p p3 | ||
| 236 | */ | ||
| 237 | inline vec3 barycenter( | ||
| 238 | const vec3& p1, const vec3& p2, const vec3& p3 | ||
| 239 | ) { | ||
| 240 | return vec3( | ||
| 241 | (p1.x + p2.x + p3.x) / 3.0, | ||
| 242 | (p1.y + p2.y + p3.y) / 3.0, | ||
| 243 | (p1.z + p2.z + p3.z) / 3.0 | ||
| 244 | ); | ||
| 245 | } | ||
| 246 | |||
| 247 | /** | ||
| 248 | * \brief Computes the barycenter of three points in 2d. | ||
| 249 | * \param[in] p1 first point | ||
| 250 | * \param[in] p2 second point | ||
| 251 | * \param[in] p3 third point | ||
| 252 | * \return the barycenter of \p p1, \p p2 and \p p3 | ||
| 253 | */ | ||
| 254 | inline vec2 barycenter( | ||
| 255 | const vec2& p1, const vec2& p2, const vec2& p3 | ||
| 256 | ) { | ||
| 257 | return vec2( | ||
| 258 | (p1.x + p2.x + p3.x) / 3.0, | ||
| 259 | (p1.y + p2.y + p3.y) / 3.0 | ||
| 260 | ); | ||
| 261 | } | ||
| 262 | |||
| 263 | /** | ||
| 264 | * \brief Computes the cosine of the angle between two 3d vectors. | ||
| 265 | * \param[in] a first vector | ||
| 266 | * \param[in] b second vector | ||
| 267 | * \return the cosine of the angle between \p a and \p b | ||
| 268 | */ | ||
| 269 | ✗ | inline double cos_angle(const vec3& a, const vec3& b) { | |
| 270 | ✗ | double lab = ::sqrt(length2(a)*length2(b)); | |
| 271 | ✗ | double result = (lab > 1e-50) ? (dot(a, b) / lab) : 1.0; | |
| 272 | // Numerical precision problem may occur, and generate | ||
| 273 | // normalized dot products that are outside the valid | ||
| 274 | // range of acos. | ||
| 275 | geo_clamp(result, -1.0, 1.0); | ||
| 276 | ✗ | return result; | |
| 277 | } | ||
| 278 | |||
| 279 | /** | ||
| 280 | * \brief Computes the angle between two 3d vectors. | ||
| 281 | * \param[in] a first vector | ||
| 282 | * \param[in] b second vector | ||
| 283 | * \return the angle between \p a and \p b in radians, in | ||
| 284 | * the interval \f$ [ 0 \ldots \pi ] \f$. | ||
| 285 | */ | ||
| 286 | inline double angle(const vec3& a, const vec3& b) { | ||
| 287 | ✗ | return ::acos(cos_angle(a, b)); | |
| 288 | } | ||
| 289 | |||
| 290 | /** | ||
| 291 | * \brief Computes the cosine of the angle between two 2d vectors. | ||
| 292 | * \param[in] a first vector | ||
| 293 | * \param[in] b second vector | ||
| 294 | * \return the cosine of the angle between \p a and \p b | ||
| 295 | */ | ||
| 296 | inline double cos_angle(const vec2& a, const vec2& b) { | ||
| 297 | double lab = ::sqrt(length2(a)*length2(b)); | ||
| 298 | double result = (lab > 1e-20) ? (dot(a, b) / lab) : 1.0; | ||
| 299 | // Numerical precision problem may occur, and generate | ||
| 300 | // normalized dot products that are outside the valid | ||
| 301 | // range of acos. | ||
| 302 | geo_clamp(result, -1.0, 1.0); | ||
| 303 | return result; | ||
| 304 | } | ||
| 305 | |||
| 306 | /** | ||
| 307 | * \brief Computes the determinant of two vectors. | ||
| 308 | * \param[in] a first vector | ||
| 309 | * \param[in] b second vector | ||
| 310 | * \return the determinant of \p a and \p b | ||
| 311 | */ | ||
| 312 | inline double det(const vec2& a, const vec2& b) { | ||
| 313 | ✗ | return a.x * b.y - a.y * b.x; | |
| 314 | } | ||
| 315 | |||
| 316 | /** | ||
| 317 | * \brief Computes the angle between two 2d vectors. | ||
| 318 | * \param[in] a first vector | ||
| 319 | * \param[in] b second vector | ||
| 320 | * \return the angle between \a and \b in radians, | ||
| 321 | * in the interval \f$ [-\pi \ldots \pi] \f$ | ||
| 322 | */ | ||
| 323 | inline double angle(const vec2& a, const vec2& b) { | ||
| 324 | return det(a, b) > 0 ? | ||
| 325 | ::acos(cos_angle(a, b)) : | ||
| 326 | -::acos(cos_angle(a, b)); | ||
| 327 | } | ||
| 328 | |||
| 329 | /** | ||
| 330 | * \brief Computes the normal of a 3d triangle | ||
| 331 | * \param[in] p1 , p2 , p3 the three vertices of the | ||
| 332 | * triangle | ||
| 333 | * \return the normal of the triangle (\p p1, \p p2, \p p3). | ||
| 334 | */ | ||
| 335 | ✗ | inline vec3 triangle_normal( | |
| 336 | const vec3& p1, const vec3& p2, const vec3& p3 | ||
| 337 | ) { | ||
| 338 | ✗ | return cross(p2 - p1, p3 - p1); | |
| 339 | } | ||
| 340 | |||
| 341 | /** | ||
| 342 | * \brief Computes the area of a 3d triangle | ||
| 343 | * \param[in] p1 , p2 , p3 the three vertices of the triangle | ||
| 344 | * \return the area of the triangle (\p p1, \p p2, \p p3). | ||
| 345 | */ | ||
| 346 | 425659 | inline double triangle_area_3d( | |
| 347 | const double* p1, const double* p2, const double* p3 | ||
| 348 | ) { | ||
| 349 | 425659 | double Ux = p2[0] - p1[0]; | |
| 350 | 425659 | double Uy = p2[1] - p1[1]; | |
| 351 | 425659 | double Uz = p2[2] - p1[2]; | |
| 352 | |||
| 353 | 425659 | double Vx = p3[0] - p1[0]; | |
| 354 | 425659 | double Vy = p3[1] - p1[1]; | |
| 355 | 425659 | double Vz = p3[2] - p1[2]; | |
| 356 | |||
| 357 | 425659 | double Nx = Uy*Vz - Uz*Vy; | |
| 358 | 425659 | double Ny = Uz*Vx - Ux*Vz; | |
| 359 | 425659 | double Nz = Ux*Vy - Uy*Vx; | |
| 360 | 425659 | return 0.5 * ::sqrt(Nx*Nx+Ny*Ny+Nz*Nz); | |
| 361 | } | ||
| 362 | |||
| 363 | /** | ||
| 364 | * \brief Computes the area of a 3d triangle | ||
| 365 | * \param[in] p1 , p2 , p3 the three vertices of the triangle | ||
| 366 | * \return the area of the triangle (\p p1, \p p2, \p p3). | ||
| 367 | */ | ||
| 368 | inline double triangle_area( | ||
| 369 | const vec3& p1, const vec3& p2, const vec3& p3 | ||
| 370 | ) { | ||
| 371 | 425659 | return triangle_area_3d(p1.data(), p2.data(), p3.data()); | |
| 372 | } | ||
| 373 | |||
| 374 | /** | ||
| 375 | * \brief Computes the area of a 2d triangle | ||
| 376 | * \param[in] p1 first vertex of the triangle | ||
| 377 | * \param[in] p2 second vertex of the triangle | ||
| 378 | * \param[in] p3 third vertex of the triangle | ||
| 379 | * \return the signed area of the 2D triangle (\p p1, \p p2, \p p3), | ||
| 380 | * positive if the triangle is oriented clockwise, negative otherwise. | ||
| 381 | */ | ||
| 382 | inline double triangle_signed_area_2d( | ||
| 383 | const double* p1, const double* p2, const double* p3 | ||
| 384 | ) { | ||
| 385 | double a = p2[0]-p1[0]; | ||
| 386 | double b = p3[0]-p1[0]; | ||
| 387 | double c = p2[1]-p1[1]; | ||
| 388 | double d = p3[1]-p1[1]; | ||
| 389 | return 0.5*(a*d-b*c); | ||
| 390 | } | ||
| 391 | |||
| 392 | /** | ||
| 393 | * \brief Computes the area of a 2d triangle | ||
| 394 | * \param[in] p1 first vertex of the triangle | ||
| 395 | * \param[in] p2 second vertex of the triangle | ||
| 396 | * \param[in] p3 third vertex of the triangle | ||
| 397 | * \return the signed area of the triangle (\p p1, \p p2, \p p3), | ||
| 398 | * positive if the triangle is oriented clockwise, negative otherwise. | ||
| 399 | */ | ||
| 400 | inline double triangle_signed_area( | ||
| 401 | const vec2& p1, const vec2& p2, const vec2& p3 | ||
| 402 | ) { | ||
| 403 | ✗ | return 0.5 * det(p2 - p1, p3 - p1); | |
| 404 | } | ||
| 405 | |||
| 406 | /** | ||
| 407 | * \brief Computes the area of a 2d triangle | ||
| 408 | * \param[in] p1 first vertex of the triangle | ||
| 409 | * \param[in] p2 second vertex of the triangle | ||
| 410 | * \param[in] p3 third vertex of the triangle | ||
| 411 | * \return the area of the triangle (\p p1, \p p2, \p p3). | ||
| 412 | */ | ||
| 413 | inline double triangle_area( | ||
| 414 | const vec2& p1, const vec2& p2, const vec2& p3 | ||
| 415 | ) { | ||
| 416 | ✗ | return ::fabs(triangle_signed_area(p1, p2, p3)); | |
| 417 | } | ||
| 418 | |||
| 419 | /** | ||
| 420 | * \brief Computes the area of a 2d triangle | ||
| 421 | * \param[in] p1 first vertex of the triangle | ||
| 422 | * \param[in] p2 second vertex of the triangle | ||
| 423 | * \param[in] p3 third vertex of the triangle | ||
| 424 | * \return the area of the triangle (\p p1, \p p2, \p p3). | ||
| 425 | */ | ||
| 426 | inline double triangle_area_2d( | ||
| 427 | const double* p1, const double* p2, const double* p3 | ||
| 428 | ) { | ||
| 429 | return ::fabs(triangle_signed_area_2d(p1,p2,p3)); | ||
| 430 | } | ||
| 431 | |||
| 432 | /** | ||
| 433 | * \brief Computes the center of the circumscribed circle of | ||
| 434 | * a 2d triangle. | ||
| 435 | * \param[in] p1 first vertex of the triangle | ||
| 436 | * \param[in] p2 second vertex of the triangle | ||
| 437 | * \param[in] p3 third vertex of the triangle | ||
| 438 | * \return the circumcenter of the triangle (\p p1, \p p2, \p p3). | ||
| 439 | */ | ||
| 440 | vec2 GEOGRAM_API triangle_circumcenter( | ||
| 441 | const vec2& p1, const vec2& p2, const vec2& p3 | ||
| 442 | ); | ||
| 443 | |||
| 444 | /** | ||
| 445 | * \brief Tests whether a 3d vector has a NaN (not a number) coordinate. | ||
| 446 | * \param[in] v a 3d vector | ||
| 447 | * \return true if one of the coordinates is a NaN, false otherwise | ||
| 448 | */ | ||
| 449 | inline bool has_nan(const vec3& v) { | ||
| 450 | return | ||
| 451 | Numeric::is_nan(v.x) || | ||
| 452 | Numeric::is_nan(v.y) || | ||
| 453 | Numeric::is_nan(v.z); | ||
| 454 | } | ||
| 455 | |||
| 456 | /** | ||
| 457 | * \brief Tests whether a 2d vector has a NaN (not a number) coordinate. | ||
| 458 | * \param[in] v a 2d vector | ||
| 459 | * \return true if one of the coordinates is a NaN, false otherwise | ||
| 460 | */ | ||
| 461 | ✗ | inline bool has_nan(const vec2& v) { | |
| 462 | return | ||
| 463 | ✗ | Numeric::is_nan(v.x) || | |
| 464 | ✗ | Numeric::is_nan(v.y); | |
| 465 | } | ||
| 466 | |||
| 467 | /** | ||
| 468 | * \brief Computes a 3d vector orthogonal to another one. | ||
| 469 | * \param[in] V a 3d vector | ||
| 470 | * \return a 3d vector orthogonal to \p V | ||
| 471 | */ | ||
| 472 | vec3 GEOGRAM_API perpendicular(const vec3& V); | ||
| 473 | |||
| 474 | /** | ||
| 475 | * \brief Computes the signed volume of a 3d tetrahedron | ||
| 476 | * \param[in] p1 first vertex of the tetrahedron | ||
| 477 | * \param[in] p2 second vertex of the tetrahedron | ||
| 478 | * \param[in] p3 third vertex of the tetrahedron | ||
| 479 | * \param[in] p4 fourth vertex of the tetrahedron | ||
| 480 | * \return the signed volume of the tetrahedron | ||
| 481 | * (\p p1, \p p2, \p p3, \p p4) | ||
| 482 | */ | ||
| 483 | 1188202 | inline double tetra_signed_volume( | |
| 484 | const vec3& p1, const vec3& p2, | ||
| 485 | const vec3& p3, const vec3& p4 | ||
| 486 | ) { | ||
| 487 | 1188202 | return dot(p2 - p1, cross(p3 - p1, p4 - p1)) / 6.0; | |
| 488 | } | ||
| 489 | |||
| 490 | /** | ||
| 491 | * \brief Computes the signed volume of a 3d tetrahedron | ||
| 492 | * \param[in] p1 first vertex of the tetrahedron | ||
| 493 | * \param[in] p2 second vertex of the tetrahedron | ||
| 494 | * \param[in] p3 third vertex of the tetrahedron | ||
| 495 | * \param[in] p4 fourth vertex of the tetrahedron | ||
| 496 | * \return the signed volume of the tetrahedron | ||
| 497 | * (\p p1, \p p2, \p p3, \p p4) | ||
| 498 | */ | ||
| 499 | inline double tetra_signed_volume( | ||
| 500 | const double* p1, const double* p2, | ||
| 501 | const double* p3, const double* p4 | ||
| 502 | ) { | ||
| 503 | return tetra_signed_volume( | ||
| 504 | *reinterpret_cast<const vec3*>(p1), | ||
| 505 | *reinterpret_cast<const vec3*>(p2), | ||
| 506 | *reinterpret_cast<const vec3*>(p3), | ||
| 507 | *reinterpret_cast<const vec3*>(p4) | ||
| 508 | ); | ||
| 509 | } | ||
| 510 | |||
| 511 | /** | ||
| 512 | * \brief Computes the volume of a 3d tetrahedron | ||
| 513 | * \param[in] p1 first vertex of the tetrahedron | ||
| 514 | * \param[in] p2 second vertex of the tetrahedron | ||
| 515 | * \param[in] p3 third vertex of the tetrahedron | ||
| 516 | * \param[in] p4 fourth vertex of the tetrahedron | ||
| 517 | * \return the volume of the tetrahedron | ||
| 518 | * (\p p1, \p p2, \p p3, \p p4) | ||
| 519 | */ | ||
| 520 | inline double tetra_volume( | ||
| 521 | const vec3& p1, const vec3& p2, | ||
| 522 | const vec3& p3, const vec3& p4 | ||
| 523 | ) { | ||
| 524 | 1138868 | return ::fabs(tetra_signed_volume(p1, p2, p3, p4)); | |
| 525 | } | ||
| 526 | |||
| 527 | /** | ||
| 528 | * \brief Computes the center of the circumscribed sphere | ||
| 529 | * of 3d tetrahedron | ||
| 530 | * \param[in] p1 first vertex of the tetrahedron | ||
| 531 | * \param[in] p2 second vertex of the tetrahedron | ||
| 532 | * \param[in] p3 third vertex of the tetrahedron | ||
| 533 | * \param[in] p4 fourth vertex of the tetrahedron | ||
| 534 | * \return the circumcenter of the tetrahedron | ||
| 535 | * (\p p1, \p p2, \p p3, \p p4) | ||
| 536 | */ | ||
| 537 | vec3 GEOGRAM_API tetra_circum_center( | ||
| 538 | const vec3& p1, const vec3& p2, | ||
| 539 | const vec3& p3, const vec3& p4 | ||
| 540 | ); | ||
| 541 | |||
| 542 | /** | ||
| 543 | * \brief Computes the centroid of a 3d triangle with weighted points. | ||
| 544 | * \details The integrated weight varies linearly in the triangle. | ||
| 545 | * \param[in] p first vertex of the triangle | ||
| 546 | * \param[in] q second vertex of the triangle | ||
| 547 | * \param[in] r third vertex of the triangle | ||
| 548 | * \param[in] a the weight associated with vertex \p p | ||
| 549 | * \param[in] b the weight associated with vertex \p q | ||
| 550 | * \param[in] c the weight associated with vertex \p r | ||
| 551 | * \param[out] Vg the total weight times the centroid | ||
| 552 | * \param[out] V the total weight | ||
| 553 | */ | ||
| 554 | inline void triangle_centroid( | ||
| 555 | const vec3& p, const vec3& q, const vec3& r, | ||
| 556 | double a, double b, double c, | ||
| 557 | vec3& Vg, double& V | ||
| 558 | ) { | ||
| 559 | double abc = a + b + c; | ||
| 560 | double area = Geom::triangle_area(p, q, r); | ||
| 561 | V = area / 3.0 * abc; | ||
| 562 | double wp = a + abc; | ||
| 563 | double wq = b + abc; | ||
| 564 | double wr = c + abc; | ||
| 565 | double s = area / 12.0; | ||
| 566 | Vg.x = s * (wp * p.x + wq * q.x + wr * r.x); | ||
| 567 | Vg.y = s * (wp * p.y + wq * q.y + wr * r.y); | ||
| 568 | Vg.z = s * (wp * p.z + wq * q.z + wr * r.z); | ||
| 569 | } | ||
| 570 | |||
| 571 | /** | ||
| 572 | * \brief Computes the mass of a 3d triangle with weighted points. | ||
| 573 | * \details The integrated weight varies linearly in the triangle. | ||
| 574 | * \param[in] p first vertex of the triangle | ||
| 575 | * \param[in] q second vertex of the triangle | ||
| 576 | * \param[in] r third vertex of the triangle | ||
| 577 | * \param[in] a the weight associated with vertex \p p | ||
| 578 | * \param[in] b the weight associated with vertex \p q | ||
| 579 | * \param[in] c the weight associated with vertex \p r | ||
| 580 | * \return the mass of the weighted triangle ( \p p, \p a), | ||
| 581 | * ( \p q, \p b), ( \p r, \p c) | ||
| 582 | */ | ||
| 583 | ✗ | inline double triangle_mass( | |
| 584 | const vec3& p, const vec3& q, const vec3& r, | ||
| 585 | double a, double b, double c | ||
| 586 | ) { | ||
| 587 | ✗ | return Geom::triangle_area(p, q, r) / 3.0 * ( | |
| 588 | ✗ | sqrt(::fabs(a)) + sqrt(::fabs(b)) + sqrt(::fabs(c)) | |
| 589 | ✗ | ); | |
| 590 | } | ||
| 591 | |||
| 592 | /** | ||
| 593 | * \brief Generates a random point in a 3d triangle. | ||
| 594 | * \details Uses Greg Turk's second method. | ||
| 595 | * Reference: Greg Turk, Generating Random Points | ||
| 596 | * in Triangles, Graphics Gems, p. 24-28, code: p. 649-650. | ||
| 597 | * \param[in] p1 first vertex of the triangle | ||
| 598 | * \param[in] p2 second vertex of the triangle | ||
| 599 | * \param[in] p3 third vertex of the triangle | ||
| 600 | * \return a random point in triangle ( \p p1, \p p2, \p p3 ) | ||
| 601 | */ | ||
| 602 | 802112 | inline vec3 random_point_in_triangle( | |
| 603 | const vec3& p1, | ||
| 604 | const vec3& p2, | ||
| 605 | const vec3& p3 | ||
| 606 | ) { | ||
| 607 | 802112 | double s = Numeric::random_float64(); | |
| 608 | 802112 | double t = Numeric::random_float64(); | |
| 609 |
2/2✓ Branch 0 taken 400822 times.
✓ Branch 1 taken 401290 times.
|
802112 | if(s + t > 1) { |
| 610 | 400822 | s = 1.0 - s; | |
| 611 | 400822 | t = 1.0 - t; | |
| 612 | } | ||
| 613 | 802112 | double u = 1.0 - s - t; | |
| 614 | return vec3( | ||
| 615 | 802112 | u * p1.x + s * p2.x + t * p3.x, | |
| 616 | 802112 | u * p1.y + s * p2.y + t * p3.y, | |
| 617 | 802112 | u * p1.z + s * p2.z + t * p3.z | |
| 618 | 802112 | ); | |
| 619 | } | ||
| 620 | } | ||
| 621 | |||
| 622 | /** | ||
| 623 | * \brief A 3D Plane. | ||
| 624 | * \details The plane is represented by the coefficients | ||
| 625 | * a,b,c,d of its equation \f$ ax + by + cz + d = 0 \f$. | ||
| 626 | */ | ||
| 627 | struct Plane { | ||
| 628 | |||
| 629 | /** | ||
| 630 | * \brief Constructs the plane passing through three points. | ||
| 631 | * \param[in] p1 first point | ||
| 632 | * \param[in] p2 second point | ||
| 633 | * \param[in] p3 third point | ||
| 634 | */ | ||
| 635 | Plane(const vec3& p1, const vec3& p2, const vec3& p3) { | ||
| 636 | vec3 n = cross(p2 - p1, p3 - p1); | ||
| 637 | a = n.x; | ||
| 638 | b = n.y; | ||
| 639 | c = n.z; | ||
| 640 | d = -(a * p1.x + b * p1.y + c * p1.z); | ||
| 641 | } | ||
| 642 | |||
| 643 | /** | ||
| 644 | * \brief Constructs a plane passign through a point and orthogonal | ||
| 645 | * to a vector. | ||
| 646 | * \param[in] p the point | ||
| 647 | * \param[in] n the vector | ||
| 648 | */ | ||
| 649 | Plane(const vec3& p, const vec3& n) { | ||
| 650 | a = n.x; | ||
| 651 | b = n.y; | ||
| 652 | c = n.z; | ||
| 653 | d = -(a * p.x + b * p.y + c * p.z); | ||
| 654 | } | ||
| 655 | |||
| 656 | /** | ||
| 657 | * \brief Constructs a plane from the coefficients of its equation. | ||
| 658 | */ | ||
| 659 | Plane( | ||
| 660 | double a_in, double b_in, double c_in, double d_in | ||
| 661 | ) : | ||
| 662 | a(a_in), | ||
| 663 | b(b_in), | ||
| 664 | c(c_in), | ||
| 665 | d(d_in) { | ||
| 666 | } | ||
| 667 | |||
| 668 | /** | ||
| 669 | * \brief Constructs an uninitialized plane. | ||
| 670 | */ | ||
| 671 | Plane() { | ||
| 672 | } | ||
| 673 | |||
| 674 | /** | ||
| 675 | * \brief Gets the normal vector of the plane. | ||
| 676 | */ | ||
| 677 | vec3 normal() const { | ||
| 678 | return vec3(a, b, c); | ||
| 679 | } | ||
| 680 | |||
| 681 | double a, b, c, d; | ||
| 682 | }; | ||
| 683 | |||
| 684 | /*******************************************************************/ | ||
| 685 | |||
| 686 | /** | ||
| 687 | * \brief Axis-aligned bounding box. | ||
| 688 | */ | ||
| 689 | class Box { | ||
| 690 | public: | ||
| 691 | double xyz_min[3]; | ||
| 692 | double xyz_max[3]; | ||
| 693 | |||
| 694 | /** | ||
| 695 | * \brief Constructs an uninitialized box | ||
| 696 | * \details Please note that the box is uninitialized. One may | ||
| 697 | * call clear() to get an initialized empty box. | ||
| 698 | */ | ||
| 699 | 504 | Box() { | |
| 700 | } | ||
| 701 | |||
| 702 | /** | ||
| 703 | * \brief Constructs a box from lower and upper bounds | ||
| 704 | * \param[in] x1 , y1 , z1 the lower bounds | ||
| 705 | * \param[in] x2 , y2 , z2 the upper bounds | ||
| 706 | */ | ||
| 707 | 85068 | Box(double x1, double y1, double z1, double x2, double y2, double z2) { | |
| 708 | 85068 | xyz_min[0] = x1; | |
| 709 | 85068 | xyz_min[1] = y1; | |
| 710 | 85068 | xyz_min[2] = z1; | |
| 711 | 85068 | xyz_max[0] = x2; | |
| 712 | 85068 | xyz_max[1] = y2; | |
| 713 |
2/22✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
|
85066 | xyz_max[2] = z2; |
| 714 | } | ||
| 715 | |||
| 716 | /** | ||
| 717 | * \brief Constructs a box from lower and upper bounds | ||
| 718 | * \param[in] lo the lower bound as a vec3 | ||
| 719 | * \param[in] hi the upper bound as a vec3 | ||
| 720 | */ | ||
| 721 | Box(const vec3& lo, const vec3& hi) { | ||
| 722 | xyz_min[0] = lo.x; | ||
| 723 | xyz_min[1] = lo.y; | ||
| 724 | xyz_min[2] = lo.z; | ||
| 725 | xyz_max[0] = hi.x; | ||
| 726 | xyz_max[1] = hi.y; | ||
| 727 | xyz_max[2] = hi.z; | ||
| 728 | } | ||
| 729 | |||
| 730 | /** | ||
| 731 | * \brief Gets the lower bounds | ||
| 732 | * \return the lower bounds as a vec3 | ||
| 733 | */ | ||
| 734 | vec3 lo() const { | ||
| 735 | return vec3(xyz_min); | ||
| 736 | } | ||
| 737 | |||
| 738 | /** | ||
| 739 | * \brief Gets the higher bounds | ||
| 740 | * \return the higher bounds as a vec3 | ||
| 741 | */ | ||
| 742 | vec3 hi() const { | ||
| 743 | return vec3(xyz_max); | ||
| 744 | } | ||
| 745 | |||
| 746 | /** | ||
| 747 | * \brief Tests whether a box contains a point. | ||
| 748 | * \param[in] b the point | ||
| 749 | * \return true if this box contains \p b, false otherwise | ||
| 750 | */ | ||
| 751 | bool contains(const vec3& b) const { | ||
| 752 | ✗ | for(coord_index_t c = 0; c < 3; ++c) { | |
| 753 | ✗ | if(b[c] < xyz_min[c]) { | |
| 754 | return false; | ||
| 755 | } | ||
| 756 | ✗ | if(b[c] > xyz_max[c]) { | |
| 757 | return false; | ||
| 758 | } | ||
| 759 | } | ||
| 760 | return true; | ||
| 761 | } | ||
| 762 | |||
| 763 | /** | ||
| 764 | * \brief Enlarges the box | ||
| 765 | * \param[in] d the amount that should be subtracted from the lower | ||
| 766 | * bounds and added to the upper bounds | ||
| 767 | */ | ||
| 768 | void enlarge(double d) { | ||
| 769 | xyz_min[0] -= d; | ||
| 770 | xyz_min[1] -= d; | ||
| 771 | xyz_min[2] -= d; | ||
| 772 | xyz_max[0] += d; | ||
| 773 | xyz_max[1] += d; | ||
| 774 | xyz_max[2] += d; | ||
| 775 | } | ||
| 776 | |||
| 777 | /** | ||
| 778 | * \brief Makes this box empty | ||
| 779 | * \details Initializes the lower bounds to the greatest floating point | ||
| 780 | * number and the higher bounds to minus the greatest floating point | ||
| 781 | * number | ||
| 782 | */ | ||
| 783 | void clear() { | ||
| 784 | for(index_t c=0; c<3; ++c) { | ||
| 785 | xyz_min[c] = Numeric::max_float64(); | ||
| 786 | xyz_max[c] = -Numeric::max_float64(); | ||
| 787 | } | ||
| 788 | } | ||
| 789 | |||
| 790 | /** | ||
| 791 | * \brief Adds a point to this box | ||
| 792 | * \param[in] p a const reference to the point to be added | ||
| 793 | * \details The box is the smallest axis-aligned box enclosing | ||
| 794 | * all added points | ||
| 795 | */ | ||
| 796 | void add(const vec3& p) { | ||
| 797 | for(index_t c=0; c<3; ++c) { | ||
| 798 | xyz_min[c] = std::min(xyz_min[c], p[c]); | ||
| 799 | xyz_max[c] = std::max(xyz_max[c], p[c]); | ||
| 800 | } | ||
| 801 | } | ||
| 802 | |||
| 803 | }; | ||
| 804 | |||
| 805 | typedef Box Box3d; | ||
| 806 | |||
| 807 | /** | ||
| 808 | * \brief Tests whether two Boxes have a non-empty intersection. | ||
| 809 | * \param[in] B1 first box | ||
| 810 | * \param[in] B2 second box | ||
| 811 | * \return true if \p B1 and \p B2 have a non-empty intersection, | ||
| 812 | * false otherwise. | ||
| 813 | */ | ||
| 814 | inline bool bboxes_overlap(const Box& B1, const Box& B2) { | ||
| 815 |
4/4✓ Branch 0 taken 13594751 times.
✓ Branch 1 taken 3665606 times.
✓ Branch 2 taken 11426 times.
✓ Branch 3 taken 3380 times.
|
17275163 | for(coord_index_t c = 0; c < 3; ++c) { |
| 816 |
4/4✓ Branch 0 taken 12482882 times.
✓ Branch 1 taken 1111869 times.
✓ Branch 2 taken 10840 times.
✓ Branch 3 taken 586 times.
|
13606177 | if(B1.xyz_max[c] < B2.xyz_min[c]) { |
| 817 | return false; | ||
| 818 | } | ||
| 819 |
4/4✓ Branch 0 taken 12004811 times.
✓ Branch 1 taken 478071 times.
✓ Branch 2 taken 10734 times.
✓ Branch 3 taken 106 times.
|
12493722 | if(B1.xyz_min[c] > B2.xyz_max[c]) { |
| 820 | return false; | ||
| 821 | } | ||
| 822 | } | ||
| 823 | return true; | ||
| 824 | } | ||
| 825 | |||
| 826 | /** | ||
| 827 | * \brief Computes the smallest Box that encloses two Boxes. | ||
| 828 | * \param[out] target the smallest axis-aligned box | ||
| 829 | * that encloses \p B1 and \p B2 | ||
| 830 | * \param[in] B1 first box | ||
| 831 | * \param[in] B2 second box | ||
| 832 | */ | ||
| 833 | inline void bbox_union(Box& target, const Box& B1, const Box& B2) { | ||
| 834 |
2/2✓ Branch 0 taken 985635 times.
✓ Branch 1 taken 328545 times.
|
1314180 | for(coord_index_t c = 0; c < 3; ++c) { |
| 835 | 985635 | target.xyz_min[c] = std::min(B1.xyz_min[c], B2.xyz_min[c]); | |
| 836 | 985635 | target.xyz_max[c] = std::max(B1.xyz_max[c], B2.xyz_max[c]); | |
| 837 | } | ||
| 838 | } | ||
| 839 | |||
| 840 | /*******************************************************************/ | ||
| 841 | |||
| 842 | /** | ||
| 843 | * \brief Axis-aligned bounding box. | ||
| 844 | */ | ||
| 845 | class Box2d { | ||
| 846 | public: | ||
| 847 | double xy_min[2]; | ||
| 848 | double xy_max[2]; | ||
| 849 | |||
| 850 | /** | ||
| 851 | * \brief Constructs an uninitialized Box2d | ||
| 852 | * \details Please note that the box is uninitialized. One may | ||
| 853 | * call clear() to get an initialized empty box. | ||
| 854 | */ | ||
| 855 | ✗ | Box2d() { | |
| 856 | } | ||
| 857 | |||
| 858 | /** | ||
| 859 | * \brief Constructs a box from lower and upper bounds | ||
| 860 | * \param[in] x1 , y1 the lower bounds | ||
| 861 | * \param[in] x2 , y2 the upper bounds | ||
| 862 | */ | ||
| 863 | Box2d(double x1, double y1, double x2, double y2) { | ||
| 864 | xy_min[0] = x1; | ||
| 865 | xy_min[1] = y1; | ||
| 866 | xy_max[0] = x2; | ||
| 867 | xy_max[1] = y2; | ||
| 868 | } | ||
| 869 | |||
| 870 | /** | ||
| 871 | * \brief Constructs a box from lower and upper bounds | ||
| 872 | * \param[in] lo the lower bound as a vec2 | ||
| 873 | * \param[in] hi the upper bound as a vec2 | ||
| 874 | */ | ||
| 875 | Box2d(const vec2& lo, const vec2& hi) { | ||
| 876 | xy_min[0] = lo.x; | ||
| 877 | xy_min[1] = lo.y; | ||
| 878 | xy_max[0] = hi.x; | ||
| 879 | xy_max[1] = hi.y; | ||
| 880 | } | ||
| 881 | |||
| 882 | /** | ||
| 883 | * \brief Gets the lower bounds | ||
| 884 | * \return the lower bounds as a vec2 | ||
| 885 | */ | ||
| 886 | vec2 lo() const { | ||
| 887 | return vec2(xy_min); | ||
| 888 | } | ||
| 889 | |||
| 890 | /** | ||
| 891 | * \brief Gets the higher bounds | ||
| 892 | * \return the higher bounds as a vec2 | ||
| 893 | */ | ||
| 894 | vec2 hi() const { | ||
| 895 | return vec2(xy_max); | ||
| 896 | } | ||
| 897 | |||
| 898 | /** | ||
| 899 | * \brief Tests whether a box contains a point. | ||
| 900 | * \param[in] b the point | ||
| 901 | * \return true if this box contains \p b, false otherwise | ||
| 902 | */ | ||
| 903 | bool contains(const vec2& b) const { | ||
| 904 | ✗ | for(coord_index_t c = 0; c < 2; ++c) { | |
| 905 | ✗ | if(b[c] < xy_min[c]) { | |
| 906 | return false; | ||
| 907 | } | ||
| 908 | ✗ | if(b[c] > xy_max[c]) { | |
| 909 | return false; | ||
| 910 | } | ||
| 911 | } | ||
| 912 | return true; | ||
| 913 | } | ||
| 914 | |||
| 915 | /** | ||
| 916 | * \brief Enlarges the box | ||
| 917 | * \param[in] d the amount that should be subtracted from the lower | ||
| 918 | * bounds and added to the upper bounds | ||
| 919 | */ | ||
| 920 | void enlarge(double d) { | ||
| 921 | xy_min[0] -= d; | ||
| 922 | xy_min[1] -= d; | ||
| 923 | xy_max[0] += d; | ||
| 924 | xy_max[1] += d; | ||
| 925 | } | ||
| 926 | |||
| 927 | /** | ||
| 928 | * \brief Makes this box empty | ||
| 929 | * \details Initializes the lower bounds to the greatest floating point | ||
| 930 | * number and the higher bounds to minus the greatest floating point | ||
| 931 | * number | ||
| 932 | */ | ||
| 933 | void clear() { | ||
| 934 | for(index_t c=0; c<2; ++c) { | ||
| 935 | xy_min[c] = Numeric::max_float64(); | ||
| 936 | xy_max[c] = -Numeric::max_float64(); | ||
| 937 | } | ||
| 938 | } | ||
| 939 | |||
| 940 | /** | ||
| 941 | * \brief Adds a point to this box | ||
| 942 | * \param[in] p a const reference to the point to be added | ||
| 943 | * \details The box is the smallest axis-aligned box enclosing | ||
| 944 | * all added points | ||
| 945 | */ | ||
| 946 | void add(const vec2& p) { | ||
| 947 | for(index_t c=0; c<2; ++c) { | ||
| 948 | xy_min[c] = std::min(xy_min[c], p[c]); | ||
| 949 | xy_max[c] = std::max(xy_max[c], p[c]); | ||
| 950 | } | ||
| 951 | } | ||
| 952 | }; | ||
| 953 | |||
| 954 | |||
| 955 | /** | ||
| 956 | * \brief Tests whether two Box2d have a non-empty intersection. | ||
| 957 | * \param[in] B1 first box | ||
| 958 | * \param[in] B2 second box | ||
| 959 | * \return true if \p B1 and \p B2 have a non-empty intersection, | ||
| 960 | * false otherwise. | ||
| 961 | */ | ||
| 962 | inline bool bboxes_overlap(const Box2d& B1, const Box2d& B2) { | ||
| 963 | for(coord_index_t c = 0; c < 2; ++c) { | ||
| 964 | if(B1.xy_max[c] < B2.xy_min[c]) { | ||
| 965 | return false; | ||
| 966 | } | ||
| 967 | if(B1.xy_min[c] > B2.xy_max[c]) { | ||
| 968 | return false; | ||
| 969 | } | ||
| 970 | } | ||
| 971 | return true; | ||
| 972 | } | ||
| 973 | |||
| 974 | /** | ||
| 975 | * \brief Computes the smallest Box2d that encloses two Box2d. | ||
| 976 | * \param[out] target the smallest axis-aligned box | ||
| 977 | * that encloses \p B1 and \p B2 | ||
| 978 | * \param[in] B1 first box | ||
| 979 | * \param[in] B2 second box | ||
| 980 | */ | ||
| 981 | inline void bbox_union(Box2d& target, const Box2d& B1, const Box2d& B2) { | ||
| 982 | ✗ | for(coord_index_t c = 0; c < 2; ++c) { | |
| 983 | ✗ | target.xy_min[c] = std::min(B1.xy_min[c], B2.xy_min[c]); | |
| 984 | ✗ | target.xy_max[c] = std::max(B1.xy_max[c], B2.xy_max[c]); | |
| 985 | } | ||
| 986 | } | ||
| 987 | |||
| 988 | /*******************************************************************/ | ||
| 989 | |||
| 990 | #ifndef GOMGEN | ||
| 991 | |||
| 992 | /** | ||
| 993 | * \brief Applies a 3d transform to a 3d vector. | ||
| 994 | * \details Convention is the same as in OpenGL, i.e. | ||
| 995 | * vector is a row vector, multiplied on the left | ||
| 996 | * of the transform. | ||
| 997 | * Internally, the vector is converted into | ||
| 998 | * a 4d vector, with w coordinate set to zero. | ||
| 999 | * \param[in] v the input 3d vector to be transformed | ||
| 1000 | * \param[in] M the transform, as a 4x4 matrix, using | ||
| 1001 | * homogeneous coordinates | ||
| 1002 | * \tparam FT type of the coordinates | ||
| 1003 | * \return the transformed 3d vector | ||
| 1004 | */ | ||
| 1005 | template <class FT> [[deprecated("use operators and vec3/4 conversions")]] | ||
| 1006 | inline vecng<3,FT> transform_vector( | ||
| 1007 | const vecng<3,FT>& v, const Matrix<4,FT>& M | ||
| 1008 | ) { | ||
| 1009 | return vecng<3,FT>( vecng<4,FT>(v,FT(0.0)) * M ); | ||
| 1010 | } | ||
| 1011 | |||
| 1012 | /** | ||
| 1013 | * \brief Applies a 3d transform to a 3d point. | ||
| 1014 | * \details Convention is the same as in OpenGL, i.e. | ||
| 1015 | * vector is a row vector, multiplied on the left | ||
| 1016 | * of the transform. | ||
| 1017 | * Internally, the point is converted into | ||
| 1018 | * a 4d vector, with w coordinate set to one. Transformed | ||
| 1019 | * coordinates are divided by the transformed w to form | ||
| 1020 | * a 3d point. | ||
| 1021 | * \param[in] p the input 3d point to be transformed | ||
| 1022 | * \param[in] M the transform, as a 4x4 matrix, using | ||
| 1023 | * homogeneous coordinates | ||
| 1024 | * \tparam FT type of the coordinates | ||
| 1025 | * \return the transformed 3d point | ||
| 1026 | */ | ||
| 1027 | template <class FT> [[deprecated("use operators and vec3/4 conversions")]] | ||
| 1028 | inline vecng<3,FT> transform_point( | ||
| 1029 | const vecng<3,FT>& p, const Matrix<4,FT>& M | ||
| 1030 | ) { | ||
| 1031 | vecng<4,FT> q = vecng<4,FT>(p,FT(1.0)) * M; | ||
| 1032 | return vecng<3,FT>(q.x/q.w, q.y/q.w, q.z/q.w); | ||
| 1033 | } | ||
| 1034 | |||
| 1035 | |||
| 1036 | /** | ||
| 1037 | * \brief Applies a 3d transform to a 3d point. | ||
| 1038 | * \details Convention is the same as in math, i.e. | ||
| 1039 | * vector is a column vector, multiplied on the right | ||
| 1040 | * of the transform. | ||
| 1041 | * Internally, the point is converted into | ||
| 1042 | * a 4d vector, with w coordinate set to one. Transformed | ||
| 1043 | * coordinates are divided by the transformed w to form | ||
| 1044 | * a 3d point. | ||
| 1045 | * \param[in] p the input 3d point to be transformed | ||
| 1046 | * \param[in] M the transform, as a 4x4 matrix, using | ||
| 1047 | * homogeneous coordinates | ||
| 1048 | * \tparam FT type of the coordinates | ||
| 1049 | * \return the transformed 3d point | ||
| 1050 | */ | ||
| 1051 | template <class FT> [[deprecated("use operators and vec3/4 conversions")]] | ||
| 1052 | inline vecng<3,FT> transform_point( | ||
| 1053 | const Matrix<4,FT>& M, const vecng<3,FT>& p | ||
| 1054 | ) { | ||
| 1055 | vecng<4,FT> q = M * vecng<4,FT>(p,FT(1.0)); | ||
| 1056 | return vecng<3,FT>(q.x/q.w, q.y/q.w, q.z/q.w); | ||
| 1057 | } | ||
| 1058 | |||
| 1059 | /** | ||
| 1060 | * \brief Applies a 4d transform to a 4d vector. | ||
| 1061 | * \details Convention is the same as in OpenGL, i.e. | ||
| 1062 | * vector is a row vector, multiplied on the left | ||
| 1063 | * of the transform. | ||
| 1064 | * \param[in] v the input 4d vector to be transformed | ||
| 1065 | * \param[in] M the transform, as a 4x4 matrix | ||
| 1066 | * \tparam FT type of the coordinates | ||
| 1067 | * \return the transformed 4d vector | ||
| 1068 | */ | ||
| 1069 | template <class FT> [[deprecated("use operators and vec3/4 conversions")]] | ||
| 1070 | inline vecng<4,FT> transform_vector( | ||
| 1071 | const vecng<4,FT>& v, const Matrix<4,FT>& M | ||
| 1072 | ) { | ||
| 1073 | return v*M; | ||
| 1074 | } | ||
| 1075 | |||
| 1076 | #endif | ||
| 1077 | |||
| 1078 | /******************************************************************/ | ||
| 1079 | |||
| 1080 | /** | ||
| 1081 | * \brief Creates a translation matrix from a vector. | ||
| 1082 | * \details The translation matrix is in homogeneous coordinates, | ||
| 1083 | * with the same convention as OpenGL (transforms row vectors | ||
| 1084 | * mutliplied on the left). | ||
| 1085 | * \param[in] T a const reference to the translation vector | ||
| 1086 | * \return the translation matrix | ||
| 1087 | */ | ||
| 1088 | inline mat4 create_translation_matrix(const vec3& T) { | ||
| 1089 | mat4 result; | ||
| 1090 | result.load_identity(); | ||
| 1091 | result(3,0) = T.x; | ||
| 1092 | result(3,1) = T.y; | ||
| 1093 | result(3,2) = T.z; | ||
| 1094 | return result; | ||
| 1095 | } | ||
| 1096 | |||
| 1097 | /** | ||
| 1098 | * \brief Creates a scaling matrix. | ||
| 1099 | * \details The scaling matrix is in homogeneous coordinates, | ||
| 1100 | * with the same convention as OpenGL (transforms row vectors | ||
| 1101 | * mutliplied on the left). | ||
| 1102 | * \param[in] s the scaling coefficient | ||
| 1103 | * \return the scaling matrix | ||
| 1104 | */ | ||
| 1105 | inline mat4 create_scaling_matrix(double s) { | ||
| 1106 | mat4 result; | ||
| 1107 | result.load_identity(); | ||
| 1108 | result(0,0) = s; | ||
| 1109 | result(1,1) = s; | ||
| 1110 | result(2,2) = s; | ||
| 1111 | return result; | ||
| 1112 | } | ||
| 1113 | |||
| 1114 | /******************************************************************/ | ||
| 1115 | |||
| 1116 | /** | ||
| 1117 | * \brief A Ray, in parametric form. | ||
| 1118 | */ | ||
| 1119 | struct Ray { | ||
| 1120 | /** | ||
| 1121 | * \brief Ray constructor. | ||
| 1122 | * \param[in] O the origin of the ray. | ||
| 1123 | * \param[in] D the direction of the ray. | ||
| 1124 | */ | ||
| 1125 |
4/10✓ Branch 1 taken 279 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 34719 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 69713 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 279 times.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
|
209980 | Ray(vec3 O, vec3 D) : origin(O), direction(D) { |
| 1126 | } | ||
| 1127 | /** | ||
| 1128 | * \brief Ray constructor. | ||
| 1129 | */ | ||
| 1130 | Ray() { | ||
| 1131 | } | ||
| 1132 | vec3 origin; | ||
| 1133 | vec3 direction; | ||
| 1134 | }; | ||
| 1135 | |||
| 1136 | /******************************************************************/ | ||
| 1137 | |||
| 1138 | } | ||
| 1139 | |||
| 1140 | #endif | ||
| 1141 |