Model（Shape）（Surface）

模型。物體的造型。

Scanning

掃描。實體變模型。

Modeling

產生模型。有兩種方式：

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

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

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

Printing

列印。模型變實體。

Rendering

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

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

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

屬於Graphics領域，容後介紹。

Animation

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

屬於Animation領域，容後介紹。

使用C/C++處理模型

C與C++本身沒有處理模型的函式庫。大家傾向直接使用現成的函式庫，例如Open3D、libigl、PCL、CGAL、OpenMesh。

使用Python處理模型

PyMeshLab容易上手。它是軟體MeshLab幕後的函式庫。

使用HTML與JavaScript處理模型

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

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

一、讀取模型。首先利用fetch()載入模型檔案，然後自行剖析檔案內容，擷取模型數據，存入陣列。

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

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

<script> var model = {}; fetch('bunny.obj') .then(response => response.text()) .then((data) => { loadmodel(data, model); buildmodel(model, scalar); draw(model); }); function loadmodel(data, model) { model.points = new Array(); model.faces = new Array(); var lines = data.split('\n'); for (let line of lines) { if (line.length == 0 || line[0] == '#') continue; var s = line.match(/\S+/g); switch (s[0]) { case 'v': model.points.push([parseFloat(s[1]), parseFloat(s[2]), parseFloat(s[3])]); break; case 'f': model.faces.push([parseInt(s[1]) - 1, parseInt(s[2]) - 1, parseInt(s[3]) - 1]); break; } } } </script>

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

<script> var scalar = 1000; function translate(p, v) { p[0] += v[0]; p[1] += v[1]; p[2] += v[2]; } function scale(p, v) { p[0] *= v[0]; p[1] *= v[1]; p[2] *= v[2]; } function buildmodel(model, scalar) { var max = [-1e9, -1e9, -1e9]; var min = [+1e9, +1e9, +1e9]; for (var i=0; i<model.points.length; i++) { max[0] = Math.max(max[0], model.points[i][0]); max[1] = Math.max(max[1], model.points[i][1]); max[2] = Math.max(max[2], model.points[i][2]); min[0] = Math.min(min[0], model.points[i][0]); min[1] = Math.min(min[1], model.points[i][1]); min[2] = Math.min(min[2], model.points[i][2]); } var center = [0,0,0]; center[0] = -(max[0] + min[0]) / 2; center[1] = -(max[1] + min[1]) / 2; center[2] = -(max[2] + min[2]) / 2; for (var i=0; i<model.points.length; i++) { translate(model.points[i], center); scale(model.points[i], [-scalar,-scalar,-scalar]); } } </script>

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

<canvas id="PointCloud" width="200" height="200"></canvas> <script> var canvas = document.getElementById("PointCloud"); var ctx = canvas.getContext("2d"); ctx.fillStyle = 'rgb(192,0,0)'; var focal_length = 950; var distance = 1000; var screen_center = [canvas.width/2, canvas.height/2, 0]; function project(p, focal_length) { p[0] = p[0] * focal_length / p[2]; p[1] = p[1] * focal_length / p[2]; p[2] = focal_length; } function draw(model) { ctx.clearRect(0, 0, canvas.width, canvas.height); for (let i=0; i<model.points.length; i++) { var p = model.points[i]; translate(p, [0,0,distance]); project(p, focal_length); translate(p, screen_center); ctx.fillRect(p[0],p[1],2,2); } } </script>

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

使用現成軟體處理模型

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

CAD軟體：Tinkercad、OpenSCAD、AutoCAD、FreeCAD、SolidWorks、Solid Edge、Creo Parametric。

BIM軟體：SketchUp、Revit。介紹文章。

動畫軟體：Blender、3ds Max。

建模軟體：Rhinoceros 3D、Alias。

雕塑軟體：MeshLab、MeshMixer、ZBrush、3D-Coat、Nomad Sculpt。

檢視軟體：Microsoft 3D Viewer、Online 3D Viewer、F3D。

常見的檔案格式：OBJ、X3D。讀取各種檔案格式的函式庫：assimp。

常見的測試模型：Stanford bunny、Armadillo、David、……。詳細列表請見維基百科。

Point Cloud（Surfel）

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

struct Point {float x, y, z;} p[10000];

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

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

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

Mesh

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

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

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

