Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Branch and Bound for b2DynamicTree #548

Closed
wants to merge 6 commits into from
Closed

Branch and Bound for b2DynamicTree #548

Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift click to select a range
bf36001
Branch and bound insertion method.
RandyGaul Jun 22, 2019
470004b
match camel case
RandyGaul Jun 22, 2019
dd562c9
kill dead comment
RandyGaul Jun 22, 2019
25aff53
more camel case and style fitting
RandyGaul Jun 22, 2019
a778ac0
Some links
RandyGaul Jun 22, 2019
d3a69b1
Typo and camel case
RandyGaul Jun 26, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
match camel case
  • Loading branch information
@RandyGaul
RandyGaul committed Jun 22, 2019
commit 470004bbf89d677a7deae2ab00ef671fffa9dc41
62 changes: 31 additions & 31 deletions Box2D/Collision/b2DynamicTree.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -191,15 191,15 @@ struct b2PriorityQueue
{
m_capacity *= 2;

float32* old_costs = m_costs;
float32* oldCosts = m_costs;
m_costs = (float32*)b2Alloc(m_capacity * sizeof(float32));
memcpy(m_costs, old_costs, m_count * sizeof(float32));
if (old_costs != m_costArray) b2Free(old_costs);
memcpy(m_costs, oldCosts, m_count * sizeof(float32));
if (oldCosts != m_costArray) b2Free(oldCosts);

int32* old_indices = m_indices;
int32* oldIndices = m_indices;
m_indices = (int32*)b2Alloc(m_capacity * sizeof(int32));
memcpy(m_indices, old_indices, m_count * sizeof(int32));
if (old_indices != m_indexArray) b2Free(old_indices);
memcpy(m_indices, oldIndices, m_count * sizeof(int32));
if (oldIndices != m_indexArray) b2Free(oldIndices);
}

m_indices[m_count] = index;
Expand Down Expand Up @@ -246,9 246,9 @@ struct b2PriorityQueue
private:
inline int32 Predicate(int32 index_a, int32 index_b)
{
float32 cost_a = m_costs[index_a];
float32 cost_b = m_costs[index_b];
return cost_a < cost_b ? -1 : cost_a > cost_b ? 1 : 0;
float32 costA = m_costs[index_a];
float32 costB = m_costs[index_b];
return costA < costB ? -1 : costA > costB ? 1 : 0;
}

inline void Swap(int32 index_a, int32 index_b)
Expand Down Expand Up @@ -287,34 287,34 @@ int32 b2DynamicTree::PickBest(b2AABB to_insert)
b2PriorityQueue queue;
queue.Push(m_root, InheritedCost(to_insert, m_nodes[m_root].aabb));

float to_insert_sa = to_insert.GetPerimeter();
float best_cost = FLT_MAX;
int best_index = b2_nullNode;
int search_index;
float search_delta_cost;
while (queue.Pop(&search_index, &search_delta_cost))
{
b2AABB search_aabb = m_nodes[search_index].aabb;
float cost = Cost(to_insert, search_aabb) search_delta_cost;
if (cost < best_cost) {
best_cost = cost;
best_index = search_index;
float toInsertSurfaceArea = to_insert.GetPerimeter();
float bestCost = FLT_MAX;
int bestIndex = b2_nullNode;
int searchIndex;
float searchInheritedCost;
while (queue.Pop(&searchIndex, &searchInheritedCost))
{
b2AABB search_aabb = m_nodes[searchIndex].aabb;
float cost = Cost(to_insert, search_aabb) searchInheritedCost;
if (cost < bestCost) {
bestCost = cost;
bestIndex = searchIndex;
}

float delta_cost = InheritedCost(to_insert, search_aabb) search_delta_cost;
float lower_bound = to_insert_sa delta_cost;
if (lower_bound < best_cost) {
int child1 = m_nodes[search_index].child1;
int child2 = m_nodes[search_index].child2;
float inheritedCost = InheritedCost(to_insert, search_aabb) searchInheritedCost;
float lower_bound = toInsertSurfaceArea inheritedCost;
if (lower_bound < bestCost) {
int child1 = m_nodes[searchIndex].child1;
int child2 = m_nodes[searchIndex].child2;
if (child1 != b2_nullNode) {
assert(child2 != b2_nullNode);
queue.Push(child1, delta_cost);
queue.Push(child2, delta_cost);
queue.Push(child1, inheritedCost);
queue.Push(child2, inheritedCost);
}
}
}

return best_index;
return bestIndex;
}

void b2DynamicTree::InsertLeaf(int32 leaf)
Expand Down Expand Up @@ -484,7 484,7 @@ int32 b2DynamicTree::Balance(int32 iA)
C->parent = A->parent;
A->parent = iC;

// A's old_costs parent should point to C
// A's old parent should point to C
if (C->parent != b2_nullNode)
{
if (m_nodes[C->parent].child1 == iA)
Expand Down Expand Up @@ -544,7 544,7 @@ int32 b2DynamicTree::Balance(int32 iA)
B->parent = A->parent;
A->parent = iB;

// A's old_costs parent should point to B
// A's old parent should point to B
if (B->parent != b2_nullNode)
{
if (m_nodes[B->parent].child1 == iA)
Expand Down