Model

Model(Shape)(Surface)

模型。物體的造型。

Scanning

掃描。實體變模型。

Modeling

產生模型。有兩種方式:

一、使用硬體,操作相機、光達,擷取真實世界的物體形狀。

二、使用軟體,操作滑鼠、繪圖板,創作自己心儀的物體形狀。

網路上已經有許多現成的模型資料庫,大家可以使用他人製作的模型,不必自己親手設計模型。

Printing

列印。模型變實體。

Rendering

渲染。顯示模型。有兩種方式:

一、顯示於二維平面,例如液晶螢幕、投影幕。

二、顯示於三維空間,科學家正在研究當中。

屬於Graphics領域,容後介紹。

Animation

動畫。操控並且顯示模型。

屬於Animation領域,容後介紹。

使用C/C++處理模型

C與C++本身沒有處理模型的函式庫。大家傾向直接使用現成的函式庫,例如libiglPCLCGALOpenMesh

使用HTML與JavaScript處理模型

JavaScript本身沒有處理模型的函式庫。大家傾向直接使用現成的函式庫,例如p5.js<model-viewer>

也可以土法煉鋼。三個步驟:讀取模型、建立模型、渲染模型。

一、讀取模型。首先在HTML當中,建立一個<object>,載入模型檔案。然後在JavaScript當中,存取<object>,剖析檔案內容,擷取模型數據,存入陣列。

瀏覽器為了安全起見,預設禁止讀取本機檔案。如果你想用自己電腦做實驗,你必須修改瀏覽器設定。做好實驗記得改回來。

Firefox
網址列輸入 about:config
security.fileuri.strict_origin_policy 的值改為 false

二、建立模型。設定模型的中心、尺寸。順便將模型轉成正面。

三、渲染模型。首先在HTML當中,建立一個<canvas>。然後在JavaScript當中,利用內建函式庫WebGL,將模型畫在<canvas>上面。需要「透視投影」的知識。我將模型畫成點雲。

學會呈現點雲之後,就能做一些簡單的實驗了,例如實施幾何變換:平移、縮放、旋轉,例如隨著滑鼠旋轉。

使用現成軟體處理模型

模型的演算法,早已經製作成套裝軟體。完全不需要學習程式語言與數學,只需要仔細閱讀軟體使用說明書。發揮創意,就能做出各種模型外觀。

知名軟體:TinkercadMeshLabOpenSCADSketchUpAutoCADSolidWorksRhinoceros 3D

常見的檔案格式:OBJX3D

常見的測試模型:Stanford bunnyArmadilloDavid、……。詳細列表請見維基百科

課程、書籍、網站

https://mirelab6.wixsite.com/dgpslides
https://github.com/danielepanozzo/gp
http://school.geometryprocessing.org/
http://www.pmp-book.org/
https://www.coursera.org/learn/interactive-computer-graphics
http://kevinkaixu.net/
http://homes.cs.washington.edu/~seitz/talks/3Dhistory.pdf
http://graphics.csie.ntu.edu.tw/~robin/courses/gm13/

Model Representation

Point Cloud(Surfel)

「點雲」。大量的點座標,皆位於物體表面。

點雲是以儀器掃瞄物體所得到的原始資料,儀器是相機、雷射、聲納等等。根據儀器的功能,點座標還可以附帶其他資訊,比如顏色、法向量。

建立點雲,通常是以紅外線掃描器,掃描真實物體。測量光線往返的時間、夾角,計算物體表面的距離、座標,稱作sheet-of-light triangulation。

大家習慣將點雲轉換成其他資料結構,以便計算。

Mesh

「網格」。大量的平坦多邊形。通常是三角形或四邊形。

一個三角形有三個頂點座標。三角形的頂點順序,決定了三角形的正面:正視三角形的正面,大家習慣讓三角形頂點呈逆時針順序。依照頂點順序計算叉積,得到三角形的正面的法向量。這是大家約定俗成、心照不宣的規矩。

資料結構是兩個一維陣列:一個陣列記錄每個點的座標、另一個陣列記錄每個三角形的三個點的編號。由於三角形經常共用頂點,因此兩層式的資料結構,得以節省記憶體空間。

存檔時,只記錄點與三角形。計算時,以點與三角形求得邊。

大家習慣使用網格。優點是計算方便,只有點邊面。缺點是失真,稜稜角角。

Parametric Surface

「參數曲面」和「網格」概念相仿,連續與離散的差別而已。

「參數曲面」。大量的曲面。通常是Bézier surfaceNURBS surface

Voxel

「體素」。整數格點有著數值。通常是Boolean或實數。

訂立臨界值,等於此臨界值的地點,當作表面。調整臨界值,以擴張或收縮表面。

資料結構是三維陣列,或者是八元樹。有人把體素的八元樹稱作sparse voxel octree。

體素和像素概念相同,差別僅在於:像素數值通常是RGB顏色、體素數值通常是物質密度。

建立體素,通常是以超音波、核磁共振等儀器,掃描真實物體,取得各種直線軌道的數值;然後實施演算法,估計每一個體素的數值。請參考image reconstruction

亦可手動設定體素數值,打造心儀模型。例如MagicaVoxel

亦可運用特殊亂數,決定每一個體素的數值,打造特殊模型。例如三維版本的Perlin noise,可以打造雲霧。請參考這份講義

Isosurface(Implicit Surface)

「等值曲面」和「體素」概念相仿,連續與離散的差別而已。

「等值曲面」。處處皆有數值。通常是實數。

以一個連續函數,決定每一個地點的數值。訂立臨界值,等於此臨界值的地點,當作表面。調整臨界值,以擴張或收縮表面。甚至累加多個函數,得到特殊的表面形狀。

知名範例是blobby surface:運用「球體」的數學函數,打造球體模型;改用「淡出的球體」的數學函數,例如三維常態分布,打造球體模型;令多個三維常態分布相加,打造宛如肥皂泡的模型。

以連續函數建立模型,優點是100%精確,無論如何縮放,細節依舊清晰,沒有任何偏差。

順帶一提,等值曲面有一個特例是distance field,能產生模型的聯集、交集、補集。請參考isosurface rendering

Model Reconstruction(Under Construction!)

Point Cloud Registration

配準。儀器於多種地點掃描相同物體,各得一群點雲。所有點雲整合到同一個世界座標系,通通拼裝在一起,形成完整的物體表面。

演算法請參考alignment

Point Cloud Normal Estimation

法向量估計。點雲每一點,求得法向量。

必須知道儀器地點,才能決定法向量是朝內或朝外。

此主題只針對儀器掃瞄物體所得到的原始資料:點雲。此主題不針對後製資料:網格、參數曲面、體素、等值曲面;它們可以利用幾何原理推理出法向量。

principal component analysis (PCA):該點的所有鄰點(半徑範圍內),實施主成分分析(平面擬合)。第一與第二主成分,作為切向量。第三主成分,作為法向量。缺點是無法處理稜角。

Point Cloud ⇨ Mesh

crust algorithm:先求Voronoi diagram,納入其頂點再求Delaunay triangulation。改良版本

Point Cloud ⇨ Voxel

Poisson surface reconstruction:一、點雲已經附帶法向量。二、RBF interpolation,法向量們從離散變連續。三、體素數值設為外1內0,體素梯度將是表面法向量。現在反過來,已知體素梯度,求得體素數值,即是反梯度運算,即是解Poisson equation。程式碼

Mesh ⇨ Voxel

《An Accurate Method for Voxelizing Polygon Meshes》

Voxel ⇨ Mesh

這篇文章彙整了各種演算法,提供了實作

marching cube:觀察一個立方體:8個體素、12條邊。根據12條邊的端點大小關係,決定網格位置。程式碼改良版本

dual contouring:額外知道每個體素的梯度,得以製造美觀網格。

Mesh Generation(Under Construction!)

簡介

調整網格的點邊面。

網格的基本操作

1. vertex move    (advance: laplacian)              smoothing
2. edge flip      (advance: delaunay triangulation) refinement
3. edge contract  (advance: quadric error metric)   simplication
4. edge split     (advance: sqrt(3) ...)            subdivision

Mesh Subdivision

繁化。增加點數。內插。

Loop subdivision
Catmull-Clark subdivision
Doo-Sabin subdivision
Butterfly subdivision
sqrt(3) subdivision
PN triangle

Mesh Simplification(Mesh Decimation)(Mesh Coarsening)

簡化。減少點數。截彎取直。

Ramer-Douglas-Peucker algorithm:用於折線。

Garland-Heckbert algorithm (quadric error metric):收縮一條邊,兩端點併為新點,令「新點」到「兩端點的各個鄰面」的「距離平方總和(二次型、齊次座標)」盡量小,定為誤差。每回合取當下誤差最小的邊進行收縮。新點以反矩陣求得;當反矩陣不存在,則改用舊兩點的加權平均數。程式碼

spectral coarsening:我沒有學會。讓Laplacian matrix的特徵向量盡量保持相同。

Mesh Refinement(Mesh Adaptive Subdivision)

細緻化。局部反覆繁化,讓三角形最小角盡量大,讓表面勻稱。

Ruppert's algorithm:Delaunay triangulation局部繁化。

Chew's algorithm:改良版本。最小角至少28.6°。程式碼

Mesh Fairing(Mesh Smoothing)

平滑化。點數不變,讓表面柔順。

Laplacian smoothing:填坑。將凹陷程度添加回去。

p̕ᵢ = pᵢ + ∆pᵢ

diffusion smoothing:凹陷程度乘上固定倍率,添加回去。

p̕ᵢ = pᵢ + α ∆pᵢ   (0 ≤ α ≤ 1)

Taubin smoothing:倍率正負交替。用於封閉表面,避免體積越縮越小。

p̕ᵢ = pᵢ + α ∆pᵢ   (α > 0)   收縮
p̕ᵢ = pᵢ + β ∆pᵢ   (β < 0)   膨脹

bilaplacian smoothing:兩次laplacian。用於管狀表面,避免凹陷成最小曲面。

p̕ᵢ = pᵢ + ∆∆pᵢ

Feature-preserving Mesh Smoothing

保留形狀的平滑化。點數不變,抹平表面,保留稜角。

fuzzy median filter:法向量套用濾波器,然後更新點座標。

《fuzzy vector median-based surface smoothing》
nᵢ⁎ = median(adj(nᵢ))
n̕ᵢ = sum { w(nᵢ⁎,nⱼ) nⱼ } ÷ sum w(nᵢ⁎,nⱼ)
   j∈adj(i)               j∈adj(i)
where w(n⁎,nⱼ) = gauss(‖n⁎ - nⱼ‖)

bilateral filter:點分別投影到每個面。新點是垂足們的加權平均數,權重由bilateral filter算得。

《non-iterative, feature-preserving mesh smoothing》
p̕ᵢ = sum { w(f,pᵢ) projf(pᵢ) } ÷ sum w(f,pᵢ)
      f                           f
define w(f,pᵢ) = area(f) gauss1(‖centroid(f) - pᵢ‖) gauss2(‖projf(pᵢ) - pᵢ‖)

Curvature-based Mesh Smoothing【尚待確認】

曲率的平滑化。「和諧能量-保角能量=面積」推廣成主曲率。

bending energy:主曲率平方和盡量小。

Leif Kobbelt "Discrete Fairing"  (1997)
https://www.graphics.rwth-aachen.de/publication/03168/

Willmore energy:主曲率差平方盡量小。保角變換。

Discrete Willmore Flow (2005)
robust fairing via conformal curvature flow (2003)
https://www.cs.cmu.edu/~kmcrane/Projects/ConformalWillmoreFlow/

Hessian energy:二次微分矩陣的相關數盡量小。主成分分析?

A Smoothness Energy without Boundary Distortion for Curved Surfaces (2020)
https://odedstein.com/projects/curved-hessian/
1. min distance           min x*Lx
2. min area               min x*L_cotx  = min curvature
3. min curvature variance min x*L_cot^2x
"implicit fairing of irregular meshes using diffusion and curvature flow"(1999)
4. min willmore energy   min (k1 - k2)^2    conformal! (2005)
5. min xxx energy        min (k1^2 + k2^2)
Leif Kobbelt "Discrete Fairing"  (1997)
6. min bilaplacian energy: 1/2 integral |laplace u|^2 dx ==x=> ||grad u||^2
7. min hessian energy:     1/2 integral Hu:Hv dx  ===>   trace(Hu^t Hv)
https://odedstein.com/projects/curved-hessian/

Mesh Consolidation

鞏固。貼齊、拉直、擺正。

optimization:形狀、距離、平滑,三種能量最佳化。函式庫

Mesh Repairing

修補。有人彙整了各種函式庫

gap / hole / non-manifold edge / self-intersection
polygon soup / handle

《Robust Repair of Polygonal Models》

Mesh Hole Fillng

補洞。

1. find hole
2. triangulation (dynamic programming)
2-1. min area triangulation
2-2. min-max dihedral angle triangulation
2-3. min weight triangulation
3. refine
4. fair

《Filling Holes in Meshes》

Mesh Cutting

切割。剪開網格,形成邊界。

1. conformal parameterization
2. distortion measure for pairwise shortest path
3. minimum spanning tree

《surface-based cut construction for planar graph》

Mesh Modeling(Under Construction!)

Mesh Skeleton Extraction

剝皮剔骨。

laplacian smoothing:收縮邊直到變成骨架。

《Skeleton Extraction by Mesh Contraction》2008

《Point Cloud Skeletons via Laplacian Based Contraction》

《3D Skeleton: A State-of-the-Art Report》

Mesh Cage Generation

穿衣戴帽。

《Interactive Cage Generation for Mesh Deformation》2017

《Skeleton Based Cage Generation Guided by Harmonic Fields》2019

Mesh Deformation

形變。維持模型的基礎結構,改變模型的形狀。

n-point deformation:網格頂點當作控制點,直接形變。
skeleton deformation:額外建立樹狀骨架,端點是控制點。又稱pose space deformation。
cage deformation:額外建立網格框架,頂點是控制點。
[skeleton deformation]
yi = sum wij mj xi
     i,j

x: mesh vertex
m: bone vertex
w: weight such that sum wij = 1 for each i
                     j
y: skin vertex

[delta mush]
1. laplacian smoothing: x' = (I - aL)^k x
2. rigid alignment: min sum (I - aL)^k || Fj xi - yi ||^2
                     F   i

Mesh Parameterization

參數化。網格表面建立座標系統,網格每一處設定獨一無二的座標(參數)。方便貼圖、組裝。

方法是deformation。正向變換,攤平網格表面,形成方形或其他形狀,貼上座標系統,貼上圖片,反向變換。

1. deformation + embedding: 攤平網格
2. interpolation: 建立正對應
3. texture mapping
http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/13_Parameterization2.pdf
spatial method:
(fixed boundary/dirichlet) minimize sum of all pairs energy: laplacian matrix
(free boundary/neumann)    pin 2 points, matrix size * 2
spectral method:
minimize sum of all-pairs energy + constraint sum of weight: Laplacian Eigenmap
all pairs geodesic shortest path: Isomap/MDS
circle patterns
https://www.numerical-tours.com/matlab/meshdeform_2_parameterization_sphere/

diffusion = dirichlet energy minimization algorithm
  (aka gradient descent)

3d diffusion + spherical projection = spherial diffusion
  (aka Projected Gradient Method)

Mesh Remeshing

網格重建。重新建立點與邊。

1. triangular mesh
1-1. surface-based: isotropic remeshing
     edge operation + normal smoothing (optimization)
1-2. parameterization-based: delaunay remeshing
     deformation + coordinate interpolation (voronoi diagram)
2. quad-dominant mesh
https://zhuanlan.zhihu.com/p/104107745
Instant Field-Aligned Meshes
http://igl.ethz.ch/projects/instant-meshes/

1. 兩種轉法 (轉是指陀螺旋轉)
   (1) 先轉兩個法向量的法向量(cross),再轉法向量
   (2) 同時轉兩個法向量,找空間最小夾角

2. mesh ---> graph
   (1) sample ---> vertex,已知法向量n,不知表面向量o,不知表面向量的預設轉角k
   (2) neighbor ---> edge,所有兩兩點對的夾角平方誤差總和最佳化
   (3) 預設轉角k被離散化了,360度看是要幾等分都可以
   (4) k看起來是網格的邊的相位,o看起來好像是梯度。
   (5) k是切面的座標軸的角度差,o是切線,可以用來做levi-civita connection。
  (6) 頗像panorama warping。http://kaiminghe.com/sig13/

3. 變成稀疏大矩陣,用gauss-seidel遞推法硬幹。仿照mesh smoothing的概念,會收斂

4. 然後又加了一個位移量p,說是可以處理mesh的折痕...這是為啥?

Mesh Editing

編輯。調整網格形狀,根據筆劃。

A Sketch-Based Interface for Detail-Preserving Mesh Editing
https://www.eecs.tu-berlin.de/institut_fuer_technische_informatik_und_mikroelektronik/cg_archiv/menue/research/projects/sbm/

Mesh Sculpting

雕刻。調整網格形狀,特定位置凸起或凹陷。

Shape Analysis(Under Construction!)

Shape Description

描述。將形狀獨特之處寫成數值,以供辨識比對。

point feature histogram (PFH):每個點的半徑範圍之內,每組點對求得描述。針對一組點對,建立垂直座標軸,計算法向量的夾角、扭轉角,得到三種角度。360°等分成5個箱子,三種角度總共5³ = 125個箱子。一組點對投票給一個箱子。125個數字,依序串成一串,當作特徵描述。

fast point feature histogram (FPFH):每個點的半徑範圍之內,不算所有點對,只算中心點到其餘點。並且求得加權平均數,權重是距離倒數。節省計算時間,犧牲細膩程度。

FPFH(pij) = PFH(pij) + 1/k sum PFH(pik) / dik
                         k in adj(i)

Shape Feature Extraction

特徵擷取。將形狀獨特之處揭露出來。

Shape Correspondence

對應。找到相同特徵。

https://gfx.cs.princeton.edu/pubs/Kim_2011_BIM/
https://gfx.cs.princeton.edu/pubs/Lipman_2009_MVF/
http://imagine.enpc.fr/~groueixt/3D-CODED/

Shape Alignment / Shape Matching

對齊。找到給定部件。

Shape Segmentation

分割。區隔部件,找到邊界。

Shape Approximation

近似。簡化形狀。方便實施變換、碰撞偵測。

Shape Interpolation

內插。找到形狀變化過程。

Shape Synthesis(Under Construction!)

3D點雲 ⇨ 3D模型(Surface Generation)

生成。點雲變表面,並且參數化,並且貼紋理。

http://imagine.enpc.fr/~groueixt/atlasnet/

2D線條 ⇨ 3D模型(Sketch-based Modeling)

繪製曲線,產生表面。

2D圖片 ⇨ 3D模型

Model Fabrication(Under Construction!)

Model Fabrication

Model Optimization

Model Compositing

合成。組裝模型。

Model Decomposition(Model Segmentation)

分段。區分模型的各個部件。

http://cg.cs.uni-bonn.de/en/projects/point-cloud-processing-with-primitive-shapes/
Dapper: decompose-and-pack for 3D printing

Model Retargeting

重新定位。調整並組裝模型的各個部件。

Model Blending

合成。剪接模型。

Model Boxelization

Model Assembling

Scene Modeling(Under Construction!)

Scene Synthesis

生成。家居擺設。

Scene Segmentation

分割。找出模型。

Scene Labeling

標記。鑑定技能。

目前的做法是圖片辨識。