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
|
// 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 : An example of AABB tree constructed with
// custom point and triangle types.
//
//******************************************************************************
#include <iostream>
#include <list>
#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;
// custom point type
struct My_point {
double m_x;
double m_y;
double m_z;
My_point(const double x,
const double y,
const double z)
: m_x(x), m_y(y), m_z(z) {}
};
// custom triangle type with
// three pointers to points
struct My_triangle {
My_point *m_pa;
My_point *m_pb;
My_point *m_pc;
My_triangle(My_point *pa,
My_point *pb,
My_point *pc)
: m_pa(pa), m_pb(pb), m_pc(pc) {}
};
// the custom triangles are stored into a vector
typedef std::vector<My_triangle>::const_iterator Iterator;
// The following primitive provides the conversion facilities between
// the custom triangle and point types and the CGAL ones
struct My_triangle_primitive {
public:
// this is the type of data that the queries returns. For this example
// we imagine that, for some reasons, we do not want to store the iterators
// of the vector, but raw pointers. This is to show that the Id type
// does not have to be the same as the one of the input parameter of the
// constructor.
typedef const My_triangle* Id;
// CGAL types returned
typedef K::Point_3 Point; // CGAL 3D point type
typedef K::Triangle_3 Datum; // CGAL 3D triangle type
private:
Id m_pt; // 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(Iterator it)
: m_pt(&(*it)) {}
const Id& id() const { return m_pt; }
// utility function to convert a custom
// point type to CGAL point type.
Point convert(const My_point *p) const
{
return Point(p->m_x,p->m_y,p->m_z);
}
// on the fly conversion from the internal data to the CGAL types
Datum datum() const
{
return Datum(convert(m_pt->m_pa),
convert(m_pt->m_pb),
convert(m_pt->m_pc));
}
// returns a reference point which must be on the primitive
Point reference_point() const
{ return convert(m_pt->m_pa); }
};
typedef CGAL::AABB_traits<K, My_triangle_primitive> My_AABB_traits;
typedef CGAL::AABB_tree<My_AABB_traits> Tree;
int main()
{
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_triangle> triangles;
triangles.push_back(My_triangle(&a,&b,&c));
triangles.push_back(My_triangle(&a,&b,&d));
triangles.push_back(My_triangle(&a,&d,&c));
// constructs AABB tree
Tree tree(triangles.begin(),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;
}
|
