A Doom engine in about 2000 lines of C

Page 2/4
1 | | 3 | 4

By ARTRAG

Enlighted (6564)

ARTRAG's picture

05-06-2017, 23:30

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

By Grauw

Ascended (10135)

Grauw's picture

06-06-2017, 01:38

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 Smile.

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.

By santiontanon

Paragon (1519)

santiontanon's picture

06-06-2017, 02:58

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).

By PingPong

Prophet (3788)

PingPong's picture

06-06-2017, 21:10

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...

By ARTRAG

Enlighted (6564)

ARTRAG's picture

06-06-2017, 22:33

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

By Lord_Zett

Paladin (807)

Lord_Zett's picture

06-06-2017, 22:35

enuf talking plz make some code and show us.!

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

By Grauw

Ascended (10135)

Grauw's picture

07-06-2017, 00:00

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

By Grauw

Ascended (10135)

Grauw's picture

07-06-2017, 00:13

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).

By ARTRAG

Enlighted (6564)

ARTRAG's picture

07-06-2017, 09:04

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.

By ARTRAG

Enlighted (6564)

ARTRAG's picture

07-06-2017, 09:47

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