keith@EXPO.LCS.MIT.EDU (Keith Packard) (11/24/88)
The appropriate way to fix the arc code is to special case zero and one width wide arcs and avoid the complicated mathematics required in the general case. The definition of a wide arc has been taken quite literally in R3, my aim was not for performance, rather a demonstration of correctness. The central problem lies in the difficulty of solving exactly the intercept coordinates of an arbitrary horizontal line (a span) with the inner and outer edges of the arc. The boundaries of the arc are defined by the set of points line_width/2 along a normal to the elipse from the elipse. The solution seems an easy one, simply compute an equation which describes the boundary, and solve for x in terms of y. Unfortunately, the equation takes a nasty turn. At one point, I created a 13 page equation with macsyma, which needed to be substituted into several other equations (much smaller, say 1/2 page). So, the current code uses Newtons method to solve the equation to the desired precision. Not perfect, but quite reasonable. This equation is solved three times for each horizontal span along the elipse. Three times because of some special cases with strange elipses. Try computing a 1000x100 elipse and a 100x1000 elipse and notice how much longer the second one takes. This is why filled elipses are so much faster. Although they aren't correct yet, even a better solution need not solve the difficult problem described above; the boundary of the filled shape is a simple elipse. Now, of course, this is only the solution for *solid* arcs. Dashes provide ample opportunity for algorithmic dancing. Ideally, the dashes would be spaced along the elipse by computing the path length of segments of the elipse. If this sounds familiar to you from analysis classes, it should. Eliptic integrals are probably one of the most studied forms not solvable in closed form. Bleah again. The code in the sample server takes a cheap approach. It approximates the elipse by using a diamond. Fortunately, the protocol document allows this approximation by not specifying how the dashes are to be computed. Because of the amount of time I spent with this code, I had to leave it before I had profiled and optimized it. I suspect it could run about 2 or 3 times as fast by making some fairly minor optimizations. As I have not collected any data, this is more hopeful than expected. Other optimizations include: o special case 1 width arcs. The equations might be easier to solve than in the general case. o special case circular arcs. The equations are solvable in closed form quite easily. o redesign the span-merging code to avoid some computation. This is less useful, as the code isn't too bad right now. Most useful would be to eliminate the immense amount of small memory allocation which occurs in this code. I'm not well versed in numerical methods, perhaps a better solution for some of the equations could be designed. Also, using GCC and substituting float arithmetic for double could substantially improve performance on many machines, at some sacrifice in accuracy. Keith Packard MIT X Consortium (617) 253-1428 keith@EXPO.LCS.MIT.EDU