Содержание к диссертации
Введение
Глава 1. Модели и методы в моделировании технологического процесса фрезерования. Литературный обзор 8
1.1. Обпщй взгляд на моделирование технологических процессов в машиностроении 8
1.2. Существующие модели симуляции удаления материала 10
1.3. Математические модели, используемые для определения объёма, заметаемого движущимся телом 16
1.3.1. Дифференциальное уравнение заметания и его расширение 16
1.3.2. Методы, использующие параметрическое и неявное представление 18
1.3.3. Идентификация и отсечение внутренних объектов 21
1.3.4. Приближённые методы построения заметаемого объёма 23
1.4. Представление объёмной геометрии 27
1.4.1. Модели представления геометрии 27
1.4.2. Традиционные методы формирования математических моделей твёрдых тел 32
1.5. Постановка задачи исследования 41
Глава 2. Построение тела, заметаемого инструментом на участке траектории УП 42
2.1. Основные положения в задаче определения поверхности, заметаемой инструментом 42
2.2. Построение аналитической поверхности, образованной в ходе движения инструмента 45
2.2.1. Построение поверхности, заметаемой коническим инструментом 45
2.2.2. Построение поверхности, заметаемой сферическим инструментом 50
2.2.3. Построение заметаемой поверхности в общем случае 52
2.3. Построение заметаемого объёма на одном участке траектории 58
Глава 3. Построение результатов обработки для последовательности кадров 67
3.1. Общий взгляд на возможность построения 67
3.2. Формирование динамического BSP-дерева 70
3.3. Критерий построения непротиворечивого BSP-дерева 78
3.4. Уточнение 80
3.5. Булевы операции 84
3.5.1. Объединение деревьев 84
3.5.2. Двоичное разбиение BSP-дерева 87
3.5.3. Реализация булевой операции в вершинах дерева 92
Глава 4. Практические результаты 95
4.1. Программные модули симуляции фрезерной обработки на станках с ЧПУ 95
4.2. Оценка возможностей предложенного метода 101
4.2.1. Оценки скоростей выполнения разных этапов моделирования .101
4.2.2. Оценка возможностей булевых операций 107
Заключение 110
- Методы, использующие параметрическое и неявное представление
- Построение поверхности, заметаемой коническим инструментом
- Построение заметаемого объёма на одном участке траектории
- Формирование динамического BSP-дерева
Введение к работе
В различных отраслях промышленности применяется обработка со снятием материала (обработка резанием). Одним из основных видов этой обработки является фрезерная обработка [4], которая по своим возможностям позволяет получать детали достаточно сложной формы.
В силу своей универсальности развитие фрезерной обработки привело к появлению фрезерных станков с числовым программным управлением (ЧПУ), а в настоящее время подобные станки используются, пожалуй, на каждом крупном машиностроительном и других предприятиях.
Однако, несмотря на широкое распространение подобного класса оборудования, остаётся сложным вопрос качественного управления этими станками, в первую очередь из-за сложностей, вызванных оценкой правильности разрабатываемой управляющей программы (УП) без её выполнения непосредственно на станке.
Для решения этой проблемы ведутся разработки моделей и методов моделирования процесса фрезерной обработки [4], каждый из которых имеет свои достоинства и недостатки. Основным инструментом для реализации этого моделирования является компьютерная техника.
В основе всех методов геометрического моделирования и имитирования фрезерной обработки лежит задача определения объёма, удаляемого инструментом в ходе обработки [37, 38, 79, 53, 83, 84]. Выделяют два главных подхода в решении указанной задачи: методы, использующие точный аналитический подход и приближённые методы.
В целом, для аналитических методов, таких как: методы, основанные на конструктивной объемной схеме представления геометрии (CGS) [65], методы, определяющие точное представление границ заметаемого объёма [82, 88, 63, 94, 44, 56], методы, использующие R-функции [80] и др. свойственны большие временные затраты и дополнительные требования к вычислительным ресурсам компьютера.
Другая категория методов — приближённые методы. В работах [54] приводятся методы, реализация которых основана на использовании специального оборудования. Авторы работ [57, 81] для решения поставленной задачи используют расширение известного алгоритма Z-буфера. Широкий круг методов приближённого построения тел, заметаемых инструментом, основывается на использовании различных полигональных сеток, задающих движущиеся объекты [53, 60, 87]. В работах [48, 61, 69, 90, 94, 91] применяются методы, основанные на кодировании цвета. Для методов, относящихся к этой категории характерно то, что при решении проблемы временных затрат за счёт уменьшения вычислительной стоимости алгоритмов возникает новый вопрос - оценка точности выполняемых построений.
Несмотря на имеющиеся результаты, в силу уже приведённых причин (сложности вычислений и проблемы оценки построения), вопрос моделирования фрезерной обработки является по-прежнему актуальным.
Работа выполнялась на кафедре "Прикладная геометрия и автоматизация проектирования" Уральского государственного технического университета (г. Екатеринбург), в сотрудничестве с ТЦ ИНТЕКС (г. Екатеринбург). Хочется отметить, что со стороны её директора к.т.н., доц. Каца Евгения Исааковича была оказана значимая помощь в техническом руководстве и сопровождении настоящей работы.
Целью диссертационной работы является разработка методов и алгоритмов моделирования фрезерной обработки на станках с ЧПУ.
Для достижения этой цели необходимо решить следующие задачи:
1) построить математическую модель процесса удаления материала из
заготовки:
- построить аналитическое и аппроксимированное представление
тел, образуемых в ходе движения фрезерного инструмента; ~ реализовать методы удаления заметаемых тел из заготовки.
2) разработать программную реализацию алгоритмов.
Автор защищает
Математические модели представления аналитической поверхности, заметаемой в ходе движения инструмента;
Методы построения аппроксимации аналитического представления, допускающие динамическое уточнение результатов аппроксимации;
Программную реализацию симуляции удаления материала в ходе фрезерной обработки на станках с ЧПУ.
Научная новизна результатов работы заключается в следующем.
Построены математические модели построения поверхности, заметаемой движущимся инструментом: модели записаны в форме NURBS.
Разработан метод построения аппроксимированного представления тела заметаемого инструментом, который позволяет выполнять построение с изменяемой точностью.
Практическая ценность результатов работы состоит в следующем.
Разработана программная реализация задачи построения твёрдотельной модели, описывающей геометрическую форму результата фрезерной обработки на станках с ЧПУ. Данный модуль включён в качестве ядра системы, выполняющей верификацию и симуляцию управляющих программ для станков с ЧПУ. Полученные результаты позволяют говорить о том, что применение предлагаемых алгоритмов в реализации программного средства позволяет существенно сократить временные затраты на разработку УП для станков с ЧПУ, а также повысить их качество.
Результаты работы автора применяются на ряде предприятий машиностроительного комплекса, что подтверждают акты внедрения.
Достоверность научных результатов и выводов обоснована применением методов теории вычислительной геометрии и компьютерной графики. Полученные результаты подтверждаются совпадением результатов расчётов с экспериментальными результатами, полученными при обработке на станках с ЧПУ.
Основные положения работы и отдельные её результаты докладывались на 4 научно-технических конференциях и 3 выставках.
По теме диссертационной работы опубликовано 9 работ, из них 2 статьи.
Диссертация состоит из введения, 4 глав и заключения. Список используемых источников составляет 97 наименований.
Первая глава работы посвящена обзору математических моделей и алгоритмов, применяемых для определения тел, заметаемых движущимися инструментами. Приводится классификация некоторых, уже имеющихся, методов.
Вторая глава работы, посвящена описанию предлагаемого метода построения тела, заметаемого инструментом, на отдельном участке траектории.
В третьей главе описываются методы построения аппроксимированного представления заметённого объёма для последовательности кадров УП.
В четвёртой главе приводятся экспериментальные результаты работы предлагаемых методов, даётся сравнение с известными аналогами.
Методы, использующие параметрическое и неявное представление
В работе [30] отмечается ряд методов, позволяющих решать проблему тримирования. Для этого могут использоваться следующие подходы: - определение пересечения типа поверхность-поверхность. Решение проблемы приводится в работах [39, 40, 41, 27, 29]; - использование Z-буфера [94] - хорошо известная и эффективная методика, используемая в компьютерной графике; - "Бросание луча" [73, 72] - процедура, посредством которой луч направляется из точки, принадлежащей внутренней части объекта и пересекает на своём пути все поверхности. Точки пересечения нумеруются, и рассчитываются их расстояния от начальной точки. В результате сохраняются только те поверхности, которые связаны с самыми дальними точками, поскольку, именно они, должны принадлежать границе заметаемого объёма. Авторы работы [47] разработали эффективный алгоритм для вычисления заметаемых объёмов, в которых происходит самопересечение. Для этого они вначале вычисляют первоначальное представление границы охваченного объёма, используя метод SEDE. Затем, для отрезания лишних точек используют разработанный ими метод. Изначально объект задаётся кусочно-гладкой функцией fy которая имеет отрицательные значения внутри объекта, положительные снаружи и 0 на границе объекта. В этом случае они определяют функцию px(t) = Д77СМ)), где Г} - представляет обратный поток, полученный при помощи метода SDE. В результате, общая процедура гримирования будет выполняться только для точек, которые удовлетворяют условию рх (t) 0 , при некотором t, изменяющимся во времени. Вычислительная сложность этого алгоритма, включая процедуру тримирования4 определяется как 0(п2 log(w)), где п1 - граница снизу; время выполнения одного шага в триангулированном представлении границы объекта.
В 1986 году Т. van Hook [54] разработал метод отображения объёмов, заметаемых инструментом, движущимся по траектории, задаваемой управляющей программой для станка с ЧПУ. Предложенный метод позволял выполнять симуляцию удаления материала в реальном времени (10 операций в секунду). Реальное время отображения объёмной модели было достигнуто используя булевы операции в пространстве изображения, которые выполнялись на специальном оборудовании. Для этого рабочее пространство и инструмент были представлены в виде декселей - модификация общеизвестного метода Z-буфера. Каждый дексель (элемент глубины) представляется прямоугольным объектом, сориентированным в направлении вектора наблюдения, а булевы операции с объёмными телами, в данном представлении, выполняются как операции над одномерными представлениями этих объектов.
Однако, предложенный [54] метод имеет определённые недостатки: вектор, ориентирующий структуру декселя, фиксируется вектором наблюдения, в результате весь процесс моделирования должен повторяться при смене точки наблюдения.
Эти проблемы были решены в 1994 году авторами работы [58] путём расширения метода [54] . Предложенная ранее структура декселя [54] теперь имела свою собственную систему координат, независимую от вектора наблюдения. Зависимость от точки наблюдения также решалась за счёт преобразования структуры декселя в набор контуров, которые могут наблюдаться с любого направления. Авторы [58] также описали методы, дающие возможность оценить ошибки метода [54].
Однако, в прикладных программах, где высокое быстродействие является существенным, вычисление граничных поверхностей инструмента в пространстве объекта и дальнейшее преобразование этих поверхностей в представление в виде декселей — нежелательно. Это объясняется тем, что в процессе формирования строки сканера может потребоваться триангуляция поверхностей, в результате чего необходимо будет выполнить пересчёт строки сканера для всех созданных треугольников, что, несомненно, существенно скажется, на общем времени работы алгоритма. Однако отметим, что в том случае, когда представление объёма в виде декселей уже существует, выполнение операции заметания может быть выполнено непосредственно в пространстве изображения, не требуя дополнительных преобразований. В 1994 году был разработан метод [57] ускоренного создания заметаемого объёма, работающий в пространстве изображения.
В 1991 авторами [81] также использовалось расширение алгоритма Z-буфера для симуляции обработки на станках с ЧПУ. Так называемый G-буфер использовался для сохранения различной информации о пикселе: глубины, вектора нормали, куска (части) или идентификатора объекта и другая информация. В результате такой G-буфер мог отображаться обычными методами. Непосредственно траектория, заметаемая инструментом при обработке на станках с ЧПУ, может быть получена просто путём просмотра G-буфера по глубине. Однако данный метод может использоваться только для трёх координатной обработки; оценка ошибок в этом методе также невозможна.
Абсолютно другой подход (называемый "косилка лужаек") был предложен авторами [60] в 1989 году. Каждая поверхность аппроксимировалась многоугольной сетью, в которой векторы (например, нормальные векторы или ось аппликат) сохранялись в точках сети в течение всей процедуры симуляции. Эти векторы, связанные с поверхностью заготовки, пересекались с многоугольной аппроксимацией инструмента. Векторы сети сокращались на величину верхней или нижней ошибки, когда инструмент проходил над ними. Конечные точки сети отображались, используя оставшиеся части от векторов поверхности, и окрашивались кодированным цветом. Результирующая полигональная поверхность может наблюдаться с любых направлений используя обычную технологию визуализации Z-буфера. Данный подход очень удобен для оценки различных видов ошибок, которые могут образовываться в ходе моделирования. Данные возможности исследованы в работе [59].
Авторами [97] был разработан метод, который может быть использован для электроэрозионной обработки, где удаляются только участки рабочего пространства. Они изменили подход и вместо использования декселей применяют в своём методе, так называемую, цилиндрическую R-карту, из которой дексель может быть получен указанием высоты цилиндра и угола поворота. Определение ошибок при обработке также производится на основе кодирования цвета.
Построение поверхности, заметаемой коническим инструментом
Применение адекватных математических моделей для имитирования технологического процесса фрезерной обработки на станках с ЧПУ позволяет быстрее и качественнее создавать управляющие программы для станков с ЧПУ. Качественное создание УП повышает эффективность работы реальных технологических процессов предприятия.
Математическое моделирование технологического процесса фрезерной обработки тесно связано с задачей поиска объёма, заметаемого телом, движущимся по некоторой траектории. На возможность моделирования оказывает влияние выбор концепции построения заметаемого объёма. Это могут быть направления, использующие аналитическое решение задачи, а тшоке способы, вьшолняющие упрощение (аппроксимацию) оперируемой геометрической информации. Способ контроля и проверки процесса моделирования требует разработки пакета прикладных программ имитирования и симулирования фрезерной обработки. С учётом изложенного были поставлены следующие задачи исследования: 1) построить математические модели процесса фрезерной обработки на станках с ЧПУ; 2) проверить достоверность разработанных моделей путём сравнения результатов моделирования и реального технологического процесса или аналитическим решением; 3) разработать пакет прикладных программ моделирования фрезерной обработки; 4) включить разработанные модели в состав геометрического ядра системы, выполняющей имитацию и верификацию управляющих программ для станков с ЧПУ.
Как уже отмечалось, задача моделирования технологического процесса фрезерной обработки на станках с ЧПУ является по-прежнему актуальной, но остаётся достаточно сложной. К её решению можно подойти как к чисто геометрической задаче, не учитывая технологические особенности. Это упрощение вполне допустимо, учитывая то, что мы находимся на начальном этапе построения математической модели указанного технологического процесса. Для этого, прежде чем решать вопросы построения объёмного представления образуемых тел, попытаемся оценить, какие поверхности образуются в ходе указанного технологического процесса. По-прежнему будем считать, что технологический процесс фрезерной обработки упрощённо представляется парой - управляющая программа и инструмент.
Управляющая программа - просто траектория движения инструмента (составленная из отрезков прямых и дуг окружности), а вот инструмент может иметь произвольную геометрическую форму. В действительности именно форма инструмента во много определяет сложность, а, соответственно, и способы общего построения.
Укажем, что технологический инструмент, для которого реализуются методы построения заметаемого объёма и поверхностей, представляет собой тело вращения, образующая которого составлена из отрезков прямых и дуг окружностей, т.е. инструменты формируются участками поверхностей конуса, сферы и тора (рис. 2.1 а.). На форму инструмента накладывается ограничение, такое, что в пределах одного участка образующей инструмент может являться только выпуклым телом (рис. 2.1 б.). Однако, несмотря на указанное ограничение нужно отметить, что в целом подобная схема позволяет задавать инструменты достаточно широкого класса. В общем случае инструмент является объединением выпуклых тел и в итоге может быть не выпуклым телом (рис. 2.1 а).
Для описания метода формирования поверхности, заметаемой инструментом, рассмотрим случай, когда траектория движения инструмента представляет собой отрезок прямой, а сам инструмент - выпуклое тело. В этом случае нетрудно показать, что искомая поверхность может быть составлена из трех частей: - поверхности инструмента, видимой в направлении движения вдоль траектории в начальной точке; - поверхности инструмента, видимой в противоположном направлении в конечной точке; - линейчатой поверхности, образованной перемещением линии видимого контура (ЛВК) вдоль траектории. ЛВК - это кривая на поверхности объекта (инструмента), на которой меняет знак скалярное произведение вектора направления взгляда на нормаль к поверхности. Если поверхность гладкая, то упомянутое скалярное произведение на этой кривой равно нулю. Для выпуклого тела ЛВК разбивает поверхность на две связные части - видимую и невидимую (рис. 2.2). При этом можно утверждать, что при изменении направления взгляда на противоположное видимая и невидимая поверхности просто меняются местами. Кроме того, очевидно., что при перемещении объекта вдоль направления взгляда видимость любой его точки не изменяется. Таким образом, задача построения поверхности, заметаемой инструментом, сводится к решению следующих подзадач: построение ЛВК; - построение видимой и невидимой поверхностей инструмента (назовем их передняя и задняя); - построение линейчатой поверхности. Отметим, что приведенные рассуждения справедливы для произвольного выпуклого инструмента, а не только для тела вращения. Следовательно, предлагаемый подход может быть использован не только для фрезерной обработки, но и для токарной, электроэрозионной и др. Ограничиваясь случаем выпуклого инструмента, мы сильно сужаем область применения метода. Однако, если инструмент представить в виде объединения выпуклых тел, а это уже достаточно широкий класс, то результат решения задачи для такого составного инструмента есть просто объединение результатов, полученных для его выпуклых частей. Аналогичное утверждение справедливо для произвольной траектории, составленной из отрезков. В случае криволинейной траектории возможны специальные обобщения, либо аппроксимация отрезками. Основываясь на выше сказанном, рассмотрим методы построения аналитической поверхности, образуемой инструментом, движущимся по прямолинейному участку траектории.
Построение заметаемого объёма на одном участке траектории
Схем представления объемной геометрии много. В целом эти методы классифицируются [52] как: методы, основанные на Вокселях (Voksel) - элементах объёмного изображения; методы, использующие разбиение пространства двоичное и выше (Quadtrees & Octrees, BSP-деревья); методы конструктивной объёмной геометрии (CSG); методы, основанные на кинематическом задании тел (Sweep). Вокселя для представления объемной геометрии Каждый из этих способов оперирования объёмной геометрии имеет свои достоинства и недостатки, и говорить о том, какой из них лучше или хуже нет смысла, поскольку особенности, которые использует каждый метод, сильно зависят от предметной области их применения. К примеру, методы, использующие Воксель-представление, нашли широкое применение в системах применяемых в медицине (рис. 2.10.).
При преимуществе в простоте, интуитивности, однозначности представления, одинаковой сложности задания любых объектов и тривиальности выполнения булевых операций, применение данного подхода для моделирования удаления материала проблематично в силу приближённости представления, отсутствия возможности выполнения аффинных преобразований и большой потребности в ресурсах памяти. Отметим, что подобные примеры могут быть приведены и для других способов оперирования объёмной информацией. В Таблице 2.1 приводится классификация некоторых возможностей данных методов, основанная на [52].
Как отмечалось ранее, предлагаемый подход моделирования удаления материала из поверхности заготовки состоит в использовании технологических особенностей фрезерной обработки. А именно, то, что получение результатов обработки осуществляется на основе пошагового (покадрового) выполнения управляющей программы. На каждом шаге из тела заготовки удаляется (вычитается) объём, заметаемый инструментом на соответствующем кадре программы. Окончательный результат обработки получается при повторении данной процедуры для всей управляющей программы.
В силу ряда причин нам представляется, что в качестве метода описания объёмной геометрии может использоваться метод, основанный на BSP-деревьях. Выбор этого метода обусловлен его расширенной функциональной возможностью по представлению и оперированию геометрической информацией (см. классификацию методов представления объёмной геометрии -Таблица 2.1). Однако, кроме отмеченных расширенных функциональных возможностей, которые также присущи и другим методам представления объемной геометрии, для данного метода удалось найти решения, позволившие существенно ускорить и упростить реализацию моделирования удаления материала. Эти решения будут обсуждаться в Главе 3.
Как известно BSP-деревья (Binary Space Partitioning Tree) - это стандартное средство, используемое для сортировки и поиска многоугольников и многогранников в n-мерном пространстве. Оно основывается на пространственной декомпозиции.
В то же время, этот метод может использоваться для задания твёрдотельных объектов. Взятое в целом В SP-дерево представляет собой всё пространство, а каждый его узел ограничивает выпуклое подпространство. Каждый из узлов дерева хранит информацию о "гиперплоскости", делящей пространство узла на 2 части (переднюю и заднюю, что определяется направлением вектора нормали к этой плоскости), а также ссылки на два новых узла, представляющих эти части. При этом в узлах может храниться информация об одном или нескольких полигонах, лежащих в этой "гиперплоскости" (рис. 2.11.). Обычно BSP-деревья используются для представления двух- и трехмерных пространств, но, по определению, эти структуры не ограничены тремя измерениями. В нашем случае этим пространством является часть пространства, заметённая инструментом, а BSP-дерево задаёт ограничивающий это пространство объём.
Для демонстрации возможности применения BSP-деревьев в моделировании удаления материала рассмотрим следующий пример. В горизонтальной плоскости по прямолинейному участку траектории движется конический инструмент. Аналитическая поверхность, заметаемая этим инструментом, вычисленная согласно п. 2.1.1, показана на рис. 2.12 а). Плоскости, позволяющие построить твёрдотельное аппроксимированное представление данной поверхности в виде BSP-дерева, представлены на рис. 2.12 б). Отметим, что точки, принадлежащие этим плоскостям также рассчитываются, используя соотношения, приведённые в п. 2.1. Для задания каждой грани в этой модели не обязательно наличие контура, её образующего; достаточно указать одну точку на плоскости и вектор нормали (изображение контуров граней на рис. 2.12 выполнено только для наглядности).
Формирование динамического BSP-дерева
Предложенный в предыдущей главе подход по формированию тела, заметаемого движущимся инструментом на одном участке траектории, также может быть использован при получении результата обработки в целом для всего процесса фрезерования. Для этого достаточно выполнить на каждом кадре программы последовательное построение заметаемого объёма (в форме BSP-дерева см. п. 2.3.) и его булево вычитание из тела заготовки, которая также должна быть представлена в виде BSP-дерева. Результатом такой процедуры будет по-прежнему В SP-дерево, полностью описывающее результат удаления материала.
Несмотря на кажущуюся простоту предложенного подхода реализация предложенной процедуры связана с определёнными трудностями. А именно, непосредственное выполнение операции вычитания заметаемого объёма из тела заготовки, даже в виде BSP-дерева, требует временных затрат, причём эти затраты превосходят время построения самого BSP-дерева на соответствующих кадрах программы. Учитывая то, что подобное вычитание должно производится для каждого кадра программы (их может быть сотни тысяч), становиться вполне понятным и обоснованным требование к скорости выполнения этих операций вычитания, а эта задача является достаточно сложной.
Принимая во внимание указанный факт к решению задачи моделирования можно подойти по иному. Если операция вычитания объёмов так критична по времени и сильно влияет на производительность всего метода, то можно попытаться сократить число её повторений. Лучшим случаем было бы выполнение булевой операции не для каждого кадра управляющей программы, а для всей программы в целом, т.е. только один раз. Данное условие требовало бы создания В SP-дерева, описывающего заметаемый объём полностью на всей программе. Возникает вопрос, может ли быть получено такое BSP-дерево, а если да, то что оно будет из себя представлять?
Нужно сказать, что в принципе такое BSP-дерево может быть построено. Для этого, по-прежнему, могут использоваться грани, формируемые на каждом кадре управляющей программы по правилам, описанным в п. 2.3. Подчёркивая преимущества этого дерева, укажем, что оно будет строиться только один раз, следовательно, оно может являться более сбалансированным. Для этого могут использоваться всевозможные, уже известные, алгоритмы построения BSP-деревьев.
Однако, такой метод построения В SP-дерева имеет ряд существенных недостатков. Во-первых, всё множество граней, сформированных на этапе покадрового выполнения управляющей программы, будет содержать большое количество плоскостей, которые заведомо в формировании границы объёма участвовать не будут. Вследствие этого возникает задача идентификации и удаления этих плоскостей, поскольку в конечном BSP-дереве их оставлять нельзя. В противном случае может произойти неправильное построение дерева и, кроме того, это приведёт к существенной потери памяти и производительности при работе с BSP-деревом. Заметим, что на этапе формирования BSP-дерева полностью все подобные грани удалены быть не могут, так как их положение и вклад в общий объём можно рассматривать только в совокупности со всеми остальными гранями объёма. Как следствие, необходимо проведение некоторой специальной процедуры прореживания уже построенного BSP-дерева, что, несомненно, приведёт к частичной или полной перестройке первоначального BSP-дерева.
Во-вторых, построение сбалансированного дерева (в данной ситуации, когда известны все образующие объём грани, построение такого дерева желательно) сильно зависит от выбора начальной грани. В работе [74] указывается, что поиск такой начальной грани BSP-дерева является достаточно существенной задачей.
В-третьих, есть ещё одна специфическая проблема, которая пока не приводилась. Для её обсуждения вернёмся к тому, что рассматривается технологический процесс фрезерной обработки, а предлагаемые методы должны обеспечивать возможность его моделирования. Процесс "ручного" создания конструктором управляющей программы можно представить последовательностью следующих действий: - конструктор-технолог формирует последовательность управляющих команд (для этого могут использоваться различные САМ программы, либо, в крайнем случае, конструктор задаёт их самостоятельно). Набор этих команд назовём версией УП; - далее, технолог должен проверить эту версию или выполнить её; - после исправления ошибок создаётся новая версия УП, которая впоследствии также проверяется. Другими словами, технолог, который непосредственно занят созданием управляющих программ и несёт ответственность за их качество и правильность, в своей работе часто возвращается назад по программе, делая при этом изменения. Как следствие, результат обработки, а вместе с ним и объём, заметаемый инструментом, также изменяются; естественно, что модель, имитирующая технологический процесс, тоже должна обладать возможностью описанного действия. В случае, когда производится построение BSP-дерева для всей последовательности кадров программы, реализация данного условия приведёт к полной перестройке ранее сформированного BSP-дерева, что, несомненно, скажется на условиях работы пользователя и времени получения конечной управляющей программы. Решение описанных проблем достигается при расширении обычного представления ВSP-деревьев до нового понятия - динамического BSP-дерева. Динамическим В SP-деревом будем называть дерево, которое не нужно перестраивать при добавлении в него новых граней (плоскостей). Конечно, сама суть поставленного вопроса достаточно спорна, известно [74, 62], что BSP-дерево является достаточно статичной структурой и требует своей перестройки при изменении сцены. Однако, учитывая некоторые особенности предметной области фрезерной обработки, данная процедура формирования динамического BSP-дерева всё же возможна.
