|
ФИЗИКО-МАТЕМАТИЧЕСКОГО ЛИЦЕЯ № 30 of 30 Phys-Math Lyceum Tough Render FarmАвторы:
Научный руководитель проекта: Галинский Виталий Александрович Общий обзор и постановка задачиРост производительности аппаратного обеспечения персональной вычислительной техники в последнее десятилетие позволил перенести мощные графические пакеты для моделирования и синтезирования реалистичных изображений с суперкомпьютеров и вычислительных станций на персональные компьютеры. Основная задача таких пакетов - построение (rendering) выходных изображений с использованием заранее заданной геометрической модели с помощью специальных алгоритмов. На данный момент существует несколько алгоритмов построения реалистичных изображений ([1], [2], [3]). Одним из этих методов построения является алгоритм трассировки лучей (Ray Tracing). Метод предназначен для построения изображения сцен на основе аналитического описания их объектов ([4]). Аналитическое задание составных частей сцены позволяет получить высокий уровень выходного результата, так как точное математическое описание позволяет избежать визуального несоответствия форм объектов их настоящему виду (такой эффект наблюдается в некоторых системах моделирования из-за использования аппроксимации всех форм с помощью треугольников). Доклад посвящен реализации метода трассировки лучей, несколько отличающейся от имеющихся аналогов благодаря своим особенностям в использовании различных формул для вычисления и инструментальных средств реализации. Постановка задачиТребуется по известному описательному набору геометрических объектов, их композиций и источников света построить битовое изображение, т.е. перспективную проекцию данного набора объектов на плоскость экрана дисплея из точки, где находится камера обзора, в заданном направлении на определенном расстоянии от камеры обзора до экрана. Для упрощения процесса моделирования реализуется язык описания 3D сцен. Реализация (TRF)Описание алгоритмаЧерез каждый дискретный элемент проекционного экрана (итогового изображения) пропускается луч и ищется ближайшее пересечение с объектами сцены. После нахождения точки пересечения и ее положения на объекте по данным параметрам определяется освещенность данной точки. Нахождению первичных лучей (лучей проходящих через виртуальную дискретную плоскость) соответствует свой алгоритм основанный на простейших векторных преобразованиях луча относительно данных параметров камеры. Для реализации простейших пространственных примитивов (список см. ниже) использованы особенности каждого объекта для нахождения пересечения его поверхности с лучом в пространстве. Для упрощения моделирования сцен каждый объект может быть подвергнут аффинному преобразованию в пространстве, что позволяет создавать объекты в их канонических формах и трансформировать в нужные образы. Для этого разработан алгоритм пост- и пред- преобразования уравнения луча в пространстве при поиске пересечения с объектом. В целях увеличения быстродействия вычислений разработана система заключения объектов в выпуклые примитивы (bound volumes), для форм которых поиск пересечения (а точнее лишь проверка на его наличие) осуществляется небольшим количеством операций. При этом после проверки на пересечение с оболочкой только при положительном ответе на нее ищется пересечение с самим объектом. Для сложных составных объектов (представляемых в виде коллекции треугольников) производится рекурсивное подразбиение пространства на подпространства и перегруппировка треугольников по ним с созданием дополнительных выпуклых оболочек заключения. Для реализации агрегатных объектов на основе операций объединения, пересечения, слияния и вычитания в алгоритме поиска пересечения используется оригинальный алгоритм проверки принадлежности точек пересечения объектам, составляющим агрегатный. Основная идея заключается в том, что в отличие от способа, предложенного в [4], проверка выбранных точек на луче осуществляется на уровне сравнения подотрезков на нем (в 1D пространстве а не в 3D). Базовый набор геометрических примитивовОписательный набор базовых примитивов делится на источники света, геометрические объекты и камеры обзора. Набор геометрических объектов включает в себя следующие примитивы:
Импортирование сцен из других файловых форматов осуществляется согласно принципам, описанным в [5]. Источники светаПоддерживаемые источники света могут быть следующих типов:
Для задания камеры используется ее положение, ориентация направления (или точка обзора), направляющий вектор "вверх" и проекционное расстояние. Для придания объектам отличительных свойств поверхности разработана модель освещения включающая в себя локальную модель освещения от источников света с учетом: равномерно рассеянного света, диффузное отражение, зеркальное отражение, диффузное преломление и зеркальное преломление. При глобальном освещение учитывается связность с другими объектами сцены, при этом рассматриваются: тени от объектов, преломление и отражение. Модель освещенияДля применения законов геометрической оптики к поверхностям объектов применяется модель освещения Холла (Hall), описанная в [4], [6], включающая в себя локальные (от источников света) и глобальные (от других объектов сцены) характеристики взаимодействия поверхностей объектов сцены с окружающей средой:
Помимо этого для придания реалистичности в алгоритм освещения включает в себя наличие пространственных характеристик среды - тумана и коэффициента поглощения. ТекстурированиеТекстурирование - замена параметров поверхности в зависимости от положения точки на объекте. Реализованы различные способы моделирования текстуры: проективные текстуры и процедурные текстуры ([7], [6]). Схема наложения - это преобразование координат из трехмерного пространства в двухмерные, для последующего наложения проекционных текстур (двухмерных изображений) Разработаны следующие алгоритмы текстурирования и режимов наложения:
Изображения воспринимаются в широко распространенных форматах: 'BMP', 'PCX', 'TGA', 'JPG' ([5], [8], [9]), а также внутренних упрощенных форматов 'G24', 'GSM'. Язык описания сценРазработанный язык описания сцен позволяет в наглядном виде в текстовом файле задавать составные части сцены. Язык реализует описание объектов и источников света с их характеристиками, позиции камеры наблюдателя, параметров построения, а также возможность описания переменных для дальнейшего использования в качестве параметров различных описаний. Переменные могут быть следующих типов: число, вектор, цвет, объект, источник света, трансформация, коэффициенты освещенности, текстуры. Поддерживаются скалярные/векторные выражения с использованием основных операций и дополнительных из векторной алгебры. В выражениях могут быть использованы некоторые математические функции (sin, cos, sqrt, rand, abs, pow, asin, acos и т.д.). Для удобства моделирования в язык включены некоторые управляющие конструкции алгоритмических языков:
Возможно комментированное текста (до конца строки '//' и вложенное '/*...*/'). Внутренняя организацияДля обеспечения производительности и упрощенного конструирования набора базовых средств синтезирования все базовые примитивы в системе устроены в виде объектов с методами доступа, в которые входят основные функции вычисления пересечения луча с объектом, трансформации объекта, вычисления нормали в точке поверхности объекта и общая функция установки параметров. Все дополнительные характеристики в объектах устроены в виде линейного списка подобъектов с методами их применения. Сюда относятся всевозможные виды текстурирования и выбора схемы наложения. При динамическом вычислении освещенности объектов происходит перебор всех подобъектов из списка с последовательным вызовом методов применения. Инструментальные средства разработкиБиблиотека поддержки графики (TQGR)Весь комплекс построен с использованием графической библиотеки, поддерживающей работу с основными типами адаптеров CGA/EGA/VGA, c наиболее распространенными SVGA-картaми (Cirrus Logic, Trident, S3, Tseng Labs, Paradise и др.) и картами, поддерживающими VESA стандарт ([10], [11]). В библиотеке реализован вывод простейших графических примитивов: точек, отрезков, окружностей, эллипсов и т.д., а также шрифтов, находящихся в ПЗУ (ROM BIOS) компьютера и растровых шрифтов формата (*.FNT). Библиотека поддерживает графический курсор (реализовано отслеживание конфликтов рисования графических объектов и изображения курсора). Рисование графических примитивов осуществляется с отсечением в заданной прямоугольной области с произвольным смещением центра системы координат. Библиотека имеет расширенные цветовые возможности: поддерживаются режимы индексного, заданного пользователем палитрового набора, черно-белого (Gray scale) и цветного (RGB) формата рисования для каждого режима. Используется метод полутонирования (Dither) ([2], [1]) c матрицей возбуждения 16х16 для каждого из перечисленных выше режимов с ограниченной цветовой глубиной. Библиотека 3D графики (TSGRAPH)Библиотека разработана для обеспечения манипулирования геометрическими объектами в пространстве. Библиотека реализует управление объектами на основе основных аффинных преобразований в пространстве: перемещение, масштабирование, повороты. Базовыми объектами библиотеки являются вектора в пространстве и "преобразования" в пространстве. Последние представляют собой матричное представление преобразований координат в пространстве (матрица имеет размерность 4x4 для обеспечения композиций всех преобразований) ([12], [1]). На основе базовых в библиотеке реализована поддержка дополнительных объектов:
РезультатыПрименение разработанного программного комплекса широко: от просчетов статичных сцен до анимационных последовательностей. Например, для уроков по стереометрии можно строить примеры сечений различных сплошных тел. Для разработки различных приложений данный комплекс применим в качестве средства для дизайна фонов, спрайтов, 3D шрифтов и т.д.ПримерВ качестве примера ниже приводятся файлы описания сцены и просчитанные результаты.
Характеристики и общая информация о программеРазработка выполнена на языках программирования "Си" и "Ассемблера". Проект состоит из модулей:
Литература
ПриложениеДалее приводится краткая сводка синтаксиса в форме Бекуса-Наура. /*************************************************************** * Copyright (C) 1999 * Computer Graphics Support Group of 30 Phys-Math Lyceum ***************************************************************/ /* FILE NAME : TRTSCENE.BNF * PURPOSE : Tough Render Farm package project. * Parser of TRF (rendering scene format) file. * Bacus-Naur-normalized-Form scene description. * PROGRAMMER : CGSG'98-99. * LAST UPDATE : 25.05.1999 (from 25.02.1999) * NOTE : None. * * No part of this file may be changed without agreement of * Computer Graphics Support Group of 30 Phys-Math Lyceum. */ nonliterals: < ... > /in (...) - comments/ literals: ' ... ' ('\'' - quote) comments allowed: closed /* ... */ to end of line // ... groups closed in parents (for ex. (...) | (...)) or: | repeated group: { ... } optional group: [ ... ] start of nonliteral definition: ::= /* Common types */ <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' <int> ::= {<digit>} <real> ::= [<int>]'.'[<int>] <vec> ::= '<' <real> ',' <real> ',' <real> '>' <str> ::= '"' {<any_character>} '"' <letter> ::= {'a' | ... | 'z' | 'A' | ... | 'Z' | '_' | '\x80' | '\x81' | ... } <name> ::= <letter>{<letter> | <digit>} <color> ::= <vec(R,G,B)> [ ',' <num(Alpha)> ] /* Common file structure */ <data_file> ::= {<object> | <light_source> | <camera> | <parameters> | <scene_environment> | <condition> | <loop> | <variable_description> } /* Condition statement */ <condition> ::= 'if' '(' <real(Condition:IsNonZero)> ')' '{' <data_file> '}' ['else' '{' <data_file> '}'] /* Loop statement */ <loop> ::= 'repeat' '(' <int(NumberOfRepeat:Counter)> ')' '{' <data_file> '}' /* Variable description ([re]definition) */ <variable_description> ::= <name> '=' <expression_or_TRF_data_object_declare> ';' /*** * Rendering parameters ***/ <parameters> ::= 'parameters' '{' { ('size' <int(Width)>, <int(Height)> ';') | ('max_level' '=' <int(RecourseDepth)> ';') | ('resample' '=' <int(ResampleMaxDepth)> ';') | ('tolerance' '=' <real(ThresholdOfColorDifference)> ';') | } '}' /*** * Scene environment ***/ <scene_environment> ::= <fog> | <background_color> | <air> | <ambient> <fog> ::= 'fog' '{' { ('distance' <num> ';') | /* distance to fog */ ('coef' <num> ';') | /* decay coefficient */ ('color' <color> ';') /* fog color */ } '}' <background_color> ::= 'background_color' <color> ';' <ambient> ::= 'ambient' <color> ';' <air> ::= 'air' '{' { ('nrefr' <num> ';') | /* Index of refraction */ ('decay_coef' <num> ';') /* Decay coefficient */ } '}' /*** * Objects ***/ /* Common object (! - inverse object) */ <object> ::= ['!'] 'object' '{' <primitive> ';' {<object_modifier> ';'} '}' /* Primitive objects*/ <primitive> ::= <sphere> | <plane> | <box> | <cylinder> | <quadric> | <tor> | <triangle> | <trimesh> | <CSG> | <bone> /* Object modifiers */ <object_modifiers> ::= <transformation> | <clip> | <bound> | <texture> | <surface> | ('noshadow' [<num(LightID)>]) /*** * Primitives ***/ /* Sphere primitive object */ <sphere> ::= 'sphere' <vec(center)> ',' <num(radius)> /* Plane primitive object */ <plane> ::= ('plane' <vec(normal)> ',' <num(distance)>) | ('plane' <vec(P0)> ',' <vec(P1)> ',' <vec(P2)>) /* Box primitive object */ <box> ::= 'box' <vec(corner)> ',' <vec(width)> /* Cylinder primitive object */ <cylinder> ::= ('cylinder' <vec(pointfrom)> 'dir' <vec(direction)> ',' <num(radius)> ['cut']) | ('cylinder' <vec(pointfrom)> 'to' <vec(endpoint)> ',' <num(radius)> ['cut']) /* Quadric primitive object */ <quadric> ::= /* Common case by coefficients (A..J) * + A B C D + * | B E F G | * | C F H I | * + D G I J + */ ('quadric' 'matrix' <num(A)> ',' <num(B)> ',' ... ',' <num(J)>) | /* Common case by coefficients at equation: * axx + byy + czz + dxy + exz + fyz + gx + hy + iz + j = 0 */ ('quadric' 'equation' <num(a)> ',' <num(b)> ',' ... ',' <num(j)>) | /* Quadric cylinder around axe (0 - X, 1 - Y, 2 - Z) with two * radiuses */ ('quadric' 'cylinder' ('0' | '1' | '2') <num(R1)> ',' <num(R2)>) | /* Quadric cone around axe (0 - X, 1 - Y, 2 - Z) with two * radiuses */ ('quadric' 'cone' ('0' | '1' | '2') <num(R1)> ',' <num(R2)>) | /* Quadric paraboloid around axe (0 - X, 1 - Y, 2 - Z) with two * radiuses */ ('quadric' 'paraboloid' ('0' | '1' | '2') <num(R1)> ',' <num(R2)>) | /* Quadric ellipsoid around axe with center and 3 radiuses */ ('quadric' 'ellipsoid' <vec(center)> ',' <vec(radiuses)>) /* Tor primitive object */ <tor> ::= 'tor' <num(R1)> ',' <num(R2)> /* Triangle (normals for smoothed) primitive object */ <triangle> ::= 'triangle' <vec(P0)> ',' <vec(P1)> ',' <vec(P2)> ['normals' <vec(N0)> ',' <vec(N1]> ',' <vec(N2)>] /* Trimesh primitive object */ <trimesh> ::= ('trimesh' ['smooth'] '{' /* Points number and coordinate data */ <int(NumberOfPoints)> <vec(P0)> ',' <vec(P1)> ',' ... ',' <vec(PN)> /* Triangles number and references to points */ <int(NumberOfTriangles)> '(' <int> ',' <int> ',' <int> ')' '(' <int> ',' <int> ',' <int> ')' ... '}') | ('trimesh' ['smooth'] <str(FileName:NFF/OBJ/GEO/TRB)>) /* CSG primitive object */ <CSG> ::= ('union' | 'merge' | 'intersection' | 'difference' | 'unmerge') '{' { <object> | <CSG_loop> } '}' /* CSG creation inside loop */ <CSG_loop> ::= 'repeat' '(' <int(Counter)> ')' '{' { <object> | <variable_description> } '}' /* Bone primitive object */ <bone> ::= 'bone' <vec(Center)> ',' <num(Radius)> /* Polygon set primitive object */ <polygon> ::= 'polygon' <object> <texture> <int(PolygonsNumber)> <int(PointsNumber)> { <vec(point)> | <int(PointsNumber)> | ',' } ';' /*** * Modifiers ***/ /* Affine transformation */ <transformation> ::= ('transformation' '{' {<transformation_specifiers> ';'} '}') | <transformation_specifiers> /* Affine transformation specifiers */ <transformation_specifiers> ::= /* Common case by coefficients (a11..a43) * + a11 a12 a13 0 + * | a21 a22 a23 0 | * | a31 a32 a33 0 | * + a41 a42 a43 1 + */ ('matrix' <vec(row1)> ',' <vec(row2)> ',' <vec(row3)> ',' <vec(row4)> ) | (('scale' | 'translate') <vec>) | ('rotate_x' <num(Angle)>) | ('rotate_y' <num(Angle)>) | ('rotate_z' <num(Angle)>) /* Clip subobject */ <clip> ::= 'clip_by' <object> /* Bound subobject */ <bound> ::= 'bound_by' <object> /* Surface shading coefficients */ <surface> ::= ('surface' '{' {<surface_specifiers> ';'} '}') | <surface_specifiers> <surface_specifiers> ::= ('coef' <num(Ka)> ',' <num(Kd)> ',' <num(Ks)> ',' <num(Kr)> ',' <num(Kt)> ',' <num(p)>) | ('envi' <num(NRefr)> ',' <num(Decay)>) | ('color' <color>]) /* Texture samples */ <texture> ::= 'texture' '{' { ('copy') | ('planar_mapping' <vec(Loc)> ',' <vec(U)> ',' <vec(V)> ',' <vec(W)>) | ('spherical_mapping' <vec(Loc)> ',' <vec(Pole)> ',' <vec(Zero)> ',' <num(ReplByU)> ',' <num(ReplByV)> [<num(OffByU)> ',' <num(OffByV)>]) | ('torus_mapping' <num(R)> ',' <num(r)> ',' <num(ReplByU)> ',' <num(ReplByV)>) ',' <num(OffU)> ',' <num(OffV)>| ('cylindric_mapping' <vec(Loc)> ',' <vec(Dir)> ',' <vec(Zero)> ',' <num(ReplByV(Length))> ',' <num(ReplByU)> [, <num(OffsetByV(Length))> ',' <num(OffsetByU)>]) | ('image_map' <str(FileName:BMP/G24/GSM)> ['tile' ','] {<image_type> ','} <num(coef)>) | ('chess' <num(Scale)> ',' <num(CoefB)> ',' <num(CoefW)>) | ('gradient' <vec(Loc)> ',' <vec(Dir)> ',' <num(Len)>) | ('color_map' '{' <num(Coef)>, <color(TableEntryColor)>]; ... '}' ) | } '}' <image_type> ::= 'bump' | 'color' | 'red' | 'green' | 'blue' | 'alpha' | 'ambient' | 'diffuse' | 'spectral' | 'transmit' | 'color_map' /*** * Light sources ***/ /* Common light */ <light_source> ::= 'light' '{' <primitive_light> ';' {<light_modifier> ';'} '}' /* Primitive lights */ <primitive_light> ::= <dir> | (<point> | <spot>) /* Light modifiers */ <light_modifiers> ::= <transformation> | <light_surface> /*** * Primitives light ***/ /* Direct light primitive */ <dir> ::= 'dir' <vec(direct)> /* Point primitive light */ <point> ::= 'point' <vec(loc)> ['dir' <vec(dir)> ['cone' <num(Angle)> ',' <num(DecayAngle)>]] /*** * Light modifiers ***/ /* Surface shading coefficients */ <light_surface> ::= ('color' <color(LightSourceColor>) | ('decay_coef' <num(Decay)>) | 'noshadow' | ('light_id' = <int(LightID)>) /*** * Camera ***/ /* Camera description */ <camera> ::= 'camera' '{' {<cam_place> | <cam_dir>| <cam_look_at> | <cam_up> | <cam_focus> | <half_proj_plane_width>} '}' <cam_place> ::= /* camera location */ 'location' <vec> ';' <cam_dir> ::= /* camera direction from location to */ 'dir' <vec> ';' <cam_look_at> ::= /* camera direction from location to */ 'look_at' <vec> ';' <cam_up> ::= /* camera direction from location to up */ 'up' <vec> ';' <cam_focus> ::= /* focus distance */ 'project_distance' <real> ';' <half_proj_plane_size> ::= /* camera project plane size */ 'size' <num(Width)> ',' <num(Height)> ';' /* END OF 'TRFSCENE.BNF' FILE */ |
|