Skip to main content
Code Review

Return to Answer

Commonmark migration
Source Link

#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:

Fixed bugs; added test/benchmark code
Source Link
Toby Speight
  • 87.8k
  • 14
  • 104
  • 325

#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
Post Undeleted by Toby Speight
Fixed a bug and an inconsistent comment
Source Link
Toby Speight
  • 87.8k
  • 14
  • 104
  • 325
 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});
}
Post Deleted by Toby Speight
Source Link
Toby Speight
  • 87.8k
  • 14
  • 104
  • 325
Loading
lang-cpp

AltStyle によって変換されたページ (->オリジナル) /