54
ALGORITEM ZA DOLOČITEV POVEZOVALNIH FUNKCIJ	INFORMATICA 3/91
KRIVULJ B-ZLEPKOV IN NURB KRIVULJ V POLINOMSKEM ČASU
Keywords: B-spline curves, NURB curves, blending functions,	Borut Žalik, Nikola Guid,
de Boor algorithm, time complexity, computer graphics	Andrej Tibaut in Aleksander Vesel
Tehniška fakulteta Maribor
Povzetek: Povezovalne funkcije krivulj B-zlepkov in NURB krivulj so definirane z rekurzivno formulo, čigar direktna vgradnja v algoritem pripelje do eksponentne časovne zahtevnosti izračunavanja povezovalnih funkcij glede na njihov red. S pravilno pripravo podatkovnih struktur in upoštevanjem lastnosti povezovalnih funkcij lahko sestavimo algoritem, ki izračuna povezovalne funkcije in nariše krivuljo v polinomskem času. Izdelan algoritem smo primerjali glede na porabljen čas CPU z iterativnim de Boorovim algoritmom, s katerim določimo točke na krivulji brez izračunavanja povezovalnih funkcij. Ugotovimo, da je naš algoritem učinkovitejši celo od de Boorovega algoritma v primeru periodičnih in neperiodičnih krivulj B-zlepkov, v primeru NURB krivulj pa je slabši.
An algorithm for B-spline and NURB blending functions determination in a polynomial time. B-spline and NURB blending functions are defined by recursive formula. Its direct implementation into a program lead us to the exponential time complexity regarding to the degree of blending functions. With paying attention to a correct data structure we have been able to construct an algorithm which evaluates the blending functions and plots the curve in a polynomial time. This algorithm has been compared with iterative de Boor algorithm which determines the points on a curve without blending function calculation. The values of the CPU time spend on curve generation show, that our algorithm is better in the case of periodical and nonperiodical B-spline curves, and in the case of NURB curves it is worse than de Boor algorithm.
1. UVOD
2. DEFINICIJA KRIVULJ B-ZLEPKOV
Pri realizaciji algoritmov za izračun in izris krivulj B-zlepkov se srečamo s problemom izračunavanja povezovalnih ali baznih funkcij. Za hiter izris krivulj B-zlepkov in NURB krivulj sicer obstaja iterativni de Boorov algoritem, kjer povezovalnih funkcij sploh ni potrebno izračunavati, vendar je mnogokrat zelo ugodno, če lahko prikažemo tudi povezovalne funkcije, predvsem zaradi učenja in raziskovanja. Seveda je najugodneje, če so povezovalne funkcije izračunane analitično in zakodirane v algoritmu (bazne funkcije so polinomi ustreznega reda). Periodične bazne funkcije nižjih redov (2 ali 3) lahko hitro izpeljemo, najdemo pa jih tudi v literaturi. V primeru uporabe neperiodičnih baznih funkcij moramo vložiti že več napora, da izpeljemo vse potrebne povezovalne funkcije. Le-te že redkeje najdemo (npr. v ITURK80) in |YAMA88I). Določitev koeficientov povezovalnih funkcij višjih redov pa zahteva precej truda.
Definicijo in lastnosti krivulj B-zlepkov najdemo na mnogih mestih v literaturi (1B0HM841, [MORT85I, IBART871, [GUID88], [PIEC87], (YAMA881). V nadaljevanju bomo uporabljali oznake in zaključke iz vira IGUID90). Krivulja B-zlepkov je definirana kot:
p(u) = T r N (u) '-i i , k
(1)
kjer so r kontrolne točke in N bazne ali povezovalne i i , k
funkcije reda k, ki so definirane z rekurzivno formulo:
N (u) = i , o
1, u £ u < u 1	I
O, sicer
(u - u ) N (u) (u - u) N	(u)
N (u) =---LJili-+ _ÍÜÜÍ-(2)
i , k
U - U iti	I
fl a'*"!
55
A4. j
O.O 1.0 2.0 3.0 4.0 5.0 6.0 7,0 0.Q
O)
1 .O	2 .O
3.0	4.0	S.O	6.0
"J
Slika 1 Kubične bazne funkcije,
a)	U = [0, 1, 2, 3, 4,
knot
b)	U = 10, O, O, O, 1,
knot
Množico u shranimo v vozliščni vektor U =
J	kno t
..., u ]. Obravnavali bomo dve obliki vozliščnega vektorja:
a) Vozliščni vektor, ki določa nesklenjene periodične
krivulje B-zlepkov. Za nas so zanimivi le tisti odseki, kjer
sodeluje k+1 povezovalnih funkcij, saj je krivulja
B-zlepkov definirana v intervalu u e [u + k, u - ki. K	o	m
Definiran je kot [GUID901:
U = [u , u , u ..... u ] = [O, 1, 2..... ml
knot 0 12	m
ki jih določa vozliščni vektor 5, 6, 7, 8]
2, 3, 4, 5, 6, 6, 6, 6]
b) Vozliščni vektor, ki določa neperiodične krivulje B-zlepkov. Definiran je kot [GU1D901: U = [u , u , u ..... u ] .
kno t 0 12	m
u = O; l
če i s k
u = i - k; če k+1 s i s m - k - 1
i
u =m-2k; če m - k s i s m i
kjer je m definiran z enačbo 3. Bazne funkcije za n = 3 nam kaže slika lb.
in k
m je določen s formulo:
m = n + k + 1 kjer je:
n: število kontrolnih točk minus 1 k: red povezovalnih funkcij.
Bazne funkcije za n = 4 in k.= 3 nam kaže slika la.
(3)
3. PRIPRAVA PODATKOVNE STRUKTURE ZA DOLOČITEV POVEZOVALNIH FUNKCIJ
Potek izračunavanja povezovalnih funkcij z algoritmom, ki
neposredno rešuje enačbo 2, nam kaže slika 2. Rekurzivni
klici nam ustvarijo polno dvojiško drevo. Število vozlišč v.
takem drevesu je določeno z enačbo k
L 2'
(4)
N,-3 N^.,	N,£k_3 NitLk_3 N,2,_3	N„3,k.
level O
k-1
NNNNNNN N
1.0	\-1.0 1.1,0	¡-2.0 !*l.c -Sfi 1 ite.O 1 i*3,0
N N N N k
1 Vk-2,a 1 Vk-m 1 Vk-1.0 1 i+k,0
Slika 2 Drevo rekurzivnih klicev funkcije N
56
level O
k-1,0
Slika 3 Modificirana struktura za izračun funkcije N
k-l
I ,k
2 vrednosti povezovalnih funkcij na globini k določimo brez
k
računanja (enačba 2), vse preostale 2 - 1 vrednosti povezovalnih funkcij pa moramo izračunati, kar vodi k eksponencialni časovni zahtevnosti
Ttk) = 2k - 1 = 0(2k).
15)
Če pa boljše pogledamo sliko 2, vidimo, da se nekatere povezovalne funkcije, shranjene v vozliščih drevesa, ponavljajo. Z združevanjem vozlišč, ki hranijo iste povezovalne funkcije, dobimo novo strukturo, ki jo vidimo na sliki 3. Število vozlišč v taki strukturi je določeno z enačbo
£ (i + i)
1-0
(k + 3k + 2).
(6)
TreePointer = "TreeType; TreeType = record
Ni: integer;	{indeks povezovalne funkcije)
LeftValue,	{spodnja meja določena z Uknot)
RightValue,	{zgornja meja določena z Uknot)
LDenominator,	{imenovalec levega izraza)
RDenominator,	{imenovalec desnega izraza)
Nu: real; {vrednost povezovalne funkcije pri izbranem u) PerrnanentLL, {zastavica na globini 0; če TRUE,potem Nu=0) Permanent: Boolean; {če TRUE, izračun Nu ni potreben) Lson, Rson,	{kazalca na zapise višje v strukturi)
list: TreePointer;	{kazalec na naslednji seznam)
end; {record TreeType>
LevelConnType = "ListOfPointers; ListOfPointers = record
ToLevel: TreePointer;	{kazalec na seznam TreePointer)
Nk: Integer;	{stopnja povezovalne funkcije)
NextLevel: LevelConnType; {kazalec na naslednji zapis) end; {record ListOfPointers)
Slika 4 nam kaže uporabljeno podatkovno strukturo.
Tudi tokrat k + 1 začetnih vrednosti povezovalnih funkcij na globini k določimo brez računanja, tako da nam ostane le ^ k(k + 1) izračunov, ki pa jih lahko opravimo v polinomskem času:
T(k) = i k(k+l) = 0(k2)	(7)
Da bi lahko določili vrednost povezovalne funkcije glede na izbiro parametra u v polinomskem času, moramo pripraviti ustrezno podatkovno strukturo. Funkcijo na globini j (0 s j < k) izračunamo s pomočjo dveh funkcij iz globine j+1. Ugodno bi bilo našo shemo s slike 3 obrniti tako, da bodo prej dostopna vozlišča z večjo globino. Podatkovno strukturo tvorimo kot seznam enosmerno povezanih seznamov, kjer imamo na vrhu k+1 vozlišč s povezovalnimi funkcijami reda 0 in na dnu samo eno vozlišče reda k. Strukturo deklariramo na naslednji način:
Slika 4 Podatkovna struktura za izračun povezovalnih funkcij v polinomskem času
Inicializacija podatkovne strukture
S tako pripravljeno podatkovno strukturo, ki jo vidimo na sliki 4, lahko izračunamo poljubno povezovalno funkcijo glede na postavljeni vozliščni vektor, le prave podatke moramo vpisati v posamezne zapise. Podatkovno strukturo začnemo polniti pri zapisih, ki hranijo povezovalne funkcije stopnje 0 in so na vrhu seznama seznamov. Najprej za vsako povezovalno funkcijo na globini 0 preverimo mejni vrednosti iz vozliščnega vektorja in s tem določimo interval, v katerem je posamezna povezovalna funkcija definirana. Če sta obe vrednosti enaki, postavimo zastavico PerrnanentLL na TRUE, vrednost povezovalne funkcije shranjene v komponenti Nu pa je 0. V primeru, ko se vrednosti LeftValue in
57
T: LevelConnType
Slika 4 Podatkovna struktura za izi
RightValue razlikujeta, postavimo zastavico PermanentLL v FALSE, Nu dobi vrednost 1, vrednosti iz vozliščnega vektorja vpišemo v LeftValue ter RightValue in določimo konstanti v imenovalcih, ki ju shranimo v komponenti zapisa LDenominator in RDenominator. Nato napolnimo še , preostale zapise v podatkovni strukturi s slike 4 tako, da se spuščamo po seznamu tipa LevelConnType. Če imata oba zapisa na višjem nivoju v podatkovni strukturi zastavico PermanentLL TRUE, dobi tudi zastavica pravkar obravnavanega zapisa vrednost TRUE, Nu pa vrednost 0, sicer pa postavimo zastavico PermanentLL v FALSE. V tem primeru določimo interval, v katerem ta povezovalna funkcija deluje, kot unijo dveh sosednjih intervalov z nižjega nivoja dostopnih preko kazalcev Lson in Rson, nato pa z njihovo pomočjo določimo še imenovalca.
Določitev vrednosti povezovalne funkcije pri izbranem parametru
Pri izbrani vrednosti parametra u v večini primerov sodeluje pri izračunu funkcije N^ manjše število povezovalnih funkcij, kot smo jih označili z zastavico PermanentLL. Tako npr. na globini 0 sodeluje kvečjemu le ena povezovalna funkcija, ki ima po enačbi 2 vrednost 1. Zato v vsakem zapisu tipa TreeType uvedemo še zastavico Permanent, ki ima vrednost TRUE pri vseh funkcijah N , kjer velja u g (LeftValue, RightValue). Seveda dobi zastavica Permanent takoj vrednost TRUE, če ima takšno vrednost tudi PermanentLL. Zastavice na globinah večjih kot 0 določimo v primeru, ko ima zastavica PermanentLL vrednost FALSE, z naslednjim logičnim izrazom
povezovalnih funkcij v polinomskem času
Permanet := Lson";Permanent and Rson".Permanent.
Postavitev zastavic spremenimo, ko tekoči parameter u spremeni interval v vozliščnem vektorju U^ . Izračun vrednosti povezovalnih funkcij pri parametru u sedaj opravimo tako, da od globine 1 do k izračunamo le povezovalne funkcije v tistih zapisih, ki imajo postavljeno zastavico Permanent na vrednost FALSE.
Na sliki 5 vidimo primer, ko želimo izračunati neperiodično povezovalno funkcijo N s slike lb. Če je ue[0,l), moramo opraviti 5 izračunov (vrednost funkcije reda 0 je določena že vnaprej in je ne upoštevamo). Potek izračuna vidimo na sliki 5, če sledimo puščicam. Vrednost zastavice PermanentLL smo označili z velikima črkama T in F, vrednost zastavice Permanent pa z malima črkama t in f. Če je ue[l,2), bi morali opraviti le tri izračune. Na sliki 6 vidimo algoritem, ki uporablja opisano podatkovno strukturo, za izračun vrednosti povezovalne funkcije.
4. PRIPRAVA PODATKOVNE STRUKTURE IN ALGORITEM ZA IZRIS KRIVULJ B-ZLEPKOV
Priprava podatkovne strukture
Vsako povezovalno funkcijo bomo izračunali v diskretnih točkah. Naj bo na intervalu [u ,	) dovolj NoOfSteps
izračunov. Ker se vsaka povezovalna funkcija razteza največ na k+1 intervalih (slika la in lb), bo za posamezno povezovalno funkcijo potrebnih največ (k+1) * NoOfSteps izračunov [ŽALI901. Za vsako bazno funkcijo si shranimo še dejansko število izračunanih vrednosti. Vse podatke shranimo v zapis BfType.
58
utO.&J	ufC.O)	Wto.l)

Slika 5 Potek izračuna povezovalne funkcije ^
BfType = record
Bf: array (O..UValuesMaxl of real; NoOfUvalues: integer;
end
UValuesMax £ (k+1) * NoOfSteps
Da bi lahko direktno uporabili enačbo 1 za določitev krivulj B-zlepkov, bomo vse funkcije N^ ^ predstavili kot kazalce na zapise tipa BfType in jih shranili v polje tipa AllBFunctionType:
AllBfunctionType = array [O..NoOfBfl of "BfType.
Izračun in izris periodičnih krivulj B-zlepkov
Potrebujemo n+1 enakih periodičnih povezovalnih funkcij, ki so med seboj le premaknjene (slika la). Zato je dovolj, če izračunamo le eno povezovalno funkcijo in zanjo rezerviramo prostor, za vse ostale n bazne funkcije pa postavimo le kazalce na zapis tipa BfType. Potrebno podatkovno strukturo vidimo na sliki 7a.
Časovna in prostorska zahtevnost določitve povezovalnih funkcij sta neodvisni od števila kontrolnih točk, tako da lahko zapišemo: T(n) = 1
• S(n) = 1	(8)
Funkcijo za izračun baznih funkcij pokličemo le ((k+l)NoOfSteps) - krat.
function ModifiedNfit: LevelConnType; u: real): real;
{ Funkcija izračuna vrednost povezovalne funkcije krivulje B-zlepkov.
-	t: kazalec na podatkovno strukturo,
-	u: vrednost parametra, pri kateri bomo izračunali
povezovalno funkcijo >
var
bufferNu: real; q: TreePointer;
begin (* ModifiedNF *) t := t". NextLevel; while t o nil do begin
q := t'.ToLevel; while q o nil do with q" do begin
if not permanet then Nu .= LeftDenominator • (u - LeftValue) * Lson'.Nu + RightDenominator * (RightValue - u)* Rson".Nu;
end;
BufferNu := Nu;
q := q". list;
end;
t := t".NextLevel; end;
ModifiedNf := BufferNu;
end; < ModifiedNF >
Slika 6 Algoritem za izračun vrednosti povezovalne funkcije
Odsek krivulje B-zlepkov narišemo tako, da upoštevamo le tiste povezovalne funkcije, ki na tem odseku nastopajo in jih zmnožimo s pripadajočimi kontrolnimi točkami. V začetku algoritma za izris krivulj B-zlepkov določimo, katere povezovalne funkcije sodelujejo pri odseku, ki ga trenutno rišemo (slika 8). Prvo in zadnjo povezovalno funkcijo, ki hkrati določata tudi indeks ustrezne kontrolne točke, shranimo v spremenjivki firstBf in lastBf. V drugem delu algoritma določimo še indeks diskretne vrednosti vsake povezovalne funkcije, shranjene v zapisu tipa BfType, ki jo pri izračunu točk na krivulji po enačbi 1 potrebujemo. Nesklenjeno periodično krivuljo B-zlepkov, čigar povezovalne funkcije so na sliki la, vidimo na sliki 9a. Z majhno spremembo pri pripravi podatkov lahko s tem algoritmom narišemo tudi sklenjeno krivuljo B-zlepkov, ki jo vidimo na sliki 9b.
AllBfunctionType

Bf' Bflypg |
AltBfunc tionType
AllBfunctionType
b>
I'll-A Bf BfType |
C)
Slika 7 Podatkovna struktura baznih funkcij za:
a)	periodične krivulje B-zlepkov
b)	neperiodične krivulje B-zlepkov
c)	NURB krivulje
59
Procedure PlotBSpl(k,m: integer; periodic: boolean;
Pts: AllBfunctionType; rx,ry: PointsType);
{ - k: red povezovalnih funkcij,
-	m: število vozliščnih vrednosti,
-	periodic: TRUE, če rišemo periodične krivulje B-zlepkov
-	Pts: polje kazalcev na povezovalne funkcije,
-	rx,ry: polje kontrolnih točk.
Var
x, y: PolyLineType;
j, ui, ni, ind, firstBf, iastBf: integer; a: real; begin
firstBf : = -1;	IastBf := k - 1;
fon ui := 0 to m-2*k-l do begin 1
ijirstBf ': = firstBf + 1;	IastBf := IastBf + 1;
for j := O to NoOfSteps do
begin
xlj 1 := 0; y[jI := 0; for ni := firstBf to IastBf do begin
if periodic then
ind := (iastBf - ni) * NoOfSteps + j else
if ni <= k then
ind := (IastBf - k) • NoOfSteps + j else
ind := (IastBf - ni) * NoOfSteps + j; a := Ptslnil'.Bflindl; xlj] : = x[j) + rxlnil • a; ylj) := ylj] + rylni] * a; end; end;
gPolyLine(NoOfSteps+l, x, y); end;
end; < PlotBspl )
Slika 8 Algoritem za izris krivulj B-zlepkov
Potrebno podatkovno strukturo vidimo na sliki 7b, ki jo uporablja algoritem za izris krivulje B-zlepkov (slika 8). Na sliki 10 vidimo primer neperiodične krivulje B-zlepkov, katere povezovalne funkcije so na sliki lb.
Slika 10 Neperiodična krivulja B-zlepkov
5. DEFINICIJA NURB KRIVULJ
NURB krivulje ("nonuniform rational B-spline curves") so s svojo univerzalnostjo pritegnile mnogo raziskovalcev ([WAYN831, [BČHM841, 1PIEG87], [PIEG891, [R0GE90]). Z njimi lahko eksaktno predstavimo tako daljice, stožnice, kot poljubno oblikovane krivulje. NURB krivulje B-zlepkov uporabljajo tudi nekateri komercialni modelirni sistemi. Definirane so kot:

b)
Slika 9 * a) Nesklenjena periodična krivulja B-zlepkov b) Sklenjena periodična krivulja B-zlepkov
p(u)
y N (u) w r ^ l.k 1 i
v n u w
u J.fc J
J=0
= T R (u) r [ , k 1
(9)
kjer so r. kontrolne točke in k racionalne povezovalne funkcije, ki so definirane s kvocientom:
Izračun in izris neperiodičnih krivulj B-zlepkov
V primeru neperiodičnih krivulj B-zlepkov je število povezovalnih funkcij, ki jih moramo izračunati, večje. V najslabšem primeru moramo določiti k+1 povezovalnih funkcij, od katerih jih je k neperiodičnih in ena periodična. Na primeru s slike lb, ko je k = 3 in n = 8 vidimo, da je prvih k baznih funkcij (N , N , N ) zrcalnih zadnjim k
0,3 1,3 2,3	J
baznim funkcijam (N , N , N ). Zato je dovolj, če
7,3 6,3 5,3
izračunamo le prve, druge pa dobimo z enostavno zamenjavo mest koeficientov v polju. Med neperiodičnimi baznimi funkcijami se pojavijo periodične povezovalne funkcije, če je n i 2k [GUID90]. Kot smo že videli, pa te zahtevajo samo en izračun.
Tudi tokrat je prostorska in časovna zahtevnost določitve povezovalnih funkcij neodvisna od števila kontrolnih točk, tako da velja enačba 8. Funkcijo za izračun baznih funkcij v najslabšem primeru pokličemo
l^NoOfSteps + 2»No0fSteps + .... + (k+l)*NoOfSteps = = 0.5 * (k2 + 3k + 2) * NoOfSteps.
N (u) w
R (U) = —hI-!--(10)
i,k	n
T N (U) W J.k	J
V enačbi 10 nastopajo bazne funkcije N , ki so rekurzivno definirane z enačbo 2. Z vsoto v imenovalcu izraza 10 funkcijo Rj pri vsaki vrednosti parametra u normaliziramo. Množico vrednosti w , vv^ 0, 0 s i s n imenujemo uteži. Shranimo jih v vektor uteži W = [w , w..... w ]. Število
o i	n
uteži je enako številu točk, tako da točko r utežimo z utežjo w. Vozliščni vektor je definiran podobno kot tisti, ki določa neperiodične krivulje B-zlepkov (poglavje 2):
kjer velja: « = 0 ; ie i s k	(a)
u = m-2k ; če m-k s i s m	(b) i
u £ u ; če i > k in k+1 s i,k	s m-k-1 (c) i k
Za vozle na intervalu (b) velja, da so lahko	neuniformni. To pomeni, da razmaki med vozli niso nujno konstantni.
Vrednosti sosednjih vozlov so lahko enake,	vendar pri tem
60
velja, da ne sme biti enakih več kot k+1 sosednjih vozlov. Če vsem utežem 0 s i s n dodelimo vrednost 1, preide NURB krivulja v krivuljo B-zlepkov. Torej so R posplošitev povezovalnih funkcij N( . funkcij za NURB krivulje vidimo na sliki1 11.
l,k
Primer povezovalnih
Slika 11 Kubične racionalne povezovalne funkcije določene z: U = [0, 0, O, 0, 1, 2, 3, 4, 5, 6, 6, 6, 6] in
knot
W = [1, 1, 1, 5, 1, 1, 1, 1, 11
6. ALGORITEM ZA IZRAČUN NURB KRIVULJ
Za izračun povezovalnih funkcij N^ uporabljamo že znano dinamično drevesno strukturo (poglavje 3). Tudi za shranjevanje vrednosti R] vzamemo isti tip podatkovne strukture kot za N
i, k
NURB: AUBFunctionType,
s to razliko, da ima tokrat vsaka funkcija R kazalec na
i,k
svoj zapis tipa BfType (slika 7c).
Za izračun racionalnih povezovalnih funkcij upoštevamo naslednje:
-	potrebujemo n+1 povezovalnih funkcij ^ ki so lahko vse, zaradi morebitnega neuniformnega vozliščnega vektorja, različne;
-	ker v splošnem niti dve racionalni povezovalni funkciji nista enaki, moramo določiti tudi vseh n+1 R
1 , k
Pseudo kod algoritma za izračun povezovalnih funkcij NURB krivulj vidimo na sliki 12.
Pri analizi časovne zahtevnosti za izračun neperiodične krivulje B-zlepkov smo ugotovili, da je le-ta neodvisna od števila točk. Tokrat pa so zaradi neuniformnega vozliščnega vektorja vse funkcije N^ med seboj različne. Vsako izmed njih izračunamo v polinomskem času (enačba 7), za izračun vseh funkcij N pa moramo poklicati rutino za izračun baznih funkcij
2*(l*No0fSteps + 2*NoOfSteps + ... + k*NoOfSteps) + + (k+l)(n+l-2k)*No0fSteps = (k+l)(n-k+i)«NoOfSteps.
Število klicev je tokrat v linearni odvisnosti od števila kontrolnih točk krivulje. Ko smo izračunali vse povezovalne funkcije	k> Je potrebno izračunati še racionalne
povezovalne funkcije R^ . Vsaka R! se razteza največ čez k+1 segmentov vozliščnega vektorja. Za vsako vrednost u
Type
Ptr = "TypePtr;
TypePtr = array [O..knotmax] of record
knot : real; index : integer; end;
procedure MakeNURBf(ABF: AllBFunctionType;
Var NURB: AllBFunctionType; Wei: PointerToWeights; Knt: PointerToKnots; NoAllBf, k: integer; var indexs: Ptr);
{ -	ABF: kazalec na povezovalne funkcije Ni,k,
-	NURB: kazalec na NURB povezovalne funkcije,
-	Knt: kazalec na vozliščni vektor,
-	Wei: kazalec na polje, kjer so shranjene uteži,
-	NoAllBf: število neperiodičnih pov. funkcij v ABF,
-	k: stopnja racionalnih povezovalnih funkcij
-	indexs: kazalec na polje vozlov.
var
i, num, c, m, NoUv : integer;
function Summatindexs: Ptr; i,j,k,m: integer;
N: AllBFunctionType; W: PointerToWeights; Knt: PointerToKnots): real; ( - i: indeks funkcije, ki se trenutno izračunava,
-	j: indeks vrednosti povezovalne funkcije,
-	k: stopnja povezovalnih funkcij,
-	N: kazalec na polje vrednosti povezovalnih funkcij,
-	W: kazalec na polje uteži.
var
Sum, u	: real;
Bfu, ind, kplusl : integer; begin
Kplusl := 1; Bfu := 0;
u := CetuValue(Knt,indexs,i,j);
while (kplusl s k + 1) and (Bfu i NoAllBf) do
begin
if (u £ Knt"[Bfu]) and (u s Knt"[Bfu + k +ll) then begin
ind := GetIndex(Knt,indexs,i,j,Bfu); Sum:= Sum + N(Bfu]".Br| ind] * W"[Bfu); kplusl := kplusl + 1; end;
Bfu := Bfu +1; end;
Summa:= Sum; end; ( Summa }
begin { MakeNURBf ) new(indexs);
indexs'(O).index := 0; indexs~[0].knot := Knt".[01; m := NoAllBf + k + 1; C := 0; for i := 0 to k do begin
num := i;
while (num s m - k) and (c a m) do begin
if num s k then begin
indexs"(num + 1],index := ABF"[numl".NoOfUValues; indexs'lnum + ll.knot := Knt"[i + k + 11; end else begin
indexs"[num + 11.index := indexs~[num - ki.index + ABF"lnumi.NoOfU Values; indexs'lnum + 1).index := Knt"|num + k + 1); end;
num := num + k + 1; c := c + 1; end; end;
GetDiffKuotslindexs,NoAllBf + k + l.NoOffDiff);
for i := 0 to NoAllBf do
begin
m := NoAllBf + k + 1; NoUv := ABFlil'.NoOfUValues; NURBlil'.NoOfUValues := NoUv; for j := 0 to NoUv do NURBlir.Bflj] := ABFIi]".Bfl j] * WeiMi] /
Summa( indexs, i, j,k,m, ABF, Wei, Knt);
end;
end; { MakeNURBf )
Slika 12 Algoritem za izračun NURB krivulj
61
moramo določiti vsoto imenovalca v enačbi 10, ki je seštevek k+1 vrednosti funkcij N( k pomnoženih z utežmi	kar
opravimo v polinomskem času.
Algoritem za izris NURB krivulj, ki uporablja podatkovno strukturo s slike 7c, vidimo na sliki 13. Primer NURB krivulje določene s povezovalnimi funkcijami na sliki 11 pa vidimo na sliki 14.
procedure PlotNURBSpline (m, n, k : integer;
Knt : PointerToKnots; rx, ry : PtoPoints; NURB : AllbFunctionType; indexs : Ptr); { - m: število vozlišč vozliščnega vektorja,
-	n: število kontrolnih točk in število povez. funkcij,
-	k: stopnja racionalnih povezovalnih funkcij,
-	Knt: kazalec na vozliščni vektor,
-	rx,ry: kazalca na x- in ^-koordinate kontrolnih točk,
-	NURB: kazalec na vrednosti povezovalnih funkcij
-	indexs: kazalec na polje vozlov.	>
var
x, y : PolyLine_Type;
i,j,ind,NoOfKnt,firstRBf,lastRBf,func,ni,Steps: integer; first : boolean; begin
NoOfKnt := NoOfDiffKnots(indexs);
for i:=l to NoofKnt-1 do
begin
f irst:=true; for j:=0 to n do
if (Knt"[j]<=rKnt[il) and (rKnt[i+ll<=Knt"[j+k+ll) then if first then begin
firstRbf :=j; first:=f alse; end
else lastRbf:=j; Steps: =round((rKnt[i+l]-rKnt!i])*NoofSteps)+l; for ni: =1 to Steps do begin x[ni]:=0; y[nil:=0;
for func:=firstRbf to lastRbf do begin
ind:=round((rKnt[il-Knt-(funcl),NoofSteps)+ni-l; x[ni]:=x[ni]+ NURB[funcP.Bf(ind]*rx-[func]; y!nil:=y[ni]+ NURBifuncl~.Bf[ind]*ry-[func]; end; end;
gPolyLine( Steps, x,y); end;
end; { PlotNURBSpline >
Slika 13 Algoritem za izris NURB krivulj
Slika 14 NURB krivulja
7. ZAKLJUČEK
Opisana algoritma za izris krivulj B-zlepkov in NURB krivulj smo uporabili v programskem orodju za študij krivulj v CAGD, ki smo ga izdelali v našem laboratoriju [CUID911. Časovno zahtevnost obeh izdelanih algoritmov smo primerjali z de Boorovim iterativnim algoritmom [ YAMA881 in iterativnim racionalnim de Boorovim algoritmom [FARI891, ki izračunata ustrezno krivuljo brez določevanja povezovalnih funkcij. Rezultati so prikazani v tabeli 1 za primer, ko imamo 35 kontrolnih točk. Vidimo, da je naš algoritem za izris krivulj B-zlepkov hitrejši od de Boorovega algoritma, saj s sestavo primerne podatkovne strukture izkorišča lastnosti krivulj B-zlepkov oziroma njihovih povezovalnih funkcij (t. j. da je potrebno določiti samo k+1 različnih povezovalnih funkcij). De Boorov racionalni iterativni algoritem za izris NURB krivulj pa je hitrejši od našega algoritma, saj je tokrat potrebno izračunati vseh n povezovalnih funkcij. Seveda pa de Boorov algoritem ne omogoča prikaz povezovalnih funkcij, ki pa smo jih želeli vključiti v omenjen paket za študij krivulj.
Tabela 1 Čas (msek) porabljen za izris krivulj B-zlepkov in NURB krivulj z različnimi algoritmi
		A	B	a C	l q a D	n i t e E	m F	G	H		
	2	1 .59	1.71	1 . 74	1. 83	3 . 46	3 . 47	22.95	5 . 54	22	96
n e	3	1 . 97	2. 18	2. 14	2.59	5.27	5 . 33	34. 56	9 . 50	34	88
d	5	2. 74	4. 07	4 . 04	• 7.84	10 . 49	10.60	63. 25	20 . 65	66	96
	8	4 . 40	22. 84	11 . 53	87.49	20.87	2 1 . 26	119.91	43 . 11	197	65
A: naš algoritem - periodične krivulje C: naš algoritem - neperiodične krivulje E: de Boorov algoritem - periodične krivulje G: naš algoritem za NURB krivulje I: rekurzivni algoritem za NURB krivulje
B:	Cox-de Boorova formula - periodične krivulje
D:	Cox-de Boorova formula - neperiodične krivulje
F:	de Boorov algoritem - neperiodične krivulje H: de Boorov racionalni algoritem za NURB krivulje
62
Opisan algoritem lahko brez težav priredimo tudi za izračun in izris drugih tipov krivulj in ploskev, kar smo storili tudi v našem programskem paketu za študij krivulj v CAGD. Algoritem smo napisali v pascalu in za izris uporabili funkcije standarda CKS. Izdelali smo ga na skromni aparaturni opremi: IBM PC/AT-286/16Mh z uporabo matematičnega koprocesorja.
8. LITERATURA
1MORT85] Mortenson, M. E., "Geometric Modeling", John Wiley & Sons, New York, 1985.
[PIEG87] Piegel, L. and R. F. Sproull, "Curve and Surface Construction Using Rational B-splines", Comput. Aided Design, Vol. 19, No. 9, 1987, pp. 485 - 498.
[PIEG891 Piegl, L., "Modifying the shape of rational B-splines. Part 1: curves", Comput. Aided Design, Vol. 21, No. 8, 1989, pp. 509-518.
IBART87] Bartels, R. H., J. C. Beatty, and B. A. Barsky, "An Introduction to Splines for Use in Computer Graphics and Geometric Modeling", Morgan Kaufman Publishers, Los Altos, California, 1987.
IBC5HM84] Bohm, W., G. Farin, and J. Kahmann, "A survey of curve and surface methods in CAGD", Comput. Aided Geometric Design, Vol. 1, No. 1, 1984, pp. 1-60.
[FARI89] Farin, G., "Rational Curves and Surfaces", in Mathematical Methods in Computer Aided Geometric Design, (eds. T. Lyche and L. L. Schumaker), Academic Press, 1989, pp. 215-238.
[GU1D881 Guid, N., "Računalniška grafika", fakulteta Maribor, Maribor, 1988.
Tehniška
1GUID90] Guid, N. and B. Zalik, "Contributions to	practical
considerations of B-splines", Automatica,	Zagreb, Vol. 31, No. 1-2, 1990, pp. 83-88.
[GUID91] Guid, N., B. Zalik, and A. Vesel, "A	software
teaching tool for curve methods in CAGD",	Proc. of Computer Graphics and Education '91, Barcelona, 1991, pp. 62 - 70.
(R0GE901 Rogers, D. F. and L. A. Adlum, "Dynamic rational B-spline surfaces", Comput. Aided Design, Vol. 22, No. 9, 1990, pp. 609 - 616.
[TURK801 Turk, S., "Računarska grafika. Osnovi teorije i primjene", Školska knjiga Zagreb, Zagreb, 1980.
[WAYN831 Wayne, T., "Rational B-splines for Curve and Surface Representation", IEEE Comput. Graphics and Application, Vol. 3, No. 6, pp. 61-69.
[YAMA881 Yamaguchi, F., Curves and Surfaces in Computer Aided Geometric Design", Springer-Verlag, Berlin, Heidelberg, 1988.
12ALI901 Žalik, B. and N. Guid, "Časovna in prostorska zahtevnost pri izrisu krivulj B-zlepkov", Proč. 34. konferenca ETAN, Zagreb, Vol. 8, 1990, pp. 65-72.