Алгоритм определения невидимых линий

Разработаем теперь очень важный алгоритм, задача которого заключается в вычерчивании только видимых частей отрезка PQ. Для краткости часто будем записывать "PQ" для обозначения "отрезка прямой линии PQ", являющегося частью бесконечной прямой, проходящей через точки Р и Q. Для каждого треугольника АВС из списка, записанного в массив TRIANGLE, необходимо выполнить проверку — не будет ли он закрывать PQ (или его часть). Как и ранее, Е — точка наблюдения. Будем говорить, что треугольник АВС закрывает точку R, если отрезок ER пересекает треугольник АВС в точке, внутренней как по отношению к отрезку, так и по отношению к треугольнику. Стороны треугольника не относятся к внутренним точкам, а концевые точки отрезка не являются внутренними для отрезка. Таким образом, точка R не закрывается треугольником АВС ни в том случае, когда точка R принадлежит внутренней части треугольника, ни в том случае, когда она принадлежит стороне треугольника, закрытой другим треугольником. Если треугольник АВС не закрывает точку R, то будем говорить, что точка R видима по отношению к треугольнику АВС. Если только конечное число точек отрезка PQ видимо по отношению к треугольнику АВС, все равно будем говорить, что АВС закрывает PQ. Например, на рис. 8.1 треугольник 130 закрывает отрезок 12, хотя этот треугольник не закрывает точку 1. Если треугольник не закрывает PQ, нельзя сделать заключение, что все точки PQ видимы по отношению к этому треугольнику, поскольку треугольник может закрыть PQ частично. Треугольник частично закрывает PQ, если он закрывает бесконечно много точек отрезка PQ и в то же время бесконечно много точек этого отрезка остаются видимыми по отношению к этому треугольнику. Если некоторый треугольник закрывает PQ, то нет необходимости учитывать оставшиеся треугольники в списке, но можно немедленно прийти к заключению, что PQ закрыт и не должен вычерчиваться. Обсудим видимость отрезка прямой линии PQ по отношению к треугольнику АВС в алгоритмическом смысле. Пусть заданы видовые координаты Хр, Yр, Zp, Xq ,... и так далее для пяти точек Р, Q, А, В, С и коэффициенты а, Ь, с, h уравнения ax+by+cz=h. Вся информация о треугольнике АВС сохраняется в элементе массива TRIANGLE[j]. Ключевым фактором в нашем анализе будет бесконечная пирамида, вершина которой находится в точке Е, а боковые грани проходят через стороны треугольника АВ, ВС, СА. Эту пирамиду для краткости назовем одним словом "пирамида", а треугольник АВС — термином "треугольник". Все внутри пирамиды позади треугольника будет невидимым, а все точки впереди или вне пирамиды — видимыми (относительно данного треугольника). На рис. 8.2 отрезок прямой линии PQ пересекает пирамиду в двух точках — I и J. Часть IJ отрезка PQ будет невидимой, а части Р1 и JQ — видимыми. (Ради краткости вместо фразы "видимый по отношению к треугольнику АВС" будем применять термин "видимый".) Сложность нашей задачи заключается в очень большом количестве случаев, которые предстоит рассмотреть. В ситуации, показанной на рис. 8.2, можем вычислить положение точки I следующим образом. Векторное представление прямой линии PQ записывается в виде

Дата добавления: 2014-01-14