Splitting concave polygons

Computer Graphics- SCC 342
Chapter 4: Graphics Output
Dr. Doaa Hegazy
2D Graphics Primitives
• Graphics drawing is based on basic geometric
structures called graphics primitives
– Points
– Lines
– Circles
– Conic Sections
4.1 Coordinate Reference Frames
• To describe a picture, first decide upon a
convenient Cartesian coordinate system,
called the world-coordinate reference frame
• WCR can be 2D or 3D
• Objects in pictures described by:
– positions in world coordinates
– Color
– coordinate extents = the minimum and maximum
x, y, and z values for each object
4.1 Coordinate Reference Frames
Screen Coordinates
• Locations on a video monitor are referenced in
integer screen coordinates, which correspond to
the pixel positions in the frame buffer
• Pixel coordinate values give the scan line number
(the y value) and the column number (the x value
along a scan line)
• Scan-line algorithms for the graphics primitives
use the defining coordinate descriptions to
determine the locations of pixels that are to be
4.1 Coordinate Reference Frames
Screen Coordinates
• For the present, we assume that each integer
screen position references the center of a
pixel area
4.1 Coordinate Reference Frames
Absolute and Relative Coordinate Specifications
• Absolute coordinate values: the values
specified are the actual positions within the
coordinate system in use
• Relative coordinates: we can specify a
coordinate position as an offset from the last
position that was referenced (called the
current position)
4.6 File Area Primitives
• Another useful component beside geometric objects
is describing an area with filled color
• Referred to as fill area or filled area
• Most graphics routins require the fill area to
specified as polygon
- their boundries are described by linear equations.
- most surface can be approximated by polygons
(called surface tessellation)
4.7 Polygon Fill Area
• Polygons: plane figure specified by three or more vertices
and connected by edges
• Has all vertices within plane- no edge crossing
• Polygon classification:
- Convex: interior angle = or less than 180 degrees
- Concave: interior angle greater than 180 degrees
• Implementations for filling algorithms are complicated
for concave polygons
4.7 Polygon Fill Area
Identifying concave polygons
- extension of some edges will intersect
other edges
- take a look at the polygon vertex positions
relative to the extension line of any edge:
some vertices are on one side and some are
on the other
4.7 Polygon Fill Area
Splitting concave polygons
- Split concave
polygons into a set
of convex polygons
- Using edge vectors
and edge cross
- Use vertex position
relative to edge
extension line.
4.7 Polygon Fill Area
Splitting concave polygons
• Assume all polygons in xy plane
• Ek = Vk+1 – Vk
• Calculate cross product of successive edge
- if at least z component of one vector is
negative, then concave polygon.
- no successive vertices are collinear.
• Split along the line of the first edge vector in
the cross product pair.
4.7 Polygon Fill Area
Splitting concave polygons
4.7 Polygon Fill Area
Splitting concave polygons
4.7 Polygon Fill Area
Splitting concave polygons
• Another method is a rotational method
4.7 Polygon Fill Area
Splitting convex polygons into triangle
- define any sequence of three consecutive
vertices to a triangle.
- delete middle vertex from the original list
- continue forming triangle
- stop when only three vertices are
4.7 Polygon Fill Area
Inside-Outside test
• Also called odd-even test
4.7 Polygon Fill Area
Winding-Number test
• Count counterclockwise encirclements of
4.7 Polygon Fill Area
Polygon tables
• objects in a scene are described as sets of
polygon surface facets
• Object description includes:
- Coordinate information (geometry for the polygon
- Surface parameters(color, transparency, and
light-reflection properties)
• Object information are organized in tables.
4.7 Polygon Fill Area
Polygon tables
4.7 Polygon Fill Area
Polygon tables
• Important for check for consistency and
1. each pixel is an end point for at least two
2. every edge is part of at least one polygon
3. every polygon is closed
4. each polygon has at least one shared edge

similar documents