Archived

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

70% of Tutorials SUCK - collision detection

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

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
I''m now certain (almost certain anyway) that the problem is with MAX exporting the data to the .ase files. It is butchering some of the normals/geometry I think. I''ll take a look at the algorithms mentioned in that last post. I have it ''working'' now, click on my sig if you''re interested. I''m about sick of MAX''s bs right about now. Is it gonna switch the indices on the normals this time or not? No one knows for sure...

-BacksideSnap-

Share this post


Link to post
Share on other sites
That''s a really good article byteme. I wish I had seen it a few days ago... I need to go through and manually calulate out the normals saying as MAX butchered them in the export. For $4000 that program sure is a POS. More crashhappy then me driving with a single malt in my lap.

-BacksideSnap-

Share this post


Link to post
Share on other sites
Backside, I dont know what it is but for some reason I keep running into pages discussing exactly the problems you face. First triangle/ray intersection and now the y/z flipping of vertices by 3dsMAX

Apparently it isn''t a "problem", it''s known to do it.

Check out this article, found it right here on good ol'' Gamedev.

YIPPEE!

- Rob



ByteMe95::~ByteMe95()

Share this post


Link to post
Share on other sites
Haha... Maybe I should quit my whining and look around the web a bit. I haven''t checked out that article yet, but my problem with MAX is that it''s inconsistent. Sometimes it switches shit, sometimes it doesn''t... Not that I can cry too much about it, I got it from a friend. Had I actually paid for it myself I would have a reason to moan. I''m eventually going to write my own level builder anyway. I''ll check it out... Hopefully I can get it all working. I want to put a better level in my demo before I add in terrain as well. The fact that this isn''t working right is really holding me back a lot. That''s why I''m being such a bitch about it. Thanks once again.

-BacksideSnap-

Share this post


Link to post
Share on other sites
Hey, I know that frustrating feeling. I dont think you''re a true game programmer unless you know that feeling of frustration and just wanting to give up. But you never do cause you know there is ALWAYS an answer out there waiting for you to find it, and when you do and you get your shit workin, it''s worth all that annoying bullshit you had to put up with.

I took a look at your site backside, it looks pretty nice, how long have you been doing 3d?



ByteMe95::~ByteMe95()

Share this post


Link to post
Share on other sites
I''ve been doing 3D and graphics for a little over a year... I''ve been programming in oGL for about 9-10 months. I switched gears about a year and a half ago and went into programming (where I belong) after getting my BS in Mechanical Engineering. Thank god I did, I''m making a hell of a lot more money, and having a hell of a lot more fun doing so. I guess I really started programming in 6th grade in BASIC on my Apple IIe... Then Pascal... then Fortran... Finally c++ (and web programming too, but that doesn''t count Anyway, I''m sure that''s much more information than you wanted to know.
As far as the frustration goes - I''ve been about ready to send my computer out the window a couple times... It feels unusually nice running that knight in my demo into the walls though. I''m sure my girlfriend is wondering wtf is wrong with me and why she let a freak move in with her.
Back to the topic, I think I have a solution for the problem. The orientation on the faces is still correct when I switch the y and z indices, so I''ll just generate face normals off of that instead of reading them in from file. Who gives a damn about the vertex normals, if part of the ambient lighting screws up who cares. Not me, and certainly not at this point.

-BacksideSnap-

Share this post


Link to post
Share on other sites
Well, if anyone cares it was MAX''s fault, mainly, along with a couple of stupid errors on my part (an if else in place of an if, actually). For some reason when I rotated the geometry in it, it didn''t rotate the normals. I had to calculate them myself, but that wasn''t a big deal. It''s working about 99% right now, with a couple of little fixes that need to be taken care of. Fuck you 3DS MAX. If anyone out there is using .ase files, be careful. It may not export the data correctly.

-BacksideSnap-

Share this post


Link to post
Share on other sites
They can shorten my name to backside if they want to get backhanded Actually, backside is fine. All it is referring to is taking a wave left if you''re normal footed (and right if you''re goofy-footed). Just a surfing (real surfing, not the internet) term. Of course, only people with a coast would know that.
How difficult is MAXscript? I may have to try it out. Either that or build my own mesh editor, which I''m going to eventually get around to doing anyway. I''ll look at what''s on your site. It''s similar to what I want to build.

-BacksideSnap-

Share this post


Link to post
Share on other sites