Page 100 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Lab on Computer Graphics Kumar Vishal, Lovely Professional University

Notes Unit 6: Implementing Polygon Filling Algorithm

CONTENTS

Objectives
Introduction
6.1 Scan-line Fill Algorithm
6.1.1 Basic Scan-fill Algorithm
6.2 Boundary-fill Algorithm

6.3 Flood Fill Algorithm
6.4 Summary
6.5 Keywords
6.6 Review Questions

6.7 Further Readings
Objectives

After studying this unit, you will be able to:
• Understand the concept of scan-line fill algorithm

• Explain boundary-fill algorithm
• Discuss about flood fill algorithm

Introduction

A polygon is a closed planar path composed of a finite number of chronological line segments.
The straight line segments that make up the polygon are called its sides or edges and the points
where the sides meet are the polygon’s vertices. If a polygon is simple, then its sides (and
vertices) constitute the boundary of a polygonal region, and the term polygon sometimes also
describes the interior of the polygonal region (the open area that this path encloses) or the union
of both the region and its boundary. An important issue that arises when filling polygons is
that of deciding whether a particular point is interior or exterior to a polygon. A rule called the
odd-parity (or the odd-even rule) is usually applied to test whether a point is interior or not. A
half-line starting from the particular point and extending to infinity is drawn in any direction
such that no polygon vertex intersects with the line. The point is considered to be interior if the
number of intersections between the line and the polygon edges is odd.
Generation of solid areas from the simple edge of the vertex description is referred as solid
scan conversion or polygon filling or contour filling. Given the edges defining a polygon, and
a colour for the polygon, we need to fill all the pixels inside the polygon.

There are mainly three algorithms present for polygon filling:
1. Scan-line fill algorithm

2. Boundary-fill algorithm
3. Flood fill algorithm

94 LOVELY PROFESSIONAL UNIVERSITY