Lofted polygon radius causing overlap in parallel transport.

As far as I understand, you use spline for generating the axis of the body. I would advise you to restrict the curvature of the spline. So in this case you will face overlapping but it will not be so dramatic. (In other words, imagine, that your spline was not a spline but a corner - infinite curvature in the vertex and zero curvature in other points, in this case other points generate cylinder, whereas vertex generates fracture, where overlapping occurres. So the less curvature - the less overlapping. The less diameter of the pipe - the less overlapping.
I think the curvature of the spline is connected to diameter of pipe with the following equation:
1/C >= R; C - curvature of the spline, R - radius of the pipe.

to calculate C you have to take the second derivative of the spline parametrized by length. (See also http://en.wikipedia.org/wiki/Curvature ).

Another problem might be, that the quaternion you get from the spline, is not on the same hemisphere of the hyper-sphere as the quaternion of the previous frame.
You can easily check that, by taking the 4d-dot-product of the quaternion, it must be >= 0, if it is not, they dont lie in the same hemisphere.

How do you specify the spline control points? Do you use quaternions to define the spline-control-points-orientation? Make sure that following quats lie in the same hemisphere then, be checking their dot-product.

I've attached is a wireframe version of what is going on.

The spline points are generated from the random waypoints using the code attached.

Waypoints are generated very simply as follows:

        private void GenerateWaypoint(ref Vector3 waypoint_Current)
        {          
            waypoint_Current += new Vector3(Game1.Random.Next(-8, 8), Game1.Random.Next(-5, 25), -Game1.Random.Next(5, 15));
        }

I guess that in this case the waypoints are not acceptable for the spline control points.  They have no orientation assigned to them but I am not sure how I would do that if that is how I should proceed?

        private void GenerateSplinePoints(List<Vector3> waypoints, int index_Start, int index_End)
        {
            // Camera will always start at first point on interpolated path (points_Interpolated)
            // Camera forward = (next interpolated path point - current interpolated path point)
 
            // Interpolated path (along spline)
            for (int i = index_Start; i < index_End - 2; i++)
            {
                // NB index starts from 0            
                spline_Point_List.AddRange(Interpolate(waypoints[i - 1], waypoints[i], waypoints[i + 1], waypoints[i + 2]));
            }
        }
 
        /// <summary>
        /// Returns a list of points on a spline between v2 and v3 (the first point being v2)
        /// </summary>
        /// <param name="v1">Previous point</param>
        /// <param name="v2">First point on spline</param>
        /// <param name="v3"></param>
        /// <param name="v4"></param>
        /// <param name="detail">Number of points on the spline</param>
        /// <returns></returns>
        private Vector3[] Interpolate(Vector3 v1, Vector3 v2, Vector3 v3, Vector3 v4)
        {
            // List size will equal number of points on spline
            Vector3[] list = new Vector3[spline_Point_Detail];
       
            for (int i = 0; i < spline_Point_Detail; i++)
            {
                Vector3 point_New = Vector3.CatmullRom(v1, v2, v3, v4, i / (float)spline_Point_Detail);
                list[i] = point_New;
 
                if (i > 0)
                {
                    // Create a segment for collision detection from this point and the previous point
                    segment_List.Add(new CD_Segment(list[i - 1], list[i]));
                }
            }
 
            // Add the final segment from v3 as it is not inclusive
            segment_List.Add(new CD_Segment(list[spline_Point_Detail - 1], v3));
 
            return list;
        }

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:

Can you show the code in CD_Segment

Sure.  The segment is just there to define the center of the lofted polygon.  It can be used for collision detection against the the radius of the tube.

using System;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
 
namespace Cthonian
{
    public class CD_Segment
    {
        public Vector3 A;
        public Vector3 B;
 
        public CD_Segment(Vector3 a, Vector3 b)
        {
            A = a;
            B = b;
        }
 
        /// <summary>
        /// Given segment ab and a point, compute closest point on ab (Page 128)
        /// </summary>
        /// <param name="point">Point to find closest point on segment to</param>
        /// <returns></returns>
        public Vector3 ClosestPtPointSegment(Vector3 point)
        {
            Vector3 ab = B - A;
 
            // Project c onto ab, computing parameterised position d(t) = a + t * (b - a)
            float t = Vector3.Dot(point - A, ab) / Vector3.Dot(ab, ab);
 
            // If outside segment, clamp t (and therefore d) to the closest endpoint
            // - If used with a ray t only needs to be clamped when it is negative
            // - If used with a line t never needs to be clamped
            MathHelper.Clamp(t, 0.0f, 1.0f);
 
            // Compute projected position from the clamped t (closest point on ab)
            return A + t * ab;
        }
 
        /// <summary>
        /// Returns the squared distance between a point and the segment
        /// </summary>
        /// <param name="point"></param>
        /// <returns></returns>
        public float SquareDistanceToPoint(Vector3 point)
        {
            Vector3 ab = B - A;
            Vector3 ac = point - A;
            Vector3 bc = point - B;
            
            float e = Vector3.Dot(ac, ab);
 
            // Handle cases where c projects outside ab 
            if (e <= 0.0f)
            {
                // A is closest to point
                return Vector3.Dot(ac, ac);
            }
 
            float f = Vector3.Dot(ab, ab);
 
            if (e >= f)
            {
                // B is closest to point
                return Vector3.Dot(bc, bc);
            }
 
            // Handle cases where c projects onto ab
            return Vector3.Dot(ac, ac) - e * e / f;
        }
    }
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:

I dont quite understand where in the code you calulate the orientation at a waypoint. Can you explain that please?

Anyway, if you look at the wireframe-rendering, you can see quite good what happens, You see 3 sements. The end of the 1st segment and the beginning of the 3rd segment are not easy to connect. The 2nd segment must make a big turn to connect them. That probably explains it. You need to choose waypoints, that are easier to connect.

Thanks ike.

Right now I am not calculating the orientation at the waypoint, just its position.   I've got no hope of getting a decent waypoint for the spline using my naff method where the position is just picked at random.

Could you please recommend a method that would pick better waypoints that are easier to connect?

Can you explain a bit, what the spline is used for?
Do the points have to be distributed randomly, or should there be any sort of order?
Why do they have to be random, cant you defined sone points hardcoded?

The waypoints start from (0,0,0) and then move in the +ve Z direction but with random x and y values.

The waypoints are used to generate the spline

The spline is used to create a tube from frames on each interpolated spline point.  It defines the center of the tube at all times no matter what the orientation.

I would need to create waypoints at different random locations that would not allow the tube to overlap as shown in the wireframe picture.
 
The random waypoints could follow a rule of being a certain length apart but I would need a way of making sure that the next waypoint generated would not allow the tube to overlap itself.

>> The waypoints start from (0,0,0) and then move in the +ve Z direction but with random x and y values.
>> need a way of making sure that the next waypoint generated would not allow the tube to overlap itself.

So you increase Z by a given value for each point? Or is that random too?

Can you post the original assignment text? Thats gonna be easier.

Thank you for the pictures that helped me understand :)

I've attached my code for getting the curvature of the CatmullRom spline.  Can you tell me if you see any errors in there?

Assuming it is correct:

If the constant uniform radius of the tube is less than the reciprocal of the number returned by the method then the waypoints are acceptable.

The problem is that I could be regenerating waypoints indefinitely until the equation (R < 1/C) is satisfied.

Can anyone suggest a sensible way of random waypoint generation to minimize the (R > 1/C) problem?

Thank you.

ike, this is not an assignment, it is something I am tackling in my spare time so there is no original text, sorry.

However to make things easier we could assume the following:

1) z is always going to increase from one waypoint to the next; the tube will never go back on itself
2) The length from one waypoint to another would remain constant

