Улучшение производительности функции трассировки лучей

Question

У меня есть простой raytracer в 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?

Answer 1

Глядя на ваш код, похоже, что ваша основная проблема в том, что у вас есть строки кода, которые вызываются 2560000 раз. Это займет много времени, независимо от того, какую работу вы выполняете в этом коде. Однако, используя numpy , вы можете объединить большую часть этой работы в небольшое количество numpy вызовов.

Первое, что нужно сделать, это объединить ваши лучи в большие массивы. Вместо использования объекта Ray с векторами 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]
...

, чтобы продолжить только со значениями, которые проходят дискриминантный тест. Таким образом, вы можете легко повысить производительность на несколько порядков.

Answer 2

1) Трассировка лучей - это весело, но если вам нужна производительность, сбросьте python и переключитесь на C. Не C ++, если вы не какой-то супер эксперт, просто C.

2) Большой выигрышв сценах с несколькими (20 и более) объектами стоит использовать пространственный индекс, чтобы уменьшить количество тестов пересечений.Популярные варианты: kD-деревья, OctTrees, AABB.

3) Если вы серьезно, проверьте ompf.org - это ресурс для этого.

4) Не ходитеобъединиться с Python, спрашивая об оптимизации - большинство людей могут снимать от 1 до 2 миллионов лучей в секунду через внутреннюю сцену со 100 тысячами треугольников ... на ядро.Никогда не думай собирать их вместе.В этом случае правильной оптимизацией является переключение языков.

Answer 3

Лучше всего будет максимально использовать таблицы поиска и предварительно рассчитанные значения.

Поскольку ваш ответ на мой комментарий показывает, что ваши векторы направления лучей являются единичными векторами, в указанном вами критическом разделе вы можете сделать хотя бы одну оптимизацию сразу. Любая векторная точка имеет квадрат длины, поэтому сама единичная векторная точка всегда будет равна 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

темп точка темп даст вам эквивалент sum( map( lambda component: component*component, temp ) ) ... я не уверен, что быстрее, хотя.

Answer 4

Одна небольшая оптимизация: a и b * b всегда положительны, поэтому disc < 0.0 имеет значение true, если (c > 0 && b < min(a, c)). В этом случае вы можете избежать расчета b * b - 4.0 * a * c. Я полагаю, что учитывая профиль, который вы сделали, это, скорее всего, сбрит 7% времени выполнения удара.

Answer 5

С таким кодом вы можете извлечь выгоду из запоминания общих подвыражений, таких как self.radius * self.radius как self.radius2 и 1 / self.radius как self.one_over_radius. Затраты на интерпретатор python могут доминировать над такими тривиальными улучшениями.