1. Введение
Интерес к синтезу изображений объясняется высокой информативностью
Ж'; последних. Информация, содержащаяся в изображении, представлена в
наиболее концентрированной форме, и эта информация, как правило, более
доступна для анализа: для ее восприятия получателю достаточно иметь
относительно небольшой объем специальных знаний.
Разработка машинно-ориентированных методов решения геометрических задач в настоящее время мыслится как синтез методов аналитической и дифференциальной геометрии, машинного моделирования, графических методов аппроксимации, интерполирования и оптимизации, различных итерационных методов и др., о чем говорится в [47].
Необходимо отметить высокий уровень развития компьютерной графики в ряде областей, а также новые тенденции.
1.1. Обзор методов построения основных геометрических объектов
В настоящее время успешно решена задача построения основных графических примитивов, простых трехмерных фигур и ряда поверхностей, что рассмотрено, например, в работе [53].
Существуют различные методы описания кривых и поверхностей, реализуемые как при помощи уравнений явного вида, так и неявного вида. Среди них параметрический метод имеет определенные преимущества перед другими, в особенности, когда нужно получить графическое изображение на дисплее или управляющие ленты для металлорежущего станка.
Если кривая или поверхность определена уравнением явного вида, то для получения ее графического изображения вычисляются последовательно
-4-
координаты точек, отвечающие определенным значениям параметра. С другой стороны, если кривая определена уравнением неявного вида, приходится решать нелинейное уравнение для каждой точки. Также, применение параметрических методов в значительной мере упрощает вычисление кривых, связанных со смещением режущего инструмента и других подобных кривых в задачах числового управления. В пользу этого метода говорит тот факт, что при его применении перенос или вращение осей координат или предмета не требует модификации функций от используемых предметов, а осуществляется, как правило, при помощи переноса или вращения векторов, определяющих заданную кривую.
И, наконец, параметрические методы пригодны для кусочно-гладкого описания кривых и поверхностей, как, например, в разработанной Безье системе проектирования UNISURF.
Параметрическое описание кривых в координатной форме имеет следующий вид:
А уравнение г - r(u,v) определяет поверхность в трехмерном
пространстве, координаты точек которой определяются функциями х = x(u,v);y = y{u,v);z = z{u,v)
Представляя кривые таким образом, мы получаем возможность дать простое математическое описание закрученных кривых в трехмерном пространстве; прежде такие кривые определялись с помощью своих проекции на две взаимно перпендикулярные координатные плоскости. Во-вторых, представление кривых в параметрических координатах дает возможность избежать определённых проблем, которые могут возникнуть, когда замкнутые кривые и кривые с вертикальными касательными представляются в некоторой фиксированной системе координат. И, наконец, что, пожалуй, наиболее важно, такое представление позволяет очень просто осуществлять такие
т
-5-
преобразования координат, как перенос и вращение. Другими словами, параметрический способ задания кривых освобождает от привязки к какой-либо определённой системе координат.
Одновременно с разработкой систем, основанных на параметрическом методе, появились автоматические чертежные устройства, графические дисплеи и станки с цифровым управлением. Параметрический способ задания кривых и поверхностей оказался исключительно удобным для применения этих новшеств. При эксплуатации графических дисплеев необходимо обеспечить преобразование координат,, определение проекций, различного рода трехмерных изображений и т.д.; все эти операции наиболее просто осуществляются при параметрическом представлении кривых и поверхностей. Дисплеи позволяют получать на экране графическое изображение, показывающее, как математически описанный трехмерный объект будет выглядеть, если его рассматривать из любой интересующей нас точки пространства.
Существуют основные уравнения дифференциальной геометрии для пространственных кривых, которые в совокупности известны как формулы Френе - Серре.
dr _
— = Т, - касательная к кривой
ds
— = jiv, - главная нормаль и бинормаль к кривой ds
dN
----= тВ- хТ, - кручение кривой
ds
dB A! ' "
— = -tN, - кручение кривой ds
Кроме параметрических существуют неявные уравнения для поверхностей и кривых в трехмерном пространстве
Квадратичное уравнение общего вида
m
»
ах2 + by2 +cz2 + 2hxy + Igzx + 2fyz 4- 2ux + 2vy + 2wz + d = 0 представляет поверхности второго порядка общего вида, к которым
относятся сферы, цилиндры, конусы, эллипсоиды, параболоиды и гиперболоиды. Для однозначного представления любой поверхности второго порядка уравнением неявного вида в каждом отдельном случае это уравнение должно быть определенным образом пронормировано..
•щ Хотя в последнее время в язык APT, предназначенный для
программирования станков с ЧПУ, были введены средства параметрического определения поверхностей, применение языка APT базируется на неявных уравнениях классических поверхностей, таких как плоскости, поверхности и сферы. Несмотря на большое разнообразие способов образования поверхностей, кодирование последних в памяти ПЭВМ осуществляется при помощи сравнительно небольшого набора канонических типов поверхностей. Перечислим эти канонические типы поверхностей.
1. Плоскость Ах + By + Cz-D-Q кодируется коэффициентами (A,B,C,D),
где А2+В2+С2=1. Прямая в двухмерном пространстве кодируется как плоскость при С=0.
2. Сфера (х-Х)2 +{y-Y)2 +(z-Zf = R2 кодируются набором чисел (X,Y,Z,R).
3. Круговой цилиндр
{х-Х)2 +{y-Y)2 +(z-Zf -[A(x-X)+ B{y-Y)+C{z-Z)]2 = R2, где (X,Y,Z) -W произвольная точка на центральной оси, а (А,В,С) - единичный
вектор, направленный вдоль этой оси, кодируются набором (X,Y,Z,A,B,C,R). Окружность в двухмерном пространстве кодируется как цилиндр, в котором А=В=0, С=1.
4. Круговой конус
[A{x-X)+B{y-Y) + C(z-Z)]2 =l(x-X)2 +{y-Y)2 +{z-Z)2\cos2©c вершиной (X,Y,Z), полу углом при вершине 0 и осью, направление которой
-7-
определяется единичным вектором (А,В,С), кодируются набором чисел (X,Y,Z,A,B,C,cos0).
5. Поверхность второго порядка
Ах2 + By2 +Cz2 +D + 2Fyz + 2Gxy + 2Px + 2Qy + 2Rz = О кодируются набором (A,B,C,D,F,G,H,P,Q,R). Любое плоское коническое сечение
кодируется как поверхность второго порядка, в которой G=F=G=R=0, иными словами трактуется как цилиндр.
6. Табулируемый цилиндр (TABCYL) - это цилиндр, образующие которого проходят через точки кусочно-кубической кривой, определяемой множеством заданных точек.
Таким образом, как отмечено в [32],: «в настоящее время на практике широко применяются различные методы интерполяции, аппроксимации и сглаживания. Из всех существующих способов аналитического описания обводов наибольшее распространение получили кубические и бикубические уравнения, представленные в параметрической форме Фергюссона, Безье и других. Такие способы описания кривых обладают определенными конструктивными достоинствами, например, легко, достигается плавность вычисленной кривой, существенно повышается эффективность взаимодействия человека и ЭВМ. и т.п.». Эти методы хорошо изучены и с успехом используются.
1.2. Обзор методов построения составных поверхностей
Отметим также достижения в решении задач построения составных поверхностей. Некоторые из них рассмотрены в работе [53].
Одним из первых методов, основанных на разбиении проектируемой поверхности на порции, принадлежит Фергюсону, причем этот метод отличается от традиционных еще и тем, что кривые и поверхности в этой
процедуре определяются с помощью параметрического представления, а не в декартовых координатах.
При построении кривых и поверхностей параметрические уравнения имеют определенные преимущества. Поскольку объекты имеют, как правило, сложную форму, не допускающую описания при помощи простых аналитических функций, мы вынуждены определять кривые и поверхности по частям.
Поскольку приходится вычислять касательные, нормали, кривизны и т.д., нужна такая параметризация, для которой легко производится операция дифференцирования. Очень удобны для этой цели полиномы от некоторого количества параметров, но такие полиномы требуют большого числа коэффициентов, физический смысл которых трудно понять. Более того, применение полиномов высокой степени может вызвать нежелательные колебания кривой. Кубические уравнения оказались удачным компромиссом для многих приложений, и большинство методов проектирования и подгонки основано на использовании параметризации с помощью кубических функций.
Например, уравнение порции кубической поверхности в форме Фергюсона.
\/
«00 «01 «02 «03 1
«10 «11 «12 «13 V
«20 «21 «22 «23 v2
^«30 «31 «32 «33 v3
Ряд методов определения поверхности основаны на системе построения двух пересекающихся семейств кривых. Куне предложил чрезвычайно общую теорию построения порций поверхности. Он показал, как соединить четыре произвольные граничные кривые единой гладкой порцией поверхности и обеспечить непрерывность градиентов и кривизны между двумя порциями поверхности.
-9-
r(O,v)
Задача определения порции поверхности сводится к нахождению функции r(w,v) с подходящим типом «хорошего поведения», которая при н=0, и-\, v=0 или v=l представляет нужную граничную кривую.
A, 00
A 00
-[«o("W")A> (")
7(0,0) r(0,l) гДО.0) rw(O,l)
/¦(1,0) r(l,l) r,(l,0) r,(l,l)
г„(0,0) ги(0,1) re,(0,0) гви(0Д)
я0О)
Л 00 A 00
(1)
_rB(l,O) г„(1Д) гЯУ(1,0) г
Можно значительно упростить уравнение порции поверхности по Кунсу (1) подходящим определением граничных кривых и градиентов в ортогональных к ним направлениях. Используя функции смешения, можно представить сегмент кривой с помощью положений его концевых точек и значений касательных в них векторов г, ru, rv, ruv в ее четырех углах.
r(u,v) = [а0(и) а, (и) J3O(и) /7, («)]х
Или, более сжато,
7(0,0) г (ОД) г„ (0,0) г,(0Д)"
г(1,0) г (1,1) rv(l,0) гД1Д)
г„(0,0) г„(0,1) ruv(0,0) С (ОД)
г„(1,0) г„(1,1) ги,(1,0) гву(1,1)
Порциьо поверхности этого типа часто называют определенной тензорным (или декартовым) произведением
- 10-
Как было отмечено, декартовые координаты имеют недостатки по сравнению с параметрическим подходом к проектированию кривых и поверхностей. Однако непараметрические методы могут быть эффективно использованы при определении однозначных поверхностей, не имеющих больших градиентов по отношению к некоторой базовой плоскости. Там, где эти методы применимы, они предпочтительней параметрических методов в смысле объема вычислений.
Простейший алгоритм построения поверхности в декартовых координатах подгоняет полиномы от скалярных величин хиу вида
/«0
к значениям z, заданным в узлах фиксированной прямоугольной сетки на плоскости (х,у), что показано на Рис. 1. Шаг сетки может быть переменным.
Y
Рис. 1 Определение поверхности на фиксированной прямоугольной сетке
Если мы согласны взять р и q достаточно большими, можно применить обобщение метода Лагранжа для нахождения единственного полинома, который будет интерполировать все заданные точки. Но построенной таким
11
образом поверхности свойственны нежелательные осцилляции, которые часто появляются при использовании метода Лагранжа для подгонки большого числа точек. Поэтому большинство практических систем применяют один полином низкой степени от х и у для каждой отдельной ячейки сетки и используют условие непрерывности градиента поперек границ порций, соответствующих этим ячейкам, чтобы синтезировать гладкую составную поверхность.
Метод R-фунщий академика РвачеваВ.Л. описан в его работе [45]. Было замечено, что среди функций непрерывных аргументов существуют функции, которые по ряду свойств напоминают функции алгебры-логики.
Функции, обладающие в определенном смысле «логическим зарядом», из которых составлены множества, названы R-функциями. В зависимости от числа множеств, покрывающих цифровую ось, получаем множества R-функций, соответствующие функциям двухзначной, трехзначной, четырехзначной и т.д. логики.
Пусть Y=F(xi, xn) есть функция непрерывных аргументов хь хп (0 < п < 8), определенных в области D. Если значения, которые может принимать функция в области D принадлежат множеству В={0, к-1}, то функцию Y=F(xb xn) будем называть k-значным предикатом, определенным в области D.
Построение сложных геометрических объектов с помощью более простых обычно осуществляется по некоторым логическим правилам, которые поддаются формализации на основе использования функций логики.
Рассмотрим изображение, показанное на Рис. 2
12
F2
F3
Рис. 2 Составной геометрический объект
Его предикатное описание будет иметь вид:
F1 - круг радиуса 2 с центром в точке 0; F2 - области, ограниченные прямой х = ±1; F3 - полуплоскость ниже прямой у =1
Переход от предикатного описания к аналитическому будет осуществляться путем некоторой формальной процедуры, состоящей в замене символов предикатных уравнений символами некоторых реализуемых функций.
Так как
Fl=(4-x2-y2 >0); F2 = (x2-1 >0); F3 = (l-
то аналитическое описание будет иметь вид:
<*
13
Таким образом, ГО, описанный методом R-функций, будет представлять собой функцию, имеющую вид единого аналитического выражения, построенного с помощью заданной базисной системы функций.
В данной диссертационной работе продолжены исследования в области методов построения и использования составных поверхностей.
Разработка методов описания различных видов поверхностей для изображения объектов в графических системах, диктуется потребностями практики; их применяют при создании приложений в области конструкторских разработок, в области дизайна, на железнодорожном транспорте, в авиационно-космической промышленности, на производстве, в системах автоматизированного проектирования (САПР), в геоинформационных системах (ГИС) и т.д.
Широкое применение кусочных методов формирования криволинейных обводов в твердотельном моделировании объектов технологически сложных отраслей промышленности (авиационной, судостроении, автомобилестроении и др.) объясняется целым рядом их замечательных особенностей, отмеченных в [12].
Во первых, сконструированные кривые и поверхности практически всегда удовлетворяют свойствам действительно 3-х мерного объекта, например проходят через заданные точки, имеют заданные наклоны и др.. Кусочные функции, описывающие эти кривые и поверхности, как правило, многократно диффиренцируемы и их производные удовлетворяют критериям непрерывности.
Во вторых, процесс конструирования криволинейных обводов может быть интерактивным и выполняться итерационно. Геометрическую модель, полученную на некотором шаге итерации, модифицируют до достижения желаемой формы.
В третьих, полученные геометрические модели трехмерных объектов возможно использовать не только для их визуализации и последующей оценки свойств формы, но и для разработки технологического процесса изготовления и др.. Форма технического объекта в первую очередь обусловлена его функциональным назначением, кроме этого в ряде случаев она должна удовлетворять и эстетически требованиям. Например, в авиастроении критерием выбора параметров внешнего обвода являются его геометрические характеристики. В судостроении при моделировании обводов судна, гребного винта таким критерием являются гидродинамические характеристики. В автомобилестроении - аэродинамические и эстетические характеристики.
1.3. Развитие вычислительной техники и новые задачи
Необходимо отметить и другие тенденции.
Во многих работах отмечается значительное возрастание возможностей вычислительной техники (ВТ), и открывающиеся вследствие этого перспективы. Например, в [33] утверждается: «Возможности ВТ в частности — за счет нового уровня визуализации результатов компьютерного моделирования, делает в настоящее время актуальной постановку дальнейших исследований в области синтеза кривых или поверхностей различных геометрических форм с целью получения широкого класса новых линий и поверхностей».
В то же время этап взрывного развития переживают системы, основанные на глобальной компьютерной сети Internet и крупных корпоративных компьютерных сетях intranet. Нельзя не заметить повышенный интерес к интеграции информационных ресурсов, т.е. к объединению различных методов и технологий в единый комплекс (о чем сказано, например, в [57]), что привело, соответственно, к созданию интегрированных систем. Такой интерес обусловлен возросшей сложностью информационных моделей, необходимостью обрабатывать большие объемы разнородной информации.
15
Особый интерес представляет новый тип интегрированных систем — геоинформационные системы (ГИС) [57]. Важнейшей частью ГИС является графика, но существующие графические технологии направлены на решение частных задач в определенных, довольно специализированных областях. Если рассматривать применение графики в ГИС, то из обзора [41] вытекает, что в этой области наиболее изучены следующие направления:
• картография, хранение карт, привязка пространственных изображений к картам;
• векторизация растровых снимков поверхности Земли, полученных со спутника;
• различного рода анализ изображений, распознавание образов;
• восстановление трехмерных сцен по серии снимков;
• трехмерное зрение, выделение контуров тела.
В данной работе проводятся исследования, направленные на принятие решений, позволяющих осуществить приведение графики к требованиям интеграции. Разрабатываются способы работы со сложными составными графическими объектами в интегрированных системах, построенных на основе и компьютерных сетей.
1.4. Анализ исследований в данной области
Краткий обзор наиболее приоритетных исследований и методов построения составных кусочных поверхностей свидетельствует о том, что работы в области прикладной геометрии поверхностей и вычислительной геометрии подняли на новый качественный уровень именно конструктивно-аналитическое направление исследуемого вопроса, что видно по работам [1], [28], [23], [45], [15], [49], [44], [60], [39], [32], [47], [12]. Однако, как сказано в [32], универсального метода, пригодного для визуализации в сетевой среде, не существует. Из анализа существующих методов конструирования
* 16
геометрических форм и особенностей прикладных задач вытекают следующие выводы:
• существующие конструктивные методы геометрического моделирования имеют определенную область применения, у некоторых эта область обширна, у некоторых - узка, уровень привлечения современных достижений математических и смежных технических
^ наук для комплексного решения задач проектирования и технологии
еще не достиг своего завершающего этапа [32];.
• существует потребность использования сразу нескольких методов построения геометрического объекта (ГО), т.к. каждый метод, решая определенную задачу, не может удовлетворять всем требованиям. Например, как отмечается в [32],: «методы интерполяции на основе кусочно-полиноминальных или В-сплайнов (См. [2], [11]) дают
__ достаточно точные результаты при проектировании одномерных
обводов, но, к сожалению, при конструировании двумерных обводов добиться такого эффекта не просто из-за сегментации задачи, что в конечном счете приводит к увеличению объема вычислений и памяти ЭВМ»;
• имеет место локальный подход к созданию графических систем. Наибольшие успехи достигнуты в автоматизации проектирования отдельных задач. Однако такой подход затрудняет разработку
^ интегрированных систем;
• графические системы, используемые в настоящее время, в большинстве не ориентированы на использование в компьютерных сетях. Они, если и допускают функционирование в сетевом режиме, то все равно не используют эффективно ресурсы, возможности сетей;
• недостаточная гибкость систем. Например, существующие САПР, как правило, позволяют получать приемлемые проектные решения, не |
