Разбиение

Как объяснялось ранее, для каждой из пересекающихся поверхностей необходимо создать непрерывное разбиение, которое затем нужно сохранить в виде квадрантного дерева. Поскольку рациональные (нерациональные) поверхности Безье1 разбивать проще, чем рациональные (нерациональные) поверхности В-сплайнов, мы преобразуем каждую NURBS-поверхность в множество рациональных лоскутов Безье (рис. К.1).

Разбиение

После того как это будет проделано, пары рациональных лоскутов Безье, которые могут пересекаться, сохраняются в списке, называемом списком соперников (rival list). Например, на рис. К.2 показано преобразование NURBS-поверхностей S1 и S2 (рис. К.2, а) в четыре рациональных лоскута Безье Pi, Р2, РЗ и Р4 и два рациональных лоскута Безье Q1 и Q2 соответственно. Эти рациональные лоскуты Безье сохраняются в квадрантных деревьях (рис. К.2, б). Обратите внимание, что на рис. К.2, а пересечения могут возникать между лоскутами РЗ и Q1 и лоскутами Р4 и Q1. Поэтому данные пары записываются в список соперников (рис. К.2, в). Возможность пересечения двух лоскутов может быть обнаружена путем сравнения минимального размера блоков, каждый из которых едва умещает в себе лоскут.

После этого проверяется, являются ли лоскуты, хранящиеся в списке соперников, достаточно плоскими для того, чтобы их можно было аппроксимировать плоскими четырехугольниками. Если какой-либо из лоскутов в списке не является достаточно плоским, он делится на четыре части. В этом случае квадрантное дерево соответствующей поверхности обновляется с учетом этих новых лоскутов. Также модифицируется список соперников, так что пары, включавшие до разбиения старый лоскут, удаляются, а вместо них добавляются пары с новыми лоскутами.

Разбиение
 
На рис. К.З показано, как изменяется квадрантное дерево и список соперников, когда лоскут делится на части, поскольку не прошел тест на плоскостность. В данном примере на плоскостность проверяются лоскуты из пары P3-Q1, и лоскут Q1 делится на четыре новых лоскута: Qll, Q12, Q13 и Q14. Здесь мы предполагаем, что лоскут РЗ прошел тест на плоскостность. Таким образом, квадрантное дерево, изображенное на рис. К.2, б, обновляется в соответствии с рис. К.З, б. После этого производится тест на пересечение между новыми лоскутами и РЗ для обновления пары P3-Q1 в исходном списке соперников. Если новые лоскуты располагаются, как показано на рис. К.З, а, то пара РЗ- Q1 будет заменена на две пары РЗ-Qll и P3-Q12 (рис. К.З, в).
Разбиение
 

 


1 Рациональная поверхность Безье получается из поверхности Безье путем введения однородных координат для контрольных точек.

 

Смотрите также