Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

-BacksideSnap-

70% of Tutorials SUCK - collision detection

This topic is 6692 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

WTF is wrong with the people out there who post wrong info in their tutorials? Don''t they check the damn code and validity of what they''re saying? I guess not. I seen fucked up code everywhere from nowhere.com to Flipcode. Just a note to newbies out there (and not so newbies): don''t believe everything you read. If something you saw on a site doesn''t work properly, there''s a damn good chance it isn''t your fault. Anyway, what brought me to this is trying to get a working algorithm for detecting if a vector collides with a triangle. I have it working where I can detect if the vector crosses the triangles plane, no thanks to what I read on the net. If anyone has a WORKING point in triangle algorithm I would appreciate a code snippet, or a little help. I tried summing all of the angles formed by the point and the vertices of the triangle... this doensn''t work so well. Actually it doesn''t work well at all and I''m starting to have doubts about the data I read in from a MAX .ase file. It all shows up fine on the screen, all in place, so logically it must be correct... right? I tried dropping out the indice of the triangle''s vertices and point in(or out of) the triangle with the greatest normal component, therefore projecting it on one of the coordinate planes, converting to barycentric coords, and testing. This works half way, but there are still a lot of ''holes'' that don''t return collision when they should. If I have to I''ll upload the code, but I really don''t think anyone wants to go through all of it- there''s quite a bit. If anyone has been down this road and can offer suggestions or an algorithm I''d really appreciate it. Thanks in advance, and sorry if I''m a bit bitter. -BacksideSnap-

Share this post


Link to post
Share on other sites
Advertisement
Don''t worry about being bitter, if I remember correctly I think I was actually crying when I wrote a similar function..but it''s not as painful as it could be..you''ve already done the major part, you''ve determined that the line does indeed intersect the plane of the polygon..here''s the rest:

*first you need to calc normal vectors for each edge of the polygon, facing into the polygon..this vector will be parallel with the plane, and can be derived from the cross product between the plane normal and the vector from the side of the polygon..

*find the intersection of your line segment with the plane of the polygon, this will give you a point that you know lies somewhere on the plane..

*for each side of the polygon, do a front/back test against your intersection point using that extra vector from before..if they are all inside you''ve got your answer..

that''s the basic process..of course it means an extra vector for each side of the polygon but I think it''s well worth it..you can calc those at startup..before you blast me for posting the concept and not the code, I can assure you that I do actually use this method and it works beatifully..if you need help with some of the calculations you can email me and I''ll get more in depth with you..BTW the extra calculations aren''t too bad either, when just one of the front/back tests fails you can abort..

"Like all good things, it starts with a monkey.."

Share this post


Link to post
Share on other sites
I am completely new to 3D, but I was just wondering. Wouldn''t a line always intersect a plane unless the plane was "parallel" to the line? In every other instance, since a plane stretches out infintely, the line would haveto intersect it at some point.

Dont you think? :o)

------------------------------
fclose(fp)
------------------------------

Share this post


Link to post
Share on other sites
In curved space, I guess 2 parallel lines could intersect.

How''s anyone on relativity around here?

Share this post


Link to post
Share on other sites
Wouldn''t two parallell lines in curved space curve by an equal amount??

(I have no idea, just asking)

Share this post


Link to post
Share on other sites

There was a useful article in Dr. Dobb''s this month that covered 3d and 2d point-in-triangle testing. I don''t know if the article is on the web(ddj.com), but it was pretty good. Also may have to watch out for floating point errors(e.g. if a == 0 + or - really small value) on something like that.


To the guy asking about infinite planes. Yes, in Euclidean geometry, a line would insert the plane unless it was perpendicular to the normal of the plane(unless it was IN the plane). However, floating point errors for slopes and normals could mess with this at extreme angles(should always use tolerances with floating point instead of just straight up comparison a==b).

Share this post


Link to post
Share on other sites
Thanks for the reply monkeyman, I had a feeling a response would come from a CA brother. I considered using that method before, and I think I may try and implement it tonight. I''m sick of people posting worthless shit all over the web though, I''ve read a bunch of shit that''s totally wrong out there, even some of the tutorials here (quite a few of em actually, and no, I''m not going to name them).

I still think that MAX has messed my coords up somehow... The angle test should have worked. Wierd things have been happening in my ase files too. I actually have found quite a few bugs in MAX... yes, it''s been that kind of week. I can''t get a damn thing to work.

And to whoever, an infinite line will intersect with a plane if the two are not parallel. Thank you for straying from the topic. If anyone out there still has a working barycentric algorithm I wouldn''t mind seeing it. I want to compare the two methods.

Dogfood, I''ll try to check that article out. Thanks.

-BacksideSnap-

Share this post


Link to post
Share on other sites
May not be the most efficient, but you can do this:

Once you know the vector intersects the plane and you have your point, drop the index (x, y, or z) that is greatest in the normal. This reduces the triangle and point to 2 dimensions. Now, for each edge, see if your point is on the left of all edges. This assumes a counter-clockwise winding.

Another way would be after you have reduced it to 2 dimensions, is to run a ray to the right and see if you have only 1 intersection with the edges. Only intersect test with edges which have a top Y greater than the Y of your ray and a bottom Y equal to or less than the Y of your ray.

Share this post


Link to post
Share on other sites
dont get bitter get even. huh!
ok well mate i wrote donkey kong a couple of days ago and theres a bit in there about a line segment intersecting with a triangle
so dont delay head over to http://members.xoom.com/myBollux/home.html
and download it.
btw the programs not 100% finished i was gonna do it today but certain things keep me back (mainly not rising until 4pm cause of me spinning head)

Share this post


Link to post
Share on other sites
Have you ever had a look at these algorithms:

http://www.acm.org/jgt/papers/MollerTrumbore97/

It's from www.acm.org ... it's published ... it works (I've used Baduels algorithm before) ...

MK42

Edited by - MK42 on July 16, 2000 1:59:57 PM

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!