Maths: Graphing Quadratic Equations (without gaps)

How to draw a quadratic curve?

I have a quadratic in the form of 3 floats A, B and C.... I want to draw it! I need to do this using ONLY a setPixel function...

1) I could step through each pixel along the X axis of the graph, calc the x value, then use that the calc the y value.

This will lead to gaps in my line where the difference between one Y value and the next (as I step along the width of the graph) is greater than 1 pixel.

2) Perform method 1... then rearrange the equation and do the same for the Y axis of the graph... plotting each of the possible X values.

This is complicated(!) and would lead to quite a few repeat setPixel calls.

3) Step though X in a really small amount. A fraction of the size of a pixel. This would allow for less gaps than method 1 but would have a lot of repeat setPixel calls. Also, I can't GUARANTEE there won't be a gap for the odd quadratic. This isn't very precise.


Is there a nice (FAST) way of doing this?

Thanks
Bresenham
As in (3) but the step is just big enough to paint another pixel.

Bresenham
As in (3) but the step is just big enough to paint another pixel.



Yeah I have used that for lines (and I understand it also works for circles) but how does that apply to quadratic curves?

Thanks
Last edited on
I will try to explain it. But please read the bresenham for circles.

You've got a parabola $ y - ax^2 = 0 $ vertex in $(0;0)$
This can be constructed by indicating another point $P = (x;y)$, so $a = \frac{y}{x^2}$

Divide the curve in 2 parts.
_ $0 <= y' <= 1 we advance for x
_ $1 < y'$ we advance for y

I will explain the first case for an $a>0$
At each step we advance to the right, and test if our current midpoint is below or above the curve
We replace the x,y values in the formula
$D = -a (x_j + 1)^2 + (y_j + 0.5)$

Now, if $D>0 we will paint the `south' pixel (where we are), else we paint the `north' (advance in y)


To have only integer operations:
Multiply the discriminant by $2 \Delta x^2$ D = -2 \Delta y (x_j+1)^2 + \Delta x^2 (2y+1)

To avoid computing all that we use the increments (analyse the $x_j+2$ pixel)
If we paint the `south': D += -2 \Delta y (2 x_j + 3)
If we paint the `north': D += -2 \Delta y (2 x_j + 3) + 2 \Delta x^2
Last edited on
Another possibility is to use a recursive algorithm.
Compute 2 points on the curve, if their distance is greater that 1 (there is a gap) recurse with their midpoint on the curve.

You may want to take a look at DeCasteljau too http://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm#Geometric_interpretation
would it be possible to use the derivative of the quadratic equation to calculate the rate of change of curve.

basically if f'(x) is the derivative of f(x),

then f'(x) = 0 relates to the x-value at which the parabola turns.

this corresponds to a horizontal tangent at that point.

hence f'(x) --> 0 implies greatest change in x over smaller to zero change in y.

and f'(x) --> infinity implies smaller to zero change in x over greatest change in y.

So with some formulation you might be able to come up with a relation between this rate and the next x value such that the maximum change for either x or y is not more than 1 pixel.
Generally all curves are approximated with lines so there is no reason why you couldn't use bresenham's algorithm. Unless you're plotting points at extremely large steps it will look fine.
@ne555 thanks, will have a read of the maths in your first example... but i do like the simplicity of the second :)

@sik rate of change would be a good way to look at it, because i think i would be half way towards anti-aliasing the line too!

@ssrun i was hoping to make it more accurate


Thanks for all your ideas. Will have a think/play and let you know what I do.
Last edited on
Topic archived. No new replies allowed.