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

?ГБ 0«

.8 ДО

ДОНЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи

УДУГАМА ЛИЛДЖАНАКА САВИТРА КОР АЛА (Шри Ланка)

ОРГАНИЗАЦИЯ СИСТОЛИЧЕСКОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ДЛЯ СИНТЕЗА ИЗОБРАЖЕНИЙ МЕТОДОМ ИЗЛУЧАТЕЛЬНОСТИ В РЕЖИМЕ РЕАЛЬНОГО ВРЕМЕНИ

Специальность 03.13.yg- "Вычислительные машины» системы и сети, элементы и устройства вычислительной техники и систем

управлении"

Автореферат диссертации на соискание ученой степени кандидата технических наук

Донецк - 1996

Диссертация является рукописью

Работа выполнена в Донецком государственном техническом университете на кафедре "Электронные вычислительные машины"

Научный руководитель - кандидат технических наук, доцент Вашков Е.А.

Официальные оппоненты- доктор технических наук, профессор Погорелый Сергей Демьянович; кандидат технических наук, доцент Вороной Сергей Михайлович.

Ведущая организация - Институт проблем моделирования в энергетике НАН Украины (г. Киев).

Защита состоится 25 апреля 1996 г. в 14 часов на заседании специализированного совета К.06.04.01 Донецкого государственного технического университета по адресу, 340000, г.Донецк ул. Артема, 58, корп. 1, ауд. 201.

Отзывы на автореферат направлять по адресу. 340000, г.Донецк ул. Артема, 58, ученому секретарю ДГТУ.

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

Автореферат разослан 25 марта 1996г.

Ученый секретарь специализированного совета,

кандидат технических доцент

Мокрый Г.В.

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность и степень последовательности темы. Одной из бурно развивающихся в настоящее время областей вычислительной техники является машинная (компьютерная) графика, находящая широкое применение в различных областях науки и техники, например, в медицине, в физике, в химии и т.д. Одной из главных задач машинной графики является генерация реалистических изображений в реальном масштабе времени, которая используется для авиатренажеров, САПР, производство кино, реклам и т.д.

Системы генерации изображений в реальном масштабе времени должны иметь высокую производительность, то есть должны генерировать 25 - 40 кадров в секунду (25 - 40 мс/кадр). Проблемами синтеза графических систем реального времени занимаются многие институты как в странах СНГ, так и за рубежом. В качестве примера можно утазать разработанные в институте автоматики и автометрии СО АН России для авиа- и космических тренажеров системы синтеза визуальной обстановки реального времени. Кроме того, изображения должны сохранить реалистичность синтезируемой сцены. Наиболее распространенными методами получения таких изображений являются методы трассировки лучей и излучательности. Однако их применение требует больших затрат времени. При использовании таких методов в реальном времени следует программно и аппаратно ускорить вычислительные процессы.

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

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

Идея работы заключается в ускорении этапа определения видимых поверхностей с помощью построения вычислительных систолических структур на базе быстрого алгоритма вычисления точки пересечения луча с объектом.

Основные задачи. Для достижения цели ставятся и решаются

следующие задачи:

1. Получение оценок трудоемкости известных алгоритмов вычисления точки пересечения луча с объектом с целью выбора оптимального варианта для применения в методе излучательнос-ти.

2. Разработка быстродействующего алгоритма вычисления точки пересечения луча с объектом для ускорения процесса синтеза изображения.

3. Разработка структуры вычислительной системы для систем визуализации в режиме реального времени на базе метода излучательности.

4. Разработка способов построения и организация вычислительного процесса в СБИС систолической структуры, ориентированной на этап определения видимых поверхностей.

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

Теоретическая ценность, практическая значимость и новизна

исследований

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

Практическая значимость и новизна. Разработаны структуры пикселного процессора (ПП) на основе алгоритма обратного параметра и организация процессора определения видимости (ПОВ) на базе пикселного процессора. Процессор определения видимости позволяет повысить производительность вычислительных систем для. синтеза изображения за счет исключении операции умножения и деления. Данный процессор определяет видимые поверхностей сцен со скоростью более 1,6 млн. полигонов/с для объектов со средней шириной проекции не более 50 пикселов. Эквивалентная производительность процессора - более одного миллиона MIPS.

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

Положения. Установлена возможность исключения операций

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

Результаты. Основные результаты работы, выносимые на защиту:

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

2. Методика и результаты оценки трудоемкости алгоритмов вычисления точки пересечения луча с объектом.

3. Способ организации систолической вычислительной системы синтеза изображений в режиме реального времени на основе алгоритма обратного параметра.

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

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

Методология и методы исследования. Бри решении поставленных задач в работе использованы методы аналитической геометрии, линейной и векторной алгебры, теории вероятности и математической статистики, методы математического и программного моделирования.

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

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

Уровень реализации, внедрение научных разработок

Тематика диссертационной работы и использование ее результатов связаны с выполнением госбюджетной НИР Г21-91 "Разработка архитектуры вычислительных комплексов систем синтеза визуальной обстановки для индивидуальных тренажеров транспортных средств".

Способ организации вычислительной системы и метод ускорения процесса синтеза высококачественных изображений окружающей обстановки использованы в ОАО "Институт КМШИгипро-газ" при разработке технических предложений по созданию системы визуализации проектно-конструкторских решений в области промышленного строительства.

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

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

Апробация работы. Основные научные результаты диссертационной работы докладывались и обсуждались:

- на международной конференции KDS-95 в г. Ялта 1995г;

- на семинарах отдела N22 отделения гибридных моделирующих и управляющих систем в энергетике Института проблем моделирования в энергетике HAH Украины;

- на семинарах кафедры ЭВМ ДонГТУ.

Публикации. Основные результаты диссертации отражены в 4 печатных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, изложенных на 164 страницах машинописного текста, содержит 33 рисунка, 20 таблиц, список литературы из 118 наименований и приложения.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы исследований и указывается логическая взаимосвязь глав.

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

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

Алгоритмы точки пресечения луча с объектом является вычислительной основой метода трассировки лучей и время расчета пересечения может достигать 95% всех временных затрат. Поэтому предложена классификация метода трассировки лучей на основе алгоритмов определения точки пересечения прямолинейного луча с объектом. Эти алгоритмы также интенсивно используются в методе излучательности при вычислении коэффициентов формы и при определении видимых поверхностей. Приведены известные алгоритмы вычисления точки пересечения луча с объектами, представленные в виде многогранников, образованных плоскими гранями и модели закраски. Также рассмотрены способы ускорения метода трассировки лучей и излучательности. Кроме того, проводится анализ архитектур вычислительных систем для синтеза изображения. На основе проведенных анализов формируется цель и задачи исследования.

Во второй главе предлагается новый алгоритм (алгоритм обратного параметра) вычисления точки пересечения луча визирования с объектом. Объекты задаются как выпуклые плоские многогранники.

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

п-г = D, (1)

где D - константа,

п - единичная нормаль к плоскости (nx,ny,nz),

г - вектор произвольной точки на плоскости.

Луч визирования задается параметрическим уравнением:

r(t) = Se + tc, (2)

где se - вектор начальной точки луча (sx,sy,sz), с - направляющий вектор луча (сх,су,с2), t - параметр (t>0).

В уравнении (2) вектор с не нормируется. Для определения точки пересечение луча с плоскостью, в формулу (1) подставляется значение г из уравнения (2), так как точки пересечения имеют одну и ту же координату для уравнения плоскости и луча: Num

е = --, (3)

Den

где Num => D - n-se, Den = n-c.

Знаменатель (3) можно представить следующим образом: Den = nxcx + nyCy + nzcz (4)

Предположим, что синтезируется изображение методом трассировки лучей для экрана с растром рхд. Пусть расстояние между пикселами экрана по горизонтали а, по вертикали - Ь. С учетом этого координаты точки экрана Огэ,Уэ)> cx,cy,cz можно заменить на x3,y&,d. При трассировке луча через каждый пиксел экрана можно двигаться по вертикали или по горизонтали.

Если принять строчную развертку по вертикали, уравнение (4) можно записать в следующем воде: Denn = ЛхХэ + ЛуУэ + nzcf, Denij+i = пхх8 + лу(уэ + b) + nzd = Den u + nyb, где i = 1,2,...,р, j = 1,2,...,g. Если разворачивать по горизонтали, получим Deni+n - Denn. + пха. Обозначим

кх = пха, ку = пуЬ.

Так как в уравнение (3) числитель Num будет постоянным для несущей плоскости при постоянном расположении наблюдателя, можно преобразовать (3) для лучей визирования во всех пикселах экрана при строчной развертке по вертикали следующим образом:

^ij = tij-l + ку >

где х = 1/t, Ку' = ky/Wum.

При развертке по горизонтали будет следующий вид

= ti-ld + ^х >

где кх = kx/Num.

Запомнив предварительно начальные значения tjj, Denn i=0, J-о и кх', ку', кх, ку для каждой грани объекта, можно вычислить соответствующее обратное значение параметра t (t) и Den несущей плоскости для каждого луча визирования, и следовательно, можно проверить пересекается ли данный луч с текущим объектом.

Проверка пересечения луча с объектом осуществляется следующим образом: если минимальное значение t для видимых граней (tin) выпуклого объекта больше максимального значения %

для невидимых граней (тои0 этого же объекта, то луч пересекает объект, так как существенны только t > 0. В рис.1 приведена псевдокод выполнения алгоритма обратного параметра.

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

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

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

Теоретический анализ показывает, что для вычисления глубинного параметра с погрешностью не более 1 мм и правильного определения видимой плоскости разрядность ПП при глубине сцены до 10 км должна быть не менее 57 бит, а при глубине 100 км - не менее 64 бита. Выполнена экспериментальная проверка полученной оценки разрядности. Эксперименты проводились с помощью программы, которая вычисляет параметр t и определяет точку пересечения по известному алгоритму, описанному в главе 1. Результаты вычислений сравниваются с х и точкой пересечения, определенной по алгоритму обратного параметра. Результаты эксперимента подтверждают правильность теоретической оценки.

Также приводится три способа организации систем генерации изображений на базе транспьютеров:

- систолической обработки граней;

- построчной генерации изображения;

- векторной системы генерации изображения;

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

Алгоритм обратного параметра

Предварительные вычисления to.о. Deпо. оj Num, кх > ку )

кх, ку для каждой грани каждого объекта; for i ;= 1 to р do begin

для каждой грани каждого объекта

вычисляются ti.o и Derii, о for j := 1 to q do begin

n0b_hit = 0; npi^hit = 0; thit = 0;

for n_obj 1 to n do begin

hlt_p] = 0; Xin := tout •'= 0;

for л_pl . = 1 to л do begin

tij : = ti.j-i+ky'; Dent. Л Derii.i-i+kv; if Dent, i ( 0 then {плоскость не видима) if tij > 0 then begin

if tij ■> tout then tout tij; end

else tin •'= 0;

else {плоскость видима}

