Can someone explain me how rayCast works?

Question

Im learning libgdx and one of the things that really confuses me its raycasting. I read a tutorial of how to use it and I understand it but I really want to know what's in the back. I searched for the source code of this method.

public void rayCast (final RayCastCallback callback, float point1X, float point1Y, float point2X, float point2Y) {   // FIXME pool RayCastCallback?
    world.raycast(new org.jbox2d.callbacks.RayCastCallback() {
    @Override
    public float reportFixture (org.jbox2d.dynamics.Fixture f, Vec2 p, Vec2 n, float fraction) {
        return callback.reportRayFixture(fixtures.get(f), point.set(p.x, p.y), normal.set(n.x, n.y), fraction);
    }
}, this.point1.set(point1X, point1Y), this.point2.set(point2X, point2Y));

} How we can see this method calls itself recursively and returns a call to reportRayFixture of the callback variable. The thing that really confused me it's from where the code select the Fixture, and how its checks every fixture. Can someone explain me really how its works.

This its the source code page https://github.com/libgdx/libgdx/blob/master/extensions/gdx-box2d/gdx-box2d-gwt/src/com/badlogic/gdx/physics/box2d/gwt/emu/com/badlogic/gdx/physics/box2d/World.java

I will appreciate it!

Answer 1

Raycasting is when we draw an invisible line through space and see what it intersects with. A common use for this is to figure out what a player is clicking on- we draw a line from the camera in the direction that the player is clicking, and the first object our line touches is the line the player clicked on.

In Box2D, the RayCastCallback interface is used to allow you to write code that gets executed when your ray hits a Fixture (for example, you may want to ignore certain fixtures). I haven't used this personally, but I imagine you could use something like this in a shooter game to see if a wall-penetrating weapon could hit an object behind a wall (or something like that).

At a high level, what this lovely piece of code is doing is a little slight of hand- if you look at it really closely, what it's doing is taking in the libGDX RayCastCallback and wrapping it in a JBox2D RayCastCallback which has a slightly different API. It's more like it's overloading the method than calling it recursively.

What I don't know is why the author chose to create the Point1 and Point2 instance variables. I would think if you had multiple fixtures they would get overridden, so perhaps they are supposed to contain the last fixture hit by the ray? Even so, it looks like multiple raycasts would overwrite them.

Answer 2

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.