Some time ago, a friend asked me about drawing a rotated elipse, something like the yellow one in the following picture:
|
|
The basic ideea who came imediately, is that a rotated elipse,
can be achieved drawing a "normal" elipse (as in red)
into a rotated axis system.
I.e. Drawing an elipse rotated with the angle a is like drawing a "normal" elipse into a axis system rotated with -a. This paper as first step describe how to draw a point into a rotated axis system, then show how to draw a elipse based on both trigonometrical and analytical expresions. In the end, I present a speed optimization and some benchmarks.
From here you can get the demo for KDE 2.2/Linux
|
1. Rotated axis
|
|
Having a point P (x1,y1) in order to get the coordinated of P into a system of axis having the same origin O and rotated with angle a, have to do: r=sqrt(x1^2+y1^2) sin(f)=y1/r cos(f)=x1/r --- in old axis x2=r.cos(f-a) y2=r.sin(f-a) --- in new axis using the formulas for sin, cos of a diference: sin(a-b)=sin(a)*cos(b)-cos(a)*sin(b) cos(a-b)=cos(a)*cos(b)+sin(a)*sin(b) the final results for the point coordinated in new axis system will be:
|
|||
2. Trigonometrical solution
|
|
Trigonimetrical equation for an "standard" elipse (unrotated and centered in origin) is: x=A*cos(u) y=B*cos(u) where A/B are the value of the 2 elipse radius (oriented on X an Y axis), and u is the angle of the radius for the point. u will be from 0 to 2*PI. But, since the elipse is centered in O (doesn't mater of axis) we always have symetry by origin. So, we can use u just from 0 to PI, calculate the values for x and y, rotate them, then for drawing just reuse these values by changing the sign for calculated values. This have to cut in half the ammount of time the algorithm spend for point calculation. Ofcourse, this optimization, can't be applied if you intend to change the function to draw just a piece of the elipse. In the provided demo, the drawing is implemented by segments. So I iterate with the angle from 0 to PI and calculate the points, then draw a line from the previous points to the curent one. The method of widget provided as demo is void DrawWidget::trigEllipse1(QPainter &p,int xi, int yi, int width, int height, double angle); |
3. Analytical solution
|
The analytical equation for a "standard" elipse is: x^2/A^2+y^2/B^2-1=0 wich generate solution: y=[+|-]B/A*sqrt(A^2-x^2). Well, we can get both y coresponding for an x from this formula, but that means we have to rotate both points. Cause of that in the implementation of the demo, I didn't use this feature, but I used the same simetry by origin as before (in order to avoid to rotate a point). As implementation, I iterated with x from -A to +A, then draw the segment between the previous points and curent one. The method of widget provided as demo is void DrawWidget::anlEllipse1(QPainter &p,int xi, int yi, int width, int height, double angle); |
4. Optimizations
The rotation use the same sin(a) and cos(a) for each point on the elipse. So, we calculate the values sinangle and cosangle once, outside the loop.
|
|
Using simetry by Y axis, we can just calculate the P1(x,y) then getting P2 from it. This calculation have to be performed before apply the rotation. Then we have to rotate both points P1 and P2. After rotation using simetry by origin, we can calculate P3 from P1 and P4 from P2. With this won't have to calculate more than one quadrant using trigonometry (or sqrt). The implementation for the trigonometrical and analytical methods can be seen into void DrawWidget::trigEllipse2(QPainter &p,int xi, int yi, int width, int height, double angle); void DrawWidget::anlEllipse2(QPainter &p,int xi, int yi, int width, int height, double angle); |
5. Benchmarks
The following benchmarks has ben made under a Celeron 433 Mhz, Linux 2.4.7, gcc 2.96.a) Time required for a couple of math functions. The biger time ==> slower speed
sqrt: 81,83,84,86,86,84,88,84,85,87, = 84.800000
sin: 80,85,84,84,85,84,87,84,85,83, = 84.100000
cos: 86,90,92,89,93,90,91,90,91,91, = 90.300000
tan: 108,114,114,115,114,114,113,116,113,115, = 113.600000
mul: 8,8,8,9,9,9,9,8,9,9, = 8.600000
div: 9,9,10,8,8,8,8,9,8,9, = 8.600000
What is interesting here, is that the trigonometrical functions and the sqrt() have comparable speeds, and are about 10 times slower than multiplication and division. So, the main target for any optimizations will first be to get rid off trig. functions and sqrt(). So, the analytical approach, will be faster than the trigonometrical one, since for each calculated point we have to calculate just a sqrt(), in trig. approach we have to calculate both a sin() and a cos() for it. Also, we see that the rotation of points doesn't have a dramatically impact in speed, since the sin & cos are calculated only once for all the points. Rotation use 4 multiplication 1, adition and 1 substraction so it will be less that a sqrt() or a trigonometrical call.
Strange
the tan() is slower that sin() and cos(). Can anybody who know how
the coprocessor is implemented internaly explain this to me?
Personaly,I expected to be the oposite, and I was prepared to change the trig.
formula to calculate everything based on tan(half of angle).
It might help something, since we can calculate the tan() just once and
replace a sin() and a cos(), but anyhow not as dramaticaly as I
expected to be. So I didn't presented these formulas here :-)
From the folklor, I belived, that the coprocessor internaly is implemented to calculate
all the trig. functions based on tan(), but the benchmarks prove here
that this is just a false mith !!!
b) The benchmark run for the 4 algorithms.
anl1: 93,92,93,93,93,92,93,93,93,93, = 92.800000
anl2: 80,81,81,80,80,81,81,80,80,80, = 80.400000
trig1: 101,102,101,101,102,101,101,102,102,101, = 101.400000
trig2: 86,87,85,86,85,85,85,85,85,86, = 85.500000
As
expected, the analytical implementation is faster than
trigonometrical one, in both cases: 92.8 / 101.4 and 80.4 / 85.5
Also, he optimization that require calculating just a quadrant, then
expand the result for other quadrants is visible: 80.4/ 92.8 and 85.5 / 101.4
