Тип данных для ребер
Листинг 13.6. Скелет типа данных для класса Edge
class Edge{Point3 first, second: // end points of the edge // концевые точки каждого ребра
Face *facel. *face2; // pointers to its two faces // указатели на две грани ребра
Cuboid extent: //3D extent of edge // трехмерный экстент ребра
Face *nextFace: // next face for testing // следующее ребро для тестирования }: В листинге 13.6 приведен скелет класса Edge, представляющего каждое ребро, подлежащее тестированию. Помимо очевидной необходимости сохранять концевые точки ребра (или индексы списка вершин, если такой список используется), о каждом ребре хранится дополнительная информация - с целью обеспечить максимальную эффективность. Эта информация состоит из следующих элементов:
1. extent: экстент ребра - параллелепипед, выровненный по осям координат, который точно охватывает ребро.
2. facel, face2: указатели на две грани, связанные с данным ребром. Поскольку ни одна из этих граней не может заслонять ребро, то их не нужно тестировать, и поэтому они пропускаются.
13.6. О методах удаления невидимых линий
3. nextFace: указатель на следующую грань в списке граней, подлежащую тестированию. Когда ребро разделяется на части и одна его часть заносится обратно в список ребер, то она уже была протестирована относительно каких-либо граней. Следовательно, когда она позднее будет извлечена из списка, то ее нужно будет протестировать только относительно граней, оставшихся в списке. Для построения исходного списка ребер просматривается список граней, и ребра каждой лицевой грани заносятся в список ребер. Ребра-дубликаты удаляются из списка, после чего заполняются поля каждого объекта класса Edge.
Отметим, что имеются некоторые преимущества упорядочивания списка граней таким образом, чтобы самые «заметные» грани (грани большого размера вблизи от глаза камеры) находились в начале списка, В этом случае ребра будут тестироваться прежде всего относительно таких граней, которые вероятнее всего устранят их.
Удобно выделить геометрическое тестирование ребра относительно грани в подпрограмму: