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