Графика и обработка изображений. Фракталы icon

Графика и обработка изображений. Фракталы



НазваниеГрафика и обработка изображений. Фракталы
Дата конвертации28.08.2012
Размер171.55 Kb.
ТипДокументы
1. /algor/3D-2D.txt
2. /algor/3D.doc
3. /algor/Алгоpитм наложения линз.txt
4. /algor/Алгоритм пламени.txt
5. /algor/Вpащение pастpовой каpтинки.txt
6. /algor/Геометрия.doc
7. /algor/Геометрия2.doc
8. /algor/Графика.doc
9. /algor/Графика2.doc
10. /algor/Диофантовы уравнения.doc
11. /algor/Интегралы.doc
12. /algor/Интегральные уравнения.doc
13. /algor/Интерполяция функций.doc
14. /algor/Комбинаторика.doc
15. /algor/Комплексный анализ.doc
16. /algor/Криптография.doc
17. /algor/Наборы псевдослучайных чисел.doc
18. /algor/Нахождение собственных значений и собственных векторов матрицы.doc
19. /algor/Обыкновенные дифференциальные уравнения.doc
20. /algor/Операции над полиномами и степенными рядами.doc
21. /algor/Операции над полиномами.doc
22. /algor/Ортогональные полиномы.doc
23. /algor/Поиск.doc
24. /algor/Полиномиальные и трансцендентные уравнения.doc
25. /algor/Простейшие операции над матрицей.doc
26. /algor/Путь в двумерном лабиринте - волновой алгоритм.txt
27. /algor/Работа с датами.doc
28. /algor/Работа с разреженными матрицами.doc
29. /algor/Работа с формулами.doc
30. /algor/Работа с формулами2.doc
31. /algor/Решение систем линейных алгебраических уравнений.doc
32. /algor/Сортировка.doc
33. /algor/Суммирование рядов.doc
34. /algor/Теория графов.doc
35. html">/algor/Теория чисел.doc
36. /algor/Экстремумы функций.doc
37. /algor/Эффекты.txt
38. /algor/геом.doc
39. /algor/деревья какие-то.txt
Графика и обработка изображений. Фракталы
Геометрия
Геометрия
Графика
Графика
Интегралы
Интегральные уравнения
Интерполяция функций
Вычисление факториала
Комплексный анализ
Криптография
Нахождение собственных значений и собственных векторов матрицы
Обыкновенные дифференциальные уравнения
Операции над полиномами
Ортогональные полиномы
Поиск подпоследовательности в массиве (простой)
Полиномиальные и трансцендентные уравнения
Умножение матриц
Работа с датами
Работа с разреженными матрицами
Работа с формулами
Решение систем линейных алгебраических уравнений
Сортировка
Суммирование рядов
Теория графов
Наибольший общий делитель двух целых чисел (алгоритм Евклида)
Экстремумы функций
Афинные преобразования на плоскости

Графика и обработка изображений. Фракталы.

Удаление скрытых линий и поверхностей.

1  Классификация методов удаления невидимых частей


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

  1. По выбору удаляемых частей:
    удаление невидимых линий, ребер, поверхностей, объемов.

  2. По порядку обработки элементов сцены:
    удаление в произвольном порядке и в порядке, определяемом процессом визуализации.

  3. По системе координат:

    • алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями (объем вычислений растет как N2),

    • алгоритмы работающие в пространстве изображения, когда для каждого пиксела изображения определяется какая из N граней объекта видна (при разрешении экрана M×M объем вычислений растет как M2 ×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 в приложениях. Модификация должна учесть то, что для каждой строки сканирования теперь может обрабатываться не один многоугольник.

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

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

  2. Собственно заливка.

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


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

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




Рис. 18: Соотношения между окном экрана (сплошная рамка) и многоугольником (штриховая рамка)

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

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

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

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

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

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

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

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

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

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


Xmin  Wл    и    Xmax  Wп    и    Ymin  Wн    и    Ymax  Wв,






здесь

Xmin,Xmax,Ymin,Ymax

-

ребра оболочки




Wл, Wп, Wн, Wв

-

ребра окна

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


Xmin > Xп,    Xmax < Wл,    Ymin > Wв,     Ymax < Wн



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




Рис. 19: Ошибочное определение внешнего многоугольника как пересекающего при использовании прямоугольной оболочки

Проверка на пересечение окна многоугольником может быть выполнена проверкой на расположение всех вершин окна по одну сторону от прямой, на которой расположено ребро многоугольника. Пусть ребро многоугольника задано точками 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.




Рис. 20: Тест на охватывающий/внешний многоугольник

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


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

Предполагается, что экран у дисплея квадратный.
если в окне что-то есть, то алгоритм разобьет это окно.
окно разбивается на четыре одинаковых подокна.
каждый многоугольник сравнивается с каждым окном.
предполагается, что все значения заданы в системе координат экрана (пространстве изображения).
предполагается, что устранение нелицевых граней проведено до начала работы алгоритма.
Вершина - массив размером 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)

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

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

инициализировать черный фоновый цвет или интенсивность

Фон = О

Поместить окно размером с экран в стек

PUSH ОКНО(0, 0, Wmax)

while (стек не пуст)

взять окно из стека

Pop Окно(Хнач, Удач, Размер)

инициализировать счетчик многоугольников

Внешность = 0

Выполнить для каждого многоугольника габаритный тест с

прямоугольной оболочкой, чтобы найти внешние многоугольники

while (i <= N and внешность = О)

call Габарит(i, Многоугольник, Окно, Внешность)

i = i + 1

end while

если хотя бы один многоугольник не является внешним, то

разбить окно или изобразить пиксел

if Внешность > О then:

если размер окна больше пиксела, то разбить окно

if Размер > 1 then

Размер = Размер/2

Push Окно(Хнач + Размер, Унач + Размер, Размер)

Push Окно(Хнач, Унач + Размер, Размер)

Push Окно(Хнач + Размер, Унач, Размер)

Push Окно(Хнач, Унач, Размер)

else

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

call Покрытие(Вершина, N, Многоугольник, Окно; Номер)

if Номер > 0 then

call Визуализация(Окно, Многоугольник (Номер, 3))

else

Изобразить пустое окно

call Визуализация(Окно, Фон)

end if

end if

else

call Визуализация(Окно, Фон)

end if

end while

finish


подпрограмма реализации простого габаритного теста с

прямоугольной оболочкой

subroutine Габарит(i, Многоугольник, Окно; Внешность)

вычисление габаритов окна: Хлев, Управ, Хниз, Yвepx

Хлев = Окно(1, 1)

Хправ = Окно(1, 1) + Окно*) - 1

Yниз = Окно(1, 2)

Yвepx = Окно(1, 2) + Окно(1, 3) - 1

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

Внешность = 1

if Многоугольник(i, 8) > Хправ then Внешность = 0

if Многоугольник(i, 9) < Хлев then Внешность = 0

if Многоугольник(i, 10) > Yверх then Внешность = 0

if Многоугольник(i, 11) < Yниз then Внешность = 0

return


подпрограмма визуализации окна

subroutine Визуализация(окно, Интенсивность)

Setpixe(x, у, 1) - функция визуализации пиксела,

координаты которого (х, у), с интенсивностью I

for j = Окно(1, 2) to Окно(1, 2) + Окно(1, 3) - 1

for i = Окно(1, 1) to Окно(1, 1) + Окно(1, 3) - 1

Setpixe(i, j, Интенсивность)

next i

next j

return


подпрограмма, проверяющая, покрывает ли многоугольник центр окна

subroutine Покрытие(Вершина, N, Многоугольник, Окно; Номер)

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

если центр этого окна находится внутри многоугольника

поскольку вершины многоугольника перечисляются по часовой

стрелке, его внутренность лежит справа от контура

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

Номер = О

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

то Номер будет равен номеру того из них, который видим

присвоить Zmax начальное значение, равное нулю. Тут предполагается,

что все многоугольники расположены в положительном

полупространстве Z >= 0

Zmax = 0

вначале предположим, что покрывающих многоугольников

нет

Номер = 0

установить центр окна

ТочкаX = Окно(1, 1) + Окно(1, 3)/2

ТочкаY = Окно(1, 2) + Окно(1, 3)/2

для каждого многоугольника

for i = 1 to N

Индекс = Многоугольник(i, 1)

Для каждого ребра многоугольника

for j = 1 to Многоугольник(i, 2) - 1

T1x = Вершина(Индекс, 1)

T1у = Вершина(Индекс, 2)

T2x = Вершина(Индекс + 1, 1)

T2y = Вершина(Индекс + 1, 2)

заметим, что Точка, Tl, Т2 - это сокращения для

идентификаторов ТочкаX, ТочкаY и т. п.

call Видимость(Точка, Tl, Т2; Твидимость)

if Твидимость < 0 then 1

Индекс = Индекс + 1

next j

проверка относительно последнего ребра многоугольника

Т1х = Вершина(Индекс, 1)

T1у = Вершина(Индекс, 2)

Т2х = Вершина(Многоугольник (i, 1), 1)

Т2у = Вершина(Многоугольник (i, 1), 2)

call Видимость(Точка, Tl, Т2, Твидимость)

if Твидимость >= 0 then

call Вычислить(Вершина, i, Многоугольник, Окно; z)

if z > Zmax then

Zmax = z

Номер = i

end if

end if

1 next i

return


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

subroutine Видимость(Точка, P1, P2; Твидимость)

видимость Точка следует определить относително стороны P1-P2

Твидимость <0, если Точка невидима

=0, если Точка лежит на P1-P2

>0, если Точка видима

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

Sign - функция, принимающая значения -1,0,1 в зависимости

от того, будет ли знак ее аргумента отрицателен,

равен нулю или положителен

Раб1 = (ТочкаX - P1X) * (P2Y-P1Y)

Раб2 = (ТочкаY - P1Y)*(P2X-P1X)

Раб3 = Раб1 - Раб2

Твидимость = Sign(Раб3)

return

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

subroutine Вычислить(Вершина, i, Многоугольник, Окно; z)

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

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

наблюдения для этого пиксела

Мах - обозначение функции, вычисляющей максимум

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

Хцентр = Окно(1, 1) + Окно(1, 3)/2

Yцентр = Окно(1, 2) + Окно(1, 3)/2

определение координаты z многоугольника в центре пиксела

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

заметим, что многоугольник такого типа может совершенно

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

точек - например, в результате ступенчатости

if Многоугольник(i, 6) = 0 then

for j = 2 to Многоугольник(i, 2)

z=Max(Вершина(j, 3), Вершина(j -1, 3))

next j

else

вычисление z по уравнению плоскости многоугольника

А = Многоугольник(i, 4)

В = Многоугольник(i, 5)

С = Многоугольник(i, 6)

D = Многоугольник(i, 7)

z = - (А * Хцентр + В * Yцентр + D)/С

end if

return


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


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

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

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

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

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


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

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

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

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

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

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

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




Рис. 21: Определение пересечения луча и оболочки

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


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



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


d2 = (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, то луч не пересекает объекты, заключенные в оболочку.

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

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

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

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



Похожие:

Графика и обработка изображений. Фракталы iconДокументы
1. /Прэтт Э. Цифровая обработка изображений. 1982 Ч.1 Непрерывные изображения.djvu
2....

Графика и обработка изображений. Фракталы iconКомпьютерная графика Изучив эту тему вы узнаете: Виды графических компьютерных изображений
Большинство редакторов ориентированы не столько на создание изображений, сколько на их обработку
Графика и обработка изображений. Фракталы iconДокументы
...
Графика и обработка изображений. Фракталы iconКонтрольное задание 3 по теме «создание мультимедиаклипа по теме “Фрактальная геометрия”»
Но магнетизм темы таков, что увидевший однажды, забыть не сможет никогда. Фракталы – суть нашего мира… фракталы – математика во всей...
Графика и обработка изображений. Фракталы iconДокументы
1. /Бутаков Е.А. Островский В.И. Фадеев И.Л. Обработка изображений на ЭВМ. 1987.djvu
Графика и обработка изображений. Фракталы iconЦой Ю. Р., Спицын В. Г. Кафедра вычислительной техники
Трехэтапная обработка цифровых изображений с использованием эволюционирующих искусственных нейронных сетей*
Графика и обработка изображений. Фракталы iconSheet 1: Графика и мультимедиа
Мониторинг обученности учащихся 9 классов по теме "Кодирование и обработка графической и мультимедийной информации" (%)
Графика и обработка изображений. Фракталы iconКонспект урока №1 «Графика. Виды графики. Первоначальное знакомство с редактором TuxPaint»
Методы и приёмы обучения: объяснительно-иллюстративный; словесный (фронтальная беседа); наглядный (демонстрация компьютерной презентации);...
Графика и обработка изображений. Фракталы iconПлан-конспект урока по теме «Линзы. Построение изображений, даваемых линзами»
Образовательные : изучить действия собирающей и рассеивающей линз, ознакомить учащихся с экспериментальным получением изображений...
Графика и обработка изображений. Фракталы iconТема 17. Обработка изображений нет ничего, на что бы ни дерзнуло воображение человека
Воображение вещь хорошая. Но вытащить бомжа из подвала, отмыть, превратить в Аполлона, упаковать в спичечную коробку и отправить...
Графика и обработка изображений. Фракталы iconДокументы
1. /dsp01-Введение в цифровую обработку сигналов.doc
2. /dsp02-Цифровые...

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов