Devion
Game Dev

Поиск ближайшей точки к кривой

Добавлен
Возможно ли быстро вычислить ближайшую точку к кривым 3го/4го порядка без деления на более мелкие отрезки? Если да, то как?
Вообще в идеале задача звучит как "поиск ближайшей точки на кривой относительно луча". Может даже такой вариант кто знает?

Принятый ответ

Насколько мне известно, в общей виде - нельзя. Если вкратце опишешь, какую проблему решаешь, то есть вероятность найти альтернативные варианты.
14 июл 2017
2 806
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
29
0
Найти ближайшую точку из списка доступных?
0
27
0
alexprey,
без деления на более мелкие отрезки
0
30
0
Насколько мне известно, в общей виде - нельзя. Если вкратце опишешь, какую проблему решаешь, то есть вероятность найти альтернативные варианты.
Принятый ответ
2
29
2
Откуда кривая то собственно взялась, если не из набора точек? Какая-то формула? Можно спроецировать её на прямую и найти локальные минимумы.
2
30
2
Doc, очевидно, что если известен порядок кривой, то она строится по известной формуле =)
0
27
0
есть безье 3/4 порядка. т.е. да как сказал кламп - по формуле.
Формула кривой безье третьего порядка выглядит так:
        public static Vector3 Bezier(Vector3 a, Vector3 b, Vector3 c, float t)
        {
            var c0 = (1 - t)*(1 - t);
            var c1 = (1 - t)*2*t;
            var c2 = t*t;
            return c0*a + c1*b + c2*c;
        }
формула безье 4го порядка вот так:
        public static Vector3 Bezier(Vector3 a, Vector3 b, Vector3 c, Vector3 d, float t)
        {
            float c0 = (1 - t)*(1 - t)*(1 - t);
            float c1 = (1 - t)*(1 - t)*3*t;
            float c2 = (1 - t)*t*3*t;
            float c3 = t*t*t;
            return c0*a + c1*b + c2*c + c3*d;
        }
Применений несколько, все даже не назову, но вот ближайший кейс.
Есть некоторая камера, которая смотрит на построенную кривую безье. В точке, на которую мы указали/нажали должен появиться новый объект.
Т.е. наши базовые данные: 3 точки кривой, луч (позиция+направление) направленный из камеры.
Задача: определить ближайшую к кривой точку и выполнить с ней нужные манипуляции.
Использовать дробление на более мелкие отрезки я не хочу, т.к. это очень затратно, особенно если кандидатов на пересечение будет больше. Габаритный тест решит проблему, но только частично.
Пробовал делить на отрезки более экономно (поделить на три отрезка, вычислить квадрат расстояния, отсеять, снова поделить, и так несколько раз), но результат такого деления становится некорректным, когда указатель оказывается чуть дальше.
В принципе ладно, ответ "нельзя" меня устраивает, просто надеялся, мало ли.
0
30
0
Devion, как именно располагается и чем задаётся вектор камеры относительно кривой? Модель плоская или всё-таки пространственная?
2
29
2
Очень сомневаюсь в "нельзя". Если искать пересечение между линией и плоскостью, но используя вместо уравнения плоскости уравнение безье то наверное может получиться. Советую спросить не здесь, а на stackoverflow/math.stackexchange
0
30
0
Doc:
Очень сомневаюсь в "нельзя".
Собственно, я говорил про "в общем виде", когда ещё не было внесено никаких уточнений. И да, действительно, "в общем виде" в целом редко что оказывается "льзя".
Советую спросить не здесь, а на stackoverflow/math.stackexchange
Совет дня, если честно.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.