Алгоритм построения точек пересечения нелинейчатых поверхностей

Аннотация

А.В. Замятин

В статье описан алгоритм построения точки пересечения прямой с нелинейчатой поверхностью. Алгоритм реализован в среде ObjectARX для AutoCAD. Это дают возможность использовать в качестве входных данных объекты автоматизированной системы AutoCADи применять при проектировании полученные результаты. Алгоритм может быть использован в качестве самостоятельной программы или являться модулем более сложного программного комплекса.
Ключевые слова: нелинейчатая поверхность, прямая, сплайн, сеть, точка пересечения.

05.13.18 - Математическое моделирование, численные методы и комплексы программ

В практических задачах, связанных с геометрическим моделированием акустических процессов в помещениях, задач расчета освещенности помещений и прилегающих территорий и других, необходимо находить точки пересечения прямых с ограждающими поверхностями и вычислять в них нормали к поверхностям. Это необходимо для получения отраженных и преломленных лучей.
В данной статье рассмотрены алгоритм построения точек пересечения прямых с нелинейчатыми поверхностями и касательных к поверхностям в найденных точках.
В настоящее время проектирование зданий и сооружений выполняется с использованием автоматизированных систем. Поэтому представляет интерес разработка соответствующих алгоритмов в среде используемой при проектировании автоматизированной системы. Это позволяет значительно облегчить их разработку, так как дает возможность использовать в алгоритмах ресурсы автоматизированной системы, и делает более удобным их практическое применение, в связи с использованием стандартного интерфейса данной системы.
Приведенные в статье алгоритмы разрабатывались в среде ObjectARX для AutoCAD 2007 [1]. Технология программирования ObjectARX позволяет в полной мере использовать алгоритмические возможности среды программирования VisualC++ [2] и графические возможности автоматизированной системы AutoCAD [3].

Пусть поверхность задана сетью, представляющей собой два пересекающихся семейства сплайнов mi и nj (рис. 1). Сплайны, определяющие сеть, являются объектами класса AcDbSpline [1](здесь и далее указаны классы системы AutoCAD). Определяющие точки сплайнов обоих семейств находятся в узлах сети, на рис. 1 они обозначены через Mij. Количество определяющих точек на сплайнах каждого семейства одинаково. Прямая l, точку пересечения которой с поверхностью надо определить, задана точками L1 и L2.
Первым этапом алгоритма (пункт 1 на рис. 2) является выполнение функции ListSpl, определяющей необходимые для дальнейших расчетов, параметры заданной поверхности. Начальные данные функция извлекает из базы данных чертежа системы AutoCAD. К параметрам, определяемым функцией относятся: координаты узловых точек сети и первые производные в этих точках к сплайнам mi и nj. Координаты узловых точек Mijизвестны, производные в этих точках находятся с помощью стандартной функции GetFirstDeriv. Параметры поверхности хранятся в списке, каждый элемент которого содержит следующие переменные:

• pts, тип AcGePoint3dArray – динамический массив точек трехмерного пространства, содержит  координаты точек Mij, взятые по сплайну mi;
• vsm, тип AcGeVector3dArray – динамический массив векторов трехмерного пространства, содержит производные в точках Mij к сплайну mi;
• vsn, тип AcGeVector3dArray, содержит производные в точках Mij к сплайну nj;
• l, содержит указатель на следующий элемент списка, если данный элемент является последним, то значение этой переменной равно NULL.

Результатом работы функции является указатель на первый элемент созданного списка.
На следующем этапе алгоритма функция Pr_t_perпроизводит приближенное вычисление точки пересечения прямой с поверхностью (пункт 2 на рис. 2). Целью данного этапа является определение пространственного четырехугольника поверхности, в пределах которого находится точка пересечения. Входными данными является указатель на начальный элемент списка параметров поверхности, созданный предыдущей функцией.
Для каждого пространственного четырехугольника поверхности, граничные отрезки сплайнов MijMij+1, Mij+1Mi+1j+1, Mi+1j+1Mi+1j, Mi+1jMij заменяем хордами и проводим диагональ Mi+1jMij+1 (рис. 3). Аппроксимируем четырехугольник поверхности двумя треугольными отсеками плоскости ΔMijMij+1Mi+1j+1Mi+1j и ΔMij+1Mi+1+1jMi+1jMi+1j
Необходимо построить точки пересечения заданной прямой с плоскостью каждого треугольника, для этого решаем следующую систему линейных уравнений
    где                                                                         
, , , ,

x₁,  y₁,  z₁ и x₂,  y₂,  z₂  координаты точек L₁ и L₂, определяющих прямую l,  x₃,  y₃,  z₃, x₄,  y₄,  z₄, x₅,  y₅,  z₅ координаты точек, определяющих соответствующий треугольный отсек плоскости. При решении этой системы получим координаты точки пересечения прямой с плоскостью, обозначим их через x_п,  y_п,  z_п.
Определим, попадает ли найденная точка пересечения в пределы треугольного отсека. Приведем плоскость треугольника в положение параллельное одной из координатных плоскостей, например xOz. Найдем направляющие косинусы вектора нормали плоскости:
   
Угол, составляемый горизонтальной проекцией вектора нормали плоскости  с осью Oy равен:

Определим угол, составляемый вектором нормали с плоскостью xOy: .
Повернем систему координат вокруг оси Oz на угол γ. В новой системе координат вектор нормали плоскости будет лежать в плоскости yOz. Матрица этого преобразования имеет вид:
 
Следующим поворотом системы координат вокруг оси Ox на угол  приведем ось Oy в положение, параллельное нормали плоскости. Матрица этого преобразования имеет вид:
            
Получим матрицу суммарного преобразования , умножив матрицу   на  
    
Координаты точки пересечения и точек, определяющих треугольный отсек, в новой системе координат вычислим по следующему соотношению:
.  
Проведем прямую  и определим точки ее пересечения со сторонами треугольника. Если число точек пересечения с абсциссой меньше , равно 0 или 2, то точка находится вне треугольника, если равно 1, то она попадает в треугольный отсек плоскости.
Проделав, описанные выше действия для каждого четырехугольника заданной поверхности, получим приближенные значения координат точек ее пересечения с прямой.
Функции Pr_t_perвозвращает динамический массив точек pts (тип AcGePoint3dArray) содержащий точки пересечения и два динамических массива целых чисел isиjs(тип AcGeIntArray) содержащие индексы iи jопределяющие четырехугольник поверхности, в котором находится точка пересечения.
Следующая функция MSpl (пункт 3 на рис. 2), строит сплайны вокруг четырехугольника поверхности, в который попала точка пересечения (рис. 4). Обозначим их через m’k и n’l. Эти сплайны строятся по начальной и конечной точкам и значениям производных в них. Для большей точности берутся по два сплайна с каждой стороны отсека. Они являются частями исходных сплайнов, определяющих поверхность и применяются для ускорения процесса вычисления, так как исходные сплайны имеют значительное число определяющих точек, следовательно, на работу с ними будет затрачено много времени. В качестве входных параметров функция использует указатель на список, содержащий параметры поверхности,  индексы iи jопределяющие четырехугольник поверхности, в котором находится точка пересечения. Функция возвращает два указателя на массивы, содержащие m’k и n’l  (объекты типа AcDbSpline).
Далее (пункт 4 на рис.2) функция NSpl строит через средние точки m’k и n’l два сплайна mи n (рис. 4) и аналогично функции Pr_t_perопределяет в каком, из четырех полученных четырехугольников, находится точка пересечения и рассчитывает расстояние d до ближайшей точки этого четырехугольника.
В пункте 5 алгоритма (рис. 2) производится проверка: если d>e где e заданная точность вычисления, то процесс повторяется для того четырехугольника, в котором находится точка пересечения, если заданная точность достигнута, то по следующей формуле (пункт 6 на рис. 2) вычисляется вектор нормали к поверхности
, где
 и  направляющие векторы касательных в точке пересечения, координаты которых равны первым производным к сплайнам mi и nj.
Приведенный алгоритм может быть использован самостоятельно в виде встроенной команды системы AutoCAD, или входить, в качестве модуля, в более сложные программные комплексы, в тех задачах, где необходимо находить точки пересечения прямых с поверхностями и вычислять в них векторы нормалей.

Литература

1. Полищук Н.Н. AutoCAD Разработка приложений, настройка и адаптация. БХВ – Петербург. Санкт-Петербург, 2006.
2. Секунов Н.Ю. Visual C++ Визуальная среда программирования. Bhv. Москва, 1999.
3. Полищук Н.Н. AutoCAD 2007. БХВ – Петербург. Санкт-Петербург, 2008.