Vertex rotation math

[ar81]

If you wonder how to do 3D rotation,  you know C++ and how to code, but you do not master math, here it is a
common way to rotate in 3D around a vector.  I will guess that C++ calculates sine and cosine using angles
expressed in radians

We have

Pivot point = (xr,yr,zr)
Vector = (Vx,Vy,Vz)
Angle in degrees

Non rotated Vertex = (x0,y0,z0)

Step 1.  Convert angle to radians

Angle in radians = Angle in degrees * Pi / 180

Step 2. Precalculate rotation matrix
We have a matrix that looks like
| a  b  c |
| d  e  f |  
| g  h  i |

The values of the matrix are

a = 1 + (1-cos(angle))*(Vx*Vx-1)
b = -Vz*sin(angle)+(1-cos(angle))*Vx*Vy
c = Vy*sin(angle)+(1-cos(angle))*Vx*Vz
d = Vz*sin(angle)+(1-cos(angle))*Vx*Vy
e = 1 + (1-cos(angle))*(Vy*Vy-1)
f = -Vx*sin(angle)+(1-cos(angle))*Vy*Vz
g = -Vy*sin(angle)+(1-cos(angle))*Vx*Vz
h = Vx*sin(angle)+(1-cos(angle))*Vy*Vz
i = 1 + (1-cos(angle))*(Vz*Vz-1)

If you do not know what is a rotation matrix, do not worry.
There are several methods to do some rotations, one of them is using a rotation matrix, which is a set of data that is used for rotation as described here.

The following steps must be done for every vertex

Step 3. Make pivot point to be (0,0,0)

(x,y,z) = (x0-xr,y0-yr,z0-zr)

Step 4. Rotate the vertex

x1 = x * a + y * b + z * c
y1 = x * d + y * e + z * f
z1 = x * g + y * h + z * i

Step 5. Make pivot point not to be (0,0,0)

(x2,y2,z2) = (x1+xr,y1+yr,z1+zr)

The resulting rotated vertex is...

Rotated vertex = (x2,y2,z2)

----------------------------------
Tip:
Sine and Cosine functions are very processor time consuming.
It is better to create an array (let's say 3600 elements in the array to have a precision of 0.1 degrees) and
precalculate both sine and cosine and store those values.
It is faster to retrieve values from an array than to calculate those values every single time.
But it will consume RAM.  Anyway, if you have 512Mb RAM, 2 arrays of 3600 double precision elements may not be a
big problem, and you will gain in performance.



Post Edited ( 12-20-07 20:42 )

[Urwumpe]

Don't believe ar81 on the sine and cosine table. your processor can calculate the sine faster and more accurate as you can
look it up in a table. And that since the good old Pentium processor (Pentium was generally as fast as looking the data up in
a table, with 16 cycles for trivial angles).

All processors already have such tables and a very clever math to increase accuracy inside them.

If you want to stay fast on a modern PC, just help it help you... keep your angles small. A calculation with angles from -45°
to +45° is faster on a PC as with angles above 360°.

But also, its better to make your computer use the trigonometric  functions as rare as possible, by using vector calculations - modern CPUs with MMX or 3Dnow know special operations, which speed up vector math a lot and your compiler can use.

Also the vector math can be memorized much simpler as shown. But I would have to explain this in OrbiterWiki, they require
some graphics.

The rotation matrix can eg be created as a sum of three simple matrices, which are easier to memorize. Also for many
scenarios, you don't need a general rotation matrix, but just the rotation around a basic axis, which are also simpler to
remember.



Message modifié ( 21-12-2007 00:22 )

[ar81]

Don't believe ar81 on the sine and cosine table

Then don't believe the programmer who told me that....

What is certain is that such a math is useful, and you may simplify the way you want it.
As I said there are several ways to reach the same result.
I was just pointed out concepts.

Oh, and BTW Urwumpe, nice work with the Anim8tor script.
I tested it and looks good.

I know you were being trying to put down Mesh Wizard in the past as if it was a competition for your script, but I am
not competing.  People may choose to use whatever they want.  I feel a bit disappointed to see that such unhealthy
spirit of competition is still present.

And instead of engaging you in a fight, I wish you the best, and I congratulate you for your work.
But with your actions I can't help but to feel disappointed of "developed" countries where I see the same
underdeveloped country' attitudes I see here.

You know what?  
I got a hamster lately.  I bought two, thinking that at least I would see a good example of good relations between
animals, but one of them killed the other.  I realized that having two hamsters is like having two crocodiles.  I realized
that animals do not understand evil, but humans do (or at least that's what I used to think) and yet you see people
acting like a hamster.

I would love to see a community, some civilized place where people can share, and where I can feel that humans are
not a bunch of animals, like my hamsters.  Sometimes when I post in the net feel like exchanging words with a race of
crocodiles.  I have seen dark things in humans, mistreatment, harassment, exploited people, racism with very
dramatic cases of people I know.  And you are not helping to restore my faith in humanity.

But I do not return evil, I return good.  So have a merry christmas and a happy new year.

[Urwumpe]

Well, you can try turn it into a personal attack, including a lot of pathetic trolling (don't wish me a nice Xmas, in the same post where you try to attack me personally and nationalistic. Its even more unfriendly as staying serious.), but just believe me that the
trigonometric functions are not the evil you make them. Just look up the cycle times for a modern CPU - the book i used
yesterday was from 1995, before the invention of such cool stuff like MMX or 3Dnow.

You can for example read about modern CPU optimization here:

http://www.cs.cornell.edu/courses/cs412/2001sp/resources/Pentium%20Processor%20Optimization.pdf

Remember: Accessing data in RAM takes much longer as looking up data inside the CPU (modern RAM is still about 20-60 times slower as a typical CPU). So unless you can store the full table somewhere in cache, its useless. And you never have
enough cache to store 25,000 vertex points, the rotation matrix and all other needed information.

The hint of using tables for trigonometric functions comes from a time, when there had been no Floating Point Units included in CPUs - about the early 1990s - and when it was needed to calculate the sine by iteratively  solving a series until the error was so low that it does not hurt anymore (about 1000 loops for getting the same accuracy as the FPU of a current PC delivers). And even then, you had people who found ways to calculate a sine faster, than by using software (eg by using the sine tables inside the DSP of the Atari Falcon...that had been times).

Since then, it became common to just fill a matrix with constant values of sine and cosine, without wasting cycles for
looking these up in a table. If you use the right functions of your C++ compiler, you don't even need to know assembler - the compiler sorts and optimizes the mathematical operations for you (most better compilers can already produce good  SIMD code automatically).

So, we are back on the first rule of software development: Debugging comes before optimization. Make your code
straight forward first, achieves all requirements, avoid useless optimizations and find out then, at which point you spend
most of your run-time. I remember one anecdote from Microsoft, where an Excel team in the 1980s spent 4 weeks for developing an optimization, which saved only 90 µSeconds during a 2 hours test. Of course, they later kept the old version, because it was better readable for the developers.

And no, I don't need to compete with mesh wizard. Or does it convert from an8 to msh now? Can it optimize meshes by avoiding material changes? If I remember correctly, the omitting of material and texture change information recommended in the mesh format standard caused problems for your applications, Orbiter did not have...

PS: You have a pretty bad opinion about your hamsters.  Don't insult them by comparing them to humans...

PPS: If you would come from the same country as I come, my reaction would have been less far friendly. I know what is taught in schools here and what I can expect....



Message modifié ( 21-12-2007 15:17 )

[ar81]

including a lot of pathetic trolling

...and you are not helping to restore my faith in humanity.  That is rude.
You may decide to help people or to add more load to people and make them feel bad.  
I have seen many inhuman acts, from criminal attacks to harassment, people enslaved, abuses that would freak people out...

I quit the M6 forums because I was tired of people who do not help me to restore my faith in humanity.
If I returned the evil I have seen and suffered, I would be part of the problem.
So I decided to share the product of my work and to deliver a different way to see life to people.
But in the end I do not have faith in humanity, and you are not helping.
This is not pathetic, this is REAL.

But with your actions I can't help but to feel disappointed of "developed" countries where I see the same
underdeveloped country' attitudes I see here.

If you feel it is nationalistic, then I am insulting my own country too.
You say that you may see not good things at schools, so indeed I was right.



Post Edited ( 12-21-07 15:45 )

[Urwumpe]

Yes, you reduce me to my nationality. Thats nationalism. It is not important if somebody from a developed country reduces
somebody from a so called developing country to his country or the other way around. if you want to argue free from
nationalism, you need to watch others without knowing their country. You could be from Spain, and still appear not wiser.
Where you come from is a nice to know, but what you do and say, is all that matters.

And calling something pathetic pathetic is not rude - just honest. "In rhetoric, pathos is the use of emotional
appeals to alter the audience's judgment. A common use of pathos in argument is creating a sense of rejection if the audience
doesn't agree. Creating a fear of rejection is in essence, creating a pathos argument."

[ar81]

What is certain is that I feel bad now. Bad things in my personal life. After good news come bad news. And I came to
M6 and now here and people add more load.  That's the fact now.

[Urwumpe]

I feel good... only a few hours until my Christmas holidays begin.

(Now, ain't that evil? )



Message modifié ( 21-12-2007 16:08 )

[GXE3]

I was seriously thinking about staying out of this, but GUYS, COME ON.
There's no need to be arguing like this, it's almost Christmas. Besides everyone is entitled to there own opinion whether it
may be how to calculate something or how to program software.

ar81, don't quit Dan's forums like you did M6 forums. The fact of the matter is, a lot of people have learned something about
Orbiter and about programming just because you responded to their posting. I'm one of them.

Have a Merry Christmas
BOTH OF YOU!

[computerex]

Quite an amusing conversation. Ar81, please explain why you insulted the entire world a couple of times just in this thread?
You lost your faith in humanity eh? You know who that sounds like? The killers of the recent school shootings...One even wore
a shirt that said "Humanity is overrated".



Post Edited ( 12-22-07 16:28 )

[Urwumpe]

Well, christmas is a pretty stressful time, if you do it wrong. Maybe somebody develops the wish to be no longer part of
humanity. In that case...

http://break.com/index/achmed-sings-christmas-songs.html

[Pirx]

Terrible things seem to happen on orbinaut forums during the weekends (also on M6 a week or two ago). Must be
the loneliness of space

If we return to the original topic of the discussion, it is always better to test. So the ones of you brave enough can
download and run the following test:
http://www.sendspace.com/file/jid2fi
* Run from the command prompt.
* Computes the sum of sine and cosine squared for 15000 values with table look-up or FPU.
* Source code included (Open Watcom compiler required).
* Assembly listing included in case there are doubts about code optimization.

At least on my AMD CPU and even on AMD Phenom, if we trust AMD data sheets, the FPU computation of sine and
cosine seems to be 100+ cycles. Wouldn't be able to test on Intel until January.


P.S.: You are not nice people making me remember 80x87 instructions just before Christmas

[Tachyon]

AR81 & Urwumpe  - don't make me come over there and separate you two.....

.....  where's the love man?  (80's beer commercial)  

But seriously - sometimes it's not what you say but how you say it.. While AR81's method for calculating that vertex
rotational thingy may not be bleeding edge method due to "other" ways and "hardware" improvements that can be
exploited - opening your response Urwumpe with "Don't believe ar81 on the sine and cosine table" is a fairly
aggressive and easily perceived "attack" on the previous author (whomever it might have been). I think this is called -
first blood.

Now AR81's response to you, if it was in fact an a retaliatory attack, appeared to me to be an attempt to defuse what
could turn out to be a flame fest ......  

Now I don't really "know" either of you other than seeing your names here frequently. I'd like to assume that you're
both reasonably mature adults (young adults?) Please for the health of the community here, let it go .... it ain't worth
it.



"to hell with world peace - imagine using your turn signal !"    [insert laugh track]

[ar81]

I should tell you that I do not believe in humanity.
And the way I "shoot" is trying to keep my corner of the world clean of evil.
Instead of shooting, what I do is to show other people that we can help each other, one of the many reasons why I
make addons.  The best addons I have made came out of a time of crisis.

As I said, sometimes people behave as if they had the brain of hamsters.

In 2006 I had to face some people who were doing evil things.
In recent days I knew that what I did to stop them did not work.
So I do not know what to think... it looks like a surreal story from Heavy Metal where everything ends up being
wrong, unhappy endings, evil wins.  I will leave it in the hands of God from now on.  The world is not my business
anymore.

But it doesn't make me to have more faith in humanity.
And one thing that discourages more is that someone in some other corner of the world likes to add some load to
people who feel like that.  It tells me I can't count on anyone, or just a few ones.

I even do good things and people jump on me, even at M6.  
What do you want me to do?  Shooting someone?
Fortunately I am not a follower of violence.  I am against any form of violence.
At most you may see a shooting of bytes... files being converted from MSH to OBJ format in my hard disk (that's
violence, man).

But I do not believe in human being too much since 2006 (one of the most horrible years of my life), but recent days
shows me that justice does not exist, and tells me that evil wins most of times.  Keeping my corner of the world clean
means I am trying to surround myself with good people, the few ones who show themselves human.  That's why I
left M6, but I keep being followed by those are not worthy to be in my world.  

For some reason I see one good thing in my life, and then 2 bad ones.
In a world infested with evil, shooting will not solve anything, just survive and surround yourself with good people, to
see if that makes myself to recover faith in humanity.

Thanks God I have found some good people here.
I think I have not recovered from 2006.
Thanks to all those who supported me with their words, to make me keep walking.  
That is quite great christmas gift.

I do have some good surprise for new year, when I will have the chance to upload...
Not really a big thing, but somehow helpful for you, people.



Post Edited ( 12-29-07 00:30 )

[reekchaa]

I think "Good/God" and "Evil" come with very complex philosophies that intrisically spur dissent with everyone, but I
really appreciate what you're trying to share with us, ar81.

Anyone who has a different way of thinking has the courage to be respected for his/her opinion.

[ar81]

It was evil enough to make my american and french friends to agree with me.

[Pirx]

A lot about human soul but not much about vertex rotation math

Also, nobody seems bold enough to try my program but you are not going to get away that easily...

Intel PIV needs 200+ cycles for the combined sin+cos calculation. Core 2 averages 100+. I must say I was rather
surprised by these results. My initial expectations were very much like  Urwumpe's.

Edit: There was an error in the numbers above. Now corrected.

On a positive note it seems Visual C++ 2008 provides some good performance improvements for floating-point
computations if you compile your code with /arch:SSE2 (the result will only run on PIV/Athlon 64 or later). No, of
course, no automatic vectoring of computations, just using an XMM register for a single floating point number. I
wonder if Martin will be successful with the migration of Orbiter to VS 2005 or 2008

http://orbit.m6.net/Forum/default.aspx?g=posts&t=16971



Post Edited ( 01-03-08 10:40 )