For a racing game, I want the course to consist of a network of pipes. Each pipe follows a bezier curve and may need as many as 10 or 20 control points. The bezier curves should be easy to work with in the track editor, but, for in-game collision detection, I think I need to use a different representation. I say this because a 20th-order bezier curve takes a while to evaluate, plus I honestly don''t even know the equation for a "bezier pipe" (maybe "bezier cylinder" would be better). The collision I want to detect is that of a ray with the pipe, btw. My first thought was to chop up each pipe into a bunch of straight sections, i.e. cylinders (collision detection would then just be ray-cylinder tests). However, to keep the pipe "smooth" enough, I''d need use a lot of really short cylinders, which would mean a lot of ray-cylinder tests for each ray (too slow). I have this other idea of chopping up the pipe into "circularly curved" sections, i.e. pipes that follows the circumference of a circle (picture macaroni noodles). I imagine the bezier curve could be approximated more accurately in this way, but I don''t know how complicated the ray collisions would be with this kind of object... Anyway, I''d appreciate any other ideas on this

Hmmm - I reckon you ought to limit the number of control points on the bezier curves. More complicated curves can be made out of several simpler ones. Keeping two consecutive curves smooth can be done by making sure that the connecting point is the midpoint of the last "free" point of the first curve, and the first "free" point of the second.

The editor could be something to this effect. All the curves are cubic. When you move a red point, its partner moves, too. The curves will merge smoothly.

To answer your question, I recommend dividing the curves up into straight lines. If you need more accuracy, you can increase the number of segments - and you don''t really need that many straight line segments to create the illusion of a true curve. 16 seems to work for most cubics.

I''ll second Beer Hunter''s suggestion to use a piecewise Bezier curve, with each piece being quadratic or cubic. This is the standard way of doing things. Higher order polynomials (which a high order Bezier curve *is*) can be problematic and evaluation can even be unstable for floating point reasons.

I also agree that you should go ahead and break the curve into straight segments, at least for collision detection. Although you could do something like you suggest, discretizing the pipes into something like torus segments (your macaroni noodles), the cost of colliding those might exceed the cost of intersecting more straight segments. Plus, coding might be more challenging.

P.S. BH, did you ever find that beer you are hunting? .

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Yeah, I found the beer - I''m just waiting until I''m 18 so I can drink it

Lol, BeerHunter. And thanks for the tip about breaking up the bezier curve. That will definitely simplify the track creation.

As far as discretizing (good word!) the curve into cylinders, I think this could probably be made fast enough, even given the high LOD I'm going to need. However, I'm still interested in the macaroni-noodle approximation (further research identified them as torus segments, as Graham mentioned )...

The beauty of this approximation is that, no matter how crudely I approximate the original bezier, the pipe is still perfectly smooth, which is much more important to me than the approximation's accuracy. In fact a very crude torus approximation could serve as the definition of the pipe in-game (I would still use beziers in the track editor, though, because of their "user-friendliness" as far as laying out a pipe).

There is a problem, though: I want a variable pipe radius. This would translate to a linear change in radius over the length of a segment, and I don't think the torus equation can be modified to accomodate this. So, I have this bizarre idea of a way to approximate a torus using spheres:

This is the concept in 2D. As you can see, I've used 6 circles to roughly define two hexagons (the white parts). Now, if you were to just spin this about the vertical axis, the circles would become spheres, and the white hexagons would become a torus with a hexagonal cross section. Voila! The choice of 6 is arbitrary, btw, and obviously I would use more than 6 to get a rounder cross section. Further tweaking of the spheres' arrangement in 3D can produce a variable-radius cross section.

quote:

---

Original post by grhodes_at_work
Plus, coding might be more challenging.

---

Well, that about sums up the disadvantage of this method over cylinders. However, as a programmer, I've noticed I often latch on to the most obscure solution to a problem I can think of, so perhaps I am beyond such common sense at this point.

Any more thoughts on this are much appreciated.

Edited by - Eric on September 14, 2001 12:56:21 AM

There is more than one parametric equation for generating a torus. They simply vary by how you slice it. So you slice it the way that makes it easiest to make the modifications you want. One set of parametrics is x=(r1*cos(s)+r2)*cos(t), y=r1*sin(t), z=(r1*cos(s)+r2)*sin(t) where r1 is the "pipe radius". The equations just draws a circle with radius r1 in the xy plane with a center at (r2,0) then rotates it around the y axis. The rotation just uses x because z is zero and y is unchanged by rotation about the y axis.

This problem arose several months ago when another GameDev poster was asking about his racing in a tunnel game!

One of the simplest collision detection algorithms involves transforming the problem into cylindrical polar coordinates centered on the central axis of the tunnel. Then, a collision will occur whenever the radius of the car/plane/jet/ is greater than or equal to the radius of the tunnel at that z location (if z is taken as the longitudinal axis of the cylinder).

Additionaly, the computation of new velocity vectors is trivial since the angular velocity (about the centre of the tunnel) will not change (ie its conservative under elastic colisions of point objects inside a circle) and the radial velocity will change sign.

If your object that is floating around inside the tunnel is not a point mass (or cannot be approximated as one for collision purposes) then you can perform the same computation for each vertex on its edge. When any vertex has a radius >= radius of tunnel, reverse its radial velocity. Compute the radial component of force with which the object hit the wall and then compute the moment generated about the centre of mass of the object (as the wall exerts and equal and opposite force on the object through the colliding vertex. This will enable the computation of the rotation of the object.

Hope this helps,

Timkin

LilBudyWizer, yeah, I saw this alternate equation for the torus earlier. It would be easy to make the smaller radius a function of the "larger" angle, but when it comes to solving the ray-torus intersection using this equation, I''m baffled.

Anyway I think I''ll go with the cylinder approximation, as most of you suggest. Since the paths of my racers are fairly predictable, I should be able to take advantage of frame coherence to minimize the number of ray-cylinder collision tests I have to perform.

Timkin, hehe, I checked out the other thread you mentioned... your idea of using cylindrical polars is pretty interesting. However, I think that my ray-cylinder test would be more complicated in polar coords than in cartesian coords (a ray in polar coords is kinda nasty, as I recall). Btw are you like a "free-lance" moderator here at GameDev? I didn''t see your name next to any of the forums.

I forgot it was a question about collision detection. Never mind

quote:

---

Original post by Eric
Timkin, hehe, I checked out the other thread you mentioned... your idea of using cylindrical polars is pretty interesting. However, I think that my ray-cylinder test would be more complicated in polar coords than in cartesian coords (a ray in polar coords is kinda nasty, as I recall).

---

Mmm. Why do you need the ray cylinder test though to be computed in polars? You only need to use polars for the collision detection algorithm. It''s fairly trivial to convert between polar and cartesian and much faster if you use a simple look-up table for values of sine and cosine, rather than computing them using the library functions.

quote:

---

Original post by Eric
Btw are you like a "free-lance" moderator here at GameDev? I didn''t see your name next to any of the forums.

---

You could say that. I am a roving moderator, which means that I don''t have a specific forum to call my flock, but rather I lend my eyes and ears to several forums. In particular, I frequent the AI forum and (not as much) the Maths/Physics forum.

Cheers,

Timkin