Subdivision, interpolation and splines
Date
2000-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: In this thesis we study the underlying mathematical principles of stationary subdivision,
which can be regarded as an iterative recursion scheme for the generation of smooth curves
and surfaces in computer graphics. An important tool for our work is Fourier analysis, from
which we state some standard results, and give the proof of one non-standard result. Next,
since cardinal spline functions have strong links with subdivision, we devote a chapter to this
subject, proving also that the cardinal B-splines are refinable, and that the corresponding
Euler-Frobenius polynomial has a certain zero structure which has important implications
in our eventual applications. The concepts of a stationary subdivision scheme and its convergence
are then introduced, with as motivating example the de Rahm-Chaikin algorithm.
Standard results on convergence and regularity for the case of positive masks are quoted and
graphically illustrated.
Next, we introduce the concept of interpolatory stationary subdivision, in which case
the limit curve contains all the original control points. We prove a certain set of sufficient
conditions on the mask for convergence, at the same time also proving the existence and
other salient properties of the associated refinable function. Next, we show how the analysis
of a certain Bezout identity leads to the characterisation of a class of symmetric masks which
satisfy the abovementioned sufficient conditions. Finally, we show that specific special cases
of the Bezout identity yield convergent interpolatory symmetric subdivision schemes which
are identical to choosing the corresponding mask coefficients equal to certain point evaluations
of, respectively, a fundamental Lagrange interpolation polynomial and a fundamental
cardinal spline interpolant. The latter procedure, which is known as the Deslauriers-Dubuc
subdivision scheme in the case of a polynomial interpolant, has received attention in recent
work, and our approach provides a convergence result for such schemes in a more general
framework.
Throughout the thesis, numerical illustrations of our results are provided by means of
graphs.
AFRIKAANSE OPSOMMING: In hierdie tesis ondersoek ons die onderliggende wiskundige beginsels van stasionêre onderverdeling, wat beskou kan word as 'n iteratiewe rekursiewe skema vir die generering van gladde krommes en oppervlakke in rekenaargrafika. 'n Belangrike stuk gereedskap vir ons werk is Fourieranalise, waaruit ons sekere standaardresuJtate formuleer, en die bewys gee van een nie-standaard resultaat. Daarna, aangesien kardinale latfunksies sterk bande het met onderverdeling, wy ons 'n hoofstuk aan hierdie onderwerp, waarin ons ook bewys dat die kardinale B-Iatfunksies verfynbaar is, en dat die ooreenkomstige Euler-Frobenius polinoom 'n sekere nulpuntstruktuur het wat belangrike implikasies het in ons uiteindelike toepassings. Die konsepte van 'n stasionêre onderverdelingskema en die konvergensie daarvan word dan bekendgestel, met as motiverende voorbeeld die de Rahm-Chaikin algoritme. Standaardresultate oor konvergensie en regulariteit vir die geval van positiewe maskers word aangehaal en grafies geïllustreer. Vervolgens stelons die konsep van interpolerende stasionêre onderverdeling bekend, in welke geval die limietkromme al die oorspronklike kontrolepunte bevat. Ons bewys 'n sekere versameling van voldoende voorwaardes op die masker vir konvergensie, en bewys terselfdertyd die bestaan en ander toepaslike eienskappe van die ge-assosieerde verfynbare funksie. Daarna wys ons hoedat die analise van 'n sekere Bezout identiteit lei tot die karakterisering van 'n klas simmetriese maskers wat die bovermelde voldoende voorwaardes bevredig. Laastens wys ons dat spesifieke spesiale gevalle van die Bezout identiteit konvergente interpolerende simmetriese onderverdelingskemas lewer wat identies is daaraan om die ooreenkomstige maskerkoëffisientegelyk aan sekere puntevaluasies van, onderskeidelik, 'n fundamentele Lagrange interpolasiepolinoom en 'n kardinale latfunksie-interpolant te kies. Laasgenoemde prosedure, wat bekend staan as die Deslauriers-Dubuc onderverdelingskema in die geval van 'n polinoominterpolant, het aandag ontvang in onlangse werk, en ons benadering verskaf 'n konvergensieresultaat vir sulke skemas in 'n meer algemene raamwerk. Deurgaans in die tesis word numeriese illustrasies van ons resultate met behulp van grafieke verskaf.
AFRIKAANSE OPSOMMING: In hierdie tesis ondersoek ons die onderliggende wiskundige beginsels van stasionêre onderverdeling, wat beskou kan word as 'n iteratiewe rekursiewe skema vir die generering van gladde krommes en oppervlakke in rekenaargrafika. 'n Belangrike stuk gereedskap vir ons werk is Fourieranalise, waaruit ons sekere standaardresuJtate formuleer, en die bewys gee van een nie-standaard resultaat. Daarna, aangesien kardinale latfunksies sterk bande het met onderverdeling, wy ons 'n hoofstuk aan hierdie onderwerp, waarin ons ook bewys dat die kardinale B-Iatfunksies verfynbaar is, en dat die ooreenkomstige Euler-Frobenius polinoom 'n sekere nulpuntstruktuur het wat belangrike implikasies het in ons uiteindelike toepassings. Die konsepte van 'n stasionêre onderverdelingskema en die konvergensie daarvan word dan bekendgestel, met as motiverende voorbeeld die de Rahm-Chaikin algoritme. Standaardresultate oor konvergensie en regulariteit vir die geval van positiewe maskers word aangehaal en grafies geïllustreer. Vervolgens stelons die konsep van interpolerende stasionêre onderverdeling bekend, in welke geval die limietkromme al die oorspronklike kontrolepunte bevat. Ons bewys 'n sekere versameling van voldoende voorwaardes op die masker vir konvergensie, en bewys terselfdertyd die bestaan en ander toepaslike eienskappe van die ge-assosieerde verfynbare funksie. Daarna wys ons hoedat die analise van 'n sekere Bezout identiteit lei tot die karakterisering van 'n klas simmetriese maskers wat die bovermelde voldoende voorwaardes bevredig. Laastens wys ons dat spesifieke spesiale gevalle van die Bezout identiteit konvergente interpolerende simmetriese onderverdelingskemas lewer wat identies is daaraan om die ooreenkomstige maskerkoëffisientegelyk aan sekere puntevaluasies van, onderskeidelik, 'n fundamentele Lagrange interpolasiepolinoom en 'n kardinale latfunksie-interpolant te kies. Laasgenoemde prosedure, wat bekend staan as die Deslauriers-Dubuc onderverdelingskema in die geval van 'n polinoominterpolant, het aandag ontvang in onlangse werk, en ons benadering verskaf 'n konvergensieresultaat vir sulke skemas in 'n meer algemene raamwerk. Deurgaans in die tesis word numeriese illustrasies van ons resultate met behulp van grafieke verskaf.
Description
Thesis (MSc)--University of Stellenbosch, 2000.
Keywords
Interpolation, Spline theory, Stationary subdivision, Dissertations -- Mathematics