next »

[Zaphos]

It seems like a fair amount of people have made custom paper-doll type animation systems for their games.  I was thinking about making one that supports deformation of individual parts with bezier surfaces (+ some interpolation between surfaces), to give intuitive support for non-rigid transformations.

So, I was hoping to find out:

 1. Has anyone done this?

 2. Have any of the paper-doll systems made their code available & clean enough to be a good starting point?

 3. Is anyone interested in something like this?  If you're interested in using something like this, do you have any suggestions on how I can make a tool that's usable for you?  (e.g. should I write loading / animation support for some languages, and which ones, etc?)

Thanks for any input!

[Alex May]

I'm interested - I think the dannobot had something like this in super pillow fighter. I think I recall a thread.

Also check out that HL2 mod Flipside!

The main thing I would be after is IK animation. I don't think I would use it in a game, as I've too much on and no compatible game designs, but I think it would be a great stylistic choice, and have done so for some time. Flipside is proof! Proof that I was right all along!

[Ryan]

After I finish the basics (finally, almost done!) I'm going to start on simple skeletal animation stuff for 2d ragdolls. The only thing I've ever really found was this article:

http://gpwiki.org/index.php/OpenGL:Tutorials:Basic_Bones_System

That may help get you started, though there isn't any information there about bezier surfaces.

[raigan]

About the ugly "collapsing" that can happen around joints, a pretty good solution is presented in the "hardware skinning with quaternions" article in GPG4, they call it "spherical joint blending" or something -- the idea is you bind the elbow verts to a "virtual" bone whose position is the same as the lower arm, but whose orientation is halfway between the lower and upper arm. This explanation sounds more complicated than it really is!

This is similar to some other solutions that involve generating multiple bones around the elbow, but it's much simpler and looks better.

One huge problem we've just come across (haven't started yet on animation, just reading up still) is that if you want to support arbitrary deformation of a 2D shape, you need to re-triangulate every frame (which can be slow). It's amazing how complicated 2D can be.... ARGH!

[the_dannobot]

Yeah, I've done some paper-doll animation, but nothing as complicated as using bezier curves to deform the model.  I've just done simple "2d quad displayed over a bone". 

To do deformation like what you're talking, I guess you'd have to do a mesh attached to the bone and use some spring-based physics for the deformation?  I had a hard enough time getting ragdoll physics to work, but that would probably be really cool if you could do it.  You could do some pretty sweet cloth simulation if nothing else

[Chris Whitman]

There are area-preserving deformation methods I've read about for 2D objects. I seem to recall spotting a paper on a non-linear least squares method for object deformation that produces excellent results and converged very quickly. It was a SIGGRAPH thing.

I'll see if I can dig up a link to the paper sometime when it isn't so late.

[Zaphos]

The main thing I would be after is IK animation. I don't think I would use it in a game, as I've too much on and no compatible game designs, but I think it would be a great stylistic choice, and have done so for some time. Flipside is proof! Proof that I was right all along!

Do you mean IK animation as in using IK to dynamically create animations of (for example) a character picking up an object?  Or using IK on the tool side of things to make animating easier?
I'm not really seeing where flipside uses IK, at least just from watching a video of the game.

That may help get you started, though there isn't any information there about bezier surfaces.

Thanks for the link! 

About the ugly "collapsing" that can happen around joints, a pretty good solution is presented in the "hardware skinning with quaternions" article in GPG4, they call it "spherical joint blending" or something -- the idea is you bind the elbow verts to a "virtual" bone whose position is the same as the lower arm, but whose orientation is halfway between the lower and upper arm. This explanation sounds more complicated than it really is!

Spherical blend skinning seems nice, but isn't that overkill for 2D?  It seems like most 2D systems just have the parts z-sorted and rigidly aligned to a bone.

One huge problem we've just come across (haven't started yet on animation, just reading up still) is that if you want to support arbitrary deformation of a 2D shape, you need to re-triangulate every frame (which can be slow). It's amazing how complicated 2D can be.... ARGH!

Well, that's really only if you want the character to be able to stretch infinitely; you should be able to get quite a reasonable range of deformation from a static triangulation.  And if you really did want that much deformation, you could automatically detect when a retriangulation is needed and only do it at that time.  And you can potentially spread that cost over multiple frames, since it should happen relatively infrequently I think.

Yeah, I've done some paper-doll animation, but nothing as complicated as using bezier curves to deform the model.  I've just done simple "2d quad displayed over a bone". 

To do deformation like what you're talking, I guess you'd have to do a mesh attached to the bone and use some spring-based physics for the deformation?  I had a hard enough time getting ragdoll physics to work, but that would probably be really cool if you could do it.  You could do some pretty sweet cloth simulation if nothing else

Bezier surfaces don't require spring-based physics.  The deformation would be animator controlled; it would just allow people to bend quads and interpolate between those bends, since I think if you have purely rigid transformations things won't look as nice.  Some neat procedural animation would also be possible with the system -- for example a fat character whose belly jiggles -- but it wouldn't need to be physically driven.  (In fact, if it were physically driven I probably wouldn't use bezier surfaces?)

There are area-preserving deformation methods I've read about for 2D objects. I seem to recall spotting a paper on a non-linear least squares method for object deformation that produces excellent results and converged very quickly. It was a SIGGRAPH thing.

I'll see if I can dig up a link to the paper sometime when it isn't so late.

Perhaps As-Rigid-As-Possible Shape Manipulation?

[Alex May]

The main thing I would be after is IK animation. I don't think I would use it in a game, as I've too much on and no compatible game designs, but I think it would be a great stylistic choice, and have done so for some time. Flipside is proof! Proof that I was right all along!

Do you mean IK animation as in using IK to dynamically create animations of (for example) a character picking up an object?  Or using IK on the tool side of things to make animating easier?
I'm not really seeing where flipside uses IK, at least just from watching a video of the game.

I meant tool-side. The Flipside comment relates to the stylistic comment rather than the IK comment.

[Zaphos]

I meant tool-side. The Flipside comment relates to the stylistic comment rather than the IK comment.

Ah ... then I agree!

[raigan]

Spherical blend skinning seems nice, but isn't that overkill for 2D?  It seems like most 2D systems just have the parts z-sorted and rigidly aligned to a bone.

If you only support rigid alignment, you end up having to give everyone "elbow and knee pads" (Oni did this). I guess my opinion is: it's not actually any more work at runtime to have different verts from the same polygon bound to different bones (it just requires a bit more development time), and it lets you do all sorts of loco-roco type stuff, so why not?

If you do support some sort of skinning/per-vertex binding to bones (rather than per-shape/rigid), the "spherical" method is totally worth trying since it's only a few lines and is a huge improvement in some cases.

Well, that's really only if you want the character to be able to stretch infinitely; you should be able to get quite a reasonable range of deformation from a static triangulation.  And if you really did want that much deformation, you could automatically detect when a retriangulation is needed and only do it at that time.  And you can potentially spread that cost over multiple frames, since it should happen relatively infrequently I think.

Invalidating a pre-calculated triangulation actually happens wayyyy more than you'd think -- it seems to happen all the damn time. Whenever a vertex changes from convex to concave it can happen, and there are all sorts of other more subtle cases which happen too. For instance, a concave vertex moving "inward" just a bit can cross an internal triangle edge, flipping the clockness of the triangle and screwing everything up.

If anyone knows of a good solution for this, please tell me! It seems like there could be some rules that might result in a less-prone-to-invalidation triangulation, but I haven't found any. In loco-roco they must have either had the artists specify the triangulations by hand, or else they only supported cases where an existing stable triangulation was known (rippling waves specifically can either be fine or terrible depending on the triangulation).

[Chris Whitman]

