Войти
ФлеймФорумПрограммирование

Построение оптимальной сетки(дискретизация функции)

#0
0:59, 6 апр. 2021

Пусть имеется нелинейное уравнение двух переменных не имеющее аналитического решения которое нужно многократно решать в реалтайм. Для ускорения предполается предрасчитать поверхность решений и хранить в каждом узле значение+частные производные для быстрой интерполяции кубическим сплайном.
Вопрос в построении оптимальной сетки, при минимальном кол-ве узлов нужно получить максимальную точность. Типа такого,
surf2 | Построение оптимальной сетки(дискретизация функции)
Интуитивно понятно что там где где функция изменяется быстрее нужно плотнее делать сетку как на рисунке.
Интересует вопрос какие есть алгоритмы для этих целей?


#1
2:04, 6 апр. 2021

Гугли triangulation nurbs surface

#2
(Правка: 3:12) 2:40, 6 апр. 2021

Scarabus
не то, на первый взгляд похожие идеи(увеличение детализации на кривизне поверхности), в остальном общего мало. У меня в отличии от свободной 3D поверхности только две независимые координаты, соответственно мне нужна не триангуляция поверхности, а прямоугольная решетка на плоскости.
вот вид сверху,
surf3 | Построение оптимальной сетки(дискретизация функции)
эта сетка похожа на то что надо но построена наугад, естественно финальная сетка будет помельче, крупные ячейки здесь для наглядности.
Также вопрос как быстро найти индексы нужных узлов по входным значениям параметров, если разметка сетки регулярная то индекс можно вычислить без поиска что есть хорошо, для нерегулярной разметки поиск может убить весь профит.

#3
3:13, 6 апр. 2021

Tonal
Так в общем случае, нурбс - это сплайн в какое угодно линейное пространство \(\mathbb{R}^n \to \mathbb{R}^m\), не обязательно зацикливаться только на 3д-поверхностях.

#4
(Правка: 5:25) 4:57, 6 апр. 2021

Delfigamer
Я не зацикливаюсь на 3д-поверхности, задача по сути двумерна.
Не совсем понятно как мне поможет этот НУРБС, понятно что инструмент мощный, но что он дает конкретно в этой задаче?
Как замена обычному кубическому сплайну сомнительно, кроме того что просто удобнее хранить не набор направляющих точек, а частные производные к поверхности(вычисленные не по соседним узлам, а в локальной окрестности узла), сами частные производные нужны также в явном виде для нелинейного МНК(так что возможно будут хранится и вторые производные для кубической интерполяции первых).
Вобщем решение нужно не из области компьютерной графики, а скорее из области вычислительной математики.
Вроде все просто, нужно упаковать функцию в таблицу, вопрос в том как сделать это максимально эффективно.

#5
(Правка: 6:28) 6:28, 6 апр. 2021

Tonal
> Не совсем понятно как мне поможет этот НУРБС, понятно что инструмент мощный, но
> что он дает конкретно в этой задаче?
У рационального сплайна вообще форма кривой не такая, как у полиномиального. Вполне возможно, что для твоей задачи рациональный сплайн как раз подойдёт гораздо лучше, чем полиномиальный с таким же числом параметров.

Tonal
> Как замена обычному кубическому сплайну сомнительно, кроме того что просто
> удобнее хранить не набор направляющих точек, а частные производные к
> поверхности
Там не в производных дело. Посуди сам.
Вот кусок произвольного квадратичного сплайна от двух аргументов:

    \(\displaystyle z = a_0 + a_1 \ x^2 + a_2 \ y^2 + a_3 \ x + a_4 \ y + \ a_5 \ x \ y\)

Вот кусок рационального сплайна второго порядка от двух аргументов:

    \(\displaystyle z = \frac{a_0 + a_1 \ x^2 + a_2 \ y^2 + a_3 \ x + a_4 \ y + \ a_5 \ x \ y}{b_0 + b_1 \ x^2 + b_2 \ y^2 + b_3 \ x + b_4 \ y + \ b_5 \ x \ y}\)

А вычислять эти параметры и там, и там можно всеми способами. В рациональном сплайне точно так же можно как вручную задать все производные для знаменателя для каждого узла, так и выставить только координату w и генерировать производные из соседей по точно таким же алгоритмам (uniform/chordal/centripetal/velocipedal).

#6
(Правка: 6:32) 6:31, 6 апр. 2021

Вот например, мне кажется, на участке \(y \in [0; 1]\) твоей поверхности в #0, рациональный сплайн бы очень даже хорошо зашёл.

#7
(Правка: 9:15) 9:14, 6 апр. 2021

Tonal
это называется rectilinear transformation. идея в том, чтобы для функции f(x, y) подобрать монотонные функции одного аргумента a(u)=x, b(v)=y, для которых определить обратные: u = a*(x), v = b*(x), и далее определить новую функцию:
g(u, v) = f(a(u), b(v)).
далее ты на регулярной сетке дискретизуешь g(u, v), а чтобы узнать значение f(x, y), ты читаешь его из точки функции g:
f(x, y) = g(a*(x), b*(y))

функции a(), b() выбираются совершенно произвольные, они только должны быть инвертируемыми. например, если ты знаешь, что у тебя у функции f(x, y) много всего интересного происходит в районе x ~ 1, то функции можно выбрать так:
x = 1 - u^10
y = v

#8
12:54, 6 апр. 2021

Suslik
> rectilinear transformation
вот прям оно, то что я пытаюсь навелосипедить)
возможность вычислить индексы без поиска походу отсекает все другие варианты разметки.

Delfigamer
попробую оба варианта.

#9
(Правка: 4:06) 2:57, 10 апр. 2021

Неплохая сетка вроде есть, по канонам rectilinear transformation
surf1 | Построение оптимальной сетки(дискретизация функции)
дальше понеслась, диаппазон  для первой производной по х зашкаливает, даблы не вывозят решать уравнение во всем диаппазоне параметров.
график в логаррифическом масштабе по вертикали
dsurf4 | Построение оптимальной сетки(дискретизация функции)
введение линейного наблюдателя позволяет сделать экстраполяцию
dsurf5 | Построение оптимальной сетки(дискретизация функции)
диаппазон больше видимой Вселенной, а степень больше чам у Гугола, хорошо хоть меньше числа Грэмма)))))

Эрмитов локальный сплайн на с условием на нерерывность первой производной на таком масштабе фейлится, но картинка выглядит вполне адекватной для интерполяциии.

Рациональный сплайн должен по идее подойти, но я не вкурил сходу какой выбрать(и как расчитать его параметры).
Потому начал опять велосипедить,
-до этого была попытка аппроксимировать Всю эту поверхность кастомной функцией от 7- табличных функций_параметров.

a*(1+b*x.^(-c)).^(-1/d).*(1+f*x/g).^(g)+h
x=x, a=f1(y),b=f2(y),c=f3(y),d=f4(y),f=f5(y),g=f6(y),h=f7(y)
точность, получилась фиговенькая точность, но при любом фиксированном y это всего 7 параметров!
dsurf6 | Построение оптимальной сетки(дискретизация функции)
интуитивно кажется что такая аппроксимация будучи применена как сплайн не ко всей области определения, а к одной ячейке сетки должна дать типа  "суперпупер" точность.
Для практических целей достаточно поднять точность всего в 1000 раз, осталось придумать как сшить куски и определять параметры.

#10
(Правка: 7:05) 6:58, 10 апр. 2021

если тебе нужна функция, которая очень резко растёт, то есть вот такие пара функций:
https://www.desmos.com/calculator/p9ibyaghmr
у первой из них все производные равны нулю в нуле. у второй — все производные равны бесконечности в нуле. то есть если разложить эти две функции по ряду тейлора, у них радиус сходимости равен нулю. это очень злые функции, гораздо злее любого полинома конечной степени.

#11
(Правка: 1:12) 0:36, 26 апр. 2021

Suslik
> это очень злые функции, гораздо злее любого полинома конечной степени.
и правда злые, я обошелся 16-й степенью со смещением.

+ Показать

сначала я считал сплайн ручками неправильно)
пробовал разные встроенные в Матлаб сплайны, сложилось впечетление что В-сплайны на мелкой сетке ведут себя неплохо, но на крупной рассыпаются(лавинообразный рост ошибки) раньше, Эрмитов кубический сплайн показал себя лучше(причем на хорошей сетке глобальный практически совпадает с локальным).

После того как разобрался с Матлабовским форматом сплайна и мой велосипед заработал)
На радости насчитал пачку производных для Эрмитова локального сплайна 5-й степени(в каждой точке хранится матрица 3х3(значение функции+8производных),  такой сплайна дал +2 порядка точности по сравнению с кубическим.

+ Показать

Дальше ржака, Матлабовский солвер исходного уравнения жестко тупил и я решил замутить свой солвер чтобы быстрее разные сетки строить.
Придумал грубую аппроксимацию для стартовой точки, затюнил метод Ньютона, и... скорость в 20раз быстрее сплайна, занавес)

ЗЫ: Матлабовский солвер тупит походу потому что считает в какой то длинной арифметике +у него нет хорошей начальной точки снаружи задается только диаппазон для поиска
мой солвер в double
0.229337572693541
выxлоп Matlab
0.22933757269354080325821809546192

#12
10:22, 26 апр. 2021

Tonal
лол у тебя самая большая ошибка в самых плоских местах

#13
(Правка: 10:58) 10:56, 26 апр. 2021

Suslik
> лол у тебя самая большая ошибка в самых плоских местах
не, график развернут.
вот в том же ракурсе что и сетка
Spl5err1 | Построение оптимальной сетки(дискретизация функции)

ФлеймФорумПрограммирование