Notes 3, Ray Tracing, 7 Maj 96 (bugfixed 9 Feb 97) ****************************************************** Figyelem, a level tartalmat mashol publikalni reszben vagy egeszben az engedelyem nelkul szigoruan tilos !!! ****************************************************** Ahhoz, hogy vegre valami RTRT fele osszejojjon bizony maximalis optimalizaciora van szukseg. Nos egy peldacska arra, hogy ez mit is jelent... Targy: Gomb es sugar metszespont vizsgalatanak masodfoku egyenlete eppen 2 gyokot ad. Ekkor meg kell vizsgalni, hogy mely gyok a szamunkra megfelelo. Hogy tegyuk ezt? Ha ugyesen oldottuk meg a masodfoku egyenletet, akkor a gyokok: b +/- d (ahol 'd' a diszkriminans gyoke) Mivel d pozotiv, ezert biztosan tudjuk, hogy melyik gyok a kisebb. Szamunkra a megfelelo gyok az lesz, amelyik a kisebb, de legyen pozitiv (hiszen a sugar, az csak egy felegyenes) es legyen egy bizonyos tavolsagnal kisebb (ez vagy a minimum kereses, vagy a fenyforras tavolsaga miatt kell). Ime az altalam irt elso megoldas a vizsgalatokra: ( 'k' a kisebb gyok, 'n' a nagyobb, 'D' az adott tavolsag) R1: 1. k ? D / \ k=D ---> egyik gyok sem jo | 2. n ? 0 / \ n>0 n<=0 ---> egyik gyok sem jo | 3. k ? 0 / \ k<=0 k>0 ---> k a keresett gyok | 4. n ? D / \ n=D ---> egyik gyok sem jo | \ n a keresett gyok Ez a rutin vegezhet 1,2,3 vagy 4 vizsgalatot. Nezzuk a kov. megoldasom: R2: 1. k ? 0 / \ k<=0 k>0 / \ 2. n ? 0 2. k ? D / \ / \ n>0 n<=0 k=D ---> egyik gyok sem jo | | \ 3. n ? D \ k a keresett gyok / \ egyik gyok sem jo n=D | \ \ egyik gyok sem jo n a keresett gyok Ez a rutin max. 3 feltetelt vizsgal. Valamint talalhato benne ismetlodo resz, tehat roviditheto a kod. Most nezzuk meg a gyakorlatban milyen esetek vannak, azok milyen gyakoriak (fontosak). Illetve melyik eset meddig tart az egyes rutinoknal? Az esetek: 1. a gomb elottunk van, k es n is nagyobb D-nel. Nincs jo gyok! Ez a legvaloszinubb eset. R1 ideje 1, R2 ideje 2. 2. a gomb elottunk van, n nagyobb D, de k kisebb D. Tehat a jo gyok a k! Ha az objektumok vegignezese optimalis"", akkor ez az eset valoszinutlen. R1 ideje 3, R2 ideje 2. 3. a gomb elottunk van es mindket dofespont D-nel kisebb. A jo gyok megint k! Ez az eset minimum elofordul egyszer (ha van gyok). De utana valoszinubb a 1. eset. R1 ideje 3, R2 ideje 2. 4. a gomb mogottunk van. Nincs jo gyok! Altalaban a targyak a kamera elott mozognak. Ezert ez sem tul gyakori eset. R1 ideje 2, R2 ideje 2. 5. a gombben vagyunk es n kisebb D. A jo gyok az n! Nagyon ritka, specialis eset. R1 ideje 4, R2 ideje 3. 6. a gombben vagyunk es n nagyobb D. Nincs jo gyok! Meg ritkabb, meg specialisabb eset. R1 ideje 4, R2 ideje 3. "" Az objektumok vegignezese akkor az optimalis, ha azt az objektumot vizsgaljuk eloszor, amely a legkozelebb van. Ha egy vegtelenitett listan vannak az objekteink, akkor ezt tehetjuk ugy, hogy megjegyezuk, hogy vagy az elozo fazisban, vagy az elozo pixelnel melyik objektum volt a legkozelebbi, hiszen eleg valoszinu, hogy most is az lesz. Ezert itt kezdjuk a vizsga- lodast (hit cache). Tehat szumma: a legvaloszinubb esetet kiveve, az R2-s algoritmus volt a gyorsabb. Na ez igy nem oke, tehat rajottem, hogy van meg jobb megoldas, keresztezzuk R1 es R2 elonyos vonasait: R3: 1. k ? D / \ k=D ---> egyik gyok sem jo | 2. k ? 0 / \ k<=0 k>0 ---> k a keresett gyok | 3. n ? 0 / \ n>0 n<=0 ---> egyik gyok sem jo | 4. n ? D / \ n=D ---> egyik gyok sem jo | \ n a keresett gyok Ime az idoket osszefoglalo tablazatocska: (SUM6 es AVG6 a hat eset osszege es atlaga, SUM3 es AVG3 pedig az elso harom est osszege es atlaga). # 1. | 2. | 3. | 4. | 5. | 6. # SUM6 | AVG6 # SUM3 | AVG3 ====#=============================#=============#============ R1: # 1 | 3 | 3 | 2 | 4 | 4 # 17 | 2.83 # 7 | 2.33 ----#----+----+----+----+----+----#------+------#------+----- R2: # 2 | 2 | 2 | 2 | 3 | 3 # 14 | 2.33 # 6 | 2.00 ----#----+----+----+----+----+----#------+------#------+----- R3: # 1 | 2 | 2 | 3 | 4 | 4 # 16 | 2.67 # 5 | 1.67 Vagyis altalaban R3, a feltetelek helyes vegrehajtasi sorrendje... ,,,,,,,,,,,,,,,, ;TomCat/Abaddon; ;KaproncaiTamas; ;tomcat@szif.hu; ''''''''''''''''