следующий фpагмент (2)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
Msg : 86 of 100
From : anonlab4@gla.ac.uk 2:5030/315 23 Oct 95 15:53:06
To : All 26 Oct 95 05:04:38
Subj : http://www.uncg.edu/~kehoff/kenny/vrend/spanarr.html
--------------------------------------------------------------------------------
----------------------------------------------------------------------------
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)
|