Poprawa wydajności funkcji uderzenia raytracing

Question

Mam prosty raytracer w python. renderowanie obrazu 200x200 zajmuje 4 minuty, co zdecydowanie jest zbyt duże jak na mój gust. Chcę poprawić sytuację.

Kilka punktów: Fotografuję wiele promieni na każdy piksel (w celu zapewnienia wygładzenia krawędzi), co daje łącznie 16 promieni na piksel. 200x200x16 to suma 640000 promieni. Każdy promień musi zostać przetestowany pod kątem wpływu na wiele obiektów Sfery na scenie. Ray jest również dość trywialny przedmiot

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

Kula jest nieco bardziej skomplikowane i wykonuje logikę dla przebojowej/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  

Teraz wpadłem trochę profilowanie i wydaje się, że najdłuższa przetwarzanie czas jest w funkcji 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} 

To mnie nie zaskakuje, a ja chcę maksymalnie zmniejszyć tę wartość. Mijam do linii profilowania, a wynik jest

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) 

Więc wydaje się, że większość czasu spędza się w tym fragmencie kodu:

 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 

Gdzie tak naprawdę nie zobaczyć wiele optymalizować. Czy masz pojęcie, jak uczynić ten kod bardziej wydajnym bez przechodzenia w C?

Answer 1

Z kodu jak to można skorzystać z memoizing wspólne podwyrażeń jak self.radius * self.radius jako self.radius2 i 1/self.radius jako self.one_over_radius. Obciążenie interpretera Pythona może dominować tak trywialne ulepszenia.

Answer 2

1) Ray tracing jest zabawa, ale jeśli zależy w ogóle na temat wydajności, zrzutu pytona i przełączyć się na C. Nie C++, chyba że jesteś jakimś super ekspertem, po prostu C.

2) duża wygrana w sceny z wieloma (20 lub więcej) obiektami to użycie indeksu przestrzennego w celu zmniejszenia liczby testów przecięcia. Popularne opcje to kD-drzewa, OctTrees, AABB.

3) Jeśli poważnie, sprawdź ompf.org - jest to źródło tego.

4) Nie należy pytać o optymalizację za pomocą pytona - większość ludzi może strzelać od 1 miliona do 2 milionów promów na sekundę poprzez scenę wewnętrzną ze 100 tysięcy trójkątów ... Na rdzeń.

Uwielbiam śledzenie w języku Python i ray, ale nigdy nie pomyślałbym, żeby je połączyć. W takim przypadku prawidłową optymalizacją jest zmiana języków.

Answer 3

Jedna drobna optymalizacja jest: a i b * b zawsze są pozytywne, więc disc < 0.0 jest prawdą jeśli (c > 0 && b < min(a, c)). W takim przypadku można uniknąć obliczania b * b - 4.0 * a * c. Biorąc pod uwagę profil, w którym to zrobiłeś, najpewniej zginiesz 7% czasu wykonania trafienia.

Answer 4

Twój najlepszy zakład będzie polegał na używaniu tablic przeglądowych i obliczonych wartości w jak największym stopniu.

W odpowiedzi na mój komentarz zaznaczono, że wektorami kierunkowymi promienia są wektory jednostkowe, w sekcji krytycznej, którą wpisałeś, możesz dokonać co najmniej jednej optymalizacji bezpośrednio poza kijem.Każda kropka wektorowa ma długość równą kwadratowi, więc kropka wektorze jednostkowym sama będzie zawsze równa 1.

Również wstępnie obliczyć promień do kwadratu (w funkcji sfery __init__).

Wtedy masz:

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 kropka temp zamierza dać równowartość sum(map(lambda component: component*component, temp)) ... Nie jestem pewien, która jest szybsza choć.

Answer 5

Patrząc na twój kod, wygląda na to, że głównym problemem jest to, że masz linie kodu, które są nazywane 2560000 razy. To zajmie dużo czasu, niezależnie od tego, jaką pracę wykonujesz w tym kodzie. Jednak używając numpy, możesz zebrać dużo tej pracy w niewielkiej ilości numpy połączeń.

Pierwszą rzeczą do zrobienia jest połączenie promieni razem w duże tablice. Zamiast używać obiektu Ray, który ma wektory 1x3 do początku i kierunku, użyj macierzy Nx3, które mają wszystkie promienie potrzebne do wykrywania trafień. W górnej części swojej funkcji przeboju skończy się patrzy tak:

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 

Na kolejnej części można użyć

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

kontynuować tylko wartości, które przechodzą dyskryminacyjnej testu. W ten sposób możesz łatwo uzyskać ulepszenia wydajności rzędu wielkości.