Удаление невидимых. Картинная плоскость. Классификация алгоритмов

1. Удаление невидимых

2. Картинная плоскость

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

3. Классификация алгоритмов

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

4.    Алгоритм плавающего горизонта

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

5. Алгоритм плавающего горизонта

6. Алгоритм плавающего горизонта

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

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

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

9. Удаление невидимых ребер

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

10. Алгоритмы, использующие список приоритетов

11. Алгоритм Варнока (Warnock)

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

12. Алгоритм Вейлера-Азертона (Weiler-Atherton)

Разбиение картинной плоскости можно производить не только
прямыми, параллельными координатным осям, но и по
границам проекций граней. В результате получается точное
решение задачи.
Предлагаемый метод работает с проекциями граней на
картинную плоскость.
В качестве первого шага производится сортировка всех граней
по глубине (front-to-back).
Затем из списка оставшихся граней берется ближайшая грань A
и все остальные грани обрезаются по этой грани. Если проекция
грани B пересекает проекцию грани A, то грань B разбивается
на части так, что каждая часть либо содержится в грани A, либо
не имеет с ней общих внутренних точек.
Таким образом, получаются два множества граней: Fin – грани,
проекции которых содержатся в проекции грани A (сюда входит
и сама грань A), и Fout – грани, проекции которых не имеют
общих внутренних точек с проекцией грани A.
Множество Fin обычно называют множеством граней,
внутренних по отношению к A.

13.

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

14.

Простая 3d сцена
Представление Z-буфера

15. z-буфур (Буфер глубины)

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

16. z-буфур (Буфер глубины)

Концептуально:
Sort (max zzxx
xy )
( x, y )
Sort (min zzxx
xy )
( x, y )

17. z- буфур

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-

18. z- буфур (dup)

- 10 - 12 - 14 - 16 - 18 - 20 - 22
-2 - 4 - 6 - 8
z
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-

19. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-

20. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
-
-
-10
-
-
-
-
-
-
-
-
-
-
-
-
-

21. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9

22. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
99

23. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
98

24. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
88

25. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
88

26. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
8
8

27. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
8
8
18

28. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
8
8
18
17

29. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
8
8
18
17
15

30. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
8
8
18
17
15
14

31. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
10
9
9
8
8
8
18
17
15
14

32. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

33. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

34. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

35. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

36. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

37. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

38. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
18
17
15
14

39. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
20
18
17
15
14

40. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
20
20
18
17
15
14

41. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
9
9
8
8
8
20
20
18
17
15
14

42. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
9
8
8
8
20
20
18
17
15
14

43. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
6
8
8
8
20
20
18
17
15
14

44. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
6
7
8
8
20
20
18
17
15
14

45. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
6
7
8
8
20
20
18
17
15
14

46. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
6
7
8
8
20
20
18
17
15
14

47. z- буфур : Render

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
6
7
8
8
11
20
18
17
15
14

48. z- буфур : Rendering (выполнено)

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
17
10
4
6
7
8
8
11
20
18
17
15
14
z

49. z- буфур : Итог

-2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22
z
17
10
4
6
7
8
8
11
20
18
17
15
14