автореферат диссертации по инженерной геометрии и компьютерной графике, 05.01.01, диссертация на тему:Разработка методов и геометрических моделей анализа незаполненных пространств в задачах размещения

кандидата технических наук
Ситу Лин
город
Москва
год
2011
специальность ВАК РФ
05.01.01
цена
450 рублей
Диссертация по инженерной геометрии и компьютерной графике на тему «Разработка методов и геометрических моделей анализа незаполненных пространств в задачах размещения»

Автореферат диссертации по теме "Разработка методов и геометрических моделей анализа незаполненных пространств в задачах размещения"

На правах рукописи

Ситу Лин

«РАЗРАБОТКА МЕТОДОВ И ГЕОМЕТРИЧЕСКИХ МОДЕЛЕЙ АНАЛИЗА НЕЗАПОЛНЕННЫХ ПРОСТРАНСТВ В ЗАДАЧАХ

РАЗМЕЩЕНИЯ»

Специальность 05.01.01 Инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

1 5 т 2011

Москва 2011

005006100

Работа выполнена в Московском авиационном институте (национальный исследовательский университет) на кафедре «Инженерная графика»

Научный руководитель:

кандидат технических наук," доцент, Маркин Леонид Владимирович

Официальные оппоненты:

доктор физико-математических наук, доцент, Рабинский Лев Наумович, декан факультета «Прикладная механика» МАИ

кандидат технических наук, Викулин Юрий Юрьевич , начальник отдела геометрических данных ОАО «Компания «Сухой»

Ведущая организация: Московский государственный техниче-

ский университет радиотехники, электроники и автоматики (МИРЭА)

Защита состоится « 28 » декабря 2011г. в 10.00 часов на заседании диссертационного совета Д 212.125.13 при ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)» по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)»

Автореферат разослан « 25 » ноября 2011 г.

Ученый секретарь

диссертационного совета Д 212.125.13, кандидат технических наук, профессор

Л. В. Маркин

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Развитие современной авиационно-космической :хники, рост требований к ней и повышение плотности компоновки заставляют энструкторов постоянно совершенствовать методы проектирования. Даже грвые опыты компьютеризации процесса проектирования при решении гдельных частных задач показали их высокую эффективность. Однако переход г 2Б объектов к ЗО объекта^'и усложнение формы размещаемых объектов от инейных полос до реальных объектов современной техники вызвало свинообразное усложнение математического описания процесса размещения. В иссертационной работе, исследуются вопросы, связанные с автоматизацией цной из важных и' трудоёмких операций проектирования - размещения юметрических объектов среди уже размещенных и областей запрета (например, ортовых приборов в отсеке легкого самолета). Современные методы зтоматизации компоновки основанны на различных геометрических моделях и гсгоритмах последовательно-одиночного размещения, что позволяет отыскать окальный экстремум функции цели по параметрам размещения. Различные :пекты вопросов автоматизации компоновки нашли свое разрешение в работах .Л.Рвачева, Ю.Г.Стояна, Н.И.Гиля, В.Н.Гаврилова, М.Ю.Куприкова,"В.В. 1альчевского, В.И.Кулиша, Л.В.Маркина и др.

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

Задача определения формы незаполненных пространств достаточно легко решается человеком, ассоциативное мышление которого способно

распознать, что эта часть пространства больше всего похожа на цилиндр, а эта на сферу. К сожалению эта столь простая для человека операция распознавай] образов представляет значительную сложность даже для современных ЭВГ> которые с трудом распознают и классифицируют не то что трехмерные объект! а обычный рукописный текст. Таким образом, для компьютерно] проектирования ответ на этот вопрос является чрезвычайно сложной задаче распознавания образа пространства и получил свое решение лишь д; некоторых частных случаев.

Известные работы по проблемам вложимости получили свое решение трудах выдающихся математиков Дж. Александера, П. С. Александрова, Е. Bai Кампена, К. Куратовского, С. Маклейна, Л. С. Понтрягина, Р. Тома, X. Уитни, > Хопфа и других как решение достаточно абстрактных задач топологии вложимости подпространств определенного класса в некое абстрактно пространство, вложимости графов и т.п. Наиболее близкие к геометри результаты получены в защищенной в 2002 году докторской диссертации на соискание ученой степени доктора физ-мат. наук Скопенкова А.Б. «Вложения многообразий в Евклидовы пространства», но полученные в ней результаты носят абстрактный математический характер. Другие прикладные исследования в этой области не имеют геометрической направленности, например, защищенная в 2007 году диссертация Лифшица Ю.М. на соискание ученой степени канд. физ-мат наук посвящена анализу вложимости символьных подстрок в архивированных текстах без их распаковки. Представляемая же диссертация посвящена именно геометрическим проблемам вложимости в задачах автоматизированной компоновки технических объектов. Такая задача актуальна при автоматизированном проектировании объектов с высокой плотностью компоновки, прежде всего летательных аппаратов. Используемые при решении этой задачи рецепторные геометрические модели были предложены Д.М.Зозулевичем в 60-х годах прошлого века и использованы для

ешения других прикладных задач К.М.Наджаровым, Г.В.Корн и рядом других второв.

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

Достижение поставленной цели диссертационной работы осуществлено а основе решения следующих задач:

1. Анализ физической постановки задачи получения компоновок аивысшей плотности;

2. Анализ методов геометрического моделирования в задачах втоматизации компоновки;

3. Выбор метода геометрического моделирования, позволяющего существить распознавание формы незаполненных пространств;

4. Разработка геометрических моделей оценки формы незаполненного ространства, ее вида из объектов определенного класса, размеров и асположения;

5. Разработка методов преобразования геометрических моделей видов параметрическая <-» рецепторная» для оценки и визуализации результатов юделирования;

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

7. Тестирование на реальных объектах и оценка точности разработанной геометрической модели на примере компоновки технического отсека легкого самолета «АСА-2».

Метододика исследования. При решении поставленной задачи диссертационной работе был использован рецепторный метод, основанный i дискретизации пространства на отдельные ячейки - рецепторы (в англоязычно литературе этот метод называется «воксельным»). Такой метод позволяет да исследования формы облака рецепторов использовать методы теори вероятностей и математической статистики в пределах точности рецепторно геометрической модели. На основании такого анализа задача автоматизаци компоновки решается как задача последовательно-одиночного размещени объектов класса «примитивы» и объекты СТС (сложных технических структур т.е. композиция примитивов).

Программная реализация предложенных геометрических моделе базируется на платформе Microsoft и языковых средств MS Visual Studio©.

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

В ходе работы были получены следующие новые результаты:

1. Разработан метод определения геометрической формы незаполненных пространств на основе рецепторного метода геометрического моделирования и аппарата статистической проверки гипотез.

2. Разработана геометрическая модель описания формы незаполненных пространств в параметрическом виде в классе объектов «примитивы» и объектов СТС («композиция примитивов»),

3. Разработан метод преобразования параметрической модели в рецепторную и рецепторной в параметрическую для примитивов и объектов СТС применительно к задачам автоматизированной компоновки.

4. Разработан метод определения вложимости геометрических объектов незаполненные пространства и алгоритм автоматизированной компоновки по ритерию максимального заполнения компоновочного пространства.

5. Осуществлена программная реализация разработанной гометрической модели и ее визуализация на алгоритмическом языке С (С-Ьагр).

6. Проведена верификация разработанной геометрической модели, ее очности представления геометрических объектов и времени выполнения в

ависимости от исходных параметров.

7. Результаты исследований в области анализа незаполненных ространств внедрены при проектировании легкого самолета АСА-2 и в учебный

процесс МАИ.

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

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

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

Апробация работы. Основные результаты работы докладывались обсуждались на национальных и международных научно-технически конференциях:

1. Научно - практическая конференция студентов и молодых учёных MAI «Инновации в авиации и космонавтике - 2010 », МАИ, Москва, 2010 г.

2. Международном молодежном научном форуме-олимпиаде по приоритетным направлениям развития Российской Федерции, МГТУ им. Н.Э.Баумана, Москва, 2010 г.

3. VII Всероссийской конференции студентов, аспирантов и молодых учёных «Технологии Microsoft в теории и практике программирования», МАИ, Москва, 2010 г.

4. 9-ой Международной конференции «Авиация и космонавтика - 2010», МАИ, Москва, 2010 г.

5. Научно-практической конференции студентов и молодых учёных МАИ «Инновации в авиации и космоновтике -2011 », Москва, 2011 г.

Кроме того, результаты работы внедрены в учебный процесс кафедры «Инженерная графика» МАИ и при создании легкого самолета АСА-2.

Публикации

Основные материалы диссертационной работы опубликованы в 6 печатных работах, в том числе 1 работы в издании, входящем в перечень ВАК.

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения и писка используемых источников. Общий объем диссертационной работы оставляет 121 страниц., включая 67 рисунок и 1 таблица. Список литературы ключает 116 наименований, в том числе 16 на иностранных языках.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

1. Основные операции компьютерной геометрии и графики (пространственные преобразования, определение инциндентности и т.п.);

2. Преобразования на плоскости, определение расстояний, периметров и т.д. в двумерном пространстве;

3. Геометрические преобразования, определение пересечений объектов и в трехмерном пространстве.

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

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

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

• необходимость оперирования с геометрической информацией обработка которой в ЭВМ представляет собой отдельную и весьма непростун задачу;

• неочевидность алгоритма решения задачи оптимального размещения.

Опыт разработки такого «эрзац-мышления» для компьютерного

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

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

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

Во второй главе диссертационной работы представлены разработка методов и геометрических моделей анализа незаполненных пространств в задачах размещения.

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

Пусть имеется N компонуемых объектов Т, (1=1, ... , И) и область размещения П. Требуется разместить эти объекты с учетом заданных ограничений в области О таким образом, чтобы функция цели компоновки Ф (X) достигала экстремума, т.е. определить

Ех1гФ(Х) приХс: О где X -некоторая переменная, определяющая параметры размещения. Таким образом, математическая постановка задачи размещения включает 3 компонента:

1. Выбор функции цели Ф (X);

2. Выбор переменной X;

3. Выбор и формализация ограничений.

Основным геометрическим условием рационального размещения объектов является условие рационального размещения в области О некоторого множества

(гГ

компонуемых объектов I 'я (где п достаточно велико) или наибольшего

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

ку=£ук.0./г0тс.

1=1

п

ка г

где - сумма объемов п скомпонованных объектов,

Vотс. - объем отсека, в котором производится компоновка. Условие максимальной плотности компоновки записывается в виде выражения ЕзОг Г(Х) при X с О

1 0)

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

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

Для решения поставленной задачи нами положено использование рецепторных геометрических моделей (РГМ), дискретизирующих пространство. В основу рецепторного метода (известного также как «матричный», «бинарный», «перечисления элементов пространства», «воксельный» (в

-12-

англоязычной литературе) и т.д.) положено приближенное представление геометрического объекта в поле или пространстве рецепторов. Для плоского случая поле рецепторов представляет собой однородную прямоугольную сеть тхп, каждая клетка которой рассматривается как отдельный рецептор, который может иметь два состояния - «О» или «1». Математически рецепторная геометрическая модель описывается множеством А={аК]}, где

Г 1, если рецептор возбужден,

а'-] |0, если рецептор не возбужден

Рецептор считается невозбужденным, если через него не проходит граница объекта и он не принадлежит внутренней области (рисунок 1). Трехмерные объекты описываются трехмерной матрицей А-{а^} размерностью тхпхр. Переведя данные об уже размещенных объектах в рецепторное пространство (рисунок 1), будем искать для возможного размещения еще неразмещенных объектов свободные области как «сгустки» близкорасположенных 0-вых рецепторов. При этом пространственная задача сводится к плоской, для чего анализируются как бы срезы компоновки. Именно рецепторные геометрические модели позволяют сформировать специальные алгоритмы, которые не только выявляются незаполненные области, но и позволяют найти центр каждой из них. Далее оценка формы незаполненной области (как сгустка рецепторов) производится по слоям, что рецепторная модель позволяет сделать особенно эффективно. Для каждого слоя свободного пространства необходимо определить, на какой плоский примитив (круг, прямоугольник, многоугольник) срез свободной области больше всего похож.

Однако в исходной конструкторской документации размещаемые объекты задаются не РГМ, а как отдельные примитивы или их композиция, причем каждый примитив задается своими характерными размерами (т.е. исходные модели представлены в параметрической форме).

Рисунок 1 - Описание объекта рецепторной матрицей Поэтому анализу незаполненного пространства в нашей модели предшествует преобразование исходной параметрической модели в рецепторную и последующее обратное преобразование рецепторной в параметрическую для интерпретации результатов моделирования (рисунок 2).

Рисунок 2 - Преобразование моделей «рецепторная - параметрическая»

Результат преобразования параметрической модели в рецепторную показан на двумерном пространстве показан на рисунке 3.

Далее производится анализ непосредственно РГМ. Для этого нами разработан алгоритм, позволяющий определить центр определенной свободной области (пока плоской) и ее размеры. На рисунке 4 видно, что на срезе рецепторной матрицы алгоритм обнаружил 4 такие области, которые закрасил разным цветом.

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

- 14-

Рисунок 3 - Преобразование параметрической модели в рецепторную в двухмерном пространстве в области £1

Рисунок 4 - Положения и размеров незаполненных областей по плоскому

сечению

Для этого из центра каждой области по отдельному сечению строится годограф радиуса-вектора, после чего таким пространством признаков для нас танет годограф функции радиуса вектора от центра сечения Г= Я, (ср,) (рисунок

:)

где К,- текущая длина радиуса - вектора для /-го рецептора,

срг текущий угол радиуса - вектора для / - го рецептора. - 15-

После того, как для конкретной плоской области сформирована функцию Л, (ср,), мы на время забываем о РГМ и начинаем анализировать эту функцию. Если формой этой области был бы круг, то функция была бы идеальной прямой, высота которой показала бы нам радиус этого круга (рисунок 6), если многоугольник - то «пила» с количеством вершин, равным количеству сторон.

рентные рэцегтгорь;

Радкгус- еек'ср

___1_

Рисунок 5 - Построение годографа функции радиуса-вектора

Координаты вершин по (р позволят определить соотношения сторон прямоугольника. Именно этот график и станет объектом анализа, по которому необходимо определить геометрическую форму исследуемой области.

многоугольник круг

<Р, Ры

Рисунок 6 - Анализ незаполненной области пространства (случаи - круг и

многоугольник)

На графике мы никогда не увидим столь идеальной кривой - на ее

характер будут влиять как случайные отклонения 5, , обусловленной

дискретностью рецепторной модели, так и систематические отклонения,

обусловленные тем, что исследуемая область является не идеальным кругом,

прямоугольником и т.п. Реальный график функции Я, (щ), сделанный для

- 16-

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

Далее производится анализ сечений следующего слоя. Если форма сечения и его размеры не изменились (в пределах статистических погрешностей), то область интерпретируется как цилиндр или призма, если изменяются размеры без изменения формы - то как шар, пирамиду или конус. «Резкое» изменение размеров или формы сечения говорит о границы области незаполненного пространства.

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

6г«рЬ

« 1 \ \ Л

- Т" —"7 \~~fzr—г Ц />л / \М / ! / 5-Л " \ / 1 V

— ■к гк мо

Рисунок 7 - График реальной функции для анализа образа незаполненного

пространства

Разработанный в рамках выполнения диссертационной работы программный комплекс позволяет визуализировать незаполненные области пространства. Из тестового примера, изображенного на рисунке 8 видно, что незаполненные пространство состоит из отдельных областей, автоматически пронумерованных системой.

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

Если после выявления свободной области у нас появилась необходимость разместить в этой области не параллелепипед максимального размера (рисунок 9), а, например, сферу определенного радиуса (рисунок 10), то она становится после этого полноправным участником сцены (рисунок 11) и после нажатия интерфейсной кнопки «Analysis» происходит новое определение конфигурации незаполненных пространств.

Рисунок 8 - Определение конфигурации незаполненных пространств и вывод результатов анализа в графическом и параметрическом виде

Рисунок 9 - Визуализация вписанного объекта максимально возможных

размеров

Рисунок 10 - Добавление скомпонованных объектов в РГМ - сферы максимально возможного радиуса как области возможного размещения

Рисунок 11 - Размещенный в свободной области объект как полноправный

участник сцены

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

1,0

0,8

5 0,6 г

|о,4

\

змер реце птора А

у\ Погре шность ог исания 8

1 5 10 15 20 25

к 1000 рецепторов матрицы

Рисунок 12 - Оценка точности РГМ в зависимости от размеров рецептора

-20-

Значение наиболее вероятной относительной погрешности будут определяться размерами описываемого тела. Для описанной РГМ сферы различных радиусов, расположенных в рецепторной матрице размерами 1мх1м, вычисленные значения относительной погрешности приведены на рисунке 13.

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

х 1000 рецепторов матрицы

Рисунок 13 - Графики оценка относительной погрешности РГМ

На рисунке 14 приведена оценка затрат процессорного времени при ;шении поставленной задачи распознавания плоской области с фиксированным отчеством рецепторов (1000 хЮОО). Из рисунка 14 видно, что время работы юцессора определяется количеством уже размещенных объектов, но все равно лается сравнительно небольшим (доли секунды) даже для компьютера эщности ниже средней.

mm Graphic [ 30 Vsew Analysis Curve view Data Analysis

Computer Processing Time

о t 2 э

Number Of Objects

Рисунок 14 - Затраты процессорного времени для определения незаполненных пространств в зависимости от числа уже размещенных объектов Внедрение результатов исследования проведено использованием разработанных методов и программ в процессе проектирования легкого самолета АСА-2, позволившим выявить незаполненные пространства в техническом отсеке (рисунок 15) и в учебный процесс кафедры инженерной графики МАИ.

Рисунок 15 - Выявленные свободные пространства легкого самолета

Заключение

На основе анализа существующих методов ГМ в задачах автоматизации компоновки обоснована целесообразность использования рецепторных моделей как одной из моделей, используемых в начальных этапах проектирования технических объектов. Выбор именно рецепторных моделей основан на том, что РГМ позволяет формировать геометрические модели объектов СТС, легко преобразуемые в другие виды моделей, в частности параметрические. Проведенное исследование позволило сформулировать следующие выводы:

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

2. Разработанная геометрическая модель описания формы незаполненных пространств, анализируя форму в рецепторном пространстве, позволяет представить результаты анализа в параметрическом виде в классе объектов «примитивы» и объектов СТС («композиция примитивов»).

3. Разработан - метод преобразования параметрической модели в рецепторную и рецепторной в параметрическую для примитивов и объектов СТС применительно к задачам автоматизированной компоновки.

4. Разработан метод определения вложимости геометрических объектов в езаполненные пространства и алгоритм автоматизированной компоновки по ритерию максимального заполнения компоновочного пространства.

5. Осуществлена программная реализщация разработанной геометрической одели на алгоритмиченском языке С (С-БЬагр), включая блок визуализации эмпоновки и оценки результатов моделирования.

6. Проведенная верификация разработанной геометрической модели эказала, что ее точность представления геометрических объектов зависит от тдеров компонуемых объектов и дискретности их описания, и для реальных эмпонуемых объектов бортового оборудования при размерах рецепторной атрицы 5... 10 тысяч элементов абсолютная погрешность описания формы не эевышает 0,1 мм, а относительная - 0,01.. .0,03%.

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

Основное содержание диссертации изложено

В изданиях, рекомендованных ВАК РФ:

1. Ситу JL, Хтун Н. Н., Маркин JI. В. Рецепторные геометрические модели в задачах автоматизированной компоновки технического отсека легкого самолета. // Труды МАИ, электр. журнал (http://www.mai.ru), вып. №47, 2011 г.

В других изданиях:

2. Ситу Лин. Дискретные модели выявления формы незаполненных пространств. // Научно - практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космонавтике - 2010 ». Тезисы докладов. - М.: Изд-во МАИ. - 2010. - С. 192.

3. Ситу Лин. Распознавание незаполненных пространств в задачах объемной компоновки. // Студенческий научный вестник. Сборник статей международного молодежного научного форума-олимпиады по приоритетным направлениям развития Российской Федерции, МГТУ им. Н.Э.Баумана. - М.: Изд-во HTA «АПФН» , 2010. С.192 - 196.

4. Ситу Лин. Использование рецепторных моделей для компоновки незаполненных пространств. // Технологии Microsoft в теории и практике программирования: труды VII Всероссийской конференции студентов, аспирантов и молодых учёных. - М.: Изд-во Вузовская книга - МАИ. — 2010. — С.87 -88.

5. Ситу Лин. Алгоритмы распознавания незаполненных пространств в задачах компоновки. // 9-я Международная конференция «Авиация и космонавтика - 2010 ». - М.: Изд-во МАИ. - 2010.-С.315-316.

6. Ситу Лин. Разработка математического и программного обеспечения для автоматизированной компоновки незаполненных пространств. // Научно-практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космоновтике - 2011 ».-М.: Изд-во МЭИЛЕР.С. 112.

Оглавление автор диссертации — кандидата технических наук Ситу Лин

Введение.

1 Анализ методов геометрического моделирования объектов. в задачах автоматизации компоновки.

1.1 Обще требования к формированию геометрических моделей. трехмерных объектов.

1.1.1 Требования к формированию геометрических моделей. объектов СТФ и СТС.

1.2 Общие принципы формирования геометрических моделей. объектов.

1.3 Методы моделирования трехмерных ГО.

1.4 Возможности использования кусочно-аналитических геометриических моделей в задачах компоновки.

1.5 Рецепторные геометрические модели и общие принципы их формирования

1.6 Особенности визуализации геометрических моделей. трехмерных объектов.

ВЫВОДЫ К ГЛАВЕ 1.

2 Разработка и исследование методов формирования РГМ анализа незаполненных пространств в задачах размещения.

2.1 Постановка задачи исследования.

2.2 Методы решения формирования РГМ анализа. незаполненных пространств.

2.3 Формирование РГМ объектов в двумерном пространстве.

2.4 Формирование РГМ объектов в трехмерном пространстве.

2.5 Хранение разреженных матриц для РГМ.

2.6 Геометрическая модель определеничя вложимости объектов, описанных РГМ.

ВЫВОДЫ К ГЛАВЕ 2.

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

3.1 Определение формы свободной области в двухмерном. пространстве.

3.2 Определение формы свободной области в трехмерном. пространстве.

ВЫВОДЫ К ГЛАВЕ 3.

4 Исследование рецепторных геометрических моделей анализа незаполненных пространств в задачах размещения.

4.1 Оценка точности рецепторной геометрической модели (РГМ).

4.2 Оценка производительности вычислений с помощью. рецепторной геометрической модели (РГМ).

4.3 Примеры реализации рецепторной геометрической модели определения незаполенных пространств.

Введение 2011 год, диссертация по инженерной геометрии и компьютерной графике, Ситу Лин

Автоматизация проектирования занимает особое место среди информационных технологий. Во-первых, автоматизация проектирования -синтетическая дисциплина, ее составными частями являются многие другие современные информационные технологии. Так, техническое обеспечение систем автоматизированного проектирования (САПР) основано на использовании размещения объектов как в двухмерном, так и в трехмерном пространстве. По опубликованным данным [26] применение САПР позволяет в 2-3 раза сократить время проектирования и доводки летательных аппаратов (JIA), в 3-5 раз время подготовки их производства. В САПР используются персональные компьютеры и рабочие станции, математическое обеспечение САПР отличается богатством и разнообразием используемых методов вычислительной математики, статистики, математического программирования, дискретной математики, искусственного интеллекта.

Летательный аппарат как объект проектирования представляет собой сложную техническую систему. На рисунке В.1 представлены основные блоки проектирования самолета на ранних этапов разработки проекта. Каждый из блоков обладает собственной библиотекой методов. Количество расчетных модулей на которые делятся блоки зависит от конкретного этапа проектирования и определяет характеристики расчетной модели блока.

Это согласуется с современной методологией автоматизированного проектирования, когда в соответствии с принципами системного подхода, каждому этапу проектирования соответствуют свои модели. Программные комплексы САПР относятся к числу наиболее сложных современных программных систем, основанных на операционных системах Unix, Windows, языках программирования С, С++ , Java, и других, современных CASE-технологиях, реляционных и объектно-ориентированных системах управления базами данных (СУБД), стандартах открытых систем и обмена данными в компютерных средах. Таким образом, блок геометрии являете существенным компонентом общей САПР летательных аппаратов (ЛА).

Рисунок В.1 - основные блоки автоматизированного проектирования Л А

На сегодняшний день разработаны геометрические и математические модели (ГМ и ММ), которые обеспечивают простоту ввода геометрической информации, что важно для начальных этапов проектирования. К сожалению, они, как правило, имеют сложную внутреннюю информационную структуру. Скорость обработки таких моделей недостаточна для обеспечения интерактивных режимов работы. Особенно остро стоит задача обеспечения скорости работы алгоритмов обработки геометрической информации в задачах компоновки в силу необходимости анализа условия взаимного непересечения большого количества геометрических объектов (ГО) [26, 52, 54].

Задачи автоматизации компоновки отличаются наиболее низкой степенью формализации. Между тем они занимают одно из первых мест по сложности и в значительной мере влияют на качество проектирования таких сложных технических объектов как летательный аппарат. Но возможности ЭВМ только дополняют интеллектуальные возможности человека. Процесс разработки проекта - творческий акт и он никогда не может быть до конца формализован. Отметим особенности изделий авиационной техники (АТ) как объектов проектирования:

• большое разнообразие геометрических объектов (ГО) - от ГО простых структур и форм, представляющих собой, например, детали креплений и приборы до ГО сложных технических структур (СТС);

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

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

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

Развитие современной авиационно-космической техники, рост требований к ней и повышение плотности компоновки заставляют конструкторов постоянно совершенствовать методы проектирования. Даже первые опыты компьютеризации процесса проектирования при решении отдельных частных задач показали их высокую эффективность. Работы по автоматизации размещения не составляли исключения. Первые публикации, посвященные автоматизации решения задач размещения относятся к 60-м годам прошлого века и связаны с именами Л.В.Канторовича и В.А. Залгаллера по раскрою материалов методами линейного программирования. Однако переход от 2Т> объектов к ЗБ объектам и усложнение формы размещаемых объектов от линейных полос до реальных объектов современной техники вызвало лавинообразное усложнение математического описания процесса размещения. Несмотря на то, что исследованию этого вопроса посвящены труды многих ученых - В.Л.Рвачева, Ю.Г.Стояна, В.Н.Гаврилова, М.Ю.Куприкова, В.В. Мальчевского, Л.В.Маркина и многих других, эта задача далека от своего разрешения.

Данная работа посвящена вопросам автоматизации компоновки, в частности такому ее аспекту, как «доразмещение» еще не размещенных объектов среди тех, которые уже установлены в определенном замкнутом пространстве. С геометрической точки зрения она представляет собой решение задачи «вложимости» ГО определенного класса в зоны их возможного размещения и в широком плане может трактоваться как задача распознавания образов применительно к предметной области компоновки технических объектов с высокой плотностью размещения, в частности ЛА. Цели работы

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

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

3. Исследование и верификация разработанных геометрических моделей.

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

Заключение диссертация на тему "Разработка методов и геометрических моделей анализа незаполненных пространств в задачах размещения"

ВЫВОДЫ К ГЛАВЕ 3

В данной главе представлена разработанная РГМ определения формы, размеров и положения незаполненных пространств как сгустка 0-вых рецепторов рецепторной матрицы. Исходная дискретность рецепторной модели позволяет анализировать рецепторную матрицу по слоям, определяя на какую геометрическую фигуру больше всего статистически подходит «плоский срез» рецепторной матрицы - на круг, прямоугольник или многоугольник. Описаны алгоритмические и программные основы реализации предложенного подхода на основе РГМ на ПЭВМ с использованием алгоритмического языка С (включая модуль визуализации полученного результата). Приведены тестовые примеры реализации предложенной геометрической модели. На основе исследований и разработок данной главы можно сделать следующие выводы:

Рисунок 3.13 - Схема алгоритма определении незаполненных областей размещения еще объекты

Maxirnun Draw » Rectangle Sphere Cylinder Draw j

Manual Draw о Rectangle Sphere Cylinder Width Height Length

7 7 7

Draw

Random Analysis Default Button

ShowFree

Data Analysis mmяёшёшш

Fil* Edit Tools View Rendering Help

Mam Graphic 3D View Analytic Curve View Data Analyst»

Analy»» Free Ana|ysrt

Choose The Spac* о

Sh*t X - 2,5bvt Y«2 , SUrt lO , End X-36 , End Y-ЗЪ , End ¿—12

W«ttt>-34,Hr*aM-Э4Д «ngtb-32

Maximum RadMs is 16.

Рисунок 3.14 - Визуализация вписанного объекта максимально возможных размеров

Analysis Free Апа|уБ|Б

Choose The Space q

Manmun Draw

Reclaivgle о £рі>«ГЄ Суіігкіеі I Draw :

Manua Drav, о Rectangle Sphere Cylinder width Height Length

7 7 7

Random Analysis Ddta Analysis

Default Button ShowFree

Start X»2,5b«t V-2 , Start Z-IO , End X-36 , End Y-3b , End ¿-42

Wtdtt» 34,Hogt*

Momuni Length a ІИ.

НЯНИ а)

• метод хранения разреженных матриц;

• метод структуризации ГМ объекта выделением пространственных форм одного класса эквивалентности;

• метод формирования матриц сложной структуры.

4. Разработанное на языке С программное обеспечение позволяет не только определять незаполненные области пространства, но и визуализировать полученные результаты и формировать данные о свободных пространствах в виде параметрических моделей.

4 Исследование рецепторных геометрических моделей анализа незаполненных пространств в задачах размещения

4.1 Оценка точности рецепторной геометрической модели (РГМ)

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

- громоздкость описания объектов, затрудняющая ввод и переработку геометрической информации в ЭВМ;

- большие затраты машинного времени при реализации метода. Тем не менее, нам представляется целесообразным развитие рецепторного метода с целью его адаптации к задачам автоматизированной компоновки.

Производим анализ точности РГМ рассматривая сначала плоский (2Б) случай - описание рецепторной моделью плоского контура. Примем допущения:

- рецептор имеет форму квадрата со стороной А;

- положение рецептора в системе координат рецепторной матрицы определяется его нижней левой стороной (рисунок 4.1).

Теперь рассмотрим прохождение теоретического контура размещаемого предмета через этот рецептор. Сначала рассмотрим случай, когда через него проходит строго вертикальный контур области (рисунок 4.2 а).

Рисунок 4.7 - Иллюстрация тестового примера оценки погрешности - шар вписан в рецепторную матрицу

Результаты расчета приведены в виде графика на (рисунок 4.8). Из этого графика видно, что погрешность описания формы РГМ зависит от размера рецептора, которая, в свою очередь, определяется количеством рецепторов в конкретной рецепторной матрице.

Имеется порог (в нашем случае это примерно 5 тысяч рецепторов), при уменьшении которого абсолютная точность описания формы резко снижается.

Значение наиболее вероятной относительной погрешности будут определяться размерами описываемого тела.

4.3 Примеры реализации рецепторной геометрической модели определения незаполенных пространств

Известно, что в процессе как ручного, так и автоматизированного проектирования самолета, строится график площадей по длинней самолета, характерный вид которого представлен на рисунке 4.12. Из этого рисунка видно, что для обеспечения заданного закона изменения площади омываемых поверхностей по длине самолета всегда остаются неиспользованные пространства (на рисунке 4.12 они заштрихованы). В них проектанты постараются разместить оборудование самолета, топливо, поленый груз и т.п., но даже после этого часть свободного пространства сохраниться, но выявить его станет значительно труднее из-за большого количества уже размещенных там объектов. Однакое его выявление и использование позволит повысить качество проектных решений, т.к. предопределит, что будет возить проектируемый самолет в этих пространствах -необходимое оборудование или воздух. крыло уШШ шасси внТотсёкЖ вооружений Щ

Библиография Ситу Лин, диссертация по теме Инженерная геометрия и компьютерная графика

1. Александров В.В., Горский Н.Д. Рекусивный подход к представлению и анализу данных. // Сб.статей «Прикладная информатика», вып. 2(7).М.:Финансы и статистика, 1984. - с. 102-117

2. Алекандров В.В., Горский Н.Д. Представление и обработка изображений.

3. Арциховская-Кузнецова J1.B. Автоматизация построения перспективных изображений. Учевное пособие. М.:МАДИ , 1986. - 68 с.

4. Арциховская-Кузнецова J1.B. Преобразование координат в машинной графике. Учебное пособие. М.:МАДИ , 1985. - 64 с.

5. Аггеева И.А., Корн Г.В., Маркин JI.B. Геометрические модели изделий машиностроения. // В сб.: Тезисы докладов Всесоюзной конференции «Современные проблемы автоматики». М.: 1989. - с. 47

6. Барковский В.И. Методологические аспекты разработки программы создания истребителя нового поколения // Сборник РАРАН, 2002. №28/4.

7. Барковский В.И., Скопец Г.М., Степанов В.Д. Методология формирования технического облика экспортно ориентированных авиационных комплексов. М.: Физматлит. 2008.

8. Баяковский Д.М., Галактионов В.А., Михайлова Т.Н. Графор. Графическое расширение ФОРТРАНа. М.: Наука , 1985. - 288 с.

9. Бодрышев В.В., Маркин J1.B. О заполнении замкнутого контура прямоугольниками. // В сб.: Тезисы докладов Всесоюзной конференции « Математическое обеспечение рационального раскроя в системах автоматированного проектирования». Уфа : 1987. - с. 18 - 19 .

10. Вальков К.И. Основы геометрического моделирования. Д.: ЛИСИ, 1986.

11. Гаврилов В.Н., Вахрушев А.Н. Разработка базы данных для задач компонования летательных аппаратов // В сб. Тезисов докл. III Всес. конф. «Автоматизация поиского конструирования и подготовка инженерных кадров». Иваново, 1983.

12. Горелик А.Г. Автоматизация инженерно-графических работ с помощью ЭВМ. -Минск: Высшая школа, 1980 г. 206 с.

13. Горелик А.Г. Об алгоритмическом построении теоретико-множественного описания геометрического объекта. // Вычислительная техника в машиностроении. Минск: ИТК АН БСССЗ, 1968, февраль , - с. 36 - 49 .

14. Горелик А.Г. Методы геометрического моделирования при автоматизированном проектировании объектов сложной структуры. Диссертация на соискание уч. степени д.т.н. - Минск: 1983.

15. Гардан И., Люка М. Машинная графика и автоматизация конструирования. -Мир, 1987.-270 с.

16. Грувер М., Зиммерс Э. САПР и автоматизация производства. М.:Мир, 1987. -528 с.

17. Гаврилов В.Н. Автоматизированная компоновка приборных отсеков летательных аппаратов. -М.: Машиностроение, 1988. 136 с.

18. Горский Г.К., Зозулевич Д.М., Шерлинг Д.Р. Алгебрологический метод решения геометрических задач при автоматизированном проектировании с помощъю ЭЦВМ. // В кн.: ВТ в машиностроении. Минск: ИТК АН БССР, 1971. - с. 24 -31.

19. Герасименко Е.П., Зозулевич Д.М. Минемизация вычислительного процесса при решении геометрических задач с помощъю рецепторных матриц. // В кн.: ВТ в машиностроении. Минск, ИТК АН БССР: июнь, 1970. с. 26 - 40 .

20. Герасименко Е.П., Зозулевич Д.М. Методы формирования трехмерных рецепторных матриц на ЭВМ. // В кн.: ВТ в машиностроении. Минск. ИТК АН БССР, 1971.-с. 24-31 .

21. Герасименко Е.П., Кот В.И. и др. Автоматизация проектирования печатных блоков с модулями произвольной формы. М.: Машиностроение , 1979. - 167 с.

22. Гиллой В. Интерактивная машинная графика. Структуры данных, алгоритмы, языки. М.: Мир, 1981. - 3 84 с.

23. Куприков М.Ю., Маркин Л.В., Панов В.В. и др. Формирование рационального облика перспективных авиационных ракетных систем и комплексов. М.: Машиностроение, 2010.

24. И.И.Котов, В.С.Полозов, Л.В.Широкова. Алгоритмы машинной графики. -М.Машиностроение, 1977. -238 с.

25. Котов И.И. Прикладная геометрия и автоматическое воспроизведение поверхностей. // В кн.: Кибернетика графики и прикладная геометрия поверхностей. Москва: МАИ, 1971, вып. 231 - с. 3 - 5

26. Клишин В.В. Моделирование трехмерных объектов на основе объемных базовых элементов формы. Диссериация на соискание уч.степени к.т.н., - М.:1983.

27. Мальчевский В.В. Автоматизация процесса компоновки самолета. М.: Изд-во МАИ, 1987.

28. Ли К. Основы САПР (САБ/САМ/САЕ ). СПБ .: Питер, 2004.

29. Маркин Л.В. Задачи формирования подсистем компоновки САПР летательных аппаратов. // В сб.: «Прикладная геометрия и инженерная графика в теории и практике авиационного автоматизированного проектирования» . Киев: КИИГА, 1984.-с. 6-9

30. Маркин Л.В. Геометрические модели компонуемых объектов в системе автоматизированного проектирования воздушных судов. // В сб. Научных трудов «Геометрические модели в авиационном проектировании». Киев: КИИГА, 1987. -с. 12-17

31. Маркин JI.В. Применение нормальных уравнений для решения компоновочных задач // Сб. «Геометрическое моделирование, инженерная и компьютеная графика». Тези доповидей. Харькие. 1993, XIII.

32. Математика и САПР: В 2-х кн. Кн. I. Пер. с франц. Шенен П., Гардан И. и др. -М.: Мир, 1988.-204 с.

33. Нестеров A.A., Куприков М.Ю., Маркин Л.В. Проектирование установок ракетного вооружения летательных аппаратов / под ред. В.А.Нестерова. М. Машиностроение, 2008.

34. Нильсон П. Принципы искусственного интеллекта: Пер с англ. М.: Радио и связь, 1985.

35. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. М.: Мир, 1976.- 373 с.

36. Обзор методов геометрического моделирования графических систем. Под ред. Педанова И.Б. М.:АН СССР ВЦ, 1987.

37. Осипов В.А. Математическое моделирование в автоматизированной системе геометрических расчетов. // В кн.: Машинное проектирование, увязка и воспроизведение сложных деталей в авиастроении. Иркутск, Изд. ИЛИ, 1977, -с.4-14.

38. Осипов В.А, Проектирование непрерывных каркасов поверхностей с наперед заданными дифференциальными свойствами. // Научн.тр. МИРЭА, 1972, вып. 63. Инженерная графика, -с. 47-53.

39. Осипов В.А. Машинные методы проектирования непрерывно-каркасных поверхностей. М.: Машиностроение, 1979, 248 с.

40. Перевезенцева A.B. Объемная компоновка отсеков оборудования с использованием SolidWorks // САПР и графика, 2006, № 6.

41. Похвалинский А.Б. Средства геометрического моделирования трехмерных объектов в САПР. Диссертация на соискание ученой степени к.т.н., Киев: 1986.

42. Принс M.Д. Машинная графика и автоматизация проектирования, М.: Сов.радио, 1975.-280 с.

43. Полозов B.C., Буденков O.A., Рожков С.И. и др. Автоматизированное проектирование. Геометрические и графические задачи. М.: Машиностроение, 1983.- 280 с.

44. Рыжов H.H. О теории каркаса. // Тр.УДН им. Лумумбы, №1 (И) 1963 с.9-19.

45. Рыжов H.H. Каркасная теория задания и конструирования поверхностей. // Тр.УДН им.Лумумбы, 1967, №3 (ХХУ1), с.3-12.

46. Рыжов H.H. Определитель поверхности и его применение. // Тр.УДН им.Лумумбы, том. III, Прикладная геометрия, серия "Математика", вып. 4, 1971. -с.3-17.

47. Реквиша А.А.Г., Воулкер Г.Б. Булевы операции при объемном, моделировании. Алгоритмы определения и соединения границ. // ТИНЭР, 1985, № I. с.32-49.

48. Рвачев В.Д. Геометрические приложения алгебра логики.- Киев: Техника, 1967. -211 с.

49. Рвачев В.Л. Теория R функций и некоторые ее приложения. - Киев: Наукова думка, 1982. - 552 с.

50. Роджерс Д., Адаме Дж. Математические основы машинной графики. М.: Машиностроение, 1980. - 240 с.

51. Розенфельд А., Дейвис Л.С. Сегментация и модели изображения. // ТИИЭР, т.67, №5, 1979.-е. 149-185

52. Рогоза Ю.А. Задание геометрических объектов в дискретном пространстве. МАИ, М.: 1989.-6 е.- Рукопись деп. в ВИНИТИ 27.12.89. №7690-В-89

53. Рогоза Ю.А., Сморщков Э.К. Об одной модели в позиционных задачах инженерной графики. Омский политехнический институт. Омск: 1988. -6с. -рукопись деп. в ВИНИТИ 21.02.89 №1110-В-89

54. Ситу JL, Хтун Н. Н., Маркин Л. В. Рецепторные геометрические модели в задачах автоматизированной компоновки технического отсека легкого самолет // Труды МАИ, электр. журнал (http://www.mai.ru), вып. №47, 2011 г.

55. Ситу Лин. Дискертные модели выявления формы незаполненных пространств // В сб.:Тез.докл научно практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космонавтике - 2010 ». Тезисы докладов. - М.: Изд-во МАИ. - 2010.-С.192.

56. Ситу Лин. Алгоритмы распознавания незаполненных пространств в задачах компоновки // В сб.:Тез.докл. 9-я Международная конференция «Авиация и космонавтика 2010 ». - М.: Изд-во МАИ. - 2010 . - С.315-316.

57. Стоян Ю.Г., Яковлев C.B. Математические модели и оптимизационные методы геометрическою проектирования. Киев.: Наукова думка, 1986 г.-265с.

58. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наукова думка, 1976г. - 246с.

59. Стоян Ю.Г. Размещение геометрических объектов. Киев: Наукова думка, 1975. -239 с.

60. Стоян Ю.Г., Кулиш Е.Н. Автоматизация проектирования компановки оборудования летательных аппаратов. М.: Машиностроение, 1984. -192с.

61. Сидоренко С.М. Вычислительная геометрия в машиностроении. М.: Машиностроение, 1983г. 160 с.

62. Стародетко Е.А., Усов Б.А. Методы лекальной параметризации в системах геометрического проектирования. Вычислительная техника в машиностроении. -1982.-№3.-с. 3-8.

63. Стародетко Е.А. Элементы вычислительной геометрии. Минск Наука и техника. 1986.-239 с.

64. Техническое зрение роботов /Под ред.Пью А., Пер, с англ. Миронова Д.Ф., Под ред. Г.П.Катыса. М.: Машиностроение, 1987. - 320 с.

65. Фоли Дж., Дэм А. Основы интерактивной машинной графики. М. Мир, 1985, -367 е., т,2

66. Фролов С.А. Алгоритмы графического решения задач на ЭВМ. Сб.: вычислительной техника, №4, М.: 1964г.- с. 5-10.

67. Фролов С.А. Кибернетика и инженерная графика. М.: Машиностроение, 1974г. -200 с.

68. Фокс А., Пратт М. Вычислительная геометрия, Применение в проектировании и на производстве. М.: Мир, 1982г. - 304 с.

69. Формалев В.Ф. Основы построения и математическое обеспечение системы автоматизированного проектирования летательных аппаратов. Автоматизация проектных расчетов. М.: МАИ, 1980. - 42 с.

70. Фу К. Структурные методы в распознавании образцов /Под ред. Айзермана М.А. М.: Мир, 1971.-319 с.

71. Якунин В.И. Геометрические основы системы автоматизированного проектирования технических поверхностей. М.: Изд. МАИ, 1980г.

72. Alexandre Hardy., Willi-Hans Steeb. Mathematical tools in computer graphics with C# implementations, April 1, 2008, p.496.

73. Barry G. Blundell. An introduction to computer graphics and creative 3-D environments, September 12, 2008, p. 500.

74. С. H. Chen., P. S. P. Wang. Pattern recognition and computer vision, September 2004.

75. Frieder G., Gordon D., Reynolds R. A. Back-to Front display of Voxel-Based Objects // IEFE Computer Graphics and Applications, v. 5, №1, Jan. 1985, p. 5-60

76. Gargantini I. Linear Octrees for Fast Processing of Three Dimensional Objects, // Computer Graphics and Image Processing, v. 20, №4, Dec. 1982., p. 565-574

77. Gargantini I., Walsh T.R., Wu O.L. Viewing Trans-Formations of Voxel-Based Objects via linear Octrees, IEEE Computer Graphics and Applications, 1986, №10, p. 12-21

78. Jacking C.L., Tanimoto S.L. Oct-trees and Their Use in Representating Three -Dimensional Objects,- Computer Graphics and Image Processing, VI4 , №3, Nov. 1980, p. 249-270

79. Jean Gallier. Geometric Methods and Applications: For Computer Science and Engineering, June 21, 2011, p.707.

80. Maurice G. Kendall. The advanced theory of statistics, 1945, p. 457

81. Max K. Agoston. Computer Graphics and Geometric Modeling, 2004, p. 373-470

82. Meagher.D. Geometric Modeling Using Octree Encoding, Computer Graphics and Image Processing, V.19, №2, June 1982, p. 129-147

83. Requcha A.A.G., Voelker H.B. Solid Modeling : A historical summary and contemporary assessment, IEEE, Computer Graphics and Applications , 1982, v.2, №2, p.9-24

84. Requcha A.A.G. Representation for Rigid Solid. Theory Methods and Systems. -Computer Surveys, 1980, v. 12, №4, p. 437-464

85. Samet H., Robert E., Webber E. Hierarhical Data Structures And Algorithms For Computer Graphics, Computer Graphics and Apptications, May 1988, p. 48-68 ; July 1988, p. 59-75

86. Sergios T., Konstantinos K. Pattern Recognition, 2009.

87. Sue Johnston-Wilder and John Mason. Developing Thinking in Geometry, 2005, p 961