T
Terry Reedy
Ideasman said:
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
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
S
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:
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
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 said:
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
A
Alex Martelli
Ideasman said:
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
J
John Hunter
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
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
S
Sean Ross
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
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
J
Jeff Epler
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
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
S
Sean Ross
[re: dictionary record of shared normals]
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
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
I
Ideasman
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()
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()
I
Ideasman
Its indenting for me- Netscape/Mozilla
John said:
M
Miki Tebeka
J
Jiba
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
J
Javier Ruere
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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-----
Hash: SHA1
'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-----
A
Andreas Neudecker
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
might want to try out Psyco: http://psyco.sourceforge.net/ . I have
tried it recently and it speeds up execution considerably.
Regards
Andreas
B
Bengt Richter
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.
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