Thinking aloud on polygon filling
I've not actually done any coding on my Sam 3d experiments in a while,
but I have been thinking a lot about the best way to implement polygon
filling. I had a polygon filler working in a much earlier version of
my code (see, e.g. http://uk.youtube.com/watch?v=kr_Lz98qVjE from
about 0:39) but it only did triangles, didn't clip and generally
wasn't really up to snuff in several ways that hit the frame rate.
Anyway, I've been playing around with a few ideas and was wondering if
someone with a more instinctive grasp for this sort of thing might
help out.
I previously tried using a span buffer. Each pixel span (i.e. a
horizontal line of pixels) was inserted into a linear list of existing
spans for that scan line, by clipping it against the spans that were
already there then shuffling things around in memory. So there was a
binary search and then often a small LDIR. The entire frame was drawn
at the end. I even tried a system whereby each span list was compared
with the previous span list and only the differences were plotted.
That was much faster than just dumbly drawing the whole list, but
slower than just plotting the spans to the screen and not doing the
list search and insert. Furthermore, as you add more polygons to the
scene, the insert gets more expensive very quickly.
Idea 1 is to divide the screen into 8×8 blocks, keep an overview that
tags each as either block filled with a certain colour or messy. The
polygon filler tags as many blocks as possible as completely filled,
and consults & modifies a 1 bit mask for each run of 8 pixels in a
messy block. So searching the existing structures for each individual
container is faster because it's O(1), and you're doing exactly as
much searching as you were for a 64×64 rectangle, then maybe less or
maybe more depending on the relative dimensions. As there are only 256
possible masks for each 8 pixel messy area, you can easily write 256
separate functions for that part of the insert (or have a program
generate them). But you need to do some extra work to figure out how
the polygon maps to each 8×8 block, whereas you need to know where it
starts and ends in each scan line regardless. You're potentially
keeping a 1 bit version of the entire display as well as the real
screen, but that neatly fits onto the end of each screen's 32 kb page,
conveniently ending exactly before the start position of my
multiplication tables. Of course, messy areas are directly plotted to
the display as they are drawn, solid colour blocks are drawn in a
separate pass at the end, and not redrawn if they were the same colour
in the preceding frame.
Idea 2 is a closer modification of what I had. During the normal draw
phase, spans are stored to a buffer, but this time in no particular
order. At the end of frame, the spans are sorted and mutually clipped
through the creation of a binary tree. Possibly the tree is serialised
and compared to the previous span list at the end, to reduce overall
drawing. So searching costs the same as it did, but inserts are
cheaper and their costs grow much less quickly. Building the tree scan
line by scan line at the end means I can throw 32 kb or whatever at
the tree for each separate scan line (since the contents aren't
interesting after it has either been drawn or serialised).
Idea 3 is a brute-force memory bashing version of the original. Each
scan line is now represented by 512 bytes of memory. That amounts to
two bytes associated with each screen pixel. If a span starts in that
pixel then its end location and colour are stored. So searching is
linear, but inserting is as cheap as can be. Some sort of bucket
system could be implemented, e.g. not allowing any scan line to pass
the next 32 pixel boundary — so writing new spans to the intermediate
buffer might require up to 8 writes, but searching is much faster.
Serialising can be done at the end of frame to compare to the previous
display if necessary.
Anyway, I really can't decide which way to go. And there are probably
other, better ideas. Is there any expertise on this list on this sort
of thing?
RSS Feed