Сгладить ломаную линию (кривые Безье и т.п.)

Нужно сгладить линию, типа так:

Как это сделать?
Как я понимаю нужно копать в сторону сплайнов... Например кривые Безье... Но не ясно, как сгладить линию из большого количества отрезков, у Безье там всего три-четыре контрольных точек, а если у меня линия из сотни точек состоит, то как сглаживать? Группами по три-четыре точки? Результат будет фигня...
Нашёл вот такое:
http://www.codeproject.com/KB/recipes/BezirCurves.aspx

Но там ограничение в 32 точки, что тоже не подходит... Надо условно бесконечное количество...
Куда копать?

Группами по 4 точки. Результат будет не фигня.
Разумеется, группы - это не (n,n+1,n+2,n+3), (n+4,n+5,n+6,n+7), ..
а (n,n+1,n+2,n+3), (n+1,n+2,n+3,n+4), (n+2,n+3,n+4,n+5).

Хорошо, получил при (n,n+1,n+2,n+3) точки на кривой с определённым интервалом... Получил точки при (n+1,n+2,n+3,n+4)... И как теперь эти два массива объеденить? Или не так надо делать?

Аппроксимировать фрагментом кривой N cтепени (N подбирается по вкусу и требованиям к вычислительной сложности).
Брать группы по N+1 точек, и рассчитывать коэффициенты уравнения кривой.
Алгоритм можно нагуглить, я когда-то помнил наизусть мог в экселе какие угодно коэф-ты найти.

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

Executor
NURBS же, сколько хочешь точек столько и делаешь. Вычислительные затраты на точку растут только от степени кривой, но не от количества точек.

Executor
Я не теоретик, а практик... Поэтому могу посоветовать найти через codesearch исходники библиотеки кривых для Q3Radiant, и в файле splines/splines.cpp внимательно рассмотреть код функции idSplineList::buildSpline() (и сопутствующих). Только в том виде, как там, алгоритм не годится (кваку писали индусы, как известно), нужно начинать расчет не с 3, а с 0, и продолжать не до кол-ва точек, а до кол-ва+3. Индексы, выходящие за пределы массива контрольных точек, обрезать по 0 (для незамкнутого сплайна) или переносить на другой конец массива (для замкнутого).

Executor
> Хорошо, получил при (n,n+1,n+2,n+3) точки на кривой с определённым интервалом... Получил точки при (n+1,n+2,n+3,n+4)... И как теперь > эти два массива объеденить?
Отрезок (n,n+1,n+2,n+3) описывает кривую межу точками n+1 и n+2 , (n+1,n+2,n+3,n+4) между точками n+2 и n+3 и т.д. В зависимости от порядка сплайна будет зависеть гладкость сшивки отрезков (чем выше порядок тем лучше будут сшиваться куски). На границах надо выбрать определенные условия, обычно полагают равенство нулю соответсвующих производных (а ну да, можно еще продолжить, как сказали выше, функцию зеркальным отражением).

Для Безье что-то вроде как я нарисовал на картинке. Только если зеркальные контрольные точки брать как есть, получится очень уж запутанная кривая, надо их как-то уменьшать чтоли, умножать на скаляр < 1.0f ?

kvakvs
> Только если зеркальные контрольные точки брать как есть, получится очень уж запутанная кривая
Зеркалировать можно относительно адекватной прямой проходящую через крайнюю точку и, например, ортоганально последнуму отрезку (фактически это и будут ограничения на производные).

Чем NURBS то не подходит?

Cairo
agg

Всем спс...

KpeHDeJIb
Вроде то что нужно, спасибо... Буду разбираться в НУРБСах... :)

Вроде нашёл:
http://www.nar-associates.com/nurbs/c_code.html

XaeroX
> Я не теоретик, а практик...

Я тоже... :)

  Subroutine to generate a rational B-spline curve using an uniform open knot vector
  Subroutine to generate a rational B-spline curve using an uniform periodic knot vector
  Subroutine to generate rational B-spline basis functions--open knot vector
и т.п.

В чём собственно между ними разница?

Executor
Catmull-Rom попробуй.
В книге "Методы и алгоритмы комп. графики в примерах на Visual C++" Алексея Полякова доступно объясняется.

[A][R][T]
Пробывал, не то...