[Solved]: How to find contour lines for Appel’s Hidden Line Removal Algorithm

ignougroup
Problem Detail: 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.

Fig. 8.4 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. enter image description here

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.

Asked By : Scott Chamberlain

Answered By : Yves Daoust

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3139

Leave a Reply