next »

[Zaphos]

With their method, you just need to compute G, the pseudoinverse of the matrix A, which is easy enough, and then b(V) is a non-linear function of V they describe in detail. Fortunately you can precompute G, so you don't need to do a linear solve each iteration or anything. I think I'll stick with the method they've got, unless I find I have convergence problems or something, in which case I might use Levenberg-Marquardt or see what else I can do. I don't know, we'll cross that bridge when we come to it.

Ah, cool ... I admit I had just skimmed through "gauss-newton" and assumed you'd need a new solve each step, oops!  Kind of surprised they precompute G and not the cholesky factorization of A^T A though.

But again, I don't know how well motions out of the plane can be captured. Weng et al. doesn't mention a system for depth sorting individual control points. Igarashi et al. does, but they don't specify how it works. The issue would be if you, say, had an arm bending all the way around the body. It should be manageable.

There's a paper related to this problem called "Local Layering" that you might want to look at -- http://graphics.cs.cmu.edu/projects/local-layering/

[Chris Whitman]

There's a paper related to this problem called "Local Layering" that you might want to look at -- http://graphics.cs.cmu.edu/projects/local-layering/

Whoa! Rad, thanks. That looks like exactly the kind of thing I was looking for.

[tsameti]

Laplacian coordinates... Levenberg-Marquardt...

Man, I miss the taste of Math.

Chris, is this project meant to produce animation cycles similar to what Atlus does in 'Odin Sphere'? They used sprite deformations to do breathing (especially for huge characters or objects) and a few other things.

[Chromanoid]

how about using 3d software like blender (with orthographic projection)?

[Chris Whitman]

Chris, is this project meant to produce animation cycles similar to what Atlus does in 'Odin Sphere'? They used sprite deformations to do breathing (especially for huge characters or objects) and a few other things.

It should be able to do this, yes, and hopefully more. The point is a general purpose high-quality sprite animation utility, so I hope to add lots of fun features eventually, but the base feature set is going to allow you to quickly rig one or more images, create keyframes by deforming these images in a "reasonable" way (with some user control over parameters) and output a sprite sheet of animations. I'd like to at least be able to produce convincing basic animations like idling or walk/run cycles.

Obviously this is more tailored to sideview perspectives, since there isn't necessarily enough information in a still image to do top down or 3/4 animations.

I mean, we'll have to see what kinds of geometries and animations it can handle. This is an experiment, so I'm not making any guarantees at this point.

how about using 3d software like blender (with orthographic projection)?

There's no functionality in Blender to do anything much like this, as far as I'm aware.

[Chromanoid]

how about using 3d software like blender (with orthographic projection)?

There's no functionality in Blender to do anything much like this, as far as I'm aware.

it is not very comfortable, but i think one could setup some planar meshes and rig them in a way that you will get similar results.
anyway i would love to have such an animator you are planning.

[Jetrel]

If you made this and open-sourced it, you, sir, would be a god.

I know a lot of people who'd love to have something like this, but can't justify the expense in time.  I think it's especially these "awesome but not critical to have" features that get badly neglected in development; since most development, even amateur, is just desperate to make a finished game at all, and cuts "mad plans" like this left and right.

[Chris Whitman]

Phew, day two of work and I am SICK OF GRAPHS.

But I have contour tracing and extraction working, which gives the first half of the image triangulation algorithm. This is illustrated by this quick sketch of Silhouette-Pompadour-Man.



Regions with high curvature exhibit some artifacts, which are fixable by choosing a higher sampling resolution:



Whether that kind of resolution will be appropriate on your average computer to work with the model at interactive rates is a good question. I'm thinking it might be possible to run marching squares at a very high sampling rate, then smooth the graph with a bias towards convex areas. That might produce better results, but I'm not going to worry about it right now.

Next up is filling the interior, then the smoothing and simplifying.

[Chris Whitman]

Progress on the algorithm implementation!

The interior graph with connecting edges in its initial shape (lower resolution):



The final interior graph, after simplification and smoothing, ready for triangulation (slightly higher res -- I keep moving the sampling resolution higher and lower to see if it will break):



Next up is triangulation of the internal graph (not difficult), building the operators and performing the optimization (theoretically not hard, but the paper is vague in parts and may contain errors, so who knows).

[Zaphos]

Looks decent!  I guess it has problems with sharp concave features though?  The mesh seems to leak out of the boundaries, and you webbed up his fingers.

I always just use Shewchuk's Triangle library to get an initial mesh, so if this approach proves finicky you might try that out -- the license is a bit vague but I think he'd be fine with you using it in free software.  The main drawback is that I don't think it compiles correctly in 64-bit mode.

[Chris Whitman]

Yeah, that's just an artifact of marching squares, and it's easily solvable by increasing the level of detail of the mesh. If I wanted to make the algorithm smarter, I could increase the sampling in areas of high curvature. I'll probably consider doing that once things are actually working.

I looked at just using Delaunay triangulation of the boundary polygon, but the worry there is not winding up with enough geometry in narrow areas. With this algorithm, you're guaranteed to have at least two triangles width no matter how narrow the area is, which should lead to better performance in the deformation solver. Same deal with having a mostly regular rectangular grid on the interior of large areas.

Edit: also, if the mesh leaks out a little, it isn't a huge deal, since those areas will still be rendered as transparent, the only worry would be a lot of mesh leaking accompanied with extreme deformations, which might then result in blurring. I joined the fingers in my test thing so I could see what the hell was going on with the hands.

Edit edit: But yeah, I sat around for a while debating using Triangle, but eventually I decided to stick with the method recommended by the paper I'm working from, even if it meant digging out the paper it originally came from and sorting through its inevitable ambiguities and errors.

Sometimes I wished academics actually bothered to write out algorithms in such a way that anyone reading could actually implement them without having to make stuff up or spend hours figuring out what the hell the original author was thinking.

[Chris Whitman]

All right, uh... this method appears to have been patented by Microsoft (not that they're using it), so I guess it's back to the drawing board!

Edit: on the other hand, I guess it explains why no one has done anything like this before. Go go gadget patent trolling.

[Inane]

All right, uh... this method appears to have been patented by Microsoft (not that they're using it), so I guess it's back to the drawing board!

That sucks, man.

[Zaphos]

All right, uh... this method appears to have been patented by Microsoft (not that they're using it), so I guess it's back to the drawing board!

Edit: on the other hand, I guess it explains why no one has done anything like this before. Go go gadget patent trolling.

(Though ... actually something like this is in after effects -- the puppet tool.  It follows the other paper I mentioned though.  Using the same tech there's also Takeo's research prototype movingsketch, and picmo ...)

(Also I probably wouldn't have even checked if it was patented, you're better off not even knowing, since knowing infringement triples your liability in court and IANAL but I don't think microsoft actually cares ...)

Anyway, hopefully you can re-use a lot of the same work in implementing a different method?

[Xion]

just keep making it in secret, and give it only to trusted people in back-alley deals next to a shady looking hole-in-the-wall eatery that is obviously a front for something far more ominous, and when the Microsoft agents come for you (for they will inevitably come for you), round up all the connections you've made over the years to use all of their individual areas of expertise to help you out of the Tight Jam (but not before you almost get got and are in need of rescuing). We will then, collectively and with a united "fuck yeah!" Stick It To The Man.

The government will then thank you and award you with some kind of fancy distinguishment, even though you broke the law (but they won't notice that, they never do.)



but please keep working on this, or something like it.

[Chris Whitman]

Yeah, I found out accidentally while looking to see if anyone else had successfully implemented this.

I've pretty much got to finish work on this because I need to hand it in in two days.

After that, I'll probably implement the method from the Takeo paper for use in the actual application. The worst part is that this technique depends on the Takeo paper, and numerous other research efforts which were publicly funded and not patentable, but because they put the last brick on, as it were, now they can just sit on it for 20 years with no intent to turn it into a real product. The patent system blows.

[Chris Whitman]

So this is due today, and last night was in a catastrophic state. Like, it was running, but shit was just crinkling up and shooting off into random places.

BUT GUESS WHAT!?



I worked from 8:00 a.m. to 2:00 a.m. on this yesterday and was back at it at 8:00 this morning again. I have been working on this for an entire week now, minimum twelve hours a day. I am so relieved I could die. There are still some issues with the triangulation algorithm when triangulating outlines with high curvature using a low resolution, but that's relatively minor.

I haven't implemented global area preservation, and probably won't have time, but the deformation totally works and it's awesome.

I also found two notational errors in the paper.

It's really unfortunate that I can't include this in the thing due to patents, but man. It's good to be done. I like how this is, like, my homework dev log now.

Edit: since I'm open-sourcing the thing, I wonder if I could include the algorithm in there, enabled by a define or something and just let people recompile the application at their own risk.

#ifdef I_AM_A_CRIMINAL

[JMickle]

I really doubt microsoft are going to sue you for using it in any way, and everyone using your program will appreciate it hugely if included. Why not just go for it? I personally think you're worrying way too much.

Program sounds fantastic so far btw.

[FatHat]

All right, uh... this method appears to have been patented by Microsoft (not that they're using it), so I guess it's back to the drawing board!

Edit: on the other hand, I guess it explains why no one has done anything like this before. Go go gadget patent trolling.

Just curious which patent it is? If you're talking about marching cubes/squares (I noticed you mentioned that earlier) I'm pretty sure that patent expired a few years ago.

[Chris Whitman]

Yeah, the marching squares patent expired a few years ago. It's the actual deformation algorithm here that is patented.

I don't know, they shouldn't even have software patents, in my opinion. Or, at the very least, you should need to demonstrate an actively developed implementation which will someday be available to the general public within some time frame in order to sue for patent violation.

Anyway, now that this actually works, I'll give it some thought. I mean, I'm not planning to profit off this, but I'd rather not sit around waiting to be sued either.


I finally fixed at least the bulk of the triangulation and smoothing edge cases: