Вычислить точку на поверхности сплайна

Question

Я работаю над алгоритмом управления, который будет работать на встроенной системе. Мой язык программирования - C, и система будет довольно сильно ограничена с точки зрения памяти и вычислительной мощности.

У меня есть несколько (порядка 10) опорных точек в трехмерном пространстве. Обычно они статичны, но время от времени меняются. Я хотел бы подогнать поверхность сплайна так, чтобы она проходила через все эти точки, а затем иметь функцию, которая для заданного входного вектора (x, z) возвращает расстояние y от плоскости y = 0.

Я думаю, что это проблема, которая должна быть решена в двух частях: 1) некоторые новые коэффициенты будут вычисляться всякий раз, когда изменяется контрольная точка, и 2) коэффициенты вставляются в функцию, которая возвращает y для заданного (x, z). (Только 2 должно происходить в режиме реального времени.)

Я немного исследовал в сети это, но мне трудно с математикой, и большая часть материала относится к компьютерной графике. Я даже не уверен, какой тип сплайна мне нужен; NURBS и Catmull-Rom оба кажутся актуальными. И наконец, что касается формы краев моего сплайна: поскольку мои входные векторы взяты из хорошо ограниченных показаний датчика, мне действительно все равно, что делает сплайн за пределами этой границы.

Я был бы очень благодарен за некоторую помощь или указатели на соответствующий материал, и любые фрагменты псевдокода были бы очень признательны.

Answer 1

Если бы вы могли каким-то образом генерировать треугольники Безье при изменении ваших опорных точек, гладкую поверхность этих треугольников легко рассчитать даже при ограниченных ресурсах вашего микроконтроллера - для этого требуется только повторное сложение и деление на два.

Один из способов создания треугольников Безье, которые проходят через все ваши точки, состоит в том, чтобы использовать триангуляцию Делоне на ваших контрольных точках, чтобы найти группу треугольников, которые покрывают вашу поверхность. Затем используйте углы этих треугольников в качестве углов ваших треугольников Безье и произвольно выбирайте контрольные точки так, чтобы грань между соседними треугольниками была "гладкой" (а не "согнутой").

Один из возможных способов выбора этих контрольных точек:

Для каждой из угловых точек треугольника (т. Е. Каждой из ваших исходных опорных точек):

• найти все края треугольника, где один конец в этой угловой точке
• найти все точки, "соединенные" с этой угловой точкой (на другом конце этих ребер)
• установить плоскую плоскость, которая проходит через эту угловую точку, а наименьшие средние квадраты "приближаются" к соединенным точкам
• Для каждого ребра выберите точку 1/4 (или 1/3 или 1/10 или что-то еще) от заданной угловой точки к соединенной угловой точке. Забудьте эту точку после нахождения ближайшей точки на плоскости к этой точке. Используйте полученную точку в качестве одной из контрольных точек в двух треугольниках, которые граничат с этим краем.

Это дает все, кроме одной контрольной точки для каждого треугольника Безье. Для оставшейся центральной контрольной точки треугольника Безье, возможно, проще всего использовать среднее геометрическое (центроид) угловых точек.