A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
#ifndef EXT_RANDOM_ACCESS_HEAP_H
#define EXT_RANDOM_ACCESS_HEAP_H
#include "foundation/PxArray.h"
// MM: heap which allows the modification of the priorities of entries stored anywhere in the tree
// for this, every entry gets an id via which it can be accessed
// used in ExtMeshSimplificator to sort edges w.r.t. their error metric
// ------------------------------------------------------------------------------
namespace physx
{
namespace Ext
{
template <class T> class RandomAccessHeap
{
public:
RandomAccessHeap() {
heap.resize(1); // dummy such that root is at 1 for faster parent child computation
ids.resize(1);
nextId = 0;
}
void resizeFast(PxArray<PxI32>& arr, PxU32 newSize, PxI32 value = 0)
{
if (newSize < arr.size())
arr.removeRange(newSize, arr.size() - newSize);
else
{
while (arr.size() < newSize)
arr.pushBack(value);
}
}
PxI32 insert(T elem, PxI32 id = -1) // id for ability to alter the entry later or to identify duplicates
{
if (id < 0) {
id = nextId;
nextId++;
}
else if (id >= nextId)
nextId = id + 1;
if (id >= 0 && id < PxI32(posOfId.size()) && posOfId[id] >= 0)
return id; // already in heap
heap.pushBack(elem);
ids.pushBack(id);
if (id >= PxI32(posOfId.size()))
resizeFast(posOfId, id + 1, -1);
posOfId[id] = heap.size() - 1;
percolate(PxI32(heap.size()) - 1);
return id;
}
bool remove(PxI32 id)
{
PxI32 i = posOfId[id];
if (i < 0)
return false;
posOfId[id] = -1;
T prev = heap[i];
heap[i] = heap.back();
heap.popBack();
ids[i] = ids.back();
ids.popBack();
if (i < PxI32(heap.size()))
{
posOfId[ids[i]] = i;
if (heap.size() > 1)
{
if (heap[i] < prev)
percolate(i);
else
siftDown(i);
}
}
return true;
}
T deleteMin()
{
T min(-1, -1, 0.0f);
if (heap.size() > 1)
{
min = heap[1];
posOfId[ids[1]] = -1;
heap[1] = heap.back();
heap.popBack();
ids[1] = ids.back();
ids.popBack();
posOfId[ids[1]] = 1;
siftDown(1);
}
return min;
}
void makeHeap(const PxArray<T> &elems) // O(n) instead of inserting one after the other O(n log n)
{
heap.resize(elems.size() + 1);
ids.resize(elems.size() + 1);
posOfId.resize(elems.size());
for (PxU32 i = 0; i < elems.size(); i++)
{
heap[i + 1] = elems[i];
ids[i + 1] = i;
posOfId[ids[i + 1]] = i + 1;
}
PxI32 n = (heap.size() - 1) >> 1;
for (PxI32 i = n; i >= 1; i--)
siftDown(i);
}
void clear()
{
if (heap.capacity() == 0)
{
heap.resize(1);
}
else
{
heap.forceSize_Unsafe(1);
}
if (ids.capacity() == 0)
{
ids.resize(1);
}
else
{
ids.forceSize_Unsafe(1);
}
posOfId.forceSize_Unsafe(0);
nextId = 0;
}
PX_FORCE_INLINE PxI32 size() { return heap.size() - 1; }
PX_FORCE_INLINE bool empty() { return heap.size() <= 1; }
private:
void siftDown(PxI32 i)
{
PxI32 n = PxI32(heap.size()) - 1;
PxI32 k = i;
PxI32 j;
do
{
j = k;
if (2 * j < n && heap[2 * j] < heap[k])
k = 2 * j;
if (2 * j < n && heap[2 * j + 1] < heap[k])
k = 2 * j + 1;
T temp = heap[j]; heap[j] = heap[k]; heap[k] = temp;
PxI32 id = ids[j]; ids[j] = ids[k]; ids[k] = id;
posOfId[ids[j]] = j;
posOfId[ids[k]] = k;
}
while (j != k);
}
void percolate(PxI32 i)
{
PxI32 k = i;
PxI32 j;
do
{
j = k;
if (j > 1 && !(heap[j >> 1] < heap[k]))
k = j >> 1;
T temp = heap[j]; heap[j] = heap[k]; heap[k] = temp;
PxI32 id = ids[j]; ids[j] = ids[k]; ids[k] = id;
posOfId[ids[j]] = j;
posOfId[ids[k]] = k;
}
while (j != k);
}
PxArray<T> heap;
PxArray<PxI32> ids;
PxArray<PxI32> posOfId;
PxI32 nextId;
};
}
}
#endif