My script is taking 12 hours+ any suggestions?

Discussion in 'Python' started by Terry Reedy, Aug 30, 2003.

  1. Terry Reedy

    Terry Reedy Guest

    "Ideasman" <> wrote in message
    news:3f4ff9f8$0$23588$...
    > 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.


    I wonder if there is not some way to sort or classify verts so you do
    not have to do a complete nxn comparison.

    TJR
    Terry Reedy, Aug 30, 2003
    #1
    1. Advertising

  2. Terry Reedy

    Sean Ross Guest

    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" <> wrote in message
    news:3f4ff9f8$0$23588$...
    > 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 =
    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 = SHARED[j]
    break
    else:
    SHARED.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
    Sean Ross, Aug 30, 2003
    #2
    1. Advertising

  3. Ideasman wrote:

    > Its indenting for me- Netscape/Mozilla
    >
    > John Roth wrote:
    >> Your script isn't indented properly in Outlook Express,
    >> making it very difficult to read


    It's apparently using tabs and therefore does not get displayed
    as indented by many newsreaders, including Outlook Express
    and KNode. Therefore, it's nearly unreadable and it's unlikely
    you'll get any help from users of such newsreaders, including me.

    *ALWAYS* use spaces, NOT tabs, in any code you post. This
    is assuming that you care for the code you post to be read,
    as is likely the case when you're asking for help about it.


    Alex
    Alex Martelli, Aug 30, 2003
    #3
  4. Terry Reedy

    John Hunter Guest

    >>>>> "Ideasman" == Ideasman <> writes:

    Ideasman> Hi I have a made a script that process normals for a
    Ideasman> flat shaded 3D mesh's. It compares every vert with
    Ideasman> every other vert to look for verts that can share
    Ideasman> normals and It takes ages.

    Not what you asked, but are you familiar with VTK and it's python
    interface? It supports various shading algorithms, and is written in
    C++ so is quite speedy.

    http://public.kitware.com/VTK/

    JDH
    John Hunter, Aug 30, 2003
    #4
  5. Terry Reedy

    Sean Ross Guest

    Sean Ross, Aug 30, 2003
    #5
  6. Terry Reedy

    Jeff Epler Guest

    As one poster mentioned, you should convert to Python floats once, not
    many times.

    Second, you achieve some speed increase by putting everything inside a
    function. For instance, this program:
    for i in range(1000): j = sin(i)
    will run just a bit faster if you write it as
    def f():
    for i in range(1000): j = math.sin(i)
    f()
    because access to "i" and "j" will be a C array indexing operation
    instead of a Python hash table lookup. You can get a little bit more
    speed if you make 'math.sin' into a local variable, for instance with
    def f():
    sin = math.sin
    for i in range(1000): j = sin(i)
    f()

    As to the smoothing algorithm itself: I haven't decoded exactly what
    you're doing, but I once wrote a polygon smoothing algorithm modeled
    after http://www.xmission.com/~nate/smooth.html -- Here is his summary
    of his method:
    * First builds a list of all the triangles each vertex is in.
    * Then loops through each vertex in the the list averaging
    * all the facet normals of the triangles each vertex is in.
    * Finally, sets the normal index in the triangle for the vertex
    * to the generated smooth normal. If the dot product of a facet
    * normal and the facet normal associated with the first triangle
    * in the list of triangles the current vertex is in is greater
    * than the cosine of the angle parameter to the function, that
    * facet normal is not added into the average normal calculation
    * and the corresponding vertex is given the facet normal.
    * This tends to preserve hard edges. The angle to use depends
    * on the model, but 90 degrees is usually a good start.
    In my application, I had a flag available which said whether a particular
    face should participate in smooth normal generation or not, so I ignored
    that part of the algorithm.

    The step which takes some time is the grouping of the vertices. My
    models were small, so an N^2 approach in vertex count was not a problem
    even though I had to do the smoothing "online". The naive way, which
    involves comparing each vertex to all the other vertices, is N^2.

    You can get better-than-N^2 in a couple of ways. For instance, you
    could use a tree structure to partition space, just like octrees are
    used for color reduction. (this probably gives O(NlgN) behavior) You could
    just use a Python dict to place points into bins of a carefully chosen
    size so that points the other algorithms would consider identical almost
    always end up in the same bin, and points that the other algorithms
    would consider different almost always end up in different bins. I
    think this would give nearly O(N) behavior.

    Jeff
    Jeff Epler, Aug 30, 2003
    #6
  7. Terry Reedy

    Sean Ross Guest

    "Sean Ross" <> wrote in message
    news:0uW3b.4392$...
    [re: dictionary record of shared normals]
    >
    > But, this takes up more space than the jagged list version. And the

    look-up
    > is slower.


    Actually, that's wrong. Because of the way I built the dictionary

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

    is actually more like this

    SHARED = {0: <list object at 17970096>,
    1: <list object at 17970096>,
    3: <list object at 17970096>,
    2: <list object at 68520397>}

    where <list object at 17970096> is [0,1,3]
    and <list object at 68520397> is [2]

    So, we're only using space for two lists, not four (plus space for
    the dictionary, it's keys, yada, yada). As an added benefit,
    the look-up for shared normals is quick and easy as well:

    # v0.share_normal(v3)
    SHARED[0] is SHARED[3]

    where we only have to check the identity of the lists being referenced.

    Another benefit of this is, if you add a new vert to the dictionary after
    you've processed the file, if the new vert shares normals with any of the
    verts in the dictionary, you just add it to the list of the first one that
    you
    come across, and all of the other verts that this new vert would share
    normals with will also have that new verts index in their share list. Not
    bad.

    So, it looks to me like this may be the best of the three methods I've
    presented: It calls share_normal() at most as many times as the jagged
    list method (and probably far fewer times). It updates easily and the
    effects
    are distributed. And the subsequent share normal checks by identity are
    quick
    and efficient. But, hey, I could be wrong. For one thing, I don't even know
    if
    you need to do this type of thing...

    OK, then. Have fun,
    Sean
    Sean Ross, Aug 30, 2003
    #7
  8. Terry Reedy

    Ideasman Guest

    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.

    I'm not asking anyone to rewrite the script- just have a look for any
    stupid errors that might be sucking up time.








    #!/usr/bin/python
    ##############
    # AUTOSMOOTH #
    ##############
    import sys
    import os
    import string
    import math

    # Used to write floats that dont' contain letters/
    def saneFloat(float):
    #return '%(float)b' % vars() # 6 fp as house.hqx
    return '%f' % float # 10 fp



    #Open file from the command line, turn into a list and close it.
    file = open(sys.argv[-1], 'r')
    fileLineList = file.readlines()
    file.close

    # Remember the number of lines for progress indication.
    fileLen = len(fileLineList)

    # Autosmooth value. Higher will autosmooth larger angles.
    maxDiff = 1.66

    # Loop through the lines.
    lineIndex = 0
    while lineIndex < len(fileLineList):

    #Find Geom TAG..
    if str(fileLineList[lineIndex])[0:8] == 'Geometry':
    lineIndex += 1
    # break if looping beyong the file,
    if lineIndex > len(fileLineList):
    break

    # Here we remember lines that have been processed.
    # it needs to be reset for each geom object.
    listOfDoneLines = []

    # Start a new loop that checks the current vert against all the others
    newLoopindex = lineIndex
    while len(string.split(fileLineList[newLoopindex])) == 12:
    print '\n', fileLen, newLoopindex,

    #vertexnum = newLoopindex - lineIndex

    # Compare the 2 lines
    newCompareLoopindex = newLoopindex + 1 # compare the current vert to
    this new one.
    thisPassDoneLines = [] # act apon this after comparing with each vert
    thisPassDoneNormals = []
    while len(string.split(fileLineList[newCompareLoopindex])) == 12:

    # Speed up the process by using 2 if's, splitting the string only if
    it has not been evaluated already.
    if newCompareLoopindex not in listOfDoneLines:
    comp1 = string.split(fileLineList[newLoopindex])
    comp2 = string.split(fileLineList[newCompareLoopindex])

    if [comp1[0], comp1[1], comp1[2]] == [comp2[0], comp2[1], comp2[2]]:

    if newLoopindex not in listOfDoneLines: # Only needs to be added once
    listOfDoneLines.append(newLoopindex)

    if newLoopindex not in thisPassDoneLines: # Only needs to be added
    once
    thisPassDoneLines.append(newLoopindex)
    thisPassDoneNormals.append([eval(comp1[8]), eval(comp1[9]),
    eval(comp1[10])])

    listOfDoneLines.append(newCompareLoopindex)
    thisPassDoneLines.append(newCompareLoopindex)
    thisPassDoneNormals.append([eval(comp2[8]), eval(comp2[9]),
    eval(comp2[10])])
    print '#',

    newCompareLoopindex += 1



    if len(thisPassDoneLines) > 1: # Ok We have some verts to smooth.


    # This loops through all verts and assigns each a new normal.
    for tempLineIndex in thisPassDoneLines:

    tempSplitLine = string.split(fileLineList[tempLineIndex])

    # We add to these for every vert that is similar, then devide them
    to get an average.
    NormX = 0
    NormY = 0
    NormZ = 0

    # A list of vert line indicies that we will create to store verts
    that have normals close to ours.
    thisVertFrendsCount = 0

    # This compares the current vert with all the others, if they are
    close then add to vertFrends.
    for tNorm in thisPassDoneNormals: # tNorm is just used for one of
    the normals in the thisPassDoneNormals

    if abs(eval(tempSplitLine[8]) - tNorm[0]) +
    abs(eval(tempSplitLine[9]) - tNorm[1]) + abs(eval(tempSplitLine[10])
    -tNorm[2])< maxDiff:

    #maxDiff
    NormX += tNorm[0]
    NormY += tNorm[1]
    NormZ += tNorm[2]

    thisVertFrendsCount += 1


    #Now devide the normals by the number of frends.
    NormX /= thisVertFrendsCount
    NormY /= thisVertFrendsCount
    NormZ /= thisVertFrendsCount

    # make unit length vector.
    d = NormX*NormX + NormY*NormY + NormZ*NormZ
    if d>0:
    d = math.sqrt(d)
    NormX/=d; NormY/=d; NormZ/=d


    # Write the normal to the current line
    tempSplitLine[8] = str(saneFloat(NormX))
    tempSplitLine[9] = str(saneFloat(NormY))
    tempSplitLine[10] = str(saneFloat(NormZ))

    fileLineList[tempLineIndex] = string.join(tempSplitLine) + '\n'



    newLoopindex += 1

    lineIndex += 1


    # Writing to file
    # file to write
    file = open(sys.argv[-1], 'w')
    file.writelines(fileLineList)
    file.close()
    Ideasman, Aug 30, 2003
    #8
  9. Terry Reedy

    Ideasman Guest

    Its indenting for me- Netscape/Mozilla


    John Roth wrote:
    > Your script isn't indented properly in Outlook Express,
    > making it very difficult to read
    >
    > John Roth
    >
    > "Ideasman" <> wrote in message
    > news:3f4ff9f8$0$23588$...
    >
    >>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.
    >>
    >>I'm not asking anyone to rewrite the script- just have a look for any
    >>stupid errors that might be sucking up time.
    >>
    >>
    >>
    >>
    >>
    >>
    >>
    >>
    >>#!/usr/bin/python
    >>##############
    >># AUTOSMOOTH #
    >>##############
    >>import sys
    >>import os
    >>import string
    >>import math
    >>
    >># Used to write floats that dont' contain letters/
    >>def saneFloat(float):
    >>#return '%(float)b' % vars() # 6 fp as house.hqx
    >>return '%f' % float # 10 fp
    >>
    >>
    >>
    >>#Open file from the command line, turn into a list and close it.
    >>file = open(sys.argv[-1], 'r')
    >>fileLineList = file.readlines()
    >>file.close
    >>
    >># Remember the number of lines for progress indication.
    >>fileLen = len(fileLineList)
    >>
    >># Autosmooth value. Higher will autosmooth larger angles.
    >>maxDiff = 1.66
    >>
    >># Loop through the lines.
    >>lineIndex = 0
    >>while lineIndex < len(fileLineList):
    >>
    >>#Find Geom TAG..
    >>if str(fileLineList[lineIndex])[0:8] == 'Geometry':
    >>lineIndex += 1
    >># break if looping beyong the file,
    >>if lineIndex > len(fileLineList):
    >>break
    >>
    >># Here we remember lines that have been processed.
    >># it needs to be reset for each geom object.
    >>listOfDoneLines = []
    >>
    >># Start a new loop that checks the current vert against all the others
    >>newLoopindex = lineIndex
    >>while len(string.split(fileLineList[newLoopindex])) == 12:
    >>print '\n', fileLen, newLoopindex,
    >>
    >>#vertexnum = newLoopindex - lineIndex
    >>
    >># Compare the 2 lines
    >>newCompareLoopindex = newLoopindex + 1 # compare the current vert to
    >>this new one.
    >>thisPassDoneLines = [] # act apon this after comparing with each vert
    >>thisPassDoneNormals = []
    >>while len(string.split(fileLineList[newCompareLoopindex])) == 12:
    >>
    >># Speed up the process by using 2 if's, splitting the string only if
    >>it has not been evaluated already.
    >>if newCompareLoopindex not in listOfDoneLines:
    >>comp1 = string.split(fileLineList[newLoopindex])
    >>comp2 = string.split(fileLineList[newCompareLoopindex])
    >>
    >>if [comp1[0], comp1[1], comp1[2]] == [comp2[0], comp2[1], comp2[2]]:
    >>
    >>if newLoopindex not in listOfDoneLines: # Only needs to be added once
    >>listOfDoneLines.append(newLoopindex)
    >>
    >>if newLoopindex not in thisPassDoneLines: # Only needs to be added
    >>once
    >>thisPassDoneLines.append(newLoopindex)
    >>thisPassDoneNormals.append([eval(comp1[8]), eval(comp1[9]),
    >>eval(comp1[10])])
    >>
    >>listOfDoneLines.append(newCompareLoopindex)
    >>thisPassDoneLines.append(newCompareLoopindex)
    >>thisPassDoneNormals.append([eval(comp2[8]), eval(comp2[9]),
    >>eval(comp2[10])])
    >>print '#',
    >>
    >>newCompareLoopindex += 1
    >>
    >>
    >>
    >>if len(thisPassDoneLines) > 1: # Ok We have some verts to smooth.
    >>
    >>
    >># This loops through all verts and assigns each a new normal.
    >>for tempLineIndex in thisPassDoneLines:
    >>
    >>tempSplitLine = string.split(fileLineList[tempLineIndex])
    >>
    >># We add to these for every vert that is similar, then devide them
    >>to get an average.
    >>NormX = 0
    >>NormY = 0
    >>NormZ = 0
    >>
    >># A list of vert line indicies that we will create to store verts
    >>that have normals close to ours.
    >>thisVertFrendsCount = 0
    >>
    >># This compares the current vert with all the others, if they are
    >>close then add to vertFrends.
    >>for tNorm in thisPassDoneNormals: # tNorm is just used for one of
    >>the normals in the thisPassDoneNormals
    >>
    >>if abs(eval(tempSplitLine[8]) - tNorm[0]) +
    >>abs(eval(tempSplitLine[9]) - tNorm[1]) + abs(eval(tempSplitLine[10])
    >>-tNorm[2])< maxDiff:
    >>
    >>#maxDiff
    >>NormX += tNorm[0]
    >>NormY += tNorm[1]
    >>NormZ += tNorm[2]
    >>
    >>thisVertFrendsCount += 1
    >>
    >>
    >>#Now devide the normals by the number of frends.
    >>NormX /= thisVertFrendsCount
    >>NormY /= thisVertFrendsCount
    >>NormZ /= thisVertFrendsCount
    >>
    >># make unit length vector.
    >>d = NormX*NormX + NormY*NormY + NormZ*NormZ
    >>if d>0:
    >>d = math.sqrt(d)
    >>NormX/=d; NormY/=d; NormZ/=d
    >>
    >>
    >># Write the normal to the current line
    >>tempSplitLine[8] = str(saneFloat(NormX))
    >>tempSplitLine[9] = str(saneFloat(NormY))
    >>tempSplitLine[10] = str(saneFloat(NormZ))
    >>
    >>fileLineList[tempLineIndex] = string.join(tempSplitLine) + '\n'
    >>
    >>
    >>
    >>newLoopindex += 1
    >>
    >>lineIndex += 1
    >>
    >>
    >># Writing to file
    >># file to write
    >>file = open(sys.argv[-1], 'w')
    >>file.writelines(fileLineList)
    >>file.close()
    >>

    >
    >
    >
    Ideasman, Aug 30, 2003
    #9
  10. Terry Reedy

    Miki Tebeka Guest

    Hello,

    > 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.
    >
    > I'm not asking anyone to rewrite the script- just have a look for any
    > stupid errors that might be sucking up time.

    If you're running on x86 you might want to try psyco (http://psyco.sourceforge.net).

    Miki
    Miki Tebeka, Aug 31, 2003
    #10
  11. Terry Reedy

    Jiba Guest

    On Sat, 30 Aug 2003 13:08:24 -0400
    Ideasman <> wrote:

    > 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.


    I'm doing similar 3D location (X, Y, Z) comparisons... You can make it MUCH MUCH faster if you use dicts insteed of comparison : use the (X, Y, Z) tuple as key and a list of point sharing the normal as value.

    Obviously this will work ONLY if the point have exactely the same normal.

    If not, the solution is to use a rounded normal as key. E.g. use 'round(x * 100.0) / 100.0' instead of x for an (approximative) 0.01 precision, and proceed similarly with y and z.

    Jiba
    Jiba, Sep 1, 2003
    #11
  12. Terry Reedy

    Javier Ruere Guest

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Jiba wrote:

    > If not, the solution is to use a rounded normal as key. E.g. use

    'round(x * 100.0) / 100.0' instead of x for an (approximative) 0.01
    precision, and proceed similarly with y and z.

    round can round to a given precition using the second optional
    argument so this two expressions would be equivalent:

    round(x*100)/100.0 == round(x, 2)

    Javier

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.2.2 (MingW32)
    Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

    iD8DBQE/Uuto8XQC840MeeoRAuLiAKCBBAAO4Q071hvfpa/m7NOi2Vq7AgCeOkLU
    07hZL8F2ZzF2lyyZDRLHcZE=
    =upl+
    -----END PGP SIGNATURE-----
    Javier Ruere, Sep 1, 2003
    #12
  13. Hi, even if you find ways to speed up the code through editing, you
    might want to try out Psyco: http://psyco.sourceforge.net/ . I have
    tried it recently and it speeds up execution considerably.


    Regards


    Andreas


    Ideasman wrote:
    > 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.
    >
    > I'm not asking anyone to rewrite the script- just have a look for any
    > stupid errors that might be sucking up time.
    >
    >
    >
    >
    >
    >
    >
    >
    > #!/usr/bin/python
    > ##############
    > # AUTOSMOOTH #
    > ##############
    > import sys
    > import os
    > import string
    > import math
    >
    > # Used to write floats that dont' contain letters/
    > def saneFloat(float):
    > #return '%(float)b' % vars() # 6 fp as house.hqx
    > return '%f' % float # 10 fp
    >
    >
    >
    > #Open file from the command line, turn into a list and close it.
    > file = open(sys.argv[-1], 'r')
    > fileLineList = file.readlines()
    > file.close
    >
    > # Remember the number of lines for progress indication.
    > fileLen = len(fileLineList)
    >
    > # Autosmooth value. Higher will autosmooth larger angles.
    > maxDiff = 1.66
    >
    > # Loop through the lines.
    > lineIndex = 0
    > while lineIndex < len(fileLineList):
    >
    > #Find Geom TAG..
    > if str(fileLineList[lineIndex])[0:8] == 'Geometry':
    > lineIndex += 1
    > # break if looping beyong the file,
    > if lineIndex > len(fileLineList):
    > break
    >
    > # Here we remember lines that have been processed.
    > # it needs to be reset for each geom object.
    > listOfDoneLines = []
    >
    > # Start a new loop that checks the current vert against all the
    > others
    > newLoopindex = lineIndex
    > while len(string.split(fileLineList[newLoopindex])) == 12:
    > print '\n', fileLen, newLoopindex,
    >
    > #vertexnum = newLoopindex - lineIndex
    >
    > # Compare the 2 lines
    > newCompareLoopindex = newLoopindex + 1 # compare the current
    > vert to this new one.
    > thisPassDoneLines = [] # act apon this after comparing with
    > each vert
    > thisPassDoneNormals = []
    > while len(string.split(fileLineList[newCompareLoopindex]))
    > == 12:
    >
    > # Speed up the process by using 2 if's, splitting the
    > string only if it has not been evaluated already.
    > if newCompareLoopindex not in listOfDoneLines:
    > comp1 = string.split(fileLineList[newLoopindex])
    > comp2 = string.split(fileLineList[newCompareLoopindex])
    >
    > if [comp1[0], comp1[1], comp1[2]] == [comp2[0],
    > comp2[1], comp2[2]]:
    >
    > if newLoopindex not in listOfDoneLines: # Only
    > needs to be added once
    > listOfDoneLines.append(newLoopindex)
    >
    > if newLoopindex not in thisPassDoneLines: # Only
    > needs to be added once
    > thisPassDoneLines.append(newLoopindex)
    > thisPassDoneNormals.append([eval(comp1[8]),
    > eval(comp1[9]), eval(comp1[10])])
    >
    > listOfDoneLines.append(newCompareLoopindex)
    > thisPassDoneLines.append(newCompareLoopindex)
    > thisPassDoneNormals.append([eval(comp2[8]),
    > eval(comp2[9]), eval(comp2[10])])
    > print '#',
    >
    > newCompareLoopindex += 1
    >
    >
    >
    > if len(thisPassDoneLines) > 1: # Ok We have some verts to
    > smooth.
    >
    >
    > # This loops through all verts and assigns each a new
    > normal.
    > for tempLineIndex in thisPassDoneLines:
    >
    > tempSplitLine =
    > string.split(fileLineList[tempLineIndex])
    >
    > # We add to these for every vert that is similar,
    > then devide them to get an average.
    > NormX = 0
    > NormY = 0
    > NormZ = 0
    >
    > # A list of vert line indicies that we will create
    > to store verts that have normals close to ours.
    > thisVertFrendsCount = 0
    >
    > # This compares the current vert with all the
    > others, if they are close then add to vertFrends.
    > for tNorm in thisPassDoneNormals: # tNorm is just
    > used for one of the normals in the thisPassDoneNormals
    >
    > if abs(eval(tempSplitLine[8]) - tNorm[0]) +
    > abs(eval(tempSplitLine[9]) - tNorm[1]) + abs(eval(tempSplitLine[10])
    > -tNorm[2])< maxDiff:
    >
    > #maxDiff
    > NormX += tNorm[0]
    > NormY += tNorm[1]
    > NormZ += tNorm[2]
    >
    > thisVertFrendsCount += 1
    >
    >
    > #Now devide the normals by the number of frends.
    > NormX /= thisVertFrendsCount
    > NormY /= thisVertFrendsCount
    > NormZ /= thisVertFrendsCount
    >
    > # make unit length vector.
    > d = NormX*NormX + NormY*NormY + NormZ*NormZ
    > if d>0:
    > d = math.sqrt(d)
    > NormX/=d; NormY/=d; NormZ/=d
    >
    >
    > # Write the normal to the current line
    > tempSplitLine[8] = str(saneFloat(NormX))
    > tempSplitLine[9] = str(saneFloat(NormY))
    > tempSplitLine[10] =
    > str(saneFloat(NormZ))
    >
    > fileLineList[tempLineIndex] =
    > string.join(tempSplitLine) + '\n'
    >
    >
    >
    > newLoopindex += 1
    >
    > lineIndex += 1
    >
    >
    > # Writing to file
    > # file to write
    > file = open(sys.argv[-1], 'w')
    > file.writelines(fileLineList)
    > file.close()
    >
    Andreas Neudecker, Sep 1, 2003
    #13
  14. On Sat, 30 Aug 2003 13:08:24 -0400, Ideasman <> wrote:

    >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.

    n*(n-1)/2 can be big. How big is it in your case?
    Others have suggested using a dict to avoid that kind of search. Take the advice,
    unless the whole problem is bogus somehow, in which case find that out first.

    >
    >I'm not asking anyone to rewrite the script- just have a look for any
    >stupid errors that might be sucking up time.
    >

    Some thoughts:

    Check your memory usage. If your data set is huge, you could be paging and killing all
    semblance of performance.

    Upgrade to 2.3, so you can benefit from its speedups and neato features.

    Perhaps go back to whoever produced the source data and see if this apparent editing
    of a text file is really the best way to accomplish your end goal.

    For more detailed help with the file, post enough of an example and explanation to
    spec it exactly. There may be ways to avoid stuff you are doing.

    Further thoughts, if you really have to do what you are doing:

    Try timing it, so you know where the time is going. (See time, profile, hotshot modules).

    Don't use eval to convert strings to numeric values (use int(s) or float(s))
    Don't re-evaluate expressions (especially complex ones) even twice in a hot loop.
    Don't evaluate constant (with respect to current loop, not necessarily globally constant)
    expressions within a loop (hoist them out to outer loops, and break them into
    subexpressions that can be hoisted out as far as possible.
    Don't create and store redundant information.
    Don't index through a list when you can iterate through it. Use enumerate if you need an index in parallel.
    Don't walk through a sequence to find something if you can use a dict to look it up directly.
    Don't leave stuff like str(saneFloat(NormX)) in code you expect to go fast.
    I.e., clean out desperate hacks that you don't really know what they are doing,
    and fix any problems that reemerge properly ;-)
    Don't use builtin names like float, str, int, etc. for your own variable or parameter names.
    It will bite you eventually.
    If your input text is well formatted, perhaps sorting chunks as text can accomplish some useful grouping.
    Consider decorate-sort to group things according to some computed feature value.
    Or use a dict with list values as suggested by others.
    Look at zip and/or list comprehensions for creating/manipulating sequences.

    HTH

    Regards,
    Bengt Richter
    Bengt Richter, Sep 1, 2003
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Malik Asif Joyia
    Replies:
    2
    Views:
    1,071
    =?Utf-8?B?ZGFuaWVs?=
    Aug 12, 2005
  2. Rahmi Acar
    Replies:
    0
    Views:
    549
    Rahmi Acar
    Jul 17, 2003
  3. Jim Cain
    Replies:
    1
    Views:
    191
    Yukihiro Matsumoto
    Jul 18, 2003
  4. Gancy
    Replies:
    5
    Views:
    94
    Anno Siegel
    Jan 29, 2005
  5. rutherf
    Replies:
    2
    Views:
    409
    rutherf
    Oct 28, 2006
Loading...

Share This Page