Основы САПР (CAD,CAM,CAE) - (Кунву Ли)(2004) (951262), страница 101
Текст из файла (страница 101)
Схема вычисления Р» ' (аг(б-О; ]<к: бч ) л[Л Р[1-к+1+)]: (ог(г 1: г<К: г ) ( Гог(З' Д-1: З г: З--) [ 6лиэко аппроксимировать исходную кривузй„"'квк 'и в случае применения алгоритма де Кастильо для аппроксимации кривой Безье. Такая аппроксимация прямолинсйными сегментами может использоваться для вычисления начальных значений точек пересечения между кривыми В-сплайна. Алгоритм Кокса— де Бура может быть реализован на языке С (листинг Ж.
[). Листинг Ж.Х. Реализация алгоритма Кокса — де Бура на языке С Сок бе Волг(Д. г. Р. ц, 1, В) 1пг Кз /+ порядок В-сплайна +/ Клод "с; /" последовательность узлов */ Ро)пс Р; /* задающие точки */ бовь)е ц; /* значение паранетра */ (пс 1: /+ целое числа.
такое. что ср ] <- ц < с[1+ц +/ Розог +а; /* Р(ц) */ [ Рого( зпс боць)е вне'- а+1+а; б[ 'ц,:- С[З]з б2 " 1[(+К-г] - ц; А[б] (б1 * А[З] + б2 * А[)-Ц)/(б1 + б2) ) ) '% д[к-ц; ) , Приложение 3 » рээ 1 уо н» ' »ы» и» » рээ Рис. 3.2. Объединение узловых значений Рис. 3.т. Объединение двух В-сплайнов (3.1) Я , (»=О,...,п); К, „(» = п+ 1, ..., т+ п). (3.3) Объединение В-сплайнов Чтобы получить новые задающие точки и узловые значения объединенной кривой, мы предположим, что объединяемые кривые имеют одинаковый порядок. В противном случае перед тем как выполнить объединение, нам придется изменить ту кривую, у которой порядок меньше, придав ей тот же порядок, что и у другой кривой (то есть мы будем находить узловые точки и узловые значения эквивалентной кривой боле высокого порядка).
Эта процедура описывается в 1381. Обозначим уравнения первого и второго В-сплайна порядка й как Р,(и) и Рэ(и), соответственно. Далее предположим, что Р,(и) определяется задающими точками 0, (»' = О, 1, ..., и) с узловыми значениями р; (» = О, 1, ..., п + 1). Аналогичным образом, Рз(и) определяется задающими точками К; (1 = О, 1, ..., т) с узловыми значениями щ (» = О, 1, ..., и» + й). Обратите внимание, что ()„— это то же самое, что и Кэ (рис. 3.1). Тогда уравнения Р,(и) и Рэ(и) могут быть записаны следующим образом: Р,(п) = ~ (4;К*(и); ~ О Рэ(и)=2 К,И»»(и). (3.2) -о Теперь определим задающие точки и узловые значения объединенной кривой (беэ вывода).
Мы проверим результат, показав, что объединенная кривая в своих соответствующих частях представляет исходные кривые. Во-первых, множество задающих точек объединенной кривой Р; представляет собой простое обьединение множеств задающих точек двух кривых: Обратите'внимание; что Ко не фигурирует. в уравнений (33),.поскольку:это то же самое, что и Я Узловые значения объединенной кривой находятся путем слияния двух наборов -:, узловых значений, после того как вс6 узлы гр; булут сдвинуты так, что газ будет ' . равняться и ь Нам известно, что сдвиг всех узлов на одно и то же расстояние ие ' .
влияет на уравнение кривой, поскольку важность имеет только разность между узловыми значениями. При объединении двух наборов узловых значений не-..'!; которые из ннх, соответствующие точке сопряжения между двумя кривыми, исключаются, так что они будут повторяться только л — 1 раз. Если количество .': повторений больше, чем й — 1, получившаяся объединенная кривая не может',: рассматриваться как один В-сплайн и, таким образом, не удовлетворяет соотно' шению, определяющему число задающих точек, их порядок и количество узле"::.':,' вых значений.
Процесс получения узловых значений для объединенной кривой .' . иллюстрирует рис. 3.2. Узловые значения и; сдвигаются на расстояние (о„,» — в»4), У так что узловое значение го» становится равным р„,н и из попарно равных узл»Р вых значений о„,н ..., р„,» и гон ..., ю», оставляются только (л — 1) узлов от пх,„д»»:"', р„,». Таким образом, узловые значения, которые будут использоваться для обьв.'' '- диненной кривой, находятся, как показано штриховыми прямоугольннкамиз»»~' "-':. рис.
3 2, и могут быть выражены следующим образом: в (»=О,..., и+л = 1); (3.4);; И~,„+ о„,» -и (» = и+ 4, ..., и+ т+ л). Теперь убедимся, что объединенная кривая, которая определяется задающими . '., точками и узловыми значениями, заданными формулами (3.3) н (3.4), совпадает с двумя исходными В-сплайнами в каждой из соответствующих частей.
Рассмотрим часть кривой, соответствующую интервалу»„(= п„) и гни (= о„„= р„,э = ... = = р„„„,). Мы знаем, что Аги(и) — единственная функция сопряжения первого порядка, не убывающая в данном диапазоне а. Распространяя эффект Ж„э(и) (рис. 6.5), мы найдем, что Ф„»,~»(и), М„.
»„а»(и), ..., Ф»(п) яапяюгся ненулевыми функциями сопряжения порядка Й. Таким образом, кривая определяется задающими точками Р, »нь Р„ыъ ..., Р„. Эти задающие точки совпадают с точками Я„» и я„»,ъ ..., Я„. Далее, подмножество узловых значений объединенной кривой, участвующих в вычислении функций сопряжения.
А» .»»ь»(и), А»„»„э»(и), ..., А»„„(и), будет совпадать со значениями, входяшими.в Рт(сч). Из этого мы можем заключить, что обьединенная кривая Р(и) совпадаатс»Рл(п) лля значений и в щ»п»ервале г„и 1„~». К тому же заключению мы пр»»дом В с»'учае, когда и находлтсл меж- $ ейзэевтэз!$фВм~фЯЩВМ1кф" 1 Ф„, (и) Ж„ъ„, (и)1 (И.1) 1 г,. <и <г„, Фы(и) = О во всех остальных случах (И.2) (И.З) ду узловыми знвчейия1эи, 'меньшими Г„. Таким же образом можно показать, что Р(и) совладает с рз(я) ярц ц г„ы.
Пример 3.1 Два непериодических однородных В-сплайна порядка 4, один из которых определен задающими точками Рь Ръ Рэ и Рв а другой — Я, (= Рэ), Я~, Яз и Я4, требуется представить с помощью объединенного В-сплайна Найти узловые значения объединенной кривой. Решение Кривая В-сплайна, определенная точками Рь будет имел узловые значения О О О О 1 1 1 1, а кривая, определенная точками ф, — узловые значения О О О О 1 2 2 2 2. Чтобы сделать первое узловое значение из второго набора равным последнему узловому значению первого набора, узловые значения второго набора сдвигаются на 1, в результате чего получаются значения 1 1 1 1 2 3 3 3 3.
После этого два набора узловых значений обьединяются, и некоторые из узловых значений, равные 1, удаляются, чтобы они фигурировали только три (то есть л — 1) раза. Соответственно, объединенная кривая будет иметь узловые значения О О О О 1 1 1 2 3 3 3 3. Приложение И Доказательство формулы дифференцирования В-сплайна Чтобы доказать чюрмулу (6АЗ), сначала докажем справедливость следующего соотношения: Для доказательства (И.1) мы перепишем уравнения (6.32) и (6.33) более удоб- ным образом: Ж„(и) = ' И„,(и)+ '"' Ж,.„ь,,(и). — гэ. — г.~ Теперь выведем формулу (И.1), рассуждая по индукции. Иными словами, мы покажем, что уравнение (И.1) справедливо при г = л, если установлена его справедливость при г = л — 1.
Мы также покажем, что равенство (И.1) выполняется при г = 2. В таком случае оно должно выполняться н прн г= 3. Повторяя это индуктивное рассуждение с увеличением г, мы можем доказать, что формула (И.1) выполняется для всех г. Первым делом покажем, что равенство (И.1) выполняется при г = 2. Подставляя г = 2 в (И.З), получим Х,,(и) = ' 1ч„(э)+ "' Ф„ы (и). (ИА) Дифференцирование уравнения (И.4) дает Жь, (и) Жэы (э) Х.2 (э) Ггы 1у Гм 2 Гм! что эквивалентно уравнению (И.1) при г= 2. Предполагая, что (И.1) справедливо для г = к — 1, имеем Ж,з,(и) =(л-2) — ' ( Ф,э а(и) Ф„ы,(п)) (И.5) г;ыг ю Теперь с помощью уравнения (И5) нам необходимо показать, что уравнение (И.1) ':,!;: справедливо при г = л.
Подставляя г = э в уравнение (ИВ) и дифференцируя его .";": по и, получим (И.7) Е!,», -и и!.»-2 (и) Е!+»-! Е! ! и — Е; Х...(и) — ' Хм!м»(и) Ее — 2 Е„»- Е!+! Второе слагаемое+ Третье слагаемое = Р,' =(Й-1) Е„», -Е, Е!,» — и Е+! 1Х,»,( ) '1 Е!,» ! — Е; Е„» — Е,»! '1 (» 2 ~ Хс»-!(и) Х»+»м!(и)1 и — Е; ! Е!.» — и Х»„„,(и)+ " Х„,,(и) Ем»-! Ем! Е+» Е+! Х!»(и)= —,' — " + ' Х, ' (и)+ — "Х„ы,(и).
(И.б) Хы, (и') 'Х,.',»з ', (и) и - Е! '.:.,';:-;':: ' Е»„-и Е!*м! Е! Ем» Е!+! «ь м Возьмем выражения Х;»,(и) и Х!„,,(и) из уравнения (И.5) и подставим их в уравнение (И.б): Х„, (и) Х„„, (и)1 Е!.„— Е!„) й-г ~ и-г, и — Е; + ~ ' Хсм»(и)- ' Х»„» т(и) + я -2 ! Е!,„-и Е+» и! Е!»» Е! 2 Теперь перепишем второе слагаемое, прибавив и вычтя член и затем применив формулу (И.З): 7» — 2 Г и — Е; Второе слагаемое = ~ Х,м»(и)+ Х смт(и) »-! Е! Ею+»-2 ! Е!+»- Ем! Е» — 2 Ее -2 Х, (и) — Х»и (и). Е! Е! Е »-! Е! ! Изменим порядок суммирования во втором и треп ем слагаемом формулы (И.7): А — 2 ~ Е»-и Х!, (и)+ "" Х„„»(и)— Ем» Ем! Еи»-! Е„» — Е!,! Х!...,(и)- " " Х„„,,(и) = Е!+»-! Ем! Наконец, добавив этот результат к первому слагаемому в формуле (И.7), полу- чим: (Первое слагаеь»ое) '+(Второе слшт»емое+ Третье Елагаемое) ~ =(1 ' '(и) "'"-'(и) (й г Е!»»-! — Е! Ем» -Е+! Е!.»-! Е Е!*» — Е»м ~Х»» !(и) Х»„»,(и) =( 1)' '- Ем» Е! ! Результат идентичен формуле (И.1).
Теперь докажем формулу (6АЗ) с помощью формулы (И.1). Перепишем произ' водную первого порядка от кривой В-сплайна при условии, что значение парь, метра и находится в интервале Е, и Е»„, следующим образом: »ЕР(и) -». =~Р!Х! (и) = 'Я,,Р!Х, (и). Ии !.о ' ' !.»-м!' Из формулы (И.1) получаем: ! (И18) — (-) - ХР(-) У ! Обратите внимание, что мы сократили диапазон суммирования в формуле (И 8)„', ' ' .
зная, что Х! м !~м !(и) = О и Х»„,»,(и) = 0 при Е, и Е»,!. Замена (! + 1) на 7' во втором слагаемом формулы (И.8) даст Р.(Е»-1) '»' — ~Р.,(Й вЂ” 1) ,Еи,„м» ' Е!,»,-Е», !м,' ' Е,„,-Е, Р! -Р», ~ (Е» 1) ' '-'Хс»!(и)= ,'ЕР,'Х!м,(и) ;»», » Е>!! Е, !!-м2 Таким образом, мы имеем »ЕР(и) — ~Р!'Х!м!(и), Е!и !-»-мг Приложение К Р! РЗ РЗ Р4 СП О2 К.1. Разбиение Р! Р2 РЗ Р4 О11 О12 О!3 О14 6 РЗ вЂ” О!1 РЗ - О12 Р4 — О1 в Подход Пенга к вычислению пересечения ЙУКВБ-поверхностей В этом приложении дается пошаговое описание подхода Пенга Как объяснялось ранее, для каждой из пересекающихся поверхностей необходимо создать непрерывное разбиение, которое затем нужно сохранить в виде квадрантнаго дерева Поскольку рациональные (нерациональные) поверхности Безье' разбивать проще, чем рациональные (нерациональные) поверхности В-сплайнов, мы преобразуем каждую М)КВЗ-поверхность в множество рациональных лоскутов Безье (рис.
К.1). Рис. Кдц Преобразование МйяББ-лааерхиости а рациональные лоскуты Безье После того как это будет проделано, пары рациональных лоскутов Безье, которые могут пересекаться, сохраняются в списке, называемом стлтском соперников (г!гтт1 Ы). Например, на рис. К2 показано преобразование 1ч'()КВЗ-поверхностей 31 и З2 (рис. К.2, а) в четыре рациональных лоскута Безье Р1, Р2, РЗ и Р4 и два рациональных лоскута Безье О1 и О2 соответственно. Эти рациональные лоскуты Безье сохраняются в каадрантных деревьях (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
