Jump to content
  • Advertisement
Sign in to follow this  

How to sample a 3D dubins path according to distance travelled?

This topic is 814 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am looking for ways to get the location of an agent is at when

it has traveled a certain distance on a 3D Dubins Curve

I am looking into a prototype like this

CalcVec(DubinsPath* dubinspath, float distTraveled, D3DXVECTOR3* currPos, double* pSlopeNow);



Edited by lucky6969b

Share this post

Link to post
Share on other sites

Hmm, I haven't done this for 3d, but I've done it for 2d.  I believe it will mostly be the same, which is getting the distance of the three parts.  The start arc, the line, and the end arc.  Once you have those distances (which I store in the DubinPath for convenience), compare that to the current distance, which will tell you which of the pieces you are on, and from there it's a parametric equation.  It might be a little tougher in 3d, because I'm not sure the exact equation for an arc that changes in elevation.  I wonder if you could ignore it and do a straight linear interpolation on the Z to simplify that portion, as finding the length of an arc is fairly simple, as is finding the position on an arc given a T value.


Hopefully that all makes sense, let me know if you need further clarification.

Edited by ferrous

Share this post

Link to post
Share on other sites

Hello ferrous,

Thanks for answering my question....

Have you got any ideas what these cryptic names mean?

I just extract them from here


I just start thinking about it, I probably need to have at least a starting position and an ending position

so that I can do a D3DXVec3Lerp on it.


Just an educated guess, does it mean, like start, end and intermediate start and end?

What do all the w's, c's, k's, q's and l's do?




struct DubinsPath3D

    D3DXVECTOR3 p_s;
    D3DXVECTOR3 p_e;
    float angl_s;
    float angl_e;

    int _case;
    float R;
    float gam;
    float L;

    int lamda_s;
    float k_s;
    float psi_s;
    D3DXVECTOR3 c_s;
    D3DXVECTOR3 w_s;
    D3DXVECTOR3 q_s;

    int lamda_si;
    float psi_si;
    float k_si;
    D3DXVECTOR3 c_si;
    D3DXVECTOR3 w_si;
    D3DXVECTOR3 q_si;
    int lamda_e;
    float k_e;
    float psi_e;
    D3DXVECTOR3 c_e;
    D3DXVECTOR3 w_e;
    D3DXVECTOR3 q_e;

    int lamda_ei;
    float k_ei;
    float psi_ei;
    D3DXVECTOR3 c_ei;
    D3DXVECTOR3 w_ei;    
    D3DXVECTOR3 q_ei;   
    D3DXVECTOR3 w_l;
    D3DXVECTOR3 q_l;



Edited by lucky6969b

Share this post

Link to post
Share on other sites

Sigh, looks like a mathematician wrote it, and not a programmer =)  Have you tried contacting the owner of the GitHub to see if they can explain the variables?  You may also do some searches for dubins airplane and see if you can find better descriptions.  The math on dubins airplane is pretty complex.


They seem to be ways of describing the 3d arcs involved, you might be able to either dig around the github for clues or do some searches.  A simple D3DXVec3Lerp won't work for you in this case, as you're traveling along those arcs, not a straight line.  Unless you've broken up that arc into line segments, but then to do that you'd already have a way of getting positions out of the arc.

Share this post

Link to post
Share on other sites

I read up the comments of the code this morning.

I came to understand what it is doing


the ones that start with the letter 'q' is a directional vector

'w' is a positional vector



// # end spiral
sol.c_e = cre - D3DXVECTOR3(0, 0, -dist2*tan(gam));
sol.psi_e = theta - PI / 2;
sol.lamda_e = 1;

//# hyperplane H_s : switch from first spiral to line
sol.w_s = w1;
sol.q_s = q1;

// # hyperplane H_l: switch from line to last spiral
sol.w_l = w2;
sol.q_l = q1;

// # hyperplane H_e: end of Dubins path
sol.w_e = ze;
sol.q_e = dot(D3DXVECTOR3(1, 0, 0), rotY(anglend));

It is a RSR turn.

Start with the w_s, which is an end point of a spiral

and q_s is which direction it is pointing towards.


So let's say I start with position (10, 20, 30) and some direction say a radian of 1.57

If a path is found and in the case of RSR turn, there will be a spiral

between (10, 20, 30) and w_s, and the directions are already said,

which is 1.57 from the starting point and ends with q_s


So the problem reduces to finding a sampled point within the spiral itself

The other segments are found exactly the same way.


Unfortunately, I am not good at mathematics, and I couldn't find much materials

on how to go about finding the value of the sampled point...



Edited by lucky6969b

Share this post

Link to post
Share on other sites

What is the implication of dotting a vector and a matrix and resulting in another vector like this?



    // x = ax + by + cz
    // y = px + qy + rz
    // z = ux + vy + wz

    double x = t1.x * t2._11 + t1.y * t2._12 + t1.z * t2._13;
    double y = t1.x * t2._21 + t1.y * t2._22 + t1.z * t2._23;
    double z = t1.x * t2._31 + t1.y * t2._32 + t1.z * t2._33;
    return D3DXVECTOR3(x, y, z);


When dotting a vector against another vector, I get a scalar, it tells me how the vectors are separating.

But I don't know the true meaning of dotting a vector against a matrix that results in another vector of sums



Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!