It looks like the angle limits are no longer in the TDMT code I've been using.  I was calling more than once, but to accomodate multiple octree passes.  The slowdown was at the end, when it was checking the outstanding 52 vertices against the entire mesh, using only one octree zone (in the shrinkwrap, not TDMT itself).

As usual, I haven't read the code carefully.  I'll study it and see how it needs to be implemented.

Edit:

Okay.  I see what you did.  The alternate code I've been using also does the back-facing test for the polys.  It does seem more straightforward.  But I don't understand the idea of running the function only once.  There were two reasons for doing multiple runs.  One was varying the angle, as noted.  The other was enlarging the bounding boxes, to catch possible cases in which no match was found due to the octree divisions cutting the correct match tri out of the point's octree zone.  My tested multiple runs were for that purpose, and each run did find something.  The final "catch-all" phase was very slow about it, however.

So how do you suggest the new code be implemented in TDMT, given the octree handling?

re: Angle limiting issue...

The testing for angle limits was causing false hits in some cases.  Basically, the code is/was looking for the "closest match" (polygon intersection) within some region, but screening out polygons that didn't meet the angle limit test.  If it found some hit, the xpolys[] array was set to the hit poly for that vertex.

On the next pass, the angle limit was relaxed, but the only vertices tested were ones that didn't yet have an xpolys[] entry (no hit yet).

The problem with this is that the 'best match' poly (say, on the chin) could have failed the more stringent angle limit test on the first pass (when a bad poly on the nostril/inner_mouth got selected) because it was never tested.

If the angle test was not there,  the code would have still hit the nose/mouth poly, but later found a better match on the chin poly.

The solution to this problem is to stop weeding out steep angled polygons, which means you only need to do one pass through that code (relative to this issue).

re: Longest-edge region expansion issue...

To be honest, I had forgotten about this.  I'd recommend just doing this for the first (or only) pass. Alternately, putting the "if xpolys[vi] == -1:" test back in, but also passing a flag to the routine to determine whether or not to do that test, because of the next issue...

re: Polys/Verts can belong to more than one region...

It's also recently occured to me that when the regions are inflated/expanded (without looking, I think the original regions are/were also inflated by some small amount), then the "best match" might actually be in some 'other' region than the one being tested, so we can get false hits in some cases because of this.  Currently, there are two issues related to fixing this...

1. the "if xpolys[vi] == -1:"  test would keep you from finding newer/better matches in other regions.

2. Once #1 is fixed (don't use that test on the first (or only) pass), there's still a problem that the matchdist variable gets re-initialized (for each vertex) within each region test.

...to fix this second issue, you need another array of matchdistances (one per dest vertex) instead of the single local variable.  This array should be initialized to 10000.0 (or more), before calling linecast_loop().  This would let the code look at all relevent polygons, storing the closest match it found (regardless of which region it was in).

In short:

• either do the longest-edge region expansion on the first pass, or put the "if xpolys[vi] == -1:"  back in.
• If you put the "if xpolys[vi] == -1:"  filter back in, make sure you can disable that test on the first pass.
• in either case, the local matchdist variable needs to change to a matchdist[per_vertex] array, so that the value survives across regions.

The attached is presented just so you can understand what I'm on about....

Aha!  I'll try what you suggest, with the "if xpolys..." and I'll have to think about an array for the matchdists.  What you say with that makes sense.

Hmm, hmm.

BTW, I tested the Moller / Trumbore Fast, Minimum Storage Ray/Triangle Intersection code in my other plugin and it suffers from similar rounding-error issues as the current point-in-tri code based on Dan Sunday's Intersections of Rays, Segments, Planes and Triangles in 3D code (which itself is based on the Moller / Trumbore code).  I haven't studied your implementation of the Moller / Trumbore code, so it's possible that you got it working fine, but I'm not sure it buys you anything over the current implementation (assuming the epsilon/tolerance values are set correctly in each).

The biggest distinction between the two is that the original Moller / Trumbore code doesn't require pre-computing/storing the tripoly 'plane' equations.

Without spending more time adjusting the Moller / Trumbore code, so far, my best results have come from the current Sunday-based implementation.

Ah.  Moller / Trumbore.  Right, the planes aren't pre-calculated for that.  Moller / Trumbore.  Hmm. 

This was actually faster than the... Moller / Trumbore.

