DOC

Constrained multi-degree reduction of triangular Bezier surfaces

By Clifford Armstrong,2014-01-26 11:32
11 views 0
Constrained multi-degree reduction of triangular Bezier surfaces

    Constrained multi-degree reduction of

    triangular Bezier surfaces

    App1.Math.J.ChineseUniv

    2009,24(4):417430

    ConstrainedmultidegreereductionoftriangularB6ziersurfaces

    ZHOULianWANGGuojin

    Abstract.Thispaperproposesandappliesamethodtosorttwo-dimensionalcontrolpoints oftriangularB6ziersurfacesinarowvector.UsingthepropertyofbivariateJacobibasis functions,itfurtherpresentstwoalgorithmsformultidegreereductionoftriangularB6zier

    surfaceswithconstraints,providingexplicitdegree-reducedsurfaces.Thefirstalgorithmcan

    obtaintheexplicitrepresentationoftheoptimaldegree

    reducedsurfacesandtheapproximating

    errorinbothbound~ycurveconstraintsandcornerconstraints.Butithastosolvetheinversion ofamatrixwhosedegreeisrelatedwiththeoriginalsurface.Thesecondalgorithmentailsno matrixinversiontobringaboutcomputationalinstability,givesstabledegree

    reducedsurfaces

    quickly,andpresentstheerrorbound.Intheend,thepaperprovestheefficiencyofthetwo algorithmsthroughexamplesanderroranalysis.

    ?lIntroduction

    B6ziercurves(surfaces1areoneofthemostwidelyusedmodelingtoolsinCAD/CAM systems[.

    Itisofgreatimportanceingeometryprocessingtoachievedegreereduction,whichis aprocesstofindalowerdegreecurve(surface)toapproximateanotherparametercurve(surface)

    withagivendegree,whilekeepingtheerrorwithinagiventolerance.Considerablemethods havebeendevelopedtoreducedegrees.whichmainlyfallintotwocategories.Oneadoptsdis

    cretizationmethods[2?7l,

    andtheother,algebraicmethods[.

    Someresearchershavemade

    certainachievements[13-171inthedegreereductionoftensorproductB6ziersurfaces.Butfew

    studieshavebeendoneontriangularB6ziersurfaces[.Thus,whatisneedednowisto

    enablethemultidegreereductionoftriangularB6ziersurfacesatonetimewhilekeepingcorner

    andboundarycurveconstraints.SOastocreateamoreefficientandprecisemodelingsystem. TheWOrkofLu20lmeetsthestatedrequirement.Againithastosolvetheinversionofahigh degreematrix,whichneedslongcomputingtimeandisquestionableinitsstability. Received:2008——12.-18

    MRSubiectC:lassification:65D18

    Keywords:triangularB6ziersurface,explicit,boundarycurveconstraint,cornerconstraint,degreereduc

    tion,Jacobipolynomial

    DigitalObjectIdentifier(DOI1:10.1007/sl1766009-21495

    SupportedbytheNationalNaturalScienceFoundationofChina(60873111;60933007) C0rresp0ndingauthor,Email:wanggJ@zju.edu.cn

    418App1.Math.J.

    ChineseUnivVl01.24.NO.4

    Withafairviewofformerresearchachievements,wepresentthealgorithmsf_ormulti

    degree

    reductionoftriangularB6ziersurfacesunderbothcornersandboundarycurvesconstraintsre-

    spectively.Thebasicideaistoachievedimensionalreductionofcontrolpointsandbasis functionsbyusingtheconversionbetweenbivariateJacobibasisfunctionsandbivariateBern-

    steinbasisfunctionsaswellastheorthogonalityofJacobipolynomials.Thefirstalgorithm

derivestheoptimaldegree

    reducedsurfaceandthebestexplicitpresentationofapproximating errorunderthetwoconstraintsinamostpreciseway.Butitalsoneedstosolvetheinversion

    ofamatrixwhosedegreeis0(n),whereisthedegreeoftheoriginalsurface.Thesecond algorithmavoidstheinversematrixbyusingthepropertyofbivariateBernsteinpolynomials.

    Itprovidesstablenumericalcalculationwithminorcomputationalerrortoleranceandpresent

    s

    theerrorbound.

    ?2Preliminaries

    DefinedontriangulardomainT:={(s,t):s,t0,l

    surfaceofdegreeisdefinedasfollows[1]:

    P(s,))

    8t0},atriangularB6zier

    (2.1)

    whereB~j(s,t)=t'(1s一))jisthebivariateBernsteinbasisfunctionof degreen,Pi,

    jarethecontrolpointsofthesurface.

    2.1Jacobibasisfunctionsontriangulardomain

    BivariateJacobibasisflmctions(s,t)ontriangulardomainaredefinedasfoilows:

    (s.):^(s)(1s)/2.(),

    1

    where181>1/2and

    ()

    isunivariateJacobipolynomial[

    [^']. hl,

    2

    R(u

    --

    T

    +

G~

    1

    t+?+"+1tl-

    t)

    ofdegreert.Denote+,=+++1/2,then (Q+1/2)n(k(9+1/2)k(T+1/2)k(k+)+1

    !(咒一七)!(2+)(2n/+1)()+'

    Inthispaperjgeneralizedhypergeometricseries[3]isdenotedas

    (01'.',ni

    b,

    alJ

    .

    1

    (b/)k(1)n;Z

    where,J?z+,,n.,by,cEC,(c):cf). BivariateJacobibasisfunctionshavethefollowingproperties:

    Property1?BivariateJacobibasisfunctionsofdegreenontriangulardomainTareorthogonal

    withweightfunction (.,,)sc~-I/t,8/.(1(s)'1/2

    (++7+i/2)

    1/2)!(Z1/2)!(71/2)

    7

    ?

    ?

    }l

    ?=A

    "

    e

    r

    e

h

    ?

    ZHOULian,eta1.ConstrainedmultidegreereductionoftriangularB6ziersurfaces

    Thatis

    Lemma1.FOr

    polynomialsBZ1 aSfollows[23]: where

    419

    (s,)=?e(,i,)(s,), 0<

    k

    </

    (s,):?d(n,l,)B(s,), i+j

    el

    (

    ,

    k

    ,

    k,,J=c一一()()()(+1/2)~(/3+1/2)j(7+1/2)t,ht,f!(+1)n+c

    ?

    (,Tti;1/2,1/2,1/2,n), k(s,;a,b,c,N):=(?一1+1)1k(a+1)k(b+1)(st)

    .

    Qc(?(s;a,2k+b+C+1,N)Q(s;b,C,8+t)

    'n

    ,l,)

    Qc(;,M):s(一一l),

    =

()

    2.2Onedimensionalsortingofcontrolpointsofsurfaceandbasisfunctions In1959whendeCasteljauinventedB6ziercurves,herealizedtheneedfortheextension ofcurveideastosurfaces.Interestinglyenough,thefirstsurfacetypeheconsideredwaswhat wenowcallBdziertriangular.Thishistorical'first'oftriangularpatchesisreflectedbythe mathematica1statementthattheyareamore'natural'generalizationofB6ziercurvesthan tens0rDroductpatches[.

    Basedonthis'natural'generalization,thispaperfirstconsidersthe re

    sorringofthecontrolpoints.ThenusingtheconversionbetweenBernsteinbasisandJacobi basis,andtheorthogonalityofJacobipolynomials,wederivetheoptimaldegree

    reducedsur

    faceandthecorrespondingerror.

    Definition1.IfabinaryarrayP,

    (i+J)arrangedinarowvectorconformsto

    theorderofthesubscript(i,J)intheindexset2={(n,0),(n1,1),?,(0,n),(0,n

    1),.,(0,0),(1,0),.,(佗一1,0),(n2,1),?,?,(1,佗一2),',(1,1),.,(几一

    3,1),'_'},

    wesaythearraysatisfies(i,J)?Q".Thissortingmethodiscalledhelicalsorting.When=5,

    thesortingispresentedinFig.1fa).

    Definition2.IfabinaryarrayJk,

    l(s,t)(02)arrangedinarowvectorconformsto

    theorderofthesubscript(i,J)intheindexsetA{(n,n),(n,凡一1),',(n,O),(n1,n

    1),(n1,凡一2),.,(n1,0),(n2,n2),?,(0,0)),wesaythearraysatisfies(,1)

    ?A.

    When=5thesortingispresentedinFig.1(b).

    UsintheabovetwosortingmethodsandLemma1,theconversionofthetwobaseis describedasfollows:

    Theorem1.BivariateBernsteinbasisBn-(8,t)andJacobibasis(s,t)canrepresent 420App1.Math.J.ChineseUniv

Po4p03p02PolPoo

    (a)(i,J)?【2

    v01.24.No.4

    J54J53352JslJso

    (b)(i,J)?A

    Fig.1Whenn=5,binaryarraiespt, JandJk,

    farearranged

    eachotherwith

    B=J,,7E,p,

    ,

    J,,7)=BD,,,y)

    Here,

    B=(B(s,0)1×【(+2)(+1)/23,J',)=((s,)))1×【(+2)(+1)/21, E,,1)=(e}''(n,,)),D,,1)=(dn,l,)),(,J)?Q",(2,)?A,

    wheretheelementsofeachrowofmatrixE)satisfy(i,J)?Qandtheelementsofeach

    columnofmatrixE,,)satisfy(1, k)?A.TheelementsofeachrowofmatrixD''') satisfyk)?AnandtheelementsofeachcolumnofmatrixD)satisfy(i,J)?Q. AsthispaperonlydiscussesJacobipolynomialsintwooccasionswhenQ=8=10and

    ==,y=5/2,thefollowingabbreviatednotationsareusedforconvenience:

    J:=J,.,

    ,

    E:=E(o,o,o)

    ,

    D:=D(O,O,O),

    J.:=j(5/2,5/2,5/

    ,

    E:=E(5/2,5/2,5/,

    D:=D/,/,/.

?3Theproblemofdegreereductionandprec0nditioningof

    boundarycurves

    (nm)degreereductionoftriangularB6ziersurfacePn(s,t)in(2.1)istofindatriangular B6ziersurfaceofdegreem(m<n),

    Q(s,t):?qi,jB~3(s,)),(3.1)

    iWj<rn

    whosecontrolpointsare{q,J}i+Jm,SOthatthedistancefunctionbetweentwosurfacesin 2-normiSminimized.Thatis.

    d(P"(s,),Qm(s,)):哪川捌

    AstheinformationofcornersofsurfacesinaCAD/CAMsystemusuallyneedstobepre

    served,weneedtoconsiderthecontinuitiesatthecornersofdegree

    reducedsurfaces.Moreover,

    mostoftheproductsconsistofcomplexsurfaceswhicharecomposedofseveralpatches.In ZHOULian,eta1.ConstrainedmultidegreereductionoftriangularB6ziersurfaces421 ordertopreservethecontinuitiesglobally,weshouldmakeconstraintsontheboundarycurves ofthedegree

    reducedsurfaces.Sothissectionpresentsthepreconditioningofboundarycurves underthesetwoconstraints.

    3.1Boundaryconstraints

    ToasingletriangularB6ziersurface,itsthreeboundarycurvesarerespectivelyaSfollows s+t=1:Pa(s)=?Pi-n_t(s),0sl

    i=0

    s=0:P2(t1

    t=0:P3(s)=

    ?Po,J(),0t1

    d=0

    ?p(s),0s1i=0

    (3.2)

    (3.3)

    (3.4)

    where(s):(:)(1s).siistheBernsteinbasisfunctionofdegree.Thethreeboundary curvesareB6ziercurvesofdegreefn.

    Tomakeconstraintsontheseboundarycurves,weneedtokeephighorderinterpolationat theendpoints.Inordertogetthedegreereducedcurvesofthesethreeboundarycurves

    ,

    we

    usetheexistingmethod[toobtainthedegreereducedcurvesof(3.2)

    (3.4)withconstraints

    ofendpointshighorderinterpolation.Thebasicideaissummarizedasfollows.

    GivenaB6ziercurveofdegreen

    S()=t?[0,1](3.5)

    Theoptimal(n--n1)degree

    reducedapproximatingcurvehavingequalderivativesupto(r1)

    thand(81)thordersattheendpoints,respectivelyi.e., s'(0)=T(0),k=0,1,?,r1;s(1)=T(1),1=0,1,,s1,

    iSdenotedas

    1

    T())=?…n()).

    =0

    ThecontrolpointsofthecurveTn1(t)ofdegreenlcanbeexpressedinmatrixform

    Here,

    (B.一一F.A.(?)B)

    =(bi,j)(+1)×(+1),

    1)(:)(;),

    j:

    ,

    ,,

    (3.6)

    }1b

    ,,,........

一一/

    n

    l

    0

    =

    .1

    .Z

    .n

    <> u.u ,??J,

    =

    422

    ?=

    App1.Math.J.ChineseUniv

    c+c一一+2

    rs+1

    r+1

    0

    0

    nlrs+2 1r+1 cTtl~

    -

    8+2

    0

    c吕一一一c一一

    cn-r

Report this document

For any questions or suggestions please email
cust-service@docsford.com