16 replies to this topic

[JM33]

Hi everyone, I know this is a common question but my searches are not turning up good solutions (ones that work).

I have a flight simulator / jet fighter game. I have other airplanes (enemy targets) flying around in the world. I want to shoot a guided missile at the target. My original approach for this works most of the time, but sometimes fails.

What I have done is found my missile's heading vector, and the vector between the missile and the target. I take the cross product of the 2 vectors to get my rotation axis vector. The angle of rotation is found by arccosine of the dot product of the cross product of my missile & target vectors. Since I do not want the missile to turn directly at the target immediately, I limit the rotation to 2 degrees. After rotating, I move the missile along its forward vector, by its speed.

To explain the failure in this, let me give in an example. The game starts & out in front of my airplane is the target. For this example both objects are flying forward. If I fire the missile, it goes straight for the target and hits.

However, if I roll my airplane over (upside down) the missile seems to turn the wrong direction. It will often make a big loop and eventually find the target and destroy it. It seems that the rotation angle should be negative in this case, but I don't know how to determine if I need to do so.

Here is some basic code to demonstrate:
[source lang="java"]Vector3D targvec = new Vector3D(targetmatrix[12], targetmatrix[13], targetmatrix[14]);Vector3D R1pos = new Vector3D(R1Matrix[12], R1Matrix[13], R1Matrix[14]);Vector3D R1head = new Vector3D(R1Matrix[8], R1Matrix[9], R1Matrix[10]);Vector3D newtargvec = targvec.subtract(R1pos);newtargvec = newtargvec.normalize();R1head = R1head.normalize();float angle = R1head.angleBetween(newtargvec); // acos(R1head.dotProduct(newtargvec)Vector3D rotaxis = R1head.crossProduct(newvec);rotaxis.normalize();if (angle > 2){ angle = 2;Matrix.rotateM(R1Matrix, 0, (float) angle, rotaxis.getX(), rotaxis.getY(), rotaxis.getZ());setMoveForwardMatrix(tempMatrix, -(movedist),R1Matrix[8], R1Matrix[9], R1Matrix[10]);Matrix.multiplyMM(R1Matrix, 0, tempMatrix, 0, R1Matrix, 0); [/source]

[Álvaro]

You can extract a signed angle from the size of the cross product: If you started with unit-length vectors, it's just asin(length(rotaxis)).
[EDIT: Please, ignore that.]

You can also avoid using angles at all by computing the quaternion that corresponds to the desired rotation, but applying the 2-degree-per-frame limit is trickier and I don't have time to think about it right now. Maybe I'll post some code tonight.

Edited by Álvaro, 08 November 2012 - 03:36 PM.

[JM33]

Thanks Alvaro, I have succesfully used quaternions to achieve the full rotation to towards the target. However, I have no idea how to get a limited (x degrees) rotation from the quaternion without converting it to angle-axis. After converting and limiting the angle, I get the same results. A code example would be great, but even just an explanation of the process would help.

[Álvaro]

Well, the real part of a quaternion is w = cos(alpha/2), so you can translate an inequality like `alpha <= 2 degrees' to `w >= cos(1 degree)'. So if your quaternion has a real part that is below the threshold, set it to the threshold and rescale the other three numbers to make sure the quaternion preserves unit length.

I haven't thought about it carefully, but if your quaternion has negative real part you may want to flip its sign before you do what I describe above (remember that q and -q represent the same rotation).

[JM33]

This seems to be on the right track, but I'm not sure. The part about limiting the rotation seemed to work but I am still getting inconsistent results. Same problem, when the plane turns upside down, the rocket will miss.

Does it matter that I am still converting the quaternion back to a matrix (instead of converting to axis angle)? I am multiplying the converted matrix by the rockets matrix. As far as I know with quaternions, you have to convert to matrix, as I am using opengles on android.

The other thing I noticed was that the limiting threshold for the quaternion worked when it shouldn't have. At first I only limited the w value to anything below the threshold. code example:
[source lang="java"]Quaternion head = new Quaternion(0, R1head.getX(), R1head.getY(), R1head.getZ()).normalize();Quaternion newvec = new Quaternion(0, newtargvec.getX(), newtargvec.getY(), newtargvec.getZ()).normalize();Quaternion rot = head.rotBetween(newvec); //Get Quaternion for rotation between the two vectors float turn_threshold = FloatMath.cos(maxrot/2); // maxrot is the rockets maximum rotation angle (2)if (rot.w < turn_threshold){ rot.w = turn_threshold;} float[] qmat = rot.toMatrix(); //convert quaternion to matrixMatrix.multiplyMM(R1Matrix, 0, R1Matrix, 0, qmat, 0); [/source]

