Адаптивные алгоритмы построения поверхностей

Vlad128

Где бы такое найти? Типа есть отображение из подмножества R^2 в R^3, задающее поверхность. Нужен алгоритм, который сам подберет сетку и построит поверхность.
И еще бонус-вопрос, что-то все забыл: есть ли общий метод нахождения производной по начальным данным? Типа дифур \dot x = f(x) x(0) = x0, хочется найти d x(T)/d x0.

blackout

Один из вариантов - строится квадратная сетка, потом если на каком-то квадрате функция ведет себя плохо этот квадрат делится на 4 в 2 раза меньших и т.д., пока на каждом квадрате функция не ведет себя хорошо. При это следится за тем, чтобы любые два соседних по стороне квадрата либо были равны, либо отличались по размеру ровно в 2 раза.
Когда сетка готова - каждый квадрат делится на 2 или больше треугольника и получается триангуляция.
Критерий плохости квадрата можно выбирать любой - например квадрат ABCD можно считать плохим, если f(A)+f(C)-f(B)-f(D) > epsilon
В целом этот алгоритм не супер.

Vlad128

В целом этот алгоритм не супер.
да, приходят в голову самому подобные алгоритмы и чувствуется, что они не супер. Но в твоем описании встретил полезную идею, спасибо.
Вот есть всякие алгоритмы, которые строят поверхности уровня, а точнее, поверхности, где для каждого отрезка можно сказать, пересекает ли он поверхность и если пересекает, то где, а вот для моего случая что-то ничего хорошего не находится.
Если поможет, то мне нахаляву известна нормаль к поверхности в каждой точке. Производные по (u,v к сожалению, похоже, что аналитически не считаются (см. бонус вопрос).
Было бы очень неплохо делить квадрат не средней точкой, а смещенной от центра исходя из какой-нибудь априорной оценки. Вот придумать такую оценку что-то не получается.

Vlad128

А какие мысли по поводу заменить квадраты сразу на треугольники и добавлять центральную точку треугольника в качестве дополнительной? Чем хуже, что-то я не могу догнать?

Vlad128

если f(A)+f(C)-f(B)-f(D) > epsilon
там кстати R^2 -> R^3, а не R^2->R, для второго случая есть очень хорошие и проверенные алгоритмы как раз :crazy:
но тут можно и другие условия подогнать, например, максимальное расстояние между образами.

lenmas

А чего не хочется maple какой использовать?

BSCurt

А какие мысли по поводу заменить квадраты сразу на треугольники и добавлять центральную точку треугольника в качестве дополнительной? Чем хуже, что-то я не могу догнать?
С такими треугольниками сетка будет весьма не регулярной казалось бы, и старые грани изначальной триангуляции никуда не изменяются в отличие от разбиения на квадраты, т.е. при постановке центральной точки улучшение точности будет только по внутренности треугольника.
Может быть лучше бить треугольник на четыре, добавляя новые вершины в серединах граней

Perce

Может быть не совсем по теме, но посоветую просмотреть хотя бы бегло книжку Скворцов А.В. Триангуляция Делоне и её применение.
Upd: Ну и ещё Глава 6 (Parametric surface meshing) из книги P.-L. George, H. Borouchaki. Delaunay Triangulation and Meshing. Application to Finite Elements. У меня только бумажный вариант есть, не знаю, есть ли электронный где-нибудь в свободном доступе.

stm7543347

если на каком-то квадрате функция ведет себя плохо
... то как об этом узнать?

blackout

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

Vlad128

Ну тут же две триангуляции, одна на (u,v другая на (x,y,z второй управлять как бэ и не очень-то получается при подобных алгоритмах.
Но с другой стороны да, если даже на (u,v) треугольники начинают вырождаться, то это плохо, поиск по сути одномерным становится.

Vlad128

Parametric surface meshing
ну да, так это и называется :) Спасибо, будем искать книгу.

blackout

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

gala05

нейронная сеть кохонена, думаю, сгодится

Vlad128

Прикольная идея там у них, находят первую квадратичную форму поверхности, зная метрику получают отображение области определения, в другую, которая уже дальше отображается «изометрически» (почти) на поверхность. На этой новой области определения строят красивую триангуляцию. Но насколько это будет хорошо работать, если квадратичную форму считать приближенно, хз. Попробую метод , наверное.

stm7543347

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

blackout

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

Vlad128

любые два соседних по стороне квадрата либо были равны, либо отличались по размеру ровно в 2 раза.
а можно еще глупый вопрос: зачем и почему строго в 2?

Vlad128

Плохость, кстати, собираюсь определять по размеру образа и по отклонению нормали от известной (я там писал, что мне известная точная нормаль к поверхности).

blackout

а можно еще глупый вопрос: зачем и почему строго в 2?
Тебе в конце нужно будет каждый квадрат разделить на треугольники. При этом не должно оказаться такой ситуации, что вершина одного треугольника лежит на стороне другого и при этом не совпадает с его вершиной.
Теперь у тебя есть квадрат и соседние с ним по каждой стороне. Если соседние по стороне квадраты в два раза меньше, то ты делишь эту сторону пополам, если равны или в два раза больше, то не делишь. В результате у тебя получается квадрат у которого некоторые стороны поделены пополам и ты легко строишь его триангуляцию:

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

Vlad128

Круто, не задумывался о таком, спасибо!
Оставить комментарий
Имя или ник:
Комментарий: