AN OBJECT-ORIENTED DESIGNFOR HIERARCHICAL B-SPLINE SURFACESByHailin YanB.Sc University of Science and Technology of ChinaA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE STUDIESCOMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAFebruary 1993© Hailin Yan, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(SignatureDepartment of Computer ScienceThe University of British ColumbiaVancouver, CanadaDate^March 15,1993DE-6 (2/88)AbstractThis thesis documents an object-oriented software system that supports free-form sur-face modelling based on the hierarchical overlay methodology of [Forsey88]. This workis motivated by the need to provide a space-efficient representation of tensor-producthierarchical spline surfaces, multiple offset method support, and general surface repre-sentation. This design uses a spatial data structure, the quadtree, to achieve this goal.The quadtree, itself a hierarchical data structure, is very suitable in this application be-cause of its ability to focus on the interesting subsets of the data. This focusing resultsin an efficient representation. The quadtree is also attractive because of its conceptualclarity and ease of maintenance.The package is implemented in C++ to provide: a) extensibility so that the newtools can be easily integrated into the existing package; b) reusability of code; and c)localization of code. Finally, this object-oriented hierarchical design keeps all of theoriginal features of the hierarchical overlay method of [Forsey90].iiTable of ContentsAbstract^ iiList of Tables vList of Figures^ viAcknowledgements viii1 Introduction 11.1 The Problems and Motivations ^ 11.2 The Design Goals ^ 31.3 Overview ^ 42 Background 62.1 The Hierarchical Surface Methodology ^ 62.2 Object-Oriented Programming and the Waterloo C++ Spline Classes 113 Design and Implementation 193.1 Analysis of Hierarchical Surface Representations ^ 193.2 Overview of Functional Relationships and Structures in the Design . 273.3 Functional Specification for Each Class ^ 353.3.1^Hierarchical Overlay Classes 353.3.2^Quadtree Classes ^ 433.3.3^The Support Classes 51iii3.4 Design Review ^ 584 Storage and Performance Analysis^ 594.1 Storage Benchmarks ^ 594.1.1 Storage Analysis in the Single-overlay Quadtree Representation ^ 604.1.2 Storage Analysis in the Multiple-overlay Quadtree Representation 614.2 Performance Benchmarks ^ 654.2.1 CV Navigation 664.2.2 Traversals in a Hierarchical Surface ^ 704.2.3 Evaluation ^714.2.4 Refinement ^ 724.2.5 Multi-level Editing ^735 Conclusion and Future Work^ 755.1 Conclusion ^ 755.2 Future Work 76Appendices^ 79A Mathematical Background on Tensor-product B-spline Surfaces^79B The Definition of Quadtrees and Their Characteristics ^84Bibliography^ 87ivList of Tables3.1 Four kinds of quadtree data structures for hierarchical overlays ^ 244.2 Storage overheads for a fully refined surface in three kinds of data structures 624.3 Storage overheads for a sparsely refined surface in three kinds of structures 634.4 Execution time for getting a CV in the multiple-overlay quadtree ^ 674.5 Execution time for getting a CV in single-overlay quadtrees ^ 674.6 Execution time (in psec) for getting a CV and its neighbour in the multiple-overlay quadtree representation ^ 684.7 Execution time (in psec) for getting a CV and its neighbour in the single-overlay quadtree representation ^ 694.8 Execution time (in psec) for getting a CV and the CV's in its parent! childpatch in the multiple-overlay quadtree representation ^ 69vList of Figures2.1 Surface S[k] and edited surface S[k+11 ^82.2 A 16-patch surface described by 49 control vertices ^92.3 A 16-patch surface with refinement and overlay control vertices ^ 102.4 Basis Class Hierarchy ^ 142.5 The hierarchy for parametric tensor-product surfaces ^ 172.6 The basis spline surface object ^183.7 A hierarchical surface and its multiple - overlay quadtree representation^253.8 A hierarchical surface and its single - overlay quadtree representation^263.9 A hierarchical bi-cubic B-spline surface ^283.10 The initial hierarchical surface in a multiple- overlay quadtree ^303.11 The hierarchical surface in a multiple - overlay quadtree after one refinement 313.12 The hierarchical surface in a multiple - overlay quadtree after the secondrefinement ^ 323.13 The final hierarchical surface in a multiple- overlay quadtree ^ 333.14 The initial hierarchical surface in single - overlay quadtrees ^343.15 The hierarchical surface in single - overlay quadtrees after one refinement^363.16 The hierarchical surface in single - overlay quadtrees after the second refine-ment ^ 373.17 The final hierarchical surface in single- overlay quadtrees ^ 383.18 A hierarchical B-spline surface object in the multiple - overlay quadtree . ^ 38vi3.19 A hierarchical B-spline surface object in single- overlay quadtrees ^393.20 HierOverlay Class Structure ^ 393.21 QuadTree Class Hierarchy 443.22 The hierarchy for a control node definition ^ 513.23 The Control Node Matrix Structure ^ 574.24 The definition for the nth lowest level in a quadtree ^ 645.25 One non-uniform refinement case in the single- overlay quadtree structure^77A.26 Regions for four equal patches ^ 82B.27 A region, its maximal blocks, and the corresponding quadtree. (a) Region.(b) Block decomposition of the region in (a). (c) Quadtree representationof the blocks in (b) 85viiAcknowledgementsI would like to thank Dr. David Forsey, my thesis supervisor, for his guidance and en-couragement throughout my work on this thesis. The discussion between us improved thecontent and presentation of this thesis significantly. I would also like to thank Dr. JackSnoeyink for reading through the draft of this thesis, his comments and his help. Manythanks go to the graduate students of the Department of Computer Science, especiallyChristopher Healey, Karen Kuder, Gene Lee, Stanley Jang, Vishwa Ranjan and TonyLau for their help and suggestions. I also wish to thank those people from the WaterlooComputer Graphics Laboratory for supplying the C++ Spline Software Package, whichI made use of in my implementation.viiiChapter 1IntroductionThis thesis is motivated by the need for an efficient representation of hierarchical B-spline surfaces. This chapter describes the problems inherent in constructing free-formhierarchical B-spline surfaces, briefly presents our design goals, and closes with a thesisoverview.In this thesis, it is assumed that the reader has a basic knowledge of splines as used inthe design of surfaces in computer graphics, at least to the level presented in AppendixA. For more information, refer to [Bartels87] or [Farin90].1.1 The Problems and MotivationsIn the traditional approach to B-spline surface modelling, a surface is defined by: anm x n matrix of control vertices, two knot vectors determining the location of each CV'in parametric space, and the appropriate basis functions (See Appendix A). The numberof patches in the surface is increased from mn to (7n + 1)n or m(n + 1), using a processcalled knot insertion or refinement. A general, space-efficient approach for representingtensor-product spline surfaces was proposed in [Forsey90]. It offers greater editing flexi-bility than is normally found in systems using traditional representations ([Riesenfeld81],[Tiller83], [Maiorino85] and [Sederberg & Parry86]). Forsey introduced a data struc-turing technique which allows local refinement of tensor-product spline surfaces (such as'Cy means control vertex.1Chapter 1. Introduction^ 2B-splines and their rational counterparts) so that the number of patches in a given regioncan be increased without affecting the rest of the surface. Local refinement, coupled witha reference-plus-offset representation of the hierarchy, allows surface manipulation inde-pendent of refinement by exploring the local geometry of the surface. This "hierarchicalform" is applicable to any spline with a refinement procedure and locally supported basisfunctions. These properties can be used in the task of creating a complex shape froma single, continuous, tensor-product spline surface, and are useful in free-form surfacedesign in general. For details, refer to Section 2.1.Although the above hierarchical surface approach overcomes some of the shortcomingsof traditional tensor-product spline surfaces, the current prototypical hierarchical B-spline editor exhibits the following cumbersome characteristics: A flexible, but space-inefficient internal representation, in which each control vertexuses 6 pointers (4 pointers to its immediate neighbours in the CV matrix in thesame overlay and 1 each to a corresponding CV in the two adjacent levels); Only bi-cubic B-splines are available; The process of adding new offset methods is not structured; Multiple hierarchical surfaces cannot be manipulated within a single invocation ofthe editor.This thesis is the result of a re-evaluation of the software needs and requirements ofa hierarchical spline editing system, motivated by:1. Extensibility. The package must not be limited to one particular type of spline. Itis essential that it is easy to develop new surface editors which can be used with avariety of spline formulations.Chapter 1. Introduction^ 32. Reusability of code. It is desirable to avoid repetition of code with similar func-tionality. Code should be reused rather than duplicated.3. Localization of code. Code that deals with related matters, or structurally similaralgorithms to achieve related goals, should be concentrated, as much as possible,in a single location.4. More compact representation of the hierarchical surface itself.To provide a solid foundation, a C++ spline software system supporting interactivespline modelling was obtained from the University of Waterloo's Computer GraphicsLaboratory ((Bartels91]). This system contains a reusable collection of support programsfor splines, rendering, refinement, display and interaction.1.2 The Design GoalsThe ultimate purpose of this research is to aid in the development of a highly interactiveand intuitive modelling tool to replace the existing prototypical editor. This thesis detailsthe implementation of C++ tools that both efficiently represent the hierarchical surfaceand provide a complete set of procedures to deal with the manipulation and instantiationof such a surface.A hierarchical surface is comprised of multiple levels of "spline overlay" with theparametric spacing of patches in each overlay being half of that in the preceding level.In this multi-resolution representation of a surface, level 0 has the largest parametricspacing (typically 1.0) and level n + 1 has a spacing that is half of that of level n.The criteria for choosing an efficient data structure to represent a hierarchical surfaceare: fast access to an arbitrary control vertex in the hierarchyChapter 1. Introduction^ 4 fast access to the immediate neighbours of a given control vertex fast access to level n ± 1 from level n fast traversal of the hierarchy minimized storage requirementsAn efficient data structure for a hierarchical surface representation is desired. Thisdata structure must be easy to implement, minimize memory requirements and be flexi-ble enough to support future extensions. Since our design adopts the hierarchical overlaymethod, it is not surprising that a data structure has been chosen with a similar hierar-chical nature. That is, a hierarchical data structure, the quadtree, is used to represent ahierarchical spline surface.1.3 OverviewThe rest of this thesis is organized as follows:Chapter 2 describes the hierarchical spline methodology, object-oriented programmingand the Waterloo C++ spline classes.Chapter 3 gives a detailed description of our design of an object-oriented hierarchicalB-spline surface. We capture the major characteristics of our design using an example,and then explore their advantages.Chapter 4 presents an assessment of the design with respect to the space- and time-efficiency of the main operations in our surface modeller. We then analyze the strengthsand weaknesses of the design.Chapter 5 concludes the thesis with the results of our research and presents directionsfor future study.Appendix A gives B-spline and tensor-product B-spline surface definitions.Chapter 1. Introduction^ 5Appendix B describes a hierarchical data structure, the quadtree, and its characteris-tics.Chapter 2Background2.1 The Hierarchical Surface MethodologyTensor-product B-splines are flexible surface representations, but they possess a de-ficiency when it comes to refinement. Refinement is usually advocated as a means ofgaining finer control over a spline surface during editing. However, refinement may addmore control vertices than required. One method of localizing the effect of refinement isthe hierarchical surface representation presented in [Forsey90].A degree (k, l) tensor-product B-spline surface has the form:n-1 rn-iS(U, V) = E Ei.0 i=oThe control vertices V j are arranged in an m x n rectangular array, called the controlvertex mesh indexed by i, j. Each l/,, is a vector (Here, vector refers to the cardinalcoordinates). Bi,k(u) and Bi,i(v) are the univariate B-spline basis functions. The variablesk and 1 are the orders of the B-splines in the u and v parametric directions, respectively.Hierarchical surface representation is a data structuring technique imposed upon atensor-product spline surface. This data structure relies on two properties of the B-spline basis function: local support and refinement. Local support means that the areaon a surface affected by a single control vertex is bounded. The procedure of refinementproduces an exact re-representation of the original surface but with a larger number of'This section is referenced from [Forsey90].6Chapter 2. Background^ 7patches and control vertices. Local refinement exploits the local support property of theB-spline basis function to restrict the extent of refinement over the surface by increasingthe number of patches in a restricted region.A level - k surface S[k](u, v) is defined over control nodes2 jk.3 by the following equa-tion:s[k](u, v) E E fiiTB.1,2(u)BIy(v)The surface derived from the refinement of a restricted region of S[ 14 , defined by asubset of the V[k], is the level - k 1 surfaces[k+i](u, v) E E .1,73k.+1,BIkk+1,1_lu)-"3,1jdefined by control nodes Vi[ +1] and a different set of basis functions obtained throughrefinement of the restricted region. Each S [k] is called an overlay. The level - k surfaceis the parent of the child at level - k + 1 and the level - 0 surface is called the root-level.Only midpoint refinement is used. Therefore, each child overlay has uniform knot vectorswith half of the spacing of its parent overlay.If one control node of 17,[1:+1] is moved (edited), the surface S[k+1] departs from itsparent, S[k], in the local area influenced by that particular control node. If editing isrestricted to those control nodes of V[ k+1] whose corresponding basis functions are zeroat the boundary between the surfaces S[k] and S[k+1], discontinuities will not appear inthe surface. Figure 2.1 shows the surface S[k] superimposed on the surface S[k+1] afterthe control vertex Qics+1] has been moved. The resulting composite surface retains thecontinuity properties of the underlying basis functions because the nature of the basicsurface representation has not changed.2Any control vertex in any level of a hierarchical surface is called a control node. In the remainderof this thesis, CV means control node in a hierarchical surface.Chapter 2. Background^ 8Figure 2.1: Surface PI and edited surface S [k+1]Local refinement can be repeated on the interior of an overlay to create further overlayswithin overlays. The basic operation of creating an overlay consists of designating acontrol node fir[ksi on the surface at a particular level of refinement and executing arefinement step to re-represent the area influenced by the refined control node Vthis causes overlays to overlap each other in S[k+1], the overlapping overlays are made intoa composite overlay by combining their respective control nodes into a single collection.Figure 2.2 shows a schematic plan of 7 x 7 matrix of control vertices (circled x's),along with the 16 bi-cubic B-spline patches and the surface that they define. This con-stitutes the minimal portion of the surface that would change due to any movement ofthe central control node V[s] . Figure 2.3 illustrates the overlay that would result fromlocal refinement. The black dots represent the control nodes in 0+ 1], and dashed boxesoutline the smaller patches that the central control node Vthis central control node of 1-/[k+1] is moved, and all the others are held fixed, the patchesgiven by the dashed boxes will remain an integral part of the surface and the boundarywill remain continuous with the 12 surrounding patches defined by the control vertices- 47.[ ks + 1 ] . If-11`.+1-1 will influence. If onlyChapter 2. Background^ 9Figure 2.2: A 16-patch surface described by 49 control verticesin 17[k] . The degree of continuity at the boundary depends upon the continuity of thesplines themselves. For bi-cubic patches, it will be C2 ; while for bi-quadric patches, itwill be C1 .For editing which involves the movement of several control vertices that modify alarger area of the surface, the new overlay must enclose the union of the individualsingle-vertex overlays. For editing that is to influence a smaller region, refinement willbreak each patch into several subpatches.The net effect of repeated local refinement is a surface composed of a collection ofoverlays at different levels of refinement.Two problems remain. Although editing the surface within an overlay cannot produceboundary anomalies (using the above definition of an overlay, the only control nodes thatare allowed to move are those that will not affect the boundary), moving the surfaceimmediately surrounding an overlay will cause tears to appear at the boundary betweenChapter 2. Background^ 10Figure 2.3: A 16-patch surface with refinement and overlay control verticespatches defined at two different levels. Also, when editing takes place at one level ofsurface definition, any overlays resting within the edited area are expected to remainembedded in that area. The embedded overlays will follow editing changes only if theycan be dynamically influenced by changes in the shape of some ancestor overlay. Thisamounts to saying that their control vertices must move in accordance with the movementof the section of the surface being edited.These properties are achieved by a method called offset-referencing. The positionsof the control nodes of any overlay are defined relative to a point on the parent surfaceS[k] , rather than relative to a single fixed frame of reference defined by some externalcoordinate system. In this reference-plus-offset formulation, each control node Vi[3k.+1] ofany part of the surface, whether the root-level parent surface or an overlay at any levelof refinement, is written in the formT,[k+1] - 6[k+1] Er, ri[+1]ijChapter 2. Background^ 11where illi:j+11 is the reference position, and 61:711 is the offset vector. Both are specifiedseparately for each control node Ojk+11 in each overlay. The position of Viijk+11 immediatelyafter creating a new overlay using refinement is equal to Akatil and, by definition, thevalue of CR:7 11 is zero. Any change to the position of a control node Vr il, is stored in theoffset vector 61711 as a relative change in position from the reference pointThe,73operator El) specifies how fiV:711 is combined with OlV1 and is called the offset method.This operator can be defined as one of several kinds of operations, such as vector addition,tangent plane, skeletal frame and dynamic function methods in our implementation.Changes to the surface at any level of refinement close to the root level appear asglobal changes to the overlay surface at the current level of refinement. The current levelof the surface has its control vertices modified in accordance with changes in the referenceposition information, and this in turn affects the reference information for finer levels ofthe surface. Likewise, adjustments to the offset affect the surface at the current level ofrefinement and all finer levels.Rendering proceeds for any point on the surface using reference and offset informationat the lowest level of the tree containing that point.2.2 Object-Oriented Programming and the Waterloo C++ Spline ClassesThis section briefly introduces the main concepts of object-oriented programming (en-capsulation, inheritance, polymorphism, overloading and genericity) using examples fromthe Waterloo C++ Spline Software Package (WaSP).The promise of object-oriented languages is that code written in an object-orientedfashion is highly modular, maintainable, flexible and reusable. These advantages arisefrom the virtues of encapsulation, inheritance and polymorphism manifested in variousobject-oriented languages in the form of objects defined by classes. A good introductionChapter 2. Background^ 12to the basics of object-oriented programming may be found in [VIeyer88]. For moredetails on the specific features of C++, consult [Ellis90, 14opman90, or Stroustrup9l].An informal explanation of these concepts in the context of the design philosophy for theWaSP spline classes will be presented.Encapsulation is a fundamental aspect of object-oriented programming. Code anddata are encapsulated when related data and algorithms are tightly bound together andcan be accessed only through a well defined interface. This interface should be indepen-dent of the algorithms, data storage, and data management within the code. Encapsu-lated code provides services, but does not reveal the details of how those services arecarried out.Code and data that have been encapsulated are often referred to as an abstract datatype. An abstract data type definition is called a class in C++. An instance of a class iscalled an object.A class definition provides the template of an abstract data type, which includes data,construction, destruction, access, management, and service.The following code segment shows part of the class definition for the class NUBBasisfrom WaSP:// NUBBasis represents a non-uniform B-spline basisclass NUBBasis: public BBasis {private: // Private members can be accessed only by members// in this class or its friend classes/functions.NumberSequence knts; // knots.public:^// Public members can be accessed by all the// instances of this class.// Constructor, set knts to [0,1,-3.NUBBasis( int dimension, int order );// Destructor"NUBBasis();Chapter 2. Background^ 13// Make knts a copy of ns.void setKnots( const NumberSequencek ns );// Add the value of a knot.void addKnot( double knt, int mult=1 );// Delete the value of a knot.void deleteKnot( int i );Management and service are incorporated using code that defines the public interfacein the form of member functions. The functions setKnots, addKnot, and deleteKnotare examples of member functions that provide various services to users of a NUBBasisobject. Member data is also encapsulated in the class definition. Data can be declared tobe either public or private. Public data can be accessed and modified directly by usersof a NUBBasis object. Private data can only be accessed by the member functions ofthe given object. The variable knts is an example of a private data variable. Users of aNUBBasis object must "request service" through a call to a member function in orderto access or modify private member data. Every new instantiation of an object gets itsown unique copy of the member data variables in the class definition. Modifying a givenNUBBasis object's member data has no effect on the data values of other NUBBasisobjects. This method of access control enforces encapsulation by making it impossiblefor a program using NUBBasis objects to depend on anything other than the publicinterface. In particular, the implementation of member functions can be changed freely,as long as the original public interface is maintained.Initialization, allocation, and deallocation of objects and their corresponding memberdata are performed automatically through the use of special constructor and destructormember functions. The semantics of C++ provide rules that specify when constructorsand destructors are to be invoked. The function NUBBasis(int dimension, int order) isan example of a constructor for the NUBBasis class. The C++ statementChapter 2. Background^ 14FuncBasisBBasisI^IBezBasis NUBBasisFigure 2.4: Basis Class HierarchyNUBBasis nub_obj(8,4);defines a new NUBBasis object called nub_obj, and automatically invokes the constructorfunction, which initializes the dimension and order of the object to 8 and 4 respectively.The destructor rNUBBasisO is called whenever a NUBBasis object is destroyed eitherexplicitly by an invocation of "delete" or implicitly upon the return of a procedure inwhich the object appears as a local variable. The destructor "cleans up" by freeingmemory allocated to the object before it disappears.Another fundamental concept in object-oriented programming is inheritance. Classescan be grouped into type hierarchies using inheritance. This feature is used to definea new class, called a derived class, in terms of an existing class, which is referred to asa base class. The derived class "inherits" the base class' member functions and data.In addition to defining its own functions and data, the new class can replace "inher-ited" information, providing a natural supporting mechanism for incremental softwaredevelopment.Inheritance also provides a logical way of organizing services into several layers ofcomplexity, represented by classes in several layers of a hierarchy.' Through the use ofinheritance, the C++ hierarchy for spline basis functions is organized in several layers(Figure 2.4).'Reference from C++ Prime r[Lippman91].Chapter 2. Background^ 15Class derivation permits code to be extended with a minimum of effort and disruption.For example, the member function evaluate is defined in the class BBasis, and thus it doesnot need to be redefined as a member function in the class NUBBasis because NUBBasisis a derived class of BBasis. Inheritance and class derivation provide the ability tomodify services as well as to augment them. For example, there are no member functionsorder() and knots() in the class FuncBasis, but they do exist in the class BBasis which isderived from FuncBasis. BBasis augments the services of FuncBasis. On the other hand,both BBasis and FuncBasis have the member function evaluate(double u), however thesetwo functions have different definitions. BBasis modifies the evaluate function serviceinherited from FuncBasis.Objects that come from the same class hierarchy are permitted to act as membersof a common family, whenever this is appropriate. However, C++ requires that thedeclaration of a member function be virtual, if it will be redefined further along in ahierarchy. This redefinition of functions is called polymorphism.Sometimes it is desirable to omit a definition for a virtual function in a base class.This can be done by putting =0 after the member's declaration in place of code. Sucha function is called a pure virtual function. If a class contains a pure virtual function, itis known as a virtual class. No objects of this class type may be declared since the classcontains a gap in its definition.A derived class may provide only some of the definitions for the pure virtual functionsthat it inherits. It might omit others which would be inappropriate for it to provide. Onlywhen all pure virtual functions have been defined through a chain of class derivationsdoes it become possible to instantiate objects of a particular class.Overloading is another basic concept of object-oriented programming. It providesefficiency and compactness of syntax by allowing function names to be reused withina class. The various commonly named functions can be distinguished by the type andChapter 2. Background^ 16number of parameters passed to them. There is no need to invent different names toapply to variants of a single concept. In C++, both functions and standard operatorscan be given overloaded definitions, provided that any ambiguity can be resolved in thecontext of usage. For example, evaluate in the class FuncBasis has overloaded definitionswhich are dependent upon the type of operations.Recently, genericity has become a popular term in object-oriented programming.This term was coined in [Meyer88] to describe a controlled form of macro which is usefulin defining collections of similar classes or functions. Because C++ requires all variablesand constants to be declared with a type, it can be inconvenient to construct classesof a generic nature. Templates provide a way of getting around this inconvenience. Forexample, a class can be defined as an array of integer numbers or an array of real numbers.A class or function definition can be headed by a template list of formal tokens, whichare then used as type declarations in the definition. Thus a generic class for such arraycan be created by:template<class DATATYPE>class array {DATATYPE data;}If an instance array<int> x is declared, x will be an array of integers; if an instancearray< double> x is declared, x will be an array of double precision floating point numbers.WaSP includes a rich collection of spline types in a well-organized collection of hi-erarchies. Spline bases are defined separately from classes that assemble splines from abasis and coefficients.For extensibility, the C++ spline classes were designed to provide several levels ofinheritance so that new classes can be inserted at an appropriate level, and so thatprograms can use as general a class as possible.Chapter 2. Background^ 17TPSurf^(a container class for parametric tensor-product surfaces)LCSurf^(a base class for linear combinationtensor-product surfaces)BSurf^(a container class for basis splinetensor-product surfaces )BezSurf - - -^NUBSurf - - -^NURBSurfFigure 2.5: The hierarchy for parametric tensor-product surfacesThe goal of reusability led to the separation of the class for a basis from the classfor parametric splines. The particular basis used to build spline functions, curves andsurfaces is separated from the algorithms and data that a basis needs.The class FuncBasis is the general base class for any function basis. It would beappropriate to derive a class for trigonometric functions from FuncBasis. The BBasisclass is the base class for any basis spline. A basis spline is defined by its degree, itsknot vector, and its evaluation algorithm. The evaluation algorithm may use subsidiaryinformation (e.g., a control vertex mesh).A version of the parametric tensor-product surface hierarchy from WaSP is shown inFigure 2.5. This set of classes is used in our implementation.The class TPSurf is a container class for parametric tensor-product surfaces, fromwhich any other special parametric tensor-product surface can be derived. The classLCSurf is a base class for linear combination tensor-product surfaces, derived from theclass TPSurf. The class BSurf is a container class for basis spline surfaces, derivedfrom the class LCSurf. It contains a control vertex mesh, TupleMatrix, and two linearcombination bases in order to describe a completed basis spline surface. A pictorialChapter 2. Background^ 18representation of a BSurf object is shown in Figure 2.6.The class TupleMatrix is a matrix of vectors, which is used to describe the controlvertex mesh in a tensor-product B-spline surface. The TupleMatrix class is also definedin WaSP.More information about the above is found in [Bartels9l].Chapter 3Design and ImplementationThis chapter presents the design and implementation for two different quadtree datastructures. Both data structures are specifically devoted to representing hierarchicalB-spline surfaces.3.1 Analysis of Hierarchical Surface RepresentationsThis section describes the functional requirements of any implementation of a hierarchicalsurface, and proposes appropriate data structures for its representation.The prototypical hierarchical surface editor of [Forsey88] is limited in several ways (seeChapter 1). For example, only a bi-cubic B-spline hierarchical surface can be instantiatedand the process of adding new offset methods is not structured. This implementation,however, has served as the model for the functional requirements of a hierarchical sur-face. The operations can be divided into three groups: surface definition dealing withinstantiation, creation and evaluation; surface navigation dealing with accessing CV's;and control node operation dealing with CV attributes and storage.1. Surface definition: create a new hierarchical surface with a given dimension, order, and CV mesh. evaluate (position/derivatives) the surface at a parametric point (u,v). traverse one level overlay with a given function.19Chapter 3. Design and Implementation^ 20 traverse an entire hierarchy with a given function. generate an overlay (i.e., refine a surface locally around a given CV). increase/decrease the dimension (i.e., the number of rows/columns) of a sur-face2. Surface navigation: get the CV at the position (i,j,level)1 .(this corresponds to the Vi,[lievell in Section 2.1) get the north/south/east/west neighbour of a given CV. return neighbours of a given CV within a certain range. get the CV at the corresponding parametric location on a different level overlayfor a given CV.3. Control nodes: query/set attribute—offset vector qj—reference vector 8,3—offset method/function—visibility—colour—movability (i.e., Can the position of the control vertex be altered withoutcausing discontinuities in the surface?) get final position (for a given offset method), i.e., 17,i!.,k).1 (i,j,level) identifies a CV position in the hierarchy. level represents which level overlay this CV liesin; (i,j) represents the indexes in the m x n matrix of control vertices at that level.Chapter 3. Design and Implementation^ 21A hierarchical surface is considerably more complicated than a single tensor-productsurface. It has: multiple levels, each procedurally connected through refinement, offset vector andoffset function. levels of overlays, each containing one or more continuous spline surfaces. an m x n matrix of CV's for each fully-refined level. If the its, ^surface has anmi x ni matrix of CV's, the (i 1)3t overlay will have a (2m i — u_order + 1) x (2ni —v_order + 1) matrix of CV's. Here, u_order and v_order are the orders in the uand v parametric directions, respectively. However, depending upon the pattern ofrefinement, this matrix can be— empty,— partially filled with an arbitrary clustering of CV's (the minimum size of eachcluster is dependent upon the order and type of spline),— or full.Given the wide range of possible distribution of CV's in an overlay, the data structurechosen to represent a hierarchical surface is the quadtree since it has proven very effectivein representing rectangular clustering of two dimensional information.Briefly, a quadtree is a tree whose nodes are either leaves or have at most four children(ordered 1, 2, 3, and 4). If a node in the quadtree is not a leaf, it is called an internalnode; otherwise, it is called a leaf node. A quadtree partitions R2 into rectangular quad-rants recursively according to the similitude of the components within the domain beingrepresented. A general description of quadtrees is provided in Appendix B.Quadtrees have been used to represent images, point data, areas, curves, and surfaces.Chapter 3. Design and Implementation^ 22DeFloriani et al. ([DeFloriani82]) discuss a data structure for multilevel surface represen-tation consisting of a nested, triangulated, irregular network ([Lee and Schachter80]) thatis used for surface interpolation and can also serve as a mechanism for data compression.Gomez and Guzman ([Gomez79]) use a data structure related to the quadtree that isbased upon a recursive subdivision of the surface into four triangles of unequal size. Thisdata structure uses a process that stops when a triangle matches the surface to withina prespecified error. Carlson ([Carlson82]) describes a quadtree-based data structureused to model three-dimensional objects in computer graphics, which allows for the in-tersection of polygonal objects or other primitive shapes to create more complex objects.Wilhelms ([Wilhelms90]) utilizes octrees, the 3D equivalent of the quadtree, for fasterisosurface generation by storing summary information to prevent useless explorations ofregions of little or no interest within a volume.The various kinds of quadtree differ in: the type of data represented, the decomposition process, the resolution (variable or constant).The decomposition of the domain proceeds either by partitioning into four equalparts (regular decomposition) or into unequal parts governed by the input (irregulardecomposition). For a hierarchical surface, regular decomposition is adopted because ofthe regular subdivision of the surface by midpoint refinement. Irregular decompositionmay prove useful in a hierarchical surface with non-uniform surface refinement, but thisis left as a subject for future work.Recursive local refinement in hierarchical surfaces results in a surface composed ofspline patches with different parametric spacing. In a hierarchical surface, each overlaymay be only a subset of the full m x n array of CV's possible for that particular overlayChapter 3. Design and Implementation^ 23(i.e., some entries in the array will be null or undefined). A homogeneous region in thearray is one where either none or all of the CV's are defined and it is used for determiningthe regions in a quadtree decomposition.We consider four different approaches for using quadtree data structures to representa hierarchical surface. Each approach is characterized according to the type of datastored in each node or decomposition principle (patch definition versus CV definition),and the mechanism used to represent multiple level overlays (one quadtree per overlayversus multiple overlays per quadtree).If quadtree decomposition is governed by the distribution of patches in each hierar-chical overlay, each node in the quadtree represents one or more tensor-product B-splinepatch(es). Specifically, each leaf node in the quadtree contains one s x t control vertexmatrix2 defining one or more B-spline patch(es). Thus, adjacent nodes in the quadtreewill have multiple references to any common CV's.If quadtree decomposition is based upon a partition of control vertices in a hierarchicalsurface, each node in a quadtree stores an s x t control vertex mesh defining part or allof an overlay. This method's advantage is that no control vertex is shared. However, itmay be necessary to access several nodes in a quadtree to get one patch definition in anoverlay.To represent the multiple overlays in a hierarchical surface, each level overlay can berepresented by a separate quadtree, or the entire hierarchical surface can be stored in asingle quadtree, that is, each overlay can be stored in nodes at the corresponding depthin the quadtree. A quadtree representing only one level overlay is called a single-overlayquadtree, and one representing the entire hierarchical surface is called a multiple-overlayquadtree.In a multiple-overlay quadtree, nodes at a given level represent the corresponding level2 Here s,t >= 4 in the bi-cubic B-spline surface case.Chapter 3. Design and Implementation^ 24ompositionprinciplemethodof representationcontrol vertexdomainpatchdomainsingle-overlayquadtree implemented *multiple-overlayquadtree* implementedTable 3.1: Four kinds of quadtree data structures for hierarchical overlaysoverlay in a hierarchical surface. Every node, represented by a control node matrix andfive pointer fields, is associated with a certain part of the surface. The root node isassociated with the root level overlay of the hierarchical surface.In a single-overlay quadtree, each overlay is represented by an independent quadtreethat describes the subset of the overlay that has so far been defined by refinement of theparent overlay. Each leaf node in a quadtree representing a given level overlay describesthe subset of the 224evel /22*depth possible patches in that level. Here, depth is defined tobe the depth of the leaf node in the quadtree. All internal nodes are phantom nodes.The entire hierarchical surface structure requires as many quadtrees as there are overlaylevels.In total, there are four kinds of quadtree data structures (Table 3.1) for representinghierarchical overlays, but only two of them have been implemented.The remainder of this chapter describes how these two approaches are used to rep-resent the same hierarchical surface. Figure 3.7 illustrates the multiple-overlay quadtreerepresentation and Figure 3.8 shows the single-overlay quadtree representation.In the following, the detailed operations for forming these two quadtree structuresare explored.Chapter 3. Design and Implementation^ 25Figure 3.7: A hierarchical surface and its multiple-overlay quadtree representationChapter 3. Design and Implementation^ 26Figure 3.8: A hierarchical surface and its single- overlay quadtree representationChapter 3. Design and Implementation^ 273.2 Overview of Functional Relationships and Structures in the DesignSoftware support for hierarchical uniform B-spline patches with local refinement re-stricted to midpoint subdivision has been implemented. The system is written in C++and takes advantage of the object-oriented nature of the language. As described in theprevious chapter, C++ allows for the creation of structures that inherit functionalityfrom other structures. The first task in our object-oriented design was to decompose theproblem domain into a set of classes.The criterion of extensibility shaped the various class hierarchies to provide severallevels of inheritance. This is arranged to enable new classes to be inserted at an appro-priate level (for example, the creation of the class BSurfQuadTree derived from the classQuad Tree) such that programs can use as general a class as possible.The criterion of reusability led to the decision to separate the class for surface repre-sentations (quadtrees) from the class for hierarchical overlays. Because one might wantto add new surface representation methods into our hierarchical surface modeller, thisdesign allows for a maximal amount of code reuse.The criterion of localization shaped decisions about where in the hierarchy the classesshould be included and what mechanisms in C++ should be used to achieve certain goals.The following section examines functional relationships between classes in our design anddata structures, and provides one simple example to explain how they fit together.The organization of our hierarchical overlays provides a mechanism for the creationand manipulation of hierarchical surfaces using Bezier splines, uniform non-rational B-splines and uniform rational B-splines. The following example describes how to constructand represent the particular hierarchical bi-cubic B-spline surface shown in Figure 3.9.This surface has 3 overlay levels obtained in 3 refinement steps around Vi[T, VA} and VP).Multiple-overlay quadtree representationChapter 3. Design and Implementation^ 28Figure 3.9: A hierarchical bi-cubic B-spline surfaceChapter 3. Design and Implementation^ 29A multiple-overlay quadtree hierarchical surface (an instance of the class HierBOver-lay) begins with one overlay level representing a bi-cubic B-spline patch (surface) definedby a 4 x 4 control vertex mesh, and is represented by an instance of multiple-overlayquadtree (an instance of the class BSurfQuadTree). Each overlay at a given level of thesurface hierarchy is represented by the nodes of the quadtree at the corresponding depth.Initially, for a new surface (consisting of a single patch), this multiple-overlay quadtreehas just one root node storing the original patch definition, that is, one 4 x 4 controlnode matrix and its corresponding B-spline surface definition. Of course, each node inthe B-spline surface quadtree also contains general information found in any quadtree,such as its parent pointer, its four child pointers, the index in its parent, and so on.Before refinement, the original bi-cubic B-spline patch is represented internally in themultiple-overlay quadtree, as shown in Figure 3.10.To get the hierarchical surface representation shown in Figure 3.9, the region aroundcontrol node v) is refined to create the first overlay consisting of 4 spline patches.The modified data structure in the multiple-overlay quadtree is displayed in Figure 3.11(augmenting the data appearing in Figure 3.10).In a similar way, the control node 1/1.[1] is chosen and refined to get the second leveloverlay which also has 4 patches. The corresponding multiple-overlay quadtree represent-ing this hierarchical surface is shown in Figure 3.12.The final step in obtaining the hierarchical surface as shown in Figure 3.9, is local re-finement around the control node V2i2j. This refinement produces the desired hierarchicalsurface represented by the multiple-overlay quadtree (Figure 3.13).Single-overlay quadtree representationIn the single-overlay quadtree representation for the hierarchical surface (Figure 3.9),a separate quadtree is required for each overlay level.A hierarchical surface (an instance of the class HierBOverlay) using the single-overlayChapter 3. Design and Implementation^ 30Figure 3.10: The initial hierarchical surface in a multiple-overlay quadtreeChapter 3. Design and Implementation^ 31Figure 3.11: The hierarchical surface in a multiple-overlay quadtree after one refinementChapter 3. Design and Implementation ^ 32Figure 3.12: The hierarchical surface in a multiple-overlay quadtree after the secondrefinementquadtree data structure is constructed. This surface (containing only one level of overlay)is stored in one single-overlay quadtree list (an instance of the class BSurfQuadTreeList)to represent the entire hierarchical surface. For an initial surface consisting of one leveloverlay, the single-overlay quadtree list has only one element, a single-overlay quadtreethat stores the original surface definition (one control node matrix and its correspondingB-spline surface definition). The single-overlay quadtree and multiple-overlay quadtreehave the same quadtree class definition, except that each node in the multiple-overlayquadtree contains one u_order x v_order control node matrix, whereas a node in the single-overlay quadtree could contain up to a (2' + u_order — 1) x (2n + v _order — 1) controlnode matrix. The remaining objects have the same definition and similar functionalrelationships as in the multiple-overlay quadtree.Figure 3.14 shows the data structure for a single level single patch surface.After refining the patches around the control node VP) to create the first level overlay,Chapter 3. Design and Implementation^ 33Figure 3.13: The final hierarchical surface in a multiple- overlay quadtreeChapter 3. Design and Implementation^ 34Figure 3.14: The initial hierarchical surface in single-overlay quadtreesChapter 3. Design and Implementation^ 35a second quadtree is added to the single-overlay quadtree list (Figure 3.15).Refinement around the control node 171.[ results in the single-overlay quadtree repre-sentation shown in Figure 3.16.2]Finally, refinement around the control node V2[,2 results in the hierarchical surfaceshown in Figure 3.9 and has the corresponding quadtree representation as shown inFigure 3.17 (augmenting the data appearing in Figure 3.16).In our design, an object from the class for hierarchical overlays holds an objectfrom the class for quadtree/quadtree list as member data for surface representation. Thequadtree list is represented by a doubly-linked list of quadtrees. In the quadtree datastructure itself, there is a pointer pointing to the root node in the tree. Each node inthe quadtree has a pointer to its parent and four pointers to its children. Each nodecontains an object of class CntrlNodeMatrix as member data used to define the B-splinepatch(es) represented by the node. A pictorial representation of a HierBOverlay objectin the multiple-overlay/single-overlay quadtree structure is shown in Figure 3.18/3.19 .3.3 Functional Specification for Each ClassThis section will explore all the classes related to our hierarchical B-spline surface designand their functional specifications.3.3.1 Hierarchical Overlay ClassesA simplified version of the hierarchical structure for the class HierOverlay (Figure 3.20)shows HierOverlay, a general base class for any hierarchical overlay, HierBOverlay, abase class for any hierarchical basis spline tensor-product surface, and three leaf classes,HierNUBOverlay, HierNURBOverlay and HierBezOverlay, for hierarchical non-rationalB-spline surfaces, hierarchical rational B-spline surfaces and hierarchical Bezier splineChapter 3. Design and Implementation ^ 36Figure 3.15: The hierarchical surface in single-overlay quadtrees after one refinementChapter 3. Design and Implementation^ 37Figure 3.16: The hierarchical surface in single-overlay quadtrees after the second refine-mentChapter 3. Design and Implementation^ 38Figure 3.17: The final hierarchical surface in single- overlay quadtreesFigure 3.18: A hierarchical B-spline surface object in the multiple - overlay quadtreeChapter 3. Design and Implementation^ 39Figure 3.19: A hierarchical B-spline surface object in single- overlay quadtreesChapter 3. Design and Implementation^ 40surfaces, respectively.The HierOverlay ClassThe HierOverlay class describes any type of hierarchical overlay. The following codefragment shows key members of this class:class HierOverlay {protected:int name;// Identify this hierarchical overlay -- a unique name.public:virtual short totalLevel()=0;// Return the total number of levels of overlays in this hierarchy.virtual void traversal( HierTravFn function )=0;// Traverse this hierarchy with a given function.inline int getName() const;inline void setName( int i );// Get or set this hierarchical overlay's identification.};All the hierarchical overlay structures have some common operations, such as retriev-ing the total number of overlays in the hierarchy, or traversing the hierarchy with a givenfunction, but employ different methods to perform these operations. Therefore, we makethese methods pure virtual functions in this abstract class. This ensures a definition foreach method will be provided by one of HierOverlay's derived classes.The HierBOverlay ClassHierBOverlay is a base class for any hierarchical basis spline surface. In this and all subse-quent classes, only a selected subset of the member functions will be shown. Destructorsand some variants of other member functions designed for special cases or efficiency donot appear for the sake of brevity.Chapter 3. Design and Implementation^ 41template <class SurfaceRepresentation>class HierBOverlay : public HierOverlay {protected:SurfaceRepresentation *tree;// Pointer to the whole hierarchical data structure.RWBoolean symmetry;// Indicate whether all the operations are handled symmetrically.public:HierBOverlay( BSurfk );HierBOverlay( BSurf * );HierBOverlay( const HierBOverlayk );// Copy constructor creates an instance pointing to the same surface.short totalLevel();// Return the total number of all the overlays in this hierarchy.void updateCV( short level, int i, int j, DoubleVec vector );// Edit a CV at position (level,i,j) in the hierarchical surface.// Update its offset vector and all affected control nodes in finer overlays.void traversal( TravFn fn );// Traverse the hierarchy with a given function.void leavesTraversal( TravFn fn );// Traverse all leaves of hierarchy applying fn to each leaf node of.// the quadtree. fn returns a boolean. If the boolean is TRUE, the// traversal continues; if it is false, the traversal terminates.void nodesTraversallnLevel( short i, TravFn fn );// Traverse all nodes in the level "i" applying fn to each node.void refinement( short level, int i, int j );// Only refine where needed according to the specified CV.CntrlNodeList* CVInDownLevel( short level, int i, int j );CntrlNodeList* CVInUpLevel( short level, int i, int j );// Get a CV in the down/up level from a given CV(same u,v location).ControlNode* CVInDownPatch( short level, int i, int j );ControlNode* CVInUpPatch( short level, int i, int j );// Get a CV in the down/up patch from a given CV(same patch definition).ControlNode* CVNeighbour( short level, int i, int j, int flag );// Return north/south/east/west neighbour of a given CV// according to flag = NORTH/SOUTH/EAST/WEST.Cntr1NodeMatrix* CVNeighbours( short level, int i, int j,Chapter 3. Design and Implementation^ 42int low_i, int high_i,int low_j, int high_j );// Return given range neighbours of a given CV.ControlNode* CVNavigate( short level, int i, int j );// Return the control node at (level,i,j).DoubleVec getUVParameters( short level, int i, int j );// Get the corresponding (u,v) values in hierarchy.virtual void evaluate( double u, double v,Triple * );virtual void evaluate( double u, double v,int du,int dv,Triple * );virtual void normal( double u, double v, Triple * );virtual void curvature( double u, double v, double * );virtual void curvMaxMin( double u, double v, Triple *, Triple * );// Evaluate the surface at a given point in parametric space.inline void setSymmetry( RWBoolean value );inline RWBoolean getSymmetry();// Get or set the symmetry attribute in this hierarchy.inline BSuriQuadTree *refQuadTree() const;1;The most important member function in the HierBOverlay class is refinement. Onlyvia refinement can we get multi-level overlays in the hierarchical surface. Refinementoccurs only where it is necessary to gain finer control over the B-spline surface duringediting. Another important member function is updateCV, which allows us to edit thefinal position of a CV in the hierarchical surface. The class HierBOverlay also providesa number of basic functions including various kinds of traversal of the hierarchy, gettingthe control node via its position (level,i,j), finding the neighbour(s) of a given CV, andevaluating a point in the hierarchical surface corresponding to the point (u,v) in itsparametric space. The initially input B-spline surface is defined by its degree/order,knots and control vertex mesh.An object tree of the template class SurfaceRepresentation provides the entire hi-erarchical surface representation. In the multiple-overlay quadtree representation, thetemplate class SurfaceRepresentation is specified as the class BSurfQuadTree. In theChapter 3. Design and Implementation^ 43single-overlay quadtree representation, the template class SurfaceRepresentation is spec-ified as the class BSurfQuadTreeList. For example, if we want to declare an object xas a hierarchical surface using the multiple-overlay quadtree structure, we could specifyHierBOverlay<BSurfQuadTree> x. Similarly, if we want to declare an object xas a hierarchical surface using the single-overlay quadtree structure, we need to specifyHierBOverlay<BSurfQuadTreeList> x. All of these quadtree-related classes are de-fined in the Quad Tree class library. The class BSurf provides a general B-spline surfacedescription. It is defined in WaSP. The class ControlNode and the class CntrlNodeListprovide the control vertex and the list of control vertices representations, respectively.They are defined in the Support Classes library.3.3.2 Quadtree ClassesA version of the hierarchy for the class Quad Tree is shown in Figure 3.21.The figure shows SNTree, a general base class for an N-ary tree, and BSurfQuadTree,a class for the quadtree representing a hierarchical B-spline surface in the multiple-overlayquadtree representation, or representing one overlay of a hierarchical B-spline surface inthe single-overlay quadtree representation. Correspondingly, each BSurfQuad Tree hasits own node class definition. The node classes themselves have the same hierarchicalstructure.The SNTree ClassThe SNTree class from WaSP describes an N-ary tree data structure, each node of whichhas one parent node and any number of child nodes. The key members of this class are:class SNTree {protected:SNTreeNode *root;Chapter 3. Design and Implementation^ 44Figure 3.21: QuadTree Class HierarchyChapter 3. Design and Implementation^ 45// Pointer to the root of the tree.public:void insertRoot (SNTreeNodek newRoot);// Make newRoot the root of this tree.RWBoolean insert(SNTreeNodek parent,int childPos,SNTreeNodek element);/* Insert an element as the childPos child of parent. All currentchildren of element are discarded.Insert returns TRUE if successful, FALSE if something went wrong. */RWBoolean removeSubTree (SNTreeNodek node, SNTreeTravFn fn = NULL);/* Remove node from the tree. All of node's children are removed too.returns TRUE if successful, FALSE otherwiseEach node in the subtree is removed from the tree recursively bydoing a prefix traversal on the subtree and calling fn on each node.If no function is supplied a default routine is used. */SNTreeNode *removeSubTree (SNTreeNodek parent, int childPos,SNTreeTravFn fn = NULL);/* Remove the childPos child of parent. All of the removed node'schildren are removed as well. Returns a pointer to the removedroot of the subtree or NULL if something went wrongEach node in the subtree is removed from the tree recursively bydoing a prefix traversal on the subtree and calling fn on each node.If no function is supplied a default routine is used. */SNTreeNode *remove (SNTreeNodek parent, int childPos);/* Remove the childPos child of parent. All of the removed node'schildren remain in the tree and become children of node's parent.Returns a pointer to the removed node/NULL if something went wrong. */RWBoolean remove (SNTreeNodek node);/* Remove node from the tree. All of node's children remainin the tree and become children of node's parent.Returns TRUE if successful, FALSE otherwise. */RWBoolean moveSubTree(SNTreeNodek node,SNTreeNodek destParent,int posy;/* Move the subtree rooted at node to be the pos-th child of parent.For the operation to be successful, parent must not already have achild in that position. Returns TRUE if successful, FALSE otherwise. */RWBoolean isEmpty ();// Return TRUE if the tree is empty.RWBoolean isNodeInTree (SNTreeNode& node);// Check to see if the node is really in the tree.int whichChild (SNTreeNodek parent, SNTreeNodek node);/* Search for the child number of node in parent.If node isn't a child of parent then return -1. */Chapter 3. Design and Implementation^ 46void prefixTraversal (SNTreeTravFn fn);void postfixTraversal (SNTreeTravFn fn);/* Traverse the tree in a pre or postfix order applying fn to eachelement of the tree. fn returns a boolean. If the boolean is TRUE,traversal continues, if it is FALSE, traversal terminates. */1 ;SNTree provides many basic operations for a tree data structure, such as removal ofa node, insertion of a node, subtree movement, traversal in pre/postfix order, and so on.Since these operations are needed in all the tree data structures, we could reuse a largeamount of code if we derived the Quad Tree and Octree classes from SNTree.The SNTreeNode class from WaSP defines a node in the N-ary tree class SNTree. Itcan be inserted into trees of the type SNTree. The key members of the class SNTreeNodeare:class SNTreeNode {protected:int numChildren;SNTreeNode **children;// Pointers to the children of this node.SNTreeNode *parent;// Pointer to the parent of this node.public:SNTreeNode();SNTreeNode(const SNTreeNode& n);SNTreeNode(int numchildren);// The third constructor constructs a node with the specified number of children.RWBoolean hasChildren(void) const;// Return true if the node has any children, false otherwise.inline SNTreeNode *getParent(void) const;// Return the parent of this node.virtual SNTreeNode *getChild(int i) const;// Return the ith child of this node.inline int getNumChildren(void) const;// Return the number of children this node can accommodate.Chapter 3. Design and Implementation ^ 47int growNumChildren(int newNumChildren);// Increase the number of children this node has to newNumChildren.// newNumChildren must be larger than the position of the last// non-NULL child. Returns old numChildren.;The class SNTreeNode holds basic information needed for a node in a tree, such asthe number of children, its parent pointer, and its child pointers. It also provides basicoperations for the node, like getting its parent, fetching one of its children, obtainingthe number of children, and judging whether or not it has children. It would be anappropriate base class for other tree node classes.The QuadTree ClassThe class Quad Tree is used to implement a general class of quadtree data structureswhich are based on the principle of recursive decomposition of space into four partitions.The key members of the class QuadTree are:class QuadTree : public SNTree {public:QuadTree();// Constructor for the empty tree.QuadTree( const QuadNodek );QuadTree( QuadNode *);QuadTree( const QuadTreek );// For copying.inline QuadNode *rootNode() const;// Get the root node in the current tree.void leavesTraversal( QuadTreeTravFn fn );/* Traverse all leaf nodes in the tree applying fn to each leaf node.fn returns a boolean. If the boolean=TRUE, the traversal continues;if it is false the traversal terminates. */void nodesTraversallnLevel( short level, QuadTreeTravFn fn );/* Traverse all nodes in the depth "level" of the tree applying fnto each node. fn returns a boolean. If the boolean is TRUE,the traversal continues; if FALSE, the traversal terminates. */;Chapter 3. Design and Implementation^ 48Since Quad Tree inherits all the operations from the class SNTree, we do not need toprovide additional operations specifically for manipulating quadtrees. In order to makeit easy for reading and using, we list prefixTraversal and postfixTraversal here again withtwo other traversal operations, leaves Traversal and nodesTraversallnLevel. Note thesemethods are simply calling the corresponding functions in the base class SNTree. SNTreealso provides another basic function rootNode to let us access the root node of a quadtree.The key members of the class QuadNode are:class QuadNode : public SNTreeNode {protected:int indexInParent;// Identify which child of its parent this node belongs to;// If it has no parent, indexInParent = -1.public:inline void setParent( QuadNode * );void putNewChild( QuadNode *, int );// Put the given node as the indexed child. Return this child.RWBoolean isLeaf() const;// Return true if the node is a leaf.inline int index() const;// Return which child of its parent this node belongs to.inline int depth() const;// Return this node's depth in the tree.};Common function members which are often used in the quadtree are listed in theclass QuadNode. This ensures they are localized and easy to read and use.The BSurfQuadTree ClassThis class implements the multiple-overlay quadtree approach for hierarchical overlays.In the hierarchical surface design, the class BSurfQuadTree is derived from the generalChapter 3. Design and Implementation^ 49class QuadTree. The data stored in each node represents some of the B-spline patches.Decomposition is based on subdividing the parametric space, which is a reflected in theoriginal surface. Resolution depends on the refinement of a surface in the multiple - overlayquadtree representation. The key members of the class BSurfQuadTree are:class BSurfQuadTree : public QuadTree {protected:** short virtualHeight;// Indicate which level contains the actual surface node.// In the single-overlay quadtree, we don't need this member.short totalHeight;// Indicate the total height in this quad tree.** int patchNoInU, patchNoInV;// Indicate how many patches are contained in the root level.// In the single-overlay quadtree, we don't need these two members.public:BSurfQuadTree( BSurf& );BSurfQuadTree( BSurf * );// Set the root node's surface to the given one, constructorBSurfQuadTree( const BSurfQuadNode&, BSurfQuadTree *tree );// Set the given node to the root node, copy its subtree** short actualHeight();// Return the actual height of the tree which represents the// different refined overlays.// In the single-overlay quadtree, we don't have this function.short height();// Return the height of the tree.BSurfQuadNode *getQuadNode( **short level, int i, int j );// Get the quadnode which patch is identified by CV (level,i,j)// In the single-overlay quadtree, we don't have the parameter - level.ControlNode* CVNavigate(**short level,int i,int j,HierBOverlay *x);// According to this control vertices's index (i,j), return its// corresponding control node.// In the single-overlay quadtree, we don't have the parameter - level.void updateCV( **short level, int i, int j, DoubleVec );// Set the double vector to a control node offset, given// index (i,j). We also need to modify all the affected// reference positions in the finer level(s).Chapter 3. Design and Implementation^ 50// In the single-overlay quadtree, we don't have the parameter - level.CntrlNodeMatrix* CVNeighbours( **short level, int i, int j,int low_i, int high_i,int low_j, int high_] );// According to this control node index (i,j) , return the// corresponding control node matrix , which index range is from// (i+low_i, j+low_j) to (i+high_i, j+high_j)// In the single-overlay quadtree, we don't have the parameter - level.CntrlNodeList*// Return a CVCntrlNodeList*// Return a CVCVInDownLevel(short level,int i,int j,HierBOverlay *x);in the down level from a given CV (same u, v location).CVInUpLevel(short level,int i,int j,HierBOverlay *x);in the up level from a given CV (same u, v location).The class BSurfQuadTree uses the member virtualHeight from the multiple-overlayquadtree structure to handle an input initial surface which is not regular (if the numberof patches in the u or v parametric direction is not 2n, phantom internal quadtree nodesare needed to obtain the desired regular decomposition). In the single-overlay quadtreestructure, this member is not needed since it is identified in the class BSurfQuadNode inorder to merge different patches during refinement. The members virtualHeight, patch-NoInU and patchNolnV are used to identify phantom internal nodes in the multiple-overlay quadtree representation. All member functions in this class support thecorresponding operations in the class HierBOverlay, no matter what kind of quadtreerepresentation is adopted.The key members of the class BSurfQuadNode are:class BSurfQuadNode : public QuadNode {protected:CntrlNodeMatrix *CVnodes;// Store the control nodes' information related to this surface patch.public:BasicControlNode *getInternalControlNode( int i, int j );// Get the corresponding internal control node in the quadtree..1Chapter 3. Design and Implementation^ 51CntrlNodeMatrix* getCntr1NodeMatrix();// Return the related control node matrix.TupleMatrix getCpFinalMat();// Get the current CV matrix which patch is defined in this quad node.1;Each node in the quadtree for representing hierarchical B-spline surfaces describesa B-spline patch(es). In other words, the class BSurfQuadNode contains the memberCVnodes, an object of the class CntrlNodeMatrix. The other function members provideoperations for surface representation and offset-referencing method. In the single-overlayquadtree, each node holds two members patchNoInU and patchNoInV to store the actualnumber of patches in the u or v parametric direction, since they might not be 2".3.3.3 The Support ClassesTo take advantage of the offset-referencing mechanism and gain better offset structurein our hierarchical surface design, we define classes suitable for describing a control nodein a hierarchical surface. This definition supports various kinds of offset methods, suchas vector addition, tangent plane, skeletal frame and dynamic function. A version of thehierarchy for a control node class is shown in Figure 3.22.The key members of the base class BasicControlNode are:class BasicControlNode {private:Chapter 3. Design and Implementation ^ 52void setCpDerived( DoubleVec vector );// Set the control node's derived position.protected:DoubleVec CpDerived;// Obtained by subdivision from parent.DoubleVec *CpOffset;// Set by editing of this control node.RWBoolean moveable;RWBoolean visible;long color;// Indicate the control node's attributes.public:BasicControlNode( unsigned dimension=3 );BasicControlNode( DoubleVec vector );// If we are given the derived vector.BasicControlNode( const BasicControlNode& );// Constructor.inline DoubleVec getCpDerived() const;// Get the control node's derived position.inline DoubleVec getCpOffset();void setCpOffset( DoubleVec vec );// Get or set the control node's offset vector.BasicControlNode& operator=( const BasicControlNodet x );// Set "x" to the current BasicControlNode.BasicControlNode copy() const;// Make a copy for the current control node.RWBoolean getBooleanFlag( CntrlNodeFlag flag );void setBooleanFlag( CntrlNodeFlag flag, RWBoolean value );// Note the definition : enum CntrlNodeFlag {VISIBLE, MOVEABLE}.long getAttribute( CntrlNodeAttr attr );void setAttribute( CntrlNodeAttr attr, long value );// Note the definition : enum CntrlNodeAttr {COLOR}.virtual DoubleVec getCpFinal();// Use the offset method to calculate the final CV position.;The most important member function in the class BasicControlNode is getCpFinal.This function calculates the control node coordinates from A j, ^and ®.Chapter 3. Design and Implementation^ 53The class BasicControlNode is the type for the private control node. It contains thefollowing information: reference position (obtained by subdivision from the parent patch), offset vectca. pointer, how to get a reference position, how to get/reset an offset vector, how to get/set an attribute (attr_name,value), how to calculate a final position (apply offset method to offset).The class ControlNode is used as the type for the public control node in the application,and contains more information that is not in a BasicControlNode: a pointer to the hierarchical surface that contains the node, which level overlay of the hierarchy contains the node, the node's position (i,j) in the current level, an internal/private control node object.The key members of the class ControlNode are:class ControlNode {private:int ith, jth;// Represent the control node's position in one level surface overlay.short level;// Represent which level of the hierarchy the control node lies in.HierBOverlay *surface;// Identify which hierarchic surface this control node lies in.BasicControlNode *node;// The basic control node information responds to this Control Node.Chapter 3. Design and Implementation^ 54public:ControlNode copy() const;// Copy the current control node.ControlNode operator=( const ControlNode& a );// Should point to the same node as BasicControlNode.inline HierBOverlay *getSurface() const;// Get which hierarchical surface this control node lies in.IntVec getPosInHier();// Get the control node's position (i,j,level) in the hierarchy.inline short whichLevel() const;// Get which level of the hierarchy this control node lies in.inline BasicControlNode *getControlNode() const;// Get the internal control node.DoubleVec getCpFinal();// Get this control node's final position in world coordinate frame.DoubleVec getCpDerived();// Get this control node's reference position in world coordinates.DoubleVec getCpOffset();// Get this control node's offset vector in world coordinates.RWBoolean getBooleanFlag( CntrlNodeFlag flag );void setBooleanFlag( CntrlNodeFlag flag, RWBoolean value );long getAttribute( CntrlNodeAttr attr );void setAttribute( CntrlNodeAttr attr, long value );I;The key members of the class AdditionCntrlNode for the addition offset method (de-rived from the class BasicControlNode) are:class AdditionCntrlNode : public BasicControlNode {public:DoubleVec getCpFinal();// Calculate a control node's final position via the addition offset method.};The addition offset method applies vector addition to calculate the final position ofthe control node rather than the virtual calculation getCpFinal.Chapter 3. Design and Implementation^ 55The key members of the class Tangent0117-11VodefOrthetangent plane offset method(derived from the class BasicControlNode) are:class TangentCntrlNode : public BasicControlNode {private:DoubleVec Uij, Vij, Nij;// Tangent plane is defined by the two partial derivative: Uij, Vij;// Nij is the normal to this tangent plane, i.e. Uij X Vij.void setTangentPlane( DoubleVec uij, DoubleVec vij );// Set the tangent plane for this offset method.public:TangentCntrlNode( DoubleVec vector, DoubleVec du, DoubleVec dv );TangentCntrlNode( const TangentCntrlNodek );// ConstructorTupleVec getTangentPlane();// Get the tangent plane for this offset method.DoubleVec getCpFinal();// Get a control node's final position in the world coordinate frame.} ;This class calculates the position of a CV using a local coordinate frame taken fromthe parent overlay and an offset interpreted as a position in that local frame.The key members of the class FrameOffset for the skeletal frame offset method (de-rived from the class BasicControlNode) areclass FrameOffset : public BasicControlNode {private:STransformLinHandle *frame;// Store the frame.public:FrameOffset( int dim = 3 );FrameOffset( DoubleVec vector );// Default constructor containing an identity transformation matrix// of the supplied dimension.FrameOffset( const DoubleGenMatk basis, DoubleVec vector );Chapter 3. Design and Implementation^ 56FrameOffset( const DoubleGenMat& basis, const DoubleVeck origin,DoubleVec vector );FrameOffset( const FrameOffset& v );FrameOffset( STransformLinHandle *x, DoubleVec vector );FrameOffset( const STransformLinHandle& x, DoubleVec vector );// Constructorvoid setBasis( const DoubleGenMatk newBasis );// Use this new matrix as the basis matrix for this frame.// Here the basis matrix is for a linear transformation, not a spline basis.void setOrigin (const DoubleVeck newOrigin);// Use this new DoubleVec as the origin for this frame.DoubleGenMat getBasis (void);DoubleVec^getOrigin(void);// Return the basis vectors and the origin.inline STransformLinHandle* getFrame();// Get the frame for this control node.DoubleVec getCpFinal();// Apply the linear transformation to basic control node and// get the control node's final position.;This class provides the coordinate frame and the method for getting the control nodefinal position in a global coordinate frame.The key members of the class GeneralOffset for the user-defined dynamic offsetmethod (also derived from the class BasicContmlArode) are:class GenericOffset : public BasicControlNode {private:FuncFromFunction *function;public:GenericOffset( FuncFromFunction *f, int dimension=3 );GenericOffset( FuncFromFunction *f, DoubleVec vector );DoubleVec getCpFinal();// Apply the generic function to the basic control node and// get the control node's final position.1;The class FuncFromFunction is a user-defined function based on a C++ function.Chapter 3. Design and Implementation^ 57BasicControlNode *^BasicControlNode*BasicControlNode *^BasicControlNode* BasicControlNode *BasicControlNode * •••BasicControlNode *^BasicControlNode*^BasicControlNode *Figure 3.23: The Control Node Matrix StructureThe class CntrlNodeMatrix represents the control node mesh of a B-spline surface. Inthe class CntrlNodeMatrix, each element is a control node pointer (Figure 3.23). Thisclass is used for space- and time-efficiency, especially when updating the offset vectoror reference position for a control node. All the references to this control node objectshare the same data, thus it is not necessary to update the different control node objectsrepresenting the same control node. Operations on a control node include obtainingits CpDerived reference vector (M), Cp0ffset offset vector (On, CpFinal coordinates(0,3k.), and its attributes (such as moveable, visible and colour).CntrlNodeMatrix also provides basic operations on the matrix, such as: how to set one element in the control node matrix, how to update its offset vector in an element, how to get its subMatrix, how to insert/delete the new rows or columns in a control node matrix, how to get an element, row number, and column number.The above are primitive classes which are used in the hierarchical surface design. Thenext chapter will examine the space- and time-efficiency for basic operations provided byeach of those classes. 111 •••••Chapter 3. Design and Implementation^ 583.4 Design ReviewIn the above, two kinds of quadtree data structures have been proposed as representationsfor hierarchical B-splines surfaces. Both of these maintain the nature of the surfacehierarchy. It is easy to understand this design and implement hierarchical B-splinessurfaces via such quadtree data structures. The C++ classes for hierarchical splines inour design have the following characteristics: multiple surface support better offset structure rational/non-rational uniform refinement (midpoint subdivision) compatible with the spline formulation for curves, surfaces and volumesThis system can be used to create a new hierarchical surface given the size, degree,and CV mesh. That is, it supports arbitrary order B-splines, and has the ability toincrease/decrease the number of rows/columns in the root-level surface.Our design and implementation is still incomplete at present. For example, onlymidpoint subdivision is used. Whenever multi-level editing3 is executed, all affectedcontrol nodes in finer overlays are updated immediately. From the time-efficiency pointof view, we could buffer edited control nodes at a certain level, then update their offsetsat that level and all affected control nodes in finer overlays at the same time whennecessary. This would save a lot of time when doing multi-level editing in a hierarchicalsurface. In the next chapter, this point will be further discussed during the examinationof performance.3When editing takes place at one level overlay of surface definition, any finer overlays resting withinthe edited area will follow editing changes, which amounts to saying that their control vertices will movein accord with the movement of the edited CV. Also refer back in Section 2.1.Chapter 4Storage and Performance AnalysisOne of the primary motivations for using a quadtree data structure to represent hierar-chical B-spline surfaces is to reduce the storage requirement via the use of aggregationof homogeneous quadtree nodes. This chapter assesses the space- and time-efficiency ofthis design.4.1 Storage BenchmarksThis section examines storage costs of two quadtree representations for a hierarchicalsurface and compares them in the best/worst case, respectively. The "average" storagerequirement for representing a hierarchical surface will not be fully explored becauseof the difficulty of determining what the "average" case is. To evaluate the quadtreerepresentation, the two approaches will be compared with each other, and with the rep-resentation used in the prototype hierarchical surface editor. Bi-cubic B-spline surfacesare taken as an example to assess storage costs for these representations.In the prototype hierarchical surface editor, it is necessary to represent six neighboursof a control node. If we define that each pointer needs Mpointer bytes of memory, this costs—a fixed 6Mpointer- pointer bytes of memory (6 pointers to north, south, east, west, up and downneighbour, respectively). Suppose that Ncv is the number of control nodes in a hierar-chical surface, in total, the storage overhead for a hierarchical surface is 6MpoinierNCVbytes.59Chapter 4. Storage and Performance Analysis^ 604.1.1 Storage Analysis in the Single-overlay Quadtree RepresentationThe single-overlay quadtree approach uses a separate quadtree to represent each levelof overlay in the hierarchical surface. The number of nodes required for each quadtree(i.e., for each level of overlay) depends upon the extent that the level has been defined.When a new level is initiated, the quadtree nodes at different levels are generated. Asfurther refinement occurs at this level, every four sibling leaf nodes in the quadtree thatcontain only non-null references to CV's are coalesced into a parent node that containsa CV matrix containing all of the pointers to CV's in its children. This parent node isconverted into a leaf node and its children are deleted. Such processing proceeds untilno four homogeneous sibling leaf nodes exist in the quadtree. When this level is fullyrefined (i.e., all possible CV's are generated), the quadtree evolves to one that has onlya single root node containing a CV matrix with all the CV's at that level. Because eachnode in the quadtree contains five pointers (4 pointers to its children and 1 pointer toits parent), it needs 5Mpoinier bytes of memory in total. Here, an internal node in thequadtree does not contain a CV matrix but simply contains 5 pointers. Each leaf nodein the quadtree holds a CV matrix in addition to 5 pointers. The size of this CV matrixis initially 1 x 1 but as nodes are coalesced (described above), this matrix can grow toa size that encompasses all the CV's at this level. If there are N node quadtree nodes forthe entire hierarchical surface, the storage overhead for quadtrees alone is 5Mpointer N nodebytes.In the single-overlay quadtree representation, the storage requirement is minimal whena hierarchical surface is fully refined. In that case, if we define that level is the number ofoverlays in a hierarchical surface, the storage requirement is NcvMpointer + 5Mpoinier *levelbytes because each single-overlay quadtree contains only one node. If the hierarchicalsurface is not fully refined, it is necessary to add some internal nodes in order to reach allChapter 4. Storage and Performance Analysis^ 61leaf nodes from the root node. Each internal node needs 5 M.— pointer bytes of space. Thisstorage cost depends upon refinements of the hierarchical surface. Suppose that Nu is thenumber of CV's in the u parametric direction at the root level, N„ is the the number ofCV's in the v parametric direction at the root level. In the worst case, when every lowestinternal node has three leaf nodes , the storage overhead is 5Mposnt er "Y. 12 ^,_ 12 A level +ilogmax(Nubytes.In the single-overlay quadtree representation, if an initial input surface does not con-tain the 2" * r CV mesh required by a regular decomposition, the size of the CV matrixneeds to be stored in every node of the quadtree so that during a refinement operation,it is possible to tell when a leaf node becomes a candidate for merging with its siblingnodes. Though such information can be calculated, two extra fields in each node willsave a lot of execution time. Suppose that M— int eg er represents the size of an integer,this requires 2M.— integer Nn ode bytes extra space for single-overlay quadtrees representing ahierarchical surface if each field needs M— integer bytes of memory.4.1.2 Storage Analysis in the Multiple -overlay Quadtree RepresentationIn the multiple-overlay quadtree approach, a single quadtree stores all the CV's for theentire hierarchical surface. The storage requirement for a multiple-overlay quadtree is5Mpo inter Nn ode bytes if there are Nuode quadtree nodes in this multiple-overlay quadtree.The number of nodes required for such a quadtree depends upon how many patchesare in all levels of a hierarchical surface. When a new level initiated, a number' ofnew quadtree nodes are generated. Every refinement at this level generates more nodes.Each leaf node in the quadtree holds one 4 x 4 CV matrix defining one bi-cubic B-splinepatch. Thus, it will require 16Mpointerpointer + 5Mpointer bytes of memory for each leaf node. Tospeed up processing and evaluation in the "leaf" node, the CV matrix in each internal1 4, 8, or 16, depending upon where refinement occursChapter 4. Storage and Performance Analysis ^ 62level No. of control nodes No. of overhead pointers inoriginal editor single quadtree multiple quadtree0 16 96 23 211 25 150 32 842 49 294 56 3363 121 726 128 13444 361 2166 368 53765 1225 7350 1232 215046 4489 26934 4496 860167 17161 102966 17168 3440648 67801 406806 67808 13762569 265225 1591350 265232 550502410 1054729 6328374 1054736 22020096Table 4.2: Storage overheads for a fully refined surface in three kinds of data structuresnode is retained (defining a patch at other than the lowest level). A storage overheadof 21 Mpointer Nnode bytes exists just for the multiple-overlay quadtree. In such a datastructure, the worst case for storage overhead occurs when a multiple-overlay quadtree isfull, i.e., each level in the hierarchical surface is fully refined. Each control node requiresnearly 21Mpointerpointer bytes of extra space because each control node affects almost 16 patchesof a hierarchical surface and Nnode almost equals Arcv.In the multiple-overlay quadtree representation, if an initial input surface does notcontain 2n * 2n patches required by a regular decomposition, it is necessary to add somevirtual patches' (implicitly) in the initial input surface to make regular decompositionpossible in the patch domain. That is to say, some phantom internal nodes' are createdto reach the root overlay. The memory cost for this is low because it does not add anyextra fields into the nodes in the quadtree.2Virtual patch means it is undefined in the initial surface.3A phantom internal node is an internal node which does not contain a CV matrix.Chapter 4. Storage and Performance Analysis^ 63level No. of CV representativecase No. of overhead pointers in each levelprototype editor single quadtree multiple quadtree0 16 M 96 23 (1.44 / CV) 21 (1.31 /CV)1 25 MEMO 150 32 (1.28 / CV) 84 (3.36 / CV)2 25 150 133 (5.32 / CV) 84 (3.36 / CV)11111MO3 25 150 140 (5.6 / CV) 84 (3.36 / CV)4 25 150 147 (5.88 / CV) 84 (3.36 / CV)5 25 150 154 (6.16 / CV) 84 (3.36 / CV)6 25 150 161 (6.44 / CV) 84 (3.36 / CV)7 25 150 168 (6.72 / CV) 84 (3.36 / CV)8 25 150 175 (7 /CV) 84 (3.36 /CV)9 25 150 182 (7.28 / CV) 84 (3.36 / CV)10 25 150 189 (7.56 / CV) 84 (3.36 / CV)Table 4.3: Storage overheads for a sparsely refined surface in three kinds of structuresChapter 4. Storage and Performance Analysis^ 64the nth lowest level(containing 2 "lx 2 '1 CV matrix) the 3rd lowest level(containing 4 x 4 CV matrix)the 2nd lowest level(containing 2 x 2 CV matrix)the 1st lowest level(containing 1 x 1 CV matrix)Figure 4.24: The definition for the nth lowest level in a quadtree.Table 4.2 shows the storage overhead for a fully-refined hierarchical surface usingthe three different data structures. Table 4.3 shows the storage overhead for a sparselyrefined hierarchical surface' using the three different data structures.Comparing the storage requirements of the two quadtree representations, there is nodoubt that a single-overlay quadtree surface representation is the best when a hierarchicalsurface is fully refined or when the patches of a hierarchical surface are clustered. In thiscase, the multiple-overlay quadtree representation requires a lot more storage than thesingle-overlay quadtree representation. On the other hand, the best case for the multiple-overlay quadtree representation (when all patches in a hierarchical surface are scatteredin different areas) is the worst case for the single-overlay quadtree representation, sinceit will contain a large number of phantom internal nodes. As shown in Table 4.3, whenthe patches of a hierarchical surface are extremely sparse or scattered, the single-overlayquadtree representation has the highest storage overhead.To avoid the worst case of storage overhead in the single-overlay quadtree represen-tation, the following strategy could be adopted: whenever a node lies in the nth lowest4This is almost the worst case for single-overlay guadtrees.Chapter 4. Storage and Performance Analysis ^ 65depth of a quadtree (as shown in Figure 4.24) and satisfies the relationship:2n-1 * 2n-1 — #Ncv < 7 * #Nnodel 5(i.e., the cost of the quadtree nodes exceeds the number of null entries in all the children)all the subtrees are coalesced into one 2n-1 x 2n-1 CV matrix. This matrix may containsome null entries corresponding to undefined CV's, but the number of null entries will beless than the total storage required for all of the descendant nodes generated accordingto homogeneousness. Another way to avoid the worst case would be to utilize both thesingle-overlay quadtree and multiple-overlay quadtree representations, i.e., when a hier-archical surface is sparsely refined, adopt the multiple-overlay quadtree representation;otherwise, use the single-overlay quadtree representation. These methods have not beenimplemented, and are the subject of future work.4.2 Performance BenchmarksThis section describes and analyzes the performance of representative operations on ahierarchical surface stored in two kinds of quadtree data structures.To get an intuitive feeling of their performance, primitive operations in a hierarchicalsurface were tested to give their execution times when using one of the two differentquadtree data structures. At the same time, we analyzed where the execution time wasspent in both quadtree representations.The following primitive operations on a hierarchical surface were examined: CV navigation.— getting the CV at a given position,— getting the north/south/east/west neighbour of a given CV,5 Here, #Ncv is the number of generated CV's in this node's CV matrix; #N„ode is the number ofhomogeneous nodes for this node's descendants.Chapter 4. Storage and Performance Analysis^ 66—getting neighbours of a given CV within a certain range,—getting the CV at the corresponding parametric location on a different leveloverlay for a given CV. Various traversals— traverse one level overlay with a given function.— traverse an entire hierarchy with a given function. Evaluate the surface at a given point Refinement Multi-level editing4.2.1 CV NavigationGetting the control node with given indexes (level, i,j) from a hierarchical surface is a basicoperation, and its execution time 6 in a quadtree data structure is compared with theexecution time of retrieving a control vertex with given indexes (i,j) from a TupleMatrix(a standard two dimensional array where each element is a vector). Execution time for getting a control node from a TupleMatrix is 7 microseconds; Execution time (in microseconds) for getting a control node from a hierarchicalsurface in the multiple-overlay quadtree representation is shown in Table 4.4. Execution time? (in microseconds) for getting a control node from a hierarchicalsurface in the single-overlay quadtree representation is shown in Table 4.5.6The execution time was measured on a Silicon Graphics IRIS 4D crimson workstation.7This result comes from a sparsely refined hierarchical surface (the worst case).Chapter 4. Storage and Performance Analysis ^ 67Overlay level 1 2 3 4 5 6 7 8 9 10Execution time (psec) 34 39 40 60 72 82 90 101 112 122Table 4.4: Execution time for getting a CV in the multiple-overlay quadtreeOverlay level 1 2 3 4 5 6 7 8 9 10Execution time (fisec) 43 44 47 70 78 87 101 112 122 131Table 4.5: Execution time for getting a CV in single-overlay quadtreesIt will take more time to get one control node from a hierarchical surface than froma TupleMatrix even when the control node lies in the root level overlay, because thereare some extra function calls and pointer operations (e.g., getting the quadtree from thehierarchy, getting the root node from the quadtree, getting the control node matrix fromthe root node, and getting the control node from the matrix).Table 4.4 and Table 4.5 show that when going to a finer level to search for the controlnode, an extra 10 microseconds might be required. Most of the extra time is used bybit-shift operations to get the proper node in a quadtree for the given indexes (level,i,j).In a multiple-overlay quadtree, execution time has a linear relationship with level of thecontrol node. The upper bound on execution time for getting a control node is O(level)in the multiple-overlay quadtree representation.If we define that Ti„ei is execution time for getting the proper quadtree representinga certain level overlay; depth is the level of the quadtree that the node, where the CVat (level, i , j) is contained, lies in, then in the single-overlay quadtree representation, thetime required to get the control node (level,i,j) is bounded by O(depth) -I-Ti„ei. It isnecessary to first go to the quadtree representing the level (which costs Ti„, / executiontime); and then in the corresponding quadtree, it is necessary to go to the node thatChapter 4. Storage and Performance Analysis^ 68Level CV North CV South CV West CV East CV1st 34 40 27 36 332nd 39 40 30 35 373rd 40 35 29 35 314th 60 64 28 43 51Table 4.6: Execution time (in psec) for getting a CV and its neighbour in the multi-ple-overlay quadtree representationcontains the required control node. This takes O(depth) execution time. In total, itsexecution time is bounded by O(depth)8 .For comparison, if a single TupleMatrix is used to represent each level of a hierarchicalsurface, approximately 3 psec is required to obtain a proper TupleMatrix (i.e., a properlevel) and 7 psec is required to retrieve a CV from the TupleMatrix. In total, it takesabout 10 psec.Getting the north/south/west/east neighbour of a control node with given indexes(level,i,j) is another primitive operation in a hierarchical surface. This takes almost thesame execution time as getting the control node with given indexes (level,i,j) except thatit has one extra "add" operation (i + 1 or i — 1 or j -I- 1 or j — 1). For both quadtreerepresentations, this point is the same. Table 4.6 shows the execution time for gettinga control node and its north/south/west/east neighbour in the multiple-overlay quadtreerepresentation of a hierarchical surface. Table 4.7 shows the execution time for gettinga control node and its north/south/west/east neighbour in the single-overlay quadtreerepresentation of a hierarchical surface.Getting the control node(s) at the corresponding parametric location of a differentlevel overlay from a given CV (level,i,j) is an elementary operation. No matter what kindof quadtree representation is adopted, this has the same upper-bound execution time as8 Tlevel is far less than 0(depth) and ignored.Chapter 4. Storage and Performance Analysis^ 69Level CV North CV South CV West CV East CV1st 43 45 47 47 482nd 44 49 48 46 503rd 47 51 52 51 534th 70 78 74 76 75Table 4.7: Execution time (in psec) for getting a CV and its neighbour in the sin-gle-overlay quadtree representationLevel position CV CV in the parent patch CV in the child patch1st (2,1) 34 - 602nd (1,1) 39 70 653rd (2,2) 40 364 604th (2,2) 60 366 -Table 4.8: Execution time (in psec) for getting a CV and the CV's in its parent' childpatch in the multiple-overlay quadtree representationgetting the control node with given indexes (level,i,j) except that some extra calculationis required to get the corresponding control node index(es) (develn, in , j„) in the parent orchild patch of a given CV. Table 4.8 shows the execution time for getting a control nodeand the corresponding CV(s) in the parent and child patches of a hierarchical surfaceusing the multiple-overlay quadtree representation.'Another often-used operation is to get neighbours of a given control node (level,i,j)within the index range [(inrin)imin), (imax)imax)]. Suppose the execution time for gettingone control node with given indexes (level,i,j) is Tcv. Then, its upper bound executiontime will not be more than 0((imax — imin)(imar min)T CV) using either of the twoquadtree data structures.9Table 4.8 has two testing cases which take 364 and 366 psec execution time, because the controlnode lists are obtained in these two testing cases instead of one control node. The control nodes in thecontrol node list form a convex hull containing the given CV.Chapter 4. Storage and Performance Analysis^ 70All of the above operations involve a CV navigation.4.2.2 Traversals in a Hierarchical SurfaceNext, we describe traversal, another kind of elementary operation in a hierarchical sur-face. In our design, we can traverse an entire hierarchy or one level overlay of a hierarchywith a given function.In the multiple-overlay quadtree representation, execution time for traversing an entirehierarchy has a linear relationship with the number of nodes in the quadtree because everynode needs to be visited and has the given function applied to it. Execution time fortraversing a certain level of a hierarchy represented by a multiple-overlay quadtree includesvisiting all the nodes above this level (since it is necessary to first visit nodes above thelevel in order to reach nodes in the desired level) and applying the given function to allthe nodes at this level. Assume that Nnode is the number of nodes in a multiple-overlayquadtree, NnodeAboveLevel is the number of nodes above the specific level of a hierarchy ina multiple-overlay quadtree, NnodeInLevel is the number of nodes at the specific level of ahierarchy in a multiple-overlay quadtree, and Tfun, is execution time for applying the givenfunction to each node. Then execution times for traversing an entire hierarchy or onelevel of a hierarchy are bounded by O(NnodeTfunc) and 0(NnodeAboveLevel NnodeInLevelTfunc),respectively.In the single-overlay quadtree representation, the execution time for traversing anentire hierarchy is related to the number of nodes and the number of leaf nodes inthe quadtrees because it is necessary to visit every node and apply the given functionto every leaf node. Assume that Nnode is the number of nodes in all single-overlayquadtrees, &ay e, is the number of leaf nodes in all single-overlay quadtrees, NleavesInOneTreeand NnodeInOneTree is the number of leaf nodes and the number of all nodes in one singlequadtree representing a certain level overlay of a hierarchical surface in the single-overlayChapter 4. Storage and Performance Analysis^ 71quadtree representation. Then execution time for traversal in a specific level overlay of ahierarchy represented by a single-overlay quadtree data structure includes the executiontime to reach the proper single-overlay quadtree describing that level overlay and totraverse this single-overlay quadtree. Execution times for traversal in an entire hierarchyor one level overlay of a hierarchy are bounded by 0(Nnode + Niea„„Tfitnc ) and O(level+NleavesInOneTree Tfunc + NnodelnOneTree), respectively.4.2.3 EvaluationEvaluating a point in a hierarchical surface is also a primitive operation (including normalvector and curvature evaluation). Because extra storage has been used to retain theR[k] at each level, in the multiple-overlay quadtree representation, execution time forevaluating a point is equal to the execution time required to reach the leaf node thatcontains this point plus the execution time required to evaluate a point in a patch (whichis defined by the leaf node).In the single-overlay quadtree representation, it is necessary to first get a CV matrixwhich defines a patch containing the point. Such an operation may involve several nodesof a quadtree, thus having a longer execution time than when using the multiple-overlayquadtree representation. In total, when using the single-overlay quadtree representation,the execution time for evaluating a point is equal to the execution time for getting therequired CV matrix plus the execution time for evaluating the point in the patch definedby the CV matrix.For this kind of evaluation operation, the multiple-overlay quadtree representation canbe better than the single-overlay quadtree representation.Chapter 4. Storage and Performance Analysis^ 724.2.4 RefinementRefinement is a crucial operation to hierarchical surfaces. The execution time for refine-ment of a hierarchical surface in two different quadtree data structures will be analyzed.First, it takes some time to judge whether a given CV (level,i,j) can be refined inthe current level overlay. If not, it is necessary to go to the parent level to get thecorresponding point, repeating this procedure until a proper refinable point is found.Such judgement involves deciding whether at most(2 Ru_order/21/2-1 -I- u_order mod 2)(2 r[v_order/2]/21 + v_order mod 2)patches exist at the current level. Here, u_order and v_order are the B-spline orders inthe u and v direction of parametric space, respectively.After the proper refinable point in a hierarchical surface is obtained, we need to refinea surface that contains at most(2 i[u_order/2]/2] + u_order mod 2)(2 r[v_order/1]/2 -1 + v_order mod 2)patches. During this refinement, space has to be allocated for every recently createdcontrol node in the finer level if it does not already exist in the finer level overlay. In theworst case, it is necessary to allocate space for (2(2 i[u_order/ 2]/21 + u_order mod 2) +u_order — 1)(2(2 [[v_order/2]/21 + v_order mod 2) + v_order — 1) control nodes, and setpointers to those objects appropriately.All of the above steps in both quadtree surface representations have to be executed,and thus both representations have almost the same execution time for these operations.To decide whether to-be-created control nodes have existed in the lower level overlaytakes some time in the multiple-overlay quadtree representation because each controlnode might lie in u_order * v_order patches, i.e., u_order * v_order nodes of a multiple-overlay quadtree. Average judgement involves (u_order * v_order)/4 nodes of a multiple-overlay quadtree. However, this execution time still has a constant upper bound 0(1),Chapter 4. Storage and Performance Analysis ^ 73although this constant is a little larger. In the multiple-overlay quadtree representation,one refinement operation takes between 0.5 and 1 seconds'.In the single-overlay quadtree representation, one additional step for refinement is stillrequired, i.e., merging every cluster of four nodes into one larger node in the quadtree.In this step, each newly-created node has to check whether it can be merged with threeneighbours. If it can be merged, it is necessary to change its phantom parent node toa leaf node, set the corresponding control node pointer matrix properly, and delete theoriginal four leaf nodes in the quadtree. This procedure is repeated for the newly-createdleaf node until it can not be merged. This recursive step will take considerable executiontime.For a refinement operation, execution time in the multiple-overlay quadtree represen-tation is less than in the single-overlay quadtree representation.4.2.5 Multi-level EditingEditing a hierarchical surface interactively is an important task in our design. Hierar-chical B-spline refinement and offset-referencing provide a mechanism that allows ma-nipulation of the surface regardless of any previous refinement of the surface. A changeto the surface at any level of refinement closer to the root (level 0 through level k — 1)changes _Mk] altering the shape of the surface. This, in turn, changes the reference infor-mation for any recursively defined overlay SR+ 11 , percolating the effect down through thehierarchy. Similarly, changes to S[k], effected through the offsets at that level, influencethe shape of the surface S[k] and all finer levels of overlay within the affected region. Inour implementation, this is a non-trivial operation because each affected control node(for which d[i] or RN has been changed) lying in a non-leaf node of the quadtree willaffect (u_order +1)* (v_order +1) control nodes in the next finer level. If a control node10 Run on a Silicon Graphics IRIS 4D crimson workstation.Chapter 4. Storage and Performance Analysis ^ 74close to the root level is edited and a hierarchy contains a lot of overlays which mightbe affected, it will take considerable time to update an entire hierarchical surface. Thisoperation in the two kinds of quadtree surface representations has the same executiontime bound because each edited CV will affect the same number of CV's in the finer leveloverlays.It is better to adopt the "lazy evaluation" method to deal with this situation in orderto speed up execution. That is to say, some flag could be set to indicate which controlnodes need updating in the future, but those control nodes are not actually updated untilthey are needed.Up until now, we have roughly examined the space/performance efficiency in ourobject-oriented design for hierarchical B-spline surfaces in two different quadtree datastructures. The next chapter will look at what can be improved in the future.Chapter 5Conclusion and Future WorkThis chapter briefly summarizes the design for hierarchical surface representations anddiscusses what can be further studied in the future.5.1 ConclusionSurface representations are important in the domains of computer graphics, geometricmodelling, image processing, geographic information systems and robotics. The hierarchi-cal overlay surface is proposed as a general, flexible, space-efficient surface representation.It is coupled with a hierarchical data structure, the quadtree, in order to further reducememory requirements and to keep its time-efficiency via the nature of homogeneous hi-erarchies. In this thesis, two object-oriented schemes based on quadtree data structuresfor the representation of hierarchical B-spline surfaces have been presented. The schemeshave the following advantages: They keep all the characteristics of hierarchical surfaces, such as the reference-plus-offset feature. This represents regions as a series of overlays with differentknot spacing allowing the shape of a hierarchical surface to be modified at multiplelevels of overlay. It circumvents the effect of knot insertion for the traditionaltensor-product surface upon shape manipulation. They support multiple surface representations.75Chapter 5. Conclusion and Future Work^ 76 They provide different offset methods. They have an ability to focus on the interesting subsets of the data, which resultsin an efficient representation and improved execution time. It is easy to experiment with new types of hierarchical spline surfaces.The main algorithms for the hierarchical B-spline surface operations and its corre-sponding quadtree operations have been described in the previous chapters, and theircomplexity and memory requirements have also been discussed.Finally, we took advantage of the object-oriented nature in our implementation be-cause we aimed for flexibility, extensibility, portability and re-use in our design andcoding. C++ exhibits those properties and enables larger programs to be structured ina rational way. Therefore, our modelling tools were written in the C++ programminglanguage on SGI workstations at the GraFiC/Imager lab.5.2 Future WorkIt is clear that many questions remain. Some of them, by themselves, are topics deservingspecial attention. Others have known solutions but implementing them can neverthelessbe difficult. Thus, it is not surprising that various portions of our modelling systemare incomplete. This section briefly describes some of the problems left unsolved andextensions that would be considered useful capabilities within our modelling tools.One extension is to integrate the non-uniform refinement with the current uniformmidpoint subdivision. Thus, the more powerful NURBS could be taken as a mathemati-cal form for representing and designing both standard analytic shapes (conics, quadrics,surfaces of revolution, etc.) and free-form shapes precisely since NURBS are genuinegeneralizations of non-rational B-spline forms as well as rational and non-rational BezierCVIarea 1CV'area 2 ‘..Chapter 5. Conclusion and Future Work^ 77aria 3_.-._!_-^1'1 /- - -11-Cif -',:.‘^-..+4-i - -433 .•. j_.ar._ _._.11 -._. 011 1K11 1Figure 5.25: One non-uniform refinement case in the single-overlay quadtree structuresurfaces. In the multiple-overlay quadtree representation, this extension is easy to imple-ment to a certain degree since we only need to add two extra fields to each node in thequadtree in order to present non-uniform knots for each patch. However, a lot of diffi-culty still exists. For example, when there is a multiple-overlay quadtree representing ahierarchical surface (Figure 5.25), we cannot further refine this surface at the boundariesbetween areas 1, 2 and 3. In the single-overlay quadtree representation, such extension ismore difficult. For example, it is hard to deal with the case shown in Figure 5.25 duringthe aggregation of homogeneous nodes of a quadtree, even if they lie in the finest leveloverlay. Suppose we want to do refinements at CV1 , CV2 and CV3 according to the area1, 2 and 3 patterns, respectively.This design is constructed to easily extend to hierarchical volumes using octrees. Thisis an interesting area worth studying further.Besides these, there are still a number of interesting and attractive avenues for futurework. For example, an alternative to the quadtree representation is to use a decompo-sition method that is not regular (i.e., rectangles of arbitrary size rather than squares).This alternative has the potential of requiring less space via coalescence in a quadtree.Another interesting topic is the extension of our design to Box-splines, which haveChapter 5. Conclusion and Future Work^ 78a triangular grid in parametric space. The type of quadtree used often depends on thegrid formed by the image sampling process or surface representation. Square quadtreesare appropriate for square grids and triangular quadtrees are appropriate for triangulargrids (relating to Box-spline basis functions).Thus, there is a lot of interesting work which can still be done in surface representationwith hierarchical methods.Appendix AMathematical Background on Tensor-productB-spline SurfacesA parametric spline is defined analytically as a set of polynomials over a knot vector. Aknot vector is a vector of real numbers, called knots, in nondecreasing order; i.e.u = [uo, ui ,^uq] such that ui._1 < ui, i = 1, ..., q. A spline of order k is a Ck-2continuous polynomial of degree at most k — 1 on each interval [ui_1 , ui).The ith B-spline basis function of order k (degree k —1) for the knot vector [ui,^uj+k]is denoted Bi,k(Ui,^Ui+k; u) and can be expressed as the following recurrence relation:u - uitii±k;u) = ^Bi,k-1(Ui, 7 Ui+k-1; U)Ui+k-1 uiUi+k -^ .101:+1,k-1(Ui-1-1, • .. tti+k; u)Ui+k Ui+1Vui < u < ui+i and Bi,i (ui, ui+1 ; u) =^1 ui < U < 2.1410 otherwiseThe above equation means that the B-spline of order k in the ith span is the weightedaverage of the B-splines of order k — 1 on the ith and (i 1)st spans, each weight beingthe ratio of the distance between the parameter and the end knot to the length of thek — 1 spans. The computation of B i,k(ui, ui+k; u) involves all the knots from ui to Ui+kbut no others, since the width of support is k spans.The restrictions on the specification of a knot vector are that the same value cannotappear more than k times and that the knots must be in nondecreasing order. If the same79Appendix A. Mathematical Background on Tensor-product B-spline Surfaces ^80knot value ui occurs t times (i.e., ui = ui+1 = =^where t < k, the continuityat this knot is reduced by t — 1.Moving through the knot vector, each basis function is nonzero over a successive setof k + 1 knots. So, k m 1 knots define M + 1 basis functions that correspond to them + 1 control vertices.A degree (k, I) tensor-product B-spline surface has the form:n mS(u, v) = E Ei=0 j=0The control vertices 14,; are arranged in a topologically rectangular array called acontrol vertex mesh. Bi,k(u) and Bi,i(v) are the univariate B-spline basis functions.The rational B-spline surface representation has one more degree of freedom, weight.The degree (k,l) rational B-spline surface (in 3D) is defined as the map of a tensor-productB-spline surface in 4D:n mS(u, v) = E Ei=0 j=0EL() E7210 Bi,k( U )Bi$1 ( V ) WijVij E i1=0 E71=O Bi,k(U)Bjj(V)Wijn m= E E Ri,k;j,l(ti=0 j=0where 14,.; are the 3D control points andk(u)BB /(v)wijVii Ri,k;jj(u, v) = nEr=o ET-o BrA(u)B,,i(v)wr,sThe Ri,k;i,i(u, v) functions are the bivariate rational basis functions.For some applications, subdivision of a B-spline surface is desirable. Subdivisionmeans that a surface constructedV0,0 •^VO,n from one net of control vertices,Vm ,0 Vm,nAppendix A. Mathematical Background on Tensor-product B-spline Surfaces^81 weighted by two sets of B-splines, Bi,k and B;,1 and defined on two sequences of knots, {iii }gil-k and {iiii }70 “, respectivelycan be represented in terms ofW0,0^ ^WO,n+nl a large net of control vertices,Wm+mi . . . Wm+mi weighted by two refined sets of B-splines, BP] and B.111 and defined on two finer sequences of knots, {i/ i }rmi +k and {thi}rni +I .After refinement, the surface becomesm+m1 n+n1S(U[11 , v[1] ) = EE Bl iku[ii)Blikv[1])wiji.0 J=0which is defined by a finer control vertex meshIn our implementation, we use the Olso algorithm ([Cohen80, Riesenfeld8l, Prautzsch84,Prautzsch85, and Lee85]) for our midpoint subdivision. The re-representation of the sur-face defined by (m+1) x (n+1) control vertices [V] as a surface of (m+m 1 +1) x (n+n1 +1)new control vertices [W] is accomplished by two matrices composed of the a coefficients,[ateit] and [aright][HI= [aleft][v] [aright]Twhere14—k+1,v-1+1 • • • V5—k+1,v[V] =V5,v-1+1^•^V6,1)WA— k-I- 1,A - 1-1- 1 WA— k-1- 1,A=141;4,A-1+1Appendix A. Mathematical Background on Tensor-product B-spline Surfaces ^820I^IIIv0 u[ale f t]Figure A.26: Regions for four equal patchesas-k+1,k(1t — k 1) ...^— k +1)(15-k+1,k(11 )^as,k(p)a.),_/+1,/(A — / + 1) ... a..,„/(A — /^1)[aright]a-y-1+1,1 (A)The simplest example is derived from the uniform cubic case where each parametricrange in u and v is broken at its midpoint. This converts each patch determined by thecontrol vertices [V] into four equal patches according to the diagram (Figure A.26)[aleft][aright] =[A1] for regions I and III[A2] for regions II and IV[A1] for regions I and II[A2] for regions III and IVAppendix A. Mathematical Background on Tensor-product B-spline Surfaces^83The matrices [A1] and [A2] are given by0[A1] =1 1 0 0i 21 3 1 08 4 81^12 2 00 1 3 18 4 8[A2] =1 3 1 0g 4 80 1 1 02 20 1 3 18 4 8and1^1_ 2 2 0 0 _A more detailed treatment of this material, and computational algorithms for B-spline, Bezier, and NURB surfaces can be found in [Bartels87].Appendix BThe Definition of Quadtrees and TheirCharacteristicsA quadtree is a data structure, originally used for image representation, that is based onthe successive subdivision of the image into rectangular quadrants. It is represented by atree of outdegree 41 , where the root corresponds to the image itself and its four childrencorrespond to the northwest, northeast, southwest and southeast quadrants respectively.The root node has no parent and leaf nodes have no children. Each node in the quadtreecontains six pieces of information. The first five items are pointers to the node's parentand to its four children. The sixth piece of information describes the node itself (suchas colour, etc). Figure 3b is a block decomposition of the region in Figure 3a. Figure3c is the corresponding quadtree, which encoded image array (Figure 3b). It exploitstwo-dimensional coherence by recursively decomposing such an image into square areasof identical colour. This decomposition begins with a tree structure consisting of a singleroot node corresponding to the whole image. Unless the image is homogeneous (i.e., allthe same colour), it is subdivided into four quadrants. This process is repeated for anynon-homogeneous sub-region. Each of the leaf nodes in the resulting quadtree representa region having the same colour.In our design, if the quadtree decomposition is governed by control vertices, eachrni x ni CV matrix for one level i when fully-refined in a hierarchical surface is taken aslA tree of outdegree n means that each node in the tree has at most n children.84Appendix B. The Definition of Quadtrees and Their Characteristics^85Figure B.27: A region, its maximal blocks, and the corresponding quadtree. (a) Region.(b) Block decomposition of the region in (a). (c) Quadtree representation of the blocksin (b).Appendix B. The Definition of Quadtrees and Their Characteristics ^86an image array; each CV is an element in such an image array. In a hierarchical surface,each overlay may be only a subset of the full m i x ni array of CV's. A homogeneousregion in the array is one where either none or all of the CV's are defined. That is tosay, the CV matrix is recursively decomposed.If the quadtree decomposition is governed by patches, each si x ti patch matrix forone level i when fully-refined in a hierarchical surface is taken as an image array; eachpatch is an element in such an image array and defined by one CV matrix. In a hier-archical surface, each overlay may be only a subset of the full si x ti array of patches.A homogeneous region in the array is one where either none or all of the patches aredefined. That is to say, patches are recursively decomposed.There are numerous ways to represent quadtrees. These range from fully pointeredquadtrees in which each pointer from parent to child is stored explicitly, to pointerlessquadtrees in which no pointers are stored. Mark and Lauzon [Mark85] compare the meritsand space-efficiency of several quadtree data structures. Fully pointered quadtrees offermaximum flexibility because they can be traversed in any order, but more storage spaceis required for the pointers. Pointerless quadtrees are the most compact in terms ofstorage requirements, but they have to be traversed in the order of their creation, whichreduces the speed of some algorithms. These represent the two extremes for time- andspace-efficiency.In the literature, three types of structures for quadtrees are reported. Klinger andRhodes ([Klinger79]) index nodes using a form of key derived from the ordered list ofancestors of the node, and use size and coordinate information for operations. Hunter([llunter79]) applies a "roped net", a pointer-based structure where each node is linked toits neighbours. A simpler hierarchical structure was adopted by Samet et al aSamet80]).with a node linked only to its parent and children.Bibliography[1] S. K. Abdali and D. S. Wise, "Experiments with quadtree representation of matrices,"Proceedings of the International Symposium on Symbolic and Algebraic Computation,July 1988.[2] D. Ayala, P. Brunet, R. Juan, and I. Navazo, "Object representation by means of non-minimal division quadtrees and octrees," ACM Transactions on Graphics 4, January1985, 41-59.[3] R. H. Bartels, and John C. Beatty, "An introduction to Splines for use in ComputerGraphics and Geometric Modeling," Morgan Kaufmann Publishers, Inc., 1987.[4] M. A. Bauer, "Set operations in linear quadtrees," Computer Vision, Graphics andImage Processing 29, February 1985, 248-258.[5] D. A. Beckley, M. W. Evens, and V. K. Raman, "Multikey retrieval from k-d trees andquad-trees," Proceedings of the SIGMOD conference, Austin, TX, May 1985, 291-301.[6] P. W. Besslich, "Quadtree construction of binary images by dyadic array transfor-mations," Proceedings of the IEEE Conference on Pattern Recognition and ImageProcessing, Las Vegas, June 1982, 550-554.[7] W. Boehm, "Rational geometric splines," Computer Aided Geometric Design 4, 1987,67-77.[8] F. W. Burton, and J. G. Kollias, "Comment on the explicit quadtree as a structurefor computer graphics," Computer Journal 26, 2, May 1983, 188.[9] F. W. Burton, V. J. Kollias and J. G. Kollias, "Expected and worst-case storagerequirements for quadtrees," Pattern Recognition Letters 3, 2, March 1985, 131-135.[10] I. Carlbom, I. Chakravarty, and D. Vanderschel, "A hierarchical data structure forrepresenting the spatial decompostion of 3-D objects," IEEE Computer Graphics andApplications 5, 4, April 1985, 24-31.[11] C. H. Chien and J. K. Aggarwal, "A normalized quadtree representation," ComputerVision, Graphics and Imagine Processing 26, 3, June 1984, 331-346.[12] C. H. Chien and J. K. Aggarwal, "Reconstruction and matching of 3-D objectsusing quadtrees/octrees," Proceedings of the Third Workshop on Computer Vision:Representation and Control, Bellaire, MI, October 1985, 49-54.[13] Hiroaki Chiyokura & Fumihiko Kimura, "Design of Solids with Free-Form Surfaces,"Computer Graphics, Vol. 17, No. 3, July 1983.87Bibliography^ 88[14] J. H. Chu, "Notes on expected numbers of nodes in a quadtree," Computer ScienceDeparment, University of Maryland, College Park, MD, January 1988.[15] J. H. Clark, "Hierarchical geometric models for visible surface algorithms," Com-munications of the ACM 19, 10, October 1976, 547-554.[16] E. Cohen, T. Lyche, and R. F. Riesenfeld, "Discrete B-splines and subdivision tech-niques in computer-aided geometric design and computer graphics," Computer Graph-ics and Image Processing, 14, 2, October 1980, 87-111.[17] Sabine Coquillart, "Extended Free-Form Deformation: A Sculpturing Tool for 3DGeometric Modeling," Computer Graphics, Vol. 24, No. 4, August 1990.[18] M. S. Cottingham, "A compessed data structure for surface representation," Com-puter Graphics Forum 4, 3, September 1985, 217-228.[19] W. A. Davis and X. Wang, "A new approach to linear quadtrees," Proceedings ofGraphics Interface 85, Montreal, May 1985, 195-202.[20] C. R. Dyer, A. Rosenfeld, and H. Samet, "Region representation: boundary codesfrom quadtrees," Communications of the ACM 23, 3, March 1980, 171-179.[21] C. Faloutsos, T. Sellis, and N. Roussopoulos, "Analysis of object oriented spatialaccess methods," Proceedings of the SIGMOD Conference, San Francisco, May 1987,426-439.[22] Gerald Fairn, "Curves and Surfaces for Computer Aided Geometric Design: A prac-tical guide," Academic Press, Inc., 1988.[23] R. A. Finel and J. L. Bentley, "Quad trees: a data structure for retrieval on com-posite keys," Acta Informatica 4, 1, 1974, 1-9.[24] D. R. Forsey, "Part II: Hierarchical Free-Form Surfaces," Ph.D thesis, Univ. ofWaterloo, 1990.[25] J. H. Friedman, F. Baskett, and L. J. Shustek, "An algorithm for finding nearestneighbors," IEEE Transactions on Computers 24, 10, October 1975, 260-269.[26] D. R. Fuhrmann, "Quadtree traversal algorithms for pointer-based and depth-firstrepresentations," IEEE transactions on Pattern Analysis and Machine Intelligence 10,6, November 1988, 955-960.[27] Irene Gargantini, "An Effective Way to Represent Quadtrees," Comm. of the ACM,Vol 25, No. 12, Dec. 1982, 905-910.[28] N. K. Gautier, S.S. Iyengar, N. B. Lakhani, and M. Manohar, "Space and timeefficiency of the forest-of-quadtrees representation," Image and Vision Computing 3,2, May 1985, 63-70.[29] T.N.T. Goodman, "Shape preserving interpolation by parametric rational cubicsplines," Proc. Int. Conf. on Numerical Mathematics, Int. Series Num. Math. 86, 1988,Birkhauser, Basel.Bibliography^ 89[30] G. M. Hunter, and K. Steiglitz, "Operations on Image Using Quad Trees," IEEETrans. Pattern Anal. & Mach. Intell., Vol PAMI-1, 1979, 145-153.[31] A. Hunter, and P. J. Willis, "Breadth-first quad encoding for networked picturebrowsing," Comput. & Graphics, Vol 13, No. 4, 1989, 419-432.[32] T. J. Ibbs and A. Stevens, "Quadtree storage of vector data," International Journalof Geographical Information Systems 2, 1, January-March 1988, 43-56.[33] C. L. Jachins and S. L. Tanimoto, "Quad-trees, oct-trees, and k-trees — a general-ized approach to recursive decompostion of Euclidean space," IEEE Transactions onPattern Analysis and Machine Intelligence, 5, September 1983, 533-539.[34] L. Jones and S. S. Iyengar, "Space and time efficient virtual quadtrees," IEEETransactions on Pattern Analysis and Machine Intelligence 6, 2, March 1984, 244-247.[35] G. Kedem, "The quad-CIF tree: a data stucture for hierarchical on-line algorithms,"Proceedings of the Nineteenth Design Automata Conference, Las Vegas, June 1982,352-357.[36] M. L. Kersten and P. van Emde Boas, "Local optimizations of quadtrees," TechnicalReport IR-51, Free University of Amsterdam, Amsterdam, The Netherlands, June1979.[37] A. Klinger, and C. R. Dyer, "Experiments in Picture Representation Using RegularDecomposition," Comput. Graphics and Image Processing, Vol. 5, 1976, 68-105.[38] A. Klinger, and M. L. Rhodes, "Organization and access of image data by areas,"IEEE Trans. Pattern Anal. Mach. Intell., 1,1979, 50-60.[39] Koji Komatsu, "Human skin model capable of natural shape variation," The VisualComputer, 3, 1988, 265-271.[40] S. X. Li and M. H. Loew, "The quadcode and its arithmetic," Communications ofthe ACM 30, 7, July 1987, 621-626.[41] S. X. Li and M. H. Leow, "Adjacency detection using quadcodes," Communicationsof the ACM 30, 7, July 1987, 627-631.[42] D. M. Mark and J. P. Lauzon, "The space effiency of quadtrees: an empirical exam-ination including the effects of 2-dimensional run-encoding," Geo-Processing 2, 1985,367-383.[43] D. C. Mason, and M. J. Callen, "Comparison of two dilation algorithms for linearquadtrees," Image and Vision Computing 6, 3, August 1988, 169-175.[44] M. Nahas, H. Huitric and M. Saintourens, "Animation of B-Spline Figure," TheVisual Computer, 3(4), 1987.[45] R. C. Nelson and H. Samet, "A population analysis of quadtrees with variable nodesize," Computer Science TR-1740, University of Maryland, College Park, MD, Dece-meber 1986.Bibliography^ 90[46] R. C. Nelson and H. Samet, "A population analysis for hierarchical data stuctures,"Proceedings of the SIGMOD Conference, San Francisco, May 1987, 270-277.[47] M. A. Oliver, and N. E. Wiseman, "Operations on quadtree encoded images," TheComp. J. 26(1), 1983, 83-90.[48] M. A. Oliver and N. W. Wiseman, "Operations on quadtree leaves and related imageareas," Comp. J. 26, 4, November 1983, 375-380.[49] M. H. Overmars, "Geometric data structures for computer graphics: an overview,"in Theoretical Foundations of Computer Graphics and CAD, Springeer-Verlag, Berlin,1988, 21-49.[50] F. Peters, "An algorithm for transformations of pictures represented by quad-trees,"Computer Vision, Graphics and Image Processing 32, 3, December 1985, 397-403.[51] L. Piegl, and W. Tiller, "Curve and Surface constructions using rational B-splines,"Computer Aided Design, Vol. 19, 1987, 485-498.[52] S. Ranade, A. Rosenfeld and J. M. S. Prewitt, "Use of quadtrees for image seg-mentation," Computer Science TR-878, University of Maryland, College Park, MD,February 1980.[53] W. C. Rheinboldt and C. K. Mesztenyi, "On a data structure for adaptive finiteelement mesh refinements," ACM Transactions on Mathmatical Software 6, 2, June1980, 166-187.[54] R. F. Riesenfeld et al. "Using the Oslo Algorithm as a Basis for CAD/CAM Geo-metric Modeling," Proc. NCGA National Conf. NCGA, Fairfax, Va. 1981, 345-356.[55] D. F. Rogers, and L. A. Adlum, "Dynamic rational B-spline surfaces," ComputerAided Design, Nov. 1990, 609-616.[56] H. Samet, "Region representation: quadtees from boundary codes," Communica-tions of the ACM 23, 3, March 1980, 163-170.[57] H. Samet and A. Rosenfeld, "Quadtree structures for image processing," Proceedingsof the Fifth International Confernce on Pattern Recognition, Miami Beach, December1980, 815-880.[58] H. Samet, "Connected component labeling using quadtrees," J. of the ACM 28, 3,July 1981, 487-501.[59] H. Samet, "Neighbor Finding Techniques for Images Representated by Quadtrees,"Comp. Graphics and Image Processing, Vol. 18, 1982, 37-57.[60] H. Samet, "The quadtree and related hierarchical data structures," Computer Vi-sion, Graphics, and Image Processing 26, 1, April 1984, 187-260.[61] H. Samet and R. E. Webber, "On encoding boundaries with quadtrees," IEEE Trans-actions on Pattern Analysis and Machine Intelligence 6, 3, May 1984, 365-369.Bibliography^ 91[62] H. Samet, "A top-down quadtree traversal algorithm," IEEE Transactions on Pat-tern Analysis and Machine Intelligence 7, 1, January 1985, 94-98.[63] H. Samet and C. A. Shaffer, "A model for the analysis of neighbor finding in pointer-based quadtrees," IEEE Transactions on Pattern Analysis and Machine Intelligence 7,6, November 1985, 712-720.[64] H. Samet, and R. E. Webber, "Hierarchical data structures and algorithms for com-puter graphics, Part I Fundamentals," IEEE Comp. Graphics and Appl., May 1988,48-68.[65] H. Samet, and R. E. Webber, "Hierarchical data structures and algorithms for com-puter graphics, Part II Applications," IEEE Comp. Graphics and Appl., July 1988,59-75.[66] H. Samet, "Design and Analysis of Spatial Data Structures," Addison-Wesley, Read-ing, MA, 1990.[67] D. S. Scott and S. S. Iyengar, "A new data structure for efficient storing of images,"Pattern Recognition Letter 3, 3, May 1985, 211-214.[68] C. A. Shaffer and H. Samet, "Optimal quadtree construction algorithms," ComputerVision, Graphics, and Image Processing 37, 3, March 1987, 402-419.[69] M. Shneier, "Note: Calculations of Geometric Properties Using Quadtrees," Com-puter Graphics and Image Processing, Vol 16, 1981, 296-302.[70] M. Tamminen, "Comment on quad- and oct-trees," Communications of the ACM27, 3, March 1984, 248-249.[71] S. Tanimoto and T. Pavlidis, "A hierarchical data structure for picture processing,"Computer Graphics and Image Processing 4, 2, June 1975, 104-119.[72] Tiller, W., "Rational B-splines for curve and surface representation," IEEE Comput.Graph. Appl. 3, 9, September 1983, 61-69.[73] A. Unnikrishnan, Y. V. Venkatesh, and P. Shankar, "Connected component labellingusing quadtrees - a bottom-up approach," Computer Journal 30, 2, April 1987, 176-182.[74] J. R. Woodwark, "The explicit quad tree as a structure for computer graphics,"Computer Journal 25, 2, May 1982, 235-238.[75] J. R. Woodwark, "Compressed quad trees," Computer Journal 27, 3, August 1984,225-229.[76] M. A. Yerry and M. S. Shephard, "A modified quadtree approach to finite elementmesh generation," IEEE Computer Graphics and Applications 3, 1, January/February1983, 39-46.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- An Object-oriented design for hierarchical B-spline...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
An Object-oriented design for hierarchical B-spline surfaces Yan, Hailin 1993-12-31
pdf
Page Metadata
Item Metadata
Title | An Object-oriented design for hierarchical B-spline surfaces |
Creator |
Yan, Hailin |
Date | 1993 |
Date Issued | 2008-09-11T23:05:55Z |
Description | This thesis documents an object-oriented software system that supports free-form surface modelling based on the hierarchical overlay methodology of [Forsey88]. This work is motivated by the need to provide a space-efficient representation of tensor-product hierarchical spline surfaces, multiple offset method support, and general surface representation. This design uses a spatial data structure, the quadtree, to achieve this goal. The quadtree, itself a hierarchical data structure, is very suitable in this application because of its ability to focus on the interesting subsets of the data. This focusing results in an efficient representation. The quadtree is also attractive because of its conceptual clarity and ease of maintenance. The package is implemented in C++ to provide: a) extensibility so that the new tools can be easily integrated into the existing package; b) reusability of code; and c)localization of code. Finally, this object-oriented hierarchical design keeps all of the original features of the hierarchical overlay method of [Forsey90]. |
Extent | 3825128 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2008-09-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051433 |
URI | http://hdl.handle.net/2429/1864 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- ubc_1993_spring_yan_hailin.pdf [ 3.65MB ]
- [if-you-see-this-DO-NOT-CLICK]
- Metadata
- JSON: 1.0051433.json
- JSON-LD: 1.0051433+ld.json
- RDF/XML (Pretty): 1.0051433.xml
- RDF/JSON: 1.0051433+rdf.json
- Turtle: 1.0051433+rdf-turtle.txt
- N-Triples: 1.0051433+rdf-ntriples.txt
- Original Record: 1.0051433 +original-record.json
- Full Text
- 1.0051433.txt
- Citation
- 1.0051433.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 30 | 82 |
United States | 24 | 5 |
Germany | 7 | 0 |
France | 7 | 0 |
Russia | 5 | 0 |
Japan | 3 | 0 |
Luxembourg | 2 | 0 |
Canada | 1 | 0 |
Bulgaria | 1 | 0 |
Algeria | 1 | 0 |
India | 1 | 0 |
Austria | 1 | 0 |
Brazil | 1 | 23 |
City | Views | Downloads |
---|---|---|
Beijing | 21 | 12 |
Unknown | 18 | 23 |
Shenzhen | 9 | 70 |
Ashburn | 7 | 0 |
University Park | 6 | 2 |
Saint Petersburg | 5 | 0 |
Munich | 5 | 0 |
Tokyo | 3 | 0 |
Fremont | 3 | 2 |
Dallas | 1 | 0 |
Mountain View | 1 | 0 |
Chemnitz | 1 | 0 |
Oran | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051433/manifest