Computer Graphics
From mathematics …
𝑆 = 𝐩 ∈ 𝐑3 , 𝑓 𝐩 = 0
𝑛
1
𝛼𝑅 𝐩 ≈ 𝛿𝑖
𝑑 𝐩 = 𝑛(𝐩) ⋅ 𝑙 𝑛
𝑖=0
© Giimann Futuristic Road Tunnel / Created in MOI3D and 3dsMax / Rendered with V-Ray
… to the screen
E. Galin
[Link]@[Link]
[Link]
Université Lyon 1
Signed Distance Fields 17 septembre 2024 1
Computer Graphics
Mathematics
Modeling
Color and Texturing
Shading
Realistic Rendering
Acceleration
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 2
Computer Graphics
Surfaces Implicites
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 3
Surfaces implicites
Implicit Surfaces Applications
Distance Fields Représentation adaptée à la modélisation de volumes de géométrie et de topologie changeante
Ray Intersection
Appendix
Terminator 2 Judgment day
Verrous scientifiques et techniques
Variété de formes
Représentation compacte
Verrous
Modélisation Animation Visualisation
Contrôle de forme Habillage de particules Intersection Δ ∩ 𝑺
[Link]@[Link] Raccordements Contrôle de mouvement Approximation de 𝑺
[Link]
Signed Distance Fields 17 septembre 2024 4
Surfaces implicites
Implicit Surfaces Définition
Distance Fields Caractérisation S = 𝐩 ∈ 𝐑3 , 𝑓 𝐩 = 0 𝑓(𝐩) < 0 S
Ray Intersection
Si 0 valeur régulière de 𝑓, alors 𝑓 −1 0 est une 2 variété
Appendix 𝑓(𝐩) > 0
Convention d’intérieur de la surface 𝑓 𝐩 < 0 𝑓(𝐩) = 0
Une 2 variété sépare 𝐑3 en une surface et 2 sous domaines 𝑓 𝑥, 𝑦, 𝑧 = 𝑥2 − 𝑦 2 − 𝑧 2 − 1
connexes : une région finie dans la surface S et une région
Sphère unité
infinie dehors (théorème de séparation)
Propriétés
Formes géométriques à 2 dimensions dans 𝐑3
Un voisinage V(𝐩) est équivalent à un disque
2 variété Autres
p
p
V(𝐩) p
p
Sphère Tore Surface à bord Raccord à trois feuilles
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 5
Gradient
Implicit Surfaces Définition et propriétés
Distance Fields Le gradient 𝛻𝑓 est le vecteur des dérivées partielles S = 𝐩 ∈ 𝐑3 , 𝑓 𝐩 = 0
Ray Intersection 𝜕𝑓 𝜕𝑓 𝜕𝑓
Appendix
𝛻𝑓 = , ,
𝜕𝑥 𝜕𝑦 𝜕𝑧 S
p
Approximation d’une dérivée
𝜕𝑓 𝑓 𝑥 + 𝜀, 𝑦, 𝑧 − 𝑓 𝑥 − 𝜀, 𝑦, 𝑧 n
≈
𝜕𝑥 2𝜀
La normale 𝐧 à la surface S dérive du gradient
∀𝐩 ∈ 𝑆 𝐧 = 𝛻𝑓 𝐩 / 𝛻𝑓 𝐩
Suivi de gradient
Projection d’un point proche de la surface sur S
𝐩 −𝜀𝑓(𝐩)
Gradient descent
Start from 𝐩
At every step S
𝐩 = 𝐩 − 𝜀 𝛻𝑓 𝐩
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 6
Propriété de Lipschitz
Implicit Surfaces Définition
Distance Fields La fonction 𝑓 doit être au moins de classe 𝐶 0 (les classes 𝐶 1 ou 𝐶 2 sont plus régulières)
Ray Intersection
𝑓 est 𝜆 −Lipschitzienne si et seulement si
Appendix ∃λ > 0 ∀ 𝐩, 𝐪 ∈ 𝐑3 × 𝑹3 𝑓 𝐩 − 𝑓 𝐪 < λ|𝐩 − 𝐪 |
Propriétés
Critère d’exclusion [Hart1996]
𝑓 /λ est une borne inférieure de la distance Euclidienne
Soit f une fonction 𝜆 −Lipschitzienne, alors ∀ 𝐩 ∈ 𝐑3
p p
𝐵(𝐩, 𝑓(𝐩) /λ) ∩ 𝑆 = ∅ r
r
Boule de centre p Rayon 𝑓(𝐩) /λ 𝑓 𝐩
>𝑟
𝜆
[Link]@[Link]
[Link] J. Hart. Sphere Tracing: A Geometric Method for the Anti aliased Ray Tracing of Implicit Surfaces, The Visual Computer, 12(10), 1996
Signed Distance Fields 17 septembre 2024 7
Computer Graphics
Distance Fields
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 8
Arbre de construction
Implicit Surfaces Construction
Distance Fields Difficulté fondamentale
Ray Intersection
Construire une expression analytique de la distance
Appendix
Euclidienne signée est en général impossible
On construit 𝑓 comme une borne inférieure (en valeur
absolue) 𝐶 0 ou 1–Lipschitzienne avec ∀𝐩 𝑓 𝐩 ≤ 𝑑 𝐩, 𝑆
Combinaison hiérarchique [Wyvill1999]
Primitives aux feuilles Mélange
Opérateurs aux nœuds
Echelle Différence
Sphères Torsion Sphère
Union
Cylindres
[Link]@[Link]
[Link] B. Wyvill, A. Guy, E. Galin. Extending the CSG-Tree. Computer Graphics Forum. 18 (4), 149 – 158, 1999
Signed Distance Fields 17 septembre 2024 9
Primitives
Implicit Surfaces Distance à un squelette
Distance Fields Convention 𝑓 𝐩 < 0 si 𝐩 dans l’objet, 𝑓 𝐩 > 0 dehors
Ray Intersection
Tore, disque arrondi, barre arrondie, sphère, sphère le long d’une courbe
Vidéo
Appendix
𝑓 𝐩 = 𝑑 𝐩, 𝑆 − 𝑟
Rayon
Distance au squelette r c
Sphère
Vidéo 𝑓 𝐩 = ||𝐩 − 𝐜|| − 𝑟
Courbe
Snail
© Inigo Quilez
Primitives polygonales (boite, pyramide) : intersections de demi espaces…
[Link]@[Link]
𝑑 𝐩, 𝜋 = 𝐩 − 𝐜 ⋅ 𝐧
[Link]
Signed Distance Fields 17 septembre 2024 10
Opérateurs de combinaison
Implicit Surfaces Opérateurs booléens
Distance Fields Union, intersection, différence
Ray Intersection
𝑓𝐴∪𝐵 𝐩 = min 𝑓𝐴 , 𝑓𝐵 𝑓𝐴∩𝐵 𝐩 = max 𝑓𝐴 , 𝑓𝐵 𝑓𝐴−𝐵 𝐩 = max 𝑓𝐴 , −𝑓𝐵
Appendix
Mélange
Dans le domaine des Blobs, on calcule 𝑓𝐴 + 𝑓𝐵 simplement [Wyvill1999]
Modèle plus complexe pour les distances signées
1
Correction g 𝑎, 𝑏 = 6 𝑟 ℎ3
𝑓𝐴∪∗ 𝐵 𝐩 = min 𝑓𝐴 , 𝑓𝐵 − 𝑔 𝑓𝐴 , 𝑓𝐵
avec ℎ = max 𝑟 − 𝑎 − 𝑏 , 0 /𝑟
Union Offset
Rayon de mélange
b- a = r
g(a,b) a
Elephant © Inigo Quilez
[Link]@[Link]
[Link] B. Wyvill, A. Guy, E. Galin. Extending the CSG-Tree. Computer Graphics Forum. 18 (4), 149 – 158, 1999
Signed Distance Fields 17 septembre 2024 11
Transformations affines
Implicit Surfaces Principe
Distance Fields En modélisation implicite, on déforme l’espace par la transformation inverse
Ray Intersection
𝑓𝜔(𝐴) 𝐩 = 1/ 𝐽𝜔−1 𝑓𝐴 ∘ 𝜔−1
Appendix
Translation, rotation, homothétie 𝐽𝜔−1 1
Norme du Jacobien
𝐽𝜔−1 = 1
𝑓𝑇 𝐴 𝐩 = 𝑓𝐴 ∘ 𝐩 − 𝐭 𝑓𝑅 𝐴 𝐩 = 𝑓𝐴 ∘ 𝑅 −1 𝐩 𝑓𝑆 𝐴 𝐩 = 1/𝑠 𝑓𝐴 ∘ (𝐩/𝑠)
Translation inverse Rotation inverse Homothétie inverse
𝑅 −1 𝜃 = 𝑅 −𝜃
Les compositions de transformations ne
sont pas commutatives
Matrices de rotation
Différentes matrices selon les repères [Shirley]
1 0 0 𝑥 2 𝑎 + 𝑐 𝑥𝑦𝑎 − 𝑠𝑧 𝑥𝑧𝑎 + 𝑠𝑦
𝑅𝑥 𝜃 = 0 𝑐 −𝑠 𝑅𝑢 𝜃 = 𝑥𝑦𝑎 + 𝑠𝑧 𝑦 2 𝑎 + 𝑐 𝑦𝑧𝑎 − 𝑠𝑥
0 𝑠 𝑐 𝑥𝑧𝑎 − 𝑠𝑦 𝑦𝑧𝑎 + 𝑠𝑥 𝑧2𝑎 + 𝑐
où 𝑐 = cos 𝜃 et 𝑠 = sin 𝜃 où 𝑎 = 1 − cos 𝜃
[Link]@[Link]
[Link] P Shirley. Fundamentals of Computer Graphics. Third Edition. AK Peters
Signed Distance Fields 17 septembre 2024 12
Composition
Implicit Surfaces Formes complexes
Distance Fields Construction de formes complexes par assemblage hiérarchique de primitives
Ray Intersection Placement d’instances et composition dans le graphe de scène
Appendix
Graphe de scène ⇔ Composition de fonctions ⇔ Appels
Colonne
Bruit
Union
Boites Cylindres
Temple
Union
Translation Translation
Colonnes Pavés
[Link]@[Link] Temple © Inigo Quilez
[Link]
Signed Distance Fields 17 septembre 2024 13
Déformation
Implicit Surfaces Définition
Distance Fields Déformation l'espace w
𝑓𝜔(𝐴) 𝐩 = 𝑓𝐴 ∘ 𝜔−1
Ray Intersection
Restriction éventuelle à une région Ω
Appendix
Mise en œuvre analytique
La fonction w doit être inversible
Jacobien 𝐉𝜔−1 complexe pour calculer analytiquement 𝛻𝑓
𝑐𝑥 𝑠𝑦 0
𝜔𝜃−1
ሶ 𝐩 = 𝜔 −𝜃ሶ 𝐩 = −𝑠𝑦 𝑐𝑦 0
0 0 1
ሶ et 𝑠 = sin 𝜃𝑧
où 𝑐 = cos 𝜃𝑧 ሶ
Torsion [Barr1984] Vitesse angulaire
Perturbation par bruit
Déplacement stochastique de 𝐩 𝑓𝜔(𝐴) 𝐩 = 𝑓𝐴 ∘ 𝐩 − 𝛿(𝐩)
Fractional Brownian Motion
Bruit ou turbulence
[Link]@[Link]
[Link] B. Wyvill, A. Guy, E. Galin. Extending the CSG-Tree. Computer Graphics Forum. 18 (4), 149 – 158, 1999
Signed Distance Fields 17 septembre 2024 14
Computer Graphics
Ray – Distance Field Intersection
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 15
Introduction
Implicit Surfaces
Distance Fields Visualization
Ray Intersection 𝑆 = 𝐩 ∈ 𝑅3 |𝑓 𝐩 = 0
Appendix
Polygonization [Araujo2015] converts model to large meshes
Direct ray tracing remains computationally intensive
Parallel implementation partially alleviate the problem
[Link]@[Link]
Ladybug
© Inigo Quilez
[Link]
Signed Distance Fields 17 septembre 2024 16
Ray marching
Implicit Surfaces Définition
Distance Fields Déplacement le long du rayon Δ à pas constant 𝜀 [Perlin1989]
Ray Intersection
Intersection si 𝑓 𝐩 change de signe
Raffinement par dichotomie Implicit surface S Ray D
Appendix
𝑆 = 𝐩 ∈ 𝐑3 |𝑓 𝐩 = 0 Δ: 𝜹 𝑡 = 𝐨 + 𝐮𝑡 | 𝑡 ∈ 0, ∞
Ray Marching
Start from ray origin 𝑡 = 0
At every step
Intersection found
Compute 𝐩 = 𝐨 + 𝐝𝑡
If 𝑓 𝐩 < 0 then return 𝑡 u
Otherwise step forward
o
𝑡=𝑡+𝜀
March along the ray at positions p(t)
Computationally intensive with fixed step [Perlin1989]
[Link]@[Link]
[Link] K. Perlin, E. Hoffert. Hypertexture. ACM SIGGRAPH Computer Graphics, 23(3), 1989.
Signed Distance Fields 17 septembre 2024 17
Sphere Tracing
Implicit Surfaces Origine
Distance Fields Algorithme complexe à partir des dérivées premières et secondes [Kalra1989]
Ray Intersection
Principe
Appendix
Déplacement adaptatif long du rayon Δ avec un pas minimum 𝜀 [Hart1989, Hart1996]
Intersection si 𝑓 𝐩 change de signe
Lorsque 𝑓 est 𝜆 −Lipschitzienne alors |𝑓 𝐩 |/ 𝜆 est une borne de la distance Euclidienne à 𝑆
∀𝐩 ∈ 𝐑3 𝐵 𝐩, 𝑓 𝐩 /𝜆 ∩ 𝑆 = ∅
Sphere Tracing [Hart1996]
Start from ray origin 𝑡 = 0
At every step p
Compute 𝐩 = 𝐨 + 𝐝𝑡 Intersection found
If 𝑓 𝐩 < 0 then return 𝑡
Otherwise step forward
𝑡 = 𝑡 + max |𝑓 𝐩 |/𝜆, 𝜀
Δ
Sphere tracing
[Link]@[Link] D. Kalra, H. Barr. Guaranteed Ray Intersections with Implicit Surfaces. ACM SIGGRAPH Computer Graphics, 23(3), 1989.
[Link] J. Hart. Sphere Tracing: A Geometric Method for the Antialiased Ray Tracing of Implicit Surfaces. The Visual Computer 12(10), 527–545,1996.
Signed Distance Fields 17 septembre 2024 18
Computer Graphics
Appendix
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 19
Distance à une boite
Implicit Surfaces Distance Euclidienne b
Distance Fields On utilise la distance entre p et deux plans parallèles
Ray Intersection
Appendix 𝜋𝐚 𝜋𝐛 a
0 si 𝐚𝑥 < 𝐩𝑥 < 𝐛𝑥
p
d 𝐩, 𝜋𝐚 ∩ 𝜋𝐛 = ቐ 𝑥 𝐩𝑥
𝐚 − si 𝐩𝑥 < 𝐚𝑥
𝐧𝐚 𝐧𝐛 𝐩𝑥 − 𝐛𝑥 si 𝐩𝑥 > 𝐛𝑥
a b
d2 𝐩, B = d2 𝐩, Sx + d2 𝐩, Sy + d2 𝐩, S𝑧
Distance signée
Soit 𝐜 = 𝐚 + 𝐛 /2 le centre, 𝐩 = 𝐩 − 𝐜 et 𝐝 = 𝐛 − 𝐚 /2 la diagonale
−𝐝
On tire parti de la symétrie en définissant 𝐪 = abs 𝐩
0 si 𝐪 ∉ 𝐵 Maximum de 𝐪i < 0 si 𝐪 ∈ 𝐵
d 𝐩, 𝐵 = min max 𝐪x , 𝐪y , 𝐪z , 0 + max 𝐪, 𝟎
Norme Euclidienne Vecteur nul
[Link]@[Link]
0 si 𝐪 ∈ 𝐵
[Link]
Signed Distance Fields 17 septembre 2024 20 20
Distance à un segment
Implicit Surfaces Distance à une droite p
Distance Fields Pythagore dans le triangle 𝐚𝐩𝐪 d2 𝐩, Δ
Ray Intersection 2 D
Appendix
d2 𝐩, Δ = 𝐩 − 𝐚 2
− 𝐩−𝐚 ⋅𝐮
q
Carré de la distance a
u
Distance à un segment
Calcul de 𝑙 = 𝐩 − 𝐚 ⋅ 𝐮 où 𝐮 = 𝐛 − 𝐚 / 𝐛 − 𝐚
p a p
b
2
𝐩−𝐚 si 𝑙 < 0 q
2 2 2 a
d 𝐩, 𝐚𝐛 = 𝐩−𝐚 − 𝐩−𝐚 ⋅𝐮 si 0 < 𝑙 < 𝐛 − 𝐚
2 u b
𝐩−𝐛 sinon
p
p
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 21 21
Distance à un cercle ou un disque
Implicit Surfaces Cercle
2 2 2
Distance Fields Par construction 𝑑 𝐩, 𝐶 = 𝑑 𝐩, 𝜋 + 𝐜−𝐪 −𝑟 ou q projeté de p
Ray Intersection p u
Appendix double Circle::R(const Vector& p) const {
Vector n = p – c;
double h = n * u; c
double y = n * n – h * h ; // Radial distance q
y = r – sqrt ( y );
return sqrt ( y * y + h * h );
// Distance to circle
p
}
if ( y < r*r ) { return z; } // Distance to disc
Disque
On teste si 𝐜 − 𝐪 < 𝑟 : dans ce cas où l’on calcule la distance au plan p
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 22
Distance à une courbe
Implicit Surfaces Distance d’un point à une courbe
Distance Fields Soit G une courbe d’équation paramétrée 𝐜 𝑡 où 𝑡 ∈ [0,1]
Ray Intersection
Appendix 𝑑2 𝐩, Γ = min 𝐜 𝑡 − 𝐩 2
𝑡∈[0,1]
Polynôme de degré n
Recherche des racines de l’équation 𝐜 𝑡0
𝐜 𝑡1
2 ′ ′ 𝐜 0 𝐜 1
𝑑 𝐩, Γ = 0 ⟺ 𝐜 𝑡 − 𝐩 ⋅ 𝐜 𝑡 = 0
Equation de degré 2𝑛 − 1 à résoudre sur [0,1] p
𝟐
Chercher le minimum de 𝐜 𝑡 − 𝐩 avec au plus 2𝑛 − 1 racines 𝑡𝑘 et {0,1}
[Link]@[Link]
[Link]
Signed Distance Fields 17 septembre 2024 23 23