|
|
Drawing & Filling Bezier Curves in the Compact Framework
--Copyright 2009 Travis Feirtag
|
Introduction
Here are my implementations for the DrawBezier and DrawBeziers methods which are missing from the .NET Compact Framework. I also include implementations for FillBezier and FillBeziers which do not exist in the .NET libraries at all. I thought that we should be able to fill the curves as well as draw them. I hope these methods will be helpful to anyone who wishes to draw bezier curves on mobile devices.
I have made every effort to make this code efficient and error free.
If you find a bug in the code or a better way to implement the algorithm, please feel free to send me an email with your questions/comments/suggestions.
|
A Bezier Curve generated using 4 control points (B0, B1, B2, B3).
B0 & B3 are end points on the curve.
B1 & B2 are control points representing the tangent lines to the curve.
|
Mathematical Representation of a Bezier Curve
Once you see and understand the equations, you will see how easy they are to utilize. I do not claim to be a mathematician. I am 'standing on the shoulders of giants' when I use the equations. I use the knowledge with respect and admiration for the great skill, ingenuity and experience that went into the development of Bezier curves. I highly recommend reading the book "An Introduction to NURBS by David Rogers" (see references at end). It is a fantastic book that describes Nonuniform Rational B-Spline curves in an easy to understand format and gives a historical perspective for the development of curve and surface representations in computer graphics and CAD/CAM systems. Bezier curves are actually a special case NURB curve.
| Parametric Bezier Curve Equation |
|
|
P(t) =
|
|
Bi Jn, i (t)
|
|
0 <= t <= 1
|
|
| Bezier basis or blending function |
|
|
Jn, i (t) =
|
(
|
|
)
|
t i (1 - t) n - i
|
|
(0)0 = 1
|
|
| with |
|
|
Continuity
Consider that 4 control points will only give you a finite set of curves. To draw a longer, more complex curve you will need more control points. A long curve will be a piecewise representation of individual bezier curves with 4 control points each. The end point of one bezier curve will be the starting point of the next curve. This is called Geometric Continuity. A curve is said to have geometric continuity when piecewise curves share common endpoints or a join point.
This technique is used to draw longer, more complex curves.
We simply need to piece together a set of bezier curves into the desired curve. The DrawBeziers and FillBeziers are piecewise implementations.
A curve can also have Parametric Continuity. A curve is said to have parametric continuity when the tangent at the join point has the same magnitude and direction. My implementation of curve generation does not guarantee parametric continuity. If you want to have a curve with parametric continuity, it is up to you to enter the correct control points. Maybe I'll do that for a later version.
Implementation for the Compact Framework
I would like to begin this section by saying that this implementation will not be 100% compatible with the .NET Full Framework DrawBezier & DrawBeziers implementation. This version requires you to pass a Graphics object to the drawing methods. Obviously this is different than the .NET Full Framework because the Graphics class implements these methods. Of course, this point is only important if you wish to share a common code base between the .NET Compact Framework and the .NET Full Framework.
All my example screen shots were run on my Dell Axim x51v. It's got an XScale running at 624Mhz with a graphics accelerator.
You will notice that the inputs to the methods take PointF (float points) structs. Oddly, this struct does not exist in the Compact Framework so I include an implementation. I prefer to do all the calculations in floating point and then convert to Int32. Unfortunately the Compact Framework GDI.NET implementation only supports passing Point (int points) arrays to the drawing routines.
The essential concept of creating a curve is to calculate points along the curve and then use the DrawLines method that is supported in Compact Framework. You will notice the constants define at the top. LINE_POINTS_PER_CURVE value should be obvious that it defines how many points that will be calculated along the Bezier curve. PARAM_CURVE_STEP defines the incremental value for the loop through the curve. Note, if you change the number of points per curve you will need to change the denominator of PARAM_CURVE_STEP to match that value. The code could be changed to do this dynamically as well. I didn't care to do that for this implementation.
private const Int32 LINE_POINTS_PER_CURVE = 15;
private const float PARAM_CURVE_STEP = 1.0f / 15.0f;
private void DrawBezier(Graphics grfx, Pen linePen, PointF ptB0, PointF ptB1, PointF ptB2, PointF ptB3)
{
Point[] ptsBezier = new Point[LINE_POINTS_PER_CURVE + 1];
ptsBezier[0] = new Point(Convert.ToInt32(ptB0.X), Convert.ToInt32(ptB0.Y));
Int32 nIndex = 1;
for (float t = PARAM_CURVE_STEP; t < 1.0f; t += PARAM_CURVE_STEP)
{
float fW = 1 - t;
float fA = fW * fW * fW;
float fB = 3 * t * fW * fW;
float fC = 3 * t * t * fW;
float fD = t * t * t;
float fX = fA * ptB0.X + fB * ptB1.X + fC * ptB2.X + fD * ptB3.X;
float fY = fA * ptB0.Y + fB * ptB1.Y + fC * ptB2.Y + fD * ptB3.Y;
ptsBezier[nIndex] = new Point(Convert.ToInt32(fX), Convert.ToInt32(fY));
nIndex++;
}
ptsBezier[LINE_POINTS_PER_CURVE] = new Point(Convert.ToInt32(ptB3.X), Convert.ToInt32(ptB3.Y));
grfx.DrawLines(linePen, ptsBezier);
}
|
|
The basic
DrawBezier curve implementation takes a graphics object, a pen, and four points as input and draws a curve. You can see from the screen capture that the drawn curve also shows red control points. I also included a separate method for drawing the control points. This is intended for development purposes. I could also add a tangent line between end points and control points to see the structure of the curve.
The DrawBezier method from MSDN is limited to a single curve so I don't find it very useful. It's easier to use the DrawBeziers method and pass in an array of points.
|
private void DrawBeziers(Graphics grfx, Pen bezierPen, PointF[] ptsCurve)
{
if (ptsCurve == null)
return;
if (ptsCurve.Length < 4)
return;
Int32 nLength = ptsCurve.Length - 4;
if (nLength > 0)
{
if (nLength % 3 != 0)
return;
}
Int32 nTotalPoints = 1 + (nLength / 3);
Int32 nCurveIndex = 0;
Int32 nBezierIndex = 0;
Point[] ptsBezier = new Point[nTotalPoints * (LINE_POINTS_PER_CURVE + 1)];
while (nCurveIndex < ptsCurve.Length - 1)
{
PointF ptB0 = ptsCurve[nCurveIndex++];
PointF ptB1 = ptsCurve[nCurveIndex++];
PointF ptB2 = ptsCurve[nCurveIndex++];
PointF ptB3 = ptsCurve[nCurveIndex];
ptsBezier[nBezierIndex++] = new Point(Convert.ToInt32(ptB0.X), Convert.ToInt32(ptB0.Y));
for (float t = PARAM_CURVE_STEP; t < 1.0f; t += PARAM_CURVE_STEP)
{
float fW = 1 - t;
float fA = fW * fW * fW;
float fB = 3 * t * fW * fW;
float fC = 3 * t * t * fW;
float fD = t * t * t;
float fX = fA * ptB0.X + fB * ptB1.X + fC * ptB2.X + fD * ptB3.X;
float fY = fA * ptB0.Y + fB * ptB1.Y + fC * ptB2.Y + fD * ptB3.Y;
ptsBezier[nBezierIndex++] = new Point(Convert.ToInt32(fX), Convert.ToInt32(fY));
}
ptsBezier[nBezierIndex++] = new Point(Convert.ToInt32(ptB3.X), Convert.ToInt32(ptB3.Y));
}
grfx.DrawLines(bezierPen, ptsBezier);
}
|
|
The DrawBeziers method implementation also takes a graphics object and a pen. The control points are stored in a PointF array. The first four points stores the initial curve. Three additional points are given for the next curve section. The previous end point is used as the starting point of the next curve. You will see that I do size checking of the PointF array making sure that the size matches the 4-3 criteria. I just have it return if the array size is not correct, could probably change that to throw an exception.
The screen capture shows a curve that was drawn with DrawBeziers method. In the debug build, I include timing information showing how long the total curve calculations took and how long it took CF to draw the curve. For this example there are 16 points for input. Based on the source code above, you will see that 16 points input should generate an output point array of (16 * (15 + 1)) or 256 output points. As you can see, it took 1.46 milliseconds to calculate the 256 points and 5.35 ms to draw them. Obviously the drawing operation is what takes the most time.
The drawing operation will be affected by the Pen's line width. A line width of 1.0f will draw the quickest. The technique for drawing lines is based on Bresenham's algorithm (1965). You will see later on that line widths greater than 1 can hit the drawing performance considerably and it can be a performance bottleneck. For this example the line width is 2.0f. I used this width to see the screen capture better. I need a better screen capture app that can capture the 480x640 resolution of my Dell Axim. Remote Zoom In cannot accomodate this resolution. I need to write something to handle this.
|
|
|
The FillBezier method is simply the DrawBezier curve generation algorithm that uses the FillPolygon method to fill the curve. This example uses the same points from the first example and performs a fill operation on the generated points. The astute observer will notice that in this example the grfx.FillPolygon operation is more than 2 times faster than the grfx.DrawLines from first example. Granted, filling a Bezier curve that isn't a closed curve isn't very useful.
|
|
|
The FillBeziers method uses the curve point generation algorithm to create the same points from the DrawBeziers method but instead uses the FillPolygon method to fill the curve. This example shows that the grfx.FillPolygon method is 2 times faster than the grfx.DrawLines method.
|
|
|
Drawing a Big Bezier Curve.
Now it gets interesting to see how long a large input PointF array will take. In this example, the Draw Big Bezier generates a 304 point array. The output array should be (304 * (15 + 1)) or 4864 output points. The screen shot on the left uses a line width of 1.0f. You can see that it only took 28.5 ms to calculate the output points. I think that was pretty good. And then drawing it only took 87.9 ms, which is roughly 3 times longer to draw.
|
|
|
So let's try drawing the same 304 input points for the Bezier curve with line width 2.0f. You will see the calculation of the 4864 output points took approximately the same amount of time. But, WOW, it took over 2.5 seconds to draw the lines !!! It took over 90 times longer to draw the line then to calculate it. Yikes, major bottle neck. I would probably be better off translating the points over 1 point and redrawing with a line width of 1.0f.
The grfx.DrawLines implementation starts to have problems with larger line widths. I'll have to look into a better way, if possible.
|
|
|
|
Loading Bezier curve data from an XML file. Okay, so let's do something that is better than random lines and fills. For this example I took an SVG file on the desktop and converted it (another article?!) to my own custom XML curve file format. The filename is 'bfly01.xml' and it contains all the Bezier curve information for the butterfly screen shot.
Obviously loading a file from flash and converting it will take longer than having the data in memory. Another improvement can be to capture the output points and store than for redrawing. In a later article I'll show you how we can do some cool things like translate, scale and rotate the output point data. Saves time if you don't have to recalculate the curve information everytime.
|
Visual Constraints
Please keep in mind that by using 15 points along each curve you may have issues with the visual accuracy and aesthetics of the rendered curve. When spanning greater screen distances, you can easily improve the quality of the curve by combining more bezier curves together in a longer curve so that you have more points. Or you can change the number of points calculated per Bezier curve by changing the values for LINE_POINTS_PER_CURVE and PARAM_CURVE_STEP.
Native C++ Library Implementation
For those of you who wish to squeeze every bit of performance out of a mobile implementation (and you know who you are), I also provide a C++ version of code to calculate the Bezier curve points which is compiled into a separate native library. Then you can make Platform Invoke calls to the native code and circumvent the JIT compilation. You will still pay a penalty for marshalling the data between managed and unmanaged code. But the greater amount of calculations you require, the more this option becomes appropriate. This is only meant to calculate the Bezier curve points and leaves the drawing to the GDI .NET libraries. Yes, we could have the native code draw to the device context but then why are we using Compact Framework at all ?!
|
|
So I had to write an implementation in a C++ native library to calculate the Bezier output points to give a performance comparison of managed code to unmanaged code. For those of you who still think that managed code is just as fast as native code, I'm here to burst your bubble. Here is the evidence that shows you can get a performance increase for your important calculations using native C++ libraries.
You will see that the same 304 input points for the Bezier curve from a previous example was 2.4 times faster in calculating the 4864 output points than the managed code implementation. The drawing time is still the same for both examples.
Of course, I can already hear people saying that 28 ms is fast enough. I will concede that sometimes it can be "fast enough" but on a Windows Mobile device there is limited speed and resources. The more your app does, the more important it is to squeeze every bit of performance out of your code.
Also, you will note in the OnLoad method I make an initial PInvoke call to the native library to JIT the DllImport to the native code. There will always be a penalty for the first time you make any managed call and this includes the setup for a managed call to a native library.
|
|
|
Calculate output points using Native C++ library and draw with line width 2.0f. You will see that in this example it didn't matter that we calculated the output points quicker, it still takes 2.5 seconds to draw the lines.
|
Source Code
Projects were written using Visual Studio 2005.
C# Source Code : CeBezier
C++ Source Code : CeNatBezier
Compiled binaries : CeBezier_Binaries
Conclusion
I had fun with this one and I plan on other advanced graphics topics for the Compact Framework.
References
Introduction to NURBS: with a historical perspective
by David Rogers
ISBN #1558606696
Graphic Gems I
Edited by Andrew Glassner
ISBN #0122861663
MSDN - DrawBezier and DrawBeziers