[C++][OpenGL] Powłoka wypukła

[raV]

Hej!

Czy macie pomysł jak rozwiązać problem powłoki wypukłej (przestrzeń 3D) z zadaną dokładnością (punkty nie wystają poza powłokę o więcej niż x)?

[Toster]

uzyj ukladu sferycznego do opisu punktow. zmieniajac kąty alfa i theta poruszasz sie po sferze o zdanym promieniu r, wiec jak nie tykasz r to zawsze rysujesz po powłoce/sferze.

[raV]

Doprecyzuję: mamy n punktów i chcemy je "opakować", ale z pewną dokładnością.

 

Czyli wybrać punkty, które później połączmy jakoś w ściany... tworząc wielobok

[Toster]

Twoj opis jest zbyt lakoniczny aby zaproponowac rozwiazanie. Ogolne rozwiazanie jest proste w slowach:

1. Definiujesz powierzchnie opisujaca twoja wypuklosc

2. liczysz odleglosc kazdego punktu od powierzchni, jesli jest

[raV]

Muszę wyznaczyć z zadaną dokładnością powłokę wypukłą zbioru punktów z przestrzeni trójwymiarowej, tak aby żaden z punktów nie wystawa ponad nią bardziej niż ustalę.

 

Dla powierzchni znam algorytm Grahama. Dla 3D nie znam odpowiednika.

Jeżeli idzie o tą "dokładność", chodzi o to, żeby zmniejszyć czas obliczeń. Myślałem o podziale przestrzeni na podobszary i otaczaniu "wokseli o krawędzi (np) 10px" ..

[Toster]

a to ja niestety tutaj nie pomoge

ale cos tam na sieci jest http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

dla algorytm Grahama 3d

[raV]

To może chociaż ktoś podpowie, czy da sie tak zapisac wierzcholki, zeby potem w OpenGL łatwo połączyć je ścianami?

Oblicze punkty powłoki, a potem chcialbym je w OGLu ładnie zaprezentować...

[Toster]

triangle strip np albo lista trojkatow. podajesz liste wspolrzednych wierzcholkow (x, y,z) jako vertex buffer, a nastepnie 2 ga list indexow, gdzie kazdy wierzcholek z pierwszej listy ma kolejny index. Ta druga lista zwie sie index bufer. No i dajesz na tym render

[Spider100]

Chyba mowa o otoczce wypukłej w 3d ;]

 

Można zrobić to bruteforce dość prosto.

Bierzesz 4 punkty i tworzysz z nich czworościan wypukły.

Sprawdzasz kolejne punkty:

Jeśli punkt znajduje się wewnątrz czworościanu to go pomijasz jeśli nie to dodajesz go do bryły jako nowy wierzchołek i budujesz ściany podparcia. Trzeba usunąć tutaj wcześniej dodawane wierzchołki które automatycznie mogą znajdować się wewnątrz nowej bryły.

Metoda nie jest najszybsza ale względnie prosta.

 

Opengl tego nie załatwi... No chyba że narysujesz wszystkie możliwości trójkątów na zbiorze wierzchołków z depth testem to wynikiem na ekranie faktycznie będzie otoczka wypukła ale to bezsnesowne i niepraktyczne

[raV]

 

Jeśli punkt znajduje się wewnątrz czworościanu to go pomijasz jeśli nie to dodajesz go do bryły jako nowy wierzchołek i budujesz ściany podparcia. Trzeba usunąć tutaj wcześniej dodawane wierzchołki które automatycznie mogą znajdować się wewnątrz nowej bryły.

 

 

Dzięki za odpowiedź. Być może to, czego szukam to otoczka wypukła a nie powłoka wypukła. Potrzebuję różnych pomysłów, również wolnych (żeby inne były "szybkie" :-)

Powiedz mi tylko, jak sprawdzić, czy punkt leży wewnątrz bryły, a jeżeli leży, to jakie ściany stworzyć a które usunąć ?

[Spider100]

By sprawdzić czy punkt jest wewnątrz bryły wystarczy sprawdzić czy znajduje się dla wszystkich ścian po tej samej stronie płaszczyzn wyznaczanych przez ściany z których składa się bryła. Do tego zadania wystarczy równanie płaszczyzny lub google

Jeżeli nowy punkt leży wewnątrz bryły to go pomijasz.

Jeśli któryś ze starych punktów leży wewnątrz bryły po dodaniu nowego punktu to usuwasz wszystkie ściany z którymi się łączy.

Największy problem tego algorytmu to dodawanie nowego punktu, wymaga znalezienia płaszczyzn stycznych do krawędzi na których będą znajdować się nowe ścianki.

 

Ogólnie jeśli nie masz trochę obycia z geometrią obliczeniową to radzę poszukać gotowych algorytmów pod hasłem "3d convex hull"