## Real Time 3D example

Want to discuss about Demos on the Oric, here you are !
jbperin
1st Star Corporal
Posts: 10
Joined: Wed Nov 06, 2019 11:00 am

### Re: Real Time 3D example

ThomH wrote:
Thu Dec 26, 2019 7:52 pm
Cool, I've written homebrew 3d on an Atari Lynx, which has a separate maths unit including multiply with accumulate that makes life very easy, and on a Z80-based machine. So naturally I stuck my nose into your code.
I feel honored that you casted a glance at my code.
If I had known that such a thing could happen, I would have cleaned it a little bit
ThomH wrote:
Thu Dec 26, 2019 10:32 pm
It looks like your fast project ejects the classic linear algebra solution of dividing by z in favour of a trigonometric solution, using atan to determine the angles between a point and the horizontal and vertical planes, then using those angles to look up the 2d point through which the relevant ray runs? Have I understood that correctly? If so, very devious!
Yes you understood right. Get out of academic 3D to street math 3D that might suit better to 8 bits 1Mhz processor.
ThomH wrote:
Thu Dec 26, 2019 10:32 pm
If you can come up with that, I'm sure you're ahead of me on almost everything else, but on the off-chance: definitely using a binary search for display-area edge clipping. I do them in 3d, before projection, to offer guarantees about range at the next stage but I've also read persuasive arguments that if your objects are generally 'small' then it's more efficient to clip after projection.
That's a very good advice. I plan to use the projection in several pass. A first pass to determine which Object are in the field of vision.
And then, in an other pass, only project points and faces that belongs to visibles objects.
I also think of using distance to deal with Level Of Detail. For far objects, use a kind of vectorial drawing of a sprite .. and only use points and faces projection for close objects.
Well there are many ideas to explore . It is hard to determine which one is the most ressources-saving . That's why it's very interesting to take advantage of your experience.
Your post make me think of the topic of polygon clipping which is very interesting. I'm working on a own-made algo because sutherland hodgman algorithm looks far too heavy for a 6502.

ThomH wrote:
Thu Dec 26, 2019 10:32 pm
I keep meaning to stop being lazy and write a quick tunnel game based on fixed height walls, 2d map geometry, a 1d 1/z buffer and partial redraws — in the special case of fixed-height walls the 1/z buffer is nothing more than a "put this column into this slot only if it is bigger than the one that's already here", and you end up with a 240-entry table of height + pattern per screen column. So if you still have the previous table sitting around, it's pretty trivial to draw only the differences — completely redraw any column with a different pattern, just adjust the height of the others up or down a bit.
DBUG has done something like that here:
viewtopic.php?f=20&t=1813&hilit=walls.zip#p16985
ThomH wrote:
Thu Dec 26, 2019 10:32 pm
You're obviously a much more productive person than I am.
Sorry you can't beat me on the field of lazyness .. homebrew is the proof

Chema
Game master
Posts: 2539
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

### Re: Real Time 3D example

About the filled polys routine, as I said I gave it a try some time ago. It looked terrific for a demo, but had some problems for using it in a real game. I always felt frustrated to some extent by not being able to add it to 1337.

I uploaded a couple of demos here, with a very primitive version of the engine (many nasty things appeared later on, as can be seen in the looong thread - but it was really fun!)
viewtopic.php?f=20&t=364&p=2555#p2555

Dbug
Posts: 3111
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

### Re: Real Time 3D example

Well, what I wanted to do was to extend the system to use span buffers and delta screen updates, but I never quite managed to find an efficient way of doing that.

Basically the idea is that you still rasterize the edges, but instead of drawing the horizontal segment immediately to the screen, instead you register that in a list of segments.

You do that for all your polygons, and when you are done, you do a display pass of the segments.

The naive version would be incredibly slow, but the idea was to try try to peep two lists of segments, one for the current frame, one for the new frame, and only redraw the parts that are different.

