Равномерная дискретизация кривой Безье

Question

Мне нужно дискретизировать кривую Безье 3-го порядка с точками, равномерно распределенными вдоль кривой. Кривая определяется четырьмя точками р0, р1, р2, р3 и общая точка р (т) с 0 < т < 1 определяется по формуле:

point_t = (1 - t) * (1 - t) * (1 - t) * p0 + 3 * (1 - t) * (1 - t) * t * p1 + 3 * (1 - t) * t * t * p2 + t * t * t * p3; 

Моя первая мысль была discretise т = 0, t_1 , ... t_n, ..., 1

Это не работает, поскольку в общем случае мы не получаем равномерного расстояния между дискретизированными точками.

Подводя итог, что мне нужно это алгоритм discretise параметрическую кривую так, чтобы:

|| p(t_n) - p(t_n_+_1) || = d 

Я думал о рекурсивно вдвое сократить кривую Безье с Casteljau algorithm до требуемого разрешения, но это потребовало бы много дистанционных вычислений.

Любая идея о том, как решить эту проблему аналитически?

Answer 1

То, что вы ищете, также называется параметризацией длины дуги.

В общем случае, если вы разделите кривую безье в фиксированном интервале параметрической установки по умолчанию, результирующие сегменты кривой не будут иметь одинаковую длину дуги. Вот один из способов сделать это http://pomax.github.io/bezierinfo/#tracing.

Некоторое время назад я играл с небольшим количеством кода (поток кривизны), который требовал, чтобы точки были как можно более равномерно разделены. Вот сравнение (без правильной маркировки по осям!;)) С использованием линейной интерполяции и monotone cubic interpolation из того же набора квадратурных выборок (я использовал 20 выборок на каждую кривую, каждая из которых оценивалась с использованием 24-градусной гаусс-легендарной квадратуры) для повторной калибровки кубической кривой ,

[Пожалуйста, обратите внимание, что это по сравнению с другим пробегом алгоритма с использованием гораздо больше узлов и образцов, взятых в качестве земли истины.]

Вот demo с помощью монотонной кубической интерполяции для повторной калибровки кривой. Функция Curve.getLength является квадратурной функцией.