Computer Graphics (CS4300) 2011S: Lecture 8

Today

• rectangles in 2D
• polygons in 2D
• tessellation by ear-clipping

Rectangles in 2D

• axis-aligned rectangles are very common in 2D graphics, especially GUIs
  • typically represented as a point giving the upper left corner (i.e. the corner with minimum and coordinates) plus (non-negative) width and height (horizontal and vertical extents, respectively)
    
  • often are all integers (pixel coords) but some APIs allow floating point rects as well
  • easy to check if a given point is in a rect: and
  • two axis-aligned rects and overlap iff
    • and and
    • and
    • diagram:
      
  • also easy to rasterize, e.g.
    • for to
      • for to
        • turn on pixel
• non-aligned rectangles are less common
  • can treat as an axis-aligned in a rotated coordinate system (we will cover rotations in detail soon)
  • or, just don’t special-case, and handle like any other convex polygon

Polygons in 2D

• def: a simple polygon in 2D is an ordered sequence of line segments , , such that
  • each edge is the segment from a start vertex to an end vertex
  • for
  • 
  • non-adjacent edges do not intersect
  • the only intersection of adjacent edges is at their shared vertex
• note that it is sufficient to store e.g. only the start vertices, and this also enforces the connectivity constraints by construction
• this also illustrates that the number of sides equals the number of vertices
• the polygon degenerates to a segment if (it’s also possible to have degenerate polygons for )
• nomenclature: sometimes even an open chain of segments is called a polygon
• definition of inside is intuitive for a simple polygon
• how to check if a point is inside a simple polygon?
• a polygon is convex if, for any two points and both inside the polygon, all points along the segment from to are also inside the polygon
• have already covered point-in-polygon test for convex simple polygons: e.g. consider the edges in counter-clockwise order (this is conventional) and then check if is on or to the left of every edge
• for non-convex polygons, one solution is to tessellate: break the polygon into a set of convex pieces, and then check each piece separately (will cover this later)
• it is also possible (and classical) to perform insideness checks without tessellating
  • two common conventions: “even-odd” rule, and “nonzero” (aka “winding”) rule
  • in each case, construct a ray in an arbitrary direction from the test point
  • even-odd rule
    • count number of intersections of with the polygon. is defined to be inside the poly if the intersection count is odd.
    • reasoning: each time an edge is crossed, either switch from inside to outside or outside to inside
    • but since poly is closed, know that ray must end up outside
  • nonzero rule
    • again compute all intersections of with the poly edges , but this time keep track of whether the edge crossed from left to right (i.e. on left side of and on right side of ) or right to left
    • count +1 for left-to-right and –1 for right-to-left
    • is defined to be inside the poly if and only if (iff) final count is nonzero
    • reasoning: consider sweeping a point along the perimeter of the poly
    • take the integral of the orientation angle of the line segment from to
      
    • turns out that, for one complete sweep of the polygon, the integrated winding angle will be an integer multiple of
    • intuition: reasonable definition of inside-ness is to check if the poly “circled around” in CCW direction different number times than in CW direction
    • nonzero intersection test turns out to be a shortcut to compute (proof is a little subtle and we will not cover it)
  • these two rules can produce different results!
    
    
  • note that nonzero rule requires external boundary of poly to be in opposite winding order than holes (e.g. CCW for outside, CW for holes)
  • no clear “winner”, simply a matter of choice
  • some APIs only implement one rule or the other
  • Both rules can run into problems if intersects polygon right on a vertex. In that case, just start over with a different . A random choice of (remember, any ray will do) will not touch any vertex “with probability 1” (in continuous coords; “with high probability” in discrete coords, like floating point or integer).
• to rasterize a convex simple polygon, one general approach is
  • for to
    • for to
      • turn on pixel
• the details of figuring out the top, bottom, and horizontal extent of the poly at each line can be worked out, even in extensions to non-convex and non-simple polys (using either even-odd or nonzero fill rule)
• we will not cover the details, because in practice, it is becoming less common to rasterize polygons in this way
• instead, most systems are now simply tessellating the polygon into triangles (even if convex) and then rasterizing the triangles
• we will cover tessellation into triangles later today, and rasterizing triangles next time
• what about non-simple polygons?
  • the edges may self-intersect
  • there may be holes
  • there may be degenerate components
  • these complicate both point-in-polygon testing and rasterization algorithms
  • in practice, self-intersecting polys don’t seem to have many important uses
  • but still generally good to be able to handle them, because e.g. a poly may accidentally become self-intersecting due e.g. to numerical imprecision
  • or user may simply draw a self-intersecting poly
  • holes are sometimes useful: consider drawing a picture of a donut!
  • how to even define “inside-ness” for a non-simple polygon?
    • even-odd and nonzero rules still can be applied, and in this case can be considered definitional

Tesselation

• in general, tessellation is the process of dividing an arbitrary polygon into a disjoint union of smaller polys
• most common case in practice is to tessellate into triangles because
  • triangles are the simplest non-degenerate polygon
  • triangles are always convex
• tessellation into triangles is specifically called triangulation
• fact: any simple polygon with sides can always be tessellated into exactly triangles
• this is minimal, though it is also possible to use more triangles
• easy to see for convex simply polys
  • pick any arbitrary vertex
  • draw diagonals from to all other vertices
  • done!
  • number of diagonals will always be
  • there will be one triangle per diagonal, plus “the last one”
  • the resulting array of triangles can be efficiently stored as a triangle fan, which we will discuss in more detail next time
• in fact, even non-convex simple polys can be tessellated into triangles, but a more involved algorithm is required
• extensions also exist for non-simple polys, but we will not cover them
• what is the computational complexity of triangluating a simple polygon?
  • note that a lower bound is , because at least triangles must be produced
  • in 1991, Chazelle demonstrated an algorithm, but it’s complex and not typically implemented
  • reasonably simple algorithms exist, and are used in practice
  • a randomized alg that is probabilistically is also often used
• we will study a particularly simple algorithm called ear clipping that is
  • hence, not optimal, but can still be reasonably fast in practice for polys with relatively few vertices
• We have already defined “convexity” in terms of a whole polygon. We can also say that an individual vertex is convex if the internal angle at that vertex is less than radians; otherwise it’s convcave or reflex.
• an ear is a sequence of three consecutive vertices , , where
  • is convex and
  • the triangle formed by the three vertices includes no other vertex
• terminology: the segment from to is a diagonal of the polygon, and the vertex is the ear tip
• fact: a poly with always has at least two ears
• basic idea:
  • while
    • find an ear and cut it off!
• naive implementation is
  • : until remaining polygon is a triangle
    • : check each sequence of three consecutive vertices
      • : check if every other vertex is outside the candidate ear
• note that the resulting triangulation will have exactly triangles, because each time an ear is cut off one triangle is produced and one vertex is consumed
• a faster implementation is also relatively simple
  • : label all original vertices as either convex or reflex
  • : find all ear tips of the original poly by checking for each convex vertex whether any reflex vertex is inside the corresponding candidate ear
  • : repeat until
    • using e.g. linked list datastructures: cut off the first currently known ear , ,
    • “repair” the datastructures for the adjacent vertices and
      • if vertex was convex, then it is still convex
      • if vertex was reflex, it may become convex
      • : each adjacent vertex that ends up convex needs to be (re-)tested for “ear-tip-ness”, again by checking if any reflex vertex is inside the ear
  • example
    
• writing a fast, small, portable, and general triangulation library is apparently a tall order
• almost like writing a good image compression/decompression library
• in practice, a number of algorithms exist, with licenses ranging from public domain to proprietary
• see e.g. here for an account many commonly available libraries and their advantages and disadvantages

Next Time

• reading on website
• triangle meshes
• barycentric coordinates
• rasterizing triangles

this page subject to change  |  last updated Sat Jun 25 11:33:47 EDT 2011  |  course homepage