Sign in to follow this  
kyoukikoi

Help on self-written RayPlaneIntersection Algorithm

Recommended Posts

Hello everybody, i am writing an algorithm for ray-plane intersectiontest. Here the code: http://pastebin.com/f4da17631 Here a sketch of my idea!: Free Image Hosting at www.ImageShack.us<br /><br />QuickPost Quickpost this image to Myspace, Digg, Facebook, and others! The idea is to take a Plane defined by three vectors v0, v1, v2 and a ray defined by its origin and its direction i first calculate the planes edges: edge1 = oVert2 - oVert1; edge2 = oVert3 - oVert1; then the normal: normal = cross(edge1, edge2); now i can check wether the ray is parallel to the plane and additionally, if the distance of the rayorigin and the plane approaches zero: normaldotdir = dot(normal, direction); normaldotw = dot(normal, w); if(normaldotdir > -0.0000001 && normaldotdir < 0.0000001) { if(normaldotw > -0.0000001 && normaldotw < 0.0000001) return true; return false; } now we can get the parameter s of the ray if we say, that the point of intersection is: (origin - v0) + s*direction = w + s*u the dotproduct of the normal and the equation above has to approach zero to be inside the plane: dot(normal, (w+s*u)) = dot(normal, w) + dot(normal, s*u) = 0 - dot(normal, w) = s*dot(normal, u) s = ( - dot(normal, w) / dot(normal, u) ) point of intersection is: cut = origin + ( s*direction ) now we have to get the u and v coordinates of the directionvectors of the planes i create the vector from v0 to the point of intersection P(s) = cut and project it to edge1 projected_u = dot(edge1, v0Ps); dividing projected_u by the lenght of edge1 gives u: u = projected_u / norm(edge1); the same for v: v = dot(edge2, v0Ps) / norm(edge2); if(u < 0 || u > 1) return false; if(v < 0 || v > 1) return false; this test doesnt work somehow, mathematically i think everythings correct... any help would be appreciated thank you all in advance!

Share this post


Link to post
Share on other sites
Your approach is quite a bit more complicated than mine. This is the actual code I'm using:


float dpNV = planeNormal.dot(rayVec);
if(abs(dpNV) > epsilon){
out = rayOrig + planeNormal.dot(planePt - rayOrig)/dpNV * rayVec;
return true;
}
return false;


Where planePt is any point which lies in the plane. If you store the plane's D values, you can do the intersection with 2 less operations, but I don't bother with it.

Share this post


Link to post
Share on other sites
Oh right, your plane is bounded. The solution that comes to mind is to do the ray/plane intersection I posted above, and then convert the intersection point to barycentric coordinates. Then you'll check if it's in the plane with
(u > 0 && u < 1 && v > 0 && v < 1). It should be almost identical to the point-in-triangle test. Here's the code I'm using for that. It should (hopefully work for your problem too)


float dpNV = planeNormal.dot(rayVec);
if(abs(dpNV) > epsilon){
iPt = rayOrig + planeNormal.dot(planeV0 - rayOrig)/dpNV * rayVec;
Vec3 vec0,vec1,vec2;
float invDenom;
vec0 = planeV1 - planeV0;
vec1 = planeV2 - planeV0;
vec2 = iPt - planeV0;
float dot00 = vec0.dot(vec0);
float dot01 = vec0.dot(vec1);
float dot02 = vec0.dot(vec2);
float dot11 = vec1.dot(vec1);
float dot12 = vec1.dot(vec2);
invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
return(u > 0 && u < 1 && v > 0 && v < 1);
}
return false;

Share this post


Link to post
Share on other sites
Quote:
Original post by taz0010
Oh right, your plane is bounded. The solution that comes to mind is to do the ray/plane intersection I posted above, and then convert the intersection point to barycentric coordinates. Then you'll check if it's in the plane with
(u > 0 && u < 1 && v > 0 && v < 1). It should be almost identical to the point-in-triangle test. Here's the code I'm using for that. It should (hopefully work for your problem too)


float dpNV = planeNormal.dot(rayVec);
if(abs(dpNV) > epsilon){
iPt = rayOrig + planeNormal.dot(planeV0 - rayOrig)/dpNV * rayVec;
Vec3 vec0,vec1,vec2;
float invDenom;
vec0 = planeV1 - planeV0;
vec1 = planeV2 - planeV0;
vec2 = iPt - planeV0;
float dot00 = vec0.dot(vec0);
float dot01 = vec0.dot(vec1);
float dot02 = vec0.dot(vec2);
float dot11 = vec1.dot(vec1);
float dot12 = vec1.dot(vec2);
invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
return(u > 0 && u < 1 && v > 0 && v < 1);
}
return false;


the first operations are equal to my approach

but i want to return, u, v, the distance of the rayorigin to the intersection point t, the intersection point itseflf

Well i thought about my current algorithm and found out, that it would be better to normalize the normal, what i missed doing... and then i have a redundant calculation in that algorithm preventing some calculations...

i'm gonna try it considering your help ^^

thank you

Share this post


Link to post
Share on other sites
Well i changed my code with your help but it still doesnt work... sometimes it detects a collision, sometimes not, depending on the distance of the camera to the bounding box and its angle to the planes...

can you tell me how to define the bounding box planes correctly?

thank you

Share this post


Link to post
Share on other sites
Quote:
Original post by taz0010
If your ray-to-plane intersection test part of an oriented bounding box test? Can I get some background info so I know exactly what you want the algorithm to do?


Yes. I have an OBB(!) with BindPoseCenter(Transform reference) and CombinedCenter; Rotation; and the Bounds;

Free Image Hosting at www.ImageShack.us<br /><br />QuickPost Quickpost this image to Myspace, Digg, Facebook, and others!



8 Fields for the Corners:

BackBottomLeft( min ),
BackBottomRight ( max.x;min.y;min.z) ,
FrontBottomRight(max.x,min.y,max.z),
FrontBottomLeft(min.x,min.y,max.z),
BackUpLeft(min.x,max.y,min.z),
BackUpRight(max.x,max.y,min.z),
FrontUpRight( max ),
FrontUpLeft(min.x,max.y,max.z)

And the planes:

v2
|
|
|
|
v0-------v1

always like this:

plane( v0, v1, v2 )

directionplane = ( FBR, FBL, FUR )
backplane = ( BBL, BBR, BUL )
rightplane = ( BBR, FBR, BUR )
leftplane = ( FBL, BBL, FUL )
upplane = ( BUL, BUR, FUL )
downplane = ( FBL, FBR, BBL )

my function is following

public bool RayOBB_Geometric(Vector3 Rayorigin, Vector3 Raydirection, List<CollisionPlane> oPlanes) {

List<CollisionPlane> oIntersectedPlanes = new List<CollisionPlane>();

foreach(CollisionPlane oPlane in oPlanes)
if(RayPlane_Geometric(Rayorigin, Raydirection, oPlane.V0, oPlane.V1, oPlane.V2)) {
oIntersectedPlanes.Add(oPlane);
}

if(oIntersectedPlanes.Count > 0)
return true;

return false;
}

And so on.
I think there is something wrong when i update the boundingboxes...

I update them after my animation-skintransformset has been updated.

each bone has an OBB ... i pass the bone-skintransform to the OBBs update method and apply the matrix on the bounding boxes center and rotation.. that works without any problems

i thought about to transform the ray in the obbs space, so that i dont have to apply any rotation on the corners anymore.. but i somehow have to geet the correct data for the corners!!!

Hum... what i recognized: sometimes anything works! and sometimes i get 6 intersected planes on 5 boxes even if there are none oO

look at these screens in that album ( imageshack ): http://img704.imageshack.us/g/almcorrect.png/

on the leg, there are two intersections: correct
but the other one: 4 or 5 intersections, though i clicked on the screen where only one is visible

Share this post


Link to post
Share on other sites
Quote:
Original post by kyoukikoi
Quote:
Original post by taz0010
If your ray-to-plane intersection test part of an oriented bounding box test? Can I get some background info so I know exactly what you want the algorithm to do?


Yes. I have an OBB(!) with BindPoseCenter(Transform reference) and CombinedCenter; Rotation; and the Bounds;

Free Image Hosting at www.ImageShack.us<br /><br />QuickPost Quickpost this image to Myspace, Digg, Facebook, and others!



8 Fields for the Corners:

BackBottomLeft( min ),
BackBottomRight ( max.x;min.y;min.z) ,
FrontBottomRight(max.x,min.y,max.z),
FrontBottomLeft(min.x,min.y,max.z),
BackUpLeft(min.x,max.y,min.z),
BackUpRight(max.x,max.y,min.z),
FrontUpRight( max ),
FrontUpLeft(min.x,max.y,max.z)

And the planes:

v2
|
|
|
|
v0-------v1

always like this:

plane( v0, v1, v2 )

directionplane = ( FBR, FBL, FUR )
backplane = ( BBL, BBR, BUL )
rightplane = ( BBR, FBR, BUR )
leftplane = ( FBL, BBL, FUL )
upplane = ( BUL, BUR, FUL )
downplane = ( FBL, FBR, BBL )

my function is following

public bool RayOBB_Geometric(Vector3 Rayorigin, Vector3 Raydirection, List<CollisionPlane> oPlanes) {

List<CollisionPlane> oIntersectedPlanes = new List<CollisionPlane>();

foreach(CollisionPlane oPlane in oPlanes)
if(RayPlane_Geometric(Rayorigin, Raydirection, oPlane.V0, oPlane.V1, oPlane.V2)) {
oIntersectedPlanes.Add(oPlane);
}

if(oIntersectedPlanes.Count > 0)
return true;

return false;
}

And so on.
I think there is something wrong when i update the boundingboxes...

I update them after my animation-skintransformset has been updated.

each bone has an OBB ... i pass the bone-skintransform to the OBBs update method and apply the matrix on the bounding boxes center and rotation.. that works without any problems

i thought about to transform the ray in the obbs space, so that i dont have to apply any rotation on the corners anymore.. but i somehow have to geet the correct data for the corners!!!

Hum... what i recognized: sometimes anything works! and sometimes i get 6 intersected planes on 5 boxes even if there are none oO

look at these screens in that album ( imageshack ): http://img704.imageshack.us/g/almcorrect.png/

on the leg, there are two intersections: correct
but the other one: 4 or 5 intersections, though i clicked on the screen where only one is visible


Hum.. i have another idea...

My OBB has a center which will be transformed by the bone-skintransform applied...

why not take the ray origin and direction and transform these vectors with the inverse skin transform of the bone...

then i have the ray transformed to the bindpose box and i at least know that i have the correct data of the corners...

i checked the normals visually by the way... horizontal planes normals always point downwards..

vertical planes normals are pointing to the boxcenter... i think there is a source of failures.... i think i have to align the normals correctly in the first place...

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

Sign in to follow this