Graphics Primitives (2)
Outline
• Scan conversion
– OpenGL - Polygon setting
– Polygon Scan Conversion
– Filling algorithms
– Storage
– Triangle scan conversion
About polygons
• Convex and Concave polygons
An object is convex if and only if any line segment connecting two
points on its boundary is contained entirely within the object or one
of its boundaries.
OpenGL Fill-Area Attributes
- attributes: display style (a single color,
a specified fill pattern, or in a “hollow”
style)
OpenGL Fill-Area Attributes Functions
- Convex polygons
- Default: a solid-color region
- a fill pattern - a mask (bit array which relative positions are to
be displayed in a single selected color) - 32 × 32 bit mask
- To set the current fill pattern
glPolygonStipple (fillPattern)
Ex. GLubyte fillPattern [ ] = {0xff, 0x00, 0xff, 0x00, ... }
OpenGL Fill-Area Attributes Functions
GLubyte fillPattern [] = {
0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0xc0,
0x00, 0x00, 0x01, 0xf0,
0x00, 0x00, 0x07, 0xf0,
0x0f, 0x00, 0x1f, 0xe0,
……… }
OpenGL Fill-Area Attribute Functions
• Texture and Interpolation Patterns
– simulate the surface appearance of materials
• Interpolation - assign different colors to
polygon vertices
glShadeModel (GL_SMOOTH)
OpenGL Fill-Area Attribute Functions
• Wire-Frame Methods
– show only polygon edges - hollow display
glPolygonMode (face, displayMode);
face (GL_FRONT, GL_BACK, or GL_FRONT_AND_BACK)
displayMode (GL_LINE , GL_POINT , GL_FILL )
OpenGL Fill-Area Attribute Functions
• Front-Face Function
glFrontFace (vertexOrder)
vertexOrder (GL_CW or GL_CCW (default))
•
OpenGL Fill-Area Attribute Functions
• glBegin(GL_POLYGON)
• glBegin (GL_TRIANGLES)
• glBegin (GL_TRIANGLE_STRIP)
• glBegin (GL_TRIANGLE_FAN)
• glBegin (GL_QUADS)
• glBegin (GL_QUAD_STRIP)
•
OpenGL Fill-Area Attribute Functions
Polygon Filling Algorithms
• Inside-Outside tests (odd-even rule)
• Bounding box
• Seed fill algorithms
– Boundary fill algorithm
– Flood fill algorithms
Inside Test (odd-even Method)
• Draw any line to an
arbitrary point
• Count intersection
points
• Inside = odd count
• Outside = even count
• If a vertex is an
intersection point
(check the two adjacent
sides
Filling Algorithms
Boundary Fill Flood Fill
Bfill(int x, int y, int fc, int bc) Ffill(int x, int y, int fc, int oc)
{ int cc (current-color (x,y)) { int cc (current-color (x,y))
if((cc!=fc) && (cc!=bc)) if(cc==oc)
{ color(x,y,fc); { color(x,y,fc);
Bfill(x+1,y,fc,bc); Ffill(x+1,y,fc,oc);
Bfill(x-1,y,fc,bc); Ffill(x-1,y,fc,oc);
Bfill(x,y+1,fc,bc); Ffill(x,y+1,fc,oc);
Bfill(x,y-1,fc,bc); Ffill(x,y-1,fc,oc);
{ {
} }
Polygon Storage - Tables
• a surface shape usually defined as a mesh of
polygon covers
• data for each polygon is placed into tables
• data tables can be organized into two groups:
geometric tables and attribute tables
Polygon Storage - Tables
• Geometric data tables contain
– vertex coordinates and
– parameters to identify the spatial orientation of the
polygon surfaces
• Attribute information contain
– parameters specifying the degree of transparency,
reflectivity and texture characteristics
Polygon Storage - Tables
• Geometric data – three lists
– a vertex table,
– an edge table,
– a surface-facet table
Geometric data Tables
Geometric data Tables
Triangle Area Filling Algorithms
• Why do we care about triangles?
• Edge Equations
• Edge Walking
Do something easier!
• Instead of polygons, TRIANGLES! Why?
1) All polygons can
be broken into
triangles
2) Easy to specify
3) Always convex
4) Going to 3D is
MUCH easier
Polygons can be broken down
Triangulate - Dividing a
polygon into triangles.
Is it always possible?
Why?
Specifying a model
• For polygons, we had to worry about
connectivity AND vertices.
• How would you specify a triangle?
• Only vertices
(x1,y1) (x2,y2) (x3,y3)
– No ambiguity
– Line equations
A1x1+B1y1+C1=0 A2x2+B2y2+C2=0 A3x3+B3y3+C3=0
Scan Converting a Triangle
• Two main ways
to rasterize a
triangle
– Edge Equations
• A1x1+B1y1+C1=0
• A2x2+B2y2+C2=0
• A3x3+B3y3+C3=0
– Edge Walking
Types of Triangles
What determines the spans? Can you think of an easy way
to compute spans?
What is the special vertex here?
Edge Walking
• 1. Sort vertices in
y and then x P0
• 2. Determine the
middle vertex
• 3. Walk down
edges from P0 P1
• 4. Compute spans
P2
Edge Equations
P0
• A1x + B1y + C1=0
• A2x + B2y + C2=0
• A3x + B3y + C3=0
P1
P2
Edge Equations
• Orient edge equations so that their positive-half
spaces are in the triangle's interior
Edge Equations
• What does the edge equation P0
mean?
• A1x + B1y + C1=0
• P1[2,1], P0 [6,11]
• A=-10, B=4, C=16
• What is the value of the
equation for the:
– gray part
– yellow part
– the boundary line
• What happens when we
reverse P0 and P1? P1
Combining all edge equations
1) Determine edge equations P0
for all three edges
2) Find out if we should
reverse the edges
3) Create a bounding box P1
4) Test all pixels in the
bounding box whether they too P2
reside on the same side
Recap
P0
P0
P1 P1
P2
P2