Lidi, poraďte mi prosím.
Mám zadaný konvexní objekt ve 3D a je popsán jako množina rovin zapsaná ve formě ax+by+cz+d=0. Vždy platí, že existuje nejméně jeden bod, který leží tak, aby všechny roviny jej měly v kladném poloprostoru, který vymezují... laicky řečeno, roviny vymezují konvexní objekt tak, že jejích normály směřují dovnitř toho objektu.
Netušíte, jak by se rychle daly spočítat vrcholy takového objektu ... pro jeho namalování na obrazovku. Hrubou silou se to dá dělat tak, že projdu všechny možné trojice rovin a spočítám průsečíky. Následně každý průsečík podrobím testu, zda se nachází uvnitř tělesa, které vznikne tím, že ze všech rovin odeberu ty tři, které jsem k výpočtu použil. To funguje perfektkně, ale má to háček. Výsledkem je algoritmu O(N^4), což pro kouli o 100 facech dělá 100mil výpočtů (při vzniku 1 mil vertexů). Což je úděsný.
Nemáte někdo aspoň odkaz na nějaký zlepšovák? |
Registrace nového uživatele 
