CS-184: Computer GraphicsLecture #13: Natural Splines, B-Splines, and NURBS Prof. James O’BrienUniversity of California, BerkeleyV2008-S-13-1.01Natural SplinesDraw a “smooth” line through several points2A real draftsman’sspline.Image from Carl de Boor’s webpage.2Natural Cubic SplinesGiven pointsGenerate a curve with segmentsCurves passes through pointsCurve is continuousUse cubics because lower order is better...3n + 1nC23Natural Cubic Splines4u = 0u = 1u = 2u = 3u = nu = n − 1s1s2s3snsn−1x(u) =s1(u) if 0 ≤ u < 1s2(u − 1) if 1 ≤ u < 2s3(u − 2) if 2 ≤ u < 3...sn(u − (n − 1)) if n − 1 ≤ u ≤ n4Natural Cubic Splines5u = 0u = 1u = 2u = 3u = nu = n − 1s1s2s3snsn−1si(0) = pi−1i = 1 . . . nsi(1) = pii = 1 . . . ns"i(1) = s"i+1(0) i = 1 . . . n − 1s""i(1)= s""i+1(0) i = 1 . . . n − 1s""1(0)= s""n(1) = 05Natural Cubic Splines5u = 0u = 1u = 2u = 3u = nu = n − 1s1s2s3snsn−1si(0) = pi−1i = 1 . . . nsi(1) = pii = 1 . . . ns"i(1) = s"i+1(0) i = 1 . . . n − 1s""i(1)= s""i+1(0) i = 1 . . . n − 1s""1(0)= s""n(1) = 0← n constraints← n constraints← n-1 constraints← n-1 constraints←2 constraintsTotal 4n constraints5Natural Cubic Splines6Interpolate data pointsNo convex hull propertyNon-local supportConsider matrix structure... using cubic polynomialsC26B-SplinesGoal: cubic curves with local supportGive up interpolation Get convex hull propertyBuild basis by designing “hump” functions7C27B-Splines8b(u) =b−2(u) if u−2≤ u <u−1b−1(u) if u−1≤ u <u0b+1(u) if u0≤ u <u+1b+2(u) if u+1≤ u ≤u+2b!!−2(u−2) = b!−2(u−2) = b−2(u−2) = 0b!!+2(u+2) = b!+2(u+2) = b+2(u+2) = 0b−2(u−1)= b−1(u−1)b−1(u0) = b+1(u0)b+1(u+1)= b+2(u+1)8B-Splines8b(u) =b−2(u) if u−2≤ u <u−1b−1(u) if u−1≤ u <u0b+1(u) if u0≤ u <u+1b+2(u) if u+1≤ u ≤u+2b!!−2(u−2) = b!−2(u−2) = b−2(u−2) = 0b!!+2(u+2) = b!+2(u+2) = b+2(u+2) = 0b−2(u−1)= b−1(u−1)b−1(u0) = b+1(u0)b+1(u+1)= b+2(u+1)Repeat for and←3 constraintsTotal 15 constraints ...... need one more←3 constraints←3×3=9 constraintsb!b!
Unlocking...