Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Vector visibility - Z axis solution
2007-12-04 07:52
LHS

Registered: Dec 2002
Posts: 66
Vector visibility - Z axis solution

Hi all,

I am coding a classical demo part - filled vector. I have a routine for vertex transformation (rotation) and a routine for EOR surface filling.

If I have f.e. a simple opaque cube (all angles are 90dgrs), what is the best technique to check which surface I may show and which I mustn't? I have f.e. 4 vertexes of a side (X, Y and Z coordinates in signed variable), how can I calculate, if is this surface (of the cube) visible or invisible? I think the same technique can be used for a glanz cube which surface is inner or outer.

Thanks,

LHS
 
... 20 posts hidden. Click here to view all posts....
 
2007-12-05 08:08
LHS

Registered: Dec 2002
Posts: 66
JackAsser, Oswald and the rest <<thanks you very much for your hints, now I am going to try code function filled vector and then I will let you know my result

Oswald <<I like your demos, specially I mean VOID or SOILED LEGACY are one the best demos at C64 (I like your combination of high code & high design). When you released your first demos under COMA (btw. your first(?) COMA demo with real multitasking from Flag96 is not on CSDB - why? if you don't have a copy I think I can find it in my archive...), I was active coder too -> I don't know all hard C64 calculation (f.e. Graham's or AEG's vectors), but after 12 years of coding I know C64 limits and I don't contend with 6502 implementation ;-)
Of course I know transformation matrix of 3D vertex, I know a fast signed multiplication routine with bits rotation etc. I have coded a fast dots vector and now I will only code a classic filled vector.

Do you mean is perspective projection necessary for a simple filled vector? I have an implementation of the projection without divine:
if you know max Z of all vertexes then
constP = Zmax - Z(of actual point)
ASL constP (possible several times over)
perspX = constP * X
perspY = constP * Y
but now I am using paraler projection.
2007-12-05 08:38
JackAsser

Registered: Jun 2002
Posts: 2014
Ok people, since I was a bit unclear I've written a little tut:

1) A little bit of matrices

First of all it's essential that you understand what a normal 3x3 matrix is
made up of. Let's consider the unit matrix, i.e. the one that's implicitly used
for a non-transformed space:

|1 0 0|
|0 1 0|
|0 0 1|

What this matrix actually tells us is the X,Y,Z coordinates for the X,Y,Z
unit world axises.

|1 0 0|
|0 1 0|
|0 0 1|
 ^ ^ ^
 | | +- Zw = [0,0,1]
 | +--- Yw = [0,1,0]
 +----- Xw = [1,0,0]

As you can see, for a normal untransformed spaces it's quite obvious that
the world axises have coords [1,0,0] (the x-axis), [0,1,0] (the y-axis),
[0,0,1] (the z-axis).

Important: Conslusion, each column in the rotation matrix gives us the
coordinates for each of the unit axises in our transformed space, described
in the untransformed space's coordinates.

More generally the rotation matrix:

     |Rxx, Ryx, Rzx|
Mr = |Rxy, Ryy, Rzy|
     |Rxz, Ryz, Rzz|
       ^    ^    ^
       |    |    +- Zw = [Rzx, Rzy, Rzz]
       |    +------ Yw = [Ryx, Ryy, Ryz]
       +----------- Xw = [Rxx, Rxy, Rxz]

I.e. the world axises for our rotated space expressed in our current
untransformed space coordinates are:

Xw = [Rxx, Rxy, Rxz]
Yw = [Ryx, Ryy, Ryz]
Zw = [Rzx, Rzy, Rzz]

Ok, enough about rotation matrices and world axises. If you don't get it,
re-read and only move forward until you really get this.



2) Deriving the vertices for the unit cube using the rotation matrix

The coordinates for a unit cube are:

p1 = [ 1,  1,  1 ]
p2 = [ 1,  1, -1 ]
p3 = [ 1, -1,  1 ]
p4 = [ 1, -1, -1 ]
p5 = [-1,  1,  1 ]
p6 = [-1,  1, -1 ]
p7 = [-1, -1,  1 ]
p8 = [-1, -1, -1 ]

By symmetry we quickly se that it can be reduced to:
p1 = [ 1,  1,  1 ]
p2 = [ 1,  1, -1 ]
p3 = [ 1, -1,  1 ]
p4 = [ 1, -1, -1 ]
p5 = -p4
p6 = -p3
p7 = -p2
p8 = -p1

So, we really only need to calculate p1-p4. Let's consider p1 first:

p1 = [1,1,1]

Remeber the unit matrix:

