Алгоритмические методы машинного формирования изображений трехмерных объектов в системах геометрического моделирования

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

В нашей стране созданию систем автоматизированного проектирования цридается большое значение. Так, необходимость «расширять автоматизацию проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники» записана в «Основных направлениях экономического и социального развития СССР на 1981;1985 годы и на период до 1990 года» (Материалы ХШ съезда КПСС,-М.: Политиздат, 1981, с.144).

В настоящее время как в нашей стране, так и за рубежом системы автоматизированного проектирования (САПР) успешно используются в различных отраслях цромышленности /2,13−16,24,25,28,40,46,49,5259,77,88,93,105,111,113,114/. Тем не менее, накопленный опыт эксплуатации САПР машиностроительных изделий говорит о недостаточном уровне автоматизации начальных этапов проектных работ таких, на которых осуществляется выбор и отработка принципов действия, определение внешнего облика разрабатываемого изделия, поиск конструкторских решений. Поскольку при этом определяются многие геометрические характеристики будущих изделий: взаимное расположение элементов конструкции, их форма и отдельные размеры, то работа конструктора на этих этапах требует выполнения большого объема чертеж-но-графических работ по прорисовке многочисленных вариантов проектных решений. Поэтому одной из актуальных задач дальнейшего совершенствования САПР, предназначенных для проектирования сложных технических изделий, является автоматизация геометрического моделирования, т. е. моделирования геометрических отношений в разрабатываемых объектах /17,40,43,50,53,54,58,75,89/.

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

Применяемые в настоящее время средства векторной машинной графики /3−6,12,18−23,26,27,30,40,51,59,87,90,91,102,103/ не удовлетворяют в полной мере всем требованиям геометрического моделирования. Формируемые ими контурные изображения трехмерных объектов не всегда обладают достаточной наглядностью. Кроме того, векторные дисплеи имеют ограничение на сложность воспроизводимых ими изображений.

Более высокими изобразительными возможностями обладают средства растровой машинной графики /1,42,51,73,80,85,86,94,98,105, 106,111/. Применение их в САПР делает возможным представление результатов геометрического моделирования сложных технических объектов в виде наглядных и реалистичных тоновых изображений, сложность которых ограничивается только разрешающей способностью растра и числом используемых градаций яркости и цвета.

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

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

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

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

ЦЕЛЬ РАБОТЫ заключается в разработке и исследовании методов и алгоритмов машинного формирования цветных тоновых изображений трехмерных объектов, ограниченных участками плоскостей и квадратичных поверхностей, и внедрении их в практику автоматизированного проектирования технических объектов. Указанная цель достигается в результате:1) разработки метода формирования изображения, основанного на декомпозиции изображаемых геометрических тел на простые геометрические тела и представлении проекций потенциально видимых частей их граней в алгебро-логической форме-2) разработки методики и алгоритмов преобразования произвольных ограниченных областей плоскости в границы сегментов их сечений линиями сканирования-3) разработки методов проецирования потенциально видимых частей граней простых геометрических тел и преобразования их проекций в границы сегментов-4) разработки методов и алгоритмов сокращения времени формирования изображения за счет минимизации площади области сканирования, достаточной для преобразования в границы сегментов простых геометрических тел и их граней-5) экспериментального исследования эффективности алгоритмов минимизации площади области сканирования при различных режимах их использования.

