Поиск готового решения

[ssoft]

Ну ладно, пусть t - расстояние по пути (тоже от 0 до 1), как-то посчитали P1 и P2, и.. что мне с этим делать? У меня входные точки (x, y, z)(t) и выходные должны быть "в том же формате". Можете прояснить этот момент?

Вот как бы я решал задачу:

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

Далее использовал бы МНК и получил точки (x, y, z) сплайна P0, P1, P2, P3.

Сплайн определяет аналитическое множество точек "в том же формате", что и исходное аппроксимируемое множество - (x, y, z).

Вообще, мне не совсем ясен этот вопрос. Результат для МНК всегда "в том же формате", что и исходные данные (если, конечно, Вы не пытаетесь решить задачу по каждой компоненте отдельно).
Параметр t_i должен быть одинаков для всех компонент, каждому  (x_i, y_i, z_i) соответствует единственное значение t_i.

Есть N точек (x, y, z) с регулярным шагом по времени. Порядок N - сотни, тысячи и больше. Требуется заменить их кубическим сплайном Безье с минимальным числом контрольных точек. Ну т.е. кривой проходящей через все N точек, разумеется с какой-то заданной погрешностью.

Вообще, правильное ли начальное описание задачи?

1. Есть ли в данных регулярный шаг по времени? Если да, то наилучшая параметризация для t_i будет нормированное время, а не расстояние.

2. Что значит "кубическим сплайном Безье с минимальным числом контрольных точек"? У кубического сплайна Безье всегда 4 управляющие точки.
В общем случае для построения кривой, аппроксимирующей все N точек с какой-то заданной погрешностью, может потребоваться либо более одного сплайна Безье, либо другой вид сплайна, либо сплайн Безье более высокого порядка.
В первом случае требуется использовать более одного сплайна Безье и стыковать их по условиям неразрывности и гладкости, либо использовать более сложные B-сплайны или NURBS и добиваться нужной точности путем последовательного увеличения количества используемых контрольных точек сплайна.

И вот еще: наше обсуждение игнорирует (или никак не учитывает) эту ссылку
http://webdocs.cs.ualberta.ca/~graphics/books/GraphicsGems/gems/FitCurves.c

Ссылку посмотрю чуть позднее.

[Igors]

Вот как бы я решал задачу:

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

Далее использовал бы МНК и получил точки (x, y, z) сплайна P0, P1, P2, P3.

А есть ли здесь 2 варианта? Вот как я понял (не стесняйтесь поправлять). Геометрическая (пространственная) параметризация - значит параметр t сопоставляется с (относительной) длиной пути. Вначале t каждой точки считается как сумма длин пройденных отрезков, но потом может меняться - вместо ломаной уже есть какая-то кривая, расстояние по ней может быть значительно больше чем по начальной ломаной.

А вот параметризация "по времени" никаким изменениям уже не подлежит, т.к. время жестко привязано к точкам. И вот теория концентрируется на параметризации "по длине". Т.е. "есть исходные точки" (2D или 3D) и по ним нужно найти сплайн - а время тут как бы и ни причем. Вообще-то это разумно - ведь когда мы видим путь (траекторию) - мы ничего не можем сказать как он проходился по времени. Но меня-то это не устраивает, требуется получить не только траекторию в пр-ве, но и x(t), y(t) и z(t). Поэтому для искомых точек P1 и P2 нужно получить не только (x, y, z) но и время - а где его взять? См 3 картинки выше - в правом окне ведь тоже есть управляющие точки, и они должны иметь 2 координаты.

Использовать найденное решение можно если исходные точки представить как пары "время + значение". И тупо передрать код, пусть себе параметризует по хорде. А на выходе для P1 и P2 мы получим и значение и время. Но увы, на 3 координаты это никак не распространяется (ну это я так думаю).

Выходит остается только "вариант 2" (параметризуемся по времени, дальше МНК).  Он совсем не плох (сейчас доделываю), но никак не учитывает модуляцию по времени (фактически ре-параметризацию). На выходе имеем P1(x, y, z) и P2(x, y, z), времени-то все равно нет, остается положить его 1/3 для P1 и 2/3 для P2 (работает)

Вообще, правильное ли начальное описание задачи?

Ну то уже включается "думать неохота" Все там правильно, и все Вы прекрасно поняли 

[ssoft]

Варианты параметризации - это следствие прикладных целей задачи. Поэтому легко может быть и больше, чем 2 варианта)).
Вариант с параметризацией по пространству имеет цель - наилучшее приближение геометрии, поэтому и параметр t выбирается через дистанция вдоль кривой.
Вариант с параметризацией по времени преследует наиболее точное соответствие данных к времени. Например, экспериментальные зависимости и т.п.

Можно построить и сплайн вида P(u), где P - это точки (x, y, z, t), тогда время t - это одна из компонент, а в качестве параметра будет выступать u.
Параметризацию u можно выполнить по пространственным хордам sqrt(dx²+dy²+dz²), координата времени не участвует.
В этом случае t = t₀ + t₁u + t₂u² + t₃u³, и чтобы найти точку на момент t потребуется решить уравнение относительно u, а затем найти уже x, y и z.

[ssoft]

И вот еще: наше обсуждение игнорирует (или никак не учитывает) эту ссылку
http://webdocs.cs.ualberta.ca/~graphics/books/GraphicsGems/gems/FitCurves.c

Ссылку посмотрю чуть позднее.

По ссылке реализовано приближение точек набором сплайнов Безье 3-го порядка с целью геометрического приближения с заданной точностью.
Этот вариант мы тоже рассматривали.

В общем случае для построения кривой, аппроксимирующей все N точек с какой-то заданной погрешностью, может потребоваться либо более одного сплайна Безье ...

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

Представленная реализация - это частный случай для 2D точек и сплайна Безье 3-го порядка. Обобщить на 3D или сплайны другого порядка нельзя, так как вместо производных тангенсы, да и уравнения преобразованы.
То что я писал - это самый общий случай, из которого получается и представленный частный.
Равномерность по времени здесь не учитывается (если она нужна), так как цель - наилучшее пространственное приближение.

[Igors]

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

Это нужно делать для любого метода, нельзя надеяться  что любой набоо точек ляжет под 1 сегмент (кривую всего из 2 точек). Сейчас этим и занимаюсь, и выплыла такая деталь:  "точка наибольшего отклонения" вовсе не означает "точку наилучшего разбиения", иногда начинает молотить так:

[0..60]  - пытаемся аппроксимировать 61 точку одним сегментом. Не выходит, погрешность больше допустимой, наибольшая в точке.. 1(?). Затем в точке 2 и.т.д. пяток-десяток "лишних" сегментов наструячит. Сейчас убираю их вторым проходом.

Для стыковки сплайнов между собой введены дополнительные условия неразрывности и гладкости,

Нет, это юзер решает интерактивно

[Igors]

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

Для сегмента сплайна (P0, P1, P2, P3) требуется найти P1 и P2. Это успешно решается МНК с параметризацией по времени. Теперь хотелось бы большего - уметь находить "веса" W1 и W2 для точек P1 и P2. См. аттач. Углы наклона симметричны, но W1 = 2, W2 = 1, поэтому кривая несимметрична.  Собсно ничего страшного не случится с обычным МНК - ну да, не вытянет он такое одним сегментом, накидает 1-2 лишних точек, это не катастрофа. Но все-таки хотелось бы. Как используются веса

1) Модулируется время
c3 * t^3 + c2 * t^2 + c1 * t = user_T

Т.е. сначала решается кубическое ур-е и находится параметр t.  Коэффициенты "c"

q1 = W1 / 3
q2 = 1 - W2 / 3
c1 = 3.0 * q1;
c2 = 3.0 * (-2.0 * q1 + q2);
c3 = 1 + 3.0 * (q1 - q2);

Выше это уже было. просто здесь W1 и W2 как их видит юзер (по умолчанию единички)

2) И с подделанным t рисуем кривую "увеличивая" управляющие точки, т.е.

bezier(t) = P0 * b0(t) + (P0 + (P1 -  P0) * W1) * b1(t) + (P3 - (P3 - P2) * W2) * b2(t) + P3 * b3(t)

В рез-те углы наклона остаются теми же, но кривая больше "прижимается" к касательной с большим весом

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

Можно построить и сплайн вида P(u), где P - это точки (x, y, z, t), тогда время t - это одна из компонент, а в качестве параметра будет выступать u.
Параметризацию u можно выполнить по пространственным хордам sqrt(dx²+dy²+dz²), координата времени не участвует.
В этом случае t = t₀ + t₁u + t₂u² + t₃u³, и чтобы найти точку на момент t потребуется решить уравнение относительно u, а затем найти уже x, y и z.

Думаю параметризация по длине/хорде здесь вообще ни причем. Гарантируется что шаг по времени между исходными точками достаточно мал (обычно это данные "кадр за кадром"). Др словами нет опасности что сплайн выбросит какую-то "петлю" между 2 исходными точками. Да, мы можем параметризоваться по длине и посчитать время таким же образом как x, y. z - но что это за значения и что с ними дальше делать? Не вижу как они связаны с искомыми W1 и W2

[ssoft]

Направление для размышления).

Кривая Безье 3-го порядка выглядит так:

bezier(t) = p0 * b0(t) + p1 * b1(t) + p2 * b2(t) + p3 * b3(t)

Для удобства пользователя ее представляют с весами в виде:

bezier(t) = P0 * b0(t) + (P0 + (P1 -  P0) * W1) * b1(t) + (P3 - (P3 - P2) * W2) * b2(t) + P3 * b3(t)

Соответственно соотношения между точками pi, найденными с помощью МНК, и точками Pi с весами будет таким

p0 = P0
p1 = P0 + (P1 -  P0) * W1
p2 = P3 - (P3 - P2) * W2
p3 = P3

4-е уравнения, 6-ть неизвестных P0, P1, P2, P3, W1, W2.

Если построить сплайн в том числе и для компоненты времени T, то при параметризации по хордам получим хорошее приближение к правильному движению вдоль кривой. В нужном месте в нужное время).

T = T0 + T1 * t + T2 * t^2 + T3 * t^3

Рассчитанные Ti не являются ci в Ваших выражениях?

c3 * t^3 + c2 * t^2 + c1 * t = user_T

Тогда дополним 4-е уравнения еще такими:

c1 = T1
c2 = T2
c3 = T3
q1 = W1 / 3
q2 = 1 - W2 / 3
c1 = 3.0 * q1;
c2 = 3.0 * (-2.0 * q1 + q2);
c3 = 1 + 3.0 * (q1 - q2);

Уравнений стало больше, чем неизвестных))). 12-ть уравнений, 11-ть неизвестных - P0, P1, P2, P3, W1, W2, c1, c2, c3, q1, q2.
Чем-то нужно пренебречь или дополнить ещё другими условиями или допущениями.

[Igors]

ssoft, завтра подумаю о Вашем предложении. А сегодня наконец доделал второй проход. Очень прилично работает (аттач). "Синицу" уже имеем 

[m_ax]

Ой, товарищь ssoft Вам уже всё разжевал.. Время взять и сделать уже наконец)

[Igors]

Если построить сплайн в том числе и для компоненты времени T, то при параметризации по хордам получим хорошее приближение к правильному движению вдоль кривой. В нужном месте в нужное время).

Получим P1 и P2 для "скорости от пути". И что с ними делать? С весами W1, W2 они никак не связаны. Напр при W1 = W2 = 1 скорость может гулять как хочет в зависимости от исходных точек.

Рассчитанные Ti не являются ci в Ваших выражениях?

К сожалению - нет. Правду сказать, идей нет - может ларчик просто "не открывался" т.е. задача не решаема?

товарищь

Для фанов дуста объясняю еще раз: в существительных мужского рода оканчивающихся на шипящую - мягкий знак НЕ пишется.

[ViTech]

товарищь

Для фанов дуста объясняю еще раз: в существительных мужского рода оканчивающихся на шипящую - мягкий знак НЕ пишется.

Правильно. Тру товарищ должен быть товарищЪ .

[Igors]

Есть мысль искать W1 и W2 на втором проходе. Это выглядит так:

- ключи посчитаны (имеются P1 и P2) в точках напр 10, 20, 30. Пытаемся посчитать W1 и W2 в точках 10 и 30, и, если получится, выкинуть точку 20. 

Чувствую это уже решается, правда пока не знаю как 

[ssoft]

Есть мысль искать W1 и W2 на втором проходе.
...  и, если получится, выкинуть точку 20.

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

Я ранее случайно написал сплайн по времени в виде полинома, а нужно было в виде сплайна Безье), так будет правильнее

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

T =  T0 * b0(t) + T1 * b1(t) + T2 * b2(t) + T3 * b3(t)

Если я правильно понимаю, то запись c3 * t^3 + c2 * t^2 + c1 * t = user_T означает заданный пользователем закон изменения времени вдоль кривой.
Используя известные зависимости

q1 = W1 / 3
q2 = 1 - W2 / 3
c1 = 3.0 * q1;
c2 = 3.0 * (-2.0 * q1 + q2);
c3 = 1 + 3.0 * (q1 - q2);

это уравнение можно привести к виду

W1 * phi1(t) + W2 * phi2(t) = 0;

и решить задачу МНК относительно поиска W1 и W2.
(Так не получится, но можно по-другому. Конкретнее в следующем посте.)

После этого определить P0, P1, P2, P3 из найденых W1, W2, p0, p1, p2, p3
(p0, p1, p2, p3 - найденные с помощью МНК опорные точки для сплайна Безье 3-го порядка)

p0 = P0
p1 = P0 + (P1 -  P0) * W1
p2 = P3 - (P3 - P2) * W2
p3 = P3

[Igors]

Веса введены для удобства работы со сплайном. Их наличие или отсутствие никаким образом не влияет на полученную форму кривых Безье.
В Вашем случае веса связаны также с законом изменения времени вдоль сплайна.
...
Если я правильно понимаю, то запись c3 * t^3 + c2 * t^2 + c1 * t = user_T означает заданный пользователем закон изменения времени вдоль кривой.

Все что делает юзер влияет на форму кривой - иначе эта операция не имеет для него смысла. См напр эффект применения весов на картинке выше. Как работают веса

- да, меняется параметризация, и это зависит только от весов W1 и W2
- НО длины векторов (P1 - P0) и (P3 - P2) также меняются  (множатся на W1 и W2) - причем втихаря                                                                                         

Вот выше было 3 картинки. Само по себе изменение управляющих точек P1 и P2 соответствует изменению скоростей вдоль (x, y, z), т.е. повороту векторов в левом окне. А при изменении весов скорости в крайних точках остаются неизменными, т.к. бОльшие вектора компенсируются параметризацией.

Собсно по-другому "веса" никак и не сделать. Ну и все это довольно стандартно, просмотрев пяток 3D приложений увидим такое же поведение.

это уравнение можно привести к виду

W1 * phi1(t) + W2 * phi2(t) = 0;

и решить задачу МНК относительно поиска W1 и W2.

Так t теперь уже не овечка-костанта. Как его выразить через user_T (исходное время)? 

[ssoft]

Попробовал решить задачу.

Пришел к выводу, что не понимаю откуда "ноги растут" в выражении - откуда оно берется и какой смысл несёт.

c3 * t^3 + c2 * t^2 + c1 * t = user_T

и почему

q1 = W1 / 3
q2 = 1 - W2 / 3
c1 = 3.0 * q1;
c2 = 3.0 * (-2.0 * q1 + q2);
c3 = 1 + 3.0 * (q1 - q2);

Подставляя разные значения вместо W1 и W2 получаем практически произвольные кривые для нахождения t, причем не из какого-то фиксированного диапазона [0,1] (см.аттач).

Вопрос 1 - что это и как конкретно с этим работают?

Вопрос 2 - может мы вообще имеем дело с рациональными сплайнами Безье? Там веса имеют вполне определенный смысл.
http://edu.alnam.ru/book_cpsp.php?id=47