Viivan leikkely

Viivasegmentin ja pääakseleiden suuntaisen suorakulmion leikkaus tasossa Cohen-Sutherland -algoritmilla. Tarkoitus on todeta kulkeeko tason viiva, josta vain päätepisteet tunnetaan, suorakaiteen läpi ja jos niin mitkä ovat ne pisteet joissa viiva leikkaa suorakaiteen rajat. Tämä tieto tarvitaan kun näytöllä on esitettävä mielivaltainen tason viivasegmentti vain siltä osin kuin se on rajaussuorakaiteen sisällä

1001 1000 1010
0001 0000 0010
0101 0100 0110

Ensin muodostetaan viivasegmentin päätepisteille 4-bittiset outcodet (kts. oheinen taulukko). Bitti on ykkönen jos piste on leikkaussuoran 'väärällä' puolella. Jos piste on suorakaiteen sisällä, kaikki bitit ovat nollia.

Onko piste suorakaiteen ylä- tai alapuolella?
- Jos piste on suorakaiteen yläpuolella, on eniten merkitsevä bitti 23 ykkönen.
- Jos piste on suorakaiteen alapuolella, on toiseksi eniten merkitsevä bitti 22 ykkönen.

Onko piste suorakaiteen oikealla tai vasemmalla puolella?
- Jos piste on suorakaiteen oikealla puolella, on toiseksi vähiten merkitsevä bitti 21 ykkönen.
- Jos piste on suorakaiteen vasemmalla puolella, on vähiten merkitsevä bitti 20 ykkönen.

Pikahylkäys- ja pikahyväksymistesteillä karsitaan pois helpot tapaukset.

Pikahyväksymistesti: jos viivasegmentin molempien päätepisteiden outcode on 0000 niin viiva on kokonaan suorakaiteen sisällä eikä leikkelyä tarvita. Koko viiva piirretään suorakulmion sisään.

Pikahylkäystesti: muodostetaan päätepisteiden outcodeista tulos bittitason AND -operaatiolla. Jos tuloksessa on yksikin ykkösbitti, niin viiva ei leikkaa suorakulmiota vaan on kokonaan sen ulkopuolella. Tuloksessa on ykkösbitti jos on jokin rajaussuora jonka suhteen molemmat päätepisteet ovat suorakaiteen ulkopuolella. Viivaa ei tässä tapauksessa lainkaan leikellä, eikä sitä tarvitse piirtää suorakulmion sisään.

Jäljelle jääneet hankalammat tapaukset ratkaistaan käyttäen mm. interpolointia. Ensin muodostetaan bittitason XOR -operaatio viivasegmentin päätepisteiden outcodejen välille. Tuloksessa bitti on ykkönen jos vastaavat bitit outcodeissa ovat erilaisia ja tällöin löytyy rajaussuora.

Viivasegmentin päätepisteet ovat p ja q ja leikauspisteen koordinaatit rajaussuoran kanssa saadaan interpoloimalla:

y = yp (xq - xr) / (xq - xp) + yq (xr - xp) / (xq - xp)
x = xp (yq - yr) / (yq - yp) + xq (yr - yp) / (yq - yp)

Kun leikkauspiste on laskettu, tarkastetaan kumpi päätepiste on rajan ulkopuolella. Ulkopuolella oleva päätepiste korvataan leikkauspisteellä. Viivan uudelle päätepisteelle lasketaan outcode.

Tämä proseduuri täytyy käydä läpi korkeintaan neljä kertaa jonka jälkeen tuloksena on kokonaan suorakaiteen sisälle leikelty viivasegmentti tai on todettu että viiva ei sittenkään kuulu suorakaiteen sisään.


Matte3D

PÄÄSIVU