Hidden line algorithms are procedures in which lines in three dimensional representations of objects are hidden because they are determined to be on the “far” or opposite side of the shape, and as such, they should not be seen. This type of algorithm is very important in three-dimensional graphing software, such as that employed by computer-assisted design (CAD) programs. In order to provide an accurate representation of the object, and thereby allow the user to correctly interpret the object, certain lines must be hidden.
Although there are numerous algorithms that do this, none of them is simple or quick. They all require a relatively large amount of processing power, and thus, are cumbersome. Therefore, using the quickest hidden line algorithm possible is extremely important, as is finding new and faster algorithms altogether.
The first of these algorithms was written by Appel. He employed a counter of all forward facing surfaces on objects that do not have interpenetrating faces as a method of determining which lines needed to be hidden. This algorithm was also written for closed-faced or self-contained bodies.
Additional modifications can be made for bodies that don’t follow these rules. For example, calculations can be done on bodies with interpenetrating faces to break them into 1- and 2-manifolds. A 1-maifold has all front facing surfaces, and a 2-manifold is the type of body the algorithm was designed for.
Appel’s algorithm is what is known as an edge/intersection algorithm as it uses edges and intersections as the primary focus of the calculation. Other types of algorithms that seek to accomplish the same hidden-line removal use various other parts of the body. Some of these include the Weiss algorithm, which is a point/surface test, the Galimberti/Montenari algorithm, a surface/surface test, and the Watkins algorithm, a sample span test.
Currently, the most popular algorithms are known as z-buffering and face drawing algorithms. Z-buffering removes all hidden surfaces, and is very slow because it compares all interior points. Face drawing would be faster, since it simply overwrites hidden lines with the front-most face, except that it still has to compute the interior points of those frontal faces. Current CAD modeling cuts down on processor usage by employing an analogous procedure to a hypothesis test. The computer determines a probability and, if it is of a certain value, makes the binary decision to draw or not draw. Obviously, if the decision is wrong, the algorithm produces an incorrect result and the shape is misrepresented by the graphics software.
Use of such probability-based algorithms is largely an acceptable manner of drawing the three-dimensional objects that are needed in software such as a CAD. Although there is a chance of error, all of the research conducted in the world also incorporates a similar chance. It’s an acceptable chance of error to produce great results; in this case, the most sophisticated design software in existence.
References:
1. Heger, Walter. “Vector Hidden Line Removal and Fractional Quantitative Invisibility.” http://wheger.tripod.com/vhl/vhl.htm
Mr. Heger is a software developer who has contributed to numerous marketed software products.
2 Comments
October 22, 2006 at 12:09 am
Coincidence????
In the research on the Hidden Line problem, research uncovered that much of the work was attributed to Arthur Appel (1960). In the post on the Four Color problem, a Kenneth Appel (1972) was part of the computer solution. Both problems
involved heavy computer calculations and simultations.
Coincidence? Relation?
The type of work (heavy computational) was common to both problems.
Interesting ….
Dr. Glass
August 12, 2008 at 6:43 pm
What about the poweful Nasa hidden line algorithm. It was very fast and quite general.