BALL SURFACE REPRESENTATIONS USING PARTIAL DIFFERENTIAL EQUATIONS AHMED SALEH ABDULLAH KHERD DOCTOR OF PHILOSOPHY UNIVERSITI UTARA MALAYSIA 2015 Permission to Use In presenting this thesis in fulfilment of the requirements for a postgraduate degree from Universiti Utara Malaysia, I agree that the Universiti Library may make it freely available for inspection. I further agree that permission for the copying of this thesis in any manner, in whole or in part, for scholarly purpose may be granted by my supervisor or, in their absence, by the Dean of Awang Had Salleh Graduate School of Arts and Sciences. It is understood that any copying or publication or use of this thesis or parts thereof for financial gain shall not be allowed without my written permission. It is also understood that due recognition shall be given to me and to Universiti Utara Malaysia for any scholarly use which may be made of any material from my thesis. Requests for permission to copy or to make other use of materials in this thesis, in whole or in part, should be addressed to: Dean of Awang Had Salleh Graduate School of Arts and Sciences UUM College of Arts and Sciences Universiti Utara Malaysia 06010 UUM Sintok Abstrak Sejak dua dekad lalu, pemodelan geometri menggunakan pendekatan persarnaan pem- bezaan separa (PPS) telah dikaji secara meluas dalam Rekabentuk Geometri Bantuan Komputer (RGBK). Pendekatan ini pada mulanya diperkenalkan oleh beberapa orang penyelidik berdasarkan kepada permukaan BCzier yang berkaitan dengan luas permu- kaan minimum ditentukan oleh lengkung sempadan yang ditetapkan. Walau bagaima- napun, perwakilan permukaan BCzier boleh diperbaiki dari segi masa pengiraan clan luas permukaan minimum dengan menggunakan perwakilan permukaan Ball. Sehu- bungan itu, kajian ini membangunkan satu algoritma untuk mengitlak permukaan Ball dari lengkung sempadan menggunakan PPS eliptik. Dua permukaan Ball khusus iaitu hannonik dan dwiharmonik pertarnanya dibina dalam membangunkan algoritma yang dicadangkan. Permukaan terdahulu dan kemudian masing-masing memerlukan dua dme mpat syarat sempadan. Bagi mengitlak permukaan Ball dalam penyelesaian poli- nomial untuk sebarang PPS peringkat empat, kaedah Dirichlet digunakan. Keputusan berangka diperolehi keatas contoh titik data yang diketahui umum menunjukkan algo- ritma perrnukaan Ball teritlak yang dicadangkan mempamerkan keputusan lebih baik daripada perwakilan permukaan BCzier dari segi masa pengiraan dan luas permukaan minimum. Tambahan pula, algoritma yang baharu dibina juga memenuhi sebarang per- mukaan dalam RGBK termasuk permukaan BCzier. Algoritma ini kemudiannya diuji dalarn permasalahan pengekalan kepositifan permukaan dm pembesaran imej. Kepu- tusan menunjukkan algoritma yang dicadangkan adalah setanding dengan kaedah yang sedia ada dari segi kejituan. Justeru, algoritrna ini adalah satu alternatif berdaya maju untuk membina permukaan Ball teritlak. Dapatan daripada kajian ini menyurnbang kearah bidang pengetahuan untuk pembinaan semula permukaan berdasarkan pende- katan PPS dalam bidang pemodelan geometri dan grafik komputer. Kata kunci: Permukaan Ball, Persamaan pembezaan separa, Kaedah Dirichlet, Pe- ngekalan kepositifan, Pembesaran imej. Abstract Over two decades ago, geometric modelling using partial differential equations (PDEs) approach was widely studied in Computer Aided Geometric Design (CAGD). This approach was initially introduced by some researchers to deal with Bkzier surface re- lated to the minimal surface area determined by prescribed boundary curves. However, BCzier surface representation can be improved in terms of computation time and min- imal surface area by employing Ball surface representation. Thus, this research devel- ops an algorithm to generalise Ball surfaces from boundary curves using elliptic PDEs. Two specific Ball surfaces, namely harmonic and biharmonic, are first constructed in developing the proposed algorithm. The former and later surfaces require two and four boundary conditions respectively. In order to generalise Ball surfaces in the poly- nomial solution of any fourth order PDEs, the Dirichlet method is then employed. The numerical results obtained on well-known example of data points show that the proposed generalised Ball surfaces algorithm performs better than BCzier surface rep- resentation in terms of computation time and minimal surface area. Moreover, the new constructed algorithm also holds for any surfaces in CAGD including the Bezier surface. This algorithm is then tested in positivity preserving of surface and image en- largement problems. The results show that the proposed algorithm is comparable with the existing methods in terms of accuracy. Hence, this new algorithm is a viable alter- native for constructing generalized Ball surfaces. The findings of this study contribute towards the body of knowledge for surface reconstruction based on PDEs approach in the area of geometric modelling and computer graphics. Keywords: Ball surface, Partial differential equation, Dirichlet method, Positivity pre- serving, Image enlargement. Acknowledgements I would like to express my sincere gratitude to my supervisor Dr. Azizan Bin Saaban who gave me a lot of guidances and advices. I thanked him not only as my supervisor, but also as my counselor. I am grateful to the Ministry of Higher Education of Malaysia for providing me with the Fundamental Research Grant Scheme (FRGS) (SIO: 12380) to enable me to pursue this research. I wish to thank the staff from the School of Quantitative Sciences, Universiti Utara Malaysia. This research would not have been possible without the facilities provided by the School of Quantitative Sciences, Universiti Utara Malaysia. I would like to dedicate this thesis to my parents, my wives and Al-Ahgaff University, Yemen, for their support. Table of Contents Permission to Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abstrak 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abstract iii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgements iv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of Tables xi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of Symbols xviii . . . . . . . . . . . . . . . . . . . . . CHAPTER ONE INTRODUCTION 1 1.1 Research Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problem Statement 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Research Questions 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Objective of the Research 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Research Framework 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Scope of the study 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Significance of the Study 6 1.8 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 ................. CHAPTER TWO LITERATURE REVIEW 8 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Review on Bkzier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Derivative and Integral of Bernstein Polynomials . . . . . . . . . 11 . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 BCzier Monomial Form 12 2.2.3 Degree Elevation of BCzier Curves . . . . . . . . . . . . . . . . . 12 2.2.4 BCzier Rectangular Surfaces . . . . . . . . . . . . . . . . . . . . 13 2.3 Review on Ball Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 Said-Ball Representation . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1.1 Said-Ball Monomial Form . . . . . . . . . . . . . . . . 17 2.3.1.2 Conversion of Said-Ball Curve to BCzier Curve . . . . 17 2.3.1.3 Said-Ball Rectangular Surfaces . . . . . . . . . . . . . 19 v 2.3.1.4 Converting Said-Ball Surface into Bkzier Surface . . . . 2.3.2 DP-Ball Curves Representation . . . . . . . . . . . . . . . . . . . 2.3.2.1 DP Monomial Form . . . . . . . . . . . . . . . . . . . 2.3.2.2 Conversion of DP-Ball Curve to BCzier Curve . . . . . 2.3.2.3 DP-Ball Rectangular Surfaces . . . . . . . . . . . . . . 2.3.2.4 Converting DP-Ball Surface into BCzier Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Wang-Ball Curves 2.3.3.1 Wang-Ball Monomial Form . . . . . . . . . . . . . . . 2.3.3.2 Conversion of Wang-Ball Curve to BCzier Curve . . . . 2.3.3.3 Wang-Ball Rectangular Surfaces . . . . . . . . . . . . . 2.3.3.4 Converting Wang-Ball Surface into BCzier Surface . . . 2.4 Parametric Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Harmonic and Biharmonic Surface . . . . . . . . . . . . . . . . . . . . . 2.5.1 The First Fundamental Form . . . . . . . . . . . . . . . . . . . . 2.5.2 Monomial Matrix Form . . . . . . . . . . . . . . . . . . . . . . . 2.5.2.1 BCzier Monomial Matrix . . . . . . . . . . . . . . . . . 2.5.2.2 Said-Ball Monomial Matrix . . . . . . . . . . . . . . . 2.5.2.3 DP-Ball Monomial Matrix . . . . . . . . . . . . . . . . 2.5.2.4 Wang-Ball Monomial Matrix . . . . . . . . . . . . . . 2.5.2.5 Converting the Control Points of BCzier Surface into Con- . . . trol Points of Ball Surface using Monomial Matrix 2.6 Definition of Isothermal Surface . . . . . . . . . . . . . . . . . . . . . . 2.7 Estimate the Partial Derivative with respect to x and y for the Control Points at the Boundary Curves . . . . . . . . . . . . . . . . . . . . . . . ... CHAPTER THREE HARMONIC AND BIHARMONIC SURFACE 3.1 Harmonic of X(u. v) Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Biquadratic Harmonic Patches 3.1.1.1 Said-Ball Patch . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Bicubical Harmonic Patches . . . . . . . . . . . . . . . . . . . . 3.1.2.1 Bicubical Harmonic Said-Ball Patches . . . . . . . . . 3.1.2.2 Bicubical Harmonic DP-Ball Patches . . . . . . . . . . 3.1.3 Graphical Examples for Harmonic Bicubic Surface . . . . . . . . vi 3.1.3.1 Graphical Examples for Harmonic Bicubic Said/Wang- Ball Surface . . . . . . . . . . . . . . . . . . . . . . . 3.1.3.2 Graphical Examples for Harmonic Bicubic DP-Ball Sur- face . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Biharmonic of X(u,v ) Patch . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Bicubic Biharmonic Patch . . . . . . . . . . . . . . . . . . . . . 3.2.1.1 Bicubic Said/Wang-Ball Biharmonic Equation . . . . . 3.2.1.2 DP-Ball Biharmonic Equation . . . . . . . . . . . . . 3.2.2 Graphical Examples for Bihannonic Bicubic Patch . . . . . . . . 3.2.2.1 Graphical Examples for Biharmonic Bicubic SaidNang- Ball Patch . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2.2 Graphical Examples for Biharmonic Bicubic DP-Ball Sur- face . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Biquartic Biharmonic Equation . . . . . . . . . . . . . . . . . . . 3.2.3.1 Biquartic Said-Ball Biharmonic Equation . . . . . . . . 3.2.3.2 Biquartic DP-Ball Biharmonic Equation . . . . . . . . . 3.2.3.3 Biquartic Wang-Ball Biharmonic Equation . . . . . . . 3.2.4 Graphical Examples for Bihannonic Biquartic Patch . . . . . . . 3.2.4.1 Graphical Examples for Biharmonic Biquartic Said-Ball Patch . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4.2 Graphical Examples for Biharmonic Biquartic DP-Ball Patch . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4.3 Graphical Examples for Biharmonic Biquartic Wang-Ball Patch . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CHAPTER FOUR POLYNOMIAL SOLUTIONS OF FOURTH ORDER LINEAR ELLIPTIC PARTIAL DIFFERENTIAL EQUATIONS AND EXTREMAL OF THE DIRICHLET FUNCTIONAL IN TERMS OF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BALLSURFACE 4.1 Polynomial Solutions of Fourth Order Linear Elliptic PDEs in terms of Ball Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Said-Ball Polynomial Solutions for Fourth Order Partial Differen- tial Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.1.1.1 Odd Degree-n Said-Ball Boundary Curves Defined on Rectangular Grid . . . . . . . . . . . . . . . . . . . . . 104 4.1.1.2 Relation Between Cubic Said-Ball Boundary Coefficients and Polynomial Coefficients Using Fourth Order PDEs 104 4.1.1.3 Relation Between Quintic Said-Ball Boundary Coeffi- cients and Polynomial Coefficients Using Fourth Order PDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.1.2 DP-Ball Polynomial Solutions for Fourth-Order Partial Differen- tial Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.1.3 Odd Degree-n DP-Ball Boundary Curves Defined on Rectangular Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.1.3.1 Relation Between Cubic DP-Ball Boundary Coefficients and Polynomial Coefficients Using Fourth Order PDEs 108 4.1.3.2 Relation Between Quintic DP-Ball Boundary Coefficients and Polynomial Coefficients Using Fourth Order PDEs 110 4.1.4 Wang-Ball Polynomial Solutions for Fourth Order Partial Differ- ential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 12 4.1.4.1 Odd Degree-n Wang-Ball Boundary Curves Defined on Rectangular Grid . . . . . . . . . . . . . . . . . . . . . 1 12 4.1.4.2 Relation Between Cubic Wang-Ball Boundary Coeffi- cients and Polynomial Coefficients Using Fourth Order PDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 12 4.1.4.3 Relation Between quintic Wang-Ball Boundary Coeffi- cients and Polynomial Coefficients Using Fourth Order PDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.1.5 Surface Construction . . . . . . . . . . . . . . . . . . . . . . . 11 5 4.1.6 Graphical Examples . . . . . . . . . . . . . . . . . . . . . . . . 11 6 4.1.6.1 Bicubic SaidIWang-Ball . . . . . . . . . . . . . . . . . 116 4.1.6.2 Biquintic Said-Ball . . . . . . . . . . . . . . . . . . . . 1 18 4.1.6.3 Bicubic DP-Ball . . . . . . . . . . . . . . . . . . . . . 11 9