tag:blogger.com,1999:blog-1386948037384435441.post7588413996152060894..comments2024-03-01T18:53:33.429-08:00Comments on Jeff Muizelaar: Geometry HomeworkJeff Muizelaarhttp://www.blogger.com/profile/17483047845050494642noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-1386948037384435441.post-37966167418274606632009-10-18T18:55:14.153-07:002009-10-18T18:55:14.153-07:00A quick and dirty comparison puts the polar coordi...A quick and dirty comparison puts the polar coordinate version at about 1050 cycles and the new Cartesian one at about 360 cycles. So just under 3x faster.Jeff Muizelaarhttps://www.blogger.com/profile/17483047845050494642noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-1236056059024980322009-10-18T06:01:23.714-07:002009-10-18T06:01:23.714-07:00It would be very interesting to see the performanc...It would be very interesting to see the performance numbers comparing this algorithm to the existing code.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-66321450017375530312009-10-15T20:36:38.589-07:002009-10-15T20:36:38.589-07:00Yep, it should be mid2. I put that error in when m...Yep, it should be mid2. I put that error in when manually inlining dot() and perp() to post the solution here. Interestingly enough it still passed the tests that I was running.Jeff Muizelaarhttps://www.blogger.com/profile/17483047845050494642noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-881406890471543392009-10-15T11:04:49.103-07:002009-10-15T11:04:49.103-07:00mid2, not mid, in the numerator in the k2 calculat...mid2, not mid, in the numerator in the k2 calculation there at the end, right?Borishttps://www.blogger.com/profile/18001520282139292690noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-31054383677142842772009-10-15T07:51:38.452-07:002009-10-15T07:51:38.452-07:00Last night Boris suggested bisecting the angle twi...Last night Boris suggested bisecting the angle twice and then computing the tan of it. This turns into the following, which seems to work pretty well:<br /><br /> vector_t mid;<br /> mid.x = a.x + b.x;<br /> mid.y = a.y + b.y;<br /> double l = sqrt(mid.x*mid.x + mid.y*mid.y);<br /> mid.x /= l;<br /> mid.y /= l;<br /><br /> vector_t mid2;<br /> mid2.x = a.x + mid.x;<br /> mid2.y = a.y + mid.y;<br /><br /> k2 = (4./3.)*(-a.y*mid.x + a.x*mid.y)/(a.x*mid2.x + a.y*mid2.y);<br /><br />Where 'a' and 'b' are the vectors from the center to the start and end points respectivelyJeff Muizelaarhttps://www.blogger.com/profile/17483047845050494642noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-6511660350918891972009-10-14T22:46:05.810-07:002009-10-14T22:46:05.810-07:00@Jeff,
You can derive from the "Hermite type...@Jeff,<br /><br />You can derive from the "Hermite type approximation" a constant α and and some formulas that let you calculate any given quarter-circle without any polar coordinates. A diagram would probably help: <a href="http://create.ly/g0t26y8y1" rel="nofollow">see here</a> Basically, given the center point C and the desired radius, you can derive the other three points of the bounding square, A, B, D. B and D are the Bezier endpoints, and the constant α lets you calculate the control points P and Q trivially - the notation α(D→A) means "form the vector from D to A, then multiply it by α".<br /><br />You then have to cut up the Bezier if you don't want the whole quarter-circle, but I believe that can be done with no trig either.Zack Weinberghttps://www.blogger.com/profile/09886144371565535869noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-83702982345812106532009-10-14T18:19:40.724-07:002009-10-14T18:19:40.724-07:00@Zack,
I've quickly skimmed through the paper...@Zack,<br /><br />I've quickly skimmed through the paper by Goldapp. He gives the tan(a/4) formulation in the "Hermite-type approximation" section. The other formulations, although potentially more accurate, seemed more complicated than they were worth.<br />Also, as far as I could tell, the formulations he gives all use polar coordinates?Jeff Muizelaarhttps://www.blogger.com/profile/17483047845050494642noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-23031014261342628962009-10-14T18:12:05.626-07:002009-10-14T18:12:05.626-07:00@Brendan: We convert arcs to cubic bezier splines ...@Brendan: We convert arcs to cubic bezier splines because that's what's supported by cairo's path format. There's been talk of keeping arcs as arcs instead of approximating them by splines. However, the additional curve type adds complexity.<br /><br />Interestingly enough, Postscript had support for arcs but this was removed in PDF.Jeff Muizelaarhttps://www.blogger.com/profile/17483047845050494642noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-583754278877420932009-10-14T17:47:05.599-07:002009-10-14T17:47:05.599-07:00Boris,
The input is the center and the two end po...Boris,<br /><br />The input is the center and the two end points for the arc.<br /><br />Brendan,<br /><br />This code will not necessarily be used for implementing cairo_arc because that already use polar coordinates. The Cartesian version is for round joins and caps.Jeff Muizelaarhttps://www.blogger.com/profile/17483047845050494642noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-5446200445318464682009-10-14T16:21:39.727-07:002009-10-14T16:21:39.727-07:00Boris, the cairo api has
void cairo_arc(cairo_t *...Boris, the cairo api has<br /><br />void cairo_arc(cairo_t *cr, double xc, double yc, double radius, double angle1, double angle2);Unknownhttps://www.blogger.com/profile/11594518327193290812noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-37493275568192316412009-10-14T16:15:46.330-07:002009-10-14T16:15:46.330-07:00rethinking this, maybe you use cubic splines becau...rethinking this, maybe you use cubic splines because you can transform just the 4 points? if you do want to check out Blinn's article: page 5 and 6 have two of the better algorithms, but...<br /><br /><a href="http://books.google.com/books?id=KBDS6GAwSwAC&lpg=PP1&pg=PA1#v=onepage&q=&f=false" rel="nofollow">Google Books: How Many Ways Can You Draw A Circle?</a>Unknownhttps://www.blogger.com/profile/11594518327193290812noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-16701175476832104772009-10-14T16:06:31.913-07:002009-10-14T16:06:31.913-07:00Jeff, what's the actual input into the algorit...Jeff, what's the actual input into the algorithm here? Is it the center and the two arc endpoints? Or the two angles A and B? Or something else?Borishttps://www.blogger.com/profile/18001520282139292690noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-85772452264747568842009-10-14T16:03:22.412-07:002009-10-14T16:03:22.412-07:00I'll try the challenge...but is there a reason...I'll try the challenge...but is there a reason you're using cubic splines? Jim Blinn's excellent "How many ways can you draw a circle?" gives a great selection of circle (and arc) drawing algorithms, most of them for vector displays...perfect if you need to decompose the arc into line segments.Unknownhttps://www.blogger.com/profile/11594518327193290812noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-26124401849855474482009-10-14T14:52:39.471-07:002009-10-14T14:52:39.471-07:00As a note, you could turn my explanation into a de...As a note, you could turn my explanation into a derivation by simply running the steps backwards, as long as |(B-A/2)| < pi/2 and B-A != 0.Borishttps://www.blogger.com/profile/18001520282139292690noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-35622688852468846052009-10-14T14:47:16.420-07:002009-10-14T14:47:16.420-07:00OK. So the formula for k2 there gives exactly the...OK. So the formula for k2 there gives exactly the same value as the formula for h, up to sign. I didn't check the signs, but they should be checkable without too much trouble.<br /><br />Proof: The 4/3 is the same in both formulas and can be dropped for purposes of comparing the two values. If R is the radius of the circle, then we have:<br /><br />q1 = R^2<br />q2 = R^2 + R^2 cos (B - A)<br /><br />(since q1 - q1 is just the dot product of (ax,ay) and (bx,by), and the two vectors both have length R and have angle B-A between them.<br /><br />|ax*by - ay*bx| is just the length of the cross product of the two vectors considered as three-dimensional vectors, and has magnitude R^2*|sin(B-A)|. I'm going to drop the absolute value; this is where you'd need to check your signs.<br /><br />Now we have (ignoring the 4/3):<br /><br />k2 = (sqrt(2*R^2*R^2(1 + cos(B-A))) - R^2 - R^2*cos(B-A))/(R^2*sin(B-A).<br /><br />All the R^2 go away, and we are left with:<br /><br />k2 = (sqrt(2(1+cos(B-A)) - 1 - cos(B-A))/sin(B-A)<br /><br />Now we use the identity: 1 + cos(x) = 2cos^2(x/2) to get:<br /><br />k2 = (2cos((B-A)/2) - 2cos^2((B-A)/2)) / sin(B-A)<br /><br />and then use sin(2x) = 2sin(x)cos(x) to get:<br /><br />k2 = (1 - cos((B-A)/2))/(sin((B-A)/2)<br /><br />Now use 1 - cos(x) = 2sin^2(x/2) and the sin(2x) formula again to get:<br /><br />k2 = sin((B-A)/4)/cos((B-A)/4)<br /><br />and we're done.<br /><br />At least an explanation, right? ;)Borishttps://www.blogger.com/profile/18001520282139292690noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-65677253799489927042009-10-14T14:05:33.582-07:002009-10-14T14:05:33.582-07:00First off, your formulas for pt2 and pt3 don't...First off, your formulas for pt2 and pt3 don't match the paper's. The paper has, for example:<br /><br />pt2.x = pt1.x + center.x - k2*pt1.y<br /><br />This is clearly bogus, if I understand how this stuff is supposed to work, since that gives the wrong direction at pt1. Your formula for pt2 is more likely to be correct (though your formula for pt3 seems to have bx and by switched).Borishttps://www.blogger.com/profile/18001520282139292690noreply@blogger.comtag:blogger.com,1999:blog-1386948037384435441.post-35423488397269859982009-10-14T12:24:09.178-07:002009-10-14T12:24:09.178-07:00I spent a bunch of time staring at this problem fo...I spent a bunch of time staring at this problem for rounded rectangle drawing in Mozilla's Thebes wrapper. You might find the big long comment starting at http://mxr.mozilla.org/mozilla-central/source/gfx/thebes/src/gfxContext.cpp#806 helpful, and the papers cited there (especially the one by Michael Goldapp; <a href="http://dx.doi.org/10.1016/0167-8396(91)90007-X" rel="nofollow">doi:10.1016/0167-8396(91)90007-X</a>). Unfortunately, it's not available online for free. And I have no idea about the numerical stability when the two arc endpoints are close.<br /><br />Incidentally, it would be great if Cairo had direct support for SVG elliptical arcs as path segments...Zack Weinberghttps://www.blogger.com/profile/09886144371565535869noreply@blogger.com