haviland@emily.uvm.edu (tom haviland) (06/28/91)
I have a couple of polygon filling questions I wonder if anyone out
there has answers to.
What I'm trying to do is actually a hidden line removal problem, but the
things I'm trying to hide are polygons, all of which are in parallel
planes, and are unfilled. Essentially this breaks down into a polygon
filling problem; I need to know which polygons a point is inside of to
determine whether or not to draw that point. If any of the polygons
enclosing the point have a lower Z value, then don't draw.
All this is fine; I'm using an Active Edge Table algorithm to generate
a picture of the points (of all the polygons) to examine on each scan line.
Where I'm having problems is at the intersections of lines. In some cases
where two lines (in the same polygon) are moving towards an intersection they
merge on the screen like in this woefully inadequate diagram:
^
Lines Touch --> ||
||
| |
| |
In this case, the algorithm would not notice that two adjoining pixels
(note the algorithm can look only at one scan line at a time) of the
same polygon actually were different edges and would think any pixels
farther along were inside the polygon. So I changed the algorithm
to keep track of what edges pixels belong to, as well. In the above case
it would see that the adjacent pixels, while belonging to the same polygon,
were actually from different lines and would know that subsequent pixels
would not be enclosed by the polygon.
This is fine for the above case, but it falls apart in the case of two
lines coming together (somewhat) horizontally, like this:
| <---line A
|
|
X------------- <----line B
---------
X is the intersection of A and B
At point X,the same situation applies as above, so the program decides its
come out of the figure when actually it is just entering it.
The easy response seems to be, "well, don't draw the endpoint." This would
work in the above diagram, but look at this one:
----- A
---------
xxx
----------
----- B
x A and B intersect along last three points.
On this one, even if you don't draw the endpoint you'll end up with
two points for different lines in the same area. So...I'm stuck.
This seems to be a problem that would crop up in any generic polygon
filling algorithm (well, kind of; you wouldn't need to fill in areas
where lines merge since they're already filled, but you need to know when
you're in the polygon); but I can't find any information. All the books I've
seen just say, "well, just go along flipping your in and out states at
each pixel (or span of pixels) and you're all set!"
Any suggestions?
Tom
Thomas P. Haviland
University of Vermont
haviland@emily.uvm.edu (802)-656-2540
"Knowledge is no substitute for retractability"