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

У меня есть простой raytracer в python. рендеринг изображения 200×200 занимает 4 минуты, что, безусловно, слишком много для моего вкуса. Я хочу улучшить ситуацию.

Некоторые моменты: я снимаю несколько лучей на каждый пиксель (для обеспечения сглаживания) для общей суммы 16 лучей на пиксель. 200x200x16 – это общее количество 640000 лучей. Каждый луч должен быть проверен на воздействие на несколько объектов Sphere в сцене. Рэй также является довольно тривиальным объектом

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

Сфера немного сложнее и несет логику для 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?

5 Solutions collect form web for “Улучшение производительности функции трассировки лучей”

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

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

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

4) Не ходите на ompf с python, спрашивая об оптимизации – большинство людей могут снимать от 1 миллиона до 2 миллионов лучей в секунду через внутреннюю сцену с 100 тысячами треугольников … На ядро.

Я обожаю Python и трассировку лучей, но никогда не буду рассматривать их вместе. В этом случае правильная оптимизация заключается в переключении языков.

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

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

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

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

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

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

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