FAQ
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()

Search Discussions

  • John Roth at Aug 30, 2003 at 1:58 am
    Your script isn't indented properly in Outlook Express,
    making it very difficult to read

    John Roth

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

    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 at Aug 30, 2003 at 5:57 pm
    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" <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.

    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()
  • Alex Martelli at Aug 30, 2003 at 7:46 am

    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
  • Terry Reedy at Aug 30, 2003 at 5:04 am
    "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.
    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
  • Sean Ross at Aug 30, 2003 at 5:20 am
    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
  • Sean Ross at Aug 30, 2003 at 3:21 pm
    "Sean Ross" <sross at connectmail.carleton.ca> wrote in message
    news:0uW3b.4392$_F1.665478 at news20.bellglobal.com...
    [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
  • Michael Peuser at Aug 30, 2003 at 7:12 am
    "Ideasman" <cpbarton at pacific.net.au> schrieb im Newsbeitrag
    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.

    I'm not asking anyone to rewrite the script- just have a look for any
    stupid errors that might be sucking up time.
    As has been mentioned the source is not indented - there is no safer way to
    make Python programs unusable ;-)

    Looking through it you have *a lot* of evals in loops. Remove that! You
    should convert your data immediately to a binary internal format while
    reading from the file (first loop).

    Kindly
    Michael P
  • John Hunter at Aug 30, 2003 at 1:07 pm
    "Ideasman" == Ideasman <cpbarton at pacific.net.au> 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
  • Sean Ross at Aug 30, 2003 at 1:47 pm
    For anyone who is interested, the OP's code can be viewed (with indentation
    intact) here:
    http://mail.python.org/pipermail/python-list/2003-August/181365.html

    (I know, because that was the only place I could view it - no indentation
    here as well)

    HTH
    Sean
  • Jeff Epler at Aug 30, 2003 at 2:02 pm
    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
  • Mel Wilson at Aug 31, 2003 at 4:03 am
    In article <3f4ff9f8$0$23588$5a62ac22 at freenews.iinet.net.au>,
    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.
    I don't know for sure, but a few things look suspicious.

    - Keeping a list of line numbers of lines that have been
    looked at. When you do this, an expression like
    if newCompareLoopindex not in listOfDoneLines:
    means a sequential search of the list every time. A set of
    processed lines, or a dictionary keyed by the line numbers
    of processed lines might be faster. Another alternative, if
    you can spare the memory, would be a list
    isProcessed = [0]*fileLen
    where you set
    isProcessed[lineIndex] = 1
    as the line is processed, and change the test mentioned
    above to simply
    if isProcessed[newCompareLoopindex]:

    - keeping all the input data in string form and splitting
    the line each time it's used must be taking time. (The
    alternative has dangers too, if unpacking all the lines
    exceeds your memory, then you could trade 12 hours
    unpacking data lines for 12 hours on the swap file)

    - the line
    if [comp1[0], comp1[1], comp1[2]] == [comp2[0], comp2[1], comp2[2]]:
    results in building two brand new lists, comparing their
    contents, then throwing them away. It might be better to
    code
    if comp1[0] == comp2[0] and comp1[1] == comp2[1] and comp1[2] == comp2[2]:

    - many str calls to convert things that are already strings
    (as far as I can tell), although this will probably be a
    very small saving.

    - as somebody else said, we don't know what kind of code is
    being `eval`ed, maybe your problem just takes 12 hours to
    solve.

    Good Luck. Mel.
  • Miki Tebeka at Aug 31, 2003 at 7:16 am
    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
  • Jiba at Sep 1, 2003 at 2:09 am

    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
  • Javier Ruere at Sep 1, 2003 at 6:47 am

    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
  • Andreas Neudecker at Sep 1, 2003 at 12:26 pm
    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()
  • Bengt Richter at Sep 1, 2003 at 8:29 pm

    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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedAug 30, '03 at 1:58a
activeSep 1, '03 at 8:29p
posts17
users15
websitepython.org

People

Translate

site design / logo © 2022 Grokbase