Számítógépi grafika
Vágás

Feladat:

Ha az alakzat nagyobb, mint a képtartomány¨, amelyben megjelenítendő, akkor a kívül eső része­ket el kell hagyni, azaz az alakzatról „le kell vágni”, röviden szólva: az alakzatot vágni kell.

Tegyük föl, hogy az alakzat (egyenes) szakaszokra bontható. (A tartományok vágása hasonlóan megoldható, bár további problémákat is fölvet.) Az alábbiakban szakaszok vágását vizsgáljuk.

Cohen-Sutherland módszere

Cohen-Sutherland algoritmusa a következő felismerésre épít:

A szakasz és a képtartomány kölcsönös viszonya lényegében a következő négyféle lehet: a sza­kasz

1.        teljesen benne van a képtartományban (l. az ábrán az A szakaszt),

2.        csak egyik végpontja esik a tartományba (l. az ábrán az B szakaszt),

3.        bár mindkét végpontja kívül esik a tartományon mégis a „középső” darabja a tartományban fut (l. az ábrán az C szakaszt),

4.        és a tartomány nem rendelkezik közös ponttal (l. az ábrán az D szakaszt).

1. ábra. Szakasz és képtartomány viszonya.

Mindenek előtt próbálja ki: mire lehet gondolni (csvagasFP.exe,/CSvagasTP.exe)!

A lényeg

Osszuk fel a képtartományt magába foglaló síkot 9 részre, és sorszámozzuk meg az alábbiak szerint. Vegyük észre a sorszámokban a „bináris szabályszerűséget”!

9=10012

1=00012

3=00112

8=10002

0=00002

2=00102

12=11002

4=01002

6=01102

(-: Ugye megvan a bináris logika? :-)

Egy-egy bit tartozik –a felső, a „balsó”, az alsó és a „jobbsó”– a négy kívül levő síkrészhez.ª

A vágandó szakasz végpontjait kódoljuk a szerint, melyik tartományba esik. Ha a szakasz mind­két végpontja  0-kódú, akkor kirajzolható. Ha nem, akkor gondolkodni kell! :-)

Vegyük észre: akkor és csak akkor fut a szakasz „egyértelműen szerencsétlen” tartomány(ok)ba, ha a két végpont-kód bites ÉS-művelet eredménye nem 0 értékű. (Például: 9 ÉS 3 = 10012 ÉS 00112 = 00012… éppen az a bit 1-es, amelyik a „szerencsétlen” tartományhoz van rendelve.)

Ha egyéb eset áll fenn, akkor egyszer vagy kétszer metszi a (0-kódú) képtartomány határoló egyeneseit. A feladat e metszéspontok megtalálása. Valahogy így ©:

Eljárás CSVagas(Változó p1,p2:TPont):

    Változó
      c,c1,c2:TKod;  p:TPont

    c1:=VégpontKód(p1); c2:=VégpontKód(p2)

    Ciklus amíg nem ((c1=0) és (c2=0)) [legalább egyik végpont még nincs belül]
                és ((c1 ÉS c2)=0)  [a szakasz nem biztos, hogy kívül fut]

      Ha c1=0 akkor [p1 OK. Nézzük a másikat: Csere(p1,p2)]
        p:=p1; p1:=p2; p2:=p;  c:=c1; c1:=c2; c2:=c
      Elágazás vége

      [p1 felöli új metszéspont meghatározása => p1]

      Elágazás
         (c1 ÉS 1)=1 esetén FelsoVagas(p1.x,p1.y,p2.x,p2.y)
         (c1 ÉS 2)=2 esetén JobbVagas(p1.x,p1.y,p2.x,p2.y)
         (c1 ÉS 4)=4 esetén AlsoVagas(p1.x,p1.y,p2.x,p2.y)
         (c1 ÉS 8)=8 esetén BalVagas(p1.x,p1.y,p2.x,p2.y)
      Elágazás vége

      c1:=VégpontKód(p1)
    Ciklus vége

    Ha (c1=0) és (c2=0) akkor {a belső szakasz kirajzolható}

      Szakasz(p1,p2)

    Elágazás vége

Eljárás vége.

2. ábra. Képernyő-koordinátarendszer és képtartomány

Függvény VégpontKód(Konstans p:TPont):TKód
  Változó
    c:TKod

  c:=0

  Ha p.y<KF akkor c:=c VAGY 1

  Ha p.x>KJ akkor c:=c VAGY 2

  Ha p.y>KA akkor c:=c VAGY 4

  Ha p.x<KB akkor c:=c VAGY 8
  VégpontKód:=c

Eljárás vége.

Az egyes vágáseljárások meghatározzák a p1 és p2 pontra illeszkedő egyenes és a megfelelő határoló egyenes metszéspontját. Ez két lineáris egyenletből álló egyenletrendszer megoldását jelenti.

Például a FelsőVágás esetében: az y=(y2-y1)/(x2-x1)*(x-x1)+y1 és az y=KF egyenletek megoldá­sát keressük. Azaz x-re kell rendezni a KF=(y2-y1)/(x2-x1)*(x-x1)+y1 egyenletet, amiből már következik a keresett x és y:

x=x1+(x2-x1)/(y2-y1)*(KF-y1)

y=KF

Azaz az eljárás kódja:

Eljárás FelsoVagas(Változó x1,y1,x2,y2:Egész[1]):

  x1:=x1+(x2-x1)/(y2-y1)*(KF-y1); y1:=KF

Eljárás vége.

A program az alábbi deklarációk után válik teljesen érthetővé, egyértelművé:

Típus  TPont=Rekord(x,y:Egész)

       TKod=0..12

3. ábra. A Cohen-Sutherland algoritmusa működés közben.

A (Turbo/Free Pascal) keretprogram olvasható alább, amelyben csak néhány eljárás törzse maradt kitöltendő. (Letölthető a Free Pascal-hoz: LetoltendoVagasFP.zip)

A keretprogram

Program Vagas;

  Uses

    Crt,Graph;

  Const

    gPath='C:\langs\tp\bgi';

    {KépTartományt határoló egyenesek paraméterei (VGA-hoz igazítva):}

    KF0=100; KB0=100; KJ0=500; KA0=350;

    MaxX0=640; MaxY0=480;     {Próbaszakaszok száma:}

    SzakaszDb=5;
  Type

    TPont=Record x,y:Integer End;

    TSzakasz=Array [1..2] of TPont;

    TKod=0..12;

  Const {Próbaszakaszok:}

    sz:Array [1..SzakaszDb] of TSzakasz=(
                                 ((x:KB0+229;y:KF0+129),(x:KJ0-229;y:KA0-129)),

                                 ((x:KB0-19;y:KF0+19),(x:KB0+190;y:KF0+39)),

                                 ((x:KB0-9;y:KA0-19),(x:KJ0+19;y:KA0-99)),

                                 ((x:KB0-9;y:KF0-9),(x:KJ0+19;y:KF0-19)),

                                 ((x:KB0-59;y:KA0+59),(x:KJ0+69;y:KF0-69))

                                );

  Var

    p1,p2:TPont;

    i:Integer;

    KF,KB,KA,KJ:Integer;

 

  Procedure Inic;

    Var

      i,j,

      gd,gm:Integer;

      nyX,nyY:Real;

  Begin

    DetectGraph(gd,gm);

    InitGraph(gd,gm,gPath);

    ClearDevice;

    {képernyőre transzformálás (TP->FP miatt):}

    nyX:=GetMaxX/MaxX0; nyY:=GetMaxY/MaxY0;

    KF:=Round(KF0*nyY); KA:=Round(KA0*nyY);

    KB:=Round(KB0*nyX); KJ:=Round(KJ0*nyX);

    For i:=1 to SzakaszDb do

      For j:=1 to 2 do

      Begin

        sz[i][j].x:=Round(sz[i][j].x*nyX); sz[i][j].y:=Round(sz[i][j].y*nyY);

      End;

    SetLineStyle(SolidLn, 0, ThickWidth);

    SetColor(Green); Rectangle(KB,KF,KJ,KA);

  End;

 

  Procedure Szakasz(Const p1,p2:TPont);

  Begin

    Line(p1.x,p1.y,p2.x,p2.y);

  End;

 

  Function VegpontKod(Const p:TPont):TKod;

  Begin

 

  End;

 

  Procedure FelsoVagas(Var x1,y1,x2,y2:Integer);

  Begin

 

  End;

 

  Procedure AlsoVagas(Var x1,y1,x2,y2:Integer);

  Begin

 

  End;

 

  Procedure BalVagas(Var x1,y1,x2,y2:Integer);

  Begin

 

  End;

 

  Procedure JobbVagas(Var x1,y1,x2,y2:Integer);

  Begin

 

  End;

 

  Procedure CSVagas(Var p1,p2:TPont);

    Var

      c,c1,c2:TKod;

      p:TPont;

  Begin

 

  End;

 

