Пример. Правильные многогранники.
Многогранник называется правильным, если все его грани — одинаковые правильные многоугольники, и двугранные углы при всех ребрах равны. Известно, что существуют ровно пять типов правильных многогранников:
| Грань | Число вершин $(v)$ | Число ребер $(e)$ | Число граней $(f)$ | Число ребер у грани $(p)$ | Число ребер у вершины $(q)$ | |
|---|---|---|---|---|---|---|
| Тетраэдр | Треугольник | 4 | 6 | 4 | 3 | 3 |
| Куб | Квадрат | 8 | 12 | 6 | 4 | 3 |
| Октаэдр | Треугольник | 6 | 12 | 8 | 3 | 3 |
| Додекаэдр | Пятиугольник | 20 | 30 | 12 | 5 | 3 |
| Икосаэдр | Треугольник | 12 | 30 | 20 | 3 | 5 |
Имеется соотношение между числом вершин ($v$), ребер ($e$) и граней ($f$) (формула Эйлера):
(1)Обозначим через $l$ длину ребра многогранника, $\alpha$ величину двугранного угла между соседними гранями, $R$ — радиус описанной окружности, $r$ — радиус вписанной окружности, $S$ — площадь поверхности, $V$ — объем многогранника. Имеют место соотношения:
(2)Все правильные многогранники можно построить, взяв за основу куб.
Мы вначале рассмотрим свойства фигур, а затем обсудим алгоритм построения их в среде OpenCascade.
Тетраэдр
Чтобы получить правильный тетраэдр достаточно взять четыре несмежные вершины куба и провести плоскости через каждые три из выбранных вершин. Пусть вершины куба имеют координаты
(3)Грани тетраэдра содержат вершины
(4)Длина ребра такого тетраэдра равна $l=2\sqrt{2}$.
Октаэдр
Тетраэдр можно вписать в куб двумя способами. Пересечение таких тетраэдров дает октаэдр, многоугольник, имеющий восемь треугольных граней с вершинами, расположенными в центрах граней куба.
Длина ребра такого октаэдра равна $l=\sqrt{2}$.
Додекаэдр
Додекаэдр имеет двенадцать граней, каждая из которых является правильным пятиугольником. Чтобы выполнить его построение напомним вначале, что отношение стороны к диагонали правильного пятиугольника равно параметру "золотого сечения" $\tau = (\sqrt{5}-1)/2=0.6180$ (корню квадратного уравнения $\tau^2=1-\tau$).
Возьмем за основу куб с указанными выше вершинами (длина его ребра равна двум). Построим на каждой грани куба "крышечку" из двух трапеций и двух треугольников со сторонами длины $2\tau$ (см. рисунок). Можно показать, что "конек" крышечки отстоит от грани куба на расстоянии $\tau$ и что трапеция и треугольник крышечек соседних граней лежат в одной плоскости, образуя правильный пятиугольник — грань додекаэдра.
Например, с вершиной куба $(1, 1, 1)$ связаны три грани с вершинами:
Длина ребра такого додекаэдра равна $l=2\tau$.
Икосаэдр
Икосаэдр имеет двадцать граней, каждая из которых является правильным треугольником. Чтобы построить его можно найти центры граней додекаэдра и соединить ребром каждые два центра соседних граней. Отметим, что в свою очередь, центры граней икосаэдра,служат вершинами додекаэдра.
С другой стороны, вершины икосаэдра располагаются в вершинах прямоугольников, лежащих в координатных плоскостях со сторонами $(2, 2\tau)$, как показано на рисунке справа.
Изображение правильных многогранников средствами OpenCascade
Приведем участок программы рисования правильных многогранников. Пусть мы придерживаемся структуры MFC, как говорилось в Подключение OpenCascade к MFC-приложению, и пусть участок программы ниже принадлежит процедуре класса "документ", в котором определена переменная
Handle(V3d_Viewer) myViewer;
О рисовании примитивов: линий и участков поверхностей см. в Отображение графических примитивов (точки, линии) и Отображение графических примитивов (многоугольники)
Мы вначале должны создать структуру, группу примитивов и атрибуты рисования граней
Handle(Visual3d_ViewManager) ViewManager = myViewer->Viewer();
//
Handle(Graphic3d_Structure) structure = new Graphic3d_Structure(ViewManager);
ViewManager->Display(structure);
Handle(Graphic3d_Group) group = new Graphic3d_Group(structure) ;
//
// Атрибуты граней
Handle(Graphic3d_AspectFillArea3d) aspectArea = new Graphic3d_AspectFillArea3d();
aspectArea->SetInteriorStyle(Aspect_IS_SOLID); // грани закрашиваются
aspectArea->SetInteriorColor (Quantity_NOC_WHITE); // белым цветом
aspectArea->SuppressBackFace (); // задняя сторона не рисуется
aspectArea->SetEdgeOn (); // у граней отображаются ребра
aspectArea->SetEdgeColor (Quantity_NOC_YELLOW); // желтым цветом
aspectArea->SetEdgeWidth (2.0); // толщина линии
group->SetPrimitivesAspect(aspectArea); // устанавливаем атрибуты
Чтобы не перечислять все вершины и грани (для тетраэдра это сделать просто, а для икосаэдра весьма утомительно), мы поступим следующим образом. Напишем процедуру, на вход которой подаются вершины одной грани, а в ней различными поворотами этой грани будем строить остальные. Пусть процедура оформлена как
void PolytopeDraw( int nFaces, int nVrtxPerFace, int nEdgesPerVrtx, gp_Pnt* faceVrtx,
Handle(Graphic3d_Group) group )
{
// Входные величины
// nFaces - число граней многогранника
// nVrtxPerFace - число вершин у грани
// nEdgesPerVrtx - число ребер, приходящих в одну вершину
// faceVrtx - координаты вершин одной из граней
// group - заполняемая группа примитивов
. . . . .
Тогда для построения тетраэдра достаточно написать
// Тетраэдр
gp_Pnt faceVrtx[3];
faceVrtx[0].SetCoord(+1.,-1.,-1.);
faceVrtx[1].SetCoord(-1.,+1.,-1.);
faceVrtx[2].SetCoord(+1.,+1.,+1.);
PolytopeDraw( 4, 3, 3, faceVrtx, group );
Для куба:
// Куб
gp_Pnt faceVrtx[4];
faceVrtx[0].SetCoord(-1.,-1.,+1.);
faceVrtx[1].SetCoord(+1.,-1.,+1.);
faceVrtx[2].SetCoord(+1.,+1.,+1.);
faceVrtx[3].SetCoord(-1.,+1.,+1.);
PolytopeDraw( 6, 4, 3, faceVrtx, group );
Октаэдр:
// Октаэдр
gp_Pnt faceVrtx[3];
faceVrtx[0].SetCoord(1.,0.,0.);
faceVrtx[1].SetCoord(0.,1.,0.);
faceVrtx[2].SetCoord(0.,0.,1.);
PolytopeDraw( 8, 3, 4, faceVrtx, group );
Додекаэдр
// Додекаэдр
gp_Pnt faceVrtx[5];
double tau = (sqrt(5.)-1) / 2.;
faceVrtx[0].SetCoord(-1., -1., -1.);
faceVrtx[1].SetCoord(-tau, 0., -1.-tau);
faceVrtx[2].SetCoord(tau, 0., -1.-tau);
faceVrtx[3].SetCoord(1., -1., -1.);
faceVrtx[4].SetCoord(0., -1.-tau, -tau);
PolytopeDraw( 12, 5, 3, faceVrtx, group );
Икосаэдр
// Икосаэдр
gp_Pnt faceVrtx[3];
double tau = (sqrt(5.)-1) / 2.;
faceVrtx[0].SetCoord(0.,tau,1.);
faceVrtx[1].SetCoord(-tau, 1., 0.);
faceVrtx[2].SetCoord(-1.,0.,tau);
PolytopeDraw( 20, 3, 5, faceVrtx, group );
Перейдем теперь к описанию процедуры PolytopeDraw.
Определим два массива для хранения векторов нормалей к граням и многоугольников-граней.
// Массив нормалей к граням
std::vector<gp_Vec> faceNormal;
// Массив многоугольников граней
std::vector<Handle(Graphic3d_ArrayOfPolygons)> facePolygon;
Эти массивы будут запоняться по мере построения новых граней. В конце число элементов в них должно быть равно nFaces. Положим в них заданную первую грань
// Первая грань
Handle(Graphic3d_ArrayOfPolygons) polygon = new Graphic3d_ArrayOfPolygons(nVrtxPerFace);
int i;
for( i=0; i<nVrtxPerFace; i++ )
polygon->AddVertex(faceVrtx[i]);
facePolygon.push_back(polygon);
// Нормаль к первой грани
gp_Vec normal;
for( i=0; i<nVrtxPerFace; i++ ) {
int ip = (i+1)%nVrtxPerFace;
gp_Vec vec1(gp::Origin(),faceVrtx[i]);
gp_Vec vec2(gp::Origin(),faceVrtx[ip]);
normal += vec1^vec2;
}
normal.Normalize();
faceNormal.push_back(normal);
Теперь в цикле по граням и в цикле по вершинам граней будем поворачивать каждую грань вокруг оси, проходящей через центр многогранника (начало координат) и вершину. Поворот выполняется на угол кратный
//
// Поворот грани
double angle_min = 2.*M_PI/nEdgesPerVrtx; // Угол поворота грани
Сначала поворачиваем нормаль и проверяем, нет ли уже ее в массиве. Если есть — грань уже построена. Если нет — строим новую грань поворотом вершин и кладем новую нормаль и грань в массивы.
Итак, циклы по граням и вершинам
//
// Цикл по граням: для каждой строим поворотом соседнюю
for( int iFace=0; iFace<nFaces-1; iFace++ ) {
polygon = facePolygon[iFace];
normal = faceNormal[iFace];
// Цикл по вершинам грани: каждая вершина задает ось поворота
for( int iVrtx=1; iVrtx<=nVrtxPerFace; iVrtx++ ) {
Строим ось, проходящую через начало координат и вершину, и организуем цикл по углу
// Поворачиваем грань вокруг оси, проходящей через вершину
// Ось поворота
gp_Ax1 axis(gp::Origin(), gp_Dir(gp_Vec(gp::Origin(),polygon->Vertice(iVrtx))) );
// Цикл по углу
for( int iAngle=1; iAngle<nEdgesPerVrtx; iAngle++ ) {
double angle = iAngle*angle_min;
Вычисляем преобразование поворота и, применяя его к нормали, получаем нормаль новой грани
gp_Trsf transform;
transform.SetRotation(axis,angle);
// Нормаль к новой грани
gp_Vec normal_new = normal.Transformed(transform);
Выясняем, нет ли уже ее в массиве нормалей
// Нет ли ее в списке?
bool exist = false;
for( i=0; i<faceNormal.size(); i++ ) {
if( (faceNormal[i]-normal_new).Magnitude()<0.01 ) {
exist = true; break;
}
}
Если нет, строим новую грань и запоминаем ее. На этом циклы заканчиваются.
if( !exist ) {
// Нормали в списке нет. Добавляем новую грань
Handle(Graphic3d_ArrayOfPolygons) polygon_new;
polygon_new = new Graphic3d_ArrayOfPolygons(nVrtxPerFace);
ArrayVrtxCopy(polygon_new,polygon);
ArrayVrtxTransform( polygon_new, transform );
facePolygon.push_back(polygon_new);
faceNormal.push_back(normal_new);
}
}
}
}
Я не нашел в системе возможности копирования массивов и выполнения преобразования над вершинами массива, так что пришлось написать свои процедуры, текст которых приведен ниже. Но вернемся к нашему алгоритму. По окончании циклов все многоугольники построены, осталось добавить их в группу
for( int iFace=0; iFace<nFaces; iFace++ ) {
polygon = facePolygon[iFace];
group->AddPrimitiveArray(polygon);
}
}
И это все. Теперь процедура копирования вершин массива
// Копирование вершин массива
void ArrayVrtxCopy( Handle(Graphic3d_ArrayOfPrimitives) arrayTo, Handle(Graphic3d_ArrayOfPrimitives) arrayFrom )
{
// Число вершин
int nbVrtx = arrayFrom->VertexNumber ();
// Копируем вершины
gp_Pnt point;
for( int i=1; i<=nbVrtx; i++ ) {
point = arrayFrom->Vertice(i);
arrayTo->AddVertex(point);
}
//
}
и процедура преобразования вершин массива
// Преобразование вершин массива
void ArrayVrtxTransform( Handle(Graphic3d_ArrayOfPrimitives) anArray, gp_Trsf aTranform )
{
// Число вершин
int nbVrtx = anArray->VertexNumber ();
// Преобразуем вершины
gp_Pnt point;
for( int i=1; i<=nbVrtx; i++ ) {
point = anArray->Vertice(i);
point.Transform(aTranform);
anArray->SetVertice(i,point);
}
//
}
Структура данных для описания многогранника
Выше мы написали процедуру для построения и отображения многогранников. Однако, точнее, строятся не многогранники,
а совокупность их граней. В этом построениии нельзя, например, узнать соседнюю грань, либо перечислить ребра и грани, которым принадлежит данный узел, иными словами, отсутствует описание топологии фигуры. В этом разделе мы рассмотрим один из способов описания топологии, а именно, двусвязный список ребер (doubly-connected edge list, см. книгу M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computantional Geometry. Algorithms and Applications).
Будем использовать три типа данных:
- узел (vertex) — точка в пространстве,
- ребро (edge) — отрезок прямой между узлами,
- грань (face) — многоугольник, граница которого образуется узлами и ребрами.
Чтобы иметь возможность обходить грань (мы будем обходить ее против часовой стрелки), ребра должны иметь направление (начальный и конечный узлы), и для ребра должно быть определено понятие "следующий". Кроме того, ребро должно ссылаться на грани, которые находятся слева и справа от него. Для этого мы поступим следующим образом. Сопоставим каждому ребру две записи, отвечающие двум направлениям его обхода (см. рисунок). Если ребро-запись $e$ отвечает проходу от узла $v$ к узлу $w$, то парное (twin) ему ребро $twin(e)$ отвечает проходу в обратном направлении от узла $w$ к узлу $v$. Эти записи будут ссылаться друг на друга. Таким образом, мы будем использовать следующие типы записей:
- узел (Vertex) имеет координаты и указатель на одно из ребер, которое выходит из него:
struct Vertex{
gp_Pnt m_point;
Edge *m_edge;
};
- ребро (Edge) имеет указатель на узел начала ребра, указатель на парное (twin) ребро и указатель на грань слева, для которой ребро служит границей. Кроме того, имеется указатель на следующее ребро, составляющее границу той же грани:
struct Edge{
Vertex *m_origin;
Edge *m_twin, *m_next;
Face *m_face;
};
- грань (Face) имеет указатель на одно из ребер внешней границы:
struct Face{
Edge *m_edge;
};
Обсудим, каким образом с помощью введенных понятий решаются типичные задачи, которые встретятся нам далее.
Для данного узла получить исходящее ребро, лежащее на границе данной грани.
Узел ссылается на одно из исходящих ребер. Однако, если точка соседствует с несколькими гранями, из узла исходят несколько ребер, и среди них требуется отыскать нужное, а именно то, которое ссылается на данную грань (см. рисунок выше). Алгоритм выглядит следующим образом:
Edge* Vertex::GetEdge( Face *face ) {
Edge *edge = m_edge;
while( edge && edge->m_face!=face ) {
edge = edge->m_twin->m_next;
if( edge==m_edge ) edge = NULL;
}
return edge;
}
Для данного узла найти следующий узел, лежащий на границе данной грани.
С помощью процедуры мы можем пройти по всем узлам границы грани. Находим исходящее ребро, а затем узел, в который оно приходит как начало парного ребра:
Vertex* Vertex::GetNext( Face *face ) {
Edge *edge = GetEdge( face );
Vertex *vrtx = NULL;
if( edge )
vrtx = edge->m_twin->m_origin;
return vrtx;
}
Для данного ребра найти предыдущее ребро, лежащее на границе данной грани.
С помощью процедуры мы можем пройти по всем ребрам границы грани в направлении по часовой стрелке (так, чтобы грань лежала справа). Находим исходящее ребро, а затем узел, в который оно приходит как начало парного ребра:
Edge* Edge::GetPrevious() {
Edge *edge = this;
do {
edge->m_twin->m_next->m_twin;
} while( edge->m_face != m_face );
return edge;
}
Для данного узла найти предыдующий узел, лежащий на границе данной грани.
С помощью процедуры мы можем пройти по всем узлам границы грани в направлении по часовой стрелке (так, чтобы грань лежала справа).
Vertex* Vertex::GetPrevious( Face *face ) {
Edge *edge = GetEdge( face );
edge = edge->GetPrevious();
return edge->m_origin;
}
Таким образом, совокупность описанных объектов типа Vertex, Edge и Face представляет собой достаточно гибкий инструмент для описания топологии многогранника.
Построение структуры правильного многогранника
При построении структуры правильного многогранника мы используем описанный выше алгоритм, основанный на задании узлов одной грани. Остальные грани вычисляются с помощью поворотов.
// Построение топологии правильного многогранника
void PolytopeTopo( int nFaces, int nVrtxPerFace, int nEdgesPerVrtx, gp_Pnt* faceVrtx, CDCList* dcList)
{
// Входные величины
// nFaces - число граней многогранника
// nVerticesPerFace - число вершин у грани
// nEdgesPerVertex - число ребер, приходящих в одну вершину
// faceVrtx - координаты вершин одной из граней
// dcList - двусвязный список описания топологии
//
// Первая грань
CDCList::Face* face = dcList->NewFace(faceVrtx,nVrtxPerFace);
//
// Угол поворота грани
double angle = 2.*M_PI/nEdgesPerVrtx; // Угол поворота грани
//
// Цикл по граням: для каждой строим поворотом соседнюю
gp_Vec normal;
for( int iFace=0; iFace<nFaces-1; iFace++ ) {
CDCList::Face* face = dcList->m_faces[iFace];
normal = face->m_normal;
// Цикл по вершинам грани: каждая вершина задает ось поворота
CDCList::Edge *edge_prev, *edge;
CDCList::Vertex *vrtx_prev, *vrtx, *vrtx_next;
edge_prev = face->m_edge;
for( int iVrtx=0; iVrtx<nVrtxPerFace; iVrtx++, edge_prev=edge ) {
// Следующее ребро
vrtx_prev = edge_prev->m_origin;
edge = edge_prev->m_next;
vrtx = edge->m_origin;
// Нет ли уже грани?
if( edge_prev->m_twin ) // есть
continue;
// Поворачиваем грань вокруг оси, проходящей через вершину
gp_Ax1 axis(gp::Origin(), gp_Dir(gp_Vec(gp::Origin(),vrtx->m_point)) );
gp_Trsf transform;
transform.SetRotation(axis,angle);
// Нормаль к новой грани
gp_Vec normal_new = normal.Transformed(transform);
// Нет ли уже этой грани?
CDCList::Face* face_twin = NULL;
for( int i=0; i<dcList->m_faces.size(); i++ ) {
gp_Vec normal_face = dcList->m_faces[i]->m_normal;
if( (normal_face-normal_new).Magnitude()<0.01 ) {
face_twin = dcList->m_faces[i];
break;
}
}
if( !face_twin ) {
// Нормали в списке нет. Добавляем новую грань
face_twin = dcList->NewFace(face,transform);
}
// Есть соседняя грань по ребру edge_prev. Определяем его twin
CDCList::Edge* twin = face_twin->m_edge;
while( twin->m_origin->m_id!=vrtx->m_id )
twin = twin->m_next;
edge_prev->m_twin = twin;
twin->m_twin = edge_prev;
}
}
}
Усеченные правильные многогранники
Используя топологию правильного многогранника можно построить многогранник, получающийся отсечением его вершин плоскостями, проходящими через точки, лежащие на одной трети примыкающих ребер. Это нак называемые архимедовы тела.
Алгоритм разобьем на два этапа. Сначала отсечем вершины, так что на их месте появятся "дырки" в поверхности (у новых ребер не будет соседей-twin):
// Обрезаем вершины многогранника на 1/3 ребра
void PolytopeCutVrtx( CDCList* dcList )
{
// Цикл по граням
int faceCount = dcList->m_faces.size();
for( int iFace=0; iFace<faceCount; iFace++ ) {
CDCList::Face* face = dcList->m_faces[iFace];
// Цикл по ребрам грани
CDCList::Edge* edge = face->m_edge;
CDCList::Vertex* vrtx = edge->CalcVertex(2./3.);
do {
CDCList::Edge* edge_new = edge->m_list->NewEdge(vrtx);
edge_new->m_next = edge->m_next;
edge->m_next = edge_new;
// Вторая точка
edge = edge_new->m_next;
if( edge==face->m_edge )
vrtx = edge->CalcVertex(0.5);
else
vrtx = edge->CalcVertex(1./3.);
//
edge->m_origin = vrtx;
vrtx->m_edge = edge;
//
vrtx = edge->CalcVertex(0.5);
} while( edge!=face->m_edge );
}
}
После этого на месте "дырок" строим новые грани;
// Заполнение дырок
void FillHoles( CDCList* dcList )
{
// Цикл по граням
int faceCount = dcList->m_faces.size();
for( int iFace=0; iFace<faceCount; iFace++ ) {
CDCList::Face* face = dcList->m_faces[iFace];
// Цикл по ребрам грани
CDCList::Edge* edge = face->m_edge;
do {
// Есть ли соседняя грань?
if( ! edge->m_twin ) {
FillHole( edge );
}
edge = edge->m_next;
} while( edge!=face->m_edge );
}
}
//
void FillHole( CDCList::Edge* anEdge )
{
CDCList* cdList = anEdge->m_list;
CDCList::Face* face = new CDCList::Face(cdList);
CDCList::Edge* edge = anEdge;
CDCList::Edge* twin_next = NULL;
CDCList::Edge* twin = NULL;
do {
CDCList::Vertex* vrtx = edge->m_next->m_origin;
twin = cdList->NewEdge(vrtx);
twin->m_face = face;
twin->m_twin = edge;
twin->m_next = twin_next;
edge->m_twin = twin;
face->m_edge = twin;
// Следующее ребро
twin_next = twin;
edge = edge->m_next->m_twin->m_next;
} while( edge!=anEdge );
edge->m_twin->m_next = twin;
}
Например, в результате отрезания вершин икосаэдра, мы получим усеченный икосаэдр, представленный на рисунке.
