Улучшение производительности функции трассировки лучей
У меня есть простой raytracer в python. рендеринг изображения 200x200 занимает 4 минуты, что, безусловно, слишком много для моего вкуса. Я хочу улучшить ситуацию.
Некоторые моменты: я снимаю несколько лучей на каждый пиксель (для обеспечения сглаживания) для общей суммы 16 лучей на пиксель. 200x200x16 - это общее количество 640000 лучей. Каждый луч должен быть проверен на воздействие на несколько объектов Sphere в сцене. Ray также является довольно тривиальным объектом
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?
Ответы
Ответ 1
Глядя на ваш код, похоже, что ваша главная проблема в том, что у вас есть строки кода, которые вызываются 2560000 раз. Это займет много времени, независимо от того, какую работу вы выполняете в этом коде. Однако, используя NumPy, вы можете объединить большую часть этой работы в небольшое количество NUPY-вызовов.
Первое, что нужно сделать, это объединить ваши лучи вместе в большие массивы. Вместо использования объекта 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]
...
продолжить только со значениями, которые проходят дискриминантный тест. Таким образом, вы можете легко повысить производительность на несколько порядков.
Ответ 2
1) Трассировка лучей - это весело, но если вы вообще не заботитесь о производительности, дамп-питон и переключитесь на C. Не С++, если вы не являетесь супер-экспертом, просто C.
2) Большая победа в сценах с несколькими (20 или более) объектами заключается в использовании пространственного индекса для уменьшения числа тестов пересечения. Популярные варианты - kD-деревья, OctTrees, AABB.
3) Если вы серьезно, посмотрите ompf.org - это ресурс для этого.
4) Не ходите на ompf, когда python спрашивает об оптимизации - большинство людей могут снимать от 1 миллиона до 2 миллионов лучей в секунду через внутреннюю сцену с 100 тысячами треугольников... На ядро.
Я люблю Python и трассировку лучей, но никогда не буду рассматривать их вместе. В этом случае правильная оптимизация заключается в переключении языков.
Ответ 3
С таким кодом вы можете воспользоваться мемонимированием общих подвыражений, таких как self.radius * self.radius как self.radius2 и 1 / self.radius как self.one_over_radius. Накладные расходы интерпретатора python могут доминировать в таких незначительных улучшениях.
Ответ 4
Одна незначительная оптимизация: a и b * b всегда положительны, поэтому disc < 0.0 истинно, если (c > 0 && b < min(a, c)). В этом случае вы можете избежать вычисления b * b - 4.0 * a * c. Учитывая профиль, который вы сделали, это, скорее всего, побьет 7% времени выполнения удара, я думаю.
Ответ 5
Лучше всего будет использовать таблицы поиска и предварительно рассчитанные значения как можно больше.
Как ваш ответ на мой комментарий указывает, что ваши векторы направления лучей являются единичными векторами, в критическом разделе, который вы указали, вы можете сделать хотя бы одну оптимизацию сразу с места в карьер. Любая векторная точка сама по себе является квадратом длины, поэтому сама единичная векторная точка всегда будет равна 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 ) )... я не уверен, что быстрее, хотя.
