Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Растрова розгортка багатокутників
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Комп'ютерна графіка
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Лабораторна робота №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.
а
б
Рис. 3.2 Система координат рядків сканування.
Модифікація системи координат скануючого рядка і тесту активації усуває цю проблему, як це показано на рис.3.2(б). Вважається, що сканируючі рядки проходять через центри рядків пікселів, тобто через середини інтервалів, як це показано на рис.3.2(б). Тест активації модифікується в такий спосіб: перевіряється, чи лежить всередині інтервалу центр піксела, розташованого праворуч від перетину. Однак піксели все ще адресуються координатами лівого нижнього кута. Як показано на рис.3.2(б), результат даного методу коректний.
Горизонтальні ребра не можуть перетинати скануючий рядок і, таким чином, ігноруються. Це зовсім не означає, що їх немає на малюнку. Ці ребра формуються верхнім і нижнім рядками пікселів, як показано на рис.3.2. Рис.3.2 ілюструє коректність верхнього і нижнього ребер багатокутника, отриманих у результаті модифікації системи координат скануючих рядків.
Додаткові труднощі виникають при перетині скануючого рядка і багатокутника точно по вершині, як це показано на рис.3.3.
Рис.3.3. Особливості перетинів з рядками сканування.
При використанні угоди про середину інтервалу між скануючими рядками одержуємо, що рядок у=3,5 перетне багатокутник у 2, 2 і 8, тобто вийде непарна кількість перетинань. Отже, розбивка пікселів на пари - дасть невірний результат, тобто піксели (0, 3), (1, 3) і від (3, 3) до (7, 3) будуть фоновими, а піксели (2, 3), (8, 3), (9, 3) зафарбуються в колір багатокутника. Тут виникає ідея враховувати тільки одну точку перетинання з вершиною. Тоді для рядка у=3,5 одержимо правильний результат. Однак результат застосування методу до рядка у=1,5, що має два перетини в (5, 1), показує, що метод невірний. Для цього рядка саме розбивка на пари дасть вірний результат, тобто пофарбований буде тільки піксел (5, 1), Якщо ж враховувати у вершині тільки одне перетинання, то піксели від (0, 1) до (4, 1) будуть фоновими, а піксели від (5, 1) до (9, 1) будуть пофарбовані в колір багатокутника.
Правильний результат можна одержати, враховуючи точку перетинання у вершині два рази, якщо вона є точкою локального мінімуму чи максимуму і враховуючи її один раз в іншому випадку. Визначити локальний максимум чи мінімум багатокутника в розглянутій вершині можна за допомогою перевірки кінцевих точок двох ребер, з'єднаних у вершині. Якщо в обох кінців координати у більші, ніж у вершини, виходить, вершина є точкою локального мінімуму. Якщо менші, значить, вершина - точка локального максимуму. Якщо одна більша, а інша менша, то вершина не є ні точкою локального мінімуму, ні точкою локального максимуму. На рис.3.3 точка P1 - локальний мінімум, Р3 - локальний максимум, а Р2, Р4 - ні то і ні інше. Отже, у точках Р1 і P3 враховуються два перетинання із скануючими рядками, а в Р2 і Р4 - одне.
Простий алгоритм з упорядкованим списком ребер
Використовуючи описані вище методи, можна розробити ефективні алгоритми растрової розгортки суцільних областей, які називаються алгоритмами з упорядкованим списком ребер. Вони залежать від сортуван ня в порядку сканування крапок перетинань ребер багатокутника із скануючими рядками. Ефективність цих алгоритмів залежить від ефективності сортування. Наведемо дуже простий алгоритм.
Простий алгоритм з упорядкованим списком ребер
Підготувати дані:
Визначити для кожного ребра багатокутника точки перетинань із скануючими рядками, проведеними через середини інтервалів, для чого можна використовувати алгоритм Брезенхема чи ЦДА. Горизонтальні ребра ігноруються. Занести кожне перетинання (х, у+1/2) у список. Відсортувати список по рядках і по зростанню х у рядку; тобто (x1, у1) передує (х2, у2), якщо у 1>у2 чи y1=y2 і xx2(x2.
Перетворити ці дані в растрову форму:
Виділити з відсортованого списку пари елементів (x1, у1) і (х2, у2). Структура списку гарантує, що y=у1=у2 і x1(x2. Активувати на скануючому рядку y піксели для цілих значень x, таких, що x1<x+1/2(x2.
Приклад 4.1. Простий упорядкований список ребер
Розглянемо багатокутник, зображений на рис.4.1. Його вершини: P1, (1,1), P2(8,1), P3(8,6), P4(5,3) і P5(1,7). Перетинання із серединами скануючих рядків наступні:
скан. рядок 1.5 (8, 1.5), (1, 1.5)
скан. рядок 2.5 (8.2.5), (1, 2.5)
скан. рядок 3.5 (8, 3.5), (5.5, 3.5), (4.5, 3.51), (1, 3.5)
скан. рядок 4.5 (8, 4.5), (6.5, 4.5), (3.5, 4.5). (1, 4.5)
скан. рядок 5.5 (8, 5.5), (7.5, 5.5), (2.5, 5.5), (1, 5.5)
скан. рядок 6.5 (1.5, 6.5), (I, 6.5)
скан. рядок 7.5 немає
Весь список сортується в порядку сканування спочатку зверху вниз і потім - зліва направо: (1, 6.5), (1.5, 6.5), (1, 5.5), (2.5, 5.5),(7.5, 5.5), (8, 5.5), (1, 4.5), (3.5, 4,5). (6.5, 4.5). (8, 4.5). (1, 3.5). (4.5,3.5), (5.5, 3.5), (8. 3.5), (1, 2.5), (8, 2.5),( 4, 1.5), (8, 1.5).
Виділяючи із списку пари перетинань і застосовуючи алгоритм, описаний вище, одержимо список пікселів, що повинні бути активовані:
(1,6)
(l, 5), (2, 5), (7, 5)
(1, 4), (2, 4), (3, 4), (6, 4), (7, 4)
(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (7, 3)
Рис.4.1. Результат растрової розгортки суцільної області,
зображеної на рис.3.1.
(1,1), (2, 2), (3, 2) (4, 2), (5, 2), (6, 2), (7, 2) (1, 1), (2, 1), (3,1), (4,1), (5, 1), (6,1), (7, 1)
Результат представлений на рис.4.1. Зауважимо, що обидва верти кальних і нижнє ребро зображені правильно.
Більш ефективні алгоритми з упорядкованим списком ребер
В алгоритмі, описаному в попередньому розділі, генерується великий список, який необхідно цілком відсортувати. Алгоритм можна покращити, якщо підвищити ефективність сортування. Останнє досягається поділом сортування по рядках у напрямку y і сортування в рядку в напрямку х за допомогою групового сортування по y. Зокрема, алгоритм тепер можна представити в наступному вигляді:
Більш ефективний алгоритм з упорядкованим списком ребер
Підготувати дані:
Визначити для кожного ребра багатокутника точки перетинань із скануючими рядками, проведеними через середини інтервалів, тобто через у+1/2. Для цього можна використовувати алгоритм Брезенхема чи ЦДА. Горизонтальні ребра не враховувати. Помісти ти координату y точки перетинання в групу, що відповідає y.
Для кожної у-групи відсортувати список координат х точок перетинань у порядку зростання; тобто х1, передує х2, якщо: x1<x2.
Перетворити ці дані в растрову форму:
Для кожного скануючого рядка виділити із списку координат х точок перетинань пари точок перетинань. Активувати на скануючому рядку y піксели для цілих значень х, таких, що x1(x+1/2(x2.
В алгоритмі спочатку за допомогою групового сортування по у відбувається сортування в порядку сканування рядків, а потім сортування в рядку. Таким чином, розгортання починається до завершення всього процесу сортування. У такому алгоритмі почасти легше додавати чи видаляти інформацію з дисплейного списку. Необхідно тільки додати чи видалити інформацію з відповідних y-груп; отже, пересортувати доведеться тільки порушені зміною рядка. Нижче даний алгоритм ілюструється на прикладі.
Приклад 5.1. Більш ефективний упорядкований список ребер
Розглянемо знову як і в прикладі 4.1 багатокутник з рис.3.1. Спочатку створюються у-групи для всіх скануючих рядків, як це показано на рис.5.1. Багатокутник розглядається проти годинникової стрілки, починаючи з вершини Р, і перетинання, що виходять, невідсортовані по x, заносяться у відповідні групи, як це показано на рис.5.1(а). Перетинання були обчислені відповідно до угоди про середину інтервалу між скануючими рядками. Як ілюстрацію на рис.5.1(b) показано відсортовані перетинання. На практиці можна використовувати невеликий буфер скануючого рядка, що містить від сортовані координати - v точок перетинання, як це показано на рис.5.1 (с). Такий буфер дозволяє більш ефективно додавати чи видаляти перетинання в список, їх просто можна додавати до кінця списку кожної у-групи, тому що сортування відкладається до моменту переміщення рядка в буфер. Отже, не потрібно тримати цілком відсортований список у-груп.
Рис.5.1. y-групи скануючих рядків для багатокутника, зобр. на рис.3.1.
В результаті виділення пар перетинань з відсортованого по y списку і застосування алгоритму для кожного скануючого рядка одержимо список активованих пікселів.
Хоча в цій версії алгоритму задача сортування спрощується, потрібно або обмежене число перетинань з даним скануючим рядком, або резервування великої кількості пам'яті, значна частина якої не буде використовуватися. Цей недолік можна усунути завдяки використанню зв'язного списку, тобто шляхом введення додаткової структури даних. Попереднє обчислення перетинань кожного скануючого рядка з кожним ребром багатокутника вимагає великих обчислювальних затрат і значних обсягів пам'яті. Увівши список активних ребер (CAP), як це передбачалося для растрової розгортки в реальному часі, можна скоротити потреби в пам'яті й обчислювати перетинання із скануючими рядками в покроковому режимі. Алгоритм, утворений в результаті всіх поліпшень, виглядає так:
Алгоритм з упорядкованим списком ребер, що використовує список активних ребер
Підготувати дані:
Використовуючи скануючі рядки, проведені через середини відрізків, тобто через у+1/2, визначити для кожного ребра багатокутника найвищий скануючий рядок, перетятий ребром.
Занести ребро багатокутника в у-групу, відповідно цьому скануючому рядку.
Зберегти в зв'язному списку значення: початкове значення координат х точок перетинання, - число скануючих рядків, перетятих ребром багатокутника, і - крок збільшення по х при переході від одного скануючого рядка до іншого.
Перетворити ці дані в растрову форму:
Для кожного скануючого рядка перевірити відповідну у-групу на наявність нових ребер. Нові ребра додати в CAP.
Відсортувати координати х точок перетинання з CAP у порядку зростання; тобто x1 передує x2 ,якщо x1<x2.
Виділити пари точок перетинань з відсортованого по х списку. Активувати на скануючому рядку у піксели для цілих значень х, таких, що x1(x+1/2(x2. Для кожного ребра з CAP зменшити на 1. Якщо <0, то вилучити дане ребро з CAP. Обчислити нове значення координат х точок перетинання хнов= xстар+.
Перейти до наступного скануючого рядка.
В алгоритмі передбачається, що всі дані попередньо перетворено до вигляду, прийнятого для багатокутників.
Текст програми.
#include <vcl.h>
#include <math>
#include <list>
using namespace std;
#include <stdio>
#pragma hdrstop
#include "Unit1.h"
#pragma package(smart_init)
#pragma link "CSPIN"
#pragma resource "*.dfm"
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
int k;//mashtab
int kp;//k-st' to4ok
const int MaxBuff=50;
list<int> buff[MaxBuff];
void DrawGrid(){
TRect r;
r.Left=0;
r.top=0;
r.right=Form1->Image1->Width;
r.Bottom=Form1->Image1->Height;
Form1->Image1->Canvas->FillRect(r);
int x=0, y=0;
while(x< Form1->Image1->Width){
Form1->Image1->Canvas->MoveTo(x,0);
Form1->Image1->Canvas->LineTo(x,Form1->Image1->Height);
x+=k; }
while(y<Form1->Image1->Height){
Form1->Image1->Canvas->MoveTo(0,y);
Form1->Image1->Canvas->LineTo(Form1->Image1->Width,y);
y+=k; }
}
void SetPixel(int x,int y){
TRect r;
r.Left=x*k+1;
r.top=(y+1)*k;
r.right=(x+1)*k;
r.Bottom=y*k+1;
Form1->Image1->Canvas->Brush->Color=0xcacaca;
Form1->Image1->Canvas->FillRect(r);
Form1->Image1->Canvas->Brush->Color=0xffffff;
}
void DrawLine(int x1,int y1,int x2,int y2){
int kx=1,ky=1;
double dx,dy,x,y;
int prevx=-1;
int prevy=-1;
int lx=abs(x1-x2);
int ly=abs(y1-y2);
int temp=0;
if(x1>x2)
kx=-1;
if(y1>y2)
ky=-1;
if(lx>ly){
dy=ly/(double)lx;
y=y1;
for(int x=x1;lx>=abs(x1-x);x+=kx){
SetPixel(x,(int)(y+0.5));
if(y1!=y2){
//buff[(int)(y+0.5)].push_back(x);
if(prevy==-1){
buff[(int)(y+0.5)].push_back(x);
prevy=(int)(y+0.5);
prevx=x;
}else if(prevy!=(int)(y+0.5)){
buff[(int)(y+0.5)].push_back(x);
prevy=(int)(y+0.5);
prevx=x;
temp=0;
}
temp++;
}
y+=dy*ky;
}
}else{
dx=lx/(double)ly;
x=x1;
for(int y=y1;ly>=abs(y1-y);y+=ky){
SetPixel((int)(x+0.5),y);
if(y1!=y2){
//buff[y].push_back((int)(x+0.5));
if(prevy==-1){
buff[y].push_back((int)(x+0.5));
prevy=y;
prevx=(int)(x+0.5);
}else if(prevy!=y){
buff[y].push_back((int)(x+0.5));
prevy=y;
prevx=(int)(x+0.5);
temp=0; }
temp++; }
x+=dx*kx;
} }}
void __fastcall TForm1::FormShow(TObject *Sender)
{ k=(Image1->Width < Image1->Height ? Image1->Width : Image1->Height)/CSpinEdit1->Value;
CSpinEdit1->MaxValue=CSpinEdit1->MinValue+MaxBuff;
DrawGrid();}
int x1,y1,x2,y2;
void __fastcall TForm1::Image1MouseDown(TObject *Sender,
TMouseButton Button, TShiftState Shift, int X, int Y)
{ x1=X/k;
y1=Y/k;
SetPixel(x1,y1);
kp++;
CSpinEdit1->Enabled=false;
if(kp>1)
DrawLine(x1,y1,x2,y2);
x2=x1;
y2=y1;}
void __fastcall TForm1::CSpinEdit1Change(TObject *Sender)
{
k=(Image1->Width < Image1->Height ? Image1->Width : Image1->Height)/CSpinEdit1->Value;
DrawGrid();}
void __fastcall TForm1::Button1Click(TObject *Sender)
{ int l;
int first,next;
for(int i=0;i<MaxBuff;i++){
l=buff[i].size();
buff[i].sort();
while(!buff[i].empty()){
if(buff[i].size()<2)
break;
first=buff[i].front();
buff[i].pop_front();
next=buff[i].front();
if(((next-first)==0)&&!(buff[i].size()%2))
continue;
buff[i].pop_front();
for(int j=first;j<next;j++)
SetPixel(j,i); }}}
void __fastcall TForm1::Button2Click(TObject *Sender)
{ for(int i=0;i<MaxBuff;i++)
buff[i].clear();
CSpinEdit1->Enabled=true;
kp=0;
DrawGrid();}
Результат виконання програми
Висновок
Висновок: в даній лабораторній роботі я ознайомився з основами комп’ютерної графіки – простий алгоритм з упорядкованим списком ребер.
.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора