Mapping 3D Line Segments

Date: 10/06/97 at 20:12:39
From: Dave Ice
Subject: How do I map 3D line segments onto a 2D perspective as seen 
from an arbitrary point in space?

This thought experiment has me stumped. I'm writing a computer program 
where a stick figure is seen from different perspectives. When the 
stick finger moves his limbs, I want the movements to be accurately 
projected on the 2D computer screen in "correct perspective." I'm 
looking for a general algorithm that will map 3D movements into 2D 
perspective no matter where "in space" I view the stick figure from.

I *think* I can state the problem this way:

PROBLEM:
-------
Given:  a line segment defined by the following:
     Length = L
     Start Point (relative to the origin) = (Xa,Ya,Za)
     Theta = angle of rotation in the XY plane
             of the segment about the point (Xa,Ya,Za);
             measured counterclockwise from the positive X axis
     Phi = angle of rotation in the YZ plane
           of the segment about the point (Xa,Ya,Za);
           measured counterclockwise from the positive Z axis
(this is all I know about one of the stick figure's limbs when it is 
moved)

Problem 1:
Find the End Point (Xb,Yb,Zb) relative to the origin (0,0,0)

Problem 2:
Find a 2D representation of the line segment as viewed by an observer 
at an arbitrary point P = (Xp,Yp,Zp) in space; i.e.
     (Xa',Ya') = [Function](Xa,Ya,Za)  and
     (Xb',Yb') = [Function](Xb,Yb,Zb)


WHAT I'VE DONE
--------------
I believe the answer to Problem 1 is:
     Xb = Xa + (L * cos(Theta) * sin(Phi))
     Yb = Ya + (L * sin(Theta) * sin(Phi))
     Zb = Za + (L * cos(Phi)
We also know that
     L = SQRT[ (Xb-Xa)^2 + (Yb-Ya)^2 + (Zb-Za)^2 ]

In the special case where the observer is located directly on the X or 
Z axis and the stick figure's waist is located at the origin, my 
program seems to work ok using the above polar coordinate equations 
because I don't need to figure out what to do with the Z coordinate.  
But I'm left with no "perspective"; rotations in the perpendicular 
plane are "invisible" as illustrated below.

     Stickman lifts his arm (Theta rotation) in profile;
     in front view the movement cannot be seen.
              O                O
           ^  |--           ^  |
           y  |             y  |
              |  x ->          |  z ->
         profile view      front view

Similar events happen to other limbs that can rotate in two planes; 
they tend to disappear from the perpendicular view.

I think I'm on the right track (maybe not).  What I need is a way to 
simulate this perspective...
      y
       |
       |
       |________x
      /
     /
    z

...in a 2D coordinate graphing system.  But I'm hoping there's a 
general solution to this problem that works for any perspective.


WHAT I THINK I NEED
-------------------
Seems to me I'm talking about two things: a coordinate translation and 
a coordinate projection. I surfed the Geometry Center Home Page at 
http://www.geom.uiuc.edu    and found a section on "Projective 
Transformations" that I didn't fully understand; it involved a 4x4 
matrix acting on 3 coordinates to produce 3 different coordinates.  
My need seems to be for a matrix (or function) to turn 3 coordinates 
into 2 coordinates.

My math skill: I took first-year calculus in college; I'm okay at 
geometry knowledge but my spacial visualization isn't good - this 
problem may be ridiculously simple and I'm just missing it. It's been 
a long time since I did matrix math, so if the solution turns out to 
be a matrix, I'd appreciate pointers or references.

Thanks for taking a look!

Date: 10/07/97 at 14:37:50
From: Doctor Tom
Subject: Re: How do I map 3D line segments onto a 2D perspective as 
seen from an arbitrary point in space?

Hi Dave,

Unfortunately, the easiest way to do it (by far) is by using the
4x4 matrix transformations. You actually have to turn 4 dimensions
into 2, assuming that you're drawing pictures of 3D items.

This is what's taught in a first year course in computer graphics,
so I'm not going to list all the details here, but I'll give you
a couple of pointers, and you can then look in a book on
computer graphics for the details.

The great thing about 4x4 matrices is that they represent almost any
transformation you might be interested in - rotations, translations,
uniform or non-uniform scalings, shear operations, one, two, and
three-point perspective transformations, orthogonal transformations,
windowing operations, and even more bizarre things.

If you need to do a combination of things like a rotation followed
by a translation followed by a perspective transformation, you just
write down the three different matrices for those 3 operations,
multiply them together, and the resulting product of matrices
represents the combined operation and you can multiply all the 3D
points in your original model by this one matrix to get the
transformed points.

For technical reasons, you need a fourth coordinate to do this
efficiently, but the idea is this:  The 3D point you would call
(x, y, z) is represented by any 4D "homogeneous" vector like this:
(ax, ay, az, a), where a is non-zero. We usually pick a to be
1, so it is represented by (x, y, z, 1). But if after multiplying
your input 4D vector by the matrix you get something like this:
(2, 11, 18, 2), the a is 2, so this corresponds to (2/2, 11/2, 18/2)
in 3 dimensions.

The trick with perspective transformations is that although the 
result will be a 4D homogeneous vector, you can change it (as 
explained above) to a 3D vector.  But it is cleverly done so that the 
z coordinate of that vector can be ignored - the x and the y represent
screen space. The z coordinate is not useless, however. It gives an 
indication of how "deep" into the picture the object is. This is 
useful if you're drawing a bunch of items that behind each other from 
certain points of view. To draw them correctly, you need to draw the 
stuff behind followed by the stuff in front so that objects that are 
partly obscured are rendered correctly.

I hope that's enough of a start. Now go to a book on computer graphics 
for the details on all those transformation and projection matrices.  
A good (but expensive) book is called, _Computer Graphics: Principles 
and Practice_, second edition, by Foley, van Dam, Feiner, and Hughes.  
Don't worry if you can't find that one, though, because there are 
others that are pretty good as well.

Good luck.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/