def bary(rayOrg,rayDelta,n,p0,p1,p2,d): # Neil Hayes' awesome code - inputs rayOrg, rayDelta (@axis), trinormal, p0, p1, p2, polydistancefromplane
    #d is a plane, as in Geom.polyplanes
    """
    Adapted from jj_wrap.pl  version 2.2b (shrink-wrapping perlscript for Modo) by:
    julian johnson: julian@exch.demon.co.uk
    http://www.exch.demon.co.uk/jj_modoscripts.htm
    """
    ### Is ray pointing to front side of tri and not parallel
    ndot = n[0]*rayDelta[0] + n[1]*rayDelta[1] + n[2]*rayDelta[2] #dot(n,rayDelta)

    if not ndot < 0.0: return (-1, [0.0,0.0,0.0], ndot)

    ### compute parametric point of intersection
    t = d - (n[0]*rayOrg[0] + n[1]*rayOrg[1] + n[2]*rayOrg[2]) #dot(n,rayOrg)

    ### Is ray origin on backside of poly?
    if not t <= 0.0: return (-2, [0.0,0.0,0.0], t)

    ### Ray intersects plane so compute intersection point
    t /= ndot
    p = [0.0,0.0,0.0]
    p[0] = rayOrg[0] + rayDelta[0] * t
    p[1] = rayOrg[1] + rayDelta[1] * t
    p[2] = rayOrg[2] + rayDelta[2] * t

    ### Find dominant axis to project onto
    if abs(n[0]) > abs(n[1]):

        if abs(n[0]) > abs(n[2]):
            ##remove X
            u0 = p[1] - p0[1]
            u1 = p1[1] - p0[1]
            u2 = p2[1] - p0 [1]

            v0 = p[2] - p0[2]
            v1 = p1[2] - p0[2]
            v2 = p2[2] - p0[2]

        else:
            ##remove Z
            u0 = p[0] - p0[0]
            u1 = p1[0] - p0[0]
            u2 = p2[0] - p0[0]

            v0 = p[1] - p0[1]
            v1 = p1[1] - p0[1]
            v2 = p2[1] - p0[1]

    else:
        if abs(n[1]) > abs(n[2]):
            ## remove Y
            u0 = p[0] - p0[0]
            u1 = p1[0] - p0[0]
            u2 = p2[0] - p0[0]

            v0 = p[2] - p0[2]
            v1 = p1[2] - p0[2]
            v2 = p2[2] - p0[2]

        else:
            ## remove Z
            u0 = p[0] - p0[0]
            u1 = p1[0] - p0[0]
            u2 = p2[0] - p0 [0]

            v0 = p[1] - p0[1]
            v1 = p1[1] - p0[1]
            v2 = p2[1] - p0[1]

    ### computer denominator for 2D projection
    temp = (u1v2) - (v1u2)
    if not (temp != 0.0):
        return (-3, [0.0,0.0,0.0], temp) #try next poly

    temp = 1.0/temp

    ### compute each barycentric (check for out of range)
    alpha = (u0v2 - v0u2) * temp
    if not (alpha >= 0.0):
        return (-4, [0.0,0.0,0.0], alpha) #try next poly

    beta = (u1v0 - v1u0) * temp
    if not (beta >= 0.0):
        return (-5, [0.0,0.0,0.0], beta) #try next poly

    gamma = 1.0 - alpha - beta
    if not (gamma >= 0.0):
        return (-6, [0.0,0.0,0.0], gamma) #try next poly

    #if made here then ray hit a target tri
    return (1, p, t)

Ok, I just ported that over to my plugin and... I can't say whether it's faster or not (not an issue in my plugin :) ), I can see how it could be faster, since in the worst-case, it does 8 total multiplies and one divide (once you remove the stuff that's already done in linecast_loop()).  Verses 11 multiples and 2 divides. It can also fail faster and in more places, keeping many of those multiplies from happening (best-case is only 2 multiples, vs.  9 multiplies and one divide in the current code).

As for it's robustness, without any tolerance values added, it appears to work more reliably than the other routines do without any tolerance values added, but it's still missing some hits.  It's currently not as reliable as my current implementation, with the epsilon/tolerance values I gave you the other day.

If this code is significantly faster than my current code (?), I can mess around with it and see if I can make it work better.

Just for kicks...

[NUDITY WARNING]

Standard Cylinder, with figure's texture applied...

Shrink-wrapped to figure...

...with uv-mapping transfered from figure...

I think it might be faster because there are more cases in which it might escape before doing any serious calculations?  When I looked at your version, it calculated several things up front, before it checked to see if we could escape.  Or am I wrong in thinking that?

What you've done there is kind of what I've been working with in shrinkwrapping.  How would you try to accomodate the split between the legs?  Part of my trouble has been moving verts without hits into line with the others.  Another problem has been dealing with shrink cases in which the normals of the shrinking object don't handle so well for the purpose of the shrink.

Mind you, this is veering OT for TDMT discussion, isn't it?

I'd forgotten what a headache scaling is!  Translate to world center, then scale, then translate back.  Feh.

Quote - I think it might be faster because there are more cases in which it might escape before doing any serious calculations?  When I looked at your version, it calculated several things up front, before it checked to see if we could escape.  Or am I wrong in thinking that?

Yes, that's basically what I said above :).

Quote - What you've done there is kind of what I've been working with in shrinkwrapping.  How would you try to accomodate the split between the legs?

I wouldn't. (as a user/operator of the plugin, I'd fix my input mesh to also have it split at that spot, if that's what I wanted).

Quote - Part of my trouble has been moving verts without hits into line with the others.

Options:

1. fix the code so there are no missed hits.
2. move them to the average of thier neighbor verts.
3. before moving any verts, determine the missed vert positions relative to thier neighbors, then move the hit verts, then move the misses into thier neighbor-relative positions (relative-position-weighted).
4. do nothing with them.

...both 2 & 3 have additional issues when neighbors are also 'misses'.

Quote - Another problem has been dealing with shrink cases in which the normals of the shrinking object don't handle so well for the purpose of the shrink.

Not much you can do programatically about that.  That requires the code to divine intention on the part of the user - something typically difficult to do :).

Quote - Mind you, this is veering OT for TDMT discussion, isn't it?

That hasn't stopped us before :).

*"Yes, that's basically what I said above :)."

*Right.  I can see that, now that you point it out....  I wasn't equating the term "fail" with "escape" when I read your initial post.  Erm.

*"...both 2 & 3 have additional issues when neighbors are also 'misses'."

*I've basically implemented both of these.  Clusters of missed verts require multiple passes for correction.  Another thought I had was moving inward in waves, colliding as we go.  So everything moves until things stop.  This would require some sort of cloth-like stretch limit, to stop neighbor verts when a vert has collided and the neighbors reach their limits.  That's been a wee bit beyond me so far, however....

*"Not much you can do programatically about that.  That requires the code to divine intention on the part of the user - something typically difficult to do :)."

*For that I provide various different ways of processing the normals, with a user selection among the types.  Hence my question, earlier, about capsule mapping.  I got capsule mapping to work, but it's a bit of a kludge, alas.

"That hasn't stopped us before :)."

