6502.org • View topic - C=Hacking Issue #8

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

C=Hacking Issue #8

Page 1 of 2

[ 22 posts ]

Go to page 1, 2 Next

Previous topic | Next topic

Author

Message

A0CBM

Post subject: C=Hacking Issue #8

Posted: Tue Nov 05, 2019 8:52 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

Does anyone know how to explain some of the methods used on "A different perspective - 3D Graphics on the C64"? I know how to do the matrix math, but computer graphics wasn't a thing when I was in college. He talks about double checking his math and shows a 3 X 3 matrix, but I just don't follow it all. They should be a transformation matrix of sorts, I guess I'm not seeing where the numbers all come from.

Top

BigEd

Post subject: Re: C=Hacking Issue #8

Posted: Tue Nov 05, 2019 10:11 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10940
Location: England

Any relation to the explanations in these articles?
http://retro64.altervista.org/blog/3d-g ... basic-c64/
http://retro64.altervista.org/blog/an-i ... d-objects/

Edit: found the original article you mentioned:
http://csbruce.com/cbm/hacking/hacking08.txt
A Different Perspective: Three-Dimensional Graphics on the C64 -- by Stephen Judd and George Taylor (C64)

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Wed Nov 06, 2019 12:43 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

I'll look at those articles and see if they help.

One question that I have is that all the rotations can be by one matrix, which is made of all three axis matrices multiplied together into one matrix. I believe that multiplication is a cross product, not a dot product, which is how I think the values of T1..T10 are calculated.

Top

BigEd

Post subject: Re: C=Hacking Issue #8

Posted: Wed Nov 06, 2019 12:52 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10940
Location: England

For context, here's a relevant snippet of the 1994 article A Different Perspective: Three-Dimensional Graphics on the C64 by Stephen Judd and George Taylor:

Quote:

"But," you may say, "we have to do the same number of multiplications to get
M as we do to apply each rotation separately! How is this supposed to
help?" This is how it is supposed to help:

1) We now have a single matrix which describes ALL the rotations.
For a single point we haven't gained much, but if we have
a lot of points (and a cube has eight), transforming every
point is now a single matrix multiplication. In other words,
if we have a lot of points to transform we get a HUGE savings
computationally.

2) We can take advantage of trigonometric identities and in so
doing make the computation of M very simple.

Computationally speaking, this is known as a "good idea".

To multiply the three rotation matrices together, we need to take advantage
of a few trigonometric properties. We need the two identites mentioned
earlier:

sin(a+b) = sin(a)cos(b) + cos(a)sin(b)
cos(a+b) = cos(a)cos(b) - sin(a)sin(b)

We will also use the fact that cosine is even and sine is odd, that is

cos(-a) = cos(a)
sin(-a) = -sin(a)

Using the above identities it is easy to see that

sin(a)sin(b) = (cos(a-b) - cos(a+b))/2
cos(a)cos(b) = (cos(a+b) + cos(a-b))/2
sin(a)cos(b) = (sin(a+b) + sin(a-b))/2

We are going to rotate first around the z-axis by an amount sz, then the
y-axis by an amount sy, then the x-axis by an amount sx. Why rotate in that
order? Why not.

M = XYZ

If you multiply everything out (and I encourage you to do so, not only for
practice, but also as a double-check of my work), and use the above trig
identities, the result is:

[A B C]
M = [D E F]
[G H I]

Where
A = (cos(t1)+cos(t2))/2
B = (sin(t1)-sin(t2))/2
C = sin(sy)
D = (sin(t3)-sin(t4))/2 + (cos(t6)-cos(t5)+cos(t8)-cos(t7))/4
E = (cos(t3)+cos(t4))/2 + (sin(t5)-sin(t6)-sin(t7)-sin(t8))/4
F = (sin(t9)-sin(t10))/2
G = (cos(t4)-cos(t3))/2 + (sin(t6)-sin(t5)-sin(t8)-sin(t7))/4
H = (sin(t3)+sin(t4))/2 + (cos(t6)-cos(t5)+cos(t7)-cos(t8))/4
I = (cos(t9)+cos(t10))/2

with
t1 = sy-sz
t2 = sy+sz
t3 = sx+sz
t4 = sx-sz
t5 = sx+sy+sz = sx+t2
t6 = sx-sy+sz = sx-t1
t7 = sx+sy-sz = sx+t1
t8 = sy+sz-sx = t2-sx
t9 = sy-sx
t10= sy+sx

How is this supposed to be the "simplified" version? If you look closely,
there are no multiplies. We can calculate the entire rotation matrix M in
about the same time as it would take to do two multiplications. This also
means that the associated problem with multiplications, loss of accuracy, is
now gone.

(When we multiply two vectors, indeed there are two ways of doing it, resulting in the dot product or in the cross product. But when we multiply two matrices, there's one way to do it, which results in a matrix. If we start with two square matrices, we again get a square matrix, of the same size.)

Top

John West

Post subject: Re: C=Hacking Issue #8

Posted: Wed Nov 06, 2019 1:26 pm

Joined: Tue Sep 03, 2002 12:58 pm
Posts: 325

There's a LOT of work omitted in "If you multiply everything out (and I encourage you to do so, not only for practice, but also as a double-check of my work), and use the above trig identities". It's not remotely obvious where the final form of the matrix comes from. If you want to understand those expressions, the only way to do it is the hard way: multiply out those three matrices and apply the trig identities yourself. It'll be a lot of work, and it will be very easy to make mistakes. And, honestly, it's not really worth it.

You'll need to know how to multiply matrices first, which you can find in every introduction to linear algebra. It's not a dot or cross product, because those concepts only work for vectors. A matrix product is a matrix product.

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Wed Nov 06, 2019 4:39 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

I'm glad to see people that know of the math I seek help with. I went through the process of multiplying the matrices that represent the total 3D rotation and when I was done, I had this:

[ cos(B)cos(B) 0 0 ] [ X1 ]
[ 0 cos(B)cos(B) 0 ] [ Y1 ]
[ 0 0 cos(B)cos(B) ] [ Z1 ]

Does anyone know if this is correct for a Cartesian coordinate where X1,Y1,Z1 are vectors? Will this get through each of the rotations involved in a 3D rotation?

Top

dmsc

Post subject: Re: C=Hacking Issue #8

Posted: Thu Nov 07, 2019 12:40 am

Joined: Mon Sep 17, 2018 2:39 am
Posts: 137

Hi!

A0CBM wrote:

That can't be correct, as rotation matrices have a determinant == 1, and yours don't.

Top

John West

Post subject: Re: C=Hacking Issue #8

Posted: Thu Nov 07, 2019 11:00 am

Joined: Tue Sep 03, 2002 12:58 pm
Posts: 325

OK, I'll give it a go. We start with three rotation matrices:

Code:

    [  cos(a) -sin(a)       0 ]
X = [  sin(a)  cos(a)       0 ]
    [       0       0       1 ]

    [       0       0       0 ]
Y = [       0  cos(b) -sin(b) ]
    [       0  sin(b)  cos(b) ]

    [  cos(c)       0  sin(c) ]
Z = [       0       1       0 ]
    [ -sin(c)       0  cos(c) ]

First, multiply Y*Z:

Code:

     [ 0*cos(A)+0*0+0*-sin(c)                       0*0+0*1+0*0            0*sin(c)+0*0+0*cos(c) ]
YZ = [ 0*cos(A)+cos(b)*0+-sin(b)*-sin(c) 0*0+cos(b)*1+-sin(b)*0 0*sin(c)+cos(b)*0+-sin(b)*cos(c) ]
     [ 0*cos(A)+sin(b)*0+cos(b)*-sin(c)   0*0+sin(b)*1+cos(b)*0  0*sin(c)+sin(b)*0+cos(b)*cos(c) ]

     [              0     0               0 ]
   = [  sin(b)*sin(c) cos(b) -sin(b)*cos(c) ]
     [ -cos(b)*sin(c) sin(b)  cos(b)*cos(c) ]

     [                  0      0                  0 ]
   = [  cos(b-c)-cos(b+c) cos(b) -sin(b+c)+sin(b-c) ] / 2
     [ -sin(b+c)+sin(c-b) sin(b)  cos(b+c)+cos(b-c) ]

Then we multiply X by this. I'll only do the top-left element, because that's tedious enough as it is

Code:

    (cos(a)*0+-sin(a)*(cos(b-c)-cos(b+c))+0*(-sin(b+c)+sin(c-b)))/2
    = (-sin(a)*cos(b-c) + sin(a)*cos(b+c))/2
    = (-sin(a+b-c)+sin(a-b+c) + sin(a+b+c)+sin(a-b-c))/4

I've probably gone wrong somewhere (and I don't see how that would simplify to the expression in the article), but hopefully you get the idea.

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Thu Nov 07, 2019 11:53 am

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

Thanks John. I'll go through it again, I'm sure I did something wrong, but I do see you are missing a 1 in the corner of your Y-transformation matrix, which will make a difference.

Top

John West

Post subject: Re: C=Hacking Issue #8

Posted: Thu Nov 07, 2019 1:37 pm

Joined: Tue Sep 03, 2002 12:58 pm
Posts: 325

Yes, that will make a big difference. I knew I'd get something wrong.

I am not doing a dot product. I am (badly) doing matrix multiplication (followed by simplification using trig identities), because these things are matrices. If you haven't come across matrices before and want to understand what's going on here, you will need to learn about them. Almost any introduction to linear algebra will do. If it has the word 'rotation' in the index, it's likely to be a more application-oriented approach.

Matrix multiplication can be implemented as a series of dot products between the row and column vectors of the matrices, and at a more advanced level that's a useful thing to know (it can help with a deeper insight into what's really going on). But for a complete beginner, I think it just confuses things. Forget the dot products. Matrix multiplication is its own thing.

Top

dmsc

Post subject: Re: C=Hacking Issue #8

Posted: Thu Nov 07, 2019 8:52 pm

Joined: Mon Sep 17, 2018 2:39 am
Posts: 137

With proper tools it is not that difficult, using MAXIMA in my Linux console (%i are my inputs, %o are maxima output):

Code:

~$ maxima 

Maxima 5.42.1 http://maxima.sourceforge.net
using Lisp GNU Common Lisp (GCL) GCL 2.6.12
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.

(%i1) MX: matrix(
     [cos(a),-sin(a),0],
     [sin(a),cos(a),0],
     [0,0,1] );

                            [ cos(a)  - sin(a)  0 ]
                            [                     ]
(%o1)                       [ sin(a)   cos(a)   0 ]
                            [                     ]
                            [   0        0      1 ]

(%i2) MY: matrix(
    [cos(b),0,-sin(b)],
    [0,1,0],
    [sin(b),0,cos(b)] );

                            [ cos(b)  0  - sin(b) ]
                            [                     ]
(%o2)                       [   0     1     0     ]
                            [                     ]
                            [ sin(b)  0   cos(b)  ]

(%i3) MZ: matrix(
    [1,0,0],
    [0, cos(c),sin(c)],
    [0, -sin(c),cos(c)]   );

                            [ 1     0        0    ]
                            [                     ]
(%o3)                       [ 0   cos(c)   sin(c) ]
                            [                     ]
                            [ 0  - sin(c)  cos(c) ]

(%i4) MX . MY . MZ;

        [ cos(a) cos(b) ]    [ cos(a) sin(b) sin(c) - sin(a) cos(c) ]    [ (- sin(a) sin(c)) - cos(a) sin(b) cos(c) ]
        [               ]    [                                      ]    [                                          ]
(%o4)   [ sin(a) cos(b) ]    [ sin(a) sin(b) sin(c) + cos(a) cos(c) ]    [   cos(a) sin(c) - sin(a) sin(b) cos(c)   ]
        [               ]    [                                      ]    [                                          ]
        [    sin(b)     ]    [           - cos(b) sin(c)            ]    [              cos(b) cos(c)               ]

