Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
AABBTreeToBuffer.h
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
10
12#include <deque>
14
16
17template <class T> using Deque = std::deque<T, STLAllocator<T>>;
18
20template <class TriangleCodec, class NodeCodec>
22{
23public:
25 using NodeHeader = typename NodeCodec::Header;
26
29
32
35
38
40 bool Convert(const VertexList &inVertices, const AABBTreeBuilder::Node *inRoot, const char *&outError)
41 {
42 const typename NodeCodec::EncodingContext node_ctx;
43 typename TriangleCodec::EncodingContext tri_ctx(inVertices);
44
45 // Estimate the amount of memory required
46 uint tri_count = inRoot->GetTriangleCountInTree();
47 uint node_count = inRoot->GetNodeCount();
48 uint nodes_size = node_ctx.GetPessimisticMemoryEstimate(node_count);
49 uint total_size = HeaderSize + TriangleHeaderSize + nodes_size + tri_ctx.GetPessimisticMemoryEstimate(tri_count);
50 mTree.reserve(total_size);
51
52 // Reset counters
53 mNodesSize = 0;
54
55 // Add headers
56 NodeHeader *header = HeaderSize > 0? mTree.Allocate<NodeHeader>() : nullptr;
57 TriangleHeader *triangle_header = TriangleHeaderSize > 0? mTree.Allocate<TriangleHeader>() : nullptr;
58
59 struct NodeData
60 {
61 const AABBTreeBuilder::Node * mNode = nullptr; // Node that this entry belongs to
62 Vec3 mNodeBoundsMin; // Quantized node bounds
63 Vec3 mNodeBoundsMax;
64 uint mNodeStart = uint(-1); // Start of node in mTree
65 uint mTriangleStart = uint(-1); // Start of the triangle data in mTree
66 uint mNumChildren = 0; // Number of children
67 uint mChildNodeStart[NumChildrenPerNode]; // Start of the children of the node in mTree
68 uint mChildTrianglesStart[NumChildrenPerNode]; // Start of the triangle data in mTree
69 uint * mParentChildNodeStart = nullptr; // Where to store mNodeStart (to patch mChildNodeStart of my parent)
70 uint * mParentTrianglesStart = nullptr; // Where to store mTriangleStart (to patch mChildTrianglesStart of my parent)
71 };
72
73 Deque<NodeData *> to_process;
74 Deque<NodeData *> to_process_triangles;
75 Array<NodeData> node_list;
76
77 node_list.reserve(node_count); // Needed to ensure that array is not reallocated, so we can keep pointers in the array
78
79 NodeData root;
80 root.mNode = inRoot;
81 root.mNodeBoundsMin = inRoot->mBounds.mMin;
82 root.mNodeBoundsMax = inRoot->mBounds.mMax;
83 node_list.push_back(root);
84 to_process.push_back(&node_list.back());
85
86 // Child nodes out of loop so we don't constantly realloc it
88 child_nodes.reserve(NumChildrenPerNode);
89
90 for (;;)
91 {
92 while (!to_process.empty())
93 {
94 // Get the next node to process
95 NodeData *node_data = to_process.back();
96 to_process.pop_back();
97
98 // Due to quantization box could have become bigger, not smaller
99 JPH_ASSERT(AABox(node_data->mNodeBoundsMin, node_data->mNodeBoundsMax).Contains(node_data->mNode->mBounds), "AABBTreeToBuffer: Bounding box became smaller!");
100
101 // Collect the first NumChildrenPerNode sub-nodes in the tree
102 child_nodes.clear(); // Won't free the memory
103 node_data->mNode->GetNChildren(NumChildrenPerNode, child_nodes);
104 node_data->mNumChildren = (uint)child_nodes.size();
105
106 // Fill in default child bounds
107 Vec3 child_bounds_min[NumChildrenPerNode], child_bounds_max[NumChildrenPerNode];
108 for (size_t i = 0; i < NumChildrenPerNode; ++i)
109 if (i < child_nodes.size())
110 {
111 child_bounds_min[i] = child_nodes[i]->mBounds.mMin;
112 child_bounds_max[i] = child_nodes[i]->mBounds.mMax;
113 }
114 else
115 {
116 child_bounds_min[i] = Vec3::sZero();
117 child_bounds_max[i] = Vec3::sZero();
118 }
119
120 // Start a new node
121 uint old_size = (uint)mTree.size();
122 node_data->mNodeStart = node_ctx.NodeAllocate(node_data->mNode, node_data->mNodeBoundsMin, node_data->mNodeBoundsMax, child_nodes, child_bounds_min, child_bounds_max, mTree, outError);
123 if (node_data->mNodeStart == uint(-1))
124 return false;
125 mNodesSize += (uint)mTree.size() - old_size;
126
127 if (node_data->mNode->HasChildren())
128 {
129 // Insert in reverse order so we process left child first when taking nodes from the back
130 for (int idx = int(child_nodes.size()) - 1; idx >= 0; --idx)
131 {
132 // Due to quantization box could have become bigger, not smaller
133 JPH_ASSERT(AABox(child_bounds_min[idx], child_bounds_max[idx]).Contains(child_nodes[idx]->mBounds), "AABBTreeToBuffer: Bounding box became smaller!");
134
135 // Add child to list of nodes to be processed
136 NodeData child;
137 child.mNode = child_nodes[idx];
138 child.mNodeBoundsMin = child_bounds_min[idx];
139 child.mNodeBoundsMax = child_bounds_max[idx];
140 child.mParentChildNodeStart = &node_data->mChildNodeStart[idx];
141 child.mParentTrianglesStart = &node_data->mChildTrianglesStart[idx];
142 NodeData *old = &node_list[0];
143 node_list.push_back(child);
144 if (old != &node_list[0])
145 {
146 outError = "Internal Error: Array reallocated, memory corruption!";
147 return false;
148 }
149
150 // Store triangles in separate list so we process them last
151 if (node_list.back().mNode->HasChildren())
152 to_process.push_back(&node_list.back());
153 else
154 to_process_triangles.push_back(&node_list.back());
155 }
156 }
157 else
158 {
159 // Add triangles
160 node_data->mTriangleStart = tri_ctx.Pack(node_data->mNode->mTriangles, mTree, outError);
161 if (node_data->mTriangleStart == uint(-1))
162 return false;
163 }
164
165 // Patch offset into parent
166 if (node_data->mParentChildNodeStart != nullptr)
167 {
168 *node_data->mParentChildNodeStart = node_data->mNodeStart;
169 *node_data->mParentTrianglesStart = node_data->mTriangleStart;
170 }
171 }
172
173 // If we've got triangles to process, loop again with just the triangles
174 if (to_process_triangles.empty())
175 break;
176 else
177 to_process.swap(to_process_triangles);
178 }
179
180 // Finalize all nodes
181 for (NodeData &n : node_list)
182 if (!node_ctx.NodeFinalize(n.mNode, n.mNodeStart, n.mNumChildren, n.mChildNodeStart, n.mChildTrianglesStart, mTree, outError))
183 return false;
184
185 // Finalize the triangles
186 tri_ctx.Finalize(inVertices, triangle_header, mTree);
187
188 // Validate that we reserved enough memory
189 if (nodes_size < mNodesSize)
190 {
191 outError = "Internal Error: Not enough memory reserved for nodes!";
192 return false;
193 }
194 if (total_size < (uint)mTree.size())
195 {
196 outError = "Internal Error: Not enough memory reserved for triangles!";
197 return false;
198 }
199
200 // Finalize the nodes
201 if (!node_ctx.Finalize(header, inRoot, node_list[0].mNodeStart, node_list[0].mTriangleStart, outError))
202 return false;
203
204 // Shrink the tree, this will invalidate the header and triangle_header variables
205 mTree.shrink_to_fit();
206
207 return true;
208 }
209
211 inline const ByteBuffer & GetBuffer() const
212 {
213 return mTree;
214 }
215
218 {
219 return mTree;
220 }
221
223 inline const NodeHeader * GetNodeHeader() const
224 {
225 return mTree.Get<NodeHeader>(0);
226 }
227
229 inline const TriangleHeader * GetTriangleHeader() const
230 {
231 return mTree.Get<TriangleHeader>(HeaderSize);
232 }
233
235 inline const void * GetRoot() const
236 {
237 return mTree.Get<void>(HeaderSize + TriangleHeaderSize);
238 }
239
240private:
241 ByteBuffer mTree;
242 uint mNodesSize;
243};
244
std::deque< T, STLAllocator< T > > Deque
Definition: AABBTreeToBuffer.h:17
#define JPH_SUPPRESS_WARNINGS_STD_BEGIN
Definition: Core.h:372
#define JPH_SUPPRESS_WARNINGS_STD_END
Definition: Core.h:384
unsigned int uint
Definition: Core.h:439
#define JPH_NAMESPACE_END
Definition: Core.h:367
#define JPH_NAMESPACE_BEGIN
Definition: Core.h:361
Array< Float3 > VertexList
Definition: Float3.h:43
#define JPH_ASSERT(...)
Definition: IssueReporting.h:33
std::vector< T, STLAllocator< T > > Array
Definition: STLAllocator.h:81
A node in the tree, contains the AABox for the tree and any child nodes or triangles.
Definition: AABBTreeBuilder.h:40
AABox mBounds
Bounding box.
Definition: AABBTreeBuilder.h:79
uint GetTriangleCountInTree() const
Get triangle count in tree.
Definition: AABBTreeBuilder.cpp:63
uint GetNodeCount() const
Number of nodes in tree.
Definition: AABBTreeBuilder.cpp:47
Conversion algorithm that converts an AABB tree to an optimized binary buffer.
Definition: AABBTreeToBuffer.h:22
bool Convert(const VertexList &inVertices, const AABBTreeBuilder::Node *inRoot, const char *&outError)
Convert AABB tree. Returns false if failed.
Definition: AABBTreeToBuffer.h:40
static const int TriangleHeaderSize
Size in bytes of the header for the triangles.
Definition: AABBTreeToBuffer.h:37
typename TriangleCodec::TriangleHeader TriangleHeader
Header for the triangles.
Definition: AABBTreeToBuffer.h:34
const ByteBuffer & GetBuffer() const
Get resulting data.
Definition: AABBTreeToBuffer.h:211
typename NodeCodec::Header NodeHeader
Header for the tree.
Definition: AABBTreeToBuffer.h:25
static const int HeaderSize
Size in bytes of the header of the tree.
Definition: AABBTreeToBuffer.h:28
static const int NumChildrenPerNode
Maximum number of children per node in the tree.
Definition: AABBTreeToBuffer.h:31
const TriangleHeader * GetTriangleHeader() const
Get header for triangles.
Definition: AABBTreeToBuffer.h:229
const NodeHeader * GetNodeHeader() const
Get header for tree.
Definition: AABBTreeToBuffer.h:223
ByteBuffer & GetBuffer()
Get resulting data.
Definition: AABBTreeToBuffer.h:217
const void * GetRoot() const
Get root of resulting tree.
Definition: AABBTreeToBuffer.h:235
Axis aligned box.
Definition: AABox.h:16
Vec3 mMin
Bounding box min and max.
Definition: AABox.h:300
bool Contains(const AABox &inOther) const
Check if this box contains another box.
Definition: AABox.h:137
Vec3 mMax
Definition: AABox.h:301
Simple byte buffer, aligned to a cache line.
Definition: ByteBuffer.h:16
Type * Allocate(size_t inSize=1)
Allocate block of data of inSize elements and return the pointer.
Definition: ByteBuffer.h:33
const Type * Get(size_t inPosition) const
Get object at inPosition (an offset in bytes)
Definition: ByteBuffer.h:61
This class encodes and compresses quad tree nodes.
Definition: NodeCodecQuadTreeHalfFloat.h:62
bool NodeFinalize(const AABBTreeBuilder::Node *inNode, uint inNodeStart, uint inNumChildren, const uint *inChildrenNodeStart, const uint *inChildrenTrianglesStart, ByteBuffer &ioBuffer, const char *&outError) const
Once all nodes have been added, this call finalizes all nodes by patching in the offsets of the child...
Definition: NodeCodecQuadTreeHalfFloat.h:136
uint GetPessimisticMemoryEstimate(uint inNodeCount) const
Get an upper bound on the amount of bytes needed for a node tree with inNodeCount nodes.
Definition: NodeCodecQuadTreeHalfFloat.h:65
bool Finalize(Header *outHeader, const AABBTreeBuilder::Node *inRoot, uint inRootNodeStart, uint inRootTrianglesStart, const char *&outError) const
Once all nodes have been finalized, this will finalize the header of the nodes.
Definition: NodeCodecQuadTreeHalfFloat.h:166
uint NodeAllocate(const AABBTreeBuilder::Node *inNode, Vec3Arg inNodeBoundsMin, Vec3Arg inNodeBoundsMax, Array< const AABBTreeBuilder::Node * > &ioChildren, Vec3 outChildBoundsMin[NumChildrenPerNode], Vec3 outChildBoundsMax[NumChildrenPerNode], ByteBuffer &ioBuffer, const char *&outError) const
Definition: NodeCodecQuadTreeHalfFloat.h:75
static constexpr int HeaderSize
Size of the header (an empty struct is always > 0 bytes so this needs a separate variable)
Definition: NodeCodecQuadTreeHalfFloat.h:29
static constexpr int NumChildrenPerNode
Number of child nodes of this node.
Definition: NodeCodecQuadTreeHalfFloat.h:18
This class is used to encode and compress triangle data into a byte buffer.
Definition: TriangleCodecIndexed8BitPackSOA4Flags.h:123
uint Pack(const IndexedTriangleList &inTriangles, ByteBuffer &ioBuffer, const char *&outError)
Definition: TriangleCodecIndexed8BitPackSOA4Flags.h:142
uint GetPessimisticMemoryEstimate(uint inTriangleCount) const
Get an upper bound on the amount of bytes needed to store inTriangleCount triangles.
Definition: TriangleCodecIndexed8BitPackSOA4Flags.h:134
void Finalize(const VertexList &inVertices, TriangleHeader *ioHeader, ByteBuffer &ioBuffer) const
After all triangles have been packed, this finalizes the header and triangle buffer.
Definition: TriangleCodecIndexed8BitPackSOA4Flags.h:206
Definition: TriangleCodecIndexed8BitPackSOA4Flags.h:27
static constexpr int TriangleHeaderSize
Size of the header (an empty struct is always > 0 bytes so this needs a separate variable)
Definition: TriangleCodecIndexed8BitPackSOA4Flags.h:34
Definition: Vec3.h:16
static JPH_INLINE Vec3 sZero()
Vector with all zeros.
Definition: Vec3.inl:107
Header for the tree.
Definition: NodeCodecQuadTreeHalfFloat.h:22