Skip to content

Instantly share code, notes, and snippets.

@oxysoft
Last active March 13, 2021 00:15
Show Gist options
  • Save oxysoft/8a97b918b11e537dab5c05f26e19ed6d to your computer and use it in GitHub Desktop.
Save oxysoft/8a97b918b11e537dab5c05f26e19ed6d to your computer and use it in GitHub Desktop.
Optimized algorithm I made which finds the closest point on a bezier spline to another arbitrary P point
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment