The Mud Puddle

Home of Jon "evincarofautumn" Purdy

Heuristic Rendering?

Yeah, why not? Read on.

This idea has been wriggling around in my mind for a while. Say you want a really fast, really simple software renderer (3D, of course). The principal thing you must do is draw triangles. And lots of them, and swiftly. And in many different colours.

To do that, of course, a lot of people will tell you to actually draw triangles. By the scanline! Do not listen to these people. With heuristics in mind, it's possible, if not actually rather easy, to figure out the following:

  • Ignoring colouring, drawing a model generally results in a rather simple filled 2D region on the screen; and
  • Most 2D regions such as this (except, perhaps, some very special cases) can be tessellated with a significantly lower number of arbitrarily-sized rectangles than of pixels; so
  • The solution is simple: sort triangles into edge cases and non-edge cases, fill the non-edge cases with a small number of large rectangles and fill the edge-cases with a larger number of smaller rectangles, according to the preferred maximum resolution.

Since it requires the renderer to keep track of a lot of rectangles, an algorithm of this sort is increasingly memory-intensive as models have more and more edge cases. Hence it's best for rendering objects without many holes. Figuring out where the rectangles actually go is no more difficult than drawing a triangle by scanlines.

The simplest method that I have found is to subdivide a square bounding box using a quadtree. This has the benefit of being both independent of screen resolution and easy to arbitrarily limit to a maximum number of subdivisions. That and a quadtree class is ridiculously easy to implement, especially when only leaf nodes have to keep track of only a Boolean ("marked" or "unmarked") status.

I'll post code (and rewrite this crappy explanation) once I finish writing it.

Note that if no one has come up with this specific idea before me (which I'm fairly sure they haven't, even if, by my description, they have), I'll accept credit for it.

And my internet keeps disconnecting and reconnecting. It's painful to be on IM like this.

Oh, well. Dial-up sucks. At least at RIT I'll have good service.

last updated 4 months ago #