Differentiable Curve(Under Construction!)

課程

http://www.cs.uu.nl/docs/vakken/ddm/2019-2020/
https://cims.nyu.edu/gcl/teaching.html
https://mirelab6.wixsite.com/dgpslides
https://graphics.stanford.edu/courses/cs468-13-spring/schedule.html
http://school.geometryprocessing.org/
http://ddg.cs.columbia.edu/
http://www.cs.cmu.edu/~kmcrane/
http://wordpress.discretization.de/geometryprocessingandapplicationsws19/2019/10/17/lecture-progress/
http://fernandodegoes.org/
https://graphics.tudelft.nl/Publications-new/2016/VCDPBHB16/

備忘

0. speed: parameter
1. tangent : gradient of position
2. normal : variant of tangent
3. distance
4. area
5. curvature
6. principal curvature
7. shape operator
8. energy

curve

curvature
1. curve       p(t)                   = (x(t), y(t))
2. ds          ‖p′(t)‖                = √x′(t)² + y′(t)² = ds
3. length      s(t) = ∫₀ᵗ ‖p′(t)‖     = ∫₀ᵗ √x′(t)² + y′(t)²
4. tangent     T(t) = p′(t) / ‖p′(t)‖ = normalize(dp/dt)
5. normal      N(t) = p″(t) / ‖p″(t)‖ = normalize(dT/dt)
6. binormal    B(t) = T(t) × N(t)
7. curvature   κ(t) = ‖p′(t) × p″(t)‖ / ‖p′(t)‖³
8. torsion     τ(t) = [(p′(t) × p″(t)) ∙ p‴(s)] / ‖p′(t) × p″(t)‖²

reparameterization

arc length reparameterization (tangent normalization)
x. length               s(t)   (strictly monotone increasing)
y. inverse of s(t)      t(s)
z. reparameterization   p(s) = p(t(s))
a. arc length           ‖p(s1) - p(s2)‖ = |s1 - s2|
b. ds                   ‖p′(s)‖ = 1
c. curvature            κ(s) = ‖T′(s)‖ = ‖N(s)‖ = ‖p″(s)‖ = 1/r
d. torsion              τ(s) = ‖B′(s)‖
1. tangent              T(s) = p′(s)           = dp/ds
2. normal (scaled) κ(s) N(s) = p″(s)           = dT/ds
3. normal               N(s) = p″(s) / ‖p″(s)‖ = normalize(dT/ds)

frenet frame

2d frenet frame
{ dT/ds =   κ N
{ dN/ds = - κ T

3d frenet frame
{ dT/ds =   κ N
{ dN/ds = - κ T + τ B
{ dB/ds = - τ N

Differentiable Surface(Under Construction!)

donut

surface

principal curvature
{ κ₁ = H + sqrt(H² - K)
{ κ₂ = H - sqrt(H² - K)

Gaussian curvature
K = κ₁κ₂                 determinant
K = Ag(p) / A(p)         加了鄰居後的面積比率
Ag(p): spherical image   gauss map area

mean curvature
    1  ⌠
H = —— |  ‖x″θ(t)‖dθ   每個方向(角度0到2π)的曲線的曲率的平均
    2π ⌡0
H = (κ₁+κ₂)/2                              Euler Curvature Formula
H = -½(∇∙n⃗)         = -div(n⃗)/2
Hn⃗ = ½ ∇A(p) / A(p) = grad(area)/2area     垂直移動後的面積比率

curvature special case
1. K = 0  developable surface / ruled surface in 3D
2. H = 0  minimal surface / harmonic

variational geometry

curve stretching energy   ∫ ‖p′(t)‖² dt    (sum of squared length)
curve bending energy      ∫₀ˡ κ²(s) ds     (euler elastica)
(with reparameterization) ∫ ‖p″(t)‖² dt

surface stretching energy ∫ ‖∇p(u,v)‖² dudv            (laplacian = 0)
surface bending energy    ∫ (½(κ₁+κ₂))² dA = ∫ H² dA   (bilaplacian = 0)
(with reparameterization) ∫ ‖∇∇p(u,v)‖² dudv           (trival!)
 1. become flat surface, ∇p(u,v) = 0
 2. off-diagonal of hessian matrix are gone, H = trace(∇∇p)/2

jacobian matrix p′(t)   = ∇p
hessian matrix  x″(u,v) = ∇∇x

bending energy    ∫ (κ₁+κ₂)²/4 dA = ∫ H² dA
Willmore energy   ∫ (κ₁-κ₂)²/4 dA = ∫ (H² - K) dA

fundamental form

first fundamental form
x-component of dot product of two tangent vectors
[xu∙xu xu∙xv]  trace = xu² + xv² = grad²    ‖Ⅰ‖² = (xu + xv)²
[xv∙xu xv∙xv]  min ∫ trace => laplace = 0     (membrane energy)

second fundamental form
x-component of dot product of normal vector and tangent variant?
[n∙xuu n∙xuv]  ‖Ⅱ‖² = sum sigma² = k1² + k2²
[n∙xvu n∙xvv]  min ∫ ‖Ⅱ‖² => laplace² = 0  (thin-plate energy)
   dN/dp ???

fundamental form application
trace(Ⅰ)    = length² = ‖xu‖² + ‖xv‖² = grad²
det(Ⅰ)      = area    = ‖xu × xv‖
trace(Ⅱ Ⅰ⁻¹) = 2H      = k1 + k2    (eigenvalue = principal curvature)
det(Ⅱ Ⅰ⁻¹)   = K       = k1k2

fundamental form application
1. shape operator     S = Ⅱ Ⅰ⁻¹
2. eigenvalues of shape operator are principal curvatures

fundamental form application
3. stretching energy  ∫∫Ω ‖diag(Ⅰ'(u,v)-Ⅰ(u,v))‖² dudv
4. bending energy     ∫∫Ω ‖Ⅱ'(u,v)-Ⅱ(u,v)‖² dudv
Ⅰ = dp∙dp
Ⅱ = -dp∙dn
Ⅲ = dn∙dn
KⅠ + 2HⅡ + Ⅲ = 0

延伸閱讀:其他類型的曲線

function curve / function surface

curvature
κ(t) = p″(t) / √(1 + p′(t)²)³
κ(t) ≈ p″(t)   when ‖p′(t)‖ << 1

isocurve(implicit curve) / isosurface(implicit surface)

Curvature formulas for implicit surfaces
https://math.stackexchange.com/questions/383407/
curvature of Isophote
https://en.wikipedia.org/wiki/Isophote

Differentiable Polyline(Under Construction!)

discrete curve

discrete curvature
1. dT = dN , edge = 0 , vertex = θ   轉角大小是曲率積分,角平分線是曲率方向
2. curavture: κn⃗ = 2sin(θ/2)n⃗
3. https://zhuanlan.zhihu.com/p/72083902

Differentiable Mesh(Under Construction!)

Differentiable Mesh

1. gradient
2. laplacian-beltrami

Differential Form

「微分型」。點、邊、面,之間的關聯。

Exterior Calculus

「外微積分」。微分、積分、區域、邊界,之間的關聯。

Exterior Algebra

「外代數」。梯度、散度、旋度,之間的關聯。

https://reurl.cc/odkpAl
https://www.researchgate.net/profile/Marc_Gerritsma/publication/301851033/figure/fig4/AS:667721201102864@1536208548882/Physical-quantities-in-R-3-can-be-associated-with-either-inner-or-outer-oriented-points.png
https://images.app.goo.gl/s2Mmvhv51BMkvMER9
http://ddg.cs.columbia.edu/SIGGRAPH06/DECApplications.pdf
https://www.cs.cmu.edu/~kmcrane/Projects/DGPDEC/
point   ∇   edge   ∇×  face    ∇·  cell
scalar ---> vector ---> vector ---> scalar
  |⋆          |⋆          |⋆          |⋆
cell    ∇·  face   ∇×  edge    ∇   point
scalar <--- vector <--- vector <--- scalar

∆ = d⋆d⋆ + ⋆d⋆d

No Free Lunch: Curvature

事情變得很複雜。一種運算有多種定義方式。

http://geometry.cs.cmu.edu/ddgshortcourse/AMSShortCourseDDG2018_Overview.pdf

No Free Lunch: Laplace-Beltrami Operator

Discrete Laplace operators: No free lunch
如果在二維空間 三個願望一次滿足  四個願望就不行了

discrete surface

discrete curvature
1. principal     https://computergraphics.stackexchange.com/questions/1718
2. mean          http://copyme.github.io/flower/mean-curvature/

from vertex
1. angle deficit: K = 2π - sum θᵢ        角錐展開、頂角大小
   gaussian curavture: K = (2π - sum θᵢ) / (A(p)/3)   曲率積分

from cell
2. mean curvature: 2Hn⃗ = ∇A(p) / A(p)   角錐壓平、面積最小
3. mean curvature: 2Hn⃗ = -∆x            所有方向的二次微分加總

from edge
4. mean curvature: H(e) = ½β‖e‖
   dihedral angle: β      相鄰三角形的法向量夾角,相鄰三角形的轉角。
   (concave is positive)
5. shape operator: S(e) = βeeᵀ / ‖e‖²    3x3矩陣
   { S(e)e = βe
   { S(e)v = 0   when e ⟂ v
6. shape operator: S(v) = sum S(e) / (A(p)/3)
discrete gradient
1. hat function
2. barycentric coordinate

discrete laplacian (Laplace-Beltrami Operator)
1. combinatorial laplacian (min pairwise squared distance)
   [from mean curvature to edge gradient]
   1  ⌠
   —— |  ‖x″θ(t)‖dθ  ---->  div(∇x) = ∆x
   2π ⌡0
   每個方向(角度0到2π)的曲線的曲率的平均 ---> 鄰邊梯度的微分的總和(無須平均)
   所有方向的二次微分加總
2. cot laplacian (min surface area)
   [from area differential to mean curvature]
   2Hn⃗ = ∇A(p) / A(p)  ---->  grad(voronoi cell) = laplace_cot(vertex)
   讓角錐側面積盡量小(側面積→底面積)的頂點移動方向的反方向
   https://www.slideshare.net/gpeyre/mesh-processing-course-mesh-parameterization
3. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds (2003)
   鈍角改用mixed cell
4. A Laplacian for Nonmanifold Triangle Meshes (2020)

normal

normal
1. length is 1
2. cross product

normal type
1. vertex
2. face
3. corner

normal reconstruction
1.1 face -> edge
1.2 face/edge -> vertex
2.  vertex -> face

normal interpolation
1. 角平分線             (normal length = 1, 等腰三角形對稱軸)
2. sphere interpolation (no need normalization)

tangent: Principal Curvature Directions

https://mathematica.stackexchange.com/questions/127975/

《Discrete Differential-Geometry Operators for Triangulated 2-Manifolds》

mean curvature
      1          1             1                        2(pᵢ - pⱼ)∙n⃗
H = —————  sum ( — cot(θᵢⱼ⁺) + — cot(θᵢⱼ⁻) ) ‖pᵢ - pⱼ‖² —————————————
    A(pᵢ) (i,j)  8             8                          ‖pᵢ - pⱼ‖²
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^
                                  wᵢⱼ                        κᵢⱼ
radius of curvature
              ‖pᵢ - pⱼ‖²
r = 1/κᵢⱼ = —————————————    弦(pᵢ,pⱼ),i點法向量n⃗
            2(pᵢ - pⱼ)∙n⃗    半弦長、cos,得到斜邊r

symmetric curvature tensor
B = [ a b ]  where a + c   = 2H = trace(Ⅱ Ⅰ⁻¹)
    [ b c ]        ac - b² = K  = det(Ⅱ Ⅰ⁻¹)

vᵢⱼ = normalize( (pⱼ - pᵢ) - projn⃗(pⱼ - pᵢ) )

solve vᵢⱼᵀ B vᵢⱼ = κᵢⱼ

min sum wᵢⱼ (vᵢⱼᵀ B vᵢⱼ - κᵢⱼ)²
     j

energy

euler elastica
http://www.pci.tu-bs.de/aggericke/PC4e/Kap_V/Normalschwingungen.htm

discrete mean curvature    H = -½(∇∙n⃗) ---> 2Hn⃗ = div(grad(x)) = ∆x
discrete stretching energy ∫ ‖∇x‖² dA                             (∆x = 0)
discrete bending energy    ∫ ‖diag(∇∇x)‖² = ∫ ‖∇∙∇x‖² = ∫ ‖∆x‖²  (∆²x = 0)
discrete Willmore energy   Wᵢ = sum βᵢⱼ - 2π   [Schröder05]

discrete curve bending energy
ds = (si+1 - si)
κ(s) = ‖pi+1 - pi‖ / ds      (arc length reparameterization)
Ebend = ∫₀ˡ κ²(s) ds = sum { ‖pi+1 - pi‖² / (si+1 - si) }

Surface Field(Under Construction!)

field

《Directional Field Synthesis, Design, and Processing》

https://avaxman.github.io/Directional/tutorial/
field
多變量函數用在曲面:函數輸入是曲面的參數座標。

directional field
1. n-vector field (usually 2 tangent vectors)
2. parallel transport: f1:(c1,c2) dot e = f2:(c1,c2) dot e   c1 = v dot t1
3. connection  連成線
4. principal matching: [see panozzo slide] [see directional tutorial]
5. interpolation

singularity
1. umbilic / umbilicus (k1 = k2)
2. wedge
3. trisector

singularity by gauss map
以二維向量場為例
待測點周圍逆時針繞一圈,看看向量的輻角變化,轉了幾周,不等於零的都是奇異點
1. 平流                  0周
2. source放射/sink內聚  +1周=360度
3. saddle十字流出入     -1周=-360度
4. 轉圈                 +1或-1

hairy ball theorem / Poincaré–Hopf theorem
球面上,連續切向量場一定有零(源匯)

tangent vector field

mapping           X -> Y

fiber             反對應,y對應到的所有x,毛囊y的一堆毛x

(fiber) bundle    (parameter,field) -> parameter 視作一種投影
                  萬物->核心。比方說世界萬物->土水風火Doodle God

section           parameter -> (parameter,field) 取得其中一個元素
                  得到一個超級向量場,維度包含了參數和場

vector bundle     (parameter,vector field) -> parameter
tangent bundle    (parameter,tangent plane) -> parameter
                  輸入:所有切面。輸出:切點(或者是X軸方向)
                  可以視作一個4維流形。

section of tangent bundle = tangent vector field
                  parameter -> (parameter,tangent plane) 取得其中一個元素
                  切面以及切點(或者是X軸方向)

cotangent bundle  外代數的對偶(不是垂直補集)
                  切點參數和切線參數互調(也有可能是轉置?)

connection

directional derivative 純量場對向量微分
                       各個地點,純量對向量做微分,純量對方向微分
                       方向微分就是梯度在該方向上的投影(點積)

covariant derivative   向量場對向量場微分(或者,純量場對向量場微分)
                       各個地點,向量對向量做微分,向量對方向微分
                       X值、Y值分別對方向微分,總共兩次
                       方向微分就是梯度在該方向上的投影(點積)

lie derivative         張量場/向量場/純量場對向量場微分
connection             vector bundle裝備上covariant derivative
                       簡單來說,section of vector bundle的方向微分運算子
                       (超級向量場,超級向量場) -> 超級向量場
                       切點的參數(u,v)可以重新想成是路徑的起點與方向?
                       順帶一提,多變量函數的微分就是變換矩陣
                       超級向量場之中,元素套用transformation得到鄰居

connection             Fij ∘ Fjk = Fijk
                       切面(的向量)實施變換,得到隔壁切面(的向量)
                       可以沿著路徑複合。不同路徑可能結果不同。

affine connection      切面(的向量)實施仿射變換,得到隔壁切面(的向量)

holonomy angle         繞一圈之後的相位差
                       跟面積成正比、跟高斯曲率總和成正比

trivial connection     任意一個向量場都可以作為connection
                       相鄰向量差異大小,當作微分算子的計算結果(變換矩陣)
                       優點:各種路徑結果均相同

flat connection        曲率為零。向量全部指向同一方向?
                       holonomy angle = 0

levi-civita connection

riemannian metric      切面集增加副屬性,引入了距離
                       每個切面的X軸Y軸訂好位置之後
                       每個切面的對應點之間,形成一個點集合,定義一個距離函數
                       換句話說
                       切面上的每一個點,各有一個專屬的距離函數
                       所有距離函數總共R^2個,可以看成一個距離函數場
                       一個距離函數的輸入,是兩個切面(的兩個對應點)
                       可以想成二維座標距離(切面由切點決定,切點共有R^2個)

killing vector field   距離函數場對機靈向量場微分=0
                       A-orthogonal  所以是 isometry geometric flow

levi-civita connection 可微、保距、torsion-free
                       向量與切線夾角是定值
                       { Ri(Ti) = Ri(Ti+1)    where R is rotation
                       { Ri(Bi) = 0
                       切線沿著路徑亂走,切線長度與幅角不變化

parallel transport

parallel transport     表面攤平、曲線拉直
                       切面(的向量)實施變換,移動到隔壁切面

parallel transport     向量場對向量場微分=0,路徑微分版本
                       微分=0的意義:以路徑方向為準,向路徑看齊
                       流形表面選出一條路徑(向量場,路徑的方向)
                       流形表面選出一個切線(向量場,切線r,theta),有初始方向
                       極座標r,theta可以換成二維座標c1,c2
                       離散版本的話,就要看每個切面的X軸Y軸座標系統怎麼訂

Mesh Field(Under Construction!)

field

Trivial Connections on Discrete Surfaces (2010)
計算fundamental group的holonomy angle,最小平方解。

Globally Optimal Direction Fields (2013)
n-vector alignment

dihedral angle 相鄰三角形的法向量夾角,相鄰三角形的轉角。

Surface Transformation(Under Construction!)

Surface Transformation(Geometric Flow)

isometric mapping => gaussian curvature is the same (Theorema Egregium)
harmonic mapping => ???
isoperimetric inequality
梯度平方和-梯度差平方=面積的兩倍
(‖Fx‖² + ‖Fy‖²) - ‖Fy - ±Fx⟂‖² = ±2(Fx × Fy)      local
Dirichlet energy - isogonal energy = 2 ⋅ area     global
surface transformation
1. isometric: J = Q, Ⅰ = I
2. conformal: J = sQ,Ⅰ = sI
3. equiareal: det(J) = ±1, det(Ⅰ) = 1

surface transformation
1. conformal   first fundamental form E = G, F = 0
               https://math.stackexchange.com/questions/1514312/
               https://math.stackexchange.com/questions/940456/
2. harmonic    first fundamental form minimize trace
               Minimal Surface

rigid motion of object
2d curve: same speed, curvature
3d curve: same speed, curvature, torsion
3d surface: same first/second fundamental form
3d space: same first fundamental form

mobius transformation

平移 旋轉 縮放 反演
保長 保距 保角 和諧
http://reedbeta.com/blog/conformal-texture-mapping/
http://www.cs.jhu.edu/~misha/Fall09/16-conformalmetrics.pdf

conformal transformation

Conformal Equivalence of Triangle Meshes (2008)

[continuous]
g' = e^2u g
g is metric on reimann manifold

[discrete]
lij' = lij + ui + uj
lij = 2 log wij
wij is metric on mesh (every face ijk satisfies triangle inequality)
不必是弧線,可以是直線...

Mesh Transformation(Under Construction!)

piecewise affine transformation

piecewise affine alignment

三角形任取兩鄰邊,再取法向量,補足線性變換的基底。

兩鄰邊叉積求得法向量。叉積是面積量不是長度量。調整法向量長度時,分母開根號,成為長度量。

solve A(pᵢ - t) = (p̕ᵢ - t̕)     for i = 1,2,3,4
solve A(pᵢ - p₁) = (p̕ᵢ - p̕₁)   for i = 2,3,4
    [   |     |     |   ]       [   |     |     |   ]
V = [ p₂-p₁ p₃-p₁ p₄-p₁ ]   V̕ = [ p̕₂-p̕₁ p̕₃-p̕₁ p̕₄-p̕₁ ]
    [   |     |     |   ]       [   |     |     |   ]
AV = V̕
A = V̕V⁻¹
normal vector of triangle (p₁,p₂,p₃):
              (p₂ - p₁) × (p₃ - p₁)
p₄ - p₁ = ―――――――――――――――――――――――――――――
          sqrt(‖(p₂ - p₁) × (p₃ - p₁)‖)

normal vector of triangle (p̕₁,p̕₂,p̕₃):
              (p̕₂ - p̕₁) × (p̕₃ - p̕₁)
p̕₄ - p̕₁ = ―――――――――――――――――――――――――――――
          sqrt(‖(p̕₂ - p̕₁) × (p̕₃ - p̕₁)‖)

Surface Mapping(Under Construction!)

Shape Approximation

D(M₁, M₂) = ∫x (n̕ᵢᵀx̕ᵢ - nᵢᵀxᵢ)² dA   點到切平面距離,平方誤差總和
D(M₁, M₂) = ∫x ‖n̕ᵢ - nᵢ‖² dA         法向量,平方誤差總和

Shape Metric

《Functional and shape data analysis》

https://di.ku.dk/forskning/research_school/phd_courses/upcoming/international-phd-course-in-nonlinear-statistics/files/
https://di.ku.dk/forskning/research_school/phd_courses/upcoming/international-phd-course-in-nonlinear-statistics/schedule/

Square Root Velocity Function  微分開根號
兩個函數一起重新參數化,SRVF的L2距離保持不變
=> REGISTRATION = PARAMETRIZATION  改一改參數化函數就行了 sqrt(r'(t))
=> Fisher-Rao Metric

但是那個r(t)要怎麼窮舉咧...要怎麼離散化咧...