Майнинг Octree (OCT)
О статье
Полученный таким образом алгоритм иерархического деления полигонов на тайлы (далее "Иерархический тайлинг") позволяет стремительно производить разбиение и просчет видимости отображаемого пространства, посещая при этом только те участки изображения, которые содержат видимые края поверхностей. Участки изображения, в которых видимость определена, больше не обрабатываются алгоритмом, и информация о них остается неизменной вплоть до окончательного формирования кадра. Тайлинг и формирование изображения с разрешением 512х512 требует столько же времени, как и традиционный метод сканирования (incremental scan conversion), но при большем разрешении (напр. 4096х4096) наш алгоритм оказывается на порядок быстрее, делая его удобным для решения таких задач, как сглаживание и линейная фильтрация. Для сложных сцен с большим количеством перекрывающихся полигонов мы комбинируем иерархический тайлинг с другими иерархическими алгоритмами определения видимости, производя отброс невидимой геометрии и в объектном пространстве. Тестируя такую комбинацию алгоритмов на изображении с сеткой в 4096х4096 пикселей, мы достигли производительности иерархического Z-буфера при просчете видимости на изображении размерностью 512х512 пикселей. При этом алгоритм эффективно сглаживал изображения, содержащие сотни тысяч полигонов.
Введение
Наиболее простой и распространенный алгоритм тайлинга полигонов — это алгоритм преобразований по линии сканирования (incremental scanline conversion), далее-Инкрементальное сканирование.
- используя Z-буфер, путем сравнения значений глубины;
- обрабатывая полигоны в порядке от дальнего к ближнему (алгоритм художника), каждый раз переписывая значения параметров пикселя.
- обрабатывая полигоны в порядке от ближнего к дальнему и обновляя только вакантные пиксели.
Однако первый и самый главный недостаток традиционного инкрементального сканирования состоит в том, что алгоритм вынужден сканировать каждый пиксель на каждом примитиве, затрачивая, таким образом, драгоценное время на обработку невидимой геометрии. Если сцена не слишком сложна, это не страшно, но если количество полигонов велико, указанный недостаток существенно понижает эффективность алгоритма. В идеале, время работы совершенного алгоритма должно быть прямо пропорционально сложности видимой геометрии сцены и не зависеть от общей сложности сцены и количества невидимых глазу полигонов.
Второй недостаток, присущий инкрементальному сканированию, заключается в том, что оно затрачивает массу времени на определение краев полигона и просчет содержимого внутри примитива "пиксель за пикселем", тогда как все возможные комбинации пикселей, возникающие при пересечении краем полигона некоторого блока пикселей, могут быть просчитаны заранее и сохранены в виде битовых масок, называемых масками охвата. Путем композиционирования (здесь: совмещение на основе булевых операций) масок, соответствующих краю примитива, можно легко определить, какие именно пиксели будут принадлежать примитиву. Ранее подобная технология использовалась при реализации функций цифровой фильтрации изображения для вычисления площади охвата фрагментом полигона пространства внутри пикселя. [Carpenter84, Sabella-Wozny83, Fieume-et-al83, Fieume91].
Для сцен с большим количеством взаимно перекрывающихся полигонов мы комбинировали иерархический тайлинг с иерархическим алгоритмом определения видимости [Greene-Kass-Miller93, Greene-Kass94, Greene95], который позволяет отбросить невидимую геометрию непосредственно в объектном пространстве. Такая комбинация дает возможность рендеризовать сложнейшие сцены при малых временных затратах, обеспечивая при этом высокое качество сглаживания. Так, на тестовой сцене с 167 миллионами повторяющихся полигонов комбинированный метод определил видимость в изображении с сеткой 4096х4096 так же быстро, как метод иерархической Z-буферизации [Greene-Kass-Miller93] на изображении 512х512 пикселей.
2. Предыдущие наработки
Наш алгоритм основан на алгоритме рекурсивного деления пространства по Варноку [Warnock69], когда участки изображения (ячейки), в которых видимость не определена, делятся на четыре равных подпространства. В начальный момент все примитивы, составляющие сцену, назначаются базовой ячейке, называемой корневой ячейкой и равной размеру экрана. Далее корневая ячейка делится на четыре равные подпространства (субъячейки) меньшего размера. Теперь на каждой стадии деления (цикла рекурсии), наш алгоритм рассматривает субъячейки как находящиеся внутри полигона, содержащие полигон полностью или пересекающие обрабатываемый примитив. Будем называть эти ячейки как внутренние, внешние и пересекающие соответственно. Из всех трех типов ячеек только пересекающие ячейки будут подвергнуты дальнейшему делению. Ячейки, которые целиком находятся внутри одного или нескольких полигонов, считаются идентифицированными и дальнейшему делению не подлежат, так как все остальные полигоны, принадлежащие данной ячейке, будут невидимы и отброшены алгоритмом. Управление процессом деления ячеек на субъячейки и критерии, по которым делается вывод о необходимости дальнейшего деления, зависят от конкретного варианта реализации алгоритма Варнока и могут варьироваться [Roger85]. Типовая схема реализации обрабатывает полигоны без какой либо жесткой привязки к последовательности их подачи на обработку, поддерживает список потенциально видимых полигонов для каждой ячейки и затрачивает значительное время, сравнивая значения глубин с целью отсечения невидимых примитивов.
2.2 Охватывающие маски
3. Тройственная маска
На практике алгоритм использует сетку размерностью 8х8, однако на рисунках в целях наглядности изображена сетка 4х4.
Операции (1) и (2), приведенные для тройственных масок, аналогичны обычным маскам и легко понятны. В работе [Greene95] можно дополнительно посмотреть примеры, иллюстрирующие совмещение тройственных масок и варианты формул для различных операций с масками.Алгоритм работы различных масок //Тайлинг полигона при помощи охватывающих масок. Существующая охватывающая маска C для конкретной ячейки экрана представляет собой маску полигона, обработанного циклом ранее, и который находится ближе, чем обрабатываемый (текущий) полигон. Полигоны поступают на обработку строго по одному, от ближнего к дальнему. Обычные охватывающие маски Существующая маска пикселя: С (1) В соответствии с точками пересечения краев полигона и границ пикселя выбираем из таблицы, соответствующие таким краям маски (назовем их E1, E2,...En). Путем совмещения краевых масок определим маску полигона P : P = E1 & E2 &...& En; (2) Определим маску W соответствующую видимым сэмплам полигона P внутри С : W = P & ~C;Обновляем содержимое пиксельной маски C : C' = C | P;Тройственные охватывающие маски Существующая тройственная маска для ячейки из "пирамиды охвата": (Cc, Cv) — закрытые и вакантные составляющие маски.(1) Находим точки пересечения краев полигона с границей ячейки и находим соответствующие этим краям маски из таблицы ((E1c, E1v),... (Enc, Env)).Находим маску P(Pc, Pv) полигона : Pc = E1c & E2c & ... & Enc; Pv = E1v | E2v | ... | Env; (2) Находим маску W полностью видимых ячеек, принадлежащих полигону внутри (Cc, Cv) : W = Cv & Pc;Находим маску А активных ячеек на полигоне внутри (Сс, Сv): А = ~(W | Pv | Cc);Обновляем (Cc, Cv): Cc' = Cc | W; Cv' = Cv & ~W;
3.1 Тайлинг путем рекурсивного деления
Для того, что бы осуществить деление полигона Р на маски, по точкам пересечения краев полигона с границей ячейки мы определяем соответствующие тройственные маски (просчитанные заранее и хранящиеся в виде таблицы). Найденные таким образом маски краев совмещаются (см. пометку (1) в описании алгоритма приведенного выше) для получения маски, соответствующей полигону Р в данной ячейке. Далее, начиная с корневой ячейки пирамиды, мы совмещаем маску полигона с маской соответствующей данной ячейке по предыдущим циклам. В результате мы определим три типа субъячеек:
Мы игнорируем ячейки, где Р невидим, отобразим или пометим ячейки, в которых видимость Р однозначно определена, а активные ячейки (маска А) дополнительно поделим (т.е. выполним рекурсию деления). Для каждой поделенной ячейки весь цикл выработки и обработки маски будет повторен, в результате мы перейдем на следующий уровень пирамиды, и определим новые активные ячейки, более точно соответствующие краю полигона. И так до самого точного уровня пирамиды, где ячейка будет равна пикселю на краю полигона, и с целью дальнейшей фильтрации мы задействуем самый верхний уровень пирамиды, делящий пиксель на сетку из растровых сэмплов. В этом случае мы сможем переключиться на работу с традиционным А-буфером: находим видимые сэмплы, принадлежащие Р; определяем их влияние на конечный цвет пикселя и полученное значение заносим в накопитель; после этого обновляем охватывающую маску для пикселя.
LISTING 1 (pseudocode) /* Recursive subdivision procedure for tiling a convex polygon P. After clipping P to the near clipping plane in object space, if necessary, and projecting P's vertices into the image plane, we call tile_poly with the root mask of the mask pyramid, P's edge list, and "level" set to 1. arguments: (Cc,Cv): pyramid mask (input and output) edge_list: P's edges that intersect pyramid mask level: pyramid level: 1 is root, 2 is next coarsest, etc. */ tile_poly((Cc,Cv), edge_list, level) { set active_edge_list to nil /* build P's mask (Pc,Pv) */ Pc = all_ones Pv = all_zeros for each edge on edge_list { find intercepts on square perimeter of mask if square is outside edge then return /* polygon doesn't intersect mask */ if edge intersects square, then { append edge to active_edge_list /* Note: at the pixel level, Ec is a conventional coverage mask and Ev = ~Ec */ look up edge mask (Ec,Ev) Pc = Pc & Ec Pv = Pv | Ev } } /* make "write" bit mask and update pyramid mask */ W = Cv&Pc Cc = Cc | W Cv = Cv & ~W if level is the pixel level, then { /* filter pixel using coverage mask W */ /* to perform A-buffer box filtering: add bitcount*color to accumulation buffer */ evaluate shading and update accumulation buffer return } for each TRUE bit in W { for each pixel in this square region of screen { /* to perform A-buffer box filtering: add 64*(polygon color) to accumulation buffer */ evaluate shading and update accumulation buffer } } /* Recursive Subdivision */ /* make "active" bit mask */ A = ~(W | Pv | Cc) /* subdivide active subcells */ for each TRUE bit in A { /* call corresponding subcell S call its pyramid mask (Sc,Sv) */ copy all edges on active_edge_list that intersect S to S_edge_list tile_poly((Sc,Sv), S_edge_list, level+1) /* propagate coverage status to coarser levels of mask pyramid */ if Sc is all_ones then Cc = Cc | active_bit /* set covered status */ if Sv is not all_ones then Cv = Cv & ~active_bit /* clear vacant status */ } }
Теперь, когда сама процедура тайлинга полигона была рассмотрена, мы готовы применить ее к рендеризации кадра. Но для начала уясним суть применяемых структур данных: структуры пирамиды, массива изображения, структуры используемой трехмерной модели.
Для того, что бы деление Варнока могло управляться операциями с битовыми масками, мы храним информацию о видимости ранее обработанных полигонов в пирамиде, состоящей из охватывающих масок. Как мы видим из схемы на Рис. 2, в начальный момент единственная тройственная охватывающая маска представляет собой целый экран, тройственные маски следующего уровня соответствуют субъячейкам корневой маски и т.д. Таким образом, "пирамиду охвата" можно назвать иерархическим представлением изображения (отображаемого пространства), где С и V биты маски классифицируют ячейки изображения как занятые, вакантные или активные. Внутри занятых ячеек, вся геометрия, лежащая глубже, полностью скрыта и является невидимой. Внутри вакантных ячеек все растровые сэмплы считаются незанятыми в текущий момент и могут сменить свой статус при обработке других полигонов. Внутри активных ячеек, по крайней мере, один растровый сэмпл (но не все сразу) будет однозначно занят. На самом верхнем уровне пирамиды мы используем традиционные маски, где один бит описывает статус единичного отсчета растра (растрового сэмпла): т.е. — занят сэмпл или нет, а именно лежит внутри полигона или снаружи. Верхний, пиксельный, уровень пирамиды используется при избыточной дискретизации и реализации фильтрации. В этом случае каждая маска соответствует сетке 8х8 растровых сэмплов внутри одного пикселя. Так, соответствующая такому описанию пирамида изображения 512х512 pix с избыточной дискретизацией 8х8 на каждый пиксель будет содержать четыре уровня — тройственные маски будут храниться в трех массивах размерностью 1х1, 8х8 и 64х64; а четвертый уровень будет представлять массив 512х512 обычных масок.
Требования к количеству памяти, необходимой для хранения пирамиды, очень невелики. Ввиду того, что самый точный уровень использует всего один пиксель на растровый сэмпл, и наибольшее количество ячеек пирамиды будет находиться именно на этом уровне, то результирующие требования к памяти будут чуть выше, чем один бит на сэмпл. На практике, для хранения N-уровневой пирамиды потребуется, в среднем, от 1 целой и 1/32 до 1 целой и 1/63 бит на сэмпл, при N>1. Для сравнения заметим, что поддержка Z-буфера требует несопоставимо большего количества памяти, т.к. буфер хранит значение глубины для каждого сэмпла изображения.
Теперь несколько слов о представлении трехмерной модели. Наш алгоритм требует жесткого порядка обработки полигонов от ближнего к дальнему, поэтому представить трехмерную сцену в виде дерева двоичного деления пространства, или по другому, дерева BSP (binary space partitioning tree) будет наиболее оптимальным решением. Заранее просчитанная BSP сцена обеспечит нам требуемый порядок подачи полигонов на обработку. Далее, в части 6, мы обсудим аспекты использования BSP при формировании динамических сцен.
На этапе предварительных вычислений мы формируем дерево BSP для нашей сцены. Далее, создаем таблицы краев для обычных и тройственных масок. Для этого мы делим периметр квадрата, соответствующего ячейке, на равные отрезки (например, на 64 равных отрезка). Каждой паре отрезков, не принадлежащих одной и той же стороне квадрата, будет соответствовать запись в таблице, представляющей собой двумерный массив. Запись представляет собой маску, соответствующую расположению сэмплов в сетке при определенном пересечении краем полигона сторон квадрата. После формирования таблицы мы узнаём, какие именно отрезки периметра пересечены и находим соответствующую запись. С целью экономии, для краев с противоположными направлениями мы применяем одну и ту же запись, так как логическое "отрицание" операции (C | V) для битовых масок, по сути, соответствует обратному краю. Однако иерархический тайлинг подразумевает однозначное трактование занятых и вакантных участков в тройственной маске, поэтому для исключения неоднозначности мы применяем следующую процедуру. Концы отрезков, применяемых для деления квадрата, всегда сформируют некий четырехугольник. Отсюда, любая субъячейка, пересекаемая этим четырехугольником, будет считаться активной, гарантируя действительную вакантность для вакантных ячеек, и занятость для занятых.
Создание кадра изображения начинается с чистки содержимого накопительного буфера и пирамиды. Обработка полигонов производится начиная с самого ближнего, в порядке, обеспечиваемом BSP структурой сцены. Каждый полигон подрезается по размерам выбранного квадранта в объектном пространстве, если необходимо, и проецируется на двумерное отображаемое пространство. При этом на не нужно хранить информацию о глубине. Перед тем, как приступить к тайлингу полигона, мы определяем, является ли видимым прямоугольник, содержащий в себе полигон (polygon bounding box). Если эта процедура не позволяет определить, что прямоугольник спрятан, то мы помещаем его в наименьшую из возможных ячеек нашей пирамиды и работаем с ним в соответствии с процедурой, описанной в Листинге 1. В тех участках экрана, где фрагменты полигона видимы, мы обновляем содержимое буфера изображения и статус пирамиды. Как только все полигоны обработаны, сцена считается обработанной и содержимое буфера изображения выводится на экран.
Мы уже обсудили применение фильтрации на базе А-буфера, который, в свою очередь, к алгоритмам area sampling (дискретизация участков изображения). Abram, Westover и Whitted применили охватывающе маски к методам jitter (разброс сэмплов по стохастическому закону) и конволюции c произвольным ядром, а так же для выполнения операций затенения полигонов на базе таблиц [Abram-et-al85]. Все эти методы совместимы с иерархическим тайлингом. Для реализации табличной конволюции (table driven convolution) влияние каждого субпиксельного сэмпла на соседние пиксели вычисляется заранее и хранится в виде таблицы коэффициентов. Для простейших реализаций затенения полигонов влияние произвольного набора сэмплов может быть сохранено в виде коэффициентов, которые позволят, например, эффективно, байт за байтом, работать с охватывающими масками. Мы использовали этот метод для фильтрации 3х3 сетки из соседствующих пикселей.
Для исключения функций фильтрации изображения и осуществления обычной дискретизации нам достаточно упростить наш алгоритм. В этом случае маска, соответствующая самому точному уровню пирамиды, будет определять не сетку субпиксельных сэмплов, а пиксельный блок 8х8. Таким образом, для каждой субъячейки, имеющей значение "TRUE" (см. псевдокод), мы определяем оттенок пикселя и пишем результат непосредственно в буфер изображения. Ввиду того, что теперь единичный сэмпл соответствует пикселю, нам нет необходимости использовать аккумулирующий (накопительный) буфер.
Благодаря своей способности отсекать невидимую геометрию во всех элементах, составляющих иерархию изображения, иерархический тайлинг обрабатывает плотно перекрытые сцены значительно эффективнее типовых тайловых алгоритмов, которые вынуждены тратить время на попиксельную обработку невидимой геометрии. Тем не менее, наш алгоритм "пропустит через себя" все полигоны сцены, хотя многие из них вскоре определятся как полностью невидимые. Что бы исправить положение, мы скомбинируем наш алгоритм с иерархическим методом определения видимости [Greene-Kass-Miller93, Greene-Kass94, Greene95], что позволит иерархически отбросить невидимую геометрию непосредственно в объектом пространстве сцены. В нашем случае мы применим алгоритм иерархического Z-буфера [Greene-Kass-Miller93], хотя это и потребует внесения некоторых изменений в структуру объектного и отображаемого пространств. Так, в отображаемом пространстве вместо использования Z-пирамиды будет применена наша "пирамида охвата". В объектном пространстве мы изменим дерево разбиений пространства (octree) таким образом, чтобы обеспечить строгий порядок полигонов от ближнего к дальнему. Заметьте, что наш Z-буфер обрабатывал подпространства в порядке от ближнего к дальнему, но полигоны, находящиеся в этих подпространствах, могли обрабатываться в любом порядке, а так как сами кубические подпространства (квадранты) иерархически входили друг в друга, т.е. были дочерними и сами могли иметь дочерние квадранты, то будет недостаточным, просто построить структуру BSP внутри каждого квадранта. Что бы обеспечить строгий порядок обработки от ближнего к дальнему, мы должны видоизменить алгоритм построения древовидной структуры BSP.
5.1 Building an Octree of BSP trees (построение октаструктуры из структур BSP)
5.2 Комбинирование иерархических алгоритмов тайлинга и видимости
Такая комбинация алгоритмов эффективно работает как с объектным, так и с отображаемым пространством. Также как и иерархический Z-буфер в объектном пространстве, мы посещаем только видимые ветви дерева. В отображаемом пространстве иерархический тайлинг посещает только те ячейки, которые пересекаются видимыми в окончательном изображении поверхностями. Видимые сэмплы изображения повторно не переписываются.
6 Работа с динамическими моделями (сценами)
6.1 Ленивая Z-буферизация (Lazy Z-buffering)
В случае, когда большая часть сцены обрабатывается строго от ближнего к дальнему, то вышеизложенный вариант "ленивого z-буфера" будет лишь немногим медленнее базового иерархического тайлинга. Описанная ситуация возникнет тогда, когда некоторое небольшое количество движущихся полигонов будет размещено перед статическим (неизменяемым) набором примитивов, просчитанных от ближнего к дальнему. При самых тяжелых условиях, когда расположенные впереди движущиеся объекты не были обработаны первыми, ленивый z-буфер окажется чуть медленнее иерархического z-буфера.
Для полигональных сцен, состоящих их независимо передвигающихся твердых объектов, можно применить другой способ просчета изображения, дающий возможность обработать полигоны строго от ближнего к дальнему, а значит использовать стандартный иерархический тайлинг полигонов. Для этого каждое твердое тело сцены мы представим в виде отдельной октаструктуры из структур BSP (аналогично тому, что описывалось в параграфе 5.1). Для формирования кадра изображения мы обрабатываем все октаструктуры одновременно, в порядке от ближнего к дальнему, отбрасывая те ветви октаструктуры, кубические пространства которых полностью перекрыты пирамидой охвата. Синхронность обработки октаструктур обеспечиваем следующим образом — для каждой октаструктуры выбираем самый ближний куб из листовых ветвей в качестве текущего и проверяем его на пересечение с ближайшими кубами листовых ветвей остальных октаструктур. Если одиночный куб не пересекает других кубов, то мы смело рендеризуем всю его BSP структуру. Если пересекает, то подрезаем полигоны пересеченных кубов под границы текущего куба, полученные фрагменты внедряем в структуру BSP текущего куба и уже затем рендеризуем полученное BSP дерево. Таким образом, мы последовательно отбросим или отрендеризуем все ветви октаструктур, тем самым закончив обработку сцены. Описанный подход к визуализации динамических сцен близок по затратам времени к стандартному иерархическому тайлингу, за исключением разницы во времени, необходимом на реорганизацию и слияние древовидных структур объектов. Слияние структур может потребовать значительных вычислений и времени, но в большинстве сцен такое объединение будет не частым явлением, поэтому допустимо считать, что применение описанного метода будет оправданным.
Следующая таблица производит сравнение двух иерархических алгоритмов по некоторым ключевым параметрам.
8. Тайлинг многогранников
9. Реализация на практике и результаты
Для того, чтобы оценить производительность И.тайлинга по сравнению с традиционным инкрементальным сканированием, мы задействовали простейшую модель, состоящую из 64 кубов, обеспечивающих 192 лицевые поверхности (См. Рис.5). Рендеризация проводилась как с использованием И.тайлинга, так и с применением традиционного "алгоритма художника" т.е. методом от дальнего к ближнему, в результате чего метод инкрементального сканирования многократно переписывал каждый пиксель на своем пути. В результате И.тайлинг обеспечил рендеризацию изображения в 512х512 пикселей с фильтрацией на сетке в 4096х4096 растровых сэмплов за 0.357 секунды. Алгоритм художника за такое же время обеспечил рендеризацию сетки в 910х910 сэмплов, а протестировать его на сетке 4096х4096 мы просто не смогли ввиду тривиальной нехватки количества оперативной памяти на компьютере для формирования полноцветного RGB изображения таким способом. Проведенный пример показывает, что даже на простейших моделях для осуществления сглаживания и фильтрации И.тайлинг более привлекателен традиционного сканирования.
Что бы сравнить производительность И.тайлинга и И.Z-буфера мы рендеризовали анимацию, представляющую собой виртуальную прогулку по зданию. И.тайлинг производил визуализацию изображения на сетке в 4096х4096 растровых сэмплов, получив в итоге финальные кадры с разрешением 512х512 пикселей и наложенной фильтрацией. И.Z-буфер непосредственно осуществлял рендеринг 512х512 pix изображения с обычной дискретизацией. В итоге И.тайлинг показал практически одинаковую производительность с И.Z-буфером, но с той разницей, что в первом случае мы наблюдали сглаженный А-буфером приятный на вид кадр, а во втором, как и ожидалось, изображение имело отчетливо заметную "ступенчатость".
На реальных тестах с применением косинусной фильтрации и в режиме поддержки множественных стохастических комбинаций сэмплов алгоритм показал время в 5.15 минуты для Рис. 6 и 34 секунды для Рис. 7, содержащего приблизительно 83300 видимых полигонов. Использование однотипных комбинаций сэмплов уменьшило время рендеризации изображения Рис. 6 до 4.48 секунды. Приведенные выше результаты тестирования позволяют сказать, что рассмотренный нами иерархический алгоритм тайлинга полигонов с использованием охватывающих масок очень эффективно обрабатывает сцены сверхсложной геометрии и сферой его применения является генерация изображений трехмерных моделей высокой и сверхвысокой сложности.
Элегантный алгоритм деления пространства, изобретенный Варноком, является одним из самых известных в компьютерной графике. Однако, несмотря на то, что этот алгоритм очень хорошо изучен, на практике его применяют достаточно редко, ввиду недостаточной производительности оригинальной процедуры деления. В нашей работе мы показали, насколько эффективным может быть деление по Варноку управляемое тройственными охватывающими масками. Получившийся в результате алгоритм иерархического тайлинга полигонов показывает прекрасные результаты, обрабатывая только ячейки с видимыми фрагментами полигонов и никогда не переписывая однажды сформированный пиксель. Конек алгоритма — изображения с высоким разрешением, поэтому это очень удобный инструмент для осуществления функций сглаживания и фильтрации. Алгоритм компактен, не вызовет сложностей при реализации и требует минимальных размеров памяти.
Автор благодарит Гавина Миллера за предложенный вариант совмещения аппаратного и программного тайлинга, описанного в п. 5.2. Гавин также оказал содействие в проектировании тестовой модели офисного блока Рис. 4. Общение и дискуссии с Piter van Zee зародили идеи совмещения древовидных структур, описанного в п. 6.2. И, наконец, автор выражает признательность рецензенту #4 SIGGRAPH за очень внимательное изучение статьи и конструктивную критику.