Ok, then just take hardcoded points, no need to generate them randomly. This way you can much easier make sure, that they dont overlap.

> Can anyone suggest a sensible way of random waypoint generation to minimize the (R > 1/C) problem?

When the splines were invented, they represented the wooden ruler which was binded to waypoints. I.e. normally splines gives you almost minimal curvature. You can use square polinomial splines for example. Even in case of you get not minimal curvature, it will be almost minimal (accurate to members, which --> 0).

Concerning your calculations: I cannot verify them since I don't work with 3d gfx (and don't work with graphix at all, I am Linux programmer), but I see that it seems, your spline-approximation takes 4 vectors, so this means it doesn't use square polinomial splines, probably it uses cubic polinomial splines or something other... I would advise you to debug spline-approximation algo in 2d space (it is easier to plot results), you may just put zero instead of one of co-ordinates and use your 3d-classes for 2d-calculations. Then plot curves in the 2d screen.

>> not bigger than +/- 45 degrees

read: not bigger than +/- 90 degrees

>>Anyway, if you want to make it random and 1) and 2) is assumed, just generate 2 random angles, >>around y-axis and z-axis. where {0 degrees, 0 degrees} points towards the z-axis. Make sure the >>angles are not bigger than +/- 45 degrees. add a vector with the length of assumption (2) and the >>random angles to the last position, there you go.

