Пусть нам нужно отсечь отрезок прямой АС, показанный на рис. 7.27, б, границами CVV. Это означает, что нам даны две точки в однородных координатах: А - (ах, ау, а2, ав)иС - (сх, су, сг, сю); и мы хотим определить, какая часть этого отрезка располагается внутри CVV. Если при этом отрезок пересекает границу CW, то нам потребуется вычислить точку пересечения / = (Jx, Iy, 1г, 1Ю).
Как и в случае алгоритма Сайруса-Бека, мы представляем CW в виде шести бесконечных плоскостей и определяем, где находится заданное ребро по отношению к каждой плоскости поочередно. Отсекаемое ребро можно представить параметрически в виде А + (С - A)t. Оно находится в точке А при t = О и в точке С при г - 1. Для каждой стенки CVV мы вначале проверяем, располагаются ли точки Л и С по одну и ту же сторону стенки. Если это так, то вычислять пересечение ребра со стенкой не нужно. Если они лежат по разные стороны стенки, мы определяем точку пересечения и отсекаем ту часть ребра, которая лежит на внешней стороне стенки.
Следовательно, мы должны иметь возможность проверять, находится ли точка «снаружи» или «внутри» по отношению к стенке. Рассмотрим, например, плоскость х = -1, которая является одной из стенок CVV. Точка Л находится справа от плоскости («внутри»), если
- > -1, или ах > -aw, или (aw + ах) > 0. (7.14)
(При умножении обеих частей неравенства на отрицательный множитель необходимо изменить знак неравенства на противоположный. Однако здесь мы имеем дело только с положительными значениями aw; см. упражнения.) Аналогично, точка Л находится с внутренней стороны плоскости х = 1, если
- < 1, или (аш - ах) > 0.
Таблица 7.1. Граничные коды, вычисляемые для каждой конечной точки ребра Координата границы Однородная величина Плоскость отсечения
| W+ X |
х=-1 |
|
|
ВС, |
w-x |
х= 1 |
|
ВС, |
W+ у |
/=-1 |
|
ВС3 |
w-у |
/=1 |
|
ВС, |
w+ z | z=-l |
|
вс5 |
w-z | z= 1 |
Блинн [Blinn, 26] называет эти величины «граничными координатами» («boundary coordinates* - ВС) точки Л и перечисляет шесть таких величин, список которых приводится в табл. 7.1. Эти шесть величии вычисляются сначала для точки Л и затем повторно для точки С. Если все шесть величин положительны, то точка располагается внутри CVV. Если хотя бы одна из них отрицательна, то точка располагается снаружи. Если обе точки располагаются внутри, то имеет место тот самый случай тривиального приема,