Bezier Curve Fitting in Corona SDK

You may be wondering, what does Bezier Curve Fitting algorithm’s have anything to do with mobility and entrepreneurship? Nothing with entrepreneurship, but a lot with mobility. Why? Simple, I wrote a entire bezier rendering algorithm in our Corona SDK which is our framework for building apps with a single code base to both iOS and Android devices, and, also, it just so happens, that curves and surfaces and anything to do with concepts in advanced geometric modeling has been part of me since my days at Deneba while working as an software engineer for their flagship product, Canvas. (This puts me back at around 1991 time frame).

Bezier curves are a form of parametric curve and are commonly used in most 2D software graphic products available today. The type of Bezier curve I normally like to work with are cubic Bezier’s, mostly because I grew up using them and they are the standard parametric curve for PostScript, Illustrator and are pretty much the norm for font outlines. Computational wise, cubic Beziers are costlier versus quadratic. My first exposure to quadratic curves was when I was working on the Flash Authoring tool. I still consider cubic Beziers, the standard.

One of the things that has always been challenging is the fact that mobile devices have been in part, not powerful enough to render parametric curves, and what has been quite costly is the editing of such curves and fitting them to a set of points that are drawn while dragging the mouse and or in the case of the iPhone/iPad, your finger, across the ‘drawing board’. Lucky for us today, most smart phones come equipped with OpenGL GPU’s so the notion of rendering curves are a thing of the past.

Well, not for me, sure I can hand off a set of points and have the GPU render the curve for me, but I am old school. I want to control how I want to draw the points and part of eating my own dog food, is, if our CoronaSDK can mustard such performance heavy algorithm given how we go from Lua to Objc-C etc….

The approach was straight forward, drag the finger across the iPhone, create a line, then, reduce the number of points on the line and finally pass the points through a curve fitting algorithm. Given that I have a set amount of time due to my obligations as a co-founder and others, the first thing I did was to be able to generate a plain old cubic Bezier curve.

That was easy. Tap on the screen four times, create a curve, then move the handles and end points, redraw the curve. See Bezier Curve Editing in Corona SDK. The next thing was just for fun, move an object along the curve. Object along a Bezier Curve in Corona SDK.

Then came the hard part. How do I generate a curve given a set of points that mimics the pencil tool in Adobe Illustrator. Well, being a member of the ACM I set out to find some sort of paper on polygon point reduction. All my research led to Ramer–Douglas–Peucker algorithm.

Once I figured out how to modify the RDP algorithm to fit my needs and had it working, I went looking for my Graphic Gems I book and read Philip J Schneider’s ‘An Algorithm for Automatically Fitting Digitized Curves’. In conjunction with other papers on Curve Fitting from the ACM as well as my other CG books, from Farin’s “CADG 5th Edition”, Mark de Berg’s book “Computational Geometry” and lastly, Schneider’s own book “Geometric Tools for Computer Graphics”, I figured out what the best approach was to create a curve fitting algorithm in Lua using our very own Corona SDK.

Here is the video, Creating a Bezier curve using Polygon Point Reduction and CurveFitting in Corona SDK. And here is the app running on a device, Bezier Curve Fitting on an iPhone with an app created in our very own Corona SDK.

I will be posting the source as soon as I clean it up and optimize it even further for better performance.

Carlos.

ps: Just to be clear, the core fitting code is all Lua. The drawing part is all CoronaSDK.

pss: The premiere book on splines is by the Killer B’s. Beatty, Bartels and Barsky, “An Introduction to Splines for Use in Computer Graphics and Geometric Modeling” By Richard H. Bartels, John C. Beatty, Brian A. Barsky. Although I didn’t have the chance to consult the book for the curve fitting project, it is by far, one of the best books on Splines.