Jump to content
  • Advertisement
midn

Algorithm Get angle of ray&AABB intersection?

Recommended Posts

Posted (edited)

I have modified the HitBoundingBox algorithm that can be found on some sources (link) to suit my structs and API:

Point rayaabbintersection(Point minB, Point maxB, Point origin, Point dir) {
	char inside = TRUE;
	char quadrant[2];
	register int i;
	int whichPlane;
	double maxT[2];
	double candidatePlane[2];
	
	/* Find candidate planes; this loop can be avoided if
   	rays cast all from the eye(assume perpsective view) */
	for (i=0; i<2; i++)
		if(origin.arr[i] < minB.arr[i]) {
			quadrant[i] = LEFT;
			candidatePlane[i] = minB.arr[i];
			inside = FALSE;
		}else if (origin.arr[i] > maxB.arr[i]) {
			quadrant[i] = RIGHT;
			candidatePlane[i] = maxB.arr[i];
			inside = FALSE;
		}else	{
			quadrant[i] = MIDDLE;
		}

	/* Ray origin inside bounding box */
	if(inside)	{
		return origin;
	}


	/* Calculate T distances to candidate planes */
	for (i = 0; i < 2; i++)
		if (quadrant[i] != MIDDLE && dir.arr[i] !=0.)
			maxT[i] = (candidatePlane[i] - origin.arr[i]) / dir.arr[i];
		else
			maxT[i] = -1.;

	/* Get largest of the maxT's for final choice of intersection */
	whichPlane = 0;
	for (i = 1; i < 2; i++)
		if (maxT[whichPlane] < maxT[i])
			whichPlane = i;

	float coord[2];

	/* Check final candidate actually inside box */
	if (maxT[whichPlane] < 0.) return (Point) {.x = NAN, .y = NAN};
	for (i = 0; i < 2; i++)
		if (whichPlane != i) {
			coord[i] = origin.arr[i] + maxT[whichPlane] * dir.arr[i];
			if (coord[i] < minB.arr[i] || coord[i] > maxB.arr[i])
				return (Point) {.x = NAN, .y = NAN};
		} else {
			coord[i] = candidatePlane[i];
		}
	return (Point) {.x = coord[0], .y = coord[1]}; /* ray hits box */
}

Excuse the bad code, it's a copy paste of the original with a few changes :P. The reason for all those iterations over i is because the original was designed allow technically any amount of dimensions.
Anyway, I'm terribly bad at geometry, does anyone know how I can get the angle of the intersection?

Edited by Midnightas

Share this post


Link to post
Share on other sites
Advertisement

Can you clarify what you mean by angle of intersection? I can imagine it meaning (for example) the absolute angle of the ray with respect to the coordinate system, or either of the two angles formed where the ray (potentially) meets an edge of the box (that is, the angle on the 'left' and 'right' of the ray, where the two angles sum to 180 degrees).

If you could post an image or a text diagram, that might be the easiest way to demonstrate what you mean.

Share this post


Link to post
Share on other sites
30 minutes ago, Zakwayda said:

Can you clarify what you mean by angle of intersection? I can imagine it meaning (for example) the absolute angle of the ray with respect to the coordinate system, or either of the two angles formed where the ray (potentially) meets an edge of the box (that is, the angle on the 'left' and 'right' of the ray, where the two angles sum to 180 degrees).

If you could post an image or a text diagram, that might be the easiest way to demonstrate what you mean.

I can't explain it in words, because I don't know the terminology, but I have drawn a gimp diagram where the black rectangles are AABBs and red lines are rays.
image.png.b185dff3ad45d1abbe56565fd11a37ba.png

Share this post


Link to post
Share on other sites

Thanks for the diagram :)

This is off the top of my head, so I can't guarantee I won't make any mistakes here.

You can compute the angle between two 2-d vectors a and b as follows:

angle = atan2(perp_dot(a, b), dot(a, b))

For your case, compute the angle between the ray direction vector and either of the direction vectors for the intersected edge. For a horizontal edge you'd use (1, 0) or (-1, 0), and for a vertical edge you'd use (0, 1) or (0, -1). Since the edge vector elements are always 0 or +/-1, you can simplify/optimize the angle computation if you wish.

This will give you one of the two angles. Subtract from pi (or 180 if you're using degrees) to get the other angle. Based on your diagram it looks like you want the smaller angle, so select the smaller of the two (of course it's possible the two angles will be equal, as appears to be the case in your second example, in which case it doesn't matter which one you pick).

There are probably other ways it can be done, but that's the first solution that comes to mind.

Share this post


Link to post
Share on other sites
Posted (edited)

I'd be doing that probably at most around ~30 times per frame, so I don't think I'd need to optimize it further. Thank you, I'll test it when I have the time!

I don't actually need the smaller angle, I need one of the angles to calculate the direction in which the ray will bounce (according to physical laws), so any angle's fine (if I'm on the right track).

Edited by midn

Share this post


Link to post
Share on other sites

Quick question that I didn't think of: How would I know which edge was hit?

Share this post


Link to post
Share on other sites
Posted (edited)
27 minutes ago, midn said:

Quick question that I didn't think of: How would I know which edge was hit?

Based on a quick look at the code, I think 'whichPlane' tells you that. (It's either 0 for a horizontal edge and 1 for a vertical edge or vice versa - I didn't examine the code closely enough to determine which.)

Quote

I don't actually need the smaller angle, I need one of the angles to calculate the direction in which the ray will bounce (according to physical laws), so any angle's fine (if I'm on the right track).

For that, you can (and probably should) use vector reflection rather than angles. (I say 'probably should' because angles can be fiddly to work with for various reasons. Working directly with vectors can be more straightforward in many cases.)

You'll need the normal of the edge that the ray hit, which you can get from 'whichPlane' and (for example) the ray direction or the location of the intersection point. You'd then reflect the ray direction with respect to that normal.

I realize I'm not including all the details there, but I'd start by searching for something like '2d vector reflection' to see what you can find (the algorithm is straightforward, and is dimension-independent, so if you find a 3-d version, you can use it for 2-d as well).

Obviously if you run into problems, you can post back.

[Edit: Technically, 'whichPlane' only tells you the direction of the edge, and not specifically which edge was intersected. That's sufficient for computing the angle, but for the reflection method you need to know the exact edge, which I explained later how to find.]

Edited by Zakwayda

Share this post


Link to post
Share on other sites

I mean.. it works, but the entire game in general is extremely buggy.

image.png.597ce723a8309a3db624344bd67c3658.png

I don't even know what is causing this.

This thread's issue is solved, though, so thanks!

Share this post


Link to post
Share on other sites

I'm not sure what's happening in the image you posted, but if you're not sure if the reflection is working, you might try testing it in isolation, making sure you have the correct normals, and so on.

Even if the reflection part is correct, there are many other things that can go wrong in collision detection and response (often having to do with numerical error). Again, performing controlled tests in isolation might help you narrow things down.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!