Mathematics and Implementation ofComputer Graphics Techniques 2015

Boundary Aligned Smooth 3D Cross-Frame Field
Jin Huang, Yiying Tong, Hongyu Wei, Hujun Bao
SIGGRAPH Asia 2011
Kenshi Takayama
Assistant Prof @ National Insitute of Informatics
takayama@nii.ac.jp
2nd round
3 October 2015

Background: 2D Frame Field & Quad Meshing• 2D Frame Field
 Auto-computed• UV Parameterization
 Auto-computed

Mixed-Integer Quadrangulation [Bommes,Zimmer,Kobbelt,SIGGRAPH09]

2D Frame Field

UV Parameterization= Quad Mesh2Background: 3D Frame Field & Hex Meshing• 3D Frame Field
 Heuristic• UVW Parameterization
 Auto-computed“Meta-Mesh” to define
3D Frame Field
UVW Parameterization= Hex Mesh

CubeCover - Parameterization of 3D Volumes [Nieser,Reitebuch,Polthier,SGP11]

3

Distance between 3D Frames

𝑅1𝑅2𝑅3・・・ℎ 𝑠 ≔ 𝑠𝑥2 𝑠𝑦2 + 𝑠𝑦2 𝑠𝑧2 + 𝑠𝑧2 𝑠𝑥2

2𝑑𝑠

𝑑 𝑅𝑎 , 𝑅𝑏 ≔𝑠∈𝑆 2ℎ 𝑅𝑎 𝑠ℎ 𝑅𝑏 𝑠• Integral over an entire sphere  Spherical Harmonics!
4Representing 3D frames using SH coeffsℎ 𝑅𝑠= 𝜆−4 ×+ 𝜆−1 ×𝑌4−4𝑌4−1+ 𝜆2 ×+ 𝜆−3 ×𝑌4−3+ 𝜆0 ×

𝑌40+ 𝜆3 ×𝑌42+ 𝜆1 ×+ 𝜆4 ×== 𝑠𝑥2 𝑠𝑦2 + 𝑠𝑦2 𝑠𝑧2 + 𝑠𝑧2 𝑠𝑥2𝑌4−2𝑌43

𝜆−4𝜆−3𝜆−2𝜆−1𝜆0𝜆1𝜆2𝜆3𝜆4ℎ 𝑠+ 𝜆−2 ×𝑅= 7×
𝑌41+ 5×𝑌40

𝑌44

𝑌440000700055

Representing 𝑅 using ZYZ Euler angles
𝑅 𝛼, 𝛽, 𝛾=𝑅Z 𝛾

𝑅Y 𝛽𝑅Z 𝛼=𝑅Z 𝛾

𝑅X −𝜋2𝑅Z 𝛽=cos 𝛾 −sin 𝛾 0sin 𝛾 cos 𝛾 0001010cos 𝛽 −sin 𝛽 0sin 𝛽 cos 𝛽 0001●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●𝑅 𝛼, 𝛽, 𝛾 =10000−1●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

𝑅Z 𝛾●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

𝜋
𝑅X −
2

Rotation about Z axis by 𝛼
𝜋2

𝑅X1
0000
1

𝑅Z 𝛼

0−1
0

cos 𝛼 −sin 𝛼 0
sin 𝛼 cos 𝛼 0001●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

𝑅Z 𝛽●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

𝑅X

𝜋2●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●𝑅Z 𝛼6Deriving 𝑅Z 𝛼 & 𝑅X

https://en.wikipedia.org/wiki/Table_of_spherical_harmonics#Real_spherical_harmonics

𝑌4−4 𝑥, 𝑦, 𝑧 =3 35𝑥𝑦 𝑥 2 − 𝑦 2
4 𝜋

𝑌40 𝑥, 𝑦, 𝑧 =3 135𝑧 4 − 30𝑧 2 + 3
16 𝜋

𝑌4−3 𝑥, 𝑦, 𝑧 =3 35
3𝑥 2 − 𝑦 2 𝑦𝑧
4 2𝜋

𝑌41 𝑥, 𝑦, 𝑧 =3 5𝑥𝑧 7𝑧 2 − 3
4 2𝜋

𝑌4−2 𝑥, 𝑦, 𝑧 =3 5𝑥𝑦 7𝑧 2 − 14 𝜋

𝑌42 𝑥, 𝑦, 𝑧 =3 5 2𝑥 − 𝑦 2 7𝑧 2 − 18 𝜋

𝑌4−1 𝑥, 𝑦, 𝑧 =3 5𝑦𝑧 7𝑧 2 − 34 2𝜋

𝑌43 𝑥, 𝑦, 𝑧 =3 35 2𝑥 − 3𝑦 2 𝑥𝑧
4 2𝜋2𝜋𝜋𝑅Z 𝛼 𝑖,𝑗 =0𝑅X𝜋2𝜋
202𝜋0

3 35 2 2𝑥 𝑥 − 3𝑦 2 − 𝑦 2 3𝑥 2 − 𝑦 216 𝜋𝑥 = sin 𝜃 cos 𝜙𝑦 = sin 𝜃 sin 𝜙𝑧 = cos 𝜃𝑗

𝑌4𝑖 sin 𝜃 cos 𝜙 + 𝛼 , sin 𝜃 sin 𝜙 + 𝛼 , cos 𝜃 ⋅ 𝑌4 sin 𝜃 cos 𝜙 , sin 𝜃 sin 𝜙 , cos 𝜃 sin 𝜃 𝑑𝜃 𝑑𝜙𝜋=𝑖,𝑗𝑌44 𝑥, 𝑦, 𝑧 =0𝑗

𝑌4𝑖 sin 𝜃 cos 𝜙 , − cos 𝜃 , sin 𝜃 sin 𝜙 ⋅ 𝑌4 sin 𝜃 cos 𝜙 , sin 𝜃 sin 𝜙 , cos 𝜃 sin 𝜃 𝑑𝜃 𝑑𝜙 use Computer Algebra Systems (CAS): Mathematica, Maple, Sage7

