<p>If you are in a hurry to get your renderer working <em>and</em> you already have the filled polygonal routine <em>functioning correctly</em>, 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.</p>

<p>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*} &amp; \overline {D}=\dfrac {\overline {A}+\overline {B}} {2}\\ &amp; 
\overline {E} =\dfrac {\overline {A}+2\overline {B}+\overline {C}}{4}\\ &amp;
\overline {F}=\dfrac {\overline {B}+\overline {C}} {2}
\end{align*}
$$
(which is also great if you only have fixed point maths).</p>

<p>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.</p>

CC BY-SA 3.0
2016-01-12T13:04:15.660Z
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
CC BY-SA 3.0
2016-01-12T14:09:28.923Z
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
CC BY-SA 3.0
2016-01-12T16:22:31.000Z
Thanks for the help. Just found the issue. The a and c in the quadratic equation were inverted.
Creator
CC BY-SA 3.0
2016-01-12T12:53:59.170Z
2017-05-31T07:26:51.043Z
2017-05-31T07:26:51.043Z
Simon F
<p>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:</p>

<p><img src="https://cdn.discordapp.com/attachments/132932473242910720/136193149239427073/unknown.png" alt="i"></p>

<p><img src="https://cdn.discordapp.com/attachments/132932473242910720/136196291146285056/unknown.png" alt="a"></p>

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

<p>The code I use for Beziers is <a href="http://pastebin.com/s8qDC4NH" rel="noreferrer">here</a>. The one for lines is <a href="http://pastebin.com/bKv55tch" rel="noreferrer">here</a>. For those who don't know that is Lua. </p>

<p>Path rendering (lines) : 32 - 39
  The algorithm is as follows:</p>

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

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

<p>The white part is rendered in a completely different way:</p>

<ol>
<li>I get the x coordinates of the Beziers and lines at a particular Y, the put them into a table.</li>
<li>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.</li>
</ol>

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

<p>The code I use for the drawing itself is this one:</p>

<pre><code>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
</code></pre>

<p>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.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2016-01-12T08:36:11.910Z
Is there a reason nobody responds? Should I reformulate the question?
Creator
CC BY-SA 3.0
2016-01-12T10:52:36.993Z
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
CC BY-SA 3.0
2016-01-12T12:10:08.863Z
OK. Thanks. I did not realize so little people were here.
Creator
<rendering><algorithm><geometry><line-drawing>
How should I fill a shape consisting of Bezier curves and straight lines?
Creator
# How should I fill a shape consisting of Bezier curves and straight lines?

(Asked by: username_0 on 2016-01-11)

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:

![i](https://cdn.discordapp.com/attachments/132932473242910720/136193149239427073/unknown.png)

![a](https://cdn.discordapp.com/attachments/132932473242910720/136196291146285056/unknown.png)

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

The code I use for Beziers is [here](http://pastebin.com/s8qDC4NH). The one for lines is [here](http://pastebin.com/bKv55tch). 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.

**Tags:** rendering, algorithm, geometry, line-drawing

> **Comments:**
> **username_0**: Is there a reason nobody responds? Should I reformulate the question?  
> **username_1**: 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.  
> **username_0**: OK. Thanks. I did not realize so little people were here.  

---

## 1 answers

### Answer by username_2 on 2016-01-12. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: Thanks for the help. Just found the issue. The a and c in the quadratic equation were inverted.  

---

