#Superficial review
Superficial review
Missing code
#Missing code
II had to infer the Quadtree
and Element
class definitions (so I might have come up with something different to what you have):
Re-write
#Re-write
I'mI'm going to start with a similar Element
structure, but I don't see a need for an element to know its container here, so I'll remove the intrusive pointer:
Putting it all together
#Putting it all together ThereThere were a couple of bugs in my thoughts above; having corrected them, we get:
#Superficial review
#Missing code
I had to infer the Quadtree
and Element
class definitions (so I might have come up with something different to what you have):
#Re-write
I'm going to start with a similar Element
structure, but I don't see a need for an element to know its container here, so I'll remove the intrusive pointer:
#Putting it all together There were a couple of bugs in my thoughts above; having corrected them, we get:
Superficial review
Missing code
I had to infer the Quadtree
and Element
class definitions (so I might have come up with something different to what you have):
Re-write
I'm going to start with a similar Element
structure, but I don't see a need for an element to know its container here, so I'll remove the intrusive pointer:
Putting it all together
There were a couple of bugs in my thoughts above; having corrected them, we get:
#Putting it all together
This now just needsThere were a main()
and the code to update aggregate values when elements are added or moved.couple of bugs in my thoughts above; having corrected them, we get:
#include <glm/glm.hpp>
#include <algorithm>
#include <iterator>
#include <iosfwd>
#include <memory>
#include <string>
#include <vector>
struct Element
{
glm::vec3 pos;
float weight;
};
class Octree
{
// geometry
const glm::vec3 far_bottom_left;
const glm::vec3 near_top_right;
const glm::vec3 middle;
// limit to tree depth
unsigned level;
// aggregate properties from constituent objects
double total_weight = 0;
glm::vec3 mean_position = {};
// subtree objects - any or all may be null
// index using (left=4, right=0) + (bottom=2, top=0) + (far=1, near=0)
std::unique_ptr<Octree> children[8] = {};
// directly held elements - empty unless all children are null
std::vector<Element> objects = {};
public:
explicit Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth);
void add(Element e);
std::ostream& print(std::ostream&, const std::string& indent) const;
friend std::ostream& operator<<(std::ostream& out, const Octree& o) {
return o.print(out, {});
}
private:
bool is_leaf() const;
};
Octree::Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth)
: far_bottom_left{far_bottom_left},
near_top_right{near_top_right},
middle{0.5f * far_bottom_left + 0.5f * near_top_right},
level{max_depth}
{}
void Octree::add(Element e)
{
if (level == 0 || objects.empty() && is_leaf()) {
objects.emplace_back(std::move(e));
return;
}
const bool left = e.pos.x < middle.x;
const bool down = e.pos.y < middle.y;
const bool far = e.pos.z < middle.z;
auto& child = children[4*left + 2*down + far];
if (!child) {
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fblntr : ntrfbl).x = middle.x;
(down ? fblntr : ntrfbl).y = middle.y;
(far ? fblntr : ntrfbl).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
forauto (auto&to_move o:= std::move(objects);
objects.clear();
add(std::move for (auto& o): to_move);
objects.clear add(std::move(o));
}
child->add(std::move(e));
}
bool Octree::is_leaf() const
{
// we're a leaf node if all children are null
return std::all_of(std::begin(children), std::end(children),
[](auto& x){return !x;});
}
To test it, here's some output operators:
std::ostream& operator<<(std::ostream& os, const glm::vec3& pos)
{
return os << '(' << pos.x
<< ',' << pos.y
<< ',' << pos.z
<< ')';
}
std::ostream& operator<<(std::ostream& os, const Element& e)
{
return os << e.pos;
}
std::ostream& Octree::print(std::ostream& os, const std::string& indent) const
{
os << indent
<< "Octree " << far_bottom_left
<< " to " << near_top_right << '\n';
if (!os) { return os; }
for (auto const& e: objects) {
os << indent << "- " << e << '\n';
}
if (!os) { return os; }
for (auto i = 0u; i < std::size(children); ++i) {
if (children[i]) {
os << indent
<< (i & 1 ? "far" : "near") << ' '
<< (i & 2 ? "bottom" : "top") << ' '
<< (i & 4 ? "left" : "right") << ": \n";
children[i]->print(os, indent+" ");
if (!os) { return os; }
}
}
return os;
}
And a test program to show we're producing the right output, and to measure execution time:
#include <chrono>
#include <iostream>
#include <random>
int main()
{
{
// Visual test - do these few points go into the right boxes?
Octree tree{{0,0,0}, {1,1,1}, 23};
std::mt19937 gen;
std::uniform_real_distribution<float> dis{0,1};
for (auto i = 0u; i < 20; ++i) {
tree.add({{dis(gen), dis(gen), dis(gen)}, 1});
}
std::cout << tree;
}
std::cout << std::endl;
{
// Timing test
Octree tree{{0.3,0.3,-0.3}, {1,1,1}, 5};
std::mt19937 gen;
std::uniform_real_distribution<float> dis{0,1};
auto const starttime = std::chrono::high_resolution_clock::now();
auto const chunk = 10000;
for (auto i = 0u; i < 20; ++i) {
for (auto j = 0; j < chunk; ++j) {
tree.add({{0.3dis(gen),0.3 dis(gen),-0.2 dis(gen)}, 21});
}
auto const now = std::chrono::high_resolution_clock::now();
auto const time_in_ms
= duration_cast<milliseconds>(now - starttime);
std::cout << chunk*(i+1) << " points: "
<< time_in_ms.count() << " ms\n";
}
}
}
My results:
Octree (0,0,0) to (1,1,1)
near top right:
Octree (0.5,0.5,0.5) to (1,1,1)
near top right:
Octree (0.75,0.75,0.75) to (1,1,1)
near top right:
Octree (0.875,0.875,0.875) to (1,1,1)
- (0.992881,0.957507,0.996461)
near top left:
Octree (0.75,0.875,0.875) to (0.875,1,1)
- (0.792207,0.878431,0.959492)
near top left:
Octree (0.5,0.75,0.75) to (0.75,1,1)
- (0.725839,0.970593,0.98111)
near bottom left:
Octree (0.5,0.5,0.75) to (0.75,0.75,1)
- (0.503663,0.655741,0.797929)
far top right:
Octree (0.5,0.5,0) to (1,1,0.5)
near top right:
Octree (0.75,0.75,0.25) to (1,1,0.5)
- (0.798106,0.80028,0.297029)
far top right:
Octree (0.75,0.75,0) to (1,1,0.25)
- (0.964889,0.967695,0.157613)
near bottom left:
Octree (0.5,0.5,0.25) to (0.75,0.75,0.5)
- (0.740647,0.743132,0.474759)
near bottom right:
Octree (0.5,0,0.5) to (1,0.5,1)
near bottom right:
Octree (0.75,0,0.75) to (1,0.25,1)
near top left:
Octree (0.75,0.125,0.875) to (0.875,0.25,1)
- (0.814724,0.135477,0.905792)
- (0.835009,0.126987,0.968868)
far bottom right:
Octree (0.75,0,0.5) to (1,0.25,0.75)
- (0.913376,0.221034,0.632359)
near top left:
Octree (0.5,0.25,0.75) to (0.75,0.5,1)
- (0.678735,0.398739,0.75774)
far bottom right:
Octree (0.5,0,0) to (1,0.5,0.5)
- (0.957167,0.109862,0.485376)
near top left:
Octree (0,0.5,0.5) to (0.5,1,1)
far top left:
Octree (0,0.75,0.5) to (0.25,1,0.75)
near top right:
Octree (0.125,0.875,0.625) to (0.25,1,0.75)
- (0.211924,0.933993,0.68136)
near top left:
Octree (0,0.875,0.625) to (0.125,1,0.75)
- (0.112465,0.915736,0.639763)
near bottom left:
Octree (0,0,0.5) to (0.5,0.5,1)
far top right:
Octree (0.25,0.25,0.5) to (0.5,0.5,0.75)
- (0.392227,0.422088,0.655478)
far bottom right:
Octree (0.25,0,0.5) to (0.5,0.25,0.75)
far top left:
Octree (0.25,0.125,0.5) to (0.375,0.25,0.625)
- (0.278498,0.188382,0.546881)
far bottom left:
Octree (0.25,0,0.5) to (0.375,0.125,0.625)
- (0.308167,0.0975404,0.547221)
near top left:
Octree (0,0.25,0.75) to (0.25,0.5,1)
- (0.0357117,0.361294,0.849129)
far bottom left:
Octree (0,0,0) to (0.5,0.5,0.5)
near bottom left:
Octree (0,0,0.25) to (0.25,0.25,0.5)
far top right:
Octree (0.125,0.125,0.25) to (0.25,0.25,0.375)
- (0.173865,0.171187,0.301913)
near bottom right:
Octree (0.125,0,0.375) to (0.25,0.125,0.5)
- (0.141886,0.00478348,0.421761)
10000 points: 15 ms
20000 points: 27 ms
30000 points: 38 ms
40000 points: 49 ms
50000 points: 59 ms
60000 points: 69 ms
70000 points: 78 ms
80000 points: 88 ms
90000 points: 98 ms
100000 points: 107 ms
110000 points: 118 ms
120000 points: 129 ms
130000 points: 140 ms
140000 points: 152 ms
150000 points: 163 ms
160000 points: 172 ms
170000 points: 181 ms
180000 points: 190 ms
190000 points: 199 ms
200000 points: 208 ms
#Putting it all together
This now just needs a main()
and the code to update aggregate values when elements are added or moved.
#include <glm/glm.hpp>
#include <algorithm>
#include <iterator>
#include <memory>
#include <vector>
struct Element
{
glm::vec3 pos;
float weight;
};
class Octree
{
// geometry
const glm::vec3 far_bottom_left;
const glm::vec3 near_top_right;
const glm::vec3 middle;
// limit to tree depth
unsigned level;
// aggregate properties from constituent objects
double total_weight = 0;
glm::vec3 mean_position = {};
// subtree objects - any or all may be null
// index using (left=4, right=0) + (bottom=2, top=0) + (far=1, near=0)
std::unique_ptr<Octree> children[8] = {};
// directly held elements - empty unless all children are null
std::vector<Element> objects = {};
public:
explicit Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth);
void add(Element e);
private:
bool is_leaf() const;
};
Octree::Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth)
: far_bottom_left{far_bottom_left},
near_top_right{near_top_right},
middle{0.5f * far_bottom_left + 0.5f * near_top_right},
level{max_depth}
{}
void Octree::add(Element e)
{
if (level == 0 || objects.empty() && is_leaf()) {
objects.emplace_back(std::move(e));
return;
}
const bool left = e.pos.x < middle.x;
const bool down = e.pos.y < middle.y;
const bool far = e.pos.z < middle.z;
auto& child = children[4*left + 2*down + far];
if (!child) {
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
for (auto& o: objects)
add(std::move(o));
objects.clear();
}
child->add(std::move(e));
}
bool Octree::is_leaf() const
{
// we're a leaf node if all children are null
return std::all_of(std::begin(children), std::end(children),
[](auto& x){return !x;});
}
int main()
{
Octree tree{{0,0,0}, {1,1,1}, 2};
tree.add({{0.3,0.3,-0.3}, 5});
tree.add({{0.3,0.3,-0.2}, 2});
}
#Putting it all together There were a couple of bugs in my thoughts above; having corrected them, we get:
#include <glm/glm.hpp>
#include <algorithm>
#include <iterator>
#include <iosfwd>
#include <memory>
#include <string>
#include <vector>
struct Element
{
glm::vec3 pos;
float weight;
};
class Octree
{
// geometry
const glm::vec3 far_bottom_left;
const glm::vec3 near_top_right;
const glm::vec3 middle;
// limit to tree depth
unsigned level;
// aggregate properties from constituent objects
double total_weight = 0;
glm::vec3 mean_position = {};
// subtree objects - any or all may be null
// index using (left=4, right=0) + (bottom=2, top=0) + (far=1, near=0)
std::unique_ptr<Octree> children[8] = {};
// directly held elements - empty unless all children are null
std::vector<Element> objects = {};
public:
explicit Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth);
void add(Element e);
std::ostream& print(std::ostream&, const std::string& indent) const;
friend std::ostream& operator<<(std::ostream& out, const Octree& o) {
return o.print(out, {});
}
private:
bool is_leaf() const;
};
Octree::Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth)
: far_bottom_left{far_bottom_left},
near_top_right{near_top_right},
middle{0.5f * far_bottom_left + 0.5f * near_top_right},
level{max_depth}
{}
void Octree::add(Element e)
{
if (level == 0 || objects.empty() && is_leaf()) {
objects.emplace_back(std::move(e));
return;
}
const bool left = e.pos.x < middle.x;
const bool down = e.pos.y < middle.y;
const bool far = e.pos.z < middle.z;
auto& child = children[4*left + 2*down + far];
if (!child) {
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? ntr : fbl).x = middle.x;
(down ? ntr : fbl).y = middle.y;
(far ? ntr : fbl).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
auto to_move = std::move(objects);
objects.clear();
for (auto& o: to_move)
add(std::move(o));
}
child->add(std::move(e));
}
bool Octree::is_leaf() const
{
// we're a leaf node if all children are null
return std::all_of(std::begin(children), std::end(children),
[](auto& x){return !x;});
}
To test it, here's some output operators:
std::ostream& operator<<(std::ostream& os, const glm::vec3& pos)
{
return os << '(' << pos.x
<< ',' << pos.y
<< ',' << pos.z
<< ')';
}
std::ostream& operator<<(std::ostream& os, const Element& e)
{
return os << e.pos;
}
std::ostream& Octree::print(std::ostream& os, const std::string& indent) const
{
os << indent
<< "Octree " << far_bottom_left
<< " to " << near_top_right << '\n';
if (!os) { return os; }
for (auto const& e: objects) {
os << indent << "- " << e << '\n';
}
if (!os) { return os; }
for (auto i = 0u; i < std::size(children); ++i) {
if (children[i]) {
os << indent
<< (i & 1 ? "far" : "near") << ' '
<< (i & 2 ? "bottom" : "top") << ' '
<< (i & 4 ? "left" : "right") << ": \n";
children[i]->print(os, indent+" ");
if (!os) { return os; }
}
}
return os;
}
And a test program to show we're producing the right output, and to measure execution time:
#include <chrono>
#include <iostream>
#include <random>
int main()
{
{
// Visual test - do these few points go into the right boxes?
Octree tree{{0,0,0}, {1,1,1}, 3};
std::mt19937 gen;
std::uniform_real_distribution<float> dis{0,1};
for (auto i = 0u; i < 20; ++i) {
tree.add({{dis(gen), dis(gen), dis(gen)}, 1});
}
std::cout << tree;
}
std::cout << std::endl;
{
// Timing test
Octree tree{{0,0,0}, {1,1,1}, 5};
std::mt19937 gen;
std::uniform_real_distribution<float> dis{0,1};
auto const starttime = std::chrono::high_resolution_clock::now();
auto const chunk = 10000;
for (auto i = 0u; i < 20; ++i) {
for (auto j = 0; j < chunk; ++j) {
tree.add({{dis(gen), dis(gen), dis(gen)}, 1});
}
auto const now = std::chrono::high_resolution_clock::now();
auto const time_in_ms
= duration_cast<milliseconds>(now - starttime);
std::cout << chunk*(i+1) << " points: "
<< time_in_ms.count() << " ms\n";
}
}
}
My results:
Octree (0,0,0) to (1,1,1)
near top right:
Octree (0.5,0.5,0.5) to (1,1,1)
near top right:
Octree (0.75,0.75,0.75) to (1,1,1)
near top right:
Octree (0.875,0.875,0.875) to (1,1,1)
- (0.992881,0.957507,0.996461)
near top left:
Octree (0.75,0.875,0.875) to (0.875,1,1)
- (0.792207,0.878431,0.959492)
near top left:
Octree (0.5,0.75,0.75) to (0.75,1,1)
- (0.725839,0.970593,0.98111)
near bottom left:
Octree (0.5,0.5,0.75) to (0.75,0.75,1)
- (0.503663,0.655741,0.797929)
far top right:
Octree (0.5,0.5,0) to (1,1,0.5)
near top right:
Octree (0.75,0.75,0.25) to (1,1,0.5)
- (0.798106,0.80028,0.297029)
far top right:
Octree (0.75,0.75,0) to (1,1,0.25)
- (0.964889,0.967695,0.157613)
near bottom left:
Octree (0.5,0.5,0.25) to (0.75,0.75,0.5)
- (0.740647,0.743132,0.474759)
near bottom right:
Octree (0.5,0,0.5) to (1,0.5,1)
near bottom right:
Octree (0.75,0,0.75) to (1,0.25,1)
near top left:
Octree (0.75,0.125,0.875) to (0.875,0.25,1)
- (0.814724,0.135477,0.905792)
- (0.835009,0.126987,0.968868)
far bottom right:
Octree (0.75,0,0.5) to (1,0.25,0.75)
- (0.913376,0.221034,0.632359)
near top left:
Octree (0.5,0.25,0.75) to (0.75,0.5,1)
- (0.678735,0.398739,0.75774)
far bottom right:
Octree (0.5,0,0) to (1,0.5,0.5)
- (0.957167,0.109862,0.485376)
near top left:
Octree (0,0.5,0.5) to (0.5,1,1)
far top left:
Octree (0,0.75,0.5) to (0.25,1,0.75)
near top right:
Octree (0.125,0.875,0.625) to (0.25,1,0.75)
- (0.211924,0.933993,0.68136)
near top left:
Octree (0,0.875,0.625) to (0.125,1,0.75)
- (0.112465,0.915736,0.639763)
near bottom left:
Octree (0,0,0.5) to (0.5,0.5,1)
far top right:
Octree (0.25,0.25,0.5) to (0.5,0.5,0.75)
- (0.392227,0.422088,0.655478)
far bottom right:
Octree (0.25,0,0.5) to (0.5,0.25,0.75)
far top left:
Octree (0.25,0.125,0.5) to (0.375,0.25,0.625)
- (0.278498,0.188382,0.546881)
far bottom left:
Octree (0.25,0,0.5) to (0.375,0.125,0.625)
- (0.308167,0.0975404,0.547221)
near top left:
Octree (0,0.25,0.75) to (0.25,0.5,1)
- (0.0357117,0.361294,0.849129)
far bottom left:
Octree (0,0,0) to (0.5,0.5,0.5)
near bottom left:
Octree (0,0,0.25) to (0.25,0.25,0.5)
far top right:
Octree (0.125,0.125,0.25) to (0.25,0.25,0.375)
- (0.173865,0.171187,0.301913)
near bottom right:
Octree (0.125,0,0.375) to (0.25,0.125,0.5)
- (0.141886,0.00478348,0.421761)
10000 points: 15 ms
20000 points: 27 ms
30000 points: 38 ms
40000 points: 49 ms
50000 points: 59 ms
60000 points: 69 ms
70000 points: 78 ms
80000 points: 88 ms
90000 points: 98 ms
100000 points: 107 ms
110000 points: 118 ms
120000 points: 129 ms
130000 points: 140 ms
140000 points: 152 ms
150000 points: 163 ms
160000 points: 172 ms
170000 points: 181 ms
180000 points: 190 ms
190000 points: 199 ms
200000 points: 208 ms
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
for (auto& o: objects)
add(std::swapmove(objects,o));
child.objects.clear();
#include <glm/glm.hpp>
#include <algorithm>
#include <iterator>
#include <memory>
#include <vector>
struct Element
{
glm::vec3 pos;
float weight;
};
class Octree
{
// geometry
const glm::vec3 far_bottom_left;
const glm::vec3 near_top_right;
const glm::vec3 middle;
// limit to tree depth
unsigned level;
// aggregate properties from constituent objects
double total_weight = 0;
glm::vec3 mean_position = {};
// subtree objects - any or all may be null
// index using (left=0left=4, right=4right=0) + (bottom=0bottom=2, top=2top=0) + (far=0far=1, near=1near=0)
std::unique_ptr<Octree> children[8] = {};
// directly held elements - empty unless all children are null
std::vector<Element> objects = {};
public:
explicit Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth);
void add(Element e);
private:
bool is_leaf() const;
};
Octree::Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth)
: far_bottom_left{far_bottom_left},
near_top_right{near_top_right},
middle{0.5f * far_bottom_left + 0.5f * near_top_right},
level{max_depth}
{}
void Octree::add(Element e)
{
if (level == 0 || objects.empty() && is_leaf()) {
objects.emplace_back(std::move(e));
return;
}
const bool left = e.pos.x < middle.x;
const bool down = e.pos.y < middle.y;
const bool far = e.pos.z < middle.z;
auto& child = children[4*left + 2*down + far];
if (!child) {
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
for (auto& o: objects)
add(std::swapmove(objects,o));
child->objects objects.clear();
}
child->add(std::move(e));
}
bool Octree::is_leaf() const
{
// we're a leaf node if all children are null
return std::all_of(std::begin(children), std::end(children),
[](auto& x){return !x;});
}
int main()
{
Octree tree{{0,0,0}, {1,1,1}, 2};
tree.add({{0.3,0.3,-0.3}, 5});
tree.add({{0.3,0.3,-0.2}, 2});
}
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
std::swap(objects, child.objects);
#include <glm/glm.hpp>
#include <algorithm>
#include <iterator>
#include <memory>
#include <vector>
struct Element
{
glm::vec3 pos;
float weight;
};
class Octree
{
// geometry
const glm::vec3 far_bottom_left;
const glm::vec3 near_top_right;
const glm::vec3 middle;
// limit to tree depth
unsigned level;
// aggregate properties from constituent objects
double total_weight = 0;
glm::vec3 mean_position = {};
// subtree objects - any or all may be null
// index using (left=0, right=4) + (bottom=0, top=2) + (far=0, near=1)
std::unique_ptr<Octree> children[8] = {};
// directly held elements - empty unless all children are null
std::vector<Element> objects = {};
public:
explicit Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth);
void add(Element e);
private:
bool is_leaf() const;
};
Octree::Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth)
: far_bottom_left{far_bottom_left},
near_top_right{near_top_right},
middle{0.5f * far_bottom_left + 0.5f * near_top_right},
level{max_depth}
{}
void Octree::add(Element e)
{
if (level == 0 || objects.empty() && is_leaf()) {
objects.emplace_back(std::move(e));
return;
}
const bool left = e.pos.x < middle.x;
const bool down = e.pos.y < middle.y;
const bool far = e.pos.z < middle.z;
auto& child = children[4*left + 2*down + far];
if (!child) {
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
std::swap(objects, child->objects);
}
child->add(std::move(e));
}
bool Octree::is_leaf() const
{
// we're a leaf node if all children are null
return std::all_of(std::begin(children), std::end(children),
[](auto& x){return !x;});
}
int main()
{
Octree tree{{0,0,0}, {1,1,1}, 2};
tree.add({{0.3,0.3,-0.3}, 5});
tree.add({{0.3,0.3,-0.2}, 2});
}
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
for (auto& o: objects)
add(std::move(o));
objects.clear();
#include <glm/glm.hpp>
#include <algorithm>
#include <iterator>
#include <memory>
#include <vector>
struct Element
{
glm::vec3 pos;
float weight;
};
class Octree
{
// geometry
const glm::vec3 far_bottom_left;
const glm::vec3 near_top_right;
const glm::vec3 middle;
// limit to tree depth
unsigned level;
// aggregate properties from constituent objects
double total_weight = 0;
glm::vec3 mean_position = {};
// subtree objects - any or all may be null
// index using (left=4, right=0) + (bottom=2, top=0) + (far=1, near=0)
std::unique_ptr<Octree> children[8] = {};
// directly held elements - empty unless all children are null
std::vector<Element> objects = {};
public:
explicit Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth);
void add(Element e);
private:
bool is_leaf() const;
};
Octree::Octree(glm::vec3 far_bottom_left,
glm::vec3 near_top_right,
unsigned max_depth)
: far_bottom_left{far_bottom_left},
near_top_right{near_top_right},
middle{0.5f * far_bottom_left + 0.5f * near_top_right},
level{max_depth}
{}
void Octree::add(Element e)
{
if (level == 0 || objects.empty() && is_leaf()) {
objects.emplace_back(std::move(e));
return;
}
const bool left = e.pos.x < middle.x;
const bool down = e.pos.y < middle.y;
const bool far = e.pos.z < middle.z;
auto& child = children[4*left + 2*down + far];
if (!child) {
glm::vec3 fbl = far_bottom_left;
glm::vec3 ntr = near_top_right;
(left ? fbl : ntr).x = middle.x;
(down ? fbl : ntr).y = middle.y;
(far ? fbl : ntr).z = middle.z;
child = std::make_unique<Octree>(fbl, ntr, level-1);
// move any directly-held object
for (auto& o: objects)
add(std::move(o));
objects.clear();
}
child->add(std::move(e));
}
bool Octree::is_leaf() const
{
// we're a leaf node if all children are null
return std::all_of(std::begin(children), std::end(children),
[](auto& x){return !x;});
}
int main()
{
Octree tree{{0,0,0}, {1,1,1}, 2};
tree.add({{0.3,0.3,-0.3}, 5});
tree.add({{0.3,0.3,-0.2}, 2});
}