1 // Copyright (c) 2008 INRIA Sophia-Antipolis (France).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/AABB_tree/include/CGAL/internal/AABB_tree/AABB_node.h $
7 // $Id: AABB_node.h 7938060 2020-09-22T15:47:26+02:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Camille Wormser, Pierre Alliez, Stephane Tayeb
12
13 #ifndef CGAL_AABB_NODE_H
14 #define CGAL_AABB_NODE_H
15
16 #include <CGAL/license/AABB_tree.h>
17
18
19 #include <CGAL/Profile_counter.h>
20 #include <CGAL/Cartesian_converter.h>
21 #include <CGAL/intersections.h>
22 #include <CGAL/Bbox_3.h>
23 #include <vector>
24
25 namespace CGAL {
26
27 /**
28 * @class AABB_node
29 *
30 *
31 */
32 template<typename AABBTraits>
33 class AABB_node
34 {
35 private:
36 typedef AABB_node<AABBTraits> Self;
37
38 public:
39 typedef typename AABBTraits::Bounding_box Bounding_box;
40
41 /// Constructor
AABB_node()42 AABB_node()
43 : m_bbox()
44 , m_p_left_child(nullptr)
45 , m_p_right_child(nullptr) { };
46
47 AABB_node(Self&& node) = default;
48
49 // Disabled copy constructor & assignment operator
50 AABB_node(const Self& src) = delete;
51 Self& operator=(const Self& src) = delete;
52
53 /// Returns the bounding box of the node
bbox()54 const Bounding_box& bbox() const { return m_bbox; }
55
56 /**
57 * @brief General traversal query
58 * @param query the query
59 * @param traits the traversal traits that define the traversal behaviour
60 * @param nb_primitives the number of primitive
61 *
62 * General traversal query. The traits class allows using it for the various
63 * traversal methods we need: listing, counting, detecting intersections,
64 * drawing the boxes.
65 */
66 template<class Traversal_traits, class Query>
67 void traversal(const Query& query,
68 Traversal_traits& traits,
69 const std::size_t nb_primitives) const;
70
71 private:
72 typedef AABBTraits AABB_traits;
73 typedef AABB_node<AABB_traits> Node;
74 typedef typename AABB_traits::Primitive Primitive;
75
76
77 public:
78 /// Helper functions
left_child()79 const Node& left_child() const
80 { return *static_cast<Node*>(m_p_left_child); }
right_child()81 const Node& right_child() const
82 { return *static_cast<Node*>(m_p_right_child); }
left_data()83 const Primitive& left_data() const
84 { return *static_cast<Primitive*>(m_p_left_child); }
right_data()85 const Primitive& right_data() const
86 { return *static_cast<Primitive*>(m_p_right_child); }
87 template <class Left, class Right>
set_children(Left & l,Right & r)88 void set_children(Left& l, Right& r)
89 {
90 m_p_left_child = static_cast<void*>(std::addressof(l));
91 m_p_right_child = static_cast<void*>(std::addressof(r));
92 }
set_bbox(const Bounding_box & bbox)93 void set_bbox(const Bounding_box& bbox)
94 {
95 m_bbox = bbox;
96 }
97
left_child()98 Node& left_child() { return *static_cast<Node*>(m_p_left_child); }
right_child()99 Node& right_child() { return *static_cast<Node*>(m_p_right_child); }
left_data()100 Primitive& left_data() { return *static_cast<Primitive*>(m_p_left_child); }
right_data()101 Primitive& right_data() { return *static_cast<Primitive*>(m_p_right_child); }
102
103 private:
104 /// node bounding box
105 Bounding_box m_bbox;
106
107 /// children nodes, either pointing towards children (if children are not leaves),
108 /// or pointing toward input primitives (if children are leaves).
109 void *m_p_left_child;
110 void *m_p_right_child;
111
112 }; // end class AABB_node
113
114
115 template<typename Tr>
116 template<class Traversal_traits, class Query>
117 void
traversal(const Query & query,Traversal_traits & traits,const std::size_t nb_primitives)118 AABB_node<Tr>::traversal(const Query& query,
119 Traversal_traits& traits,
120 const std::size_t nb_primitives) const
121 {
122 // Recursive traversal
123 switch(nb_primitives)
124 {
125 case 2:
126 traits.intersection(query, left_data());
127 if( traits.go_further() )
128 {
129 traits.intersection(query, right_data());
130 }
131 break;
132 case 3:
133 traits.intersection(query, left_data());
134 if( traits.go_further() && traits.do_intersect(query, right_child()) )
135 {
136 right_child().traversal(query, traits, 2);
137 }
138 break;
139 default:
140 if( traits.do_intersect(query, left_child()) )
141 {
142 left_child().traversal(query, traits, nb_primitives/2);
143 if( traits.go_further() && traits.do_intersect(query, right_child()) )
144 {
145 right_child().traversal(query, traits, nb_primitives-nb_primitives/2);
146 }
147 }
148 else if( traits.do_intersect(query, right_child()) )
149 {
150 right_child().traversal(query, traits, nb_primitives-nb_primitives/2);
151 }
152 }
153 }
154
155 } // end namespace CGAL
156
157 #endif // CGAL_AABB_NODE_H
158