libigl v2.5.0
Loading...
Searching...
No Matches
AABB.h
Go to the documentation of this file.
1// This file is part of libigl, a simple c++ geometry processing library.
2//
3// Copyright (C) 2015 Alec Jacobson <alecjacobson@gmail.com>
4//
5// This Source Code Form is subject to the terms of the Mozilla Public License
6// v. 2.0. If a copy of the MPL was not distributed with this file, You can
7// obtain one at http://mozilla.org/MPL/2.0/.
8#ifndef IGL_AABB_H
9#define IGL_AABB_H
10
11#include "Hit.h"
12#include "igl_inline.h"
13#include <Eigen/Core>
14#include <Eigen/Geometry>
15#include <vector>
16namespace igl
17{
28 template <typename DerivedV, int DIM>
29 class AABB
30 {
31public:
33 typedef typename DerivedV::Scalar Scalar;
35 typedef Eigen::Matrix<Scalar,1,DIM> RowVectorDIMS;
37 typedef Eigen::Matrix<Scalar,DIM,1> VectorDIMS;
39 typedef Eigen::Matrix<Scalar,Eigen::Dynamic,DIM> MatrixXDIMS;
41 // Shared pointers are slower...
42 AABB * m_left;
44 AABB * m_right;
46 Eigen::AlignedBox<Scalar,DIM> m_box;
48 int m_primitive;
49 //Scalar m_low_sqr_d;
50 //int m_depth;
52 AABB():
53 m_left(NULL), m_right(NULL),
54 m_box(), m_primitive(-1)
55 //m_low_sqr_d(std::numeric_limits<double>::infinity()),
56 //m_depth(0)
57 {
58 static_assert(DerivedV::ColsAtCompileTime == DIM || DerivedV::ColsAtCompileTime == Eigen::Dynamic,"DerivedV::ColsAtCompileTime == DIM || DerivedV::ColsAtCompileTime == Eigen::Dynamic");
59 }
61 // http://stackoverflow.com/a/3279550/148668
62 AABB(const AABB& other):
63 m_left(other.m_left ? new AABB(*other.m_left) : NULL),
64 m_right(other.m_right ? new AABB(*other.m_right) : NULL),
65 m_box(other.m_box),
66 m_primitive(other.m_primitive)
67 //m_low_sqr_d(other.m_low_sqr_d),
68 //m_depth(std::max(
69 // m_left ? m_left->m_depth + 1 : 0,
70 // m_right ? m_right->m_depth + 1 : 0))
71 {
72 }
74 // copy-swap idiom
75 friend void swap(AABB& first, AABB& second)
76 {
77 // Enable ADL
78 using std::swap;
79 swap(first.m_left,second.m_left);
80 swap(first.m_right,second.m_right);
81 swap(first.m_box,second.m_box);
82 swap(first.m_primitive,second.m_primitive);
83 //swap(first.m_low_sqr_d,second.m_low_sqr_d);
84 //swap(first.m_depth,second.m_depth);
85 }
87 // Pass-by-value (aka copy)
88 AABB& operator=(AABB other)
89 {
90 swap(*this,other);
91 return *this;
92 }
94 AABB(AABB&& other):
95 // initialize via default constructor
96 AABB()
97 {
98 swap(*this,other);
99 }
101 // Seems like there should have been an elegant solution to this using
102 // the copy-swap idiom above:
103 IGL_INLINE void deinit()
104 {
105 m_primitive = -1;
106 m_box = Eigen::AlignedBox<Scalar,DIM>();
107 delete m_left;
108 m_left = NULL;
109 delete m_right;
110 m_right = NULL;
111 }
113 ~AABB()
114 {
115 deinit();
116 }
126 template <
127 typename DerivedEle,
128 typename Derivedbb_mins,
129 typename Derivedbb_maxs,
130 typename Derivedelements>
131 IGL_INLINE void init(
132 const Eigen::MatrixBase<DerivedV> & V,
133 const Eigen::MatrixBase<DerivedEle> & Ele,
134 const Eigen::MatrixBase<Derivedbb_mins> & bb_mins,
135 const Eigen::MatrixBase<Derivedbb_maxs> & bb_maxs,
136 const Eigen::MatrixBase<Derivedelements> & elements,
137 const int i = 0);
143 template <typename DerivedEle>
144 IGL_INLINE void init(
145 const Eigen::MatrixBase<DerivedV> & V,
146 const Eigen::MatrixBase<DerivedEle> & Ele);
158 template <typename DerivedEle, typename DerivedSI, typename DerivedI>
159 IGL_INLINE void init(
160 const Eigen::MatrixBase<DerivedV> & V,
161 const Eigen::MatrixBase<DerivedEle> & Ele,
162 const Eigen::MatrixBase<DerivedSI> & SI,
163 const Eigen::MatrixBase<DerivedI>& I);
165 IGL_INLINE bool is_leaf() const;
176 template <typename DerivedEle, typename Derivedq>
177 IGL_INLINE std::vector<int> find(
178 const Eigen::MatrixBase<DerivedV> & V,
179 const Eigen::MatrixBase<DerivedEle> & Ele,
180 const Eigen::MatrixBase<Derivedq> & q,
181 const bool first=false) const;
182
187 IGL_INLINE int subtree_size() const;
188
195 template <
196 typename Derivedbb_mins,
197 typename Derivedbb_maxs,
198 typename Derivedelements>
199 IGL_INLINE void serialize(
200 Eigen::PlainObjectBase<Derivedbb_mins> & bb_mins,
201 Eigen::PlainObjectBase<Derivedbb_maxs> & bb_maxs,
202 Eigen::PlainObjectBase<Derivedelements> & elements,
203 const int i = 0) const;
215 template <typename DerivedEle>
216 IGL_INLINE Scalar squared_distance(
217 const Eigen::MatrixBase<DerivedV> & V,
218 const Eigen::MatrixBase<DerivedEle> & Ele,
219 const RowVectorDIMS & p,
220 int & i,
221 Eigen::PlainObjectBase<RowVectorDIMS> & c) const;
239 template <typename DerivedEle>
240 IGL_INLINE Scalar squared_distance(
241 const Eigen::MatrixBase<DerivedV> & V,
242 const Eigen::MatrixBase<DerivedEle> & Ele,
243 const RowVectorDIMS & p,
244 const Scalar low_sqr_d,
245 const Scalar up_sqr_d,
246 int & i,
247 Eigen::PlainObjectBase<RowVectorDIMS> & c) const;
260 template <typename DerivedEle>
261 IGL_INLINE Scalar squared_distance(
262 const Eigen::MatrixBase<DerivedV> & V,
263 const Eigen::MatrixBase<DerivedEle> & Ele,
264 const RowVectorDIMS & p,
265 const Scalar up_sqr_d,
266 int & i,
267 Eigen::PlainObjectBase<RowVectorDIMS> & c) const;
276 template <typename DerivedEle>
277 IGL_INLINE bool intersect_ray(
278 const Eigen::MatrixBase<DerivedV> & V,
279 const Eigen::MatrixBase<DerivedEle> & Ele,
280 const RowVectorDIMS & origin,
281 const RowVectorDIMS & dir,
282 std::vector<igl::Hit> & hits) const;
291 template <typename DerivedEle>
292 IGL_INLINE bool intersect_ray(
293 const Eigen::MatrixBase<DerivedV> & V,
294 const Eigen::MatrixBase<DerivedEle> & Ele,
295 const RowVectorDIMS & origin,
296 const RowVectorDIMS & dir,
297 igl::Hit & hit) const;
307 template <typename DerivedEle>
308 IGL_INLINE bool intersect_ray(
309 const Eigen::MatrixBase<DerivedV> & V,
310 const Eigen::MatrixBase<DerivedEle> & Ele,
311 const RowVectorDIMS & origin,
312 const RowVectorDIMS & dir,
313 const Scalar min_t,
314 igl::Hit & hit) const;
315
316public:
327 template <
328 typename DerivedEle,
329 typename DerivedP,
330 typename DerivedsqrD,
331 typename DerivedI,
332 typename DerivedC>
333 IGL_INLINE void squared_distance(
334 const Eigen::MatrixBase<DerivedV> & V,
335 const Eigen::MatrixBase<DerivedEle> & Ele,
336 const Eigen::MatrixBase<DerivedP> & P,
337 Eigen::PlainObjectBase<DerivedsqrD> & sqrD,
338 Eigen::PlainObjectBase<DerivedI> & I,
339 Eigen::PlainObjectBase<DerivedC> & C) const;
340
354 template <
355 typename DerivedEle,
356 typename Derivedother_V,
357 typename Derivedother_Ele,
358 typename DerivedsqrD,
359 typename DerivedI,
360 typename DerivedC>
361 IGL_INLINE void squared_distance(
362 const Eigen::MatrixBase<DerivedV> & V,
363 const Eigen::MatrixBase<DerivedEle> & Ele,
364 const AABB<Derivedother_V,DIM> & other,
365 const Eigen::MatrixBase<Derivedother_V> & other_V,
366 const Eigen::MatrixBase<Derivedother_Ele> & other_Ele,
367 Eigen::PlainObjectBase<DerivedsqrD> & sqrD,
368 Eigen::PlainObjectBase<DerivedI> & I,
369 Eigen::PlainObjectBase<DerivedC> & C) const;
370private:
371 template <
372 typename DerivedEle,
373 typename Derivedother_V,
374 typename Derivedother_Ele,
375 typename DerivedsqrD,
376 typename DerivedI,
377 typename DerivedC>
378 IGL_INLINE Scalar squared_distance_helper(
379 const Eigen::MatrixBase<DerivedV> & V,
380 const Eigen::MatrixBase<DerivedEle> & Ele,
381 const AABB<Derivedother_V,DIM> * other,
382 const Eigen::MatrixBase<Derivedother_V> & other_V,
383 const Eigen::MatrixBase<Derivedother_Ele>& other_Ele,
384 const Scalar up_sqr_d,
385 Eigen::PlainObjectBase<DerivedsqrD> & sqrD,
386 Eigen::PlainObjectBase<DerivedI> & I,
387 Eigen::PlainObjectBase<DerivedC> & C) const;
388 // Compute the squared distance to the primitive in this node: assumes
389 // that this is indeed a leaf node.
390 //
391 // Inputs:
392 // V #V by dim list of vertex positions
393 // Ele #Ele by dim list of simplex indices
394 // p dim-long query point
395 // sqr_d current minimum distance for this query, see output
396 // i current index into Ele of closest point, see output
397 // c dim-long current closest point, see output
398 // Outputs:
399 // sqr_d minimum of initial value and squared distance to this
400 // primitive
401 // i possibly updated index into Ele of closest point
402 // c dim-long possibly updated closest point
403 template <typename DerivedEle>
404 IGL_INLINE void leaf_squared_distance(
405 const Eigen::MatrixBase<DerivedV> & V,
406 const Eigen::MatrixBase<DerivedEle> & Ele,
407 const RowVectorDIMS & p,
408 const Scalar low_sqr_d,
409 Scalar & sqr_d,
410 int & i,
411 Eigen::PlainObjectBase<RowVectorDIMS> & c) const;
412 // Default low_sqr_d
413 template <typename DerivedEle>
414 IGL_INLINE void leaf_squared_distance(
415 const Eigen::MatrixBase<DerivedV> & V,
416 const Eigen::MatrixBase<DerivedEle> & Ele,
417 const RowVectorDIMS & p,
418 Scalar & sqr_d,
419 int & i,
420 Eigen::PlainObjectBase<RowVectorDIMS> & c) const;
421 // If new distance (sqr_d_candidate) is less than current distance
422 // (sqr_d), then update this distance and its associated values
423 // _in-place_:
424 //
425 // Inputs:
426 // p dim-long query point (only used in DEBUG mode)
427 // sqr_d candidate minimum distance for this query, see output
428 // i candidate index into Ele of closest point, see output
429 // c dim-long candidate closest point, see output
430 // sqr_d current minimum distance for this query, see output
431 // i current index into Ele of closest point, see output
432 // c dim-long current closest point, see output
433 // Outputs:
434 // sqr_d minimum of initial value and squared distance to this
435 // primitive
436 // i possibly updated index into Ele of closest point
437 // c dim-long possibly updated closest point
438 IGL_INLINE void set_min(
439 const RowVectorDIMS & p,
440 const Scalar sqr_d_candidate,
441 const int i_candidate,
442 const RowVectorDIMS & c_candidate,
443 Scalar & sqr_d,
444 int & i,
445 Eigen::PlainObjectBase<RowVectorDIMS> & c) const;
446
455 template <typename DerivedEle>
456 IGL_INLINE bool intersect_ray_opt(
457 const Eigen::MatrixBase<DerivedV> & V,
458 const Eigen::MatrixBase<DerivedEle> & Ele,
459 const RowVectorDIMS & origin,
460 const RowVectorDIMS & dir,
461 const RowVectorDIMS & inv_dir,
462 const RowVectorDIMS & inv_dir_pad,
463 std::vector<igl::Hit> & hits) const;
473 template <typename DerivedEle>
474 IGL_INLINE bool intersect_ray_opt(
475 const Eigen::MatrixBase<DerivedV> & V,
476 const Eigen::MatrixBase<DerivedEle> & Ele,
477 const RowVectorDIMS & origin,
478 const RowVectorDIMS & dir,
479 const RowVectorDIMS & inv_dir,
480 const RowVectorDIMS & inv_dir_pad,
481 const Scalar min_t,
482 igl::Hit & hit) const;
483public:
484 EIGEN_MAKE_ALIGNED_OPERATOR_NEW
485 };
486}
487
488
489#ifndef IGL_STATIC_LIBRARY
490# include "AABB.cpp"
491#endif
492
493#endif
igl::AABB
Implementation of semi-general purpose axis-aligned bounding box hierarchy.
Definition AABB.h:30
igl::AABB::find
IGL_INLINE std::vector< int > find(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< Derivedq > &q, const bool first=false) const
Find the indices of elements containing given point: this makes sense when Ele is a co-dimension 0 si...
igl::AABB::VectorDIMS
Eigen::Matrix< Scalar, DIM, 1 > VectorDIMS
Fixed-size (DIM) (Column)Vector type using Scalar
Definition AABB.h:37
igl::AABB::init
IGL_INLINE void init(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< Derivedbb_mins > &bb_mins, const Eigen::MatrixBase< Derivedbb_maxs > &bb_maxs, const Eigen::MatrixBase< Derivedelements > &elements, const int i=0)
Build an Axis-Aligned Bounding Box tree for a given mesh and given serialization of a previous AABB t...
igl::AABB::squared_distance
IGL_INLINE void squared_distance(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const AABB< Derivedother_V, DIM > &other, const Eigen::MatrixBase< Derivedother_V > &other_V, const Eigen::MatrixBase< Derivedother_Ele > &other_Ele, Eigen::PlainObjectBase< DerivedsqrD > &sqrD, Eigen::PlainObjectBase< DerivedI > &I, Eigen::PlainObjectBase< DerivedC > &C) const
Compute the squared distance from all query points in P already stored in its own AABB hierarchy to t...
igl::AABB::m_left
AABB * m_left
Pointer to "left" child node (nullptr if leaf)
Definition AABB.h:42
igl::AABB::is_leaf
IGL_INLINE bool is_leaf() const
Return whether at leaf node.
igl::AABB::m_primitive
int m_primitive
Index of single primitive in this node if full leaf, otherwise -1 for non-leaf.
Definition AABB.h:48
igl::AABB::squared_distance
IGL_INLINE void squared_distance(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< DerivedP > &P, Eigen::PlainObjectBase< DerivedsqrD > &sqrD, Eigen::PlainObjectBase< DerivedI > &I, Eigen::PlainObjectBase< DerivedC > &C) const
Compute the squared distance from all query points in P to the closest points on the primitives store...
igl::AABB::Scalar
DerivedV::Scalar Scalar
Scalar type of vertex positions (e.g., double)
Definition AABB.h:33
igl::AABB::init
IGL_INLINE void init(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele)
Build an Axis-Aligned Bounding Box tree for a given mesh and given serialization of a previous AABB t...
igl::AABB::intersect_ray
IGL_INLINE bool intersect_ray(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &origin, const RowVectorDIMS &dir, igl::Hit &hit) const
Intersect a ray with the mesh return first hit.
igl::AABB::intersect_ray
IGL_INLINE bool intersect_ray(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &origin, const RowVectorDIMS &dir, const Scalar min_t, igl::Hit &hit) const
Intersect a ray with the mesh return first hit farther than min_t
igl::AABB::init
IGL_INLINE void init(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< DerivedSI > &SI, const Eigen::MatrixBase< DerivedI > &I)
Build an Axis-Aligned Bounding Box tree for a given mesh.
igl::AABB::squared_distance
IGL_INLINE Scalar squared_distance(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &p, int &i, Eigen::PlainObjectBase< RowVectorDIMS > &c) const
Compute squared distance to a query point.
igl::AABB::swap
friend void swap(AABB &first, AABB &second)
Definition AABB.h:75
igl::AABB::m_right
AABB * m_right
Pointer to "right" child node (nullptr if leaf)
Definition AABB.h:44
igl::AABB::subtree_size
IGL_INLINE int subtree_size() const
Number of nodes contained in subtree.
igl::AABB::MatrixXDIMS
Eigen::Matrix< Scalar, Eigen::Dynamic, DIM > MatrixXDIMS
Fixed-width (DIM) Matrix type using Scalar
Definition AABB.h:39
igl::AABB::squared_distance
IGL_INLINE Scalar squared_distance(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &p, const Scalar low_sqr_d, const Scalar up_sqr_d, int &i, Eigen::PlainObjectBase< RowVectorDIMS > &c) const
Compute squared distance to a query point if within low_sqr_d and up_sqr_d.
igl::AABB::intersect_ray
IGL_INLINE bool intersect_ray(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &origin, const RowVectorDIMS &dir, std::vector< igl::Hit > &hits) const
Intersect a ray with the mesh return all hits.
igl::AABB::RowVectorDIMS
Eigen::Matrix< Scalar, 1, DIM > RowVectorDIMS
Fixed-size (DIM) RowVector type using Scalar
Definition AABB.h:35
igl::AABB::squared_distance
IGL_INLINE Scalar squared_distance(const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &p, const Scalar up_sqr_d, int &i, Eigen::PlainObjectBase< RowVectorDIMS > &c) const
Compute squared distance to a query point (default low_sqr_d)
igl::AABB::serialize
IGL_INLINE void serialize(Eigen::PlainObjectBase< Derivedbb_mins > &bb_mins, Eigen::PlainObjectBase< Derivedbb_maxs > &bb_maxs, Eigen::PlainObjectBase< Derivedelements > &elements, const int i=0) const
Serialize this class into 3 arrays (so we can pass it pack to matlab)
igl::AABB::m_box
Eigen::AlignedBox< Scalar, DIM > m_box
Axis-Aligned Bounding Box containing this node.
Definition AABB.h:46
igl_inline.h
IGL_INLINE
#define IGL_INLINE
Definition igl_inline.h:15
igl
Definition AABB.h:17
igl::Hit
Reimplementation of the embree::Hit struct from embree1.0.
Definition Hit.h:18