Last active
March 13, 2021 00:15
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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