## Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes

 Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes From: Tom Forsyth - 2008-11-02 19:03:46 ```There's a bunch of heuristics, none of which we were that happy with. When I worked on Granny it first inserted knots at discontinuities, then used recursive midpoint subdivision for places where the errors exceeded the set tolerance. For non-obvious reasons, *midpoint* subdivision worked better than putting the knot at the place of highest error. We had some hand-wavy explanations why this way that I never really bought into, but it certainly did work better. Dave Moore who is now on Granny has tried a few other heuristics as well. The most notable one is removing knots - the midpoint subdivision can add too many knots getting to the required error tolerance, and so a pruning phase of finding redundant knots can help quite a bit. There's lots of ways of picking which knots to remove, and I forget which he found worked best. But yes - it's just all a bunch of hacks and experience and large data sets to play with :-) TomF. From: Charles Nicholson [mailto:charles.nicholson@...] Sent: Sunday, November 02, 2008 10:12 AM To: Game Development Algorithms Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes On Fri, Oct 31, 2008 at 8:15 AM, Tom Forsyth wrote: Spot on. I think there may be words from Casey Muratori in the archives about this, or here: http://mollyrocket.com/942 It seems like knot time selection is pretty important, but in that write-up Casey sort of glosses over it, claiming that he "uses heuristics" to select times.   If you're not using heuristics and you're actually hunting down the global maximum, probably defined by some weighted combination of least error and minimal knot count, it seems like it becomes a nice little NP-complete number (homeomorphic to 0-1 knapsack?) and you start using things like dynamic programming methods, etc... to search the space.  This seems like a hell of a lot of hard work and diminishing returns if 'dumber' approaches can yield good-enough solutions. So what heuristics work well here for picking knot times?  Is it just inflection points? I realize we're talking about the internal guts of a commercial animation exporter here, though, and understand if sharing isn't appropriate. -charles From: Charles Nicholson [mailto:charles.nicholson@...] Sent: Thursday, October 30, 2008 2:37 PM To: Game Development Algorithms Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes On Tue, Oct 14, 2008 at 7:54 PM, Tom Forsyth wrote: You really need to be fitting splines to your data.  Even if those splines happen to be degree-1 (i.e. linear segments - they certainly have their uses), the point is that even with an interpolating spline, the control points do not necessarily lie on the original sampled data, nor do they lie on the sampled times. Thread necromancy! Out of curiosity, what's the canonical approach for fitting a splines to control points?  I'm imagining some non-linear least-squares approach where you're minimizing the error between the spline and the keyframe values, which seems like it leads to inverting very large and sparse matrices. -charles ------------------------------------------------------------------------- This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100&url=/ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```