Maths: Graphing Quadratic Equations (without gaps)

[beakie]

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

[ne555]

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

[beakie]

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

[ne555]

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

[ne555]

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

[SIK]

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.

[ssrun]

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.

[beakie]

@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.