При выборе очередного пикселя окружности имеется
При удалении объектов от центра проекции их изображение на картинной плоскости:
- (Правильный ответ) уменьшается
- увеличивается
- перекашивается
Если векторное произведение двух векторов ненулевой длины равно нулевому вектору, то эти два вектора:
- (Правильный ответ) коллинеарны
- взаимно перпендикулярны
- компланарны
В алгоритме Робертса для определения того, какая часть видимого ребра многогранника экранируется другими многогранниками, используется:
- уравнение плоскости, проходящей через данное ребро и точку положения наблюдателя, и параметрическое уравнение ребра
- (Правильный ответ) параметрическое уравнение ребра и параметрическое уравнение луча, идущего от наблюдателя в произвольную точку ребра
- уравнения плоскостей, содержащих данное ребро и параметрическое уравнение луча, который идет от наблюдателя в произвольную точку ребра
Развертывающаяся поверхность — это:
- (Правильный ответ) поверхность, отображающаяся на плоскость с сохранением расстояний между точками
- поверхность, составленная из четырехугольников
- поверхность, склеенная из кусков цилиндров разных диаметров
Кто из перечисленных специалистов разрабатывал алгоритмы закрашивания?
- (Правильный ответ) А. Гуро
- Э. Кэтмул
- Дж. Варнок
Проекция является изометрической, если:
- (Правильный ответ) нормаль к проекционной плоскости образует равные углы с осями координат
- направление проецирования составляет 45° с проекционной плоскостью
- проекционная плоскость совпадает с одной из координатных плоскостей
Какие параметры являются основой модели HSV?
- (Правильный ответ) тон, светлота, насыщенность
- яркость, контрастность, интенсивность
- высота, длина, объем
Алгоритмы Брезенхема растровой дискретизации окружности и эллипса
Алгоритм изображения окружности несколько сложнее, чем построение отрезка. Мы рассмотрим его для случая окружности радиуса с центром в начале координат. Перенесение его на случай произвольного центра не составляет труда. При построении растровой развертки окружности можно воспользоваться ее симметрией относительно координатных осей и прямых . Необходимо сгенерировать лишь одну восьмую часть окружности, а остальные ее части можно получить путем отображений симметрии. За основу можно взять часть окружности от 0 до 45 в направлении по часовой стрелке с исходной точкой построения . В этом случае координата окружности является монотонно убывающей функцией координаты .
При выбранном направлении движения по окружности имеется только три возможности для расположения ближайшего пикселя: на единицу вправо, на единицу вниз и по диагонали вниз (рис. 8.7). Выбор варианта можно осуществить, вычислив расстояния до этих точек и выбрав минимальное из них:
Алгоритм можно упростить, перейдя к анализу знаков величин . При диагональная точка лежит внутри окружности, поэтому ближайшими точками могут быть только диагональная и правая. Теперь достаточно проанализировать знак выражения . Если , выбираем горизонтальный шаг, в противном случае - диагональный. Если же 0" />
, то определяем знак , и если , выбираем диагональный шаг, в противном случае - вертикальный. Затем вычисляется новое значение , причем желательно минимизировать вычисления не только этой величины, но и величин на каждом шаге алгоритма. Путем несложных преобразований можно получить для первого шага алгоритма, что .
После перехода в точку по диагонали новое значение вычисляется по формуле , при горизонтальном переходе , при вертикальном - .
Таким образом, алгоритм рисования этой части окружности можно считать полностью описанным (блок-схема его приведена нарис. 8.8). Все оставшиеся ее части строятся параллельно: после получения очередной точки можно инициализировать еще семь точек с координатами .
Для построения растровой развертки эллипса с осями, параллельными осям координат, и радиусами воспользуемся каноническим уравнением
В отличие от окружности, для которой было достаточно построить одну восьмую ее часть, а затем воспользоваться свойствами симметрии, эллипс имеет только две оси симметрии, поэтому придется строить одну четверть всей фигуры. За основу возьмем дугу, лежащую между точками и в первом квадранте координатной плоскости.
В каждой точке эллипса существует вектор нормали, задаваемый градиентом функции . Дугу разобьем на две части: первая - с углом между нормалью и горизонтальной осью больше 45 (тангенс больше 1) и вторая - с углом, меньшим 45 (рис. 8.9). Движение вдоль дуги будем осуществлять в направлении по часовой стрелке, начиная с точки . Вдоль всей дуги координата является монотонно убывающей функцией от , но в первой части она убывает медленнее, чем растет аргумент, а во второй - быстрее. Поэтому при построении растрового образа в первой части будем увеличивать на единицу и искать соответствующее значение , а во второй - сначала уменьшать значение на единицу и определять соответствующее значение .
Направление нормали соответствует вектору
Отсюда находим тангенс угла наклона вектора нормали: . Приравнивая его единице, получаем, что координаты точки деления дуги на вышеуказанные части удовлетворяют равенству . Поэтому критерием того, что мы переходим ко второй области в целочисленных координатах, будет соотношение , или, переходя к целочисленным операциям, .
При перемещении вдоль первого участка дуги мы из каждой точки переходим либо по горизонтали, либо по диагонали, и критерий такого перехода напоминает тот, который использовался при построении растрового образа окружности. Находясь в точке , мы будем вычислять значение . Если это значение меньше нуля, то дополнительная точка лежит внутри эллипса, следовательно, ближайшая точка растра есть , в противном случае это точка (рис. 8.10а).
На втором участке дуги возможен переход либо по диагонали, либо по вертикали, поэтому здесь сначала значение координаты y уменьшается на единицу, затем вычисляется и направление перехода выбирается аналогично предыдущему случаю (рис. 8.10б).
Остается оптимизировать вычисление параметра , умножив его на 4 и представив в виде функции координат точки. Тогда для первой половины дуги имеем
Все оставшиеся дуги эллипса строятся параллельно: после получения очередной точки , можно инициализировать еще три точки с координатами . Блок-схему не приводим ввиду прозрачности алгоритма.
Векторы называются коллинеарными, если:
- (Правильный ответ) они лежат на параллельных прямых
- они имеют равную длину
- они лежат на перпендикулярных прямых
Какие три цвета являются базовыми в восприятии глазом человека?
- оранжевый, фиолетовый, зеленый
- голубой, малиновый, желтый
- (Правильный ответ) красный, зеленый, синий
Для увеличения эффективности поиска пересечений луча с объектами в методе трассировки лучей используется:
- двоичное разбиение пространства
- метод деления отрезка пополам
- (Правильный ответ) погружение объектов в сферические оболочки
Плоскость задана уравнением , луч — уравнениями . Какая из следующих групп условий необходима для того, чтобы луч пересек плоскость?
Какая из следующих формул является формулой линейной интерполяции функции одной переменной ( — значения аргумента, — значения функции)?
Важным условием применения модели излучательности является:
- (Правильный ответ) предположение, что для каждой пары элементов сцены можно определить, какая доля энергии одного попадает на другой
- (Правильный ответ) то, что все объекты сцены являются идеальными рассеивателями
- возможность вычисления расстояния до источника света от любой поверхности сцены
Метод трассировки лучей основан на:
- отслеживании луча света от источника до его попадания на первый же объект сцены
- отслеживании луча от источника света до наблюдателя с учетом отражений от предметов
- (Правильный ответ) отслеживании луча в обратном порядке от наблюдателя к объектам и к источнику света с учетом отражений
На первом шаге алгоритма Аппеля строится матрица элементы которой показывают:
- (Правильный ответ) какие из проекционных многоугольников отбрасывают тень на другие
- отбрасывает ли проекционный многоугольник тень
- какие из элементов сцены экранируют другие от наблюдателя
Какой из следующих наборов данных однозначно определяет плоскость?
- (Правильный ответ) три точки в пространстве не лежащие на одной прямой
- точка, принадлежащая плоскости, и расстояние от плоскости до начала координат
- четыре точки в пространстве
Структура какого цветового пространства основана на теории, что цвет не может быть одновременно зеленым и красным или желтым и синим?
Наиболее трудоемкая процедура в методе трассировки лучей:
- (Правильный ответ) поиск пересечений луча с объектами сцены
- расчет преломленного луча при прохождении полупрозрачных объектов
- расчет отраженного луча
Укажите плоскость, на которую осуществляется проекция с помощью следующей матрицы:
Двоичное разбиение пространства используется:
- при изображении гладких поверхностей
- (Правильный ответ) при изображении многогранников
- (Правильный ответ) при изображении сцен, содержащих объекты, для каждого из которых уже имеется алгоритм вывода на экран
Если найдены барицентрические координаты точки внутри треугольника с вершинами , то как выглядит формула линейной интерполяции на треугольнике?
Границы окна заданы уравнениями . Отрезок задан параметрическими уравнениями
При каком условии он обязательно пересечет прямую, содержащую нижнюю границу окна (ее уравнение )?
При закрашивании грани многогранника, аппроксимирующего гладкую поверхность, по методу Фонга:
- интенсивность освещения точек грани вычисляется путем билинейной интерполяции интенсивностей, вычисленных в вершинах
- (Правильный ответ) интенсивность освещения точек вычисляется с учетом направления нормали к поверхности, которая строится путем билинейной интерполяции нормалей в точках, соответствующих вершинам многогранника
- интенсивность освещения точек грани постоянна
Алгоритм Брезенхема растровой дискретизации отрезка
При построении растрового образа отрезка необходимо, прежде всего, установить критерии "хорошей" аппроксимации. Первое требование состоит в том, что отрезок должен начинаться и кончаться в заданных точках и при этом выглядеть сплошным и прямым (при достаточно высоком разрешении дисплея этого можно добиться). Кроме того, яркость вдоль отрезка должна быть одинаковой и не зависеть от наклона отрезка и его длины. Это требование выполнить сложнее, поскольку горизонтальные и вертикальные отрезки всегда будут ярче наклонных, а постоянная яркость вдоль отрезка опять же достигается на вертикальных, горизонтальных и наклоненных под углом в 45 линиях. И, наконец, алгоритм должен работать быстро. Для этого необходимо по возможности исключить операции с вещественными числами. С целью ускорения работы алгоритма можно также реализовать его на аппаратном уровне.
В большинстве алгоритмов используется пошаговый метод изображения, т.е. для нахождения координат очередной точки растрового образа наращивается значение одной из координат на единицу растра и вычисляется приращение другой координаты.
Задача состоит в построении отрезка, соединяющего на экране точки с координатами (будем считать, что ). Для построения отрезка прямой на плоскости с вещественными координатами можно воспользоваться уравнением прямой, проходящей через две заданные точки, которое имеет вид
Теперь, считая, что - координаты текущей точки растрового образа, а - точное значение координаты точки отрезка, можно построить следующую точку:
Следует заметить, что целочисленная координата изменится только в том случае, если y превысит величину ( есть ближайшее к целое число, полученное в результате операции округления). Приведенный пример включает операции с вещественными числами, которые выполняются существенно медленнее, чем соответствующие целочисленные операции, а при построении растрового образа отрезка желателен алгоритм, по возможности обращающийся только к целочисленной арифметике. Кроме того, алгоритм должен работать при любом взаимном расположении концов отрезка.
Алгоритм Брезенхема построения растрового образа отрезка был изначально разработан для графопостроителей , но он полностью подходит и для растровых дисплеев. В процессе работы в зависимости от углового коэффициента отрезка наращивается на единицу либо , либо , а изменение другой координаты зависит от расстояния между действительным положением точки и ближайшей точкой растра (смещения). Алгоритм построен так, что анализируется лишь знак этого смещения.
На рис. 8.2 это иллюстрируется для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент , то при выходе из точки пересечение с прямой будет ближе к прямой , чем к прямой . Следовательно, точка растра лучше аппроксимирует прохождение отрезка, чем точка . При верно обратное.
На рис. 8.3 показано, каким образом строятся точки растра для отрезка с тангенсом угла наклона , а на рис. 8.4 - график смещения. В начале построения смещение полагается равным , а затем на каждом шаге оно наращивается на величину , и если при этом вертикальная координата точки растра увеличивается на единицу, то смещение в свою очередь уменьшается на единицу.
На рис. 8.5 приведена блок-схема алгоритма для случая i_1, \quad j_2> j_1, \quad k>0" />
. Нетрудно понять, как от этого алгоритма перейти к целочисленному: достаточно вместо величины смещения перейти к величине =2\Delta i\cdot e" />
.
Приведем общий алгоритм Брезенхема, который учитывает все возможные случаи направления отрезка, рассматриваемого как вектор на координатной плоскости (на рис. 8.6 выделены четыре области и указаны особенности алгоритма в каждой из них).
В описании алгоритма используются следующие функции:
Предполагается, что концы отрезка не совпадают и что все используемые переменные являются целыми.
Технической основой возникновения компьютерной графики явилось:
- использование в компьютере магнитной ленты как носителя информации
- увеличение производительности компьютеров
- (Правильный ответ) использование дисплея как устройства вывода
Какие из следующих алгоритмов свето-теневого анализа работают в объектном пространстве?
- (Правильный ответ) модифицированный алгоритм Вейлера-Азертона
- алгоритм Аппеля
- метод теневого буфера
Достоинством проекции Меркатора является то, что она:
- сохраняет относительные расстояния между точками
- (Правильный ответ) является конформной
- сохраняет относительные масштабы материков
В алгоритме Брезенхема растровой развертки окружности основные построения производятся для:
- четверти окружности
- половины окружности
- (Правильный ответ) одной восьмой части окружности
Алгоритм отсечения отрезка выпуклым многоугольником начинается:
- с определения, не проходит ли он через вершину многоугольника
- (Правильный ответ) с анализа расположения концов отрезка по отношению к окну
- с определения, является ли он параллельным одной из сторон многоугольника
Оставить комментарий
Inna Petrova 18 минут назад
Нужно пройти преддипломную практику у нескольких предметов написать введение и отчет по практике так де сдать 4 экзамена после практики
Иван, помощь с обучением 25 минут назад
Коля 2 часа назад
Здравствуйте, сколько будет стоить данная работа и как заказать?
Иван, помощь с обучением 2 часа назад
Инкогнито 5 часов назад
Сделать презентацию и защитную речь к дипломной работе по теме: Источники права социального обеспечения. Сам диплом готов, пришлю его Вам по запросу!
Иван, помощь с обучением 6 часов назад
Василий 12 часов назад
Здравствуйте. ищу экзаменационные билеты с ответами для прохождения вступительного теста по теме Общая социальная психология на магистратуру в Московский институт психоанализа.
Иван, помощь с обучением 12 часов назад
Анна Михайловна 1 день назад
Нужно закрыть предмет «Микроэкономика» за сколько времени и за какую цену сделаете?
Иван, помощь с обучением 1 день назад
Сергей 1 день назад
Здравствуйте. Нужен отчёт о прохождении практики, специальность Государственное и муниципальное управление. Планирую пройти практику в школе там, где работаю.
Иван, помощь с обучением 1 день назад
Инна 1 день назад
Добрый день! Учусь на 2 курсе по специальности земельно-имущественные отношения. Нужен отчет по учебной практике. Подскажите, пожалуйста, стоимость и сроки выполнения?
Иван, помощь с обучением 1 день назад
Студент 2 дня назад
Здравствуйте, у меня сегодня начинается сессия, нужно будет ответить на вопросы по русскому и математике за определенное время онлайн. Сможете помочь? И сколько это будет стоить? Колледж КЭСИ, первый курс.
Иван, помощь с обучением 2 дня назад
Ольга 2 дня назад
Требуется сделать практические задания по математике 40.02.01 Право и организация социального обеспечения семестр 2
Иван, помощь с обучением 2 дня назад
Вика 3 дня назад
сдача сессии по следующим предметам: Этика деловых отношений - Калашников В.Г. Управление соц. развитием организации- Пересада А. В. Документационное обеспечение управления - Рафикова В.М. Управление производительностью труда- Фаизова Э. Ф. Кадровый аудит- Рафикова В. М. Персональный брендинг - Фаизова Э. Ф. Эргономика труда- Калашников В. Г.
Иван, помощь с обучением 3 дня назад
Игорь Валерьевич 3 дня назад
здравствуйте. помогите пройти итоговый тест по теме Обновление содержания образования: изменения организации и осуществления образовательной деятельности в соответствии с ФГОС НОО
Иван, помощь с обучением 3 дня назад
Вадим 4 дня назад
Пройти 7 тестов в личном кабинете. Сооружения и эксплуатация газонефтипровод и хранилищ
Иван, помощь с обучением 4 дня назад
Кирилл 4 дня назад
Здравствуйте! Нашел у вас на сайте задачу, какая мне необходима, можно узнать стоимость?
Иван, помощь с обучением 4 дня назад
Oleg 4 дня назад
Требуется пройти задания первый семестр Специальность: 10.02.01 Организация и технология защиты информации. Химия сдана, история тоже. Сколько это будет стоить в комплексе и попредметно и сколько на это понадобится времени?
Иван, помощь с обучением 4 дня назад
Валерия 5 дней назад
ЗДРАВСТВУЙТЕ. СКАЖИТЕ МОЖЕТЕ ЛИ ВЫ ПОМОЧЬ С ВЫПОЛНЕНИЕМ практики и ВКР по банку ВТБ. ответьте пожалуйста если можно побыстрее , а то просто уже вся на нервяке из-за этой учебы. и сколько это будет стоить?
Иван, помощь с обучением 5 дней назад
Инкогнито 5 дней назад
Здравствуйте. Нужны ответы на вопросы для экзамена. Направление - Пожарная безопасность.
Иван, помощь с обучением 5 дней назад
Иван неделю назад
Защита дипломной дистанционно, "Синергия", Направленность (профиль) Информационные системы и технологии, Бакалавр, тема: «Автоматизация приема и анализа заявок технической поддержки
Иван, помощь с обучением неделю назад
Дарья неделю назад
Иван, помощь с обучением неделю назад
Алгоритм изображения окружности несколько сложнее, чем построение отрезка. Мы рассмотрим его для случая окружности радиуса с центром в начале координат. Перенесение его на случай произвольного центра не составляет труда. При построении растровой развертки окружности можно воспользоваться ее симметрией относительно координатных осей и прямых . Необходимо сгенерировать лишь одну восьмую часть окружности, а остальные ее части можно получить путем отображений симметрии. За основу можно взять часть окружности от 0 до 45 в направлении по часовой стрелке с исходной точкой построения . В этом случае координата окружности является монотонно убывающей функцией координаты .
При выбранном направлении движения по окружности имеется только три возможности для расположения ближайшего пикселя: на единицу вправо, на единицу вниз и по диагонали вниз (рис. 8.7). Выбор варианта можно осуществить, вычислив расстояния до этих точек и выбрав минимальное из них:
Алгоритм можно упростить, перейдя к анализу знаков величин . При диагональная точка лежит внутри окружности, поэтому ближайшими точками могут быть только диагональная и правая. Теперь достаточно проанализировать знак выражения . Если , выбираем горизонтальный шаг, в противном случае - диагональный. Если же 0" />
, то определяем знак , и если , выбираем диагональный шаг, в противном случае - вертикальный. Затем вычисляется новое значение , причем желательно минимизировать вычисления не только этой величины, но и величин на каждом шаге алгоритма. Путем несложных преобразований можно получить для первого шага алгоритма, что .
После перехода в точку по диагонали новое значение вычисляется по формуле , при горизонтальном переходе , при вертикальном - .
Таким образом, алгоритм рисования этой части окружности можно считать полностью описанным ( блок-схема его приведена на рис. 8.8). Все оставшиеся ее части строятся параллельно: после получения очередной точки можно инициализировать еще семь точек с координатами .
Для построения растровой развертки эллипса с осями, параллельными осям координат, и радиусами воспользуемся каноническим уравнением
В отличие от окружности, для которой было достаточно построить одну восьмую ее часть, а затем воспользоваться свойствами симметрии, эллипс имеет только две оси симметрии, поэтому придется строить одну четверть всей фигуры. За основу возьмем дугу, лежащую между точками и в первом квадранте координатной плоскости.
В каждой точке эллипса существует вектор нормали, задаваемый градиентом функции . Дугу разобьем на две части: первая - с углом между нормалью и горизонтальной осью больше 45 (тангенс больше 1) и вторая - с углом, меньшим 45 (рис. 8.9). Движение вдоль дуги будем осуществлять в направлении по часовой стрелке, начиная с точки . Вдоль всей дуги координата является монотонно убывающей функцией от , но в первой части она убывает медленнее, чем растет аргумент , а во второй - быстрее. Поэтому при построении растрового образа в первой части будем увеличивать на единицу и искать соответствующее значение , а во второй - сначала уменьшать значение на единицу и определять соответствующее значение .
Направление нормали соответствует вектору
Отсюда находим тангенс угла наклона вектора нормали: . Приравнивая его единице, получаем, что координаты точки деления дуги на вышеуказанные части удовлетворяют равенству . Поэтому критерием того, что мы переходим ко второй области в целочисленных координатах, будет соотношение , или, переходя к целочисленным операциям, .
При перемещении вдоль первого участка дуги мы из каждой точки переходим либо по горизонтали, либо по диагонали, и критерий такого перехода напоминает тот, который использовался при построении растрового образа окружности. Находясь в точке , мы будем вычислять значение . Если это значение меньше нуля, то дополнительная точка лежит внутри эллипса, следовательно, ближайшая точка растра есть , в противном случае это точка (рис. 8.10а).
На втором участке дуги возможен переход либо по диагонали, либо по вертикали, поэтому здесь сначала значение координаты y уменьшается на единицу, затем вычисляется и направление перехода выбирается аналогично предыдущему случаю (рис. 8.10б).
Остается оптимизировать вычисление параметра , умножив его на 4 и представив в виде функции координат точки. Тогда для первой половины дуги имеем
Все оставшиеся дуги эллипса строятся параллельно: после получения очередной точки , можно инициализировать еще три точки с координатами . Блок-схему не приводим ввиду прозрачности алгоритма.
Для заполнения областей , ограниченных замкнутой линией, применяются два основных подхода: затравочное заполнение и растровая развертка .
Методы первого типа исходят из того, что задана некоторая точка (затравка) внутри контура и задан критерий принадлежности точки границе области (например, задан цвет границы). В алгоритмах ищут точки, соседние с затравочной и расположенные внутри контура. Если обнаружена соседняя точка, принадлежащая внутренней области контура, то она становится затравочной и поиск продолжается рекурсивно.
Методы растровой развертки основаны на сканировании строк растра и определении, лежит ли точка внутри заданного контура области. Сканирование осуществляется чаще всего "сверху вниз", а алгоритм определения принадлежности точки заданной области зависит от вида ее границы.
Сначала рассмотрим простой алгоритм заполнения с затравкой с использованием стека. Под стеком в данном случае мы будем понимать массив , в который можно последовательно помещать значения и последовательно извлекать, причем извлекаются элементы не в порядке поступления, а наоборот: по принципу "первым пришел - последним ушел" (" first in - last out"). Алгоритм заполнения выглядит следующим образом:
Алгоритм можно модифицировать таким образом, что соседними будут считаться восемь пикселей (добавляются элементы, расположенные в диагональном направлении).
Методы растровой развертки рассмотрим сначала в применении к заполнению многоугольников. Простейший метод построения состоит в том, чтобы для каждого пикселя растра проверить его принадлежность внутренности многоугольника. Но такой перебор слишком неэкономичен, поскольку фигура может занимать лишь незначительную часть экрана, а геометрический поиск - задача трудоемкая, сопряженная с длинными вычислениями. Алгоритм станет более эффективным, если предварительно выявить минимальный прямоугольник , в который погружен контур многоугольника, но и этого может оказаться недостаточно.
В случае, когда многоугольник, ограничивающий область, задан списком вершин и ребер ( ребро определяется как пара вершин), можно предложить еще более экономный метод. Для каждой сканирующей строки определяются точки пересечения с ребрами многогранника, которые затем упорядочиваются по координате . Определение того, какой интервал между парами пересечений есть внутренний для многогранника, а какой нет, является достаточно простой логической задачей. При этом если сканирующая строка проходит через вершину многогранника, то это пересечение должно быть учтено дважды в случае, когда вершина является точкой локального минимума или максимума. Для поиска пересечений сканирующей строки с ребрами можно использовать алгоритм Брезенхема построения растрового образа отрезка.
В заключение в качестве примера приведем алгоритм закраски внутренней области треугольника, основанный на составлении полного упорядоченного списка всех отрезков, составляющих этот треугольник. Для записи горизонтальных координат концов этих отрезков будем использовать два массива " />
и " />
размерностью, равной числу пикселей растра по вертикали (рис. 8.11).
Построение начинается с инициализации массивов " />
и " />
: массив " />
заполняется нулями, а массив " />
- числом , равным числу пикселей растра по горизонтали. Затем определяем значения ,J_" />
, ограничивающие треугольник в вертикальном направлении. Теперь, используя модифицированный алгоритм Брезенхема, занесем границы отрезков в массивы " />
и " />
. Для этого всякий раз при переходе к очередному пикселю при формировании отрезка вместо его инициализации будем сравнивать его координату с содержимым -й ячейки массивов. Если [j]> i" />
, то записываем координату в массив " />
. Аналогично при условии [j] < i" />
координату записываем в массив " />
.
.
Этот алгоритм можно легко распространить на случай произвольного выпуклого многоугольника.
Какие законы используются для смешения цветов с применением координат МКО?
- Менделя
- Ньютона
- (Правильный ответ) Грассмана
В каком случае при использовании метода деления отрезка пополам на первом итерационном шаге дроблению будут подвергаться два отрезка?
- когда исходный отрезок — полностью видимый
- когда один конец отрезка лежит внутри окна
- (Правильный ответ) когда отрезок имеет две точки пересечения с границами окна
К центральным проекциям относятся:
- аксонометрическая
- (Правильный ответ) перспективная с двумя точками схода
- изометрическая
- косоугольная
Алгоритмы заполнения областей
Для заполнения областей , ограниченных замкнутой линией, применяются два основных подхода: затравочное заполнение и растровая развертка.
Методы первого типа исходят из того, что задана некоторая точка (затравка) внутри контура и задан критерий принадлежности точки границе области (например, задан цвет границы). В алгоритмах ищут точки, соседние с затравочной и расположенные внутри контура. Если обнаружена соседняя точка, принадлежащая внутренней области контура, то она становится затравочной и поиск продолжается рекурсивно.
Методы растровой развертки основаны на сканировании строк растра и определении, лежит ли точка внутри заданного контура области. Сканирование осуществляется чаще всего "сверху вниз", а алгоритм определения принадлежности точки заданной области зависит от вида ее границы.
Сначала рассмотрим простой алгоритм заполнения с затравкой с использованием стека. Под стеком в данном случае мы будем понимать массив, в который можно последовательно помещать значения и последовательно извлекать, причем извлекаются элементы не в порядке поступления, а наоборот: по принципу "первым пришел - последним ушел" ("first in - last out"). Алгоритм заполнения выглядит следующим образом:
Алгоритм можно модифицировать таким образом, что соседними будут считаться восемь пикселей (добавляются элементы, расположенные в диагональном направлении).
Методы растровой развертки рассмотрим сначала в применении к заполнению многоугольников. Простейший метод построения состоит в том, чтобы для каждого пикселя растра проверить его принадлежность внутренности многоугольника. Но такой перебор слишком неэкономичен, поскольку фигура может занимать лишь незначительную часть экрана, а геометрический поиск - задача трудоемкая, сопряженная с длинными вычислениями. Алгоритм станет более эффективным, если предварительно выявить минимальный прямоугольник, в который погружен контур многоугольника, но и этого может оказаться недостаточно.
В случае, когда многоугольник, ограничивающий область, задан списком вершин и ребер (ребро определяется как пара вершин), можно предложить еще более экономный метод. Для каждой сканирующей строки определяются точки пересечения с ребрами многогранника, которые затем упорядочиваются по координате . Определение того, какой интервал между парами пересечений есть внутренний для многогранника, а какой нет, является достаточно простой логической задачей. При этом если сканирующая строка проходит через вершину многогранника, то это пересечение должно быть учтено дважды в случае, когда вершина является точкой локального минимума или максимума. Для поиска пересечений сканирующей строки с ребрами можно использовать алгоритм Брезенхема построения растрового образа отрезка.
В заключение в качестве примера приведем алгоритм закраски внутренней области треугольника, основанный на составлении полного упорядоченного списка всех отрезков, составляющих этот треугольник. Для записи горизонтальных координат концов этих отрезков будем использовать два массива " />
и " />
размерностью, равной числу пикселей растра по вертикали (рис. 8.11).
Построение начинается с инициализации массивов " />
и " />
: массив " />
заполняется нулями, а массив " />
- числом , равным числу пикселей растра по горизонтали. Затем определяем значения ,J_" />
, ограничивающие треугольник в вертикальном направлении. Теперь, используя модифицированный алгоритм Брезенхема, занесем границы отрезков в массивы " />
и " />
. Для этого всякий раз при переходе к очередному пикселю при формировании отрезка вместо его инициализации будем сравнивать его координату с содержимым -й ячейки массивов. Если [j]> i" />
, то записываем координату в массив " />
. Аналогично при условии [j] < i" />
координату записываем в массив " />
.
.
Этот алгоритм можно легко распространить на случай произвольного выпуклого многоугольника.
Задана матрица и вектор . Результатом умножения матрицы на вектор является вектор , координаты которого вычисляются по формуле:
При выборе очередного пикселя окружности имеется:
- четыре варианта направлений
- (Правильный ответ) три варианта направлений
- восемь вариантов направлений
В алгоритме клиппирования многоугольника обход вершин всегда осуществляется:
- по часовой стрелке
- против часовой стрелки
- (Правильный ответ) направление не важно, но обход должен быть последовательным
Вопросы и упражнения
- Что такое разложение в растр?
- Какова математическая основа растрового разложения в алгоритме Брезенхема?
- По какому критерию инициализируется пиксель в этом алгоритме?
- Чем отличаются ветви алгоритма при углах наклона 45 ?
- Какую часть окружности достаточно построить, чтобы затем путем отражений получить окружность целиком?
- Какую часть эллипса достаточно построить, чтобы затем путем отражений получить эллипс целиком?
- Назовите два типа алгоритмов заполнения областей .
- Какая структура данных используется в алгоритмах с затравкой?
- Какие данные используются при построении растровой развертки треугольника?
Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).
Окружность с центром в начале координат описывается уравнением:
Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi, Yi), ближайшую к истинной окружности, так чтобы ошибка:
была минимальной. Причем, как и в алгоритме Брезенхема для генерации отрезков, выбор ближайшей точки выполняется с помощью анализа значений управляющих переменных, для вычисления которых не требуется вещественной арифметики. Для выбора очередной точки достаточно проанализировать знаки.
Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.
Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.
Рис. 0.3.1: Варианты расположения очередного пиксела окружности
При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) - перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) - перемещение по диагонали, либо Pv = (Xi, Yi-1) - перемещение по вертикали.
Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:
Выбирается и заносится та точка, для которой это значение минимально.
Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd >0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.
Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.
Для определения того, какой пиксел выбрать Pg или Pd составим разность:
И будем выбирать точку Pg при di < 0, в противном случае выберем Pd.
Рассмотрим вычисление di для разных вариантов.
Для вариантов 2 и 3:
Добавив и вычтя (Y-1) 2 получим:
В квадратных скобках стоит Dd, так что
Для варианта 1:
Случай Dd > 0
Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.
Для определения того, какую пиксел выбрать Pd или Pv составим разность:
Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.
Рассмотрим вычисление si для разных вариантов.
Для вариантов 5 и 6:
Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.
Добавив и вычтя (X+1) 2 получим:
В квадратных скобках стоит Dd, так что
Для варианта 7:
Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.
Случай Dd = 0
Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.
di > 0 - выбор диагонального пиксела Pd
si > 0 - выбор вертикального пиксела Pv
выбор диагонального пиксела Pd.
Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.
1. Для горизонтального шага к Xi+1, Yi
2. Для диагонального шага к Xi+1, Yi-1
3. Для вертикального шага к Xi, Yi-1
В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:
Dd = (X+1) 2 + (Y-1) 2 - R 2 = 1 + (R-1) 2 - R 2 = 2*(1 - R)
Пикселы в остальных четвертях можно получить отражением. Кроме того достаточно сформировать дугу только во втором октанте, а остальные пикселы сформировать из соображений симметрии, например, с помощью подпрограммы Pixel_circle, приведенной в Приложении 5 и заносящей симметричные пикселы по часовой стрелке от исходного.
В Приложении 6 приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения 6. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.
Экран растрового дисплея можно рассматривать как матрицу дискретных элементов, или пикселей. Процесс определения пикселей, наилучшим образом аппроксимирующих некоторую геометрическую фигуру, называется разложением в растр, или построением растрового образа фигуры. Построчная визуализация растрового образа называется растровой разверткой данной фигуры.
В каком случае луч пересекает сферу в двух точках (задана сфера с центром в точке и радиусом )?
В каком случае устранить ступенчатый эффект невозможно?
- если изображается гладкая кривая
- (Правильный ответ) если рисунок черно-белый
- если горизонтальный или вертикальный размер изображения занимает меньше четверти экрана
Метод художника основан на:
- предварительном выявлении частей сцены, которые являются невидимыми и которые изображать не следует
- (Правильный ответ) упорядочении частей изображения по глубине и изображении всех их в порядке увеличения глубины
- разбиении сцены на отдельные части, упорядочении их по глубине и изображении только ближайших к наблюдателю
Картинная плоскость — это:
- плоскость, на которой стоят изображаемые предметы
- (Правильный ответ) плоскость, на которой формируется видимый образ посредством проекции
- плоскость в системе координат наблюдателя
Читайте также: