Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes
Tom Forsyth <tom.forsyth <at> eelpi.gotdns.org>
2008-11-02 19:05:35 GMT
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 <at> gmail.com]
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 <tom.forsyth <at> 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.
-charles
From: Charles Nicholson [mailto:charles.nicholson <at> 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 <at> eelpi.gotdns.org>
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 <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
-------------------------------------------------------------------------
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 <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
RSS Feed