16.8. Разбиение единичной сферы

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

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

— иметь одну и ту же площадь;

— быть одинаковой формы;

— быть регулярно расположенными;

— обладать округлой формой;

- разбиение должно обеспечивать достаточно хорошее угловое разрешение;

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

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

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

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

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

Рис. 16.14. (см. скан) Проектирование додекаэдра и икосаэдра на единичную сферу для получения разбиения на и ячеек.

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

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

Рис. 16.15. а — усеченный икосаэдр, представляющий собой полуправильный многогранник с 32 гранями; б — пента до декаэдр, состоящий из 60 треугольных граней. Более мелкие разбиеиия поверхности единичной сферы могут основываться на таких полуправильных многа-гранниках.

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

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

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

Если нам все же желательно получить более мелкое разбиение, то мы можем попытаться разложить уже имеющееся на треугольные элементы. Например, если разбить каждую из пятиугольных граней додекаэдра на пять равных треугольников, то получим пентадодекаэдр с 60 гранями (рис. 16.15, б). Ом является двойственным по отношению к усеченному икосаэдру.

Действуя в том же направлении, можно подразделить каждый из полученных треугольников на четыре меньших треугольника в полном соответствии с хорошо известными в геодезии куполообразными конструкциями (рис. 16.16). Смягчением некоторых из перечисленных выше требований можно достичь высокого разрешения. На самом деле, лучше использовать двойственные конструкции, так как их грани в подавляющем большинстве являются (неправильными) шестиугольниками с рассредоточенными между ними 12 пятиугольниками (рис. 16.15, б). Этим способом можно обеспечить сколь угодно мелкие разбиения.

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

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

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

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