Autor Wątek: Część wspólna sfery i prostopadłościanu  (Przeczytany 1565 razy)

Offline ropuch

  • Użytkownik

# Kwiecień 20, 2010, 14:20:02
Jestem kiepski z matmy i mam problem z obliczeniem objętości części wspólnej sfery i prostopadłościanu.
Prostopadłościan jest ułożony równo z osiami układu współrzędnych (axis aligned :P).
Szukałem na google, ale jedyne co znajduje to sprawdzanie czy zaszła kolizja, a ja potrzebuję objętość.
Tymczasowo rozwiązuję to poprzez obliczenie objętości części wspólnej prostopadłościanu i bounding boxa tej sfery, ale dokładność tego rozwiązania mnie nie zadowala.
Może mi ktoś pomóc? :)
« Ostatnia zmiana: Kwiecień 21, 2010, 00:27:29 wysłana przez ropuch »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline pinqwin

  • Użytkownik

# Kwiecień 20, 2010, 15:27:31
Rozwiązań jest co najmniej kilka, w zależności jaką chcesz mieć dokładność, możesz opisać np. OctTree na jednym i drugim obiekcie z dosyć dużą ilością podziałów i policzyć liście które są w kolizji. Jeśli chcesz policzyć dokładnie objętość to poszukaj czegoś odnośnie CSG, bo będziesz potrzebował dokładnie wyznaczyć najpierw bryłę - część wspólną z tych dwóch brył.
Na chłopski rozum jeśli będziesz wiedział co jest w kolizji to zawsze będziesz miał do policzenia objętości graniastosłupów chyba że chcesz to policzyć dla sfery idealnej :P wtedy to już tylko całki ;]

Offline Dab

  • Redaktor
    • blog

# Kwiecień 20, 2010, 15:55:20
Tak jak przedmówca pisze -- bez całek się nie obędzie :)
Powiedz lepiej po co ci takie obliczenia, być może są zupełnie niepotrzebne.

Offline ropuch

  • Użytkownik

# Kwiecień 20, 2010, 17:39:09
Jest mi to potrzebne do raytracera.
Muszę znaleźć wagę dla fotonu w zależności ile przestrzeni zajmuje w pewnym obszarze. Kiedy aproksymuję foton prostopadłościanem widać artefakty w niektórych miejscach i chciałbym się ich pozbyć :P
Prędkość działania nie jest priorytetowa, natomiast zajętość pamięci tak. Dlatego wolałbym nie używać metody z octree o której wspomniał pinqwin.
Sfera jest idealna - mam dany środek oraz promień. W przypadku prostopadłościanu przechowuję pozycję punktów o minimalnej oraz maksymalnej pozycji.
Wiem jak używać CSG do renderowania, ale nie wiem w jaki sposób wyciągnąć przy jego pomocy objętość jakiegoś obiektu.

Offline pinqwin

  • Użytkownik

# Kwiecień 20, 2010, 21:06:43
CSG do renderowania to nie koniecznie są operację boolowskie na bryłach, z tego co pamiętam to jest np. biblioteka do CSG chyba OpenCSG czy coś takiego ale to liczy CSG przy pomocy raytracingu, a generalnie musisz wykonać operację boolowska na bryłach, jednak jeżeli to ma być sfera idealna, to CSG się nie nadaje musisz to policzyć strikte matematycznie.

Offline ropuch

  • Użytkownik

# Kwiecień 21, 2010, 00:25:59
"Wymyśliłem" (czyt. przypomniałem sobie z notatek), że można to całkować w sposób podobny do tego na rysunku.
Teraz mam pytanie jak zminimalizować błąd tej metody?
Niestety nie byłem zbyt uważnym uczniem na metodach numerycznych :P

edit: Zapomniałem dodać, że problem dotyczy 3D, obrazek jest tylko poglądowy.
« Ostatnia zmiana: Kwiecień 21, 2010, 00:37:53 wysłana przez ropuch »

Offline Dab

  • Redaktor
    • blog

# Kwiecień 21, 2010, 00:36:19
Po pierwsze możesz zagęszczać punkty próbkowania.
Po drugie zmieniając (w przypadku 2D) prostokąty na trapezy dostajesz już całkiem niezłe przybliżenie.

Offline TeMPOraL

  • Użytkownik
    • devBlog

# Kwiecień 21, 2010, 00:41:45
Hmm... a metoda Monte Carlo? Wybieramy sobie jak najmniejszą bryłę otaczającą (np. sferę albo prostopadłościan) nasze badane obiekty, po czym losujemy punkt wewnątrz tej bryły i sprawdzamy, czy punkt ten leży równocześnie wewnątrz prostopadłościanu i sfery. Jeśli wylosujemy w ten sposób wiele (kilka, kilkadziesiąt tysięcy, może i milion) punktów i pozliczamy, które trafiały do części wspólnej to otrzymamy dobre przybliżenie tego, jak się ma objętość części wspólnej do objętości bryły, wewnątrz której losowaliśmy :).

Offline ropuch

  • Użytkownik

# Kwiecień 21, 2010, 00:44:39
Spróbuję zaimplementować "trapezy" w 3D, dzięki :)
W tym przypadku Monte Carlo chyba będzie zużywać za dużo mocy w porównaniu do rezultatu.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Kwiecień 21, 2010, 11:00:58
Cytuj
"Wymyśliłem" (czyt. przypomniałem sobie z notatek), że można to całkować w sposób podobny do tego na rysunku.
Całkować numerycznie to chcesz? Przecież to można w miarę prostą całką policzyć. :)

Offline ropuch

  • Użytkownik

# Kwiecień 21, 2010, 11:11:21
Całkować numerycznie to chcesz? Przecież to można w miarę prostą całką policzyć. :)

Nie umiem wykombinować wzoru. Możesz mnie jakoś naprowadzić? :)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Kwiecień 21, 2010, 11:25:16
Nie umiem wykombinować wzoru. Możesz mnie jakoś naprowadzić? :)
Przypadek 2D jak na rysunku: dorysuj oś X i Y z punktem zero w środku koła i olej dolną połówkę koła (i tak jest poza prostokątem). Masz funkcję y=sqrt(r*r-x*x), gdzie r jest promieniem koła. Funkcja sqrt(r*r-x*x)-y_bottom jest równa wysokości okręgu koła nad dolną krawędzią prostokąta. Całkując tą funkcję w zakresie wyznaczonym przez prostokąt dostajesz pole powierzchni części wspólnej.

Pułapki:
- jeżeli prostokąt w poziomie wychodzi poza koło, całkujesz tylko w zakresie koła,
- jeżeli dolna krawędź prostokąta jest poniżej osi koła, dzielisz cały przypadek na dwa (drugi liczy dolną część),
- jeżeli górna krawędź prostokąta przycina koło od góry wyznaczasz fragment, w którym górna krawędź wspólnego obszaru jest prosta i tą część liczysz jako osobno pole prostokąta


W przypadku 3D będzie rzecz jasna sporo trudniej. ;)

Offline TeMPOraL

  • Użytkownik
    • devBlog

# Kwiecień 21, 2010, 14:04:19
W przypadku 3D będzie rzecz jasna sporo trudniej. ;)
Może scałkować numerycznie metodę dla 2D po trzecim wymiarze? :>