(%i5) trigreduce(%);

              cos(b + a)   cos(b - a)
(%o5) matrix([---------- + ----------, 
                  2            2

   cos(c + b + a)    cos(c + b - a)   cos(c - b + a)   cos(c - b - a)
(- --------------) - -------------- + -------------- + --------------
         4                 4                4                4

   sin(c + a)   sin(c - a)     sin(c + b + a)    sin(c + b - a)
 - ---------- + ----------, (- --------------) - --------------
       2            2                4                 4

   sin(c - b + a)   sin(c - b - a)   cos(c + a)   cos(c - a)
 + -------------- + -------------- + ---------- - ----------], 
         4                4              2            2

 sin(b + a)   sin(b - a)     sin(c + b + a)    sin(c + b - a)   sin(c - b + a)
[---------- - ----------, (- --------------) + -------------- + --------------
     2            2                4                 4                4

   sin(c - b - a)   cos(c + a)   cos(c - a)
 - -------------- + ---------- + ----------, 
         4              2            2

cos(c + b + a)   cos(c + b - a)   cos(c - b + a)   cos(c - b - a)   sin(c + a)
-------------- - -------------- - -------------- + -------------- + ----------
      4                4                4                4              2

   sin(c - a)               sin(c + b)    sin(c - b)  cos(c + b)   cos(c - b)
 + ----------], [sin(b), (- ----------) - ----------, ---------- + ----------])
       2                        2             2           2            2

(%i6) string(%);

(%o6) matrix(
[
  cos(b+a)/2+cos(b-a)/2 ,
  (-cos(c+b+a)/4)-cos(c+b-a)/4+cos(c-b+a)/4+cos(c-b-a)/4-sin(c+a)/2+sin(c-a)/2 ,
  (-sin(c+b+a)/4)-sin(c+b-a)/4+sin(c-b+a)/4+sin(c-b-a)/4+cos(c+a)/2-cos(c-a)/2
],[
  sin(b+a)/2-sin(b-a)/2 ,
  (-sin(c+b+a)/4)+sin(c+b-a)/4+sin(c-b+a)/4-sin(c-b-a)/4+cos(c+a)/2+cos(c-a)/2 ,
  cos(c+b+a)/4-cos(c+b-a)/4-cos(c-b+a)/4+cos(c-b-a)/4+sin(c+a)/2+sin(c-a)/2
],[
  sin(b) ,
  (-sin(c+b)/2)-sin(c-b)/2 ,
  cos(c+b)/2+cos(c-b)/2
])

Have Fun!

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Fri Nov 08, 2019 5:19 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

I do get the idea. I'm very rusty and have to check and recheck to make sure I did it right, but It's coming.

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Fri Nov 08, 2019 5:35 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

Code:

          [     cos(y)         -sin(x)(-sin(y))      cos(x)(-sin(y))  ]

XY  =     [     cos(x)            cos(x)               cos(x)cos(y)   ]

          [  cos(x)cos(y)      -sin(x)cos(y)           cos(x)cos(y)   ]

Now it's time for the big one. Multiply by Z. I want to see how rotations are done in assembly on a Commodore computer. Here's my results for a rotation around the Z-axis. You want to check it?

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Sat Nov 09, 2019 5:32 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

That's wrong too.

Top

A0CBM

Post subject: Re: C=Hacking Issue #8

Posted: Mon Nov 11, 2019 12:00 pm

Joined: Wed Nov 04, 2015 11:10 am
Posts: 51

I think I've got math done, but I don't what to do with this:
-sin(z)cos(x) + cos(z)sin(y)sin(x)

after even/odd formulas are applied
sin(-z)cos(x) + cos(z)sin(y)sin(x)

Product to Sum works fine for the term on the left of the + : sin(-z)cos(x).
I don't know how to handle the term on the right: cos(z)sin(y)sin(x), to get rid of the multiplications.

Top

Page 1 of 2

[ 22 posts ]

Go to page 1, 2 Next

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 6 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum