13.6.1. Геометрическое тестирование в подпрограмме еа'деТеБГ-О
Основная работа НЬЯ-алгоритма, скелет которой приводится в листинге 13.7, возлагается на функцию еадеТезтДЕ.Р). Простейшие тесты должны выполняться первыми, чтобы сколь возможно быстро определиться с ребром Е. Если одного теста недостаточно, то должен выполняться следующий. Хотя возможно много вариантов, разумной последовательностью тестов является такая: О Тестирование экстента. Экстент по х ребра Е тестируется относительно экстента грани £ Если они не пересекаются, то грань £не может заслонять ребро Е. Если же пересечение имеет место, то тестируются соответствующие экстенты по у, и ребро Е по-прежнему «выживет», если и эти экстенты не пересекаются. Оба этих теста - очень быстрые.
О Ребро на ближней стороне. Если обе концевые точки У, и У2 ребра Е находятся ближе, чем плоскость грани /*", то такое ребро не может заслоняться гранью Р и потому выживает. Если уравнение плоскости грани /*" имеет вид т Р = Д где т - внешняя нормаль, то можно сформировать две величины 5, = (т V, - И) и 52 = (т У2 - £>). Если обе эти величины положительны, то ребро Е лежит на ближней стороне плоскости (с той же стороны, что и глаз). (Почему?) Мы уже видели подобный тест относительно плоскости грани в методе сортировки глубины в листинге 13.3.
О Ребро проходит сквозь плоскость. Если величины 5, и 52 имеют различные знаки, то ребро должно «протыкать» плоскость грани. В этом случае удобно разделить его на два куска, один из которых находится на ближней стороне плоскости грани, а второй - на дальней. Ближний кусок несомненно переживет процесс тестирования и поэтому отправится в список выживших ребер, возвращаемых подпрограммой еадеТезШ. Судьба дальнего отрезка ребра по-прежнему остается невыясненной. Аналогично, если обе величины 5, и 52 отрицательны, то все ребро Е лежит на дальней плоскости и для него требуется дальнейшее тестирование. Для того чтобы найти, где ребро Е с концевыми точками V, и У2 протыкает плоскость, напишем для этого ребра обычную параметрическую форму У,(1 - г) + У2г и подставим ее в уравнение плоскости грани. Как обычно, решим полученное уравнение для времени соударения £Ыс. Значение ^ мы будем использовать в параметрической форме плоскости для вычисления точки пересечения ребра Е с плоскостью грани.