Generate 2 points along Bezier curve between 2 vectors, accounting for rotation

[Jenna Huntsman]

Hey!

Just about fried my brain trying to work this out (it's been a while since high-school math).

I want to generate 2 equally spaced points along Bezier curve between vectors A and B

For example, Vector A is <0,1,1> and Vector B is <1,0,-1>

Vector A and B also have rotation values (stored in Rads, but will put Degrees here) A: <0,90,0> B: <0,0,0>

I've also got a base position vector (pos) which in this example will be <0,0,0> (rotation is irrelevant)

How can I do this?

Thank you!

In case it helps, here's some actual (example) values for A and B, and their rotations

Pos: <0,0,0>

A (positon): <-0.50716, 1.00641, -1.64015>
A (rotation): <-86.63250, 0.94834, -74.28978>

B (position): <1.11717, 1.06567, -1.35355>
B (rotation): <-82.30524, -5.75685, -126.59010>

Edited January 18, 2021 by Jenna Huntsman

[animats]

Interpolate along the Bezier curve in the usual way to get the point. Then use SLERP to interpolate the rotation.

[Jenna Huntsman]

1 hour ago, animats said:

Interpolate along the Bezier curve in the usual way to get the point. Then use SLERP to interpolate the rotation.

Sorry, I should have been clearer.

Currently, my script interpolates position linearly between A and B - this isn't what I want. I want it to interpolate on a spherical curve between A and B - I know that I can use Cubic interpolation, but I need to be able to dynamically generate the 2 control points needed to use Cubic interpolation

[Wulfie Reanimator]

11 hours ago, Jenna Huntsman said:

Sorry, I should have been clearer.

Currently, my script interpolates position linearly between A and B - this isn't what I want. I want it to interpolate on a spherical curve between A and B - I know that I can use Cubic interpolation, but I need to be able to dynamically generate the 2 control points needed to use Cubic interpolation

Am I understanding correctly that given the two points A and B, the interpolated object should move in a smooth arc between those points, as if moving along the surface of a sphere (those diameter is the distance between A and B)? And the object's rotation would be interpolated with quaternion slerp?

Edited January 18, 2021 by Wulfie Reanimator

[Jenna Huntsman]

5 hours ago, Wulfie Reanimator said:

Am I understanding correctly that given the two points A and B, the interpolated object should move in a smooth arc between those points, as if moving along the surface of a sphere (those diameter is the distance between A and B)? And the object's rotation would be interpolated with quaternion slerp?

That's right - I've actually sorted out rotation, I've got working code for cubic interpolation, but I only want to feed my code the start and end point, and no intermediate control points - so the script needs to calculate the 2 control points I need for the spherical motion

I've attached an image to help explain - vector A is P0, vector B is P3. I want to be able to generate P1 and P2 based on a sphere around Pos (<0,0,0> in my example)

 

Edited January 18, 2021 by Jenna Huntsman

[Wulfie Reanimator]

7 hours ago, Jenna Huntsman said:

That's right - I've actually sorted out rotation, I've got working code for cubic interpolation, but I only want to feed my code the start and end point, and no intermediate control points - so the script needs to calculate the 2 control points I need for the spherical motion

If you've already got the rotation part right, then the position should be much simpler to implement.

These two seem pretty promising as far as examples go:

Implementing the spherical movement: https://youtu.be/TpYCd8yBa3Q

Demonstrating approximate values with cubic curves: https://digerati-illuminatus.blogspot.com/2008/05/approximating-semicircle-with-cubic.html

Your problem will be to decide which way to move about the sphere. Do you go "over" or "under" the sphere? What happens when A is below B or B below A?

I might come back with code later, but no guarantees.

Edited January 18, 2021 by Wulfie Reanimator

[Jenna Huntsman]

1 hour ago, Wulfie Reanimator said:

If you've already got the rotation part right, then the position should be much simpler to implement.

These two seem pretty promising as far as examples go:

Implementing the spherical movement: https://youtu.be/TpYCd8yBa3Q

Demonstrating approximate values with cubic curves: https://digerati-illuminatus.blogspot.com/2008/05/approximating-semicircle-with-cubic.html

Your problem will be to decide which way to move about the sphere. Do you go "over" or "under" the sphere? What happens when A is below B or B below A?

I might come back with code later, but no guarantees.

Please do, I've spent hours on it again today and I haven't progressed anywhere.

The idea is that the most direct route between A and B is taken, but never intersecting with the center point (hence why I don't want to use linear interpolation), although in terms of Z over would be preferable

I have some code which reliably determines the linear midpoint, and hacks in a method to determine A and B

origin = A
target = B

vector offset = target - origin; //offset between origin and dest, in x y z
vector ctrlpt = origin + (offset / 2); //find linear halfway point between origin and dest
vector ctrlpt1 = <((PI_BY_TWO * offset.x) + origin.x),ctrlpt.y,ctrlpt.z>;
vector ctrlpt2 = <ctrlpt.x,((PI_BY_TWO * offset.y) + origin.y),ctrlpt.z>;

The problem is that this only generates a convex curve in one direction (clockwise), but otherwise generates a concave curve in the other direction (which I don't want - it should always be a convex curve) and the curve does not account for the Z axis

EDIT:

Managed to brute force a solution - Instead of generating a linear halfway point, I generated 2 linear points with 1/3rd spacing,  and then recycling the known X Y Z values from A and B, which now generates the curve correctly in both directions

Now I need to drink the night away! 😅

Edited January 18, 2021 by Jenna Huntsman

[Jenna Huntsman]

20 hours ago, Jenna Huntsman said:

Please do, I've spent hours on it again today and I haven't progressed anywhere.

The idea is that the most direct route between A and B is taken, but never intersecting with the center point (hence why I don't want to use linear interpolation), although in terms of Z over would be preferable

I have some code which reliably determines the linear midpoint, and hacks in a method to determine A and B

origin = A
target = B

vector offset = target - origin; //offset between origin and dest, in x y z
vector ctrlpt = origin + (offset / 2); //find linear halfway point between origin and dest
vector ctrlpt1 = <((PI_BY_TWO * offset.x) + origin.x),ctrlpt.y,ctrlpt.z>;
vector ctrlpt2 = <ctrlpt.x,((PI_BY_TWO * offset.y) + origin.y),ctrlpt.z>;

The problem is that this only generates a convex curve in one direction (clockwise), but otherwise generates a concave curve in the other direction (which I don't want - it should always be a convex curve) and the curve does not account for the Z axis

EDIT:

Managed to brute force a solution - Instead of generating a linear halfway point, I generated 2 linear points with 1/3rd spacing,  and then recycling the known X Y Z values from A and B, which now generates the curve correctly in both directions

Now I need to drink the night away! 😅

Or not - my rotation interpolation made this look like a curve, but it was actually linear movement.

I've written this code, which mathematically SHOULD be working, the only problem is, that it only works correctly if the movement is anticlockwise (again, concave, convex problem)

    vector offset = camPos_target - camPos_origin; //offset between origin and dest, in x y z
    vector ctrlpt = camPos_origin + (offset / 2); //find halfway point between origin and dest
    //vector locoffset = ctrlpt - llGetPos();
    vector ctrlptthrd = camPos_origin + (offset / 3); //find 1/3 point between origin and dest
    vector ctrlpt2thrd = camPos_origin + (2*(offset/3)); //find 2/3 point between origin and dest
    vector ctrlptoff = ctrlpt - llGetPos();
    vector ctrlptthrdoff = ctrlptthrd - llGetPos();
    vector ctrlpt2thrdoff = ctrlpt2thrd - llGetPos();
    float radx = ctrlptoff.x * TWO_PI;
    float rady = ctrlptoff.y * TWO_PI;
    //vector ctrlpt1 = <ctrlptthrd.x + ctrlptoff.x,ctrlptthrd.y + ctrlptoff.y,ctrlptthrd.z>;
    //vector ctrlpt2 = <camPos_target.x + ctrlptoff.x,camPos_target.y + ctrlptoff.y,ctrlpt2thrd.z>;
    float ang = llAngleBetween(camRot_origin, camRot_target) * RAD_TO_DEG;
    float angthrd = ang/3;
    float vecdist = llVecDist(camPos_origin,camPos_target);
    float xoffthrd = radx*llCos(ang);
    float yoffthrd = rady*llSin(ang);
    vector ctrlpt1 = <ctrlptthrd.x + (xoffthrd),ctrlptthrd.y + (yoffthrd),ctrlptthrd.z>;
    float xoff2thrd = radx*llCos(ang);
    float yoff2thrd = rady*llSin(ang);
    vector ctrlpt2 = <ctrlptthrd.x + (xoff2thrd),ctrlptthrd.y + (yoff2thrd),ctrlpt2thrd.z>;
    llSay(0,"radx: " + (string)radx + "cos(" + (string)ang + ") = " + (string)(radx*llCos(ang)) + "\nrady: " + (string)rady + "sin(" + (string)(ang) + ") = " + (string)(rady*llSin(ang)) + "\nctrlptoff: " + (string)ctrlptoff);

Heelp! 

Edited January 19, 2021 by Jenna Huntsman

[Mollymews]

On 1/20/2021 at 6:01 AM, Jenna Huntsman said:

the only problem is, that it only works correctly if the movement is anticlockwise (again, concave, convex problem)

what happens when camPos_target and camPos_origin are swapped ? Does the progression of points move in the counter direction ?

and what happens when a 1 or -1 direction multiplier is introduced. 1*f = anticlockwise,  -1*f = clockwise ?

[Jenna Huntsman]

47 minutes ago, Mollymews said:

what happens when camPos_target and camPos_origin are swapped ? Does the progression of points move in the counter direction ?

and what happens when a 1 or -1 direction multiplier is introduced. 1*f = anticlockwise,  -1*f = clockwise ?

Swapping would only make the camera jump to the target, then travel back to the origin point

I did actually implement a function for that this morning, I can call isAntiClockwise(camPos_origin, camPos_target) which will return TRUE if the direction of travel is anticlockwise, and FALSE if clockwise. (Unhelpfully llAngleBetween only returns a positive value, even though it'd be more useful if it would determine the direction of travel as if you could only use positive values you can just run the result through llFabs) I used this to determine whether to add or subtract to ctrlptthrd - this did help a little bit, but it's not as reliable as I would like

[Quistess Alpha]

On 1/18/2021 at 6:55 AM, Jenna Huntsman said:

I want to be able to generate P1 and P2 based on a sphere around Pos (<0,0,0> in my example)

So, I know this is an old post, but I stumbled upon it, and it didn't look like it got a good answer. I might be understanding the problem wrong, but here's the problem, as I'm understanding it:

Assume there is a sphere at point <0,0,0> and two vectors A and B on that sphere. Find equally spaced(in spherical distance) points between A and B that lie on the sphere:

vector sphere_interpolate(vector A,vector B, float percent)
{ // return A when percent ==0, B when percent==1.
  rotation rot = llRotBetween(A,B);
  vector axis = llRot2Axis(rot);
  vector angle = llRot2Angle(rot);
  
  vector ret = A * llAxisAngle2Rot(axis,percent*angle);
  // if the lengths of A and B are known to be the same, this next line is unnessessary:
  ret = llVecNorm(ret) * ( ((1-f)*llVecMag(A)) + ((f)*llVecMag(B)) ); // there are efficiency gains to be had here I'm too lazy to do.
  return ret;
}

and for the given example of wanting to find 2 points, let percent be 0.33 and 0.66.

[Jenna Huntsman]

On 9/20/2021 at 4:14 AM, Quistess Alpha said:

So, I know this is an old post, but I stumbled upon it, and it didn't look like it got a good answer. I might be understanding the problem wrong, but here's the problem, as I'm understanding it:

Assume there is a sphere at point <0,0,0> and two vectors A and B on that sphere. Find equally spaced(in spherical distance) points between A and B that lie on the sphere:

vector sphere_interpolate(vector A,vector B, float percent)
{ // return A when percent ==0, B when percent==1.
  rotation rot = llRotBetween(A,B);
  vector axis = llRot2Axis(rot);
  vector angle = llRot2Angle(rot);
  
  vector ret = A * llAxisAngle2Rot(axis,percent*angle);
  // if the lengths of A and B are known to be the same, this next line is unnessessary:
  ret = llVecNorm(ret) * ( ((1-f)*llVecMag(A)) + ((f)*llVecMag(B)) ); // there are efficiency gains to be had here I'm too lazy to do.
  return ret;
}

and for the given example of wanting to find 2 points, let percent be 0.33 and 0.66.

Just revisiting this problem after a little while!

I've figured out that I also need to provide a plane normal so that the interpolation path follows along a defined plane between points A and B, and having the appropriate curvature for that path along the sphere.

How could that be added?

(many thanks for this code! I'm not a great mathematician and I can't seem to find the info I need elsewhere!)

Edited April 3 by Jenna Huntsman

[Quistess Alpha]

2 hours ago, Jenna Huntsman said:

I'm not a great mathematician

For this sort of thing, it's more about information flow than the math. Figure out what information you have, what information you need, and then find a way to convert one to the other.

Thinking about it backwards starting with the 'want': a spherical arc between 2 points needs a center, then once you have that, there are probably several ways to turn that into an arc, but fixing the thing I wrote years ago to include a center rather than just assuming <0,0,0> is the center:

// 2 points, a center and a list of percents along the circular arc to return. percent=0->A, percent=1.0->B
// assumes A,center,B is an isosceles triangle, which in general it won't be.
list sphere_interpolate(vector A,vector B, vector center, list percents)
{ // return A when percent ==0, B when percent==1
  
  A = A-center;
  B = B-center;
  
  rotation rot = llRotBetween(A,B);
  vector axis = llRot2Axis(rot);
  vector angle = llRot2Angle(rot);
  
  list rets;
  integer i = llGetListLength(percents);
  while(~--percents)
  {   //vector ret = center + A * llAxisAngle2Rot(axis,percent*angle);
      rets+= ( center + A*llAxisAngle2Rot(axis,angle*llList2Float(percents,i)) );
  }
  
  return rets;
}

but if I'm understanding you right, we don't know what point is the center of our hypothetical sphere, we only have a normal to the plane, and a radius (or some other measure of the curvature. After looking at some quick sketch diagrams, the most intuitive and easy to work with piece of information is the inner angle of the curve). Would need some debugging, but my first try would probably go something like:

// UNTESTED!
// angle in radians, TWO_PI -> return midpoint of A&B; PI -> return center that makes a quarter arc.; 0-> math error (point at infinity).
vector find_center(vector A, vector B, vector normal, float angle)
{
   vector average = 0.5*(B+A); // point between B&A.
   vector delta = average-A; // could use (B-A)/2, but this makes a bit more sense since we'll use average for the last step.
   
   float halfChord = llVecMag(delta); // half the distance from A to B.
    
   float dist = halfChord*llTan(0.5*angle); // distance from average to center
  
   vector cross = llVecNorm(normal%delta); // should point from midpoint of B&A to center.
   return average + dist*cross;
   
}

Big picture idea is that whenever you have a normal vector, you almost always want to take a cross product with some vector that lies in the plane of interest, giving you 2 vectors in that plane, from which you should be able to make any other point in that plane as ( (some point in the plane) + (a weighted sum of those 2 vectors) ).

Edited April 3 by Quistess Alpha

[Jenna Huntsman]

41 minutes ago, Quistess Alpha said:

For this sort of thing, it's more about information flow than the math. Figure out what information you have, what information you need, and then find a way to convert one to the other.

Thinking about it backwards starting with the 'want': a spherical arc between 2 points needs a center, then once you have that, there are probably several ways to turn that into an arc, but fixing the thing I wrote years ago to include a center rather than just assuming <0,0,0> is the center:

// 2 points, a center and a list of percents along the circular arc to return. percent=0->A, percent=1.0->B
// assumes A,center,B is an isosceles triangle, which in general it won't be.
list sphere_interpolate(vector A,vector B, vector center, list percents)
{ // return A when percent ==0, B when percent==1
  
  A = A-center;
  B = B-center;
  
  rotation rot = llRotBetween(A,B);
  vector axis = llRot2Axis(rot);
  vector angle = llRot2Angle(rot);
  
  list rets;
  integer i = llGetListLength(percents);
  while(~--percents)
  {   //vector ret = center + A * llAxisAngle2Rot(axis,percent*angle);
      rets+= ( center + A*llAxisAngle2Rot(axis,angle*llList2Float(percents,i)) );
  }
  
  return rets;
}

but if I'm understanding you right, we don't know what point is the center of our hypothetical sphere, we only have a normal to the plane, and a radius (or some other measure of the curvature. After looking at some quick sketch diagrams, the most intuitive and easy to work with piece of information is the inner angle of the curve). Would need some debugging, but my first try would probably go something like:

// UNTESTED!
// angle in radians, TWO_PI -> return midpoint of A&B; PI -> return center that makes a quarter arc.; 0-> math error (point at infinity).
vector find_center(vector A, vector B, vector normal, float angle)
{
   vector average = 0.5*(B+A); // point between B&A.
   vector delta = average-A; // could use (B-A)/2, but this makes a bit more sense since we'll use average for the last step.
   
   float halfChord = llVecMag(delta); // half the distance from A to B.
    
   float dist = halfChord*llTan(0.5*angle); // distance from average to center
  
   vector cross = llVecNorm(normal%delta); // should point from midpoint of B&A to center.
   return average + dist*cross;
   
}

Big picture idea is that whenever you have a normal vector, you want to almost always want to take a cross product with some vector that lies in the plane of interest, giving you 2 vectors in that plane, from which you should be able to make any other point in that plane as ( (some point in the plane) + (a weighted sum of those 2 vectors) ).

Hmm, okay, seems like I made a mistake.

The points I have are, 2 vectors (A and B) representing arbitrary points on the surface of a hypothetical shape, and vector of the center point of that shape, and a float representing the interpolation amount.

If it helps, I also know the 2 rotations of those points A and B.

Looking at the output, I wonder if the results being outside what I'm expecting is maybe because it'd be better to interpolate along an ellipsoid rather than a sphere? How could that be done?

I (somewhat shamefully) asked an AI model about this but as far as I could tell the math it was able to output was garbage.

Edited April 3 by Jenna Huntsman