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