НАУЧНАЯ НОВИЗНА работы состоит в следующем: I) предложен и обоснован новый метод формирования изображения объектов, заданных плоскостями и квадратичными поверхностями, основанный на декомпозиции геометрических тел на простые геометрические тела и представлении проекций их граней в алгебро-логической форме-2) разработан метод классификации границ сегментов элементарных областей плоскости и методика выделения из них границ сегментов заданной области-3) получены аналитические соотношения, описывающие в алгеб-ро-логической форме проекции потенциально видимых частей граней простых геометрических тел, и исследованы условия их существования-4) разработан новый метод расчета координат точек линии пересечения квадратичных поверхностей и метод классификации их проекций как границ сегментов-• 5) разработаны методы минимизации площади области сканирования для проекций простых геометрических тел и проекций их граней, обеспечивающие сокращение непроизводительных затрат машинного времени при построении изображения.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Диссертационная работа выполнена в соответствии с тематическим планом научно-исследовательских работ Куйбышевского ордена Трудового Красного Знамени политехнического института и комплексной научно-технической программой Минвуза РСФСР «Системы автоматизированного проектирования» .

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

Комплекс программ реализован на универсальном языке РЬI и может быть использован в САПР различных организаций, занимающихсяпроектированием технических объектов и систем.

ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ. Основанная на применении разработанного комплекса программ методика геометрического моделирования технических изделий использовалась в хоздоговорной работе 5/77 (гос. per. № 76 093 943) и хоздоговорной работе 3/83 (гос. per. № 1 830 000 624), выполняемой по важнейшей тематике.

Экономический эффект от внедрения результатов работы составил 40 тыс. руб.

НА ЗАВДТУ ВЫНОСИТСЯ:1) обоснование метода формирования растровых изображений трехмерных объектов, заданных плоскостями и квадратичными поверхностями, основанного на декомпозиции геометрических тел на простые геометрические тела и представлении проекций потенциально видимых частей их граней в алгебро-лошческой форме-2) алгоритм преобразования произвольных ограниченных областей плоскости, заданных в алгебро-логической форме, в границы сегментов их сечений линиями сканирования-3) метод и алгоритм проецирования потенциально видимых частей граней простых геометрических тел и преобразования их проекций в границы сегментов-4) методы повышения эффективности разработанных алгоритмов формирования изображений трехмерных объектов за счет минимизации площади области сканирования на уровне простых геометрических тел и их граней.

АППР0БАВДЯ РАБОТЫ. Основные результаты докладывались и обсуждались на следующих конференциях и семинарах: — областная научно-техническая конференция «Молодые ученыеКуйбышевской области — производству», Куйбышев, 1977 г.— отраслевые семинары по применению электронно-вычислительной техники в проектно-технических разработках, Куйбышев, 1977, 1978 г.— 5,7,8,9 научно-технические конференции факультета математических знаний Куйбышевского политехнического института, Куйбышев, 1980, 1982, 1983, 1984 г.— научно-технический семинар кафедры «Техническая кибернетика» Куйбышевского авиационного института, Куйбышев, 1984 г.— научно-технический семинар Института аналитического приборостроения АН СССР, Ленинград, 1984 г.— Общемосковский семинар по математическому обеспечению систем машинной графики, Институт проблем управления АН СССР, Москва, 1984 г.— научно-технический семинар кафедры инженерной графики Московского авиационного института, Москва, 1984 г.

Основные результаты работы.

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

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

3. Сформулирована задача классификации границ сегментов элементарной области плоскости и предложен метод ее решения.

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

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

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

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

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

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

10. Экспериментально исследована эффективность разработанных алгоритмов минимизации площади области сканирования и определен режим оптимального их использования.

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

12. Основанная на применении разработанного комплекса программ методика геометрического моделирования технических объектов внедрена с экономическим эффектом 40 тыс. руб.

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

Диссертация посвящена решению одной из актуальных задач, однако, полученные в ней результаты не исчерпывают собой всего круга проблем растровой машинной графики. К числу таких проблем превде всего следует отнести проблему элайсинга {авсаыпд) /99,101,105/, проблемы изображения объектов, обладающих определенной текстурой поверхности, проблемы более полного и точного моделирования фотометрических факторов, соответствующих заданным условиям и ряд других. Сложность и чрезвычайная трудоемкость большинства из этих задач требует не только всесторонних теоретических исследований, но и создания специализированных высокопроизводительных дисплейных процессоров /94,99,103,106/.