Catmull-Rom Spline (Extension to hermite)

[thanhle]

Hi guys,
If anyone uses the CSceneNodeAnimatorFollowSpline, its implementation is a hermite spline, which moving last control point affect the first point.

Catmull-Rom tend to fix this issue. Anyway here is the modification to the CSceneNodeAnimatorFollowSpline animate function. You can create another spline animator call CSceneNodeAnimatorFollowCatmullSpline.

Code: Select all

//! animates a scene node
void CSceneNodeAnimatorFollowCatmullSpline::animateNode(ISceneNode* node, u32 timeMs)
{
    if(!node)
        return;
 
    const u32 pSize = Points.size();
    if (pSize==0)
    {
        if ( !Loop )
            HasFinished = true;
        return;
    }
    if (pSize==1)
    {
        if ( timeMs > StartTime )
        {
            node->setPosition(Points[0]);
            if ( !Loop )
                HasFinished = true;
        }
        return;
    }
 
    const f32 dt = ( (timeMs-StartTime) * Speed * 0.001f );
    const s32 unwrappedIdx = core::floor32( dt );
    if ( !Loop && unwrappedIdx >= (s32)pSize-1 )
    {
        node->setPosition(Points[pSize-1]);
        HasFinished = true;
        return;
    }
    const bool pong = PingPong && (unwrappedIdx/(pSize-1))%2;
    const f32 u =  pong ? 1.f-core::fract ( dt ) : core::fract ( dt );
    const s32 idx = pong ?  (pSize-2) - (unwrappedIdx % (pSize-1))
                        : (PingPong ? unwrappedIdx % (pSize-1)
                                    : unwrappedIdx % pSize);
    
    const core::vector3df& p0 = Points[clamp(idx, pSize)];
    const core::vector3df& p1 = Points[clamp(idx + 1, pSize)];
    
 
     core::vector3df t1;
     core::vector3df t2;
    if (idx > 0)
    {
        t1 = 0.5f*(Points[clamp(idx + 1, pSize)] - Points[clamp(idx - 1, pSize)]);
    }
    else
    {
        t1 = Points[clamp(idx + 1, pSize)] - Points[clamp(idx, pSize)];
    }
    if (idx < Points.size() - 2)
    {
        t2 = 0.5f * (Points[clamp(idx + 2, pSize)] - Points[clamp(idx, pSize)]);
    }
    else
    {
        t2 = Points[clamp(idx + 1, pSize)] - Points[clamp(idx, pSize)];
    }
 
    // hermite polynomials
    const f32 h1 = 2.0f * u * u * u - 3.0f * u * u + 1.0f;
    const f32 h2 = -2.0f * u * u * u + 3.0f * u * u;
    const f32 h3 = u * u * u - 2.0f * u * u + u;
    const f32 h4 = u * u * u - u * u;
 
    core::vector3df f = p0 * h1 + p1 * h2 + t1 * h3 + t2 * h4;
    node->setPosition(f);
}

One thing I notice with existing spline function is. I don't know why
const bool pong = PingPong && (unwrappedIdx / (pSize - 1)) % 2;
const f32 u = pong ? 1.f - core::fract(dt) : core::fract(dt);


if we set u as below. It seems to also works.
const f32 u = core::fract(dt);

[robmar]

Nice and very useful! The original spline animator was not so good!

One other issue is making the object flying the path look forward, and for that to track smoothly, especially around corners.

Are you drawing the red path lines following the spline points?

[thanhle]

The red line is the actual path. It's the connection of small straight line segments drawn from a modified CSceneNodeAnimatorFollowCatmullSpline function above. Just create an override function that return position without the node argument.

e.g. Straight segment of 10 units.

Code: Select all

 
            core::vector3df curpoint(controlPoints[0]);
            core::vector3df nextpoint;
            int i = 0;
            video::SMaterial mtl;
            mtl.Lighting = false;
    while (curpoint.getDistanceFromSQ(controlPoints.getLast()) > 1.0f)
            {
                nextpoint = mSplinePath->getCSceneNodeAnimatorFollowCatmullSplinePos (i * 10);
 
                smgr->getVideoDriver()->setTransform(video::ETS_WORLD, core::matrix4());
                smgr->getVideoDriver()->setMaterial(mtl);
                smgr->getVideoDriver()->draw3DLine(curpoint, nextpoint, video::SColor(150, 255, 0, 0));
                curpoint= nextpoint;
                i++;
            }

Look at vector can be calculated from i+1 etc. I'm not sure it will be smooth if you put the camera on it. You can try it out.

You can reduce the error in estimating the segment length if you calculated the length of the curve first. E.g. if you want to have 1000 segments between the start and end point etc.

Regards
Thanh

[robmar]

Thanks, very useful!

I´m finding it is smooth until there is a sharp curve, then it can get a bit bumpy.

It also gets bumpy as the camera tracks onto complex objects that were culled, I guess the frame rate drops... to be expected of course

[thanhle]

Maybe try to reduce the segment length at sharp curve.
If you have method that can detect the rapid change in gradient, then maybe you can make the segment length proportional to the gradient? or estimate the the radius of the curve and derive the proportion segment lengths.

Goodluck mate.

[robmar]

I guess the thing is to always have enough points, because when there are few, the direction changes on the curve become extreme.

I was also working on roll by determining the change of direction, and the same issue applies.

All fun stuff!

Cheers!