dynamic_tree.h

// SPDX-FileCopyrightText: 2023 Erin Catto
// SPDX-License-Identifier: MIT
 
#pragma once
 
#include "box2d/api.h"
#include "box2d/constants.h"
#include "box2d/types.h"
 
#define b2_defaultCategoryBits (0x00000001)
#define b2_defaultMaskBits (0xFFFFFFFF)
 
typedef struct b2TreeNode
{
    b2AABB aabb; // 16
 
    // Category bits for collision filtering
    uint32_t categoryBits; // 4
 
    union
    {
        int32_t parent;
        int32_t next;
    }; // 4
 
    int32_t child1; // 4
    int32_t child2; // 4
 
    // todo could be union with child index
    int32_t userData; // 4
 
    // leaf = 0, free node = -1
    int16_t height; // 2
 
    bool enlarged; // 1
 
    char pad[9];
} b2TreeNode;
 
typedef struct b2DynamicTree
{
    b2TreeNode* nodes;
 
    int32_t root;
    int32_t nodeCount;
    int32_t nodeCapacity;
    int32_t freeList;
    int32_t proxyCount;
 
    int32_t* leafIndices;
    b2AABB* leafBoxes;
    b2Vec2* leafCenters;
    int32_t* binIndices;
    int32_t rebuildCapacity;
} b2DynamicTree;
 
BOX2D_API b2DynamicTree b2DynamicTree_Create(void);
 
BOX2D_API void b2DynamicTree_Destroy(b2DynamicTree* tree);
 
BOX2D_API int32_t b2DynamicTree_CreateProxy(b2DynamicTree* tree, b2AABB aabb, uint32_t categoryBits, int32_t userData);
 
BOX2D_API void b2DynamicTree_DestroyProxy(b2DynamicTree* tree, int32_t proxyId);
 
// Clone one tree to another, reusing storage in the outTree if possible
BOX2D_API void b2DynamicTree_Clone(b2DynamicTree* outTree, const b2DynamicTree* inTree);
 
BOX2D_API void b2DynamicTree_MoveProxy(b2DynamicTree* tree, int32_t proxyId, b2AABB aabb);
 
BOX2D_API void b2DynamicTree_EnlargeProxy(b2DynamicTree* tree, int32_t proxyId, b2AABB aabb);
 
typedef bool b2TreeQueryCallbackFcn(int32_t proxyId, int32_t userData, void* context);
 
BOX2D_API void b2DynamicTree_QueryFiltered(const b2DynamicTree* tree, b2AABB aabb, uint32_t maskBits,
                                           b2TreeQueryCallbackFcn* callback, void* context);
 
BOX2D_API void b2DynamicTree_Query(const b2DynamicTree* tree, b2AABB aabb, b2TreeQueryCallbackFcn* callback, void* context);
 
typedef float b2TreeRayCastCallbackFcn(const b2RayCastInput* input, int32_t proxyId, int32_t userData, void* context);
 
BOX2D_API void b2DynamicTree_RayCast(const b2DynamicTree* tree, const b2RayCastInput* input, uint32_t maskBits,
                                     b2TreeRayCastCallbackFcn* callback, void* context);
 
typedef float b2TreeShapeCastCallbackFcn(const b2ShapeCastInput* input, int32_t proxyId, int32_t userData, void* context);
 
BOX2D_API void b2DynamicTree_ShapeCast(const b2DynamicTree* tree, const b2ShapeCastInput* input, uint32_t maskBits,
                                       b2TreeShapeCastCallbackFcn* callback, void* context);
 
BOX2D_API void b2DynamicTree_Validate(const b2DynamicTree* tree);
 
BOX2D_API int32_t b2DynamicTree_GetHeight(const b2DynamicTree* tree);
 
BOX2D_API int32_t b2DynamicTree_GetMaxBalance(const b2DynamicTree* tree);
 
BOX2D_API float b2DynamicTree_GetAreaRatio(const b2DynamicTree* tree);
 
BOX2D_API void b2DynamicTree_RebuildBottomUp(b2DynamicTree* tree);
 
BOX2D_API int32_t b2DynamicTree_GetProxyCount(const b2DynamicTree* tree);
 
BOX2D_API int32_t b2DynamicTree_Rebuild(b2DynamicTree* tree, bool fullBuild);
 
BOX2D_API void b2DynamicTree_ShiftOrigin(b2DynamicTree* tree, b2Vec2 newOrigin);
 
static inline int32_t b2DynamicTree_GetUserData(const b2DynamicTree* tree, int32_t proxyId)
{
    return tree->nodes[proxyId].userData;
}
 
static inline b2AABB b2DynamicTree_GetAABB(const b2DynamicTree* tree, int32_t proxyId)
{
    return tree->nodes[proxyId].aabb;
}