50288

Заповнення багатокутників

Лабораторная работа

Информатика, кибернетика и программирование

Однією із унікальних характеристик растрового пристрою є можливість представлення суцільних областей. Генерацію суцільних областей із простих описів ребер або вершин називають растровою розгорткою суцільних областей, заповненням багатокутників або заповненням контурів. Для цього використовують кілька методів, які можна поділити на дві категорії: растрова розгортка та заповнення із затравкою.

Украинкский

2014-02-03

69 KB

9 чел.

Лабораторна робота №3.

Заповнення багатокутників.

Однією із унікальних характеристик растрового пристрою є можливість представлення суцільних областей. Генерацію суцільних областей із простих описів ребер або вершин називають растровою розгорткою суцільних областей, заповненням багатокутників або заповненням контурів. Для цього використовують кілька методів, які можна поділити на дві категорії: растрова розгортка та заповнення із затравкою.

В методах растрової розгортки намагаються визначити в порядку сканування рядків, чи лежить точка всередині контура. Ці алгоритми проводять сканування зазвичай від "верху" контура до його "низу". В методах заповнення із затравкою передбачається, що відома певна точка (затравка), яка знаходиться всередині замкнутого контуру. В алгоритмах шукають точки, які розташовані навколо затравки і знаходяться всередині контуру. Якщо сусідня точка розташована не всередині, значить, знайдено межу контура. Якщо точка знаходиться всередині контуру, то вона стає новою затравочною точкою і пошук продовжується рекурсивно.

1. Малювання заповненого трикутника.

Однією із базових операцій в 3D-графіці є малювання заповненого трикутника. Розглянемо малювання такого трикутника методом растрової розгортки. Його зображення на екрані  – це набір горизонтальних відрізків, причому, оскільки трикутник – фігура випукла, кожному рядку екрану відповідає не більше одного відрізку. Тому достатньо пройтись по всім рядкам екрану, які перетинаються з трикутником (тобто, від мінімального до максимального значення y для вершин трикутників), і провести відповідні горизонтальні відрізки (див. мал. 1).

Малюнок 1

Нехай кожна вершина задається структурою-записом (точка.x, точка.y). Відсортуємо вершини так, щоб вершина A стала верхньою, С – нижньою; тоді min(y)=A.y, max(y)=C.y, і потрібно пройтись по всім лініям від min(y) до max(y). Розглянемо деяку лінію sy(). Якщо sy<B.y, то ця лінія перетинає сторони AB і AC; якщо syB.y – то сторони BC і AC. Координати всіх вершин відомі, тому можна записати рівняння сторін і знайти перетин потрібної сторони і прямої y=sy. При цьому отримаємо два кінця відрізка. Так як невідомо, який з них лівий, який правий, то потрібно порівняти координати x і поміняти значення при необхідності. Після цього потрібно намалювати цей відрізок. Таку процедуру потрібно повторит для кожного рядка. Зупинимося більш докладніше на знаходжені перетину прямої y=sy(поточного рядка) і сторони трикутника, наприклад, AB. Напишемо рівняння прямої AB в формі x=k*y+b:

.

Підставляючи відоме для поточної прямої значення y=sy, отримаємо:

.

Також потрібно врахувати випадок, коли B.y=C.y – в цьому випадку (і тільки в цьому, тому що якщо C.y=A.y, то трикутник пустий і малювати його не варто; а якщо B.y=A.y, то syA.y і до ділення на B.y  справа не дійде) виникне спроба ділення на ноль. Таким чином код матиме вигляд:

{...}

{сортуємо вершини A, B, C}

{...}

for sy:=A.y to C.y do

begin

  x1:=A.x+(sy–A.y)*(C.x–A.x)/(C.y–A.y);

  if (sy<B.y) then

    x2:=A.x+(sy–A.y)*(B.x–A.x)/(B.y–A.y)

  else

    if C.y=B.y then

      x2:=B.x

    else  x2:=B.x+(sy–B.y)*(C.x–B.x)/(C.y–B.y);

  if x1>x2 then

  begin

    tmp:=x1; x1:=x2; x2:=tmp;

  end;

  drawHorizontalLine(sy, x1, x2);

end;

2.Заповнення багатокутників.

2.1. Растрова розгортка багатокутників.

Багато замкнених контурів є простими багатокутниками. Якщо контур складається із кривих ліній, то його можна апроксимуати багатокутником або багатокутниками. Найпростіший метод заповнення багатокутника полягає в перевірці на належність багатокутнику кожного піксела в растрі. Так як більшість пікселів лежить поза багатокутником, то даний метод досить нераціональний. Витрати часу обчислення можна скоротити шляхом виділення дя багатокутника оболонки – найменшого прямокутника, що містить всередині себе баатокутник. В цьому випадку перевіряються тільки внутрішні точки цього прямокутника.

Простий алгоритм із впорядкованим списком ребер.

Алгоритми растрової розгортки суцільних областей залежать від сортування в порядку сканування точок перетину ребер багатокутника із скануючими рядками. Ефективність таких алгоритмів залежить від ефективності сортування. Найпростіший алгоритм в цьому випадку матиме вигляд:

підготувати дані:

визначити для кожного ребра багатокутника точки перетину із скануючими рядками, проведеними через середини інтервалів, для чого можна використати алгоритми Брезенхема або ЦДА. Горизонтальні ребра при цьому ігноруються. Занести кожний перетин () в список. Відсортувати список по рядкам і по зростанню x в рядку, тобто (x1, y1) є попередником (x2, y2), якщо y1>y2 або y1=y2 і x1x2.

перевести таким чином отримані дані в растрову форму:

виділити із відсортованого списку пари елементів (x1, y1) та (x2, y2). Структура списку гарантує, що y=y1=y2 і x1x2. Активізувати на скануючому рядку y піксели для цілих значень x, таких, що .

Алгоритм із списком ребер та прапорцем.

Алгоритм, що використовує список ребер та прапорець, є двохкроковим. Перший крок полягає в в промальовці контура, в результаті чого на кожному скануючому рядку утворюються пари обмежуючих пікселів. Другий крок полягає в заповнені пікселів, що розташовані між обмежуючими пікселями. Таким чином алгоритм можна зформулювати так:

Промальовка контура:

використовуючи домовленість про середину інтервалу між скануючими рядками для кожного ребра, що перетинає скануючий рядок, відмітити самий лівий піксел, центр якого лежить справа від перетину; тобто

Заповнення:

Для кожного скануючого рядку , що перетинає багатокутник

intro=false

for x=0 {ліва межа} to x=xmax {права межа}

  if піксел в точці має граничне значення then

    інвертувати значення змінної intro

  if intro=true then

    присвоїти пікселу в x значення кольору багатокутника

  else присвоїти пікселу в x значення кольору фону

end if

next x

2.2. Алгоритми заповнення із затравкою.

В алгоритмах заповнення із затравкою допускається, що відомий хоча б один піксел із внутрішньої області багатокутника. Алгоритм робить спробу знайти і зафарбувати всі інші піксели, що належать внутрійній області. Області можуть бути або внутрішньо-, або  гранично-визначеними. Якщо область відноситься до внутрішньо-визначеної, то всі піксели, що належать внутрішній частині, мають один і той же колір або інтенсивність, а всі піксели, зовнішні по відношенню до області, мають інший колір.

Зафарбовування області , що задана кольором границі. 

Розглянемо точку, що обмежена набором пікселів заданого кольору, і точку (x, y), що лежить всередині цієї області.

Найпростіший алгоритм має вигляд:

procedure PixelFill(x, y, BorderColor, Color: integer);

var

  c: integer;

begin

  c:=GetPixel(x, y);

  if (c<>BorderColor) and (c<>color) then

  begin

    putPixel(x, y, color);

    PixelFill(x–1, y, BorderColor, color);

    PixelFill(x+1, y, BorderColor, color);

    PixelFill(x, y–1, BorderColor, color);

    PixelFill(x–1, y, BorderColor, color);

    PixelFill(x, y+1, BorderColor, color);

  end;

end;

 Цей алгоритм хоча і заповнює найскладніші області, є досить неефективним, так як вже для промальованого піксела функція викликається ще три рази, і, крім того, вимагає занадто великого стеку із-за глибини рекурсії. Тому для вирішення задачі зафарбовування області краще алгоритми, що здатні обробляти відразу цілі групи пікселів.

Розглянемо версію одного із найпопулярніших алгоритмів подібного типу, коли для заданої точки (x, y) визначається та заповнюється максимальний відрізок (x1, xr), що містить цю точку і лежить всередині області. Після цього в пошуках ще не заповнених пікселів перевіряються відрізки, що лежать вище та нижче. Якщо такі піксели знаходяться, то функція викликається рекурсивно для їх обробки. Такий алгоритм працює ефективно навіть для областей з дірками.

uses mGraph;

function LineFill(x, y, dir, prevX1, prevXr, BorderColor, color: integer): integer;

var

 x1, xr: integer;

 c: byte;

begin

 x1 := x; xr := x;

 repeat

   dec(x1);

   c := memGetPixel(x1, y);

 until (c = borderColor) or (c = Color);

 repeat

   inc(xr);

   c := memGetPixel(xr, y);

 until (c = borderColor) or (c = Color);

 inc(x1); dec(xr);

 BLine(x1, y, xr + 1, y, color);

 x := x1;

 while x <= xr do

 begin

   c := memGetPixel(x, y + dir);

   if (c <> borderColor) and (c <> color) then

     x := LineFill(x, y + dir, dir, x1, xr, borderColor, color);

   inc(x);

 end;

 x := x1;

 while x < prevX1 do

 begin

   c := memGetPixel(x, y - dir);

   if (c <> borderColor) and (c <> color) then

     x := LineFill(x, y - dir, -dir, x1, xr, borderColor, color);

   inc(x);

 end;

 x := prevXR;

 while x < xR do

 begin

   c := memGetPixel(x, y - dir);

   if (c <> borderColor) and (c <> color) then

     x := LineFill(x, y - dir, -dir, x1, xr, borderColor, color);

   inc(x);

 end;

 LineFill := xR;

end;

procedure FillRegion(const x, y, borderColor, color: integer);

begin

 LineFill(x, y, 1, x, x, borderColor, color);

end;

                    
Питання для самоконтролю.
 [50]

  1.  Назвіть загальні методи, які використовуються при заповненні замкнених областей.

В чому полягає сутність методів растрової розгортки при зафарбовуванні замкненої області.

В чому полягає сутність методів зафарбовування із затравкою.

Опишіть алгоритм малювання зафарбованого трикутника.

Опишіть алгоритм заповнення області, заданою кольором межі, із затравкою.

Завдання для самостійного виконання.[50]

  1.  Створити процедуру малювання зафарбованого трикутника.[20]

Програмно реалізувати алгоритм визначення попадання точки в трикутник.[20]

Реалізувати найпростіший алгоритм заповнення певним кольором довільного контуру із заданим кольором межі.[10]


 

А также другие работы, которые могут Вас заинтересовать

34561. Драматургия французского экзистенциализма, ее идейные и стилевые особенности (Ж. Ануй, Ж. П. Сартр, А. Камю) 19.51 KB
  Камю. Все дозволено Ивана Карамазова единственное выражение свободы писал Альбер Камю 1913 1960. С юности Камю зачитывался Достоевским Ницше Мальро. Мысли об абсурде абсурд царит о всевластии смерти познание себя познание смерти ощущение одиночества и отчуждения от омерзительного внешнего мира все мне чуждо постоянны и неизменны в эссеистике прозе и драматургии Камю.
34562. Сюжет и герой романа А. Камю («Посторонний», «Чума») 18.47 KB
  Мерсо взрывается выкрикивает что всю жизнь ощущал дыхание мрака смерти. Гораздо больше Мерсо любит природу особенно море. Суд над Мерсо. Те кто судят Мерсо продолжают верить что бытие изначально имеет высший позитивный смысл.
