Any good examples of 3D vector programming?

[Art]

The Liang-Barsky algorithm adapted for Basic is like this:

t1=0: t2=1
dx=x2-x1: dy=y2-y1
for i=1 to 4
if i=1 then a=-dx: b=x1
if i=2 then a=dx: b=255-x1
if i=3 then a=-dy: b=y1
if i=4 then a=dy: b=191-y1
if a=0 and b<0 then goto end
if a<0 and b<t2*a then goto end
if a<0 and b<t1*a then t1=b/a
if a>0 and b<t1*a then goto end
if a>0 and b<t2*a then t2=b/a
next i
u1=x1+t1*dx: v1=y1+t1*dy
u2=x1+t2*dx: v2=y1+t2*dy
end

x1,y1 - the first endpoint of the original line
x2,y2 - the second endpoint of the original line
t1,t2 - interval 0,1 representing two endpoints of the line
i=1,2,3,4 - testing the left, right, bottom, top screen edge (0,255,0,192)
u1,v1 - the first endpoint of the clipped line
u2,v2 - the second endpoint of the clipped line

I corrected some errors from a C listing I found (dividing by 0 and using very large numbers), but there is still one division (b/a). When I tested it in the Spectrum Basic with normal floating point numbers, it worked very precisely and no lines were missing. When I converted it to use only integer numbers, it wasn't very precise, some lines were missing and I had to add a correction to keep some endpoints on the screen (for example: if u1>255 then u1=255). For integer testing, I made the following changes and I compiled the program in Hisoft Basic with all variables as integer numbers:

t2=64
b=b*64 (added line after "if a=0 then goto (next i)")
u1=x1+t1*dx/64: v1=y1+t1*dy/64
u2=x1+t2*dx/64: v2=y1+t2*dy/64

I think that in classic Spectrum vector games, they probably use some more clever way to clip lines, but I have no idea what it could be.

[catmeows]

And do you know WHEN is the line missing ?

[Art]

I did some tests and finally I think that maybe this alorithm isn't very good for the Spectrum assembler. But I found the Sutherland-Hodgman algorithm adapted for the Amiga assembler, and it is based on addition and division by 2 to find a point of intersection with a screen edge. So I will try to play with this idea.

[Art]

So, the last agorithm works very well, it clips exactly at the screen border and on the original lines, and no lines are missing. It doesn't need any big numbers and it uses only integer numbers, addition, subtraction and division by 2, so I guess that it should be fast in assembler. Its main idea is about iteration and dividing an interval by 2. The explanation which I found isn't very well made and moreover it's for filled polygons, but I extracted the line clipping idea and adapted it for the Spectrum Basic. Probably it can be optimized, but I'll think about it later in assembler.

The only problem is that if there is an interval from -1 to 0 (one pixel out of the screen and one pixel on the screen border), the integer part of (-1+0)/2 is -1 and if the interval is divided again, the result it -1 again, so the iteration never ends. But I guess that it will not happen in assembler with negative numbers.

[Art]

