Explain the scan-line algorithm, Data Structure & Algorithms

Assignment Help:

Explain the Scan-Line Algorithm

This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of filling just one surface, we now deal with multiple surfaces. As each scan line is processed, all polygon surfaces intersecting that line are examined to determine which are visible. Across each scan line, depth calculations are made for each overlapping surface to determine which is nearest to the view plane. When the visible surface has been determined, the intensity value for that position is entered into the refresh buffer.

We assume that tables are set up for the various surfaces, which include both an edge table and a polygon table. The edge table contains coordinate end points for each line in the scene, the inverse slope of each line, and pointers into the polygon table to identify the surfaces bounded by each line. The polygon table contains coefficients of the plane equation for each surface, intensity information for the surfaces, and possibly pointers into the edge table. To facilitate the search for surfaces crossing a given scan line, we can set up an active list of edges from information in the edge table. This active list will contain only edges that cross the current scan line, sorted in order of increasing x. In addition, we define a flag for each surface that is set on or off to indicate whether a position along a scan line is inside or outside of the surface. Scan lines are processed from left to right. At the leftmost boundary of a surface, the surface flag is turned on; and at the rightmost boundary, it is turned off.  Figure 3.6 illustrates the scan-line method for locating visible portions of surface for pixel positions along the line. The active list for scan line 1 contains information from the edge table for edges AB and BC, only the flag for surface S1 is on. Therefore, no depth calculations are necessary, and intensity information for surface S1 is entered from the polygon table into the refresh buffer. Similarly, between edges EH and FG, only the flag for surface S2 is on. No other positions along scan line 1 intersect surfaces, so the intensity values in the other areas are set to the background intensity. The background \intensity can be loaded throughout the buffer in an initialization routine. 

For scan lines 2 and 3 in Figure, the active edge list contains edges AD, EH, BC, and FG. Along scan line 2 from edge AD to edge EH, only the flag for surface S1 is on. But between edges EH and BC, the flags for both surfaces are on. In this interval, depth calculations must be made using the plane coefficients for the two surfaces. For this example, the depth of surface S1 is assumed to be less than that of S2, so intensities for surface S1 are loaded into the refresh buffer until boundary BC is encountered. Then the flag for surface S1 goes off, and intensities for surface S2, so intensities for surface S1 are loaded into the refresh buffer until boundary BC is encountered. Then the flag for surface S1 goes off, and intensities for surface S2 are stored until edge FG is passed. 

We can take advantage of coherence along the scan lines as we pass from one scan line to the next. In Figure 3.6, scan line 3 has the same active list of edges as scan line 2. Since no changes have occurred in line intersections, it is unnecessary again to make depth calculations between edges EH and BC. The two surfaces must be in the same orientation as determined on scan line 2, so the intensities for surface S1 can be entered without further calculations.

 

688_data structure.png


Related Discussions:- Explain the scan-line algorithm

Merging, Merging two sequence using CREW merge

Merging two sequence using CREW merge

The space - time trade off, The Space - Time Trade Off The best algorit...

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic

Depth of complete binary tree, What will be depth do , of complete binary t...

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

Pipeling, Asktypes of pipelining question #Minimum 100 words accepted#

Asktypes of pipelining question #Minimum 100 words accepted#

Define different types of sparse matrix, Q1. Define a sparse matrix. Explai...

Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

Abstract data type-list, It is a useful tool for indicating the logical pro...

It is a useful tool for indicating the logical properties of data type. It is a collection of values & a set of operations on those values. Methodically, "a TYPE is a set, & elemen

#titlestrings, given the string "Data Structures & , Algorithms", write a p...

given the string "Data Structures & , Algorithms", write a program that uses sequential search to return index of ''&''

Draw a flowchart that takes temperatures input, Write an algorithm in form ...

Write an algorithm in form of a flowchart that takes temperatures input over a 100 day period (once per day) and outputs the number of days when temperature was below 20C and numbe

General, whats the definition of ADT and data type?

whats the definition of ADT and data type?

Define queue, A queue is a, FIFO (First In First Out) list.

A queue is a, FIFO (First In First Out) list.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd