Curves & You: Part 1

Intoductions

This is the first is a series of articles about some of the benefits , techniques, and challenges of using parametric curves in 3D games. The examples and code will be C# in Unity but the math is going to be universally applicable and most of the problems and solutions we'll look at in later entries easily extend to any 3D engine.

This series was catalyzed by the Global Game Jam 2012 entry Ossiphidia. Ossiphidia takes place on a looping track of snake skeleton that looks like this:

Making something like that by hand is challenging, tedious, and nearly impossible to do with any degree of precision. Building it procedurally using parametric curves had two major advantages:

  • positioning and alignment of each vertebra is accurate and consistent
  • the framework to make the structure is easily extendible to make other structures.

To illustrate the second point, here's another structure generated using the same code and the same simple model of a single rib unit, changing only the values of some numeric parameters:

Building that manually would take hours and hours of work.

So, Why Do I Care?

Curves have a variety of properties that make them important in game development. A curve can define the path an object follows as it moves through space. It can just as easily be used to generate the floor in a level (note: it is not actually "as easy"). Curves can provide a smooth transition for cameras or other objects and for games where a custom physics engine is out of scope, they can be used to track a variety of physics effects. This series is going to start with the basics and we'll build on them to identify and resolve several potential challenges that might come up; you'll also see some applications.

Enjoy!

Waypoints vs Parametric Curves

Waypoints and parametric curves are the two simplest ways to generate any sort of path in 3D space. Neither is necessarily better than the other- in fact, we'll be converting all of the curves we use into waypoints when we actually start using them. The key differences are highighted below. Let's look at a graph first and then we'll discuss each property in turn.

  • Point Density
    • Waypoints: limited by the number of waypoints
    • Curves: infinite/limited by your imagination
  • Flexibility
    • Waypoints: high degree of control over positioning
    • Curves: most simple curves allow only basic customization
  • Path Flow
    • Waypoints: connect-the-dots/straight lines
    • Curves: mooth, flowing turns
  • Orientation Along/About Path
    • Waypoints: must be keyed manually
    • Curves: can be inferred from curve structure

Both have their uses. Waypoints are generally a lot simpler, though, so there's less to be said about them (exception: see Bezier Curves, below). Since there's more to be said about curves, we'll say more about them! 

Point Density

This is far and above the most important difference between using waypoints and using curves to define a structure. In fact, it's the only real difference on this list; the other distinctions follow from this.

When you use waypoints, the number of distinct points you have is equal to the number of waypoints you make- you'll need to somehow interpolate between adjacent points to fill in gaps or describe behavior between waypoints. On the other hand, even when you reduce a curve to a series of waypoints (as we will in the next article), you still have the core curve definition to fall back on if you ever need more detail.

Flexibility

While the point density may be the core distinction between waypoint system and parametric curves, flexibility may be the most important distinction from a game development perspective. If you need to stretch out a waypoint-based path to compensate for a new model, you will only need to reposition a few waypoints.

On the other hand, if your base curve is a circle you can't just go in and tweak the definition of a circle to meet your changing needs. That being said, circles are so common that they tend to get a lot of use anyway, and other families of curves like the torus knot group (which was used in Ossiphidia) can be used to generate interesting organic shapes more precisely than a human would necessarily be able to place waypoints.

Path Flow

Before any smoothing takes place, a waypoint path is going to be exactly as smooth as its creator made it; this means that it tends to look a bit like a connect-the-dot or a constellation: a lot of straight lines between points, with abrupt or sharp angles between them. This is a direct result of our first distinction- infinite point density gives parametric curves as much smoothness as you're willing to compute.

Path Orientation

This is one of the areas where parametric curves shine, even if the significance is not readily apparent. While a waypoint chain does have some intrinsic sense of "forward" (facing towards the next waypoint in sequence) it has no intrinsic "up". You can borrow the up direction from your environment but as we'll see several articles from now that can create continuity errors in object orientation. The only realistic approach is to bake orientation in by hand at each waypoint and perform some sort of interpolation in between to smooth things out.

