Булевы операции с полиэдрами

Это операции над множествами точек, внутри полиэдров. Операция «И» (получение пересечения (общей части) двух полиэдров), «ИЛИ» (объединение двух полиэдров), «НЕ-И» (вычитание одного полиэдра из другого). Они используются при работе с конструктивной геометрией (Constructive solid geometry).

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

В результате вычитания одного полиэдра h1 из другого h2 («НЕ-И») получается набор полиэдров. Обычно поступают следующим образом, находят грань h1, которая находится внутри h2 (отсекают грань h1 плоскостями полиэдра h2) и разделяют h1 плоскостью этой грани, полиэдр с положительной стороны записывают в выходной набор, а с оставшуюся часть продолжают делить остальными плоскостями. В случае, если нет ни одной грани h1 внутри h2, полиэдры либо не пересекаются (операция «И» дает пустой полиэдр), тогда результатом является h1, либо h2 целиком находится внутри h2, тогда результатом является пустой набор полиэдров.

Объединение двух полиэдров («ИЛИ») это один из них и результат вычитания его из второго. В особых случаях, когда один полиэдр лежит внутри другого (все вершины одного внутри или на границе другого) имеет смысл просто оставить больший полиэдр.

Лекция 9-10-11-12