This did not account for a "w" value lower than zero. However when the "w" value was near -0.9, sometimes the rocket would still hit the target. Even though this code changed the value from -0.9 to +0.99 (or cos(1)). When I tried to limit the negative W value the rocket would never hit the target.I have a much harder time visualizing quaternions so I am quite confused.

Also I am not sure what you meant by scaling the other three parts after changing the W value. Do I need to just normalize it?

[Álvaro]

Also I am not sure what you meant by scaling the other three parts after changing the W value. Do I need to just normalize it?

Not quite. You need to scale the unreal part of the quaternion (the coefficients of i, j and k) so that the whole quaternion is unit length. Something like this:

#include <boost/math/quaternion.hpp>
#include <cmath>

typedef boost::math::quaternion<double> Q;

Q limit_rotation(Q q, double min_real_part) {
  if (q.real() <= -min_real_part || q.real() >= min_real_part)
    return q;

  if (q.real() < 0)
    q = -q;

  double desired_unreal_length = std::sqrt(1 - min_real_part * min_real_part);
  double old_unreal_length = abs(q.unreal());
  return Q(min_real_part) + q.unreal() * (desired_unreal_length / old_unreal_length);
}

Edited by Álvaro, 11 November 2012 - 12:33 AM.

[JM33]

return Q(min_real_part) + q.unreal() * (desired_unreal_length / old_unreal_length);
}

Sorry I only know Java, but is this returning a Quaternion that is created by a double value? I don't understand how to do that. Don't you need either "w,v" or "w,x,y,z" values?

[Álvaro]

5.2 is a perfectly good quaternion, also known as 5.2 + 0*i + 0*j + 0*k.

More explicitly, what I am returning there is the quaternion
w = min_real_part
x = q.x * (desired_unreal_length / old_unreal_length)
y = q.y * (desired_unreal_length / old_unreal_length)
z = q.z * (desired_unreal_length / old_unreal_length)

Does that answer your question?

[JM33]

Yes that helps!
Now the part I don't understand is the q.unreal(), what is going on there? My assumption based on q= w +xi + yj + zk is that the unreal part is x+y+z. However when I tried that I got strange results. Thank you for your help

[Álvaro]

The unreal part of w + xi + yi +zk is 0 + xi + yi + zk. The documentation is here.

Edited by Álvaro, 14 November 2012 - 06:53 AM.

[JM33]

Sorry Alvaro, the documentation didn't help me as it does not show how they calculate the unreal part. If you say the unreal part is "0 + xi +yj +zk", then how do I get the value of i,j,k?

In my last post I had assumed the unreal part was 0 + q.x+q.y+q.z by making i,j and k equal to 1. As I said that produced bad results. I don't think setting them to zero would work, but I also tried multiplying each by the real part "w". Again bad results.

Sorry for not understanding, I think I'm struggling to understand the imaginary part of quaternions. It seems sometimes i,j,k just get dropped (meaning value of 1), and sometimes they are zero. I really appreciate your help.

[Álvaro]

Sorry Alvaro, the documentation didn't help me as it does not show how they calculate the unreal part. If you say the unreal part is "0 + xi +yj +zk", then how do I get the value of i,j,k?

The unreal part is what I said, and the documentation says the same thing: The unreal part of a quaternion is another quaternion, which happens to have the real part zeroed out. To get the values of x, y and z from q = w + xi + yj + zk, you use something like R_component_2(), R_component_3() and R_component_4(). But this should be irrelevant, since you aren't using Boost.Quaternions.

Sorry for not understanding, I think I'm struggling to understand the imaginary part of quaternions. It seems sometimes i,j,k just get dropped (meaning value of 1), and sometimes they are zero. I really appreciate your help.

i, j and k are never 1 and they are never 0. I am not sure what you have seen that gave you that impression.

[JM33]

Well, I have to create my own quaternion class, and I didn't have an unreal() method so I was just trying to figure that out. I found through a search that with quaternions, i = j = k = sqrt(-1).

[source lang="java"]public double unreal() { double i = FloatMath.sqrt(-1); double unreal = this.x*i + this.y*i + this.z*i; return unreal; }[/source]

However, I just plugged that in and it didn't work. So I will check over some of my code.

[Álvaro]

That is some very confused post. i, j and k are different things, which have something to do with rotating 180 degrees around the x, y and z axes, or something like that. It is true that i^2 = j^2 = k^2 = -1, but this should tell you that they are not real numbers and therefore cannot fit in a double.

public Quaternion unreal() {
  return Quaternion(0, this.x, this.y, this.z); // or with `new', or however this is done in your language.
}

[JM33]

OK, yes I was very confused, and I never needed to solve for i,j,k in the first place.

The code you gave me works as often as the original code I had with angle/axis, however with the opposite effect. Basically if my plane is upside down I hit the target, otherwise not. If I remove the lines to negate the quaternion when q.real() is less than 0, I get the original results (plane upside down = miss &amp; plane right side up = hit).

If you have any suggestion or insight please let me know. I feel like this is really close to the right solution as the rotation is being correctly limited to the maximum rotation, but still needs to be inverted properly. I am wondering if there is anything that can be referenced to determine when to negate the quaternion, such as the up vectors of the rocket and target?

Here is my code as-is:
[source lang="java"]Vector3D targvec = new Vector3D(targetmatrix[12], targetmatrix[13], targetmatrix[14]);Vector3D R1pos = new Vector3D(R1Matrix[12], R1Matrix[13], R1Matrix[14]);Vector3D R1head = new Vector3D(R1Matrix[8], R1Matrix[9], R1Matrix[10]);Vector3D newtargvec = targvec.subtract(R1pos);newtargvec = newtargvec.normalize();R1head = R1head.normalize();Quaternion head = new Quaternion(0, R1head.getX(), R1head.getY(), R1head.getZ()).normalize();Quaternion newvec = new Quaternion(0, newtargvec.getX(), newtargvec.getY(), newtargvec.getZ()).normalize();Quaternion rot = head.rotBetween(newvec).normalize();float turn_threshold = 0.9998477f; // cos(maxrot/2) = cos(1)Quaternion newq = rot.limit_rotation(rot, turn_threshold); // see Quaternion code belowfloat[] qmat = newq.toMatrix(); Matrix.multiplyMM(R1Matrix, 0, R1Matrix, 0, qmat, 0);[/source]

And my relative Quaternion functions:
[source lang="java"]public Quaternion limit_rotation(Quaternion q, float min_real_part) {if (q.real() <= -min_real_part || q.real() >= min_real_part) return q;if(q.real() < 0){ q = q.multF(-1); // negate quaternion}float desired_unreal_length = FloatMath.sqrt(1 - min_real_part * min_real_part);float old_unreal_length = q.unreal().abs(); Quaternion limit = new Quaternion(min_real_part, q.x * (desired_unreal_length / old_unreal_length), q.y * (desired_unreal_length / old_unreal_length), q.z * (desired_unreal_length / old_unreal_length));Log.i("QuatLimit", "Result = w: " + Float.toString(min_real_part) + ", x:" + Float.toString(limit.x) + ", y:" + Float.toString(limit.y) + ", z:"+ Float.toString(limit.z)); return limit;}public Quaternion(float real) { this.w = real; this.x = 0; this.y = 0; this.z = 0;}public float real() { return this.w;}public Quaternion unreal() { return new Quaternion(0, this.x, this.y, this.z);}public float abs() { return FloatMath.sqrt(x * x + y * y + z * z + w * w);}public Quaternion (float w, float x, float y, float z) { this.set(w, x, y, z);}public Quaternion multF(float scalar) { this.x *= scalar; this.y *= scalar; this.z *= scalar; this.w *= scalar; return this;}[/source]

Edited by JM33, 18 November 2012 - 09:34 PM.

[Álvaro]

The main suggestion I have is to try to isolate one instance of the computation where the code is not doing what you want it to do, look at the numbers, follow the code with a debugger and see where things are going wrong. That's a really boring thing to do, but also extremely useful.

[JM33]

Solved! Basically what I needed to do was orient the quaternion to the rocket's current orientation around the forward vector. I was only supplying the forward vector, which was not enough to know if I had any amount of "roll" around the forward vector.

So I ended up making a quaternion of the current rocket rotation from the current matrix, and multiplying that by the limit_rotation quaternion from before. Then I set that back to a matrix plugged that into the rotation portion of the rockets matrix(Instead of multiplying the two matrices).

[source lang="java"]Quaternion transform_rotation = Quaternion.setFromMatrix(R1Matrix).normalize(); Quaternion head = new Quaternion(0, R1head.getX(), R1head.getY(), R1head.getZ()).normalize(); Quaternion newvec = new Quaternion(0, newtargvec.getX(), newtargvec.getY(), newtargvec.getZ()).normalize(); Quaternion rot = head.rotBetween(newvec).normalize(); float turn_threshold = 0.999874f; // maxrot is the rockets maximum rotation angle (2) rot = Quaternion.limit_rotation(rot, turn_threshold).multQ(transform_rotation); float[] qmat = rot.toMatrix(); for (int i= 0; i< 10; i++){ R1Matrix[i] = qmat[i]; }[/source]

Thank you so much Álvaro, your code worked perfectly to limit the rotation of the quaternion.