If anyone knows of a good solution for this, please tell me! It seems like there could be some rules that might result in a less-prone-to-invalidation triangulation, but I haven't found any. In loco-roco they must have either had the artists specify the triangulations by hand, or else they only supported cases where an existing stable triangulation was known (rippling waves specifically can either be fine or terrible depending on the triangulation).

The paper I was thinking of was this one research.microsoft.com/users/kunzhou/publications/2DShape.pdf.

It preserves global area as well as local coordinates for each vertex. It also saves you the pain of setting blend-weights on vertices and allows for a free deformation of points. The downside is that it requires an iterative solver, but they claim the process converges within acceptable limits in about ten iterations, which is comparable to other, linear methods.

[Zaphos]

If you only support rigid alignment, you end up having to give everyone "elbow and knee pads" (Oni did this). I guess my opinion is: it's not actually any more work at runtime to have different verts from the same polygon bound to different bones (it just requires a bit more development time), and it lets you do all sorts of loco-roco type stuff, so why not?

If you do support some sort of skinning/per-vertex binding to bones (rather than per-shape/rigid), the "spherical" method is totally worth trying since it's only a few lines and is a huge improvement in some cases.

Good points; I'll definitely play with nicer skinning methods.  Or, actually, if I can implement what Mr. Cake pointed to, that should be the nicest of them all
(and then I can add explicit layering and stick bezier surfaces [for non-volume-preserving deformations] on top of it, I suppose)

Invalidating a pre-calculated triangulation actually happens wayyyy more than you'd think -- it seems to happen all the damn time. Whenever a vertex changes from convex to concave it can happen, and there are all sorts of other more subtle cases which happen too. For instance, a concave vertex moving "inward" just a bit can cross an internal triangle edge, flipping the clockness of the triangle and screwing everything up.

"Concave vertex" is a strange term to use.
I assume you're doing a finite element simulation on a 2D mesh?  It seems people can get finite element simulations of elastically deforming objects to do fine without remeshing at all.  Instead, when invalid things happen (such as self intersection / element inversion) they fix the problems in the current mesh.  Have you seen Invertible Finite Elements For Robust Simulation of Large Deformation?  That's a whole paper on how to handle this kind of problem without remeshing ...

For simulating things in the borderline between water and solid, Adam Bargteil had a siggraph paper recently that does do remeshing ("A Finite Element Method for Animating Large Viscoplastic Flow") ... which could probably be made fast for 2D.  It doesn't do remeshing very frequently, either, so spreading the cost across frames also seems possible.

If anyone knows of a good solution for this, please tell me! It seems like there could be some rules that might result in a less-prone-to-invalidation triangulation, but I haven't found any. In loco-roco they must have either had the artists specify the triangulations by hand, or else they only supported cases where an existing stable triangulation was known (rippling waves specifically can either be fine or terrible depending on the triangulation).

Jonathan Shewchuck has discussed at great length what properties define a good finite element (and hence: a good triangulation).  See his webpage ...
I'm curious to see what papers / sources you've seen so far?

The paper I was thinking of was this one research.microsoft.com/users/kunzhou/publications/2DShape.pdf.

It preserves global area as well as local coordinates for each vertex. It also saves you the pain of setting blend-weights on vertices and allows for a free deformation of points. The downside is that it requires an iterative solver, but they claim the process converges within acceptable limits in about ten iterations, which is comparable to other, linear methods.

Thanks!  I'm not sure how helpful that is for physical simulation (ie raigan's problem?) but it's good for me!    I had only seen the earlier As-Rigid-As-Possible Shape Manipulation, but this looks like they took that paper and improved it.

[raigan]

I'm not doing FEM or anything, the mesh is purely for sending to OpenGL. It could be animated using regular "kinematics" or whatever -- once you allow non-rigid transformation you open a huge can of worms in terms of keeping the mesh valid.

By concave I just meant the external angle of the vertex is <180deg.

[Zaphos]

I'm not doing FEM or anything, the mesh is purely for sending to OpenGL. It could be animated using regular "kinematics" or whatever -- once you allow non-rigid transformation you open a huge can of worms in terms of keeping the mesh valid.

By concave I just meant the external angle of the vertex is <180deg.

I'm not sure what you mean by "regular" kinematics, but I think the model you're using to create your animation does matter a lot for determining what the right way to handle this is.  If you're doing physical simulations, with finite elements + static mesh you do need to handle inverted elements but it can do it robustly with good results.  If you're doing artist-controlled bezier surfaces, you basically just don't have the problem at all.  As-rigid-as-possible shape manipulation I'm pretty sure didn't need to re-triangulate at all.

I don't think I've seen a method that needs to worry explicitly about changing from convex to concave on the surface, but I'm sure I haven't seen a lot of things, so I'm curious what method has been giving you this kind of trouble?

[raigan]

It can be animated in any way -- for instance plain "morph target" animation as in Quake, where each frame of the animation specifies a position for the vertices, or any sort of procedural animation (via sin waves or whatever), pretty much anything non-rigid can invalidate the triangulation.

I'll attach an example picture -- obviously this is a bit contrived, but it illustrates the problem. In this case there is actually no static triangulation that works. Storing a triangulation with each keyframe also doesn't work, because the problems occur in-between the two keyframes rather than on keyframe boundaries. One solution would be to (in a preprocess) determine when the triangulation breaks and automatically insert a new keyframe at that point which copied the current shape but used a different triangulation. Sadly this solution can't be applied to anything reactive/physics-based though, because there's no easy way to tell "which keyframe you're on".

Another solution for this specific case is to add "steiner verts" along the bottom edge of the shape in order to allow a static triangulation that's always valid;  as far as I can tell there's no way to automate this sort of "solution" -- it requires a person to figure out the solution via intuition, and it's not always this obvious. If you're planning on releasing tools to the public, it's the sort of thing you don't want them to have to screw around with for every shape they create!!

This is also something that i'm sure needed to be dealt with in loco-roco.

BUT: there's of course the possibility that i'm totally confused about this and overlooking something very simple and obvious.. please let me know

[raigan]

whoops, apparently the correct term is "steiner points" (basically extra verts); for some reason i'm getting this error when trying to edit the post:

Database Error: Lost connection to MySQL server during query
File: /usr/home/tigsource/forums/Sources/Post.php
Line: 1423

[Zaphos]

It can be animated in any way -- for instance plain "morph target" animation as in Quake, where each frame of the animation specifies a position for the vertices, or any sort of procedural animation (via sin waves or whatever), pretty much anything non-rigid can invalidate the triangulation.

I'll attach an example picture -- obviously this is a bit contrived, but it illustrates the problem. In this case there is actually no static triangulation that works. Storing a triangulation with each keyframe also doesn't work, because the problems occur in-between the two keyframes rather than on keyframe boundaries. One solution would be to (in a preprocess) determine when the triangulation breaks and automatically insert a new keyframe at that point which copied the current shape but used a different triangulation. Sadly this solution can't be applied to anything reactive/physics-based though, because there's no easy way to tell "which keyframe you're on".

Another solution for this specific case is to add "steiner verts" along the bottom edge of the shape in order to allow a static triangulation that's always valid;  as far as I can tell there's no way to automate this sort of "solution" -- it requires a person to figure out the solution via intuition, and it's not always this obvious. If you're planning on releasing tools to the public, it's the sort of thing you don't want them to have to screw around with for every shape they create!!

This is also something that i'm sure needed to be dealt with in loco-roco.

BUT: there's of course the possibility that i'm totally confused about this and overlooking something very simple and obvious.. please let me know

OH, it all makes sense now.  Yes, every system I was discussing would be using steiner points, and I had been assuming that whatever you were thinking about would have them too ...

But yes, if you don't want steiner points, I guess you basically do have to re-triangulate every frame.
If you do have steiner points, you additionally probably want some algorithm that uses those points (or the triangles they form) as part of your calculation, so they also move in a plausible way determined by the system, since that will help keep them inside the shape and can also improve the accuracy of a simulation.

There are lots of good algorithms to automate placement of Steiner points.  The basic idea of it is typically that you want a density of points such that the triangles are smaller than the surface features you'll need.  As long as you have 'nice enough' triangles (often niceness is defined by how close they are to equilateral) which are packed densely enough, you should be able to handle a good range of deformations.

One such algorithm is to do a constrained Delaunay triangulation, and for each triangle with a circumcircle of radius greater than some size FeatureSize you specify, add a Steiner point at the center of that circle then recompute the constrained Delaunay triangulation.
A simpler way is to just throw down a regular grid, with edge length < FeatureSize, then cut away the bits that aren't inside the mesh, and connect the edge verts of your surface to the closest edge verts of grid.

An alternative approach I was thinking I'd apply for Bezier surfaces is to skip any proper triangulation at all, and instead just put down a relatively dense textured grid, with transparency (instead of polygon edges) defining the object border, and let movement of the much sparser Bezier control vertices dictate how the grid is squashed and stretched.

[raigan]

Adding points internal to the shape is going to cause huge complexity problems in terms of figuring out how to animate them -- for instance, in the example I want the tagged verts to move up and down.. any steiner point placed inside the shape may end up outside the shape as the animated verts move.

It seems like meshes for simulation are a fairly different thing that meshes for rendering.

[Zaphos]

Adding points internal to the shape is going to cause huge complexity problems in terms of figuring out how to animate them -- for instance, in the example I want the tagged verts to move up and down.. any steiner point placed inside the shape may end up outside the shape as the animated verts move.

It seems like meshes for simulation are a fairly different thing that meshes for rendering.

Yes ... this is why I mentioned you'd want a system that knows how to move the internal points as well.  Fortunately many systems provide reasonable ways to do that (bezier surfaces, physical simulation, as-rigid-as-possible or volume-preserving manipulation, and skeletal animation can all handle this).

However if you're just animating the outside points without a model that can generalize to the internal, you're right.  It's possible you could do some sort of damped springs-type simulation where internal edges act to keep vertices separate, but that might be more pain than it's worth.
If you do need to remesh every frame, that also might not be too bad since you don't have to worry about 'mesh quality' factors (like avoiding long skinny triangles).  I think the algorithm where you lay down a grid of steiner points, clipped to fit inside the shape, and then just connect the outside verts to the edges of the grid, could be quite fast in practice, especially if you can take some advantage of temporal coherency and only update the grid where it has changed.

And actually with things like Triangle, people seem to have gotten constrained Delaunay to run quite quickly as well.
It depends on what properties you want for your output and how many points you've got moving around, but I wouldn't discount per-frame retriangulation as being impossible.

(Actually I think the fastest triangulation algorithm should involve just walking around the boundary vertices making triangle fans where possible, but I haven't thought through how to [or if it's possible to] turn that in to a divide-and-conquer type algorithm that doesn't potentially have to do line intersection on O(e^2) edges.  But it seems like it should be possible to do.)

[raigan]

i've looked into this, it's pretty hilarious -- the best triangulation algorithm is O(n), but in _every_ citing is described as "unimplementable" or "too complex to realistically implement".. reading this in a research paper is pretty hilarious/depressing.

ear-clipping is O(n^2) and is what is most often used (with various added rules for choosing the "best" ear), with two or three open source implementations floating around. this is what's used in glut i thinnk.

there are also a couple better O(n*logn) or O(n*m) algos, a sweep-line one and a randomized one by chazel, but this is now in the sphere of "am i really competent enough to implement this efficiently?".. 

it amazes me that simple 2D graphics still has so many unsolved problems. wtf computational geometers?!

i'd really like to look inside the flashplayer.