
Hi,
So, I'm working on a radiosity renderer, and it's basically finished. I'm now trying to optimize it. Currently, by far the most computationally expensive operation is visibility testing, where pixels are counted by the type of patch that was drawn on them. Here's my current code, which I'm fairly sure can be optimized:
line 1) pixel_data = np.cast['int16'](255.0*glReadPixels(0,0,patch_view.width,patch_view.height,GL_RGB,GL_FLOAT)).reshape((-1,3)) line 2) pixel_data[:,1] *= 255 line 3) pixel_data[:,0] *= (255*255) line 4) pixel_data = np.sum(pixel_data,1) line 5) for pixel in pixel_data: line 6) if pixel != 0: line 7) try: self.visibility[poly1num][pixel-1] line 8) except: self.visibility[poly1num][pixel-1] = 0 line 9) self.visibility[poly1num][pixel-1] += 1
The basic idea: Convert unique an array of RGB triplets into and array of unique numbers. The triplet [0,0,1] maps to 1 and the triplet [255,255,255] maps to 16581375. The triplet [0,0,0], mapping to 0, is always discarded. The resulting array of integers in the range [1,16581375] are the (index+1)'s of a list, self.visibility[poly1num]. For each integer "i" in the array, the value in self.visibility[poly1num][i-1] must be incremented by 1.
By line: line 1: convert the read pixels from the range [0.0,1.0] (as floats) to the range [0,255] (as integers). Change the shape from (width,height,3) to (width*height,3). lines 2, 3, and 4: the pixels are an index to patches. The green channel counts 255 times as much. The red, 255 times as much as the green. This way, 255^3 possible pixel types can be had. Sum the red, green, and blue channels to arrive at a single number, which is the patch index in the range [0,255^3]. line 5: for each index in the data line 6: I'm reserving the index [0,0,0] for no patch, so if the index is that color, no patch was drawn. lines 7, 8, and 9: increment self.visibility[poly1num][pixel-1] by 1.
I have a feeling that this code is likely the bottleneck. It's taking about an hour to execute this process 8720 times when width and height are both 512. I have a feeling my code can be greatly improved in many ways--if not all over, certainly in lines 5 through 9.
Help?
Thanks, Ian

Hi again,
I've condensed the problem down a lot, because I both presented it in an overcomplicated way, and did not explain it particularly well.
Condensed problem: a = np.zeros(num_patches) b = np.array(...) #created, and is size 512^512 = 262,144 #Each value in "b" is an index into "a". #For each occurrence of a given index in "b", increment the corresponding value in "a" by +1. #How should I do that?
Simpler, and more importantly, better explained problem. Help?
Thanks again, Ian

On Thu, Jul 22, 2010 at 9:59 PM, Ian Mallett geometrian@gmail.com wrote:
Hi again,
I've condensed the problem down a lot, because I both presented it in an overcomplicated way, and did not explain it particularly well.
Condensed problem: a = np.zeros(num_patches) b = np.array(...) #created, and is size 512^512 = 262,144 #Each value in "b" is an index into "a". #For each occurrence of a given index in "b", increment the corresponding value in "a" by +1. #How should I do that?
Simpler, and more importantly, better explained problem. Help?
Is that what you want, or do you just want to know how many unique indices there are? As to encoding the RGB, unless there is a existing program your best bet is probably to use a dot product, i.e., if pix_data is (n,3) uint8, then
pix_index = np.dot(pix_data, array([1, 2**8, 2**16], dtype=uint32)
then check out the documentation for np.unique.
Chuck

On Thu, Jul 22, 2010 at 10:05 PM, Charles R Harris < charlesr.harris@gmail.com> wrote:
Is that what you want, or do you just want to know how many unique indices there are? As to encoding the RGB, unless there is a existing program your best bet is probably to use a dot product, i.e., if pix_data is (n,3) uint8, then
pix_index = np.dot(pix_data, array([1, 2**8, 2**16], dtype=uint32)
then check out the documentation for np.unique.
I like the dot product idea for the indices.
To the second, actually, I need to increment the number of times the index is there. For example, if b=[1,5,6,6,6,9], then a[6-1] would have to be incremented by +3 = +1+1+1. I tried simply a[b-1]+=1, but it seems to only increment values once, even if there are more than one occurrence of the index in "b". What to do about that?
Thanks, Ian

Ian Mallett wrote:
To the second, actually, I need to increment the number of times the index is there. For example, if b=[1,5,6,6,6,9], then a[6-1] would have to be incremented by +3 = +1+1+1. I tried simply a[b-1]+=1, but it seems to only increment values once, even if there are more than one occurrence of the index in "b". What to do about that?
Is this what you mean?
numpy.bincount( [1,5,6,6,6,9] )
array([0, 1, 0, 0, 0, 1, 3, 0, 0, 1])
HTH,
Jon

On Fri, Jul 23, 2010 at 12:13 AM, Jon Wright wright@esrf.fr wrote:
Ian Mallett wrote:
To the second, actually, I need to increment the number of times the index is there. For example, if b=[1,5,6,6,6,9], then a[6-1] would have to be incremented by +3 = +1+1+1. I tried simply a[b-1]+=1, but it seems to only increment values once, even if there are more than one occurrence of the index in "b". What to do about that?
Is this what you mean?
numpy.bincount( [1,5,6,6,6,9] )
array([0, 1, 0, 0, 0, 1, 3, 0, 0, 1])
Well, I've implemented it thusly:
pixel_data = np.cast['int16'](255.0*glReadPixels(0,0,patch_view.width,patch_view.height,GL_RGB,GL_FLOAT)).reshape((-1,3)) pixel_data = np.dot(pixel_data,np.array([65025,255,1])) count = np.bincount(pixel_data)[1:] self.visibility[poly1num][0:count.shape[0]] += count
And it works! Thanks everyone!
Ian
participants (3)
-
Charles R Harris
-
Ian Mallett
-
Jon Wright