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

Question

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.

Thanks in advance.

Answer 1

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.