I corrected the interval bug (it's interesting that it works in Basic now, but not in compiled Hisoft Basic - you can see the bug at the end of the video). Now I am rejecting out-of-sight objects using z<1, z>500, abs(x)>z+100. And now I can store many objects in the same scene.

http://phoenix.inf.upol.cz/~rachunl/test/cube5.mp4

With multiple objects, the data structure is becoming complicated in Basic, so I think that time for the assembler tests will be coming soon.

For a bigger scene it is probably better to move and rotate just centres and the clip whole object using bounding sphere or cube.

Yes, I guess so, but if I want to move and rotate camera and therefore move and rotate object centres (so the scene moves and rotates according to the camera), then I will need to rotate also every object's vertices, otherwise the objects will not face the camera correctly. Am I right?

[catmeows]

In general-yes. But only if object was not clipped already. And for distant objects you can cheat - replace object by its simplified version. On zx - with its low resolution - you probably can replace small distant object by pixel or small sprite that roughly looks like the object from one od main 8-16 angles..

[Art]

I made a new bugfixed version with simpler system of objects storage and manipulation. I also used translation and rotation of object centres and then rotation of object vertices, and I must say that it was a good idea. I also finally figured out how to clip 3D lines on z=1 before projecting them to a 2D plane using only division by 2, so the camera can go inside objects. So finally I used some ideas which Tommo wrote some time ago, but I needed to figure it out step by step.

I made a little "village", but now I see that probably I will need some fast hiden line removal algorithm. For objects' hidden lines and also for hidden objects (behing other objects). For the time being I don't know how to do it or if it can be fast enough for the Spectrum.

http://phoenix.inf.upol.cz/~rachunl/test/3d.mp4

[catmeows]

OH, you did great progress.
Hidden line removal should be simple but your engine needs to understand concept of triagles/quadruples. Then you compute normal od surface. It is cross product of two vectors on surface. Fortunately, you don't need size of normal vector, just information if surface is facing your camera or not (negative vs positive value).
Now, every line/edge betwen two visible surfaces is visible, any line between visible and invisible surface is visible (contour of object). Any line between two invisible surfaces Is not visible.

[Art]

My current program stores shapes as edges, so I can test every edge for clipping. But it makes sense that without faces, I can't know which edge is hidden.

So if I want to remove hidden lines, I have to change the shape system to store faces. I need to figure out how to define faces and how to know which edge is a part of which face. And if I want to use the z=1 clipping, I have to clip some edges and then redefine some faces according to it. Then I project it to 3D, compute normals to decide which faces are hidden and store the information. Then for every edge, I check the stored information of its two connedted faces to decide if it is hidden.

So for each edge, I probably need to store information which two faces it is connected to. Hmm, I think I need to figure out completely new shape storage system.

[RMartins]

Remember that hidden line removal is not just about hiding edges.

You have an horizontal line, that crosses your objects, hence you either have to "erase" the interior of the visible faces (drawing back to front), or you have to cut each edge (drawing front to back), since any solution of using a depth buffer on a ZX is a no-no, due to memory constraints (unless you have a very small viewport).

[Art]

Buildings' hidden line are removed. Finally it was quite easy, but I had problems with z=1 as usual. When some vertices have z<1, I can't project them to the screen plane. It's OK if I just don't want to draw those lines, but I need everything projected to test which faces are hidden, so I didn't really know how to do it right. For every face, I use three vertices to test its visibility. So I added one more test: If at least one of three face vertices has z<1, then the face is marked as visible. It works well in most cases, but sometimes it doesn't. Maybe when the face has four vertices and the fourth vertex (which I don't test) has z<1. I am not sure and I don't know it it's a good way. It was just a quick fix.

http://phoenix.inf.upol.cz/~rachunl/test/3d2.mp4

Sorry for the blinking. I still didn't do it in assembler, so I can't use a double buffer.

Remember that hidden line removal is not just about hiding edges.

You have an horizontal line, that crosses your objects, hence you either have to "erase" the interior of the visible faces (drawing back to front), or you have to cut each edge (drawing front to back), since any solution of using a depth buffer on a ZX is a no-no, due to memory constraints (unless you have a very small viewport).

Yes, it's true. Now my test program looks a bit like Cholo. I was already thinking about it. Probably it's possible to test every line with every face to find intersection points and to cut lines, but I think that it would be very slow. Do you think that erasing the interior of the visible faces would be fast enough? How would I know which part of the screen to erase?

[catmeows]

Yes, it's true. Now my test program looks a bit like Cholo. I was already thinking about it. Probably it's possible to test every line with every face to find intersection points and to cut lines, but I think that it would be very slow. Do you think that erasing the interior of the visible faces would be fast enough? How would I know which part of the screen to erase?

You can either use Z-buffer or painter algorithm.
Painter algorithm draws surfaces from back to front, overdrawing everything behind. And that's the problem - you will do a LOT of overdrawing.
Z-buffer is not much better, you write to and test Z-buffer a lot. You could use Z-buffer of smaller resolution but that will introduce glitches.
You can use S-buffer, that may use less memory than Z-buffer and should do less operation in buffer than Z-buffer but I have no idea how fast it would be to work with lists of scan lines.
If you look on early 3D games, they used either what you have right now (line removal in object scope), painter algorithm or special cases like raycasting (Wolfenstein) or portal rendering (Doom).
We have seen raycasting on ZX, it can be done with good framerate.
I have seen portal rendering on TI 83 calculator ( http://benryves.com/journal/date/2010/10 ) with 6Mhz Z80 and 96x64 resolution. It has nice ~10FPS.
You can check framerate for scene with few solid objects looks like in Starstrike II or you can check framerate for scene with a lot solid objects in Castle Master.
I'm afraid that from now every improvement will hurt framerate a lot.
You can hide horizont quite easily (see Captain Blood landing sequence), you can specialize your engine (3d part of blood brothers - https://www.youtube.com/watch?v=hNh9okE2xA4 )

To not be so pesimistic - you can optimize painter algorithm:
1) sort surfaces by Z
2) if surface is invisible - skip it
3) if surface is distant (Z>konstant), just draw visible edges
4) if surface is close, clear surface and then draw edges

