[Beady2012](https://www.is.ocha.ac.jp/~yuki/papers/beady_siggraph2012.pdf)
# 第五章 演算法
**1. design model**
* 
* 邊代表珠子
* 邊長差不多
* 每個頂點 對應到 一組連接周圍珠子的綠色線段
**將3D三角網格模型變成design model的方法**:
* 近六邊形網格
* 減少網格 > 邊長變均勻 > 三角形對偶變成六邊形
* 減少網格:
1. 移除最短的邊線
2. 使用 [Markosian et al. 1999]將偏移量設0 > 均勻分布的頂點的網格
3. 將輸入的網格( skeleton mesh)複製一次稱為:skin mesh > 將skin vertices移動到周圍頂點的中心 > 更新skeleton mesh的連接性 **5.1節**
2. **structure model**
*  **5.2節**
* 在design model中的每個面的每個頂點 + **wire edge**
* 每個degree為n的頂點變成 n個wire edge(綠色的) 和他們之間的n個新頂點，新頂點(紫色)的位置:原始頂點的稍微移向相應的邊線(就像分成三份)
* 將連接兩個wire edge 和每個珠子邊 > 線(wire)會通過珠子兩次
* 將尾巴(**linear chains**)連接到其中一個wire edge ，share a vertex in the design model在design model中分享頂點
* wire path通過珠飾的次數要盡量少(2次、除了尾巴之外)
* ==wire path使用數量最少==
* wire path要讓串珠穩定 >> 當wire path ==將珠子固定成一個完整的面== 時就會穩定
> when the position of the bead is stably fixed to a specific location by
the wires; that is, the bead belongs to a completed face
---
* **global wire path連接每個wire edge、並通過珠子兩次**
> meets all wire edges once and all bead edges twice.
* **進到珠子裡的線必須從珠子的另一端走出來***
> a wire going into a bead should go out from the other
side of the bead.
* **將珠子視為頂點 > degree(珠子)=4，保證存在Eular path**
1. 存在多種Eular path，但任意一種迴路在創建過程中可能會產生不穩定的狀態
2. 使用**face strip** : wire path完成，以面為單位進行wire path
3. 如果模型不能完整地被單個strip 覆蓋，就把剩餘的面當作分支(**branch** )，再放上wire path讓它偏離strip、造訪分支中的面再走回(go back)到strip
4. branch會導致珠子不穩定，因此branch長度只能為1
5. 將剩餘的面創造獨立的face strip，直到strips 和 他們的branchs覆蓋所有的面。ex.第一個strip覆蓋了大部分表面，額外的strip則覆蓋了突出部分，例如耳朵和手臂。
6. 對於沒有任何分支(branch)的**單一面帶single face strip** :把design model的面轉換成頂點vertices後 在對偶圖上找到 ==**Hamiltonian path**== 
* 每點恰走一次，走回起點
* NP問題，不保證有解答
:::info
VS. **Eular path:**
* 每邊走恰走一次，
* 無向圖:起終點degree()=odd
* 
:::
7. 解方:建構一些帶有分支(branch)的spanning tree
8. strip 從基礎面(base face)開始向鄰居面(**使boundary length最小的**)擴展，慢慢爬過模型全部的面 :secret:
9. **boundary length**:目前face srtip(黃色的蛇)與剩下沒爬過的面 的邊長總和(綠線的長度)
> The boundary length is given as the total length of the edges between the current face strip and the remaining faces.
10. 能讓串珠更緊湊，易於手工串珠
11. 卡住死胡同時，使用 **回朔backtracking** ； 從所有的面貪婪擴展greedy expansion search 並選擇最好的結果
==**spanning tree**== :
最小連接樹:把所有點連起來、權重由最小的邊開始+ 
3. **beadwork model**
* 
# 老師說
### 一、把design model變成structure model ; 做出wire edge
**01. 讀檔:把penguin.obj拖到程式裡、設定3D環境**
```p=
PShape penguin;
void setup(){
size(400,400,P3D);
String[] lines=loadString("penguin.obj");//用字串儲存 頂點、面的資訊
penguin=loadShape("penguin.obj");
}
void draw(){
background(#FFFFF2);
lights();
pushMatrix();
translate(width/2,heigh/2); //將模型移到視窗的中心
scale(500);
rotateY(radians(mouseX));//弧度
//若讓模型直接隨滑鼠X軸移動會轉太快
shape(penguin);
popMatrix();
}
```
企鵝模型可以隨著滑鼠左右旋轉了
模型的資訊
**02. 分點面:將模型資訊分割，儲存成面與頂點**
準備放頂點與面的ArrayList:長度不固定、可以放不同類別的資料
```p=
ArrayList<PVector>vertices;//放頂點(PVector)
ArrayList<AarrayList<Integer>>faces;
//放面 哪個面(面裡的頂點(頂點的編號) ) ex.face5有20 15 16 21這4個點
```
準備好頂點與面
```p=
void prepareVertexFaces(String []lines){
vertices=new ArrayList<PVector>();//創建new
faces=new ArrayList<ArrayList<Integer>>)();
for(int i=0;i<lines.length;i++){
String line=lines[i];//讀進每一行
char c=lines.charAt(0);//每一行的第一個字母p or v
if(c=='v'){
String[]nums=split(line," ");//用空格分割，把每個字元裝入nums裡ex.-0.1900004898055382
PVector p=new PVector(float(nums[1]),float(nums[2]),float(num[3]));//x,y,z
vertices.add(p);
}else if(c=='f'){
String[]nums=split(line," ");//ex.6,11,16,15,10
ArrayList<Integer>temp=new ArrayList<Integer>();
//裝頂點編號ex.6,11,16,15,10
for(int k=0;k<nums.length;k++){//nums.length有幾個頂點，從第1個頂點開始
temp.add(int(nums[k]));//把頂點存入temp
}
faces.add(temp);//面由頂點組成，存入一串頂點編號到faces
}
}
}
```
**03. 生成新頂點:在兩頂點間建新的頂點**
wire edge綠色線段的頂點
```p=
ArraryList<PVector>newVertices;
```
for-each循環
```p=
void generateNewVertex(){
newVertices=new ArrayList<PVector>();
for(ArraryList<Integer>face:faces){//對每一面
int N=face.size(); //有幾個頂點
for(int i=0;i<N;i++){
Integer k1=face.get(i),k2=vertices.get(k2-1);
//倆倆抓點，這個和下一個 取餘數避免超過
//抓出整個模型的頂點編號
PVector p1=vertices.get(k1-1),p2=vertices.get(k2-1);//取出頂點資訊，模型頂點編號從0開始 所以要減一
PVector center=PVector.add(p1,p2).div(2);//兩點相加除2，新頂點在兩點中間
newVertices.add(center);//存入新頂點
}
}
}
```
把面內的頂點編號，方便找(原本是整個模型的頂點編號>>面的頂點編號)
```get(i)``` vs. ```get((i+1)%N)```倆倆抓點
```get(i%N)``` vs. ```get((i+1)%N)``` 結果都一樣
在draw()裡把球畫在center
```p=
for(PVector center:newVertices){
pushMAtrix();
translate(center.x,center.y,center.z);
noStroke();//不要描邊
sphere(0.01);
popMatrix;
}
```
找到頂點中心
**04. 伸縮；可設定wire edge頂點在邊上的比例**
```p=
void generateNewVertex(float ratio){
for(ArrList<Integer>face:faces){
for(int i=0li<N;i++){
PVector p1_10=PVector.mult(p1,ratio);//乘法P1*ratio
PVector p2_10=PVector.mult(p2,ratio);
//newp1=(p1*ratio+center)/(radio+1)
PVector newp1=PVector.add(p1_10,center).div(ratio+1);
//newVertices.add(center);
newVertices.add(newp1);
newVertices.add(newp2);
}
}
}
```
老師的算法
**有多種算法;看算式決定程式的寫法**
<算法二>ratio=[0,1]
結果
### 二、strip走過模型的每一面，以面為單位進行串珠
**01. 讀檔:把設計好的ㄇ字型立方體放進來**
**```radians```** 弧度
**```frameCount```** 幀率
讓模型隨著算圖的速度&弧度自己旋轉
```p=
PShape cube;
void setup(){
size(500,500,P3D);
cube=loadShape("cube.obj");
}
void draw(){
beacground(#FFFFF2);
lights();
translate(with/2,height/2);
retate(radians(frameCount));
shape();
}
```
**02. 讀點面:**
準備好資料結構 宣告、new創建
```p=
ArrayList<PVector> vertices=new ArrayList<PVector>();
ArrayList<ArrayList<Integer>>faces=new ArrayList<ArrayList<Integer>>();
void setup(){
String[]lines=loadStrings("cube.obj");
prepareVertexFaces(lines);
}
```
一樣的方式讀點面
```p=
void prepareVertexFaces(String[]lines){
//把一行字串讀進lines
for(int i=0;i<lines.length;i++){
//在lines的長度裡，從第一行開始
Char c=lines.charAt(0);//抓每行的第一個字元(從0開始數)
if(c=='v'){//是頂點的話
String []nums=split(line,' ');//去掉空白組成新的字串
vertice=PVector(float(nums[1]),float(nums[2]),float(nums[3]));
//新字串(從0開始數)的第1、2、3分別是點的x,y,z座標，把字串轉成浮點數
vertices.add(vertice);
}else if(c=='f'){//是面的話
String []nums=split(line,' ');//存的是字串ex.nums[2]=13
for(int k=1;k<nums.length;k++){
//在字串
ArrayList<Integer>face=new ArrayList<Integer>();//放單一個面的頂點資料
face.add(int(nums[k]));//把頂點編號存到face
}faces.add(face);
}
}
}
```
**03. 找相鄰的面:有共用頂點**
```p=
int findNeighborFace(int v1,int v2,int myself){
for(int f=0;f<faces.size();i++){
if(f==myself)continue;//跳過自己
ArrayList<Integer>face=faces.get(f);//放那面的頂點
int count=0;//相同頂點的數量
for(int i=0;i<face.size();i++){
//在那面中，
int v=face.get(i);//的頂點，從0開始數
if(f==v1 || f==v2)count++;
}
if(count==2)return f;
}
return -1;//找不到
}
```
**04. 標記面:找到某面、用鍵盤指定某一面並上色**
因為深度一樣 重疊所以會閃爍
用已知的頂點，重新畫面
(就不用秀模型了```//PShape cube;``` ```//cube=loadShape("penguin.obj");```)
```p=
void drawFace(ArrayList<Integer>face){
beginShape();
for(Integer i:face){//對每一個face內的頂點序號 i
print(i+" ");//秀出 每面的頂點
PVector v=vertices.get(i-1);//obj的頂點從1開始 但程式是從0開始
vertex(v.x,v.y,v.z);//在beginShape裡面畫面
}
println();
endShape();
}
```
用鍵盤控制
```p=
int FaceID=1;//哪個面
void KeyPressed(){
if(key==0)FaceID=0;
if(key==1)FaceID=1;
if(key==2)FaceID=2;
if(key==3)FaceID=3;
}
```
上色
```p=
void draw(){
fill(#FF0000);
deawFace(faces.get(faceID));
}
```
**05. 找鄰居面上色**
準備鄰居面
```p=
ArrayList<Integer>adjacentFaces=null;
void setup(){
adjacentFaces=findAllAdjacentFaces(faceID);
}
```
輸入面的編號(faceID)，找到此面的所有鄰居(neighbor)
```p=
ArrayList<Integer>fingAllAjacentFaces(int faceID){
ArrayList<Integer>all=new ArrayList<Integer>();//放鄰居面，放鄰居(面的編號)
ArrayList<Integer>face=faces.get(faceID);//此面的頂點
for(int i=0;i<face.size();i++){
//一一比對此面的頂點中，有沒有(鄰近的兩個頂點)和誰共用 v1 v2//v2 v3//v3 v4
int i2=(i+1)%face.size();//避免超過數量
int neighbor=findNeighborFace(face.get(i),face.get(i2),faceID);
//輸入兩頂點 有沒有和某面相鄰，回傳鄰居編號
if(neighbor!=-1)all.add(neighbor);//有找到相鄰=是鄰居
}
return all;//回傳所有鄰居面的編號
}
```
用鍵盤挑選某一面、控制faceID
```p=
void KeyPressed(){
adjacentFaces=findAllAjacentFaces(faceID);
//所有鄰居的編號
}
```
挑某一面(紅色)、將他的鄰居畫上綠色
```p=
void draw(){
fill(#FF0000);//紅色
drawFace(faces.get(faceID));//輸入某面 畫某面
fill(#00FF00);//綠色
for(Integer neighbor:adjacentFaces){//對此面(faceID)的 所有鄰居面
drawFace(faces.get(neighbor));//畫面
}
}
```
**06. 把企鵝模型套進來**
把企鵝模型拖進來
```c=
void setup(){
cube=loadShape("penguin.obj");
String[]lines=loadString("penguin.obj")
}
void draw(){
retateY(radians(mouseX));//隨滑鼠的移動而轉動
noStroke();//不要邊線
scale(500);//企鵝太小 要放大
//shape(cube); //不要這行 重新用drawFace用頂點畫面
//就不會重疊閃爍了
//控制顏色
for(int fi = 0; fi < faces.size(); fi++){//從第一個面開始到全部的面
if(fi==faceID) fill(#FF0000);//遇到自己面(鍵盤控制選的面) 紅色
else if(adjacentFaces.indexOf(fi)>=0) fill(#00FF00);
//如果面是鄰居面(回傳值非-1) 綠色
else fill(200); //否則銀灰色
drawFace( faces.get(fi) );//把面畫出來 不用shape(cube)了
}
}
```
**07. 鄰居的鄰居:找隨機的相鄰面 延伸過去**
準備secondNeighbors、faceID2
用鍵盤abcd鍵控制
```c=
ArrayList<Integer>secondNeighbors=null;
int faceID2=-1;
void keyPressed(){
//按A跳到下一個面 不能超過 所以取餘數
if(key=='a')faceID=(faceID+1)%faces.size();
//按B回到上一個面 減一個=加上(全部數量-1) 1234 3-1=2=(3+3)%4
if(key=='b')faceID=(faceID+faces.size()-1)%faces.size();
if(key=='c'){
faceID2=adjancentFaces.get(0);//當前面的第0個鄰居
//找到當前面(faceID)的 鄰居(faceID2)的鄰居
secondNeighbors=findAllAjacentFaces(facesID2);
}
if(key=='d'){
faceID2=adjancentFaces.get(1);//當前面的第1個鄰居
secondNeighbors=findAllAjacentFaces(facesID2);
}
}
```
上色
```c=
void draw(){
for(int fi=0;fi<faces.size();fi++){
if(fi==faceID)fill(255,0,0);//當前面 紅色
else if(fi==faceID2)fill(255,255,0);//鄰居面 黃色
//如果是鄰居 綠色
else if(adjacentFaces.indexOf(fi)!=-1) fill(#00FF00);
//如果存在鄰居的鄰居、是鄰居的鄰居 紫色
else if(secondNeighbors!=null && secondNeighbors.indexOf(fi)!=-1)fill(255,0,255);
else fill(255);//其他面
drawFace( faces.get(fi) );
}
}
```
更好轉動 更多視角
```c=
float rotX=0,rotY=0;
void mouseDragged(){
rotX+=mouseX-pmouseX;
rotY-=mouseY-pmouseY;
}
void draw(){
rotateY(radians(rotX));//繞Y軸選轉
rotateX(radians(rotY));//繞X軸選轉 (所以不一樣)ritateX--rotY
}
```
**08. 找到所有鄰居的鄰居:紫色**
```c=
```
Sign in with Wallet
Connect another wallet