Sage code (https://cloud.sagemath.com)
Y4_4(x,y,z) = 3/4*sqrt(35/pi)*x*y*(x^2 - y^2)
Y4_3(x,y,z) = 3/4*sqrt(35/(2*pi))*(3*x^2 - y^2)*y*z
Y4_2(x,y,z) = 3/4*sqrt(5/pi)*x*y*(7*z^2 - 1)
Y4_1(x,y,z) = 3/4*sqrt(5/(2*pi))*y*z*(7*z^2 - 3)
Y40(x,y,z) = 3/16*sqrt(1/pi)*(35*z^4 - 30*z^2 + 3)
Y41(x,y,z) = 3/4*sqrt(5/(2*pi))*x*z*(7*z^2 - 3)
Y42(x,y,z) = 3/8*sqrt(5/pi)*(x^2 - y^2)*(7*z^2 - 1)
Y43(x,y,z) = 3/4*sqrt(35/(2*pi))*(x^2 - 3*y^2)*x*z
Y44(x,y,z) = 3/16*sqrt(35/pi)*(x^2*(x^2 - 3*y^2) - y^2*(3*x^2 - y^2))

Y4 = [Y4_4, Y4_3, Y4_2, Y4_1, Y40, Y41, Y42, Y43, Y44]
for i in range(9):v = []for j in range(9):Si(theta, phi) = Y4[i](sin(theta)*cos(phi+a), sin(theta)*sin(phi+a), cos(theta))
Sj(theta, phi) = Y4[j](sin(theta)*cos(phi), sin(theta)*sin(phi), cos(theta))
v.append(integral(Si(theta, phi) * Sj(theta, phi) * sin(theta), theta, 0, pi).integrate(phi, 0, 2*pi))
print v

for i in range(9):v = []
for j in range(9):Si(theta, phi) = Y4[i](sin(theta)*cos(phi), -cos(theta), sin(theta)*sin(phi))
Sj(theta, phi) = Y4[j](sin(theta)*cos(phi), sin(theta)*sin(phi), cos(theta))
v.append(integral(Si(theta, phi) * Sj(theta, phi) * sin(theta), theta, 0, pi).integrate(phi, 0, 2*pi))
print v

Matrices written down
𝑅Z 𝛼 =

cos 4𝛼0000
cos 3𝛼0000
cos 2𝛼0000
cos 𝛼0000000− sin 𝛼00− sin 2𝛼00− sin 3𝛼00− sin 4𝛼000000010000000sin 𝛼0
cos 𝛼000𝜋2000000−3 47 40000007 43 40000− 2 4− 14 40000000− 14 4 02 40000000000
14 4− 2 40000002 4
14 400005 435 80000001 200− 7 40000001 8− 7 4𝑅X=

3 805 4035 800
sin 2𝛼000
cos 2𝛼000sin 3𝛼00000
cos 3𝛼0sin 4𝛼0000000
cos 4𝛼9Going between ZYZ (3D)  SH (9D)
• ZYZ  SH𝜋𝜋𝐟 𝛼, 𝛽, 𝛾 ≔ 𝑅Z 𝛾 ⋅ 𝑅X −⋅ 𝑅Z 𝛽 ⋅ 𝑅X
⋅ 𝑅Z 𝛼 ⋅ ℎ22• SH  ZYZ𝐠 𝐟in ≔ 𝑎𝑟𝑔 min 𝐟in − 𝐟 𝛼, 𝛽, 𝛾ℎ≔2𝛼,𝛽,𝛾 ∈ℝ3000070005• Minimize 𝐸 𝛼, 𝛽, 𝛾 using Conjugate Gradient𝑑𝐸= −2 𝐟in − 𝐟 𝛼, 𝛽, 𝛾𝑑𝛼⊤ 𝑑𝐟

𝑑𝛼𝑑𝐟𝜋𝜋 𝑑 𝑅Z= 𝑅Z 𝛾 ⋅ 𝑅X −⋅ 𝑅Z 𝛽 ⋅ 𝑅X⋅⋅ℎ𝑑𝛼22𝑑𝛼𝑑 𝑅Z=𝑑𝛼−4 sin 4𝛼 0000 −3 sin 3𝛼 0000 −2 sin 2𝛼 0000 − sin 𝛼0000000 − cos 𝛼00 −2 cos 2𝛼 00 −3 cos 3𝛼 00−4 cos 4𝛼 000000000000000 4 cos 4𝛼00 3 cos 3𝛼 00 2 cos 2𝛼 00cos 𝛼 0000000− sin 𝛼 0000 −2 sin 2𝛼 0000 −3 sin 3𝛼 0000 −4 sin 4𝛼10Toy example: interpolating two frames
𝑡=0𝐟0 = 𝐟 𝛼0 , 𝛽0 , 𝛾0𝛼0 = 53∘
𝛽0 = 60∘𝛾0 = 356∘

𝑡=1𝛼𝑡 , 𝛽𝑡 , 𝛾𝑡 = 𝑎𝑟𝑔 min𝛼,𝛽,𝛾 ∈ℝ31 − 𝑡 𝐟0 + 𝑡 𝐟1 − 𝐟 𝛼, 𝛽, 𝛾2𝐟1 = 𝐟 𝛼1 , 𝛽1 , 𝛾1
𝛼1 = 160∘
𝛽1 = 43∘𝛾1 = 2∘
11

Real examples with tetrahedral meshes

12Small differences from [Huang11]• Per-vertex discretization•  per-face (Crouzeix-Raviart) discretization• #vertices ≪ #faces  much smaller problem size (x0.1)• Normal alignment properly handled• No global nonlinear solve w.r.t.

𝛼𝑖 , 𝛽𝑖 , 𝛾𝑖

• Only Laplacian smoothing + per-vertex nonlinear projection

13

Recent arXiv paper [Ray & Sokolov 2015]• Unified view toward 2D & 3D problems• Better handling of normal alignment• “Feasibility” constraint linearized & integrated
into iterative solve• SH cookbook, concise pseudocode
http://arxiv.org/abs/1507.03351

14

Small ideas for further improvements• Fix 3D frames on boundary using 2D frames• Decouple 9 SH coeffs  x1/9 dimensionality• Jacobi-style iteration  simple & parallel• Other scattered-data-interpolation tools (RBF / MLS) ?
• (Not my main focus anyway)
Instant Field-Aligned Meshes [Jakob, Tarini, Panozzo, Sorkine-Hornung, SIGGRAPH Asia 2015]15