logo标签列表

提高光线追踪命中函数的性能

pythonperformance
14
我有一个简单的Python光线追踪器。渲染一张200x200的图片需要4分钟，这绝对太慢了。我想改进这种情况。
一些要点：我为每个像素发射多条光线（以提供抗锯齿效果），每个像素总共有16条光线。200x200x16总共有640000条光线。每条光线必须在场景中的多个球体对象上进行碰撞测试。光线也是一个相当琐碎的对象。
class Ray(object):
    def __init__(self, origin, direction):
        self.origin = numpy.array(origin)
        self.direction = numpy.array(direction)

Sphere（球体）稍微复杂一些，它包含了撞击/未撞击的逻辑：

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语言吗？

3
非常清晰易懂的展示。作为一个问题，我不熟悉Python，所以想问一下：numpy.dot是否会调用C实现？如果不是，也许通过手动进行点积计算可以提高速度。 - Phrogz
是的，numpy是用C实现的。这就是为什么我觉得重新用C实现hit函数没有太多可获得的东西。 - Stefano Borini
你的方向向量是否为单位向量？在__init__函数中，你能否将它们转换成为单位向量？如果可以的话，它们的点积计算会变得更简单。 - underrun
@Synap：是的，尽管我没有强制执行，但它们被外部设置为单位向量。 - Stefano Borini
1
我还记得当用C程序在4分钟内渲染200x200时，那是相当不错的！ - Ben Jackson
@Ben：我想知道一个写得好的C程序（没有任何技巧）的实际性能会是多少。 - Stefano Borini
5个回答
9
看着你的代码，似乎主要问题是你有很多行代码被调用了2560000次。无论你在这些代码中做什么工作，都会花费很长时间。然而，使用numpy，你可以将大量工作聚合成少量的numpy调用。
首先要做的是将光线组合成大数组。不要使用具有1x3向量的原点和方向的射线对象，而是使用具有所有所需光线的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]
...

只使用通过判别式测试的值，可以轻松获得数量级的性能提升。

Numba和numpy是一个很好的组合，因为Numba可以优化循环和整个函数调用。 - Marcelo Lacerda
7

1) 光线追踪很有趣，但如果你关心性能，请放弃Python并切换到C语言。除非你是某种超级专家，否则不要选择C++，只用C。

2) 在具有多个（20个或更多）对象的场景中，使用空间索引来减少交点测试的数量是一个重大的优势。流行的选项包括kD树、OctTree和AABB。

3) 如果你认真对待这个问题，请查看ompf.org - 这是资源的来源。

4) 不要在ompf上用python询问优化问题 - 大多数人可以通过每个核心在100,000个三角形的室内场景中射出1百万至2百万条光线。

我喜欢Python和光线追踪，但从不考虑将它们结合在一起。在这种情况下，正确的优化方法是切换语言。

+1 我完全同意这个观点。Python 对于原型设计可能很不错，但是一旦您证明了算法的可行性并且关心性能，就该使用 C/C++（或编译成适当二进制文件的语言；不要自欺欺人地认为 VM/GC 语言可以胜任）。然后可以将光线追踪器包装成 Python 组件，以在更高级别的系统中使用。 - timday
@timday - 大约在1995年，我用C ++制作了一个射线跟踪OLE组件（当时它们被称为什么），并从Visual Basic应用程序中进行相机移动。 120x90像素的图像有很多帧每秒。我考虑过在我的库周围包装PyGame :-) 没时间... - phkahler
1
我认为C++现在很适合编写高性能的光线追踪代码。事实上，我就是靠这个谋生的。你只需要避免使用C++中那些糟糕而慢的部分，比如异常和STL。 - Crashworks
我的练习的重点是使用Python进行操作，确切地说我想在Python层面上尝试调优、C接口和并行化，这些都是我很少做的事情。 - Stefano Borini
@Crashworks - 避免使用具有简单重载操作符的向量类。我听说可以通过模板来避免额外开销，但我还没有尝试过 - 我只是回到了C语言。 - phkahler
1

你最好尽可能使用查找表和预计算值。

由于你对我的评论做出的回应表明你的光线方向向量是单位向量，在你列出的关键部分中，你可以立即进行至少一个优化。任何向量点积本身的长度平方都是1，因此单位向量点积本身将始终为1。

另外，在球体的__init__函数中预先计算半径的平方。

然后你就有：

temp = ray.origin - self.center
a = 1 # or skip this and optimize out later
b = 2.0 * numpy.dot(temp, ray.direction)
c = numpy.dot(temp, temp) - self.radius_squared
disc = b * b - 4.0 * c

temp dot temp 将会给你等价于 sum( map( lambda component: component*component, temp ) ) 的结果... 不过我不确定哪个更快。

做了一些测试——numpy.dot()比sum(map())快得多。 - underrun
1

如果您使用这样的代码，您可以从记忆常见子表达式中受益，例如将self.radius * self.radius记忆为self.radius2，将1 / self.radius记忆为self.one_over_radius。然而，Python解释器的开销可能会支配这些微不足道的改进。

我尝试了。好主意，但它并没有改变很多。我意识到在使用self.radius作为numpy数组时犯了一个错误，而不是一个简单的浮点数。再次，这并没有带来可衡量的变化。我正在考虑改变设计并尝试减少调用次数，但我怀疑在性能方面可以获得很大的提升，而在代码清晰度方面则会失去很多。我想我很快就要转向并行计算了。 - Stefano Borini
非常正确。C 语言实现将比 Python 虚拟机获取操作码更快地计算这些内容。虽然它们是有效的优化，但在性能良好的 C 程序中将显示出小但可测量的改进。 - phkahler
1
一个小的优化是：由于a和b * b始终为正，因此如果(c > 0 && b < min(a, c))，则disc < 0.0为真。在这种情况下，您可以避免计算b * b - 4.0 * a * c。根据您所做的配置文件，我猜这最多会节省7％的运行时间。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接