My script is taking 12 hours+ any suggestions?

[Sean Ross]

Hi.

First, it might be helpful to see a sample of the contents of the file your
pulling your information from. What do the lines look like? What information
do they contain? Does each line contain the same type of information? What
are the parts of the information contained in each line, and how do they
relate to the problem you're trying to solve? How many 'verts' (vertices?)
are there?

Describe the algorithm your applying in english. What are the steps you're
taking in order to solve this problem? They are not apparent from this code.
Can you not use some functions to break this mass of code into manageable
chunks?

To be honest, I have no idea what your code is trying to do. You say it does
this:

"Ideasman" <cpbarton at pacific.net.au> wrote in message
news:3f4ff9f8$0$23588$5a62ac22 at freenews.iinet.net.au...
> Hi I have a made a script that process normals for a flat shaded 3D
mesh's.
> It compares every vert with every other vert to look for verts that can
> share normals and It takes ages.

OK. I'm going to assume that each line in the file represents the
information relevant to one 'vert' (whatever that is). So, I would suggest,
going through the file, one line at a time, constructing a list of vert
objects, which hold this information. Something like:

fd = file(filename)
verts = [Vert(*line.split()) for line in fd]
fd.close()

where Vert() is a constructor for the class Vert:

class Vert(object):
    def __init__(self, what, ever, information,
                          will , be, split, from, the, line):
        self.what = what
        ...

    def share_normals(self, other):
        "returns True when self and other can share normals"
        ...
    ...


So, now you have a list of Verts. If you don't have the 'normals' for these
Verts from the file, and have to calculate them,
add a 'normalize(self)' method to the Vert class, and call that inside
__init__() at the appropriate time.

So, now we have a list of normalized Verts. And we want to compare every
Vert to each other to look for Verts that can share normals.
OK. Suppose

verts = [v0, v1, v2, v3]   # where v0, v1, v2, v3 are all Vert instances.

We want to see if v0 can share normals with v1, v2, and/or v3;
and if v1 can share normals with v0, v2, and/or v3; and so on.

If I check v0.share_normals(v1), do I need to check v1.share_normals(v0)?
Probably not. But then again, I haven't a clue what I'm talking about :)

Assuming I'm correct, and we don't need to check v1.share_normals(v0), then
we should probably keep a record. I'll assume that a vert can share a normal
with itself, so we don't need to keep a record for that.

I suggest making a jagged array. Call it 'SHARED'.  Build it as follows:


SHARED = [[vert.share_normal(other) for other in verts[i+1:]]
                          for i, vert in enumerate(verts[:-1])]

And, when we're done, 'SHARED' is a jagged array filled with zeroes and
ones, something like this:


        0    1   2    3
0      -   [[1,  0,  1],
1      -      - [ 0,  1],
2      -      -    -  [0]]
3      -      -    -     -

# verts indices are listed on the outside of the table
SHARED == [ [1, 0, 1], [0, 1], [0] ]

then we make a function like:

def is_shared(index1, index2):
    if index1 == index2: return True # a vert shares a normal with itself
    # adjust for jagged list indexing
    if index1 > index2:
        index1, index2 = index2, index1
    index2 -= index1 + 1
    return SHARED[index1][index2]

so we can use it to ask, later, if v0, and v3 share normals by using

'is_shared(0,3)' or 'is_shared(3,0)'    # SHARED[0][2] == True

and then we can do whatever action is appropriate using verts[0] and
verts[3].

By storing this information, we avoid having to re-calculate whether v0 and
v3 share normals every time we need to know that. And, by storing the
information in a jagged array, we save some space.



# NOTE: if v0.share_normal(v1) and v1.share_normal(v2),
# then v0.share_normal(v2) must also be True.
# so we could make SHARED a dictionary instead

SHARED = {0: [0,1,3],  # v0 shares normals with itself, v1 and v3
                      1: [0,1,3],
                      2: [2]
                      3: [0,1,3]}

Building this dictionary may save some share_normal() calls:

SHARED = {}
for i, vert in enumerate(verts):
    SHARED[i] = [i]
    for j, other in enumerate(verts):
        if j == i: continue
        if vert.share_normal(other):
            if j < i:
                # the earlier vert will have accumulated all
                # of this verts share partners, so just use those
                SHARED[i] = SHARED[j]
                break
           else:
                SHARED[i].append(j)


Then, to see whether v0.share_normal(v3), we can just ask

    3 in SHARED[0]  # and vice versa

But, this takes up more space than the jagged list version. And the look-up
is slower.

What might be better is a straight partition, like this:

SHARED = [[0,1,3], [2]]  # I'll leave how to get this up to you...

This takes up less space than each of the previous versions.
How do we use it to tell whether v0.share_normal(v3) ?

A new version of is_shared(index1, index2) would have to
find the tuple containing index1, then see if index2 is also
in that tuple. This look-up is the slowest of all!


And, after all of that, I still can't say whether this has been of use for
you, because
I have very little understanding as to what you meant for your code to be
doing.

Hopefully, this was somewhat near the mark. Also, be aware that none of the
code
above has been tested.

Good luck with what you're doing,
Sean