Как я могу сосредоточить точки в областях более высокой кривизны?

11

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

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

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


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

Это не должен быть подход в реальном времени.

Trichoplax
источник
Вы ищете более точный способ выборки из дистрибутива, без теста Монте-Карло? Если вас не волнует вычислительный подход (т.е. вы ищете точный подход, а не вычислительные усилия), у меня могло бы быть решение, но оно, конечно, могло бы быть оптимизировано.
user8469759
3
Знаете ли вы аналитическую функцию или вы можете только пробовать ее? Вы знаете его аналитическую производную?
Жюльен Геро
@JulienGuertault Мое редактирование разъясняет?
Трихоплакс
@Lukkio Сначала мне нужна точность, затем оптимизация может прийти позже, когда подход заработает.
Трихоплакс
1
Возможно, вы захотите взглянуть на методы конечных элементов , которые также используют триангуляцию (или, в более общем случае: симплексы) и часто сталкиваются с проблемой необходимости более высокой плотности выборки в выбранных регионах. Они обязаны разработать алгоритмы для этого.
Wrzlprmft

Ответы:

11

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

Допустим, у нас есть кривая равномерно параметризованная. Допустим, параметр кривой . Ваша цель - выбрать точку, соответствующую значению , чтобы кривизна была высокой.s sγss

Если вы получите величину кривизны , это тоже будет функцией . Итак, если вы нормализуете функцию, вы получите распределение вероятностей. Если вы получите интеграл от такого распределения, у вас будет накопительное распределение. Назовем эту накопительную функцию .с | с | C ( s )cs|c|C(s)

Проблема выборки из распределения, заданного кумулятивной функцией, хорошо известна, поэтому, как после того, как вы выбрали набор значений , такое значение будет связано с интересующими точками.s0,s1,,sn

Применение этого метода к случаю поверхности должно быть прямым, поскольку в основном у вас есть двумерная кумулятивная функция распределения, но проблема выборки точно такая же.

Просто, чтобы дать некоторые подробности, это в основном выборка из распределения, учитывая, что накопительная функция включает в себя два этапа:

  1. принять случайное значение в интервале , скажем,к[0,1]k

  2. решить уравнение .C(s)=k

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

user8469759
источник
1
Пока нет поддержки латекса.
joojaa
Я искал что-то, что можно было бы использовать с неявной поверхностью, даже если у нее нет параметризации. Всегда ли возможно параметризовать неявную поверхность, если известна производная?
Трихоплакс
Любые вопросы, которые будут полезны для формул MathJax, могут быть добавлены к этому мета-ответу, чтобы увеличить наши шансы на получение MathJax. (Этот уже был добавлен.)
trichoplax
Помните, что вам нужна функция распределения, полученная из кривизны, вы сказали, что можете вывести все (кстати, какая у вас поверхность? Т.е. уравнение). Во всяком случае ... что ты имеешь в виду под "производным известным"? Вы знаете явную формулу производной? или это тоже неявно? (т.е. описывается с помощью дифференциального уравнения)?
user8469759
1
Кстати ... если кривая / поверхность алгебраическая (я имею в виду выраженная полиномом или рациональным персоналом), существуют вычислительные методы, основанные на bspline / nurbs, которые объясняют, как выполнить параметризацию таких кривых. Я тут заглянул docs.lib.purdue.edu/cgi/… , дальнейший метод (даже продвинутый) можно найти в одной из моих любимых книг о Nurbs (книга NURBS от Tiller).
user8469759
2

Хорошей отправной точкой является классическая статья « Использование частиц для выборки и контроля неявных поверхностей» , опубликованная в SIGGRAPH 1994.

Простое моделирование частиц, описанное в статье « Выборка неявных объектов с помощью физических систем частиц» ( Computers & Graphics , 1996) для кривых, работает и для поверхностей; см. Динамическую текстуру для неявных поверхностей для примеров.

Более свежий пример см. В разделе Отображение формы и тона для неявных поверхностей ( Computers & Graphics , 2011).

LHF
источник
2

Следующий наивный подход, вероятно, не даст столь же хорошо распределенных точек, как те, которые дает Lhf , но он должен быть намного проще в реализации и в вычислительном отношении быстрее:

Для двух точек и обозначим через среднее расстояние, на которое вы хотите, чтобы точки со средней кривизной и имели, например, некоторую постоянную, умноженную на обратную величину средней кривизны и .у д ( х , у ) х у х уxyd(x,y)xyxy

Теперь соберите свою коллекцию точек последовательно:A

  1. Выберите случайную точку и добавьте две точки, так что все три точки образуют равносторонний треугольник с длиной ребра .д ( х , х )xd(x,x)

  2. Добавьте все точки к и отметьте их как соседние.A

  3. Повторно делайте следующее, пока в больше не будет смежности :A

    1. Выберите две соседние точки и от . Отметьте их как несмежные.у АxyA
    2. Рассмотрим точку которая имеет расстояние от обеих этих точек. Из двух возможных таких точек выберите ту, которая направлена ​​наружу от (это требует некоторой работы, но должно быть простым).d ( x , y ) Azd(x,y)A
    3. Проверьте, находится ли ближе, чем к любой точке из которая все еще смежна с другой точкой.d ( x , y ) Azd(x,y)A

      • если да, откажитесь.
      • если нет, знак и , а также и , как р дом и добавить к .z y z z AxzyzzA

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

Wrzlprmft
источник