Algorytm z Quake III - obliczanie odwrotności pierwiastka

Film objaśnia jak jest liczona odwrotności pierwiastka kwadratowego w grze Quake III. Pokazana metoda jest wydajniejsza, niż przy używaniu standardowych funkcji matematycznych

[p.....n]

Jak to było? "I kolejny dzień w życiu nie potrzebowałem do niczego wzorów skróconego mnożenia" :D

[ChamskoCytuje]

@pan_login: Nadal mu niepotrzebna, użył odwrotności pierwiastka kwadratowego a nie wzorów skróconego mnożenia ( ͡° ͜ʖ ͡°)

[K.....7]

@ChamskoCytuje: ba więcej tu trików wynikających ze specyfikacji float niż samej matematyki

[W.....i]

Na studiach przedmiot o nazwie "metody numeryczne", który oczywiście MUSIAŁ być ekstremalnie nudny i sprowadzać się do wykuwania wyprowadzeń wzorów, żeby zaliczyć kolokwium. A potem człowiek uruchamia sobie taki filmik i zdaje sobie sprawę, że MOŻNA wytłumaczyć coś w ciekawy, sensowny i zrozumiały sposób, tylko po prostu nikomu się nie chce. Lepiej zgnoić studenta i uwalić połowę semestru. Typowa edukacja w Polsce

[borsuk321]

@WykresFunkcji: na uczelniach musieliby pracować ludzie z pasją do nauczania innych, talentem do przekazywania wiedzy, zaangażowaniem, wykraczać ponad tylko znajomość tematu. Za tym by musiały iść konkretne pieniądze żeby takie jednostki garnęły się do pracy na uczelniach. W obecnym systemie to czysty przypadek że ktoś akurat lubi uczyć i jednocześnie jest profesorem z jakiejś dziedziny np. matematyki. To coś jak szansa na trafienie uczciwego polityka.

[K.....7]

Genialne rozwiązanie.

[Bilut]

Pokazana metoda jest wydajniejsza, niż przy używaniu standardowych funkcji matematycznych

W tamtych czasach. W tej chwili jest ileś zoptymalizowanych instrukcji do liczenia odwrotności pierwiastka w rozszerzeniach wektorowych CPU. No i poza tym to była metoda przybliżona (na tyle, aby efekty graficzne miały sens) - nie nadaje się do obliczeń wymagających precyzji. A przynajmniej nie z zastosowaniem pojedynczego kroku przybliżenia.

[terazpolskanow]

Tutaj po polskiemu na wikipedii:
https://pl.wikipedia.org/wiki/Szybka_odwrotno%C5%9B%C4%87_pierwiastka_kwadratowego

[krzywy_odcinek]

Carmack to jednak fachowiec był.

[nie_znam_sie2]

@krzywy_odcinek: pamiętam też jego trick z użyciem koprocesora w latach 90tych do rysowania tekstur w Quake'u. Problem z grami 3d był wtedy taki, że tekstury były nakładane na obiekty liniowo - po taniości. I przez to "pływały" na nich gdy się poruszaliśmy i słabo to wyglądało - im bardziej nachylona była ściana tym gorzej. Ale było to robione po taniości, bo matematyka by kazała wykonywać dzielenia do dokładnego nakładania tekstury,

[tokone]

@krzywy_odcinek: Przecież jest napisane w artykule, że to nie Carmack ten algorytm wymyślił tylko Terje Mathisen.

[ImperiumCienia]

Chyba mamy podobne profile na youtubie bo dzisiaj też mi się to wyświetliło w proponowanych

[K.....7]

@ImperiumCienia: ja wczoraj wieczorem to oglądałem bo było w proponowanych, może algorytm YT jest mniej skomplikowany niż nam się wydaje

[zarowka12]

Było już wielokrotnie na wykopie, ale warto przypomnieć.

[j.....k]

q3 thebest

[szokram]

Zajmuje się DSP na FPGA i tu to dopiero są sztuczki. Czasem trzeba mocno kombinować aby przetworzyć dane z ADC z próbkowaniem 250Msps nie zjadając przy okazji większości zasobów. Pokazane rozwiazanie bardzo fajne.