if ("tij > 0) & (Хц <" tirJ then begin

tin -•= tjj; hit_pl := n_pl; end

end

if (hit_pl*Ci) & ftln.>tout; (rin>Xhit) then begin

thit-'=tin; npl_hit•' =bit_pl; Лоь_Ьit: =n_obj; end

end

Определение интенсивности пиксела видимой точки

прi_hit -й грани Лоь_ъ i t so объекта; Отображение пиксела; end

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

В четвертой главе приводится организация пикселного процессора, на базе которого строится процессор определения видимости (ПОВ). Структурная схема разработанного пикселного процессора приведена на рис.2.

1шкселный процессор содержит сумматор (SM), формирующий два признака результата г и s, схему сравнения (Cm), на выходе которой устанавливается единичный сигнал с, когда значение входа А больше, чем значение входа В. Кроме этого, в ПП находится шесть 64-разрядных регистров, два 24-разрядных регистра, один 5-разрядный регистр, три триггера, девять буферов третьего состояния и блок управления (БУ). Данные поступают в ПП в виде токенов по входной шине Input и выдаются с задержкой в один такт по выходной шине Output. Найденные параметры выдаются из ПП по VT магистрали. Синхронизация работы пикселных процессоров осуществляется сигналами, которые передаются между ПП по шине управления Ctrl.

Сумматор по управляющему сигналу от БУ либо пропускает код на иине Input без изменения, либо суммирует его с содержимым регистра RGh и устанавливает признаки и (z=l, если результат не равен 0) и s (s=l, если результат отрицателен). Полученные значения 2 и s передается в блок управления через Гz и Ts триггеры, соответственно с задержкой в один такт.

Регистр RGh используется для хранения значения ку или ку', a RGres всегда принимает выходные значения сумматора. Регистр ШI сохраняет 5-разрядную команду и передает это значение в блок управления. Регистр Шрагр сохраняет цвет или идентификационный код грани объекта, пересекающейся с лучом, и передает значение в регистр Шраг, когда грань становится видимой до этого момента. В конце обработки всех

Структурная схема пикселного процессора

Rg Rg

pap per

VT магистраль

Ctri

"ВТ

-ПЖ

RG

3

max

RGtin

If

RGot?

Output

RGtout

\YJ

RGeps

Ts

x1,x2,...,xn

Tc

Tz

* * *

БУ

Ctrl

—►>

объектов в регистре Я3раг становится окончательным цвет или идентификационный код граней данного пиксела. Регистр RGtin сохраняет значение t для видимых граней, a RGtout - для невидимых. Регистр RGobj содержит значение t ближайшего объекта для данного пиксела до текущего момента. Регистр RGeps сохраняет отрицательные значения погрешности (eps). Триггер Тс использует для задержки сигнал с на следующий такт (с'). Для сравнения регистры Ш0ы. RG tout, RGens передают свои значения только в шину В, a RGres - в шину А. Но регистр RGtm передает шину А и В. Кроме того, максимальное значение передается в шину А. Код из регистра RGres в каждом такте выдается на шину Output, связанную со следующим Ш.

Организация вычислений предусматривает три вида токенов: токен плоскости (Т_Р1п), объекта (T_Obj) и столбца (Т_Со1). Каждый токен обрабатывается в ПП за 4 такта. В начале выполняется инициализация в каждом ПП с помощью подачи токена Т_Со1. Сразу после этого токена следует передача по очереди остальных токенов каждого столбца. Цепочки токенов для каждого столбца организуются следующим образом: в начале следуют токены 7_Р1п одного объекта, завершающиеся токеном TjObj, затем токены Т_Р1п следующего объекта, завершающиеся токеном T_pbj. И так продолжается передача токенов плоскости всех объектов синтезируемой сцены. В конце всех объектов следует токен Т_Со1. При этом передаются результаты данного столбца на магистраль VT и также выполняется инициализация ПП для следующего столбца. При необходимости в цепочку токенов добавляются пустые токены, так как суша кодов цепочки токенов не стала меньше, чем количество ПП. Для последнего столбца при любом случае добавляется только //п-1 пустых кодов, где Л?п - количество ПП в линейке ПОВ.

Во всех типах токенов в первом такте подается команда токена. Токен Т_Со1 имеет команду Col и цвет фона, а токен Т_Р1п подает команду Pin, имеющий 3 разных вида в зависимости от значения Num, так как устанавливаются разряды и As команды токена. Если Mum=0, то разряд ,?z=0, иначе Az=t. Если Л2=1, то As=1 (когда NumО), либо As=0 (когда Num>0). В зависимости от значения Az содержание токена T_Plr¡ для 2 и 3 тактов имеет следующие значения: при Az=1, во втором такте ку', а в третьем - t, а при Л2=0, во втором такте ку, а в

третьем - Den. В последнем такте всегда передается цвет плоскости. Токен T_0bj имеет только команду Obj.

В первом такте полученные из Input значения записываются в регистр Шгез и старше 5 разрядов - в регистр Шь В остальных тактах Ш выполняет определенную работу по принятой команде.

Во втором такте при обработке токена TjJol входные значения Input записываются в регистр Шрагр> поскольку второй код токена Т_Со1 цвет фона (ВС). Содержимые Шраг и Ш0ьз передаются в магистраль VT. Если получена команда Pin, то входной код записывается в регистр Шь- Если команда Obj, то формируется признак видимости объекта (Tin>t0ut), для чего в Cm сравнивается содержимое Шип и PGtout-

В третьем такте при получении команды Col в регистр Шип заносится максимальный код, а в RGtout и Ш0ы - минимальный. Кроме того, Шраг принимает значение из регистра ШрагР - код цвета фона. Если для данного пиксела луч не пересекается ни с одним объектом, на экране будет выводиться фоновый цвет. При получении команды Pin SM суммирует входной код . с содержимым Шь и результат заносится в регистр Шгеа. При этом реализуется либо xi+t~xi+ky', либо Denn-i^Deni+ky в зависимости от значения флага Az. При получении команды Obj и значении сигнала с'=1, производится сравнение Шип с максимальным значением. При этом проверяется условие А/ах>Шип - есть ли пересечение луча с объектом.

В четвертом такте при получении команды Col ничего не происходит. Если получена команда Pin, то работа выполняется по признакам AZl As, z, s. Если Az=0, то сравнивается содержимое регистров RGres и RGeps■ Если сигнал с=0, то в регистр Шип записывается код 0. При Аг=1 анализируются признаки As и s. Если Л3=1 и s=0, то сравниваются значения в RGres и Шtout- Если сигнал с=1, то содержимое регистра RGres записывается в регистр BGtout- Если Д2=0 и s^O, то сравнение будет производиться с содержимым регистров Шгез и Шип- Если сигнал с=0, то значение Шгез будет записываться в регистр Шип, а входной код (Input) - в Шрагр. Если 4S=0 и s=l, то в регистре. Шьin записывается нуль. Если получена команда Obj и сигнал с'=1 будет происходить сравнение значений в регистрах Шип и Шоы- Эта проверка производится для получе-

ния ближайшей точки пересечения луча с объектом. Если с=1, то содержимое регистра RGtin записывается в регистре Ш0ы, а регистр RGpаг принимает код, записанный в регистр /Й?рагР-Кроме того, так как объект закончился, в регистр RGun заносится максимальный код, а в регистр ffitout - минимальный, для обработки следующего объекта.

В таком порядке выполняется работа одного Ш. Располагая последовательно ПП, можно организовать систолический канал для изображения одного столбца пикселов. После проталкивания всех токенов Т_Р1п и T_Obj через линейку ПП, в регистрах RGobj будут храниться значения параметров t видимой точки грани некоторого'объекта, а в Шраг - цвет или идентификационный код видимой плоскости... Пропуск завершающего цепочку токена Т_Со1 вызывает последовательный вывод из каждого ПП на магистраль VT пары слов: цвет или идентификационного кода плоскости и значения параметра х. За токеном сканирующего столбца должна следовать цепочка токенов Pin и Obj нового столбца и так далее, пока не будет обработан весь кадр.

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

t = (max(//K,F(Mn/4)4) (Р - 1) + NK + Nn + 3)tt, где NK - количество кодов в цепочке токенов для одного столбца, NK = 4((m + l)n + 1);

F(z) - округление аргумента 2 в большую сторону;

tt - длительность такта процессора.

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

Производительности ПОВ в зависимости от ширины изображения объекта и количества ПП, и эквивалентная производительность ПОВ приведена в рис.3. Производительность ПОВ составит более 1600000 граней/с для объектов, изображающих по ширине 50 пикселов, а эквивалентная производительность составит 100000 MIPS при 100 МГц, а когда 330 МГц более одного миллиона MIPS.

Производительность процессора определения видимости

256

1024

512

количество ПП Ширина изображения объекта в пикселах

50 е==1 100 ГР^Л 250 500 И=Н 1024

1.27

Эквивалентная производительность процессора определения видимости

У

У..............................

/

/

256 512

Количество ПП Длительность такта

—■— 3 не —I— 5 не —ж— ■ □ 20 не х 50 не Рис. 3

10 не

В заключении перечислены основные научные и практические результаты диссертационной работы.

ЗАКЛЮЧЕНИЕ

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

Основные результаты работы заключается следующим:

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

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

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

4. Разработана структурная схема пикселного процессора на основе алгоритма обратного параметра и предложен его алгоритм функционирования. Предложена организация процессора определения видимости из линейки пикселных процессоров и найдена оценка времени этапа удаления для одного кадра. Сце-

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

5. Получены оценки разрядности информации при реализации алгоритма обратного параметра. Найдены зависимости разрядности от требуемой точности вычислений. Теоретически и экспериментально показано, что разрядность представления данных должна быть не менее 57 бит при максимальной глубине 1Q км, а 64 бит при 100 км. Определены аппаратные затраты для реализации процессора в виде БИС. Ориентировочно один пикселный процессор для своей реализации на КМОП структурах потребует не более 37000 транзисторов, что позволяет интегрировать в одной микросхеме 1024 процессора.

6. Получены оценки производительности процессора определения видимости. Производительность составляет более 1600000 граней/с для объектов со средней шириной проекции не более 50 пикселов, что в 1,5 раза выше существующих. Эквивалентная производительность составляет сто тысяч MIPS при тактовой частоте 100 МГц и количестве пикселных процессоров 256, для частоты 330 МГц и количестве пикселных процессоров 1024 -более одного миллиона MIPS.

Основные положения и результаты работы содержатся в следующих публикациях:

1. Башков Е.А., Удугама Л.С.К. Ускорение поиска точки пересечения луча с объектом в методе трассировки лучей. // Электронное моделирование, т.17, N 3, 1995. - с.11-17.

2. Udugama L.S.K. Photorealism in Computer Graphics. // Infolink, V.3, N 4, 1995. - p.22,35.

3. Башков E.A., Удугама Л.С.К. Организация системы синтеза изображений в реальном времени на базе метода излуча-тельности,- В кн.: Знания - диалог - решение: Труды международ. конф. KDS-95.- Киев, Ассоциация создателей и пользователей интеллектуальных систем, 1995.- с.254-261

4. Башков Е.А., Удугама Л.С.К. К оценки погрешности глубины при использовании Z-буфера в системах машинной графики. - Донецк, 1992, - 19с.: ил. - Дел. в УкрйНТЭИ, N 369-Ук93 от 04.03.93.

АН0ТАЦ1Я

Удугама Л.С.К. Орган1зац1я систолично1 обчислювально! системи для синтезу зображень методом випром1нювання у режим! реального часу.

Дисертац!я е рукописом на здобуття наукового ступеня кандидата тсхкхчних наук з спещальност1 05.13.08 - обчислв-вальн! машини, системи та мерёж!, елементи та пристро! обчислювально! технгки та систем керування. Донецький держав-ний технхчний унхверситет, Донецьк, 1996.

Запропоновано новий прискорений алгоритм визначення ви-димих поверхнь, виключаючий операцИ множення та Д1лення. Розроблена структура п!ксельного процесору на його основ!. Запропоновано систоличну срган!зац1ю ироцесора визначення видидастг з Л1н!йки п!ксельних процесор1в для синтезу зображень методом випром1нювання в режим! реального часу. Знайде-

*

но ошнки розрядност! npouecopiB, ix продуктивност! та апа-ратно! складность

ANNOTATION

Udugama L.S.K. The organization of a systolic computing' system for image synthesis by radiosity method in real time rates (the manuscript of the candidates thesis).

A thesis for a degree of candidate of technical sciences, speciality 05.13.08 - " Computers, systems and networks, elements and units of computer technique and control systems Donetsk state technical university, Donetsk, 1996.

New accelerated algorithm for determination of visible surfaces, excluding operations of multiplication arid division, was suggested. The structure of the pixel processor on its basis was developed. Organization of the processor of determination of visibility from an array of pixel processors for image synthesis by radiosity method in real time rates was suggested. Estimations of word length of processors, their productivity and hardware complexity were found."

КЛЮЧОВ! СЛОВА

обчислювальна система, тривим!рна компьютерна графика, синтез зображень, алгоритм визначення видимих поверхнь, спец!ал1зований процесор, п!ксельний процесор, продуктивность, реальний час.

Подп. в печать 21.03.96 г. Формат 60x84 1/i6- Бумага тип. №2 . Ризографическая печать. Усл. печ. л. 0,95. Усл. кр.-отт. 1,05. Уч.-изд. л. 0,8. Тираж 100 экз. Заказ №45/96

Донецкий государственный технический университет, 340000, г.Донецк. ул. Артема, 58 МЧП "ЛИК", г. Донецк, 230-й стрелковой дивизии, 16