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

What is keyed access- container, What is Keyed Access- Container A c...

What is Keyed Access- Container A collection may allow its elements to be accessed by keys. For instance, maps are unstructured containers which allows their elements to be

Relation of time and space complexities of an algorithm, What is complexity...

What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Advantages of dry running a flowchart, Advantages of dry running a flowchar...

Advantages of dry running a flowchart When dry running a flowchart it's advisable to draw up a trace table illustrating how variables change their values at every stage in the

Sorting algorithm, Sorting Algorithm A sorting algorithm is an algorit...

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

Data structures, 1.  You are required to hand in both a hard copy and an el...

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

Deletion of a node from a binary search tree, The algorithm to delete any n...

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

The smallest element of an array''s index, The smallest element of an array...

The smallest element of an array's index is called its Lower bound.

Implementation of queue, For a queue a physical analogy is a line at bookin...

For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr

Prime''z algorithem, Ask question #explain it beriflyMinimum 100 words acce...

Ask question #explain it beriflyMinimum 100 words accepted#

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