Mejora del rendimiento de la función de acierto raytracing

Question

Tengo un raytracer simple en python. renderizar una imagen de 200x200 lleva 4 minutos, lo que definitivamente es demasiado para mi gusto. Quiero mejorar la situación.

Algunos puntos: disparo múltiples rayos por cada píxel (para proporcionar antialiasing) para un gran total de 16 rayos por píxel. 200x200x16 es un gran total de 640000 rayos. Cada rayo debe probarse para determinar su impacto en múltiples objetos Esfera en la escena. Ray es también un objeto bastante trivial

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

Esfera es un poco más complejo, y lleva a la lógica de golpe/SIN RESULTADO:

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  

Ahora, me encontré con algunos perfiles, y parece que el tratamiento más largo el tiempo es en la función de golpe()

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} 

esto no me sorprende, y quiero reducir este valor tanto como sea posible. Paso a la línea de perfilado, y el resultado es

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) 

Por lo tanto, parece que la mayor parte del tiempo se dedica en este trozo de código:

 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 

donde yo no veo un montón Para optimizar. ¿Tiene alguna idea de cómo hacer que este código sea más eficaz sin ir C?

Answer 1

Con un código como este, puede beneficiarse de la memo- rización de subexpresiones comunes como self.radius * self.radius como self.radius2 y 1/self.radius como self.one_over_radius. La sobrecarga del intérprete de Python puede dominar tales mejoras triviales.

Answer 2

1) El trazado de rayos es divertido, pero si usted se preocupa en absoluto sobre el rendimiento, pitón volcado y cambiar a C. No C++ a menos que seas una especie de super experto, simplemente C.

2) La gran victoria en escenas con objetos múltiples (20 o más) es usar un índice espacial para reducir el número de pruebas de intersección. Las opciones populares son kD-trees, OctTrees, AABB.

3) Si habla en serio, consulte ompf.org: es el recurso para esto.

4) No vayas a ompf con python preguntando por la optimización: la mayoría de la gente puede disparar de 1 millón a 2 millones de rayos por segundo a través de una escena interior con 100 mil triángulos ... Por núcleo.

Me encanta el trazado de rayos y Python, pero nunca consideraría ponerlos juntos. En este caso, la optimización correcta es cambiar de idioma.

Answer 3

Una optimización menor es: a y b * b son siempre positivos, por lo que es verdad si disc < 0.0(c > 0 && b < min(a, c)). En este caso, puede evitar el cálculo de b * b - 4.0 * a * c. Teniendo en cuenta el perfil que hiciste, a lo más tardaré un 7% del tiempo de ejecución del golpe, supongo.

Answer 4

Su mejor opción será utilizar tablas de búsqueda y valores precalculados tanto como sea posible.

Como su respuesta a mi comentario indica que sus vectores de dirección de rayos son vectores unitarios, en la sección crítica que enumera puede hacer al menos una optimización desde el principio.Cualquier punto vectorial en sí mismo tiene una longitud al cuadrado, por lo que un punto vectorial de unidad siempre será 1.

Además, precalcule el radio al cuadrado (en la función __init__ de su esfera).

entonces usted tiene:

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 temp punto se va a dar el equivalente de sum(map(lambda component: component*component, temp)) ... no estoy seguro de que es más rápido sin embargo.

Answer 5

Al observar su código, parece que su problema principal es que tiene líneas de código que se llaman 2560000 veces. Eso tomará mucho tiempo, sin importar qué tipo de trabajo esté haciendo en ese código. Sin embargo, usando numpy, puede agregar gran cantidad de este trabajo a un pequeño número de llamadas numpy.

Lo primero que debe hacer es combinar sus rayos en grandes matrices. En lugar de usar un objeto Ray que tenga vectores de 1x3 para el origen y la dirección, use matrices Nx3 que tengan todos los rayos que necesita para la detección de golpes. El comienzo de su función golpe va a terminar con este aspecto:

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 

Para la siguiente parte se puede utilizar

possible_hits = numpy.where(disc >= 0.0) 
a = a[possible_hits] 
disc = disc[possible_hits] 
... 

para continuar con sólo los valores que pasan la prueba discriminante. De esta forma, puede obtener fácilmente mejoras de rendimiento de órdenes de magnitud.