Jaki jest najprostszy sposób obliczenia głównej krzywizny trójkąta siatkowego?

20

Mam siatkę i w obszarze wokół każdego trójkąta chcę obliczyć oszacowanie głównych kierunków krzywizny. Nigdy wcześniej tego nie robiłem, a Wikipedia niewiele pomaga. Czy możesz opisać lub wskazać prosty algorytm, który może mi pomóc w obliczeniu tego oszacowania?

Załóżmy, że znam pozycje i normalne wszystkich wierzchołków.

mesh

— ap_
źródło

24

Kiedy potrzebowałem oszacowania krzywizny siatki dla modułu cieniującego, algorytm, na którym ostatecznie się zdecydowałem, był następujący:

Najpierw obliczyłem krzywiznę skalarną dla każdej krawędzi siatki. Jeśli krawędź ma pozycje i normalne , to oszacowałem jej krzywiznę jako: $p_1, p_2$ $n_1, n_2$

krzywizna = \frac{(n_{2)} - n_{1}) \cdot (p_{2)} - p_{1})}{| p_{2)} - p_{1} |^{2)}}

$\text{curvature} = \frac{(n_2 - n_1) \cdot (p_2 - p_1)}{|p_2 - p_1|^2}$

Oblicza to różnicę w normalnych, rzutowanych wzdłuż krawędzi, jako ułamek długości krawędzi. (Zobacz poniżej, jak wymyśliłem tę formułę).

Następnie dla każdego wierzchołka patrzyłem na krzywizny wszystkich dotykających go krawędzi. W moim przypadku chciałem po prostu skalarnego oszacowania „średniej krzywizny”, więc skończyłem na średniej geometrycznej wartości bezwzględnych wszystkich krzywizn krawędzi na każdym wierzchołku. W twoim przypadku możesz znaleźć minimalne i maksymalne krzywizny i przyjąć te krawędzie za główne kierunki krzywizny (być może ortonormalizując je przy normalnym wierzchołku). To trochę trudne, ale może dać ci wystarczająco dobry wynik, co chcesz zrobić.

Motywacją dla tej formuły jest sprawdzenie, co dzieje się w 2D po zastosowaniu do koła:

wzór krzywizny zastosowany do dwóch punktów na okręgu

Załóżmy, że masz okrąg o promieniu (więc jego krzywizna wynosi ) i masz dwa punkty na kole, z ich normalnymi . Pozycje punktów, w stosunku do środka okręgu, będą wynosić i , ze względu na właściwość, że normalne koło lub kula zawsze wskazują bezpośrednio od środka. $r$ $1/r$ $n_1, n_2$ $p_1 = rn_1$ $p_2 = rn_2$

Dlatego możesz odzyskać promień jako lub . Ogólnie jednak pozycje wierzchołków nie będą względne względem środka okręgu. Możemy obejść ten problem, odejmując dwa: $r = |p_1| / |n_1|$ $|p_2| / |n_2|$

\begin{aligned} p_{2)} - p_{1} & = r n_{2)} - r n_{1} \\ = r (n_{2)} - n_{1}) \\ r & = \frac{| p_{2)} - p_{1} |}{| n_{2)} - n_{1} |} \\ krzywizna = \frac{1}{r} & = \frac{| n_{2)} - n_{1} |}{| p_{2)} - p_{1} |} \end{aligned}

$\begin{aligned} p_2 - p_1 &= rn_2 - rn_1 \\ &= r(n_2 - n_1) \\ r &= \frac{|p_2 - p_1|}{|n_2 - n_1|} \\ \text{curvature} = \frac{1}{r} &= \frac{|n_2 - n_1|}{|p_2 - p_1|} \end{aligned}$

Wynik jest dokładny tylko dla kręgów i sfer. Możemy go jednak rozszerzyć, aby uczynić go nieco bardziej „tolerancyjnym”, i używać go na dowolnych siatkach 3D, i wydaje się, że działa dość dobrze. Możemy uczynić formułę bardziej „tolerancyjną”, najpierw rzutując wektor na kierunek krawędzi, . To pozwala, aby te dwa wektory nie były dokładnie równoległe (jak w przypadku koła); po prostu rzutujemy każdy komponent, który nie jest równoległy. Możemy to zrobić, kropkując znormalizowanym wektorem krawędzi: $n_2 - n_1$ $p_2 - p_1$

\begin{aligned} krzywizna & = \frac{(n_{2)} - n_{1}) \cdot normalizować (p_{2)} - p_{1})}{| p_{2)} - p_{1} |} \\ = \frac{(n_{2)} - n_{1}) \cdot (p_{2)} - p_{1}) / | p_{2)} - p_{1} |}{| p_{2)} - p_{1} |} \\ = \frac{(n_{2)} - n_{1}) \cdot (p_{2)} - p_{1})}{| p_{2)} - p_{1} |^{2)}} \end{aligned}

$\begin{aligned} \text{curvature} &= \frac{(n_2 - n_1) \cdot \text{normalize}(p_2 - p_1)}{|p_2 - p_1|} \\ &= \frac{(n_2 - n_1) \cdot (p_2 - p_1)/|p_2 - p_1|}{|p_2 - p_1|} \\ &= \frac{(n_2 - n_1) \cdot (p_2 - p_1)}{|p_2 - p_1|^2} \end{aligned}$

Et voila, na początku tej odpowiedzi pojawiła się formuła. Nawiasem mówiąc, miłą zaletą korzystania z podpisanej projekcji (iloczyn punktowy) jest to, że formuła daje podpisaną krzywiznę: dodatnią dla wypukłych i ujemną dla wklęsłych powierzchni.

