# How to find contour lines for Appel's Hidden Line Removal Algorithm

For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all assume you have access to OpenGL, unfortunately I do not have access to anything like that for the DCPU-16 (or any kind of hardware acceleration).

I found a fairly good description of Appel's algorithm on Google Books. However there is one issue I am having trouble figuring out.

Appel defined contour line as an edge shared by a front-facing and a back-facing polygon, or unshared edge of a front facing polygon that is not part of a closed polyhedron. An edge shared by two front-facing polygons causes no change in visibility and therefore is not a contour line. In Fig. 8.4, edges AB, EF, PC, GK and CH are contour lines, whereas edges ED, DC and GI are not.

I understand the rules of the algorithm and how it works once you have your contour lines, however I do not understand is what I need to do to determine if a edge is "shared by a front-facing and a back-facing polygon, or unshared edge of a front facing polygon that is not part of a closed polyhedron" from a coding point of view. I can look at a shape and I can know what lines are contour lines in my head but I don't have a clue on how to transfer that "understanding" in to a coded algorithm.

## Update

I have made some progress in determining contour lines. I found these two lecture notes from a University of Buffalo class on computer graphics.

Consider the edges. These fall into three categories.

1. An edge joining two invisible faces is itself invisible. This will be deleted from the list and ignored.
2. An edge joining two potentially-visible faces is called a 'material edge' and will require further processing.
3. An edge joining a potentially-visible face and an invisible face is a special case of a 'material edge' and is also called a 'contour edge'.

Using the above two pieces of information I am able to get closer to being able to write this out as code, but I still have a long way to go.

• Meta discussion about this question: Should I move my question to math.stackexchange.com? Apr 22, 2012 at 22:31
• Check this answer on calculating triangle's normal. Dot product of the normal vector with line-of-sight vector determines if a triangle is front-facing.
– 9000
Apr 23, 2012 at 16:57