Yes, line-box intersection checks.  Unfortunately, I don't have the code to do that (i'd have to look it up and/or think about it more), but maybe someone else will pipe up with that.

Just to clarify something... expanding the regions for the polygon tests would help in a lot of cases (those vertices/polygons that fall right on the border would end up in both regions, instead of just ones side or the other).  And it could even catch 90+% of the other cases if the overlap is large enough and if the mesh polygons are fairly consistent in size/shape.

As for expanding the region, hell, I'd just pass some fudge value into the routine when it's sorting the vertices into regions. Then your test becomes:

if( vertX <= (boxMaxX + fudge) and vertX >= (boxMinX - fudge) )

...etc.  No need to do scaling before-hand.  So you pass a fudge factor into the routine that's categorizing the vertices of the source mesh (the ones that make up the polygons that you're going to test against) and don't pass any fudge factor (or 0.0) in when you're categorizing the target mesh verts.

erm... actually, that won't work as it's currently coded.  Currently, the source vertices (used to categorize polygons into regions) can only live in one region.  You'd need to change the code to let them exist in multiple regions (like the polygons can).

*"You'd need to change the code to let them exist in multiple regions (like the polygons can)."

*That would explain why successfully enlarging the boxes gave very strange results.  Hmm.  I'll look at the vertex placement code.

What about the RAM issues?  Did you note any leaking with your test?  I get massive leaks testing any meshes of higher vertex counts than the two ball props I mentioned before....

I didn't notice any, but I wasn't actively monitoring it either.  With that scene loaded, after running the sript (as pictured), I just checked and had 385,000K available.  I did a Scene->New to clear it all out and ended up with 408,xxxxK.  I then quit the program and ended up with 513,xxxxK.  I still have PSP and C4D running in the background, along with a couple browsers and a text-editor.

What method are you using to monitor leaks?

Tests made since implementing your suggestions and changes have been slower (presumably due to having increased the number of polygons per region), but the memory dives haven't been as dramatic.  Comparing two identical objects of about 2000 vertices each took over 30 minutes (in part because it was creating boxes), but I only lost 100 MB or memory in the process.  The same objects tested with an earlier veersion of the script required that I quit Poser because I ran out of RAM.

I fixed the box re-scaling and it groups the polygons more appropriately now, after making sure verts can be in more than one region.  This does not improve the final results at all, however.  It slows the processing a bit and returns exactly the same hits and misses as before.  :(

Which reminds me.  You alluded to still getting "false" hits, with the test from which you took the screen grab.  What would be causing those?  

Attached: an update.

What could cause them is what I mentioned a few posts back... the code stops looking once it gets a hit, but there may be a closer (correct) hit with other polygons.  The false hit polygon may or may not be facing the right direction.

See my post on the previous page where I posted the above image for additional notes on the false hits.

Quote - Ah, I'm afraid I don't follow you, regarding the mixboxes. 

...I forgot to respond to this... you had said that when you first enabled my find_regions() changes, that you got a bunch of un-grouped verts.  I was suggesting that you'd have to enable the 'mixboxes' flag in the code to fix that - to use a box large enough to encompass both meshes.

Okay.  I get it.  The normals check was something planned anyway, to help screen against such problems.  My question about that was, if the normals check rejects a polygon, we can skip the polygon boundary check and move on to the next polygon, correct?

I'm wondering about the polygons region assignments.  As an alternative to edge-checking, what about looping through the polygons in the region, then checking their vertices against the list of vertices in polygons to grab the un-grouped polygons on the region boundary?  That could expand the region by one "band" of polygons.  But that still wouldn't catch an intersecting edge, would it?

Next idea.  Find the centers of polygons and run a "closeness" check on them to place them in the region.

Both are the kind of kludgy workaround approaches that I favor to avoid something intimidating.  :-P

Mixboxes: Okay.  I added the <= condition to the code, and it began to catch everything.

As best as I can determine what you mean by the first suggestion... no .  I think you're final sentance on that is correct.

The second idea may have some merrit, but here's another idea...  I'm not sure if you're using it yet, but you have a routine in there to get edge lengths... I suspect that you could just enlarge the (polygon containing) regions by the "longest polygon edge length" on all sides and that should handle the worse-case scenerio.

So the region boxes for target vertices are size X and the region boxes used to enclose source polygons are size X + "longest polygon edge length" (in every direction).  That might give you many more polygons per region to check, but at least it's more deterministic.

"longest polygon edge length": longest from among all polygons, or screened by polys already in the group, or what?  One whopping huge poly could throw things off....  But if it avoids edge collision checks, I like it.  :)