With parametric curves it's possible to infer a local "up" at any point on the curve. What's more, these up directions will transition smoothly along the curve, without jarring disruptions in orientation. Because this local up is an intrinsic property of all smooth parametric curves (you will see some orientation jumps if your curve ha any sharp corners) it can be computed entirely procedurally.

This is advantageous because as we explore options for determining orientations along curves we will discover that many of the simpler solutions break down in certain scenarios and you cannot always determine these ahead of time. With parametric curves you have the power to really create curving structures procedurally without knowing anything about the shape of the curves.

A Quick Note About Bezier Curves

There's a class of curves called Bezier curves which live in-between the simple parametric curves we'll be talking about and waypoint structures; they are curves that use waypoints (and some tacit assumptions about how the final shape will look) to define their structure. This gives them a lot of the flexibility of waypoints along with all of the benefits that come with having an infinite point density.

As a result, Bezier Curves are really, really useful for a wide range of applications. However, they are also more complicated to work with than simple curves since you'll typically need to build interface components to support manipulating the curve.

We aren't going to be discussing creating Bezier Curves (at least, not as part of this initial series) for two reasons: 1. Every project (and every engine) is going to have differnet needs from an editor perspective and we're trying to make this series as universally applicable as possible. 2. There's already a lot of information about Bezier Curves out there, and the intent of this series is to fill a gap in available information about troubleshooting parametric curves for game projects, not to supplement an already rich body of work on Bezier Curves.

If you want to make your own Bezier Curves (or already have) that's great- all the techniques we will be discussing here and in future articles will work for them, too! If you plan to ultimately use Bezier Curves (or other parametric structures that support waypoint-based creation) then you might want to get a handle on these techniques using their simpler cousins first; you can always build up to Beziers later.

Parametric Curve Properties

There are a few properties of curves we'll need to lay out before we dive in.

Parametric Curves are Parametric

So that's pretty obvious, but what does it actually mean? An object's positions along our curves is determined by the value of a parameter, which we'll usually call t. If you think of a curve as the path an object sweeps out as it moves, then you can think of t as time- as time goes by, the position of the object algonquin the curve will change. When t goes up, the object moves "forwards" on the curve. When t goes down, the object moves "backwards" along the curve.

Typically we have a relatively simple equation using t for each of the x, y, and z coordinates of a curve (for 2D work you can omit z). For example, this parametric curve defines a circle in the X-Y plane centered on the origin with radius 1:

The Circle

x = sin(t)

y = cos(t)

z = 0

This definition of a circle is an incredibly powerful relationship that stems from that high school trig class you hated. It's probably the most common way to generate any sort of circular movement or positioning in the game world (another common approach is to use object parenting to put one object in "orbit" around another). We'll be using this relationship extensively.

You also need a start and end value for t - this determines the start and end point for the curve (note that these can be the same point in space). Depending on whether or not your engine uses degrees or radians as its default angular measurement, t will usually start at 0 and ends at 2π (for radians) or 360° (for degrees). This is especially true if you have a looping curve. If your curve loops forever (like a circle) then you won't necessarily need to worry about the start and end points, though as you'll see in the next article, an awareness of them will help when you are using the curve to arrange things.

Curves are usually Continuous

The curves we'll be dealing with will be continuous. Think about the arc a ball takes as you toss it in the air (or as it bounces against the ground when it lands), or the path of a bird in flight- the ball and the bird translate through space without any sudden jumps in location (baring unforeseen Einstein-Rosen bridges, which are beyond the scope of this article). Similarly, for most applications you will want your curves to be continuous.

This doesn't mean the curve has to be differentiable (i.e., smooth and without sudden changes in direction). If you want to design a path for a bouncing ball (which will give you more fine-tuned control over it's behavior than relying on a physics engine), it is natural to expect the ball to suddenly change directions whenever it bounces. But we don't want the ball to fall, hit the ground, spontaneously appear two feet in the air, fall three inches, instantaneously move seven miles to the right, and continue falling- the curve ought to be continuous without any sudden teleportation events.