34563. Конфликт в романе Сартра «Тошнота» 18.68 KB
  И он решает что будет описывать и исследовать состояния мира разумеется как они даны преобразованы его Рокантена сознанием а еще более сами эти состояния сознания. Но если Гуссерль выделяет описывает феномены сознания чтобы зафиксировать их безличные всеобщие структуры то Сартр в духе Ясперса Хайдеггера Марселя использует описание феноменов сознания для анализа таких экзистенциальных состояний как одиночество страх отчаяние отвращение и других поистине трагических мироощущений личности. Существовать значит сознавать...
34564. «Театр абсурда»(С.Беккет , Э.Ионеско) 18.84 KB
  Наиболее полно принципы абсурдизма были воплощены в драмах Лысая певица L cnttrice chuve 1950 драматурга Эжена Ионеско и В ожидании Годо Сэмюэла Беккета. Эжен Ионеско зачинатель абсурдизма во французской драматургии. Сюрреализм пьес Ионеско ведет свое происхождение от цирковой клоунады фильмов Ч. Ионеско отвергает но пьесы были вызваны к жизни глубокой тревогой за судьбы языка и его носителей.
34565. «Новый роман». Смысл названия А. Роб-Грийе «В лабиринте» 18.03 KB
  Исходный замысел – показать вещи такими какими они есть на самом деле. Мы не видим сами вещи они в идеологическом ряду. Автор стремится осовободить вещи от человеческой перспективы но быстро понимает что всерьез это сделать невозможно. Человеческое видение нагружает мир смыслами от него и пытается освободить вещи продолжает мощную модернистскую установку.
34566. Влияние идей структурализма, постструктурализма и постмодернизма на развитие послевоенной французской литературы 19.27 KB
  Барт различает не письмо и текст литературное произведение которое было основой классики. Текст вторичен соткан из цитат и многозначен. В тексте принципиально важна интертекстуальность. Барт: каждый текст является интертекстомпредставляет собой новую ткань сотканную из старых цитат.
34567. Антиутопия, фантастика, фэнтези в английской и американской литературе 20 в. (Д. Оруэл, Р. Бредбери, К. Вонегут, Д. Толкиен и др.) 19.65 KB
  Романы антиутопистов во многом схожи: каждый автор говорит о потере нравственности и о бездуховности современного поколения каждый мир антиутопистов это лишь голые инстинкты и эмоциональная инженерия[3]. В современном виде сформировался в начале XX века. Произведения фэнтези чаще всего напоминают историкоприключенческий роман действие которого происходит в вымышленном мире близком к реальному Средневековью герои которого сталкиваются со сверхъестественными явлениями и существами. В отличие от научной фантастики фэнтези не стремится...
34568. Движение «рассерженных» в английской литературе. Пьеса Д. Осборна «Оглянись во гневе» 19.53 KB
  Так герой пьесы Джимми Портер в Оглянись во гневе осыпает проклятиями все и вся но не произносит ни одной конструктивной мысли и обнаруживает полнейшую беззащитность перед ненавистным и угрожающим ему миром который наступает на него со всех сторон и с которым он не в силах бороться. лишь Джимми Портер. С первых слов пьесы и до ее последних строк звучит непрерывный вопль Джимми. Джимми Портер выходец из рабочей среды но его связи с ней давно порваны.
34569. Анитиколониальная и политическая проблематика в английском романе 21.82 KB
  Английский журналист Фаулер от лица которого идёт рассказ и молодой американский дипломат Пайл связанные с самого начала романа далеко не простыми взаимоотношениями. Его антиподом был английский репортёр Фаулер – усталый душевно опустошённый человек который воспринимает себя как репортёра задача которого – давать одни факты. Человек потерявший идеалы и лишённый каких либо стремлений Фаулер пытается остаться сторонним наблюдателем той борьбы и злодеяний которые развёртываются на его глазах и ищет утешения от страдания в любви. Именно...