Westheimer's Discovery:
   A couple of months in the laboratory can  
   frequently save a couple of hours in the library.

Concept 5.1 :  Triangulation
=============================

Idea:
=====
In this section we discuss developing good
skills at rendering complex surfaces.  We will also
later in this section touch on triangulation and 
provide an example.

Pointers to Polygon rendering 
=============================

  o  Keep polygon orientations consistent.  Make sure,
     that when viewed from the outside, all polygons on 
     the surface are oriented in the same direction i.e.
     (all clockwise or all counterclockwise).  
     Consistency in orientation is necessary for two sided 
     lighting.

  o  When subdividing a surface watch out for any non
     triangular polygons.  The three vertices of a triangle 
     are guaranteed to lie on a plane; any polygon with
     four or more vertices might not.  

  o  There is a tradeoff between how fine you want to
     subdivide and the rendering speed. i.e. the more the 
     triangles used the slower the rendering.  A geneal 
     rule of thumb is that objects whicha are further away 
     in a screen can be rendered with fewer polygons than 
     objects closer to the viewpoint.

  
  o
					     
			  /\			 
			 /  \		
			/    \	       
		     A /__B___\C            
		       \  |   /            
			\ |  /             
			 \| /              
			  \/               
    
     Try to avoid T-intersections in your models.  The one 
     shown above is undesirable since there is no guarantee 
     that the line segments AB and BC lie on exactly the same 
     pixels as segment AC.


Triangulation of Surfaces
=========================

A valid triangulation of a figure X is a collection of 
triangles satisfying the following 2 conditions:
(1) The collection together exactly covers X.
(2) Two triangles in the collection are either
    (a) disjoint (ie., do not intersect at all), or
    (b) intersect exactly in a vertex of both, or
    (c) intersect exactly in a side of both.

The 2 triangles ABC and CDA give a valid triangulation of the 
rectangle ABCD.

 A ____D
  |\   |
  | \  |
  |  \ |
 B|___\|C

The 3 triangles ABC, ADE, and CDE do not give a valid 
triangulation of ABCD as ABC intersects ADE in AE, which is a 
side of ADE but *not* of ABC (it's just *part* of the side AC).

 A ____D
  |\  /|
  |E\/ |
  |  \ |
 B|___\|C

In other words, an implication of condition (2) above is that 
if a vertex of one triangle lies on another then it *must* also
be a vertex of that triangle.

The 2 triangles ABD and ACD do not form a valid triangulation
of the *pentagon* ABECD as they intersect in a triangle AED 
which is, of course, neither a side nor vertex of either. However, 
triangles ABE, ADE, and DEC do form a valid triangulation of 
the pentagon.

 A ____D
  |\  /|
  |E\/ |
  | /\ |
 B|/  \|C

Note: The vertices of the triangles in a triangulation do not all have
to come from the vertices of the figure being triangulated. Extra
vertices can be introduced (called Steiner vertices). Eg, AED, DEC,
BEC, and ABE give a triangulation of ABCD with a Steiner vertex E.

 A ____D
  |\  /|
  |E\/ |
  | /\ |
 B|/__\|C

Steiner vertices are not necessary, but, nevertheless, 
are often introduced to improve the "quality" of a 
triangulation (one popular measure of quality is the minimum 
of the angles in the triangles - the larger this is the better; 
in other words skinny triangles with small angles are 
undesirable).