Begin

  Inic;

  For i:=1 to SzakaszDb do

  Begin

    SetColor(Red); p1:=sz[i][1]; p2:=sz[i][2];

    Szakasz(p1,p2);

    ReadKey;

    CSVagas(p1,p2);

    ReadKey

  End;

End.

Minden egyben letölthető: Vagas.zip.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A megoldás:

 

Program Vagas;

  Uses

    Crt,Graph;

  Const

    gPath='C:\langs\tp\bgi';

    {KépTartományt határoló egyenesek paraméterei (VGA-hoz igazítva):}

    KF0=100; KB0=100; KJ0=500; KA0=350;

    MaxX0=640; MaxY0=480;

    {Próbaszakaszok száma:}

    SzakaszDb=5;
  Type

    TPont=Record x,y:Integer End;

    TSzakasz=Array [1..2] of TPont;

    TKod=0..12;

  Const

    sz:Array [1..SzakaszDb] of TSzakasz=(

                                 ((x:KB0+229;y:KF0+129),(x:KJ0-229;y:KA0-129)),

                                 ((x:KB0-19;y:KF0+19),(x:KB0+190;y:KF0+39)),

                                 ((x:KB0-9;y:KA0-19),(x:KJ0+19;y:KA0-99)),

                                 ((x:KB0-9;y:KF0-9),(x:KJ0+19;y:KF0-19)),

                                 ((x:KB0-59;y:KA0+59),(x:KJ0+69;y:KF0-69))

                                 );

  Var

    p1,p2:TPont;

    i:Integer;

    KF,KB,KA,KJ:Integer;

 

  Procedure Inic;

    Var

      i,j,

      gd,gm:Integer;

      nyX,nyY:Real;

  Begin

    DetectGraph(gd,gm);

    InitGraph(gd,gm,gPath);

    ClearDevice;

    {képernyőre transzformálás (TP->FP miatt):}

    nyX:=GetMaxX/MaxX0; nyY:=GetMaxY/MaxY0;

    KF:=Round(KF0*nyY); KA:=Round(KA0*nyY);

    KB:=Round(KB0*nyX); KJ:=Round(KJ0*nyX);

    For i:=1 to SzakaszDb do

      For j:=1 to 2 do

      Begin

        sz[i,j].x:=Round(sz[i,j].x*nyX); sz[i,j].y:=Round(sz[i,j].y*nyY);

      End;

    SetLineStyle(SolidLn, 0, ThickWidth);

    SetColor(Green); Rectangle(KB,KF,KJ,KA);

  End;

 

  Procedure Szakasz(Const p1,p2:TPont);

  Begin

    Line(p1.x,p1.y,p2.x,p2.y);

  End;

 

  Function VegpontKod(Const p:TPont):TKod;
  Var
    c:TKod;

  Begin

    c:=0;

    If p.y<KF then c:=c OR 1;

    If p.x>KJ then c:=c OR 2;

    If p.y>KA then c:=c OR 4;

    If p.x<KB then c:=c OR 8;
    VegpontKod:=c

  End;

 

  Procedure FelsoVagas(Var x1,y1,x2,y2:Integer);

  Begin

    x1:=Round(x1+(x2-x1)/(y2-y1)*(KF-y1)); §

    y1:=KF

  End;

 

  Procedure AlsoVagas(Var x1,y1,x2,y2:Integer);

  Begin

    x1:=Round(x1+(x2-x1)/(y2-y1)*(KA-y1));

    y1:=KA

  End;

 

  Procedure BalVagas(Var x1,y1,x2,y2:Integer);

  Begin

    y1:=Round(y1+(y2-y1)/(x2-x1)*(KB-x1));

    x1:=KB

  End;

 

  Procedure JobbVagas(Var x1,y1,x2,y2:Integer);

  Begin

    y1:=Round(y1+(y2-y1)/(x2-x1)*(KJ-x1));

    x1:=KJ

  End;

 

  Procedure CSVagas(Var p1,p2:TPont);

    Var

      c,c1,c2:TKod;
      p:TPont;

  Begin
    VegpontKod(c1,p1); VegpontKod(c2,p2);

    While not ((c1=0) and (c2=0)) {legalább egyik még nincs belül}
          and ((c1 AND c2)=0)  {nem biztos, hogy kívül} do

    Begin
      If c1=0 then {p1 OK. Nézzük a másikat: Csere(p1,p2)}
      Begin
        c:=c1; c1:=c2; c2:=c;
        p:=p1; p1:=p2; p2:=p;
      End;

      {p1 felöli új metszéspont meghatározása => p1}
      If
        (c1 AND 1)=1 then FelsoVagas(p1.x,p1.y,p2.x,p2.y) else if
        (c1 AND 2)=2 then JobbVagas(p1.x,p1.y,p2.x,p2.y) else if
        (c1 AND 4)=4 then AlsoVagas(p1.x,p1.y,p2.x,p2.y) else if
        (c1 AND 8)=8 then BalVagas(p1.x,p1.y,p2.x,p2.y)
      {EndIf};

      VegpontKod(c1,p1);

      {Metszéspont-keresés -- nyomkövetés:}

      SetLineStyle(CenterLn, 0, NormWidth);
      SetColor(Yellow);
      Szakasz(p1,p2);
      ReadKey;
      SetLineStyle(SolidLn, 0, ThickWidth);
      {Nyomkövetés vége}

    End;

    If (c1=0) and (c2=0) then
    Begin {a belső szakasz kirajzolható}

      SetColor(Blue);
      Szakasz(p1,p2);
    End;

  End;

 

Begin

  Inic;
  For i:=1 to SzakaszDb do
  Begin

    SetColor(Red); p1:=sz[i][1]; p2:=sz[i][2];
    Szakasz(p1,p2);
    ReadKey;
    CSVagas(p1,p2);
    ReadKey
  End;

End.


¨ Szokás szerint a képernyővel megegyező állású téglalapra gondolunk képtartomány esetén.

ª balsó Þ 1xxx2, alsó Þ x1xx2, jobbsó Þ xx1x2, felső Þ xxx12

© A logikai műveletek jelei kisbetűsek, a bit-műveletek NAGYBETŰSEK.

[1]     Világos, hogy valójában csak az 1. pont koordinátái fognak változni, így precízebb lenne az alábbi szignatúra:

      Eljárás FeloVagas(Változó x1,y1:Egész, Konstans x2,y2:Egész)

§ Hogy ne legyen a részletszámítások során sem túlcsordulás az első adandó helyen osztunk.