Thread: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes
Brought to you by:
vexxed72
From: <Bra...@pl...> - 2008-10-10 21:02:14
|
I was just talking to a friend at lunch about using variable rate cubic-interpolated keyframes (as exported from your favorite DCC package) directly vs. using fixed-rate presampled linear-interpolated keyframes in an animation runtime. I'm not an expert on animation code by any stretch, so I was wondering, beyond the classic CPU time vs. memory trade off, what are some of the more subtle pros and cons for using each? In what situations would you chose one over the other? Thanks! Brad... |
From: Greg S. <gr...@mi...> - 2008-10-13 04:54:09
|
I think you're polarizing your options too far apart. Variable-rate linear keys are a good compromise, and the DCC keys can be used as a guide for key selection. My main issue with using the DCC keys verbatim is that you force the animator to work conservatively in order to serve compression. If further compression is required, you may need to go all the way back to the DCC package to reduce the keys. A sampled approach, even if guided by DCC keys, lifts that burden from the animator and moves the compression size-vs-quality decision further down the pipeline. ________________________________________ From: Bra...@pl... [Bra...@pl...] Sent: Friday, October 10, 2008 1:49 PM To: gda...@li... Subject: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes I was just talking to a friend at lunch about using variable rate cubic-interpolated keyframes (as exported from your favorite DCC package) directly vs. using fixed-rate presampled linear-interpolated keyframes in an animation runtime. I'm not an expert on animation code by any stretch, so I was wondering, beyond the classic CPU time vs. memory trade off, what are some of the more subtle pros and cons for using each? In what situations would you chose one over the other? Thanks! Brad... ------------------------------------------------------------------------- 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 GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: <Bra...@pl...> - 2008-10-13 17:48:27
|
Excellent points. I'm totally open to using options between those two extremes, including sampling the curve at variable intervals. Are there any magic google phrases/canonical links for resampling/reducing animation curves? My current searches mainly turn up messages in the archives of this list. (Not that that's bad, but a nice tutorial or paper might be a better starting point.) Thanks! Brad... Greg Snook <gr...@mi...> 10/12/2008 09:53 PM Please respond to Game Development Algorithms <gda...@li...> To Game Development Algorithms <gda...@li...> cc Subject Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes I think you're polarizing your options too far apart. Variable-rate linear keys are a good compromise, and the DCC keys can be used as a guide for key selection. My main issue with using the DCC keys verbatim is that you force the animator to work conservatively in order to serve compression. If further compression is required, you may need to go all the way back to the DCC package to reduce the keys. A sampled approach, even if guided by DCC keys, lifts that burden from the animator and moves the compression size-vs-quality decision further down the pipeline. ________________________________________ From: Bra...@pl... [Bra...@pl...] Sent: Friday, October 10, 2008 1:49 PM To: gda...@li... Subject: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes I was just talking to a friend at lunch about using variable rate cubic-interpolated keyframes (as exported from your favorite DCC package) directly vs. using fixed-rate presampled linear-interpolated keyframes in an animation runtime. I'm not an expert on animation code by any stretch, so I was wondering, beyond the classic CPU time vs. memory trade off, what are some of the more subtle pros and cons for using each? In what situations would you chose one over the other? Thanks! Brad... ------------------------------------------------------------------------- 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 GDA...@li... 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 GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jon W. <jw...@gm...> - 2008-10-13 19:45:39
|
Bra...@pl... wrote: > Are there any magic google phrases/canonical links for resampling/reducing > animation curves? My current searches mainly turn up messages in the > archives of this list. (Not that that's bad, but a nice tutorial or paper > might be a better starting point.) > The KiloWatt X-port plug-in for 3ds Max is open source, and does keyframe reduction using linear interpolation based on sampled data. Hopefully, working code is worth something :-) The code is BSD/MIT style license, too, so it's OK to ship on closed platforms etc. http://www.kwxport.org/ Sincerely, jw |
From: Tom F. <tom...@ee...> - 2008-10-14 05:18:45
|
The Granny3D answer is "both" :-) It first bakes everything into keyframed data, then fits cubic (in this case non-uniform rational B-spline) curves through it. The baking removes the wacky dependencies on whatever the DCC tool uses to represent its data (and there's some serious wackiness there), but gives you all the advantages of splines - i.e. smoothness and high compression. TomF. > -----Original Message----- > From: Bra...@pl... > [mailto:Bra...@pl...] > Sent: Friday, October 10, 2008 1:50 PM > To: gda...@li... > Subject: [Algorithms] Variable rate cubic keyframes vs. sampled fixed > rate linear keyframes > > I was just talking to a friend at lunch about using variable rate > cubic-interpolated keyframes (as exported from your favorite DCC > package) > directly vs. using fixed-rate presampled linear-interpolated keyframes > in > an animation runtime. I'm not an expert on animation code by any > stretch, > so I was wondering, beyond the classic CPU time vs. memory trade off, > what > are some of the more subtle pros and cons for using each? In what > situations would you chose one over the other? > > Thanks! > > Brad... > > > ----------------------------------------------------------------------- > -- > 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms- > list |
From: Sylvain G. V. <vi...@ii...> - 2008-10-14 05:50:27
|
From: Tom Forsyth <tom...@ee...> > The Granny3D answer is "both" :-) It first bakes everything into > keyframeddata, then fits cubic (in this case non-uniform rational B- > spline) curves > through it. The baking removes the wacky dependencies on whatever > the DCC > tool uses to represent its data (and there's some serious wackiness > there),but gives you all the advantages of splines - i.e. > smoothness and high > compression. Yes, I used to do the same: baking animations in Maya, exporting every keyframes (using Collada most of the time), and getting rid of interpolatable keyframes. Checking if keyframes can be linearly interpolated between the previous kept one and the next keyframe works surprisingly well for such a straight-forward algorithm (as long as one take care of a few special cases, like keeping keyframes where a movement inverse its direction, for example to keep small oscillations in robotic or in hit animations). More intricate non-linear interpolation schemes will save a bit more memory space of course. |
From: Richard F. <ra...@gm...> - 2008-10-14 10:51:41
|
I've found that for linear interpolater culling, I made marginal savings while maintaining quality by doing multiple passes of the animation key frame data. I'd do a pass and cull any key I came across, but rather than continuing on to the next key, I'd skip one, assuring myself that I had a good robust base key to make the next cull decision about. It seems to maintain impact animations better than not doing it for the same amount of foot slide and keys. 2008/10/14 Sylvain G. Vignaud <vi...@ii...> > From: Tom Forsyth <tom...@ee...> > > The Granny3D answer is "both" :-) It first bakes everything into > > keyframeddata, then fits cubic (in this case non-uniform rational B- > > spline) curves > > through it. The baking removes the wacky dependencies on whatever > > the DCC > > tool uses to represent its data (and there's some serious wackiness > > there),but gives you all the advantages of splines - i.e. > > smoothness and high > > compression. > > Yes, I used to do the same: baking animations in Maya, exporting every > keyframes (using Collada most of the time), and getting rid of > interpolatable keyframes. > > Checking if keyframes can be linearly interpolated between the previous > kept one and the next keyframe works surprisingly well for such a > straight-forward algorithm (as long as one take care of a few special > cases, like keeping keyframes where a movement inverse its direction, > for example to keep small oscillations in robotic or in hit animations). > > More intricate non-linear interpolation schemes will save a bit more > memory space of course. > > > ------------------------------------------------------------------------- > 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- fabs(); Just because the world is full of people that think just like you, doesn't mean the other ones can't be right. |
From: Sylvain G. V. <vi...@ii...> - 2008-10-15 00:40:53
|
From: Richard Fabian <ra...@gm...> > I've found that for linear interpolater culling, I made marginal > savingswhile maintaining quality by doing multiple passes of the > animation key > frame data. I'd do a pass and cull any key I came across, but > rather than > continuing on to the next key, I'd skip one, assuring myself that I > had a > good robust base key to make the next cull decision about. It seems to > maintain impact animations better than not doing it for the same > amount of > foot slide and keys. Another trick I found: when trying to interpolate keyframe N from keyframe M (M being the last kept keyframe, where M <= N-1) and keyframe N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) is counter productive. The reason is quite obvious: we don't know if the next keyframe at N+1 will be kept. Trying an interpolation with a 50% ratio, whatever the time difference with the previous keyframe is, gave me a bit more accurate results. > 2008/10/14 Sylvain G. Vignaud <vi...@ii...> > > > From: Tom Forsyth <tom...@ee...> > > > The Granny3D answer is "both" :-) It first bakes everything into > > > keyframeddata, then fits cubic (in this case non-uniform > rational B- > > > spline) curves > > > through it. The baking removes the wacky dependencies on whatever > > > the DCC > > > tool uses to represent its data (and there's some serious > wackiness> > there),but gives you all the advantages of splines - i.e. > > > smoothness and high > > > compression. > > > > Yes, I used to do the same: baking animations in Maya, exporting > every> keyframes (using Collada most of the time), and getting rid of > > interpolatable keyframes. > > > > Checking if keyframes can be linearly interpolated between the > previous> kept one and the next keyframe works surprisingly well > for such a > > straight-forward algorithm (as long as one take care of a few > special> cases, like keeping keyframes where a movement inverse its > direction,> for example to keep small oscillations in robotic or in > hit animations). > > > > More intricate non-linear interpolation schemes will save a bit more > > memory space of course. > > > > > > ------------------------------------------------------------------ > ------- > > 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 > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > > > > -- > fabs(); > Just because the world is full of people that think just like you, > doesn'tmean the other ones can't be right. > |
From: Tom F. <tom...@ee...> - 2008-10-15 02:57:11
|
Just incrementally dropping keyframes can suck - you get nasty local-minima effects like this, and the low efficiency really adds up. 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. Also important for good compression is good quantization of the control points. And quantization of time is just as important as quantization of space. You have to do the quantization while you're doing the spline fitting, or you'll get poor results - it's usually an iterative process of fit/quant/fit/quant until you reach required tolerance. It all gets fiddly and complex very quickly with a lot of non-obvious heuristics to tweak. TomF. (disclaimer - I don't have anything financial to do with Granny3D any more, though I do still work in the same office) > -----Original Message----- > From: Sylvain G. Vignaud [mailto:vi...@ii...] > Sent: Tuesday, October 14, 2008 5:41 PM > To: Game Development Algorithms > Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled > fixed rate linear keyframes > > From: Richard Fabian <ra...@gm...> > > I've found that for linear interpolater culling, I made marginal > > savingswhile maintaining quality by doing multiple passes of the > > animation key > > frame data. I'd do a pass and cull any key I came across, but > > rather than > > continuing on to the next key, I'd skip one, assuring myself that I > > had a > > good robust base key to make the next cull decision about. It seems > to > > maintain impact animations better than not doing it for the same > > amount of > > foot slide and keys. > > Another trick I found: when trying to interpolate keyframe N from > keyframe M (M being the last kept keyframe, where M <= N-1) and > keyframe > N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) > is counter productive. The reason is quite obvious: we don't know if > the > next keyframe at N+1 will be kept. > > Trying an interpolation with a 50% ratio, whatever the time difference > with the previous keyframe is, gave me a bit more accurate results. > > > > > > > > > 2008/10/14 Sylvain G. Vignaud <vi...@ii...> > > > > > From: Tom Forsyth <tom...@ee...> > > > > The Granny3D answer is "both" :-) It first bakes everything into > > > > keyframeddata, then fits cubic (in this case non-uniform > > rational B- > > > > spline) curves > > > > through it. The baking removes the wacky dependencies on whatever > > > > the DCC > > > > tool uses to represent its data (and there's some serious > > wackiness> > there),but gives you all the advantages of splines - > i.e. > > > > smoothness and high > > > > compression. > > > > > > Yes, I used to do the same: baking animations in Maya, exporting > > every> keyframes (using Collada most of the time), and getting rid of > > > interpolatable keyframes. > > > > > > Checking if keyframes can be linearly interpolated between the > > previous> kept one and the next keyframe works surprisingly well > > for such a > > > straight-forward algorithm (as long as one take care of a few > > special> cases, like keeping keyframes where a movement inverse its > > direction,> for example to keep small oscillations in robotic or in > > hit animations). > > > > > > More intricate non-linear interpolation schemes will save a bit > more > > > memory space of course. > > > > > > > > > ------------------------------------------------------------------ > > ------- > > > 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 > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > > > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms- > list > > > > > > > > > > > -- > > fabs(); > > Just because the world is full of people that think just like you, > > doesn'tmean the other ones can't be right. > > > > ----------------------------------------------------------------------- > -- > 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms- > list |
From: Charles N. <cha...@gm...> - 2008-10-30 21:46:54
|
On Tue, Oct 14, 2008 at 7:54 PM, Tom Forsyth <tom...@ee...>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 |
From: Tom F. <tom...@ee...> - 2008-10-31 16:13:53
|
Spot on. I think there may be words from Casey Muratori in the archives about this, or here: http://mollyrocket.com/942 TomF. From: Charles Nicholson [mailto:cha...@gm...] 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...@ee...> 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 |
From: Charles N. <cha...@gm...> - 2008-10-31 16:48:42
|
On Fri, Oct 31, 2008 at 9:15 AM, Tom Forsyth <tom...@ee...>wrote: > Spot on. I think there may be words from Casey Muratori in the archives > about this, or here: http://mollyrocket.com/942 > That looks like a whole lot of not fun to write. Great link though, thanks! -c From: Charles Nicholson [mailto:cha...@gm...] > 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...@ee... > > > 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Tom F. <tom...@ee...> - 2008-11-01 05:49:35
|
It was pretty evil to maintain, so I cant imagine what a pain it was to write in the first place. TomF. From: Charles Nicholson [mailto:cha...@gm...] Sent: Friday, October 31, 2008 9:49 AM To: Game Development Algorithms Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes On Fri, Oct 31, 2008 at 9:15 AM, Tom Forsyth <tom...@ee...> wrote: Spot on. I think there may be words from Casey Muratori in the archives about this, or here: http://mollyrocket.com/942 That looks like a whole lot of not fun to write. Great link though, thanks! -c From: Charles Nicholson [mailto:cha...@gm...] 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...@ee...> 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 GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Charles N. <cha...@gm...> - 2008-11-02 18:12:34
|
On Fri, Oct 31, 2008 at 8:15 AM, Tom Forsyth <tom...@ee...>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:cha...@gm...] > 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...@ee... > > > 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Tom F. <tom...@ee...> - 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:cha...@gm...] 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...@ee...> 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:cha...@gm...] 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...@ee...> 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 GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jon W. <jw...@gm...> - 2008-10-15 17:51:22
|
Sylvain G. Vignaud wrote: > From: Richard Fabian <ra...@gm...> > >> frame data. I'd do a pass and cull any key I came across, but >> rather than >> continuing on to the next key, I'd skip one, assuring myself that I >> > Another trick I found: when trying to interpolate keyframe N from > keyframe M (M being the last kept keyframe, where M <= N-1) and keyframe > N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) > is counter productive. The reason is quite obvious: we don't know if the > next keyframe at N+1 will be kept. > I'm with Richard for this: Doing recursive improvement seems to work great for removing all the almost-static keys, and reducing only harmless keys in areas of action. Sincerely, jw |
From: <Bra...@pl...> - 2008-10-15 21:10:55
|
Thanks for all the useful replies, everyone! Brad... Jon Watte <jw...@gm...> wrote on 10/15/2008 10:15:38 AM: > Sylvain G. Vignaud wrote: > > From: Richard Fabian <ra...@gm...> > > > >> frame data. I'd do a pass and cull any key I came across, but > >> rather than > >> continuing on to the next key, I'd skip one, assuring myself that I > >> > > > Another trick I found: when trying to interpolate keyframe N from > > keyframe M (M being the last kept keyframe, where M <= N-1) and keyframe > > N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) > > is counter productive. The reason is quite obvious: we don't know if the > > next keyframe at N+1 will be kept. > > > > I'm with Richard for this: Doing recursive improvement seems to work > great for removing all the almost-static keys, and reducing only > harmless keys in areas of action. > > Sincerely, > > jw > > > ------------------------------------------------------------------------- > 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Jason H. <jas...@di...> - 2008-10-18 21:43:03
|
Hey Brad, I had one last comment to add, which hadn't really been talked about. My engine uses sampled keys for skinned animations, mainly because baking a bunch of inputs down to curves with any kind of complex rig (think per-animation control skeletons with IK and constraints and SDKs) will not give you a simple curve with just a few knots on your curves. Sampled keyframes are actually smaller and cheaper on the CPU if the keys are too close together on curves. For all non-skinned animations, say for platforms or hierarchies of transforms, etc, I just grab the (non-weighted tangent Hermite) curves and implemented them directly, including all the pre- and post-infinity tangent types. This is super super cheap in terms of memory, and generally have very few keys set on background or level objects. The best thing with these kinds of actors in the scene is a smart animator can give you differently-scaled cycles on the curves, so without putting any programmer time in, you can get very clean and artist-driven animations that are not repetitive, ie. a platform with a rotating cog on it, where the platform carries the cog along with it slowly while the cog rotates quickly. Or ping-ponging animations using post-infinity tangent types. Pretty handy stuff, and really appropriate for level building. I'm not sure there's a reason to use this for characters, since most of the time, you want to kick off an animation that involves the whole body and blending... JH Bra...@pl... wrote: > Thanks for all the useful replies, everyone! > > Brad... > > > Jon Watte <jw...@gm...> wrote on 10/15/2008 10:15:38 AM: > > >> Sylvain G. Vignaud wrote: >> >>> From: Richard Fabian <ra...@gm...> >>> >>> >>>> frame data. I'd do a pass and cull any key I came across, but >>>> rather than >>>> continuing on to the next key, I'd skip one, assuring myself that I >>>> >>>> >>> Another trick I found: when trying to interpolate keyframe N from >>> keyframe M (M being the last kept keyframe, where M <= N-1) and >>> > keyframe > >>> N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) >>> is counter productive. The reason is quite obvious: we don't know if >>> > the > >>> next keyframe at N+1 will be kept. >>> >>> >> I'm with Richard for this: Doing recursive improvement seems to work >> great for removing all the almost-static keys, and reducing only >> harmless keys in areas of action. >> >> Sincerely, >> >> jw >> >> >> >> > ------------------------------------------------------------------------- > >> 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 >> GDA...@li... >> 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 > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > |
From: David B. <dbe...@na...> - 2008-10-18 22:39:13
|
I'm surprised that no one has brought up what I think of as the main issue for baking out a series of keys instead of using the keyframes directly. Often the keyframes are not the full picture, there are other factors influencing the animation such as expressions or constraints. To use the keyframes directly you must also export and implement those other contributions. If an animator has implemented a rotating platform that always faces a particular cog for example, you may find that this has been done through a "look-at constraint". To include this orientation animation you must make sure you export the look-at constraint and that your run-time implementation of "look-at" matches the animation package's implementation of "look-at". These sorts of issues go away if you just bake out every frame. - David Bennett ________________________________ From: Jason Hughes [mailto:jas...@di...] Sent: Saturday, October 18, 2008 2:43 PM To: Game Development Algorithms Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes Hey Brad, I had one last comment to add, which hadn't really been talked about. My engine uses sampled keys for skinned animations, mainly because baking a bunch of inputs down to curves with any kind of complex rig (think per-animation control skeletons with IK and constraints and SDKs) will not give you a simple curve with just a few knots on your curves. Sampled keyframes are actually smaller and cheaper on the CPU if the keys are too close together on curves. For all non-skinned animations, say for platforms or hierarchies of transforms, etc, I just grab the (non-weighted tangent Hermite) curves and implemented them directly, including all the pre- and post-infinity tangent types. This is super super cheap in terms of memory, and generally have very few keys set on background or level objects. The best thing with these kinds of actors in the scene is a smart animator can give you differently-scaled cycles on the curves, so without putting any programmer time in, you can get very clean and artist-driven animations that are not repetitive, ie. a platform with a rotating cog on it, where the platform carries the cog along with it slowly while the cog rotates quickly. Or ping-ponging animations using post-infinity tangent types. Pretty handy stuff, and really appropriate for level building. I'm not sure there's a reason to use this for characters, since most of the time, you want to kick off an animation that involves the whole body and blending... JH Bra...@pl...<mailto:Bra...@pl...> wrote: Thanks for all the useful replies, everyone! Brad... Jon Watte <jw...@gm...><mailto:jw...@gm...> wrote on 10/15/2008 10:15:38 AM: Sylvain G. Vignaud wrote: From: Richard Fabian <ra...@gm...><mailto:ra...@gm...> frame data. I'd do a pass and cull any key I came across, but rather than continuing on to the next key, I'd skip one, assuring myself that I Another trick I found: when trying to interpolate keyframe N from keyframe M (M being the last kept keyframe, where M <= N-1) and keyframe N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) is counter productive. The reason is quite obvious: we don't know if the next keyframe at N+1 will be kept. I'm with Richard for this: Doing recursive improvement seems to work great for removing all the almost-static keys, and reducing only harmless keys in areas of action. Sincerely, jw ------------------------------------------------------------------------- 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 GDA...@li...<mailto:GDA...@li...> 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 GDA...@li...<mailto:GDA...@li...> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Tom F. <tom...@ee...> - 2008-10-19 01:55:04
|
It's certainly a big problem, but if you try to solve it "correctly" you end up trying to re-implement the constraints EXACTLY as Max/Maya/XSI do them. That way lies madness. The other way to do it is to allow your artists only a very limited set of constraints that they must use in careful ways to match what the runtime is capable of. That way also lies madness :-) On the whole, our experience is that baking to keyframes is the lesser of a multitude of evils. TomF. From: David Bennett [mailto:dbe...@na...] Sent: Saturday, October 18, 2008 3:40 PM To: 'Game Development Algorithms' Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes Im surprised that no one has brought up what I think of as the main issue for baking out a series of keys instead of using the keyframes directly. Often the keyframes are not the full picture, there are other factors influencing the animation such as expressions or constraints. To use the keyframes directly you must also export and implement those other contributions. If an animator has implemented a rotating platform that always faces a particular cog for example, you may find that this has been done through a look-at constraint. To include this orientation animation you must make sure you export the look-at constraint and that your run-time implementation of look-at matches the animation packages implementation of look-at. These sorts of issues go away if you just bake out every frame. - David Bennett ________________________________________ From: Jason Hughes [mailto:jas...@di...] Sent: Saturday, October 18, 2008 2:43 PM To: Game Development Algorithms Subject: Re: [Algorithms] Variable rate cubic keyframes vs. sampled fixed rate linear keyframes Hey Brad, I had one last comment to add, which hadn't really been talked about. My engine uses sampled keys for skinned animations, mainly because baking a bunch of inputs down to curves with any kind of complex rig (think per-animation control skeletons with IK and constraints and SDKs) will not give you a simple curve with just a few knots on your curves. Sampled keyframes are actually smaller and cheaper on the CPU if the keys are too close together on curves. For all non-skinned animations, say for platforms or hierarchies of transforms, etc, I just grab the (non-weighted tangent Hermite) curves and implemented them directly, including all the pre- and post-infinity tangent types. This is super super cheap in terms of memory, and generally have very few keys set on background or level objects. The best thing with these kinds of actors in the scene is a smart animator can give you differently-scaled cycles on the curves, so without putting any programmer time in, you can get very clean and artist-driven animations that are not repetitive, ie. a platform with a rotating cog on it, where the platform carries the cog along with it slowly while the cog rotates quickly. Or ping-ponging animations using post-infinity tangent types. Pretty handy stuff, and really appropriate for level building. I'm not sure there's a reason to use this for characters, since most of the time, you want to kick off an animation that involves the whole body and blending... JH Bra...@pl... wrote: Thanks for all the useful replies, everyone! Brad... Jon Watte <jw...@gm...> wrote on 10/15/2008 10:15:38 AM: Sylvain G. Vignaud wrote: From: Richard Fabian <ra...@gm...> frame data. I'd do a pass and cull any key I came across, but rather than continuing on to the next key, I'd skip one, assuring myself that I Another trick I found: when trying to interpolate keyframe N from keyframe M (M being the last kept keyframe, where M <= N-1) and keyframe N+1, taking into account exactly (time_N - time_M)/(time_N+1 - time_N) is counter productive. The reason is quite obvious: we don't know if the next keyframe at N+1 will be kept. I'm with Richard for this: Doing recursive improvement seems to work great for removing all the almost-static keys, and reducing only harmless keys in areas of action. Sincerely, jw ------------------------------------------------------------------------- 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 GDA...@li... 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 GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jon W. <jw...@gm...> - 2008-10-20 02:37:37
|
David Bennett wrote: > > I’m surprised that no one has brought up what I think of as the main > issue for baking out a series of keys instead of using the keyframes > directly. Often the keyframes are not the full picture, there are > other factors influencing the animation such as expressions or > constraints. To use the keyframes directly you must also export and > implement those other contributions. > I think when people talk about "sampled keyframes," they're talking about sampling the total of all animations acting on a joint at a given point in time. Thus, you're also sampling whatever the IK and other constraints are doing -- you're basically setting the DCC to whatever point in time you're interested in, and reading the resulting joint matrices. Sincerely, jw |