galaxy
galaxy copied to clipboard
Published
20 hours ago •
reworks-org
reworks-org
QuadTree Culling
m_quadtree.clear(); m_output.clear();
m_quadtree.resize(SL_HANDLE.window()->get_width(), SL_HANDLE.window()->get_height());
scene->m_world.operate<components::Renderable>([&](const ecs::Entity entity, components::Renderable* renderable) {
m_quadtree.insert({.m_aabb = &renderable->get_aabb(), .m_entity = entity, .m_type = renderable->m_type});
});
m_quadtree.query({.m_aabb = &scene->m_camera.get_aabb()}, m_output);
m_quadtree.clear(); m_output.clear();
if (!scene->get_active_map())
{
m_quadtree.resize(SL_HANDLE.window()->get_width(), SL_HANDLE.window()->get_height());
}
else
{
m_quadtree.resize(scene->get_active_map()->get_width(), scene->get_active_map()->get_height());
}
scene->m_world.operate<components::RigidBody, components::Renderable>(
[&](const ecs::Entity entity, components::RigidBody* body, components::Renderable* renderable) {
m_quadtree.insert({.m_aabb = &renderable->get_aabb(), .m_entity = entity});
});
m_quadtree.query({.m_aabb = &scene->m_camera.get_aabb(), .m_entity = 0}, m_output);
/// /// QuadTree.hpp /// galaxy /// /// Refer to LICENSE.txt for more details. ///
#ifndef GALAXY_MATH_QUADTREE_HPP_ #define GALAXY_MATH_QUADTREE_HPP_
#include
#include "galaxy/ecs/Entity.hpp" #include "galaxy/graphics/Renderables.hpp" #include "galaxy/math/AABB.hpp" #include "galaxy/math/Rect.hpp"
namespace galaxy { namespace math { /// /// 2D spacial partitioning. /// class Quadtree final { public: /// /// Entity with AABB. /// struct Object final { /// /// Entity AABB from Renderable component. /// AABB* m_aabb;
///
/// Entity AABB belongs to.
///
ecs::Entity m_entity;
///
/// Renderable type.
///
graphics::Renderables m_type;
};
///
/// Argument constructor.
///
/// \param level Level of this quadtree. First is 0.
/// \param bounds Quadtree bounds.
/// \param max_objects Optional. Max objects in a quadtree before splitting.
/// \param max_levels Optional. Total number of levels allowed in a quadtree.
///
Quadtree(const int level, const Rect<float>& bounds, int max_objects = 10, int max_levels = 5) noexcept;
///
/// Destructor.
///
~Quadtree() noexcept;
///
/// Resize quadtree bounds.
///
/// \param width New quadtree width.
/// \param height New quadtree height.
///
void resize(const int width, const int height) noexcept;
///
/// \brief Insert an object into the quadtree.
///
/// If the node exceeds the capacity, it will split and add all objects to their corresponding nodes.
///
/// \param object Object to be inserted.
///
void insert(const Quadtree::Object& object);
///
/// Return all entities in the same spacial partition.
///
/// \param object Object to check.
/// \param output Array of objects that are in the same spacial partition.
///
void query(const Quadtree::Object& object, std::vector<Quadtree::Object*>& output);
///
/// Clears the quadtree.
///
void clear();
private:
///
/// Constructor.
///
Quadtree() = delete;
///
/// Splits the quadtree into 4 sub-trees.
///
void split();
///
/// Determine which node the object belongs to.
///
/// \param object Object to query its spacial index.
///
/// \return Index of object. -1 means object cannot completely fit within a child tree and is part of the parent tree.
///
[[nodiscard]] const int get_index(const Quadtree::Object& object);
private:
///
/// Current tree level.
///
int m_level;
///
/// Tree bounds.
///
Rect<float> m_bounds;
///
/// Max objects in a partition.
///
int m_max_objects;
///
/// Max levels in the tree.
///
int m_max_levels;
///
/// List of stored objects.
///
std::vector<Quadtree::Object> m_objects;
///
/// Sub-trees.
///
std::array<std::unique_ptr<Quadtree>, 4> m_nodes;
};
} // namespace math
} // namespace galaxy
#endif
/// /// QuadTree.cpp /// galaxy /// /// Refer to LICENSE.txt for more details. ///
#include "QuadTree.hpp"
namespace galaxy
{
namespace math
{
Quadtree::Quadtree(const int level, const Rect
Quadtree::~Quadtree() noexcept
{
clear();
}
void Quadtree::resize(const int width, const int height) noexcept
{
m_bounds.m_width = width;
m_bounds.m_height = height;
}
void Quadtree::insert(const Quadtree::Object& object)
{
if (m_nodes[0] != nullptr)
{
const auto index = get_index(object);
if (index != -1)
{
m_nodes[index]->insert(object);
return;
}
}
m_objects.push_back(object);
if (m_objects.size() > m_max_objects && m_level < m_max_levels)
{
if (m_nodes[0] == nullptr)
{
split();
}
for (auto it = m_objects.begin(); it != m_objects.end();)
{
const auto index = get_index(*it);
if (index != -1)
{
m_nodes[index]->insert(*it);
it = m_objects.erase(it);
}
else
{
++it;
}
}
}
}
void Quadtree::query(const Quadtree::Object& object, std::vector<Quadtree::Object*>& output)
{
const auto index = get_index(object);
if (index != -1 && m_nodes[0] != nullptr)
{
m_nodes[index]->query(object, output);
}
output.reserve(output.size() + m_objects.size());
for (auto& object : m_objects)
{
output.push_back(&object);
}
}
void Quadtree::clear()
{
m_objects.clear();
for (auto& node : m_nodes)
{
node.reset();
node = nullptr;
}
}
void Quadtree::split()
{
Rect<float> new_bounds;
new_bounds.m_x = m_bounds.m_x + (m_bounds.m_width / 2.0f);
new_bounds.m_y = m_bounds.m_y;
new_bounds.m_width = m_bounds.m_width / 2.0f;
new_bounds.m_height = m_bounds.m_height / 2.0f;
m_nodes[0] = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);
new_bounds.m_x = m_bounds.m_x;
new_bounds.m_y = m_bounds.m_y;
new_bounds.m_width = m_bounds.m_width / 2.0f;
new_bounds.m_height = m_bounds.m_height / 2.0f;
m_nodes[1] = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);
new_bounds.m_x = m_bounds.m_x;
new_bounds.m_y = m_bounds.m_y + (m_bounds.m_height / 2.0f);
new_bounds.m_width = m_bounds.m_width / 2.0f;
new_bounds.m_height = m_bounds.m_height / 2.0f;
m_nodes[2] = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);
new_bounds.m_x = m_bounds.m_x + (m_bounds.m_width / 2.0f);
new_bounds.m_y = m_bounds.m_y + (m_bounds.m_height / 2.0f);
new_bounds.m_width = m_bounds.m_width / 2.0f;
new_bounds.m_height = m_bounds.m_height / 2.0f;
m_nodes[3] = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);
}
const int Quadtree::get_index(const Quadtree::Object& object)
{
int index = -1;
const double vert_midpoint = object.m_aabb->min().x + (object.m_aabb->size().x / 2.0f);
const double hori_midpoint = object.m_aabb->min().y + (object.m_aabb->size().y / 2.0f);
const bool fits_in_top = (object.m_aabb->min().y < hori_midpoint && object.m_aabb->min().y + object.m_aabb->size().y < hori_midpoint);
const bool fits_in_bottom = (object.m_aabb->min().y > hori_midpoint);
if (object.m_aabb->min().x < vert_midpoint && object.m_aabb->min().x + object.m_aabb->size().x < vert_midpoint)
{
if (fits_in_top)
{
index = 1;
}
else if (fits_in_bottom)
{
index = 2;
}
}
else if (object.m_aabb->min().x > vert_midpoint)
{
if (fits_in_top)
{
index = 0;
}
else if (fits_in_bottom)
{
index = 3;
}
}
return index;
}
} // namespace math
} // namespace galaxy
https://pvigier.github.io/2019/08/11/vagabond-2d-physics-engine.html https://github.com/pvigier/Quadtree https://github.com/RandyGaul/cute_headers