WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

Проверка пары объектов на пересечение. Для того, чтобы определить, пересекаются ли объекты, производится проверка на перекрывание пар объемов, входящих в ОВВ-деревья объектов, начиная с корневых объемов и далее, вплоть до листьев дерева. Отсутствие пересечения двух объемов заведомо гарантирует отсутствие пересечения самих объектов в узлах сетки, ограниченными этими объемами. В этом случае спуск по дереву прекращается. В случае пересечения двух объемов на данном уровне проводится проверка для всех пар объемов следующего уровня иерархии.

Проверка пары объемов на перекрывание. По теореме о разделяющей плоскости два многоугольника, рассматриваемых в трехмерном пространстве, не пересекаются тогда и только тогда, когда существует разделяющая их плоскость, параллельная двум прямым, каждая из которых проходит через ребро одного из многоугольников. Для двух параллелепипедов получаем 15 плоскостей. Если хотя бы одна из плоскостей является разделяющей, то объемы не пересекаются.

Рис. 2. Проверка прямой на разделение двух объемов Пусть даны два объема, А и В. Пусть относительно координат объема А объем В задается матрицей поворота R и вектором сдвига T. Пусть полудлины ребер А и В равны соответственно a1, a2, a3, и b1, b2, b3, а направления ребер объемов задаются как векторы Аi и Вi, где i = 1, 2, 3. Поскольку векторы направлений объемов взаимно ортогональны, то длина проекции объема на прямую равна сумме длин проекций каждого из трех ребер, то есть ra = (Ai, L) ai i=Расстояние между проекциями центров объемов равно |(T,L)|. Отсюда получаем искомое неравенство:

3 (T, L) > (Ai, L) + (Bi, L) ai bi i=1 i=Если оно выполняется, то интервалы, а значит и объемы, не пересекаются.

Во второй главе изложены предлагаемые автором подходы к решению поставленных задач. В разделе 2.1 показано, как использование ИВиС позволяет существенно развить концепцию построения систем управления с обратной связью.

Рассмотрим определение понятия обратной связи в классической теории систем автоматического управления (САУ). В простейшем случае САУ состоит из объекта управления О и управляющего устройства УУ.

Рис. 3. Управление с обратной связью.

Состояние управляемого объекта характеризуется вектором Y, на вход управляющего устройства подается задающее воздействие G, содержащее информацию об управляемом воздействии U. Кроме того, к объекту приложено возмущающее воздействие F. Выходная величина Y, подаваемая на вход управляющего устройства и является сигналом обратной связи. Таким образом, носителем обратной связи всегда является объект управления. Другими словами, сигнал обратной связи извлекается из физического пространства.

Покажем, что ИВиС сама по себе может являться носителем обратной связи. Для обеспечения такой возможности в системе моделирования используются два различных пространства – наблюдения и анализа. Первое пространство – физическое, второе – виртуальное. Внутри физического пространства расположены маркеры, за которыми осуществляется наблюдение (регистрируются их координаты).

Внутри виртуального пространства реконструируется состояние виртуальных объектов. Такая реконструкция осуществляется на основе априорных данных о поверхностях (3D-моделях) и оперативной информации о координатах маркеров.

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

Рис. 4. Сравнение парадигм управления с обратной связью в классической постановке и с использованием ИВиС.

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

Принципиальным отличием системы управления с ИВиС является наличие звена реконструкции состояния ИВиС. Поэтому по каналу обратной связи передаются не все параметры, а только те, которые необходимы для реконструкции состояния.

Роль априорной информации – многократно увеличивать «полезность» передаваемой информации. Можно сравнить объемы данных, которые необходимы для передачи набора двумерных изображений объектов и данных о местоположении маркеров. В первом случае каждое изображение будет содержать порядка пикселей, во втором случае достаточно координат 4-х маркеров.

В разделе 2.2 изложен метод решения задачи определения пространственного положения объектов по координатам маркеров. Пусть моделируемая сцена описывается в некоторой системе координат (мировой СК). Исходными данными являются: текущие координаты n маркеров, расположенных на объекте (заданы в мировой СК) и априорно построенная модель объекта (задана в локальной СК объекта и содержит координаты узлов сеточной модели и координаты маркеров).

Требуется определить координаты заданного узла объекта в мировой СК. Для этого достаточно отыскать матрицу преобразования A локальной СК объекта в мировую:

a11 a12 a13 a a21 a22 a23 a A= a31 a32 a33 a 0 0 0 Для описания трехмерных преобразований в компьютерной графике часто используют так называемые «однородные координаты». К трем координатам векторов добавляют четвертую, которая всегда равна единице. Тогда с помощью матрицы размерностью 4х4 очень удобно описывать ортогональные преобразования.

Тогда координаты i-го маркера xiреш, yiреш, ziреш, построенные с помощью найденного преобразования, определяются следующим образом:

реш реш реш об об (x yi zi ),,,1= A* об,,,xi yi zi i где xiоб, yiоб, ziоб – координаты маркера в СК объекта Вообще говоря, для построения матрицы преобразования достаточно знать координаты любых трех маркеров, не лежащих на одной прямой. Однако на практике координаты маркеров определяются с некоторой погрешностью, а их количество может быть существенно большим и меняться во времени.

Введем функцию невязки между вычисленными и реальными координатами маркеров как функцию от коэффициентов искомой матрицы:

n f (a11, a12, a13, a14, a21, a22, a23, a24, a31, a32, a33, a34 )= i i = 2 реш реш реш = + + i 2 xi - xi yi - yi 2 zi - zi Решение задачи сводится к отысканию коэффициентов матрицы преобразования, которая минимизирует функцию невязки. Для определения точки минимума функции f запишем ее частные производные по всем аргументам (ниже приведены производные по аргументам a11-a14, производные по остальным аргументам вычисляются аналогично):

n n n n n об fa11 = 2a11 об )2 + 2a12 об yiоб + 2a13 об ziоб + 2a14 об -2 xi (xi xi xi xi xi i=1 i=1 i=1 i=1 i=n n n n n fa12 = 2a11 об yiоб + 2a12 об )2 + 2a13 yiоб ziоб + 2a14 yiоб -2 yiоб xi xi (yi i=1 i=1 i=1 i=1 i=n n n n n об fa13 = 2a11 об ziоб + 2a12 yiоб ziоб + 2a13 об )2 + 2a14 об -2 xi xi (zi zi zi i=1 i=1 i=1 i=1 i=n n n n fa14 = 2a11 об + 2a12 yiоб + 2a13 об + 2a14n - xi zi xi i=1 i=1 i=1 i=Получаем систему из 12 линейных уравнений с 12-ю неизвестными, которая распадается на 3 независимых системы для коэффициентов a11-a14, a21-a24, a31-a34.

Например, для коэффициентов a11-a14 система уравнений записывается в следующем виде:

n n n n n об a11 об )2 + a12 об yiоб + a13 об ziоб + a14 об = xi (1) (xi xi xi xi xi i=1 i=1 i=1 i=1 i=n n n n n a11 об yiоб + a12 об )2 + a13 yiоб ziоб + a14 yiоб = yiоб xi (2) xi (yi i=1 i=1 i=1 i=1 i= n n n n n об a11 об ziоб + a12 yiоб ziоб + a13 об )2 + a14 об = xi (3) xi (zi zi zi i=1 i=1 i=1 i=1 i=n n n n a11 об + a12 yiоб + a13 об + a14n = (4) xi zi xi i=1 i=1 i=1 i=Если определитель матрицы системы линейных уравнений не равен нулю, существует единственное решение. Это решение и будет точкой минимума функции невязки. Действительно, рассматриваемая функция второго порядка является непрерывной и дифференцируемой во всех точках, и при стремлении аргументов к плюс-минус бесконечности функция невязки стремится к плюс бесконечности. Это значит, что точка, в которой производная равна нулю, являться точкой минимума.

Итак, решение системы уравнений позволяет найти коэффициенты матрицы преобразования из локальной СК объекта в мировую СК. Таким образом, для того чтобы получить вектор координат произвольного узла сеточной модели объекта в мировой СК (xмир, yмир, zмир, 1), необходимо умножить найденную матрицу преобразования А на вектор координат этого узла в СК объекта (xоб, yоб, zоб, 1).

Условия существования и единственности решения. Определение коэффициентов матрицы преобразования построено на решении системы линейных уравнений. Для того чтобы система линейных уравнений имела единственное решение, необходимо и достаточно, чтобы определитель матрицы этой системы был отличен от нуля.

Исследуем выражение для определителя матрицы системы (1)–(4). Для упрощения выкладок рассмотрим двумерный случай. Тогда определитель матрицы будет равен:

n n n n n n об об об det A = n )2 об )2 - n( yiоб )2 + 2 yiоб об yiоб (xi (yi xi xi xi i=1 i=1 i=1 i=1 i=1 i= (5) n n n n об об - )2 ( yiоб )2 - ( )2 об )(xi xi (xi i=1 i=1 i=1 i=В случае, когда количество маркеров n=2 определитель тождественно равен нулю (что очевидно исходя из постановки задачи). Рассмотрим случай, когда n=3.

Пусть координаты маркеров в системе координат объекта равны (ai, bi), i = 1..3.

Подставив координаты маркеров в формулу (5) и проведя преобразования, получим следующее выражение для определителя:

2 2 2 2 det A = 3(a1 + a2 + a3 )(b12 + b2 + b3 ) - 3(a1 b1 + a2b2 + a3b3 )2 + 2 2 + 2(a1 + a2 + a3 )(b1 + b2 + b3 )(a1 b1 + a2b2 + a3b3 ) - (a1 + a2 + a3 )(b1 + b2 + b3 )2 - (6) 2 - (a1 + a2 + a3 )2 (b12 + b2 + b3 ) = (a1 (b2 - b3 ) + a2 (b3 - b1 ) + a3 (b1 - b2 )) Формула (6) представляет собой полный квадрат, а значит, определитель равен нулю только в случае, когда равно нулю выражение в скобках. Если bi = bj, ij, равенство нулю очевидно. Если это не так, выражение в скобках можно представить в виде:

a2 - a1 a3 - a= (7) b2 - b1 b3 - bРавенство (7) выполняется тогда, когда все три маркера лежат на одной прямой. В случае n>3 получим формулы, аналогичные (6), содержащие сумму квадратов. Каждый элемент суммы описывает тройки маркеров, и равен нулю, если эти три маркера лежат на одной прямой. Таким образом, определитель будет равен нулю, если все n маркеров лежат на одной прямой.

В трехмерном случае, проведя аналогичные рассуждения, получим формулы для вычисления определителя, также состоящие из суммы квадратов. При n3 в силу постановки задачи определитель тождественно равен нулю. При n4 каждый член суммы описывает четверки маркеров, а его равенство нулю означает, что все четыре маркера лежат в одной плоскости. Формулы для трехмерного случая опущены из-за их громоздкости.

Таким образом, для того, чтобы решение задачи определения координат объекта с помощью предложенного алгоритма существовало и было единственным, необходимо и достаточно, чтобы количество маркеров было больше или равно четырем, и хотя бы одна четверка маркеров не лежала в одной плоскости.

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

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

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

При поведении моделирования в условиях бортовых вычислительных комплексов становится актуальной проблема использования оперативной памяти.

Основной объем памяти занимают модели объектов и их ОВВ-деревья. Например, сбалансированное двоичное дерева для объекта, состоящего из n треугольников, будет содержать 2n-1 узлов. При этом каждый узел дерева описывается структурой данных, содержащей, как минимум, ссылки на узлы-потомки и данные об ориентации и размерах объема, что составляет 80 байт. Таким образом, вспомогательные структуры данных занимают значительно больше памяти, чем сами модели объектов (для сцен, на которых проводились испытания, этот коэффициент равен 20-30).

Предлагаемое решение проблемы состоит в выборе компромисса между стремлением достичь высокой производительности при выполнении алгоритмов и уменьшить затраты оперативной памяти. Возможности здесь достаточно велики: при уменьшении глубины дерева на k, число его узлов, а значит и расход памяти, уменьшается в 2k раз. Например, для k=3, дерево будет занимать в 8 раз меньше памяти. С другой стороны, объемы-листья дерева будут содержать по 2k треугольников, и в случае плотного контакта участков поверхностей с недостроенными деревьями потребуется гораздо больше проверок для пар треугольников. Однако, испытания показали, что увеличение времени вычисления незначительно, а уменьшение затрат оперативной памяти существенно. В рассматриваемых сценах, при уменьшении объема памяти в 8 раз, время работы метода увеличивалось в 1,4 раза.

Зная характеристики моделей объектов и параметры вычислений, можно заранее вычислить максимальную возможную глубину дерева для каждого из объектов. В некоторых случаях, по-видимому, может быть постановлена задача оптимизации, где, в зависимости от ситуации, в качестве критерия и ограничений могут выступать либо затраты памяти, либо быстродействие.

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

1. Для каждого измененного узла выбирается соответствующий объем нижнего уровня.

2. Проверяется принадлежность узла объему. Если узел не принадлежит объему, границы объема изменяются так, чтобы охватить узел.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»