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

Август 5, 2022

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

Содержание

2. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей, которые видимы или невидимы
3. Нормали тетраэдра
4. Выделяют три класса алгоритмов удаления невидимых линий или поверхностей: Алгоритмы, работающие в объектном пространстве (3D). Алгоритмы,
5. Работают в физической СК, в которой описаны эти объекты. Плюсы: Точные расчеты, ограниченные только точностью вычислений.
6. Работают в СК изображения (экрана). Точность вычислений ограничена разрешением экрана. Полученные изображения плохо масштабируются – теряется
7. Применяется только для изображения множества выпуклых многогранников, представленных в виде проволочной модели. Не учитываются тени и
8. Идея алгоритма: 1. Удаляются из каждого объекта те ребра или грани, которые скрываются самим объектом. 2.
9. Для каждого объекта сцены: Вычислить уравнение плоскости для каждой грани объекта. Вычислить проекции граней. Вычислить и
10. Выполняется проверка: существуют ли такие отрезки, которые перекрываются другими объектами на экране. Для этого каждый оставшийся
11. Работает алгоритм в пространстве изображения. z-буфер - это отдельный буфер глубины, используемый для запоминания координаты z
12. Схема работы
13. 1. Заполнить буфер кадра фоновым значением интенсивности или цвета. 2. Заполнить z-буфер минимальным значением z. 3.
14. Недостатки алгоритма Основной недостаток алгоритма с Z-буфером - большой объем требуемой памяти. Если сцена подвергается видовому
15. Преимущества Прост в аппаратной реализации Разнородность использующихся примитивов – не ограничиваемся только полигонами. Нелимитированная возможная сложность
16. Алгоритм A-буфера Алгоритм является расширением метода буфера глубины (в названии использована противоположная от Z буква алфавита).
17. Описание работы Каждая позиция в А-буфере имеет два поля. - поле глубины: здесь хранится действительное значение
18. Методы трассировки лучей Прямая трассировка. В методе прямой трассировки генерируется пучок лучей, выходящих из источника во
19. Многоугольники сначала упорядочиваются в направлении от заднего плана к переднему. В случае, когда пары многоугольников не
20. Недостатки при некотором расположении граней этот алгоритм вообще не может дать правильного результата при использовании этого
21. Работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли
22. 1. Проекция грани полностью накрывает область (рис. d); 2. Проекция грани пересекает область, но не содержится
23. Сравнивая область с проекциями всех граней, можно выделить случаи, когда изображение, получающееся в рассматриваемой области, определяется
24. Разбиение картинной плоскости можно производить не только прямыми, параллельными координатным осям, но и по границам проекций
26. Скачать презентацию

Слайд 2

Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер,

поверхностей, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.
Невидимой будет грань, нормаль N к которой ориентирована в ту же сторону, что и вектор R, направленный от наблюдателя к объекту.
Иными словами, для невидимых граней скалярное произведение данных векторов положительно: NR> 0.

Задача удаления скрытых линий и поверхностей

Слайд 3

Нормали тетраэдра

Слайд 4

Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:
Алгоритмы, работающие в

объектном пространстве (3D).
Алгоритмы, работающие в пространстве изображения (экрана) (2D).
Алгоритмы, формирующие список приоритетов.

Классификация алгоритмов по пространству

Слайд 5

Работают в физической СК, в которой описаны эти объекты.
Плюсы:
Точные расчеты,

ограниченные только точностью вычислений.
Полученные изображения можно свободно увеличивать во много раз.
Объем вычислений растет теоретически, как квадрат числа объектов (n2).
К таким алгоритма относятся:
Робертса (1963) ;
Вейлера-Айзертона (1977) ;
BSP-деревьев (1969-91);
Октодеревьев (1982).

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

Слайд 6

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

масштабируются – теряется качество.
Объем вычислений растет теоретически, как n*N (n – количество объектов, N – количество пикселей на экране).
К таким алгоритма относятся:
Z-буфера (1974); А-буфера;
Плавающего горизонта; «Художника»;
Варнока (1968) ; Построчного сканирования (1967) ;
Трассировки лучей (1968).

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

Слайд 7

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

модели.
Не учитываются тени и другие визуальные эффекты.

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

Слайд 8

Идея алгоритма:
1. Удаляются из каждого объекта те ребра или грани, которые

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

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

Слайд 9

Для каждого объекта сцены:
Вычислить уравнение плоскости для каждой грани объекта.
Вычислить

проекции граней.
Вычислить и запомнить габариты прямоугольника, описывающего проекцию объекта: Xmax, Xmin, Ymax, Ymin
Определить не лицевые плоскости:
Вычислить скалярное произведение вектора R (нормаль от наблюдателя к грани объекта) и вектора N (нормаль грани объекта).
Если RN>0 – грань невидима.
Удалить весь описывающий многоугольник, лежащий в данной плоскости.
Если в сцене лишь 1 объект – алгоритм завершён, иначе – 2-й этап.

Алгоритм Робертса (1 этап)

Слайд 10

Выполняется проверка: существуют ли такие отрезки, которые перекрываются другими объектами на

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

Алгоритм Робертса (2 этап)

Слайд 11

Работает алгоритм в пространстве изображения.
z-буфер - это отдельный буфер глубины,

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

Алгоритм Z-буфера

Слайд 12

Схема работы

Слайд 13

1. Заполнить буфер кадра фоновым значением интенсивности или цвета.
2. Заполнить z-буфер

минимальным значением z.
3.   Преобразовать каждый многоугольник в растровую форму в произвольном порядке.
4.   Для каждого Пиксел(x,y) в многоугольнике вычислить его глубину z(x,y).
5.   Сравнить глубину z(х,у) со значением Zбуфер(х,у), хранящимся в z-буфере в этой же позиции.
Если z(х,у) > Zбуфер (х,у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(х,у) на z(х,у).
В противном случае никаких действий не производить.

Описание алгоритма Z-буфера

Слайд 14

Недостатки алгоритма
Основной недостаток алгоритма с Z-буфером - большой объем требуемой памяти.

Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (x, y); обычно бывает достаточно 20 бит. Буфер кадра размером 512 * 512 * 24 бит в комбинации с z-буфером размером 512 * 512 * 20 бит требует почти 1.5 мегабайт памяти.
Так как пиксели в буфер заносятся в произвольном порядке, то возникают трудности с реализацией эффектов прозрачности или просвечивания.

Слайд 15

Преимущества
Прост в аппаратной реализации
Разнородность использующихся примитивов – не ограничиваемся только

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

Слайд 16

Алгоритм A-буфера
Алгоритм является расширением метода буфера глубины (в названии использована

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

Слайд 17

Описание работы
Каждая позиция в А-буфере имеет два поля. - поле глубины:

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

Слайд 18

Методы трассировки лучей
Прямая трассировка. В методе прямой трассировки генерируется пучок лучей,

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

Слайд 19

Многоугольники сначала упорядочиваются в направлении от заднего плана к переднему.
В

случае, когда пары многоугольников не удается достаточно просто упорядочить, они подразделяются на части до тех пор, пока получившиеся части не позволят это сделать.
Характеристика удаленности для грани ABC - это среднее значение z,
mid_z = (A.z+B.z+C.z)/3.

Алгоритм художника

Слайд 20

Недостатки
при некотором расположении граней этот алгоритм вообще не может дать правильного

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

Слайд 21

Работает в пространстве изображения.
В пространстве изображения рассматривается окно и решается

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

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

Слайд 22

1. Проекция грани полностью накрывает область (рис. d);
2. Проекция грани пересекает

область, но не содержится в ней полностью (рис. с);
3. Проекция грани целиком содержится внутри области (рис. b);
4. Проекция грани не имеет общих внутренних точек с рассматриваемой областью (рис. a).

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

Слайд 23

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

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

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

Слайд 24

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

но и по границам проекций граней. В результате получается точное решение задачи.
Предлагаемый метод работает с проекциями граней на картинную плоскость.

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

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

Содержание

Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер,

Нормали тетраэдра

Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:Алгоритмы, работающие в

Работают в физической СК, в которой описаны эти объекты. Плюсы:Точные расчеты,

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

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

Идея алгоритма:1. Удаляются из каждого объекта те ребра или грани, которые

Для каждого объекта сцены: Вычислить уравнение плоскости для каждой грани объекта.Вычислить

Выполняется проверка: существуют ли такие отрезки, которые перекрываются другими объектами на

Работает алгоритм в пространстве изображения. z-буфер - это отдельный буфер глубины,

Схема работы

1. Заполнить буфер кадра фоновым значением интенсивности или цвета.2. Заполнить z-буфер

Недостатки алгоритмаОсновной недостаток алгоритма с Z-буфером - большой объем требуемой памяти.

Преимущества Прост в аппаратной реализацииРазнородность использующихся примитивов – не ограничиваемся только

Алгоритм A-буфера Алгоритм является расширением метода буфера глубины (в названии использована

Описание работыКаждая позиция в А-буфере имеет два поля. - поле глубины:

Методы трассировки лучей Прямая трассировка. В методе прямой трассировки генерируется пучок лучей,

Многоугольники сначала упорядочиваются в направлении от заднего плана к переднему. В

Недостаткипри некотором расположении граней этот алгоритм вообще не может дать правильного

Работает в пространстве изображения. В пространстве изображения рассматривается окно и решается

1. Проекция грани полностью накрывает область (рис. d);2. Проекция грани пересекает

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

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

Похожие презентации

Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:
Алгоритмы, работающие в

Работают в физической СК, в которой описаны эти объекты.
Плюсы:
Точные расчеты,

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

Идея алгоритма:
1. Удаляются из каждого объекта те ребра или грани, которые

Для каждого объекта сцены:
Вычислить уравнение плоскости для каждой грани объекта.
Вычислить

Работает алгоритм в пространстве изображения.
z-буфер - это отдельный буфер глубины,

1. Заполнить буфер кадра фоновым значением интенсивности или цвета.
2. Заполнить z-буфер

Недостатки алгоритма
Основной недостаток алгоритма с Z-буфером - большой объем требуемой памяти.

Преимущества
Прост в аппаратной реализации
Разнородность использующихся примитивов – не ограничиваемся только

Алгоритм A-буфера
Алгоритм является расширением метода буфера глубины (в названии использована

Описание работы
Каждая позиция в А-буфере имеет два поля. - поле глубины:

Методы трассировки лучей
Прямая трассировка. В методе прямой трассировки генерируется пучок лучей,

Многоугольники сначала упорядочиваются в направлении от заднего плана к переднему.
В

Недостатки
при некотором расположении граней этот алгоритм вообще не может дать правильного

Работает в пространстве изображения.
В пространстве изображения рассматривается окно и решается

1. Проекция грани полностью накрывает область (рис. d);
2. Проекция грани пересекает