Dev Log 4: Ray cast! (part1)

In this posts we will finally have some interaction with the 3d world!

So I am going to talk about ray casting and it's implementation in the broadphase.

What is Ray Casting?

Ray casting is the action of shooting a beam (infinite or not) through the scene and check what it hit.

How does it work?

Ray casting can be done through shader if is picking or through cpu if it is picking or not. I will explain the last one with picking also.

So here is a diagram of the beam.

There are two parts of this:

The picking direction (Yellow on the image above).

The ray casting it self (Blue in the image above).

1) The picking direction is the direction in which the pixel look at the 3d scene which is always forward the view axis. In order to explain this we need to look back at how a 3d scene is presented to the screen.

In the image above we see the transfomations a 3d point or vector undergoes to get to the screen. But we start at the screen space with the mouse coordinate so we need to use the inverse transforms to get to world space (note that we dont use model tranform here).

Now that we know what to do here is the pseudocode:

normalX = ((2 * MousePosX / WindowWidth) - 1) normalY = ((2 * MousePosY / WindowHeight) - 1) clipSpaceCoord = vec4(normalX, normalY, 0, 1) viewSpaceCoord = invertedProjMatrix * clipSpaceCoord worldSpaceCoord = invertedViewMatrix * viewSpaceCoord normalize(worldSpaceCoord)

2) Now the actual ray casting!

A ray is determined by origin, direction, inverted direction and distance(optional). I mark the distance optional because the basic is a infinite ray and returns a list of aabb's it intersects. So you test the ray against root aabb if it doesn't hit then the ray is completly out of the scene bounds. If it hits then you test against its children and choose which branch is better according to the distance or just test both until you get to a leaf and then test against it and if return true then add that aabb to the list of crossed objects or return that aabb as the closest (if you used the distance criteria).

How do I know if it intersect the AABB?

The algorithm is relatively easy. The AABB define a square with (in 2D) 4 lines. A line have the next equation:

Y = M*X + B

In the AABB this is found as:

Y1 = AABB.min.y Y2 = AABB.max.y

This are 2 parallel lines in Y axis but we also have:

X1 = AABB.min.x X2 = AABB.max.x

And the ray is also a line defined as:

(X,Y) = t * ray.Direction + ray.Origin

To find where these lines intersect we simply equate the equations:

Y1 = ty1 *ray.Direction.y + ray.Origin.y

t's are our unknown variables and to find them all we do:

ty1 = (Y1 - ray.Origin.y) * ray.InvDir.y ty2 = (Y2 - ray.Origin.y) * ray.InvDir.y tx1 = (X1 - ray.Origin.x) * ray.InvDir.x tx2 = (X2 - ray.Origin.x) * ray.InvDir.x

Since lines X1, X2, Y1, Y2 are infintes there will always be t's but how do we check they are in our defined limits?

Having in mind that t's are the size of the line that hit that particular axis point of the AABB we set:

tmin = min(tx1, tx2) tmax = max(tx1, tx2)

And now to check with the others axis we say:

tymax = max(ty1, ty2) tymin = min(ty1, ty2) tmin = max(tymin, tmin) tmax = min(tymax, tmax)

As we see above we need the max of the mins to be the minimum and the min of the max to be the maximum.

The intersection happens when tmax is gratter or equal to tmin and tmin always positive (forward in the ray direction):

bool intersection = tmax >= max(0, tmin)

We have the broadphase of the raycast done but if you want more accuracy on the ray intersection you need to test it against the object shape. I will post about it on the next part.

This is what llamathrust can do now!

RED: Point of intersection MAGENTA: normal vector

That's it for this post, folk. Bye!