Конструктивная сплошная геометрия

Первые исследования в рамках второго подхода к восстановлению 3D объектов по 2D проекциям были произведены Aldefel в 1983 году [1]. На входе в программу принимаются три проекции, из которых считываются данные о примитивах. Aldefel описывает возможные связи между примитивами. Одной из основных связей является CONTACT (n, m), которая обозначает что n и m связаны хотя бы одной общений точкой. Петля — замкнутая кривая без самопересечения.

Шаг 1: Установить все отношения между примитивами, которые связаны связью CONTACT.

Шаг 2: Найти, сохранить в списке все элементарные петли (петли, которые не содержат других петель) и отметить их как «открытые».

Шаг 3: Вычисление объема всех «открытых» петель и выбор петли P с максимальным объемом. Также случайным образом выбирается проекция, которая будет считаться базовым силуэтом.

Шаг 4: Предположим что P описывает базовый силуэт одного или нескольких объектов. Для того чтобы доказать или опровергнуть это, необходимо выполнить следующий алгоритм:

· Случайным образом выбирается проекция и в ней ищутся все прямоугольные силуэты, которые совпадают с P. Если таких силуэтов не найдено, выйти из алгоритма.

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

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

Шаг 5: «Увеличить» петлю P, создав все петли, которые включают в себя петли, прилежащие к P, если их еще не существует. Добавить их в список, отметить новые зависимости, отметить новые петли как «открытые», а P пометить как «закрытую».

Шаг 6: Спроецировать полученные объекты на плоскости, чтобы определить, описываются ли они входными проекциями. Если это так, то на этом работа алгоритма завершается, в противном случае перейти к шагу 3.

Описанный алгоритм работает только для объектов равномерной толщины. Подход носит название Конструктивная сплошная геометрия (Constructive solid geometry | CSG), и его основной концепцией является возможность математического описания любых сложных объектов при помощи более простых. Простейшими телами в CSG являются примитивы — тела простой формы, такие как куб, сфера, цилиндр, призма. Более сложные объекты создаются при помощи применения булевых операций (объединение, пересечение, разность) к некоторому набору примитивов.