kirk@media.uucp (Kirk Marple) (04/12/91)
After much headscratching and discussion, a basic problem with the
spanning scanline algorithm as presented in the Rogers' Procedural
Elements for CG has appeared. The algorithm, without dealing with
intersecting polygons, seems to have an ambiguity in picking edges
which make up the span left and right boundaries. This comes to play
when the edges (the vertices at the edges' endpoints, actually) are
used for shading.
Basically, the problem lies in selecting the next edge to use from the
active edge list, where multiple edges have the same x-min value.
The edge on the right side of the span will be at the correct x location,
but could be from a polygon that is not active.
Here's an example which (hopefully) explains the problem:
Case: three polygons (labeled 1, 2, 3)
all parallel to the x, y plane
all made up of four edges
polygon 1
| __ this is actually two edges,
| / the right edge from polygon 1,
y-axis | | and the left edge from polygon 2
/ \ / |/
| _____________ -------------------\ x-axis
| | | | |
| | | | |
| |- - -| |<- polygon 2 | *- - -* <- polygon 3
| | | | | /--- (two points at same x)
---------------------- scanline i | |/
| | | | | *- - -**- - -* <- polygons 1, 2
| |_____|_____| | /\
| | | | |__ these are the points on the
| | | <- polygon 3 | vertical edges at the scanline
| |_____| (behind) \
-------------------/ z-axis (this is the x-z plane
10 20 30 x-axis that slices thru at scanline i)
OK, now that's clear (?!), let's look at the edge list at an arbitrary
scanline, called i.
xmin polygon
-----------------
0 none <--- spanleft at start is at 0 with no polygon
10 3
10 1 all edges have been put on in no special order
20 3
20 2
20 1
30 2
Here goes with the walkthrough of the active edge list.
SpanLeft SpanRight Active Processing
polygons done inside
at end of loop loop
-------- --------- -------------- ----------
0 10 3 no polygons active, so
background color is drawn for
span [0, 10], then polygon 3 becomes
active.
10 10 1,3 now we see a coexistant edge at
x = 10, where there are two edges,
one from polygon 1 and one from 3.
since the spanleft and spanright
are equal, no span is drawn
now polygons 1 & 3 are active
10 20 1 next edge is at x = 20, and edge is
from polygon 3. since more than one
polygon is active, the active polygon
which is greater in z at spanleft
is found, which is polygon 1.
Span should be drawn [10, 20],
but here is problem. The last edge
(which gave us the x = 10 span left)
is from polygon 1, and the current edge
is from polygon 3. although the
span left and right coordinates are
correct, when I go shade this span
need to know the edges which bound the
span, to get the vertex intensities.
depending on how the coexistant edges
lie in order, the edge used for the
span right could vary randomly.
I'll stop walking through now, because, hopefully, this clearly
explains the problem.
Any and all suggestions for correct methods of selecting the edges from the
active edge list are very welcome.
Some ideas I've had for solutions consist of methods for popping
the coexistant edge whose polygon matches the last edge's polygon
to the current edge's position and using it for the shading.
This works for a few cases but doesn't completely solve the problems.
--
Kirk Marple - Media Cybernetics Phone: (301)495-3305
Internet: kirk%media@uunet.uu.net UUCP: {uunet,hqda-ai}!media!kirk