this has two advantages:
1) player focuses on near objects and they will be perfect, you can still look through distant objects but they are not so important
2) if you are going to erase/fill surfaces you will need fast fill horizontal line routine - this routine wil have quite nice performance for long lines but short lines are slow. You need to mask start bits, end bits, compute number of whole bytes, maybe compute jump offset to unrolled loop, all that things take some time, even if the line is 3 or 10 pixels long. And distant objects will have a lot of short lines.

Anyway, I like what you did - full screen wireframe with line removal at this frame rate is nice.

[Art]

I added a simple system for doors and windows visible from outside.

http://phoenix.inf.upol.cz/~rachunl/test/3d3.mp4

I would like to add something to prevent the camera to go throught buildings, but I have to figure out the simplest and fastest option.

For removing hidden parts of objects, I would probably try the fill option. It's a good idea about working only on near objects. So I hope I will find a fast filling algorithm, because I've never programmed such things.

By the way, that 3D tests on the calculator look great. I was also thinking about something like that, but I have no idea how it works, so I will probably just try to improve my program.

Concerning the frame rate, my program unfortunately works like this only with accelerated video, because it's still only in compiled Basic. But I am already making some preparation for the assembler programming.

[Art]

Does anybody know about a fast assembler algorithm for erasing a quad polygon and a triangle (filling with 0)? Everything I found was only for filling an empty triangle etc., but I need to erase it with all possible lines inside.

[Tommo]

Does anybody know about a fast assembler algorithm for erasing a quad polygon and a triangle (filling with 0)? Everything I found was only for filling an empty triangle etc., but I need to erase it with all possible lines inside.

So, a complete fill?

The classic serial approach for convex polygons is to find the highest point on the polygon, then step along each of the edges from there solving for x at every possible value of y, then draw horizontal lines to join the x on one side to the x on the other.

Good term to search for: 'scan conversion'.

This site has a pretty good visual demonstration of a slightly more general version of that. Make sure you have 'scanline' selected in the pull-down at the top left. Place three or four vertices anywhere on the grid. Then repeatedly press the 'Step' button in the top right.

The find-the-highest-and-step approach means you'll always have exactly two edges in consideration and you'll sweep down from the top to the bottom. The simplest approach is just to use fixed point and calculate e.g. ((x2 - x1) << 8) / (y2 - y1) — having skipped over any horizontal edges, of course! — and then just step along y adding the delta to x and shifting right to get the integer version. This is known as the DDA algorithm.

You may notice that you can also use plain Bresenham anywhere a line is taller than wide. There's also run-slice Bresenham for edges that are wider than tall, which at least reduces you to an 8/8 divide rather than 16/8, or you can do plain Bresenham with a slightly different bias and capture x every time you modify y.

(Aside: of course run-slicing will be 16/16 and DDA will be 24/16 if you're clipping your polygons in 2d, while drawing, rather than in 3d before drawing)

[Sol_HSA]

I remember reading some graphics paper which went through various rendering algorithms including painter's, bsp, span buffers etc with discussion about various implementations, pros and cons. And there was a footnote at the end that of course we could just use a z buffer but that would be way too expensive and thus stupid.

Funny how things turned out in the end..

Anyway, span buffers might be a good fit; their primary weakness is that when there's a lot of geometry, the data structures tend to blow up. Since the processing power alone limits the geometry, I think it might work.

[Tommo]

A z-buffer parallelises trivially and has a simple O(1) data structure so it’s a great choice for hardware, but even then it’s rarely implemented naively. There are both hierarchical and deferred implementations in use today.

The main problem with span buffers is that you’re either keeping a linear list for logarithmic search, or a linked list for linear. If you do the former then on a Z80-type platform you’re going to spend so much time moving bytes around that you’re not likely to save on just doing the overdraw, because frame buffers are so compact and are generally local. I found that to be true on the Sam, at least, and that frame buffer is four times as large!

[Art]

Thank you for the tips. I made a triangle filler using horizontal lines, so it looks like this now:



It works, but when an object face has 4 vertices, I fill it using 2 triangles, so unfortunately it's two times slower for tall walls. Most of algorithms I found divide a convex polygon to triangles and then fills each triangle. The visual demonstrator from Tommo's post looks interesting, but the algorithm from the lecture looks more complicated than a triangle algorithm, so I am not sure if it would be faster.

Now I have to do some distance sort of objects to be able to fill the nearest objects last.

I also think about drawing objects according to the distance like this (from distant objects to near objects):
1. Do not draw.
2. Draw a dot.
3. Draw a small line or a small sprite.
4. Draw the object without hiding lines.
5. Draw the object with hidden lines.
6. Draw the object with hidden lines and filled (erased) visible faces.

As for a z-buffer or a span buffer, I don't know yet how it works or if it would be a better option, but I will try to look at it as well.

[Art]

The distance sort is done, so objects hide correctly behing other objects from any position and angle. So now I could add some colours (nearer objects have colour priority automatically):



I am trying to modify my triangle filler for a quad polygon.

[Joefish]

This is looking really good - what's the frame rate like now? And have you fixed the flickering, with a back-buffer. Or go 128K only and use screen paging.

One trick you can do with a back buffer is store it in a very different way to the Spectrum screen. You have a 256x256 pixel back-buffer (takes 8K, rather than 6K) where the byte order is in columns (running either upward or downward, your preference). The advantage there is that to move up or down one pixel, you add or subtract one to the screen address. To move left or right a screen byte, you need to jump a column, but this is easy as you just add or subtract one to the high byte of your screen address, in effect ±256 at a time. This lets you optimise your line drawing quite a bit faster.

Then to copy this to the main screen, you fetch a byte from buffer address (HL), write it to screen address (DE), then INC H and INC E to get the next byte to copy. Do this 32 times to copy each line of the screen.

As for Z-buffers and the like, if you meet the following conditions:

• All your objects rest on the ground

• All your objects are either vertical columns or pyramidal / tapering upward (no overhangs, tunnels or arches)

• The viewpoint can never go below ground level

• The view never needs to roll

Then you only need a 1-D height buffer. You draw objects from nearest to furthest, and for each X-position you record the highest pixel drawn. Then for further objects, you only draw the parts of them that appear higher up the screen than what you've already drawn. Sky Ranger does this effect, though it gets it wrong sometimes.

[Art]

Finally I made a quad polygon filler without dividing to two triangles, so it fills quad polygons much faster.

As for the frame rate and flickering, most of the program is still in Basic (even the filler!), so unfortunately the frame rate can be expressed rather in frames per minute than frames per second and I can't use a double buffer yet. For the time being, I am not able to program 3D vector graphics directly in assembler, so I made it in Basic to understand how it works, and then I am slowly converting it into assembler. It will probably take a long time, because I am still learning many assembler tricks.

Thank you for the tips. That height buffer is interesting. I think I understand the basic idea, but I am not sure if I could use it. For example I don't know if I can draw only parts of vector objects or how I can record highest pixels during drawing vector graphics.

[Sol_HSA]

First make it work, then make it fast. Your approach is completely valid.

[Art]

Yes, I think so. A month ago, I didn't know how to do 3D vector graphics in any language, so I am still learning how these things work and I added several new improvements. Now I am trying to figure out how to prevent the camera to go through buildings. I've tried several ideas and nothing works correctly, but I will need it to make a game.

[Sol_HSA]

You just stumbled into a rabbit hole:

https://realtimecollisiondetection.net/

It's a good book. Highly recommended.

[Art]

Thank you for the hint. So the collision test is done. I've used buildings' base polygons on the ground to test if the camera is inside. I still need to improve some parts of the whole program, but the result is quite good. After some improvements and fixing bugs, I should probably try to do some more parts in assembler.