Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Кривая Безье: значение в произвольной точке и длина кривой

Кривая Безье: значение в произвольной точке и длина кривой

Страницы: 1 2 3 Следующая »
petya-kurochkinПостоялецwww29 июля 20177:56#0
Всем привет!
Хочу сделать анимацию по кривой Безье.
Но я никогда с ними не работал. Главная мотивация - анимацию можно прототипировать в Blender'е. Т.е. можно бросить плоскость заданного размера (типа экран) и какой-нибудь там кубик, который и анимируется.

Что планируется потом? Я хочу взять keyframes и забить их в программу массивом. Проблемы:
1. Как по контрольным точкам нужно найти промежуточные значения.
2. Как найти длину кривой?

VoidSpiritПостоялецwww29 июля 20179:59#1
petya-kurochkin
> 2. Как найти длину кривой?
Приближенным методом, разбивая на отрезки и суммируя их длины
petya-kurochkin
> 1. Как по контрольным точкам нужно найти промежуточные значения.
По формуле параметрической кривой Безье x(t), y(t)
http://3d-orange.com.ua/bezier-curves-for-your-games-tutorial/

Информации море, Гугл в помощь.

Если нужно находить точку на кривой по проценту или доле от длины - то опять же разбиением на линейные отрезки и приближенным вычислением

AlikberovПостоялецwww11 апр. 201822:39#2
Ничегo, если я здесь спрошу?
Написал функцию преобразования Безье в массив координат, чтобы строить тректорию движения персонажа. Однако, как известно, кривые Безье - не сбалансированны. Если сдвигать персонажа в каждом кадре на одну координату из массива, то получается, что где-то персонаж топчется на месте и еле двигается в гуще точек, а где-то - совершает «квантовые скачки»…
Сначала хотел написать процедуру и проредусить массив, выбросив из него элементы с очень малой дистанцией. Но, написав половину цикла, почему-то подумал и тупо удалил, так как…
Затем решил доработать процедуру генерации Безье-массива, что опять-таки не удалось, так как не сообразил, как верно составить условие для помещения координаты в массив…
Везде получается слишком много переменных. Причём, первые варианты были рекурсивны и медленны. Потому, сейчас - один цикл и очень много переменных. И требуется добавить ещё столько же, чтобы добавить дробную итерацию в случае «скачков»…
Есть ли готовые решения?
Гугл выводит некоторые, но на уровне высшей математики, а не фрагментами алгоритмов. А с высшей - у меня очень туго.

P.S.: Пишу штучку одну и не хочу ту тему засорять.
А форум всегда советует поискать похожие темы… Нашёл данную…
Спасибо!

SuslikМодераторwww12 апр. 20186:45#3
Alikberov
когда строишь массив контрольных точек, вместо так:
for(float param = 0; param < 1.0f; param += stepSize)
{
  points.push_back(BezierCurve(param));
}
делаешь так:
vec3 currPoint = BezierCurve(param);
float currStepSize = stepSize;
for(float param = 0; param < 1.0f;)
{
  vec3 nextPoint = BezierCurve(param + currStepSize);
  float derivative = length(nextPoint - currPoint) / currStepSize;
  currStepSize = stepSize * dstDerivative / derivative;
  points.push_back(nextPoint);
  currPoint = nextPoint;
  param += currStepSize;
}
грубо говоря, выбираешь шаг по кривой, обратно пропорциональный производной по её параметру, а производная аппроксимируется на основе двух последних точек и шага между ними.

Правка: 12 апр. 2018 6:47

eDmkУчастникwww12 апр. 201813:54#4
Вот квадратичная Безье:
+ Показать

Остальные формулы есть в WiKi.

1 frag / 2 deathsУчастникwww12 апр. 201814:14#5
eDmk
> Вот квадратичная Безье:
Неоптимально.
eDmkУчастникwww12 апр. 201814:25#6
>Неоптимально.
Это просто по формуле. А оптимально пусть сам делает.
DelfigamerПостоялецwww12 апр. 201816:02#7
1 frag / 2 deaths
> Неоптимально.
Вот, кстати, а правда ли? Уж больно походит на миф для покрывшихся мхом сишников, наряду с "С++ медленный" и "макросы работают быстрее функций и требуют меньше стека".
Вбил в годот - https://godbolt.org/g/d9Nequ
Остальные длинные, я человек ленивый, так что рассмотрим только результат по шлангу.
+ Показать

Как видим, все повторяющиеся вычисления действительно были вынесены компилятором, а некоторые даже параллелизованы через SIMD.
Остальные подробно не рассматривал, но судя по количеству subss на процедуру - как минимум CSE выполняют все.
Так что этот метод может быть неоптимальным только в том случае, если есть принципиально другая формула.

Правка: 12 апр. 2018 16:06

1 frag / 2 deathsУчастникwww12 апр. 201819:01#8
Delfigamer
Проверь, раскрыв все скобки, и заранее вычислив члены для t*t, для t и константу.
FordPerfectПостоялецwww12 апр. 201819:11#9
Погодите, если речь о квадратичной Безье, так там длина считается аналитически.
http://www.malczak.linuxpl.com/blog/quadratic-bezier-curve-length/
https://math.stackexchange.com/questions/12186/arc-length-of-b%C3%A9zier-curves

Правка: 12 апр. 2018 19:17

FordPerfectПостоялецwww12 апр. 201819:49#10
Хотя численное определение всё-равно может быть лучше.
FordPerfectПостоялецwww12 апр. 201820:14#11
1 frag / 2 deaths
> Проверь, раскрыв все скобки, и заранее вычислив члены для t*t, для t и константу.
Я не уверен, что это здравая идея.
DelfigamerПостоялецwww12 апр. 201820:31#12
FordPerfect
> Я не уверен, что это здравая идея.
Она здравая, только немножко.
+ сурс
D:\mist>g++ --version
g++ (x86_64-posix-seh-rev1, Built by MinGW-W64 project) 7.2.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

D:\mist>g++ bezier.cpp -std=c++11 -O3 -o a.exe -DMETHOD_TU
D:\mist>a
time: 0.000027020

D:\mist>g++ bezier.cpp -std=c++11 -O3 -o a.exe -DMETHOD_TT
D:\mist>a
time: 0.000026210

D:\mist>g++ bezier.cpp -std=c++11 -O3 -o a.exe -DMETHOD_FACTORS
D:\mist>a
time: 0.000026210

D:\mist>g++ bezier.cpp -std=c++11 -O3 -o a.exe -DMETHOD_HORNER
D:\mist>a
time: 0.000038760

D:\mist>g++ bezier.cpp -std=c++11 -O3 -ffast-math -o a.exe -DMETHOD_TU
D:\mist>a
time: 0.000015560

D:\mist>g++ bezier.cpp -std=c++11 -O3 -ffast-math -o a.exe -DMETHOD_TT
D:\mist>a
time: 0.000011870

D:\mist>g++ bezier.cpp -std=c++11 -O3 -ffast-math -o a.exe -DMETHOD_FACTORS
D:\mist>a
time: 0.000011870

D:\mist>g++ bezier.cpp -std=c++11 -O3 -ffast-math -o a.exe -DMETHOD_HORNER
D:\mist>a
time: 0.000019110
Скажем так, эта идея здравая на 3% ну окей, 31% таки выжал.
Почему на каждый алгоритм программа компилируется по-новой? Хороший вопрос. Всё дело в том, что когда я вписал в одну программу обе функции сразу, они тут же стали показывать в два раза больше, каждая. Мне кажется, проблема лежит где-то между кэшем и выравниваниями. Я пытался накладывать всякие __attribute__((aligned(0x100))), но не помогло.
Интересно, что на схеме Горнера алгоритм неожиданно становится тормозным, хоть и не настолько, как плохо выровненные тете и теуу. Видимо, там умножения оказываются настолько плотными, что конвеер спотыкается на зависимостях.
Ну а вообще, если вычисленные значения потом записываются в файл - все эти проценты безжалостно поглотит доступ к диску, так что в этом месте волноваться смысла вообще никакого нет. Зачем работать дольше, если не видно разницы?

Правка: 12 апр. 2018 20:42

FordPerfectПостоялецwww12 апр. 201820:37#13
https://godbolt.org/g/GBX8uD
+ Показать
FordPerfectПостоялецwww12 апр. 201820:40#14
Delfigamer
А, если ftt снаружи считать, тогда ок.
Страницы: 1 2 3 Следующая »

/ Форум / Программирование игр / 2D графика и изометрия

2001—2018 © GameDev.ru — Разработка игр