Jak mogę skoncentrować punkty w obszarach o wyższej krzywiźnie?

Jak mogę rozmieścić punkty na niejawnej powierzchni, aby skoncentrować je bardziej gęsto w obszarach o wyższej krzywiźnie?

Rozważyłem dodawanie punktów losowo i odrzucanie punktów niewymaganych na podstawie krzywizny, ale chciałbym wiedzieć, czy istnieje lepsze podejście zapewniające bardziej równomierny rozkład na obszarach o podobnej krzywiźnie, a jednocześnie zapewniające wyższą gęstość wymaganą w wysokich regiony krzywizny.

Patrzę konkretnie na użycie tych punktów do triangulacji powierzchni i nie chcę tworzyć więcej trójkątów niż potrzebuję dla stosunkowo płaskich części.

Zostanie to zastosowane do kształtów ze znaną pochodną, aby można było obliczyć krzywiznę w danym punkcie.

Nie musi to być podejście w czasie rzeczywistym.

algorithm triangulation

— trichopaks
źródło

Czy szukasz bardziej dokładnego sposobu pobierania próbek z dystrybucji, bez testu montecarlo, to znaczy? Jeśli nie zależy ci zbytnio na podejściu obliczeniowym (tzn. Szukasz dokładnego podejścia, a nie wysiłku obliczeniowego), mogę znaleźć rozwiązanie, ale można je oczywiście zoptymalizować.

— user8469759,

Czy znasz funkcję analityczną, czy możesz tylko próbkować? Czy znasz jego analityczną pochodną?

— Julien Guertault,

@JulienGuertault Czy moja edycja wyjaśnia?

— trichoplax,

@Lukkio Chciałbym najpierw dokładności, potem optymalizacja może przyjść później, gdy podejście będzie działać.

— trichoplax,

Możesz przyjrzeć się metodom elementów skończonych , które również wykorzystują triangulację (lub bardziej ogólnie: uproszczenia) i często napotykają problem konieczności wyższej gęstości próbkowania w wybranych regionach. Na pewno opracują dla tego algorytmy.

— Wrzlprmft,

Odpowiedzi:

Pomysł, który chciałbym zastosować, byłby następujący: robię przykład dla krzywej, ale powinien być prosty w przypadku aplikacji na powierzchnię.

Powiedzmy, że mamy krzywą jednakowo sparametryzowaną. Powiedzmy, że parametrem krzywej jest . Twoim celem jest próbkowanie punktu odpowiadającego wartości tak aby krzywizna była wysoka. $\gamma$ $s$ $s$

Jeśli uzyskasz wartość krzywizny , będzie to również funkcja . Więc jeśli znormalizujesz funkcję , otrzymasz rozkład prawdopodobieństwa. Jeśli otrzymasz całkę takiego rozkładu, będziesz miał rozkład skumulowany. Nazwijmy tę funkcję skumulowaną . $c$ $s$ $|c|$ $C(s)$

Problem próbkowania z rozkładu podanego przez funkcję skumulowaną jest dobrze znany, więc w zasadzie po pobraniu próbki zestawu wartości , taka wartość będzie związana z interesującymi miejscami. $s_0,s_1,\dots,s_n$

Zastosowanie tej metody w przypadku powierzchni powinno być proste, ponieważ zasadniczo masz dwuwymiarową funkcję rozkładu skumulowanego, ale problem próbkowania jest dokładnie taki sam.

Aby podać trochę szczegółów, jest to w zasadzie próbkowanie z rozkładu, ponieważ funkcja skumulowana obejmuje dwa etapy:

weź losową wartość w przedziale , powiedzmy $[0,1]$ $k$
rozwiązać równanie . $C(s) = k$

To podejście jest dokładne, oczywiście jest drogie, ale jeśli lubisz takie podejście, możesz popracować nad optymalizacją.

— użytkownik 8469759
źródło

Nie ma jeszcze obsługi lateksu.

— joojaa,

Szukałem czegoś, co można by zastosować z niejawną powierzchnią, nawet jeśli nie ma parametryzacji. Czy zawsze można sparametryzować powierzchnię domyślną, jeśli pochodna jest znana?

— trichoplax

Wszelkie pytania, które skorzystałyby z MathJax dla formuł, można dodać do tej meta-odpowiedzi, aby zwiększyć nasze szanse na uzyskanie MathJax. (Ten już został dodany.)

— trichoplax

Pamiętaj, że potrzebujesz funkcji rozkładu wyprowadzonej z krzywizny, powiedziałeś, że możesz wyprowadzić wszystko (przy okazji, jaki rodzaj powierzchni masz? Tj. Równanie). W każdym razie ... co masz na myśli przez „znane pochodne”? znasz wyraźną formułę pochodnej? czy to też jest dorozumiane? (tzn. opisane za pomocą równania różniczkowego)?

— user8469759,

Nawiasem mówiąc ... jeśli krzywa / powierzchnia jest algebrica (to znaczy wyrażona przez wielomian lub racjonalny personel), istnieją metody obliczeniowe oparte na bspline / nurbs, które wyjaśniają, jak przeprowadzić parametryzację takich krzywych. Rzuciłem okiem tutaj docs.lib.purdue.edu/cgi/... , dalszą metodę (nawet zaawansowaną) można znaleźć w jednej z moich ulubionych książek o Nurbs (książka NURBS autorstwa Tillera).

— user8469759,

Dobrym punktem wyjścia jest klasyczny papier Wykorzystanie cząstek do próbkowania i kontrolowania niejawnych powierzchni , opublikowany w SIGGRAPH 1994.

Prosta symulacja cząstek opisana w artykule Próbkowanie niejawnych obiektów za pomocą fizycznych układów cząstek ( Computers & Graphics , 1996) dla krzywych również działa na powierzchniach; przykłady zawiera dynamiczna tekstura niejawnych powierzchni .

Aby zapoznać się z najnowszym przykładem, zobacz Kształt i ton dla niejawnych powierzchni ( Komputery i grafika , 2011).

— lhf
źródło

Poniższe naiwne podejście prawdopodobnie nie zapewni tak ładnie rozłożonych punktów, jak podane przez Lhf , ale powinno być znacznie łatwiejsze do wdrożenia i obliczeniowo szybsze:

$x$ $y$ $d(x,y)$ $x$ $y$ $x$ $y$

$A$

$x$ $d(x,x)$
$A$
$A$
1. $x$ $y$ $A$
2. $z$ $d(x,y)$ $A$
3. $z$ $d(x,y)$ $A$
  - jeśli tak, odrzuć to.
  - $x$ $z$ $y$ $z$ $z$ $A$

$A$

— Wrzlprmft
źródło