Basically that would allow full screen display with some pseudo double buffering, but it's far from trivial to do because:
- Merging segments is non trivial (it's like a form of clipping/insertion system)
- Diffing two lists of segments to find the minimum optimal area to redraw is not trivial either
- Since dynamic allocation would kill performance, you need a fixed list of buckets for the segment list, which can be hard to handle

ThomH
Flying Officer
Posts: 178
Joined: Thu Oct 13, 2016 9:55 pm

### Re: Real Time 3D example

Dbug wrote:
Tue Dec 31, 2019 1:12 pm
Well, what I wanted to do was to extend the system to use span buffers and delta screen updates, but I never quite managed to find an efficient way of doing that. ...
I tried the same thing over in Z80 world, maintaining an ordered span buffer (which makes the differential draw trivial) but my reasoning from "the amount of data will be small, just write something" that I could just use a basic array of spans and shuffle it as required led to me spending more time manipulating the array than I had previously been spending just drawing polygons. So from there you get to 3d scenes in which the span structure can be calculated more trivially and the only ones I've so far discovered are anything Doom-esque or more simple, and the 8-bit versions of Stunt Car Racer (which approximate the walls below the track as screen-space verticals regardless of your current roll, so that plus the fact that it's trivial to draw front to back).

That said, for platforms like the Oric with efficient redefinable character sets I've sort of wondered whether the smart thing to do isn't just to brute force it in text mode, doing as much of the fills using pre-filled characters as possible and only dynamically allocating characters at the edges? You'd basically do a fill at character resolution, then a perimeter walk to tidy up the edges. The main issue I haven't been able to talk myself around is how to deal with character exhaustion — if that has to happen then you want it to happen when you're drawing less consequential background things, but if you're doing a classic painter's algorithm then you're drawing back to front. I guess you could just limit yourself to a viewport that you could in theory paint with completely independent characters, though on an Oric that's kind of small. So the other solution is maintaining a simple scene.

EDIT: or you could fill a conventional left/right edge buffer, and then char-fill as many character squares as are completely filled between max(left[y...y+8]) and min(right[y...y+8]), then deal with whatever is outside that range separately. That'd avoid probably having to go barycentric for tips.

Naturally I've yet to lift a finger in implementation.

Dbug
Posts: 3111
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

### Re: Real Time 3D example

I believe a span buffer method could be useful only for scenes made of large polygons moving relatively slowly, because the time won by not having much overdraw would probably be a win.

But with scenes with many small polygons moving fast, that would probably not help much.

Regarding text mode, it's only a 8x speedup on the rasterization, I'm not sure that such a huge improvement, considering how difficult it is to do dynamic allocation of characters, and the fact that even if you are in HIRES; you do not have to compute every single scanline correctly (you can compute only half of the pixels and interpolate, that still gives you the ability to do nice dithering on a 2x2 pixels matrix.

ThomH
Flying Officer
Posts: 178
Joined: Thu Oct 13, 2016 9:55 pm

### Re: Real Time 3D example

Dbug wrote:
Mon Jan 06, 2020 8:21 pm
Regarding text mode, it's only a 8x speedup on the rasterization, I'm not sure that such a huge improvement, considering how difficult it is to do dynamic allocation of characters,
Like all games, I was imagining a heavily-simplified allocator:

If you had the first 120 characters to allocate, set a not-yet-allocated pointer to 119. Keep a 120-byte reuse buffer, and a pointer into it. Set it to 0.

When you need a new character:

Code: Select all

``````if(not-yet-allocated characters != 0) {
character to use = not-yet-allocated;
-- not-yet-allocated characters;
return character to use;
}

if(reuse pointer == 0) {
return nothing available sentinel;
}

--reuse pointer;
return reuse buffer[reuse pointer];
``````
And similarly, when drawing to the display, put IDs into reuse buffer only if you overwrite a character that isn't one of the predefined set.

Or eject the reuse buffer entirely, if you've managed largely to eliminate overdraw. Or just don't fancy the costs.

Frustratingly, although I put my Z80 work on Youtube, the span buffering stuff appears to be the only thing I didn't launch. As per the video title, that's on a Sam Coupé which sounds impressive when someone tells you it has a 6Mhz Z80, until they mention that memory contention restricts the processor to one access window in eight (!) to all (!!) RAM, and being a true 4bpp 256x192 display you've 24kb (!!!) of frame buffer to try to modify. Which all adds up for a pretty dire fill rate.