## Real Time 3D example

Want to discuss about Demos on the Oric, here you are !
jbperin
Pilot Officer
Posts: 124
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: 2686
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: 3377
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: 219
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: 3377
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: 219
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.

jbperin
Pilot Officer
Posts: 124
Joined: Wed Nov 06, 2019 11:00 am

### Re: Real Time 3D example

Chema wrote:
Tue Dec 31, 2019 9:58 am
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
It's terribly impressive !!! really stunning !!
I had missed this "too-long" thread because the 3D word cannot be searched on the forum (not enough letter in the word).
In the demo named shipdemo.tap that you provide in this post
How do you deal with hidden segments of the ship ?
Are you using normals calculation ? There are so many multiplication with this approach .. it can't be so smooth.

It seems to me that in the 1337 game, sometimes, we can see stars shining though the space ship. Although the hidden part of the ship are perfectly handled. It would mean that it is not real face filling .. but rather tricky and smart dealing with hidden parts.
I would love to know more about your dealing with this point.
ThomH wrote:
Thu Dec 26, 2019 10:32 pm
On polygon filling, I've never come up with a completely compelling solution for dealing correctly with clipping against z=1
Neither did I.

But I think I've almost managed to avoid the problem in the last demo I made of glOric and that I join to this post.

I use a z-buffer to deal with hidden faces which are in front of the camera and I select the face to draw depending on the angle of the points involved in this face. There are still cases where it fails but most of the time it does the job.
ThomH wrote:
Mon Jan 06, 2020 10:07 pm
Big congrats for that !! Colored face filling looks very great !! As well as the space ship.
How do you deal with hidden segment in space ship at 1:30 ?

I repost in attachments:
• the fixed Text Demo (no more infinite loop)
glOric_2019_02_10_TxtDemo.tap
Corrected Text Demo
• the brand new demo named LrsDemo
glOric_2019_02_10_LrsDemo.tap
Demo of Face filling clipping + zbuffer + collision detection with Ascii Art Rendering
which features :
- face filling clipping (for immersive 3D)
- zbuffer (for hidden face handling)
- ascii art rendering
- collision detection (to prevent the player from crossing walls)
It is not yet fully optimized (it is even far from it) but it starts being usable in real time. So it gives hopes:

Sources are available on the glOric repository.

Big thanks to _Dbug_ for his help, advices and support.
Last edited by jbperin on Tue Feb 18, 2020 2:50 pm, edited 1 time in total.

mikeb
Flying Officer
Posts: 249
Joined: Wed Sep 05, 2018 8:03 pm
Location: West Midlands, UK
Contact:

### Re: Real Time 3D example

Very nice demo -- now, if only there was a way to synchronize two Orics together, both running the same code, with same source data, but rendering from slightly different points of view (left, right), you could do a true 3-D display, one for each eye ...

Oh wait ...

viewtopic.php?p=18951#p18951

There's another possible use for EXOS then!

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

### Re: Real Time 3D example

jbperin wrote:
Mon Feb 10, 2020 4:51 pm
How do you deal with hidden segment in space ship at 1:30 ?
I lifted that directly from Elite — the object is convex, so drawing only those edges that are connected to at least one front-facing surface does the trick. I'll bet 1337 does the exact same thing.

I was also lucky that the computer I wrote that for supports triple buffering, so I could just (i) draw all lines; (ii) switch buffers; (iii) erase all lines on newly retired buffer. Erasing when you're guaranteed a black background is a lot cheaper than drawing because you don't have to worry about sub-byte masking.

From watching it with my own eyes, I think the original Elite just has a single XOR line routine and draws and undraws in a round robin fashion — the BBC Micro has an anaemic amount of RAM so that may have influenced the use of a single routine both to draw and erase, though I also guess an XOR is no more expensive than an OR when you've got to do every pixel as a read-modify-write anyway.

jbperin
Pilot Officer
Posts: 124
Joined: Wed Nov 06, 2019 11:00 am

### Re: Real Time 3D example

ThomH wrote:
Mon Feb 10, 2020 6:07 pm
drawing only those edges that are connected to at least one front-facing surface does the trick
Sorry but I don't understand how we determine what is a front facing surface.
It makes me think of normal vector calculation implying costly cross product operation.
Is there a cheapest way ?

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

### Re: Real Time 3D example

jbperin wrote:
Mon Feb 10, 2020 8:30 pm
ThomH wrote:
Mon Feb 10, 2020 6:07 pm
drawing only those edges that are connected to at least one front-facing surface does the trick
Sorry but I don't understand how we determine what is a front facing surface.
It makes me think of normal vector calculation implying costly cross product operation.
Is there a cheapest way ?
You work out the surface normals ahead of time, so that's where the cross products are (and the normalisation is the real cost), then just rotate them and dot product them with the vector from the viewer to any point on the surface. You can also do it in screen space by checking for clockwise or anti-clockwise winding, but only after projection so that costs more.

If you had the memory available, you could do a per-object BSP tree (they're convex, so you're guaranteed no splits), then transform the viewer into the object's coordinates to traverse that, hopefully getting you to O(log n) dot product costs rather than O(n). But I haven't tried that, so I don't know whether this is one of those cases where either: (i) the better O algorithm is actually slower because O(n) isn't that large and the more complicated data structure traversal kills you; or (ii) precision in fixed point ruins everything anyway.

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

### Re: Real Time 3D example

For the filled polygons demo, I just used the routine designed by Dbug, so he can explain better. It is great for a demo, but I doubt it is usable for a general purpose engine... it draws odd/even lines and erase even/odd lines at each frame.

For the final game, it is just wireframe drawing (thus transparent polygons) with hidden face removal. I implemented two methods for this for testing, but in the end used pre calculated normals for each face, which are rotated. These normals were also multiplied (iirc) with the observation vector, to determine visibility.

And you are right, the original Elite used xor drawing. Only the spectrum version (and 1337) use double buffer.

Al this can be done by using a fast multiplication routine using tables. The routine is here viewtopic.php?f=4&t=393

It was quite a few years ago, and I don't remember all the details...