Scribd
Upload
20 views12 pages

Scan Line Method for Polygon Filling

The Scan Line Method is a polygon filling algorithm in computer graphics that identifies and fills pixels inside a polygon by scanning horizontal lines across the screen. It utilizes an Edge Table (ET) and an Active Edge Table (AET) to efficiently manage polygon edges and intersections. This method is favored for its efficiency, ease of implementation, and good visual quality, though it can be complex for self-intersecting polygons.

Uploaded by

priyanshu sharma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
20 views12 pages

Scan Line Method for Polygon Filling

The Scan Line Method is a polygon filling algorithm in computer graphics that identifies and fills pixels inside a polygon by scanning horizontal lines across the screen. It utilizes an Edge Table (ET) and an Active Edge Table (AET) to efficiently manage polygon edges and intersections. This method is favored for its efficiency, ease of implementation, and good visual quality, though it can be complex for self-intersecting polygons.

Uploaded by

priyanshu sharma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

SCAN LINE METHOD IN COMPUTER GRAPHICS

AND VISION

By – Kirti Rohilla
231345036
BCA CC ‘5th’
INTRODUCTION

• The Scan Line Method is a polygon filling


algorithm used in computer graphics.
• It determines which pixels lie inside a polygon
and fills them with color.
• It works by scanning each line (scan line)
across the screen and identifying intersection
points with polygon edges.
BASIC CONCEPT

• Imagine drawing horizontal lines (scan lines)


across a polygon.
• Each line cuts through polygon edges at two or
more points.
• When a scan line crosses the shape, we fill the
pixels that fall inside it — between the points
where the line enters and exits the shape
STEPS IN THE SCAN LINE
ALGORITHM

1. Identify the y-coordinate range of the polygon.


2. For each scan line:
- Find intersections with polygon edges.
- Sort intersection points by x-coordinate(arrange
them from left to right (in order of x)).
- Fill pixels between alternate pairs of intersections.
3. Repeat until all scan lines are processed (You keep
moving upward to the next y-value and repeat this process for every
horizontal line until you reach the top of the polygon).
EQUATION USED IN SCAN LINE
METHOD

• To find the intersection of a scan line (horizontal


line at y) with an edge between (x1, y1) and
(x2, y2):

• Intersection X-coordinate:
• x = x1 + (y - y1) * (x2 - x1) / (y2 - y1)

• This equation helps determine where each scan


line cuts the polygon edges.
EDGE TABLE (ET) AND ACTIVE
EDGE TABLE (AET)

• The Scan Line Method uses two important data structures:

• 1. Edge Table (ET):


• - Stores edges grouped by their minimum y-value.
• - Helps quickly identify which edges become active on each scan line.

• 2. Active Edge Table (AET):


• - Contains edges currently intersecting the scan line.
• - Updated for every scan line as edges enter or leave.

• Together, ET and AET make polygon filling faster and more organized.
EXAMPLE

• Example polygon vertices: (10,10), (30,10),


(25,25), (15,25)

• Scan line at y=12 intersects edges at x=12


and x=28 → fill pixels (12–28).
• Scan line at y=20 intersects edges at x=15
and x=25 → fill pixels (15–25).
ADVANTAGES

✅ Efficient for convex and concave polygons


✅ Works line-by-line — saves time and memory
✅ Easy to implement in raster graphics
✅ Good visual quality for polygon filling
DISADVANTAGES

❌ More complex when polygons are self-


intersecting
❌ Needs handling for shared edges and vertices
❌ Floating-point rounding errors can cause gaps
or overlaps
APPLICATIONS

• Used in 2D graphics rendering


• Game design and animation
• CAD systems for surface filling
• Rasterization in computer graphics pipeline
COMPARISON

• Method | Description | Efficiency


• Flood Fill | Fills connected region from a seed
point | Slower
• Boundary Fill | Fills area bounded by color
border | Medium
• Scan Line Fill | Fills polygon line by line | Fastest
CONCLUSION

• The Scan Line Method is one of the most


efficient polygon-filling algorithms.
• It’s widely used due to its accuracy, simplicity,
and performance in raster graphics.

You might also like