Raymarching - besoin d'explications

[flure]

Salut à tous,

Je compte maintenant m'attaquer au raymarching, c'est un peu la mode en ce moment, faut bien que je me tienne à jour

Donc je crois avoir à peu près compris le principe, mais je ne suis pas certain. En premier lieu je ne vois pas la différence avec le raycasting, comme on le fait par exemple pour un freedirectional tunnel.

Ce que j'ai compris : on envoie un rayon de qui part de l'oeil et qui passe par le pixel. On le fait avancer par pas d'une certaine distance, et à chaque pas on utilise une fonction de distance qui renvoie la distance au point de l'espace le plus proche. Quand cette distance est suffisamment faible, on diminue la taille du pas, suivant la résolution désirée, jusqu'à ce que la fonction de distance renvoie une valeur suffisamment faible pour qu'on considère qu'on est arrivé. De là on obtient la couleur du pixel.

J'ai bon ?

Pour info je voudrais utiliser le raymarching pour faire du rendu de metaballs en soft, sans passer par les marching cubes. Peut-être que je devrais m'attaquer en premier à quelque chose de plus simple, comme des sphères ou des plans ?

Voilà, toute aide sera la bienvenue, et je vous tiendrai bien sûr au courant de l'évolution de mes essais sur le sujet

[@lx]

Ce que j'ai compris : on envoie un rayon de qui part de l'oeil et qui passe par le pixel. On le fait avancer par pas d'une certaine distance, et à chaque pas on utilise une fonction de distance qui renvoie la distance au point de l'espace le plus proche. Quand cette distance est suffisamment faible, on diminue la taille du pas, suivant la résolution désirée, jusqu'à ce que la fonction de distance renvoie une valeur suffisamment faible pour qu'on considère qu'on est arrivé. De là on obtient la couleur du pixel.
J'ai bon ?

Ouip! 

Pour info je voudrais utiliser le raymarching pour faire du rendu de metaballs en soft, sans passer par les marching cubes. Peut-être que je devrais m'attaquer en premier à quelque chose de plus simple, comme des sphères ou des plans ?

Le plus simple est de travailler sur une scène basique qui contient effectivement une sphère. Tu valideras l'algo. Ensuite, tu peux travailler sur un peu n'importe quoi...

[Patapom]

J'imagine que t'as lu http://www.iquilezles.org/www/material/nvscene2008/rwwtt.pdf ?

Je t'avouerais que j'ai découvert les distance fields grâce à U2 qui m'a filé ce même lien il y a à peine une semaine ! J'ai déjà fait des tests pour voir mais mes rayons manquent parfois leur cible, j'ai dû rater des trucs essentiels parce que j'ai besoin de beaucoup de steps et au bout de 64 je m'arrête et ça touche pas forcément la destination.

Voici une image en fausses couleurs d'une sphère avec du noise avec 64 steps par rayon maximum (en rouge) :


Quand c'est violet c'est l'infini donc pas besoin de tracer de rayons. Quand c'est noir c'est qu'il est pas arrivé au hit après 64 rayons, en gros, là où j'ai échoué.
J'ai pas beaucoup poussé plus loin vu que je suis sur d'autres trucs en ce moment.

Mais oui tu as bien cerné le principe : en gros tu évalues la distance à l'objet le plus proche à chaque point de ton rayon. Ca te permet d'avoir une limite maximale du pas auquel tu peux avancer avant de risquer de toucher un objet...
Le problème vient évidemment des rayons rasants puisque tu te rapproches continuellement de la surface sans forcément jamais la toucher... Du coup t'avances seulement un tout petit peu à chaque fois, c'est le paradoxe de Zénon all over again !

D'après Iñigo, tu peux fixer une taille de step minimale pour être certain de toujours avancer d'au moins un certain pas. Et tu peux aussi tirer avantage du fait que l'erreur diminue avec la distance à la caméra donc faire en sorte que tes pas de rayons soient proportionnels à cette même distance.
J'ai eu beau faire joujou avec ce pas minimum et cette correction par la distance à la caméra, j'ai toujours de la merde.

Bref. Disons que tu trouves bien ton intersection quelque part, après il s'agit de récupérer la normale à la surface, calculer l'ombrage et l'ambient occlusion.
Je vais pas paraphraser Iñigo puisque tout est expliqué dans son PDF mais ça reste assez simple. Le plus difficile restant vraiment à trouver correctement l'intersection en un minimum de steps...

Pour ce qui concerne la différence avec du ray-casting : là tu codes la distance d'un objet par rapport à un point.
En ray-tracing tu calcule carrément l'intersection du rayon avec l'objet avec une formule (pas forcément super simple selon l'objet à intersecter).

Par exemple pour un cube qui est pas le plus simple :

• En ray-trace, tu dois calculer l'intersection avec une des 6 faces du cube, en gros tu calcules l'intersection avec 6 plans et tu vérifies si cette intersection se trouve dans les limites de la taille des faces du cube. J'écris même pas le code parce que c'est une horreur.
  
• Avec les distance fields tu écris simplement :
    Distance = max( abs( p.x ), max( abs( p.y ), abs( p.z ) ) ) -1.0;

[zerkman]

ha oui j'ai entendu parler de ça récemment, mais je ne vois vraiment pas l'interêt face à du vrai raycasting où tu tombes directement sur ta cible.

Exemple : une sphère de rayon r et dont le centre a les coordonnées c=(x_c, y_c, z_c). Tu lances ton rayon à partir de l'origine o=(x_o, y_o, z_o), avec un vecteur direction d=(x_d, y_d, z_d) - vecteur unitaire (= dont la norme vaut 1). Tu résous l'équation ||o + t*d - c||² = r², si une solution existe tu trouves une distance t entre le point o et l'intersection rayon/sphère. Ton point d'intersection est donc égal à o+t*d.

L'exemple est expliqué là.

Ca se fait en un seul coup, pas de méthode itérative. Tu choisiras finalement le point le plus proche parmi les intersections avec tous les objets (ie la valeur t positive la plus faible). Il y a des algos pour éviter de calculer les intersections avec tous les objets de la scène.

D'où ma question : qu'est-ce que le "raymarching" apporte ? Ca sert à quoi de découper la recherche itérativement, et surtout est-ce que ça garantit qu'on trouve à coup sûr l'objet le plus proche sans le rater ? C'est quoi la théorie derrière ?

[nystep]

Quand cette distance est suffisamment faible, on diminue la taille du pas, suivant la résolution désirée, jusqu'à ce que la fonction de distance renvoie une valeur suffisamment faible pour qu'on considère qu'on est arrivé. De là on obtient la couleur du pixel.

En fait non, tu incrémentes ton T de la valeur de la distance à la géométrie la plus proche, ce qui garantit que la nouvelle position de ton rayon est en dehors des objets de ta scène. Après, ça converge vers un epsilon. Naturellement. C'est fort.

Effectivement la différence avec le raycasting, c'est que tu ne calcules pas d'intersections, tu les approximes à un epsilon près.

[nystep]

Je conseille cet article, très bien fait:

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter08.html

[@lx]

Comme l'a souligné Patapom, le papier d'iq est une référence et aussi celui de gpugems par nystep

J'avais contribué aussi à un petit article sur mon blog intitulé "Potatro, RayMarching and DistanceFields : a story of SphereTracing", plutôt simple et didactique, avec en prime une version 2D du raymarching pour comprendre comment cela ça fonctionne.... surtout lorsque l'on connait un peu le raytracing/casting mais qu'on ne voit pas la différence avec le raymarching.

D'où ma question : qu'est-ce que le "raymarching" apporte ? Ca sert à quoi de découper la recherche itérativement, et surtout est-ce que ça garantit qu'on trouve à coup sûr l'objet le plus proche sans le rater ? C'est quoi la théorie derrière ?

Le raymarching apporte la possibilité de rendre des formes qui sont souvent quasi-impossible à résoudre mathématiquement, de faire des combinaisons entre elles, sans que cela change quoi que ce soit au rendu... Essentiellement utilisé pour faire du rendu d'iso-surface. Après, pour déterminer l'intersection ("root finding") de manière itérative tu as plusieurs méthodes, dont la plus connue est "SphereTracing" de J.Hart... qui peut se coupler avec un algo de bisection basique sur les dernières itérations.

[nystep]

Ca se fait en un seul coup, pas de méthode itérative. Tu choisiras finalement le point le plus proche parmi les intersections avec tous les objets (ie la valeur t positive la plus faible). Il y a des algos pour éviter de calculer les intersections avec tous les objets de la scène.

Tu oublies juste un détail: un objet en raytracing, c'est un triangle.

70 000 triangles c'est beaucoup. La structure d'accélération arborescente est énorme, et la parcourir fait plein d'accès mémoire aléatoires. De plus, construire une bonne structure d'accélération peut être très couteux, ce qui empêche de le faire pour les objets animés.

[@lx]

La boucle de raymarching converge en général après 32-64 itérations, franchement c'est compétitif, surtout quand les accès mémoires sont cohérents avec les pixels adjacents... Il est également possible de faire du raymarching de façon hiérarchique: en faisant d'abord une approximation pour 16*16 pixels, puis 8*8, puis 4*4, puis 2*2 et enfin les pixels finaux... Là, tu tombes à 10 (ou -) évaluations de la fonction de distance par pixel..

J'avais tenté ça pour l'intro ergon 4k, mais j'avais été assez déçu... enfin, surtout dans le ratio quantité_de_code_supplémentaire / gain_en_perf. Bon, en plus, le problème avec ce système, c'est que tu peux te retrouver à avoir des "trous", ce qui fait que tu dois réduire le pas de manière empirique, suivant la scène, afin d'éviter ça...

Sinon, pour accélérer les choses, il y a aussi l'intérêt de faire du LOD sur la forme iso, surtout si par exemple la forme iso utilise des textures pour bumper les surfaces, il vaut mieux avoir une formule iso sans bumping, et intégrer le bumping sur les dernière itérations... c'est beaucoup moins couteux et pour le coup, ça aide pas mal dans les perfs.

[zerkman]

Tu oublies juste un détail: un objet en raytracing, c'est un triangle.

Bin dans mon exemple, j'ai donné des sphères comme objets possibles. Comme autres trucs simples il y a les parallélépipèdes (pas forcément rectangles et donc pas forcément des cubes), les cylindres, cones, plans, et compositions de tous ces trucs (unions / intersections). Les metaballs ou blobs ne sont pas compliqués non plus, c'est une fonction de distance par rapport à plusieurs centres de sphères au lieu d'un seul, les vecteurs normaux sont hyper faciles à calculer, etc.

Pour les triangles je suis parfaitement conscient que ça finit vite par devenir le bordel. L'idée est quand même de triangulariser au minimum, donc tout ce qui est faisable sans triangles doit être fait sans. En plus les triangles ont la facheuse tendance à bouffer de la mémoire, et il y a des plate-formes où la place mémoire est critique (ex. j'ai fait des trucs sur PS3 où chaque coeur dispose de 256 ko de ram).

70 000 triangles c'est beaucoup. La structure d'accélération arborescente est énorme, et la parcourir fait plein d'accès mémoire aléatoires. C'est inefficace: j'ai essayé.

En fait ça dépend énormément de ta structure d'accélération et de son organisation : par ex pour un kd tree, selon si l'arbre est équilibré, a une profondeur optimisée, etc, les résultats changent du tout au tout.

Et je maintiens qu'utiliser des triangles pour faire du raytracing, ça doit rester vraiment quand il n'y a pas d'autre solution.

[TarMil]

Pour résumer la différence:

• Le raycasting/raytracing est efficace quand on a une formule rapide pour trouver l'intersection d'un rayon et de l'objet.
  => l'objet est décrit de manière constructive : X appartient à l'objet ssi X = f(A), où f(A) est une description paramétrique de l'objet. On n'a plus qu'à résoudre f(A) = O + aV, où O et V sont l'origine et la direction du rayon, et hop! On a les intersections.
• Le raymarching est efficace quand on a une formule rapide pour trouver la distance d'un point à l'objet.
  => l'objet est décrit de manière non constructive : X appartient à l'objet ssi d(X) = 0. La formule ne permet pas directement de donner tous les points de l'objet, donc on ne peut pas (ou difficilement) trouver les intersections avec le rayon. On est obligé d'itérer.

Mais du coup, je dis peut-être une grosse connerie, mais est-ce qu'on ne pourrait pas raycaster les objets constructifs, raymarcher les objets implicites, pour finalement prendre le plus proche des deux ?

[@lx]

Bin dans mon exemple, j'ai donné des sphères comme objets possibles. Comme autres trucs simples il y a les parallélépipèdes (pas forcément rectangles et donc pas forcément des cubes), les cylindres, cones, plans, et compositions de tous ces trucs (unions / intersections).

Je doute que tu puisses calculer des intersections facilement en appliquant des déformations (twist, shear...etc.) sur les formes iso comme ça se fait couramment lorsqu'on les utilise, non? Si cette technique de raymarching a été inventé (et ça date de 1989 quand même), c'est justement pour couvrir des cas ou le raycasting est inefficace...

[nystep]

pour compléter, (beau résumé tarmil)

X appartient à l'objet ssi d(X) <= 0
L'énorme avantage c'est que tu as plus que la surface: tu sais également si tu es à l'intérieur où à l'extérieur des objets... Celà simplifie plein de choses: placement de la caméra notament... Gestion de la transparensce.
C'est important de définir la "distance intérieure" (négative) sinon la méthode des différences centrées pour calculer le gradient ne marche pas (artéfacts dans le calcul des normales dans ce cas)...

[nystep]

C'est également vrai que tu peux interopérer les 2 méthodes: il suffit de prendre le min des deux... l'interopérabilité marche y compris avec la rasterisation classique si tu prends soin d'écrire le zbuffer quand tu utilises le raytracing/raymarching

[ntsc]

tiens tite question..de graphiste c'est possible d'intégrer une scene en raymarching dans une scene 3D classique ?
PAr exemple une piece en 3D faite sous 3Ds et a l'interieur on lui colle un un truc tout space en raymarching ( comme dans la 4ko ergon).