Curvature Monotonicity Evaluation Function for 2D Polynomial Bézier Curves
Author
Norimasa Yoshida, Takafumi Saito
Title
Curvature Monotonicity Evaluation Function for 2D Polynomial Bézier Curves
Description
This notebook provides a code for computing the curvature monotonicity evaluation function for a 2D polynomial Bézier curve
Category
Academic Articles & Supplements
Keywords
2D polynomial Bézier curve, curvature monotonicity evaluation function
URL
http://www.notebookarchive.org/2024-06-1xe104l/
DOI
https://notebookarchive.org/2024-06-1xe104l
Date Added
2024-06-04
Date Last Modified
2024-06-04
File Size
52.52 kilobytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
Curvature Monotonicity Evaluation Function for 2D Polynomial Bézier Curves
Norimasa Yoshida
Nihon University
yoshida.norimasa@nihon-u.ac.jp
Takafumi Saito
Tokyo University of Agriculture and Technology
txsaito@cc.tuat.ac.jp
Nihon University
yoshida.norimasa@nihon-u.ac.jp
Takafumi Saito
Tokyo University of Agriculture and Technology
txsaito@cc.tuat.ac.jp
This notebook provides an example code for computing the CMEF (curvature monotonicity evaluation function) of a 2D polynomial Bézier curve. The CMEF is the numerator of dk/ds in Bernstein basis. Refer to [1] for the derivation of the CMEF. For the applications of CMEFs , we proposed a real time method to visualize the region of a control point where the curvature is monotonically varying [1, 2] using a GPU. For Bernstein multiplication, the scaled Bernstein [3] is used to avoid unnecessary computation of binomial coefficients.
The code can be extended to the CMEF for a 2D rational, 3D polynomial, or 3D rational Bézier curve using equations in [1].
[1] Takafumi Saito and Norimasa Yoshida, Curvature monotonicity evaluation functions on rational Bézier curves, Computers & Graphics, Vol.114, pp.219-229, Aug. 2023. https://doi.org/10.1016/j.cag.2023.05.019.
[2] Norimasa Yoshida, Seiya Sakurai, Hikaru Yasuda, Taisei Inoue and Takafumi Saito, Visualization of the Curvature Monotonicity Regions of Polynomial Curves and its Application to Curve Design, Computer-Aided Design and Applications, Vol. 21, No.1, pp.75-87, Jan. 2024. http://doi.org/10.14733/cadaps.2024.75-87
[3] J. Sánchez-Reyes, Algebraic manipulation in the Bernstein form made simple via convolutions. Computer Aided Design, Vol. 35, No.10, pp.959-967, 2003. http://dx.doi.org/10.1016/S0010-4485(03)00021-6.
The code can be extended to the CMEF for a 2D rational, 3D polynomial, or 3D rational Bézier curve using equations in [1].
[1] Takafumi Saito and Norimasa Yoshida, Curvature monotonicity evaluation functions on rational Bézier curves, Computers & Graphics, Vol.114, pp.219-229, Aug. 2023. https://doi.org/10.1016/j.cag.2023.05.019.
[2] Norimasa Yoshida, Seiya Sakurai, Hikaru Yasuda, Taisei Inoue and Takafumi Saito, Visualization of the Curvature Monotonicity Regions of Polynomial Curves and its Application to Curve Design, Computer-Aided Design and Applications, Vol. 21, No.1, pp.75-87, Jan. 2024. http://doi.org/10.14733/cadaps.2024.75-87
[3] J. Sánchez-Reyes, Algebraic manipulation in the Bernstein form made simple via convolutions. Computer Aided Design, Vol. 35, No.10, pp.959-967, 2003. http://dx.doi.org/10.1016/S0010-4485(03)00021-6.
P: control points, deg: the degree of a Bézier curve
P: control points, deg: the degree of a Bézier curve
In[]:=
P:=Table[{x[i],y[i]},{i,0,deg}]
SP: control points multiplied by its corresponding binomial coefficient
In[]:=
SP:=Table[Binomial[deg,i]{x[i],y[i]},{i,0,deg}]
BCoeffMul: Multiply P by Binomial[n,i]
In[]:=
BCoeffMul[P_]:=Module[{n=Length[P]-1},Table[Binomial[n,i]P[[i+1]],{i,0,n}]]
SBMul : Bernstein multiplication of two scalars .
In[]:=
SBMul[P_,Q_]:=Module{m=Length[P]-1,n=Length[Q]-1},TableP[[j+1]]Q[[i-j+1]],{i,0,m+n}
Min[m,i]
∑
j=Max[0,i-n]
SBMulCross: Bernstein multiplication (wedge product) of two vectors
In[]:=
SBMulCross[P_,Q_]:=Module{m=Length[P]-1,n=Length[Q]-1},Table(P[[j+1]][[1]]Q[[i-j+1]][[2]]-P[[j+1]][[2]]Q[[i-j+1]][[1]]),{i,0,m+n}
Min[m,i]
∑
j=Max[0,i-n]
SBMulDot : Bernstein multiplication (dot product) of two vectors
In[]:=
SBMulDot[P_,Q_]:=Module{m=Length[P]-1,n=Length[Q]-1},Table(P[[j+1]][[1]]Q[[i-j+1]][[1]]+P[[j+1]][[2]]Q[[i-j+1]][[2]]),{i,0,m+n}
Min[m,i]
∑
j=Max[0,i-n]
SQ : corresponds to Q_ {00}, etc . in [3]. Note that scaled Bernstein is used.
In[]:=
SQ[f_][m_,k_]:=BCoeffMul[Table[f[[i]],{i,k+1,Length[f]-(m-k)}]]
SV1, SV2, SS3, and SS4 corresponds to V1, V2, S3, and S4 in [1].
In[]:=
SV1:=deg(SQ[P][1,1]-SQ[P][1,0])
In[]:=
SV2:=deg(deg-1)(SQ[P][2,2]-2SQ[P][2,1]+SQ[P][2,0])
In[]:=
SS3:=deg^2(deg-1)(SBMulCross[SQ[P][2,0],SQ[P][2,1]]+SBMulCross[SQ[P][2,2],SQ[P][2,0]]+SBMulCross[SQ[P][2,1],SQ[P][2,2]])
In[]:=
SS4a:=SBMulCross[(SQ[P][3,1]-SQ[P][3,0]),(2SQ[P][3,1]-3SQ[P][3,2]+SQ[P][3,3])]
In[]:=
SS4b:=SBMulCross[(SQ[P][3,0]-3SQ[P][3,1]+2SQ[P][3,2]),(SQ[P][3,3]-SQ[P][3,2])]
In[]:=
SS4:=If[(deg-2)<=0,{{0,0}},deg^2(deg-1)(deg-2)(Join[SS4a,{0}]+Join[{0},SS4b])]
In[]:=
xiYtmp:=If[deg==2,-3SBMul[SS3,SBMulDot[SV1,SV2]],SBMulDot[(SBMul[SS4,SV1]-3SBMul[SS3,SV2]),SV1]]
In[]:=
xiDeg:=4deg-7
By diving xiYtmp by Binomial[xiDeg, i], we can obtain the “control points” \xi_i for CMEF.
In[]:=
xiY:=Table[xiYtmp[[i+1]]/Binomial[xiDeg,i],{i,0,xiDeg}]
By pressing SHIFT+ENTER on either of the two lines, the CMEF of a quadratic or cubic Bézier curve can be computed. It should work for quartic or higher degree Bézier curves, but it may be slower.
In[]:=
deg=2;pt={{0,0},{1,0},{2,3}};
In[]:=
deg=3;pt={{0,0},{1,0},{3,2},{4,6}};
g1: Bézier curve where a control point can be interactively moved.
In[]:=
g1:=LocatorPane[Dynamic[pt],Dynamic[Show[Graphics[BezierCurve[pt,SplineDegree->deg],Axes->True,AxesLabel->{x,y},PlotRange->{{-1,8},{-1,8}},ImageSize->{400,400}],Graphics[{Dashed,Line[pt]}]]]]
In[]:=
ReplaceXY:=Join[Table[x[i]->pt[[i+1]][[1]],{i,0,deg}],Table[y[i]->pt[[i+1]][[2]],{i,0,deg}]]
In[]:=
xiYv:=xiY/.ReplaceXY
In[]:=
maxY:=Max[Abs[xiYv]]
In[]:=
xi:=Table[{i/xiDeg,xiYv[[i+1]]},{i,0,xiDeg}]
In[]:=
xiNormalized:=Table[{i/xiDeg,xiYv[[i+1]]/maxY},{i,0,xiDeg}]
g3: CMEF with respect to parameter t. Note that CMEF is scaled within ±1.
In[]:=
g3:=Dynamic[Show[Graphics[BezierCurve[xiNormalized,SplineDegree->xiDeg],Axes->True,AxesLabel->{t,CMEF(scaledto±1)},PlotRange->{{-0.1,1.1},{-1.1,1.1}}],Graphics[{Dashed,Line[xiNormalized]}],Graphics[Point[xiNormalized]]]]
PBez : Bezier curve
In[]:=
PBez[t_]:=(1-tt)^(deg-i)tt^iSP[[i+1]]/.tt->t/.ReplaceXY
deg
∑
i=0
Pd : first derivative of PBez[t]
In[]:=
Pd[t_]:=D[PBez[tt],tt]/.tt->t
Pdd : second derivative of PBez[t]
In[]:=
Pdd[t_]:=D[PBez[tt],{tt,2}]/.tt->t
Pddd : third derivative of PBez[t]
In[]:=
Pddd[t_]:=D[PBez[tt],{tt,3}]/.tt->t
In[]:=
(*lambda[t_,xxi_]:=Binomial[xiDeg,i](1-tt)^(xiDeg-i)tt^ixxi[[i+1]]/.tt->t*)
xiDeg
∑
i=0
In[]:=
(*dkds[t_]:=lambda[tt,xi][[2]]/(Pd[tt].Pd[tt])^3/.tt->t(*slowerthandkds[t]below*)*)
In[]:=
dkds[t_]:=(Det[{Pd[tt],Pddd[tt]}]Pd[tt].Pd[tt]-3Det[{Pd[tt],Pdd[tt]}]Pd[tt].Pdd[tt])/(Pd[tt].Pd[tt])^3/.tt->t
In[]:=
kappa[t_]:=Det[{Pd[tt],Pdd[tt]}]/(Pd[tt].Pd[tt])^(3/2)/.tt->t
g2 : curvature plot with respect to t
In[]:=
g2:=Dynamic[Plot[kappa[t],{t,0,1},PlotRange->{{-0.1,1.1},{-1.1,1.1}},AxesLabel->{t,k}]]
g4 : dk/ds with respect to t
In[]:=
g4:=Dynamic[Plot[dkds[t],{t,0,1},PlotRange->{{-0.1,1.1},{-10,10}},AxesLabel->{t,dk/ds}]]
In[]:=
GraphicsGrid[{{g1,g2},{g3,g4}},ImageSize->{700,800}]
Out[]=
Cite this as: Norimasa Yoshida, Takafumi Saito, "Curvature Monotonicity Evaluation Function for 2D Polynomial Bézier Curves" from the Notebook Archive (2024), https://notebookarchive.org/2024-06-1xe104l
Download
