This module contains classes and tools for working with LR spline surfaces.

This module depends on the following GoTools modules:

• GoTools Core and the following modules external to GoTools:
• SISL (SINTEF)

Example programs corresponding to this module are listed in lrsplines2D examples

The problem with tensor-product grids

The simplest way to generate parametric surface patches is by applying the tensor-product construction to univariate parametric space curves. Examples of these are B-spline surfaces, B-spline volumes, NURBS surfaces and NURBS volumes, which are implemented in GoTools.

The number of control points of these tensor-product patches grows exponentially with the dimension of the geometric object. For instance, for curves with 10 control points, corresponding tensor-product surfaces will have 100 control points and tensor-product volumes will have 1000 control points. These control points form a rectlinear gridded structure, making it impossible to refine the model locally without refining across the entire domain. Hence, in practice, it becomes unfeasible to add sufficient detail to the model where it is needed most.

LR B-splines and LR spline surfaces

Locally Refined B-splines (LR B-splines) aim to solve this problem by providing a mathematical framework, generalizing the tensor-product construction, for refining the model locally. This framework extends to any dimension.

An LR spline surface, LRSplineSurface, is a piecewise polynomial or piecewise rational polynomial surface defined on an LR-mesh, Mesh2D. An LR-mesh is a locally refined mesh made by applying a sequence of refinements starting from a tensor-product mesh. LR spline surfaces are algorithmically defined throughout the refinement process of the mesh. An LR spline surface is defined as

$$ F(u,v) = \sum_{i=1}^L P_i s_i R_{i, p_1, p_2} (u,v) $$

where $P_i$, $i=1, ... ,L$ are the surface coefficients, and $s_i$ are scaling factors introduced to ensure partition of unity of the resulting collection of tensor product B-splines. The tensor product B-splines $R_{i,p_1,p_2}$ are of bi-degree $(p_1,p_2)$ defined on knot vectors of lengths $p_1 + 2$ and $p_2 + 2$ on the parametric domain in the $u$ and $v$ directions respectively.

-LR-mesh. The support of one tensor product B-spline visualized as a red pattern. Initial knotlines are shown as black lines, the inserted knotline segments are blue-

An LR-mesh corresponding to an LR spline surface of bidegree two is shown in the figure above. The mesh lines of the initial tensor-product surface are drawn in black. The corresponding knots are: $u_1, u_1, u_1, u_2, u_4, u_6, u_7, u_7, u_7$ in the first parameter direction and $v_1, v_1, v_1, v_3, v_5, v_6, v_6, v_6$ in the second direction. The LR-mesh is constructed by first inserting knots at $v_2$ and $v_4$ covering parts of the parameter domain in the second parameter direction followed by knots at $u_3$ and $u_5$. Note that a new knot line must cover the support of at least one B-spline in the current surface. The parameter patches limited by knot lines are denoted elements, Element2D, and serve a role in maneouvring in the parameter domain of the surface. In approximation context the elements contain data points. The initial B-spline surface has 30 basis functions (B-splines) while the constructed LR spline surface has 42 B-splines, LRSpline2D. Some lines of the LR-mesh intersecting the support of such B-spline do not correspond to knotlines of its knot mesh as they do not traverse the support completely. The refinement process is performed in the example refine_lrsurf.C.

The procedure applied is the following:

1. Add a new line segment that triggers the refinement of at least one existing tensor-product B-spline. It can be an extension of an existing line segment, can be independent of existing line segments, or increase the multiplicity of an existing the line segment. Thus, a line segment going from $(u_5,v_4)$ to $(u_5,v_5)$ is a legal choice.
2. Subdivide all tensor product B-splines with support that is completely traversed by the new line/extended line.
3. The tensor product B-splines are required to have minimal support. This means that all line segments traversing the support of a tensor product B-spline are required to be knotline segments of the B-spline taking the multiplicity of line segments into account. After inserting a new line segment and performing the subdivision in Step 2., there might still be tensor product B-splines that do not have minimal support with respect to the LR-mesh. Consequently all such B-splines must be refined. This process is continued until all tensor product B-splines have minimal support.

If more than one new knotline segment is defined simultaneously, the refinement process is applied one segment at the time. Some details on how to choose new knot line segments can be found in the example lrsplines2d_refine.

LR spline surface possess most of the nice properties of spline surfaces, such as:

• Non-negative basis function
• Partition of unity
• The surface lies in the convex hull of its coefficients

However, depending on the refinement strategy, linear dependence situations may occur. A case where such situations are identified and resolves is explained in the example identify_and_resolve_linear_dependence.

Classes involved in representing an LR spline surface

Mesh2D

The LR-mesh is represented in Mesh2D. It contains information about knot values in the two parameter directions and segments for each knot value. The latter has a compact encoding where a knot line segment is represented by the index of the start knot and the knot multiplicity. Active segments have multiplicity one or higher while segments with multiplicity 0 indicates that there is no knot in this part of the parameter domain.

Mesh2D provides functionality to enquire properties of the mesh such as: number of knots excluding multiplicity (numDistinctKnots), value of a given knot (kval), iterators to knots (knotsBegin, knotsEnd), access to knots (getKnots), parameter domain (minParam, maxParam). Also mesh rectangle information such as knot multiplicity and active and not active knot line segments, is available.

BSplineUniLR

BSplineUniLR represents a univariate B-spline by storing indices to the corresponding knot vector in Mesh2D to the active knots of the current B-splines. Properties like degree, knot values and parameter interval are deduced. Information about a possible overlap between two univariate B-splines and the Greville parameter of this B-splines is available.

LRBSpline2D

A LRBSpline2D is constructed as a tensor product between two univariate B-splines (BSplineUniLR), but contains in addition the corresponding coefficient, the scaling factor and a possible rational weight. The class contains information of the element in the support of the B-spline.

The class provides functionality to enquire the coefficient, scaling factor and rational weight as well as geometry space dimension, associated knot vector and degree. The elements in the support are avaiable and the support limits can be requested. The associated mesh is also available.

Element2D

An element represents the domain of one polynomial patch in the LR spline surface. It is limited by active knot line segments in both parameter direction. Element2D contains information about the limits of this domain, the B-splines overlapping it and, in approximation context, data points associated to this domain. Element2D provides access to information about the domain properties, the associated B-eplines and neighbouring elements. The example program
investigate_Element2D shows how to obtain information related to the elements.

LRSplineSurface

LRSplineSurface inherites ParamSurface and thus the functionality defined there. Some functionalities are not implemented, e.g. area.

LRSplineSurface is the owner of all information required to represent the surface. Bivariate B-splines and elements are contained in maps to facilitate rapid recognition of the element and B-splines having a given parameter pair in its support. A parameter remembering the last element requested serves as a tool to speed up this search. The class also contains all individual univariate B-splines required to define the bivariate B-splines.

Evaluation is performed through the functions point and evalGrid. The first is implemented in several varieties: With and without computing derivatives and with and without getting the relevant element as input. The latter evaluates a regular grid of points, one by one, after connecting the elements with a tensor-product grid. Connecting a parameter pair to an element is the most time consuming part of the evaluation, and the grid ensures a rapid recognition. Evaluation is demonstrated in the example evaluateLRSurface. See also the example investigate_LRSplineSurface for more functionality.

The LRSplineSurface is constructed through refinement given a tensor-product grid as input. The constructor can receive a spline surface, SplineSurface, or the information defining the grid as input. Refinement is triggered by LRSplineSurface, but performed in LRSplineUtils. Given an element or a B-spline selected for refinement, a knot line segment that complies to the requirements must be specified. Several options exists and are explained in some detail in the example lrsplines2d_refine.

Other classes, definitions and namespaces

• BSplineUniUtils Utility functionality for keeping track of univariate B-splines. The univariate B-splines are stored as vector in LRSplineSurface and these vectors need to be kept updated during refine operations.
• Direction2D Specifies the parameter direction of a surface.
• LinDepUtils The peeling algorithm, one step in identifiying linear dependencies.
• LogLikelyhood A statistical critierion for goodness of fit. Related to scattered data approximation.
• LRApproxApp Functionality related to the approximation of a point cloud by an LR spline surface: specific interfaces to the approximation and computation of accuracy
• LRBSpline2Dutils LRBSpline2D related functionality used in refinement.
• LRFeatureUtils Given a current LR spline surface with an associated point cloud, compute feature output in a grid. Called from LRSurfApprox to visualize certain aspects of the approximation, help documentation are available from the app PointCloud2LR.C.
• LRMinMax Computes extrema of LR spline function. The functionality requires associated contour curves as input.
• LRSplineEvalGrid Grid evaluation of the elements of an LR spline surface.
• LRSplineMBA Called from LRSurfApprox. The name space provides functionality to update an LR spline surface using an adaptation to the local approximation method multi resolution B-spline approximation.
• LRSplineUtils Utilities, mostly related to refinement of an LR spline surface, but the namespace contains also some more functionality.
• LRSurfApprox Approximate a scattered data point cloud by a 1D or 3D LR spline surface. In the latter case, the point cloud must be parameterized. A large collection of parameters can be used to guide the approximation. A short explanation can be found in the help text to the application PointCloud2LR.C, which provides an interface to the functionality. See also the example programs approximateWithLRFunc.C and approximateParPointsWithLRSurf.C. A simplified interface can be found in LRApproxApp.
• LRSurfSmoothLS Least squares approximation with a smoothing term. Called from LRSurfApprox. This approximation approach is combined with multi resolution B-spline approximation (MBA) to compute the approximating surface. Least squares approximation is typically used in the start of the process, then the process continues with MBA.
• LRSurfStitch Modifies a collection of bivariate LR spline functions organized in a regular pattern to obtain C^0^ or C^1^ continuity between adjacent functions. The process involves an increase in data size of the functions.
• LRTraceIsocontours Compute the level-set curves of an LR spline function. The function is used to compute contour curves and the use is illustrated in the app isoContours.C and the example isoContoursLRFunc.C
• SSurfTraceIsocontours Used by LRTraceIsocontours.
• TraceContoursTypedefs Typedefs and tempate functionality used by LRTraceIsocontours.
• Mesh2DUtils Utility functionality for manouvring in an LR mesh.
• MeshLR Base class for Mesh2D and Mesh3D in lrsplines3D.
• TrimSurface Create bounded surface from an LR B-spline function and associated point cloud to make the function domain correspond to the domain of the point cloud represented by its x- and y-values.
• LRSplinePlotUtils and LRSplinePlotUtils2 Debug functionality

Sources

T. Dokken, T. Lyche, K.F. Pettersen. Polynomial splines over locally refined box-partitions, Computer Aided Geometric Design, Volume 30, Issue 3, March 2013, Pages 331--356