优化光线追踪命中函数的性能
我在用Python写一个简单的光线追踪程序。渲染一张200x200的图片要花4分钟，这对我来说实在太久了。我想改善这个情况。
有几点需要说明：我每个像素发射多条光线（为了减少锯齿），每个像素总共发射16条光线。200x200x16总共就是640000条光线。每条光线都要检测它是否与场景中的多个球体相交。光线的定义其实比较简单。
class Ray(object):
def __init__(self, origin, direction):
self.origin = numpy.array(origin)
self.direction = numpy.array(direction)
而球体的定义稍微复杂一点，它包含了判断是否相交的逻辑：
class Sphere(object):
def __init__(self, center, radius, color):
self.center = numpy.array(center)
self.radius = numpy.array(radius)
self.color = color
@profile
def hit(self, ray):
temp = ray.origin - self.center
a = numpy.dot(ray.direction, ray.direction)
b = 2.0 * numpy.dot(temp, ray.direction)
c = numpy.dot(temp, temp) - self.radius * self.radius
disc = b * b - 4.0 * a * c
if (disc < 0.0):
return None
else:
e = math.sqrt(disc)
denom = 2.0 * a
t = (-b - e) / denom
if (t > 1.0e-7):
normal = (temp + t * ray.direction) / self.radius
hit_point = ray.origin + t * ray.direction
return ShadeRecord.ShadeRecord(normal=normal,
hit_point=hit_point,
parameter=t,
color=self.color)
t = (-b + e) / denom
if (t > 1.0e-7):
normal = (temp + t * ray.direction) / self.radius hit_point = ray.origin + t * ray.direction
return ShadeRecord.ShadeRecord(normal=normal,
hit_point=hit_point,
parameter=t,
color=self.color)
return None
现在，我做了一些性能分析，发现处理时间最长的部分在hit()这个函数里。
ncalls tottime percall cumtime percall filename:lineno(function)
2560000 118.831 0.000 152.701 0.000 raytrace/objects/Sphere.py:12(hit)
1960020 42.989 0.000 42.989 0.000 {numpy.core.multiarray.array}
1 34.566 34.566 285.829 285.829 raytrace/World.py:25(render)
7680000 33.796 0.000 33.796 0.000 {numpy.core._dotblas.dot}
2560000 11.124 0.000 163.825 0.000 raytrace/World.py:63(f)
640000 10.132 0.000 189.411 0.000 raytrace/World.py:62(hit_bare_bones_object)
640023 6.556 0.000 170.388 0.000 {map}
这并不让我感到意外，我想尽量减少这个时间。我进行了逐行分析，结果是：
Line # Hits Time Per Hit % Time Line Contents
==============================================================
12 @profile
13 def hit(self, ray):
14 2560000 27956358 10.9 19.2 temp = ray.origin - self.center
15 2560000 17944912 7.0 12.3 a = numpy.dot(ray.direction, ray.direction)
16 2560000 24132737 9.4 16.5 b = 2.0 * numpy.dot(temp, ray.direction)
17 2560000 37113811 14.5 25.4 c = numpy.dot(temp, temp) - self.radius * self.radius
18 2560000 20808930 8.1 14.3 disc = b * b - 4.0 * a * c
19
20 2560000 10963318 4.3 7.5 if (disc < 0.0):
21 2539908 5403624 2.1 3.7 return None
22 else:
23 20092 75076 3.7 0.1 e = math.sqrt(disc)
24 20092 104950 5.2 0.1 denom = 2.0 * a
25 20092 115956 5.8 0.1 t = (-b - e) / denom
26 20092 83382 4.2 0.1 if (t > 1.0e-7):
27 20092 525272 26.1 0.4 normal = (temp + t * ray.direction) / self.radius
28 20092 333879 16.6 0.2 hit_point = ray.origin + t * ray.direction
29 20092 299494 14.9 0.2 return ShadeRecord.ShadeRecord(normal=normal, hit_point=hit_point, parameter=t, color=self.color)
所以，看起来大部分时间都花在了这段代码上：
temp = ray.origin - self.center
a = numpy.dot(ray.direction, ray.direction)
b = 2.0 * numpy.dot(temp, ray.direction)
c = numpy.dot(temp, temp) - self.radius * self.radius
disc = b * b - 4.0 * a * c
在这里，我并没有看到很多可以优化的地方。你们有没有什么建议，能让我在不使用C语言的情况下提高这段代码的性能？
5 个回答
像这样的代码，你可以通过记住一些常用的计算结果来提高效率，比如把 self.radius * self.radius 记作 self.radius2，还有 1 / self.radius 记作 self.one_over_radius。不过，Python解释器的开销可能会让这些小改进的效果不太明显。
1) 光线追踪很有趣，但如果你在乎性能的话，还是放弃Python，换成C语言。C++就不推荐了，除非你是那种超级专家，直接用C就好。
2) 如果场景里有很多物体（比如20个以上），使用空间索引可以减少碰撞检测的次数，这样能提高效率。常见的选择有kD树、八叉树和AABB。
3) 如果你认真想了解这方面的知识，可以去ompf.org网站看看，那是个很好的资源。
4) 不要在ompf上用Python问优化的问题——那里的大多数人每秒能在一个有10万个三角形的室内场景中射出100万到200万条光线……每个核心都是这样。
我喜欢Python和光线追踪，但绝对不会把它们放在一起。在这种情况下，正确的做法是换一种编程语言。
看你的代码，主要问题是你有一些代码行被调用了2560000次。无论你在这些代码里做什么，这样都会耗费很多时间。不过，使用numpy，你可以把很多工作合并成少量的numpy调用。
首先，你需要把你的光线（ray）合并成大的数组。与其使用一个包含1x3向量的Ray对象来表示起点和方向，不如使用Nx3的数组，这样可以包含你所有需要的光线用于碰撞检测。你的碰撞检测函数的顶部最终会像这样：
temp = rays.origin - self.center
b = 2.0 * numpy.sum(temp * rays.direction,1)
c = numpy.sum(numpy.square(temp), 1) - self.radius * self.radius
disc = b * b - 4.0 * c
接下来，你可以使用
possible_hits = numpy.where(disc >= 0.0)
a = a[possible_hits]
disc = disc[possible_hits]
...
来继续处理那些通过判别式测试的值。这样做可以轻松获得数量级的性能提升。