Curves can be Open or Closed

A given curve will either loop back on itself or it won't. Curves that form a single, attached loop are closed. Curves with a start and an end are open. Sometimes closed curves are called loops and open curves are called paths but this terminology isn't universal and can cause misunderstandings and hurt feelings, so be cognizant of the different terms.

Closed curves work best for situations which repeat- modeling a race track where the player needs to drive multiple laps, for example. A camera might have a closed path it follows around another object, built to ensure that as the camera panned past a particular area the most important part of the scene had center focus.

Open curves work best when closed curves aren't necessary. They are a little easier to work with, as we'll see later, since they aren't constrained by having to link back up with themselves.

Curves Can Represent But Are Not Points in Space

You've heard the bit about how there aren't any perfecit circles? Not truly perfect, because of the granularity of the medium underlying reality? Circles are mathematical concepts- perfect shapes of uniform curve and absolute ratio. Anything you might stumble across in real life is going to have flaws. Minor flaws, maybe, but they'll be there (especially if you have a microscope). The curved we'll be dealing with are similar. They are not physical objects, not even our 3D environments. They are guides; tools; abstract ideas that happen to make programming easier. In the same way that you can't draw a circle, just an approximation of one, we don't work with pure curves, just their approximations.

You should also be aware of your cognitive bias towards interpreting curves as objects in 3D space. Just because something has three coordinates doesn't mean they correspond to good old x, y and z.

The colors in this gradient are a 3D curve expressed in color space:

<

Notice that the colors transition smoothly and that the colors on each end match up. That's because the source curve is continuous and forms a closed loop. In this next image we use the same curve to determine both the color and position of each point, which makes it easier to visualize the relationship:

 

The upper right side of the image is the part of the curve nearest to the corner of its binding cube where X, Y and Z are maximized; the nearly black region in the opposite corner is near where they are minimized. The red areas are regions high X values but low Y and Z values, and so on. If you pick a point and trace along the curve, you can see that the colors you pass through match up with the colors in the initial gradient.

The takeaway here is that when we say point (or even waypoint) we don't necessarily mean point in space. We will a lot of the time, sure. But always be asking yourself what else the point could represent. This is important to remember since we'll be working with these points quite a bit- if you creatively apply these techniques you'll come up with some really interesting results.

Curves with Infinite Density can be Baked into Finite Structures

Since calculating individual points along a curve during runtime can be a substantial performance hit (depending on the the math defining the curve and how often we need to do it), we will often "bake" a curve into a literal list of waypoints. This provides a substantial performance boost since we can look up positions in a list or array rather than compute them individually each time we need them. When we need information about points that exist in between the waypoints in our arrays we can interpolate between the bounding points.

Wait a minute! Didn't we say that curves and waypoints had different uses? Well that's true: in general, waypoints do serve a different purpose. The distinction here is that there might be eight or ten waypoints for a guard patrolling the perimeter of a house in a game, while when we reduce a curve to waypoints for performance reasons we may use upwards of 1000 waypoints- enough so that even though objects will be moving linearly along the path between any given pair of neighboring points, they appear to be moving in a smooth (dare we say- sensual?) arc. The higher density of the curve's information allows us to build a waypoint system with a higher information density than one we would care to make by hand.

We can bake more than position into our curve, too. Not only can we infer direction and orientation from a curve and bake that in, we've seen that each node can be used to store any number of directions, colors, and other values. These non-literal properties can be used to control cameras, lighting, speed, the behavior of game elements and so on.

Closing

So that was fun, right? Next time we'll break out the C# and start actually doing things. As we said, we'll be using Unity 3D for this. You can pick up a free Indie copy here if you want to follow along on your own. If you don't have Unity or prefer to use another engine, you'll need to do a bit of concept translation to get things to work, but I have mad faith in you, so no worries.

PrintView Printer Friendly Version

EmailEmail Article to Friend

« For those of you about to jam: we salute you! | Main | Postmortem: Ossiphidia »