Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from programmers.stackexchange.com Aug 12 '12 at 19:35

This question came from our site for professional programmers interested in conceptual questions about software development.

    
Meta discussion about this question: Should I move my question to math.stackexchange.com? –  Gilles Apr 22 '12 at 22:31
1  
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 '12 at 16:57

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.