Actualmente estoy asistiendo a una clase de análisis de algoritmos y nos dieron trabajo en grupo. El profesor exigió que escogiéramos algún campo en informática, que escogiéramos un algoritmo y probáramos los límites asintóticos (al menos O (N)).

Así que mi colega y yo decidimos hacer un algoritmo de gráficos por computadora, más específicamente un algoritmo de volumen de iluminación.

Pero todo el código analizado por los libros de análisis de algoritmos se ejecuta en la CPU. El código producido en OpenGL se ejecuta en la GPU, lo que no puede garantizar la linealidad, ya que está hecho de varias otras CPU que se ejecutan en paralelo.

¿Ese comportamiento influye en el cálculo? ¿Podría alguien ayudarme a descubrir por dónde empezar?

Este fragmento de código se extrae de GPU Gems 3: Dispersión volumétrica de luz como proceso posterior.

float4 main(float2 texCoord : TEXCOORD0) : COLOR0  
{  
  // Calculate vector from pixel to light source in screen space.  
   half2 deltaTexCoord = (texCoord - ScreenLightPos.xy);  
  // Divide by number of samples and scale by control factor.  
  deltaTexCoord *= 1.0f / NUM_SAMPLES * Density;  
  // Store initial sample.  
   half3 color = tex2D(frameSampler, texCoord);  
  // Set up illumination decay factor.  
   half illuminationDecay = 1.0f;  
  // Evaluate summation from Equation 3 NUM_SAMPLES iterations.  
   for (int i = 0; i < NUM_SAMPLES; i++)  
  {  
    // Step sample location along ray.  
    texCoord -= deltaTexCoord;  
    // Retrieve sample at new location.  
   half3 sample = tex2D(frameSampler, texCoord);  
    // Apply sample attenuation scale/decay factors.  
    sample *= illuminationDecay * Weight;  
    // Accumulate combined color.  
    color += sample;  
    // Update exponential decay factor.  
    illuminationDecay *= Decay;  
  }  
  // Output final color with a further scale control factor.  
   return float4( color * Exposure, 1);  
}

Creo que el límite asintótico sería una función de las muestras. Algo que también debe tenerse en cuenta son las 4 ecuaciones físicas necesarias para generar el sombreador. Gracias de antemano por toda la ayuda de la comunidad!

0
mandre96 28 abr. 2017 a las 02:27

3 respuestas

La mejor respuesta
uniform float exposure;
uniform float decay;
uniform float density;
uniform float weight;
uniform vec2 lightPositionOnScreen;
uniform sampler2D myTexture;
const int NUM_SAMPLES = 100 ;
void main()
{   
C1  vec2 deltaTextCoord=vec2(gl_TexCoord[0].st-lightPositionOnScreen.xy);                          
C2      vec2 textCoo = gl_TexCoord[0].st;                                                                         
C3      deltaTextCoord *= 1.0 /  float(NUM_SAMPLES) * density;                                        
C4      float illuminationDecay = 1.0;                                                                                 
n       for(int i=0; i < NUM_SAMPLES ; i++)     {                                          
C5              textCoo -= deltaTextCoord;                                                    
C6          vec4 sample = texture2D(myTexture, textCoo );                        
C7                     sample *= illuminationDecay * weight;                                   
C8              gl_FragColor += sample;                                                      
C9              illuminationDecay *= decay;                                                    
                                                }
C10                 gl_FragColor *= exposure;  
}

f(n) =∑_(i=0)^n〖(C_5+ C_6+ C_7+ C_8+ C_9)〗 + C_1 + C_2 + C_3 + C_4 + C_10

(C_5+ C_6+ C_7+ C_8+ C_9 )=K_1

(C_1 + C_2 + C_3 + C_4 + C_10)=K_2

Por lo tanto: f(n)= Cp* K_1*n+ K_2

Siendo Cp el número de píxeles.

Cual es f(n)= θ(n) for each pixel.

@ dv1729 El comentario realmente ayudó en el curso del desarrollo de la tarea de la universidad.

Esto demuestra que el análisis de los algoritmos de gráficos por computadora puede ser muy engañoso, porque todos sabemos lo difícil que es este tipo de posprocesamiento para el hardware, pero revisar el código nos muestra un límite asintótico que de hecho es muy bajo. Las constantes aquí pueden ser muy altas y la matemática profunda detrás de la exploración de luz volumétrica basada físicamente puede pasar desapercibida.

0
mandre96 10 jun. 2017 a las 18:43

2 2

La complejidad del algoritmo no cambia; el tiempo de ejecución sí. Pero esto es cierto para mucha complejidad. La ordenación rápida y la ordenación por fusión tienen la misma complejidad nLog (n), pero la ordenación rápida es, en promedio, más rápida en la práctica.

Los límites asintóticos no son el fin del rendimiento.

4
Nicol Bolas 28 abr. 2017 a las 00:28

Todas las líneas de código implican un tiempo de ejecución constante (no implican bucles o llamadas recursivas ni nada de eso). Sin embargo, las líneas dentro del bucle se ejecutan NUM_SAMPLES veces. Por lo tanto, el tiempo de ejecución de una invocación de sombreador será:

O (NumSamples)

Dado que este sombreador se ejecuta una vez por píxel, el tiempo total de ejecución será:

O (NumSamples * ResoluciónX * ResoluciónY)

Tenga en cuenta que Nicol Bolas tiene razón, la complejidad del algoritmo no ha cambiado, tiene lo mismo si se ejecuta en la CPU, pero sería más lento para problemas relacionados con el hardware.

En un análisis más profundo, podría analizar el uso de cada núcleo de GPU y la aceleración sobre la CPU, pero en este código simple ... No importa mucho ya que el uso probablemente sería muy cercano al 100%. En cualquier caso, para analizar esto, deberá comprender tanto la arquitectura de hardware de la GPU como los costos generales del algoritmo.

0
dv1729 30 abr. 2017 a las 20:31