En mi campo (VFX, que cubre aspectos como el trazado de rutas, la animación por computadora, la simulación de partículas, la dinámica de fluidos, el procesamiento de imágenes, etc.), la complejidad algorítmica es fundamental. No hay forma de que algo que funcione en un tiempo peor que el tiempo lineal puede esperar completar en un tiempo razonable en entradas que comúnmente alcanzan millones de vértices, polígonos, voxeles, partículas, texeles, especialmente cuando muchas de estas cosas deben completarse varias veces por segundo para proporcionar Comentarios interactivos en tiempo real.
Dicho esto, no hay un énfasis tan fuerte en la complejidad algorítmica en la discusión entre colegas, tal vez porque se da por sentado y es algo "rudimentario". En general, se asume que si está escribiendo un trazador de ruta que operará en tiempo logarítmico o mejor, y que las estructuras de datos, como las jerarquías de volumen de delimitación, son familiares y relativamente triviales de implementar para el lector. Incluso tuve un colega experto que decía que el multihilo y el SIMD son más importantes que los algoritmos, y no creo que lo dijera en el sentido de que se podría esperar mucho al paralelizar una burbuja. Creo que dijo que debido a que daba por sentado que aplicaríamos algoritmos sensibles, y el resto del desafío a menudo es la paralelización y la elección y adaptación de algoritmos y el diseño de la representación de datos para operar en paralelo.
A menudo, gran parte del enfoque se centra en tomar muchos de estos algoritmos conocidos y hacer que exploten mejor las características subyacentes del hardware, como el caché de la CPU, los registros e instrucciones SIMD, las GPU y los múltiples núcleos. Por ejemplo, Intel ideó una forma novedosa de tomar el antiguo BVH familiar y proponer el concepto de "paquetes de rayos", básicamente probando múltiples rayos coherentes a la vez con un tipo recursivo de recorrido de árboles (que podría sonar así) Viene con su parte de complejidad y gastos generales, excepto que está más que compensado por el hecho de que esos rayos ahora se pueden probar simultáneamente para las intersecciones de rayos / AABB y rayos / triángulo a través de las instrucciones y registros de SIMD). Otros trazadores de ruta de vanguardia han logrado implementar dichos índices espaciales y realizar las intersecciones de rayos directamente en la GPU.
Algo similar con la subdivisión catmull-clark, que es algo muy rudimentario en gráficos de computadora. Pero hoy en día, lo que es competitivo y eficiente y súper eficiente son las implementaciones de GPU que se aproximan a la subdivisión de CC utilizando los parches de Gregory, popularizados por Charles Loop y luego adoptados por Pixar. La implementación de CPU más sencilla ahora es bastante obsoleta, no necesariamente porque fue reemplazada en términos de complejidad algorítmica, sino porque fue reemplazada por algo que funciona bien con la GPU.
Y, por lo general, ese gran desafío en estos días no es encontrar el mejor algoritmo de una manera que sea relativamente independiente de las características subyacentes del hardware. En realidad, puse mi pie en la industria al idear una estructura de aceleración novedosa que aceleró significativamente la detección de colisiones para personajes animados y otros cuerpos blandos en los años 90 utilizando un enfoque de segmentación jerárquica en lugar de un índice espacial, lo que me ayudó mucho. ofertas de trabajo, pero en estos días ya no es tan impresionante ya que lo publiqué mucho antes de que tuviéramos tan impresionantes cachés de CPU y múltiples núcleos y GPU programables, y lo que no, y hoy en día utilizo un enfoque completamente diferente como resultado de los cambios significativos en el hardware subyacente. Así que el enfoque en realidad se ha orientado más hacia lo que podría ser en el ámbito de las "micro-optimizaciones" en mi caso sobre conceptos algorítmicos novedosos porque ahora tenemos múltiples núcleos, registros AVX, sombreadores de GPU, etc. Es un juego de pelota diferente a Ahora, donde no puedo esperar competir con un algoritmo genial, a menos que realmente funcione bien con la naturaleza peculiar del hardware de hoy en día, que en especial requiere mucha atención y cuidado para explotarlo por completo.