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
1st round
25 July 2015

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

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

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

Definition of 3D Frame• Don’t care about orientation / ordering of axes
𝑅1𝑅2

𝑅3𝑅4・・・• 𝑅1 = 𝑅2 = ⋯ = 𝑅1 , 𝑅2 , … , 𝑅24• Question: How distant is 𝑅𝑎 from 𝑅𝑏 ?

• Key insight: ℎ 𝑠 ≔ 𝑠𝑥2 𝑠𝑦2 + 𝑠𝑦2 𝑠𝑧2 + 𝑠𝑧2 𝑠𝑥2 ,𝑠 ∈ 𝑆2

• Invariant under sign flip / axis reordering!
4Distance between 3D Framesℎ 𝑠 ≔ 𝑠𝑥2 𝑠𝑦2 + 𝑠𝑦2 𝑠𝑧2 + 𝑠𝑧2 𝑠𝑥22𝑑𝑠𝑑 𝑅𝑎 , 𝑅𝑏 ≔𝑠∈𝑆 2ℎ 𝑅𝑎⊤ 𝑠ℎ 𝑅𝑏⊤ 𝑠• Integral over an entire sphere  Spherical Harmonics!
5Basics of Spherical Harmonics• Something like Fourier series on sphere
∞

𝑙-2

-1

0

1

2

30𝑓𝑙𝑚 𝑌𝑙𝑚 𝜃, 𝜙𝑓 𝜃, 𝜙 =-31

𝑙=0 𝑚=−𝑙2• Orthonormality:

3𝑚
𝑌𝑙 1 𝑠𝑠∈𝑆 2𝑚
𝑌𝑙 2 𝑠𝑑𝑠 =10if 𝑚1 = 𝑚2otherwise

𝑙6𝑚

Frame represented by SH

𝑌4−4𝑌4−32 𝜋
5 4ℎ 𝑠 =−𝑌40 𝑠 +𝑌4 𝑠 + 16 𝜋𝑌00 𝑠
157• “Frequency” unaffectedby rotation:• Frame represented as SH coeffs
for band 𝑙 = 4 (i.e. 9-vector) :• Coeffs mapped by some 9x9 matrix 𝑅 :• Distance between 𝑅𝑎 & 𝑅𝑏 :

𝑌4−2

𝑌4−1

𝑌40

𝑌41

𝑌42

𝑌43

𝑌44

simplifyℎ 𝑠 ≔ 7𝑌40 𝑠 + 5𝑌44 𝑠
4𝜆𝑚 𝑌4𝑚 𝑠ℎ 𝑅⊤ 𝑠 =: 𝑓 𝑅 𝑠 =𝑚=−4𝑓 𝑅 ≔ 𝜆−4 , 𝜆−3 , 𝜆−2 , 𝜆−1 , 𝜆0 , 𝜆1 , 𝜆2 , , 𝜆3 , 𝜆4
ℎ = 𝑓 𝐼 = (0,0,0,0, 7, 0,0,0, 5)

𝑓𝑅 = 𝑅 ℎ𝑑 𝑅𝑎 , 𝑅𝑏 = 𝑅𝑎 ℎ − 𝑅𝑏 ℎ27

Computing 9x9 𝑅 from 3D rotation 𝑅• Not immediately obvious𝜋/2
𝜃• Insight: Obvious for certain cases: 𝑅Z & 𝑅X

• (Not sure...)Rotation about Z axis by θ

 Represent rotation by ZYZ Euler angle
𝛾𝛽𝛾−2𝛾𝑅Z𝛼 = 𝑅Z 𝑅X• 𝑅 𝛼, 𝛽, 𝛾 ≔ 𝑅Z 𝑅Y• 𝑅 𝛼, 𝛽, 𝛾 = 𝑅Z

𝜋

𝑅X𝛽𝜋
2

𝑅Z 𝑅X

𝜋−2𝛽𝜋2𝑅Z 𝑅X 𝑅Z𝛼𝑅Z𝛼8

Frame that aligns with boundary surface
Coeff for 𝑌40• Frame 𝑅 aligns with:• Z axisiff• Surface normal 𝑛iff

𝑓𝑅 0 = 7𝑅𝑛→Z 𝑓 𝑅(Proof in Appendix)

0 = 7• 𝑅𝑛→Z : Rotation that brings n to Z axis

9Discretization & Objective• Tetrahedral mesh over domain Ω• Frame var 𝑓𝑝𝑖 at center 𝑝𝑖 of every (interior/exterior) triangle TRI𝑖
• Piecewise-linear frame field 𝑓• Gradient 𝛁𝑓TET𝑗 constant within each tetrahedron TET𝑗

• Objective to be minimized:
4𝐸smooth ≔volume TET𝑗TET𝑗

𝐸align ≔𝑚=−4area TRI𝑖TRI𝑖 ∈𝜕Ω𝛁𝑓TET𝑗 (𝑚)2𝑅𝑛𝑖 →Z 𝑓𝑝𝑖 0 − 72𝐸align𝐸smooth𝐸full ≔+ 𝑤alignarea 𝜕Ωvolume Ω 1/3
10

Optimization• Energy quadratic in 𝑓𝑖  Simple Laplace-like least squares <Step 1>• Problem: Arbitrary 𝑓𝑖 doesn’t represent rotation!
 <Step 2> Project 𝑓𝑖 to its closest rotation 𝑅 𝛼𝑖 , 𝛽𝑖 , 𝛾𝑖
• (Not sure how to do it...)• <Step 3> Using Φ𝑖 ≔ 𝛼𝑖 , 𝛽𝑖 , 𝛾𝑖 as initial
guess, run nonlinear optimization over Φ𝑖• L-BFGS (solver: ALGLIB, dlib, etc)
• (Not sure about analytic form of derivative...)11

Results & Performance12

Questions• Regarding implementation:
𝜋/2𝜃• Expressions for 𝑅Z & 𝑅X

• Projection of 𝑓𝑖 to its closest rotation 𝑅 𝛼𝑖 , 𝛽𝑖 , 𝛾𝑖
• Analytic derivative of 𝐸full w.r.t. {Φ𝑖 }• Possible idea for improvement:• Can we sidestep nonlinear optimizationby alternating Laplace smoothingand “normalization”?

13