| |
munkey
Account closed
Registered: Aug 2009
Posts: 12 |
Convex Polygon Drawing / EOR Filling
Hey everybody. Just a heads up this is my first post on this forum so hopefully I haven't tripped over any "etiquette" faux-pas.
I'm madly trying to get a demo finished in the next few weeks for Syntax 2010. I've written a reasonable EOR filler, but just nutting out the line-drawing side. I don't have an issue with line-drawing per-se, however I'm having trouble drawing convex polygons in such a way so as to allow the EOR filler to correctly fill them.
Initially, I've been treating each edge in isolation and EOR-drawing it to the bitplane. This doesn't seem to work (filler-wise) for all polygon cases so I've had to rethink my approach.
I've been doing lots of web-searches on the topic but haven't come across anything concrete. I'm guessing I need to treat all convex polygons in isolation when drawing them.
My current implementation "theory" involves 3-vertex polygons, wherein if a vertex does not share a y-coordinate with any other vertex in the polyon, then that vertex must not be drawn (obviously the edge connecting it to other vertices will require drawing). The reasoning behind this is that if a single pixel sits atop a triangle, it will cause the filler to draw a line past it.
I'll try to draw an ASCII diagram and hope to hell the formatting isn't screwed up ;)
V0
|\
|.\
|..\
|../V1
|./
|/
V3
So if verticies V0 and V3 are drawn to the bitmap, the EOR filler will proceed to draw a horizontal line starting at (V0x,V0y) and ending at (screen_width-1, V0y) -- and respectively for V3.
In my postulated implementation:
1. EOR-draw all lines/edges in clockwise order (being sure not to draw the last point of each edge)
2. sort triangle verticies in y
3. if top-most vertex does not share its y position with another vertex then EOR that point (erase it from bitmap)
4. if bottom-most vertex does not share its y position with another vertext then EOR that point (erase it from bitmap)
I haven't tested this out yet so not sure if it will completely work (all triangle cases). I don't like it very much because it's quite messy.
Am I even on the right track with this? Any assistance would be appreciated. |
|
| |
munkey
Account closed
Registered: Aug 2009
Posts: 12 |
Well I can now confirm that the above algorithm works. I'm wondering if anybody can offer a nicer solution? |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
"wherein if a vertex does not share a y-coordinate with any other vertex in the polyon, then that vertex must not be drawn "
I dont get it. Generally you DONT draw vertices, but only "edges", and vertical ones are special case where you only plot top & bottom. Also you can handle each "edge" without caring how they are connected, just do it as you described: dont plot leftmost or rightmost pixels (but dont let this change the line slope etc!). If you still have fill problems, then its not the line drawer, or eor filler.
(edit: well it may be a buggy line drawer, but even if the slopes are off a bit, if you get the pixels horizontally right, it should work) |
| |
munkey
Account closed
Registered: Aug 2009
Posts: 12 |
Quoting Oswald
I dont get it. Generally you DONT draw vertices, but only "edges", and vertical ones are special case where you only plot top & bottom. Also you can handle each "edge" without caring how they are connected, just do it as you described: dont plot leftmost or rightmost pixels (but dont let this change the line slope etc!).
Of course I'm only plotting edges, however consider the problem that I illustrated above--a simple triange with verticies V0, V1, V3 (actually, that's meant to be V2 and not V3, but to be consistent with the diagram I'll stick with V3).
Using your suggested method of "don't plot left-most or right-most pixels" I'll draw that polygon. I'll select the "don't plot the right-most pixel" algorithmic option:
Startint at V0:
* edge V0->V1: pixel at V0 is plotted, along with the rest of the edge to V1 (not including pixel at V1).
* edge V1->V3: pixel at V1 is plotted, along with the rest of the edge to V3 (not including pixel at V3)
* edge V3->V0: pixel at V3 is plotted, along with the rest of the edge to V0 (not including pixel at V0)
So what results is a series of 3 edges/lines with a single pixel sitting at V0 and V3. When the EOR-filler (which runs left-right and top-bottom fill) sees each of these single pixels sitting along on a screen row it fills from this pixel to the right-hand edge of the screen.
I don't understand how your suggested solution solves this case. I would love it if this is simply a bug with my line drawer. Would you please elaborate? |
| |
munkey
Account closed
Registered: Aug 2009
Posts: 12 |
Quoting Oswald
but only "edges", and vertical ones are special case where you only plot top & bottom.
This comment of yours has thrown me. I guess I don't understand to which fill algorithm you are referring?
I would have thought you actually meant to say:
Quote:"horizontal ones are special cases where you only plot left and right"
I'm sure that you did mean what you said above, however it's got me quite confused. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
maybe you are coming from the amiga ? on the c64 you eorfill from top to bottom, byte by byte 4 multicolor pixels at a time. so, vertical lines are special cases. |
| |
munkey
Account closed
Registered: Aug 2009
Posts: 12 |
Quoting Oswaldmaybe you are coming from the amiga ? on the c64 you eorfill from top to bottom, byte by byte 4 multicolor pixels at a time. so, vertical lines are special cases.
Yes I am thinking about filling within the context of an Amiga ;)
I still don't understand how your suggested algorithm deals with the case outlined above though. |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
Not sure what the problem is, but remember to eor the lines and avoid drawing the left- or rightmost pixel, which means vertical lines should be skipped. |
| |
munkey
Account closed
Registered: Aug 2009
Posts: 12 |
Quoting CruzerNot sure what the problem is, but remember to eor the lines and avoid drawing the left- or rightmost pixel, which means vertical lines should be skipped.
Thanks guys. I've run a few test cases on paper and it makes sense. For a start I've been thinking about it in the context of a horizontal filler (Amiga-like), so I've had to modify the "left-to-right" rule to "top-to-bottom".
I actually took "left-to-right" to mean traverse the vertex list from left to right (i.e. clockwise or anticlockwise order), as opposed to literally always drawing edges from the left-most vertex to right-most vertex. Works on paper :) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
it doesnt matter in what order you draw the edges, and yes it would help if you could tell what exactly is the problem. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
A normal line drawing routine would draw x1 <= xp <= x2 which will cause EOR filling bugs.
For EOR filling, draw the pixels x1 <= xp < x2.
|
... 1 post hidden. Click here to view all posts....
|
| Previous - 1 | 2 - Next |
