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

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 http://0x10c.com/doc/dcpu-16.txt. 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 http://books.google.com/books?id=aVQnUfL3yEwC&lpg=PA251&ots=zCOEvuKqve&dq=Arthur%20Appel%27s%20algorithm.&pg=PA252#v=onepage&q&f=true. 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 http://www.eng.buffalo.edu/courses/mae573/handouts/lecture13.pdf http://www.eng.buffalo.edu/courses/mae573/handouts/appel.pdf lecture notes from a University of Buffalo class on computer graphics. Consider the edges. These fall into three categories. An edge joining two invisible faces is itself invisible. This will be deleted from the list and ignored. An edge joining two potentially-visible faces is called a 'material edge' and will require further processing. 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.

• Answer:

  For the "-facing" rule to hold, you must make sure that all faces are properly oriented. Use the right-hand rule for instance, that means that the vertices of a face should be numbered in such a way that a positive rotation in the plane of the face corresponds to a normal pointing outside of the polyhedron. (Got it ?) Or more simply, every face must come with its outward-pointing normal. Dangling faces, i.e. not belonging to a closed polyhedron can be seen as having an undeterminate orientation. Now computing the parts of an edge which are hidden by a contour polygon is the main course. This problem is very close to that of clipping a line segment by a polygonal window in 2D. First consider the line of support of the line segment and find intersections with the polygon. By using a parity rule, you can easily determine the parts inside and outside the polygon.