ИСМ-06-2:
4. а) Структуры данных: B-REP, CSG. Преимущества и недостаткиОсновные принципы организации структуры данных в геометрических моделях CAD систем
Геометрические модели в CAD основаны на определенной структуре данных, которая обеспечивает топологическую целостность модели. Топология определяет отношения между простыми геометрическими объектами, которые могут быть связаны между собой и представлять единый сложный геометрический объект. Для более точного представления трехмерной модели необходимо, чтобы все элементы модели - грани и ребра были взаимосвязаны между собой.
Типы структур данных — B-Rep, CSG, крыльевых полуребер, декомпозиционные модели.
B-Rep (Boundary representation)
Эта структура данных содержит сведения о границах объема (вершинах, ребрах, гранях) и их соединении друг с другом. Это представление называется граничным представлением (boundary representation — B-rep). Многие структуры B-rep строятся по-разному в зависимости от того, какой элемент считается основным при сохранении сведений о связности.
Допустим, есть тело, изображенное на рис. 2.1.
Рис. 2.1. Объемное тело, сохраняемое в табл.1.
В структуре B-Rep это тело будет выглядеть, как показано в табл. 1.
Таблица 1. Три таблицы представления B-Rep
Таблица граней | Таблица ребер | Таблица вершин | |||
Грань | Ребра | Ребро | Вершины | Вершина | Координаты |
F1 | E1, E5, E6 | E1 | V1, V2 | V1 | x1, y1, z1 |
F2 | E2, E6, E7 | E2 | V2, V3 | V2 | x2, y2, z2 |
F3 | E3, E7, E8 | E3 | V3, V4 | V3 | x3, y3, z3 |
F4 | E4, E8, E5 | E4 | V4, V1 | V4 | x4, y4, z4 |
F5 | E1, E2, E3, E4 | E5 | V1, V5 | V5 | x5, y5, z5 |
| | E6 | V2, V5 | V6 | x6, y6, z6 |
| | E7 | V3, V5 | | |
| | E8 | V4, V5 | | |
Структура данных B-Rep выглядит очень простой и компактной. Однако «в чистом виде» она не используется в развитых системах твердотельного моделирования из-за перечисленных ниже недостатков.
а) б)
Рис.2.2. Поверхность с двумя границами и метод их обхода
Есть две распространенные структуры данных, которые позволяют избежать перечисленные проблемы при сохранении граничного представления объемного тела. Это структура полуребер (список граней, каждой из которых соответствует двусвязный список ребер, главная роль отводится граням) и структура крыльевых ребер (главная роль отводится ребрам, для каждого ребра сохраняется список граней, которым оно принадлежит, ребер, с которыми оно имеет общие вершины, и вершин на его концах).
CSG (Constructive solid geometry)
Эта структура данных представляет собой дерево, описывающее историю применения булевских операций к примитивам. Журнал операций носит название конструктивное представление объемной геометрии (CSG). А само дерево называется деревом CSG.
Рассмотрим тело, изображенное на рис 2.3., а. Его историю булевских операций можно представить в виде дерева так, как показано на рис. 2.3., б. Это дерево может быть представлено взаимосвязанными элементами данных (рис. 2.3., в).
Дерево CSG обладает следующими преимуществами:
· структура данных проста, а их представление компактно, что облегчает обработку;
· объемное тело, описываемое деревом CSG, всегда является корректным, то есть его внутренний объем однозначно отделен от внешнего. Примером некорректного объемного тела является тело с лишним ребром. Для него деление объема на внутренний и внешний вблизи вершины, к которой подходит это ребро, оказывается неоднозначным;
· представление CSG всегда может быть преобразовано к соответствующему представлению B-Rep. Это позволяет взаимодействовать с программами, ориентированными на использование B-Rep;
· параметрическое моделирование легко реализуется изменением параметров соответствующих примитивов
Недостатки:
· поскольку дерево CSG хранит историю применения булевских операций, в процессе моделирования могут использоваться только они. Это требование жестко ограничивает диапазон моделируемых объектов. Более того, оно исключает использование удобных функций локального изменения, таких как поднятие и скругление;
· для получения сведений о граничных поверхностях, их ребрах и связях между этими элементами из дерева CSG требуется сложные вычисления. К сожалению, сведения о границах нужны для множества приложений, в частности для отображения тел. Для того, чтобы отобразить затушеванное изображение или чертеж объемного тела, нужно иметь информацию о гранях или вершинах этого тела. Поэтому представление CSG является недостаточным для интерактивного отображения тел и манипулирования ими. Другой пример – расчет траектории движения фрезы с ЧПУ для обработки поверхностей тела. Для этой задачи нужны сведения о поверхностях, их ребрах и связности. Получить все эти данные из дерева CSG очень непросто.
Из-за этих недостатков разработчики программ, основанных на представлении методов C-Rep, стараются добавить соответствующие сведения о границах. Такое комбинированное математическое представление называется гибридным и требует поддержания согласованности между структурами данных.
Реализация структуры дерева CSG на языке C
struct operator {
int op_type; //Тип оператора – пересечение, объединение, разность
int L_type, R_type; //тип левого или правого узлов: 0 – оператор, 1 – примитив
void *L_ptr, *R_ptr, *p_ptr; //указатели на левый или правый узлы, на родительский
}
struct primitive {
int prim_type; //тип примитива
double pos_x, pos_y, pos_z; //положение экземпляра
double or_x, ori_y, ori_z; //ориентация экземпляра
void *attribute; //аттрибуты
}
© ism-06-2.ru