struct Point {float x, y, z;} p[10]; struct Triangle {int p1, p2, p3;} t[20]; //struct Triangle {Point* p1, *p2, *p3;} t[20];

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

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

Parametric Surface

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

「參數曲面」。三個連續函數分別對應三個座標軸的座標值，一組參數得到一個點。

float x(float u, float v) {return u*u + v*v;} float y(float u, float v) {return v*v - u - 1;} float z(float u, float v) {return u + v;} typedef float (*ParametricFunction)(float, float); struct Surface {ParametricFunction x, y, z;} s[20];

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

Bézier Surface

參數曲面有一個經典特例是Bézier surface，以及進階版本NURBS surface，可以透過控制點調整模型形狀。

struct Point {float x, y, z;} p[10]; struct BezierPatch {Point* p[4][4];} b[20];

Voxel

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

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

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

float intensity[10][10][10]; float boundary = 30f;

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

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

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

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

Isosurface（Implicit Surface）

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

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

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

float intensity(float x, float y, float z) { return pow(x, 3.) + pow(y, 3.) + pow(z, 3.); } float boundary = 125f;

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

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

Distance Field（Signed Distance Function）

等值曲面有一個經典特例是distance field，可以產生模型的聯集、交集、補集。詳情請參考isosurface rendering。

float cx = 0f, cy = 0f, cz = 0f; float radius = 5f; float signed_distance_function(float x, float y, float z) { return hypot(x - cx, y - cy, z - cz) - radius; }

Point Cloud Registration

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

iterative closest point (ICP)：請參考alignment。

globally optimal ICP (Go-ICP)：branch and bound枚舉剛體變換。

Generalized-ICP (GICP)：一、誤差區分為點到點、點到面、面到面，採用後者。二、點雲資料結構採用KD-tree，以此取得鄰居、構造平面、求得法向量。三、每個點套用常態分布Gaussian distribution，中心強外圍弱。面到面變成了混合分布到混合分布。

voxelized GICP：KD-tree改成uniform grid，誤差改成格到格。論文作者誤植為體素。

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。程式碼。

screened Poisson surface reconstruction：點到面距離。

iterative Poisson surface reconstruction：

Frankot–Chellappa algorithm：一、梯度套用平滑濾鏡。二、解Poisson equation採用快速傅立葉轉換。

Mesh ⇨ Voxel

《An Accurate Method for Voxelizing Polygon Meshes》

Voxel ⇨ Mesh

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

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

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

簡介

調整網格的點邊面。

網格的基本操作

   action          terminology    algorithm
--------------------------------------------------------
1. vertex move   | smoothing    | Laplacian smoothing
2. edge flip     | refinement   | Delaunay triangulation
3. edge contract | simplication | quadric error metric
4. edge split    | subdivision  | sqrt(3) ...

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ᵢ

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  ===>   tr(Hu^t Hv)
https://odedstein.com/projects/curved-hessian/

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ᵢ‖)

Sketch-based Mesh Smoothing【尚待確認】

基於筆劃的平滑化。調整網格形狀，根據筆劃。

A Sketch-Based Interface for Detail-Preserving Mesh Editing
https://igl.ethz.ch/projects/Laplacian-mesh-processing/sketch-mesh-editing/index.php

Mesh Sculpting

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

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 Zippering

拉鍊。兩個網格表面，邊緣相互黏貼，併成一個網格表面。

《Zippered Polygon Meshes from Range Images》

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)

Surface 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的折痕...這是為啥？

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)

signature of histograms of orientations (SHOT)：

Shape Description

描述。將形狀獨特之處寫成數值，以供辨識比對。位移旋轉後，數值需相同。

principal component analysis：憑感覺亂搞。座標軸不實用，中心則可用。

shape histogram：選定中心，同心圓、放射線。

spherical harmonics decomposition：選定中心，分解成球諧函數。

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

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

3D點雲 ⇨ 3D模型（Surface Generation）

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

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

2D線條 ⇨ 3D模型（Sketch-based Modeling）

繪製曲線，產生表面。

2D圖片 ⇨ 3D模型

Model Simplication

產生新的Graphics Pipeline。

https://research.nvidia.com/publication/2021-04_Appearance-Driven-Automatic-3D
https://users.cg.tuwien.ac.at/zsolnai/gfx/photorealistic-material-learning-and-synthesis/

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

合成。剪接模型。

Constructive Solid Geometry (CSG)

Model Boxelization

Model Assembling