- Author
- Jackson Campolattaro
Introduction
An octree is a commonly used data structure that subdivides 3d space. The Octree package provides the Octree and Node classes.
Note that the octree will often be outperformed by Spacial_searching's kD-tree. Octrees are most useful when implementing algorithms that require nodes without high aspect-ratios. Intersection and nearest-neighbor algorithms should be expected to perform worse than the kD-tree but they can be useful if the octree has already been constructed.
Building an Octree
Before an octree can be used for anything, the tree itself must be created. By default, the constructor returns a tree with a single (root) node that contains all the points. We can use the refine method to subdivide space further.
Building an Octree from a Vector of Points
The simplest way to create an octree is using a vector of points. The constructor generally expects a separate point-range and map, but the point-map defaults to CGAL's Identity_property_map if none is provided. That enables using a range that contains the points directly, because it's mapped directly to itself.
Example
This example illustrates how to create an octree from a std::vector.
An std::vector<Point_3> is manually filled with points. The vector is used as the point set, a CGAL::Identity_property_map is automatically set as the octree's map type, so a map doesn't need to be provided.
File Octree/Octree_build_from_Point_vector.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef std::vector<Point> Point_vector;
int main(int argc, char **argv) {
Point_vector points;
points.emplace_back(1, 1, 1);
points.emplace_back(2, 1, -11);
points.emplace_back(2, 1, 1);
points.emplace_back(1, -2, 1);
points.emplace_back(1, 1, 1);
points.emplace_back(-1, 1, 1);
Octree octree(points);
octree.refine(10, 20);
std::cout << octree;
return EXIT_SUCCESS;
}
Building an Octree from a Point_set_3
Using a Point_set_3 is slightly more complicated, but it comes with a number of advantages. CGAL's Point set class has many useful features. Here we take advantage of its ability to save and load from files easily. The independent point-range and map may also come with a performance benefit.
Example
This example illustrates how to create an octree from a Point_set_3 loaded from a file. It also shows a more explicit way of setting the split criteria when refining the tree.
An octree is constructed from the point set and its map. The tree is refined with a max-depth (deepest node allowed) of 10, and a bucket size (maximum number of points contained by a single node) of 20. The tree is then printed to the standard output.
The split criterion is manually constructed and passed to the refine method.
File Octree/Octree_build_from_Point_set.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef CGAL::Point_set_3<Point> Point_set;
typedef Point_set::Point_map Point_map;
int main(int argc, char **argv) {
Point_set points;
std::ifstream stream((argc > 1) ? argv[1] : "data/cube.pwn");
stream >> points;
if (0 == points.number_of_points()) {
std::cerr << "Error: cannot read file" << std::endl;
return EXIT_FAILURE;
}
std::cout << "loaded " << points.number_of_points() << " points\n" << std::endl;
Octree octree(points, points.point_map());
std::cout << octree;
return EXIT_SUCCESS;
}
Building an Octree with a Custom Split Criterion
It's very easy to create your own criterion if the existing ones don't match your needs. For example, you might design a criterion which only splits nodes that contain exactly 4 points.
- Todo:
- Link to SplitCriterion concept
Example
This example illustrates how to refine an octree using a split criterion that isn't provided by default.
The criterion is a functor created by the user to determine whether a node needs to be split. This particular criterion sets a node's bucket size as a ratio of its depth. For example, for a ratio of 2, a node at depth 2 can hold 4 points, a node at depth 7 can hold 14.
File Octree/Octree_build_with_custom_split.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef Kernel::FT FT;
typedef CGAL::Point_set_3<Point> Point_set;
typedef Point_set::Point_map Point_map;
struct Split_by_ratio {
std::size_t ratio;
Split_by_ratio(std::size_t ratio) : ratio(ratio) {}
template<class Node>
bool operator()(const Node &n) const {
return n.size() > (ratio * n.depth());
}
};
int main(int argc, char **argv) {
Point_set points;
std::ifstream stream((argc > 1) ? argv[1] : "data/cube.pwn");
stream >> points;
if (0 == points.number_of_points()) {
std::cerr << "Error: cannot read file" << std::endl;
return EXIT_FAILURE;
}
std::cout << "loaded " << points.number_of_points() << " points" << std::endl;
Octree octree(points, points.point_map());
octree.refine(Split_by_ratio(2.0));
std::cout << octree;
return EXIT_SUCCESS;
}
Traversal over an Octree
Traversal is the act of navigating among the nodes of the tree. The Octree and Node classes provide a number of different solutions for traversing the tree.
Manual Traversal
Because our octree is a form of connected acyclic undirected graph, it's possible to navigate between any two nodes. What that means in practice, is that given a pointer or reference to one node on the tree, it's possible to access any other node using the right set of operations. The node has functions that allow the user to access each of its children, as well as its parent (if it exists).
Example
This example demonstrates ways of accessing different nodes of a tree, given a reference to one.
If you have the root node, it's possible to get to its children using the subscript operator ([]). Values from 0-7 provide access to the different children. Using the operator on a leaf node is considered undefined behavior.
For non-root nodes, it's possible to access parent nodes using the parent accessor. Note that the accessor returns a pointer and not a reference, calling the root node's parent accessor will return null.
These accessors and operators can be chained to access any node in the tree in a single line of code.
File Octree/Octree_traversal_manual.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef CGAL::Point_set_3<Point> Point_set;
typedef Point_set::Point_map Point_map;
int main(int argc, char **argv) {
Point_set points;
std::ifstream stream((argc > 1) ? argv[1] : "data/cube.pwn");
stream >> points;
if (0 == points.number_of_points()) {
std::cerr << "Error: cannot read file" << std::endl;
return EXIT_FAILURE;
}
std::cout << "loaded " << points.number_of_points() << " points\n" << std::endl;
Octree octree(points, points.point_map());
octree.refine();
std::cout << "Navigation relative to the root node" << std::endl;
std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << std::endl;
std::cout << "the root node: " << std::endl;
std::cout << octree.root() << std::endl;
std::cout << "the first child of the root node: " << std::endl;
std::cout << octree.root()[0] << std::endl;
std::cout << "the fifth child: " << std::endl;
std::cout << octree.root()[4] << std::endl;
std::cout << "the fifth child, accessed without the root keyword: " << std::endl;
std::cout << octree[4] << std::endl;
std::cout << "the second child of the fourth child: " << std::endl;
std::cout << octree.root()[4][1] << std::endl;
std::cout << "the second child of the fourth child, accessed without the root keyword: " << std::endl;
std::cout << octree[4][1] << std::endl;
std::cout << std::endl;
const Octree::Node &cur = octree[3][2];
std::cout << "Navigation relative to a child node" << std::endl;
std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << std::endl;
std::cout << "the third child of the fourth child: " << std::endl;
std::cout << cur << std::endl;
std::cout << "the third child: " << std::endl;
std::cout << *cur.parent() << std::endl;
std::cout << "the next sibling of the third child of the fourth child: " << std::endl;
std::cout << (*cur.parent())[cur.index().to_ulong() + 1] << std::endl;
return EXIT_SUCCESS;
}
Preorder Traversal
It's often useful to be able to iterate over the nodes of the tree in a particular order. For example, the stream operator << uses a traversal to print out each node. A few traversals are provided, among them "Preorder" and "Postorder". To traverse a tree in preorder is to visit each parent immediately followed by its children, where in posterder traversal the children are visited first.
- Todo:
- This could use a bit more detail
Example
This example illustrates how to use the provided traversals.
A tree is constructed, and a traversal is used to create a range that can be iterated over using a for-each loop. The default output operator for the octree uses the preorder traversal to do a pretty-print of the tree structure. In this case, we print out the nodes of the tree without indentation instead.
File Octree/Octree_traversal_preorder.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef CGAL::Point_set_3<Point> Point_set;
typedef Point_set::Point_map Point_map;
int main(int argc, char **argv) {
Point_set points;
std::ifstream stream((argc > 1) ? argv[1] : "data/cube.pwn");
stream >> points;
if (0 == points.number_of_points()) {
std::cerr << "Error: cannot read file" << std::endl;
return EXIT_FAILURE;
}
std::cout << "loaded " << points.number_of_points() << " points\n" << std::endl;
Octree octree(points, points.point_map());
octree.refine();
std::cout << node << std::endl;
}
return EXIT_SUCCESS;
}
Acceleration of Common Tasks
Once an octree is built, its structure can be used to accelerate different tasks.
Finding the Nearest Neighbor of a Point
The naive way of finding the nearest neighbor of a point requires finding the distance of every other point. An octree can be used to perform the same task in significantly less time. For large numbers of points, this can be a large enough difference to outweigh the time spent building the tree.
Note that a kD-tree is expected to outperform the Octree for this task, it should be preferred unless features specific to the Octree are needed.
Example
This example illustrates how to use an octree to accelerate the search for points close to a location.
Points are loaded from a file and an octree is built. The nearest neighbor method is invoked for several input points. A k value of 1 is used to find the single closest point. Results are put in a vector, and then printed.
File Octree/Octree_find_nearest_neighbor.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/Point_set_3/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef CGAL::Point_set_3<Point> Point_set;
typedef Point_set::Point_map Point_map;
int main(int argc, char **argv) {
Point_set points;
std::ifstream stream((argc > 1) ? argv[1] : "data/cube.pwn");
stream >> points;
if (0 == points.number_of_points()) {
std::cerr << "Error: cannot read file" << std::endl;
return EXIT_FAILURE;
}
std::cout << "loaded " << points.number_of_points() << " points" << std::endl;
Octree octree(points, points.point_map());
octree.refine(10, 20);
std::vector<Point> points_to_find = {
{0, 0, 0},
{1, 1, 1},
{-1, -1, -1},
{-0.46026, -0.25353, 0.32051},
{-0.460261, -0.253533, 0.320513}
};
for (auto p : points_to_find) {
std::vector<Point> nearest_points;
octree.nearest_k_neighbors(p, 1, std::back_inserter(nearest_points));
std::cout << "the nearest point to (" << p << ") is (" << nearest_points[0] << ")" << std::endl;
}
return EXIT_SUCCESS;
}
Grading an octree
Example
This example demonstrates how to use the grade method to eliminate large jumps in depth within the octree.
A tree is created such that one node is split many more times than those it borders. grade() splits the octree's nodes so that adjacent nodes never have a difference in depth greater than one. The tree is printed before and after grading, so that the differences are visible.
File Octree/Octree_grade.cpp
#include <fstream>
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Octree/IO.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef std::vector<Point> Point_vector;
int main(int argc, char **argv) {
Point_vector points;
points.emplace_back(1, 1, 1);
points.emplace_back(2, 1, -11);
points.emplace_back(2, 1, 1);
points.emplace_back(1, -2, 1);
points.emplace_back(1, 1, 1);
points.emplace_back(-1, 1, 1);
points.emplace_back(-1.1, 1, 1);
points.emplace_back(-1.01, 1, 1);
points.emplace_back(-1.001, 1, 1);
points.emplace_back(-1.0001, 1, 1);
points.emplace_back(-1.0001, 1, 1);
Octree octree(points);
octree.refine(10, 2);
std::cout << "\nUn-graded tree" << std::endl;
std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << std::endl;
std::cout << octree << std::endl;
octree.grade();
std::cout << "\nGraded tree" << std::endl;
std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << std::endl;
std::cout << octree << std::endl;
return EXIT_SUCCESS;
}
Performance
Comparison with kD Tree
e.g. When is an octree the right choice?
Software Design
Splitting Rules
Walker Rules
History
This package was developed by Jackson Campolatarro as part of the Google Summer of Code 2020, based on a prototype code by Tong Zhao and Cédric Portaneri, under the supervision of Simon Giraudot and with the kind help and advice of Pierre Alliez
1.8.18