9
$\begingroup$

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

a

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.

$\endgroup$
3
  • $\begingroup$ Is there a reason nobody responds? Should I reformulate the question? $\endgroup$
    – Creator
    Jan 12, 2016 at 8:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – joojaa
    Jan 12, 2016 at 10:52
  • $\begingroup$ OK. Thanks. I did not realize so little people were here. $\endgroup$
    – Creator
    Jan 12, 2016 at 12:10

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Creator
    Jan 12, 2016 at 13:04
  • $\begingroup$ 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. $\endgroup$
    – Simon F
    Jan 12, 2016 at 14:09
  • 1
    $\begingroup$ Thanks for the help. Just found the issue. The a and c in the quadratic equation were inverted. $\endgroup$
    – Creator
    Jan 12, 2016 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.