On Fri, Oct 31, 2008 at 8:15 AM, Tom Forsyth <tom.forsyth@eelpi.gotdns.org> 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.


From: Charles Nicholson [mailto:charles.nicholson@gmail.com]
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 <tom.forsyth@eelpi.gotdns.org>
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.


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
GDAlgorithms-list mailing list