Fever Dorian's Sphere Packing code optimized

[notanymike]

I've converted the following code from being all pymel to mostly using
the Maya API, mainly for fun:

http://www.fevrierdorian.com/blog/post/2011/03/14/Remplir-un-mesh-de-spheres-dans-Maya-La-methode-d-un-senior

My code is available here:

http://pastebin.com/3KbhXagZ

It's a bit faster...I also attempted to translate the french parts of
the code into English, though I don't speak French, so it's just an
educated guess....

I was hoping to create a "skeletonizer" script, but maybe someone will
find what I've got here useful as is...

[notanymike]

Update:

It turns out the code was written by Djelloul Bekri, and Dorian had
just explained how it works on his blog...

On Feb 10, 9:05 am, notanymike <notanym...@gmail.com> wrote:
> I've converted the following code from being all pymel to mostly using
> the Maya API, mainly for fun:
>

> http://www.fevrierdorian.com/blog/post/2011/03/14/Remplir-un-mesh-de-...

[Justin Israel]

Hey,

While I actually am not really familiar with the original problem that this trick solves, after seeing your code I got somewhat hooked today trying to optimize it further. I thought I would post what I've to be able to have some discussion about it. There were a couple things I was confused about... But first, here is my pass at further modifying your code:

https://gist.github.com/1795840

Some changes:

1. Removed all the remaining pymel
2. During the first loop that computes the radius of each point, I create an MPoint as well and save all of the data in an object. 
3. I sort the object by radius size instead of doing that extremely repetitive loop to find the biggest sphere each time. Instead I figured we could just start with a sorted list and work through it. Am I wrong about this approach? Did they need to remain in the original order for some reason? I didn't think they did and all we care about is having the biggest spheres first.
4. For the main intensive loop, since we no longer have to do the size test, we just go forward over our sorted list, popping off the next biggest, and then doing the collision test on the remainder.

I noticed that (at least in my own tests) the original version, yours, and mine all did not properly set the radiusPP values on each particle. They all end up being 0.2. I can go and change them individually in the scene via the component editor, but I have yet to figure out how to get them to actually set in the script. So that remains unsolved.

I think my version should be faster the more steps you use and the more complex the geometry. When I tested 60 steps on a very large sphere, my results were showing a ~30% increase in speed from yours. 

Very interested in messing with this :-)

--
view archives: http://groups.google.com/group/python_inside_maya
change your subscription settings: http://groups.google.com/group/python_inside_maya/subscribe

[notanymike]

Hi, I think the radius won't be set unless in the actual nParticles-
createNPartciles menu, the box under "points" is checked, I believe. I
had a similar problem as well until I did that. In terms of my slight
fancy to have this work as a skeleton-extraction script, do you think
sorting method you introduced would make it easier to pick the spheres
whose positions would be best for joint placement?

I'm glad that I'm not the only one who got hooked on this little
script. Congratulations on what you've gotten so far, I didn't know
MFnParticleSystem supported NParticles!

On Feb 10, 7:48 pm, Justin Israel <justinisr...@gmail.com> wrote:
> Hey,
>
> While I actually am not really familiar with the original problem that this
> trick solves, after seeing your code I got somewhat hooked today trying to
> optimize it further. I thought I would post what I've to be able to have
> some discussion about it. There were a couple things I was confused
> about... But first, here is my pass at further modifying your code:
>
> https://gist.github.com/1795840
>
> Some changes:
>

>    1. Removed all the remaining pymel
>    2. During the first loop that computes the radius of each point, I

>    create an MPoint as well and save all of the data in an object.

>    3. I sort the object by radius size instead of doing that extremely

>    repetitive loop to find the biggest sphere each time. Instead I figured we
>    could just start with a sorted list and work through it. Am I wrong about
>    this approach? Did they need to remain in the original order for some
>    reason? I didn't think they did and all we care about is having the biggest
>    spheres first.

>    4. For the main intensive loop, since we no longer have to do the size

[Justin Israel]

What would be the exact criteria for making it produce output that is best suited for your joint extraction?
The sorting im doing does greatly improve performance by getting the data radius sorted once very quickly. As for your needs im sure its just a matter of how to adjust the comparisons. Right now the algorithm is geared towards filling the space with as few spheres as possible. Can you maybe explain your pseudo process for what you want to achieve?
Yea I get kind of distracted easily by these kinds of things :-)
Its good practice for me anyways to try and optimize maya code. Im not even sure why the original developer used pymel. Its way to slow to use in heavy loops. Really the goal is to do as little as possible on the python side and let the C api handle what it can. Small things like setting properties once dont really gain much though obviously.

[notanymike]

Well, I'm not an algorithms person, actually. So my ideas on the
matter can't be all that reliable, I think. I really just wing it when
it comes to Maya's Python API, I haven't actually learned Python yet,
or any other programming language, for that matter. That being said,
I'm not really aiming for something that makes a perfect skeleton on
it's own. However I'm fed up with auto-rigging systems that start out
with "placers" that are way off the scale and proportion of the model
and sometimes even not in the right pose. I would even be more
satisfied with having a curve-extraction script which I can create
joints off of as long as I had a decent head start with joint
placement. For now the only way I could think of doing it is take the
largest spheres among a group of spheres that are close within a
tolerance, and use the API to get the center of that group by creating
a MFnMesh and adding polygon with all those positions, getting that
polygon's center, then creating a joint, locator, or curve point from
that center. The problem with that is the tolerance needs to be
adjusted when the volume in the mesh shrinks (from the torso, to the
arms, to the fingers, for instance). I have no idea how to do that
part....

On Feb 11, 10:07 am, Justin Israel <justinisr...@gmail.com> wrote:
> What would be the exact criteria for making it produce output that is best suited for your joint extraction?
> The sorting im doing does greatly improve performance by getting the data radius sorted once very quickly. As for your needs im sure its just a matter of how to adjust the comparisons. Right now the algorithm is geared towards filling the space with as few spheres as possible. Can you maybe explain your pseudo process for what you want to achieve?
> Yea I get kind of distracted easily by these kinds of things :-)
> Its good practice for me anyways to try and optimize maya code. Im not even sure why the original developer used pymel. Its way to slow to use in heavy loops. Really the goal is to do as little as possible on the python side and let the C api handle what it can. Small things like setting properties once dont really gain much though obviously.
>

[notanymike]

there might be a simpler way...there's a curve fitting program called
zunzun which has a python api that I can't figure out yet...
https://code.google.com/p/pyeq2/