• Advertisement
Sign in to follow this  

Ray Intersections!

This topic is 3720 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

!!! QUESTION OBSOLETE, NEW QUESTION POSTED !!! Check out last post! Hello Dear Collision experts! :D I'm here to ask you for help in such a nice part of collision engine: Ray Intersections... Ray vs Static/Swept Circle test. to test with intersections along ray, and one part of these testing is a test with swept circle. Take a look: Click to Enlarge Because I'm a bad geometrist I can only paint these conceptions as on upper image I show, and in practical sense, only guess how this calculating... So now: I know how perform static circle vs ray test, but what to do with dynamic test??? Please Help! [Edited by - Lolmen on November 14, 2007 3:56:32 AM]

Share this post


Link to post
Share on other sites
Advertisement
I didn't look at your non-static circle/ray test. I did look at your static circle/ray test and see numerous problems. For example, your code...


float delta_dist = (ray.GetRaySrc() - center).Length();

if( delta_dist < radius_sq )
{
return false;
}


...looks quite wrong.

First you compute some distance, delta_dist, using ray.GetRaySrc() and the center of the circle. You don't define GetRaySrc, but I assume it means the starting point of the ray. The distance between the start of the ray and the circle cannot be used to determine if the ray does or does not hit the circle, so your if/return block shouldn't be there. The reason is that the other end of the ray could be anywhere...if the 2nd ray point is in the middle of the circle, then the starting point can be anywhere in space outside of the circle and you have an intersection. Your test does not check this.

Second, supposing you could determine that there is not an intersection based purely one point of the ray...your if should then look like "if delta_dist > ..." instead of "if delta_idst < ...". The idea is that if the ray is closer than the radius of the circle...then the ray hits. If the ray is farther away than the radius of the circle, then ray is not hitting the circle.

Finally, and quite important, you compute delta_dist, which is a non-squared length, then you compare against radius_sq, a squared length. This does not work. You can't compare a squared distance against a non-squared distance. They are incompatible. A more appropriate test is to never compute the non-squared distance. Replace your length() method with a lengthsq() method that never takes a square root, then compare a squared length against the squared radius.

I didn't take the time to read further than that.

So, here's a link to a discussion that may be useful.

First, the static case.

Intersection of a line and a sphere (or circle) - static version

The moving circle/line segment can be done much like the 3D swept-sphere line segment test. The following document discusses this, and even has a swept circle vs. edge (line segment) section. It has code and math, and I certainly encourage you to learn and understand the math!

Collision Detection with Swept Spheres and Ellipsoids

Share this post


Link to post
Share on other sites
Whoa, Finally!
I'm implement static circle vs ray method...
So what the deal with swept?


// Code was exscind

[Edited by - Lolmen on November 13, 2007 10:29:01 AM]

Share this post


Link to post
Share on other sites
no deal with swept. Usually, you consider things from the sphere point of view, and that means that the travel vector of the sphere gets subtracted from ray segment.

say you have ray in the form [O, D], and a sphere [C, V, r], then it is equivalent to doing the test fo ray [O, (D - V)], and static sphere [C, r].

note that you have to be careful about 'units' and quantities. it depends what V and D refer to (velocity, normalised direction, displacements?). I usually consider a ray as a trvelling point, than makes things easier, since the quantities will match.

similarly, if you want ot do the test of two swept spheres [Ca, Va, ra] and [Cb, Vb, rb], then it's equivalent with testing the ray [Ca, (Va - Vb)] with the static sphere [Cb, (rb + ra)].

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
no deal with swept. Usually, you consider things from the sphere point of view, and that means that the travel vector of the sphere gets subtracted from ray segment.

say you have ray in the form [O, D], and a sphere [C, V, r], then it is equivalent to doing the test fo ray [O, (D - V)], and static sphere [C, r].

note that you have to be careful about 'units' and quantities. it depends what V and D refer to (velocity, normalised direction, displacements?). I usually consider a ray as a trvelling point, than makes things easier, since the quantities will match.

similarly, if you want ot do the test of two swept spheres [Ca, Va, ra] and [Cb, Vb, rb], then it's equivalent with testing the ray [Ca, (Va - Vb)] with the static sphere [Cb, (rb + ra)].


So, you just mean here that I can just do like this?

// Code was exscind

It's be correct?

I also notice a bug in my code figured by mathematical sample...
I know that to fix a bug I just need test do rayStart point is inside of a circle, but if there a swept, I dunno how to be...

// Image was exscind, because we don't need it anymore...

[Edited by - Lolmen on November 13, 2007 10:37:26 AM]

Share this post


Link to post
Share on other sites
nope, not just like this.

for example, your ray is two vectors. start and end, or a origin and 'displacement'. So that's a distance, so for example meters.

your sphere vector is a 'velocity'. so that's meters / seconds or whatever.

so you need to match up the units. I suppose you would have to model your swept sphere as a sphere going from a start to an end point.

Share this post


Link to post
Share on other sites
Ok, I try to figure it out somehow...

