Вопросы к 7 - p1xelse/CG GitHub Wiki

1) Что мы называем растровой разверткой сплошных областей?

Растровая развертка сплошных областей это генерация областей на основе простых описаний рёбер или вершин.

2) Какие области можем заполнять с помощью этого алгоритма или вообще с помощью растровых?

Многоугольники(выпуклые/вогнутые)

3) Как упорядочиваем рёбра в алгоритме?

Есть текущая сканирующая строка. В списке активных рёбер хранятся только те рёбра, которые в данный момент пересекаются этой строкой. В самом начале упорядочиваются по самому большому значению сканирующей строки которая их будет пересекать. По максимальному значению координаты y. Упорядочиваем по убыванию.

4) Что такое активное ребро?

Активное ребро - то ребро, которое пересекается сканирующей строкой в рассматриваемый момент работы алгоритма.

5) Как находим активные рёбра?

Изначально сканирующую строку ставим в самую верхнюю точку, которая есть у ребра. Начинаем этой сканирующей строкой спускаться вниз.Когда встречаем ребро, у которого номер самой высшей сканирующей строки совпадает с текущей сканирующей строкой, то добавляем его в САР. Когда сканирующая строка полностью проходит это ребро удаляем его из списка.

6) Какую информацию выбираем из списка активных рёбер?

Нас интересует значение по оси абсцисс, пересечение этого ребра со сканирующей строкой.

7) Что делаем с этими значениями абсцисс?

Упорядочиваем эти значения(от меньшего к большему), разбиваем эти значения по парам.

8) Чем плох простой вариант?

Простой вариант трудоёмкий (много сортировок) и по памяти плохо (храним много данных, а именно точек пересечения всех сканирующих строк с рёбрами).

9) Как увеличиваем эффективность?

Храним пересечения только с текущей сканирующей строкой и первую сортировку по факту отбрасываем.

10) Какую СД используем?

Динамические списки. Размер списка - столько, сколько рёбер пересекает.

Каждый элемент списка хранит:

  1. Номер наивысшей сканирующей строки, которая пересекает это ребро.

  2. Абсцисса точки пересечения строки с ребром.

  3. Количество строк, пересекающих ребро.

  4. Котангенс угла наклона (приращение по x, при переходе от строки к строке).

  5. Указатель на следующий элемент списка.

Переходя к новой строке будем просматривать только те элементы списка, которые соотносятся с активными рёбрами.

Как определить какие элементы списка нам нужно рассматривать? Ведь мы не по всем элементам бегаем каждый раз

Нас будут интересовать элементы у которых номер сканирующей строки больше текущей.

11) С какими проблемами сталкиваемся в растровых алгоритмах?

Проблема 1:

Проблема может быть в горизонтальных рёбрах. (Что с ними делать?) Нужно отбрасывать одну из вершин этого ребра и не делать с ним пару. Всегда ли можно так делать? Нет не всегда. Из-за проблемы с вершинами. (вторая проблема)

Проблема 2

Существует проблема с вершинами. Два ребра в вершине имеют по точке. Проблема заключается в том, что в некоторых случаях мы должны учитывать обе точки, а в некоторых случаях одну из точек надо отбросить. Если точка является локальным экстремумом(минимумом или максимумом), то два пересечения(не отбрасываем точки).

Когда несколько горизонтальных рёбер проблема в том, что вершины не являются экстремумами.

Пример решения проблемы (!!!!не проверенный Куровым!!!!!)

Тут два горизонтальных ребра

В первом случае мы должны правую вершину горизонтали отбросить, потому что после неё идёт область вне фигуры. Во втором наоборот, мы точку не отбрасываем и используем для составления пары

В принципе можно зная какой цвет над горизонталью сказать как нам поступить: Если цвет фона и ребро идёт вверх, то не отбрасываем Если цвет закраски и ребро идёт вверх, то отбрасываем

image

Ну и по такой же логике делаем, когда ребро идёт вниз

И такой же подход для рёбер слева от горизонтали

12) Чем отличается заполнение от закраски?

РАСТРОВЫЕ МЕТОДЫ(aka ЗАКРАСКА)
В растровых методах делается попытка определить в порядке сканирования строк принадлежность точки внутренней области контура или многоугольника. Эти алгоритмы обычно просматривают многоугольники (контуры) от верхней точки до нижней. Методы растровой развертки применимы обычно и к векторным дисплеям, в которых они используются для штриховки или закраски контуров. (растровая развертка = закраска)

ЗАТРАВКА (aka ЗАПОЛНЕНИЕ)
В методах затравочного заполнения предполагается, что известна некоторая точка (затравка), лежащая внутри замкнутого контура.
В алгоритмах затравочного заполнения ищут точки, соседние с затравочными и расположенные внутри контура. Если точка оказывается внутри контура, то она становится новой затравочной точкой и поиск продолжается рекурсивно. Если же точка расположена не внутри контура, то это означает, что обнаружена граница контура. Затравочные алгоритмы применимы только к растровым дисплеям.