# A Doom engine in about 2000 lines of C

Page 2/4
1 | | 3 | 4

Is there a fine algorithm off the shelf for tracking poligons using a minimal amount of fillled boxes?

None that I know of… The most obvious starting point would be drawing edge-to-edge spans per-scanline with Bresenham. Those are filled boxes .

You could try to optimise that further, e.g. if the previous scanline has the same coordinates, then collapse the draws, etc (might work better for quads than triangles). But that only optimises a fairly specific case, and there’s so many cases… seems a very difficult problem.

Maybe another starting point could be flood fill algorithms, maybe there’s some nice idea lurking there.

What do you mean by "tracking polygons"? if you mean filling them, the classic algorithm is the "Scan-line algorithm" ( https://www.techfak.uni-bielefeld.de/ags/wbski/lehre/digiSA/... ), which can render arbitrary polygons (even concave ones).

santiontanon wrote:

What do you mean by "tracking polygons"? if you mean filling them, the classic algorithm is the "Scan-line algorithm" ( https://www.techfak.uni-bielefeld.de/ags/wbski/lehre/digiSA/... ), which can render arbitrary polygons (even concave ones).

maybe can be adjusted to work with VDP line command or rectangle fill command*. while CPU does calculate X/Y data VDP draw the line.
However, i do not expect an high speed...

In the simpler case (no stairs or multiple heights, just non orthogonal walls) the poligons needed are isosceles trapezes.
Anyway from the first tests, I should port all the math to fixed point... dunno if it is worth

enuf talking plz make some code and show us.!

and that raytrace demo of ARTRAG is a good start thing to

Hey! I’m already working on something since the IO discussion a few weeks back, but it takes time… And discussions on the topic give me new ideas and keep me motivated!

Btw in my project, the matrix math isn’t the biggest concern at all. Rasterisation is so far the more costly affair. I use 8.8 fixed point btw, targeted at turboR (but using MULUW or not doesn’t make too much of a difference).

Have you already implemented portal rendering?
Do you aim to bitmap rendering or to flat color walls?
If you go for column by column rendering, Wouter's code in our raycasting demo is probably the best one can get in order to maximize the vdp usage without incurring in the r800 halt caused by successive accesses.
The idea there was to encode columns as a sequence of colored boxes, whose heights and colors are computed and packed by a pre processing tool.

The code is scaling the next segment of the column while the vdp is plotting the current box.
Maybe having all the box sizes pre scaled could speed up a bit the work but it would increase a lot the ram usage while on TR the time of a multiplication is about the same of a table access.

Page 2/4
1 | | 3 | 4