Binary space partitioning

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Drzewo BSP)
Przejdź do nawigacji Przejdź do wyszukiwania

Binary space partitioning, BSPalgorytm polegający na rekurencyjnym dzieleniu danej przestrzeni na zbiory wypukłe przy pomocy hiperpłaszczyzn. Powstaje wówczas struktura danych zwana drzewem BSP (ang. BSP tree).

Wykrywanie kolizji — nazwa grupy algorytmów stosowanych w grafice komputerowej i symulacjach komputerowych służących znajdowaniu ograniczeń ruchu w scenach dwu- i trójwymiarowych. Najogólniej, algorytm wykrywający kolizję odpowiada na pytanie, czy przemieszczenie jakiegoś obiektu w danym kierunku jest możliwe, czy może na drodze ruchu znajdują się przeszkody, tj. inne obiekty ruchome lub nieruchome. W symulacjach ciał odkształcających się (np. tkanin) należy również wykrywać kolizje pomiędzy różnymi fragmentami tego samego obiektu.Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.

Podstawowym zastosowaniem drzew BSP jest określanie porządku (od przodu w tył) obiektów znajdujących się na trójwymiarowej scenie, co jest fundamentalne przy jej renderowaniu realizowanym przez programy do tworzenia grafiki trójwymiarowej. Pozwalają one na znaczne uproszczenie procesu określania widoczności obiektów przez kamerę/obserwatora.

Siatka to w grafice 3D i CAD dwa lub więcej wielokątów połączonych ze sobą krawędziami. Zwykle siatki tworzone są z trójkątów lub czworokątów wypukłych.Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.

Obliczanie widoczności[ | edytuj kod]

Obliczanie widoczności odbywa się na zasadzie sprawdzania, po której stronie płaszczyzny danego wierzchołka znajduje się kamera/obserwator. Na tej podstawie wybierane jest lewe lub prawe dziecko wierzchołka (bardziej odpowiednie jest określenie przednie lub tylne dziecko), które samo zawiera swoją płaszczyznę podziału i dwoje dzieci określających obiekty będące z przodu lub z tyłu tej płaszczyzny. Ostatnim dzieckiem jest liść, który zawiera właściwą geometrię do wyświetlenia dzięki temu szybko odrzucana jest znaczna część niewidocznych obiektów.

Usuwanie niewidocznych powierzchni to w komputerowej grafice 3D jeden z pierwszych etapów poprzedzających wyświetlanie obrazów, w którym określa się, które z obiektów umieszczonych na scenie są w danym rzucie widoczne (w całości lub tylko częściowo).Śledzenie promieni (ang. ray tracing) – technika generowania fotorealistycznych obrazów scen trójwymiarowych. Opiera się na analizowaniu tylko tych promieni światła, które trafiają bezpośrednio do obserwatora. W rekursywnym śledzeniu promieni bada się dodatkowo promienie odbite zwierciadlane oraz załamane.

Po wybraniu liścia często następuje sprawdzanie jakie inne liście są z niego widoczne. Najczęściej wykorzystuje się do tego portable visibility sets, czyli pola bitowe, których poszczególne bity określają po kolei widoczność każdego liścia. Bit określający widoczność samego siebie ma zawsze wartość 1.

Drzewo kd (skrót od drzewa k-wymiarowego) – struktura danych używana do dzielenia przestrzeni. Drzewa kd są przydatne w tworzeniu struktur w niektórych zastosowaniach takich jak wyszukiwanie najbliższych sąsiadów lub znajdywanie punktów w prostokątnych obszarach (w czasie O ( n + k ) {displaystyle O({sqrt {n}}+k)} , gdzie n {displaystyle n} to całkowita liczba punktów, k {displaystyle k} - liczba znalezionych punktów).Grafika 3D (grafika trójwymiarowa) – nazwa jednej z dziedzin grafiki komputerowej, zajmującej się głównie wizualizacją obiektów trójwymiarowych. Nazwa pochodzi od angielskiego sformułowania Three-Dimensional Graphics.


Podstrony: 1 [2] [3] [4]




Warto wiedzieć że... beta

Hiperpłaszczyzna (dawn. zbiór liniowy) w przestrzeni euklidesowej n-wymiarowej to zbiór rozwiązań równania postaci:
Bryła geometryczna – zbiór punktów przestrzeni trójwymiarowej homeomorficzny z pewnym wielościanem. W innym ogólniejszym ujęciu jest to trójwymiarowa figura geometryczna.
Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
Drzewo brył ograniczających (ang. bound volume hierarchy, BVH) – struktura danych do przechowywania i szybkiego wykonywania zapytań na temat obiektów w przestrzeni trójwymiarowej. Najczęściej stosowana w grafice komputerowej do akceleracji algorytmu śledzenie promieni (ray tracing) oraz w symulacjach fizyki ciał do akceleracji detekcji kolizji (np. w grach komputerowych).
Zbiór wypukły – pojęcie geometryczne, podzbiór pewnej przestrzeni zawierający wraz dowolnymi dwoma jego punktami odcinek je łączący. Wspomniana przestrzeń może być euklidesowa, afiniczna, a nawet tylko liniowa (wektorowa); we wszystkich przypadkach wymaga się, by ciało skalarów było uporządkowane, zwykle jest to ciało liczb rzeczywistych, bądź liczb zespolonych.
Gra komputerowa (gra wideo, ang. video game) – rodzaj oprogramowania komputerowego przeznaczonego do celów rozrywkowych bądź edukacyjnych (rozrywka interaktywna) i wymagającego od użytkownika (gracza) rozwiązywania zadań logicznych lub zręcznościowych. Gry komputerowe mogą być uruchamiane na komputerach osobistych, specjalnych automatach, konsolach do gry, telewizorach, telefonach komórkowych oraz innych mobilnych urządzeniach, nazywanych łącznie platformami sprzętowymi. Zadania stawiane przed graczem w grach komputerowych różnią się w zależności od gatunku i mogą polegać na przykład na rozwiązaniu zadania logicznego, eliminacji wirtualnych przeciwników czy też rywalizacji ze sztuczną inteligencją bądź innymi graczami (gra wieloosobowa); interaktywna rozrywka w celach zawodowych nosi nazwę sportu elektronicznego.
Scena (ang. scene) to w grafice 3D zbiór niezależnych, osobno stworzonych trójwymiarowych obiektów, zgrupowanych i zaaranżowanych w jedną scenę. Poza obiektami 3D w scenie znaleźć się mogą obiekty nieprzeznaczone do wizualizacji, ale związane z reżyserią sceny, takie jak: kamera (obserwator), źródła światła, emitery (obiekty emitujące cząsteczki), odpowiednie obiekty pomocnicze służące do kontroli animacji obiektów 3D, ścieżek ich ruchu oraz innych efektów specjalnych. W większości silników graficznych scena jest niema nieskończone (występują ograniczenia sprzętowe) i może znaleźć się tam prawie dowolna liczba obiektów.

Reklama