# How should I fill a shape consisting of Bezier curves and straight lines?

I have been working on a graphics library for some time now and have gotten to the point where I have to draw Bezier and line based fonts. Up to this point I am stuck with this:

The green lines are the Bezier paths, and the white part is what gets rendered.

The code I use for Beziers is here. The one for lines is here. For those who don't know that is Lua.

Path rendering (lines) : 32 - 39 The algorithm is as follows:

1. Iterating from 0 to 1 at certain intervals
2. calculating the x and y with this formula: (1-index)^2*x1+2*(1-index)*index*x2+index^2*x3

Up to this point everything works fine. The green lines are generated using the path method.

The white part is rendered in a completely different way:

1. I get the x coordinates of the Beziers and lines at a particular Y, the put them into a table.
2. I iterate through the table and each time I encounter a point I change the value of state. In the same for loop is also check whether state is on. If it is, I draw a pixel to the screen.

To find the x values of a y, I use the getX method (line 46 in Bezier and line 31 in Line).

The code I use for the drawing itself is this one:

local xBuffer = {}
local state = false

for i=0,500 do
for k,v in pairs(beziers) do
a,b = v.getX(i)
if a then
xBuffer[round(a)] = 1
if b then
xBuffer[round(a)] = 1
end
end
end
for k,v in pairs(lines) do
a = v.getX(i)
if a then
xBuffer[round(a)] = 1
end
end
state = false
for x=0,600 do
if xBuffer[x] then
state = not state
end
if state then
love.graphics.points(x,i)
end
end
end


Quick explanation: for i,v in pairs iterates through the table given as an argument to pairs. love.graphics.points(x,y) sets a point at x,y.

• Is there a reason nobody responds? Should I reformulate the question? – Creator Jan 12 '16 at 8:36
• Its early days there are only so many people who have time to answer and you've only so far reached 5 views. This stackexchange is still an infant and has not got many users give it time. – joojaa Jan 12 '16 at 10:52
• OK. Thanks. I did not realize so little people were here. – Creator Jan 12 '16 at 12:10

If you are in a hurry to get your renderer working and you already have the filled polygonal routine functioning correctly, can I suggest an alternative, possibly easier approach? Though I'm not familiar with Lua, it seems you are solving for the exact intersection of a scan line with the quadratic Bezier which, though admirable, is possibly overkill.

Instead, tessellate your Beziers into line segments and then throw those into the polygon scan converter. I suggest just using (recursive) binary subdivision: i.e. the quadratic Bezier with control points, $(\overline {A} , \overline {B} , \overline {C})$ can be split into two Beziers, $(\overline {A} , \overline {D} , \overline {E})$ and $(\overline {E} , \overline {F} , \overline {C})$ where \begin{align*} & \overline {D}=\dfrac {\overline {A}+\overline {B}} {2}\\ & \overline {E} =\dfrac {\overline {A}+2\overline {B}+\overline {C}}{4}\\ & \overline {F}=\dfrac {\overline {B}+\overline {C}} {2} \end{align*} (which is also great if you only have fixed point maths).

IIRC, each time you subdivide, the error between the Bezier and just a straight line segment joining the end points goes down by a factor of ~4x, so it doesn't take many subdivisions before the piecewise linear approximation will be indistinguishable from the true curve. You can also use the bounding box of the control points to decide if you can skip out of the subdivision process early since that will also be a conservative bound on the curve.

• Thanks! A, B, C are vectors right? Also, I am using the scanline method because it allows me to get the exact number of points I need. Could you take a look at the code and guess why it is not working? Just the formulas. Also I would upvote the response, but I don't have 15 reputation. – Creator Jan 12 '16 at 13:04
• Yes, A B &C are vectors; 2D in your case but it applies equally well to N dimensions. As for going through the code... as I said I don't know Lua and even getting a standard polygon scanline renderer correct can be tricky - e.g. You have to be very careful when counting crossings which lie exactly on vertex positions. When you extend that to handling Beziers directly (which I did about 20+ years ago) it's more difficult still. I'm sorry I don't have the time. – Simon F Jan 12 '16 at 14:09
• Thanks for the help. Just found the issue. The a and c in the quadratic equation were inverted. – Creator Jan 12 '16 at 16:22