A Primer On Computational Geometry – Part One

I’ve done a couple of posts now on simulating physics, but I approached the topic from somewhere out by the deep end, so I figure it’s high time to start simple and build a pier out to that deep end.  That means covering some basic level math and physics (don’t worry, no homework), and when it comes to physics simulations, geometry is a pretty good place to start building.  The why is simple; while there are methods for simulating real world physics without geometry, interpreting the results of those methods requires a deep understanding of the models in use, so the data makes sense.  Models that use geometry still require understanding, but if the information is displayed on the geometry, even lay people can get a feel for what the information is trying to tell us.

For example, here is a wing showing contours of pressure:

 

You should already be getting a feel for how pressure is distributed on the wing.  Let’s fill in the contours:

Now the information is even easier to get a feel for.  The pressure is low on the top and higher on the bottom.  Here is the same wing, but with streamlines that indicate velocity.

If you look, you can see that where the velocity is blue, the pressure is red, and vice versa.  This is because of Bernoulli.  A quick examination of images like this serve as a sanity check for analysts.  If I did not see this relationship between pressure and velocity play out, I’d know something was very wrong with my model.  I could plot this on a simple X-Y plot, but the results would not be as obvious to someone who is not an experienced analyst.  So geometry has value in a lot of physics simulations, hence it’s useful to understand how we represent geometry inside a computer.

Additionally, how we represent geometry inside a computer is largely consistent across disciplines, be it physics, computer animation, or video games.  Geometry is geometry.

And finally, before we begin, when talking about software development, it is important to understand that quite often there is more than one way to skin the metaphorical cat.  Those of you who have a background in developing software that uses geometry may know of other, better ways to get the same job done.  What I am presenting is what I feel to be easy for lay-persons to grok.  Please feel free to expand on your such methods in the comments.

There is a point to it all

The first thing you have to model is a point in space.  Since we live in a universe with 3 spatial dimensions, we model the point with three coordinate values, commonly know as X, Y, and Z, and denoted as (x,y,z).  This is known as Cartesian coordinates ¹.  These are real numbers ² and they can go from -infinity to +infinity, although we generally don’t go that far.  The very first point you have to define is the origin, or (0,0,0).  The origin is just a reference point, the point all other points will be located from.  Then you need to define your axes, or the directions away from the origin that define the directions of the three coordinates.  Cartesian coordinates have three axes, and all three are rotated 90 degrees away from each other.  Again, the actual direction of any axis doesn’t matter, as long as it is rotated 90 degrees away from the other two.  The axes exist just so you know what direction to measure along when locating a point in space.  It is tempting here to try and imagine that there is some grand, universal origin and some set of primary axes, but there isn’t.  It’s all very arbitrary.  As we get further along, we’ll talk about multiple frames of reference and how they can interact, and how quickly you can melt your brain when those frames of reference start moving and rotating about each other (Satellite Dynamics can be so much fun…).

Now, just to be complete, here is how we use a point in the computer.  We establish an origin.  Then we establish axes.  Then we input a point, say (2,3,4), which tells the computer to move 2 units ³ along the X-axis, 3 units along the Y-axis, and 4 units along the Z-axis.  You have just located your point in space.  Now we have two points (the origin and (2,3,4) ), so let’s draw a line connecting them.

Lines, Lines, Everywhere are Lines… (Wait, that’s not how that song goes…)

Alright, we got a line!  It connects two points.  Everyone knows what a line is, right?  We can move o…

No.  No, we can’t.  Because computers can’t ‘see’ lines like we can, so we have to give computers tools to ‘see’ the line, and since these are computers, those tools are based in math, and math means equations.  You might be thinking, “Why do we have to get math involved, I’m writing software here, can’t I just create a “Line” object, set the two points as data members, and crack open a hoppy micro-brew you’ve never heard of, because ‘hipster’?”

No, at least, not if you actually want to do anything useful with it.  So back to math class we go ⁴!  If you recall, there is an equation for a line, called the Standard Line Equation, and it looks like this:

Ax + By + C = 0

This is the 2D version; for 3D, we just add another term.

Ax + By + Cz + D = 0

Let’s just stop right here.  If you have any recollection of geometry and algebra, you remember other forms of this equation call the y-intercept and the point-slope and handful of others.  Those are all very useful forms of the line equation, but only if you are plotting the line on graph paper.  These equations aren’t much use when modeling geometry.

Turns out, if I want to define a line in a computer, I would create a line object and add the two points as data members.  Stop, no, put down the axe…  I have to do a bit more work than that, I promise.

One of the more useful forms of a line is what we call a vector

Not that vector, but he gets the definition right.  It’s a line that describes direction and magnitude.  Magnitude is the length of the line, and direction is… well, direction is the difference of all three coordinates.  Let me show you.  Say we have two points, (1,2,3) and (7,8,9).  I want a vector that describes a direction from the first point to the second, so I would subtract the first point from the second, like so:

7-1 = 6
8-2 = 6
9-3 = 6

Giving us a vector of (6,6,6), and a direction to start walking when you all tell me to go to hell.  If I wanted the vector to point the other direction, I’d flip the subtraction, so:

1-7 = -6
2-8 = -6
etc.

Of course (6,6,6) looks an awful lot like a point, so normally we’d write it with an over-score or arrow over the whole thing, but I can’t figure out how to do that on WordPress, so let’s go with a different convention, square brackets: [6,6,6] .  How do we read that vector?  Simple, it’s movement in the three directions starting from the base (the first coordinate) to the head (the second coordinate), we run 6 units along X, shift 6 units along Y, and rise 6 units along Z.  That simple.

Now, magnitude!  It’s 6, right?  Nope, it’s the hypotenuse of a triangle.

The hypowhosit of a triangle?

They hypotenuse of a right triangle.  Remember those?  Two legs, a and b, at 90 degrees to each other (a right angle), and the length of the hypotenuse c can be found with the Pythagorean Theorem, which says… No, I am not just making up names now, damn Greeks, pay attention!  Pythagoras found that for a right triangle, the sum of the squares of the legs equals the square of the hypotenuse (the third line of the triangle), or:

a² + b² = c²

In three dimensions, we just add a third term.  And hey, look, we already know the three values of x, y, and z:

x² + y² + z² = c²  or 6² + 6² + 6² = 36 + 36 + 36 = 108 => square root (108) = ~10.39

The vector magnitude is about 10.4, TaDa!  But what if we just want to denote direction?  Then we use what is known as a Unit Vector, or a vector whose magnitude is exactly equal to one.  If I wanted my highway to hell vector to be a unit vector, I would simply divide each component by the magnitude, or [(6/10.4), (6/10.4), (6/10.4)]. Yay! A Unit Vector!

I have two points, a way to describe how a line is oriented in space, a way to find the length… Is there anything else I can do with this line?  Well, yes, funny you should ask, you can define a plane with it.  But first, hold onto that feeling of astonishment, we need to talk about planes.

Planes (not the kind you get drunk on and embarrass yourself, your family, and all your ancestors when the video goes viral – unless you are on a bar, then it’s exactly that kind of plane)

If a line is a one dimensional object that is defined by two points (or one point and a vector along the line), a plane is a two dimensional object that is defined by two intersecting lines, or one vector.

Let’s take that first definition.  Draw a triangle.  You now have three intersecting lines, and two of them are sufficient to define a plane.  Erase one side of the triangle, and the remaining two sides, as long as they have one, and exactly one point in common, will define the plane.  The point tells us where the plane is located in space, and the two lines give us it’s orientation.  We can’t use a single line, because our plane could rotate about that line and we’d have no idea what position it would be at.  The second line settles that question.  The point of intersection is important because it ensures our two lines form a plane.  If the lines never intersect, well, let’s look at these images.

Two lines and a point of intersection.  Excellent.  Is that how a computer defines a plane?

No.  The computer uses the point and vector.  How, you ask?  Let’s go back to the two intersecting lines.  There is a bit of linear algebra called a Cross Product.  It’s a way to multiply two vectors together in a specific way.  Let’s take two vectors, [a,b,c] and [u,v,w]; the cross product looks like this:

[a,b,c] x [u,v,w] => (bw – cv)x + (cu – aw)y + (av – bu)z

Notice the x, y, and z terms in there?  Those are just there to denote direction.  The results of the computations in the parenthesis will combine to form a new vector, and the nature of the cross product calculation will guarantee that the new vector will be exactly orthogonal to the two vectors that formed it.

If you still don’t have this in your head yet, take out a piece of paper and lay it flat on the table.  On the paper, draw a triangle with one side missing (i.e. two lines that meet at a single point).  Those lines are now vectors pointing away from the point of intersection.  Go ahead and draw arrowheads on the free ends of the lines if you want, so you know they are vectors.  Now, take your writing utensil (a pencil) and stand it up at the point of intersection so it points directly away from the paper like a magnificent phallic tribute to the patriarchy ⁵, such that if you were to measure the angle between the pencil and the paper, you would always have a 90 degree angle (i.e. perpendicular).  The pencil is the result of the cross product of the two lines you drew, and because it is precisely rotated 90 degrees away from the plane, it is orthogonal to the plane.

If I have a vector, any vector, there is a plane in space that my vector is orthogonal to.  Likewise, if I have a plane in space, there is a vector that is orthogonal to it.  This relationship means that with a single point and a vector I can define a plane.  That vector is known as the normal of the plane.

Want one more bit of evidence that a vector defines a plane?  Here is the equation of a plane in standard form:

Ax + By + Cz + D = 0

Look familiar?

If the plane is infinite, we use a unit vector (called the unit normal) to define it.  If the plane is finite, you can still use a unit normal, or you can use a normal with a magnitude not equal to 1.  Turns out, those two vectors you performed a cross product on, they form a triangle, and the magnitude of the resultant normal is exactly equal to twice the area of that triangle (or the actual area of a parallelogram that has the two vectors for sides).

Another bit of linear algebra we can do is called the Dot Product (aka the Scalar Product).  Dot products are dead simple.  Using our two vectors from above, it works like this:

[a,b,c] . [u,v,w] => au + bv + cw = C => ||a|| ||u|| cos (theta)

So that last expression requires a bit of explanation.  C is a constant (or scalar) value.  It’s whatever number the previous multiplication and addition results in.  ||a|| is the magnitude of the [a,b,c] vector, and ||u|| is the magnitude of… you get it.  Cos (theta) is Cosine of angle theta, which is the angle between the two vectors.

Well that’s nice, but how is that useful for computer geom… WAIT!

If I had three points in a computer, I could use them to form two vectors, find the magnitudes of all the vectors, perform the dot product, use the known magnitudes to back out the angle between the vectors (do the same for the other angles as well so I know the side lengths and angles of the triangle), then perform the cross product of those two vectors, take the magnitude of the cross product vector and use that to find the area of the triangle the three points form, as well as find out precisely how the triangle is oriented in space!  Holy crap!

And that is how it starts.

Next up, combining triangles into polygons, and modeling polyhedra and other solid shapes.

 

Image by Internet Archive Book Images

1. There are also Cylindrical and Spherical coordinates, but let’s stay with Cartesian for the time being
2. you can use imaginary numbers, but then you are doing something different, so again, keeping it simple, and we’ll stay with real numbers
3. inches, centimeters, astronomical units; whatever you need for your geometry
4. Shut up, if you keep wailing, it’ll only hurt more
5. can you feel the testosterone?