   Collision detection - trajectories and moving objects
  There are a few elements to my collision detection trhan make it a bit more complicated than the standard line and polygon tests.1.  My projectile isn''t following a line, but rather a trajectory (affected by gravity, perhaps wind, etc...).  I suppose if my time step is small enough, I can treat it as a line segment for testing purposes (from start of time step to end of timestep).  This will make the test imperfect, but it may be good enough.  anyone tried this or have an easy test for trajectories as opposed to the usual line tests?2.  Aside from checking versus static objects, I need to check against moving objects.  This would be relatively straight forward except some of the objects I need to test against are vehicles and the physics for them is computed every 5 milliseconds (200 Hz) versus my projectiles which are checked every 50 milliseconds (20 Hz).  This means that the movement of the vehicles in between projectile movements can be drastic (in terms of direction changes, etc...).There are a few possible solutions to this (none of which I like):1.  Check for collision with projectiles during the vehicle physics updates instead of during the projectile physics updates.  This is unappealing due to the extra load on the CPU. This may still be the best option (combined with treating the projectile trajectories as line segments), but I hope there''s a better way.2.  trying to compute complex polygons to represent the vehicle movement since the last collision check.  this seems like it would get very messy very quickly and I probably don''t want to go there.Any thoughts on the issues or easy ways to address them?  I''m sure this has been done before, but the issue of physics being updated at different rates but trying to avoid testing at the highest common denominator isn''t simple.Thanks for any help/code/advice/ideas.Onnel  
  Are you using a mesh to determine which objects are within the proximity of other objects (to reduce the number of object-object and object-projectile collision tests)? If not, you should definitely do this.One possibility of dealing with the difference in time steps is to coursely predict the trajectory of each object through the mesh, over the time step to the next projectile update. Comparing this with the projectiles predicted trajectory would enable you to work out a rough probability of a collision. If this probability is above a chosen threshold, then find an object-update frame before the predicted collision and start checking for collisions each frame until either there is a collision, or there isn''t going to be one.Make sense?Cheers,Timkin  ;quote:1. My projectile isn''t following a line, but rather a trajectory (affected by gravity, perhaps wind, etc...). I suppose if my time step is small enough, I can treat it as a line segment for testing purposes (from start of time step to end of timestep). This will make the test imperfect, but it may be good enough. anyone tried this or have an easy test for trajectories as opposed to the usual line tests?  The fact of the matter is that the accurate movement of the projectile along the true trajectory is only as good as the framerate.  So if you are using a 50 millisecond interval, then your projectile is going to skip all points inbetween, when the time is in between those intervals.  My point is that a line is really the best way to handle this, as it''s impossible anyway for the projectile to follow the true trajectory, lest your time between frames is 0... Timkin gave a good explanation of how to handle your second question, so I won''t go into depth ;  >>1. My projectile isn''t following a line, but rather a trajectory (affected by gravity, perhaps wind, etc...). I suppose if my time step is small enough, I can treat it as a line segment for testing purposes (from start of time step to end of timestep). This will make the test imperfect, but it may be good enough. anyone tried this or have an easy test for trajectories as opposed to the usual line tests?<<Not sure how to go about this exactly, but if you want a more accurate test it seems like you could compute a spline of some form(Bezier perhaps?) and then use that in your intersection tests to see if it intersects over the time interval.I''m fairly certain this would be more time-intensive, though I''m not sure how much more.  Ultimately, whether it''s worth it or not would probably depend on how much your trajectory diverges from a straight line between each check.  If it''s a lot, then you''re probably gonna want to do something like this.  If the divergance is small, then it may not be worth the effort.Like I say...I have no actual idea how to compute this.  Just thought I''d try to throw out an idea for ya -John  ;quote:Original post by Timkin  Are you using a mesh to determine which objects are within the proximity of other objects (to reduce the number of object-object and object-projectile collision tests)? If not, you should definitely do this.  I''m using an octtree to get the rough estimates done.  The help I need is more for the more detailed stuff (as well as the issue of the different time steps).  Doing a rough plot for the vehicles may work and it''s certainly worth some thought...I''ll look in to it!Onnel;quote:Original post by Zipster  The fact of the matter is that the accurate movement of the projectile along the true trajectory is only as good as the framerate.  So if you are using a 50 millisecond interval, then your projectile is going to skip all points inbetween, when the time is in between those intervals.  My point is that a line is really the best way to handle this, as it''s impossible anyway for the projectile to follow the true trajectory, lest your time between frames is 0...   Sorry, but I think you''ve missed the whole point.  all of my physics calculations (both projectile and vehicular) are completely non-framerate dependent and I''d like to make sure my collisions are as well.  I''m not updating only on frame refreshes.  Making physics framerate dependant has all kinds of issues (all of the bad).  Basically, there may be tens (or even hundreds) of physics refreshes in between frame renders.Having said that, I think a line may still be "good enough" (I''ll have to test for sure), but framerate is a non-issue, as far as I can see.Onnel  ;quote:Original post by Teknofreek  I''m fairly certain this would be more time-intensive, though I''m not sure how much more.  Ultimately, whether it''s worth it or not would probably depend on how much your trajectory diverges from a straight line between each check.  If it''s a lot, then you''re probably gonna want to do something like this.  If the divergance is small, then it may not be worth the effort.  Right.  I think it will be a trade off in CPU time between how expensive it is to get a collision test that models the behaviour well enough (whether that be simple line or  a spline or the like) and simply running the collision physics test at a high enough rate.  I could do all my projectile and collision physics at the same hertz as my vehicles, but that would eat up a lot more CPU cycles.I think at this point I''ll just have to code something up and see how well it works in actuality.Thanks for the feedback!Onnel  ;quote:Sorry, but I think you've missed the whole point. all of my physics calculations (both projectile and vehicular) are completely non-framerate dependent and I'd like to make sure my collisions are as well. I'm not updating only on frame refreshes. Making physics framerate dependant has all kinds of issues (all of the bad). Basically, there may be tens (or even hundreds) of physics refreshes in between frame renders. It doesn't matter how often you update the physics, if the position of the projectile is a function of time then it won't matter.  You could be running at 100,000 FPS and updating the position each frame, but since the time between frames is only 0.00001 seconds, your position would update at an appropiate rate.  On the same token, you could be running at one frame every ten seconds (0.1 FPS, God forbid ); the position would still be a function of time.  However, my point is that if you try to do a line test between the last position and the current position, they are ten seconds apart, and your collision line would be horrendeously inaccurate.So what I said still stands.  The less of a time between each update, the more intermediary positions the projectile will reach.  The more intermediary positions, the smaller your collision line segments and thus the more accurate your detection.In the end, it's all still a function of time.  But the more updates, the better collision detection.  So framerate is quite a large issue.  However, once every 50 milliseconds is pretty good.In terms of the position of the object, it is framerate independant.  At any time you pick, you will get the correct position as a function of that time.  But in terms of the delta between two positions, time differences plays an important role in determining accuracy of the line between them and the true trajectory.[edited by - Zipster on September 16, 2002 4:03:51 AM];  as I understand you already have a test for lines against polygons.(You said your physics is frame independent. Is it only graphis independent?? you say you update it every 1/200 sec, so it has frames??)Anyway, if you have a way to check like Zipster suggested, it will even work with only 10 updates per second, as long you do not want to have exact collisions between two very fast moving objects (like two bullets).I coded our physics engine that way, and it handles even 1000 balls, while the framerate goes down to like 1 frame per sec. But that doesn''t matter, as the code will adopt to larger delta times and simply catch up the time passed in the next update of the physic.;quote:Original post by Zipster  In the end, it''s all still a function of time.  But the more updates, the better collision detection.  So framerate is quite a large issue.  However, once every 50 milliseconds is pretty good.  Maybe this is all a misunderstanding of the word framerate.  for me, framerate means how often the system is rendered (i.e. frames per second (FPS)).  My physics having NOTHING to do with that and the frame rate will be as high as it can manage while still calculating the physics.  My physics rate is directly controlled by me and is independent of the framerate.quote:At any time you pick, you will get the correct position as a function of that time.  But in terms of the delta between two positions, time differences plays an important role in determining accuracy of the line between them and the true trajectory.  Exactly...the size of the time slices is very important, but this size is has nothing to do with how often I render (framerate).  Again, I think there may be a misunderstanding in our definintions of framerate.  I can make my physics time slices very small as needed to make the trajectory sufficiently like a straight line, but this may cause so much CPU overhead (due to the more frequent calculations) that it isn''t worth it.I think I will simply have to try it out with different frequencies and see what kind of results I get.Thanks!Onnel