13.4.3. Помогает ли выпуклость полигонов?
Рассмотрите возможные упрощения HSR-алгоритма построчного сканирования для случая, когда все грани являются выпуклыми.
13.5. Методы разбиения области Рассмотрим принципиально другой подход к HSRy в котором используется связность области сцены. Мы уже употребляли этот термин: под связностью строки развертки понимается свойство многих соседних пикселов вдоль строки развертки покрываться или не покрываться какой-либо гранью; это связность по х при заданном у. Связность области (area coherence) - это представление о том, что многие пикселы, соседние по х или по у, обладают одним и тем же свойством. Таким образом, имеется симметрия между направлениями х и у.
Методы разбиения области основываются на разделении изображения на подобласти с последующей проверкой каждой подобласти на наличие видимых поверхностей. Если методы построчного сканирования интересуются вопросами, относящимися к глубине каждого пиксела или, самое большее, серии пикселов, то в методах разбиения используется принцип разобщения «разделяй и властвуй» («divide-and-conquer» approach). Эти методы пытаются выяснить, когда подобласть станет достаточно «простой», чтобы ее можно было нарисовать целиком без дальнейшей проверки на глубину. Если область проста в этом смысле, то она рисуется немедленно; в противном случае она разбивается на совокупность меньших подобластей, и тесты повторяются для каждой из этих подобластей. Если размер подобласти достигает некоего заранее определенного минимума (часто это один пиксел), то разбиение прекращается и выполняются явные тесты глубины с целью определить ближайшую поверхность. Затем эта область рисуется нужным цветом.
Существует несколько разновидностей алгоритмов разбиения области, все они носят название алгоритмов Варнока (Wamock algorithms), по имени Джона Варнока, который первым разработал такой под13.5. Методы разбиения области ход [Warnock, 207]. Их различия состоят в основном в определении понятия простой области и в способе разбиения области.