Алгоpитм изобpажения линий


Содержание

Алгоpитм изобpажения линий

Методы удаления невидимых частей сцены можно классифицировать:

  1. По выбору удаляемых частей:
    удаление невидимых линий, ребер, поверхностей, объемов.
  2. По порядку обработки элементов сцены:
    удаление в произвольном порядке и в порядке, определяемом процессом визуализации.
  3. По системе координат:
  • алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями (объем вычислений растет как N 2 ),
  • алгоритмы работающие в пространстве изображения, когда для каждого пиксела изображения определяется какая из N граней объекта видна (при разрешении экрана M×M объем вычислений растет как M 2 ×N).

  • 2 Алгоритмы удаления линий

    Применение — векторные устройства. Могут применяться и в растровых для ускорения процесса визуализации, но при этом не используется основное ценное качество растрового дисплея — возможность закраски поверхностей.

    Наиболее известный ранний алгоритм — алгоритм Робертса (1963 г.). Работает с только выпуклыми телами в пространстве объектов. Каждый объект сцены представляется многогранным телом, полученным в результате пересечения плоскостей. Т.е. тело описывается списком граней, состоящих из ребер, которые в свою очередь образованы вершинами.

    Вначале из описания каждого тела удаляются нелицевые плоскости, экранированные самим телом. Затем каждое из ребер сравнивается с каждым телом для определения видимости или невидимости. Т.е. объем вычислений растет как квадрат числа объектов в сцене. Наконец вычисляются новые ребра, полученные при протыкании телами друг друга.


    3 Алгоритм удаления поверхностей с Z-буфером

    Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пиксела в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пиксела дополнительно хранить еще и координату Z или глубину. При занесении очередного пиксела в буфер кадра значение его Z-координаты сравнивается с Z-координатой пиксела, который уже находится в буфере. Если Z-координата нового пиксела больше, чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пиксела и его Z-координата заносятся в буфер, если нет, то ни чего не делается.

    Этот алгоритм наиболее простой из всех алгоритмов удаления невидимых поверхностей, но требует большого объема памяти. Данные о глубине для реалистичности изображения обычно достаточно иметь с разрядностью порядка 20 бит. В этом случае при изображении нормального телевизионного размера в 768×576 пикселов для хранения Z-координат необходим объем памяти порядка 1 Мбайта. Суммарный объем памяти при 3 байтах для значений RGB составит более 2.3 Мбайта.

    Время работы алгоритма не зависит от сложности сцены. Многоугольники, составляющие сцену, могут обрабатываться в произвольном порядке. Для сокращения затрат времени нелицевые многоугольники могут быть удалены. По сути дела алгоритм с Z-буфером — некоторая модификация уже рассмотренного алгоритма заливки многоугольника. Если используется построчный алгоритм заливки, то легко сделать пошаговое вычисление Z-координаты очередного пиксела, дополнительно храня Z-координаты его вершин и вычисляя приращение dz Z-координаты при перемещении вдоль X на dx, равное 1. Если известно уравнение плоскости, в которой лежит обрабатываемый многоугольник, то можно обойтись без хранения Z-координат вершин. Пусть уравнение плоскости имеет вид:

    A·x + B·y + C·z + D = 0.

    Тогда при C не равном нулю

    z = -(A·x + B·y + D)/C

    Найдем приращение Z-координаты пиксела при шаге по X на dx, помня, что Y очередной обрабатываемой строки — константа.

    dz = -(A·(x+dx) + D)/C + (A·x + D)/C = -A·dx/C

    но dx = 1, поэтому

    dz = -A/C.

    Основной недостаток алгоритма с Z-буфером — дополнительные затраты памяти. Для их уменьшения можно разбивать изображение на несколько прямоугольников или полос. В пределе можно использовать Z-буфер в виде одной строки. Понятно, что это приведет к увеличению времени, так как каждый прямоугольник будет обрабатываться столько раз, на сколько областей разбито пространство изображения. Уменьшение затрат времени в этом случае может быть обеспечено предварительной сортировкой многоугольников на плоскости.

    Другие недостатки алгоритма с Z-буфером заключаются в том, что так как пикселы в буфер заносятся в произвольном порядке, то возникают трудности с реализацией эффектов прозрачности или просвечивания и устранением лестничного эффекта с использованием предфильтрации, когда каждый пиксел экрана трактуется как точка конечного размера и его атрибуты устанавливаются в зависимости от того какая часть пиксела изображения попадает в пиксел экрана. Но другой подход к устранению лестничного эффекта, основанный на постфильтрации — усреднении значений пиксела с использованием изображения с большим разрешением реализуется сравнительно просто за счет увеличения расхода памяти (и времени). В этом случае используются два метода. Первый состоит в том, что увеличивается разрешение только кадрового буфера, хранящего атрибуты пикселов, а разрешение Z-буфера делается совпадающим с размерами пространства изображения. Глубина изображения вычисляется только для центра группы усредняемых пикселов. Это метод неприменим, когда расстояние до наблюдателя имитируется изменением интенсивности пикселов. Во втором методе и кадровый и Z буфера имеют увеличенное разрешение и усредняются атрибуты пиксела, так и его глубина.

    Общая схема алгоритма с Z-буфером:

    · Инициализировать кадровый и Z-буфера. Кадровый буфер закрашивается фоном. Z-буфер закрашивается минимальным значением Z.

    · Выполнить преобразование каждого многоугольника сцены в растровую форму. При этом для каждого пиксела вычисляется его глубина z. Если вычисленная глубина больше, чем глубина, уже имеющаяся в Z-буфере, то занести в буфера атрибуты пиксела и его глубину, иначе никаких занесений не выполнять.

    · Выполнить, если это было предусмотрено, усреднение изображения с понижением разрешения.


    4 Построчный алгоритм с Z-буфером

    Рассмотрим теперь алгоритм с Z-буфером размером в одну строку, который представляет собой обобщение алгоритма построчной заливки многоугольника, представленный в процедурах V_FP0 и V_FP1 в приложениях. Модификация должна учесть то, что для каждой строки сканирования теперь может обрабатываться не один многоугольник.

    Общая схема такого алгоритма следующая:

  • Подготовка данных.
    Для каждого многоугольника определить максимальную Y-координату.
    Занести многоугольник в группу многоугольников, соответствующую данной Y-координате.
  • Собственно заливка.

  • 5 Алгоритм разбиения области Варнока

    Алгоритм работает в пространстве изображения и анализирует область на экране дисплея (окно) на наличие в них видимых элементов. Если в окне нет изображения, то оно просто закрашивается фоном. Если же в окне имеется элемент, то проверяется достаточно ли он прост для визуализации. Если объект сложный, то окно разбивается на более мелкие, для каждого из которых выполняется тест на отсутствие и/или простоту изображения. Рекурсивный процесс разбиения может продолжаться до тех пор пока не будет достигнут предел разрешения экрана.

    Можно выделить 4 случая взаимного расположения окна и многоугольника (рис. 0.6.49):
    · многоугольник целиком вне окна,
    · многоугольник целиком внутри окна,
    · многоугольник пересекает окно,
    · многоугольник охватывает окно.

    В четырех случаях можно сразу принять решение о правилах закраски области экрана:

    · все многоугольники сцены — внешние по отношению к окну. В этом случае окно закрашивается фоном;

    · имеется всего один внутренний или пересекающий многоугольник. В этом случае все окно закрашивается фоном и затем часть окна, соответствующая внутреннему или пересекающему окну закрашивается цветом многоугольника;

    · имеется единственный охватывающий многоугольник. В этом случае окно закрашивается его цветом.

    · имеется несколько различных многоугольников и хотя бы один из них охватывающий. Если при этом охватывающий многоугольник расположен ближе остальных к наблюдателю, то окно закрашивается его цветом.

    В любых других случаях процесс разбиения окна продолжается. Легко видеть, что при растре 1024×1024 и делении стороны окна пополам требуется не более 10 разбиений. Если достигнуто максимальное разбиение, но не обнаружено ни одного из приведенных выше четырех случаев, то для точки с центром в полученном минимальном окне (размером в пиксел) вычисляются глубины оставшихся многоугольников и закраску определяет многоугольник, наиболее близкий к наблюдателю. При этом для устранения лестничного эффекта можно выполнить дополнительные разбиения и закрасить пиксел с учетом всех многоугольников, видимых в минимальном окне.

    Первые три случая идентифицируются легко. Последний же случай фактически сводится к поиску охватывающего многоугольника, перекрывающего все остальные многоугольники, связанные с окном. Проверка на такой многоугольник может быть выполнена следующим образом: в угловых точках окна вычисляются Z-координаты для всех многоугольников, связанных с окном. Если все четыре такие Z-координаты охватывающего многоугольника ближе к наблюдателю, чем все остальные, то окно закрашивается цветом соответствующего охватывающего многоугольника. Если же нет, то мы имеем сложный случай и разбиение следует продолжить.

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

    Из изложенного ясно, что важной частью алгоритма является определение расположения многоугольника относительно окна.

    Проверка на то что многоугольник внешний или внутренний относительно окна для случая прямоугольных окон легко реализуется использованием прямоугольной оболочки многоугольника и сравнением координат. Для внутреннего многоугольника должны одновременно выполняться условия:

    Xmin і Wл и Xmax Ј Wп и Ymin і Wн и Ymax Ј Wв,
    здесь Xmin,Xmax,Ymin,Ymax ребра оболочки
    Wл, Wп, Wн, Wв ребра окна

    Для внешнего многоугольника достаточно выполнение любого из следующих условий:

    ограничена разрешающей способностью экрана

    На практике, сравнительный анализ алгоритма Коэна-Сазерленда и алгоритм Варнока (а также любых других алгоритмов удаления невидимых линий и поверхностей) крайне затруднителен. Так как в различных случаях при работе с различными моделями пространства будут эффективны различные алгоритмы. Даже при работе с одной и той же моделью в зависимости от точки расположения наблюдателя могут быть эффективны различные алгоритмы удаления невидимых линий и поверхностей.

    Список литературы

    1. Абрамова О.Ф., Котов В. В. К вопросу об импорте 3D моделей в программы с использованием графической библиотеки OpenGL [Электронный ресурс] / Котов В. В., Абрамова О.Ф. // Современная техника и технологии. — 2014. — № 1. — C. Режим доступа : http://technology.snauka.ru/2014/01/2965.
    2. Трифанов А.И., Абрамова О.Ф. Реализация собственного метода визуализации водной поверхности «скользящая текстура» / Трифанов А.И., Абрамова О.Ф. // Современные наукоёмкие технологии. — 2013. — № 8 (ч. 1). — C. 96-97.
    3. Абрамова О.Ф. Использование мультимедийных технологий в процессе обучения дисциплине «Компьютерная графика» / Абрамова О.Ф., Белова С.В. // Успехи современного естествознания. — 2012. — № 3. — C. 90.
    4. Абрамова О.Ф. К вопросу о повышении эффективности функционирования тренажёрно-обучающих систем / О.Ф. Абрамова, М.Л. Цыганкова // Открытое и дистанционное образование. — 2014. — № 4. — C. 34-39.
    5. cb.mediaedu.uz – Медиаобразовательный портал – [Электронный ресурс] – Режим доступа : http://cb.mediaedu.uz/cabinet.php?page=courses&urok=90
    6. technomag.edu.ru – Электронное издательство НАУКА и ОБРАЗОВАНИЕ – Издатель ФГБОУ ВПО «МГТУ им. Н.Э. Баумана». Эл № ФС 77 – 48211 — [Электронный ресурс] – Режим доступа : http://technomag.edu.ru/doc/49094.html
    7. Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М.: ДИАЛОГ-МИФИ, 2001.
    8. Шлыков А.А. Практическая реализация алгоритма поиска кратчайшего пути А* для трёхмерных моделей зданий / А.А. Шлыков, О.Ф. Абрамова // Современные наукоёмкие технологии. — 2014. — № 5 (ч. 2). — C. 17-18.
    9. Сиденко Л.А. Компьютерная графика и геометрическое моделирование: Учебное пособие. – СПб.: Питер, 2009. – 224 с.: ил. – (Серия «Учебное пособие»)

    Электронное периодическое издание зарегистрировано в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), свидетельство о регистрации СМИ — ЭЛ № ФС77-41429 от 23.07.2010 г.

    Соучредители СМИ: Долганов А.А., Майоров Е.В.

    Распознавание простых линий на изображении Текст научной статьи по специальности « Математика»

    Аннотация научной статьи по математике, автор научной работы — Запрягаев Сергей Александрович, Сорокин Андрей Игоревич

    In thearticle the primitive recognition and feature extraction methods are discussed. Application of integral transformation of image space into parameter space for lines and circle detection was presented. Inversion of the image coordinates was described along with its application for circle parameters estimation. Also method of algebraic curves of second order invariants analysis was used for estimation of circle, ellipse and hyperbola canonical parameters. Распознавание примитивов/ primitive recognition Интегральные преобразования/ integral transformation

    Похожие темы научных работ по математике , автор научной работы — Запрягаев Сергей Александрович, Сорокин Андрей Игоревич,

    In thearticle the primitive recognition and feature extraction methods are discussed. Application of integral transformation of image space into parameter space for lines and circle detection was presented. Inversion of the image coordinates was described along with its application for circle parameters estimation. Also method of algebraic curves of second order invariants analysis was used for estimation of circle, ellipse and hyperbola canonical parameters. Распознавание примитивов/ primitive recognition Интегральные преобразования/ integral transformation

    Текст научной работы на тему «Распознавание простых линий на изображении»

    С. А. Запрягаев, А. И. Сорокин

    Распознавание простых линий на изображении

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

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

    В общем случае объекты, подлежащие распознаванию, представляют собой сложные графические структуры с нечетко выраженными характеристиками, в целом не имеющие определенных специфических инвариантов или иных характеристик, которые могли бы служить ключевыми данными. Однако очень большое число сложных графических изображений можно разумными алгоритмами разложить на более простые графические объекты, которые в контексте данного сообщения будут называться примитивами. К ним относятся прямые линии, отрезки прямых линий, окружности, эллипсы, иные хорошо определенные простые линии. Учитывая дискретные особенности цифрового формирования изображения, ниже под примитивами понимаются не только строго определенные математические линии на плоскости (х,у), но и дискретный аналог этих объектов или цифровые объекты, в определенном смысле близкие перечисленным выше структурам.

    Так как реальное изображение может содержать многоцветные объекты, а формирую-

    щие их цифровые линии могут быть различной «толщины», задача распознавания может включать в себя подготовку изображения для сведения его к определенным нормированным условиям. В настоящей работе используется принцип сведения изображения к монохромной структуре с однопиксельным заданием линий, формирующих объект изображения. Алгоритмы, обеспечивающие такой тип [1], в данной работе не рассматриваются в силу самостоятельности этой задачи. Практическая цель работы состоит в формировании алгоритмов выделения значимых признаков примитивов и построении программного комплекса для численного моделирования процесса распознавания объектов различными методами.

    Проблема выделения и классификации значимых признаков изображения связана, в частности, и с нахождением формы объектов, содержащихся на изображении. Например, для автоматического распознавания лиц необходимо выделить глаза, рот, брови и т. д. Используя в этом случае начальное приближение глаз эллипсом, бровей — отрезками прямых, можно получить оценку аналитических параметров данных примитивов, что применяется при создании целевых баз данных. Кроме того, найденные параметры могут быть использованы как самостоятельные индикаторы характерных особенностей изображения, таки в качестве промежуточного элемента для выделения более сложных признаков.

    Обнаружение аналитических параметров таких примитивов, как прямая, окружность, эллипс, участок гиперболической кривой и т. п.

    подразумевает нахождение их положения и размера, а также инвариантных по отношению к операциям вращения и сдвига параметров (например, длины большой и малой полуосей эллипса и т. п.).

    В настоящей работе рассмотрены следующие методы обнаружения примитивов на изображении и нахождения их параметров:

    • интегрального преобразования пространства изображения в пространство параметров объекта (преобразование Радона [2,3,4]);

    • алгебраических кривых произвольного порядка.

    1. Преобразование Радона

    Преобразование Радона [1] — это хорошо известное интегральное преобразование, сопоставляющее функции f в исходном пространстве функцию на множестве плоскостей, задаваемую интегралами от f вдоль этих плоскостей. Преобразование Радона нашло широкое применение в сейсмологии, астрофизике, томографии, радиолокации и т. п. Известны многочисленные варианты интегральных преобразований, являющиеся модификациями или обобщениями данного подхода [3,5,6].

    Существует несколько тождественных определений преобразования Радона. Вот простейшее из них. Если в пространстве двух переменных задана функция /(х, у), то интегральное преобразование Радона вдоль прямой линии у = кх+ Ь имеет вид:

    ад (к ,Ь) = / /( х, кх+Ь)6х-

    / / /( х, у)6( у — кх-Ь)ёхёу.

    Здесь 8(х) — дельта-функция Дирака, а параметры линии Ь и к образуют пространство данного интегрального преобразования. Установлены многочисленные полезные свойства преобразования (1), связанные с преобразованиями сдвига, поворота, масштабирования переменных системы координат, а также связь преобразования Радона с преобразова-

    нием Фурье. Подробное исследование этих свойств и ряд их приложений в томографии приведено в [5].

    1.1. Обнаружение прямых на изображении

    Прежде всего, преобразование Радона используют для обнаружения прямых линий на изображении. Возможность такого применения связана с двойственностью пространства изображения, точки которого заданы координатами (х, у), и пространства параметров прямой (к, Ь), в соответствии с (1). Двойственность преобразования заключается в том, что каждой точке пространства изображения (хьу,) соответствует прямая Ь=-х1 к + у1 пространства параметров (к, Ь). Верно и обратное утверждение, что каждой прямой у=к0х+Ь0 пространства изображения (х, у) соответствует единственная точка пространства параметров (к, Ь)—(к0, Ь0).

    Для моделирования данного утверждения выберем в качестве математической модели «изображения» точки с координатами (х1,у1) на плоскости (х,у) сингулярную функцию вида:


    /( х, у)=6( х — х1 ж у — у 1 ).

    При этом условимся изображать значение модельной сингулярности в точке ^х;,уп) черной точкой на плоскости (х,у). В соответствии с (1) преобразование Радона для выбранной функции /(х,у) есть

    ад (к ,Ь)=6( у1 — кх1 -Ь).

    На основании принятой условности изображения сингулярности в пространстве параметров преобразования (к, Ь) совокупность сингулярных точек8(у1 — кх1 — Ь) образуют прямую линию Ь=-х1 к + у1. Таким образом, модельное изображение точки в плоскости (х, у) преобразуется в «модельное изображение» линии. Аналогично рассматриваем преобразование Радона для линии у=к0х+Ь0, заданной в пространстве. В соответствии с методом изображения сингулярности данную линию можно моделировать функцией /( х, у)=8( у — к0 х-Ь0). В результате, используя преобразование Радона (1), находим:

    ^[/1 (к ,Ь) = /б(( к — к 0) х+Ь — Ь0)ёх.

    i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

    Рис. 1. Преобразования Радона для точек, лежащих на прямой у=2х+3<к0 =2, Ь0 =3)

    Двойственность формул преобразования Радона для точки и прямой указывает на возможность создания практически эквивалентных алгоритмов поиска прямой на изображении. Варианты таких алгоритмов обсуждаются в [5] и [16].

    1.2. Алгоритм поиска прямых на изображении

    Для построения алгоритма поиска прямой на изображении рассмотрим элементарное изображение размером 5×7 пикселей, представленное на рис. 2. Пронумеруем черные точки изображения от 1 до 10. Каждой черной точке в пространстве параметров преобразования Радона (Ь, к) соответствует прямая, заданная уравнением Ь= -ук + х. Всего имеется N = 10 прямых в пространстве (Ь, к).

    1 2 3 4 5 X Точка Уравнение

    4 а 4 6 = —4Аг Ч- 5

    Рис. 2. Пространство точек исходного изображения и уравнения прямых двойственного пространства

    Найдем все точки пересечения данных прямых. Всего таких точек NN — 7): 2 = 45. Координаты точек пересечения /-й и>-й кривой в плоскости (Ь, к) при заданном выборе системы координат (х—у) определяются из выражений:

    Подсчитаем число одинаковых точек пересечения. В результате найдем шесть повторений точки пересечения (к = 1,Ь = 1), шесть повторений точки (к = -1,Ь = 9), три повторения точки (к = 0, Ь = 1). Остальные тридцать точек встретятся по одному разу. Шесть точек пересечения к = 1, Ь = 1 соответствуют прямой линии х = у + 1, проходящей через точки 1,2,3,4 на плоскости (х—у). Шесть точек пересечения к = -1, Ь = 9 соответствуют прямой линии х = -к + 9, проходящей через точки 4,5,6,7. Наконец, три повторения точки (к = 0,Ь = 7) соответствуют линии х = 7, проходящей через точки 8,9,10. Таким образом, точки с числом пересечений больше двух однозначно определяют три прямые линии на исходном изображении (вернее, их дискретные аналоги). Остальные точки пересечения соответствуют виртуальным прямым, на исходном изображении, т. е. таким прямым, которые могут быть проведены через две точки на плоскости (х—у), для которых определена точка пересечения изображений в результате преобразований Ра-

    дона, однако реально такая линия на исходном изображении отсутствует. Например, точка k = 0, b = 3 соответствует виртуальной прямой, которую можно провести через точки 2 и 6, однако на исходном изображении такой линии нет.

    В соответствии с представленным элементарным примером можно сформулировать общий алгоритм поиска прямых линий на изображении.

    Пусть W — ширина изображения в точках, H — его высота, тогда может быть записан в псевдокоде следующий алгоритм поиска прямых.

    Инициализировать список найденных точек на изображении:

    Инициализировать таблицу соответствия между точками пересечения двойственных прямых в пространстве параметров прямых и их числом:

    Par:= Map[Point, Count];

    For x := 0 to W — 1 do

    For y := 0 to H — 1 do

    if (точка (x, y) — «черная») then

    for (x0, y0) £ PointList do

    Найти точку пересечения прямых:

    Par[(b0,k0) end for; end if; end for; end for

    Параметры прямых (Ь0, к0), для которых значение счетчика Рагат [(Ь0, к0)] максимальны, принимаются за параметры обнаруженных на изображении прямых, среди которых могут быть параметры виртуальных пря-

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

    1.3. Преобразование Радона в нормальной форме

    Интегральное преобразование (1) имеетог-раничение, связанное с поиском прямых на изображении,угол наклона которых равен или близок 90o, т. е. прямых, параллельных или «почти» параллельных оси Oy. Данное обстоятельство связано с бесконечно большим значением параметра k. Для того чтобы избавиться отданной проблемы, можно определить более общее преобразование, которое имеет три параметра [3]:

    R[f](ki,k2,k3) = / /f(x,y)g(kiy + k2x + k3)dxdy.

    Очевидно, что задание трех параметров является излишним в случае прямой линии. Поэтому всегда можно установить какую-либо связь между этими параметрами, сведя параметризацию к двумерной. В литературе по использованию преобразований Радона наиболее употребительными являются два способа задания параметров преобразований. Первый способ описан в предыдущем разделе и означает следующий выбор параметров: k1 =1, k2 =—k,k3 =—b. Другой выбор параметров основан на задании линии в так называемой нормальной форме (рис. 3): ф = р — xcos9—ysin9=0.

    Рис. 3. Нормальная параметризация прямой

    В этом случае параметры преобразования Радона определяются следующим образом:

    k1 =—sin9, k2 =—cos 9, k3 =р.

    Преобразование Радона (1) принимает вид:

    R[f] (р, 9) = / / f( x, y)g( ф)dxdy.

    i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

    где ^=pcos9 — ssin9и r| = psin9+ scos9.

    Представленная форма преобразования Радона означает выполнение интегрирован ия по линии, проходящей через точку A (x=pcos 9, y =psin9), перпендикулярно линии OA, где О — начало координат.

    По аналогии с рассуждениями, приведенными выше, преобразование Радона в нормальной форме для точки (x0, y0), где x0 =p0 cos90, y0 =p0 sin90, задание изображения которой определяется сингулярной функцией вида f (x, y)=6( x — x 0 )8( y — y 0), соответствует отрезку синусоиды p0cos(9 — 90) — p=0 в пространстве параметров (p, 9). В свою очередь, преобразованию изображения прямой на плоскости (x,y), моделируемой функцией f (x, y)=6( x cos 9 0 + y sin 9 0 — p 0), соответствует точка p=p0 и 9=90 в пространстве параметров (p, 9).

    На рис. 4 представлено изображение двух точек, координаты которых на плоскости (x,y) равны (p0 =5,90 =тс/6) и и(p0 = 7,90 =тс/3). Данным точкам в пространстве параметров преобразования Радона (p, 9) соответствуют две синусоиды p, = 5cos(9 —тс/6) и p2 =7cos(9 —тс/3)

    р2 = 7соб(9—тс/3) (рис. 4). Точка пересечения данных синусоид определяется координатами

    50 тс —cos— 121 6

    или 9х « 0,2289. и, соответственно, рх = р, (9х) = = р2 (9х)

    4,784. Данным значениям координат точки пересечения синусоид в плоскости (х, у) соответствует прямая линия, проходящая через исходные точки изображения, уравнение которой есть

    или у «(4,291. )х + 21,081. Таким образом, точки, лежащие на одной прямой, имеют одну общую точку пересечения синусоид, соответствующих им в пространстве параметров (р,9).

    Имеется ясно выраженная специфика для точек, лежащих на прямой линии, проходящей через начало координат. Например, две точки (р0 =5,90 =тс/3) и (р0 =7,90 =тс/3) в пространстве параметров преобразования Радона (р,9) приводят к двум синусоидам р, = 5соб(9 —тс/3) и р2 =7соб(9—тс/3). Точки пересечения этих синусоид лежат на оси р=0, т. е. рх =0, 9х =—тс/6. В этом случае в пространстве (х,у) определяется прямая, проходящая через две точки, уравнение которой имеет вид: у=хС:д(тс/6). Аналогично, если две точки лежат на осих (р0 =5,90 =0) и (р0 = 5,90 = 0), точка пересечения соответствующих синусоид равна рх =0, 9х =тс/2.Уравнение прямой в плоскости (х,у) бу-

    Алгоpитм изобpажения линий

    Задача удаления невидимых линий и поверхностей является одной из наиболее интересных и сложных в компьютерной графике. Алгоритмы удаления заключаются в определении линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.

    Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована на рис. 6.1. Рисунок наглядно демонстрирует, что изображение без удаления невидимых линий воспринимается неоднозначно.

    Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Единого (общего) решения этой задачи, годного для различных случаев, естественно, не существует: для каждого случая выбирается наиболее подходящий метод. Например, для моделирования процессов в реальном времени требуются быстрые алгоритмы, в то время как для формирования сложного реалистического изображения, в котором представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках, фактор времени выполнения уже не так существенен. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.

    Все алгоритмы такого рода так или иначе включают в себя сортировку, причем главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения или картинной плоскости. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине остается провести сортировку по горизонтали и по вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения. Эффективность любого алгоритма удаления в значительной мере зависит от эффективности процесса сортировки.

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

    Мы приведем некоторые из алгоритмов, работающих как в объектном пространстве, так и в пространстве изображения, каждый из которых иллюстрирует одну или несколько основополагающих идей теории алгоритмов удаления невидимых линий и поверхностей.

    Удаление нелицевых граней многогранника

    Алгоритм Робертса

    Этот алгоритм, предложенный в 1963 г., является первой разработкой такого рода и предназначен для удаления невидимых линий при штриховом изображении объектов, составленных из выпуклых многогранников. Он относится к алгоритмам, работающим в объектном пространстве, и очень элегантен с математической точки зрения. В нем очень удачно сочетаются геометрические методы и методы линейного программирования .

    Выпуклый многогранник однозначно определяется набором плоскостей, образующих его грани, поэтому исходными данными для алгоритма являются многогранники, заданные списком своих граней. Грани задаются в виде плоскостей, заданных в канонической форме (см. лекцию 3) в объектной системе координат: .

    Таким образом, каждая плоскость определяется четырехмерным вектором , а каждая точка , заданная в однородных координатах, также представляет собой четырехмерный вектор:

    Принадлежность точки плоскости можно установить с помощью скалярного произведения, т.е. если , то точка принадлежит плоскости, если же нет, то знак произведения показывает, по какую сторону от плоскости эта точка находится. В алгоритме Робертса плоскости строятся таким образом, что внутренние точки многогранника лежат в положительной полуплоскости. Это означает, что вектор является внешней нормалью к многограннику (рис. 6.2). Из векторов плоскостей строится прямоугольная матрица порядка , которая называется обобщенной матрицей описания многогранника:

    Умножая столбцы матрицы на вектор , получим n -мерный вектор, и если все его компоненты неотрицательны, то точка принадлежит многограннику. Это условие будем записывать в виде (имеется в виду умножение вектор-строки на матрицу).

    В своем алгоритме Робертс рассматривает только отрезки, являющиеся пересечением граней многогранника.

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

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

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

    Если заданы концы отрезка и , а наблюдатель расположен в точке , то отрезок задается уравнением

    Для определения той части отрезка, которая закрывается каким-либо телом, достаточно найти значения и , при которых произведение вектора на обобщенную матрицу положительно. Для каждой плоскости записывается неравенство

    Полагая , получаем систему уравнений, решения которой дают нам точки «смены видимости» отрезка. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы. Число всевозможных решений при плоскостях равно .

    Так как объем вычислений растет с увеличением числа многоугольников, то желательно по мере возможности сокращать их число, т.е. если мы аппроксимируем некоторую поверхность многогранником, то в качестве граней можно использовать не треугольники, а более сложные многоугольники. При этом, разумеется, встает проблема, как построить такой многоугольник, чтобы он мало отклонялся от плоской фигуры.

    Алгоритм Варнока

    В отличие от алгоритма Робертса, Варнок в 1968 г. предложил алгоритм, работающий не в объектном пространстве, а в пространстве образа. Он также нацелен на изображение многогранников, а главная идея его основана на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. Так, например, рассматривая помещение, в котором имеется только картина на стене, мы быстро осматриваем стены, пол и потолок, а затем все внимание сосредоточиваем на картине. В свою очередь, на этой картине, если это портрет, мы бегло отмечаем фон, а затем более внимательно рассматриваем лицо изображенного персонажа, в особенности глаза, губы. Как правило, достаточно детально рассматриваются еще и руки и с чуть меньшим вниманием — одежда.

    В алгоритме Варнока и его вариантах делается попытка воспользоваться тем, что большие области изображения однородны. Такое свойство называют когерентностью, имея в виду, что смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности.

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

    Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма каждое окно разбивалось на четыре одинаковых подокна. Многоугольник, входящий в изображаемую сцену, по отношению к окну будем называть (рис. 6.3)


    • внешним, если он целиком находится вне окна;
    • внутренним, если он целиком расположен внутри окна;
    • пересекающим, если он пересекает границу окна;
    • охватывающим, если окно целиком расположено внутри него.

    Теперь можно в самом общем виде описать алгоритм.

    Для каждого окна:

    1. Если все многоугольники сцены являются внешними по отношению к окну, то оно пусто; изображается фоновым цветом и дальнейшему разбиению не подлежит.
    2. Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему внутренним, то окно заполняется фоновым цветом, а сам многоугольник заполняется своим цветом.
    3. Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему пересекающим, то окно заполняется фоновым цветом, а часть многоугольника, принадлежащая окну, заполняется цветом многоугольника.
    4. Если только один многоугольник охватывает окно и нет других многоугольников, имеющих общие точки с окном, то окно заполняется цветом этого многоугольника.
    5. Если существует хотя бы один многоугольник, охватывающий окно, то среди всех таких многоугольников выбирается тот, который расположен ближе всех многоугольников к точке наблюдения, и окно заполняется цветом этого многоугольника.
    6. В противном случае производится новое разбиение окна.

    Шаги 1–4 рассматривают ситуацию пересечения окна только с одним многоугольником. Они используются для сокращения числа подразбиений. Шаг 5 решает задачу удаления невидимых поверхностей. Многоугольник, находящийся ближе всех к точке наблюдения, экранирует все остальные.

    Для реализации алгоритма необходимы функции, определяющие взаимное расположение окна и многоугольника, которые достаточно легко реализуются в случае прямоугольных окон и выпуклых многоугольников. Для определения, является ли многоугольник охватывающим, внешним или внутренним, можно воспользоваться, например, погружением многоугольника в прямоугольную оболочку. Для определения наличия пересечений можно использовать опорные прямые (так же, как использовались плоскости в алгоритме Робертса). Если же многоугольник невыпуклый, то задача усложняется. Методы решения такого рода задач будут рассмотрены в главе, относящейся к геометрическому поиску.

    Следует заметить, что существуют различные реализации алгоритма Варнока. Были предложены варианты оптимизации, использующие предварительную сортировку многоугольников по глубине, т. е. по расстоянию от точки наблюдения, и другие.

    Алгоритм Вейлера-Азертона

    Вейлер и Азертон попытались оптимизировать алгоритм Варнока в отношении числа выполняемых разбиений, перейдя от прямоугольных разбиений к разбиениям вдоль границ многоугольников (1977). Для этого они использовали ими же разработанный алгоритм отсечения многоугольников. Алгоритм работает в объектном пространстве, и результатом его работы являются многоугольники. В самом общем виде он состоит из четырех шагов.

    1. Предварительная сортировка по глубине.
    2. Отсечение по границе ближайшего к точке наблюдения многоугольника, называемое сортировкой многоугольников на плоскости.
    3. Удаление многоугольников, экранируемых более близкими к точке наблюдения многоугольниками.
    4. Если требуется, то рекурсивное разбиение и новая сортировка.

    В процессе предварительной сортировки создается список приблизительных приоритетов, причем близость многоугольника к точке наблюдения определяется расстоянием до ближайшей к ней вершины. Затем выполняется отсечение по самому первому из многоугольников. Отсечению подвергаются все многоугольники из списка, причем эта операция выполняется над проекциями многоугольников на картинную плоскость. При этом создаются списки внешних и внутренних фигур. Все попавшие в список внешних не экранируются отсекающим многоугольником. Затем рассматривается список внутренних многоугольников и выполняется сортировка по расстоянию до отсекающего многоугольника. Если все вершины некоторого многоугольника оказываются дальше от наблюдателя, чем самая удаленная из вершин экранирующего, то они невидимы, и тогда они удаляются. После этого работа алгоритма продолжается с внешним списком.

    Если какая-то из вершин внутреннего многоугольника оказывается ближе к наблюдателю, чем ближайшая из вершин экранирующего многоугольника, то такой многоугольник является частично видимым. В этом случае предварительный список приоритетов некорректен, и тогда в качестве нового отсекающего многоугольника выбирается именно этот «нарушитель порядка». При этом используется именно исходный многоугольник, а не тот, что получился в результате первого отсечения. Такой подход позволяет минимизировать число разбиений.

    Этот алгоритм в дальнейшем был обобщен Кэтмулом (1974) для изображения гладких бикубических поверхностей. Его подход заключался в том, что разбиению подвергалась поверхность. Коротко этот алгоритм можно описать так:

    1. Рекурсивно разбивается поверхность до тех пор, пока проекция элемента на плоскость изображения не будет покрывать не больше одного пикселя.
    2. Определить атрибуты поверхности в этом пикселе и изобразить его.

    Эффективность такого метода, как и алгоритм Варнока, зависит от эффективности разбиений. В дальнейшем этот алгоритм был распространен на сплайновые поверхности.

    Метод Z-буфера

    Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом в 1975 г. Работает этот алгоритм в пространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов каждого пикселя в пространстве изображения, а Z-буфер предназначен для запоминания глубины (расстояния от картинной плоскости) каждого видимого пикселя в пространстве изображения. Поскольку достаточно распространенным является использование координатной плоскости в качестве картинной плоскости, то глубина равна координате точки, отсюда и название буфера. В процессе работы значение глубины каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка Z-буфера новым значением глубины. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по и наибольшего значения функции .

    Главное преимущество алгоритма — его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в Z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.

    Основной недостаток алгоритма — большой объем требуемой памяти. В последнее время в связи с быстрым ростом возможностей вычислительной техники этот недостаток становится менее лимитирующим. Но в то время, когда алгоритм еще только появился, приходилось изобретать способы создания буфера как можно большего объема при имеющемся ресурсе памяти.

    Например, можно разбивать пространство изображения на 4, 16 или больше прямоугольников или полос. В предельном варианте можно использовать буфер размером в одну строку развертки. Для последнего случая был разработан алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование Z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены.

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

    В целом алгоритм выглядит так:

    1. Заполнить буфер кадра фоновым значением цвета.
    2. Заполнить Z -буфер минимальным значением z (глубины) .
    3. Преобразовать изображаемые объекты в растровую форму в произвольном порядке.
    4. Для каждого объекта:

    4.1. Для каждого пикселя образа вычислить его глубину .

    4.2. Сравнить глубину со значением глубины, хранящимся в Z-буфере в этой же позиции.

    4.3. Если Z- \text<буфер>(x,y)» src=»http://www.intuit.ru/sites/default/files/tex_cache/3591abe1297615ca00ce591368f75229.png» style=»border:none;display:inline» />, то занести атрибуты пикселя в буфер кадра и заменить . В противном случае никаких действий не производить.

    Алгоритм, использующий Z-буфер, можно также применять для построения сечений поверхностей. Изменится только оператор сравнения:

    Методы приоритетов (художника, плавающего горизонта)

    Здесь мы рассмотрим группу методов, учитывающих специфику изображаемой сцены для удаления невидимых линий и поверхностей.

    При изображении сцен со сплошным закрашиванием поверхностей можно воспользоваться методом художника: элементы сцены изображаются в последовательности от наиболее удаленных от наблюдателя к более близким. При экранировании одних участков сцены другими невидимые участки просто закрашиваются. Если вычислительная трудоемкость получения изображения для отдельных элементов достаточно высока, то такой алгоритм будет не самым лучшим по эффективности, но зато мы избежим анализа (и вполне возможно, тоже дорогостоящего), позволяющего установить, какие же из элементов изображать не надо в силу их невидимости. Например, при изображении правильного многогранника мы довольно легко можем упорядочить его грани по глубине, но такая сортировка для произвольного многогранника возможна далеко не всегда. Мы рассмотрим применение этого метода на примере изображения поверхности, заданной в виде однозначной функции двух переменных.

    Пусть поверхность задана уравнением

    Тогда представляют собой набор «высот» для данной поверхности по отношению к плоскости . Поверхность будем аппроксимировать треугольниками с вершинами в точках так, что каждому прямоугольнику сетки узлов будут соответствовать два треугольника: и . Для построения наглядного изображения поверхности повернем ее на некоторый угол сначала относительно оси , а затем относительно оси , причем направление вращения выберем таким образом, что точки, соответствующие углам координатной сетки, расположатся в следующем порядке по удаленности от картинной плоскости: , т.е. точка окажется наиболее близкой к картинной плоскости (и наиболее удаленной от наблюдателя). Предполагается, что способ закрашивания треугольников уже определен. Тогда процесс изображения поверхности можно коротко записать так:

    При такой последовательности вывода изображения мы продвигаемся от самого удаленного треугольника к все более близким, частично закрашивая уже изображенные участки поверхности.

    Алгоритм художника можно применять для полностью закрашенной сцены, а для каркасного изображения, когда объект представляется в виде набора кривых или ломаных линий, он непригоден. Для этого случая предложен еще один метод, весьма эффективный — метод плавающего горизонта. Вернемся к предыдущему примеру изображения поверхности. Каркасное изображение получается путем изображения кривых, получаемых при пересечении этой поверхности плоскостями и (рис. 6.4).

    На самом деле мы будем рисовать четырехугольник и одну диагональ. В процессе рисования нам понадобятся два целочисленных массива: (нижний горизонт) и (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала мы инициализируем верхний горизонт нулем, а нижний — максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые «скрываются за горизонтом». По мере рисования нижний горизонт «опускается», а верхний «поднимается», постепенно оставляя все меньше незакрытого пространства. В отличие от метода художника, здесь мы продвигаемся от ближнего угла к дальнему. Теперь опишем алгоритм подробнее.

    Функция в этом фрагменте предназначена для вывода на экран отрезка прямой, причем в момент инициализации очередного пикселя она выполняет следующие действия:

    Алгоритмы построчного сканирования для криволинейных поверхностей

    Идея построчного сканирования, предложенная в 1967 г. Уайли, Ромни, Эвансом и Эрдалом, заключалась в том, что сцена обрабатывается в порядке прохождения сканирующей прямой. В объектном пространстве это соответствует проведению секущей плоскости, перпендикулярной пространству изображения. Строго говоря, алгоритм работает именно в пространстве изображения, отыскивая точки пересечения сканирующей прямой с ребрами многоугольников, составляющих картину (для случая изображения многогранников). Но при пересечении очередного элемента рисунка выполняется анализ глубины полученной точки и сравнение ее с глубиной других точек на сканирующей плоскости. В некоторых случаях можно построить список ребер , упорядоченный по глубине, но зачастую это невозможно выполнить корректно. Поэтому сканирование сочетают с другими методами.

    Один из таких методов мы уже рассматривали — метод Z–буфера, в котором буфер инициализируется заново для каждой сканирующей строки. Другой метод называют интервальным алгоритмом построчного сканирования. В нем сканирующая строка разбивается проекциями точек пересечения ребер многоугольников на интервалы, затем в каждом из интервалов выбираются видимые отрезки. В этой ситуации их уже можно отсортировать по глубине. Мы остановимся чуть подробнее на методе построчного сканирования для криволинейных поверхностей.

    В описании метода приоритетов поверхность задавалась в виде функции двух переменных, здесь мы будем задавать поверхность параметрическими уравнениями:

    Пересечение сканирующей плоскости с поверхностью дает нам так называемую линию уровня, или изолинию. Эта кривая может быть неодносвязной, т. е. состоять из нескольких отдельных кривых. Чтобы получить эту кривую, мы должны решить уравнение

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

    Метод двоичного разбиения пространства

    Теперь разберем один способ использования метода художника при изображении пространственных сцен, содержащих несколько объектов или составные объекты . Это так называемый метод двоичного разбиения пространства плоскостями. Плоскости, как обычно, будут задаваться с помощью вектора нормали и расстояния до начала координат (с точностью до знака). Пусть изображаемая сцена состоит из набора непересекающихся граней (они могут иметь общие прямолинейные участки границы). Проведем плоскость , разбивающую все пространство на два полупространства, в одном из которых находится наблюдатель. Предположим, что плоскость при этом не пересекает ни одну из граней (но может содержать участок ее границы). Тогда грани, находящиеся в одном полупространстве с наблюдателем, могут заслонять от него часть граней из второго полупространства, но не наоборот. Это означает, что они должны изображаться позже. Разобьем плоскостью второе полупространство и снова определим, какая группа граней из него должна изображаться раньше. Продолжая этот процесс до того уровня, когда все пространство будет разбито плоскостями на секции, в каждой из которых будет находиться только одна грань, мы получим упорядоченный набор граней. Этот порядок можно изобразить в виде двоичного дерева. В контексте рассматриваемого алгоритма это дерево представляет собой структуру данных , элементами которой являются указатель на грань изображаемой сцены, плоскость, отделяющая эту грань, указатели на левое и правое поддерево и . Такой элемент называется узлом дерева.

    В каждом узле дерева левое поддерево будет содержать грани, отделенные плоскостью, а правое — не отделенные. Рисование сцены осуществляется с помощью рекурсивного алгоритма следующего вида:

    Построение плоскостей и дерева в данном случае осуществляется «вручную». Для эффективности работы алгоритма надо стремиться к тому, чтобы дерево было сбалансированным. Если какие-то грани не удается отделить, то их пересекают плоскостями и рисуют как два объекта. Способ определения, по какую сторону плоскости находится наблюдатель, а по какую — грань, очень прост. Параметр плоскости для каждой грани будем задавать так, чтобы грань находилась в положительной полуплоскости. Тогда если при подстановке координат наблюдателя в это уравнение получаем положительное значение, то он находится в одной полуплоскости с гранью, если нет, то в разных.

    Алгоритм может применяться не только к многогранникам, но и вообще к любой сцене при условии, что имеется алгоритм изображения составляющих ее объектов. На рис. 6.6 изображена проекция сцены, разбитой вертикальными плоскостями, и соответствующее ей дерево. Положение наблюдателя отмечено кружком с буквой Н. При этой точке зрения объекты будут изображаться в последовательности 5, 6, 1, 2, 3, 4.

    Метод трассировки лучей

    Главная идея этого алгоритма была предложена в 1968 г. А.Аппелем, а первая реализация была выполнена в 1971 г.

    Наблюдатель видит любой объект посредством испускаемого неким источником света, который падает на этот объект, отражается или преломляется согласно законам оптики и затем каким-то путем доходит до глаза наблюдателя. Из огромного множества лучей света, выпущенных источником, лишь небольшая часть дойдет до наблюдателя. Следовательно, отслеживать пути лучей в таком порядке неэффективно с точки зрения вычислений. Аппель предложил отслеживать (трассировать) лучи в обратном направлении, т.е. от наблюдателя к объекту. В первой реализации этого метода трассировка прекращалась, как только луч пересекал поверхность видимого непрозрачного объекта; т.е. луч использовался только для обработки скрытых или видимых поверхностей. Впоследствии были реализованы алгоритмы трассировки лучей с использованием более полных моделей освещения с учетом эффектов отражения одного объекта от поверхности другого, преломления, прозрачности и затенения.

    В этом алгоритме предполагается, что сцена уже преобразована в пространство изображения. Если используется ортографическая проекция, то точка зрения или наблюдатель находится в бесконечности на положительной полуоси . В этом случае все световые лучи, идущие от наблюдателя, параллельны оси (рис. 6.7). Каждый луч проходит через пиксель растра до сцены. Траектория каждого луча отслеживается, чтобы определить, какие именно объекты сцены, если таковые существуют, пересекаются с данным лучом. Необходимо проверить пересечение каждого объекта сцены с каждым лучом. Если луч пересекает объект, то определяются все возможные точки пересечения луча и объекта. Можно получить большое количество пересечений, если рассматривать много объектов. Эти пересечения упорядочиваются по глубине. Пересечение с максимальным значением представляет видимую поверхность для данного пикселя. Атрибуты этого объекта используются для определения характеристик пикселя.

    Если точка зрения находится не в бесконечности (перспективная проекция), алгоритм трассировки лучей лишь незначительно усложняется. Здесь предполагается, что наблюдатель по-прежнему находится на положительной полуоси . Картинная плоскость, т.е. растр, перпендикулярна оси , как показано на рис. 6.8.

    Наиболее важным и трудоемким элементом этого алгоритма является процедура определения пересечений, поскольку эта задача отнимает наибольшую часть времени всей работы алгоритма. Поэтому эффективность методов поиска особенно важна. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или тел, ограниченных замкнутыми параметрическими поверхностями. Для ускорения поиска важно иметь эффективные критерии, позволяющие исключить из процесса заведомо лишние объекты.

    Одним из способов сокращения числа пересекаемых объектов является погружение объектов в выпуклую оболочку — сферическую или в форме параллелепипеда. Поиск пересечения с такой оболочкой очень прост, и если луч не пересекает оболочки, то не нужно больше искать пересечений этого объекта с лучом.

    Особенно просто выполняется тест на пересечение со сферической оболочкой (в лекции 3 были рассмотрены задачи о пересечении луча со сферой и плоскостью). Несколько большего объема вычислений требует задача о пересечении с прямоугольным параллелепипедом, поскольку необходимо проверить пересечение луча по меньшей мере с тремя бесконечными плоскостями, ограничивающими прямоугольную оболочку. Поскольку точки пересечения могут оказаться вне граней этого параллелепипеда, для каждой из них следует, кроме того, произвести проверку на попадание внутрь. Следовательно, для трех измерений тест с прямоугольной оболочкой оказывается более медленным, чем тест со сферической оболочкой.

    После выполнения этих первичных тестов начинается процесс поиска пересечений с объектами, попавшими в список потенциально видимых. При этом задача формирования изображения не исчерпывается нахождением самой точки пересечения: если мы учитываем эффекты отражения и преломления, необходимо отслеживать дальнейший путь луча, для чего, как правило, требуется восстановить нормаль к поверхности, а также определить направление отраженного или преломленного луча. В связи со всеми этими задачами важно выбрать достаточно удобные аппроксимации поверхностей, составляющих сцену. Определение атрибутов пикселя, выводимого в конечном итоге на экран, зависит от выбора модели освещения, о чем более подробно будет рассказано в последующих лекциях.

    Алгоритм трассировки лучей для простых непрозрачных поверхностей можно представить следующим образом.

    Создать список объектов, содержащий:

    • полное описание объекта: тип, поверхность, характеристики, тип оболочки и т.п.;
    • описание оболочки: центр и радиус для сферы или шесть значений для параллелепипеда .

    Для каждого трассируемого луча:

    Выполнить для каждого объекта трехмерный тест на пересечение с оболочкой. Если луч пересекает эту оболочку, то занести объект в список активных объектов.

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

    • Найти пересечения со всеми активными объектами.
    • Если список пересечений пуст, то изобразить данный пиксель с фоновым значением цвета.
    • В противном случае в списке пресечений найти ближайшее к наблюдателю (с максимальным значением ) и определить атрибуты точки.
    • Изобразить данный пиксель, используя найденные атрибуты пересеченного объекта и соответствующую модель освещенности.

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

    Алгоритм изображения для получения вертикальных или горизонтальных линий

    Я действительно ценю все ваши усилия, но, к сожалению, они не отвечают на вопрос. Я изложил подход bruteForce выше, и мой вопрос заключается в том, как я могу оптимизировать его. Вот резюме моего грубого подхода:

    Я хочу получить как можно меньше вертикальных и горизонтальных линий на изображении. Моя идея состояла в том, чтобы получить самую длинную линию (вертикальную или горизонтальную), а затем вторую самую длинную и так далее, что (я думаю) решает эту проблему.

    Эти изображения будут выглядеть аналогично 8-битным изображениям, но в более крупном и более детальном виде: Mario 8Bit

    До сих пор я придумал итерацию всего изображения, выделение самой длинной строки, ее сохранение и повторение изображения, но избегая посещения строки, которая уже была посещена. Если больше нет строк, которые нужно посетить, он остановится.

    Поскольку это брутфорс, это занимает больше времени, чем мне нужно. И я ищу способы оптимизировать это с точки зрения всего подхода, а не только крошечных оптимизаций внутри кода.

    Вот пример псевдокода для нахождения всей горизонтали:

    Вы получаете вертикальные линии таким же образом, переключая u и v.

    Из описания кажется, что вы ищете линии, которые состоят из пикселей, которые имеют точно такой же цвет, и которые являются абсолютно горизонтальными или вертикальными.

    Я создал пример, который генерирует кучу случайных красных линий на изображении:

    Синяя подсветка указывает на найденные линии, а зеленая подсветка показывает самую длинную найденную строку.

    Линии обнаруживаются с помощью простого подхода:

      Пройдите по всем пикселям (x, y), пока не будет найден пиксель с цветом линии

    Проверьте соседство пикселей. То есть проверьте, имеют ли пиксели «север», «юг», «восток» и «запад» текущего пикселя тот же цвет, что и текущий

    Если текущий пиксель красный, а к западу от него — белый, а к востоку от него — красный, то в этой точке начинается горизонтальная линия. Это в основном выглядит для этого шаблона:

    Если текущий пиксель красный, к северу от него — белый, а к югу от него — красный, то в этой точке начинается вертикальная линия. Это в основном выглядит для этого шаблона:

    Когда такое начало строки обнаружено, идите горизонтально или вертикально, пока не будет найден конец строки, и сохраните полученную строку

  • Наконец, сортируйте строки по длине
  • Обратите внимание, что здесь есть некоторые предположения и угловые случаи. Несмотря на то, что он находит разумные результаты, все становится сложнее, когда две линии расположены рядом друг с другом. Проще говоря: когда у вас есть образец красных пикселей, как это.

    тогда, строго говоря, невозможно сказать, являются ли они

    • три горизонтальные линии длиной 3
    • три вертикальные линии длиной 3
    • три горизонтальные линии длиной 2 и одна вертикальная линия длиной 3
    • или что угодно.

    Тем не менее, предлагаемый подход показан в этом MCVE:

    Попиксельная отрисовка линии

    Здравствуйте.
    Интересует такой вопрос.
    Требуется найти все пиксели, принадлежащие линии, зная ее начало и конец(точки начала и конца).
    Не могу никак додуматься или найти алгоритм. Может кто знает?

    То есть финальная стадия отрисовать линию по этим точкам, но это уже другая история.
    А вот формулу вывести не могу никак

    Xmin > Xп, Xmax Wв, Ymax

    Таким способом внешний многоугольник, охватывающий угол окна не будет идентифицирован как внешний (см. рис. 0.6.50).

    Проверка на пересечение окна многоугольником может быть выполнена проверкой на расположение всех вершин окна по одну сторону от прямой, на которой расположено ребро многоугольника. Пусть ребро многоугольника задано точками P1(x1,y1,z1) и P2(x2,y2,z2), а очередная вершина окна задается точкой P3(x3,y3,z3). Векторное произведение вектора P1P3 на вектор P1P2, равное (x3-x1)(y2-y1) — (y3-y1)(x2-x1) будет меньше 0, равно 0 или больше 0, если вершина лежит слева, на или справа от прямой P1P2. Если знаки различны, то окно и многоугольник пересекаются. Если же все знаки одинаковы, то окно лежит по одну сторону от ребра, т.е. многоугольник может быть либо внешним, либо охватывающим.

    Вернемся к примеру 0.6.50. Такой многоугольник рассмотренными тестами не был идентифицирован ни как внутренний ни как пересекающий. Т.е. он может быть либо внешним, либо охватывающим. Для завершающей классификации может использоваться тест с подсчетом угла, рассматривавшийся ранее для определения нахождения точки внутри/вне многоугольника. В этом тесте вычисляется суммарный угол, на который повернется луч, исходящий из некоторой точки окна (обычно центра), при последовательном обходе вершин многоугольника.

    Если суммарный угол равен 0, то многоугольник — внешний. Если же угол равен N×360 ° , то многоугольник охватывает окно N раз. Простейшая иллюстрация этого теста приведена на рис. 0.6.51.


    *Простая реализация алгоритма Варнока.

    * — эта реализация взята из другого места, но, вроде бы, все верно ];-).

    Предполагается, что экран у дисплея квадратный.
    если в окне что-то есть, то алгоритм разобьет это окно.
    окно разбивается на четыре одинаковых подокна.
    каждый многоугольник сравнивается с каждым окном.
    предполагается, что все значения заданы в системе координат экрана (пространстве изображения).
    предполагается, что устранение нелицевых граней проведено до начала работы алгоритма.
    Вершина — массив размером m х 3, в котором запоминаются координаты вершин всех многоугольников.
    m — общее число вершин многоугольников в сцене. Предполагается, что эти вершины перечислены в порядке их обхода по часовой стрелке.
    N — число многоугольников в сцене.
    информация об отдельных многоугольниках запоминается в массиве.
    Многоугольник размером N х 11

    Многоугольник ( ,1) — указатель на первую вершину многоугольника в массиве Вершина

    Многоугольник ( ,2) — число вершин многоугольника

    Многоугольник ( ,3) — интенсивность света или цвет многоугольника

    Многоугольник ( ,4-7) — коэффициенты a, b, c, d уравнения плоскости, несущей многоугольник

    Многоугольник ( ,8-11) — габариты Xmin, Xmax, Ymin, Ymax прямоугольной объемлющей оболочки многоугольника

    Push — функция, заносящая окна в стек

    Pop — функция, извлекающая окна из стека

    Wmax — максимальные габариты окна по х и у. Предполагается, что начало координат экрана находится в точке (0, 0)

    Окно — массив размером 1×3, который содержит начало координат окна и его размер в форме (Хнач, Унач, Размер)

    Внешность — флаг = 0 для пустого окна, >=1 для непустого окна


    6 Построчный алгоритм Уоткинса

    В алгоритмах построчного сканирования результирующее изображение генерируется построчно причем, подобно ранее рассмотренному алгоритму построчной заливки многоугольника, используется связность соседних растровых строк изображения. Отличие состоит в том, что учитываются все, а не один многоугольник.

    Алгоритм работает в пространстве изображения с окном высотой в одну строку и шириной в экран, тем самым трехмерная задача сводится к двумерной.

    Последовательность шагов алгоритма:
    · построение списка ребер,
    · построение списка многоугольников,


    · построение списка активных ребер — создается таблица ребер, включающая все негоризонтальные ребра многоугольников, причем элементы таблицы по значению Y-координаты отсортированы по группам.


    7 Алгоритм трассировки лучей

    При рассмотрении этого алгоритма предполагается, что наблюдатель находится на положительной полуоси Z, а экран дисплея перпендикулярен оси Z и располагается между объектом и наблюдателем.

    Удаление невидимых (скрытых) поверхностей в алгоритме трассировки лучей выполняется следующим образом:
    · сцена преобразуется в пространство изображения,

    · из точки наблюдения в каждый пиксел экрана проводится луч и определяется какие именно объекты сцены пересекаются с лучом,

    · вычисляются и упорядочиваются по Z координаты точек пересечения объектов с лучом. В простейшем случае для непрозрачных поверхностей без отражений и преломлений видимой точкой будет точка с максимальным значением Z-координаты. Для более сложных случаев требуется сортировка точек пересечения вдоль луча.

    Ясно, что наиболее важная часть алгоритма — процедура определения пересечения, которая в принципе выполняется Rx×Ry×N раз (здесь Rx,Ry — разрешение дисплея по X и Y, соответственно, а N — количество многоугольников в сцене).

    Очевидно, что повышение эффективности может достигаться сокращением времени вычисления пересечений и избавлением от ненужных вычислений. Последнее обеспечивается использованием геометрически простой оболочки, объемлющей объект — если луч не пересекает оболочку, то не нужно вычислять пересечения с ним многоугольников, составляющих исследуемый объект.

    При использовании прямоугольной оболочки определяется преобразование, совмещающее луч с осью Z. Оболочка подвергается этому преобразованию, а затем попарно сравниваются знаки Xmin с Xmax и Ymin с Ymax. Если они различны, то есть пересечение луча с оболочкой (см. рис. 0.6.52)

    При использовании сферической оболочки для определения пересечения луча со сферой достаточно сосчитать расстояние от луча до центра сферы. Если оно больше радиуса, то пересечения нет. Параметрическое уравнение луча, проходящего через две точки P1(x1,y1,z1) и P2(x2,y2,z2), имеет вид:

    P(t) = P1 + (P2 — P1)×t

    Минимальное расстояние от точки центра сферы P0(x0,y0,z0) до луча равно:

    d 2 = (x-x0) 2 + (y-y0) 2 + (z-z0) 2

    Этому соответствует значение t:

    t = — (x2-x1)·(x1-x0) + (y2-y1)·(y1-y0) + (z2-z1)·(z1-z0) (x2-x1) 2 + (y2-y1) 2 + (z2-z1) 2 .

    Если d2 > R2, то луч не пересекает объекты, заключенные в оболочку.

    Дальнейшее сокращение расчетов пересечений основывается на использовании групп пространственно связанных объектов. Каждая такая группа окружается общей оболочкой. Получается иерархическая последовательность оболочек, вложенная в общую оболочку для всей сцены. Если луч не пересекает какую-либо оболочку, то из рассмотрения исключаются все оболочки, вложенные в нее и, следовательно, объекты. Если же луч пересекает некоторую оболочку, то рекурсивно анализируются все оболочки вложенные в нее.

    Наряду с вложенными оболочками для сокращения расчетов пересечений используется отложенное вычисление пересечений с объектами. Если обнаруживается, что объект пересекается лучом, то он заносится в специальный список пересеченных. После завершения обработки всех объектов сцены объекты, попавшие в список пересеченных упорядочиваются по глубине. Заведомо невидимые отбрасываются а для оставшихся выполняется расчет пересечений и отображается точка пересечения наиболее близкая к наблюдателю.

    Дополнительное сокращение объема вычислений может достигаться отбрасыванием нелицевых граней, учетов связности строк растрового разложения и т.д.

    Для сокращения времени вычислений собственно пересечений предложено достаточно много алгоритмов, упрощающих вычисления для определенной формы задания поверхностей.

    Правила выполнения изображения схем алгоритмов

    (ГОСТ 19.701-90) (ИСО 5807-85).

    Алгоритм — конечная последовательность точно определенных действий, приводящих к однозначному решению поставленной задачи.

    Алгоритм должен обладать такими свойствами как:

    Алгоритмы могут быть заданы:

    — словесно, с помощью слов и предложений естественного языка;

    — таблично, в форме таблиц и расчетных формул;

    — графически, с помощью специальных символов — блоков.

    Описание алгоритмов с помощью блок-схем — наиболее наглядный и распространенный способ задания алгоритмов.

    Условные обозначения и правила выполнения изображения схем алгоритмов изложены в ГОСТ 19.701-90 (ИСО 5807-85).

    Стандарт не распространяется на форму записей и обозначений, помещаемых внутри символов или рядом с ними и служащих для уточнения выполняемых ими функций.

    Требования стандарта являются обязательными. Схемы алгоритмов состоят из имеющих заданное значение символов, краткого пояснительного текста и соединяющих линий. Схемы могут использоваться на различных уровнях детализации, причем число уровней зависит от размеров и сложности задачи обработки данных. Уровень детализации должен быть таким, чтобы различные части и взаимосвязь между ними были понятны в целом.

    В стандарте используются следующие понятия:

    1) основной символ — символ, используемый в тех случаях, когда точный тип (вид) процесса или носителя данных неизвестен или отсутствует необходимость в описании фактического носителя данных;

    2) специфический символ — символ, используемый в тех случаях,

    когда известен точный тип процесса или носителя данных или когда необходимо описать фактический носитель данных;

    3) схема — графическое представление определения, анализа или метода решения задачи, в котором используются символы для отображения операций, данных, потока, оборудования и т. д.

    1. Символы данных
    1.1. Основные символы данных
    1.1.1. Данные. Символ отображает данные, носитель данных не определен.
    1.1.2. Запоминаемые данные. Символ отображает хранимые данные в виде, пригодном для обработки, носитель данных не определен.
    1.2. Специфические символы данных
    1.2.1. Оперативное запоминающее устройство. Символ отображает данные, хранящиеся в оперативном запоминающем устройстве.
    1.2.2. Запоминающее устройство с последовательным доступом. Символ отображает данные, хранящиеся в запоминающем устройстве с последовательным доступом (магнитная лента, кассета с магнитной лентой, магнитофонная кассета).
    1.2.3. Запоминающее устройство с прямым доступом. Символ отображает данные, хранящиеся в запоминающем устройстве с прямым доступом (магнитный диск, магнитный барабан, гибкий магнитный диск).
    1.2.4. Документ. Символ отображает данные, представленные на носителе в удобочитаемой форме (машинограмма, документ для оптического или магнитного считывания, микрофильм, рулон ленты с итоговыми данными, бланки ввода данных).
    1.2.5. Ручной ввод. Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, полоски со штриховым кодом).
    1.2.6. Карта. Символ отображает данные, представленные на носителе в виде карты (перфокарты, магнитные карты, карты со считываемыми метками, карты со сканируемыми метками).
    1.2.7. Бумажная лента. Символ отображает данные, представленные на носителе в виде бумажной ленты.
    1.2.8. Дисплей. Символ отображает данные, представленные в человекочитаемой форме на носителе в виде отображающего устройства (экран для визуального наблюдения, индикаторы ввода информации).
    2. Символы процесса
    2.1. Основные символы процесса
    2.1.1. Процесс. Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться).
    2.2. Специфические символы процесса
    2.2.1. Предопределенный процесс. Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте ( в подпрограмме, модуле).
    2.2.2. Ручная операция. Символ отображает любой процесс, выполняемый человеком.
    2.2.3. Подготовка. Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последовательную функцию (установка переключателя, модификация индексного регистра или инициализация программы).
    2.2.4. Решение. Символ отображает решение или функцию переключаемого типа, имеющую один вход и ряд альтернативных выходов, один из которых может быть активизирован после вычисления условий, определенных внутри этого символа.
    2.2.5. Параллельные действия. Символ отображает синхронизацию двух или более параллельных операций.
    2.2.6. Граница цикла. Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или конце в зависимости от расположения операции, проверяющей условие.
    3. Символы линий
    3.1. Основной символ линий
    3.1.1. Линия. Символ отображает поток данных или управления.
    3.2. Специфические символы линий
    3.2.1. Передача управления. Символ отображает непосредственную передачу управления от одного процесса к другому, иногда с возможностью прямого возвращения к инициирующему процессу после того, как инициированный процесс завершит свои функции. Тип передачи управления должен быть назван внутри символа (например, запрос, вызов, событие).
    3.2.2. Канал связи. Символ отображает передачу данных по каналу связи.
    3.2.3. Пунктирная линия. Символ отображает альтернативную связь между двумя или более символами. Кроме того, символ используют для обведения аннотированного участка.
    4. Специальные символы
    4.1. Соединитель. Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линий и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение.
    4.2. Терминатор. Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных).
    4.3. Комментарий. Символ используют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний.
    4.4. Пропуск. Символ (три точки) используют схемах для отображения пропуска символа или группы символов, в которых не определены ни тип, ни число символов. Символ используют только в символах линий или между ними. Он применим равным образом в схемах, изображающих общие решения с неизвестным числом повторений.

    Правила применения символов:

    1) Символ предназначен для графической идентификации функции, которую он отображает, независимо от текста внутри этого символа.

    2) Символы в схеме должны быть расположены равномерно. Следует придерживаться разумной длины соединений и минимального числа длинных линий.

    3) Формы символов, установленные настоящим стандартом, должны служить руководством для фактически используемых символов. Не должны изменяться углы и другие параметры, влияющие на соответствующую форму символов. Символы должны быть, по возможности, одного размера.

    4) Символы могут быть вычерчены в любой ориентации, но, по возможности, предпочтительной является горизонтальная ориентация.

    5) Минимальное количество текста, необходимо для понимания

    функции данного символа, следует помещать внутри данного символа. Текст для чтения должен записываться слева направо и сверху вниз независимо от направления потока.

    6) Если объем текста, помещаемого внутрь символа, превышает его размеры, следует использовать символ комментария.

    7) В схемах может использоваться идентификатор символов. Это связанный с данным символом идентификатор, который определяет символ для использования в справочных целях в других элементах документации (например, в листинге программы). Идентификатор символа должен располагаться слева над символом.

    8) В качестве первого и последнего символа алгоритма должен быть использован символ указателя конца.

    Правила выполнения соединений:

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

    2) В схемах следует избегать пересечение линий. Пересекающиеся линии не имеют логической связи между собой, поэтому изменения направления в точках пересечения не допускаются.

    3) Две или более входящие линии могут объединяться одну исходящую линию. Если две или более линий объединяются в одну линию, место объединения должно быть смещено.

    4) Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.

    5) При необходимости линии в схемах следует разрывать для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц. Соединитель в начале разрыва называется внешним соединителем, а соединитель в конце разрыва — внутренним соединителем.

    6) Ссылки к страницам могут быть приведены совместно с символом комментария для их соединителей.

    Символ Наименование символа
    Символы данных
    Основные Данные + + + + +
    Запоминаемые данные + + + +
    Специфические ОЗУ + + + +
    ЗУ с послед. выборкой + + + +
    ЗУ с прямым доступом + + + +
    Документ + + + +
    Ручной ввод + + + +
    Карта + + + +
    Бумажная лента + + + +
    Дисплей + + + +
    Символы процесса
    Основные Процесс + + + + +
    Специфические Предопределенный процесс + + +
    Ручная операция + + +
    Подготовка + + + +
    Решение + +
    Параллельные действия + + +
    Граница цикла + +
    Символы линий
    Основные Линия + + + + +
    Специфические Передача управления +
    Канал связи + + + +
    Пунктирная линия + + + + +
    Специальные символы Соединитель + + + + +
    Терминатор + + +
    Комментарий + + + + +
    Пропуск + + + + +

    Примечание. Знак «+» указывает, что символ используют в данной схеме, знак «-» — не используют.

    1 — Схема данных;

    2 — Схема программы;

    3 — Схема работа системы;

    4 — Схема взаимодействия программ;

    5 — Схема ресурсов системы;

    ОЗУ — оперативное запоминающее устройство;

    ЗУ — запоминающее устройство.

    Примеры построения алгоритмов

    Алгоритмы бывают: линейные, разветвляющиеся, циклические. Линейный алгоритм не содержит логических условий, имеет одну ветвь обработки и изображается линейной последовательностью связанных друг с другом блоков. Разветвляющийся алгоритм содержит одно или несколько логических условий и имеет несколько ветвей обработки. Разветвляющиеся алгоритмы могут иметь несколько структур:

    — неполная альтернатива, обработка производится при выполнении условия в противном случае обработка не производится;

    — полная альтернатива, обработка производится при выполнении условия по ветви 1, в противном случае по ветви 2;

    — конструкция выбора, обработка производится при выполнении одного из нескольких различных условий по соответствующей ему ветви.

    Блок — Решение имеет один вход и несколько выходов, которые следует показывать:

    1) несколькими линиями от данного символа к другим символам;

    2) одной линией от данного символа, которая затем разветвляется в соответствующее число линий.

    3) каждый выход из символа должен сопровождаться соответствующими значениями условий, чтобы показать логический путь, который он представляет, с тем, чтобы эти соответствующие ссылки были идентифицированы.

    Линейная структура алгоритма

    Разветвляющиеся структуры алгоритмов

    а) неполная альтернатива


    Если условие выполняется выполнить обработку информации по ветви 1.

    б) полная альтернатива

    Если условие выполняется выполнить обработку информации по ветви 1, иначе по ветви 2.

    в) конструкция выбора

    Если выполняется условие 1, то выполняется обработка по ветви 1, если выполняется условие 2, то выполняется обработка по ветви 2, если выполняется условие 3, то выполняется обработка по ветви 3, иначе выполняется обработка по ветви 4.

    Последнее изменение этой страницы: 2020-04-19; Нарушение авторского права страницы

    Способы изображения алгоритма

    Читайте также:

    1. I.Этап.Разработка алгоритма и программы.
    2. II. Окончательные способы остановки кровотечений.
    3. IV. Способы построения графиков.
    4. XII. Способы передачи инновационных технологий
    5. Административный и судебный способы защиты экологических прав граждан. Процедуры защиты
    6. Аморфные металлические материалы (способы получения и области применения)
    7. Анализ алгоритма
    8. Анализ алгоритма Гаусса и его модификации
    9. Аналитические реакции и способы их выполнения
    10. Аподактильные (безпальцевые) способы
    11. Астигматизм и кривизна поверхности изображения.
    12. Б. Способы факторного анализа

    Алгоритмическая форма представления моделей

    ТЕМА: АЛГОРИТМИЗАЦИЯ ТЕХНОЛОГИЧЕСКИХ ЗАДАЧ

    ЛЕКЦИЯ № 17

    1. Формы представления математических моделей.

    2. Алгоритмическая форма представления моделей.

    3. Свойства алгоритма.

    Решение задачи с помощью ПЭВМ разделяется на несколько этапов. Задача, прежде всего, должна быть математически описана, например, дифференциальными уравнениями, системой линейных или нелинейных уравнений. Далее следует выбор численного метода решения, который позволит свести исходную задачу к последовательности элементарных действий. Например, интегрирование при помощи численных методов заменяют рядом последовательных сложений.

    Решение задачи на ЭВМ включает в себя следующие основные этапы:

    1. Постановка задачи.

    2. Выбор численного метода решения.

    3. Разработка алгоритма и структуры данных.

    4. Реализация алгоритма на входном языке ПЭВМ.

    5. Подготовка задания для ПЭВМ, ввод программы в оперативную память.

    6. Отладка и испытание программы.

    7. Решение задачи на ПЭВМ, обработка и оформление результатов расчета.

    Алгоритмизация задачи – процесс проектирования алгоритма для решения задач с помощью ЭВМ. Алгоритмизировать поставленную задачу это значит, что процесс проектирования необходимо описать в форме алгоритма.

    Алгоритм – это свод правил и законов, которые дают возможность, преобразуя исходные данные задачи получить результат. При этом учитывается кратчайший путь (решение) преобразования.

    Согласно ГОСТ алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.

    К изобразительным средствам описания алгоритма относятся следующие способы их представления: словесный, структурный, графический, программный.

    Способы изображения алгоритма
    Словесный Структурно-стилизованный Графический Программный

    Рис. 4.6. Способы изображения алгоритма

    Словесная форма – это текстовая форма записи на естественном языке.

    Структурно–стилизованная форма – это запись последовательности действий на алгоритмическом языке псевдокода.

    Графическая форма – это изображение последовательности действий в виде схем из графических символов.

    Программная форма — это последовательность действий, описанная на языках программирования.

    Графический способ записи алгоритма

    Графический способ изображения структур алгоритмов использует совокупность блочных символов, соединенных линиями передач управления вычислительным процессом. Такое изображение называется методом блок-схем или структурной блок–схемой алгоритма.

    Блок-схема – это графическое изображение алгоритма в виде последовательности связанных между собой блоков, каждый из которых соответствует одному шагу алгоритма.

    Подробнее рассмотрим структуру графического алгоритма, представленную на рис. 16.

    Графический способ (метод блок-схем)
    Линейная Разветвленная Циклическая
    Алгоритм с вложенными циклами

    Рис. 4.7. Структура графического алгоритма

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

    Наиболее часто употребляемые символы действий представлены в нижеследующей табл.

    Схема обозначений наиболее часто употребляемых блоков

    Наименование Обозначение Функции
    Процесс Вычислительное действие или последовательность вычислительных действий
    Решение Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий
    Модификация
    с
    b
    а

    Выполнение операций меняющихся команды, изменяющих програму
    Предопределенный процесс
    0,15 а
    а
    b
    а
    b
    а

    Вычисление по программе
    Документ
    0,5 а
    b
    R
    R

    Вывод, печать результатов на бумаге
    Соединитель
    0,5 а

    Разрыв линии потока
    Продолжение табл. 4.1
    Ввод, вывод
    0,5 а
    b
    а
    Вывод данных на перфокарты
    Пуск, останов Начало, конец, вход, выход в подпрограммах
    Комментарии Связь между элементами схемы и пояснение

    На ниже приведенных блок–схемах показано вычисление значений заданной функции у=f(х). Такие вычисления называются табулированием. Для выполнения табулирования необходимо последовательно перебрать все значения параметра х цикла в указанном диапазоне изменения хн ≤ хi ≤ хк его величины. Как только это условие будет нарушено, следует приостановить вычисления.

    На рис. 4.8,4.9 показаны примеры разветвленной и циклической блок–схем.

    Пример. Составить схему алгоритма для вычисления и печати функции при изменении параметра X от Xн до Xк с шагом h.

    Разветвленная и циклическая блок–схемы алгоритмов вычисления функции представлены на рис. 4.8,а, в и рис. 4.9.

    Рис. 4.8. Блок-схема вычисления функции

    а — разветвления блок-схема;

    в — циклическая блок-схема.

    Рис. 4.9. Циклическая блок-схема вычисления функции

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

    Но он обладает и существенным недостатком, а именно, записи предписаний не могут непосредственно восприниматься машиной и в дальнейшем выполняться. Поэтому графический способ изображения алгоритма может использоваться только для предварительной работы над проектом.

    Средством описания графических алгоритмов являются языки программирования. Они позволяют на основе строго определенных правил синтаксиса и семантики алгоритмического языка формировать последовательность предписаний, однозначно отражающих смысл и содержание графических алгоритмов.

    Алгоритм, записанный по правилам языка программирования, является исходной программой на этом языке и называется программным модулем.

    | следующая лекция ==>
    Методы получения математических моделей | ТЕМА: СОВРЕМЕННЫЕ КОМПЬЮТОРНЫЕ ТЕХНОЛОГИИ ПРОЕКТИРОВАНИЯ ТКАНЕЙ

    Дата добавления: 2014-01-07 ; Просмотров: 1941 ; Нарушение авторских прав? ;

    Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

    Методы изображения алгоритмов

    Разработка алгоритмов для структурного программирования и их реализация

    Современным пользователям и профессиональным программистам приходится иметь дело с огромным количеством разнообразных языков программирования различных уровней и назначений. Но по-прежнему начинать изучение основ программирования целесообразно на базе структурных алгоритмов и программ, так как при использовании таких форм программирования у обучающегося быстрее формируется четкое алгоритмическое мышление [1, 2].

    Цель выполнения работ: обучающиеся технических специальностей и форм обучения должны показать и закрепить свои знания по:

    • базовым понятиям алгоритмов;
    • основным методам программирования;
    • принципам работы прикладных программных средств для технических расчетов;
    • управлению техническими средствами ЭВМ.

    ОСНОВНЫЕ ТЕРМИНЫ И ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ


    Алгоритм – это последовательность элементарных шагов, выполнение которой позволяет получать однозначный результат (не зависящий от того, кто выполнял эти шаги) или за конечное число шагов прийти к выводу о том, что решения не существует. [3].

    Задача называется алгоритмически неразрешимой, если не существует машины, модели или алгоритма, которые ее бы решали.

    Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть самого простого, — процесс творческий. Другое дело – реализация уже имеющегося алгоритма, ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Совокупность действий (шагов) образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.

    Несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций [3]:

    • дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов; каждое действие исполняется только после того, как закончилось исполнение предыдущего;
    • определенность – каждое действие, правило алгоритма должно быть четким, однозначным и не оставлять место для произвола, и не требовать никаких дополнительных указаний или сведений о решаемой задаче;
    • результативность – алгоритм должен приводить к решению задачи за конечное число шагов;
    • массовость – алгоритм должен быть применим для некоторого класса задач, различающихся только исходными данными.

    Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам.

    Первое правило – необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (в виде, удобном для записи, поиска и хранения в ПК) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, в результате своей работы выдает данные, которые называются выходными.

    Второе правило – для работы алгоритма требуется память. В памяти размещаются входные, выходные и промежуточные данные. Поименованная ячейка памяти называется переменной. В теории алгоритмов размеры памяти не ограничиваются.

    Третье правило – дискретность.

    Четвертое правило – детерменированность. После каждого шага (действия) необходимо указывать, какой шаг выполняется следующим, либо дать команду остановки.

    Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считается результатом работы алгоритма.

    Виды алгоритмов как логико-математических средств:

    • механические – или детерминированные, жесткие, задают определенные действия в единственной и достоверной последовательности, обеспечивая однозначный и требуемый результат;
    • гибкие – дают последовательность нахождения решения задачи несколькими путями или способами, или это такие алгоритмы, в которых достижение результата однозначно не определено;
    • линейные – набор действий, выполняемых во времени последовательно, друг за другом;
    • разветвляющиеся – алгоритмы, содержащие хотя бы одно условие, в результате проверки которого программа переходит к одному из двух возможных шагов;
    • циклические – алгоритмы, предусматривающие многократное повторение одного и того же действия, но над новыми данными;
    • подчиненные (вспомогательные) – алгоритмы, ранее разработанные и целиком использованные при алгоритмизации задачи (обычно на их основе создаются подпрограммы).

    Процессы вычислений циклической структуры в свою очередь можно разделить на три группы:

    • циклические процессы, для которых количество повторений известно – счетные циклы или циклы с заданным количеством повторений;
    • циклические процессы, завершающиеся по достижении или нарушении некоторых условий — итерационные циклы;
    • циклические процессы, из которых возможны два варианта выхода: по завершении процесса и досрочный выход по какому-либо дополнительному условию – поисковые циклы.

    Методы изображения алгоритмов

    На практике распространены формы представления алгоритмов:

    • словесная — в виде последовательности записей на естественном языке;
    • графическая — в виде совокупности графических знаков;
    • псевдокоды – полуформализованное описание алгоритма на условном языке, включающем в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.;
    • программная – текст на языке программирования.

    Запись алгоритмов на естественном языке (словесная форма) не получила широкого распространения, из-за отсутствия наглядности; ввиду возможности неоднозначного толкования записей, и их многословности. Пример словесной формы алгоритма:

    1.Определить форматы переменных А, С и В.

    2.Ввести значения А и В с клавиатуры.

    3.Сравнить А и В.

    4.Если А больше В, то переменной С присвоить значение А.

    5.Если В больше А, то переменной С присвоить значение В.

    6.Если А равно В, переменной С присвоить значение 0.

    7.Вывести на экран значения А, В и С.

    Запись алгоритма в виде совокупности графических знаков называется блок-схемой, и получила широкое распространение в научной и учебной литературе. На изображение схем алгоритмов существует ГОСТ 19.701-90. Знаки (блоки) соединены линиями информационного потока (стрелками); каждый знак имеет определенный смысл (см. табл. 1) и соответствует одному шагу (действию) алгоритма. Внутри блока дается описание соответствующего действия. Для простоты чтения схем желательно, чтобы линия входила в блок сверху, а выходила снизу, или шла слева направо. Блоки должны быть одного масштаба. В случае, когда схема алгоритма не умещается на листе, используются соединители. В Microsoft Word для выполнения алгоритмов используется панель инструментов «Рисование – Автофигуры – Блок-схема».

    Выполнение алгоритма в виде блок-схемы перед программированием существенно облегчает процесс создания и отладки программы, определения форматов и перечня переменных, поиск ошибок, редактирование алгоритма в будущем.

    Таблица 1 ? Знаки для изображения схем алгоритмов

    Обозначение (графическое изображение) Название Назначение Наименованиеавтофигуры в Word
    Терминатор Началоили завершение программы или подпрограммы Знакзавершения
    Процесс Обработкаданных (вычисления, пересылки т.п.) Процесс
    Решение Ветвления,выбор, итерационные и поисковые циклы Решение
    Данные Операцииввода-вывода Данные
    Подготовка Счетныециклы Подготовка
    Документ Выводна бумагу Документ
    Архив Данные,хранящиеся в архиве или взятые из архива
    Документ Документ,подготовленный вручную
    Файл Файлили база данных Магнитныйдиск
    Предопреде-ленныйпроцесс Вызовподпрограмм (процедур) Типовойпроцесс
    Источникили приемникданных Указаниеисточника или приемникаданных
    Монитор Выводинформации на экран Дисплей
    Соединитель Маркировкаразрывов линий Узел
    Соединитель Маркировкаразрывов линий Ссылкана другую страницу
    Комментарий Поясненияк действиям Выноска
    Поток информации Линии,связывающие блоки Стрелка

    В теории программирования доказано [1, 2], что для записи любого сложного алгоритма достаточно трех базовых структур: следование – последовательное выполнение действий (рис. 1,а); ветвление – соответствует выбору одного из двух вариантов действий (рис. 1,б); цикл-пока – определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 2).

    Рисунок 1 ? Базовые алгоритмические структуры: а) следование, б) ветвление

    Рисунок 2 ? Базовая структура: цикл-пока

    На основе базовых структур строятся дополнительные структуры для изображения алгоритмов: выбор (рис. 3), цикл-до, счетный цикл.

    Рисунок 3 ? Дополнительная структура «выбор» и реализация ее через базовые структуры

    Рисунок 4 ? Дополнительная структура: цикл – до

    Рисунок 5 ? Дополнительная структура: цикл с заданным числом повторений (счетный цикл).

    Простые циклические конструкции могут вкладываться в другую простую циклическую конструкцию, образуя тем самым вложенный (сложный) цикл (рисунок 6). При этом необходимо придерживаться следующих правил:

     имена параметров всех простых циклов не должны повторяться;

     нельзя войти во внутренний (вложенный) цикл, минуя внешний;

     простые циклы в сложном цикле не должны пересекаться, то есть внешний цикл должен заканчиваться после внутреннего и инструкции тела внешнего цикла не должны быть в теле внутреннего цикла [2].

    Рисунок 6 – Примеры вложенных циклов

    Выполните задания из Приложений I, II и III.

    На основе алгоритмов создается программное обеспечение (ПО) для решения прикладных задач.

    ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА И ИНТЕРНЕТ – ИСТОЧНИКИ

    1.Иванова Г.С. Основы программирования.- Изд-во МГТУ им. Н.Э. Баумана.- 2004.

    2.Информатика: учеб. пособие: / Л. С. Таганов, А. Г. Пимонов: ГУ КузГТУ. – Кемерово, 2010. – 330с.

    Варианты 14 и 27 (по журналу) выполняют 1 вариант задания, 15 и 28 варианты по журналу – 2 вариант здания и т.д.

    Варианты 6, 11, 16, 21, 26, 31 (по журналу) выполняют 1 задание; варианты 7, 12, 17, 22, 27, 32 – 2 задание и т.д.

    Дополнить алгоритм началом и концом, вычислить тестовые примеры.

    Рисунок 7 – Блок схема для вариантов 1, 14, 27

    Рисунок 8 – Блок схема для вариантов 2, 15, 28.

    Рисунок 9 – Блок схема для вариантов 3, 16, 29.

    Рисунок 10 – Блок схема для вариантов 4, 17, 30.

    Рисунок 11 – Блок схема для вариантов 5, 18, 31.

    Рисунок 12 – Блок схема для вариантов 6, 19, 32.

    Рисунок 13 – Блок схема для вариантов 7, 20, 33.

    Рисунок 14 – Блок схема для вариантов 8, 21.

    Рисунок 15 – Блок схема для вариантов 9, 22.

    Рисунок 16 – Блок схема для вариантов 10, 23.

    Рисунок 17 – Блок схема для вариантов 11, 24.

    Рисунок 18 – Блок схема для вариантов 12, 25.

    Рисунок 19 – Блок схема для вариантов 13, 26.

    Статьи к прочтению:

    Способы записи алгоритмов | Информатика 9 класс #12 | Инфоурок

    Похожие статьи:

    Лекция 14. Этапы решения задач на ЭВМ. Понятие алгоритма. Языки программирования. Этапы решения задач на ЭВМ. Процесс разработки программ представляется…

    Существуют несколько способов описания алгоритма: словесное, псевдокод, блок-схема, программа. Словесное описание представляет структуру алгоритма на…

    Алгоритм рисования сглаженной линии


    Такая проблема:
    1) нужно попиксельно нарисовать линию;
    2) толщина линии должна задаваться параметром;
    3) линия должна быть сглаженная;
    4) алгоритм рисования должен быть очень быстрым, прямо таки сглаживать нужно «на лету»(без мультисемплирования и вообще желательно без буфферизации).

    Функция рисования пикселя: SetPix(int x, int y, int color); color задается так: 0xRRGGBBAA; .
    Написал свой алгоритм, он рисует линию разной толщины. Толщина разная, но на концах линия получается обрезанной:

    Подскажите алгоритм, исходники, что позволяют добиться желаемого результата)

    1 ответ 1

    Но в вашем случае требуется модифицированный алгоритм Брезенхема, меняющий интенсивность окрашивания точки, — иногда называется алгоритм Ву Сяолиня.

    Примеры обоих алгоритмов в статье на Хабре.

    Сравнительный анализ алгоритмов удаления невидимых линий и поверхностей, работающих в пространстве изображения

    технические науки

    • Абрамова Оксана Федоровна , доцент, доцент
    • Волжский политехнический институт (филиал) Волгоградский государственный технический университет
    • Никонова Надежда Сергеевна , студент
    • Волжский политехнический институт, Волгоградский государственный технический университет
    • КОЭНА-САЗЕРЛЕНДА
    • АЛГОРИТМЫ УДАЛЕНИЯ НЕВИДИМЫХ ЛИНИЙ
    • АЛГОРИТМ ВАРНОКА

    Похожие материалы

    В настоящее время практически каждый человек старается окружить себя полезными и красивыми вещами, одной из которых является компьютерная графика (ее можно встретить в печатной литературе, на экране телевизора и рекламном плакате, дизайнерском проекте). С развитием компьютерных технологий компьютерная графика все больше проникает в жизни людей, она используется в науке и образовании, бизнесе, киноиндустрии, а также во всевозможных отраслях промышленности [1]. Но не стоит забывать, что изучение компьютерной графики далеко не легкий процесс [2, 3, 4]. В данной статье мы рассмотрим одну из наиболее сложных задач компьютерной графики – удаление невидимых линий и поверхностей.

    В процессе отображения трехмерной сцены на экране может возникнуть такая ситуация, когда часть объектов сцены перекрывает другие объекты. Невидимые наблюдателю части объектов не должны быть отображены на экране, или должны рисоваться особым образом (например, пунктиром). Неправильная отрисовка видимых и невидимых линий может привести к искажению изображения (к его неправильному восприятию). Выход из подобных ситуаций можно найти с помощью алгоритмов удаления линий и поверхностей. Невидимые линии удаляются при отображении сцены в каркасном виде (алгоритм выделяет части ребер объекта, которые заслонены и удаляет их). При отображении объектов с помощью закрашенных поверхностей удаляются их невидимые части. Также определяются видимые и невидимые для наблюдателя части объемов, которые могут быть удалены аналогичным образом [3].

    В настоящее время существует множество алгоритмов удаления невидимых линий и поверхностей. Все их можно разделить на три группы:

    • алгоритмы, работающие в пространстве объекта (например, алгоритм Робертса);
    • алгоритмы, работающие в пространстве изображения (алгоритм Коэна-Сазерленда, алгоритм с использованием z-буфера, алгоритм Варнока, Алгоритм Вейлера-Азертона и другие);
    • алгоритмы, работающие попеременно с системами координат как объекта, так и изображения (алгоритм Ньюэла-Ньюэла-Санча).

    Проведем сравнительный анализ алгоритмов, работающих в пространстве объекта и в пространстве изображения (табл. 1) [2, 3, 4].

    Таблица 1 Сравнительный анализ алгоритмов удаления невидимых линий

    Алгоритмы, работающие в пространстве объекта

    Алгоритмы, работающие в пространстве изображения

    Алгоритмы имеют дело с физической системой координат, в которой описываются данные объекты

    Алгоритмы работают с системой координат экрана, на который визуализируются объекты

    Высокая точность (точные результаты, которые могут быть ограничены только точностью вычислений)

    На точность вычислений влияет разрешающая способность экрана

    растет теоретически, как квадрат числа объектов n2

    растет теоретически, как nN, где n- количество объектов в сцене,N — число пикселов

    Однако, стоит отметить, что, не смотря достаточно большое количество разнотипных алгоритмов, в решении задачи загораживания существует ряд важных и до сих пор еще не решенных проблем:

    • не существует универсального алгоритма, который не ограничивался бы определенным классом линий или поверхностей, необходимых для отображения объектов;
    • практически невозможно выделить наилучший алгоритм, который был бы пригоден для всех типов графических устройств и любых приложений [4, 5].

    Поэтому создание единого алгоритма, который смог бы справиться с удалением невидимых линий и поверхностей, является актуальной задачей повышенной сложности, которая не нашла еще своего решения.

    В данной статье будет проведен сравнительный анализ двух алгоритмов удаления невидимых линий и поверхностей, работающих в пространстве изображения: алгоритма Коэна-Сазерленда и алгоритма Варнока.

    Алгоритм Коэна-Сазерленда

    Алгоритм Коэна-Сазерленда позволяет определить часть отрезка, пересекающую выделенную прямоугольную область, определяя таким образом видимость и невидимость отрезков. Суть алгоритма заключается в том, что плоскость разбивается на 9 частей прямыми, образующими стороны прямоугольника (рис. 1). Каждая часть имеет свой 4х-битный код. [6]

    Рисунок 1 Коды областей Коэна-Сазерленда

    Поле вывода (с учетом границ) состоит из точек (x,y), которые удовлетворяют соотношения xl≤x≤xr и yb≤y≤yt . Допустим, что отрезок задан с помощью координат концевых точек (x1,y1) и (x2,y2). В начале алгоритма Коэна-Сазерленда выявляются полностью видимые и невидимые отрезки:

    В остальных случаях отрезок может (но не обязан) пересекать поле вывода.

    В данном алгоритме каждой концевой точке отрезка присваивается свой код, в зависимости от ее расположения относительно поля вывода. Если коды концов отрезков равны нулю, то он (отрезок) лежит в поле вывода (внутри окна). Для анализа остальных случаев необходимо воспользоваться операцией логического умножения кодов [6, 7].

    Руководствуясь полученной таблицей истинности, можно утверждать: если произведение концов отрезка принимает значение T (true), то этот отрезок полностью лежит по одну сторону одной из прямых (l, r, t или b), причем, важно отметить, он лежит во внешней стороне относительно поля вывода, следовательно, он полностью невидим. Если же произведение оказалось F(false), то отрезок частично находится в поле вывода [7].

    Приведем общую блок-схему алгоритма Коэна-Сазерленда (рис. 2).

    Рисунок 2 Блок-схема алгоритма Коэна-Сазерленда

    В блок-схеме используются следующие обозначения:

    • GetCode(r) – вспомогательная функция, определения кода точки;
    • C1, C2 — коды точек r1, r2;
    • Intersec(r1,l), Intersec0(r1,l) – вспомогательные функции, поиска пересечения отрезка со сторонами окна при условии, что точка r1 лежит в окне и что обе точки лежат вне окна; если пересечения нет, устанавливает переменную IsVisible в 0, соответственно.

    Входными данными являются точки (1), массив координат окна

    На выходе получаем новые концевые точки (3), а также значение переменной IsVisible (0 — отрезок видимый)[4].

    Теперь приведем блок-схемы и рассмотрим более подробно вспомогательные функции: Intersec(r1,l) и Intersec0(r1,l) (рис. 3, 4).

    Рисунок 3 Блок-схема вспомогательной функции Intersec

    Воспользуемся методом поиска пересечений, использующим параметрическое уравнение прямой, проходящей через точки:

    или в координатном виде:

    Определим точку пересечения отрезка с верхней границей окна, которая описывается соотношениями: (6).

    Тогда условие пересечения границы и отрезка имеет вид:

    Аналогично запишутся формулы для оставшихся границ окна. Если точка расположена внутри поля вывода, то, в зависимости от знака ly, необходимо искать пересечение либо с верхней, либо с нижней границей поля вывода (окна). Если такие пересечения отсутствуют, необходимо искать пересечения с двумя другими гранями окна (левой и правой стороной). До того как рассматривать выше описанные варианты, необходимо исключить случаи горизонтальных ly = 0 (пересечение с правой или левой границей: (L,y1), (R,y1), в зависимости от знака lx и вертикальных lx = 0 (пересечение с верхней или нижней границей: (x1,B), (x1,T) направлений отрезка.[7, 8]

    Рисунок 4 Блок-схема вспомогательной функции Intersec0

    Для случая, когда оба конца отрезка лежат вне окна вывода, в начале найдем одну точку пересечения с границей окна и заменим ею один из концов отрезка, а далее будем использовать вышеописанный алгоритм нахождения второй точки. Важно отметить, что первый шаг не в 100% случаев оканчивается успешно, так как с помощью предварительного анализа невозможно исключить все возможные невидимые отрезки. Аналогично предыдущему алгоритму перед поиском точек пересечения с полем вывода выполняется проверка на вертикальное и горизонтальное направление отрезка. Так как часть отрезков была исключена благодаря предварительному анализу, остаются только две возможные ситуации (рис. 5).

    Рисунок 5 Отрезки параллельны сторонам поля вывода

    Точки пересечения на рисунке 6 определяются очевидным образом.

    Далее последовательно рассматриваются 4 случая расположения точки относительно прямых, которые ограничивают поле вывода. При нахождении точки пересечения в любом из вариантов, процесс анализа останавливается, данная точка заменяется новой точкой и вызывается функция Intersec. Если при переборе всех 4х вариантов положительный ответ не был получен, переменная IsVisible получает значение 0.

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

    Алгоритм Варнока

    Алгоритм Варнока работает в пространстве изображения. В процессе его работы так же рассматривается окно и определяется пустое ли оно или его содержимое просто для визуализации. Если эти два условия не выполняются, то происходит разбиение окна до тех пор, пока содержимое фрагментов окна не станет достаточно простым для визуализации или их размеры не достигнут пределов разрешения (в этом случае информация усредняется, т.е. выводится на экран с одинаковой интенсивностью или цветом)[9].

    Существует множество видов алгоритма Варнока, все они различаются методами разбиения окна и критериями, определяющими является ли изображение в окне простым. Простейшая и оригинальная версия алгоритма Варнока выглядит следующим образом: окно, содержимое которого сложно визуализировать, разбивается на четыре одинаковых фрагмента, так называемых подокна; затем подокно, в котором есть содержимое, разбивается до тех пор, пока не будет достигнут предел разрешения экрана[8, 9].

    Такой процесс разбиения можно изобразить в виде дерева. Важно отметить, что именно в алгоритме Варнока впервые была реализована структура данных, названная кватернарным деревом. Корень этого дерева – визуализируемое окно; узла дерева – подокна (они изображаются в виде прямоугольников, которые хранят левую нижнюю координату угла подокна, а также длину его стороны). Подокна обрабатываются последовательно друг за другом слева направо на каждом уровне разбиения дерева. Перебором находится подокно, содержащее сложное изображение, которое необходимо разбить (такое подокно называется активным узлом); и все повторяется на новом уровне. На каждом уровне есть активный узел, слева от активного узла располагаются пустые окна, справа от активного узла располагаются окна, которые будут обработаны позднее, т.е. будут объявлены пустыми или будут разбиты при обратном обходе дерева.


    При помощи вышеописанного алгоритма можно удалить как невидимые линии, так и поверхности. Однако минусом данного способа является большое количество разбиений исходного окна, который возникает из-за простоты критерия разбиения и его негибкости. Эффективность повысится, если усложнить критерий и способ разбиения.

    Чтобы рассматривать более сложные критерии разбиения окна необходимо сначала определить способы расположения многоугольника относительно окна.

    Будем выделять 4 разных многоугольника (рис. 6): внешний (расположен полностью вне окна); внутренний (полностью расположен внутри окна); пересекающий (пересекает хотя бы одну границу окна); охватывающий (окно целиком располагается внутри рассматриваемого прямоугольника) [2, 6].

    Рисунок 6 Типы многоугольников: внешний (а), внутренний (b), пересекающий (c), охватывающий (d).

    Зная вышеописанные типы многоугольников, можно рассмотреть следующие правила обработки окна. Для каждого окна:

    • если в сцене присутствуют только внешние многоугольники по отношению к окну, то это окно считается пустым; оно не разбивается и изображается с фоновой интенсивность или цветом;
    • если в сцене присутствует лишь один многоугольник, который располагается внутри окна, то площадь вне многоугольника изображается с фоновой интенсивностью или цветом, а площадь внутри многоугольника, заполняется соответствующим ему цветом или интенсивностью;
    • если в сцене располагается пересекающий многоугольник, то площадь вне многоугольника изображается с фоновой интенсивностью или цветом, а площадь внутри многоугольника, которая располагается внутри окна, заполняется соответствующим ему цветом или интенсивностью;
    • если в сцене присутствует только один многоугольник (охватывающий), то окно изображается с интенсивностью или цветом соответствующими охватывающему многоугольнику;
    • если в сцене присутствует хотя бы один охватывающий многоугольник, расположенный ближе других к точке наблюдения, то окно заполняется интенсивностью или цветом, соответствующими охватывающему многоугольнику.

    В любом другом случае необходимо провести разбиение окна [1,6].

    Последний пункт для обработки окна решает задачу удалений невидимых поверхностей. Получается, что многоугольник, расположенный ближе всего к наблюдателю (к точке наблюдения) перекрывает любые другие многоугольники. Остальные пункты для обработки окна позволяют сократить число подразбиений окна, так как в них рассматриваются ситуации пересечения окна и только одного многоугольника.

    Для реализации данного алгоритма необходимо определить взаимное расположение многоугольника и окна с помощью функций, которые просты в реализации, если рассматриваются прямоугольные окна и выпуклые многоугольники, а в случае невыпуклых многоугольников задача становится сложнее.

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

    Таблица 2 Сравнительный анализ алгоритмов Коэна-Сазерленда и Варнока

    Чтобы определить, как отрезок расположен относительно окна вывода, необходимо проверить коды концов отрезка и в зависимости от их значения сделать выводы.

    Чтобы проанализировать является ли элемент изображения видимым или невидимым в окне вывода, необходимо осуществить последовательное разбиение объектного пространства на составные части.

    Пространство, в котором работает алгоритм

    Работает в пространстве изображения

    Работает в пространстве изображения

    Возможность удаления невидимых линий

    Возможность удаления невидимых поверхностей

    выполняет отсечение за несколько итераций (около 2х)

    прямо пропорционально насыщенности изображения

    Отсечение отрезков продолжается до тех пор, пока длина очередного отрезка не станет меньше наперед заданной точности.

    Разбиение области стоит прекратить, как только ее размер станет не больше одного пикселя.

    Эффективность для сложных сцен

    Повышение эффективности алгоритма

    • расположение объектов: эффективность алгоритма Коэна-Сазерленда повышается, если большая часть примитивов полностью находится в большом окне, или большинство примитивов лежит вне малого окна.
    • предварительная сортировка граней объектов, находящихся в сцене, по их расстоянию от наблюдателя.
    • повышение эффективности разбиений (например, с использованием прямоугольной объемлющей оболочки многоугольника).
    • легкая в случае прямоугольных окон и выпуклых многоугольников;
    • усложняется, если многоугольники невыпуклые
    07.12.2014, 10:19

    Попиксельная отрисовка массива ?
    Здраствуйте. Задача такова. Необходимо взять двумерный массив из файла, элементы массива.

    отрисовка линии
    пишу логический анализатор, функция читает состояние порта, и присваивает 150 раз в секунду.

    Отрисовка линии
    Вот значит сижу и туплю, а проблема то легко решаемая. Так вот, поковырялся в msdn, и не.

    Отрисовка линии
    Всем привет. вот что накатал: #include #include using namespace std; .

    Неправильная отрисовка линии
    Проблема с отрисовкой нулевой линии при чтении линии графика из массива. Нулевая линия рисуется тем.

    Илон Маск рекомендует:  Можно ли использовать иконку как картинку на кнопке tspeedbutton
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL