Game Dev

Проект создан для того, чтобы найти и собрать людей, которые занимаются разработкой игр, их обсуждения, а также…

14 jul

2017

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

Added by Devion

Devion

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

Вообще в идеале задача звучит как "поиск ближайшей точки на кривой относительно луча". Может даже такой вариант кто знает?

Answer

Насколько мне известно, в общей виде - нельзя. Если вкратце опишешь, какую проблему решаешь, то есть вероятность найти альтернативные варианты.

Like 2

alexprey - 6 years ago

Найти ближайшую точку из списка доступных?

Devion - 6 years ago

alexprey,

без деления на более мелкие отрезки

Clamp - 6 years ago
Edited by Clamp

Doc - 6 years ago

Откуда кривая то собственно взялась, если не из набора точек? Какая-то формула? Можно спроецировать её на прямую и найти локальные минимумы.

Clamp - 6 years ago

Doc, очевидно, что если известен порядок кривой, то она строится по известной формуле =)

Devion - 6 years ago

есть безье 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 точки кривой, луч (позиция+направление) направленный из камеры.
Задача: определить ближайшую к кривой точку и выполнить с ней нужные манипуляции.

Использовать дробление на более мелкие отрезки я не хочу, т.к. это очень затратно, особенно если кандидатов на пересечение будет больше. Габаритный тест решит проблему, но только частично.

Пробовал делить на отрезки более экономно (поделить на три отрезка, вычислить квадрат расстояния, отсеять, снова поделить, и так несколько раз), но результат такого деления становится некорректным, когда указатель оказывается чуть дальше.

В принципе ладно, ответ "нельзя" меня устраивает, просто надеялся, мало ли.

Clamp - 6 years ago

Devion, как именно располагается и чем задаётся вектор камеры относительно кривой? Модель плоская или всё-таки пространственная?

Doc - 6 years ago

Очень сомневаюсь в "нельзя". Если искать пересечение между линией и плоскостью, но используя вместо уравнения плоскости уравнение безье то наверное может получиться. Советую спросить не здесь, а на stackoverflow/math.stackexchange

Clamp - 6 years ago

Doc:

Очень сомневаюсь в "нельзя".

Собственно, я говорил про "в общем виде", когда ещё не было внесено никаких уточнений. И да, действительно, "в общем виде" в целом редко что оказывается "льзя".

Советую спросить не здесь, а на stackoverflow/math.stackexchange

Совет дня, если честно.

To leave a comment please sign in to the site.