I think the only thing that's stopped us so far is UVs.  Well, I've been stopped by the limits of my intelligence. 

**

I have a thought for trying to simplify correlations between objects.  Now, don't freak out, because this starts out sounding like something you didn't like before (mapping both objects to a sphere).

Say we want to compare two dissimilar heads which aren't easily lined up well for TDMT.  Start with a simplified "head" geometry, a proxy shape to which we can compare both our desired source and target, in order to get common correlations.  Shape this simplified mask as well as possible for both the source and the target (lining up nose, corners of eyes, mouth, etc, for both).  Run the source and target comparisons, each with the appropriate go-between low-res head proxy.  Hypothetically, now, we have both source and target mapped to a common geometry.

Then process the resulting .vwt files to find correlations between the desired source and target, using their common collision locations with regard to the low-res head.  I think we'd need to start with the low-res head triangles that both source and target would have in common.  Then, we'd need to map the target collision points to source triangles.  I think this probably gets back to the parametric part of your point-in-tri code.  I'm thinking of it like using the 2D version I added into the UV code.

Clear as mud?  Basically, we've re-shaped a common geometry for the source and target actors, so we have tri and vertex structure commonalities which we can try to use to correlate source and target through a shared, uh, comparator.  Did I just make up a word?  Am I babbling?

I'm also trying to figure out how to port the point-in-tri code to a .pyd file, or even a compiled .exe or .dll, to see what speed gains can be had.  I'm having some troouble getting a working compiler together for that, and I'm going to have to muddle through trying to learned the basics of C++.  My experiement with popen suggests that a simple command line .exe could be created to do the hard math, and called at need.  A .pyd might be better, in that we could just call it like a Python module.  I'm not sure how to use a .dll in Python.

Anyway, I'm thinking varied thoughts of uncertain utility again....

Yeah, I think we covered that idea back on the top-third of page 4 :).  I don't think it's a fruitfull path to go down.  Having said that, I wouldn't discourage you from experimenting either.

re: C++ version

Comming up with a C version of a couple of those routines is easy enough (I already have it in my plugin).  The problem is in the hoop-jumping needed to get the data back and forth.  A .pyd (compiled python?) may be the easiest route to take (I have no idea what's involved though, only that the data format/access may be easier).

A .pyd could supposedly be generated using Pyrex and the version of Python which Poser uses.  I've tried to get it to work, but I haven't yet acquired the Microsoft Windows include files necessary for the process.  Pyrex can generate C code from a mutant C/Python file with a .pyx extension.  Then (in theroy, and this has evidently worked for some), the C code can be compiled into a .pyd.  This also requires the source code for the appropriate version of Python.  I won't be able to buy a fully functional C compiler for a month or two, so I've been looking into the idea of a command line .exe, which might be more easily generated from the existing code.  Whether Python could handle calling something like this repeatedly for a collision loop is the open question in my mind....

So we covered the common mapping on page four?  I remember a sphere being discussed.  I was thinking of mapping to a generalized head shape, which would be easier to shape for good correlations than trying to shape and position the actual source and target.  This would basically be a way of teaching the script: "this is where the nose is on either mesh", etc.  The different feature shapes would be correlated to common tris in the generalized head shape.  No go?  Hmm....

BTW, you can download Microsoft Visual C++ 2008 Express Edition for free.

Quote - A .pyd could supposedly be generated using Pyrex and the version of Python which Poser uses.  I've tried to get it to work, but I haven't yet acquired the Microsoft Windows include files necessary for the process.  Pyrex can generate C code from a mutant C/Python file with a .pyx extension.  Then (in theroy, and this has evidently worked for some), the C code can be compiled into a .pyd.  This also requires the source code for the appropriate version of Python. 

What about creating a "stand alone" version of the worker process (in C++, C#, whatever) and just hand over all data from Poser Python through named pipes or IPC? I do this with a few apps. So I'm able to process/compute Poser data on several machines/processors at once. Poser Python is only used to syncronize processes and to distribute/collect pre-computed data.

@ Spanki: Having failed for the umpteenth time to get Dev-C++ to do anything, I downloaded the free Visual Studio 2005 Express last week.  I need to update to the Vista version before it will do anything else, and I can't download the Windows include files because my connection is too slow for the 413 MB download.  :(  I hadn't realized the 2008 version was available.  I'll check it out.  I was looking into buying an old copy of the 2003 C++ (which was used to build Python, apparently), for cheap at Amazon.  But that would be a month or two down the road.  Who knows, I may have a faster internet connection (finally) before then....

@ ADP: That's kind of what I was groping toward.  The process would have to call popen for the pipe with every loop iteration, right now.  I guess I should embed the loop code into the hypothetical C port.  Hmm.  I think I should be able to compile a command line utility without needing those Windows include files which I can't download.  Can you tell us anything about using an actual .dll with Poser Python, rather than a .exe or .pyd?

The Express version doesn't have all the bells and whistles of the Standard version, but it's enough to create console apps, full windows apps, games, dlls, etc.  BTW, the Express version(s) of Visual Studio count towards (qualify you for) 'upgrade' pricing on the Standard and Professional versions - so no need to ever buy the full retail version - if you find you need to upgrade to the Standard version at some point, you just pay upgrade pricing (~$175 or so, instead of ~$270 for the full retail box).

And yes... if you moved any of that to C, you'd want to move the entire linecast_loop() functionality over and just figure out how to get the data (various arrays) to it and the results (various arrays) back from it.

I assume you'd open a pipe, spawn the C app, have the C app connect to the pipe, get data, process data, return results and exit, but ADP should have a better idea of the best way to do all that (or going the .dll route - which would be even cleaner, if you can figure out the data / stack / function-calling interface).

Thanks for the information!  :D  I'll work on compiler issues as I have time online, in the next few days.

I've managed to work with a pipeline to an external .exe (see my recent thread on convex hulls and popen).  I can't find any examples for using a .dll instead of a .exe, unfortunately.  And, for our purposes, porting the linecast_loop over would be a major revision.  Yipes.

Quote - I've managed to work with a pipeline to an external .exe (see my recent thread on convex hulls and popen).

Do you have the C source to the exe that shows how the pipe works on that side of things?

Quote - I can't find any examples for using a .dll instead of a .exe, unfortunately.  And, for our purposes, porting the linecast_loop over would be a major revision.  Yipes.

Not a big deal... except for the additional data it needs (the region arrays to loop through, tripoly, vertex, normal and other data arrays, etc).  Heck, it could/should (might as well) compute the weight tables as well.

If you can figure out how to get these arrays...

vregs
xpolys
dstVerts
vnorms
pregs
pnorms
pplanes
tverts
srcVerts

[EDIT: along with some variables like 'numDstVerts', etc]

...across a pipe or as arguements to a .dll function call (and accessable by C/C++ code), I can port my current C code to do the current entire linecast_loop() and compute_weighting()  functionality (heck, pretty much anything/everything in the current tdmtSpanki.py file).

I don't have the source code for the qconvex.exe.  I don't think they had the code available at their site (which is linked in the thread).  If you're asking because you're interested in how they build the hull, I do have a link somewhere to a (slightly buggy) Blender script which does the same thing, using Python in Blender.  If you want to know how qconvex receives and processes the data, I can't really help with that.  :(

Let's see.  We wouldn't be able to send Numeric arrays across to an external .exe.  The arguments would go across as strings.  What sort of format would a C application require for the information?  It would have to do some processing on its end, I think, to convert the arguments back into a form it can use.  I have code that can literally export the lists or arrays to a .txt file.  I think there's a basic function for that in the UV code for TDMT.

Ideally, I'd like to see our math library and these two alternate point-in-tri functions ported to an external app too, if that would speed things up.  That was to be my first test, porting the alternate point-tri stuff to see how speed is affected (because it would be easier for me to test all of this using the less complex shrink-wrapping script I'm working on right now than to alter TDMT).  But... one thing at a time, right?

So, how could we get the data across as strings, both ways?  What would need to happen on the C end to read things back in?  What sort of export formatting for the strings would be desirable, from Poser?

I was interested in the source as some example of the pipe and data-passing mechanism.  My answer to most of your questions above is - I don't know :) (which is why I was looking for some example code).

Having said that, I'm pretty comfortable saying that using a separate .exe for just (individual) point-in-tri tests would be a waste of time and effort.  The overhead involved in calling it  thousands or tens of thousands (or even hundreds of thousands) of times would out-weigh any benefit of having it compiled.  It's possible that even doing (just) that with a .dll would be a waste of time.

To get any real benefit, you want to do all the looping through the tables in C as well.  I hadn't looked closely at your shrink-wrap code, but I'm sure it's doing something similar to the linecast_loop().

As for using strings/files - I'm not crazy about that idea. It's a lot of data to be converting to strings and/or creating files for.  Ideally, there'd be some way to pass a pointer to the array to the C code, which could then do whatever it needed to do to access that array of values.

Maybe ADP has some suggestions/thoughts/sample code?

My trouble is that I'm not familiar enough with Python and/or the Python<->dll mechanism and don't have lots of free time to go investigating it.  If you want to do some leg-work tracking down some links to info and/or sample source code showing how this is done, I can spend some time looking at it.

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146847

Just offhand, I found the above, which provides a wrapper for something called calldll, which is available at the link below.

http://www.nightmare.com/software.html

I'll have to see what either of them really does.  In the meantime, I'll keep looking around....

Edit:  It looks like calldll is a .pyd which includes source code.  That, in itself, might be helpful...?

Thanks...I'm scanning the ctypes module notes currently.

CTYPES wont work with Poser Python.

Ctypes is part of Python 2.5 (and above)

Poser Python is NOT a standard implementation of Python.

Allow a bit time to answer your questions about a kind of framework to use with an external app. I have to write an example because I'm not good enough with english to describe it clearly :)

It is possible to use a DLL with Poser Python. But it is more complicated as you may think. And less flexible (the reason why CTYPES is now part of Python). Have a look here: http://docs.python.org/ext/ext.html

@ADP

Thanks for the additional info... I'm still interested in any samples/examples/suggestions you might have on alternatives if/when you get a chance.  In the meantime, I spent a fair amount of time researching the "extension" (via .dll / .pyd) method and you're right - it looks like a pain in the ass :).  Having said that, it looks doable, if we convert some of the current 'lists' of data back over to NumPy multi-dim arrays.

So far, I haven't found any good info on getting 'list' formatted python data into C-readable format (I can see how to get a PyListObject, but it's entirely unclear on how to get at the multideminsional array data in it).  On the other hand, NumPy seems to have a good set of C/API wrapper functions available, but I'm still looking into the mechanics.

Data conversion isn't a problem. There is a module called "struct" made to move data between Python and C-structures. Part of Python since ever. I'm using this to transport data between Poser and external Apps.

Try this:

-----------------------------------------

import struct

X=1.2345
Y=3.567890
Z=7.3434673453

packedpoint=struct.pack("3f",X,Y,Z)
print packedpoint, len(packedpoint)

print struct.calcsize("3f")
X,Y,Z = struct.unpack("3f",packedpoint)

-----------------------------------------

"3f" means: 3 floats. See http://docs.python.org/lib/module-struct.html

Above the 3 float vars (X,Y,Z) are packed in one string (packedpoint). The needed length of the string is explored via "calcsize()".

I'll take a look at struct, thanks.  In our current code, we're using lists-of-lists-of-floats to represent multiple vertices.  For example, 2 vertices would be represented as:

2verts = [[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]

...except that there's (10s of) thousands of verts in each list (however many make up the model).  Using the above format, to get at each element (x, y or z value of some vertex), we ultimately do something like:

for vNdx in some_index_list:          # Loop through vertices
    vert = verts_list[vNdx]     # get desired vertex
    vX = vert[0]                       # de-reference each element
    vY = vert[1]
    vZ = vert[2]

...except that it's usually more involved than that, because we're typically looping through the triangles in some list, then grabbing the 3 vertices of each triangle.

I think I finally figured out how to get at each element in C last night, but I fell asleep before verifying it.  Here's my simple testing code:

//==================================================================<br></br>
// test( *pVerts )<br></br>
//==================================================================<br></br>
static PyObject *ex_test(PyObject *self, PyObject *args)<br></br>
{<br></br>
 PyListObject *pVectorList;  // the passed in vector list
(list-of-lists)<br></br>
 PyListObject *pVector;<br></br>
 PyFloatObject *pElement;<br></br>
 double vX = 0.0, vY = 0.1, vZ = 0.2;<br></br>
 long vCount, i;

 // start by deconstructing the args<br></br>
 if (!PyArg_ParseTuple(args, "O", &pVectorList
))<br></br>
  return NULL;

 // get vertex count<br></br>
 vCount = PyList_GET_SIZE(pVectorList);<br></br>
 <br></br>
 // try to modify each vertex...<br></br>
 for(i=0; i<vCount; i++)<br></br>
 {<br></br>
  // get each vertex/vector (another list)...<br></br>
  pVector = (PyListObject *)PyList_GET_ITEM(pVectorList,
i);

  // ...then each element of the vertex (a
float)<br></br>
  pElement = (PyFloatObject *)PyList_GET_ITEM(pVector,
0);<br></br>
  // vX = PyFloat_AS_DOUBLE(pElement);<br></br>
  PyFloat_SET_DOUBLE(pElement, i+vX);

  pElement = (PyFloatObject
*)PyList_GET_ITEM(pVector, 1);<br></br>
  // vY = PyFloat_AS_DOUBLE(pElement);<br></br>
  PyFloat_SET_DOUBLE(pElement, i+vY);

  pElement = (PyFloatObject
*)PyList_GET_ITEM(pVector, 2);<br></br>
  // vZ = PyFloat_AS_DOUBLE(pElement);<br></br>
  PyFloat_SET_DOUBLE(pElement, i+vZ);<br></br>
 }

 Py_INCREF(Py_None);<br></br>
 return Py_None;<br></br>
}<br></br>

...etc.

Note that the PyFloat_SET_DOUBLE() is my own macro and may not be functioning properly at this point.

We can de-reference more easily if we do:

for vNdx in some_index_list:          # Loop through vertices
    vX,vY,vZ = [i for i in verts_list[vNdx]]     # get desired vertex

or, for multi-level arrays:

for vNdx in some_index_list:          # Loop through vertices
    vert = [[j for j in i] for i in verts_list[vNdx]]     # get desired vertex
    (Then we'll need to sort out the inner levels....)

I don't think we go three deep anywhere, do we?
   

It all amounts to the same thing :).  If I understand your question, In the actual code, we don't go 3-deep (to start with), because we just grab v0, v1, v2 (3 vertices of a triangle), but to multiply (or otherwise deal with) the X/Y/Z elements of those, we're effectively going 3-deep, because we later de-reference v0[0], v0[1], v0[2] as well as v1[0]], v1[1], v1[2] and the same for the third vertex.

Right.  I just saw a place where I could possibly maybe contribute something.  :-P  You two are working in areas where I can't really follow, lacking a compiler.  Is there anything I can do at this point to contribute?  Or I can just sit back quietly and not interfere....

[dont't_freak_out]
...the biggest problem (IMO) with what we're doing currently (lists-of-lists-of-floats) is the shamefull amount of memory being used.  Note that each 'float' (x, y, z) is itself a PyObject, which is made up of:

int ob_refcnt;                          4 bytes
struct _typeobject *ob_type;    4 bytes for pointer, plus huge amount for the structure itself
double ob_fval;                        8 bytes

...so each float has it's own _typeobject allocated for it (roughly 20 pointers (4 bytes each) to other structures of various size, plus what may be another 2 dozen pointers to function calls), along with the additional 8 bytes for the refcnt and pointer.

We probably can't get away from the _typeobject per vertex, but if there was a 'vertex type' in Python (surely someone has already made an extension somewhere ?), we could at least save the 2 extra.
[/dont't_freak_out]

I'll investigate this more when I have more time.

Are you suggesting a reorganization of the Geom module?  We could organize things by vertex and polygon, instead of using generalized geometry lists.  Would there be a memory savings if we had a vertex class instance for each vertex and a polygon class instance for each polygon?  Wouldn't defining a new type be creating a class container for the data, essentially?  Or is there more to it?  I guess I should read the Python docs, huh?

Ah.  There is more to a type.  That involves building something in C, eh?

One of the Python packages for graphics handling might have something, but if we create a dependency to an external package, there are installation hassles for the end user, and the risk that the package might cease to be available at some point, or change and come into conflict with our use of it....

http://www.boost.org/libs/python/doc/

I'm finding many references to Boost.Python in a Google search for Python Vertex type objects....

Yes, to all of your above :).  I was referring to creating a new Python 'type', which yes, does require C code and yes, would involve installation issues.  I'll take a look at that link.

Please look at Poser standard array module:

import array

ar=array.array("d") # d for double, using 8 byte for one float
ar.fromstring()
ar.tostring(s) # results in a big stringbuffer

There is another standard method to move data around: "xdrlib"
http://docs.python.org/lib/module-xdrlib.html

As you may see, this problem isn't new ;)

More info from RFC 1014/1832 (http://www.faqs.org/rfcs/rfc1832.html)

Why not just move the whole geometry out of Poser to an external app and receive the final geometry back? An external app may use threads (with several processors) and give  computed results back to Poser in parts. This may at least feel faster because Poser isn't blocked.

It makes not mutch sense to use a lot of functions in a DLL if heavy data-conversion is required on each call. This way more time is spent to convert data as to compute results.

Forgotten to mention: With a (complete) external app based on IPC, you can use Python (2.5, 3.0) too. With all features Poser does not allow. Including CTYPE for easy access to DLL's (and many ready-to-go extensions that won't work with Poser-Python). This way it's possible to re-use code you allready have.

Havn't used this before, but looks like the right tool for you.

Pyrex lets you write code that mixes Python and C data types any way you want, and compiles it into a C extension for Python.

http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/

Works with Python >= 2.3

Quote - I'll take a look at struct, thanks.  In our current code, we're using lists-of-lists-of-floats to represent multiple vertices.  For example, 2 vertices would be represented as:

2verts = [[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]

Use Numeric (or NumPy) and this problem is solved with .flat, =resize(,new_shape), and/or a few more in no time (see Numeric Manual: http://numpy.scipy.org//numpydoc/numpy.html).

flat Accessing the flat attribute of an array returns the flattened, or ravel() 'ed version of that array, without having to do a function call. The returner array has the same number of elements as the input array, but is of rank-1. One cannot set the flat attribute of an array, but one can use the indexing and slicing notations to modify the contents of the array:

>>> print a

[[0 1 2]

[3 4 5]

[6 7 8]]

>>> print a.flat

[0 1 2 3 4 5 6 7 8]

>>> a.flat = arange(9,18)

Traceback (innermost last):

File "", line 1, in ?

AttributeError: Attribute does not exist or cannot be set

>>> a.flat[4] = 100

>>> print a

[[ 0 1 2]

[ 3 100 5]

[ 6 7 8]]

>>> a.flat[:] = arange(9, 18)

>>> print a

[[ 9 10 11]

[12 13 14]

[15 16 17]]

Really, what Poser itself needs is some kind of complete reorganization of their geometry data.  It's very hard to loop over vertex coordinates when you have to call them as X(), Y(), Z(), rather than being able to use indices.  And having to hand-calculate the vertex indices of each polygon, using the Start() and polygon length?  Feh.  I wish I had access to a compiler and had better programming skills.  I'd try to create something that would make all of this more accessible....

But I'm slightly OT....

Thank you for the information, ADP.  I was looking into Pyrex, with my initial idea of creating a .pyd.  Perhaps we've now come back full circle to the .pyd idea, with this thought of adding geometry built-in types?

If I remember right I said some time ago: Use Numeric.
But you have to use it consistently. Avoiding that data has to be moved between pure Python Objects and Numeric.

Numeric allows you to have your data the way you need it for fast computing (flattend arrays). And, the larger this set of data is, the smaller is the difference in speed to compute this data with Python compared to C. Numeric (or mutch better NumPy) isn't easy to use/understand. But very, very efficient.

Especially for large arrays you'll save a lot of memory with Numeric compared to standard Python objects. And, not at least because Numeric tries to use a continously memory block for the whole array, access ist mutch faster.

By the way: Why do you collected all vertices at once? I mean: If you compute - say - data from the head, why are the vertices for the feets are also loaded? Or is this a stupid question?

The problem is that you have a relatively large and complicated program written "top down" (or linear), not the "Python way" (object oriented). But re-writing at this point may cost a lot of time. So using a DLL seems to be the best way at the moment.

On the other hand, you are hardly limited by Poser Python (version 1.3, 1.5, 2.2, 2.4, perhaps 2.5 later, different features and restrictions, hard to debug). This is the reason why I prefer to collect data with Poser Python and move this data out (via TCP) to something with more bells and wistles.
Actually I'm testing using RPC to get data computed by 2 synchronized linux boxes. Poser Python does just transfer data. Not storing (beside of a transfer buffer). This is very fast, because the transfer is done concurrently in blocks of 2Kbyte (while there are pulled from Poser). Long before the last datapack is sent out, the first finished datapack comes back. And I'm able to turn "the dials" in beetween :)

I was looking into Pyrex, with my initial idea of creating a .pyd.  Perhaps we've now come back full circle to the .pyd idea, with this thought of adding geometry built-in types?

Keep in mind that for Pyrex it is the same as for other kinds of creating a DLL for Python: The used Python Header file has to match exactly the used Python version. But Pyrex works with Mac out of the box (as far as I know).

Actually, I'd have to re-aquaint myself with the python scripts, but I don't think we're actually working with the entire figure mesh data at one time, just the head verts/polys (for example), if that's the current mesh being matched against.

I did look at Pyrex the other day and may look at it again - I don't recall off-hand why I moved on to other possibilities, except that I was doing somewhat of a shotgun scan of the web, looking up various things about creating a .dll/.pyd file and ended up somewhere else :).

IIRC, Poser 7 comes with NumPy (or at least Numeric), so that's one option.  We tried that earlier on though and didn't see any great gains, but it's worth another look.

At this point, I don't want to do anything with the existing code - until I've had more time to investigate things (Numeric, NumPy, some form of dedicated .pyd, etc).  And that can be done with simple test-scripts.

ADP, I also agree with you about not doing tons of .dll calls, as that kinda defeats the purpose (too much overhead), but I'm not sure a stand-alone app is the way to go either.  If the .dll can provide high enough level functionality (doing the entire linecast_loop(), for example, along with some other utility functions and possibly new data type(s)), that might be the best approach.

My Cinema4D C++ plugin is several orders of magnitude faster (using similar orders of magnitude less memory) at doing this than the current python code, so I know it can be done faster - we just need to figure out the data access.

@ADP, thanks for the other links and info above too :).

Quote - ...the biggest problem (IMO) with what we're doing currently (lists-of-lists-of-floats) is the shamefull amount of memory being used.  Note that each 'float' (x, y, z) is itself a PyObject, which is made up of:

int ob_refcnt;                          4 bytes
struct _typeobject *ob_type;    4 bytes for pointer, plus huge amount for the structure itself
double ob_fval;                        8 bytes

...so each float has it's own _typeobject allocated for it (roughly 20 pointers (4 bytes each) to other structures of various size, plus what may be another 2 dozen pointers to function calls), along with the additional 8 bytes for the refcnt and pointer.

Ok, fortunately, I was wrong about the _typeobject being allocated for each instance of a float. It looks like there's only one static _typeobject per Python type (maintained by whatever module implements that type).  So that's just a pointer to the static one (whew).

So the memory issue is not nearly as bad as I suspected, but it's still an extra 16 bytes per vertex (8 extra bytes for the 2nd and 3rd floats), plus however much the extra 'list' structure that holds them is.

I'm currently messing with a 'vector' type .pyd extension to figure out how all that works, but ultimately I want to look at doing a vector-list type as well, along with various functions to work with them.

@ADP,

BTW, I'm not ignoring your various suggestions about arrays and string conversions, etc. - I'm just exploring various options and learning something in the process :).

Cage, in the meantime, is a bit lost, as usual.  LOL

As I understand it, there are some problems with trying to go completely over to Numeric (beyond the fact that there don't seem to be any useful examples that I can find).  The Linear Algebra module is broken in Poser 7, which means LinearAlgebra and Array modules can't be used and such functions need to be hand-coded.  That wouldn't be a crisis from our perspective, I guess, since we're doing vector math and not matrices.  But it seems to limit the possibilities (at least based on the limited examples I've seen).

But I'm totally confused about "object-oriented" versus "top-down".  I checked one of my three Python books on this, and it launches into listing the benefits of object-oriented programming, as opposed to C-style, without actually explaining what "object-oriented" really means.  I'm left assuming that Python modules give an example of such programming.  That's pretty much the only place I ever see that approach (as I understand it) used.  Pretty much all the implementations of Python I've seen for Poser or Blender use the C-style programming (as I understand it).  Which makes it a bit hard for someone who's teaching himself to figure out how to do things in a better way.  Hence, perhaps, all the spaghetti code that gets bandied about.  :(  I gather that many of my problems would be solved if I could be object-oriented, and I think I'd like to be, but I can't figure out how.  LOL again.

http://groups.google.com/group/comp.lang.python/msg/470b0f26b9558806?q=oe=utf-8

I'm wondering about the potential benefit of using metaclasses and perhaps doing something like the above example.  Would it be a better way of passing around the vertex and polygon (and possibly edge?) data if we created meta-metaclass instances?  Would it be better for memory consumption than having a bunch of comprehensive lists hanging around?  Metaclasses look useful, but would they be any kind of improvement?

Some initial test results...

First off, after reviewing the current code again, I see that we're already using Numeric.  With that in mind, I now have a basic 'vector' type module/extension, that keeps track of and manipulates 3 doubles (xyz but can also be referenced as rgb or uvw or even v[0], v[1], v[2]).

Example usage:

>> v1 = Vector(1.0, 2.0, 3.0)<br></br>
>> print v1.x     # xyz access<br></br>
1.0<br></br>
>> print v1.g     # rgb access<br></br>
2.0<br></br>
>> print v1.w     # uvw access<br></br>
3.0<br></br>
>> print v1[2]    # indexed access<br></br>
3.0<br></br>
>> v1[2] = 5.0    # assignment works same
way...<br></br>
>> print v.z<br></br>
5.0<br></br>
>> v1.b = 3.0<br></br>
>> print v1.w<br></br>
3.0<br></br>
>> v2 = Vector(2.0, 2.0, 2.0)<br></br>
>> v3 = v1 + v2   # addition<br></br>
>> print v3<br></br>
Vector(3.0, 4.0, 5.0)<br></br>
>> v3 = v1 - v2   # subtraction<br></br>
>> print v3<br></br>
Vector(-1.0, 0.0, 1.0)<br></br>
>> v3 = v1 *  v2  # multiplication<br></br>
>> print v3<br></br>
Vector(2.0, 4.0, 6.0)<br></br>
>> v3 = -v1       #
negation<br></br>
>> print v3<br></br>
Vector(-1.0, -2.0, -3.0)<br></br>
etc.<br></br><br></br>
support is also currently provided for:<br></br>
cross_product   #  vc = v1 % v2<br></br>
dot_product     # dot = v1 ^ v2<br></br>
normalize       #  vn =
~v1<br></br>
abs()          
#  v2 = abs(v1)<br></br>
nonzero test    # if v1<br></br>
magnitude       # mag =
v1.length()<br></br>

I've written a test script that:

• for each bodypart actor of the current selected Poser figure...
  ----- start timer
  ----- extract vertices into a Numeric array
  ----- call a test function
  ----- free the verts
  ----- print timing

----- start timer
----- extract the vertices as the new Vector() type ('list' of vectors)
----- call same test function, but set up to work with  vectors
----- free the verts
----- print timing

...the test loop is set up to do similar computations that the current linecast_loop() does (mostly a bunch of multiplies used in dot_product() calcs), but doesn't have pre-computed normals or regions, etc. so it just fakes some of that.

So far, it looks like my new Vecor-type is (a bit better than) 3x faster than using Numeric.  Keep in mind that the Vector-type is provided by a compiled C++ .pyd file, but the test routine itself is still written in Python.

Here's some sample (V4) output:

Hip - [ 1152  :  1279 ]<br></br>
---Test1 Numeric: 0.844000101089<br></br>
---Test1 Vector: 0.234999895096<br></br>
Abdomen - [ 2270  :  2362 ]<br></br>
---Test1 Numeric: 1.53100013733<br></br>
---Test1 Vector: 0.43700003624<br></br>
Chest - [ 3732  :  3914 ]<br></br>
---Test1 Numeric: 2.54699993134<br></br>
---Test1 Vector: 0.734999895096<br></br>
Neck - [ 676  :  754 ]<br></br>
---Test1 Numeric: 0.484000205994<br></br>
---Test1 Vector: 0.140999794006<br></br>
Head - [ 14022  :  15078 ]<br></br>
---Test1 Numeric: 9.81200003624<br></br>
---Test1 Vector: 2.81299996376<br></br>

etc.

...the format is:

actorname - [numpolys : numverts]
-- Numeric timing (seconds)
-- Vector timing (seconds)

...I'm not currently using numpolys, just simulating all vertices tested against 100 loops (100 polys).  As mentioned earlier, the timings don't correlate to real-world linecast_loop() times, because I'm not actually testing regions or even polygons - just doing a representive number of multiplies, like so:

----------- S N I P ------------

ray = Vector(0.0, 0.1, 0.0)  # a dummy vertex
normal<br></br>
pn = Vector(0.0, 0.1, 0.0)  # a dummy poly normal<br></br>
intersect = 1.0     # a dummy intersection
distance<br></br>
for pi in range(100):   # numPolys takes too long -
just do 100 loops<br></br>
 for vi in range(numVerts):<br></br>
  v = verts[vi]<br></br>
  ndota = pn ^ ray   # dot product<br></br>
  ndotv = pn ^ v    # dot product<br></br>
  point = Vector(v.x + (ray.x * intersect), v.y + (ray.y
* intersect), v.z + (ray.z * intersect))

  v0 = verts[0]    # just
grab the first 3 verts of the mesh as a stand-in triangle<br></br>
  v1 = verts[1]    # for this test
(we're only concerned with how long the computations<br></br>
  v2 = verts[2]    # take and not
about hit results)

  eu = v1 - v0  #vecsub(v1,v0)<br></br>
  ev = v2 - v0  #vecsub(v2,v0)<br></br>
  uu = eu ^ eu  #vector_dotproduct(eu,eu)<br></br>
  vv = ev ^ ev  #vector_dotproduct(ev,ev)<br></br>
  uv = eu ^ ev  #vector_dotproduct(eu,ev)<br></br>
  wx = point - v0  #vecsub(point,v0)<br></br>
  wu = wx ^ eu  #vector_dotproduct(wx,eu)<br></br>
  wv = wx ^ ev  #vector_dotproduct(wx,ev)<br></br>
  # that makes up the majority of the vector multiplies
of the code, so we'll just stop here<br></br><br></br>

----------- S N I P ------------
 

..just for completeness, here's the Numeric version of the above code:

----------- S N I P -------------

ray = [0.0, 0.1, 0.0]   # a dummy vertex
normal<br></br>
pn = [0.0, 0.1, 0.0]   # a dummy poly normal<br></br>
intersect = 1.0     # a dummy intersection
distance<br></br>
for pi in range(100):   # numPolys takes too long -
just do 100 loops<br></br>
 for vi in range(numVerts):<br></br>
  v = verts[vi]<br></br>
  ndota = pn[0] * ray[0] + pn[1] * ray[1] + pn[2] *
ray[2]  # dot product<br></br>
  ndotv = pn[0] * v[0] + pn[1] * v[1] + pn[2] *
v[2]    # dot product<br></br>
  point =[v[0] + (ray[0] * intersect),<br></br>
    v[1] + (ray[1] * intersect),<br></br>
    v[2] + (ray[2] *
intersect)]    #ray_segment(v, ray,
intersect)

  v0 = verts[0]    # just
grab the first 3 verts of the mesh as a stand-in triangle<br></br>
  v1 = verts[1]    # for this test
(we're only concerned with how long the computations<br></br>
  v2 = verts[2]    # take and not
about hit results)

  eu = [v1[0]-v0[0], v1[1]-v0[1],
v1[2]-v0[2]]           
#vecsub(v1,v0)<br></br>
  ev = [v2[0]-v0[0], v2[1]-v0[1],
v2[2]-v0[2]]           
#vecsub(v2,v0)<br></br>
  uu = eu[0] * eu[0] + eu[1] * eu[1] + eu[2] *
eu[2]      #vector_dotproduct(eu,eu)<br></br>
  vv = ev[0] * ev[0] + ev[1] * ev[1] + ev[2] *
ev[2]      #vector_dotproduct(ev,ev)<br></br>
  uv = eu[0] * ev[0] + eu[1] * ev[1] + eu[2] *
ev[2]      #vector_dotproduct(eu,ev)<br></br>
  wx = [point[0]-v0[0], point[1]-v0[1],
point[2]-v0[2]]   #vecsub(point,v0)<br></br>
  wu = wx[0] * eu[0] + wx[1] * eu[1] + wx[2] *
eu[2]      #vector_dotproduct(wx,eu)<br></br>
  wv = wx[0] * ev[0] + wx[1] * ev[1] + wx[2] *
ev[2]      #vector_dotproduct(wx,ev)<br></br>
  # that makes up the majority of the vector multiplies
of the code, so we'll just stop here<br></br>

----------- S N I P -------------