Graphics Equations

I may be a little unclear exactly what you want to do (in my experience using a simple bresenham algorithm where you sample every x should be extremely fast). But how about just calculating the change in y between your two points that you want to draw the line (which is approximately the derivative? - its been a while since my last math class ). Depending upon its size, select more points in between.

sierratecha at 2007-7-16 21:27:27 >

Correction.

3. For every i such that |(x(i)-x(i+1))*dd(i)|>K*(x1-x0), add a

point x = (x(i)+x(i+1))/2 and update the lists X, Y and DD.

K is just a chosen constant.

The second derivative can be seen as a measurement on how hard

the function is curving, but this only make since if we compare

it to how big part of our domain we are looking at. That is the

justification for this adjustment.

parza at 2007-7-16 21:27:27 >

What I mean by quad curves is I followed the link above and used that method. It works by going in even increments across the screen. For each pair of increment points, its creates a "quadTo" curve with the quadratic control point at the intersection of the tangent lines of the two points. There is also a limit of too small a change in derivative between two increment points, in which case it does a simple "lineTo." This is useful too because in my program I apply alot of AffineTransforms to the resulting path, and since quad control points are transformed as well, the equation retains its shape very nicely. The code boils down to:

for (double t1=safeBounds.getY(), t2=t1, dx1=dx(t1), dx2, x1=x(t1), x2;

t2<(safeBounds.getY()+safeBounds.getHeight());

t1=t2, dx1=dx2, x1=x2){

t2=t1+(safeBounds.getHeight()/STEPS);

x2=x(t2);

dx2=dx(t2);

double desc = dx1-dx2;

if ((Math.abs(desc)<.2f) || (Math.abs(desc)>3)){

path.lineTo(x2,t2);

}

else{

double ctrlx = (x2*dx1 - x1*dx2 + dx1*dx2*t1 - dx1*dx2*t2)/desc;

double ctrly = (x2 - x1 + dx1*t1 - dx2*t2)/desc;

path.quadTo(ctrlx, ctrly, x2, t2);

}

}

The interesting problem is that if function is very zoomed out, increment points might fall on unrelated parts of the funciton. Like imagine the function Sin(x) and having one point at 0,0 and another at the bottom of the next trough. Their tangent lines intersect somewhere far into the thrid quadrant, and the quadratic control points makes the function go in a huge loop in that direction. Basically by playing around with different values of min/max change in derivative, I got it to be acceptable, but if anyone has a better workaround, let me know.

As for the applet not working, I have no idea except maybe download latest Java, but I've never really made an applet before so I dunno. Works for me.

Marius311a at 2007-7-16 21:27:27 >

> The interesting problem is that if function is very zoomed out...

Is this not due to lack of resolution. If you would have more points

where the cure is bending hard, this would not happen.

Another function where your approach will run into problems is

f(x) = e^(-k*x^2) because when we increase the constant k the spice

will not be well represented when it becomes narrow compared to to

the even increment. If you use following suggestion I think it will

solve it.

Here is a improved suggestion of my previous reply 5,6. It adjusts

the increment dependent on how hard the previous step curves.

Let f(x) be your function that should be plotted between x0 and x1,

and let d initial increment.

1. Let x(o)=x0, x(1)=x0+d and x(2)=x0+2*d and compute y(i)=f(x(i))

for i=0,1,2. Let i=2.

2. Compute

dd(i) = -2*(x(i-2)*(y(i-1)-y(i))-x(i-1)*(y(i-2)-y(i))+x(i)*(y(i)-y(i-1)))/((x(i-2)-x(i-1))*(x(i-2)-x(i))*(x(i-1)-x(i)))

3. If |(x(i-1)-x(i))*dd(i)|>K1*(x1-x0) then d = d/2.

4. If |(x(i-1)-x(i))*dd(i)|<K2*(x1-x0) then d = d*2.

5. Let i = i+1

6. Let x(i) = x(i-1)+d and compute y(i) = f(x(i)). If x(i)><x1

resume at 2, else we are done.

The initial increment should be really short to catch any heavy

bending. If f(x) does not bend heavy, the increment will be adjusted

really fast since d=d/2 and d=d*2.>

parza at 2007-7-16 21:27:27 >

This topic is really fascinating to me for some reason....

I'm currenty satisfied with what I got but, some things for the method you described, parz, nonetheless. The method of comparing to dd to the size of the viewing area is very useful, I actually will use that. Also, I know my function dd directly so I don't have to calculate it. As for incrementing "d", one thing I tried was just having d be inversely related to dd(x). Basically my for loop looked like for(x=xmin;x<xmax; x+=Constant / dd(x)); It worked alright except for when dd(x) got very small it would just set a huge increment. Actually now that I think of if I did x+=Min(Constant/dd(x),maxXIncrement), that might come out nicely. Then the constant would just depent on the screen size... hmm...>

Marius311a at 2007-7-16 21:27:27 >

I look at your link and looks good. Letting the increment depend

on the inverse of dd(x) seams to be a good idea, but I think it

needs some adjustments. I found this interesting too, so I looked

into it some more and following suggests that increment depends

on the square rooted inverse.

Let x be the current location, d be the next increment, and e(x,d)

be the maximum error between the true curve and the line y going

through points [x, f(x)] and where f and y are parallel in point x.

That is e(x,d) = max_{w=[0,d]} |y(x+w) - f(x+w)|

= max_{w=[0,d]} |f'(x)*w + f(x) - f(x+w)|

where f'(x) is the first derivative of f(x). If we can find the

largest d>0 such that e(x,d) <= C, we can draw the line y between

[x, x+d] and know that the error is at most C. Now, we use Taylor

series ( http://mathworld.wolfram.com/TaylorSeries.html ) to

expand f(x+w) = f(x) + f'(x)*w + f''(x)*w^2/2! + ... Then we get

e(x,d) = max_{w=[0,d]} |f''(x)*w^2/2! + f'''(x)*w^3/3! + ...|

=< max_{w=[0,d]} |f''(x)|*w^2/2! + |f'''(x)|*w^3/3! + ...

=< |f''(x)|*d^2/2! + |f'''(x)|*d^3/3! + ...

We know that for continues function f^n(x)*d^n/n! --> 0

when n --> inf and for most functions this happens really fast.

Let us assume that we only look at functions where the first

term is significant. Then we know that

e(x,d) <= |f''(x)|*d^2/2 <= C==>

d <= sqrt(2*C/|f''(x)|)

where C = [max function error]*[error in pixels]/[window hight in pixels]

How do you know the second derivative of any incoming function?

parza at 2007-7-20 19:25:42 >

I couldn't follow your math to well, (what is the max(0,d) mean? ) but I tried having the increment vary with the inverse root and the choice of increments seems a little better so I'm gonna stick with it. The problem with this method is the same as any of the others so far, though. If I choose a control point that happens to fall where the second derivative is close to 0, then the next increment will be disproportionately large and it will miss part of the curve. I can pretty much get around this with max/min increment but thats a workaround not a solution.

Marius311a at 2007-7-20 19:25:42 >

Reposting it in better format.

> what is the max(0,d) mean?

max_{w=[0,d]) f(w) is the maximum value f(x) where x can be any

value between 0 and d. More strict it is

There exists an x=[0,d] such that f(x) = max_{w=[0,d]) f(w) and

and for all w=[0,d], f(w) <= f(x).

> I can pretty much get around this with max/min increment but thats

> a workaround not a solution.

In theory you could use more terms from the Taylor series, but then

you would have to solve a polynomial and have access to more

derivatives.

f''(x)*d^2/2! + f'''(x)*d^3/3! - C = 0

parza at 2007-7-20 19:25:42 >