Yes, I ended up babbling badly about that first idea.  Alas.  Must.  Sleep.  Soon.

In other words, when you loop through every polygon in the mesh getting edge lengths, keep track of the longest one found.  Then inside polyregs() where you call increase_box(), use that value to grow those regions.

The longest edge overall.  Okay.  Thank you.  Increase_box doesn't take a distance value any longer, BTW.  I'll have to express the argument relative to the existing dimensions of the region box.  Hmm.

cross-posted... yes - all polys.  This would be  bit 'sloppy' since as you say, one huge polygon could through things off.

A further refinement of that (fair amount of additional/redundant code) would be to use that value to create the regions, then go grab the polygons based on that, then look for the maximum edge length of the polys you rounded up with that lasso and use THAT to re-create the region and re-populate it.  That way, only the region(s) where that huge one got picked up would still be that big.  The other regions would be big enough to catch the next biggest polygon.  I'm not sure it's worth the trouble to do that though.

ahh.. yeah, I'd probably re-write that to just take a hard number.  then just add/subract that number from each dimension as appropriate (no need to do the translate/scale/translate).

*"ahh.. yeah, I'd probably re-write that to just take a hard number.  then just add/subract that number from each dimension as appropriate (no need to do the translate/scale/translate)."

*That does make more sense.  I wanted to fix what was broken, but I'll probably change it.  The box enlargement is called elsewhere, where it might make a bit more sense, as well....

But my reflex does tend to be to come up with a rather more comlicated approach than I need to.  I very much need to take Ockham's advice.

Hehe.  It's all good.  As an acedemic excersize, it worked out well - you learned something new .

Those "translate to center, rotate/scale, then translate back" operations are usually handled by concatinated matrix multiplications in 3D software.... you can build one matrix that does all those operations with a single matrix multiplication.  It's interesing stuff, but more complicated than needed for this application.

I just learned something else about PoserPython.  Numeric can be used for 3-level arrays (or deeper), but it can't be used to create arrays in which the sizes of the elements differ.  I'm not sure of the proper terms for any of this.  Basically, Numeric can't organize polygon data in which the number of entries (vertices, edges) will differ from polygon to polygon.  Which makes sense, since the Numeric module implements its arrays as matrices in some cases.

And this presumably explains why Poser's geometry API is so weird, requiring the sets list and the polygons list to be cross referenced with one another.  Rather than building geometry handling for PoserPython from scratch, it was constructed on top of Numeric and its limitations.  Or so I assume.  

This means Numeric can't be used to generate the lists for this script, at any rate.  Trying to see how it may be useful in the actual processing....

There's still misses in a few cases... I know of one possible reason (non-planar polygons) which we might have to fix by breaking things down into triangles afterall (which I think we'll need for the weighted average code anyway).  But in the meantime, I'm puzzling over exactly what polyplanes() is supposed to be doing.  I see that the value is being used in the ray intersection code, but I'm not clear exactly what value is needed there (a point on the plane?  a line to the center of the plane?)  I'll have to go look that up unless you can clarify it.  The code is currently finding the center point (average of the vertices) and then multiplying each axis of that point by each axis of the normal for that polygon, but that's not an operation I'm familiar with.

Anyway, I've made various other changes and tried to mark them all with a 'Spanki' in the comments.

Polyplanes could be completely wrong, for all I know.  I have had to cobble together that first part of the line-plane intersection code (before the edge bounds check) from hints and fragments gathered from svdl's posts on page 1, a bit of Ockham's NoPoke (now reduced to the "center method"), and a method outline offered on a Game Maker forum.  The math to calculate the plane of the polygon is gathered from the GM forum, but I have seen it repeated elsewhere online.  I plug that plane value into svdl's outlined code, assuming I've assembled his outlined code effectively.  As you may have noted, my record for correctly assembling such things isn't so great, thus far.  :-P

I was looking into Numeric both in hopes of reducing the memory issues and of speeding things up a bit.  All of this is quite slow, on my system, and I don't see reason to expect greater speed as the code becomes more complex to accomodate more situations.  I tried using Numeric for the various coordinate and normals lists used during the main linecasting process, but that really did nothing to help.  I think pulling Numeric in at that point may actually serve to complicate matters.  Hmm.

WorldNormals?  Are you testing using your worldspace additions, or have you re-tooled the script to use world coordinates instead of local coordinates?  I guess I should take a look for myself, eh?  :)

BTW, I have a LinePointDistance.py from a PyGame site.  I don't want to post a copy here without permission, but that might help with the broken code of the same name which you've added....

Google is your friend.

http://arainyday.se/projects/python/LinePointDistance/LinePointDistance.py

Do you have a link to the GM forum post you refer to?  I'm looking around to see if I can figure out what's up on that.

BTW, as I mentioned above, we might need to end up storing a triangulated representation of the mesh, so while that would double the polygons, it would also make them uniformly 3 vertices each, so that might lend itself to the Numeric thing if that helps.

*"Do you have a link to the GM forum post you refer to?"

*Yourself is the resident math whiz.  About halfway down the thread, I think.

http://forums.gamemaker.nl/index.php?act=ST&f=29&t=209834

*"it would also make them uniformly 3 vertices each, so that might lend itself to the Numeric thing if that helps."

*That would enable the use of Numeric, presumably, but not until after the switch to triangles.

Ah, what can I do to help, here?  I defer to your greater knowledge and skill.  :)  I don't want to muck things up....

Thanks.  My Python skills are at a neophyte level, so you could take a look at the changes I made and make sure I didn't screw anything up :).

I don't note anything incorrect, offhand.  A couple of points of formatting that don't really affect the outcome, in any case.  As you stated before, it's Python-ease.  :) 

Thanks.. and yeah, I'm more used to all tabs, but I've tried to stick with spaces since that's what you're doing... in C, indenting is just clarification - the code doesn't rely on it :).

Ah.  Sorry about the tabs-spaces.  They hate me in the Blender Python forums for that.  :)  I need to change the default settings I use in IDLE.

Ok, I think I understand that now and you appear to have it correct.  I think the remaining hitch is non-planar polygons (or at least the potential for them).  They will throw off the poly face normals which probably also affects the ray->plane intersection code.

Fixing that means switching to a triangular representation of the mesh we're testing against.  Ramifications are:

1. for all intents and purposes, a doubling of the polyons (the majority of Poser mesh polygons are quads).  So this means...

2. Larger storage requirements ( ultimately edges, pnorms, pplanes and pregs - but some others while building those up ).

3. A doubling of polys to test against means a longer time to test for hits (until a hit is found, so maybe slightly less than double the time, on average).

4. The current region material setting will have to be re-thought, or abandoned (no big deal).

5. It moves us a step closer to implementing the vertex weighting.

...currently, we're still getting a few misses in some cases, but as far as I can tell the regions are being set up well enough and the rays being cast are now going the right directions.  It's possible that there's still some line-intersection problem in the check_bounds() code, but the only other thing I can think of at this point is warped polygons throwing off one or more of the calculations.

If you want to look into triangulating the polygons, I'll spend some more time looking into the line intersection issue in check_bounds().

I don't think his site is online right now, but Campbell Barton (of the Blender Python community) has a mesh decimation script which is concerned with triangulation.  One point on which his script seems to spent a lot of time is the question of triangulating so as to avoid "narrow" triangles.  A quad could be split along either of two axes, and in his case, at least, splitting in the way that avoids long/thin tris is apparently important.  I wonder whether that would be the case here, as well.

Triangulating will potentially double the number of polys to loop through, but it will also enable the (presumed) speed gains of using Numeric and it will reduce the number of edges in most of the in-bounds checks.  Hopefully these points will offset the increase in sheer number somewhat....

With triangulation in mind, I'll go ahead and prepare a version of the script to implement Numeric.  I have assumed we'll just need to to run a "virtual" mesh triangulation before running the lists.  Why will more prep-lists be needed?   

I was just referring to some of the lists currently passed into the above routines (and are then deleted within the source_lists() and/or target_lists() routines).   hadn't looked to see which secific ones need adjusting.

As for the thin triangles, for out purposes, it may not matter at all.  I think I'd start by just grabbing the first 3 indices, then the second 3, etc.

The triangulation method I've seen involves connecting the start point in the polygon to all of the others which aren't already attached to the start point.  So one loop covers quads and n-gons.  It would seem that we'd get a lot of the "skinny" polys that way, but you're right - it doesn't seem like that would impact us much, if at all.

I think a list to correlate pverts to the broken down polys would be the place to start.  Break them down, create new indices, keep track of how the new and old indices match up.  Then use the list of new indices when listing regions and edges.

Hmm.  Probably more complicated than I think, as usual.  :-P

The attached has triangulation and use of Numeric for the edge lists.  Tests are returning 100% matches with the ball props.  Neato.

The triangulation has broken the multi-grouped polygon tracking and I haven't fixed that yet.  I did fix the group coloring assignments.

I commented out your print tests in the edge bounds check function and I added a worldspace flag option to the new normals list calculations.  Use of WorldVertices requires that the props be aligned in the Poser workspace when testing, and Cage is silly enough not to want to have to do that.  So I figured it was best to leave options open....

Cool.  I have some other projects that need attention, but let me transfer some interim things over to your new file and I'll post that in a bit.

I hadn't tested the new file yet, but earlier today I narrowed in on 'why' we're still getting misses in some cases and I'm not sure how to handle it yet.  As far as I can tell, it's due to a matter of precision in some of the floating point values.  In the particular case I'm looking at, there's a line with both vertices at the following Y position...

<br></br>

...note the difference in precision (at least that's what's being printed out by Python).  So in this case, the intersection test point went 'beyond' the polygon/plane/edge by 0.000000000000035046  <-- that tiny amount.

Now, in cases where the intersection point is somewhere inside the polygon, that tiny amount wouldn't make a difference, but because it lies exactly on one of the edges being checked, it matters - it's effectively the same as being 10,000.000 (pick any number) too far.

I'm still trying to figure out the best way to handle this case in a general way.

Does it introduce too much imprecision to just "clamp" the values at a certain number of places?

I'm not sure yet, but that's worth a try.  Do you have some python clamp code handy?

No, actually, and now that I think about it, this looks like the floating point precision problem which nruddock pointed out to me when I was struggling with euler/quaternion conversions.  

http://docs.python.org/tut/node16.html

I think he spoke of NANs and other troubling things in connection with the matter.  Hmm.  I'll see if I can dig up that old thread....

If you read the above link, they point out that simply rounding off the value won't fix things....  :(

Yeah, the problem is actually more complicated than I originally thought... I needed to do this in C a while back and have that code arund here somewhere.

I found the code, but unfortunately didn't jot down the url where I found the answer.  Anyway, just for the curious, here's the C code:

<pre style="border-right:#000000 1px solid;padding-right:2mm;border-top:#000000 1px solid;padding-left:2mm;padding-bottom:2mm;margin:2mm;border-left:#000000 1px solid;padding-top:2mm;border-bottom:#000000 1px solid;background-color:#aefe50;">

Real sign(Real n)
{
        if( n > 0.0 )
                return 1.0;
        if( n < 0.0 )
                return -1.0;
        return 0.0;
}

Real TrimDecimal(Real num, Real digits)
{ 

        Real n; 

        n = num * Pow(10.0, digits); 

        n = sign(n) * Abs(Floor(n + 0.5)); 

        return n / Pow(10.0, digits); 
}

Python 2.4+ offers the Decimal module to resolve these problems.  Doesn't help with PoserPython....

So will the C code help, given what was discussed at the python.org link?

Uhm.. I dunno - I hadn't read that yet :).  It just occured to me that I had the code from another program, so I went looking for it.  Without reading that page yet... my initial thought is that we would need to keep enough precision to work at Poser's tiny scale (grrrr), but based on what I saw in that one case above, we'd still be able to keep 12 digits after the decimal, so that should be fine.

I'm trying to get your most recent file (above) updated with some things I did earlier today so I can get that to you before you get to far adding anything else.  I may not have time to look into this other issue tonight.