Another case is ray vs AABB, my problem is determine the unit vector of direction AABB face, lets just say : normal to a intersection plane.

So here the code :

// Code was exscind, it obsolete and not work properly.


[Edited by - Lolmen on November 13, 2007 10:31:12 AM]

Share this post


Link to post
Share on other sites
Emmm, guys???

Well, I don't ask for solution, and I understand that your time is costly but please, give me a shot, I figure out two approaches here, it's working, but I think, it's bad from mathematical side of question.

So the question was : How to determine normal to intersection plane, and I figure out something, and it's work, but as I said, it's bad approach as I think...

Check that out:

Performming test to find normal for AABB intersection

And I do this, just like that :

{
... // Another code to determine t parameter of ray

Vector N; // normal to an intersection plane
Vector vD = ray.GetEnd()-ray.GetSrc(); // ray distance
Vector hitPt = ray.GetSrc() + t * vD; // intersection point

// test in which contour intersection point lying
if ( hitPt.x <= Mins.x+0.5f && hitPt.y >= Mins.y && hitPt.y <= Maxs.y )
{
N = Vector(-1,0); // left side
}
if ( hitPt.x >= Maxs.x-0.5f && hitPt.y >= Mins.y && hitPt.y <= Maxs.y )
{
N = Vector(1,0); // right side
}
if ( hitPt.y <= Mins.y+0.5f && hitPt.x >= Mins.x && hitPt.x <= Maxs.x )
{
N = Vector(0,-1); // up side
}
if ( hitPt.y >= Maxs.y-0.5f && hitPt.x >= Mins.x && hitPt.x <= Maxs.x )
{
N = Vector(0, 1); // down side
}

ray.SetNormalToPlane( N );
}









As you can see, I use +/- 0.5f to overcross potencial float roundings erros at long rays

So, for OBB :

perfroming search where our normal lying

And I use for this my most strangest approach:



Vector N; // normal to intersection plane

float s1 = Dot(ray.GetSrc(),orient[0]); // raySrc • orient_matrix_col_1
float s2 = Dot(ray.GetSrc(),orient[1]); // raySrc • orient_matrix_col_2
float e1 = Dot(ray.GetEnd(),orient[0]); // rayEnd • orient_matrix_col_1
float e2 = Dot(ray.GetEnd(),orient[1]); // rayEnd • orient_matrix_col_2

Vector raySrc(s1,s2); // transformed in OBB space ray start
Vector rayEnd(e1,e2); // transformed in OBB space ray end
Vector hitPt = raySrc + (rayEnd-raySrc) * t; // hit Point on transfromed ray

Vector c;
c.x = origin.Dot(orient[0]); // transfrom box origin in OBB space
c.y = origin.Dot(orient[1]); // same

Vector Mins = c - Extents; // Mins and Maxs in world space transformed to OBB axial space
Vector Maxs = c + Extents; // same

// Box vertices at local space as in AABB
Vector v1 = -Extents;
Vector v2 = Vector(-Extents.x, Extents.y);
Vector v3 = Extents;
Vector v4 = Vector(Extents.x, -Extents.y);

// Perform same test as in AABB but we do something transformation for each normal!
if ( hitPt.x <= Mins.x+0.5f && hitPt.y >= Mins.y && hitPt.y <= Maxs.y )
{
N = (-(v4-v1)*orient).Normal(); // multiplying by orient matrix
}
if ( hitPt.x >= Maxs.x-0.5f && hitPt.y >= Mins.y && hitPt.y <= Maxs.y )
{
N = ((v3-v2)*orient).Normal(); // multiplying by orient matrix
}
if ( hitPt.y <= Mins.y+0.5f && hitPt.x >= Mins.x && hitPt.x <= Maxs.x )
{
N = (-(v2-v1)*orient).Normal(); // multiplying by orient matrix
}
if ( hitPt.y >= Maxs.y-0.5f && hitPt.x >= Mins.x && hitPt.x <= Maxs.x )
{
N = (-(v4-v3)*orient).Normal(); // multiplying by orient matrix
}

ray.SetNormalToPlane( N );
}









Well, both approaches seems to work nice, I mean from visual point of view, but because it's my own implementation, and I'm a bad mathematician this may cause extra calculations or checks, and maybe figured out by more protozoon checks.

So guys, I'm call up for all of you, please, say that my approach is poor, even if it work correct, and give me a shot how I can improve it????!!!!

Share this post


Link to post
Share on other sites
Personally I'd to a line intersection test...

You can check here for some details:

http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

The math I use is this:


u = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / (float)((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));

nX = x1 + u * (x2 - x1);
nY = y1 + u * (y2 - y1);


where...
(x1, y1) = one end of the ray.
(x2, y2) = the other end of the ray.
(x3, y3) = one end of the line to test for an intersection (eg. an edge of your box).
(x4, y4) = the other end of the line to test for an intersection.
(nX, nY) = the location fo the intersection.


And the normal will always be the same fo the edge, no matter where the intersection is (normal is always perpendicular to the edge).
You can move it to the point of intersection if you want (so it's like in your pictures :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement