Эффективные растеризационные методики с рекурсивным делением плоскости изображения и объектного пространства


1. ВВЕДЕНИЕ

Типичная система визуализации реального времени разделяется на два функционально независимых блока: геометрический процессор и видеопроцессор. Такое разделение не случайно и основано на существенном различии их функций. Функции генератора изображения при генерации сцены, можно выделить в следующие категории: создание (постановка) сцены, приоритезация, геометрические преобразования и видеопреобразование. Постановка сцены — процесс сбора математических описаний объектов, находящихся в этой сцене, который начинается со считывания данных с дисковых устройств хранения. Первым шагом в создании изображения является выбор объектов, которые могут быть увидены с данной точки наблюдения, построение сцены происходит постоянно с изменением точки наблюдения и различия между последовательными точками наблюдения обычно незначительны. Аналогично и отношение приоритетов между объектами, которые определяют затенение, также меняется медленно во многих случаях. Приоритезация-это определение объектов, которые могут затенять другие менее приоритетные объекты. Подвижные объекты в базе данных осложняют обстановку, поскольку они должны быть приоритезированы не только по отношению друг к другу, но и по отношению к фиксированным объектам, поэтому существует ограничение на число подвижных объектов. Z-буфер имеет преимущества в разрешении приоритетных проблем, но имеет свои недостатки. Как и при обратно-приоритетном порядке записи каждый элемент изображения (пиксел) должен быть вычислен, даже если он и невидим. Буфер на кадр должен быть увеличен для хранения функции расстояния. Но более серьезным недостатком является проблема с фильтрацией и полупрозрачностью. Геометрические преобразования служат для преобразования математического описания объектов в трехмерном пространстве в описание в двухмерном пространстве координат экрана с учетом перемещения наблюдателя и перспективы. Видеопреобразование включает в себя все остальные вычисления, необходимые для генерации изображения — это растеризация, т.е. определение элементов изображения (пикселов) принадлежащих примитивам (многоугольникам), удаление невидимых поверхностей, интерполяция, текстурирование, фильтрация (антиэлайзинг), т.е. необходимо иметь разрешение на субпиксельном уровне, вычисление цвета с учетом тумана и генерация видеосигналов для устройства отображения. Полупрозрачные объекты повышают качество и реализм изображения, с помощью полупрозрачности осуществляется плавный переход между уровнями детальности, текстура и такие параметры, как цвет и полупрозрачность могут модулироваться интенсивностью, позволяя создавать широкий диапазон эффектов.

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

2. СИНТЕЗ ВИРТУАЛЬНОЙ СРЕДЫ С РЕКУРСИВНЫМ ДЕЛЕНИЕМ ПЛОСКОСТИ ИЗОБРАЖЕНИЯ

2.1 Фрейм-буферный метод (Frame-buffer technique)

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

2.1.1 Растеризатор системы визуализации "Альбатрос"

В основу архитектуры видеопроцессора системы "Альбатрос" положена идея рекурсивной процедуры деления экрана [1-5], локализующей внутреннюю область многоугольников в процессе растрирования. Основными характерными чертами метода являются описание многоугольников наборами прямых, проходящих через ребра, и рекурсивное деление экрана на клетки, площадь которых уменьшается в 4 раза с каждым шагом деления. С целью достижения необходимой производительности видеопроцессора деление экрана в конвейере продолжается не до пиксела, а до клетки 4 х 4 пиксела. Затем в следующем вычислительном каскаде конвейера определяется положение фрагмента многоугольника в клетке одновременно относительно всех 16 пикселов. Для устранения дефектов, связанных с дискретностью телевизионного растра, определение принадлежности элемента изображения многоугольнику осуществляется на повышенном разрешении растра: каждый пиксел разбит на 16 субпикселов. В результате формируется субпиксельный код фрагмента, который сравнивается с кодом маски клетки, сформированным из раннее обработанных более приоритетных многоугольников. В коде фрагмента остаются отмеченными только видимые субпикселы, а код маски дополняется от вновь замаскированных субпикселов. Память масок модифицируется, а субпиксельный код фрагмента сворачивается в площади пикселов и передается в четыре идентичных канала вычисления цвета. Координаты, цвет и площадь видимой части многоугольника в пикселе поступают в блок видеобуфера, который содержит память для цвета всех пикселов экрана. Результирующий цвет пиксела есть взвешенная сумма цветов видимых фрагментов многоугольников, попавших в пиксел.

2.1.2 Оценка эффективности фрейм-буферного метода с квадратной организацией памяти кадра

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

1. Мозаичный, в котором при увеличении количества многоугольников P в сцене и уменьшении их площади (A-количество пикселей в многоугольнике), глубинная сложность D остается постоянной. Время отклика t есть число модифицируемых пикселей, умноженное на время цикла Tcyc для каждого пиксела, с учетом множителя ускорения Ssqt для квадратной фрейм-буферной организации, изложенной выше.

t=N*D*Tcyc/Ssqt, где N-количество пикселей в экране.

2. Немозаичный, в котором при увеличении количества многоугольников и увеличении глубинной сложности, размер многоугольников остается постоянным. Время отклика t в этом случае есть количество многоугольников P умноженное на их среднюю площадь A и время цикла Tcyc, также с учетом множителя ускорения Ssqt.

t=P*A*Tcyc/Ssqt

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

P*A=N*D

Средняя высота H_avg или ширина W_avg многоугольника является хорошим приближением к действительным распределениям площади A и пропорциональна:

H_avg=W_avg=Ц(A)=Ц(N*D/P)

Статистические исследования показали, что для большинства графических баз данных теоретические и практические оценки производительности системы "Альбатрос" совпали [4,5].

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

2.1.3 Многоуровневое маскирование

Одной из трудоемких операций, определяющих количество отображаемых за кадр многоугольников, является преобразование их в пикселы, с одновременным удалением невидимых частей отображаемой обстановки. В некоторых устройствах (например, система визуализации "Аксай") этот процесс осуществляется с предварительным преобразованием многоугольников в сегменты-отрезки, образованные от пересечения ребер многоугольников со строками телевизионного растра [6]. При таком разложении многоугольников в растр не очень эффективно работают маски, так как они не сформированы в течение большей части кадра и приходится вычислять сегменты для многоугольников или их частей, которые закрыты более близкими к наблюдателю объектами. Процесс преобразования многоугольников в сегменты, а затем в пикселы осуществляется последовательно, так же последовательно осуществляется и процесс заполнения масок с нижнего уровня на верхний, что замедляет процесс обработки отображаемой обстановки. В связи с тем, что исходя из среднестатистической формы отображаемых многоугольников, клетка является более адекватной формой разложения в растр, чем строка (сегмент) растра, использование многоуровневого клеточного маскирования, реализованного в каждом процессоре конвейера, путем сравнения занимаемых на данном уровне многоугольником клеток с клетками, хранящимися в памяти масок от предыдущих многоугольников, позволяет сократить число вычисляемых клеток, а значит и пикселов. Деление формируемых клеток на пересеченные и внутренние позволяет формировать маски на каждом уровне, а не только последовательно с нижнего уровня на верхний [1-5]. Использование механизма многоуровневого маскирования позволяет эффективно отбраковывать многоугольники или их фрагменты попавшие в уже занятые более близкими к наблюдателю многоугольниками области экрана. Тем самым уменьшается время обработки сцены. Отметим также, что зависимость времени обработки от глубинной сложности отображаемой сцены становится при многоуровневом маскировании нелинейной: увеличение глубинной сложности не приводит к существенному увеличению времени обработки сцены. Производительность видеопроцессора в большей степени определяется суммарным периметром многоугольников в сцене. В таблице 1 показана зависимость времени обработки для одного канала нескольких сцен от наличия многоуровневого маскирования на разных уровнях деления: 1-маскирование только на 7-м уровне, 2-на 6,7-м уровнях, 3-на 5-7-м уровнях, 4-на 1-7-м уровнях. Из таблицы 1 видно, что все сцены при наличии только маскирования последнего уровня не могут обработаться за время полукадра (20 мс).

Таблица 1

Тип сценыНижние уровниВерхние уровни
Ночной аэропорт1:23мс, 2:19.5мс3:18.8мс, 4:17.5мс
Авианосец1:22мс, 2:17мс3:16.6мс, 4:16мс
Аэропорт1:20.2мс, 2:15мс3:15.9мс, 4:13.8мс
Бронетранспортер1:25мс, 2:17.6мс3:17 мс, 4:15.4мс
"Буран"1:21мс, 2:14.7мс3:14.3мс, 4:13.9мс

Примечание: Несколько систем визуализации "Альбатрос" изготовлено и установлено в ЦПК им. Ю.А. Гагарина (с 1990 г.) для тренировки космонавтов.

2.2 Виртуальная буферная методика (Virtual Buffer Technique — Система визуализации "Ариус")

Виртуально-буферные методы — это растеризация примитивов в промежуточные порции экранной памяти и повторное использование этих виртуальных порций для конструирования полного кадра. В семействе систем визуализации "Ариус" применена виртуальная методика, суть которой заключается в наличии промежуточной памяти фрагментов. Данная методика позволяет на цифровых сигнальных процессорах (DSP TMS320C80 фирмы Texas Instruments) [7-12] реализовать субпиксельную фильтрацию в реальном времени. Кроме того, снижаются требования к пропускной способности шин для подкачки текстурных карт и передачи пиксельного потока в видеобуфер, поскольку в память кадра происходит только запись готовых порций кадра, без модификации последней, а также уменьшается количество вычислений, за счет применения итерационных вычислений по-шаговыми приращениями и эффективного механизма маскирования. В данной работе получили дальнейшее развитие идеи, описанные в [1-6]. В соответствии с ростом производительности вычислительных систем повышаются требования к качеству и реализму сцен, синтезируемых компьютерными генераторами изображений. Повышение реализма достигается не только усложнением деталей сцен и увеличением производительности, но и воспроизведением специальных визуальных эффектов (различного вида текстура, газ, дым, дождь, снег и др.) Также значительно расширяются функциональные возможности систем. Ниже перечислены некоторые требования к системам визуализации для тренажеров:

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

Специализированные наборы микросхем, являющиеся основой большинства акселераторов трёхмерной графики, пока не подходят для решения подобных задач. Несмотря на то, что некоторые из них имеют достаточно высокую производительность для работы в реальном времени, их функциональные возможности сильно ограничены. Это связано с тем, что они в первую очередь ориентированы на другой круг задач — САПР и трёхмерные игры. Поэтому в качестве вычислительного ядра компьютерной системы визуализации "Ариус" был выбран сигнальный процессор TMS320C80 фирмы Texas Instruments. Тем самым, при достаточно высокой производительности была сохранена программируемость системы на всех уровнях, что дало возможность реализовать необходимые визуальные эффекты с минимальными затратами. В отличие от большинства систем визуализации, использующих традиционный фрейм-буферный (frame-buffer) подход, система "Ариус" построена с применением так называемой виртуальной методики. Отличительными чертами данного метода (как уже было сказано) являются разделение экрана на клетки и конвейеризация вычислений с использованием промежуточного описания кадра в виде списка примитивов.

В системе "Ариус" изображение формируется из спанов (span) — клеток экрана 8х8 пикселов. В настоящее время такие клетки называются тайлы (tiles). Фиксированная сетка спанов (так привычнее) позволяет вычислять точные значения параметров отображения граней только в узловых точках. Значения в промежуточных точках восстанавливаются билинейной интерполяцией по четырём узлам. Кроме того, полностью локализуются вычисления, связанные с отображением текстуры. Размер спанов выбран исходя из баланса критериев качества изображения, объёма локальной памяти процессора и вычислительной нагрузки.

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

Загрузку системы и геометрические преобразования осуществляет host-процессор (Pentium для IBM-совместимых компьютеров). Данные в систему "Ариус" поступают по шине PCI. Модуль SG (span generator) выполняет первый этап вычислений — преобразование поступающих на вход системы приоритетно упорядоченных геометрических примитивов в промежуточное описание кадра. Примитивами промежуточного описания являются фрагменты пересечения геометрических примитивов со спанами. Второй этап вычислений — обход списка примитивов, определение видимости и цвета пикселов возложен на модули VP (video-processor). Благодаря применению виртуальной методики вычисления в VP легко распараллеливаются. В зависимости от требуемой производительности система может содержать до двух модулей SG и до четырёх модулей VP.

Несколько систем визуализации "Ариус" изготовлено и установлено в ЦПК им. Ю.А. Гагарина (с 1997 г.) для тренировки космонавтов.

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

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

Оба подхода основаны на задании границ (рёбер) граней в плоскости проектора с помощью кривых линий (проекций пространственных кривых, образованных пересечением купола с плоскостями рёбер). То есть плоскостями, проходящими через рёбра и началом системы координат наблюдателя. Это даёт возможность применить достаточно простые алгоритмы растрирования, использующие кватернарное (четверичное) дерево деления плоскости изображения. Метод растрирования плоских граней с рекурсивным делением экрана (о котором говорилось выше) может быть достаточно просто обобщен на кривые и даже на криволинейные поверхности свободных форм (о которых будет сказано ниже). Наиболее просто в методе рекурсивного спуска модифицируются коэффициенты кривых второго порядка. Для этого достаточно на каждом уровне деления модифицировать не только свободный член в уравнениях ребер F, но и коэффициенты D и E.

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

Ax2 + 2Bxy + Cy2 + 2Dx + 2Ey + F = 0, (1)

ax + by + c = 0. (2)

Коэффициенты обоих уравнений (A..F, a..c) вычисляются в ходе геометрических преобразований. Уравнение (2) определяет линию пересечения плоскости проектора с плоскостью, проходящей через начало отсчёта системы координат проектора параллельно плоскости ребра.

Во втором подходе рёбра граней задаются, как некие кривые, описанные параметрическими уравнениями вида:

Ax + By + C + Dt(x, y) = 0, (3)

где A, B, C, D — коэффициенты рёбер, полученные в ходе геометрических преобразований;

t(x, y) — параметр, нелинейно зависящий от x, y.

Эффективный способ вычисления параметра t(x, y) изложен в [13].

Параметр t(x, y) универсален и может быть использован для определения текстурных координат, линейной интерполяции интенсивности и генерации растровых огней.

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

В качестве элемента разложения, при преобразовании граней в пикселы телевизионного растра, предлагается использовать уменьшающуюся в четыре раза прямоугольную клетку, первоначальный размер которой равен размеру экрана. Совокупность клеток одинакового (i-го) размера, покрывающих экран, назовём i-ым уровнем деления. Считаем, что область экрана соответствует 0-му уровню, 1/4 часть экрана — 1-му, 1/4n часть экрана (n — целое) является пикселом телевизионного растра.

При анализе (тесте) взаимного расположения клетки i-го уровня деления (Qi) и грани, возможны следующие ситуации:

  1. Qi находится вне грани (в этом случае область экрана, соответствующая клетке Qi, исключается из дальнейшего рассмотрения);
  2. Qi находится внутри грани (в этом случае все пикселы, принадлежащие Qi объявляются принадлежащими грани);
  3. Qi частично перекрывается гранью (в этом случае клетка Qi объявляется "пересечённой" и делится на четыре клетки i+1-го уровня, расположение которых снова анализируется).

Алгоритм растрирования сводится к анализу взаимного расположения клетки Qi и границ грани, заданных уравнениями (1), (2).

Способность алгоритма распознавать "внутренние" клетки может быть использована для маскирования на каждом уровне деления, (что немаловажно при прямом приоритетном порядке обработки граней и большой глубинной сложности) и организации многоуровневого Z-буфера.

Тест Qi относительно линии, определяемой уравнением (2).

1. Перевод коэффициентов уравнения (2) в локальную систему координат клетки Qi
при делении клетки Qi-1.

Перевод сводится к модификации свободного члена уравнения (2):

C(i) = C(i-1) ± a ± b, (4)

C(i) - свободный член текущего уровня деления (С(0) = с);

С(i-1) - свободный член предыдущего уровня деления;

a, b - коэффициенты исходного уравнения (2).

2. Определение местоположения клетки Qi.

Если |a|+|b|>=|C(i)|, (5)

то клетка Qi — "пересечённая".

Если |a|+|b|<=|C(i)|,

то при

C(i) < 0 — клетка Qi не принадлежит грани; (6)

C(i) > 0 — клетка Qi находится со стороны грани.

Такая трактовка знака C(i) справедлива, если нормаль плоскости ребра показывает на полупространство, в котором расположена грань.

Тест Qi относительно линии, определяемой уравнением (1).

Запишем уравнение (1) в виде:

(ax+by+d)x + (bx+cy+e)y + (dx+ey+f) = 0, (7)

где a = A, b = 0.5B, d = 0.5D, c = C, e = 0.5E, f = F;

A..F — коэффициенты уравнения (1).

3. Перевод коэффициентов уравнения (1) в локальную систему координат клетки Qi
при делении клетки Qi-1.

Перевод сводится к модификации трёх коэффициентов уравнения (7):

D(i) = 2D(i-1) ± a ± b,

E(i) = 2E(i-1) ± b ± c,

F(i) = 2f' ± D(i) ± E(i),

f' = 2F(i-1) ± D(i-1) ± E(i-1), (8)

D(i)..F(i) - коэффициенты текущего уровня деления (D(0) = d, E(0) = e, F(0) = f);

D(i-1)..F(i-1) - коэффициенты предыдущего уровня деления;

a..c - коэффициенты исходного уравнения (15);

f' - некое промежуточное значение.

4. Определение местоположения клетки Qi. Если (|a|+|c|)/2 +|b|+|D(i)|+|E(i)>=|F(i)/2|, (9)

то клетка Qi объявляется "пересечённой".

Если условие (9) не выполняется, то при

F(i) < 0 — клетка Qi не принадлежит грани; (10)

F(i) >= 0 — клетка Qi находится со стороны грани.

Такая трактовка знака F(i) справедлива, если при подстановке в уравнение (1) координат точки, принадлежащей грани, получаем знак "плюс".

Примечание.

При введении апертуры фильтра условия (5), (9) могут быть записаны следующим образом:

(|a|+|b|)*Ea(i)>=|C(i)|, (5.1)

((|a|+|c|)/2 +|b|)*Ea2(i)+(|D(i)|+|E(i)|)*Ea(i)>=|F(i)/2|, (9.1)

где Ea(i) определяет значение апертуры i-го уровня деления. Целесообразно выбрать Ea(0)=Ea(1)=…=Ea(i)=2. Тогда

|a|+|b|>=|C(i)|/ 2,

|a|+|c|+2*|b|+|D(i)|+|E(i)>=|F(i)/4|.

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

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

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

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

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

1. Вводится уравнение "полосы" (т.е. совокупности параллельных прямолинейных границ, характеризующей кривизну ребра грани относительно определённого множества точек плоскости проектора), позволяющее определить местоположение клетки i-го уровня деления (Qi) относительно ребра грани.

Ax + By + C(i) + D(i)t(i, j) ± D(i)Et(i) = 0, (11)

A, B - коэффициенты при x, y исходного уравнения (3);

C(i) - свободный член линейной части уравнения i-го уровня деления;

D(i) - коэффициент нелинейной части уравнения i-го уровня деления;

t(i, j) - среднее значение параметра t(x, y) j-ой клетки i-го уровня деления (выбирается из таблицы);

Et(i) - величина, характеризующая разброс параметра t(x, y) внутри клетки i-го уровня деления (выбирается одинаковой для всех клеток одного уровня).

Отметим, что при переходе к более "мелкому" уровню деления (т.е. с i-го уровня к уровню i+1) значение Et(i) уменьшается, обеспечивая в конечном итоге заданную точность растрирования.

2. Модификация коэффициентов уравнения (11) при переходе в локальную систему координат Qi:

C(i) = 2C(i-1) ± A ± B, (12)

D(i) = 2D(i-1),

C(i), D(i) - коэффициенты текущего уровня деления (C(0) = C, D(0) = d);

C(i-1), D(i-1) - коэффициенты предыдущего уровня деления;

3. Местоположение Qi относительно ребра определяет пара неравенств:

|A|+|B|>|C(i) + D(i)t(i, j) + D(i)Et(i)|,

|A|+|B|>|C(i) + D(i)t(i, j) — D(i)Et(i)|

и знаки выражений

(C(i) + D(i)t(i, j) + D(i)Et(i)),

(C(i) + D(i)t(i, j) — D(i)Et(i)).

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

  • относительная простота геометрических преобразований;
  • возможность корректировки значений параметра t(x, y), учитывающей "неидеальность" проекционного купола.

К недостаткам данного подхода можно отнести:

  • присутствие динамической (или статической, если проектор неподвижен) таблицы, хранящей значения параметра t(x, y);
  • наличие операций умножения.

3. СИНТЕЗ ВИРТУАЛЬНОЙ СРЕДЫ С РЕКУРСИВНЫМ ДЕЛЕНИЕМ ОБЪЕКТНОГО ПРОСТРАНСТВА

Как уже было отмечено, в статье "Синтез виртуальной среды с применением аналитических и скалярных функций возмущения и трехмерных массивов вокселей", на странице iXBT.com, при сканировании двумерного пространства нельзя получить полноценного трехмерного изображения. Полигональная трехмерная графика со сканированием полигонов в плоскости изображения не является трехмерной в полном смысле этого слова. Информация, которая предоставляется пользователю в такой технологии — неполная. Главное — это отсутствие информации о глубине объекта, имеется ввиду не отсутствие Z — координаты точки поверхности, а отсутствие информации о луче, проходящем сквозь объект. На языке математики это будет выглядеть следующим образом. Вместо того чтобы решать уравнение, с помощью которого описывается отображаемый объект в виде F(X) = 0, предлагается определить объект с помощью вещественной непрерывной описывающей функции трех переменных (x1, x2, x3) в виде F(X) >= 0, и рассматривать объекты как замкнутые подмножества Эвклидова пространства En, определяемые описывающей функцией F(X) >= 0, где F — непрерывная вещественная функция, и X= (x1,x2,x3) — задаваемая координатными переменными точка в En. Здесь F(X) > 0 задает точки внутри объекта, F(X) = 0 — точки на границе и F(X) < 0 — точки, лежащие снаружи и не принадлежащие объекту. Отсутствие информации о луче, проходящем сквозь объект, делает реализацию многих 3D эффектов и подробных деталей невозможной. На практике некоторые эффекты моделируются с помощью технологии Environment Mapped Bump Mapping (EMBM). Добиться похожих эффектов можно с помощью использования многопроходного альфа — смешивания для моделирования рельефа на трехмерных объектах. Но таким образом можно получить лишь часть эффектов возможных при использовании EMBM и с худшим качеством. Многопроходное альфа-смешивание приводит к артефактам, ограниченно монохромным освещением и не способно моделировать специфические эффекты. Основные производители графических акселераторов стремятся повышать реалистичность уже не только за счет количества полигонов. Такие технологии как Bump Mapping и Environment Mapped Bump Mapping позволяют на порядок увеличить реалистичность изображения, не требуя для этого повышения количества геометрических примитивов.

В настоящий момент все эти эффекты моделируются за счет специфических приемов, типа Environment Map — Bump Mapping описанный в [14] или Elevation Map [15], недостатками которых являются сильные ограничения на условия их применения. Например, в случае Elevation Map реализм достигается только при углах зрения близких к прямому. Повышение степени детализации ведет к сильной загрузке транспортных магистралей, и хотя вычислительных мощностей современных процессоров вполне хватает для обработки такого количества полигонов, пропускной способности шины не хватает для передачи данных. Применение текстуры решает проблему реалистичности лишь отчасти, так как вблизи объект все так же представляется как плоскость с наклеенной картинкой. Эффекты типа Bump Mapping немного улучшают картину, но и они обладают существенными ограничениями. В самой простой форме, Bump Mapping добавляет реализм к текстурам и объектам, создавая иллюзию рельефности, другими словами, изменений в поверхностной глубине, на плоской поверхности. Таким образом, получаются ячейки на мяче для гольфа, грубая поверхность камня или изрытая кора дерева. В преобразовании выдавливания, для убедительности, глаз должен чувствовать изменения в поверхностной глубине даже притом, что поверхность действительно плоская. На визуальное восприятие глубины влияет количество света, отраженного рассматриваемой поверхностью, а количество света, отраженного в любом данном направлении, зависит от отражающей поверхности. Иными словами, гладкая поверхность всегда отражает больше чем рельефная. В трехмерной графике иллюзия рельефа основана исключительно на цвете освещения/затенения. Эффект освещения/затенения легко достигается модификацией цвета каждого из элементов текстуры, или текстурируемых пикселов, при выводе изображения на экран. Bump Mapping осуществляется следующим образом. Имеется карта рельефа поверхности, как правило, это графический файл, и после вычисления нормали к грани, нормаль отклоняется на некий "возмущающий" вектор, значение которого вычисляется по карте рельефа. Соответственно изменяется количество отражаемого света, значит и цвет пиксела.

Очевидны недостатки такой методики. Хотя поверхность трехмерной модели и кажется рельефной, на краю рельеф отсутствует. Так же, при Bump Mapping не учитывается Z координата объекта. В итоге, неровности на объекте, расположенном вблизи, и неровности на удаленном объекте имеют одинаковый размер. Технология Elevation maps [15], предложенная компанией NVIDIA, по сути, является комбинацией Bump Mapping и геометрического моделирования рельефа, учитывающим Z-глубину. Суть метода заключается в рендеринге объекта, представленного как набор параллельных друг другу слоев треугольников, и использовании альфа канала текстуры как высоты данного тексела относительно некой базовой поверхности, и канала RGB для вычисления нормали к поверхности (здесь и проявляется общность Elevation Map с Bump Mapping). Соответственно, если высота пиксела меньше высоты соответствующего пиксела в карте высот то, по значениям RGB канала данного тексела вычисляется нормаль, и затем цвет пиксела. Так как при таком подходе мы имеем текстуру "слитую" с геометрией объекта в одном примитиве, то они согласованы по глубине (Z координате) и, соответственно, лишены вышеописанных недостатков Bump Mapping. Недостатки же данного подхода — очевидны. Использование технологии Elevation Map имеет сильное ограничение на угол зрения. При угле зрения близком к нулевому, будет наблюдаться не объект, а только набор параллельных друг другу плоскостей. Следовательно, отобразить с высокой степенью детализации можно только те поверхности, на которые мы практически всегда будем смотреть под углами, близкими к прямому, например траву на земле.

Реалистичное изображение эффектов типа волн на поверхности воды, облаков тумана, можно получить, используя технологию Environment map — Bump mapping [14], являющуюся еще одной модификацией bump mapping. В этом случае, помимо базовой текстуры объекта, применяются еще две текстуры. Текстура, являющаяся отрендеренным вариантом трехмерной сцены вокруг объекта (environment map), и текстура - карта рельефа (bump map). Самостоятельно и совместно с процедурными текстурами, данная технология позволяет получить такие натуральные эффекты как отражение, отражение в кривом зеркале, дрожание поверхностей, искажение изображения вызываемое водой и теплым воздухом, трансформация искажений по шумовым алгоритмам, имитация туч на небе и другие. Совсем недавно появилась новая технология Relief Texture Mapping [16], которая устраняет недостаток ограничения на угол зрения. Данная технология является трехмерной, в отличие от Bump Mapping, которая является лишь иллюзией трехмерных деталей поверхности.

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

Таким образом, можно сделать следующий вывод:

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

3.1 Способы задания свободных форм объектов

В проекте предлагается задание пяти видов свободных форм объектов, а именно:

  1. На основе сплайн-патчей.
  2. Функций возмущения в неявном виде.
  3. Функций возмущения в скалярном виде.
  4. 3D-данных объема.
  5. Convolution-поверхностей.

3.1.1 Алгебраические патчи

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

3.1.2 Функции возмущения в неявном виде

Предлагается описывать сложные геометрические объекты, задавая функцию отклонения (второго порядка) от базовой квадрики (17-22). На базе квадрик строятся свободные формы. Свободная форма есть композиция базовой квадрики и возмущения. Получающаяся поверхность будет гладкой, и потребуется небольшое количество функций возмущения для создания сложных форм поверхностей. Таким образом, задача конструирования объекта сводится к задаче деформации поверхности квадрики нужным образом, а не к аппроксимации ее примитивами (полигонами или патчами, представленными B-сплайновыми поверхностями). Кроме того, при решении описывающей функции в виде неравенства F(X) >= 0, можно визуализировать не только поверхность, но и внутреннюю структуру объекта. Задание объектов поверхностями свободных форм сокращает в 100 и более раз описание баз данных по сравнению с заданием их полигонами.

3.1.3 Функции возмущения в скалярном виде

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

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

Время вычислений при генерации рельефа местности практически не зависит от разрешения карты высот, а зависит только от разрешения экрана (квадратичная зависимость) и от разрешения по глубине Z (логарифмическая зависимость).

3.1.4 Трехмерные массивы вокселей

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

3.1.5 Convolution — поверхности

Convolution — поверхность можно определить следующим образом. Сначала дадим определение Implicit — поверхности. Implicit — поверхность S это изо — поверхность (iso-surface) уровня T (threshold — пороговый уровень) в скалярном поле f(p) [23-34]:

Convolution — поверхность это Implicit — поверхность S с базовой функцией f(p) полученная с помощью свертки (convolution).

, где r — расстояние действия поля.

Геометрическая функция g(p) определяет форму объекта и его положение в трехмерном пространстве. Kernel — функция h(p) определяет распределение потенциала в каждой точке объекта. Свертка двух функций это скалярная функция f(p), которая является Convolution — поверхностью.

Таким образом, можно синтезировать произвольной формы Convolution-поверхности относительно таких стандартных примитивов, как:

  • Точки (Points)
  • Прямые (Line segments)
  • Дуги (Arcs)
  • Треугольники (Triangles)
  • Плоскости (Planes)

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

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

3.2 Способ сканирования трехмерного пространства

Предлагается алгоритм многоуровневого отслеживания лучей (multi-level ray casting), осуществляющий эффективный поиск элементов объема — вокселей, участвующих в формировании изображения, отличающийся простотой и небольшим количеством вычислений [20]. На первом шаге рекурсии исходная пирамида видимости разбивается на четыре меньшие подпирамиды в экранной плоскости. Модификация коэффициентов квадрики:

Где коэффициенты без штриха берутся с предыдущего шага рекурсии; переменные i, j = ±1 определяются в зависимости от направления погружения в рекурсию (i — по оси x, j — по оси y). Полученные коэффициенты используются в тесте на пересечение.

Для каждой новой подпирамиды выполняется тест на пересечение с объектом. Если в уравнении квадрики Q(x, y, z) = 0 значения переменных x, y, z меняются в пределах отрезка [-1, 1], то

Теперь заметим, что если

, то, возможно, существует точка

такая, что

Если же

то заведомо таких точек не существует, а знак коэффициента A44 различает расположение подпирамиды внутри или снаружи по отношению к поверхности квадрики Q=0 (если A44 >= 0, тогда подпирамида внутри квадрики). На основании результатов этого теста осуществляется деление подпирамид, которые лежат внутри квадрики целиком или, возможно, частично, а заведомо внешние подпирамиды исключаются из обработки. Тест на пересечение подпирамид со свободными формами несколько отличается, а модификация остается прежней и для базовой квадрики и для функции возмущения. Для базовой квадрики тест на пересечение выглядит следующим образом:

Здесь R — есть максимум функции возмущения на текущем интервале, а буквы Aij — коэффициенты квадратичной функции. Для функции возмущения проводится тест:

где Aij — коэффициенты квадратичной функции возмущения, и дополнительно вычисляется значение R, которое служит добавкой к базовой функции. Если пересечение имеет место, то подпирамида подвергается следующему уровню рекурсии. Подпирамиды, не пересекающиеся с объектом, дальнейшему погружению в рекурсию не подлежат, что соответствует исключению из рассмотрения квадратных областей экрана, на которые данная подпирамида (следовательно, и поверхность объекта) не отображается. Деление пирамиды видимости ведется до тех пор, пока не достигается максимально установленный уровень рекурсии. Преимущество этой методики в том, что она позволяет на ранней стадии отбросить большие части пустого пространства.

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

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

