Nel mio campo (VFX, che copre cose come la tracciatura dei percorsi, l'animazione del computer, la simulazione delle particelle, la fluidodinamica, l'elaborazione delle immagini, ecc.), la complessità algoritmica è fondamentale. Non c'è assolutamente nulla che funzioni in modo peggiore del tempo linearithmic può sperare di completare in qualsiasi momento ragionevole input che comunemente raggiungono milioni di vertici, poligoni, voxel, particelle, texel, specialmente quando molte di queste cose devono essere completate molte volte al secondo per fornire feedback interattivo in tempo reale.
Detto questo, non c'è quella strong enfasi sulla complessità algoritmica nella discussione tipicamente tra colleghi, forse perché è in qualche modo data per scontata e piuttosto "rudimentale". Generalmente si presume che si stia scrivendo un tracciatore di percorso che funzionerà in tempo logaritmico o migliore e che le strutture di dati come le gerarchie del volume di delimitazione sono familiari e relativamente banali da implementare per il lettore. Ho persino avuto un collega esperto che ha continuato a dire che il multithreading e il SIMD sono più importanti degli algoritmi, e non credo che intendesse questo nel senso che si potrebbe aspettarsi di ottenere molto dal parallelizzare un bubble sort. Penso che abbia detto questo perché ha dato per scontato che avremmo applicato algoritmi sensibili, e il resto della sfida è spesso la parallelizzazione e la scelta e l'adattamento di algoritmi e la progettazione della rappresentazione dei dati per operare in parallelo.
Spesso in questi giorni molta attenzione è prendere molti di questi algoritmi familiari e farli sfruttare meglio le caratteristiche di base dell'hardware come la cache della CPU, i registri SIMD e le istruzioni, le GPU e i core multipli. Ad esempio, Intel ha escogitato un nuovo modo di prendere il vecchio BVH e di inventare il concetto di "pacchetti di raggi", testando in pratica più raggi coerenti in una sola volta con un tipo di attraversamento dell'albero ricorsivo (che potrebbe sembrare come veniamo con la sua parte di complessità e sovraccarico, eccetto che è più che compensato dal fatto che quei raggi possono ora essere testati simultaneamente per le intersezioni raggio / AABB e raggio / triangolo attraverso istruzioni e registri SIMD). Altri traccianti di tracciati all'avanguardia sono riusciti a implementare tali indici spaziali e ad eseguire effettivamente le intersezioni di raggio direttamente su GPU.
Una cosa simile con la suddivisione di catmull-clark, che è roba molto rudimentale nella computer grafica. Ma oggigiorno ciò che è competitivo e caldo e super efficiente sono le implementazioni di GPU che approssimano la suddivisione CC usando Gregory Patches, come reso popolare da Charles Loop e successivamente adottato dalla Pixar. L'implementazione della CPU più diretta ora è piuttosto obsoleta, non necessariamente perché è stata sostituita in termini di complessità algoritmica, ma perché è stata sostituita da qualcosa che funziona bene con la GPU.
Di solito, in questi giorni la maggior parte della sfida non è la definizione del miglior algoritmo in un modo relativamente indipendente dalle caratteristiche di base dell'hardware. In realtà ho trovato il piede nel settore presentando una nuova struttura di accelerazione che ha accelerato significativamente il rilevamento delle collisioni per l'animazione di personaggi e altri corpi morbidi negli anni '90 utilizzando un approccio di segmentazione gerarchico rispetto a un indice spaziale, che mi ha dato un sacco di offerte di lavoro, ma di questi tempi non è più così impressionante da quando l'ho pubblicato molto prima che avessimo cache di CPU e core multipli e GPU programmabili e cosa no, e oggigiorno uso un approccio completamente diverso a seguito delle modifiche significative apportate al hardware sottostante. Quindi l'attenzione si è spostata maggiormente verso ciò che potrebbe essere nel campo delle "micro-ottimizzazioni" nel mio caso rispetto ai nuovi concetti algoritmici perché ora abbiamo più core, registri AVX, shader GPU, ecc. È un gioco di palla diverso per io ora dove non posso solo sperare di competere inventando un algoritmo interessante a meno che non giochi davvero bene con la natura peculiare dell'hardware di oggi che richiede molta attenzione e attenzione in questi giorni per sfruttare appieno.