Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР. 1 отображение просранства пользователя и машинного носителя 4
![]()
|
7 АЛГОРИТМЫ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ГРАФИЧЕСКОЙ ИНФОРМАЦИИПараллельные алгоритмы обработки графической информации предполагают использование математической модели описания трехмерного графического объекта в виде рецепторной трехмерной матицы, реализованной в памяти компьютера. Каждый рецептор несет в себе информацию об элементарном объеме пространства, в котором располагается графический объект (или объекты). Информация о нескольких соседних рецепторах объединяется и представляется в виде параметров бинарного вектора. Для случая монохромного изображения каждому рецептору трехмерного пространства соответствует один бит информации в памяти. Все параметры одного вектора обрабатываются параллельно. Очевидно, чем больше уровень дискретизации объекта (в данном случае число рецепторов), тем, с одной стороны, выше точность представления графической информации и, с другой, больше затраты времени требуется на ее обработку. Кроме того, с увеличением уровня дискретизации растет объем памяти, необходимой для представления в соответствующей форме заданного объекта. 7.1 Построение сечения объекта.Продемонстрируем принцип параллельной обработки графической информации на примере решения следующей, весьма часто встречающейся в машинной графике, задачи: выполнить сечение трехмерного объекта; заштриховать площадь сечения, используя заданный вектор штриховки. Поставленную задачу можно решить следующим образом. В зависимости от параметров плоскости сечения, за счет соответствующего преобразования координат, объект располагается в трех мерном системе координат, в которой плоскость сечения перпендикулярна одной из осей координат (предположим, что это ось Z). В этом случае плоскость сечения задается одним параметром – координатой zcч, и искомое сечение будет представлено в виде множества рецепторов, образующих параллельную матрицу с координатой zcч в трехмерном рецепторном кубе (Рис. Построение сечения объекта.-81). ![]() Рис. Построение сечения объекта.‑81 Предположим, что матрица сечения Q в память имеет вид, приведенный на Error: Reference source not founda), где каждая «1» соответствует одному элементу объема тела трехмерного отсекаемого объекта. Матрица изображена для случая, когда размеры по осям X составляет 24, а по оси Y - 20 рецепторов. Матрица организована в виде 20-ти векторов qi. Каждый вектор qi представлен 24 бинарными параметрами и соответствует одной i-ой горизонтальной строке матрицы сечения Q. На Error: Reference source not foundb) приведены матрица контуров сечения, которые необходимо сформировать при решении поставленной задачи. ![]() Рис. Построение сечения объекта.‑82 В рассматриваемом алгоритме границы матрицы сечения формируются по отдельным фрагментам в следующей последовательности: S1 – матрица левых фрагментов границ сечения ( a); S2 – матрица правых фрагментов границ сечения (3b); S3 – матрица верхних фрагментов границ сечения (4a); S4 – матрица нижних фрагментов границ сечения (b). Отдельные элементы матрицы левых фрагментов границ сечения ищутся с помощью следующего логического выражения: ![]() Матрица левых границ S1 составляется из совокупности векторов siл, каждый из которых представляет 24 рецепторов i-ой горизонтальной строки. Отдельные параметры векторов формируется согласно выражению (7.1-1). Элементы матрица, представляемые одним вектором siл, обрабатываются одновременно. Каждый si л вектор левых границ формируется следующим образом. Соответствующий вектор qi матрицы сечения Q сдвигается вправо на один разряд и инвертируется. Вектор, полученный после инвертирования, логически умножается на вектор qi. Таким образом, вычисления вектора s10л, соответствующего десятой строки снизу матрицы S1, выполняются следующим образом: 011111000000000000111110 - q10 - описание 10-ой строки исходного . . сечения; 001111100000000000011111 - q10 , сдвинутый вправо на один разряд; 110000011111111111100000 - отрицание сдвинутого влево q10 ; 010000000000000000100000 - s10л - результат логического умножения 1-ой . и 3-ой строк. Элементы матрицы правых фрагментов границ сечения ищутся с помощью следующего логического выражения: ![]() Матрица правых границ S2 составляется из совокупности векторов Riп, каждый из которых представляет 24 рецепторов i-ой горизонтальной строки. Отдельные параметры векторов формируется согласно выражению (7.1-2). Элементы матрица, представляемые одним вектором siп, обрабатываются одновременно. Каждый si п вектор правых границ формируется следующим образом. Соответствующий вектор qi матрицы сечения Q сдвигается влево на один разряд и инвертируется. Вектор, полученный после инвертирования, логически умножается на вектор qi. Таким образом, вычисления вектора s10п, соответствующего десятой строки снизу матрицы S2, выполняются следующим образом: 011111000000000000111110 - q10 - описание 10-ой строки исходного . сечения; 111110000000000001111100 - q10 , сдвинутый влево на один разряд; 000001111111111110000011 - отрицание сдвинутого влево q10 ; 000001000000000000000010 - s10,п - результат логического умножения 1-ой и . 3-ой строк. Элементы матрицы верхних фрагментов границ сечения ищутся с помощью следующего логического выражения: ![]() Матрица верхних границ S3 составляется из совокупности векторов sj в, каждый из которых представляет 20 рецепторов j-ой вертикальной колонки. Отдельные параметры векторов формируется согласно выражению (7.1-3). Элементы матрица, представляемые одним вектором sjв, обрабатываются одновременно. Каждый вектор sjв верхних границ формируется следующим образом. Соответствующий вектор колонки qj матрицы сечения Q сдвигается вправо на один разряд (на а) это соответствыет сдвигу кода соответствующей колонки вниз) и инвертируется. Вектор, полученный после инвертирования, логически умножается на вектор qj. ![]() Рис. Построение сечения объекта.‑83 Таким образом, вычисления вектора s10в, соответствующего десятой колонке слева матрицы S3, выполняются следующим образом: 00111100000000111100 – q10 -описание 10-ой колонки слева исходного . . сечения; 00011110000000001111 - q10 , сдвинутый вправо (вниз) на один разряд; 11100001111111110000 - отрицание сдвинутого вниз q10 ; 00100000000000100000 s10в - результат логического умножения 1-ой и . 3-ой строк. Элементы матрицы нижних фрагментов границ сечения ищутся с помощью логического выражения: ![]() Матрица нижних фрагментов границ S4 составляется из совокупности векторов sjн, каждый из которых представляет 20 рецепторов j-ой вертикальной колонки. Отдельные параметры векторов формируется согласно выражения (7.1-4). Элементы матрица, представляемые одним вектором sjн, обрабатываются одновременно. Каждый sjн вектор нижних границ формируется следующим образом. Соответствующий вектор колонки qj матрицы сечения Q сдвигается влево на один разряд (на а) это соответствыет сдвигу колонки вверх) и инвертируется. Вектор, полученный после инвертирования, логически умножается на вектор qj. Таким образом, вычисления вектора s10н, соответствующего десятой колонке слева матрицы S4, выполняются следующим образом: 00111100000000111100 – q10 - описание 10-ой колонки слева исходного . сечения; 01111000000001111000 - q10 , сдвинутый вверх (влево) на один разряд; 10000111111110000111 - отрицание сдвинутого влево q10 ; 00000100000000000100 s10,4 - результат логического умножения 1-ой и . 3-ой строк. ![]() Рис. Построение сечения объекта.‑84 Общая матрица границ сечения будет получена как логическая сумма четырех бинарных матрица: матриц левых S1, правых S2, нижних S3 и верхних S4 фрагментов границ: ![]() Решим задачу штриховки площади сечения. Введем базовый вектор линейной штриховки F, задающий шаг между штриховыми линиями. Размерность этого вектора соответствует количеству рецепторов в одной горизонтальной строке исходной трех мерной матрицы. Пусть для рассматриваемого примера этот вектор имеет вид: W= 100010001000100010001000. На основании базового вектора штриховки для каждой i-ой строки матрицы определяется вектор штриховки Ri. Элементы r j вектор штриховки Ri определяются по следующей зависимости: r j =w i+j, если угол наклона линий штриховки равен 450; r j =w i-j, если угол наклона линий штриховки равен -450, где: j – номер колонки матрицы сечения; i - номер строки матрицы сечения. Переход от исходной матрицы сечения Q к матрице заштрихованного сечения F осуществляется следующим образом. Формируется матрица F, каждый элемент которой при штриховке под углом 450 подсчитывается согласно выражению: f i,j = q i,j . w i+j (7.1-5) где f i,j , q i,j , r i+jявляются, соответственно, элементами матриц F,Q,R i. Формирование элементов матрицы F выполняется при использовании 24-х битовых векторов, каждый из которых представляет фрагмент матрицы, составляющий одну строку. Например, при формировании вектора 10-ой строки матрицы F (строки F10) используются 24-ти битовые векторы R10 соответствующий штриховке, и Q10, соответствующий 10-ой строке матрицы сечения Q. В этом случае, реализуя выражение (7.1-5), вектор F10 будет получен следующим образом: Qi =011111000000000000111110 Ri =000010000000000000001000 ___________________________ Fi =000010000000000000001000 Общий вид матрицы F приведен на Рис. Построение сечения объекта.-85а). Для получения требуемого вида площади сечения V необходимо объединить матрицу F и Sш, что можно сделать путем логического сложения этих матриц, при котором каждый элемент результирующей матрицы формируется согласно выражению: v i,j = s i,j sш i,j , где «» означает логическое сложение. (7.1-6) Формирование элементов матрицы V также выполняется при использовании 24-х битовых векторов, каждый из которых представляет элементы матрицы, составляющие одной горизонтальной строке. Например, при формировании вектора 10-ой строки матрицы V используются 24-х битовые векторы F10 и S10, соответствующий 10-ой строке матрицы сечения S. В этом случае, реализуя выражение (7.1-5), вектор V10 будет получен следующим образом: S10=010001000000000000100010 F10=000010000000000000001000 ________________________ V10=010011000000000000101010 Для рассматриваемого примера результирующая матрица V будет иметь вид, приведенный на Рис. Построение сечения объекта.-85 b). В рассматриваемом алгоритме обрабатываются одновременно несколько точек графического объекта, кроме того, при обработке выполняются простейшие логические операции. Поэтому данные алгоритмы достаточно ![]() ![]() Рис. Построение сечения объекта.‑85 быстродействующие. Недостатком такого подхода для обработки графической информации являются большие затраты памяти. |