Lagrange
All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Modules Pages
EdgeAABBTree.h
1/*
2 * Copyright 2020 Adobe. All rights reserved.
3 * This file is licensed to you under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License. You may obtain a copy
5 * of the License at http://www.apache.org/licenses/LICENSE-2.0
6 *
7 * Unless required by applicable law or agreed to in writing, software distributed under
8 * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR REPRESENTATIONS
9 * OF ANY KIND, either express or implied. See the License for the specific language
10 * governing permissions and limitations under the License.
11 */
12#pragma once
13
14#include <lagrange/common.h>
15
16#include <Eigen/Core>
17#include <Eigen/Geometry>
18
19namespace lagrange {
20namespace bvh {
21
22// AABB tree for an edge graph
23template <typename VertexArray, typename EdgeArray, int DIM = 3>
25{
26 using Scalar = typename VertexArray::Scalar;
27 using Index = typename EdgeArray::Scalar;
28 using AlignedBoxType = Eigen::AlignedBox<Scalar, DIM>;
29 using RowVectorType = Eigen::Matrix<Scalar, 1, DIM>;
30
31 struct Node
32 {
33 AlignedBoxType bbox; //<< Node bounding box.
34 Index parent = invalid<Index>();
35 Index left = invalid<Index>();
36 Index right = invalid<Index>();
37 Index index = invalid<Index>();
38
39 bool is_leaf() const { return left == invalid<Index>(); }
40 };
41
42private:
43 const VertexArray *m_vertices = nullptr;
44 const EdgeArray *m_edges = nullptr;
45
46 std::vector<Node> m_nodes;
47 size_t m_root;
48
49public:
51 using ActionCallback = std::function<void(Scalar, Index, const RowVectorType &)>;
52
53 EdgeAABBTree() = default; // Default empty constructor
54
61 EdgeAABBTree(const VertexArray &V, const EdgeArray &E);
62
68 bool empty() const { return m_nodes.empty(); }
69
79 const RowVectorType &p,
80 Index element_id,
81 RowVectorType &closest_point,
82 Scalar &closest_sq_dist) const;
83
91 void foreach_element_in_radius(const RowVectorType &p, Scalar sq_dist, ActionCallback func)
92 const;
93
104 void foreach_element_containing(const RowVectorType &p, ActionCallback func) const;
105
120 const RowVectorType &p,
121 Index &element_id,
122 RowVectorType &closest_point,
123 Scalar &closest_sq_dist,
124 std::function<bool(Index)> filter_func = nullptr) const;
125
126protected:
127 void foreach_element_in_radius_recursive(
128 const RowVectorType &p,
129 Scalar sq_dist,
130 Index node_id,
131 ActionCallback func) const;
132
133 void foreach_element_containing_recursive(
134 const RowVectorType &p,
135 Index node_id,
136 ActionCallback func) const;
137};
138
139} // namespace bvh
140} // namespace lagrange
141
142// Templated definitions
143#include <lagrange/bvh/EdgeAABBTree.impl.h>
Main namespace for Lagrange.
Definition: AABBIGL.h:30
Definition: EdgeAABBTree.h:32
Index parent
Index of the parent node (INVALID for root).
Definition: EdgeAABBTree.h:34
Index index
Edge id for the leaf (INVALID for internal nodes).
Definition: EdgeAABBTree.h:37
Index right
Index of the right child (INVALID for a leaf).
Definition: EdgeAABBTree.h:36
Index left
Index of the left child (INVALID for a leaf).
Definition: EdgeAABBTree.h:35
Definition: EdgeAABBTree.h:25
void get_element_closest_point(const RowVectorType &p, Index element_id, RowVectorType &closest_point, Scalar &closest_sq_dist) const
Gets the closest point to a given element.
Definition: EdgeAABBTree.impl.h:198
bool empty() const
Test whether the tree is empty.
Definition: EdgeAABBTree.h:68
void foreach_element_containing(const RowVectorType &p, ActionCallback func) const
Iterate over edges that contain exactly a given query point.
Definition: EdgeAABBTree.impl.h:259
void foreach_element_in_radius(const RowVectorType &p, Scalar sq_dist, ActionCallback func) const
Iterate over edges within a prescribed distance from a query point.
Definition: EdgeAABBTree.impl.h:217
std::function< void(Scalar, Index, const RowVectorType &)> ActionCallback
closest_sq_dist x element_id x closest_point
Definition: EdgeAABBTree.h:51
void get_closest_point(const RowVectorType &p, Index &element_id, RowVectorType &closest_point, Scalar &closest_sq_dist, std::function< bool(Index)> filter_func=nullptr) const
Gets the closest point to an element of the tree.
Definition: EdgeAABBTree.impl.h:298