Innym podejściem, które mogę sobie wyobrazić, ale którego nie próbowałem, byłoby oszacowanie drugiej podstawowej formy powierzchni w każdym wierzchołku. Można to zrobić, ustawiając podstawę styczną na wierzchołku, a następnie przekształcając wszystkie sąsiednie wierzchołki w tę przestrzeń styczną i używając najmniejszych kwadratów, aby znaleźć najlepiej dopasowaną macierz 2FF. Wtedy głównymi kierunkami krzywizny byłyby wektory własne tej macierzy. Wydaje się to interesujące, ponieważ pozwala znaleźć kierunki krzywizny „sugerowane” przez sąsiednie wierzchołki bez żadnych krawędzi wyraźnie wskazujących w tych kierunkach, ale z drugiej strony jest o wiele więcej kodu, więcej obliczeń i być może mniej odporny numerycznie.

Artykuł, który przyjmuje takie podejście, to Rusinkiewicz, „Szacowanie krzywizn i ich pochodnych na siatkach trójkątów” . Działa poprzez oszacowanie najlepiej dopasowanej macierzy 2FF na trójkąt, a następnie uśrednienie macierzy na wierzchołek (podobnie jak w przypadku obliczania gładkich normalnych).

— Nathan Reed
źródło

1

Do twojej wiadomości, jeśli to ma znaczenie, użyłem twojej odpowiedzi tutaj blender.stackexchange.com/questions/146819/... ale dodając ważenie za pomocą kąta wokół p1. Nie wiesz, czy uważasz to za cenne? W każdym razie możesz skomentować. Dzięki.

— cytryna

20

Aby dodać kolejny sposób do doskonałej odpowiedzi @NathanReed, możesz użyć średniej i krzywej gaussowskiej, którą można uzyskać za pomocą dyskretnego Laplace-Beltrami.

$v_i$

$A(v_i)$ $\frac{1}{3}$ $v_j$

Teraz zadzwońmy $f(v_i)$

Δ_{S.} fa (v_{ja}) = \frac{1}{2) ZA (v_{ja})} \sum_{v_{jot} \in {N.}_{1} (v_{ja})} (do o t α_{ja jot} + do o t β_{ja jot}) (fa (v_{jot}) - fa (v_{ja}))

$\Delta_S f(v_i) = \frac{1}{2A(v_i)} \sum_{v_j \in N_1(v_i)} (cot \alpha_{ij} + cot \beta_{ij}) (f(v_j) - f(v_i))$

Gdzie $v_j \in N_1(v_i)$ oznacza każdy wierzchołek w sąsiedztwie jednego pierścienia $v_i$ .

Dzięki temu obliczenie średniej krzywizny jest dość proste (teraz dla uproszczenia nazwijmy funkcję siatki w interesującym wierzchołku po prostu $v$ ) jest

H. = \frac{1}{2)} | | Δ_{S.} v | |

$H = \frac{1}{2} || \Delta_S v ||$

Teraz przedstawmy kąt $\theta_j$ tak jak

Krzywizna Gaussa to:

K. = (2) π - \sum_{jot} θ_{jot}) / ZA

$K = (2\pi - \sum_j \theta_j) / A$

Po całym tym bólu główne dyskretne krzywizny są określone przez:

k_{1} = H. + \sqrt{{H.}^{2)} - K.} i k_{2)} = H. - \sqrt{{H.}^{2)} - K.}

$k_1 = H + \sqrt{H^2 - K} \ \ \text{and} \ \ k_2 = H - \sqrt{H^2 - K}$

Jeśli interesuje Cię temat (i dodać odniesienie do tego postu), doskonałym przeczytaniem jest: Dyskretne operatory różniczkowo-geometryczne dla triangulowanych 2-kolektorów [Meyer i in. 2003].

Za obrazy dziękuję mojemu byłemu profesorowi Niloyowi Mitrze, gdy znalazłem je w notatkach, które wziąłem za jego wykłady.

— CIFZ
źródło

Obie odpowiedzi są naprawdę dobre, ciężko mi było wybrać. Ponieważ zapytałem o najprostszy sposób, myślę, że Nathan bierze ciasto.

— ap_

2

What Meyer i in. 2003 nie wspomniał (być może wyraźnie) o tym, jak obliczyć krzywiznę wierzchołków granicznych. Ponieważ przyjęli podejście z deficytem kąta, należy odczytać krzywiznę Gaussa dla wierzchołków granicy

K = (π - \sum_{j} θ_{j}) / A_{m i x e d}

$K = (\pi - \sum_j{\theta_j})/A_{mixed}$ .

— teodron

@teodron Czy masz jakieś informacje na temat średniej krzywizny wierzchołków granicy? Czy coś takiego można zdefiniować?

— Museful

@Museful Martwię się trochę o to, że średnia krzywizna nie będzie ujemna, bez względu na rodzaj powierzchni. Jeśli operator podobny do Laplaciana jest zdefiniowany na wierzchołku granicznym, to kwestia oceny tego samego wyrażenia, obejmującego tylko trójkąty, które tworzą powierzchnie incydentu powierzchniowego w

v_{i}

$v_i$ . Są jednak nowsze prace na temat dyskretnych krzywizn ...

— teodron

-1

@ Nathan-Reed: Pytanie tylko do odpowiedzi Nathan-Reed: dlaczego użyłeś środka geometrycznego? Czy to dlatego, że jest „modelowany” według krzywizny Gaussa?

— Gabriel
źródło

3

Jeśli masz nowe pytanie, zadaj je, klikając przycisk Zadaj pytanie . Dołącz link do tego pytania, jeśli pomaga to w zapewnieniu kontekstu. - Z recenzji

— Dragonseel,