very nice script. But is it possible to redefine which bone belongs to which region? I have successfully initiated the mesh points and the bones plus regions have been found automatically, which is super cool. But two of the bones affect the wrong region. Bone2 should affect region1 and bone1 region2.
I tried to move the regions and/or bones in the lists to properly match my scene, but it obviously isn’t possible. Is there a different approach that I should take? If not, maybe you could add the feature?
Ooops and hei,
at first let me say that I’m sorry cause I haven’t replied to lots of questions about the script cause I had absolutely no idea how to go on with it.
Dunno why but I took some old ideas and did a little bit of research on the net to develop new ones.
But one step after another:
@doCHtor: I know it’s a big weakness that it doesn’t work with CAT right now. I know about this problem but with the actual script “architecture” it will be horrible to include CAT-Bones.
@Wheiraucher: Yep I know this problem that’s why I scripted kind of a XChange-function (that is not very user-friendly but it it’s there. Just go to my page and download the actual version. There should be PDF in ZIP-file explaining how to do that.
But what’s new, now?
I came to the point where I ran into problems with approaches that just take care of the mesh and read about a volume approach. Unfortunately it’s necessary to voxelize the mesh which is not possible in 3DS Max (if you imagine something like in 3D Coat). But it’s possible to create a rough volume approximation in finite time.
So what you can see in the image is that approximation. I’ve created a 70 x 70 x 70 “Voxel-Grid” for the mesh which I named Igor. (First image, left) In the second image you can see the “voxel-areas” which I visualized just for that picture by creating cubes together with Igors geometry. The last image shows the “voxel-areas” without Igors geometry.
The whole creation took… 3 minutes which is quite long cause the runtime is O(n³), since I have a triple loop. I guess I’ll run into problems when I want to create a denser voxel-grid. Does anybody have an idea how to optimize the runtime?
I’m eager on working on that script-approach.
I see, and hope that one day you will include CAT (seems like it will be with us for some time). To be honest though, right now it’s not a problem for me because I started to use 2 rig systems for my characters – CAT is for animation and max-bone based copy of the rig that’s constraint to CAT bones is used for skinning.
Reading through the tech talk you and TzMtN are having (which is beyond my knowledge ), I would like to say that if the skinning would work great, then some long but sane times it would took to autoskin the mesh would be ok – still would save lot of boring work.
Hi kogen,
I had once tried to do the same thing as you do here, but had no time to finish it and later forgot about it. Any how I found an algorithm that can speed up the voxilization process.
It went something like this:
[ol]
[li]loop along the x bounding box edge using ‘c’ as the step size
[/li][li]loop through the y bounding box edge using the same step size
[/li][li]fire a ray from where you “stand” at the direction of the z axis
[/li][li]determine if you are inside the volume or outside the volume
[/li][li]if inside, go to where the ray hit, else, all voxels between where you stand and where the ray hit are occupied.
[/li][li]continue in that fashion until you get to the end of the bounding box.
[/li][/ol]
to determine if you are inside or outside the volume I used this method (O(1)):
intersectRay only hits a mesh face only if it is fired on the side of the face that points in the direction of it’s normal. So I fire one ray on the object, then I use a normal modifier to flip the normals of the object and fire another ray.
cases:
[ol]
[li]the first ray had a hit and the second didn’t: you are outside the mesh.
[/li][li]the first ray missed and the second had a hit: you are inside the mesh.
[/li][li]both rays missed: you are outside the mesh.
[/li][li]both rays hit: if the first ray hit closer then the secons, you are outside, else you are inside.
[/li][/ol]
P.S: you should choose the 4rd axis in the algorithm to be the longest.
Hope this helps…
M.
Hei TzMtN,
yeah, I saw your approach when I was checking the forum if there was kind of voxel-technique in Max.
Actually my Script heads in your direction. I scan in every direction twice to see if I’m inside or outside the mesh with normals flipped on. That is all cool and actually I liked the idea to leave out an axis and only go with two axis like a 3D printer.
What frightens me with your approach is that I’d have to flip the normals for every region a ray hits. That would become an enormous runtime.
Or do I get something wrong?
Another approach I thought about was: Copying the mesh flippimg the normals and so having two meshes stick into eachother. Then you’d have to store all the points a ray hits and use kind of a recursive function to get all points in one ray-direction… my problem is, that Max crashed when I wanted to test more than 4 Points that had been hit
Could you explain exactly what is your algorithm and / or post a code example?
Of course, but since Max crashed I can only rewrite the pseudo-code from my imagination:
- I’ve cloned the model, flipped all faces of the clone and attached it to the original.
- I’ve created a recursive function saying: If ray hits a surface, take the actual hit-position and start this function again from the last hit-point… and so on. The recursion stops if the ray is undefined.
For a cylinder shoot in X direction this would lead to: First hit (outer hull), second hit (inner hull (flipped clone)), third hit (inner hull other side), fourth hit (outer hull (other side)), stop. - Now I found four points (where two points are identical) and theoretically I can now say where is inside and outside and fill the inside of the object with “voxel areas”. I thought that this method might be cool if it comes to overlappings such as “If two feet are standing next to eachother”. Cause so I’d find the first foot outside and the other side of it and then I’d find the second foot.
Was this clearer?
Yes it was.
My guess is that when you fire the ray from the point of the last hit, and because of precision reasons it is maybe possible that you hit the same surface again and thus entering an infinite loop. This will cause max to crash.
In order to avoid such a problem you could move a bit forward from the point of the last hit before firing the next ray. A recursive function by itself wouldn’t cause max to crash, only if it leads to an infinite loop.
About flipping the normals. From your description it sounds like you are manually flipping every face using a loop. If this is the case, then you should try to use the normal modifier instead.
You said that when using my algorithm, the bottle neck was to flip the normals every time back and forth, you could instead make a duplicate of the original object without attaching them, and fire a ray on both of them. In some cases you can even avoid firing on both of them and determine your status with only one ray.
Hope this helps,
M.
Allright I found the error, corrected it and came to the point where the voxelation isn’t the real problem.
Actually voxeling the mesh was quite cool. It took the algortihm three minutes for splitting up every axis proportionally in at least 50 steps per axis. This was cool.
The real drama began, when I started searching for the shortest distance.
At first it seemed cool, cause since it’s a grid every neighboring voxel has the same distance which meant that I wouldn’t have to deal with complex Depth-Search-Algorithms which might slow down the system and use a lot of memory.
So I went directly to the Breadth-First-Search to expand the selection stepwise and so to find the voxel that contains the mesh-point that is the nearest neighbor to the voxel that contains the bone-point.
This was a desaster. Cause it takes the algorithm 20 seconds for a distance of 10 in a voxel grid with the extension: 31x 13 x 38. Imagining that this has to be calculated for every meshpoint with every bone-point leads to an enormous runtime even if I limit the max possible distance after the algorithm would have to stop. Sooo… programming it in C++ might perhaps solve the problem but I really ask myself if the basic problem isn’t rather the approach of using a volume or the search for a shortest path.
You’re right if we would be talking about “long” in the sense of “having an end” then this would work. But the problem with that approach was, that it allocated so much memory that your PC would have hung even before you’d have had any vertex skinned.
Buuuuuut I was pretty excited when I recognized that I assumed things in a wrong way: I thought that you'd have to calculate the shortest path from every bone-voxel to every Meshpoint solely. But that is impossible and I even would say "wrong". I guess one "just" has to calculate the shortest path in the voxel-grid from the bone-point to a n y other voxel which is no problem of finding a specific voxel but finding all voxels. This is still a bit expensive but takes less time.
At the moment calculating the shortest path to any voxel for one bone is around 25 seconds (Voxelgrid density: 56 x 23 x 68). I guess that can be speeded up if the user sets something like an exit value cause it makes no sense to calculate the shortest path for e.g. the voxels in the head if you want to skin the foot. :)Ok, I will be watching this thread with great interest .
Good luck.