I've seen a few things about delauney triangulations or voronoi regions but they are pretty thick to read through. I also don't need anything exact by any means. I just need to divide a mesh into regions where I know every vert on the region border can be seen from some point in the mesh. Anyone have any pointers for this? My first instinct is to add to areas by shooting rays to an approximate spot and ending the region once there's a failure. Aside from speed (which is not a huge factor anyway), I don't have the mesh set up in a manner that makes collisions readily available, and I don't really want to go to the effort of making a BSP just for this seemingly easy problem. Anyone got a simpler way?

Quote:Original post by thatguyfromthething
I've seen a few things about delauney triangulations or voronoi regions but they are pretty thick to read through. I also don't need anything exact by any means.

Probably you do.

Quote:
I just need to divide a mesh into regions where I know every vert on the region border can be seen from some point in the mesh.

If you really mean some point, rather than all points, you need star polygons, a weaker restriction than convex polygons. Neither has any significant relation with Delaunay triangulations.
Can you explain what do you need these polygons for?

Quote:Original post by LorenzoGatti

If you really mean some point, rather than all points, you need star polygons, a weaker restriction than convex polygons. Neither has any significant relation with Delaunay triangulations.
Can you explain what do you need these polygons for?

I guess I should say tetrahedron, not polygon.

I am making a skinning plugin for maya at the moment. I thought I had a good algorithm and it works better than the default but still isn't really ideal. It does ok on the arms but the shoulders, not so much unless the joints work just right.

If you have a mesh broken into regions you can judge how much sense a weight assignment makes by how many regions it has to cross.

A good initial weight assignment is my goal, but trying to cut a mesh into regions like that is something I'd hoped to avoid and can't seem to figure out a great means of doing. I also have a couple other ideas, but if it's easy to break it into decent regions then I may as well go for the ideal solution. However, I don't want to waste a ton of time on it, either. Just getting the basic thing to work has taken over a week just because it's hard to figure out sometimes what maya API wants because all the API functions are along the line of doSomething(void *, void *) and what it expects isn't always obvious.

Quote:Original post by Emergent
Lorenzo has a really good point.

But if what you really want is to divide the volume inside your mesh into convex regions (rather than star regions), then...

Yes, constrained Delaunay tetrahedralizations can do this (by subdividing the volume into tetrahedra), though the "Delaunay"-ness is really not key to the problem; it just tends to give you "nice" tetrahedra.

The other thing I'm just starting to wonder is whether you can do the 3d analogue to ear clipping (source: Dave Eberly's site) in 2d... [EDIT: No; there are polyhedra which cannot be tetrahedralized in this way. See p.12 of this]

Can you use existing code; e.g. TetGen? (Caveat: I've never used TetGen, so I don't know if it's really appropriate for your problem, but perhaps it is.)

Thanks for the link. It's for a potentially commercial tool so I can't just copy someone's open source code probably, but it is good to at least look at it and get some idea of if it's a day or two of work, weeks of work, or one of those things that is never quite 100% right and you always go back fixing it and wishing you'd never started in the first place.

But when I think of it, ultimately the regions are just lists of verts. I just need to make some sort of check as to whether each addition vertex (or maybe polygon) is allowed to be added to the regions and then do a greedy algorithm. If I can figure that out it should not be too hard. But I don't really want to make a bsp for collision checks.

The voronoi regionalization uses something like a 'ball check', but I am not too sure of exactly what that is. I think the idea is like you tetrahydralize the whole mesh (something I am not sure how to do/is probably a bit of a pain but not insurmountable), then you add smaller regions by seeing if the center of their combined regions can contain them all without intersecting anything else.

But it would be easier if I could do it without having to store the whole tetrahydralization. Like if I could just have a list of polygons and do a check on it. But I am not sure that's possible or not without making more data structures.

Quote:Original post by Emergent
Now I am thoroughly confused.

For one thing, I don't get what this "weight" stuff you're talking about is. Maybe it's because I've never used Maya. Could you explain your problem in very simple terms? "My input is a triangular mesh. I want to get _________ as output."

(At first, I thought you wanted to learn something about the volume contained inside a mesh. But now it seems that volume is just incidental, and that what you really want is... to automatically subdivide your mesh into regions? In that case, perhaps it would be better to just think of your mesh as a graph (nodes and edges... forget about geometry, except perhaps edge lengths) and use some graph clustering algorithm (e.g., graph-Laplacian-based clustering).)

Well, I was simplifying the problem because it is a little complicated. Also, I am often loose with/don't know the right terminology for things.

The full problem is to take a set of bones and a mesh, and to assign a weight or weights to each vertex which causes the vertex to deform as the bone moves. Then when you animate the skeleton, the mesh moves around properly.

When making characters this skinning process is a huge pain. Partly because the initial weights are always all wrong, often badly. That's true of every program I know of. There are some tools/plugins that work much better but take some user input, and probably at places like indutrial lights and magic they have some killer plugins that make it a breeze. There's also some tricks to make the skinning easier but if you make lots of totally dissimilar meshes then it gets to be a pain to go through copying skin weights around between objects all the time.

So I figured for the time it saves me it's worth making this plugin, and maybe some day I will make a modeling and animation app or (much more likely) a commercial plugin that is more geared to just making game assets because I have a lot of tools for that already and the big apps are all heavily geared to making movies and don't seem to care at all about the things that are necessary for making quality game assets in a reasonable timeframe.

What typically happens is you bind the default skin, then you get this huge mess. The sides are partially attached to the arm bones, the area below the belt is usually a big mess too, sort of like everything is assigned to random crap. Sometimes the fingers are all stuck together, etc.

So obviously you don't want to have the verts on the waist attached to the arm. If you can find an automatic way to just separate the mesh into basic regions like arms, legs, and head, then you can avoid having these silly weights assigned to the wrong area.

Now, as it turns out, you don't need to have a lot of fancy tricks to make things work out good in most cases. It was not too hard to get a default bind that works better than the basic one in maya but if I could divide the mesh into regions, even just arms legs head and trunk, it should elimate all the remaining issues.

So Ideally I'd want to be able to know what region(s) that a bone is in, what region a vert is in, and the distance between bone and vert in terms of regions. With that info, weighting the skeleton is a snap (aside from the maya API part, which thankfully already works).

Now, more regions is a good thing, but like I said it doesn't need to be exact. Or I should say, it doesn't need to crack it down into a thousand pieces. The voronoi regionalization and delauney triangulation I know some people have used is really a bit overkill in that sense (and might possibly be patented for this use). The better the regions fit the actual bones, the better the results, but at the same time even 5 pieces is really enough because it's not something that can ever be exact and the basic means I use of choosing verts usually shakes out pretty well already.

But I will look at the thing you suggested - my hope is to find real simple/easy way to make this into regions and not waste any more time on this than I have to. I did think of using a cover tree, but it seemed if anything a lot harder to understand/implement than the other methods.

Have you considered a volumetric diffusion approach, such as this?

Thank you very much, swiftcoder (and good name btw).

Voxelization is an absolutely brilliant and simple way to do divvy up the mesh and it's exactly the kind of easy to use but powerful solution I was looking for.