That code is so deceptive...
Let us see... the code you link is in the World
class. com.badlogic.gdx.physics.box2d.World
that is. We are looking at the method rayCast
.
In the method we see a call to world.raycast
.
Got it?
The call is to the method raycast
(not rayCast
) of the field world
(not the class World
).
And what type is the world
field? Well, it is of class World
. org.jbox2d.dynamics.World
that is.
Now, you got it.
This is the relevant raycast method:
public void raycast(RayCastCallback callback, Vec2 point1, Vec2 point2) {
wrcwrapper.broadPhase = m_contactManager.m_broadPhase;
wrcwrapper.callback = callback;
input.maxFraction = 1.0f;
input.p1.set(point1);
input.p2.set(point2);
m_contactManager.m_broadPhase.raycast(wrcwrapper, input);
}
Ok, so this is another delegation. We have to have a look at BroadPhase
... it is a freaking interface! - Alright, from where does it come from? It is injected in ContactManager
. Who creates ContactManager
? Well World of course. With what BroadPhase
? Guess... BroadPhase
injected too!
Alright, who creates World
? - World
! (the other one). However, it is using a constructor that does not pass BroadPhase
. That constructor overload uses DefaultWorldPool
and calls another overload that uses DynamicTree
and calls yet another overload.
There are two overload it could be calling. One takes an BroadPhaseStrategy
and the other a BroadPhase
.
To know which overload, we have to have a look at DynamicTree
. It implements BroadPhaseStrategy
- thus we are calling that overload and our BroadPhase
is DefaultBroadPhaseBuffer
.
DefaultBroadPhaseBuffer.raycast
:
public final void raycast(final TreeRayCastCallback callback, final RayCastInput input) {
m_tree.raycast(callback, input);
}
DynamicTree.raycast
:
public void raycast(TreeRayCastCallback callback, RayCastInput input) {
final Vec2 p1 = input.p1;
final Vec2 p2 = input.p2;
float p1x = p1.x, p2x = p2.x, p1y = p1.y, p2y = p2.y;
float vx, vy;
float rx, ry;
float absVx, absVy;
float cx, cy;
float hx, hy;
float tempx, tempy;
r.x = p2x - p1x;
r.y = p2y - p1y;
assert ((r.x * r.x + r.y * r.y) > 0f);
r.normalize();
rx = r.x;
ry = r.y;
// v is perpendicular to the segment.
vx = -1f * ry;
vy = 1f * rx;
absVx = MathUtils.abs(vx);
absVy = MathUtils.abs(vy);
// Separating axis for segment (Gino, p80).
// |dot(v, p1 - c)| > dot(|v|, h)
float maxFraction = input.maxFraction;
// Build a bounding box for the segment.
final AABB segAABB = aabb;
// Vec2 t = p1 + maxFraction * (p2 - p1);
// before inline
// temp.set(p2).subLocal(p1).mulLocal(maxFraction).addLocal(p1);
// Vec2.minToOut(p1, temp, segAABB.lowerBound);
// Vec2.maxToOut(p1, temp, segAABB.upperBound);
tempx = (p2x - p1x) * maxFraction + p1x;
tempy = (p2y - p1y) * maxFraction + p1y;
segAABB.lowerBound.x = p1x < tempx ? p1x : tempx;
segAABB.lowerBound.y = p1y < tempy ? p1y : tempy;
segAABB.upperBound.x = p1x > tempx ? p1x : tempx;
segAABB.upperBound.y = p1y > tempy ? p1y : tempy;
// end inline
nodeStackIndex = 0;
nodeStack[nodeStackIndex++] = m_root;
while (nodeStackIndex > 0) {
final DynamicTreeNode node = nodeStack[--nodeStackIndex];
if (node == null) {
continue;
}
final AABB nodeAABB = node.aabb;
if (!AABB.testOverlap(nodeAABB, segAABB)) {
continue;
}
// Separating axis for segment (Gino, p80).
// |dot(v, p1 - c)| > dot(|v|, h)
// node.aabb.getCenterToOut(c);
// node.aabb.getExtentsToOut(h);
cx = (nodeAABB.lowerBound.x + nodeAABB.upperBound.x) * .5f;
cy = (nodeAABB.lowerBound.y + nodeAABB.upperBound.y) * .5f;
hx = (nodeAABB.upperBound.x - nodeAABB.lowerBound.x) * .5f;
hy = (nodeAABB.upperBound.y - nodeAABB.lowerBound.y) * .5f;
tempx = p1x - cx;
tempy = p1y - cy;
float separation = MathUtils.abs(vx * tempx + vy * tempy) - (absVx * hx + absVy * hy);
if (separation > 0.0f) {
continue;
}
if (node.child1 == null) {
subInput.p1.x = p1x;
subInput.p1.y = p1y;
subInput.p2.x = p2x;
subInput.p2.y = p2y;
subInput.maxFraction = maxFraction;
float value = callback.raycastCallback(subInput, node.id);
if (value == 0.0f) {
// The client has terminated the ray cast.
return;
}
if (value > 0.0f) {
// Update segment bounding box.
maxFraction = value;
// temp.set(p2).subLocal(p1).mulLocal(maxFraction).addLocal(p1);
// Vec2.minToOut(p1, temp, segAABB.lowerBound);
// Vec2.maxToOut(p1, temp, segAABB.upperBound);
tempx = (p2x - p1x) * maxFraction + p1x;
tempy = (p2y - p1y) * maxFraction + p1y;
segAABB.lowerBound.x = p1x < tempx ? p1x : tempx;
segAABB.lowerBound.y = p1y < tempy ? p1y : tempy;
segAABB.upperBound.x = p1x > tempx ? p1x : tempx;
segAABB.upperBound.y = p1y > tempy ? p1y : tempy;
}
} else {
if (nodeStack.length - nodeStackIndex - 2 <= 0) {
DynamicTreeNode[] newBuffer = new DynamicTreeNode[nodeStack.length * 2];
System.arraycopy(nodeStack, 0, newBuffer, 0, nodeStack.length);
nodeStack = newBuffer;
}
nodeStack[nodeStackIndex++] = node.child1;
nodeStack[nodeStackIndex++] = node.child2;
}
}
}
Ah!
At a glance. DynamicTree
is a binary space partioning data structure, and the code is executing a query by walking the tree according to the direction of the raycast. It appears the implementation detail is that it will check collision between the the ray and the nodes of the tree to decide which branch to follow, it keeps a stack to backtrack if needed, and will continue until it reaches a leaf, and then it calls the callback.