2
\$\begingroup\$

I am writing a game where I require a camera on rail; That is, the camera's path is fixed and follows a bezier curve. However, I cannot find any resources online for solving the closest point on a bezier curve closest to another arbitrary point, despite being something that should be common.

A good example of a game that does it very well is the original Crash Bandicoot trilogy.

So how do you do it? Or am I overthinking the problem?

\$\endgroup\$
  • \$\begingroup\$ Which development platform are you using? \$\endgroup\$ – Sourav Paul Jun 26 '16 at 1:17
  • \$\begingroup\$ I'm using Unity but this shouldn't be terribly relevant, it's mostly the maths or logic behind it I'm after, which I can then implement \$\endgroup\$ – oxysoft Jun 26 '16 at 1:41
  • \$\begingroup\$ Is it safe to assume you're using cubic Bézier splines? Or quadratic? \$\endgroup\$ – DMGregory Jun 26 '16 at 12:08
  • \$\begingroup\$ These are cubic bézier splines. \$\endgroup\$ – oxysoft Jun 26 '16 at 12:35
  • \$\begingroup\$ I've come up with a possible solution but I'm confident that there must be better way to go about it. My solution uses two bezier curves, one that defines the path of the camera and one that defines the average/approximate path the player may take. Then, 1. plot a series of points that go through both of these curves 2. find the point of the player path curve closest to the player 3. match it to the camera path and place the camera at that point 4. maybe use some sort of interpolation to smooth everything out? \$\endgroup\$ – oxysoft Jun 26 '16 at 12:42
2
\$\begingroup\$

I could not find anything on this subject so I invented my own algorithm which works by iterating over and over again to find more precise results. The higher you set the iteration count, the more precise it will be.

hope this helps anyone who has the same problem

public Vector3 GetPointClosestTo(Vector3 p, out float result, out int curve) {
// an optimized algorithm i invented which finds the closest point on a bezier to another arbitrary P point
// this algorithm is iteration based, meaning that the more iterations your perform, the more precise the results will be
// it is optimized to be fast but this particular implemention is not necessarily as fast as it could be, and the code is certainly not pretty
// optimizing this is left as an exercise to the viewer

// points is a vector3 array which defines the anchors and control points of the current bezier curve in the following format
// [anchor, control, control] * n, [anchor]
// where n is as many bezier curves which this spline defines. it pieces multiple bezier curves together, although the algorithm could be adapted for single curves that are alone

// 1. first we find the closest anchor and the corresponding curves that this anchor touches
int acount = CurveCount + 1; // number of anchors
Vector3[] anchors = new Vector3[acount];
for (int i = 0; i < acount; i++) {
    anchors[i] = transform.TransformPoint(points[i * 3]);
}

Vector3 closest;
int index;
GetClosestVector(anchors, p, out closest, out index);

float[] ts;
int[] indices;

// 2. we setup our dataset
bool fleft = false; // far left
bool fright = false; // far right
if (index == 0) {
    ts = new[] {0f, 0.5f};
    indices = new[] {index * 3};
    fleft = true;
} else if (index == anchors.Length - 1) {
    ts = new[] {0.5f, 1f};
    indices = new[] {(index - 1) * 3};
    fright = true;
} else {
    ts = new[] {0.5f, 1f, 0f, 0.5f};
    indices = new[] {(index + -1) * 3, (index + 0) * 3};
}

// 20 should be good enough for most cases, increase for better precision????????
const int iterations = 20;
float ot = result = 0f;
curve = 0;

for (int i = 0; i < iterations; i++) {
    float t0, t2;

    if (ts.Length > 2) {
        t0 = ts[0];
        t2 = ts[3]; // if we're still on an anchor point, then it's a 2-curve
    } else {
        t0 = ts[0];
        t2 = ts[1];
    }

    int i0 = indices[0]; // left index
    int i2 = indices[0];
    if (indices.Length > 1)
        i2 = indices[1];

    // calculate left/right focal points
    Vector3 v0 = transform.TransformPoint(Bezier.GetPoint(points[i0], points[i0 + 1], points[i0 + 2], points[i0 + 3], t0));
    Vector3 v2 = transform.TransformPoint(Bezier.GetPoint(points[i2], points[i2 + 1], points[i2 + 2], points[i2 + 3], t2));

    // test left/right focal points against the center focal
    Vector3[] test = {v0, closest, v2};
    float[] tmapping = {t0, ot, t2};
    GetClosestVector(test, p, out closest, out index);

    result = ot = tmapping[index];
    curve = i0;

    // update
    if (index != 1) { // shift focal point to the left/right && increase focality
        float hf = Math.Min(t0, t2) * 0.5f;
        if (fleft) // left-most anchor
            hf = t2 * 0.5f;
        else if (fright) // right-most anchor
            hf = (t2 - t0) * 0.5f;

        float t = t0;
        if (index == 2)
            t = t2;

        ts[0] = t - hf;
        ts[1] = t + hf;

        Array.Resize(ref ts, 2);

        if (index == 2 && indices.Length > 1)
            indices[0] = indices[1];
        Array.Resize(ref indices, 1);
    } else { // increase focality
        float hf;

        if (ts.Length > 2) { // we're still on the 2-curve anchor
            hf = t2 * 0.5f;
            ts[0] = t0 + hf; // compress >> o
            ts[3] = t2 - hf; // compress o <<
        } else { // we're working on a single curve now
            hf = (t2 - t0) * 0.25f; // WTFFFF

            ts[0] = t0 + hf; // push >> o
            if (!fright)
                ts[1] = t2 - hf; // push o <<
        }
    }
}

curve /= 3;

return closest;
}

private void GetClosestVector(Vector3[] vectors, Vector3 p, out Vector3 closest, out int index) {
float dist = 9999999999f;
closest = Vector3.zero;
index = 0;

for (int i = 0; i < vectors.Length; i++) {
    Vector3 v = vectors[i];
    float d = Vector3.Distance(v, p);
    if (d < dist) {
        dist = d;
        closest = v;
        index = i;
    }
}
}
\$\endgroup\$
  • \$\begingroup\$ Yes this is the engineering way :) now that you have that, you can speed-it up by preparing a flat_map (if you can find one in C#) with precalculations of this for every 10 meters or whatever your game unit. then access using lower_bound (or equivalent API). This will give you the initial position (at first display frame). From there, following target movement should be goverend by a self/adaptive-tuned PID regulator. en.wikipedia.org/wiki/PID_controller \$\endgroup\$ – v.oddou Jun 29 '16 at 1:50
  • \$\begingroup\$ Most of what you said just went over my head, I don't really know anything about engineering but the implementation is definitely not the most optimal and can surely be optimized further yeah \$\endgroup\$ – oxysoft Jun 29 '16 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.