Нужно ли тестировать каждое ребро относительно каждой грани? Нет, не нужно, поскольку о замкнутых объемных монолитных объектах нам известны два важных факта.
1. Если ребро закрывается нелицевой гранью, то какая-нибудь лицевая грань также обязательно закроет это ребро. (Почему?)
2. Каждое ребро принадлежит двум граням.
Из первого факта следует, что достаточно отсекать ребра только относительно лицевых граней, так что нелицевые грани можно исключить в самом начале, как это делалось в предшествующих алгоритмах. Из второго факта следует, что если ребро принадлежит двум нелицевым гранями, то оно должно быть невидимым и может далее не рассматриваться.
Удаление невидимых поверхностей
Грань может разделить ребро на много частей. (Покажите ситуацию, в которой грань с восемью ребрами разделяет ребро другой грани на пять частей.) Такой алгоритм должен отслеживать все «выжившие» куски ребра (то есть те, которые потенциально могут быть видимыми), и каждый из выживших кусков должен тестироваться относительно всех оставшихся граней из списка граней.
В описываемой модели прежде всего определяются все ее потенциально видимые ребра, после чего они помещаются в список ребер. Затем начинается выполнение цикла, в котором ребро извлекается из списка ребер и обрабатывается. Это ребро отсекается каждой (лицевой) гранью, и если оно выжило, то рисуется. Если же отсечение разбивает ребро на куски, то один из выживших кусков тестируется относительно всех оставшихся граней, а остальные куски помещаются обратно в список ребер. Если в какой-нибудь точке ребро отсекается целиком, то цикл начинается вновь - с извлечения из списка следующего ребра. Этот цикл продолжается до тех пор, пока список ребер не опустеет.
Рис 13.18. Эффект разделения ребра на видимые части На рис. 13.18 приведен пример, в котором ребро Е, простирающееся от вершины А до вершины В, тестируется относительно грани F и разделяется на четыре видимых части. Первое выжившее ребро становится ребром Е, а остальные выжившие заносятся в список ребер.