Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Geek Culture / Tough Maths Problem (beware)

Author
Message
Fallout
22
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 17th Jun 2004 14:42
Here's a tough old maths problem that I'll be surprised if anyone can help me with. 3D maths does my nut in. Here goes ...

I have 3 points in 3D space. A centre point (cx,cy,cz), and two other points projecting from this (fx,fy,fz and rx,ry,rz). The distance to these points can obviously be calculated, but is already known (-cf- and -cr-).

The problem I need to solve is an equal shift of the angle to find new positions for f and r respectively. By this I mean, the angle created by the lines -cf- and -cr- needs to be cut in half (note the green line). The two lines need to then be moved equally to result in a right angled triangle, with the right angle at cx,cy,cz. The idea being that I will derive the new positions (fx',fy',fz' and rx',ry',rz') for points f and r.

This would be a relatively simple trig problem in 2D, but this needs to work in 3D. The points can be anywhere in 3D space, and the triangular plane described by the 3 initial points needs to be maintained. i.e. When the new points are derived, they triangular plain must be at the same orientation. (Visualise opening a fan to 90 degrees).



Well, I'm stumped with 3D maths. Anyone?

spooky
22
Years of Service
User Offline
Joined: 30th Aug 2002
Location: United Kingdom
Posted: 17th Jun 2004 15:16
So simple. Here is the answer:



Alternative answer:




Boo!
Van B
Moderator
21
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 17th Jun 2004 16:14
KEEEEVIIIILLLLL!!!!



KE-VIL!!!!




KEVIL!



Nah, he's not here but I'm guessing he'd make mincemeat out of that problem. Maybe IM him at LLRGT.

Maybe though - it need'nt be a case of calculating angles (which is always a pain) - and instead just calculate the vector, basically just the mid point of the 2 projected lines - it looks feasible from your diagram. Then you'd calculate the angles on the mid point instead.


Van-B


The nature of Monkey was irrepressible!.
Fallout
22
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 17th Jun 2004 16:59
Hmm, yeah I've looked at vectors. I've had a few ideas that I've tried, but they all have unexpected results. I know there are some proper 3D math gurus about. I've actually posted this on a few math sites, but nobody has replied yet. Cowards.

kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 17th Jun 2004 17:08
I'm guessing you want the green line to be at 45 degrees?

First question is, how much do I rotate the vectors.
They both have to rotate an equal amount, I'm guessing.

For that, we first need to know then angle between the vectors. I'll call the vectors f and r (f = f - c, r = r - c).
The angle between the vectors is basically calculated using:

dot(f,r)=fx*rx+fy*ry+fz*rz = ||f||*||r||*Cos(angle)
So Angle = Acos(dot(f,r) / |f||*||r||))

If the angle is 90, then we're good. If the angle is for example 30, then we need to rotate the vectors over an angle of 30 degrees.

So the amount we need to rotate is (we'll call it a):
a = 45 - 0.50*Angle

Now we need a rotation axis. For that we use the cross product. We'll call de rotation axis vector q.

q = f x r
q = q / ||q|| (to normalize our axis)

Btw, in case you don't know:
q = f x r :
q.x = f.y*r.z - f.z*r.y
q.y = f.z*r.x - f.x*r.z
q.z = f.x*r.y - f.y*r.x

This does give a problem if f and r are in the same direction, because then f x r = 0. You'll have to find a way to work around it.

So now we have a rotation axis, and the angle we need to rotate. Now how do we rotate?
For that we need to use a matrix to rotate around an arbitrary axis. We'll want to rotate one vector with the angle a and the other with the angle -a. I don't know which should be rotated with a and which with -a, but I suppose you can test it.

Now to rotate a vector around this arbitrary axis with angle a, we create the following matrix A, with:

A=[[A11 A12 A13]
[A21 A22 A23]
[A31 A32 A33]]

There might be some typing errors here , but you can find this matrix on many sites (type in google: arbitrary axis rotation matrix)

A11 = q.x^2 + (q.y^2 + q.z^2)*Cos(a)
A12 = q.x*q.y*(1-Cos(a)) - q.z*Sin(a)
A13 = q.x*q.z*(1-Cos(a)) + q.y*Sin(a)
A21 = q.x*q.y*(1-Cos(a)) + q.z*Sin(a)
A22 = q.y^2 + (q.x^2 + q.z^2)*Cos(a)
A23 = q.y*q.z*(1-Cos(a)) - q.x*Sin(a)
A31 = q.x*q.z*(1-Cos(a)) - q.y*Sin(a)
A32 = q.y*q.z*(1-Cos(a)) + q.x*Sin(a)
A33 = q.z^2 + (q.x^2 + q.y^2)*Cos(a)

Now let's assume that we have to rotate f with angle a.
We do that by calculating:
f' = Af

Incase you don't know how it works:

f'.x = A11 * f.x + A12 * f.y + A13 * f.z
f'.y = A21 * f.x + A22 * f.y + A23 * f.z
f'.z = A31 * f.x + A32 * f.y + A33 * f.z

You do the same with r, but then you use a matrix built with the angle -a.

Of course after that, when you have calculate f' and r' you should add the vector c again to get the positions you want.

There might be a way easier way than this, but this what I though of first.

Kevil
Fallout
22
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 17th Jun 2004 18:13 Edited at: 17th Jun 2004 18:23
Cheers for that Kevil. I'm gonna have to spend some time analysing that, and testing it to see how it works, but thanks for the time you put into that answer. I'll see if I can get it to work.

kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 17th Jun 2004 18:37
Wait a second with that:

After thinking about it more, this might also be a method (and easier) that might work. I'm not sure if it's correct, but you should try this.

So we have the same vectors f and r.

First thing we do is normalizing the vectors, so:
f = f/||f||
r = r/||r||

Now we want to find the midpoint between the two vectors.
We'll call it d.
d = 0.50*(f + r)

Now we can say that:

f' = d + u*(f - d)
r' = d + u*(r - d)

We know that d = 0.50*(f+r), so we can simplify:
f' = 0.50*(f + r) + u*(f - 0.50*(f + r)) = 0.50*((f+r)+u*(f-r))
r' = 0.50*((f+r)+u*(r-f)) = 0.50*((f+r)-u*(f-r))

Now we calculate the dot product dot(f',r'), that is:
0.25*((f.x+r.x)^2 - u^2(f.x-r.x)^2) + 0.25*((f.y+r.y)^2 - u^2(f.y-r.y)^2) + 0.25*((f.z+r.z)^2 - u^2(f.z-r.z)^2)

Now we want the dot product to be 0 (90 degrees). Now after some simplification, we get:

0 = 1 - u^2 + (1+u^2)*(f.x*r.x + f.y*r.y + f.z*r.z)
0 = 1 - u^2 + (1 + u^2)*(dot(f,r))
0 = 1 + dot(f,r) + (dot(f,r) - 1)*u^2
u^2 = (1 + dot(f,r))/(1 - dot(f,r))
u = sqrt((1 + dot(f,r))/(1 - dot(f,r)))

And now that we have u, we can calculate f' and r', using the formulas given above.

All we need to do after that, is scaling the vectors again to their original length. So for that you should've stored the original length.

Then the f' and r' you want, are:
f' = f'*||f||/||f'||
r' = r'*||r||/||r'||

And then you have to add the vector c to it again to get the vectors you need.

Kevil
Van B
Moderator
21
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 17th Jun 2004 18:39
Yup, reading that makes me wish I'd stayed awake in math, so it must be Kevil .


Van-B


The nature of Monkey was irrepressible!.
Fallout
22
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 17th Jun 2004 19:07
Well, I did GCSE and A Level maths, but matrices and vectors never got too complex. Maybe that's more mechanics? Maybe its degree level? I don't know.

Anyway, cheers for that revision Kevil. I've actually managed to simplify the problem now (I think), so I'm gonna try and port your solution to the similified problem. The simplification is basically just that I only need to move one vector, but I still need to do it on an different axis, so it's pretty much the same problem. I basically need to get my head around using a rotation matrix.

Btw, does ||f|| denote the length of the vector f? (see, my notation knowledge is a bit weak).

BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 17th Jun 2004 19:38
1. Take 3 wooden balls, a drill, some string, a ruler and a protractor.
2. Drill a hole through each ball.
3. Tie string of the correct length to model your start position.
4. Using a protractor, move the balls as required until they reach 90 degrees.
5. Measure with the ruler - Voila!

BatVink
http://facepaint.me.uk/catalog/default.php AMD 3000+ Barton, 512Mb Ram, 120 Gig Drive space, GeForce 5200 FX 128 Mb, Asus A7N8X Mobo.
Terms & Conditions apply
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 17th Jun 2004 20:12
Yeah, ||f|| is the length of f.
And rotation matrices can be hard, that's why I showed you the second solution.

Kevil
Fallout
22
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 17th Jun 2004 20:38 Edited at: 17th Jun 2004 20:39
Kevil - I've just found this online. Tell me what you think, if you don't mind. If this works, it'll save me some time. All I need to do is port the code to db and find the normal/axis vector to pass to it, plus calculate the angle.

http://astronomy.swin.edu.au/~pbourke/geometry/rotate/source.c

Also, the normalisation function - that's just the process of making the total length 1, isn't it? So I can rewrite that by just dividing all the magnitudes by the total length?

Thanks again. I'm starting to understand this 3D matrix etc. business now.

kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 17th Jun 2004 21:41
Yeah, normalizing is making the length 1.
And I suppose that source would work. I guess it's about the same what I described with a matrix, but then in code.

Yet, I think the second method is easier and probably faster.

Kevil
David T
Retired Moderator
22
Years of Service
User Offline
Joined: 27th Aug 2002
Location: England
Posted: 17th Jun 2004 22:27
Quote: "Yup, reading that makes me wish I'd stayed awake in math, so it must be Kevil "


Is it called math in Scotland too?

Two strings walk into a bar. I'll have a pint says the first$%ASLDJ09920D"$"$D. Excuse my friend says the second, he isn't null terminated.
Fallout
22
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 18th Jun 2004 00:06
Ok, well I've got it working with a combination of what you said and that source. What I'll do now is get it running in a main program loop and test how much it slows the proggy down. I'll then try and get it working with your second version and see if it offers a performance increase.

Cheers again for your help. I'm gonna have to find some good sources for learning more about vectors and matrices, as it's obvious they're the part of my maths that I'm lacking in. I think if I can get to grips with them, I should encounter fewer stumbling blocks on my maths problems, and probably make some more complex game engines.

Login to post a reply

Server time is: 2024-09-22 02:58:34
Your offset time is: 2024-09-22 02:58:34