A Primer On Computational Geometry – Part Three

We’ve discussed building polygons.

Posts one and two both dealt with things straight and flat.  Sure, give me enough short, connected lines or triangles with very small connected angles, and I can give you the visual illusion of curvature, but mathematically, you ain’t fooling anyone.

But that doesn’t mean all curvature inside a computer is an optical illusion.  Although, with most computer graphics, what you see on the screen is straight lines and polygons, since it vastly reduces the rendering load on the processor, but that is not necessarily how the geometry is defined.

We can define curves mathematically, which means we can define them that way in the computer.  So how do we define a curve in a computer?

Functional Curves

Curves are defined by functions.  A function is an equation that takes an input value and produces an output value.  Probably the simplest curve function is a parabola.

y = x²

Give it a value for x, and it will spit out a y value that is the square of x.  And it will do it to infinity.  This is known as a continuous function.  If you plot these points on an Cartesian (XY) plot, you will get a parabola with the very bottom at the origin.  You can manipulate the position of the bottom of the parabola by adding values, or alter it’s shape, or the direction, by introducing coefficients, until you get exactly the parabola you want.

Now you may be thinking, how is this different from a bunch of small connected lines?  I mean, if you enter in discrete values for x, you will get discrete values for y, so when you plot those discrete values, you’d essentially be getting a bunch of connected lines between the discrete points, right?

No.  At least, not mathematically.  If I construct a parabola from a series of discrete lines and points, even if I use the parabola equation to find those lines and points, inside the computer, each line segment has its own equation that I have to store and process.  If I store the parabola as a a function, then I only have to store the one function.  Not only do I need to store just the one equation, I also get the added benefit of being able to change resolution on the fly, so instead of my parabola being composed of 20 points, I can very easily and accurately have it be composed of 100 points, and I don’t have to worry about problems with interpolation between the existing 20 points.

Cut It Twice And It’s Still Too Short

Let me explain the interpolation issue a bit here, because this is important.

Interpolation is the process by which we fill in the gaps in data by using the data we have.  So if I have two discrete points on a curve, I can interpolate between those two points to make a good guess at the data between those two points.  The simplest interpolation is a linear interpolation, which assumes that a straight line exists between the two points, so it’s pretty easy to fill in the data.  If the curve is pretty gentle between those two points, a linear interpolation is probably sufficient to fill in the missing information.

However, if the curvature is more aggressive, you are going to need interpolation techniques that use more information than just the two points of interest, such a 2nd order interpolation, or a higher order polynomial interpolation.

In the image above, if we did not have any of the information below the 5 line, a linear interpolation between those two boxed points would be very poor indeed.  Even a second order interpolation would probably fail to predict the rest of the parabola exactly, but it would get much closer.

Of course, parabolas are an easy target.  A quick examination of the curvature above the 5 line would strongly suggest a parabola, hence finding the rest of it would be possible.  However, not every curve is this nice.  Here is the plot of a 4th order polynomial.

This is why it’s better to just figure out a function for the shape you want, and store that, rather than the points.  If you find yourself missing data, you don’t need to interpolate, you just rerun the function with more input data until your missing data is known.

Interpolation also has a cousin, extrapolation, which uses all of the known data in an attempt to estimate what is happening past the limits of the known data.  However, extrapolation is beyond this discussion.

A Round Toit

Obviously, we need some functions to begin with.  We have the function for a parabola, so what are some others?  There are functions for planar shapes such as circles, ellipses, hyperbolas and other conic sections, as well as a large set of three dimensional shapes, like spheres, ellipsoids, and a whole host of more complex shapes.  One thing to note of all the proceeding examples is that the surfaces are largely continuous, which is to mean, there are no defined edges.  A lot of regular shapes have defined edges, which typically means the definition will involve two or more functions working together and satisfying some manner of conditions.

Take, for instance a cone or a cylinder.  If you follow those links, you’ll notice in the equation section, there are equations and defining inequalities.  Those inequalities simply define the outer boundaries of the shape and are necessary because the shape is not continuous.

All of these kinds of shapes, where there are equations that can define them, are known as mathematical surfaces or solids, and believe it or not, almost every shape you find in nature (and even many you don’t) can be defined by a set of functions or equations.

Spline-ing It All Together

While every surface and solid has a mathematical definition, finding that definition can be tricky.  Regular shapes are easy, but what happens when the shape is quite irregular?  In those cases, you can do two things; curve fitting, and using splines.

Curve fitting is taking all the known data and attempting to find a polynomial that best fits that curve.  Any good symbolic math package will have built-in functions to do this, and you can do it by hand using techniques like the Least Squares method, but no matter what you do, chances are pretty good the resulting polynomial will not precisely pass through every data point.  This is not necessarily a bad thing.  If your data was noisy to begin with (like, say, wind tunnel data), a curve fit that is not precise is probably a good thing, since, if you do it right, it will wash out a lot of the error.  However, if the data is precise, like data points taken with a laser scanner that was run over a highly organic shape you want to duplicate, then a curve fit might not work and you’ll need to build a spline.

A spline is a discontinuous function.  What this means is that it isn’t a single function or polynomial that attempts to define the shape of a curve, but is a specific set of equations that define pieces of the curve.  If you play around with vector graphics or any kind of 3D-modeling, you’ve run across splines and their 3D variant, NURBS (Non-Uniform Rational B-Splines).  Splines have some key features.  They have start and end points, called nodes, or control points.  The nodes have properties that determine if they define a line or a curve between them, and how that line or curve behaves relative to the node and any other line or curve connected to the node (if it is a midpoint node).  Those properties and characteristics are often set with handles that help control the shape.

What is happening in the software is that between each node, a function is being built that defines that curve, and rather than storing every pixel along that line, the function is stored.  Then, later, when someone whats to view the image, the viewing program doesn’t just locate and display pixel data, but rather paints pixels along the defined curve function.  It loads a bit more work onto the viewing program, but it not only lets you save a bit on storage space (and allow for greater data compression), it also gives you perfect scaling of the image, because no interpolation is necessary when blowing the image up, and no data is lost when shrinking it.

And as I mentioned before, this can be expanded into three dimensions, allowing a person to generate a near infinite range of curving surfaces by creating splined surfaces that can then be stitched together, which brings us to the next piece of this process, Boolean Operations (named after George Boole).

Booleans Are Not Scary

Regardless of how creative you are with splines, there will come a point where torturing your splines further becomes painful for everyone involved.  Not only does it represent a ridiculous amount of work for the designer, but you run the risk of creating geometry that other software packages will find difficult to process. ¹  In order to avoid this, it’s handy to use Boolean operations.

Boolean operations fall into 4 types: Addition, Subtraction, Intersection, and Imprint.

Addition, also called a Union, takes two shapes and combines them.

The important thing to note is that the resultant shape is unified. All interior surfaces are removed.  If I was to machine this part from a hollow ball and pipe, I would cut the sphere flat where I wanted to attach it to the pipe, and cut the pipe to the proper length, then weld the two together.

The Subtraction removes one shape from another.

This operation can also be flipped, so the peg is retained with a spherical cup on one end.

Intersection retains only the volume that is shared by the two shapes.

This is very useful if I need to combine two shapes in a inverse manner.  Intersection can be kind of tricky to use, since it requires an ‘inside-out’ way of thinking about the shapes.

Imprint causes both shapes to cut each other while retaining everything.

This is very useful if I need to be able to alter the properties of the cut surface.  I use this a lot when I need part of a surface to become an inlet or an outlet (the hole in the block could become a nozzle or a drain), or I want part of an object to become a sensor (the end of the peg is suddenly temperature sensitive and I can use it in my simulation to act as a thermometer).

One thing that is important to remember when doing these Boolean operations is that the original geometries are never truly lost.  The software has to keep them, even if it doesn’t display them, because those geometries define the downstream geometries.  It is possible to define the downstream geometries without retaining, but it is a lot more complex and you lose an important ability, which is being to move backward through the workflow and change things.  For example, you want the peg that was subtracted from the ball to penetrate a bit deeper, or have a slightly larger radius.  Then you just roll everything back to the point where you define the peg, make the change you want, and cause everything to roll forward to the end.  In addition to making changes easy, it’s a great way to spot inadvertent errors, especially in complex geometry.  If your change alters something downstream enough as to be of poor quality, the software will flag it for you to fix.

Sweeping Without a Broom

Aside from Boolean Operations, another way to create shapes to perform a sweep.  The essence of a sweep is to take a 2D shape and extend it along a path to form a volume.  For instance, the peg up above was made by creating a circle and sweeping the circle along the Z-axis for a certain length.  That gives me a cylinder.  The block was made in a similar fashion, but with a rectangle.  This is called an extrude (you are extruding the polygon into a solid shape).  You can also apply smooth transitions to the extrusion, such as a draft, which applies an angle to the extrude.  Had I applied a draft to the cylinder extrusion, I could have made a cone.

Another form of the sweep is the revolve.  A revolve takes a shape and spins it around an axis of revolution.  I made the ball by creating a semicircle and designating an axis that ran along the flat edge of the semicircle, then I revolved the semicircle around the axis for 360 degrees.

Now, of course, a ball, cylinder, and block are regular shapes and can be created mathematically without the need for a sweeping operations, but complex shapes are not.  For instance, if I combine an extrude and a revolve, I can get a spiral or screw shape.  If, instead of telling an extrude to follow an axis or other linear direction, I tell it to follow a spline curve, I can build a bugle.  If I create two 2D shapes, such as a circle and a square, and link them with a line or curve, I can do a loft, which instructs the sweep to move from, say, the circle, along the linked path, to the square, and gradually alter the cross sectional profile as you go. ²  There are numerous other kinds of operations a given software package can have, but they are almost all some variation of these basic Boolean or sweeping operations.

Mathematics All The Way Down

But in the end, all of these shapes are defined mathematically.  Lines and curves exists as end points and functions.  The regular shapes exist as reference points and the associated functions.  And solids exist as reference points, functions, and whatever shapes and operations were used to build them.  It doesn’t become point cloud data until it is time to discretize everything for display or numerical analysis.  The mathematical definitions are orders of magnitude more accurate, allow for near infinite scaling, and permit designers ³ to move forward and backward along the workflow in order to affect changes easily.

 

1. I ran into this problem a lot when I was a support engineer; naval architects would use Rhino to create hull shapes, because Rhino, being a software package for animators, would allow them to torture splines to death.  The resultant geometry could be processed by our software package, but our software had higher standards with regard to geometric quality, and tortured splines make for bad engineering quality geometry.  I had a sitdown with the folks at Rhino for a day and explained our concerns, and they demonstrated why bad things were happening and how to easily avoid it.  I then took that information back to my customers who used Rhino, and not a single architect was willing to alter their workflow to make the CFD analysts’ jobs a bit easier.   Sigh…
2. This is how we build wings; each wing rib is a 2D profile, they are all linked at the leading edge, and you loft from the root to the tip.
3. or optimization routines