Основные схемы представления объемных тел. Граничное представление

Твердое тело - это замкнутое пространство, ограниченное множеством поверхностей. При этом важно, что проводится различие между внутренностью объекта, “внешним” пространством и поверхностями, ограничивающими твердое тело. В зависимости от такой классификации точек пространства, вычисляются многие полезные характеричтики и свойства твердых тел. Например, в CAD/CAM важно, что адекватно представляется геометрия объекта, и что можно создавать новые, определять их метрические свойства (объем, площадь, момент инерции...); в роботехнике важна возможность определять, взаимодействуют ли 2 объекта - например, встречает ли рука робота на своем пути препятствия; в ЧПУ необходимо генерировать управляющие инструкции для инструмента, вырезающего что-то в куске заготовки и т.д. Все это примеры моделирования твердых тел. Существуют несколько основных схем для их представления.

Граничное представление, известное также как b-rep, сходно с “наивным” каркасным представлением в том, что оно описывает объект в терминах границ его поверхностей: вершин, ребер и граней. Некоторые b-rep ограничены планарными полигональными границами, и причем грани могут допускаться только как выпуклае многоугольники. Однако, если грани допускаются быть кривыми поверхностями, то даже определение, что, собственно, является гранью, может стать нетривиальным. Кривые грани часто аппроксимируются полигонами либо в виде совокупности кусков поверхностей - параметрических или неявно заданных. При этом алгоритмы, имеющие дело с представлением, должны быть способными работать с результирующими кривыми пересечения граней, которые могут быть высокого порядка.

Многие системы с граничным представлением поддерживают только объекты со степенью многообразия равной 2.

Многогранник - это твердое тело, ограниченное множеством полигональных граней, чьи ребра принадлежат четному числу граней (двум, если 2-manifold). Простой многогранник - может быть деформировани в сферу - т.е. не имеющий дырок (в противоположность тору). b-rep простого многранника удовлетворяет формуле Эйлера, которая выражает инвариантную взаимосвязь между числом вершин, ребер и граней:

V - T + F = 2.

Формула действительна и для кривых ребер и непланарных граней. Формула Эйлера устанавливает необходимое, но не достаточное условие, чтобы объект был простым многогранником. Необходимы еще дополнительные ограничения: каждое ребро должно соединять две вершины, и принадлежать точно 2-м граням, по крайней мере три ребра должны схордться а каждой вершине и грани не должны быть “разорванными”.

Обобщение формулы Эйлера применяется к 2-manifolds, имеющим грани с дырками:

V - E + F - H = 2(C - G),

где H - число дырок в гранях, G - число дырок, проходящих через объект, С - число отдельных частей объекта.

Существуют операторы Эйлера, преобразующие объекты, удовлетворяющие формуле, в новые с тем же свойством; при этом могут удаляться и добавляться вершины, ребра и грани. При этом промежуточные объекты могут не быть твердыми телами. Сконструированы и операторы, не меняющие число вершин, ребер и граней, но сдвигающие существующие.

Возможно, простейшее b-rep - это список полигональных граней, каждая представлена списком координат вершин. Существуют и иные представления - в духе предствления для полигональных сеток.

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

Именно системы на основе граничного представления доминируют на рынке; соответственно, большое количество алгоритмов разработано для их рендеринга и т. д.