Ниже будет дано математическое обоснование данного метода в качестве заключения.

3.2.1 Критерий наличия нулей аналитической функции в d-окрестности начала координат

а) Постановка задачи

В алгоритмах растрирования путем рекурсивного деления пространств произвольной размерности самым важным является вопрос о пересечении некоторой фигуры, заданной в виде неравенства f(x,y,z) >= 0 с клеткой подделения (квадратом, брусковой окрестностью

Ясно, что точное решение этой задачи (системы неравенств), имеет обозримый вид только для достаточно простых функций f(x,y,z). Даже для функции, разложимой на полиномы в до степени n точное решение неприемлимо, т.к. будет содержать корни n-ой степени.

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

Итак, теперь можно переформулировать нашу задачу точнее и соответствующими терминами:

б) Определения и соглашения

Дальнейшие рассуждения проведем для случая трехмерного пространства и манхэттеновской метрики dist(X,Y) = max{|X|,|Y|}, хотя данные результаты верны и для произвольной размерности и метрики. Выбор метрики обусловлен простыми соображениями. Как нетрудно видеть, в данной метрике граница совпадает с множеством точек, удаленных от P на расстояние

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

в) Отыскание решения

Пусть f(x,y,z)-аналитическая функция. Тогда в f(x,y,z) можно разложить в ряд Тейлора.

Отбрасывая члены со степенями выше некоторого d, получим:

Выражение 1

Перепишем Выражение 1 в виде

Выражение 2

При этом мы считаем, что выполнено следующее условие:

Выражение 3

Потому что в противном случае фигура содержит в себе начало координат — тривиальный случай.

Неравенство треугольника дает:

Выражение 4

Выражение 5

где:

Выражение 6

т.к. видно, что:

Выражение 7

Если мы определим как

Выражение 8

что фактически является правой частью в Выражение 4. Тогда получим:

Выражение 9

Действительно,

Выражение 10

и монотонно убывает при (из-за неотрицательности коэффициентов F1,…, Fd, причем Fd > 0. Это следует из наших предположений о нетривиальности пересечения).

имеет единственный неотрицательный корень Так как > 0 для , то мы получаем достаточное условие для f(x,y,z) не иметь нулей в . Хотя корень находится достаточно легко, в несколько итераций метода Ньютона, нет необходимости в его отыскании. Поскольку > 0 при и строго убывает, то достаточно проверить знак .

Таким образом, записывая критерий в пригодном для практического применения виде, имеем следующее неравенство (если оно истинно, то f(x,y,z) имеет нули в :

Выражение 11

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

ПРИМЕРЫ СОЗДАННЫХ ИЗОБРАЖЕНИЙ



    

    

    
Международная космическая станция

    
Аэропорт

    
Танк

СПИСОК ЛИТЕРАТУРЫ

  1. А.С. 1522240 СССР. Цифровой генератор изображений / А.И. Богомяков, С.И. Вяткин, Б.С. Долговесов и др. — Опубл. 15.11.89, Бюл. N 42.
  2. Вяткин С.И., Долговесов Б.С., Мазурок Б.С. и др. Эффективный метод растрирования изображений для компьютерных систем визуализации реального времени // Автометрия. — N 5. 1993.
  3. S.I.Vyatkin, B.S.Dolgovesov, B.S.Mazurok, et al. An efficient technique of image rasterization for real-time computer visualization systems. (Methods and Means for Environment Synthesis)// Optoelectronics, Instrumentation and Data Processing. Allerton Press, Inc. USA. N 5. September — October 1993.
  4. Асмус А.Э., Богомяков А.И., Вяткин С.И. и др. Видеопроцессор компьютерной системы визуализации "Альбатрос" // Автометрия. — N 6. 1994.
  5. A.E.Asmus, A.I.Bogomyakov, S.I.Vyatkin, et al. Video processor of "Albatros" image generator. (Computer Systems for Image Analysis and Synthesis)// Optoelectronics, Instrumentation and Data Processing. Allerton Press, Inc. USA. N 6. November -Dcember 1994.
  6. Буровцев В.А., Власов С.В., Вяткин С.И. и др. Геометрический процессор синтезирующей системы визуализации // Автометрия. — 1986. — N 4.
  7. Великохатный Р.И., С.И. Вяткин, О.Ю. Гимаутдинов и др. "Ариус" — семейство 3D графических систем реального времени для РС платформ // Труды 7-ой Междунар. конф. "Графикон-97". Москва, 1997.
  8. С.И. Вяткин, О.Ю. Гимаутдинов, П.Б.Гнесюк и др. Архитектура семейства систем визуализации "Ариус". // Тезисы 3-ей Междунар. научно-практич. конф. "Пилотируемые полеты в космос". РГНИИЦПК им.Ю.А. Гагарина. Звездный городок.1997.
  9. S.I. Vyatkin, B.S. Dolgovesov, S.E. Chizhik et al. "ARIUS — Family of real-time 3D image generators for PC platform". JANE'S SIMULATION AND TRAINING SYSTEMS, Editor I W Strachhan MBE AFC FRAeS, Bentworth, ALTON, Hampshire, England, 1998.
  10. Р.И. Великохатный, С.И. Вяткин, О.Ю. Гимаутдинов и др. "Семейство компьютерных систем визуализации реального времени на базе цифровых сигнальных процессоров", Четвертая Конференция — Распознавание образов и анализ изображений: новые информационные технологии, Новосибирск , 1998.
  11. С.И. Вяткин., Б.С. Долговесов, Н.Р. Каипов, С.Е. Чижик. "Архитектурные особенности системы визуализации реального времени на основе DSP" // Автометрия. — 1999.-N1.
  12. S.I.Vyatkin, O.Yu.Gimautdinov, B.S.Dolgovesov, N.R.Kaipov, and S.E.Chizhik. Architecture features of a real-time image generator based on signal processors. (Methods and Tools for Visual Environment Generation)// Optoelectronics, Instrumentation and Data Processing. Allerton Press, Inc. USA. (P. 94) N 1 January — February 1999.
  13. Vyatkin S.I., Chizhik S.E., Vilbrandt C.W. Dynamic distortion correction with viewpoint motion and non-static attitude of projector // International Conference on Human and Computer-2000 (Japan, Aizu — Wakamatsu -Tokyo, September 6-9, 2000). P. 182-189.
  14. Manuel M. Oliveira, Gary Bishop, David McAllister. Relief Texture Mapping. Proc. SIGGRAPH 2000 (New Orleans, Louisiana, July 23-28, 2000).
  15. Vyatkin S.I., Dolgovesov B.S., Yesin A.V., et al. Parallel architecture and algorithms for real-time synthesis of high-quality images using Voxel-Based surfaces // Graphicon' 2000: 10th International Conference on Computer Graphics (Moscow, August 28- September 2, 2000): М.: ВМиК МГУ, 2000. P. 117-123.
  16. Sergei I. Vyatkin, Boris S. Dolgovesov, Valerie V. Ovechkin, et al. "Photorealistic imaging of digital terrains, freeforms and thematic textures in realtime visualization system Voxel-Volumes", GraphiCon '97, Moscow.
  17. S.I. Vyatkin, B.S Dolgovesov, A.V. Yesin, et al. Voxel Volumes volume-oriented visualization system, International Conference on Shape Modeling and Applications (March 1-4, 1999, Aizu-Wakamatsu, Japan) IEEE Computer Society, Los Alamitos, California, 1999, P. 234.
  18. S.I. Vyatkin, B.S. Dolgovesov, S.E. Chizhick, "Synthesis of virtual environment with object-space recursive subdivision" — Graphicon'98 Proceedings, S. Klimenko et al. (Eds). 1998.
  19. S.I.Vyatkin, B.S.Dolgovesov, A.V.Yesin, et al. Geometric modeling and visualization of functionally defined objects.(Pattern Recognition and Image Analysis: New Information Technologies)// Optoelectronics, Instrumentation and Data Processing. Allerton Press, Inc. USA. (P.65) N 6 November — December 1999.
  20. S.I. Vyatkin, B.S. Dolgovesov, A.V. Yesin et al. Voxel Volumes Volume-Oriented Visualization System// Computer Graphics and Geometry, Internet Journal
  21. A. Sherstuyk. Fast ray tracing of implicit surfaces. In Implicit Surfaces'98, P 145-153, June 1998.
  22. McCormack J. , Sherstyuk A. Creating and rendering convolution surfaces, Computing Graphics Forum, vol. 17, No.2, 1998, P 113-120.
  23. Bloomenthal J., Shoemake K., "Convolution surfaces", SIGGRAPH'91, Computer Graphics, vol.25, No.4, 1991, P 251-256.
  24. Bloomenthal J. Sceletal Design of Natural Forms. Doctoral dissertation, University of Calgary, Department of Computer Science, 1995.
  25. G. Sealy, G. Wyvill. Smoothing of three dimensional models by convolution. In Computer Graphics International'96, June 1996, P 184-190.
  26. J. F. Blinn. A generation of algebraic surface drawing. ACM Transactions on Graphics, 1(3): 235-256, July 1982.
  27. S. Muraki. Volumetric shape description of range data using "blobby model". Computer Graphics, 25(4): 227-235, July 1991.
  28. H. Nishimura, M. Hirai, T. Kawai, T. Kawata, I. Shirakawa, and K. Omura. Object modelling by distribution function and a method of image generation. The Transactions of the Institute of Electronics and Communication Engineers of Japan, J68-D(4): 718-725, 1985.
  29. G. Wyvill, C. McPheeters, and B. Wyvill. Data structure for soft objects. The Visual Computer, 2(4): 227-234, 1986.
  30. T. Beier. Practical uses for implicit surfaces in animation. In Modeling and Animating with Implicit Surfaces, P 20.1-20.11, 1990. SIGGRAPH Course Notes 23.
  31. Bloomenthal J. Modeling the mighty maple. Computer Graphics, 19(3): 305-311, July 1985.
  32. A. Sherstuyk. Convolution Surfaces in Computer Graphics. Doctoral dissertation, Monash University, School of CSSE, 1998.




Дополнительно

iXBT BRAND 2016

«iXBT Brand 2016» — Выбор читателей в номинации «Процессоры (CPU)»:
Подробнее с условиями участия в розыгрыше можно ознакомиться здесь. Текущие результаты опроса доступны тут.

Нашли ошибку на сайте? Выделите текст и нажмите Shift+Enter

Код для блога бета

Выделите HTML-код в поле, скопируйте его в буфер и вставьте в свой блог.