Gdzie przechowywać kształty w ośmiu?

Question

Niewielkie doświadczenie w zakresie dotychczasowych decyzji dotyczących projektowania ... Opracowałem ośmioetapową strukturę, która może przechowywać punkty. Zdecydowałem się ograniczyć rekurencję "pokoleń" w oparciu o pewien bazowy rozmiar woksela. Węzły potomne są tworzone tylko po dodaniu punktów do tego węzła. Jest to , a nie dynamiczna aplikacja graficzna - ta oś i obiekty w niej zawarte są statyczne, więc wstępne przetwarzanie w celu poprawy wydajności nie jest problemem.

Teraz chciałbym dodać "kształty" do mojej ósemki - konkretnie, siatkę powierzchni złożoną z trójkątów. Wierzchołki tych trójkątów nie odpowiadają punktom zapisanym w ósemce. Jak przechowywać te kształty w ósemce? Widzę dwie opcje ...

Szary węzły są „puste”, że nie mają one kształty. W wariancie 1 kształty są przechowywane w każdym węźle, który przecinają - tj. Węzeł 1a zawiera kształt 1 i 4c & 4d kształt2. W wariancie 2 kształty są przechowywane tylko w najmniejszym węźle, który przecinają - tj. Węzeł 1a zawiera kształt 1, a węzeł 4 zawiera kształt2.

Większość postów na temat ośmiornic, które widziałem, zakłada Alt1, ale nigdy nie wyjaśniają dlaczego. Alt2 ma dla mnie więcej sensu i stworzy tylko dodatkową pracę dla tych kształtów, które znajdują się na granicach węzłów. Dlaczego Alt1 jest lepszy?

Edytuj: Aby wyjaśnić, moim językiem używanym w implementacji jest C++, więc wolałbym przykładowe implementacje w tym języku, ale pytanie jest niezależne od języka. Przepraszam, jeśli to nieprawidłowe użycie tagu.

Edycja2: chociaż nie jest to bezpośrednio związane z kwestią przechowywania kształtów, this link ma dobrą dyskusję na temat przejścia oktree, które kryje się za pytaniem. Pomyślałem, że może pomóc każdemu, kto jest zainteresowany pracą nad tym pytaniem.

Answer 1

ALT1 jest poprawny. Biorąc pod uwagę, że chcesz ograniczyć maksymalną liczbę obiektów (trójkąty) w węźle, będziesz musiał podzielić węzły, które będą zawierać wiele trójkątów. To nieuchronnie prowadzi do posiadania pojedynczego trójkąta w wielu węzłach, chyba że chcesz podzielić trójkąty tak, aby pasowały idealnie do węzłów ósemkowych (to zależy od twojej aplikacji, generalnie nie zalecałbym tego i np. Do raytracingu rzeczywiście tak naprawdę nie jest zrobione) .

Jako kontrprzykład wyobraź sobie ALT2 zawierający szczegółowy model królika Stanforda, stojącego na dużym trójkącie. Duży trójkąt uniemożliwi podział podrzędny węzła na podwęzły, a tym samym twoja liczba będzie tak dobra, jak gdybyś nie miał ósemki.

Alternatywnie, trzeba by zachować duży trójkąt w węźle głównym i podzielić go na podwęzły, które zawierałyby resztę mniejszych trójkątów. Posiadanie trójkątów nie tylko w węzłach liści, ale także w innych węzłach prawdopodobnie utrudni przejście przez ósemki (ale to również zależy od twojej aplikacji). Jeśli będziemy trzymać się scenariusza raytracingu, aby znaleźć najbliższe przecięcie promienia i trójkąta, musisz sprawdzić węzeł pod kątem wszystkich węzłów w celu znalezienia najbliższego przecięcia i będziesz musiał śledzić ruch promienia do następnego węzła, na wszystkich poziomów drzewa jednocześnie. Z drugiej strony, jeśli twoja geometria jest tylko w liściach, testujesz trójkąty w liściach w kolejności, w jakiej promień je odwiedza (przy zachowaniu śladów trójkątów, które były już testowane, aby uniknąć testowania tego samego trójkąta dwa razy).

Answer 2

Jest to bardziej w odniesieniu do quadtrees, które bardziej mi się podobają, ale są one odpowiednikiem 2D ośmiornicy; więc może mieć zastosowanie.

Ogólne podejścia do wstawiania: Każdy wewnętrzny węzeł kwadrantu ma pojemność, która jest maksymalną liczbą "obiektów", które może pomieścić ćwiartka czworoboku. Jeśli osiągniesz pojemność, podzielisz, a następnie wstawisz wszystkie "obiekty" do odpowiedniego kwadrantu dziecka. Będziesz także miał punkt, w którym podzielisz i jeden lub więcej twoich "obiektów" rozciąga się na wiele kwadrantów dziecka; uważaj na ten przypadek podczas wstawiania/wysyłania zapytań. Ogólnie rzecz biorąc, pojemność węzła jest wybierana tak, aby faworyzować szybsze wstawianie lub wysyłanie zapytań.

Biorąc to pod uwagę, nie widzę niczego złego w prezentowanym obrazie ALT2. Ale moje założenie o tym, dlaczego zawsze widzisz obraz ALT1 jest domyślnym podejściem, gdy wstawianie do niezajętej komórki polega na dzieleniu, a następnie wstawianiu.