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

Question

我在python中有一个简单的raytracer。渲染一张200x200的图像需要4分钟，这对我来说绝对是太长了。我想要改善这种情况。

一些要点:我为每个像素拍摄多条光线(以提供抗锯齿功能)，每个像素总共有16条光线。200x200x16是640000条光线的总和。必须测试每条光线对场景中多个球体对象的影响。Ray也是一个相当微不足道的对象

class Ray(object):
    def __init__(self, origin, direction):
        self.origin = numpy.array(origin)
        self.direction = numpy.array(direction)

Sphere稍微复杂一些，它包含了hit/nohit的逻辑：

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语言的情况下性能更好吗？

Answer 1

查看您的代码，您的主要问题似乎是您的代码行被调用了2560000次。无论你在代码中做什么工作，这都会花费大量的时间。但是，使用numpy，您可以将大量工作聚合到少量的numpy调用中。

要做的第一件事是将你的光线组合成一个大的数组。不使用具有1x3矢量的光线对象作为原点和方向，而是使用包含命中检测所需的所有光线的Nx3数组。hit函数的顶部将如下所示：

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

来继续处理通过判别测试的值。通过这种方式，您可以轻松获得数量级的性能改进。

Answer 2

1)光线跟踪很有趣，但如果你关心的是性能，那就丢弃python并切换到C语言。除非你是某种超级专家，否则不要使用C++，只使用C语言。

2)在具有多个(20个或更多)对象的场景中，最大的成功是使用空间索引来减少交叉测试的数量。流行的选择是kD-trees，OctTrees，AABB。

3)如果你是认真的，请查看ompf.org -它就是这方面的资源。

4)不要用python去ompf询问优化--那里的大多数人每秒可以通过包含10万个三角形的室内场景发射100万到200万条射线……每核。

我喜欢Python和光线跟踪，但从来不会考虑把它们放在一起。在这种情况下，正确的优化是切换语言。

Answer 3

使用这样的代码，您可能会受益于将self.radius * self.radius作为self.radius2和1 / self.radius作为self.one_over_radius之类的常用子表达式。python解释器的开销可能会影响这些微不足道的改进。