![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Вейлера-Азертона⇐ ПредыдущаяСтр 17 из 17
Вейлер и Азертон попытались минимизировать число шагов в алгоритме разбиения Варнока. Выходными данными этого алгоритма, который для достижения необходимой точности работает в пространстве объекта, служат многоугольники. Поэтому алгоритм можно легко использовать для удаления как невидимых линий, так и невидимых поверхностей. Алгоритм удаления невидимых линий состоит из четырех шагов: 1) предварительная сортировка по глубине; 2) отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости; 3) удаление многоугольников, экранированных многоугольником, ближайшим к точке наблюдения; 4) если требуется, то производится рекурсивное подразбиение и окончательная сортировка для устранение всех неопределенностей. Предварительная сортировка по глубине нужна для формирования списка приблизительных приоритетов. Предположим, что точка наблюдения расположена в бесконечности на положительной полуоси z, тогда ближайшим к ней и первым в списке будет тот многоугольник, который обладает вершиной с максимальной координатой z. В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка приоритетов по глубине. Отсекаться будут остающиеся в этом списке многоугольники, включая 1-й многоугольник. Вводятся два списка: внутренний и внешний. С помощью алгоритма отсечения Вейлера-Азертона все многоугольники отсекаются по границам отсекающего многоугольника. Та часть каждого отсекаемого многоугольника, которая оказывается внутри отсекающего, если она имеется, попадает во внутренний список. Оставшаяся часть попадает во внешний список. Этот этап является сортировкой на плоскости или xy-сортировкой. Теперь сравниваются глубины каждого многоугольника из внутреннего списка с глубиной отсекающего многоугольника. С использованием координат (х, у) вершин отсекаемых многоугольников и уравнений несущих плоскостей вычисляются глубины (координаты z) каждой вершины. Затем они сравниваются с минимальной координатой z (
|