хп-1 Уп-1

хо Уо

"о

с, = с,,,ф(ху)

Рис. 14.4. Логическая схема для добавления одного звена кривой Гильберта

14.5. Нерекурсивный алгоритм генерации кривой Гильберта

Алгоритмы, приведенные в табл. 14.2 и 14.7, предоставляют два нерекурсивных алгоритма построения кривой Гильберта любого порядка. Каждый из них без особых сложностей может быть реализован аппаратно. Аппаратное обеспечение для реализации алгоритма на базе табл. 14.2 включает регистр для хранения величины s, увеличивающейся на каждом шаге построения кривой и преобразуемой в координаты {х,у). Аппаратное обеспечение, реализующее алгоритм на основе табл. 14.7, не требует регистра для хранения s, но используемый при этом алгоритм более сложен.

14.6. Другие кривые, заполняющие пространство

Как упоминалось, Пеано был первым, открывшим в 1890 году кривую, заполняющую пространство. С тех пор открыто множество других кривых, которые часто носят общее название "кривые Пеано". В 1900 году Муром (Eliakim Hastings Moore) была открыта интересная вариация кривой Гильберта. Она "циклична" в том смысле, что ее конечная точка отстоит на один шаг от начальной. На рис. 14.5 показаны кривая Пеано третьего порядка и кривая Мура четвертого порядка. Кривая Мура иррегулярна в том, что кривая первого порядка представляет собой кривую "вверх-вправо-вниз" (П), но данная U-образность в кривых более высокого порядка отсутствует. За этим малым исключением алгоритмы для работы с кривой Мура очень схожи с соответствующими алгоритмами для кривой Гильберта.

Рис. 14.5. Кривые Пеано (слева) и Мура (справа)

Кривая Гильберта обобщена для произвольных прямоугольников на три и большее число размерностей. Базовый строительный блок трехмерной кривой Гильберта показан ниже. Он проходит по всем точкам куба 2x2x2. Эти и множество других кривых, заполняющих пространство, рассматриваются в работе [55].

14.7. Применение

Кривые, заполняющие пространство, находят применение при обработке изображений- сжатии, формировании полутонового изображения и текстурном анализе [44]. Еще одно приложение состоит в повыщении производительности трассировки лучей и графической визуализации. Условно сцена сканируется лучом, который перемещается в соответствии с обычным растром- слева направо через весь экран с перемещением сверху вниз. При этом, когда луч попадает на объект в базе данных моделируемой сцены, определяются его цвет и прочие свойства и изменяется вид (цвет и яркость) соответствующего пикселя на экране. (Конечно, это сверхупрощенное описание, но для наших целей его вполне достаточно.) Одна из проблем состоит в том, что зачастую такая база данных достаточно велика и данные по каждому объекту должны загружаться в память, когда сканирующий луч попадает на него. При построчном сканировании обычна ситуация, когда при проходе по строке приходится загружать в память те же объекты, которые загружались при предыдущем сканировании. Количество загрузок в память можно резко снизить, если сканирование будет обладать свойством локализации, например сканирование по квадрантам (когда переход к сканированию очередного квадранта происходит только по завершению сканирования предыдущего) зачастую позволяет существенно снизить количество загрузок в память информации об одном объекте.

14.7. ПРИМЕНЕНИЕ

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

Дуглас Вурхис (Douglas Voorhies) [58] смоделировал поведение загрузки информации об обьектах в память для обычного однонаправленного сканирования, кривой Пеано и кривой Гильберта. Его метод состоял в случайном размещении на экране окружностей заданного размера. Когда путь сканирования попадает в окружность, представляющую новый объект, последний загружается в память. Когда путь сканирования покидает обь-ект, информация о нем не выгружается из памяти до тех пор, пока путь сканирования не отойдет от обьекта на расстояние, равное удвоенному радиусу. Таким образом, если путь сканирования удаляется недалеко от объекта и вновь возвращается к нему, операции выгрузки и загрузки в память не происходит. Вурхис проводил эксперименты для окружностей разного радиуса на экране размером 1024x1024.

Считаем, что каждый раз, когда путь сканирования попадает в объект и покидает его, происходит одна операция загрузки в память. Тогда очевидно, что обычное построчное сканирование одной окружности диаметра D приводит к D операциям загрузки в память. Интересным результатом моделирования Вурхиса оказалось то, что для кривой Пеано количество операций загрузки в память в среднем составляет 2.7 и не зависит от диаметра окружности. Для кривой Гильберта среднее количество операций загрузки в память также не зависит от диаметра окружности, но составляет около 1.4. Таким образом, экспериментально доказано, что в смысле локализации при сканировании кривая Гильберта превосходит кривую Пеано и обе они существещю превосходят построчное сканирование.