# 台科電腦圖學導論Project 2: Maze Visibility and Rendering
Last Update : 2023-02-19
:::warning
閱前注意事項 : **請勿抄襲本專案的程式碼**，賴教授跟我反應過有很多人抄襲我的code，因此希望大家是透過我的文字理解原理架構，再自己重寫一遍，實作上有任何問題都可以Email([e-mail])，千萬不要直接抄，如果看完還是不懂，可以約時間用Discord討論一下。
:::

### GITHUB連結:https://github.com/frakw/NTUST_COMPUTER_GRAPHICS


這裡記錄著我遇到的一些坑，大部分是講一些程式架構跟coding注意事項，如果想要更了解背後的理論或數學可以去參考另一位學長的[文章](https://hackmd.io/@fqiObQWCSUWMlLKBbLIqXg/SyTCC1qYS)。

## 整體程式架構與流程
一開始首先要做的就是用opengl內建的function去實作，可參考助教的[文章](https://medium.com/maochinn/fltk-project-maze-338c2109989d)基本上畫地板跟call幾個function就可以完成整個project，但難就難在要自己刻出gluPerspective、gluLookAt、glVertex3f，跟深度測試。大致流程如下:
* 畫天空與地板(glvertex2f)，用2D的方式畫，可以達到無限延伸的效果，如果是用3D畫，就需要設很大的範圍才能類似無限 
* 根據助教的文章實作出整個迷宮，但這時候可能會遇到一些怪異的bug，例如天空地板亂跑，這是因為重置為單位矩陣的那幾行程式碼放錯地方了，這幾行必須要放在畫天空地板程式碼之前。

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

* 成功看到迷宮後就可以開始實作2個最重要的矩陣:`projection matrix`與`model view matrix`，其實它們分別對應到`gluPerspective`與`gluLookAt`
* 推薦一個網頁讓你了解整個流程:http://www.opengl-tutorial.org/cn/beginners-tutorials/tutorial-3-matrices/
* `model matrix`在這個project好像不會用到，概念上它就是以自我中心為0,0定義出自己的身體、手、腳...的位置
* `view matrix`這個矩陣是由2個矩陣所構成的(rotate與translate)，rotate顧名思義就是旋轉，而translate就是移動位置，這個矩陣的效果有點像是把相機轉到對的角度跟位置，才可以看到想要的vertex，但實際上我們做不是移動或旋轉相機，而是對整個世界做移動旋轉，比如:相機往右移30cm，實際上是將整個世界左移30cm，至於為甚麼要這樣，講白了就是:**到底是你在看世界還是世界在看你?**
* `projection matrix`這個矩陣就是用來產生投影的效果，但是它為為模擬人類的視錐，產生遠小近大的感覺，直接看圖更清楚
這是還沒乘上projection的樣子
乘projection後的
projection matrix也分2種，一種是我們使用的Perspective型，另一種就是沒有遠小近大的Orthographic型
* 但重點是，這2個matrix到底要怎麼產生，上面的都屁話，畢竟 **talk is cheap show me code**
其實google一下就找到惹~
[gluLookAt](https://www.khronos.org/opengl/wiki/GluLookAt_code)

#define square(x) ((x)*(x))
void NormalizeVector(float x[3]) {
	float Norm = sqrt(square(x[0]) + square(x[1]) + square(x[2]));
	x[0] /= Norm;
	x[1] /= Norm;
	x[2] /= Norm;
}

void ComputeNormalOfPlane(float result[3], float A[3], float B[3]) {
	result[0] = A[1] * B[2] - A[2] * B[1];
	result[1] = A[2] * B[0] - A[0] * B[2];
	result[2] = A[0] * B[1] - A[1] * B[0];
}

void LookAt(float eyePosition3DX, float eyePosition3DY, float eyePosition3DZ,
	float center3DX, float center3DY, float center3DZ,
	float upVector3DX, float upVector3DY, float upVector3DZ)
{
	float forward[3], side[3], up[3];
	float matrix[16];

	forward[0] = center3DX - eyePosition3DX;
	forward[1] = center3DY - eyePosition3DY;
	forward[2] = center3DZ - eyePosition3DZ;
	NormalizeVector(forward);
	// 向量外積
	float tmp[3] = { upVector3DX ,upVector3DY, upVector3DZ };
	ComputeNormalOfPlane(side, forward, tmp);
	NormalizeVector(side);
	//  向量外積
	ComputeNormalOfPlane(up, side, forward);
	matrix[0] = side[0];
	matrix[4] = side[1];
	matrix[8] = side[2];
	matrix[12] = 0.0;
	matrix[1] = up[0];
	matrix[5] = up[1];
	matrix[9] = up[2];
	matrix[13] = 0.0;
	matrix[2] = -forward[0];
	matrix[6] = -forward[1];
	matrix[10] = -forward[2];
	matrix[14] = 0.0;
	matrix[3] = matrix[7] = matrix[11] = 0.0;
	matrix[15] = 1.0;
	global::model_view = glm::make_mat4(matrix);
	global::model_view = glm::translate(global::model_view, glm::vec3(-eyePosition3DX, -eyePosition3DY, -eyePosition3DZ));
}

[gluPerspective](https://www.khronos.org/opengl/wiki/GluPerspective_code)

void Frustum(float* matrix, float left, float right, float bottom, float top,float znear, float zfar)
{
	float temp, temp2, temp3, temp4;
	temp = 2.0 * znear;
	temp2 = right - left;
	temp3 = top - bottom;
	temp4 = zfar - znear;
	matrix[0] = temp / temp2;
	matrix[1] = 0.0;
	matrix[2] = 0.0;
	matrix[3] = 0.0;
	matrix[4] = 0.0;
	matrix[5] = temp / temp3;
	matrix[6] = 0.0;
	matrix[7] = 0.0;
	matrix[8] = (right + left) / temp2;
	matrix[9] = (top + bottom) / temp3;
	matrix[10] = (-zfar - znear) / temp4;
	matrix[11] = -1.0;
	matrix[12] = 0.0;
	matrix[13] = 0.0;
	matrix[14] = (-temp * zfar) / temp4;
	matrix[15] = 0.0;
}
void Perspective(float fovyInDegrees, float aspectRatio,float znear, float zfar)
{
	float matrix[16];
	float ymax, xmax;
	float temp, temp2, temp3, temp4;
	ymax = znear * tanf(fovyInDegrees * M_PI / 360.0);
	xmax = ymax * aspectRatio;
	Frustum(matrix, -xmax, xmax, -ymax, ymax, znear, zfar);
	global::projection = glm::make_mat4(matrix);
}

* 產生這些matrix之後就可以用`glLoadMatrix`(替代最上層矩陣)或`glMultMatrix`(乘上最上層矩陣)，來測試矩陣是否正確。
* 我使用的是glm內建的資料結構mat4x4，這是為了之後的矩陣乘向量，因為用glm就不用自己刻出來了，不過自己刻出來好像也不難就是了，至於如何安裝glm，請自己google吧，位置放對基本上就完成了。
* 然後還有一點就是建議將矩陣都設為全域變數，要用的時候就不用傳來傳去，搞得很混亂。
* 如果你有試著把矩陣印出來看就會發現其實projection matrix一直都是相同的，這是正常現象，所以其實可以把`Perspective`計算projection的程式碼放到Maze物件constructor最後面的地方，就可以減少重複的運算，但如果要這麼做的話，建議再多設一個全域變數aspect，然後在Mazewindow的constructor時算好aspect = w() / h();。`Perspective(viewer_fov, global::aspect, my_near, my_far);`，更多細節可以去參考我的程式碼。
* 做完這些就會感到很迷茫，不知道接下來要幹嘛，因為不知道要怎麼改成glvertex2f，會這樣是因為後2個功能(clipping與迷宮遞迴)其實是寫在一起的，但我們當然不可能一次完成2個，所以先解決clipping的問題，clipping的問題只要解決了，1x1的迷宮就應該要能正常顯示了。
* 在測試clipping時，可以先把所有edge clip然後畫出來，就不要管哪些牆不畫，全畫就對了

for(int i=0;i<num_edges;i++){
    //clipping edges[i] 這道牆
    //用glvertex2f畫
}

* 這裡補充一下，框架裡總共有2種可以表示牆的資料結構，一種是`edge`，另一種是`LineSeg`，這2個最大差別在於一個是用指標指到vertex，另一個是自己擁有2個座標的記憶體空間，如果要傳到function運作，會建議使用`LineSeg`，要不然不小心改到某個值，造成整個程式一堆bug就完了，但框架一開始初始化就是把牆的資訊存在`edge`裡，所以這2個一定要搞清楚，怎麼互換也要先寫好，copy consrtuctor的問題也不要忘了。
* 那，問題來了，怎麼切RRRRRR???? 這個問題搞了我好幾天好幾夜。首先，在這裡你有3條路可選
1. 在還沒乘以任何矩陣前就切好所有vertex
2. vertex乘以modelview matrix後再切
3. 乘完projection matrix後除以Homogeneous的w
PPT是這樣寫:

List outputList = subjectPolygon;   
  for (Edge clipEdge in clipPolygon) do
     List inputList = outputList;
     outputList.clear();
     Point S = inputList.last;
     for (Point E in inputList) do
        if (E inside clipEdge) then
           if (S not inside clipEdge) then
             outputList.add(ComputeIntersection(S,E,clipEdge));
           end if
           outputList.add(E);
        else if (S inside clipEdge) then
           outputList.add(ComputeIntersection(S,E,clipEdge));
        end if
        S = E;
     done
  done

第一次看就懂才有鬼，你會看不懂是因為這code是拿來切多邊形的，outputList跟inputList都不需要，我們要做的更簡單，更新一個牆(edge)的頭(start)尾(end)即可，但在切之前，我們先搞清楚到底要拿甚麼來切牆壁，答案就是前面提到的視錐(frustum)，普通的視錐是像前面放的圖一樣，立體的梯形，有12個邊，也就是說一面牆在畫之前，要先經過這12個邊切切切(clipping)，然後才可以畫出來，不過這個專案比較特別，因為相機不需要上下看，所以只要用梯形平面(4個邊)順時針去切就可以了，甚至你可以像我一樣懶，只切左右2邊，也就是像小地圖那樣的2條射線，但為了避免出現bug，梯形短邊的那條可能還是需要切一下。
切的方向

clipping的pseudo code:

for(int i=0;i<num_edges;i++){   
    拿edges[i]的2個座標 開始點start 結束點end
    if(clip(左視錐射線,start,end) && clip(右視錐射線,start,end)){
        //用glvertex2f畫牆
    }
}

///////////////////////////////////////////////////
bool clip(視錐射線,start,end) {
    
	if (開始點在視錐射線的右邊) {
		if (結束點在視錐射線的左邊) {
			//狀況1
			//結束點在視錐外
			//所以要更新結束點到牆與視錐射線的交叉點
		}
		else {
			//狀況2
			//啥都不用更新，這面牆完全在視錐內
		}
	}
	else if (結束點在視錐射線的右邊) {
		//狀況3
		//開始點在視錐外
		//所以要更新開始點到牆與視錐射線的交叉點
	}
	else {
		//狀況4
		//不用畫，直接跑下個牆(edge)
		return false;
	}
	return true;

}

這段pseudo code只是為了理解在幹嘛，實際怎麼寫還是看你，至於要如何判斷左右，其實早就寫在Edge的`Point_Side`function裡了，，為了保持一致姓，所以把`Point_Side`移植到LineSeg，傳入xy座標就會回傳左右的標示`(Edge::RIGHT\LEFT)`

同樣的，要怎麼算出視錐與牆的交叉點，也已經寫在`Cross_Param`function了，這個function回傳的是從起始點到交叉點間所占該牆(edge)的比例，有了比例就可以線性內插出交叉點座標。

狀況1
狀況2，對2條射線來說，開始與結束點都在右手邊，此牆不用切，完整保留
狀況3
狀況4
寫成C++就是下面這樣，要注意的是，我把迷宮的xy平面對應到3維座標的xz，所以在存取y值時要拿z的那格資料，也就是[2]。

bool clip(LineSeg frustum_side,glm::vec4& start,glm::vec4& end) {
	char s_side = frustum_side.Point_Side(start[0], start[2]);
	char e_side = frustum_side.Point_Side(end[0], end[2]);
	if (s_side == Edge::RIGHT){
		if (e_side == Edge::LEFT) {
			float percent = frustum_side.Cross_Param(LineSeg(start, end, 2));
			end[0] = frustum_side.start[0] + (frustum_side.end[0] - frustum_side.start[0]) * percent;
			end[2] = frustum_side.start[1] + (frustum_side.end[1] - frustum_side.start[1]) * percent;
		}
	}
	else if (e_side == Edge::RIGHT){
		float percent = frustum_side.Cross_Param(LineSeg(start, end, 2));
		start[0] = frustum_side.start[0] + (frustum_side.end[0] - frustum_side.start[0]) * percent;
		start[2] = frustum_side.start[1] + (frustum_side.end[1] - frustum_side.start[1]) * percent;
	}
	else {
		return false;
	}
	return true;
}

以我自己的設計來說，是將clip寫成一個function，然後回傳bool來判斷要不要畫，你也可以外面包一層迴圈來跑過所有視錐射線。

clip完成後，1x1的迷宮就應該要能正常顯示，至於畫牆的部分，在之前測試projection與modelview矩陣時都是使用`glVertex3f`，要如何改寫成`glVertex2f`呢?
1. 因為矩陣都是使用4x4，所以vertex也要是4個值
2. 填法 `glm::vec4 vertex(迷宮平面的y值(LineSeg的[1]), 1.0f, 迷宮平面的x值(LineSeg的[0]), 1.0f)` 至於為甚麼這樣填，我也不懂
3. NDC座標 = projection * modelview * vertex
4. 壓縮NDC座標到平面(screen space) 螢幕座標=NDC座標/NDC座標的w值 (screen_coord = NDC/NDC[3])
5. `glBegin(GL_POLYGON);` `glVertex2f(screen_coord[0],screen_coord[1])` `glEnd();`

寫成C++(此段已整合到迷宮遞迴，我的程式碼裡看不到):

//畫一面牆的函式
void Maze::draw_wall(LineSeg wall,LineSeg L, LineSeg R, LineSeg front){ //L R是左右視錐射線 front是梯形短邊的射線
    glm::vec4 start(wall.start[1], 1.0f,wall.start[0], 1.0f);
    glm::vec4 end(wall.end[1], 1.0f, wall.end[0], 1.0f);
    
    glm::vec4 NDC_start = global::model_view * start;
    glm::vec4 NDC_end  = global::model_view * end;
    if (!clip(L, NDC_start, NDC_end) || !clip(R, NDC_start, NDC_end) || !clip(front, NDC_start, NDC_end)) return; //有任何一條射線判斷這面牆不用畫即可直接終止掉。
    NDC_start = global::projection * NDC_start;
    NDC_end = global::projection * NDC_end;
    if (NDC_start[3] < my_near && NDC_end[3] < my_near) return;//my_near為最近可視距離，通常為0.01
    glm::vec4 screen_start = NDC_start / NDC_start[3];
    glm::vec4 screen_end   = NDC_end / NDC_end[3];
    glBegin(GL_POLYGON);
    glVertex2f(screen_start[0], screen_start[1]);
    glVertex2f(screen_end[0], screen_end[1]);
    glVertex2f(screen_end[0], -screen_end[1]);
    glVertex2f(screen_start[0], -screen_start[1]);
    glEnd();
}

接下來是畫迷宮Cell的部分，因為我們現在只要測試1x1的迷宮能不能跑，所以只針對view_cell(玩家現在所在的Cell指標)去畫(draw_cell)，然後再拿這個Cell的四面牆去畫(draw_wall)

//畫一個Cell(四面牆)的函式
void Maze::draw_cell(Cell* now_cell, LineSeg L, LineSeg R) {
	now_cell->foot_print = true;
	LineSeg front(R.end[0],R.end[1],L.start[0],L.start[1]); //前面提到的梯形短邊，可以用左右視錐射線拼出
	for (int i = 0;i < 4;i++) {
		LineSeg edge_line(now_cell->edges[i]);
		glm::vec4 start(edge_line.start[1], 1.0f, edge_line.start[0], 1.0f),end(edge_line.end[1], 1.0f, edge_line.end[0], 1.0f);
		glColor3fv(now_cell->edges[i]->color);
		draw_wall(edge_line,L,R,front);
	}
}

//畫整個迷宮的函式
void Maze::Draw_View(const float focal_dist)
{
	frame_num++;
	global::model_view = glm::mat4(1);//填1才會是identity matrix
	float viewer_pos[3] = { viewer_posn[Maze::Y], 0.0f, viewer_posn[Maze::X] };
	LookAt(viewer_pos[Maze::X], viewer_pos[Maze::Y], viewer_pos[Maze::Z],
		viewer_pos[Maze::X] + sin(Maze::To_Radians(viewer_dir)),
		viewer_pos[Maze::Y],
		viewer_pos[Maze::Z] + cos(Maze::To_Radians(viewer_dir)),
		0.0, 1.0, 0.0);
	for (int i = 0;i < num_cells;i++)cells[i]->foot_print = false;
	draw_cell(view_cell,
		LineSeg(my_near * tan(To_Radians(viewer_fov * 0.5f)), -my_near, my_far * tan(To_Radians(viewer_fov * 0.5f)), -my_far),
		LineSeg(-my_far * tan(To_Radians(viewer_fov * 0.5f)), -my_far, -my_near * tan(To_Radians(viewer_fov * 0.5f)), -my_near));
}

上面所說的東西都完成後，應該會變下面這樣，1x1的迷宮正常跑，但10x10的就只能看到單個房間 :