1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#include <iostream>
#include <boost/iterator.hpp>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
typedef CGAL::Simple_cartesian<double> K;
// The points are stored in a flat array of doubles
// The triangles are stored in a flat array of indices
// referring to an array of coordinates: three consecutive
// coordinates represent a point, and three consecutive
// indices represent a triangle.
typedef size_t* Point_index_iterator;
// Let us now define the iterator on triangles that the tree needs:
class Triangle_iterator
: public boost::iterator_adaptor<
Triangle_iterator // Derived
, Point_index_iterator // Base
, boost::use_default // Value
, boost::forward_traversal_tag // CategoryOrTraversal
>
{
public:
Triangle_iterator()
: Triangle_iterator::iterator_adaptor_() {}
explicit Triangle_iterator(Point_index_iterator p)
: Triangle_iterator::iterator_adaptor_(p) {}
private:
friend class boost::iterator_core_access;
void increment() { this->base_reference() += 3; }
};
// The following primitive provides the conversion facilities between
// my own triangle and point types and the CGAL ones
struct My_triangle_primitive {
public:
typedef Triangle_iterator Id;
// the CGAL types returned
typedef K::Point_3 Point;
typedef K::Triangle_3 Datum;
// a static pointer to the vector containing the points
// is needed to build the triangles on the fly:
static const double* point_container;
private:
Id m_it; // this is what the AABB tree stores internally
public:
My_triangle_primitive() {} // default constructor needed
// the following constructor is the one that receives the iterators from the
// iterator range given as input to the AABB_tree
My_triangle_primitive(Triangle_iterator a)
: m_it(a) {}
Id id() const { return m_it; }
// on the fly conversion from the internal data to the CGAL types
Datum datum() const
{
Point_index_iterator p_it = m_it.base();
Point p(*(point_container + 3 * (*p_it)),
*(point_container + 3 * (*p_it) + 1),
*(point_container + 3 * (*p_it) + 2) );
++p_it;
Point q(*(point_container + 3 * (*p_it)),
*(point_container + 3 * (*p_it) + 1),
*(point_container + 3 * (*p_it) + 2));
++p_it;
Point r(*(point_container + 3 * (*p_it)),
*(point_container + 3 * (*p_it) + 1),
*(point_container + 3 * (*p_it) + 2));
return Datum(p, q, r); // assembles triangle from three points
}
// one point which must be on the primitive
Point reference_point() const
{
return Point(*(point_container + 3 * (*m_it)),
*(point_container + 3 * (*m_it) + 1),
*(point_container + 3 * (*m_it) + 2));
}
};
// types
typedef CGAL::AABB_traits<K, My_triangle_primitive> My_AABB_traits;
typedef CGAL::AABB_tree<My_AABB_traits> Tree;
const double* My_triangle_primitive::point_container = 0;
int main()
{
// generates point set
double points[12];
My_triangle_primitive::point_container = points;
points[0] = 1.0; points[1] = 0.0; points[2] = 0.0;
points[3] = 0.0; points[4] = 1.0; points[5] = 0.0;
points[6] = 0.0; points[7] = 0.0; points[8] = 1.0;
points[9] = 0.0; points[10] = 0.0; points[11] = 0.0;
// generates indexed triangle set
size_t triangles[9];
triangles[0] = 0; triangles[1] = 1; triangles[2] = 2;
triangles[3] = 0; triangles[4] = 1; triangles[5] = 3;
triangles[6] = 0; triangles[7] = 3; triangles[8] = 2;
// constructs AABB tree
Tree tree(Triangle_iterator(triangles),
Triangle_iterator(triangles+9));
// counts #intersections
K::Ray_3 ray_query(K::Point_3(0.2, 0.2, 0.2), K::Point_3(0.0, 1.0, 0.0));
std::cout << tree.number_of_intersected_primitives(ray_query)
<< " intersections(s) with ray query" << std::endl;
// computes closest point
K::Point_3 point_query(2.0, 2.0, 2.0);
K::Point_3 closest_point = tree.closest_point(point_query);
std::cout << "closest point to " << point_query << " is: " << closest_point.x() << " " << closest_point.y() << " " << closest_point.z() << std::endl;
return EXIT_SUCCESS;
}
|
