Subject: Other rendering methods?

From: Juri Munkki <[email-masked]>
Date: Wed, 25 Nov 1992 16:03:15 GMT

(This was originally a letter from me to Bernie Roehl)

Hi,	

I just read through all the accumulated messages in the rend386-list.
All my information on how rend386 is based on what was written there.
As I am a Macintosh programmer, I didn't bother to download the code.

During this autumn, I have written my own 3D routines. About a month
ago, I wrote a fairly high performance vector graphics kit that uses
fixed point math and 4x4 matrices. It could be faster, but it's fast
enough for me as it is now.

I've been thinking of writing my own scan-line based polygon renderer
for a few years now (possibly for as long as 10 years), but last
weekend, it all somehow became clear to me and I started coding.
I now have most of the code written (clipping still needs some work,
as does color video support).

I thought I would share some of my ideas with you and possibly get
some feedback from you. The rendering methods of Rend386 and my
system are quite different. I'm mostly talking about the actual
2D polygon rendering here.

I have no idea what the performance of Rend386 is, nor do I know
how my routines would compare with yours on similar hardware. I
know that I get fairly nice performance on my 16Mhz 68020. I don't
think that Apple even produces anything slower than this. I'm
probably going to get a 25 Mhz 68040 pretty soon (a Quadra 700),
which will possibly be up to 10 times faster.

If I understand correctly, your animation proceeds like this:

	- Clear buffer
	- Draw the polygons in sorted order from back to front
	- Switch video buffers

My animation method is like this:

	- Scan convert the polygons into a run-length encoded list
	- Compare this list with the list of the screen that is shown
	  and produce a list of differences
	- Draw only the changes between the two buffers

Your method is good in cases where there is very little time-coherence
in the pictures. Mine is fast when the scene doesn't change much, but
shouldn't do much worse when there are big changes.

The scan conversion starts with all vertices inserted into lists. For
each Y value, there is a list of vertices becoming active on that row
and vertices going away after that row. These lists are built before
the scan conversion. Clipping in the Y direction is also handled at
this stage. (Only clipping against the top Y boundary is necessary.)

The scan conversion proceeds as follows:

	0 Clear active list of vertices

	1 Check the activate list for the current row and
	  add vertices to the active list

	2 Insertion sort the active list according to X

	3 Push a depth priority of 0 into a "depth stack"
	  (really a linked list)

	4 Read a vertex from the active list

	5 If this depth priority exists in the stack,
	  remove that item from the stack

	6 If this depth priority isn't on the stack, insert it there
	  at the right position.

	7 If the top stack item has changed, write the previous top
	  color and boundary for that color into the output.

	8 If there are more vertices in the list, go to step 4

	9 Check the "deactivate" list and remove vertices from
	  the active list according to this list.

	10 For each active vertex, add dx to x. 
	   (dx = (x2-x1)/(y2-y1) in fixed point.)

	11 If there are more rows to process, go to step 1

The insertion sort uses very little time, since most of the time the
vertices are already in order. Only new entries need to be sorted into
the list and this doesn't happen often.

I see several advantages with my approach:

	- Double buffering is not necessary, since changes are drawn
	  very cleanly over the existing buffer.
	- The minimum amount of pixels are changed from frame to frame.
	  This is especially important for 24 bit displays where drawing
	  a single pixel requires a 32 bit move.
	- Screen clears are avoided.
	- No clipping on the X axis is necessary.
	- There are no limitations on what the polygon should be like.
	- Arbitrary clipping polygons can be used. Since there already
	  is a reserved color for "no change", because the RLE comparing
	  routine needs to produce this, this color can also be used for
	  a polygon that has very high priority. The area of the this
	  polygon will not be clipped.
	- Since arbitrary region clipping can be done with very little
	  overhead (the addition of one polygon) and no double buffering
	  has to be done, the routines can easily co-exist with windowing
	  software.
	- Only a very simple video driver has to be implemented for
	  different bit depths. Basically it takes a stream like this
	  for input:

		c0 50 -1 80 c1 82 c2 100 -1 640

	  This would use color or pattern 0 from pixels 0 to 49,
	  ignore 50 to 79, use color c1 from 80 to 81, c2 from 82 to 99
	  and ignore 100 to 639 and then move on to the next video row.
	  (-1 is the ignore color here, c0 is background)

	  A triangle moving one pixel to the right will cause only two
	  pixels to be changed per row:

		-1 100 c0 101 -1 121 c1 122 -1 640

	  My code doesn't assume anything about the resolution, but I
	  used 640 as the X resolution here, since that's what my PowerBook
	  has.

	  My current video driver is for 1-bit deep displays, so in order
	  to be useful, it has to support fill patterns. I use 32x8 patterns.

This turned out to be longer than I expected. Most of the code is in 68K
assembly, so it will not be directly useful to the Rend386 crowd.

I would be very interested to read your comments.

	Juri Munkki
	[email-masked]