Frequently Asked Questions
| demo party ex- | infused bytes e-mag | ib/news | | | win koi lat

p (2)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 86 of 100 From : 2:5030/315 23 Oct 95 15:53:06 To : All 26 Oct 95 05:04:38 Subj : -------------------------------------------------------------------------------- ---------------------------------------------------------------------------- The SpanArray as a Solution for Polygon Rasterization and Hidden Surface Removal The goal of this paper is to brainstorm on a fast scanline rasterization method that can be expanded to fully generalized hidden surface removal allowing for protruding and cyclically- overlapping polygon faces without having to calculate scanline- edge intersections. designed, written, and implemented by Kenny Hoff September 20, 1995 ---------------------------------------------------------------------------- The traditional method for rasterizing a polygon into a framebuffer involved filling the polygon one horizontal line at a time by calculating runs or spans of pixels formed by the intersections of the current scanline with the edges in the polygon face. This usually requires a great deal of redundant computation, since each edge must be checked for intersections for each new scanline. Various methods have been introduced to make this method more efficient by creating an active edge list that keeps track of the current edges that intersect with the current scanline (often the intersections are computed incrementally from the previous scanline-s intersections). This method, while much more efficient, is quite a bit more complicated and thus more difficult to optimize. We would like to be able to rasterize all edges of the polygon faces without having to worry about calculating scanline intersections and maintaining active edge lists; thus we come to what I call a SpanArray. The SpanArray structure is basically an array containing a list of spans for each scanline in the framebuffer. All edges for each polygon face can be rasterized in any order and put into this structure in such a way that after all polygons have been rasterized, the SpanArray can be easily rendered into the framebuffer. How? As each edge is rasterized, the framebuffer coordinates of all of the points along that edge will be found; so instead of having to calculate intersections with scanlines we can simply put these points in the appropriate intersection or span list corresponding to the y-values of the points. For example, say that we are given a triangle with vertices (2,1), (6,5), and (2,5), we can begin by rasterizing the edge with endpoints (2,1) and (6,5), the first point will be (2,1) so we can insert a 1 into the SpanArray span list at location 1, the subsequent points will be (3,2), (4,3), (5,4), and (6,5); all of these points will be inserted into the SpanArray as follows: SpanArray: [0] --> NULL [1] --> [2] -> NULL [2] --> [3] -> NULL [3] --> [4] -> NULL [4] --> [5] -> NULL [5] --> NULL [7] --> NULL [NumScanlinesInFrameBuffer-1] --> NULL It should be obvious that we skipped the last point. Why? Before we continue to add more edges, we must be careful in rasterizing the edges so that we can always maintain an even number of values in each span list (this will be the case for all closed polygons, if handled properly). This is necessary because the spans are defined as pairs of entries in each span list. An easy fix that will result in geometrically correct polygons is to rasterize all edges from the start point up to, but not including, the end point. Also, the spans will be filled from the left point up to, but not including, the right point. In addition, this will give correct looking polygons without overlapping polygon faces that share edges. Let-s continue on to the next edge in the triangle with endpoints (6,5) and (2,5). We will simply skip this one since it is horizontal (y values are the same). Any guesses as to why? Since this is a horizontal scanline approach to rasterization, horizontal edges will be filled since the nonhorizontal edges adjacent to the horizontal edges share the same endpoints and will end up filling this row anyway. Make sense? So one more rule to our edge rasterization: skip horizontal edges. Now finally, the last edge with endpoints (2,5) and (2,1). If we rasterize this edge, we will obtain points (2,1), (2,2), (2,3), (2,4), and (2,5). The last point (which will always have the largest y-value for the edge; must sort in y before rasterizing) must again be skipped and the remaining points can be added into the SpanArray: SpanArray: [0] --> NULL [1] --> [2] -> [2] -> NULL [2] --> [3] -> [2] -> NULL [3] --> [4] -> [2] -> NULL [4] --> [5] -> [2] -> NULL [5] --> NULL [7] --> NULL [NumScanlinesInFrameBuffer-1] --> NULL We have rasterized all of the edges of the triangle, so now we are almost ready to render the spans into the framebuffer. First we must sort the span lists in ascending order by the x-values: SpanArray: [0] --> NULL [1] --> [2] -> [2] -> NULL [2] --> [2] -> [3] -> NULL [3] --> [2] -> [4] -> NULL [4] --> [2] -> [5] -> NULL [5] --> NULL [7] --> NULL [NumScanlinesInFrameBuffer-1] --> NULL Now we can simply fill in the spans for each scanline defined by pairing the intersections stored in the SpanArray. So we have the following spans: for y=1, [2, 2); for y=2, [2,3); for y=3, [2,4); for y=4, [2,5). Notice that the intervals are closed on the left, but open on the right; remember, we must also skip the last point when filling the spans. So in this example, we will end up with a very coarse rasterized description of this triangle that will look like this when rendered into the framebuffer: 0 1 2 3 4 5 2 X 3 X X 4 X X X What happened to point (2,1)? Since it had to fill across from 2 to 2-1, it was completely skipped. It can easily be debated whether or not this point should be plotted; it probably should, but it is easier to skip it than to waste computations in determining and correcting for this case. So what now? Provided that we follow a few simple rules of edge rasterization, we have designed a complete polygon rasterizer that will work for all types of polygons, including convex, concave, self-intersecting, and ones with holes. The rules for rasterization can be summarized as follows: sort endpoints from smallest y-value to largest y-value, rasterize from startY to endY-1 inserting these points into the SpanArray, sort the span arrays for each scanline in ascending order by x-values, fill the spans defined by pairs of intersections in the span lists from the leftX to rightX-1. This is pretty simple and VERY fast, but how can this be used to solve the problem of hidden surface removal with interacting polygon-based models? This SpanArray seems to only work for one polygon face at a time; right now, this is true since the rasterized points must be sorted by x-values for each polygon face separately or we may create spans between different faces that are not there (take the case of overlapping triangles). However, if we modify the SpanArray just a little bit, we can rasterize all polygon faces in all of the polymodels into one SpanArray, and then the entire world can be rendered into the Framebuffer. We can apply a scanline Zbuffered approach to rendering the list of spans for each scanline. We must modify the SpanArray so that it will not only contain the spans for one polygon face, but for all polygon faces in the world model. Since each SpanArray element contains a linked list for the spans of a polygon face for a particular scanline, we can modify this list to instead be a list of span lists, one for each polygon face: SpanArray: [0] -> [Polygon1-s Spans] -> [Polygon2-s Spans] -> NULL | | V V [x1] [x1] | | V V [x2] [x2] | | V V [x3] [x3] | | V V [x4] [x4] | | V V NULL NULL So now element [0] of the SpanArray corresponds to two lists of spans for scanline y=0, one for Polygon1 and one for Polygon2; both of these polygons have four intersections with scanline y=0 (or two spans when paired). So now before a new polygon face is rasterized, a new polygon span list must be added to the span array to group the polygon-s spans together. It would be very inefficient to simply add a new span list to every entry in the SpanArray, so we should only add a list to a particular SpanArray when a particular scanline is intersected. So an array of flags (one for each SpanArray element or one for each scanline in the framebuffer) indicating when a new span list has been started can be used to determine when to create a new span list for the current raster point or when to just simply add to the list that is already present. After all of the polygons have been rasterized, each polygon span list must be sorted by the x-values. Now the SpanArray can hold all of the spans from all polygon faces for each scanline. If we simply store a pseudo-depth z- value for each span endpoint in addition to the x-value, we can perform a depth or visibility comparison with all of the spans along a particular scanline while rendering the SpanArray into the framebuffer. How? By using a scanline Zbuffer. This Zbuffer will be an array that can hold rasterized points for each horizontal pixel in the framebuffer for a scanline. Each span can be rendered into this Zbuffer first, while comparing current depth-values; if the new spans points are closer, then overwrite the existing values. This is done on a span point-by-point basis. The Zbuffer should be initialized for the deepest possible values for each new scanline, so that as each span is rendered, each point can be compared to the value already in the Zbuffer. This will effectively perform a pixel-by-pixel depth-comparison for the entire world model one scanline at a time. Naturally, in addition to the pseudo-depth z-value and the x- value stored in each span endpoint, we must have some information about the color of the pixels in the span (there could also be shading and texture-mapping info present). There are a lot of details left out of this brainstorm, but this should give a clear idea of how to utilize a SpanArray as a central hub for a Zbuffered renderer.

1 p(/) |p p (1)

FAQ - .

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,