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
139
140
141
142
143
144
145
146
147
|
// Copyright (c) 2009 INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: $
// $Id: $
//
//
// Author(s) : Camille Wormser, Pierre Alliez
//
//******************************************************************************
// File Description : Example of AABB tree used with a simple list of
// triangles (a triangle soup) stored into an array of points.
//
//******************************************************************************
#include <iostream>
#include <list>
#include <boost/iterator.hpp>
#include <CGAL/AABB_tree.h> // must be inserted before kernel
#include <CGAL/AABB_traits.h>
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double> K;
// My own point type
struct My_point {
double x;
double y;
double z;
My_point (double _x, double _y, double _z) : x(_x), y(_y), z(_z) {}
};
// The triangles are stored in a flat vector of points (a triangle soup):
// three consecutive points represent a triangle
typedef std::vector<My_point>::const_iterator Point_iterator;
// defines the iterator over triangles needed by the tree:
class Triangle_iterator
: public boost::iterator_adaptor<
Triangle_iterator // Derived
, Point_iterator // Base
, boost::use_default // Value
, boost::forward_traversal_tag // CategoryOrTraversal
>
{
public:
Triangle_iterator()
: Triangle_iterator::iterator_adaptor_() {}
explicit Triangle_iterator(Point_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;
private:
Id m_it; // this is what the AABB tree will store 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_iterator p_it = m_it.base();
Point p(p_it->x, p_it->y, p_it->z);
++p_it;
Point q(p_it->x, p_it->y, p_it->z);
++p_it;
Point r(p_it->x, p_it->y, p_it->z);
return Datum(p, q, r); // assembles a triangle from three points
}
// returns one point which must be on the primitive
Point reference_point() const
{
return Point(m_it->x, m_it->y, m_it->z);
}
};
// types
typedef CGAL::AABB_traits<K, My_triangle_primitive> My_AABB_traits;
typedef CGAL::AABB_tree<My_AABB_traits> Tree;
int main()
{
// generates triangle soup
My_point a(1.0, 0.0, 0.0);
My_point b(0.0, 1.0, 0.0);
My_point c(0.0, 0.0, 1.0);
My_point d(0.0, 0.0, 0.0);
std::vector<My_point> triangles;
triangles.push_back(a); triangles.push_back(b); triangles.push_back(c);
triangles.push_back(a); triangles.push_back(b); triangles.push_back(d);
triangles.push_back(a); triangles.push_back(d); triangles.push_back(c);
// constructs AABB tree
Tree tree(Triangle_iterator(triangles.begin()),
Triangle_iterator(triangles.end()));
// counts #intersections
K::Ray_3 ray_query(K::Point_3(1.0, 0.0, 0.0), 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);
return EXIT_SUCCESS;
}
|
