Основы компьютерной графики для программистов. Казанцев А.В. - 16 стр.

Основы компьютерной графики для программистов                                                                  16
____________________________________________________________________________________________________________________



Третий из приводимых здесь методов до 2005 года считался мною одним из наиболее
компактных и скоростных с вычислительной точки зрения. Этот метод был предложен
автору Д. Чистяковым в 1999 году. Заметим, что очень просто можно определить при-
надлежность точки внутренней области треугольника – единичного симплекса, то есть
треугольника, образованного точками с координатами P = (0,0 ) , Q = (1,0) , R = (0,1) .
Для этого достаточно чтобы координаты искомой точки имели значения в отрезке (0,1) ,
и выполнялось условие x + y < 1 , где x и y - координаты точки. Заметим также, что с
помощью аффинных преобразований и операций переноса или непрерывных
деформаций любой треугольник можно преобразовать к единичному симплексу.
После таких преобразований внутренняя и внешняя области треугольника остаются
таковыми. Применив такое преобразование к искомой точке, достаточно затем будет




                                         Рис. 3. Приведение произвольного треугольника к
                                                      единичному симплексу.


определить ее нахождение во внутренней или внешней области симплекса. Найдем
такое преобразование. Координаты векторов единичного базиса совпадают с
координатами точек Q и R симплекса, соответственно. Будем считать, что точка C
треугольника совпадает с началом координат. Этого всегда можно добиться
параллельным переносом треугольника на вектор − C . При этом координаты точек A и
B треугольника суть коэффициенты разложения соответствующих векторов A и B по
единичному базису. Матрица преобразования M от единичного базиса к базису на
векторах A и B составлена из координат этих векторов.
                                          ⎡ Ax Ay ⎤
                                      M =⎢         ⎥
                                          ⎣ Bx B y ⎦
Значит, для обратного перехода к единичному базису, (на векторах которого построен
симплекс), необходимо найти обратную матрицу:
                                                                  1         ⎡ By   − Ay ⎤
                                                   M −1 =                   ⎢− B          .
                                                            Ax By − Ay Bx   ⎣ x     Ax ⎥⎦
                                                                                        −1
Умножение радиус-вектора искомой точки на матрицу M       дает точку, которую
достаточно проверить на попадание во внутреннюю или внешнюю область единичного
симплекса, как было указано выше.
Идея четвертого метода, без строгого математического доказательства, была
предложена одним из моих студентов Д. Трагером в 2005 году. Этот метод немного
похож на метод углов приведенный в [8] и превосходит по скорости выполнения все из

http://www.ksu.ru/persons/9134.ru.html