Actually Bob, any spline runs the risk of overlaying an obstacle. Consider the situation in which an agent seeks a path across a river. It finds that its sequence of waypoints takes it to the river, then along its bank, then across the bridge and back along the other side of the river to the goal point. A spline carelessly generated near the river bank could easily have the agent walking on water... or perhaps missing the entrance to the bridge...

However, I do agree that there are better splines than Bezier... it''s just an easy one to find lots of info and articles on!

Cheers,

Timkin

Hmmm, I suppose in that case there COULD be problems, if there's only one waypoint defined on the center of the bridge, but I take your point. I was more thinking along the lines of the fact that a Bezier spline never actually touches the anchor points, which could represent a much more major issue. There are a few ways around the problem you describe, but probably the most flexible would be to run a "collision check" on the first few subdivisions of the curve to make sure there are no walking on water scenarios, and if there are redefining the waypoints as necessary. Given that Bezier splines are much easier to find info on, I present you with a Hermite spline function (sorry for the crappy formatting, but my ability to use the bulletin board system is very limited).

Vector Hermite(float s, Vector p1, Vector p2, Vector t1, Vector t2)
{
Vector vec;
float s2 = s*s;
float s3 = s*s*s;

vec.x = ((2*s3 - 3*s2 + 1)*p1.x) + ((-2*s3 + 3*s2)*p2.x) + ((s3 - 2*s2 + s)*t1.x) + ((s3 - s2)*t2.x);
vec.y = ((2*s3 - 3*s2 + 1)*p1.y) + ((-2*s3 + 3*s2)*p2.y) + ((s3 - 2*s2 + s)*t1.y) + ((s3 - s2)*t2.y);
vec.z = ((2*s3 - 3*s2 + 1)*p1.z) + ((-2*s3 + 3*s2)*p2.z) + ((s3 - 2*s2 + s)*t1.z) + ((s3 - s2)*t2.z);

return vec;
}

p1 and p2 are the anchor points for the curve, and t1 and t2 are the tangents at either point. Note that this assumes a 3-D "Vector" class, and so it may require a bit of editing before it will work for you. Let me know if you have any more questions.


[edited by - Mordoch Bob on April 16, 2002 1:33:02 AM]

Hehe... thanks Bob... actually I have a tonne of mathematical textbooks sitting on my shelves... personally, I know where to look regarding splines! (But I do appreciate you posting the info).

I made the comment with reference to other people who don''t have their own personal library in their office!

Cheers,

Timkin

I meant "you" in the "the great unwashed masses reading this" sense. I would very much expect a doctoral candidate to have many, many more books than I do, as well as a great deal more knowledge. The code snippet was posted for Terran''s benefit, as well as anyone else who cares. I just remember that I had an inordinate amount of difficulty finding anything really useful for Hermite splines when I tried to first implement them (due to a general lack of understanding how splines work rather than any actual complexities within the implementation), so I figured I''d simplify the problem. Anyway, even if my explanation was vaguely condescending, feel secure in the fact that you know all this stuff several orders of magnitude better than I do. For now, anyway.

quote: Original post by Mordoch Bob
Anyway, even if my explanation was vaguely condescending,

Not at all. My apologies if my reply sounded like a retort!

quote: Original post by Mordoch Bob
feel secure in the fact that you know all this stuff several orders of magnitude better than I do. For now, anyway.

Don''t be too quick to judge people as being more knowledgable than you, just because they''re title or position might suggest so. Sure, there are a lot of things I have some knowledge of and a few things I have a lot of knowledge on (compared to the average person) but I can tell you now... there are WAY more things that I don''t know than I do... and I''m happy to admit the limits of my knowledge. I haven''t used a spline in more than 5 years... and I''m sure I would struggle to pull a formula from my head... I might be able to derive one from first principles... but that''s a different matter.

As for the code and the information... that is always appreciated. Definitely post information if you feel it contributes to the discussion. That''s the whole point!

Cheers,

Timkin

What can I say? I covet your ability to derive spline theory. One day, your knowledge shall be mine.

roflmao!

I have visions of a big chair and lots of probes and hooks!

Eek!

Timkin

Either that, or doing my own doctoral studies...haven''t decided on that one yet.