Hidden vector graphics (3D)

Resident (38)

12-12-2022, 13:46

Can anybody help me with the formula's (or method) of hidden vector graphics. By that I mean that you, for example, animate a cube, but you don't draw the vectors that shouldn't be visible. There can be tricks for that when you only animate a cube. But what if the 3D object is more complex, or if it concerns 2 objects. Than only part of a vector could be hidden from view. If have searched online a bit, but because the terms are used in a lot of non related documents, it's hard to find.

I know of one: Sam Coupé 3d. But I find it very difficult to extract the correct formulas from this or to re-use the source code.

I also know of the Vector-Clipping routine by NYYRIKKI and will gladly use it also if possible.

Does anybody know of a (online) document or source code that can help here? Or would you like to help yourself in figuring it out with me?

By Sandy Brand

Champion (309)

12-12-2022, 18:19

The simplest way is to do 'wireframe' rendering of a single convex shape.

By doing 'dot products' with the surface normal vectors of the shape it is fairly straightforward to figure out which faces are visible and which are hidden from the eye. You only need to render the lines of the surfaces that are visible. If your shape is convex you don't need any complex and costly hidden surface removal algorithms.

Elite did basically this, with some additional tricks. If you look closely, all the spaceships in this game are convex hulls, with some minor exceptions here and there. And the game just didn't care about overlapping shapes.

For anything more complex (filled polygons, multiple shapes, non-convex shapes, etc.), things will be a lot more costly to compute and render at high frame-rates.

By santiontanon

Paragon (1831)

12-12-2022, 19:10

Exactly. There are basically 2 types of techniques here:
(1) "culling" techniques. These filter out triangles that you know for sure you do not want to draw. There are two standard culling techniques used in 3d renderers:
(1.a) "hidden face culling" (or sometimes called "back face culling") (what Sandy Brand was explaining). This is quite straight forward: since a triangle is made out of 3 points (a, b, c), you take the vector a->b, and the vector b->c, and compute the normal of the triangle. Then a simple dot product of that normal with the "camera direction vector" tells you if your triangle is facing the opposite direction (positive dot product) and does not need to be drawn, or is facing the camera (negative dot product), and needs to be drawn. The one thing to be careful in this technique is that you must be careful when defining the a, b, c points of your triangle, so that they are always specified in a "clockwise" order. Otherwise, the normal vector will point in the opposite direction and your dot product will have a flipped sign.
(1.b) "frustum culling": check if the triangle falls completely outside of the frustum volume that will be rendered by the camera, and thus can also be ignored.

(2) "Occlusion" techniques: these are techniques so that triangles that are closer to the camera occlude those that are further behind, and not the other way around. The classic algorithm is the "painter's algorithm" (sorting all the triangles and drawing back to front). This works well for small triangles and for a small number of triangles, but there are situations where it will not work well (specially if triangles are large). The better algorithm is the use of a z-buffer (which is unfortunately unfeasible in small 8-bit machines, as it requires storing one scalar per pixel in the screen, and it is likely we do not have enough RAM for that ).

Anyway, I hope at least the names of the different algorithms help you find what you are looking for! Of course, there are many more culling/occlusion techniques used in modern renderers, but for small 8-bit machines, probably a subset of the above is enough

By BadWolf359

Resident (38)

12-12-2022, 21:31

Very informative @Sandy Brand and @santiontanon! Thanx!

Reading this I'd better stick to (only) the Culling techniques. I was mostly asking this for usage in a demo. And luckily in that case (unlike with games) you know exactly when what happens. And that way you can more easily "predict" which vectors should be hidden. But I think it's still a bit of a puzzle.

By turbor

Hero (529)

15-12-2022, 11:10

In my 3D routine I stored the normal vector of each triangle in my data structure. Then I only calculate the Z-component of the 3D rotated normal vector and use the sign of the Z-component to see if I need to actually calculate and draw the other 3 points of the triangle. And then cache those 3 points so that you do not have to recalculate them for adjacent triangles... ;)

You have to be ware that this will not work if you add depth/perspective adjustment. Since in such case the Z-component might indicate a visible triangle while it will become invisible after perspective correction.

By BadWolf359

Resident (38)

15-12-2022, 11:44

That's pretty cool @turbor!! This is exactly what I want to do/know.
Is the source code open? Or are you willing to share? (If not, no worries) I might be able figure some of this out myself but it would really help if I had a working example.

By turbor

Hero (529)

16-12-2022, 09:13

BadWolf359 wrote:

Is the source code open? Or are you willing to share?

I never published that code (for now). I'll probably do so someday but the source is somewhere on an old DD disk that is in storage on an attic far far away, so don't expect anything in the near future.
Of course I'm willing to answer any questions you might have...

By BadWolf359

Resident (38)

16-12-2022, 19:46

Well my main question would be: How to fill a triangle efficiently (without writing the same pixel multiple times).
And how do you put a texture on it?

By st1mpy

Paladin (947)

17-12-2022, 11:15

Try reading computer graphics books for computer science courses from 1980s and early 1990s, they cover basic 3D rasterization methods.
Also I think there was pc-8801 or msx based book on the subject as well, reading old books about computers is always fun.

By turbor

Hero (529)

17-12-2022, 21:32

Very very very abbreviated:
You draw a triangle by sorting your 3 points P1,P2 and P3 so that Y1<=Y2<=Y3. If Y1!=Y2 then you first draw a triangle by setting up 2 bresenham line routines starting from P1 to P2 (line L1) and from P1 to P3(Line L2).
Now while increasing Y you calculate x of L1 at the given Y and x of L2 at the same Y, draw a line between these two X-coordinates at height Y. On an MSX2 for a solid color triangle you can use the VDP LINE command.
Once Y is Y2 you swap L1( or L2, depending on P2) for a new L3 that goes from P2 to P3 and you continue until Y==Y3 and your triangle is drawn.
If Y1 == Y2 you can setup L1 to go from P1 to P3 and L2 to go from P2 to P3, then simply jump in the loop that runs until Y==Y3

If you want a texture map on the triangle you trace through the UV-map in the same bresenham way and get the corresponding source pixel from the texture map and output it to the line you're drawing. Simply use OUT instructions or use the LMMC or HMMC command.

If bresenham doesn't ring a bell, or this short version is too confusing,then (like st1mpy suggested) find some older books about computer graphics. Modern books will simply tell you to throw the triangle list at your GPU which will take care of it

The main problem is that modern programming does an offload of all this low level rasterization to the video hardware so it isn't thought anymore unless you're interested in designing new GPU's.
Also, do not underestimated the fact that a Z80 doesn't have a multiplication routine

By Grauw

Ascended (10820)

17-12-2022, 21:39

BadWolf359 wrote:

Well my main question would be: How to fill a triangle efficiently (without writing the same pixel multiple times).

Basically I would say that depending on what you want to do it may be fastest to do no checks at all and just paint pixels multiple times. With convex shapes and back face culling there won’t be much overlap anyway. The alternative is to use a z-buffer, but the cost of keeping track of that may be higher than just writing out the pixels, although you would be able to omit the depth sort.

p.s. Check turbor’s reply in this older thread.