Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління
Лабораторна робота № 8 з дисципліни “Комп’ютерна графіка” Растрова розгортка багатокутників Можна розробити більш ефективний метод, ніж тест на приналежність внутрішньої частини, якщо скористатися тим фактом, що сусідні піксели, ймовірно, мають однакові характеристики (крім пікселів граничних ребер). Ця властивість називається просторовою когерентністю. Для растрових графічних пристроїв сусідні піксели на скануючому рядку, ймовірно, мають однакові характеристики. Це когерентність растрових рядків. Характеристики пікселів на даному рядку змінюються тільки там, де ребро багатокутника перетинає рядок. Ці перетини поділяють скануючий рядок на області.
Рис.3.1. Растрова розгортка суцільної області. Для простого багатокутника на рис.3.1 рядок 2 перетинає багатокутник при х=1 і х=8. Одержуємо три області: x<1 поза багатокутником  1(x(8 всередині багатокутника  x>8 поза багатокутником  Рядок 4 поділяється на п'ять областей: x<1 поза багатокутником  1(x(4 всередині багатокутника  4<x<6 поза багатокутником  6(x(8 всередині багатокутника  x>8 поза багатокутником  Зовсім необов’язково, щоб точки перетинану для рядка 4 відразу визначалися у фіксованому порядку (ліворуч праворуч). Наприклад, якщо багатокутник задається списком вершин P1P2P3P4P5, а список ребер - послідовними парами вершин Р1Р2, Р2Р3, Р3Р4, P4P5, P5P1 то для рядка 4 будуть знайдені наступні точки перетину з ребрами багатокутника: 8, 6, 4, 1. Ці точки треба відсортувати в зростаючому порядку по х, тобто одержати 1, 4, 6, 8. При визначенні інтенсивності, кольору і відтінку пікселів на скануючому рядку розглядаються пари відсортованих точок перетинань. Для кожного інтервалу, що задається парою перетинань, використовується інтенсивність чи колір заповнюваного багатокутника. Для інтервалів між парами перетинань і крайніх (від початку рядка до першої точки перетину і від останньої точки перетину до кінця рядка) використовується фонова інтенсивність чи колір. На рис.3.1 для рядка 4 у фоновий колір встановлені піксели: від 0 до 1, від 4 до 6, від 8 до 10, тоді як піксели від 1 до 4 і від 5 до 8 зафарбовані в колір багатокутника. Точне визначення тих пікселів, що повинні активуватися вимагає деякої обережності. Розглянемо простий прямокутник, зображений на рис.3.2. Прямокутник має координати (1,1) (5,1), (5,4), (1,4). Скануючі рядки з 1 по 4 мають перетини з ребрами багатокутника при х=1 і 5. Згадаємо, що піксел адресується координатами свого лівого нижнього кута, виходить, для кожного з цих скануючих рядків будуть активовані піксели з x-координатами 1, 2, 3, 4 і 5. На рис.3.2(а) показаний результат. Помітимо, що площа, що покривається активованими пікселами, дорівнює 20, у той час як дійсна площа прямокутника дорівнює 12. Текст програми: //--------------------------------------------------------------------------- #include <vcl.h> #include <mmsystem.h> #pragma hdrstop #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; int ig, ix[350][10], c; //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { int i, j; // Defaults Polygon->Cells[0][0]=" X"; Polygon->Cells[0][1]=" Y"; Polygon->Cells[1][0]="3"; Polygon->Cells[1][1]="3"; Polygon->Cells[2][0]="5"; Polygon->Cells[2][1]="7"; Polygon->Cells[3][0]="9"; Polygon->Cells[3][1]="8"; Polygon->Cells[4][0]="9"; Polygon->Cells[4][1]="6"; Polygon->Cells[5][0]="8"; Polygon->Cells[5][1]="1"; DefaultDrawing(); } //--------------------------------------------------------------------------- void __fastcall TForm1::DefaultDrawing(void) { int i,j,sc; // Drawing Screen->Canvas->Pen->Color=clBlack; Screen->Canvas->Pen->Width=1; Screen->Canvas->Rectangle(0,0,360,360); // axis OX Screen->Canvas->MoveTo(10,350); Screen->Canvas->LineTo(350,350); // axis OY Screen->Canvas->MoveTo(10,10); Screen->Canvas->LineTo(10,350); // Scaling sc=StrToInt(3); for(i=10,j=350;i<=350 || j>=10;i+=10*sc,j-=10*sc) { Screen->Canvas->MoveTo(i,1); Screen->Canvas->LineTo(i,352); Screen->Canvas->MoveTo(349,j); Screen->Canvas->LineTo(9,j); } for(i=9,j=0;i<350;j++,i+=30){ Screen->Canvas->TextOutA(i,350,j); } for(i=315,j=0;i>0;j++,i-=30){ Screen->Canvas->TextOutA(3,i,j+1); } Screen->Canvas->Pen->Color=clBlack; for(i=0;i<350;i++) { for(j=0;j<10;j++) { ix[i][j]=0; } } } //--------------------------------------------------------------------------- void __fastcall TForm1::ScalingChange(TObject *Sender) { DefaultDrawing(); } //--------------------------------------------------------------------------- void __fastcall TForm1::ClearClick(TObject *Sender) { DefaultDrawing(); } //--------------------------------------------------------------------------- void __fastcall TForm1::BuiltClick(TObject *Sender) { int s,xA, yA, xB, yB, xC, yC, xD, yD, xE, yE, sc; DefaultDrawing(); sc=StrToInt(3); s=ComboBox1->ItemIndex; Edit1->Text=IntToStr(s); xA=StrToInt(Polygon->Cells[1][0]); yA=StrToInt(Polygon->Cells[1][1]); xB=StrToInt(Polygon->Cells[2][0]); yB=StrToInt(Polygon->Cells[2][1]); xC=StrToInt(Polygon->Cells[3][0]); yC=StrToInt(Polygon->Cells[3][1]); xD=StrToInt(Polygon->Cells[4][0]); yD=StrToInt(Polygon->Cells[4][1]); xE=StrToInt(Polygon->Cells[5][0]); yE=StrToInt(Polygon->Cells[5][1]); Screen->Canvas->Pen->Color=clBlack; Screen->Canvas->Pen->Width=5; Screen->Canvas->MoveTo(xA*10*sc+10,-yA*10*sc+350); Screen->Canvas->LineTo(xB*10*sc+10,-yB*10*sc+350); Screen->Canvas->LineTo(xC*10*sc+10,-yC*10*sc+350); if (s==1) { Screen->Canvas->LineTo(xD*10*sc+10,-yD*10*sc+350); Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350); } if (s==2) { Screen->Canvas->LineTo(xD*10*sc+10,-yD*10*sc+350); Screen->Canvas->LineTo(xE*10*sc+10,-yE*10*sc+350); Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350); } if(s==0) Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350); Screen->Canvas->Pen->Color=clBlack; } //--------------------------------------------------------------------------- void __fastcall TForm1::BitBtn1Click(TObject *Sender) { Close(); } //--------------------------------------------------------------------------- void __fastcall TForm1::FillBClick(TObject *Sender) { int i, min, mini, temp; Screen->Canvas->Pen->Color=clBlue; for(ig=0;ig<350;ig++) { c=0; CheckPoint(); min=ix[ig][0]; mini=0; if(min!=0) { for(i=1;i<10;i++) { if(ix[ig][i]!=0 && ix[ig][i]<min) { ix[ig][mini]=ix[ig][i]; temp=min; min=ix[ig][i]; mini=i; ix[ig][i]=temp; } } } } ig=0; Timer1->Enabled=true; } //--------------------------------------------------------------------------- void __fastcall TForm1::CheckPoint(void) { int ks,sc, j; float m[10], x,y, x1,y1, x2,y2, Dx,Dy, s1,s2, Obmin, Temp, i, e; sc=StrToInt(3); ks=(ComboBox1->ItemIndex)*2+6; Edit1->Text=ks; m[0]=StrToInt(Polygon->Cells[1][0]); m[1]=StrToInt(Polygon->Cells[1][1]); m[2]=StrToInt(Polygon->Cells[2][0]); m[3]=StrToInt(Polygon->Cells[2][1]); m[4]=StrToInt(Polygon->Cells[3][0]); m[5]=StrToInt(Polygon->Cells[3][1]); if (ks==8||ks==10) { m[6]=StrToInt(Polygon->Cells[4][0]); m[7]=StrToInt(Polygon->Cells[4][1]); } else {m[6]=0; m[7]=0;} if (ks==10){ m[8]=StrToInt(Polygon->Cells[5][0]); m[9]=StrToInt(Polygon->Cells[5][1]); } else {m[8]=0; m[9]=0;} for(j=0;j<ks;j+=2) { x1=m[j]*10*sc; y1=m[j+1]*10*sc; if(j==8&&ks==10) { x1=m[0]*10*sc; y1=m[1]*10*sc; x2=m[8]*10*sc; y2=m[9]*10*sc; goto A; } if(j==6&&ks==8) { x1=m[0]*10*sc; y1=m[1]*10*sc; x2=m[6]*10*sc; y2=m[7]*10*sc; goto A; } if(j==4&&ks==6) { x1=m[0]*10*sc; y1=m[1]*10*sc; x2=m[4]*10*sc; y2=m[5]*10*sc; goto A; } // else { x2=m[j+2]*10*sc; y2=m[j+3]*10*sc; // } A: x=x1; y=y1; Dx=abs(x2-x1); Dy=abs(y2-y1); s1=x2-x1<0?-1:1; if(Dx==0) { s1=0; } s2=y2-y1<0?-1:1; if(Dy==0) { s2=0; } if(Dx<Dy) { Temp=Dx; Dx=Dy; Dy=Temp; Obmin=1; } else { Obmin=0; } e=2*Dy-Dx; for(i=0;i<=Dx;i++) { //point if(ig==y) { if(x==ix[ig][c-1]) { if(((m[j+1]>m[j+3] && m[j+1]>m[j-1]) || (m[j+1]<m[j+3] && m[j+1]<m[j-1]))) { ix[ig][c]=x; c++; } goto NeL; } ix[ig][c]=x; c++; goto NeL; } while(e>=0) { if(Obmin==1) { x=x+s1; } else { y=y+s2; } e=e-2*Dx; } if(Obmin==1) { y=y+s2; } else { x=x+s1; } e=e+2*Dy; } NeL: } } void __fastcall TForm1::Timer1Timer(TObject *Sender) { int i,ks; ks=(ComboBox1->ItemIndex)*2+6; if(ig==350) { Timer1->Enabled=false; } else { Screen->Canvas->Pen->Color=clRed; for(i=0;i<ks;i+=2) { if(ix[ig][i]!=0 && ix[ig][i+1]!=0) { Screen->Canvas->MoveTo(ix[ig][i]+10,-ig+350); Screen->Canvas->LineTo(ix[ig][i+1]+10,-ig+350); } } Screen->Canvas->Pen->Color=clBlack; } ig++; } //--------------------------------------------------------------------------- void __fastcall TForm1::Button1Click(TObject *Sender) { Close(); } //--------------------------------------------------------------------------- void __fastcall TForm1::ComboBox1Change(TObject *Sender) { int s; char ch[10]; s=ComboBox1->ItemIndex; Edit1->Text=s; ch[1]=Edit1->Text[1]; switch(ch[1]){ case '0': Polygon->ColCount=4; Polygon->Width=38*(4); break; case '1': Polygon->ColCount=5; Polygon->Width=38*(5);break; case '2': Polygon->ColCount=6; Polygon->Width=38*(6);break; } } //---------------------------------------------------------------------------
Висновок: Виконуючи цю лабораторну роботу, я освоїв алгоритм растрової розгортки і практично застосував отримані знання.