group2 0.1.0
CSE 125 Group 2
Loading...
Searching...
No Matches
physics::broadphase::Tree Class Reference

Dynamic AABB tree. More...

#include <BroadphaseTree.hpp>

Classes

struct  Node

Public Member Functions

 Tree ()=default
Proxy insertProxy (const WorldAABB &aabb, entt::entity entity)
 Insert a leaf at the given AABB.
bool updateProxy (Proxy p, const WorldAABB &newAabb, glm::vec3 displacement)
 Notify the tree that the entity's AABB moved.
void removeProxy (Proxy p)
 Destroy the leaf. The Proxy handle becomes invalid.
void queryAABB (const WorldAABB &aabb, const std::function< bool(entt::entity)> &visit) const
 Walk every leaf whose fat AABB overlaps aabb, calling visit(entity) for each.
void raycast (glm::vec3 origin, glm::vec3 dir, float maxT, const std::function< bool(entt::entity)> &visit) const
 Walk every leaf whose AABB intersects the ray segment [origin, origin + dir * maxT].
void sweptAABB (glm::vec3 halfExtents, glm::vec3 start, glm::vec3 end, const std::function< bool(entt::entity)> &visit) const
 Walk every leaf whose AABB intersects the swept-AABB [start, end] expanded by halfExtents.
void clear ()
 Clear all proxies and release pool memory.
int proxyCount () const noexcept
 Current proxy count (live leaves).
int32_t rootIndex () const noexcept
 Root node id (or -1 if empty). Exposed for debug viz.
WorldAABB nodeAabb (int32_t nodeId) const noexcept
 Read-only access to a node's AABB.
bool isLeaf (int32_t nodeId) const noexcept
 True iff the node is a leaf (no children, has entity).
int32_t leftChild (int32_t nodeId) const noexcept
 Left/right child of an interior node (or -1 if leaf / invalid).
int32_t rightChild (int32_t nodeId) const noexcept

Static Public Attributes

static constexpr float k_fatAabbMargin = 4.0f
 Margin added to every leaf's AABB so it doesn't reinsert on tiny movements.
static constexpr float k_motionPredict = 2.0f
 How aggressively to extend the fat AABB along the body's motion vector each update — multiplied by the displacement.

Private Member Functions

int32_t allocNode ()
void freeNode (int32_t id)
void insertLeaf (int32_t leaf)
void removeLeaf (int32_t leaf)
int32_t balance (int32_t a)

Static Private Member Functions

static WorldAABB combine (const WorldAABB &a, const WorldAABB &b)
static float aabbArea (const WorldAABB &a)
static bool aabbOverlap (const WorldAABB &a, const WorldAABB &b)
static bool aabbContains (const WorldAABB &container, const WorldAABB &inside)

Private Attributes

std::vector< Node > nodes_
int32_t root_ = -1
int32_t freeList_ = -1
int proxyCount_ = 0

Detailed Description

Dynamic AABB tree.

Not thread-safe — every mutating call must be serialised by the caller (typically the physics thread).

Constructor & Destructor Documentation

◆ Tree()

physics::broadphase::Tree::Tree ( )
default

Member Function Documentation

◆ aabbArea()

float physics::broadphase::Tree::aabbArea ( const WorldAABB & a)
staticprivate
Here is the caller graph for this function:

◆ aabbContains()

bool physics::broadphase::Tree::aabbContains ( const WorldAABB & container,
const WorldAABB & inside )
staticprivate
Here is the caller graph for this function:

◆ aabbOverlap()

bool physics::broadphase::Tree::aabbOverlap ( const WorldAABB & a,
const WorldAABB & b )
staticprivate
Here is the caller graph for this function:

◆ allocNode()

int32_t physics::broadphase::Tree::allocNode ( )
private
Here is the caller graph for this function:

◆ balance()

int32_t physics::broadphase::Tree::balance ( int32_t a)
private
Here is the call graph for this function:
Here is the caller graph for this function:

◆ clear()

void physics::broadphase::Tree::clear ( )

Clear all proxies and release pool memory.

◆ combine()

WorldAABB physics::broadphase::Tree::combine ( const WorldAABB & a,
const WorldAABB & b )
staticprivate
Here is the caller graph for this function:

◆ freeNode()

void physics::broadphase::Tree::freeNode ( int32_t id)
private
Here is the caller graph for this function:

◆ insertLeaf()

void physics::broadphase::Tree::insertLeaf ( int32_t leaf)
private
Here is the call graph for this function:
Here is the caller graph for this function:

◆ insertProxy()

Proxy physics::broadphase::Tree::insertProxy ( const WorldAABB & aabb,
entt::entity entity )

Insert a leaf at the given AABB.

Returns a handle the caller must keep for later update / remove.

Here is the call graph for this function:

◆ isLeaf()

bool physics::broadphase::Tree::isLeaf ( int32_t nodeId) const
nodiscardnoexcept

True iff the node is a leaf (no children, has entity).

Here is the caller graph for this function:

◆ leftChild()

int32_t physics::broadphase::Tree::leftChild ( int32_t nodeId) const
nodiscardnoexcept

Left/right child of an interior node (or -1 if leaf / invalid).

◆ nodeAabb()

WorldAABB physics::broadphase::Tree::nodeAabb ( int32_t nodeId) const
nodiscardnoexcept

Read-only access to a node's AABB.

Returns (boundsMin == boundsMax == 0) for an invalid id.

◆ proxyCount()

int physics::broadphase::Tree::proxyCount ( ) const
inlinenodiscardnoexcept

Current proxy count (live leaves).

◆ queryAABB()

void physics::broadphase::Tree::queryAABB ( const WorldAABB & aabb,
const std::function< bool(entt::entity)> & visit ) const

Walk every leaf whose fat AABB overlaps aabb, calling visit(entity) for each.

The visitor returns false to stop early, true to continue.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ raycast()

void physics::broadphase::Tree::raycast ( glm::vec3 origin,
glm::vec3 dir,
float maxT,
const std::function< bool(entt::entity)> & visit ) const

Walk every leaf whose AABB intersects the ray segment [origin, origin + dir * maxT].

Visitor returns false to stop.

◆ removeLeaf()

void physics::broadphase::Tree::removeLeaf ( int32_t leaf)
private
Here is the call graph for this function:
Here is the caller graph for this function:

◆ removeProxy()

void physics::broadphase::Tree::removeProxy ( Proxy p)

Destroy the leaf. The Proxy handle becomes invalid.

Here is the call graph for this function:

◆ rightChild()

int32_t physics::broadphase::Tree::rightChild ( int32_t nodeId) const
nodiscardnoexcept

◆ rootIndex()

int32_t physics::broadphase::Tree::rootIndex ( ) const
inlinenodiscardnoexcept

Root node id (or -1 if empty). Exposed for debug viz.

◆ sweptAABB()

void physics::broadphase::Tree::sweptAABB ( glm::vec3 halfExtents,
glm::vec3 start,
glm::vec3 end,
const std::function< bool(entt::entity)> & visit ) const

Walk every leaf whose AABB intersects the swept-AABB [start, end] expanded by halfExtents.

Used for player / projectile sweeps against dynamic bodies.

Here is the call graph for this function:

◆ updateProxy()

bool physics::broadphase::Tree::updateProxy ( Proxy p,
const WorldAABB & newAabb,
glm::vec3 displacement )

Notify the tree that the entity's AABB moved.

Returns true if the tree topology was actually adjusted.

Parameters
pProxy from a prior insertProxy.
newAabbTight AABB of the entity at its new position.
displacementMovement vector; used to fatten the new AABB so the next few frames stay inside the same leaf.
Here is the call graph for this function:

Member Data Documentation

◆ freeList_

int32_t physics::broadphase::Tree::freeList_ = -1
private

◆ k_fatAabbMargin

float physics::broadphase::Tree::k_fatAabbMargin = 4.0f
staticconstexpr

Margin added to every leaf's AABB so it doesn't reinsert on tiny movements.

In world units (matches your Quake-unit scale).

◆ k_motionPredict

float physics::broadphase::Tree::k_motionPredict = 2.0f
staticconstexpr

How aggressively to extend the fat AABB along the body's motion vector each update — multiplied by the displacement.

◆ nodes_

std::vector<Node> physics::broadphase::Tree::nodes_
private

◆ proxyCount_

int physics::broadphase::Tree::proxyCount_ = 0
private

◆ root_

int32_t physics::broadphase::Tree::root_ = -1
private
The documentation for this class was generated from the following files: