Model

Model(Shape)(Surface)

模型。物體的造型。

Scanning

掃描。實體變模型。

Modeling

產生模型。有兩種方式:

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

二、使用軟體,操作滑鼠、繪圖板,創作自己心儀的物體形狀。知名軟體如SketchUp、AutoDesk系列作。

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

Printing

列印。模型變實體。

Rendering

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

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

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

屬於Graphics領域,容後介紹。

Animation

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

屬於Animation領域,容後介紹。

使用C/C++處理模型

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

使用現成軟體處理模型

SketchUpAutoCADRhinoceros 3D

模型的檔案格式X3D

課程資料

https://www.coursera.org/learn/interactive-computer-graphics
http://cs621.hao-li.com
http://kevinkaixu.net/
https://www.cs.cmu.edu/~kmcrane/
http://www.geometrysummit.org/summerschool/presentations.html
http://homes.cs.washington.edu/~seitz/talks/3Dhistory.pdf

Model Data Structure

Point Cloud(Surfel)

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

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

大家習慣將點雲轉換成其他資料結構,減少資料量,減少處理時間。

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

Point Cloud Registration

登記。多台相機於多個位置拍攝相同景物,各得一群點雲。把所有點雲整合到同一個世界座標系,校正誤差。

請參考對齊的演算法。

Point Cloud ⇨ Mesh

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

Ruppert's algorithm:美化既有的Delaunay triangulation。

Poisson surface reconstruction:一、point cloud ⇨ voxel:體素數值內1外0。點雲法向量等於體素梯度,再以體素梯度求解體素數值,即是解Poisson equation。二、voxel ⇨ mesh:體素儲存於八元樹,套用八元樹版本的marching cube。程式碼與模型

Voxel ⇨ Mesh

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

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

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

Parametric Surface ⇨ Mesh

變成三角形:每一個曲面切成n×n格,每一格沿對角線切成兩個三角形,就這麼簡單。越多格,越細膩,越逼真。

變成平坦四邊形:我不知道怎麼做。

Model Editing(Under Construction!)

Mesh Subdivision

分割。增加點數。內插。

https://en.wikipedia.org/wiki/Subdivision_surface
http://www.cs.kent.edu/~zhao/acg13/lectures/Subdivision.pdf
Loop subdivision
Catmull-Clark subdivision
Doo-Sabin subdivision
Butterfly subdivision
sqrt(3) subdivision
PN triangle

Mesh Simplification(Mesh Decimation)

簡化。減少點數。縮邊。

Garland-Heckbert method

Mesh Smoothing

平滑。移動點。

http://www.cin.ufpe.br/~tlam/detail%20preserving%20mesh%20edition.pdf
Taubin smoothing
FVM smoothing

模型的數學運算:Laplace-Beltrami Operator

曲面之梯度的散度。

https://www.slideshare.net/gpeyre/mesh-processing-course-mesh-parameterization

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

Discrete Differential-Geometry Operators for Triangulated 2-Manifolds
各種定義

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

多變量函數用在曲面:函數輸入是曲面的參數座標。

https://graphics.stanford.edu/courses/cs468-13-spring/schedule.html
http://webcourse.cs.technion.ac.il/236629/Winter2015-2016/ho_Lectures.html
http://www.cs.cmu.edu/~kmcrane/
http://fernandodegoes.org/
https://graphics.tudelft.nl/Publications-new/2016/VCDPBHB16/
http://www.geometrysummit.org/summerschool/presentations.html
http://www.geometrie.tugraz.at/sgp2015/gradschool.php

Mesh Parameterization

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

harmonic embedding。

1. remeshing(embedding): 攤平網格
2. interpolation: 建立正對應。
3. texture mapping
http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/13_Parameterization2.pdf
http://www.riken.jp/brict/Yoshizawa/Research/Param.html
spatial method:
(fixed boundary/dirichlet) minimize sum of all pairs energy: laplace 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 
mean value
conformal
ABF++
circle patterns
MIPS
stretch
CPMS
Ricci Flow

Mesh Remeshing

重新網格化。重新離散化,重新建立點與邊。

1. optimization: modify edge
2. parameterization: voronoi diagram

Mesh Alignment

對齊。甲網格實施相似變換,盡量等於乙網格。

Mesh Deformation

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

兩種方式:一、網格頂點直接形變。二、額外建立網格,內插座標系統來形變。

二維:整個面每一點都形變,必須計算面積,形成cot。大家將cot視作laplace matrix的權重,雖然很奇怪但是很簡潔。

三維:角椎對面積微分,得到cot。角錐底部不平坦。

point difference = vertex laplace

[PP93] Computing Discrete Minimal Surfaces and Their Conjugates

piecewise linear deformation:

min sum Area_t ‖ xi' - Tt(xi) ‖²
     t

min sum sum 1/4 cot_ij ‖ (xj' - xi') - Tt(xj - xi) ‖²
     t   3

min sum ‖ Laplace_cot(xi') - Ti(Laplace_cot(xi)) ‖²
     i

Mesh Consolidation

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

Mesh Fairing

平滑化。維持模型的基礎結構,撫平模型的形狀。

Mesh Skinning

剝皮。找出骨架。

http://skinning.org/

Shape Analysis(Under Construction!)

Shape Correspondence

對應。兩個模型找到相對應的部件。

http://imagine.enpc.fr/~groueixt/3D-CODED/

Shape Alignment / Shape Matching

對齊。找到給定的部件。

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

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

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

2D線條 ⇨ 3D模型

繪製曲線,產生表面。

2D圖片 ⇨ 3D模型

Model Fabrication(Under Construction!)

Model Fabrication

Model Optimization

Model Compositing

合成。組裝模型。

Model Blending

合成。剪接模型。

Model Segmentation(Model Decomposition)

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

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

Model Retargeting

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

Model Carving

Model Boxelization

https://www.disneyresearch.com/project/boxelization/

Model Assembling