|1 0 0|
|0 1 0|
|0 0 1|
 ^ ^ ^
 | | +- Zw = [0,0,1]
 | +--- Yw = [0,1,0]
 +----- Xw = [1,0,0]


Xw+Yw+Zw = [1,0,0] + [0,1,0] + [0,0,1] = [1,1,1] = p1

As you see, by simply adding the world axises you get a corner of the unit
cube. It's quite obvious; to get from origo to a corner of a cube you need
to take one step in each dimension.

For p1-p4 we get:

Xw+Yw+Zw = [1,0,0] + [0,1,0] + [0,0,1] = [ 1,  1,  1 ] = p1
Xw+Yw-Zw = [1,0,0] + [0,1,0] - [0,0,1] = [ 1,  1, -1 ] = p2
Xw-Yw+Zw = [1,0,0] - [0,1,0] + [0,0,1] = [ 1, -1,  1 ] = p3
Xw-Yw-Zw = [1,0,0] - [0,1,0] - [0,0,1] = [ 1, -1, -1 ] = p4

Now, in general rotation matrix form:

     |Rxx, Ryx, Rzx|
Mr = |Rxy, Ryy, Rzy|
     |Rxz, Ryz, Rzz|
       ^    ^    ^
       |    |    +- Zw = [Rzx, Rzy, Rzz]
       |    +------ Yw = [Ryx, Ryy, Ryz]
       +----------- Xw = [Rxx, Rxy, Rxz]

Hence we get:

Xw+Yw+Zw = [Rxx, Rxy, Rxz] + [Ryx, Ryy, Ryz] + [Rzx, Rzy, Rzz] = [Rxx+Ryx+Rzx, Rxy+Ryy+Rzy, Rxz+Ryz+Rzz] = p1
Xw+Yw-Zw = [Rxx, Rxy, Rxz] + [Ryx, Ryy, Ryz] - [Rzx, Rzy, Rzz] = [Rxx+Ryx-Rzx, Rxy+Ryy-Rzy, Rxz+Ryz-Rzz] = p2
Xw-Yw+Zw = [Rxx, Rxy, Rxz] - [Ryx, Ryy, Ryz] + [Rzx, Rzy, Rzz] = [Rxx-Ryx+Rzx, Rxy-Ryy+Rzy, Rxz-Ryz+Rzz] = p3
Xw-Yw-Zw = [Rxx, Rxy, Rxz] - [Ryx, Ryy, Ryz] - [Rzx, Rzy, Rzz] = [Rxx-Ryx-Rzx, Rxy-Ryy-Rzy, Rxz-Ryz-Rzz] = p4

So, we have now stated that given a general rotation matrix you can derive all eight vertices of a cube by simple additions. (Good for a C64!!)



3) Deriving the normals of the faces of the unit cube using the rotatio matrix:

For filled vectors we must do backface culling, and the approach I'll give will use the face normals hence we need to derive them.

The coordinates for the 6 face normals are:

n1 = [  1,  0,  0 ]
n2 = [ -1,  0,  0 ]
n3 = [  0,  1,  0 ]
n4 = [  0, -1,  0 ]
n5 = [  0,  0,  1 ]
n6 = [  0,  0, -1 ]

By symmetry:

n1 = [  1,  0,  0 ]
n2 = -n1
n3 = [  0,  1,  0 ]
n4 = -n3
n5 = [  0,  0,  1 ]
n6 = -n5

Remeber the unit matrix:

|1 0 0|
|0 1 0|
|0 0 1|
 ^ ^ ^
 | | +- Zw = [0,0,1]
 | +--- Yw = [0,1,0]
 +----- Xw = [1,0,0]

As you can see:

Xw = [1,0,0] = n1
Yw = [0,1,0] = n3
Zw = [0,0,1] = n5

Now, in general rotation matrix form:

     |Rxx, Ryx, Rzx|
Mr = |Rxy, Ryy, Rzy|
     |Rxz, Ryz, Rzz|
       ^    ^    ^
       |    |    +- Zw = [Rzx, Rzy, Rzz]
       |    +------ Yw = [Ryx, Ryy, Ryz]
       +----------- Xw = [Rxx, Rxy, Rxz]

Hence we get:

Xw = [Rxx, Rxy, Rxz] = n1
Yw = [Ryx, Ryy, Ryz] = n3
Zw = [Rzx, Rzy, Rzz] = n5



To sum 2) and 3) up, the coordinates for all eight vertices and all six normals expressed in rotational matrix terms are:

Xw+Yw+Zw = [Rxx, Rxy, Rxz] + [Ryx, Ryy, Ryz] + [Rzx, Rzy, Rzz] = [Rxx+Ryx+Rzx, Rxy+Ryy+Rzy, Rxz+Ryz+Rzz] = p1
Xw+Yw-Zw = [Rxx, Rxy, Rxz] + [Ryx, Ryy, Ryz] - [Rzx, Rzy, Rzz] = [Rxx+Ryx-Rzx, Rxy+Ryy-Rzy, Rxz+Ryz-Rzz] = p2
Xw-Yw+Zw = [Rxx, Rxy, Rxz] - [Ryx, Ryy, Ryz] + [Rzx, Rzy, Rzz] = [Rxx-Ryx+Rzx, Rxy-Ryy+Rzy, Rxz-Ryz+Rzz] = p3
Xw-Yw-Zw = [Rxx, Rxy, Rxz] - [Ryx, Ryy, Ryz] - [Rzx, Rzy, Rzz] = [Rxx-Ryx-Rzx, Rxy-Ryy-Rzy, Rxz-Ryz-Rzz] = p4
p5=-p4
p6=-p3
p7=-p2
p8=-p1

Xw = [Rxx, Rxy, Rxz] = n1
n2 = -n1
Yw = [Ryx, Ryy, Ryz] = n3
n4 = -n3
Zw = [Rzx, Rzy, Rzz] = n5
n6 = -n5



4) Back face culling by checking which side the eye is of a plane

First consider the plane equation:

A*x+B*y+C*z+D = 0

[A,B,C] = plane normal
[x,y,z] = reference point to test
D = distance from origo to the plane expressed in negative normal lengths.

If [x,y,z] is chosen to be exactly on the plane the equation will be =0.
If [x,y,z] is chosen to be below the plane, i.e. on the anti-normal side, the equation will be <0.
If [x,y,z] is chosen to be above the plane, i.e. on the normal side, the equation will be >0.

Consider one of the faces of the unit cube, for example the face with a normal n1.

n1 = [1,0,0] = [A,B,C]
D = -1 since the distance negative distance from origo to the unit cube's faces are exactly one normal in length.

1*x + 0*y + 0*z - 1 = 0

If we chose an [x,y,z] that should lie in the plane, for example [1,0,0] we get:

1*1 + 0*0 + 0*0 - 1 = 1-1 = 0

If we chose an [x,y,z] that lies below the plane, for example [0,0,0] we get:

1*0 + 0*0 + 0*0 - 1 = 0-1 = -1

If we chose an [x,y,z] that lies above the plane, for example [10,0,0] we get:

1*10 + 0*0 + 0*0 - 1 = 10-1 = 9

As you can see, the experimental values coincide with what we stated above.


Now let's consider how to use this for backface culling:

If you eye is on the normal side of a plane we consider the plane visible, i.e. if the result of Ax+By+Cz+D > 0 the plane is considered visible.

More over, let's assume the object rotated around origo and that the eye is fixed at a distance say [0,0,-3] (typical for c64 vectors) we get:

A*0 + B*0 + C*-3 + D > 0


I.e. to determine if a plane A,B,C,D is visible, simply calculate A*0+B*0+C*-3+D and check if it's positive. Or to simplify: C*-3+D > 0.


Now, as I stated before, for the unit cube the negative distance to all faces from origo is -1. I.e. D=-1 for all planes of the unit cube in origo. This reduced our check to:

C*-3-1 > 0

Shuffle around:

C > 1/-3


Let's call 1/-3 for e. e = 1 / -distance to object (still assuming unit cube where D=-1 for all planes).



5) Combine 3) and 4) to get useful results for a c64 vector:

We've stated that D=-1 for all 6 planes of the unit cube.

We've stated that the normal vectors for all 6 planes of the unit cube expressed in general rotation matrix form are:

Xw = [Rxx, Rxy, Rxz] = n1
n2 = -n1
Yw = [Ryx, Ryy, Ryz] = n3
n4 = -n3
Zw = [Rzx, Rzy, Rzz] = n5
n6 = -n5

We've fixed the eye position at [0,0,-3] giving us an e-value of e=1/-3.

We've stated that if C>e then the plane is visible.

We've stated that [A,B,C] is the coordinats of a plane normal.

I.e. to determine if n1 is visible:

Check if: Rxz > e

For all faces:

n1: Rxz > e
n2: -n1 > e = -Rxz > e = Rxz <= e
n3: Ryz > e
n4: -n1 > e = -Ryz > e = Ryz <= e
n5: Rzz > e
n6: -n1 > e = -Rzz > e = Rzz <= e



6) Conclusion

We've shown that giving the rotational matrix we can derive all 8 vertices of the unit cube by simple additions.
We've further shown that we can also derive all 6 face normals by simply extract the world axises.
We've shown that assuming a fixed eye position at [0,0,-z] we can simply compare the z-component of a face normal with a constant (e).
We've shown how to calculate e properly.

If you wonder how to calculate a rotational matrix quickly on the C64 I recommend you read Krill's 3d-math tutorials.


Have fun!
2007-12-07 16:36
Cruzer

Registered: Dec 2001
Posts: 1048
Doing stuff like this in realtime on C64 in a demo where you don't need interactivity and therefore can predict everything is pretty stupid, since it can be precalculated and packed down to almost nothing.

All you need to do is calculate the initial visibility state of each face, and then make a table for each face for the number of frames before it switches state. E.g. if you have a cube with 6 faces, where each face on average changes state 20 times = 120 bytes, +6 for the initial states. And it's fast to look up too.
2007-12-07 19:24
Oswald

Registered: Apr 2002
Posts: 5094
demos are about showing off. what are you showing off with an animation? not much.
2007-12-07 19:48
Danzig

Registered: Jun 2002
Posts: 440
@oswald: hm, imho "glenz each frame" shows off :D
2007-12-07 20:14
Oswald

Registered: Apr 2002
Posts: 5094
danzig, imho stamp sized, every 2nd line, semi animations are not impressive. there are other routines by cruzer which I like, but not this one. anyways tastes are different I prefer fullscreen and realtime instead of small 50fps semi animations.
2007-12-07 22:15
JackAsser

Registered: Jun 2002
Posts: 2014
Quote: Doing stuff like this in realtime on C64 in a demo where you don't need interactivity and therefore can predict everything is pretty stupid, since it can be precalculated and packed down to almost nothing.

All you need to do is calculate the initial visibility state of each face, and then make a table for each face for the number of frames before it switches state. E.g. if you have a cube with 6 faces, where each face on average changes state 20 times = 120 bytes, +6 for the initial states. And it's fast to look up too.


You mean just "animate" the hidden surface states or animate all coords? Because if you only animate the surfaces states and calculate the rest, then a matrix z-cmp is still faster... ;D But I guess you meant to animate everything.
2007-12-07 22:42
Nightlord
Account closed

Registered: Jan 2003
Posts: 131
cruzer: no matter how you approach it i do not think doing realtime vectors in C64 is stupid dude :)
2007-12-08 13:30
Cruzer

Registered: Dec 2001
Posts: 1048
Oswald: Showing off doesn't count in my book if it produces no visible difference on the screen. If you wanna make something that couldn't be done as an "animation" then cool, but if it's a vector cube running for 256 frames I think it's stupid to do coord calculation and especially hidden face status in realtime.

JackAsser: I was actually only talking about hidden face status, although I usually precalculate everything since I prefer something that is smooth and runs for a short time rather than the opposite, but that's another story. Even if I was to do the coord calculations in realtime, I would assume it would still be faster to precalc the hidden states, even though I must admit I haven't researched it much, and I don't know what matrix z-cmp means. But are you sure it's faster than this?
	ldx frameLo
!:	cpx visibilityTable0
	bne !+
	lda faceVisible+0
	eor #1
	sta faceVisible+0
	inc !- +1
!:	cpx visibilityTable1
	bne !+
	lda faceVisible+1
	eor #1
	sta faceVisible+1
	inc !- +1
!:	cpx visibilityTable2
	bne !+
	...
This routine would work even if the effect is longer than 256 frames, as long as each face maximum has the same visibility status for 256 consecutive frames. It takes 7 cycles/face when no change occurs, and 20 when it changes state. Including the initial ldx I get this to 45 cycles when there's no change, and when a face switches, which probably mostly happens one at a time, it would be 58 cycles total. Less than a rasterline - can you beat that?

It could actually be even faster if the status was stored as bits in one byte rather than individual bytes, but then the precalced table would have to be about twice as long, and it would probably also be slower for each line to figure out whether it needs to be drawn and in which color.
Previous - 1 | 2 | 3 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Andy/AEG
rambo/Therapy/ Resou..
Icon/TRIAD
cba
Twilight/Excess/Arcade
Twoflower/ΤRIΛD
grennouille
Alakran_64
Guests online: 124
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 The Demo Coder  (9.6)
6 Edge of Disgrace  (9.6)
7 What Is The Matrix 2  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.7)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 X-Mas Demo 2024  (9.5)
7 Dawnfall V1.1  (9.5)
8 Rainbow Connection  (9.5)
9 Onscreen 5k  (9.5)
10 Morph  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)
Top Musicians
1 Rob Hubbard  (9.7)
2 Mutetus  (9.7)
3 Jeroen Tel  (9.7)
4 Linus  (9.6)
5 Stinsen  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.07 sec.