Sorry to be a pain but can you give me a short coded example?

I can understand that I can use a number between -45/+45 to generate the angle in degrees.  Would the z-axis remain constant each time (0,1,0) and how would I rotate around it?

I'm not sure how I can create a Vector3 from knowing its length

I can work it out the other way around using:
distance_Squared = (Vector3.x * Vector3.x) + (Vector3.x * Vector3.x) + (Vector3.x * Vector3.x)

or does this work if I work out the vector between the next waypoint - the current waypoint (v):
distance_Squared = Vector3.Dot(v, v);

Or do I just use the a set length (scalar) and multiply that by the direction I want to travel in the create the position of the next waypoint?

Thank you for your patience.

>> Thank you for your patience.

you're very welcome :)

>> Would the z-axis remain constant each time (0,1,0)

It remains constant, its the world-z-axis, but its {0,0,1}

Take the z-axis and scale it with the constant from your assumption (2).
That means you multiply each component of the vector by this constant.
If you want the distance between each waypoint being 10.0, then multiply the z-axis by 10

{0, 0, 10} = {0*10, 0*10, 1*10}

then rotate that vector by the random angles. Add the result to your previous waypoint, then you have the new waypoint.

I'm with you now for the distance part, I was thinking of finding the rotation first before moving!  

>> Would the z-axis remain constant each time (0,1,0)
Sorry I did mean 0,0,1 (world z) not 0,1,0, (world y) was a typo.

By rotating the vector, do you mean the same as transforming it, in which case can you tell me if the code I've attached below is what you had in mind?

Thanks ike.

            // Add minimum distance based on radius
            Vector3 v = waypoint_Current + new Vector3(0, 0, 10);
 
            // Choose a random x and y angle between -45 degrees and +45 degrees
            float random_Angle_X = Game1.Random.NextFloat(-0.7853982f, 0.7853982f); // ±45 degrees in radians
            float random_Angle_Y = Game1.Random.NextFloat(-0.7853982f, 0.7853982f); // ±45 degrees in radians
 
            // Rotate v around x and y axes by random amount
            v = Vector3.Transform(v, Matrix.CreateFromYawPitchRoll(random_Angle_Y, random_Angle_X, 0));
 
            waypoint_Current = v;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Ok my code doesn't work correctly as the tube can bend back on itself and reverse direction from -ve to +ve z axis.

The code contains an error, it should be: Vector3 v = waypoint_Current + new Vector3(0,0,-10).  

Also, the tube still overlaps slightly in some areas so I have definitely done something incorrect!

Any ideas on where I might have gone wrong ike?

Thanks

I've attached a picture of what I was trying to describe.

Could you please draw, what you want to get (just scratch, without 3d) 'cause I cannot understand...
It seems it's not difficult to think out en equation for necessary curve, but it is necessary to understand what you want (just  a few examples - if possible)

The picture attached in 2D is facing (heading) towards X axis.

The waypoints would be random so any spline could be created and the location of each waypoint could change.

When generating each random waypoint, I would like to put in place a set of rules that prevents the tube from overlapping (R > 1/C) but without the need for generating the interpolated points and checking the curvature each time (as it would be too expensive).

I thought what ike had posted would do such a thing, but I think I may have misinterpreted what he suggested?

Am I right? You want to build any random waypoints having some other random waypoints and you know, that you use splines for interpolation?

Rotate around x & z axes, not x and y.
Add waypoint_Current after you made the transformations with {0, 0, 10}

            // Add minimum distance based on radius
            Vector3 v = new Vector3(0, 0, 10);
 
            // Choose a random x and z angle
            float random_Angle_X = Game1.Random.NextFloat(+PI/2, -PI/2); // ±90 degrees in radians
            float random_Angle_Z = Game1.Random.NextFloat(-PI, PI); // 0..360 degrees in radians
 
            // Rotate v around x and z axes by random amount
            v = Vector3.Transform(v, Matrix.CreateFromYawPitchRoll(0, random_Angle_X, random_Angle_Z));
 
            waypoint_Current = waypoint_Current + v;
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

>>Am I right? You want to build any random waypoints having some other random waypoints and you >>know, that you use splines for interpolation?

Yes.

I want to build random waypoints starting from (0,0,0).
I'm using splines for interpolation and I'm creating frames at the interpolated points,

>>Rotate around x & z axes, not x and y.
>>Add waypoint_Current after you made the transformations with {0, 0, 10}

Ike, the code attached still causes problems :(

            // Add minimum distance based on radius [Negative as -ve z goes into screen in XNA]
            Vector3 v = new Vector3(0, 0, -10);
 
            float PI = MathHelper.Pi;
 
            // Choose a random x and y angle between -45 degrees and +45 degrees
            float random_Angle_X = Game1.Random.NextFloat(-PI * 0.5f, PI * 0.5f);   // ±90 degrees in radians
            float random_Angle_Z = Game1.Random.NextFloat(-PI, PI);                 // ±360 degrees in radians
 
            // Rotate v around x and y axes by random amount
            v = Vector3.Transform(v, Matrix.CreateFromYawPitchRoll(0, random_Angle_X, random_Angle_Z));
           
            waypoint_Current += v;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Can you print out your waypoints?
Make the angle around x smaller, take 45 degrees (PI/4)

These are the waypoints using the larger x and causing overlap:

{X:0 Y:0 Z:0}
{X:0 Y:2.591181 Z:-9.658457}
{X:0 Y:-3.496181 Z:-17.59218}
{X:0 Y:4.802968 Z:-23.17109}
{X:1.490116E-07 Y:0.4844179 Z:-32.19051}
{X:1.490116E-07 Y:10.40155 Z:-33.47525}
{X:1.490116E-07 Y:0.4462681 Z:-34.41994}
{X:1.490116E-07 Y:6.951897 Z:-42.01446}
{X:4.470348E-07 Y:16.56192 Z:-44.77986}

±45 degrees doesn't share the same issues.  However, the spline now only goes in the -ve z and ±y directions.  

If I wanted it to weave from "left" to "right" can I create a random angle for y alongside random_Angle_X or does one axis angle have to remain at 0 using this method?

 

can you print the angles too?

Ah sure:

 Matrix.CreateFromYawPitchRoll

it must be first rotated around z first, then around x.
Check your library if there is one with _RollPitch_
If not, create 2 matrices, and rotate each of them seperated and them multiply them

Oops, no, forget the last comment, can you print the angles and the points together?

Sure can,

Waypoint {X:-2.221869 Y:-1.638707 Z:-9.611344}
Angle X -0.1646131
Angle Y 0.2271807
Angle Z -1.053417

Waypoint {X:-2.981895 Y:-6.008025 Z:-18.57412}
Angle X -0.4521849
Angle Y 0.08459571
Angle Z -2.651513

Waypoint {X:2.333317 Y:-10.11693 Z:-25.98124}
Angle X -0.4234304
Angle Y -0.6224284
Angle Z -0.8233327

Waypoint {X:6.512625 Y:-13.93718 Z:-34.22376}
Angle X -0.3919869
Angle Y -0.469266
Angle Z -1.032223

Waypoint {X:9.623404 Y:-19.37234 Z:-42.02005}
Angle X -0.5746194
Angle Y -0.3796503
Angle Z -2.682592

Waypoint {X:10.86316 Y:-16.1304 Z:-51.39837}
Angle X 0.3301592
Angle Y -0.1314324
Angle Z 2.762748

Waypoint {X:5.066039 Y:-14.49616 Z:-59.38101}
Angle X 0.1641596
Angle Y 0.6281049
Angle Z -0.05984791

Waypoint {X:-1.113023 Y:-15.06612 Z:-67.22285}
Angle X -0.05702665
Angle Y 0.6673572
Angle Z -0.2779838

Waypoint {X:-4.168939 Y:-14.51966 Z:-76.72878}
Angle X 0.05467297
Angle Y 0.31104
Angle Z -0.1543787

Does that look ok to you?  I've attached the code that produces the above result.

            // Add minimum distance based on radius [Negative as -ve z goes into screen in XNA]
            Vector3 v = new Vector3(0, 0, -10);
 
            float PI = MathHelper.Pi;
 
            // Choose a random x and y angle between -45 degrees and +45 degrees
            float random_Angle_X = Game1.Random.NextFloat(-PI * 0.25f, PI * 0.25f); // ±45 degrees in radians
            float random_Angle_Y = Game1.Random.NextFloat(-PI * 0.25f, PI * 0.25f); // ±45 degrees in radians
            float random_Angle_Z = Game1.Random.NextFloat(-PI, PI);                 // ±360 degrees in radians
 
            // Rotate around z axis first
            Matrix transform = Matrix.CreateRotationZ(random_Angle_Z) * Matrix.CreateRotationX(random_Angle_X) * Matrix.CreateRotationY(random_Angle_Y);
 
            // Rotate v around x and y axes by random amount
            v = Vector3.Transform(v, transform);
           
            waypoint_Current += v;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Dont use angle y, otherwise the spline can go backwards in Z
Post the waypoints and angles without Y-rotation.

>> Dont use angle y, otherwise the spline can go backwards in Z

Using the code I posted, I am yet  encounter this problem?!  Could you please tell me how I could move left and right along x axis otherwise?

The waypoints and angles without Y-rotation are as follows:

Waypoint {X:0 Y:6.889179 Z:-7.248394}
Angle X 0.7599951
Angle Z 0.4378066

Waypoint {X:0 Y:10.88693 Z:-16.41452}
Angle X 0.4112718
Angle Z 0.1886871

Waypoint {X:0 Y:7.357797 Z:-25.77108}
Angle X -0.3606833
Angle Z -2.718297

Waypoint {X:0 Y:12.15866 Z:-34.5433}
Angle X 0.5007525
Angle Z 2.248204

Waypoint {X:0 Y:8.802938 Z:-43.96344}
Angle X -0.3422121
Angle Z -0.3956946

Waypoint {X:0 Y:14.30305 Z:-52.31502}
Angle X 0.5823773
Angle Z -1.499322

Waypoint {X:0 Y:18.27353 Z:-61.493}
Angle X 0.408298
Angle Z 2.5688

Waypoint {X:0 Y:15.89339 Z:-71.20561}
Angle X -0.2403199
Angle Z -2.731313

Waypoint {X:0 Y:10.97704 Z:-79.91362}
Angle X -0.5139669
Angle Z -1.708202  

Thank you.

I see, so if XNA uses Pre Multiplication and I want to rotate around the z axis first before rotating around the x axis, I would do the following:

Matrix transform = Matrix.CreateRotationX(random_Angle_X) * Matrix.CreateRotationZ(random_Angle_Z);

Is that correct?

1 of both, cant recall excactly now. What about the points? It works?

XNA is Pre Multiplication also.

For example:

WorldMatrix = Scale * Rotate * Translate (Not T * R * S)

Just to clarify (last time I promise):

You want me to rotate around the X axis first then around the Z axis?  (Pre M = x * z)

>> You want me to rotate around the X axis first then around the Z axis?

Yepp. I dont use XNA, I dont know the conventions of it.

No worries.

I still haven't figured out a tube radius (r) to minimum waypoint distance (d) ratio yet that works.

If:
r = d      causes overlapping
r * 2 = d causes overlapping
r * 3 = d causes overlapping
r * 4 = d causes overlapping
etc.

It seems that r * 10 = d is the first ratio that works but I am not sure as to why.  Any clues?

Because the bigger the radius, the higher is the possibility that it overlaps. Or the other way around: the smaller the distances, the higher the possibility that it overlaps.
We're getting much off-topic here.

If your question is, how to calculate that ratio, I must admit I have no idea. That is really a complicated topic, you should ask that in the math section, but I really dont think they will give you a formula how to calculate it. I would take a practical approach and try it first, there will hardly be any chance that you need to generate a random spline with tube in a program. For a wipe-out style game, you will use well defined points and store them in *race-tracks* rather than generate them randomly