Chapter 7. Polar Coordinate Systems

Report
Chapter 7
Polar Coordinate Systems
Fletcher Dunn
Ian Parberry
Valve Software
University of North Texas
3D Math Primer for Graphics & Game Development
What You’ll See in This Chapter
This chapter describes the polar coordinate system.
It is divided into four sections.
• Section 7.1 describes 2D polar coordinates.
• Section 7.2 gives some examples where polar
coordinates are preferable to Cartesian
coordinates.
• Section 7.3 shows how polar space works in 3D
and introduces cylindrical and spherical
coordinates.
• Section 7.4 makes it clear that polar space can be
used to describe vectors as well as positions.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
2
Word Cloud
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
3
Section 7.1:
2D Polar Coordinates
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
4
Polar Coordinate Space
• Recall that 2D Cartesian coordinate space has an origin and two
axes that pass through the origin.
• A 2D polar coordinate space also has an origin (known as the pole),
which has the same basic purpose: it defines the center of the
coordinate space.
• A polar coordinate space only has one axis, sometimes called the
polar axis, which is usually depicted as a ray from the origin.
• It is customary in math literature for the polar axis to point to the
right in diagrams, and thus it corresponds to the +x axis in a
Cartesian system.
• It's often convenient to use different conventions than this, as we'll
discuss later in this lecture. Until then, we’ll use the traditional
conventions of the math literature.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
5
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
6
Polar Coordinates
• In Cartesian coordinates we described a 2D point using
the using two signed distances, x and y.
• Polar coordinates use a distance and an angle.
• By convention, the distance is usually called r (which is
short for radius) and the angle is usually called θ. The
polar coordinate pair (r, θ) species a point in 2D space
as follows:
1. Start at the origin, facing in the direction of the polar
axis, and rotate by angle θ. Positive values of θ are
usually interpreted to mean counterclockwise rotation,
with negative values indicating clockwise rotation.
2. Now move forward from the origin a distance of r units.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
7
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
8
Examples
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
9
Polar Diagrams
• The grid circles show lines of constant r.
• The straight grid lines that pass through the
origin show lines of constant θ, consisting of
points that are the same direction from the
origin.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
10
Angular Measurement
• It really doesn't matter whether you use degrees or radians (or
grads, mils, minutes, signs, sextants, or Furmans) to measure
angles, so long as you keep it straight.
• In the text of our book we almost always give specific angular
measurements in degrees and use the ° symbol after the number.
• We do this because we are human beings, and most humans who
are not math professors find it easier to deal with whole numbers
rather than fractions of π.
• Indeed, the choice of the number 360 was specifically designed to
make fractions avoidable in many common cases.
• However, computers prefer to work with angles expressed using
radians, and so the code snippets in our book use radians rather
than degrees.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
11
Some Ponderable Questions
1. Can the radial distance r ever be negative?
2. Can θ ever go outside of –180°≤ θ ≤ 180°?
3. The value of the angle directly west of the
origin (i.e. for points where x < 0 and y = 0 using
Cartesian coordinates) is ambiguous. Is θ equal
to +180° or –180° for these points?
4. The polar coordinates for the origin itself are
also ambiguous. Clearly r = 0, but what value of
θ should we use? Wouldn't any value work?
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
12
Aliasing
• The answer to all of these questions is “yes”.
• In fact, for any given point, there are infinitely many polar
coordinate pairs that can be used to describe that point.
• This phenomenon is known as aliasing.
• Two coordinate pairs are said to be aliases of each other if
they have different numeric values but refer to the same
point in space.
• Notice that aliasing doesn't happen in Cartesian space.
Each point in space is assigned exactly one (x, y) coordinate
pair.
• A given point in polar space corresponds to many
coordinate pairs, but a coordinate pair unambiguously
designates exactly one point.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
13
Creating Aliases
• One way to create an alias for a point (r, θ) is to add a
multiple of 360° to θ. Thus (r, θ) and (r, θ + k360°)
describe the same point, where k is an integer.
• We can also generate an alias by adding 180° to θ and
negating r; which means we face the other direction,
but we displace by the opposite amount.
• In general, for any point (r, θ) other than the origin, all
of the polar coordinates that are aliases for (r, θ) be
expressed as:
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
14
Canonical Polar Coordinates
A polar coordinate pair (r, θ) is in canonical form
if all of the following are true:
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
15
Algorithm to Make (r, θ) Canonical
1.
2.
3.
4.
If r = 0, then assign θ = 0.
If r < 0, then negate r, and add 180° to θ.
If θ ≤ 180°, then add 360° until θ > –180°
If θ > 180°, then subtract 360° until
θ ≤ 180°.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
16
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
17
A Nit-Picky Observation
• Picky readers may notice that while this code ensures that
θ is in range –π ≤ θ ≤ π radians, it does not explicitly avoid
the case where θ = –π.
• The value π cannot be represented exactly in floating point.
In fact, because π is irrational, it can never be represented
exactly with any finite number of digits in any base!
• The value of the constant PI in our code is not exactly equal
to π, it's the closest number to π that can be represented
by a float.
• While double precision arithmetic is closer, it’s not exact.
• So, you can think of this function as returning a value from
–π to π, exclusive.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
18
Converting from Polar to Cartesian
Coordinates in 2D
Converting polar coordinates (r, θ) to the
corresponding Cartesian coordinates (x, y)
follows from the definition of sin and cos.
x = r cos θ
y = r sin θ
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
19
Converting from Cartesian to Polar
Coordinates in 2D
• Computing polar coordinates (r, θ) from
Cartesian coordinates (x, y) is slightly tricky.
• Due to aliasing, there isn't only one right
answer; there are infinitely many (r, θ) pairs
that describe the point (x, y).
• Usually, we want canonical coordinates.
• We can easily compute r using Pythagoras's
theorem
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
20
Solve for θ
Computing r was pretty easy. Now solve for θ:
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
21
Pause for Thought
•
•
•
•
There are two problems with this approach.
The first is that if x = 0, then the division is undefined.
The second is that arctan has a range from –90° to +90°.
The basic problem is that the division y/x effectively discards some
useful information when x = y. Both x and y can either be positive
or negative, resulting in four different possibilities, corresponding to
the four different quadrants that may contain the point. But the
division y/x results in a single value.
• If we negate both x and y, we move to a different quadrant in the
plane, but the ratio x/y doesn't change.
• Because of these problems, the complete equation for conversion
from Cartesian to polar coordinates requires some if statements to
handle each quadrant, and is a bit of a mess for math people.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
22
atan2
• Luckily, programmers have the atan2 function,
which properly computes the angle for all x
and y except for the pesky case at the origin.
• Borrowing this notation, let's define an atan2
function we can use in these notes in our
math notation.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
23
atan2
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
24
Two Key Observations
Two key observations about this definition.
1. First, following the convention of the atan2 function as found in
the standard libraries of most computer languages, the arguments
are in reverse order: y, x. You can either just remember that it's
reversed, or you might find it handy to remember that atan2(y, x)
is similar to arctan(y/x). Or remember that tan θ = sin θ / cos θ,
and θ = atan2(sin θ, cos θ).
2. Second, in many software libraries, the atan2 function is
undefined at the origin, when x = y = 0. The atan2 function we are
defining for use in our equations in these notes is defined such
that atan2(0, 0) = 0. In our code snippets we'll use atan2 and
explicitly handle the origin as a special case, but in our equations,
we'll use atan2 which is defined at the origin. (Note the difference
in typeface.)
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
25
Computing θ
• Back to the task at hand: computing the polar
angle θ from a set of 2D Cartesian
coordinates.
• Armed with the atan2 function, we can easily
convert 2D Cartesian coordinates to polar
form.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
26
Code Snippet
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
27
Section 7.2:
Why Use Polar Coordinates?
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
28
Why Use Polar Coordinates?
• They’re better for humans (eg. “I live 22 miles
NNE of Dallas, TX”)
• They’re useful in video games (for cameras
and turrets and assassin’s arms, oh my).
• Sometimes we even use 3D spherical
coordinates for locating things on the globe –
latitude and longitude. More coming up…
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
29
Section 7.3:
3D Polar Space
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
30
3D Polar Space
There are two kinds in common use:
1. Cylindrical coordinates
– 1 angle and 2 distances
2. Spherical coordinates
– 2 angles and 1 distance
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
31
3D Cylindrical Space
To locate the point
described by cylindrical
coordinates (r, θ, z), start
by processing r and θ just
like we would for 2D polar
coordinates, and then
move up or down the z
axis by z.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
32
3D Spherical Coordinates
• As with 2D polar coordinates, 3D spherical
coordinates also work by defining a direction and
distance.
• The only difference is that in 3D it takes two
angles to define a direction.
• There are two polar axes in 3D spherical space.
1. The first axis is horizontal and corresponds to the
polar axis in 2D polar coordinates or +x in our 3D
Cartesian conventions.
2. The other axis is vertical, corresponding to +y in our
3D Cartesian conventions.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
33
Notational Confusion
• Different people use different conventions and
notation for spherical coordinates, but most
“math people” have agreed that the two
angles are named θ and φ.
• Math people also are in general agreement
about how these two angles are to be
interpreted to define a direction.
• You can imagine it like this:
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
34
Finding the Point (r, θ, φ)
1. Begin by standing at the origin, facing the direction of the
horizontal polar axis. The vertical axis points from your
feet to your head.
2. Rotate counterclockwise by the angle θ (the same way
that we did for 2D polar coordinates).
3. Point your arm straight up, in the direction of the vertical
polar axis.
4. Rotate your arm downward by the angle φ. Your arm now
points in the direction specified by the polar angles θ, φ.
5. Displace from the origin along this direction by the
distance r, and we've arrived at the point described by the
spherical coordinates (r, θ, φ).
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
35
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
36
Azimuth, Zenith, Lat, and Long
• The horizontal angle θ is known as the azimuth, and φ is
the zenith.
• Other terms that you've probably heard are longitude and
latitude.
• Longitude is basically θ, and latitude is the angle of
inclination, 90° – φ.
• So you see, the latitude/longitude system for describing
locations on planet Earth is actually a type of spherical
coordinate system.
• We're often only interested in describing points on the
planet's surface, and so the radial distance r, which would
measure the distance to the center of the Earth, isn't
necessary.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
37
Visualizing Polar Coordinates
• The spherical coordinate system described in the
previous section is the traditional right handed
system used by “math people.”
• We'll soon see that the formulas for converting
between Cartesian and spherical coordinates are
rather elegant under these assumptions.
• However, if you are like most people in the video
game industry, you probably spend more time
visualizing geometry than manipulating
equations, and for our purposes these
conventions carry a few irritating disadvantages:
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
38
Irritating Disadvantage 1
The default horizontal direction at θ = 0 points in
the direction of +x.
• This is unfortunate, since for us, +x points “to
the right” or “east,” neither of which are the
default directions in most people's mind.
• Similar to the way that numbers on a clock
start at the top, it would be nicer for us if the
horizontal polar axis pointed towards +z,
which is “forward” or “north.”
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
39
Irritating Disadvantage 2
The conventions for the angle φ are unfortunate in several respects.
• It would be nicer if the 2D polar coordinates (r, θ) were extended
into 3D simply by adding a third coordinate of zero, like we extend
the Cartesian system from 2D to 3D.
• But the spherical coordinates (r, θ, 0) don't correspond to the 2D
polar coordinates (r, θ) as we'd like.
• In fact, assigning φ = 0 puts us in the awkward situation of Gimbal
lock, a singularity we'll describe later.
• Instead, the points in the 2D plane are represented as (r, θ, 90°).
• It might have been more intuitive to measure latitude, rather than
zenith. Most people think of the default as “horizontal” and “up” as
the extreme case.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
40
Irritating Disadvantage 3
• No offense to the Greeks, but θ and φ take a
little while to get used to.
• The symbol r isn't so bad because at least it
stands for something meaningful: “radial
distance” or “radius.”
• Wouldn't it be great if the symbols we used to
denote the angles were similarly short for
English words, rather than completely
arbitrary Greek symbols?
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
41
Irritating Disadvantages 4 and 5
4. It would be nice if the two angles for
spherical coordinates were the same as the
first two angles we use for Euler angles,
which are used to describe orientation in 3D.
(We're not going to discuss Euler angles until
Chapter 8.)
5. It's a right-handed system, and we use a lefthanded system.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
42
Spherical Coordinates for Gamers
• The horizontal angle θ we will rename to h, which is
short for heading and is similar to a compass heading.
A heading of zero indicates a direction of “forward” or
“to the north”, depending on the context. This matches
the standard aviation conventions.
• If we assume our 3D cartesian conventions described in
Chapter 1, then a heading of zero (and thus our
primary polar axis) corresponds to +z.
• Also, since we prefer a left-handed coordinate system,
positive rotation will rotate clockwise when viewed
from above.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
43
Spherical Coordinates for Gamers
• The vertical angle φ is renamed to p, which is short for
pitch and measures how much we are looking up or down.
The default pitch value of zero indicates a horizontal
direction, which is what most of us intuitively expect.
• Perhaps not-so-intuitively, positive pitch rotates downward,
which means that pitch actually measures the angle of
declination.
• This might seem to be a bad choice, but it is consistent with
the left-hand rule.
• Later we'll see how consistency with the left-hand rule
bears fruit worth suffering this small measure of counterintuitiveness.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
44
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
45
Aliasing in 3D Spherical Coordinates
• The first sure-fire way to generate an alias is to add a
multiple of 360° to either angle. This is really the most
trivial form of aliasing and is caused by the cyclic
nature of angular measurements.
• The other two forms of aliasing are a bit more
interesting, because they are caused by the
interdependence of the coordinates. In other words,
the meaning of one coordinate r depends on the values
of the other coordinate(s) – the angles) This
dependency created a form of aliasing and a
singularity:
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
46
The Aliasing and the Singularity
• The aliasing in 2D polar space could be triggered
by negating the radial distance r and adjusting the
angle so that the opposite direction is indicated.
We can do the same with spherical coordinates.
Using our heading and pitch conventions, all we
need to do is flip the heading by adding an odd
multiple of 180°, and then negate the pitch.
• The singularity in 2D polar space occurred at the
origin, since the angular coordinate is irrelevant
when r = 0. With spherical coordinates, both
angles are irrelevant at the origin.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
47
That’s Not All, Folks
• So spherical coordinates exhibit similar aliasing
behavior because the meaning of r changes
depending on the values of the angles.
• However, spherical coordinates also suffer
additional forms of aliasing because the pitch
angle rotates about an axis that varies depending
on the heading angle.
• This creates an additional form of aliasing and an
additional singularity, analogous to those caused
by the dependence of r on the direction.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
48
More Aliasing and Singularities
• Different heading and pitch values can result in the same direction,
even excluding trivial aliasing of each individual angle.
– An alias of (h, p) can be generated by (h±180°, 180° – p).
– For example, instead of turning right 90°(facing east) and pitching
down 45°, we could turn left 90°(facing west) and then pitch down
135°.
– Although we would be upside down, we would still be looking in the
same direction.
• A singularity occurs when the pitch angle is set to 90° (or any alias
of these values).
– In this situation, known as Gimbal lock, the direction indicated is
purely vertical (straight up or straight down), and the heading angle is
irrelevant.
– We'll have a great deal more to say about Gimbal lock when we
discuss Euler angles in Chapter 8.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
49
Canonical Spherical Coordinates
• Just as we did in 2D, we can define a set of canonical
spherical coordinates such that any given point in 3D
space maps unambiguously to exactly one coordinate
triple within the canonical set.
• We place similar restrictions on r and h as we did for
polar coordinates.
• Two additional constraints are added related to the
pitch angle.
1. Pitch is restricted to be in the range –90° to 90°.
2. Since the heading value is irrelevant when pitch reaches
the extreme values of Gimbal lock, we force h = 0 in that
case.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
50
Conditions for Canonical
Spherical Coordinates
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
51
Algorithm to Make (r, p, h) Canonical
1.
2.
3.
4.
5.
6.
7.
If r = 0, then assign h = p = 0
If r < 0, then negate r, add 180° to h, and negate p
If p < –90°, then add 360° to p until p ≥ –90°
If p > 270°, then subtract 360° from p until p ≤ 270°
If p > 90°, add 180° to h and set p = 180° –p
If h ≤ –180°, then add 360° to h until h > –180°
If h > 180°, then subtract 360° from h until h ≤ 180°
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
52
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
53
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
54
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
55
Converting Spherical Coordinates to
3D Cartesian Coordinates.
• Let's see if we can convert spherical coordinates
to 3D Cartesian coordinates.
• For now, our discussion will use the traditional
right-handed conventions for both Cartesian and
spherical spaces.
• Later we'll show conversions applicable to our
left-handed conventions.
• Examine the figure on the next slide, which shows
both spherical and Cartesian coordinates.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
56
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
57
What is d?
Notice that we've
introduced a new variable
d, the horizontal distance
between the point and
the vertical axis.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
58
Computing z
From the right triangle
with hypotenuse r and
legs d and z, we see
that z/r = cos φ, that is,
z = r cos φ.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
59
Computing x and y
• Consider that if φ = 90°, we
basically have 2D polar coordinates.
• Let x' and y' stand for the x and y
coordinates that would result if φ =
90°.
• As in 2D, x' = r cos θ, y' = r sin θ.
• Notice that when φ = 90°, d = r. As
φ decreases, d decreases, and by
similar triangles x/x' = y/y' = d/r.
Looking at triangle dzr again, we
observe that d/r = sin φ.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
60
Putting it All Together
Putting all this together, we have:
x = r sin φ cos θ
y = r sin φ sin θ
z = r cos θ
Using our gamer conventions:
x = r cos p sin h
y = –r sin p
z = r cos p cos h
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
61
Continuing
• r is easy:
• As before, the singularity at the origin when r = 0 is handled as a
special case.
• The heading angle is surprisingly simple to compute using our atan2
function, h = atan2(x, z).
• This trick works because atan2 only uses the ratio of its arguments
and their signs. Examine the equations x = r cos p sin h, y = –r sin p,
and z = r cos p cos h and notice that the scale factor of r cos p is
common to both x and z.
• Furthermore, by using canonical coordinates we are assuming r > 0
and –90° ≤ p ≤ 90°, thus cos p ≥ 0 and the common scale factor is
always nonnegative.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
62
Finally
• Finally, once we know r, we can solve for p
from y.
y = –r sin p
–y/r = sin p
p = arcsin(–y/r)
• The arcsin function has a range of –90° to 90°,
which fortunately coincides with the range for
p within the canonical set.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
63
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
64
Section 7.4:
Using Polar Coordinates to Specify Vectors
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
65
Using Polar Coords to Specify Vectors
• We've seen how to describe a point using
polar coordinates, and how to describe a
vector using cartesian coordinates. It's also
possible to use polar form to describe vectors.
• Polar coordinates directly describe the two
key properties of a vector, its direction and
length.
• As for the details of how polar vectors work,
we've actually already covered them.
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
66
That concludes Chapter 7. Next, Chapter 8:
Rotation in Three Dimensions
Chapter 7 Notes
3D Math Primer for Graphics & Game Dev
67

similar documents