*"I'm trying to get your most recent file (above) updated with some things I did earlier today so I can get that to you before you get to far adding anything else.  I may not have time to look into this other issue tonight."

*Okay.  Thank you for all the work you've done on this.  I don't think I would have isolated most of the problems you've found, and it would have taken me weeks of trial-and-error to accomplish what you've added in a couple of days - assuming I even got that far.  :-P

I reduced the epsilon value and put the vertex test back in, but maybe we should just add a global to enable/disable some of these things :).

Note that I also changed the increase_box() code back to taking a hard value (instead of a scalar) and implemented the 'longest edge length' as the size to grow the poly regions by.  I aslo moved the region box display up into the polyregs() routine, so it would show the overlapping regions.  Of particular note here is that due to the longest-edge value being used, this will create some pretty big overlap on simple props with large polys (like a sphere), but it should be more reasonable on something like a human head mesh.

I sprinkled various other changes throughout, and/or updated a few comments.

Excellent!  :)  Thank you.  I at least hope I'm learning a lot by seeing how someone else approaches these things.  Trying to, at least.  :-P

I just realized that Numeric provides a function to return the highest value in the array.  We can probably get the longest edge now just by using Numeric.argmax, without having to iterate over the lengths in longestedge.

I'm not sure whether Numeric might help with the float comparisons.  There could be benefits to trying to expand the use of the module.

Cool.  I really hadn't looked into Numeric or other modules, so there could be things like that in there that would be useful.

BTW, I just ran this new script (with vertex intersection test disabled) and compared it to the earlier (non-triangulated) one...

New script found all 62 matches
Old script found 12 out of 62

...the two mesh in question happen to be a ball-type mesh and a subdivided version of the same mesh, so all the vertices of the lo-res mesh still line up exactly with the hi-res version... It looks like the triangulation code helped!

(I'm still getting a failure on another test-case that I described earlier though)

Yes, I've been getting 162/162 going from a ball prop to a Wings 3d smoothed ball prop which doesn't line up completely.  The vert positions don't really match in any case.  Works nicely.  I had assumed the greater success was due to your changes from yesterday, however, rather than the triangles.  :)

Now... can it be improved further?  Hmm.

Does the method you added for bounding box enlargement translate the boxes when it enlarges them?  I switched methods because the old one had that problem when the box wasn't at 0,0,0 when it was scaled.  I guess I need to test that.  I assume you know how to do it simply while avoiding the problems I encountered.  :)

Actually, the worse the meshes line up (vertex/edge-wise) the more likely they are to get valid matches .  The current problem seems to be narrowed down to edges - whereas yesterday's version still had problems with verts.  I'll need to take a fresh look at the edge problem when I get a chance.

The bounding box enlargement simply adds/subracts a passed in value from the min/max box values (it's the code you had in there earlier).  You only have to worry about translating it too/from the center if you are using scaling (multiplication).

*"You only have to worry about translating it too/from the center if you are using scaling (multiplication)."

Uh, really?  I was doing something wrong, then.  I started testing with multiplication after I began to to end with results which included translation using the original enlargement method.  Hmm.  I get terribly confused....  :-P

Hmmm... I'm not sure what was going wrong when you tried, but I moved the region-box-drawing up into the code that extends the boxes(for creating the polygon regions), so you can see how they overlap now.

Anway, I ran the current script on that head again...

last time: 300 (more or less) misses out of 1200
this time: 14 misses

...with a lot fewer false hits.  So the good news is that we're getting closer - the bad news is that there are still some false hits and still some missed hits :).

I'll look at this more if I get some time later tonight.

You know, come to think of it, I saw translation at some point too.. but I don;t recall what I did at the time to cause that (I think the flipping of the increase to -increase was happening at the wrong time when that happened).

*"You know, come to think of it, I saw translation at some point too.. but I don;t recall what I did at the time to cause that (I think the flipping of the increase to -increase was happening at the wrong time when that happened)."

*Just as long as it isn't translating anything now.

Those are much better results with the head.  :woot:

If edges are now the problem, do you need that point line distance code?  I think we'll need something like that for edges once we get into the weighting. 

I'm going to see how much benefit can be had from extending the use of Numeric.  What else can I work in without confusing anything?  You seem to have the Master Plan.  :)