No expert here! Just my two cents.
I considered both your Ideas 1 and 2, both came out to be more expensive
with maintenance than I wanted. Especially Idea 1 (which is a basic space
partitioning tree), the masks are very inefficient when you have many
overlapping/joining polygons in the same 8*8 pix square. This happens an
awful lot for objects in the distance, I ended up having to redraw to the
same 8*8 square many times.
As I'm heavily using the stack pointer to draw to the screen I wanted to
render the whole object right-to-left line-by-line. Like Braben, I'm using
convex polys and convex objects only. (This isn't a problem when you can
glue convex objects together afterwards). For each object, there are two
kinds of mask to use - (A) one at the left and right sides of the object, ie
the background meets the object here, and (B) where the polys on the object
meet each other in the middle.
(A) is done traditionally, with a bitwise-mask to ensure crisp edges.
(B) only has 4 or 5 different flavours so is hardcoded.
I use a 'shared points' system to ensure calculations on points and vertices
are only done once, this helps ordering the rendering process as well, so I
know which polygons I'm rendering on each line. In the end the code looks a
bit like this:
Render:
PUSH HL ;Poly 1 - 4 bytes per push. Mmm, efficient-y.
PUSH HL
...
PUSH DE ;Joining bit
PUSH BC ;Poly 2
PUSH BC
...
I'm still having problems with digesting (B)-type joins when the polys are
small (less than 4 pixels), but it seems to be quite efficient.
Howard
PS Sorry for top-posting. Most rude :-)
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On
Behalf Of Thomas Harte
Sent: 25 August 2008 14:13
To: [email protected]
Subject: 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?
No virus found in this incoming message
Checked by PC Tools AntiVirus (4.0.0.26 - 10.100.019).
http://www.pctools.com/free-antivirus/
No virus found in this outgoing message
Checked by PC Tools AntiVirus (4.0.0.26 - 10.100.021).
http://www.pctools.com/free-antivirus/
