--- Log opened Sat Apr 21 00:00:25 2007
00:08 -!- zotz [n=zotz@24.244.163.157] has quit ["Leaving"]
00:10 -!- tokyo [n=tokyo@c-67-186-99-98.hsd1.il.comcast.net] has joined #synfig
00:22 < dooglus> igli: I've just worked out that the 'well-tested implementation' we found on google groups for the bezier problem doesn't really work...
00:22 < dooglus> http://groups.google.com/group/comp.graphics.algorithms/browse_thread/thread/19105107cae8b40b/4244f7787f3ff7d8?lnk=st#4244f7787f3ff7d8 is the program
00:22 < igli> oh man
00:22 < dooglus> and http://dooglus.rincevent.net/synfig/bezier.png shows an example where it fails
00:23 < dooglus> trying to find which point on the black curve is closest to point P, it compares the two rectangles, finds that the 'left' half of the curve is closer than the right half, and manages to come up with completely the wrong answer.
00:23 < dooglus> so that explains why it was quicker - it was cheating :)
00:23 < igli> ah i c
00:23 < igli> lol
00:24 < igli> guess we're back to optimising the other one then
00:24 < dooglus> I've emailed the guy who wrote that newsgroup article (10 years ago or so?) telling him about the problem
00:24 < igli> altho it does bug me; you'f think it would see which endpoint was closer
00:24 < dooglus> so maybe he'll come up with a fix for it
00:25 < igli> heh he prob'y sells the fixed version
00:25 < dooglus> the code looks to see where the point lies compared to the 2 rectangles
00:25 < dooglus> in this case, they're both:
00:25 < dooglus>         /* Point above bounding box                                     */
00:25 < dooglus> 	case 7:         return(py-ury)*(py-ury);
00:25 < dooglus> in which the only thing that matters is the vertical distance between the point and the top of the box
00:26 < dooglus> since the blue box is slightly higher than the red one at the top, that's the one it recurses into
00:26 < dooglus> but the correct answer is in the red box :(
00:26 < igli> yeah, got that ;) the base of the rectangles as we see it, is that an easily-defined line?
00:27 < dooglus> it divides the curve into 2 halves, and draws a rectangle around each half
00:27 < igli> well first thing that comes to mind is choosing the rectangle by distance to endpoint A or B
00:27 < dooglus> Casteljau tells us how to do that
00:27 < dooglus> here: http://en.wikipedia.org/wiki/De_Casteljau_algorithm#Geometrical_interpretation
00:27 < igli> ok, i haven't done any of this stuff tbh.
00:27 < igli> thanks :)
00:29 < igli> interesting
00:30 < dooglus> I can't see anything immediately why your suggestion won't work
00:30 < dooglus> but I've a feeling it won't
00:30 < igli> wouldn't surprise me a bit
00:31 < dooglus> the way I found this example was to run synfig with both the old and new algorithms running, and getting it to print out the cases where they came up with wildly different results
00:31 < igli> forgive me for being thick (and slow- been up for ages) but does this mean that recursive procedure?
00:31 < dooglus> anyway - I'd best go get some sleep.  early start in the morning.
00:31 < igli> good move;
00:31 < igli> ok night
00:31 < dooglus> I'll answer you -
00:32 < dooglus> I'm talking about comparing the 'Graphics Gems' code that works but is slow, with this 'Kinch' code from Google Groups (which is fast, but turns out to be a bit broken)
00:32 < dooglus> running both of those at once and comparing the results.
00:32 < dooglus> so.  goodnight.  :)
00:32 < igli> yeah i know that ;)
00:32 < igli> night
00:44 < igli> Philip J. Schneider in 
00:44 < igli>  Graphics Gems 1 - "Solving the Nearest-Point-on-Curve Problem".
00:45 < igli> http://truetex.com/bezint.htm # two curves
00:48 < igli> I notice from looking at your page that you are dealing with finding the intersections between two curves - a much more difficult problem than finding the distance from a point to a curve (which I think was the original question). The distance calculation will reduce to a one dimensional equation of order k(k-1) for a curve of order k, in n dimensions.  This can be solved by standard root finding techniques, without the difficulties you speak of in relation
00:49 < igli> to two curves intersecting. 
00:49 < igli> There are indeed root-finding techniques that are appropriate.  The problem is that the one suggested either bogs down or fails to converge with very broad, flat minima; these are very common in many applications of 2D cubic Bezier curves, just as the intersection problem can have broad, flat minima.
00:49 < igli> well that was riveting ;)
01:26 -!- igli [n=igli@unaffiliated/igli] has quit [Remote closed the connection]
02:04 -!- zotz [n=zotz@24.244.163.157] has joined #synfig
04:53 -!- pxegeek [n=chatzill@c-71-59-140-184.hsd1.or.comcast.net] has joined #synfig
05:02 -!- zotz [n=zotz@24.244.163.157] has quit ["Leaving"]
06:53 -!- pxegeek [n=chatzill@c-71-59-140-184.hsd1.or.comcast.net] has quit [Read error: 113 (No route to host)]
09:17 -!- xerakko [n=xerakko@debian/developer/xerakko] has quit [Remote closed the connection]
10:59 -!- igli [n=igli@unaffiliated/igli] has joined #synfig
11:56 -!- zipola [n=zipola@zip.kortex.jyu.fi] has joined #synfig
12:06 -!- sciboy [n=sciboy@203-217-74-147.dyn.iinet.net.au] has joined #synfig
12:33 -!- zipola [n=zipola@zip.kortex.jyu.fi] has quit ["Abiit"]
12:37 -!- zipola [n=zipola@zip.kortex.jyu.fi] has joined #synfig
12:38 -!- zipola [n=zipola@zip.kortex.jyu.fi] has quit [Client Quit]
12:55 -!- sciboy [n=sciboy@unaffiliated/sciboy] has quit ["Leaving"]
14:25 -!- zotz [n=zotz@24.244.163.157] has joined #synfig
16:33 -!- zotz [n=zotz@24.244.163.157] has quit ["Leaving"]
17:33 -!- igli [n=igli@unaffiliated/igli] has quit [Remote closed the connection]
18:01 -!- zipola [n=zipola@zip.kortex.jyu.fi] has joined #synfig
18:01 -!- zipola [n=zipola@zip.kortex.jyu.fi] has quit [Client Quit]
19:54 -!- sciboy_ [n=sciboy@203-217-74-147.dyn.iinet.net.au] has joined #synfig
19:55 -!- sciboy_ [n=sciboy@203-217-74-147.dyn.iinet.net.au] has quit [Client Quit]
20:11 -!- zipola [n=zipola@zip.kortex.jyu.fi] has joined #synfig
20:13 -!- zipola [n=zipola@zip.kortex.jyu.fi] has quit [Client Quit]
20:14 -!- zipola [n=zipola@zip.kortex.jyu.fi] has joined #synfig
20:56 -!- pxegeek [n=chatzill@c-71-59-140-184.hsd1.or.comcast.net] has joined #synfig
21:42 -!- zotz [n=zotz@24.244.163.157] has joined #synfig
22:33 -!- igli [n=igli@unaffiliated/igli] has joined #synfig
22:49 -!- omry [n=omry@l85-130-137-23.broadband.actcom.net.il] has quit [Read error: 104 (Connection reset by peer)]
23:12 -!- omry [n=omry@l85-130-137-23.broadband.actcom.net.il] has joined #synfig
23:31 -!- Netsplit herbert.freenode.net <-> irc.freenode.net quits: tokyo, pxegeek, igli
23:31 -!- Netsplit over, joins: igli, pxegeek, tokyo
23:43 -!- omry__ [n=omry@l85-130-137-23.broadband.actcom.net.il] has joined #synfig
23:45 -!- omry [n=omry@l85-130-137-23.broadband.actcom.net.il] has quit [Read error: 60 (Operation timed out)]
--- Log closed Sun Apr 22 00:00:25 2007