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

Основной операцией в алгоритме Варнока является определение наличия подлежащих рассмотрению элементов для некоторой области экрана. Если в данной области ничего не содержится, то нет необходимости продолжать ее рассмотрение — она пуста. Если появившийся в области экрана элемент (линия, поверхность, вершина) достаточно прост для непосредственного изображения, то-алгоритм выполняет его построение. Однако набор элементов в области экрана может быть слишком сложным для анализа и непосредственного изображения. В этом случае алгоритм сообщает о невозможности решения для данной области экрана. Таким образом, анализ элементов в области экрана имеет три возможных результата 1) в данной области не виден ни один элемент 2) выполняется построение изображения, поскольку элемент или элементы в области классифицируются как простые 3) алгоритм не дает решения, так как совокупность элементов в области экрана слишком сложна для анализа. Флойд называет такие процедуры недетерминированными, так как они могут дать отказ в случае неудачного решения поставленной задачи 192]. [c.302]

На рис. 14.8,а показана сцена, удаление невидимых линий в которой выполнено в соответствии с алгоритмом Варнока. Каждый маленький значок х представляет светящуюся точку на экране. На рис. 14.8,6 показана та же сцена без удаления невидимых линий. [c.302]

Алгоритм Варнока характеризуется пятью основными компонентами, описываемыми в следующих разделах блоками просмотра, решения, вывода элемента, вывода точки и управления. Все эти пять частей показаны на рис. 14.10. Блок просмотра исследует [c.306]

Такая техника обработки вполне универсальна. Ее можно применить для криволинейных поверхностей и для областей экрана любой желаемой формы. Методика деления области для получения более простых случаев дает удовлетворительный результат при решении проблемы удаления невидимых линий. Алгоритм может быть снабжен тривиальными или очень сложными блоками просмотра и решения алгоритм Варнока для простых вариантов легко программируется. [c.307]

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

Ин( юрмация на выходе алгоритма неудобна для вывода изображений на растровый дисплей, так как исследование окон проводится в соответствии с поисковой природой алгоритма, а не с возрастанием или убыванием координаты Кз- В связи с этим для растровых дисплеев был разработан специальный вариант алгоритма Варнока, в котором продемонстрировано остроумное использование аппаратуры управления видеотерминалами [471. [c.318]

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

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

Геометрическое упрощение проявляется при определении пересечения плоского многоугольника в экранной системе координат с окном, представляющим собой сканирующую линию с координатой как показано на рис. 14.20. Геометрическим местом пересечения является прямая в плоскости Уе, тогда как геометрическим местом соответствующего пересечения с окном в алгоритме Варнока является многоугольник в трехмерной экранной системе координат. [c.319]

Как следует изменить алгоритм Варнока, чтобы каждый видимый отрезок был представлен одной прямой, а не набором точек (рис. 14.46) [c.336]

Сравните блоки просмотра и решения алгоритмов Варнока и построчного сканирования. [c.336]

В трех описанных алгоритмах используются различные варианты алгоритма отсечения. В алгоритме Робертса имеется блок точного отсечения всех прямых. В алгоритме Варнока отсечение выполняется по граням параллелепипеда видимости вследствие того, что исследуемые области никогда не выходят за пределы этого параллелепипеда однако отсечение прямых, пересекающих плоскость 2е = О, производится неправильно. В алгоритме Уоткинса выполняется отсечение только по левому и правому краям экрана если объекты выступают за пределы нижнего и верхнего краев, построенное изображение будет неверным. Прямые, пересекающие плоскость 2е = О, также обрабатьшаются неправильно. [c.336]

Работа Флойда о недетерминированных алгоритмах (примерами которых являются алгоритмы Варнока и Уоткинса для удаления невидимых поверхностей) опубликована в работе [92]. [c.416]

В приложении приводится описание реализации алгоритма Варнока, краткая характеристика которого дана в гл. 14. Вначале описываются специализированные вычисления в блоках просмотра и решения, затем приводится текст программы на языке SAIL в том виде, как он получен из ЭВМ. [c.484]

Число вариантов реализации возможных блоков решения, пригодных для алгоритма Варнока, почти не ограничено. Ниже приводятся два интересных варианта, работающих с пересекающимися плоскостями. В них используются следующие символические обозначения 5 — число охватывающих окно многоугольников, / — число пересекающих многоугольников, не считая тех, которые закрыты плоскостью какого-либо охватывающего многоугольника. В первом варианте блока решения никогда не выполняется отображение многоугольника целиком. Блок решения должен выделять лишь два случая (рис. 14.18) [c.488]

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

Сканирующая строка делится на интервалы, и задача удаления невидимых линий решается для каждого интервала. Обработка выполняется двумя основными блоками блоком просмотра и блоком решения. Функции их во многом напоминают функции аналогичных блоков алгоритма Варнока. Блок просмотра обрабатывает каждый отрезок, который полностью или частично лежит внутри обрабатываемого интервала этот блок запоминает информацию, достаточную для определения в блоке решения, какой из перечисленных в разд. 14.4.1 случаев имеет место. Блок решения активизируется после того, как все вероятные отрезки обработаны блоком просмотра блок решения определяет, имеет ли место простой случай (случаи 1—3 в разд. 14.4.1), и если да, то генерирует отображаемую информацию в данном интервале. Однако если блок просмотра и блок решения определяют сложный случай, то вырабатывается признак отказ , что вызывает деление интервала. [c.510]

Как и в алгоритме Варнока, в функции общего блока управления входит вызов блоков просмотра и решения, деление интервалов и т. д. Учет отрезков довольно сложен, он также выполняется блоком управления (рис. П7.14). Отрезки передаются блоку просмотра в основном посредством списка XSORT. Тем не менее необходимо тщательно фиксировать каждый из обрабатываемых в интервале отрезков в одном из следующих двух списков [c.510]

Такие работы, как удаление невидимых линий и поверхностей, являются проблемой, относящейся исключительно к машинной графике. Эта проблема очень увлекательна многие специалисты затратили значительные усилия на поиск быстрых алгоритмов удаления невидимых линий и поверхностей. Некоторая начальная работа по решению этой задачи была проделана Робертсом в лаборатории Линкольна Массачусетского технологического института [234]. Его решение было весьма изящным, но достаточно расточительным с точки зрения использования мощности ЭВМ. С тех пор некоторое заметное продвижение к нахождению лучшего решения было сделано в Университете шт. Юга сюда относятся алгоритм, разработанный Дж. Варноком [300], а также работа Уоткинса и Гуро по разработке алгоритма, пригодного для аппаратной реализации [301, 104]. [c.20]

Рассмотрим детально три алгоритма. Первый из них, разработанный Робертсом, явился практически первым решением проблемы удаления невидимых линий [234] и отличается удачным использованием геометрии и линейного программирования. Второй, принадлежащий Варноку, пригоден для построения как штриховых, так и полутоновых изображений [300] будет рассмотрен штриховой вариант. Этот алгоритм интересен применением недетерминированных методов. Третий алгоритм предназначен для построения полутоновых изображений на растровых дисплеях [301]. В нем для ускорения вычислений использовано сходство соседних линий растра. [c.288]

Можно ли предложить изменения алгоритмов Уоткинса и Варнока, которые бы привели к правильной обработке объектов вне экрана [c.337]

Определение невидимых линий является одной из давних задач машинной графики. Работа Робертса [234] интересна по историческим и техническим соображением, поскольку разработанный им алгоритм дал толчок к активной работе в этой области. Изящное решение разработано Варноком [300]. Другие алгоритмы даны в работах [6, 99, 100, 165, 173, 174]. [c.416]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...