Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1028810 Posts in 41320 Topics- by 32923 Members - Latest Member: DrDiamond

August 01, 2014, 07:55:20 AM
TIGSource ForumsDeveloperTechnical (Moderators: Glaiel-Gamer, ThemsAllTook)"Paper doll" animation systems with bezier surfaces
Pages: 1 [2]
Print
Author Topic: "Paper doll" animation systems with bezier surfaces  (Read 8238 times)
raigan
Level 4
****


View Profile
« Reply #15 on: January 30, 2008, 09:39:37 AM »

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
Logged
Zaphos
Guest
« Reply #16 on: January 31, 2008, 03:20:25 AM »

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 Wink
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.
Logged
raigan
Level 4
****


View Profile
« Reply #17 on: January 31, 2008, 09:20:02 AM »

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.
Logged
Zaphos
Guest
« Reply #18 on: January 31, 2008, 12:51:05 PM »

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.)
« Last Edit: January 31, 2008, 12:57:26 PM by Zaphos » Logged
raigan
Level 4
****


View Profile
« Reply #19 on: January 31, 2008, 10:00:41 PM »

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.
Logged
Zaphos
Guest
« Reply #20 on: January 31, 2008, 11:48:13 PM »

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.
Awesome :D

Here's a graphics gem on fast polygon triangulation, with source code.  They report it's an n*log(n) algorithm that gets close to linear time in practice, and could triangulate 100 vertices in 6.7 ms ... in '94 or '95 on an "HP Series 735" ... so perhaps it will be good enough for your purposes?  It's graphics gem code, so I believe the license is this (from http://tog.acm.org/GraphicsGems/):
"EULA: The Graphics Gems code is copyright-protected. In other words, you cannot claim the text of the code as your own and resell it. Using the code is permitted in any program, product, or library, non-commercial or commercial. Giving credit is not required, though is a nice gesture. The code comes as-is, and if there are any flaws or problems with any Gems code, nobody involved with Gems - authors, editors, publishers, or webmasters - are to be held responsible. Basically, don't be a jerk, and remember that anything free comes with no guarantee."


The "fast" grid-based algorithm I was thinking of (which creates steiner points) is basically to draw the edges as lines on a grid, but instead of drawing pixels, add the lines ID (eg "this is line number 7") to a list at that grid position.  Then run across the grid in scan lines; if you've crossed an odd number of line IDs, you're inside the object and you should make a steiner point.  If you're in the process of crossing over, you should additionally either push the grid vertex to the edge line or connect to an additional vertex created on that line.
... but that's kind of half-formed in my head, and I think the graphics gem code is better if it works.

Anyway, hope that helps!
Logged
raigan
Level 4
****


View Profile
« Reply #21 on: February 01, 2008, 08:43:12 AM »

thanks!

the triangulation code in gameswf has a really good section of comments explaining the various pros/cons of different open-source implementations (and an implementation itself), if anyone else is looking at this stuff it's something to check out.
Logged
Pages: 1 [2]
Print
Jump to:  

Theme orange-lt created by panic