Алгоритмы и программные средства для пересечения трёхмерных тел в граничном представлении тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Гатилов Степан Юрьевич
Гатилов Степан Юрьевич
кандидат наук
2016
- Специальность ВАК РФ05.13.11
- Количество страниц 184
Оглавление диссертации кандидат наук Гатилов Степан Юрьевич
Введение
0.1. Историческая справка
0.2. Представление тел
0.3. Булевы операции
0.4. Фильтрация пар граней
0.5. Пересечение граней
0.6. Содержание диссертации
Глава 1. Классификация точки относительно контура
1.1. Введение
1.2. Суммирование угла
1.3. Несколько контуров
1.4. Угол вращения вдоль ребра
1.5. Число обусловленности
1.6. Ускорение
1.6.1. Предподсчёт
1.6.2. Запрос
1.6.3. Временная сложность
1.6.4. Сравнение
1.6.5. Следствия
1.6.6. Абсолютный угол поворота
1.6.7. Результаты
1.7. NURBS-кривые
1.8. Заключение
Глава 2. Вычисление NURBS
2.1. Введение
2.2. Предварительные сведения
2.3. Прямое вычисление: поиск спана
2.4. Базисные функции
2.4.1. Формула Де Бура
2.4.2. Степенной базис
2.4.3. Смешивание контрольных точек
2.5. Подход в 3D
2.5.1. Алгоритм Де Бура
2.5.2. Кусочно-полиномиальное представление
2.6. Вычисление производных
2.6.1. Формула Де Бура
2.6.2. Многочлены
2.6.3. Смешивание контрольных точек
2.7. Предлагаемый подход
2.7.1. Векторизация
2.7.2. Поиск спана
2.7.3. Базисные функции
2.7.4. Смешивание контрольных точек
2.7.5. Производные в 3Б
2.7.6. Последние замечания
2.8. Сравнение производительности
2.9. Заключение
Глава 3. Метод Ньютона-Рафсона
3.1. Введение
3.1.1. Форсирование ранга
3.2. Теория
3.2.1. Предположения
3.2.2. Сходимость метода Ньютона
3.2.3. Трассировка кривой
3.3. Пересечение поверхностей
3.3.1. Общее описание
3.3.2. Трассировка и сходимость
3.4. Экспериментальные данные
3.4.1. Метод Ньютона-Рафсона
3.4.2. Трассировка кривой
3.5. Заключение
Глава 4. Пересечение кривых и поверхностей
4.1. Постановка задачи
4.2. Аналитические случаи
4.3. Общая схема алгоритма
4.4. Обзор литературы
4.5. Глобальный анализ
4.6. Локальный анализ
4.7. Режимы и системы уравнений
4.7.1. Несингулярная система
4.7.2. Сингулярная система
4.7.3. Масштабирование
4.7.4. Реализация
4.8. Метод Ньютона
4.9. Трассировка
4.9.1. Аппроксимация кривой
4.9.2. Определение скорости
4.9.3. Предиктор
4.9.4. Корректор
4.9.5. Построение и проверка звена
4.9.6. Адаптивность величины шага
4.9.7. Экспериментальные данные
4.10. Недопущение дубликатов
4.10.1. Проверка столкновения
4.10.2. Вычисление ширины
4.10.3. Определение точки или кривой
4.11. Поиск наложения поверхностей
4.12. Якорные точки
4.12.1. Замыкание кривой в контур
4.12.2. Завершение в якорной точке
4.12.3. Завершение на границе
4.13. Обработка границ
4.13.1. Пересечения в области определения
4.13.2. Метод Ньютона на границе
4.13.3. Кривая или точка
4.13.4. Трассировка вдоль границы
4.13.5. Гладкое сочленение поверхностей
4.14. Экспериментальные данные
4.15. Заключение
Заключение
Список литературы
Приложение А. Проверки отделимости
А.1. Ограничивающие брусы
А.2. Более точные критерии
А.3. Предлагаемый метод
А.4. Теоретическое обоснование
А.5. Аналитические случаи
А.6. Реализация
А.7. Эксперименты
Приложение Б. Проверки отсутствия сингулярностей
Б.1. Ограничивающие конусы
Б.2. Простые критерии
Б.3. Касательные конусы и конусы смещения
Б.4. Нормальные конусы
Б.5. Технические леммы
Б.6. Основная теорема
Б.7. Обсуждение
Б.8. Практическое применение
Приложение В. Ранг сингулярной системы
В.1. Порядок сингулярности
В.2. Анализ ранга
Приложение Г. Акт о внедрении
Введение
Рекомендованный список диссертаций по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК
Методы аппроксимации дискретных обводов в задачах твердотельного моделирования1999 год, кандидат технических наук Денискина, Антонина Робертовна
Обобщенные методы геометрического моделирования объектов и управления их формой при параметрическом представлении2000 год, доктор технических наук Денискин, Юрий Иванович
Применение технологии NURBS к созданию трехмерных компьютерных моделей для численного анализа начально-краевых задач2007 год, кандидат физико-математических наук Минкин, Александр Сергеевич
Генерация множества контурно-параллельных линий на основе циклографического отображения применительно к обработке карманных поверхностей2022 год, кандидат наук Мясоедова Татьяна Михайловна
Исследование методов, разработка алгоритмического и программного обеспечения пространственного анализа графической информации2005 год, кандидат технических наук Утешева, Тамара Шатовна
Введение диссертации (часть автореферата) на тему «Алгоритмы и программные средства для пересечения трёхмерных тел в граничном представлении»
Актуальность темы исследования.
Представление и обработка твёрдых тел в цифровом виде — важная проблема компьютерной графики и геометрического моделирования. Моделирование твёрдых тел является основой современных систем автоматизированного проектирования трёхмерных конструкций, а также применяется при создании геометрических объектов для визуализации в различных интерактивных приложениях. Наиболее распространённым способом моделирования твёрдых тел ныне является граничное представление, совмещающее геометрическую информацию о границе тела с топологической информацией о связности элементов границы (граней, рёбер, вершин). Для достижения высокой точности и гладкости геометрического представления используются криволинейные формы, такие как кривые и поверхности второго порядка, а также КиКЕБ-сплайны.
Трёхмерная система автоматизации проектирования (САПР) — это комплексная программная система, позволяющая инженеру проектировать различные детали, сборки и прочие конструкции. Всё взаимодействие с пользователем такие системы осуществляют самостоятельно, однако для выполнения геометрических расчётов они используют «геометрические ядра» — программные компоненты, отвечающие за представление геометрических объектов, и также за выполнение основных геометрических операций над ними. Основными геометрическими объектами в геометрических ядрах являются, разумеется, твёрдые тела в трёхмерном пространстве.
Пользователь работает с САПР в интерактивном режиме: проектируемая конструкция визуализируется в реальном времени, а при каждом содержательном изменении конструкции он вынужден дожидаться завершения пересчёта геометрии перед тем, как продолжить работу. Более того, большое распространение получил подход проектирования деталей на основе истории построения, в котором все выполненные пользователем операции сохраняются в дереве. После некоторых изменений приходится производить полный пересчёт всей геометрии модели по сохранённой истории построения. При этом выполняются десятки сложных геометрических операций над твёрдыми телами, и пользователь не может продолжать работу, пока они все не завершатся.
При выполнении геометрических операций в ходе проектирования часто возникают вырожденные ситуации различного характера. Их нельзя разрешать, например, методом возмущения входных данных, поскольку чаще всего они ключевым образом отражают идею инженера. По этой причине необходимо выполнять эти операции «как есть», решая при этом принципиально неустойчивые вычислительные задачи. Из-за принципиально неустранимой чувствительности алгоритмов к возмущениям входных данных, совмещённой с необходимостью представлять криволинейную геометрию в приближённом виде, никакое геометрическое ядро не может работать абсолютно надёжно. Критические ошибки при выполнении геометрических операций могут привести к тому, что пользователь потеряет возможность продолжать дальнейшую работу над проектируемой конструкцией, даже не поняв, что же именно произошло.
Одними из наиболее востребованных в геометрическом ядре твердотельных операций
являются регуляризованные теоретико-множественные (или «булевы») операции над телами [1]. Одной из важнейших составляющих в алгоритмах выполнения булевых операций является построение линий пересечения двумерных границ двух заданных тел. Кроме булевых операций, анализ пересечения границ тел используется также для построения сечений тела и для классификации взаимного расположения тел. Таким образом, быстродействие и надёжность алгоритмов построения линий пересечения существенно влияют на эффективность работы инженера (конечного пользователя САПР), чем объясняется актуальность выбранной темы исследования.
Данная диссертация посвящена созданию, анализу и улучшению методов, используемых для построения линий пересечения двумерных границ двух тел, заданных в граничном представлении, а также разработке программных средств, основанных на этих методах. Техническая составляющая работы заключается в реализации всех методов и алгоритмов в разрабатываемом в соответствии с федеральной целевой программой геометрическом ядре промышленного назначения «Российское Геометрическое Ядро» 1 .
Основой алгоритмов поиска линий пересечения границ тел, составленных из граней, рёбер и вершин, служат алгоритмы для поиска пересечения кривых и поверхностей, на которых лежат рёбра и грани. Большие трудности в таких алгоритмах проявляются в деталях по работе с криволинейной геометрией, особенно при возникновении вырожденных случаев [2, Глава 3]. Считается, что эти алгоритмы играют критическую роль при выполнении булевых операций над телами [3, Раздел 5.1]. Проблемой поиска пересечений, особенно для случая пересечения поверхностей, занимались такие исследователи, как C. M. Hoffmann, C. L. Bajaj, R. E. Barnhill, M. E. Hohmeyer, T. W. Sederberg, T. A. Grandine, D. Manocha, T. Maekawa. Большинство известных решений ориентировано в первую очередь на невырожденные случаи, поскольку в этих случаях можно гарантировать корректность работы алгоритма.
В граничном представлении для каждой грани тела задаётся базовая поверхность, однако в общем случае грань является лишь частью этой поверхности, ограниченной контурами обрезки, составленными из всех рёбер тела, лежащих на краю этой грани. Учёт контуров обрезки обычно производится в двумерном параметрическом пространстве поверхности. Поэтому часто возникает задача определения, лежит ли точка внутри заданного контура на плоскости, являющаяся классической задачей вычислительной геометрии. Этой задаче уделяли внимание E. Haines, K. Hormann, F. R. Feito, I. Kolingerova, D. Kirkpatrick, R. E. Tarjan. Практически любое из многочисленных известных решений страдает хотя бы одним из следующих недостатков: предназначено только для многоугольников без криволинейных рёбер; имеет проблемы с надёжностью (устойчивостью); излишне сложное в практической реализации; нет возможности ускорения за счёт предподсчёта; отсутствуют доказанные нетривиальные оценки быстродействия.
NURBS-сплайны активно применяются для представления криволинейной геометрии в общем случае; не только в геометрических ядрах САПР, но и в распространённых системах трёхмерной графики и анимации. Основные результаты, связанные с NURBS, получены такими известнейшими учёными, как M. G. Cox, C. de Boor, W. Boehm, R. Risenfeld, K. J. Versprille. На вычисление значений и производных NURBS может уходить значительная
1 Полное название целевой программы приводится далее в секции практической значимости работы.
доля времени в алгоритмах геометрического ядра, включая алгоритмы пересечения NURBS кривых и поверхностей. Несмотря на то, что основные алгоритмы для вычисления NURBS известны уже примерно полвека, по-прежнему актуален вопрос эффективного использования имеющихся вычислительных ресурсов на уровне аппаратных возможностей компьютера.
При работе с криволинейной геометрией возникает необходимость решать нелинейные системы уравнений, для этого часто используется метод Ньютона-Рафсона [4]. Предлагаемый подход к пересечению кривых и поверхностей существенно основывается на представлении точек пересечения как решений систем нелинейных уравнений. В некоторых случаях система имеет неполный ранг, поэтому возникает вопрос: можно ли применять классические численные методы в этом случае? Подобные вопросы рассматривались в работах A. Ben-Israel, J. P. Dedieu, однако полученные ими результаты неприменимы в некоторых рассматриваемых в данной работе случаях.
Цели и задачи диссертационной работы. Цель работы — создание алгоритмов и программных средств для поиска линий пересечения границ трёхмерных твёрдых тел, заданных в граничном представлении.
Для достижения данной цели были поставлены следующие задачи:
1. создать программную компоненту для поиска пересечений параметрических кривых и поверхностей;
2. исследовать проблему трассировки кривых пересечения в вырожденных случаях и предложить её решения;
3. разработать простой для реализации и анализа эффективный алгоритм определения положения точки относительно контура;
4. разработать быстрые алгоритмы вычисления NURBS.
Научная новизна.
1. Применяется не используемая ранее система уравнений для поиска сингулярных кривых пересечения поверхностей, для работы с ней предложен метод форсирования ранга и адаптированы численные методы: метод Ньютона-Рафсона и метод трассировки «предиктор-корректор».
2. Доказана новая качественная теорема о наличии локальной квадратичной сходимости метода Ньютона-Рафсона при использовании форсирования ранга. Теорема является обобщением теоремы о наличии сходимости в случае постоянства ранга матрицы Якоби.
3. Доказана новая теорема о быстродействии алгоритма суммирования угла вращения с иерархией ограничивающих объёмов, связывающая время работы алгоритма со специальной характеристикой — числом обусловленности, которое зависит только от свойств контура и проверяемой точки. Доказана оценка числа обусловленности, которая не зависит от положения точки.
4. Предложен и реализован векторизованный алгоритм прямого вычисления NURBS поверхностей, работающий существенно быстрее известных аналогов.
Теоретическая и практическая значимость. Результаты, изложенные в диссертации, могут быть использованы на практике в системах геометрического моделирования и компьютерной графики. Большая часть результатов была использована при разработке «Российского Геометрического Ядра» в рамках проекта «Создание отечественного лицензируемого
программно-математического ядра 3-мерного моделирования как базы для компьютерных систем автоматизированного проектирования сложной машиностроительной продукции» в соответствии с подпрограммой «Развитие отечественного станкостроения и инструментальной промышленности» на 2011-2016 годы федеральной целевой программы «Национальная технологическая база» на 2007-2011 годы. Имеется акт о внедрении результатов диссертации (в последнем приложении).
Кроме того, некоторые результаты имеют теоретическую значимость. Теорема о сходимости метода Ньютона-Рафсона с форсированием ранга может быть применена в любой области для качественного анализа поведения метода на вырожденных системах уравнений с некоторыми свойствами. Классификация положения точки относительно контура — классическая задача вычислительной геометрии, поэтому доказанная асимптотическая оценка времени работы алгоритма может помочь при дальнейшем изучении теоретической сложности данной задачи.
Достоверность результатов происходит из нескольких источников. Теоретические результаты опираются на математические утверждения, строго сформулированные и последовательно доказанные. Программные реализации алгоритмов были всесторонне протестированы: результаты вычислений оценивались визуально, сравнением с теоретически верными результатами, проверкой на соответствие спецификации задачи; результаты проверялись на соответствие и согласованность с результатами других алгоритмов, как реализованных автором диссертации, так и взятых из сторонних программ. Корректность измерений производительности обеспечивается чётким описанием схемы проводимых замеров, усреднением времени работы по многократным запускам, использованием одного и того же вычислительного устройства для всех замеров.
На защиту выносятся следующие положения, соответствующие пункту 7 паспорта специальности 05.13.11:
1. Создана программная компонента для определения принадлежности точки области, ограниченной заданным контуром, основанная на разработанном алгоритме суммирования угла вращения с иерархией ограничивающих объёмов, и доказаны оценки времени работы этого алгоритма.
2. Предложен, программно реализован и интегрирован в геометрическое ядро быстрый алгоритм вычисления значений и производных NURBS поверхностей, использующий векторизацию.
3. Для поиска кривых касания поверхностей предложена специальная система уравнений и разработан метод форсирования ранга, доказаны утверждения о корректности метода.
4. Создана программная компонента локального анализа для решения задачи определения пересечения параметрических кривых и поверхностей.
Апробация результатов. Основные результаты диссертации докладывались на следующих конференциях: международный симпозиум GAMM - IMACS по научным вычислениям, компьютерным арифметикам и доказательным численным методам (Новосибирск, 2012), российско-монгольская конференция молодых учёных по математическому моделированию, вычислительным технологиям и управлению (Иркутск, 2015), конференция «Актуальные
проблемы вычислительной и прикладной математики» (Новосибирск, 2015), международная научная студенческая конференция «Студент и научно-технический прогресс»(Новосибирск, 2015). Кроме того, автор выступал с материалами диссертации на семинаре «Системное программирование» института систем информатики СО РАН, на семинаре лаборатории параллельных алгоритмов решения больших задач института вычислительной математики и математической геофизики (ИВМиМГ) СО РАН и на объединённом семинаре «Численный анализ» ИВМиМГ СО РАН и кафедры вычислительной математики ММФ НГУ.
Публикации. Материалы диссертации опубликованы в 8 научных работах, из них 3 статьи в иностранных рецензируемых журналах, входящих в библиографическую базу Scopus [5-7], и 5 тезисов докладов [8-12].
Личный вклад автора. Все представленные в диссертации результаты получены лично автором. Вся работа теоретического характера и подготовка всех публикаций также была выполнена лично автором. Практическая реализация алгоритмов в рамках проекта «Российское Геометрическое Ядро» выполнялась совместно с другими разработчиками проекта, однако вклад соискателя в реализацию описанных в диссертации алгоритмов был определяющим.
Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения, четырёх приложений и списка литературы. Общий объём диссертации составляет 184 страницы, из них 151 страница основного текста, включая 42 рисунка. Список литературы включает 136 наименований.
0.1. Историческая справка
12 июня 1994 года совершил свой первый полёт самолёт Boeing 777, разработка которого была выполнена полностью в цифровом виде без применения бумажных чертежей. Это стало возможным благодаря системе автоматизированного проектирования CATIA, позволившей протестировать проект без создания полномасштабного макета самолёта.
Системы автоматизированного проектирования (САПР) используются для автоматизации создания двумерных и трёхмерных геометрических моделей. Создаваемые модели используются в смежных системах, таких как средства автоматизации инженерных расчётов, анализа и симуляции физических процессов, а также автоматизированные системы технологической подготовки производства. В результате инженерам предоставляется возможность без больших затрат времени и средств оценить работоспособность и проанализировать поведение изделия по компьютерной модели, а также упростить программирование станков с ЧПУ.
Ещё в начале 50-ых годов компьютеры использовались при проектировании. Например, работа [13] от 1953 года описывает расчёт траектории движения для управления фрезерным станком. В производстве самолётов также использовались компьютерные расчёты и геометрическое моделирование для решения отдельных задач. Первой интерактивной САПР с графическим интерфейсом принято считать созданную в начале 60-ых годов программу Sketchpad [14], автор которой получил премию Тьюринга в 1988 году. В 70-ых годах стали появляться первые коммерческие САПР, а в 80-ых годах стали появляться САПР для персо-
нальных компьютеров. Сегодня разработку высокотехнологичных изделий сложно представить без САПР.
В первых трёхмерных САПР использовалось каркасное представление твёрдых тел: хранились только вершины тел и соединяющие их прямолинейные рёбра. Только в системе BUILD1 [15], разработанной Яном Брэйдом в Кембридже в 1973 году, впервые использовалось граничное представление твёрдых тел (хотя набор поверхностей ограничивался лишь плоскостями и цилиндрами). Так было положено начало полноценному твердотельному моделированию.
Параллельно расширялся арсенал криволинейных кривых и поверхностей. В работе [16] были введены поверхности Кунса, позволяющие натягивать поверхности по четырёхугольным каркасам. Кривые и поверхности Безье были изобретены независимо Де Кастельжо [17] и Безье [18] [19] в 60-ых годах2. В начале 70-ых годов в геометрическом моделировании впервые были применены B-сплайны [22], и вскоре их применение было расширено на нерациональный случай [23], породив NURBS кривые и поверхности, повсеместно используемые для геометрического представления по сей день.
В 1982 году группа создателей системы BUILD разработала первое геометрическому ядро Romulus, предназначенное для интегрирования в приложения САПР. В конце 80-ых были созданы коммерческие ядра Parasolid и ACIS, которые являются наиболее используемыми геометрическими ядрами на сегодняшний день. Ядром геометрического моделирования (геометрическим ядром) называют математическую библиотеку для работы с трёхмерными объектами. Ядро отвечает за представление геометрической модели в цифровом виде и за выполнение различных геометрических операций. Современные геометрические ядра реализуют большой набор функциональностей для работы с твёрдыми телами, например: булевы операции, сглаживание рёбер и вершин, аппроксимация полигональной моделью, построение силуэтных линий, определение столкновений, расстояний и массовых характеристик, построение тел проведением и вращением профилей, утолщение элементов модели, работа со сборками из множества отдельных тел и так далее.
В 2012 году в соответствии с федеральной целевой программой «Национальная Технологическая База»: «Создание отечественного лицензируемого программно-математического ядра 3-мерного моделирования как базы для компьютерных систем автоматизированного проектирования сложной машиностроительной продукции» началась разработка «Российского Геометрического Ядра» (RGK) [24]. Данная диссертация посвящена решению некоторого набора задач, возникших при создании геометрического ядра. Все результаты работы были в той или иной мере использованы на практике в Российском Геометрическом Ядре.
0.2. Представление тел
Для представления твёрдых тел в современных САПР почти всюду используются два формата. Базовым форматом является граничное представление (B-Rep), описывающее границу произвольного твёрдого тела геометрически и топологически. Другим форматом является конструктивная блочная геометрия (CSG), в которой тело представляется как булева
2 Лежащие в основе многочлены были использованы Бернштейном ещё в 1912 году [20] [21].
формула от базовых тел (блоков). Именно эти два представления поддерживаются нейтральными форматами IGES и STEP [25].
Следует заметить, что представление CSG не является самодостаточным, потому что базовые блоки необходимо описывать другим способом (например, как клетки свободной формы [26]), либо ограничиваться только малым набором простейших аналитических примитивов. Кроме того, над телами в формате CSG сложно выполнять большинство операций, поскольку не хранится ни геометрическая, ни топологическая информация о вершинах и рёбрах. Поэтому всюду в геометрических ядрах используется граничное представление в качестве основного.
Кроме того, нельзя не упомянуть другие способы представления тел, применяющиеся в настоящее время. В функциональном представлении (F-Rep) [27] твёрдое тело отождествляется с множеством точек, в которых положительно значение некоторой функции, обычно строящейся с применением теории R-функций [28, 29]. В некотором смысле F-Rep является расширением подхода CSG, в котором граница тела представляется при помощи единой неявной поверхности. Другой способ представления тел без зазоров между гранями — T-сплайны [30]. Этот вариант является обобщением NURBS-поверхностей, позволяющим представлять границу твёрдого тела без зазоров [31].
Математически можно считать твёрдым телом произвольное множество точек S С R3. Поскольку геометрические модели САПР имеют инженерное назначение, на твёрдые тела накладываются некоторые ограничения [32, Глава II]:
1. S — регулярное, то есть равно замыканию своей внутренности (S = S°).
2. S — ограниченное.
3. Граница dS может быть описана конечным объёмом информации.
С другой стороны, твёрдое тело также определяют непосредственно через его границу [2, Раздел 2.3]. Пусть В — ориентируемое замкнутое двумерное многообразие, вложенное в трёхмерное пространство. Тогда по теореме Жордана-Брауэра пространство без В разбивается на две несвязные части: внешнюю и внутреннюю. Внутреннюю часть можно считать твёрдым телом, ограниченным многообразием В.
Граничное представление тела состоит из топологической и геометрической информации. Геометрическая информация описывает исключительно границу тела, таким образом оправдывая название представления. В качестве чисто геометрических элементов используются точки, кривые и поверхности, причём обычно все кривые и поверхности гладкие. На рисунке 1 схематично изображены различные топологичные элементы. Основные топологические элементы твёрдого тела — вершины, рёбра и грани (как при описании многогранников).
Геометрически каждая грань представляет из себя обрезанную поверхность, поэтому в ней хранится базовая поверхность и набор циклов обрезки. Для грани всегда имеется возможность определить, с какой стороны находится тело, что обычно достигается хранением флага о совпадении внешней нормали грани и натуральной нормали базовой поверхности. Края граней задаются при помощи рёбер, геометрически представляющих из себя кривые. В каждом ребре смыкаются две грани или грань сама с собой. На каждом конце ребра расположена вершина. Обычно в вершине сходится хотя бы по три грани и ребра, хотя это не обязательно. Обрезка грани состоит из набора непересекающихся циклов, один из которых
Рис. 1. Иллюстрация топологических элементов граничного представления.
должен быть внешним, а другие — внутренними. Каждый цикл задаётся последовательностью ориентированных рёбер, лежащих на краю этой грани.
Следует заметить, что грани, рёбра и вершины модели не должны дублироваться. Во всех топологических элементах хранится информация об инцидентных элементах другого типа. Так, например, для ребра всегда можно найти концевые вершины и инцидентные грани, для вершины можно обойти все инцидентные рёбра и грани, а для грани можно обойти все рёбра и вершины, лежащие на ней. Различные ссылочные структуры данных позволяют выполнять эти задачи с разными показателями эффективности и удобства. Примером может служить классическая «крылатая» структура [33]. Более распространённая «радиальная» структура рассмотрена в [34], там же имеется обзор других структур. Ориентированные версии топологических элементов иногда выносятся в отдельные топологические элементы, которые (в случае рёбер) называются полурёбрами, корёбрами, или «использованиями» рёбер (edgeuse) [34].
Помимо основных топологических элементов, обычно используют и чисто топологические элементы высокого уровня, такие как оболочки и регионы. Оболочка представляет из себя компоненту связности границы тела, состоящую из набора граней вместе с инцидентными вершинами и рёбрами. Регион является связной частью тела как множества точек. Каждый регион должен быть ограничен ровно одной внешней оболочкой, а также, возможно, несколькими внутренними.
Геометрические данные определяют положения вершин, кривые рёбер и базовые поверхности граней. Кривые и поверхности могут быть заданы аналитически, то есть как один из простейших примитивов. Часто используемые примитивы: отрезок прямой, дуга окружности, а также части плоскости, цилиндра, сферы, конуса, тора. Исторически, изначально в граничном представлении применялся только этот способ, потому что аппаратное обеспечение было недостаточно быстрым для работы с неаналитической геометрией. Сегодня каждое геометрическое ядро поддерживает также задание кривых и поверхностей в виде NURBS сплайнов. Несмотря на возможность задания сплайновых кривых и поверхностей, большая часть геометрических элементов в машиностроительных моделях всё равно задаётся анали-
Рис. 2. Пример определения NURBS кривой5(нерациональный случай).
тически.
Аббревиатура NURBS расшифровывается как «неоднородный рациональный B-сплайн». NURBS кривая является параметрической кривой С(t) : [l;r] ^ R3, а NURBS поверхность — параметрической поверхностью S(и, v) : [a; b] х [с; d] ^ R3. Определяются NURBS кривые и поверхности следующим образом (пример приводится на рисунке 2).
Базисные функции Ni^(t) B-сплайна степени d определяются по массиву узлов {к{\ рекуррентной формулой
'NM = + liS+A^^+i^) 3
Nifi(t) = I(ki ^ t < кг+1). 4
Далее, имея массив контрольных точек Pi и соответствующих им весов wi, можно определить NURBS-кривую как
С (f) = EiNi,d(t)WiPi
() EiNiAt)wi .
Аналогично, по двум семействам базисных функций и сетке контрольных точек Pij и весов wi,j определяется NURBS-поверхность:
S( и, )
Похожие диссертационные работы по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК
Формообразование линий и поверхностей на основе кривых второго порядка в компьютерном геометрическом моделировании2018 год, доктор наук Короткий Виктор Анатольевич
Автоматизация построения судовой поверхности по линиям теоретического чертежа2024 год, кандидат наук Шоркина Ирина Николаевна
Топологическая классификация интегрируемых систем типа Чаплыгина-Горячева2019 год, кандидат наук Николаенко Станислав Сергеевич
Методы и средства повышения точности обработки фасонных деталей на фрезерных станках с ЧПУ2002 год, кандидат технических наук Грошев, Александр Владимирович
Многогранные метрики на границах выпуклых гиперболических многообразий и изгибаемость многогранников в пространстве Лобачевского2016 год, кандидат наук Слуцкий Дмитрий Анатольевич
Список литературы диссертационного исследования кандидат наук Гатилов Степан Юрьевич, 2016 год
Список литературы
Requicha A. A. G., Rossignac J. R. Solid Modeling and Beyond // IEEE Comput. Graph. Appl. 1992. Vol. 12, no. 5. P. 31-44.
Hoffmann C. M. Geometric and Solid Modeling: An Introduction. San Mateo, Calif. Morgan Kaufmann, 1989.
Krishnan S., Manocha D. et al. BOOLE: A Boundary Evaluation System for Boolean Combinations of Sculptured Solids // International Journal of Computational Geometry and Applications. 2001. Vol. 11. P. 105-144.
Голованов Н. Геометрическое моделирование. Высшее профессиональное образование. Информатика и вычислительная техника. Академия, 2011.
Gatilov S. Y. Efficient Angle Summation Algorithm for Point Inclusion Test and Its Robustness // Reliable Computing. 2013. Vol. 19. P. 1-25.
Gatilov S. Y. Using low-rank approximation of the Jacobian matrix in the Newton-Raph-son method to solve certain singular equations // Journal of Computational and Applied Mathematics. 2014. Vol. 272. P. 8-24.
Gatilov S. Y. Vectorizing NURBS surface evaluation with basis functions in power basis // Computer-Aided Design. 2015. DOI: 10.1016/j.cad.2015.10.006.
Gatilov S. Y. Efficient angle summation algorithm for point inclusion test and its robustness // 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetics and Verified Numerics. 2012.
Гатилов С. Ю. Практический подход к прямому и обратному вычислению NURBS поверхностей и кривых // матер. 53-й межд. научн. студ. конф. информ. техн. 2015. Гатилов С. Ю. Аппроксимация малого ранга матрицы Якоби в методе Ньютона-Раф-сона для решения вырожденных уравнений // матер. 53-й межд. научн. студ. конф. математика. 2015.
Гатилов С. Ю. Поиск пересечения кривых и поверхностей в трёхмерном пространстве при помощи метода трассировки // III российско-монгольская конф. мол. уч. по мат. мод., выч.-инф. техн. и управлению. 2015.
Гатилов С. Ю. Трассировка кривой пересечения поверхностей // тезисы межд. конф. «Актуальные проблемы вычислительной и прикладной математики». 2015. McDonough J. C., Susskind A. W. A Numerically Controlled Milling Machine: Tech. rep.: Massachusetts Institute of Technology Servomechanisms Laboratory, 1953. Sutherland I. E. Sketchpad: A man-machine graphical communication system: Ph. D. thesis / Massachusetts Institute of Technology. 1963.
Braid I. Designing with volumes: Ph. D. thesis / Cambridge University. 1974.
Coons S. A. Surfaces for Computer-aided design of space forms: Tech. rep.: Massachusetts
Institute of Technology, 1967.
Paul de Casteljau. Courbes et Surfaces a Poles: Tech. rep.: Societe Anonyme Andre Citroen, 1963.
Bezier P. Definition numerique des courbes et surfaces I // Automatisme. 1966. Vol. XI. P. 625-632.
19. Bezier P. Essai de definition numerique des courbes et des surfaces experimentales: contribution a l'etude des proprietes des courbes et des surfaces parametriques polynomiales a coefficients vectoriels: Ph. D. thesis / University of Paris VI. 1977.
20. Bernstein S. Demonstration du theoreme de Weierstrass fondee sur le calcul des probabilites // Communications de la Societe Mathematique de Kharkov. 1913. P. 1-2.
21. Farouki R. T. The Bernstein Polynomial Basis: A Centennial Retrospective // Computer Aided Geometric Design. 2012. Vol. 29, no. 6. P. 379-419.
22. Risenfeld R. Applications of B-Spline Approximation to Geometric Problems of CAD: Ph. D. thesis / Syracuse University. 1973.
23. Versprille K. J. Computer-Aided Design Applications of the Rational B-Spline Approximation: Ph. D. thesis / Syracuse University. 1975.
24. Баранов Л., Козлов С., Сёмин Д., Снытников Н. Российское 3D-ядро. 2013. URL: http://isicad.ru/ru/articles.php?article_num=16129.
25. Marjudi S., Amran M. F. M., Abdullah K. A. et al. A Review and Comparison of IGES and STEP // Proceedings Of World Academy Of Science. Vol. 62 of Engineering And Technology. 2010. P. 1013-1017.
26. Garcia A., de Miras J. R., Fieto F. Free-form solid modelling based on extended simplicial chains using triangular Bezier patches // Computers & Graphics. 2003. Vol. 27, no. 1. P. 27-39.
27. Pasko A., Adzhiev V., Sourin A., Savchenko V. Function representation in geometric modeling: concepts, implementation and applications // The Visual Computer. 1995. Vol. 11, no. 8. P. 429-446.
28. Shapiro V. Semi-analytic geometry with R-functions // Acta Numerica. 2007. — 5. Vol. 16. P. 239-303.
29. Рвачев В. Теория Р-функций и некоторые ее приложения. Наукова думка, 1982.
30. Sederberg T. W., Zheng J., Bakenov A., Nasri A. T-splines and T-NURCCs // ACM SIG-GRAPH 2003 Papers. SIGGRAPH '03. ACM, 2003. P. 477-484.
31. Sederberg T. W., Finnigan G. T., Li X. et al. Watertight Trimmed NURBS // ACM SIGGRAPH 2008 Papers. SIGGRAPH '08. ACM, 2008. P. 79:1-79:8.
32. Hoffmann C. M., Vanecek G. Fundamental Techniques for Geometric and Solid Modeling: Tech. rep.: Computer Science Technical Reports, 1991. Paper 885.
33. Baumgart B. G. A Polyhedron Representation for Computer Vision // Proceedings of the May 19-22, 1975, National Computer Conference and Exposition. AFIPS '75. 1975. P. 589-596.
34. Weiler K. J. Topological Structures for geometric modeling: Ph. D. thesis / Rensselaer Polytechnic Institute. 1986.
35. Piegl L., Tiller W. The NURBS Book (2nd Ed.). New York, NY, USA: Springer-Verlag New York, Inc., 1997.
36. Siemens Product Lifecycle Management Software Inc. Parasolid XT Format Reference, 2008. —april.
37. Katz S., Sederberg T. W. Genus of the Intersection Curve of Two Rational Surface Patches // Comput. Aided Geom. Des. 1988. Vol. 5, no. 3. P. 253-258.
38. Keyser J., Culver T., Foskey M. et al. ESOLID - a system for exact boundary evaluation // Computer-Aided Design. 2004. Vol. 36. P. 175-193.
39. Arruda M., Miranda A., Lira W., Martha L. Boolean Operations on Non-Manifold and B-Rep Solids for Mesh Generation // XXVII CILAMCE. 2006.
40. Lo S., Wang W. A fast robust algorithm for the intersection of triangulated surfaces // Engineering with Computers. 2004. Vol. 20, no. 1. P. 11-21.
41. Nakamura H., Higashi M., Hosaka M. Robust Computation of Intersection Graph between Two Solids // Computer Graphics Forum. 1997. Vol. 16, no. 3. P. 79-88.
42. Ouchi K., Keyser J. Handling Degeneracies in Exact Boundary Evaluation // Proceedings of the Ninth ACM Symposium on Solid Modeling and Applications. SM '04. Eurographics Association, 2004. P. 321-326.
43. Zhou Y., Suri S. Analysis of a Bounding Box Heuristic for Object Intersection //J. ACM. 1999. Vol. 46, no. 6. P. 833-857.
44. Gino van den Bergen. Efficient Collision Detection of Complex Deformable Models Using AABB Trees // J. Graph. Tools. 1998. Vol. 2, no. 4. P. 1-13.
45. Hohmeyer M. E. Robust and Efficient Surface Intersection for Solid Modeling: Ph. D. thesis / University of California. 1986.
46. Martin W., Cohen E., Fish R., Shirley P. Practical Ray Tracing of Trimmed NURBS Surfaces // J. Graph. Tools. 2000. Vol. 5, no. 1. P. 27-52.
47. Pabst H.-F., Springer J., Schollmeyer A. et al. Ray Casting of Trimmed NURBS Surfaces on the GPU // IEEE Symposium on Interactive Ray Tracing. 2006. P. 151-160.
48. Weiler K., Atherton P. Hidden Surface Removal Using Polygon Area Sorting // SIGGRAPH Comput. Graph. 1977. Vol. 11, no. 2. P. 214-222.
49. Дебелов В. А., Мацокин А. М. Алгоритм реализации теоретико-множественных операций // 8-я Международная конференция по компьютерной графике и визуализации (Графикон'98). 1998. С. 173-181.
50. Haines E. Point in polygon strategies // Graphics gems IV. San Diego, CA, USA: Academic Press Professional, Inc., 1994. P. 24-46.
51. Huang C.-W., Shih T.-Y. On the complexity of point-in-polygon algorithms // Computers and Geosciences. 1997. Vol. 23, no. 1. P. 109-118.
52. Schirra S. How Reliable Are Practical Point-in-Polygon Strategies? // Proceedings of the 16th annual European symposium on Algorithms. ESA '08. 2008. P. 744-755.
53. Hormann K., Agathos A. The point in polygon problem for arbitrary polygons // Comput. Geom. Theory Appl. 2001. Vol. 20, no. 3. P. 131-144.
54. Sarnak N., Tarjan R. E. Planar point location using persistent search trees // Commun. ACM. 1986. Vol. 29, no. 7. P. 669-679.
55. Edelsbrunner H., Guibas L. J., Stolfi J. Optimal point location in a monotone subdivision // SIAM J. Comput. 1986. Vol. 15, no. 2. P. 317-340.
56. Kirkpatrick D. Optimal search in planar subdivisions // SIAM Journal on Computing. 1983. Vol. 12. P. 28-35.
57. Zalik B., Kolingerova I. A cell-based point-in-polygon algorithm suitable for large sets of points // Computers & Geosciences. 2001. Vol. 27, no. 10. P. 1135-1145.
58. Yang S., Yong J.-H., Sun J. et al. A point-in-polygon method based on a quasi-closest point // Computers & Geosciences. 2010. Vol. 36, no. 2. P. 205-213.
59. Poveda J., Gould M., Oliveira A. A New Quick Point Location Algorithm // Conceptual Modeling for Advanced Application Domains. Springer Berlin Heidelberg, 2004. Vol. 3289 of Lecture Notes in Computer Science. P. 184-194.
60. Jimenez J. J., Feito F. R., Segura R. J. A new hierarchical triangle-based point-in-polygon data structure // Computers & Geosciences. 2009. Vol. 35, no. 9. P. 1843-1853.
61. Li J., Wang W., Wu E. Point-in-polygon tests by convex decomposition // Computers & Graphics. 2007. Vol. 31, no. 4. P. 636-648.
62. Miras J. D., Feito F. Inclusion test for curved-edge polygons // Computers & Graphics. 1997. Vol. 21, no. 6. P. 815-824.
63. Kpalma K., Yang M. Polygon interior point query and applications // Communication Technology (ICCT), 2011 IEEE 13th International Conference on. 2011. P. 814-818.
64. Leland K. O. An Algorithm for Winding Numbers for Closed Polygonal Paths // Mathematics of Computation. 1975. Vol. 29, no. 130. P. 554-558.
65. Dind J., Wang Q., Liu G. et al. PIP Algorithm Based on Monolithic Calculation for Included Angle of Half Plane Continuous Chains // Advances in Information Sciences and Service Sciences. 2013. Vol. 5. P. 412-418.
66. Jr. W. L., Preparata F. P. Finding the Contour of a Union of Iso-Oriented Rectangles. // J. Algorithms. 1980. Vol. 1, no. 3. P. 235-246.
67. Arvo J., Kirk D. A Survey of Ray Tracing Acceleration Techniques // An Introduction to Ray Tracing / Ed. by A. S. Glassner. London, UK: Academic Press Ltd., 1989. P. 201-262.
68. Yao A. C., Rivest R. L. On the Polyhedral Decision Problem // Journal on Computing. 1980. Vol. 9, no. 2. P. 483-494.
69. Grigoriev D., Karpinski M. Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees: Tech. rep.: University of Bonn, 1993.
70. Skala V. Trading Time for Space: an O(1) Average time Algorithm for Point-in-Polygon Location Problem. Theoretical Fiction or Practical Usage // Machine Graphics and Vision. 1996. Vol. 5, no. 3. P. 343-347.
71. Klein F. A New Approach to Point Membership Classification in B-rep Solids // Proceedings of the 13th IMA International Conference on Mathematics of Surfaces XIII. 2009. P. 235-250.
72. Nishita T., Sederberg T. W., Kakimoto M. Ray tracing trimmed rational surface patches // SIGGRAPH Comput. Graph. 1990. Vol. 24, no. 4. P. 337-345.
73. Piegl L. On NURBS: A Survey // IEEE Comput. Graph. Appl. 1991. Vol. 11, no. 1. P. 55-71.
74. Piegl L. A., Richard A. M. Tessellating trimmed nurbs surfaces // Computer-Aided Design. 1995. Vol. 27, no. 1. P. 16-26.
75. Luken W. L. Tessellation of Trimmed NURB Surfaces // Comput. Aided Geom. Des. 1996. Vol. 13, no. 2. P. 163-177.
76. Ma Y. L., Hewitt W. Point inversion and projection for NURBS curve and surface: Control polygon approach // Computer Aided Geometric Design. 2003. Vol. 20, no. 2. P. 79-99.
77. Selimovic I. Improved algorithms for the projection of points on NURBS curves and surfaces // Computer Aided Geometric Design. 2006. Vol. 23, no. 5. P. 439-445.
78. Hu S.-M., Wallner J. A second order algorithm for orthogonal projection onto curves and surfaces // Computer Aided Geometric Design. 2005. Vol. 22, no. 3. P. 251-260.
79. Bajaj C. L., Hoffmann C. M., Lynch R. E., Hopcroft J. E. Tracing surface intersections. // Computer Aided Geometric Design. 1988. Vol. 5, no. 4. P. 285-307.
80. Barnhill R., Kersey S. A marching method for parametric surface/surface intersection // Computer Aided Geometric Design. 1990. Vol. 7, no. 1-4. P. 257-280.
81. Mann S., DeRose T. Computing values and derivatives of Bezier and B-spline tensor products // Computer Aided Geometric Design. 1995. Vol. 12, no. 1. P. 107-110.
82. Sederberg T. W. Point and tangent computation of tensor product rational Bezier surfaces // Computer Aided Geometric Design. 1995. Vol. 12, no. 1. P. 103-106.
83. Sanchez H., Moreno A., Oyarzun D., Garcia-Alonso A. Evaluation of NURBS Surfaces: An Overview Based on Runtime Efficiency // WSCG (Short Papers). 2004. P. 235-242.
84. Krishnamurthy A., Khardekar R., McMains S. Optimized GPU evaluation of arbitrary degree NURBS curves and surfaces // Computer-Aided Design. 2009. Vol. 41, no. 12. P. 971-980.
85. Intel. Intel 64 and IA-32 Architectures Optimization Reference Manual, 2014.
86. Jankauskas K. Time-Efficient NURBS Curve Evaluation Algorithms // Proceedings of the 16th international conference on Information and Software Technologies. Information Technologies 2010. P. 60-69.
87. Prautzsch H., Boehm W., Paluszny M. Bezier and B-Spline Techniques. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2002.
88. Pankiewicz W. Algorithm 337: Calculation of a Polynomial and Its Derivative Values by Horner Scheme // Communications of the ACM. 1968. Vol. 11, no. 9. P. 633.
89. Поляк Б. Т. Метод Ньютона и его роль в оптимизации и вычислительной математике // Труды Института системного анализа РАН. 2008. Т. 28. С. 48-66.
90. Ben-Israel A. A Newton-Raphson Method for the Solution of Systems of Equations // J. Math. Anal. Appl. 1966. Vol. 15. P. 243-252.
91. Smale S. Newton's method estimates from data at one point // The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. 1986. P. 185-196.
92. Dedieu J. P., Shub M. Newton's method for overdetermined systems of equations // Math. Comput. 2000. Vol. 69. P. 1099-1115.
93. Dedieu J.-P., Kim M.-H. Newton's method for analytic systems of equations with constant rank derivatives //J. Complex. 2002. Vol. 18. P. 187-209.
94. Xu X., Li C. Convergence of Newton's Method for Systems of Equations with Constant Rank Derivatives // J. Comp. Math. 2007. Vol. 25. P. 705-718.
95. Wei F., Feng J., Lin H. GPU-based Parallel Solver via the Kantorovich Theorem for the Nonlinear Bernstein Polynomial Systems // Comput. Math. Appl. 2011. Vol. 62, no. 6. P. 2506-2517.
96. Годунов С. К. и др. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Наука, 1988.
97. Чеверда В. А., Костин В. И. r-псевдообратный для компактного оператора // Сиб. электрон. матем. изв. 2010. Т. 7. С. 258-282.
98. Stewart G. W., Sun J.-G. Matrix Perturbation Theory. Computer Science and Scientific
Computing. Academic Press, 1990.
99. Chan T. F. Rank revealing QR factorizations // Linear Algebra and its Applications. 1987. Vol. 88-89. P. 67-82.
100. Businger P., Golub G. H. Linear Least Squares Solutions by Householder Transformations // Numerische Mathematik. 1965. Vol. 7, no. 3. P. 269-276.
101. Gu M., Eisenstat S. C. Efficient Algorithms for Computing a Strong Rank-revealing QR Factorization // SIAM J. Sci. Comput. 1996. Vol. 17, no. 4. P. 848-869.
102. Kahan W. M. Numerical Linear Algebra // Canadian Mathematical Bulletin. 1966. Vol. 9. P. 757-801.
103. Wang G., Wei Y., Qiao S. Generalized Inverses: Theory and Computations. 2004.
104. Boothby W. An Introduction to Differentiable Manifolds and Riemannian Geometry. Revised, 2 edition. Academic Press, 2002.
105. Allgower E. L., Georg K. Introduction to Numerical Continuation Methods. Classics in Applied Mathematics 45. SIAM, 2003.
106. Sederberg T. W., Christiansen H. N., Katz S. Improved Test for Closed Loops in Surface Intersections // Comput. Aided Des. 1989. Vol. 21, no. 10. P. 505-508.
107. Ye X., Maekawa T. Differential geometry of intersection curves of two surfaces // Computer Aided Geometric Design. 1999. Vol. 16, no. 8. P. 767-788.
108. Mukundan H., Ko K. H., Maekawa T. et al. Tracing Surface Intersections with Validated ODE System Solver // Proceedings of the Ninth ACM Symposium on Solid Modeling and Applications. SM '04. 2004. P. 249-254.
109. Patrikalakis N. M., Maekawa T. Shape interrogation for computer aided design and manufacturing. Springer, 2002.
110. Miller J. R., Goldman R. N. Geometric Algorithms for Detecting and Calculating All Conic Sections in the Intersection of Any Two Natural Quadric Surfaces // Graph. Models Image Process. 1995. Vol. 57, no. 1. P. 55-66.
111. Dupont L., Lazard D., Lazard S., Petitjean S. Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm // Journal of Symbolic Computation. 2008. Vol. 43, no. 3. P. 168-191.
112. Kim K.-J., Kim M.-S., Oh K. Torus/Sphere Intersection Based on a Configuration Space Approach // Graphical Models and Image Processing. 1998. Vol. 60, no. 1. P. 77-92.
113. Kim K.-J. Circles in torus-torus intersections // Journal of Computational and Applied Mathematics. 2012. Vol. 236, no. 9. P. 2387-2397.
114. Jia X., Tu C., Wang W. Topological classification of non-degenerate intersections of two ring tori // Computer Aided Geometric Design. 2013. Vol. 30, no. 2. P. 181-198.
115. Kim K.-J. Torus and simple surface intersection based on configuration space approach: Ph. D. thesis / Pohang University of Science and Technology. 1998.
116. Barnhill R., Farin G., Jordan M., Piper B. Surface/surface intersection // Computer Aided Geometric Design. 1987. Vol. 4, no. 1-2. P. 3-16.
117. Grandine T. A., Klein F. W. A New Approach to the Surface Intersection Problem // Comput. Aided Geom. Des. 1997. Vol. 14, no. 2. P. 111-134.
118. Krishnan S., Manocha D. An Efficient Surface Intersection Algorithm Based on Lower-di-
mensional Formulation // ACM Trans. Graph. 1997. Vol. 16, no. 1. P. 74-106.
119. Шарый С. П. Оптимальное внешнее оценивание множеств решений интервальных систем уравнений. Часть 1 // Вычислительные Технологии. 2002. Т. 7, № 6. С. 90-113.
120. Kubica B. J. Interval Methods for Solving Underdetermined Nonlinear Systems // Reliable Computing. 2011. P. 207-217.
121. Gatilov S. Properties of nonlinear systems and convergence of the Newton-Raphson method in geometric constraint solving // Bull. Nov. Comp. Center. 2011. Vol. 32. P. 57-75.
122. Dennis J. E., Jr., Schnabel R. B. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, 1996. Vol. 16 of Classics in Applied Mathematics.
123. Cai X.-C., Keyes D. E. Nonlinearly preconditioned inexact Newton algorithms // SIAM J. Sci. Comput. 2002. Vol. 24, no. 1. P. 183-200.
124. Akima H. A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures // J. ACM. 1970. Vol. 17, no. 4. P. 589-602.
125. Catmull E., Rom R. A class of local interpolating splines // Computer aided geometric design. 1974. P. 317-326.
126. Bajaj C. L., Xu G. NURBS approximation of surface/surface intersection curves // Advances in Computational Mathematics. 1994. Vol. 2, no. 1. P. 1-21.
127. Dormand J., Prince P. A family of embedded Runge-Kutta formulae // Journal of Computational and Applied Mathematics. 1980. Vol. 6, no. 1. P. 19-26.
128. Floater M. S. Evaluation and Properties of the Derivative of a NURBS Curve // Mathematical Methods in Computer Aided Geometric Design II. San Diego, CA, USA: Academic Press Professional, Inc., 1992. P. 261-274.
129. Lee K.-Y., Cho D.-Y., Kim T.-W. A tracing algorithm for surface-surface intersections on surface boundaries // Journal of Computer Science and Technology. 2002. Vol. 17, no. 6. P. 843-850.
130. Gottschalk S., Lin M. C., Manocha D. OBBTree: A Hierarchical Structure for Rapid Interference Detection // Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. SIGGRAPH '96. New York, NY, USA: ACM, 1996. P. 171-180.
131. Klee V. L., Jr. Separation Properties of Convex Cones // Proceedings of the American Mathematical Society. 1955. Vol. 6, no. 2. P. 313-318.
132. De Montaudouin Y. Cross Product of Cones of Revolution // Comput. Aided Des. 1989. Vol. 21, no. 6. P. 404-404.
133. Sinha P., Klassen E., Wang K. K. Exploiting Topological and Geometric Properties for Selective Subdivision // Proceedings of the First Annual Symposium on Computational Geometry. SCG '85. New York, NY, USA: ACM, 1985. P. 39-45.
134. Sederberg T. W., Meyers R. J. Loop detection in surface patch intersections // Computer Aided Geometric Design. 1988. Vol. 5, no. 2. P. 161-171.
135. Sederberg T. W., Zundel A. K. Pyramids That Bound Surface Patches // Graphical Models and Image Processing. 1996. Vol. 58, no. 1. P. 75-81.
136. Selimovic I. On NURBS Algorithms Using Tangent Cones // Comput. Aided Geom. Des. 2009. Vol. 26, no. 7. P. 772-778.
Приложение А Проверки отделимости
Неоспоримой основой глобального анализа является возможность отбрасывать непересекающиеся пары частей. Это становится возможным благодаря использованию критериев непересечения частей, или критериев отделимости. Очевидно, задача точного определения, пересекаются ли части, ненамного проще самой задачи поиска пересечения геометрий, поэтому используемые критерии отделимости неизбежно допускают ложно-отрицательный вердикт, то есть они могут быть неспособны диагностировать отсутствие пересечений в случае, когда их нет. Ошибки ложно-положительного рода не допускаются. Более того, поскольку входные данные могут быть заданы неточно, пару частей можно удалить только в том случае, если расстояние между ними больше заданного пользователем порога е. Иначе возможно пропадание элементов пересечения, особенно касательных пересечений. При разработке критериев отделимости преследуются две несовместимые цели: с одной стороны, следует допускать как можно меньше ошибок, а, с другой стороны, критерий должен работать быстро, поскольку он запускается много раз в процессе подразбиения.
А.1. Ограничивающие брусы
В качестве первичного критерия отделимости используется непересечение ограничивающих брусов. Для каждой части многообразия при создании вычисляется и сохраняется ограничивающий брус. Для ЫИКВБ-сплайнов брус строится по контрольным точкам, ведь сплайн содержится в их выпуклой оболочке. Для аналитических многообразий определяется минимальный брус посредством рассмотрения случаев. Для любой пары частей можно легко и быстро определить расстояние между их брусами в смысле I^-нормы. Если оно больше порога, то пара частей точно не пересекается.
Данной простейшей проверки отделимости хватает для того, чтобы алгоритм подразбиения нормально работал. Однако, если поверхности касаются или пересекаются под малым углом, то количество ошибочно оставленных пар частей будет велико. Например, можно рассмотреть касание плоскости и сферы радиуса г. Если объекты повёрнуты произвольным образом относительно координатных осей, то можно оценить, что их части размера 8x8 будут иметь «толщину» также порядка 8. Тогда, чтобы части отбрасывались как непересекающиеся, расстояние между ними должно быть не меньше порядка 8+е. Линейный размер области, на которой это выполняется, имеет порядок г(8 + е). Следовательно, количество частей, которые попадут в эту область и не будут отброшены, имеет порядок |(1 + |). Получается, что по мере увеличения номера итерации количество брусов будет расти экспоненциально: на каждой следующей итерации будет примерно в два раза больше рабочих брусов.
Конечно, эти рассуждения не учитывают использование критерия отсутствия сингулярности, однако всё равно такой рост количества брусов для поиска произвольной точки касания нежелателен. Подобная проблема в том или ином масштабе присутствует вблизи любого касания. Можно заметить, что любая гладкая часть многообразия размера 8 на самом
деле имеет толщину, пропорциональную б2. Однако использование ограничивающих брусов, вычисленных в неподходящей системе координат, не позволяет использовать это свойство. Если использовать ограничивающее множество, которое адекватно отражает толщину как квадратичную, то проблема будет решена.
А.2. Более точные критерии
Таким образом, крайне желательно использовать более точный вторичный критерий, если первичный критерий по ограничивающим брусам не показал отделимость частей. Далее обсуждается преимущественно наиболее трудоёмкая задача пересечения поверхностей.
Известным способом решения проблемы является использование ориентированных брусов. Например, в статье [130] для поиска коллизий предлагается вычислять ограничивающие прямоугольные параллелепипеды в системе координат, определяемой по тензору инерции, а наличие пересечений проверять при помощи проверки отделимости вдоль 15-ти направлений. Данный набор направлений достаточен для точного определения отсутствия пересечения двух произвольных параллелепипедов. Он состоит из перпендикуляров к граням и общих перпендикуляров сторон (взятых с разных параллелепипедов). Этот приём можно применить для проверки отделимости частей многообразия, причём вычисление тензора инерции не нужно, поскольку оси координат для лоскута1 поверхности можно направить примерно вдоль касательных поверхности по параметрам.
С другой стороны, в [45, Раздел 4.2] предлагается другой подход к проверке отделимости. Известно, что если расстояние между двумя выпуклыми множествами больше е, то найдётся такая ось, что проекции множеств на неё также находятся на расстоянии больше е. Любую часть многообразия можно легко ограничить выпуклым многогранником: для ЫиКББ-сплайнов можно взять выпуклую оболочку контрольных точек, а для аналитических многообразий можно быстро вычислить контрольные точки геометрически эквивалентного ЫиКББ-сплайна. Следовательно, вместо проверки на пересечение простых ограничивающих множеств можно проверять выпуклые оболочки на отделимость вдоль некоторых осей.
Заметим, что проверка обычных ограничивающих брусов для выпуклых оболочек на отсутствие пересечения в точности эквивалентна выполнению проверки отделимости вдоль всех трёх координатных осей. Проверку на непересечение ориентированных ограничивающих брусов также можно заменить на проверку выпуклых оболочек на отделимость вдоль набора направлений. При этом можно использовать те же 15 направлений, которые традиционно используются в проверке на непересечение брусов. Получающаяся проверка на отделимость будет никогда не хуже, а иногда даже лучше проверки на непересечение ориентированных брусов. У данного улучшения есть и цена: нужно выполнять в пять раз больше вычислений в худшем случае, ведь каждая точка проецируется уже не на 3 оси, а на все 15.
Хохмайер в [45, Раздел 4.2.2] предлагает в качестве вторичной проверки для поверхностей использовать только отделимость вдоль осей, направленных примерно вдоль нормалей обрабатываемых частей. Таким образом, вместо использования всех 15 направлений для ограничивающих брусов используется только 2 направления. Вероятно, это сделано для того,
1 Здесь лоскут — часть поверхности, определённая на некотором брусе в её ИУ-пространстве.
Рис. А.1. Пример двух лоскутов, которые не отделимы вдоль координатных осей и своих нормалей, однако отделимы вдоль общего перпендикуляра рёбер ограничивающих ориентированных брусов. Показан общий вид, а также два специальных ракурса, в которых нормаль одного из лоскутов ортогональна линии взгляда. Пунктиром показаны потенциальные разделяющие плоскости.
чтобы ускорить выполнение данной проверки. Однако в качестве третичной проверки далее в [45, Раздел 4.2.3] предлагается определять точно отделимость выпуклых оболочек при помощи решения задачи линейного программирования. Интуиция подсказывает, что решение задачи линейного программирования в проективном четырёхмерном пространстве рандомизированным методом Зейделя работает существенно медленнее более простых проверок, рассмотренных выше (соответствующие экспериментальные данные имеются ниже). Важность данного критерия обосновывается случаями, когда часть А пересекает касательную плоскость лоскута В, но вне границ лоскута (примеры можно увидеть на рисунке А.1).
А.3. Предлагаемый метод
Для успешного решения приведённого примера достаточно провести проверки отделимости вдоль некоторых осей, которые точно характеризуют границы лоскутов. Для этого рассмотрим линейную аппроксимацию лоскута поверхности. В общем случае она представляет из себя параллелограмм, хотя для многих практически значимых поверхностей она является прямоугольником, потому что частные производные оказываются ортогональными. Отклонение лоскута от его аппроксимации квадратично зависит от линейного размера лоскута, поэтому можно полагать его малым по сравнению с размерами самого лоскута, когда он достаточно мал. Предлагается провести проверки отделимости выпуклых оболочек только вдоль тех направлений, которые необходимы, чтобы определить непересечение их линейных аппроксимаций.
Если рассмотреть разность Минковского двух параллелограммов, то её грани будут составляться либо исходными параллелограммами, либо проведением стороны одного параллелограмма вдоль стороны другого. Исключением является вырожденный случай, когда параллелограммы параллельны: тогда разность Минковского является плоским многоугольником, стороны которого параллельны сторонам исходных параллелограммов. Известно, что направление отделяет два множества тогда и только тогда, когда оно отделяет начало коор-
динат от их разности Минковского. По этой причине если параллелограммы не пересекаются, то это можно определить проверками отделимости вдоль следующих 10 осей:
1. нормали параллелограммов (2 шт.),
2. перпендикуляры к сторонам параллелограммов в их плоскостях (4 шт.),
3. общие перпендикуляры для пар сторон с разных параллелограммов (4 шт.). Отметим, что пункт 2 необходим только в вырожденной ситуации, когда параллелограммы параллельны.
Идея заключается в том, чтобы вычислить эти 10 осей для параллелограммов, которые линейно аппроксимируют лоскуты, а затем проверить критерии отделимости выпуклых оболочек, ограничивающих лоскуты, вдоль всех этих осей. Оказывается, если расстояние между лоскутами существенно больше, чем погрешность аппроксимации лоскутов параллелограммами, то такая проверка гарантированно установит отделимость между лоскутами. В следующем разделе (разделе А.4) приводится доказательство этого факта.
Предлагаемый критерий можно сравнить с вышеописанными критериями. Он лучше вторичной проверки Хохмайера, поскольку среди 10 проверяемых направлений есть нормали к параллелограммам, в точности которые использует Хохмайер в своей проверке, однако благодаря наличию ещё 8 направлений критерий успешно работает на примере из рисунка А.1. Конечно, он хуже третичной проверки Хохмайера на непересечение выпуклых оболочек, но при этом он существенно быстрее и проще.
Наконец, предлагаемый критерий можно сопоставить с критерием проверки отделимости ориентированных брусов. Можно построить для каждого лоскута ограничивающий параллелепипед, одна сторона которого направлена вдоль нормали параллелограмма, а остальные две — вдоль его сторон. Если у поверхности частные производные ортогональны, то полученный параллелепипед будет почти прямоугольным, однако в противном случае полученный существенно непрямоугольный ограничивающий параллелепипед будет точнее ограничивать лоскут, чем прямоугольный брус. Чтобы проверить эти два параллелепипеда на отделимость, нужно проверить 15 направлений. В предлагаемом критерии используется в точности 10 из них. Остальные 5 забытых направлений — это общие перпендикуляры к парам рёбер, таким что хотя бы одно из рёбер в паре короткое, потому что направлено вдоль нормали параллелограмма.
Изложенный критерий можно использовать и для кривых, нужен лишь способ определения аппроксимирующего параллелограмма. Одна из сторон параллелограмма должна быть направлена примерно вдоль касательной кривой, а вторую можно направить произвольным образом, ведь линейная аппроксимация кривой является отрезком.
А.4. Теоретическое обоснование
Определим 5-расширение произвольного выпуклого многогранника следующим образом. Рассмотрим плоскости, в которых лежат его грани, и отодвинем их вовне многогранника на расстояние 8. Тот многогранник, который будет ограничиваться отодвинутыми плоскостями, и есть ^-расширение исходного многогранника. Утолщённым параллелограммом высоты к будем называть параллелепипед, четыре параллельные стороны которого ортогональны
двум параллельным граням и имеют длину к. Такие стороны мы будем также называть высотами, а соответствующие грани — основаниями.
Теорема А.4.1. Пусть А и В — утолщённые параллелограммы с высотами кд и кв соответственно. Если ^ -расширение А не пересекается с -расширением В, то А и В отделимы вдоль одного из 10 вышеперечисленных направлений, определённых по их параллелограммам-основаниям.
Доказательство. Поскольку параллелепипеды А и В не пересекаются, то они отделимы вдоль одного из 15 направлений, из которых 6 ортогональны граням параллелепипедов, а 9 являются общими перпендикулярами для пар сторон с разных параллелепипедов. Легко видеть, что 10 из этих направлений совпадают с вышеперечисленными десятью для параллелограммов-оснований. Предположим, следствие теоремы не выполняется. Тогда А и В отделимы вдоль одного из 5 оставшихся направлений, но не отделимы вдоль 10 основных. Заметим, что эти 5 оставшихся направлений являются общими перпендикулярами двух сторон, причём одна из сторон является высотой своего утолщённого параллелограмма (и имеет длину кд или к в).
Ясно, что направления отделимости для параллелограммов и их расширений совпадают. Чтобы обнаружить противоречие, будем показывать, что отделимость расширений А и В вдоль направлений отсутствует. Для этого понадобится следующая лемма.
Лемма А.4.1. Пусть А и В — утолщённые параллелограммы с высотами На и кв соответственно, а А — ^-расширение А. Допустим, А и В не отделимы вдоль 10 вышеперечисленных направлений для параллелограммов-оснований.
Пусть А и В отделимы вдоль д, где ^ — общий перпендикуляр к некоторой стороне А и высоте В. Тогда верно хотя бы одно из двух:
1. А и В не отделимы вдоль д;
2. (д — общий перпендикуляр к высоте А и высоте В) и (А и В отделимы вдоль некоторого направления в), где в — общий перпендикуляр к высоте А и стороне В, не являющейся высотой.
Доказательство. Рассмотрим направление д, вдоль которого есть отделимость. Стороны, к которым построен общий перпендикуляр, будем называть критическими. По условию критическая сторона В является высотой, а критическая сторона А может быть, а может и не быть высотой.
Рассмотрим объекты в проекции, в которой критическая сторона А вырождается в точку Т. В общем случае проекция А имеет вид параллелограмма, а проекция В — некоторого выпуклого многоугольника. Разделяющая плоскость вырождается в прямую, разделяющую А и В, параллельную проекции критической стороны В. Ситуация изображена на рисунке А.2.
Введём косоугольную систему координат на проекции следующим образом: начало расположено в вершине Т, оси направлены вдоль инцидентных сторон А. Критическая сторона В в проекции не может быть параллельна этим осям, поскольку в таком случае разделяющая плоскость была бы параллельна одной из граней параллелепипеда А, а по условию
такой отделимости нет (см. пункты 1 и 2 из описания 10 осей). Разделяющая прямая разбивает плоскость на две полуплоскости. Если рассмотреть полуплоскость, в которой лежит В, в виде ах + Ьу ^ 1, то можно считать а > 0 и Ь > 0. Если это не верно, то можно рассмотреть в качестве критической стороны А какую-то другую сторону А, параллельную ей.
В системе координат можно рассмотреть четверти согласно рисунку А.2. Проекция В не может лежать полностью в I и 11 или в II и IV четвертях, поскольку в таком случае её можно было бы отделить от А прямой, параллельной координатной оси, а такие прямые соответствуют разделяющим плоскостям, параллельным граням параллелепипеда А. Следовательно, в проекции имеются точки Р и Q, которые лежат на координатных осях х и у соответственно. Можно выбрать их ближайшими к началу координат, тогда вся граница В между Р и Q будет лежать в треугольнике △TРQ.
Рассмотрим подробнее произвольную сторону В, которая в проекции порождает часть границы между Р и Q. Прямая, на которой лежит эта сторона, является разделяющей: вся проекция В лежит с одной стороны в силу выпуклости, а А лежит с другой стороны, потому что прямая пересекает каждую ось в точке с положительной координатой. Такая разделяющая прямая порождает в пространстве разделяющую плоскость, нормаль которой ортогональна и рассматриваемой стороне В, и критической стороне А (на проекции это точка Т). Если предположить, что рассматриваемая сторона не является высотой В, то возможны два варианта:
1. Критическая сторона А не является высотой. Тогда нормаль разделяющей плоскости является общим перпендикуляром к сторонам А и В, которые не являются высотами. Однако такое направление есть среди 10 направлений отделимости для параллелограммов-оснований А и В, что противоречит условию леммы.
2. Критическая сторона А является высотой. Тогда автоматически выполняется второй пункт заключения леммы, потому что имеется отделимость А и В вдоль общего перпендикуляра высоты А (критической стороны) и рассматриваемой стороны В, не являющейся высотой.
Рис. А.3. Отрезок в 1-ой четверти и расширение А.
Таким образом, в дальнейшем можно считать, что все стороны в проекции на границе В между Р и Q являются высотами В. Но в таком случае этих сторон не может быть несколько: все высоты В в проекции параллельны и не могут быть соседними в выпуклом многоугольнике. Таким образом, граница В между Р и Q должна быть составлена ровно из одной стороны параллелепипеда В, которая является высотой. Именно эту сторону в дальнейшем будем называть критической для В.
Новое изображение на рисунке А.3 точнее отображает ситуацию. ММ является проекцией критической стороны (и высоты), значит её длина не превышает к в. РQ является её частью, значит длина РQ также не больше к в. Можно рассмотреть ^-расширение А и его проекцию при 8 = 2 к в. При расширении вершина Т перейдёт в вершину Ш, угол при этих вершинах равен р.
Допустим, вершина Ш находится внутри или на границе △TРQ. Помня о том, что точки Р и Q должны лежать на осях координат, можно показать, что при этом условии минимально возможная длина отрезка РQ составляет 28/ сов(^) и достигается, когда Ш Е РQ и ТШ ^ РQ. Однако в нашем случае 28 = к в ^ РQ, а значит это невозможно. Следовательно, вершина Ш находится по ту сторону от прямой РQ, где расположено В, то есть в проекции А и В пересекаются.
Поскольку проекции пересекаются, то отделимости не может быть вдоль никакого направления, которое в проекции вырождается в прямую. В частности, не может быть и отделимости вдоль рассматриваемого направления й, а значит выполняется первый пункт заключения леммы.
□
Теперь можно вернуться к доказательству теоремы. Обозначим расширения А и В как А и В соответственно. Мы предположили, что А и В отделимы вдоль общего перпендикуляра сторон, причём одна из этих сторон является высотой.
Докажем, что А и В не отделимы вдоль общих перпендикуляров, опирающихся на высоту одного утолщённого параллелограмма и сторону другого, не являющуюся высотой. Дей-
ствительно, если бы они были отделимы вдоль такого направления, то А и В также были бы отделимы вдоль него. Тогда должно выполняться первое заключение леммы, то есть А и В или А и В вдоль него не отделимы. Но тогда и А с В не могут быть отделимы вдоль него — противоречие.
Теперь докажем, что А и В не отделимы вдоль общего перпендикуляра к своим высотам. Действительно, если бы они были отделимы вдоль него, то А и В также были бы отделимы вдоль этого направления, и выполнялось бы одно из двух заключений леммы. Если выполняется первое, то А и В не отделимы вдоль этого направления, а значит А и В тоже, что приводит к противоречию. Значит, должно выполняться второе заключение, то есть А и В отделимы вдоль общего перпендикуляра к высоте А и стороне В, которая не является высотой. Однако тогда А и В тоже должны быть отделимы вдоль него, а чуть выше мы уже доказали, что вдоль направления такого рода отделимости быть не может.
Получается, что А и В не отделимы вдоль общих перпендикуляров к своим сторонам при условии, что одна из сторон является высотой. Таких общих перпендикуляров ровно 5 штук. Вдоль 10 основных направлений они также не отделимы, ведь вдоль них не отделимы А и В. Получается, что два параллелепипеда не отделимы вдоль ни одного из 15 стандартных направлений. Следовательно, они должны пересекаться — противоречие.
□
Теперь можно сформулировать утверждение о том, что предлагаемая проверка отделимости с 10 осями работает в некотором смысле с квадратичной точностью, то есть хорошо работает для «тонких» лоскутов.
Следствие А.4.1. Пусть выпуклые оболочки, ограничивающие лоскуты А и В, отклоняются от аппроксимирующих параллелограммов не более чем на Еа и Ев соответственно, и все углы аппроксимирующих параллелограммов не меньше р > 0.
Тогда существует константа С, такая что: если расстояние между лоскутами больше С(Еа + Ев), то проверка отделимости выпуклых оболочек с 10 осями сработает успешно.
Доказательство. Рассмотрим параллелограмм П^ лоскута А. Согласно условию, расстояние от выпуклой оболочки до него не превосходит Еа . Значит, если рассматривать параллелограмм как утолщённый параллелограмм высоты 0 и построить к нему -расширение П^, то оно будет полностью содержать выпуклую оболочку. То же самое верно и для лоскута В.
Если предположить, что проверка сработает неуспешно, то она также неуспешно сработает для утолщённых параллелограммов П^ и Пд. Значит, по теореме А.4.1 Ев-расширение П^ должно пересекаться с ^^-расширением Пд. Обозначим эти расширения как П^ и Пд соответственно.
Рассмотрим утолщённый параллелограмм П^. Он является (Еа + Ев)-расширением параллелограмма П^, и острый угол П^ отделён от нуля числом р, значит любая его точка находится на расстоянии не более С\(Еа + Ев) от П^ для некоторой константы С\ = С\(р). Следовательно, расстояние от произвольной точки П^ до лоскута А не превосходит (С\(Еа + Ев) + Еа). Аналогичное рассуждение можно провести и для Пд. П^ и Пд пересекаются, значит у них есть общая точка. Расстояния от этой точки до лоскутов А и В оценены
сверху. Значит, расстояние между ними не превышает С(Ед + Ев), где С = 2С\ + 1. Если использовать это С в условии, то получается противоречие.
□
Понятно, что утверждение следствия А.4.1 легко было бы доказать, если использовать не 10 направлений, а все 15 стандартных направлений отделимости, определённых для ограничивающих утолщённых параллелограммов. Пять из них опираются на короткие стороны (высоты), и казалось бы, поэтому их можно не использовать. Главная мотивация теоремы А.4.1 заключается именно в том, чтобы доказать, что отбрасывание этих пяти направлений не приводит к существенному ухудшению качества проверки.
А.5. Аналитические случаи
В рассмотренных выше критериях отделимости есть коренной недостаток: все они основываются на выпуклых ограничивающих множествах (в общем случае, выпуклых оболочках). А в инженерной практике часто встречаются соосные цилиндры, вложенные сферы и конусы, для которых установить непересечение на основе выпуклых множеств невозможно без дробления на более мелкие части.
Чтобы частично решить эту проблему, были реализованы некоторые простейшие специальные критерии непересечения для частей аналитических многообразий. Сначала вычисляется пересечение ограничивающих брусов проверяемых частей. Если одно из многообразий является цилиндром, конусом или сферой, и полученный брус лежит целиком внутри него (проверяется по вершинам), то проверяемые части точно не пересекаются. Такая проверка позволяет в некоторых случаях успешно отбрасывать даже такие пары частей, у которых выпуклые оболочки пересекаются.
А.6. Реализация
Ниже представлен предлагаемый алгоритм проверки на отсутствие пересечений. Если на некотором этапе доказывается отсутствие пересечений, то дальнейшие шаги не выполняются.
1. Проверяем, пересекаются ли ограничивающие брусы2 частей.
2. Запускаем аналитические критерии отсутствия пересечений (см. раздел А.5).
3. Если какая-то из частей представлена аналитически, вычисляем контрольные точки для ограничивающей выпуклой оболочки.
4. Находим для каждой части направления сторон аппроксимирующего параллелограмма.
5. Проверяем, есть ли отделимость выпуклых оболочек вдоль 10 направлений (см. раздел А.3).
На шаге 3 направления сторон параллелограмма выбираются следующим образом. Для лоскута поверхности имеется четыре угловых контрольных точки (совпадающих с углами
2 Брусы вычисляются для каждой части многообразия при её первом появлении (ровно один раз).
лоскута) А, В, И, С (в порядке обхода). Выбираются направления 1 (лй+ад) и 2(лё+Ш), примерно направленные вдоль частных производных поверхности. В результате нормаль для параллелограмма направлена в точности вдоль общего перпендикуляра диагоналей АИ и ВС, как в работе Хохмайера. Для части кривой одна сторона параллелограмма направляется вдоль отрезка, соединяющего концевые точки. Вторая сторона направляется вдоль перпендикуляра, опущенного из средней точки кривой на отрезок.
Выпуклые оболочки отделимы вдоль направления, если интервалы их проекций на соответствующую прямую не пересекаются. Каждую точку оболочек можно спроецировать на прямую, просто вычислив скалярное произведение. Интервалы можно определить через минимумы и максимумы полученных чисел. Дальше можно применить несколько оптимизаций.
Во-первых, можно изначально спроецировать только по одной точке с каждой оболочки и сравнить полученные координаты на оси. Назовём оболочку с точкой с меньшей координатой «левой», а оболочку с точкой с большей координатой «правой». Теперь ясно, что для левой оболочки можно искать только максимум координат точек, потому что минимум координат уже не имеет значения. Аналогично для правой оболочки можно искать только минимум координат. Если максимум с левой оболочки меньше минимума с правой, то отделимость есть, а иначе — нет.
Во-вторых, проверку можно прервать досрочно, как только становится известно, что отделимости нет, то есть как только максимум для левой оболочки стал больше минимума для правой. В результате время, затрачиваемое на проверку в случае отсутствия отделимости, зависит от порядка проверки точек. В хорошем случае проверка завершается неудачей даже без обращения к большинству контрольных точек в памяти. Чтобы увеличить вероятность такого хорошего случая, желательно: во-первых, обрабатывать точки с разных оболочек вперемешку, и, во-вторых, с самого начала проверить точки в крайних положениях.
Следующее рассуждение обосновывает эффективность предлагаемых отсечений. Если в конечном счёте не получается показать отделимость частей многообразий, то все 10 запускаемых проверок срабатывают с отрицательным результатом. В противном случае ровно одна из десяти проверок срабатывает успешно, поскольку после этого остальные проверки запускать уже не нужно. В случае успешной проверки обрабатываются все контрольные точки, однако это происходит не более одного раза из десяти. Можно надеяться, что в остальных проверках большая часть точек не будет обрабатываться из-за предлагаемого отсечения, тогда общее время работы можно будет оценить примерно как два-три прохода по точкам вместо десяти в худшем случае.
Предлагаемый подход представлен в алгоритме 9. Для простоты в нашей реализации в первую очередь проверяются первая и последняя точки (в случае лоскута поверхности они соответствуют двум противоположным угловым точкам). Остальные точки проверяются поочерёдно.
А.7. Эксперименты
Алгоритмы проверки отделимости частей многообразий были проверены на нескольких примерах пересечения поверхностей. Чтобы выявить разницу в поведении критериев,
Input: Массивы точек А и В размеров т и п, единичный вектор направления d и
порог толерантности е Output: true ^^ множества А и В отделимы вдоль d // смотрим на координаты первых точек I ^ (d ■ А1); г ^ (d ■ В1);
// если точка из А правее, разворачиваем ось if I > г then
| d <--d, I <--1, r <--r;
end
// обрабатываем последние точки I ^ max(/, (d ■ Am)); r ^ min(r, (d ■ Вп)); if I + e > r then return false; // обрабатываем точки поочерёдно for г ^ {2,..., min(m, п)} do I ^ max(/, (d ■ Aj)); r ^ min(r, (d ■ Bi)); if I + £ > r then return false; end
// обрабатываем оставшиеся точки в А или В for г ^ {min(m, п),... , т} do I ^ max(/, (d ■ А»)); for г ^ {min(m, п),... ,п} do г ^ min( г, (d ■ В^)); if I + £ > г then return false; // все точки обработаны return true;
Алгоритм 9: Проверка отделимости вдоль направления
критерии
критерии 0 1 2 3 4 5 6 7 8 9 время
брусы 12 28 60 124 378 1290 4176 14644 60842 247682 496.6
брусы + 2 напр. 12 28 60 124 378 1290 4176 14644 60842 247682 563.1
брусы + 10 напр. 12 28 60 124 378 1290 4176 14644 60842 247682 614.8
брусы + 15 напр. 12 28 60 124 378 1290 4176 14644 60842 247682 661.1
брусы + лин. прогр. 12 28 60 124 378 1290 4176 14644 60842 247682 2075.3
брусы + 15 напр.
33
41
критерии 0 1 2 3 4 5 6 7 8 9 время
брусы 14 66 183 519 1536 4147 13026 35202 103803 291364 515.0
брусы + 2 напр. 7 17 39 81 159 339 1015 2939 11390 43507 67.9
брусы + 10 напр. 6 14 30 62 126 258 783 2092 7343 29386 71.8
брусы + 15 напр. 6 14 30 62 126 258 783 2092 7343 29386 77.3
брусы + лин. прогр. 6 14 30 62 126 258 783 2092 7343 29386 423.3
41
442
442
71
"59
59
979
964
130
~99
99
1965
1942
200 175
175
3936
3881
347 315
307
7853
7770
708 637
631
15883
15699
1463 1327
1325
32236
31880
3186 2891
2879
время
85.4
110.3
18.3 18.3
98.4
критерии
1 2
критерии 0 1 2 3 4 5 6 7 8 9 время
брусы 16 47 126 209 448 904 1812 3670 7575 16082 85.7
брусы + 2 напр. 14 36 80 124 250 490 996 1999 4162 8945 58.0
брусы +10 напр. 13 30 65 102 195 374 755 1519 3175 6880 59.5
брусы +15 напр. 13 30 65 102 195 374 755 1519 3174 6879 61.8
брусы + лин. прогр. 13 29 61 99 193 372 750 1517 3172 6871 217.2
критерии 0 1 2 3 4 5 6 7 8 9 время
брусы 6 23 57 128 256 533 1082 2222 4456 8901 39.8
брусы + 2 напр. 6 15 15 16 15 24 15 22 37 92 1.0
брусы + 10 напр. 5 15 12 13 9 15 12 15 31 73 1.0
брусы + 15 напр. 5 15 12 13 9 15 12 15 31 73 1.0
брусы + лин. прогр. 5 10 8 7 8 10 7 11 26 71 4.7
критерии 0 1 2 3 4 5 6 7 8 9 время
брусы 12 32 97 222 443 864 1758 3508 7082 14418 101.4
брусы + 2 напр. 12 24 64 129 239 463 907 1798 3627 7328 69.7
брусы + 10 напр. 12 24 61 115 195 366 704 1385 2756 5588 70.6
брусы + 15 напр. 12 24 59 112 195 366 704 1385 2755 5587 72.9
брусы + лин. прогр. 12 22 45 103 175 349 683 1359 2736 5560 284.8
3
124 124 124
124
124
4
5
378 1290 378 1290 378 1290
378 1290
378 1290
6
4176 4176 4176
4176
4176
7
8
14644 60842 14644 60842 14644 60842
14644 60842
14644 60842
9
247682 247682 247682
247682
247682
время
496.6 563.1 614.8
661.1
2075.3
519
81
62
1536
159
126
126 126
5
6
4147 13026
339 1015
258
783
258 258
783 783
35202
2939
2092
2092 2092
103803
11390
7343
7343 7343
291364
43507
29386
29386 29386
время
515.0
67.9
71.8
77.3 423.3
критерии
брусы
брусы + 2 напр. брусы +10 напр. брусы +15 напр.
брусы + лин. прогр.
0 1
16 47 14 36 13 30 13 30
13 29
2
126
~80 ~65~ 65
61
3
4
209 448
124 250
102 195
102 195
99 193
5
904 490 374 374
372
6
7
1812 3670
996 1999
755 1519
755 1519
750 1517
8
7575 4162 3175 3174
3172
9
16082 8945 6880 6879
6871
время
85.7 58.0 59.5
61.8
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.