WebGL模型拾取——射線法
今天要把WebGL中一個非常重要的演算法記錄下來——raycaster射線法拾取模型。首先我們來了解一下為什麼要做模型拾取,我們在做webgl場景互動的時候經常要選中場景中的某個模型,比如滑鼠拖拽旋轉,平移。為了能做到滑鼠互動,就首先要能選中場景中的模型物件,這就要用到模型拾取演算法,本文僅討論射線法模型拾取raycaster。
所謂射線法就是利用一根射線去和場景中的模型進行碰撞,撞到的模型物件就是被拾取到的模型。請看下圖
我逐個來解釋一下上圖中的元素。首先解釋相機(camera),這就是人眼的抽象,代表使用者在螢幕前的眼睛位置。人眼看到的世界是透視的(perspective),因此我們構造的視稜臺(frustum)基於透視投影。整個視稜臺區域介於場景近截面(near)和遠截面(far)之間,這個區間內的空間就是我們可以看到的場景空間。需要說明一下,near近截面我們這裡緊貼螢幕(screen),即距離很小約等於0.1,far遠截面就是我們認為的視線最遠能看到的距離,我們這裡設定為1000。螢幕screen在近截面前0.1的位置上,也是離人眼最近的截面,也是滑鼠互動的介面,這是要事先解釋明白的。理解了這個空間結構以後我們就開始講解raycaster的演算法原理。
首先我們來看一下滑鼠在螢幕上的位置點P0,我們可以看到P0點(滑鼠),這個就是滑鼠在螢幕上的位置。我們再來看看triangle1三角形1,這就是透視空間中triangle2三角形2在螢幕上的投影。我們可以明顯看到滑鼠位置P0點在螢幕triangle1三角形1內部,即滑鼠點選中triangle1三角形1。這在螢幕上可以看的很清楚,但是問題來了,在空間中滑鼠是沒有深度概念的,即滑鼠只有XY座標,沒有Z座標,那我們在視稜臺的空間座標系中如何表示滑鼠的三維空間位置呢,如果沒有滑鼠的3維空間座標,如何判斷在視稜臺空間中滑鼠是否選中triangle2三角形2這個模型物件呢?也許有同學會說,triangle1就是triangle2的投影嘛,選中投影就是選中模型了不是,我就這麼說,非常正確,能說出這樣的話就已經完全理解了模型在螢幕上的投影的原理,但是新的問題隨之又來了,如何獲取滑鼠點選模型的座標呢,即如何得到滑鼠點在模型上的那個點的三維空間座標呢,如果僅僅判斷是否選中,那投影就夠用了,但要計算滑鼠點選模型上的點座標,就遠遠不夠用了。為了解決這個問題,raycaster演算法應運而生。
raycaster顧名思義就是射線投射。他的原理其實非常簡單,就是用一根射線去交有限平面,獲得交點。射線是有起點的,起點就是我們的眼睛。我們做一根起於camera,通過滑鼠在螢幕上的位置P0,繼續延伸,交視稜臺近截面於P1,繼續延伸,交視稜臺遠截面於P3,射線截止,我們得到了一根線段P1-P3。這根線段P1-P3就是我們眼睛能看到的滑鼠發出的射線在透視空間中的部分,凡是這根線段碰到的模型,都是滑鼠點選中的空間模型。而這根線段和模型的交點就是滑鼠點選模型的交點,這個交點座標就是滑鼠點選模型的交點空間三維座標。這樣就順利解決了上面我們的問題,即求滑鼠點選空間三維模型的交點座標。在上圖中我們看得很清楚,這個交點就是P2,接下來我們就來講解怎麼求這個P2的空間座標。
做圖形學的同學們都非常清楚。如何求線段和平面的交點,這裡我擷取一部分程式碼,以供敘述方便,以下就是求線段擷取平面交點的函式。
/* */ let Intersector = require('./Intersector'); let LineSegmentIntersection = require('./Intersection').LineSegmentIntersection; let Vec3 = require('./Vec3'); let Mat4 = require('./Mat4'); let Algorithm = require('./Algorithm'); let LineSegmentIntersector = function () { Intersector.call(this); //原始的起始點和臨界值,初始化設定的資料,保留作為參照,設定後不再變動 this._orginStart = Vec3.new();//線段起點 this._orginEnd = Vec3.new();//線段終點 this._orginThreshold = 0.0;//點和線求相交時的臨界值,完全相交是很難求到的 //臨時儲存,每次求交都可能會變動的資料 //對於有變換的幾何求交,不會變換幾何頂點而是變換起始點和臨界值 this._start = Vec3.new();//線段起點 this._end = Vec3.new();//線段終點 this._threshold = 0.0;//點和線求相交時的臨界值,完全相交是很難求到的 this._direction = Vec3.new(); this._length = 0; this._inverseLength = 0; this._matrix = Mat4.new(); }; LineSegmentIntersector.prototype = Object.create(Intersector.prototype); LineSegmentIntersector.prototype.constructor = LineSegmentIntersector; Object.assign(LineSegmentIntersector.prototype, { init: function (start, end, threshold) { Vec3.copy(this._orginStart, start); Vec3.copy(this._orginEnd, end); Vec3.copy(this._start, start); Vec3.copy(this._end, end); if (threshold !== undefined) { this._orginThreshold = threshold; this._threshold = threshold; } }, intersect: function (drawable) { //先使用包圍盒子 if (!drawable.getBoundingBox().intersectLineSegment(this._orginStart, this._orginEnd)) { return; } this._drawable = drawable; let geometry = drawable.getGeometry(); let vertexbuffer = geometry.getBufferArray('Vertex'); this._vertices = vertexbuffer.getArrayBuffer(); //沒有頂點資料不處理直接返回 if (!this._vertices) return; //沒有圖元不處理直接返回 let primitive = geometry.getPrimitive(); if (!primitive) return; //初始化求相交的各種資料 let matrix = drawable.getTransform(); if (this._transform !== matrix) {//如果不一樣,需要計算新的起始點以及各種臨時資料 this._transform = matrix; Mat4.invert(this._matrix, matrix); //根據矩陣計算新的臨界值 if (this._orginThreshold > 0.0) { let tmp = this._start; Mat4.getScale(tmp, this._matrix); let x = tmp[0]; let y = tmp[1]; let z = tmp[2]; this._threshold = this._orginThreshold * (x > y ? (x > z ? x : z) : y > z ? y : z); } //根據矩陣計算新的起始點 Vec3.transformMat4(this._start, this._orginStart, this._matrix); Vec3.transformMat4(this._end, this._orginEnd, this._matrix); //根據新的起始點計算各種臨時資料 Vec3.sub(this._direction, this._end, this._start); this._length = Vec3.length(this._direction);//長度 this._inverseLength = this._length <= Algorithm.EPSILON ? 0.0 : 1.0 / this._length; Vec3.scale(this._direction, this._direction, this._inverseLength);//求單位向量 }//如果變換與上次一樣,直接使用上次的資料求相交 //求相交 primitive.operate(this); }, intersectPoint: function (vertex) { // https://www.geometrictools.com/GTEngine/Include/Mathematics/GteDistPointSegment.h //起點指向繪製點,向量M let m = Vec3.MemoryPool.alloc(); Vec3.sub(m, vertex, this._start); //起點指向終點,向量N let n = Vec3.MemoryPool.alloc(); Vec3.sub(n, this._end, this._start); //求M在N上的投影比例值 //|m|*|n|*cos / \n\*\n\ = |m|*cos/\n\ let r = Vec3.dot(m, n) * this._inverseLength * this._inverseLength; //計算繪製點到線段的距離 let sqrdist = 1.0; if (r < 0.0) {//夾角超過90度,繪製點在當前線段起點後面,求繪製點與起點的距離 sqrdist = Vec3.sqrLen(m); } else if (r > 1.0) {//繪製點在當前線段終點後面,求繪製點與終點的距離 sqrdist = Vec3.sqrDist(vertex, this._end); } else {//在0到1之間 //m - n * r 如果平行或者接近於平行,結果接近於0,相交 sqrdist = Vec3.sqrLen(Vec3.scaleAndAdd(m, m, n, -r)); } let intersection = undefined; if (sqrdist > this._threshold * this._threshold) {//超過了臨界值,沒有相交返回 } else { //相交 intersection = new LineSegmentIntersection(); //intersection._i1 = index; //intersection._r1 = 1.0; Vec3.scaleAndAdd(intersection._point, this._start, n, r); intersection._ratio = r; } Vec3.MemoryPool.free(m); Vec3.MemoryPool.free(n); return intersection; }, intersectLine: function (vertex0, vertex1) { // https://www.geometrictools.com/GTEngine/Samples/Geometrics/DistanceSegments3/DistanceSegments3.cpp //let epsilon = 0.00000001; //起點到終點的向量 let u = Vec3.MemoryPool.alloc(); Vec3.sub(u, vertex1, vertex0); let v = Vec3.MemoryPool.alloc(); Vec3.sub(v, this._end, this._start); let w = Vec3.MemoryPool.alloc(); Vec3.sub(w, vertex0, this._start); let a = Vec3.dot(u, u); let b = Vec3.dot(u, v); let c = Vec3.dot(v, v); let d = Vec3.dot(u, w); let e = Vec3.dot(v, w); let D = a * c - b * b; let sN; let tN; let sD = D; let tD = D; // compute the line parameters of the two closest points if (D < Algorithm.EPSILON) {//平行 // the lines are almost parallel sN = 0.0; // force using point P0 on segment S1 sD = 1.0; // to prevent possible division by 0.0 later tN = e; tD = c; } else { // get the closest points on the infinite lines sN = b * e - c * d; tN = a * e - b * d; if (sN < 0.0) { // sc < 0 => the s=0 edge is visible sN = 0.0; tN = e; tD = c; } else if (sN > sD) { // sc > 1=> the s=1 edge is visible sN = sD; tN = e + b; tD = c; } } if (tN < 0.0) { // tc < 0 => the t=0 edge is visible tN = 0.0; // recompute sc for this edge if (-d < 0.0) sN = 0.0; else if (-d > a) sN = sD; else { sN = -d; sD = a; } } else if (tN > tD) { // tc > 1=> the t=1 edge is visible tN = tD; // recompute sc for this edge if (-d + b < 0.0) sN = 0; else if (-d + b > a) sN = sD; else { sN = -d + b; sD = a; } } // finally do the division to get sc and tc let sc = Math.abs(sN) < Algorithm.EPSILON ? 0.0 : sN / sD; let tc = Math.abs(tN) < Algorithm.EPSILON ? 0.0 : tN / tD; // get the difference of the two closest points let closest0 = Vec3.MemoryPool.alloc(); let closest1 = Vec3.MemoryPool.alloc(); Vec3.scaleAndAdd(closest0, vertex0, u, sc); Vec3.scaleAndAdd(closest1, this._start, v, tc); let sqrDistance = Vec3.sqrDist(closest0, closest1); Vec3.MemoryPool.free(closest0); Vec3.MemoryPool.free(closest1); let intersection = undefined; if (sqrDistance > this._threshold * this._threshold) { } else { //相交 intersection = new LineSegmentIntersection(); // intersection._i1 = index0; // intersection._i2 = index1; // intersection._r1 = 1.0 - tc; // intersection._r2 = tc; Vec3.copy(intersection._point, closest1); intersection._ratio = tc; } Vec3.MemoryPool.free(u); Vec3.MemoryPool.free(v); Vec3.MemoryPool.free(w); return intersection; }, intersectTriangle: function (vertex0, vertex1, vertex2) { let e2 = Vec3.MemoryPool.alloc(); Vec3.sub(e2, vertex2, vertex0); let e1 = Vec3.MemoryPool.alloc(); Vec3.sub(e1, vertex1, vertex0); let pvec = Vec3.MemoryPool.alloc(); Vec3.cross(pvec, this._direction, e2); let intersection = undefined; //線段與三角麵點積 let det = Vec3.dot(pvec, e1); //判斷三角形所在的平面與線段是否平行,如果平行鐵定不相交,面片沒有厚度 if (Math.abs(det) < Algorithm.EPSILON) { //return undefined; }else{ let invDet = 1.0 / det; let tvec = Vec3.MemoryPool.alloc(); Vec3.sub(tvec, this._start, vertex0); let u = Vec3.dot(pvec, tvec) * invDet; //三角面超出了線段兩個點範圍外面,鐵定不相交 if (u < 0.0 || u > 1.0) { //return undefined; }else{ let qvec = Vec3.MemoryPool.alloc(); Vec3.cross(qvec, tvec, e1); let v = Vec3.dot(qvec, this._direction) * invDet; // if (v < 0.0 || u + v > 1.0) { //return undefined; }else{ let t = Vec3.dot(qvec, e2) * invDet; if (t < Algorithm.EPSILON || t > this._length) { //return undefined; }else{ //相交 intersection = new LineSegmentIntersection(); //求相交點 let r0 = 1.0 - u - v; let r1 = u; let r2 = v; let r = t * this._inverseLength; let interX = vertex0[0] * r0 + vertex1[0] * r1 + vertex2[0] * r2; let interY = vertex0[1] * r0 + vertex1[1] * r1 + vertex2[1] * r2; let interZ = vertex0[2] * r0 + vertex1[2] * r1 + vertex2[2] * r2; // intersection._i1 = index0; // intersection._i2 = index1; // intersection._i3 = index2; // intersection._r1 = r0; // intersection._r2 = r1; // intersection._r3 = r2; //這裡的點沒有經過變換,不是真實的世界座標點 Vec3.set(intersection._point, interX, interY, interZ); Vec3.transformMat4(intersection._point, intersection._point, this._transform); //求法向量,法向量未變換,如果有用途也要變換 let normal = intersection._normal; Vec3.cross(normal, e1, e2); Vec3.normalize(normal, normal); //比例,在相交線段上的比例,不需要變換 intersection._ratio = r; } } Vec3.MemoryPool.free(qvec); } Vec3.MemoryPool.free(tvec); } Vec3.MemoryPool.free(e1); Vec3.MemoryPool.free(e2); Vec3.MemoryPool.free(pvec); return intersection; // http://gamedev.stackexchange.com/questions/54505/negative-scale-in-matrix-4x4 // https://en.wikipedia.org/wiki/Determinant#Orientation_of_a_basis // you can't exactly extract scale of a matrix but the determinant will tell you // if the orientation is preserved //intersection._backface = mat4.determinant(intersection._matrix) * det < 0; }, intersectBoundingBox: function (box) { return box.intersectLineSegment(this._orginStart, this._orginEnd); }, }); module.exports = LineSegmentIntersector; // setDrawable: function (drawable) { //this._geometry = drawable.getGeometry(); //this._vertices = this._geometry.getBufferArray('Vertex'); // //let matrix = drawable.getTransform(); //if (this._transform === matrix) {//如果與上次的一樣,不再處理 //return; //} // ////如果不一樣,需要計算新的起始點已經各種臨時資料 //this._transform = matrix; //Mat4.invert(this._matrix, matrix); // ////根據矩陣計算新的臨界值 //if (this._orginThreshold > 0.0) { //let tmp = this._start; //Mat4.getScale(tmp, this._matrix); //let x = tmp[0]; //let y = tmp[1]; //let z = tmp[2]; //this._threshold = this._orginThreshold * (x > y ? (x > z ? x : z) : y > z ? y : z); //} ////根據矩陣計算新的起始點 //Vec3.transformMat4(this._start, this._orginStart, this._matrix); //Vec3.transformMat4(this._end, this._orginEnd, this._matrix); // ////根據新的起始點計算各種臨時資料 //Vec3.sub(this._direction, this._end, this._start); //this._length = Vec3.length(this._direction);//長度 //this._inverseLength = this._length <= Algorithm.EPSILON ? 1.0 / this._length : 0.0; //Vec3.scale(this._direction, this._direction, this._inverseLength);//求單位向量 // }, // setGeometry: function (geometry, matrix) { //Intersector.prototype.setGeometry.call(this, geometry, matrix); // ////如果不一樣,需要計算新的起始點已經各種臨時資料 //Mat4.invert(this._matrix, matrix); // ////根據矩陣計算新的臨界值 //if (this._orginThreshold > 0.0) { //let tmp = this._start; //Mat4.getScale(tmp, this._matrix); //let x = tmp[0]; //let y = tmp[1]; //let z = tmp[2]; //this._threshold = this._orginThreshold * (x > y ? (x > z ? x : z) : y > z ? y : z); //} ////根據矩陣計算新的起始點 //Vec3.transformMat4(this._start, this._orginStart, this._matrix); //Vec3.transformMat4(this._end, this._orginEnd, this._matrix); // ////根據新的起始點計算各種臨時資料 //Vec3.sub(this._direction, this._end, this._start); //this._length = Vec3.length(this._direction);//長度 //this._inverseLength = this._length <= Algorithm.EPSILON ? 1.0 / this._length : 0.0; //Vec3.scale(this._direction, this._direction, this._inverseLength);//求單位向量 // }, // setGeometry: function (geometry) { ////沒有頂點資料不處理直接返回 //let vertexbuffer = geometry.getBufferArray('Vertex'); //if(!vertexbuffer) return; // ////沒有圖元不處理直接返回 //let primitive = geometry.getPrimitive(); //if (primitive) //primitive.operate(this); // },
以上的LineSegmentIntersector就是計算線段和平面交點的類,具體演算法不再贅述,請自行參考《WebGL程式設計指南》。好了,我們接下來就看一個專案中的具體案例,請看下圖
我們在pick事件中使用了LineSegmentIntersector對場景中的包圍盒和座標系模型進行了raycaster射線碰撞檢測,結果我們得到了一系列的返回物件,其中包括包圍盒的2個面,座標系的一根座標軸的geometry,這就另我們覺得難辦了,滑鼠射線碰到了不止一個模型,我們該怎麼辦呢,這裡就要說明一下,一般我們都取離near近截面最近的一個模型作為我們pick選中的模型,因為其他模型都被處於前方的該模型遮擋住了。
好了,今天對raycaster的解釋就結束了,只是初步瞭解一下,raycaster還有很多應用場景,這裡和我們的滑鼠拾取不相關的就不介紹了,謝謝大家閱讀,歡迎大家一起留言探討,再次感謝。轉載本文請註明出處:https://www.cnblogs.com/ccentry/p/9973165.html