Picking Function
Patrick Lam | 16 January, 2009 | 18:25
Picking.js adds the functionality of picking to Canvas 3D. To enable picking for your scene, you would need to first instantiate a variable of Picking class with the scene, and then set the onMouseUp (a dummy function) and onMouseDown function from the Picking class.
The picking function can be broken down into a couple of small steps:
1) Construct a ray starting from where the mouse is clicked to the back of the scene
2) Make a bounding box for all objects
3) Test to see if ray intersects with any of the bounding boxes
4) Test all triangles in an object for intersection with the ray only if they pass the bounding box test
5) Sort objects that passed test from closet to furthest
We will now go into more details for each of the steps.
1) Constructing the mouse Ray
The first thing needed was the mouse coordinates on the screen. There are going to be different kinds of mouse coordinates and we want the right one. There is the coordinates for the mouse on the monitor, the coordinates inside the active window/broswer, and then there’s the coordinates for inside the canvas 3D screen (which is what we want).
The mouse coordinate system we will be using will not be the top left corner system, instead, the center of the canvas screen will be where (0, 0) is. This will allow us to better determine the mouse vector direction later.
After getting the mouse coord on the canvas screen, we can now calculate the point on the far clipping plane where we clicked on the screen. To do this, we find out what the dimension of the screen in the far clipping plane is and compare it to the dimension of the canvas screen we see. Then, we calculate the size difference ratio and then mulitply our mouse coordinates by it to get the location of our mouse click in the far plane.
Now that we have the x,y coordinates of our starting and ending points of the ray, we can now convert it into a 3D coordinate by simply assuming the following:
1) The camera is align with the z-axis
2) We are looking into the screen (negative z)
3) Camera position is the origin of the mouse ray
With this said, we can construct our mouse ray.
We now have our base mouse ray constructed. To put the finishing touches on it, we need to make the view matrix of the camera, and then apply it to the mouse vector and bring it into the correct position which is at the angle we are looking at through the camera.
2) Bounding Box
When getting vertices of objects in C3DL, they are in the object’s space and has not been transformed in any way. So to create our bounding box for the objects are simple. We loop through all the vertices of an object, and save its smallest and largest x, y, z-values, and from that we can construct our bounding box. However, this will not be enough to serve our purpose in the picking funciton. What we needed is the bounding box that contains the object after it’s transformed. There are 3 types of transformation to consider:
1) Rotational
2) Scaling (Scale Factor)
3) Translation (Position)
Depending on which type of bounding box we want, we’ll only need to apply certain transformations to the bounding box. Thinking it though logically, we have to apply the scaling and translation no matter what, so the question now is when should we apply the “rotational” transformation to the bounding box.
There are two types of bounding box: Axis-Aligned Bounding Box (AABB) and Oriented Bounding Box (OBB). As the names suggested, AABB just means the box is always aligned with the axis and OBB just means the box is oriented the way the object is. In other words, AABB does not have the rotational transformation applied, whereas OBB does.
How do we know which one to use? There are no sure way to decide which one we use, but there are a couple things you should consider to make a decision:
1) The time it needs to calculate the bounding box
2) The number of objects
3) The time needed to construct the transformation matrix and apply it to the bounding box
There are other factors that go into the decision, but what I’ve decided to do for our picking function is to use AABB. This way, we wont need to apply the transformation matrix to the vertices of the bounding box for every object in the scene, but instead, we apply the inverse transformation to the mouse ray.
Hence, our bounding box function will:
1) Loop through all the vertices to find min/max x,y,z-values
2) Apply the transformation matrix depending on the aabb parameter passed in
3) Apply scaling to values
4) Apply the translation to the values (position)
5) Return an array holding the min x, y, z-values and the max x, y, z-values
3) Ray-Box Intersection Test
Now that we finally have our ray and bounding box, we can begin our initial picking test: Ray-Box Intersection Test. As mentioned before, we will be applying the inverse transformation matrix to the ray and then perform the test. Why did we need to do this?
1) The bounding box is still in the object’s space (not world space – transformation matrix not applied)
2) The ray is in the world space (applying the object’s inverse transformation matrix will bring the ray into the object’s space)
As for the actual intersection test, it is broken intro three parts:
1) Get Intersection
2) Check if intersection is inside the bounding box
3) Call to the test with the neccessary info
4) Ray-Triangle Intersection Test
The steps for this test will pretty much be the same as the Ray-Box Intersection Test, except the test used will be different. The difference here is that instead of just looping through the objects and passing the bounding box to the intersection test, we are looping through the triangles of each object and pass the vertices of those triangles into the test. The test used is the mathematical approach in finding line-plane intersection.
1) Create two edges from the triangle vertices passed in
2) Calculate the norm of the plane
3) Solve for d in the plane equation (ax + by + cz = d)
4) Check to see if ray is parallel to plane by performing dot product on norm and ray direction vector
5) Solve for t after substituting the ray equation into the plane equation
6) Calculate the point of intersection (POI)
7) Check to see if the POI is inside the triangle by calculating the area of the triangle, and compare it to the sum of the 3 smaller triangles
If the sum is larger than the area, the POI is outside of the triangle, therefore failing the test
5) Sorting Picked Objects
After we’ve got all the objects which passed the Ray-Triangle Intersection Test, we can sort them from closest to furthest from the camera. To do this, we use bubble sort and compare the distance of the objects to the camera and swap them.
Since the onMouseDown function occurs no matter which mouse button you click, it might be useful to pass back out which mouse button was pressed. On top of that, you might want to disable the right-click menu that appears in the browser.
To tell which button was pressed, we can use either “which” or “button”. The buttons are represented with the following numbers:
scn = new Scene();
...
...
...
picker = new Picking(scn);
scn.setMouseCallback(picker.onMouseUp, picker.onMouseDown);
So whenever a mouse click event occurs on the canvas screen, the picking function will return an array of numbers, which are index to the objects in the scene, in the order of closet to furthest from the screen.
The picking function can be broken down into a couple of small steps:
1) Construct a ray starting from where the mouse is clicked to the back of the scene
2) Make a bounding box for all objects
3) Test to see if ray intersects with any of the bounding boxes
4) Test all triangles in an object for intersection with the ray only if they pass the bounding box test
5) Sort objects that passed test from closet to furthest
We will now go into more details for each of the steps.
1) Constructing the mouse Ray
The first thing needed was the mouse coordinates on the screen. There are going to be different kinds of mouse coordinates and we want the right one. There is the coordinates for the mouse on the monitor, the coordinates inside the active window/broswer, and then there’s the coordinates for inside the canvas 3D screen (which is what we want).
The mouse coordinate system we will be using will not be the top left corner system, instead, the center of the canvas screen will be where (0, 0) is. This will allow us to better determine the mouse vector direction later.
// Find position of object in browser
// Returning it's offset in the browser
function findPos(obj) {
var curleft = curtop = 0;
if (obj.offsetParent) {
do {
curleft += obj.offsetLeft;
curtop += obj.offsetTop;
} while (obj = obj.offsetParent);
return [curleft,curtop];
}
}
// Returns the mouse x,y in canvas
function getXandY( event ) {
var tempDiv = document.getElementsByTagName('canvas')[0];
var coords = findPos(tempDiv);
// determine the correct X, Y
var X = ( ( event.clientX - coords[0] ) + window.pageXOffset ) - (tempDiv.width / 2.0);
var Y = (tempDiv.height / 2.0) - ( event.clientY - ( coords[1] - window.pageYOffset ) );
return [X,Y];
}
After getting the mouse coord on the canvas screen, we can now calculate the point on the far clipping plane where we clicked on the screen. To do this, we find out what the dimension of the screen in the far clipping plane is and compare it to the dimension of the canvas screen we see. Then, we calculate the size difference ratio and then mulitply our mouse coordinates by it to get the location of our mouse click in the far plane.
// Find dimension of far clipping plane
var farWidth = 2 * ((C3DL_FAR_CLIPPING_PLANE) * Math.tan(degreesToRadians(0.5 * C3DL_FIELD_OF_VIEW)));
var farHeight = farWidth * (canvasTag.height/canvasTag.width);
// Find ratio between far clipping plane and canvas screen
var wRatio = farWidth / canvasTag.width;
var hRatio = farHeight / canvasTag.width;
// Find point clicked on far clipping plane
var farX = (canvasXY[0] / canvasTag.width) * farWidth;
var farY = (canvasXY[1] / canvasTag.height) * farHeight;
var camDist = Math.sqrt(camPos[0] * camPos[0] + camPos[1] * camPos[1] + camPos[2] * camPos[2]);
Now that we have the x,y coordinates of our starting and ending points of the ray, we can now convert it into a 3D coordinate by simply assuming the following:
1) The camera is align with the z-axis
2) We are looking into the screen (negative z)
3) Camera position is the origin of the mouse ray
With this said, we can construct our mouse ray.
var farZ = C3DL_FAR_CLIPPING_PLANE - camDist;
// Create the Starting point and direction of mouse vector
var mouseOrigin = camPos;
var mouseVec = makeVector(farX, farY, farZ);
We now have our base mouse ray constructed. To put the finishing touches on it, we need to make the view matrix of the camera, and then apply it to the mouse vector and bring it into the correct position which is at the angle we are looking at through the camera.
// View Matrix
viewMatrix = makePoseMatrix(cam.getLeft(), cam.getUp(), cam.getDir(), cam.getPosition());
// Move mouse vector to align with camera
mouseVec = multiplyMatrixByVector(viewMatrix, mouseVec);
2) Bounding Box
When getting vertices of objects in C3DL, they are in the object’s space and has not been transformed in any way. So to create our bounding box for the objects are simple. We loop through all the vertices of an object, and save its smallest and largest x, y, z-values, and from that we can construct our bounding box. However, this will not be enough to serve our purpose in the picking funciton. What we needed is the bounding box that contains the object after it’s transformed. There are 3 types of transformation to consider:
1) Rotational
2) Scaling (Scale Factor)
3) Translation (Position)
Depending on which type of bounding box we want, we’ll only need to apply certain transformations to the bounding box. Thinking it though logically, we have to apply the scaling and translation no matter what, so the question now is when should we apply the “rotational” transformation to the bounding box.
There are two types of bounding box: Axis-Aligned Bounding Box (AABB) and Oriented Bounding Box (OBB). As the names suggested, AABB just means the box is always aligned with the axis and OBB just means the box is oriented the way the object is. In other words, AABB does not have the rotational transformation applied, whereas OBB does.
How do we know which one to use? There are no sure way to decide which one we use, but there are a couple things you should consider to make a decision:
1) The time it needs to calculate the bounding box
2) The number of objects
3) The time needed to construct the transformation matrix and apply it to the bounding box
There are other factors that go into the decision, but what I’ve decided to do for our picking function is to use AABB. This way, we wont need to apply the transformation matrix to the vertices of the bounding box for every object in the scene, but instead, we apply the inverse transformation to the mouse ray.
Hence, our bounding box function will:
1) Loop through all the vertices to find min/max x,y,z-values
2) Apply the transformation matrix depending on the aabb parameter passed in
3) Apply scaling to values
4) Apply the translation to the values (position)
5) Return an array holding the min x, y, z-values and the max x, y, z-values
this.getBoundingBox = function(aabb)
{
// Find the min/max values of the object in its own space
// Only when bounding box has not been calculated before
// This saves the time needed to loop through all vertices each time bounding box is called
if (bbValues == null) {
minX = this.expandedVertices[0];
maxX = minX;
minY = this.expandedVertices[0];
maxY = minY;
minZ = this.expandedVertices[0];
maxZ = minZ;
for (i = 1; i < this.expandedVertices.length; i++) {
if (i % 3 == 0) {
if (this.expandedVertices[i] maxX)
maxX = this.expandedVertices[i];
}
else if (i % 3 == 1) {
if (this.expandedVertices[i] maxY)
maxY = this.expandedVertices[i];
}
else {
if (this.expandedVertices[i] maxZ)
maxZ = this.expandedVertices[i];
}
}
}
// Objects transformation
var objTransMat = makePoseMatrix(this.getLeft(), this.getUp(), this.getDirection(), this.getPosition());
var minArr = new Array(minX, minY, minZ);
var maxArr = new Array(maxX, maxY, maxZ);
if (!aabb) {
minArr = multiplyMatrixByVector(objTransMat, minArr);
maxArr = multiplyMatrixByVector(objTransMat, maxArr);
}
// Objects scale
var wtScale = new Array( this.getScale()[0],0,0,0,
0,this.getScale()[1],0,0,
0,0,this.getScale()[2],0,
0,0,0,1);
minArr = multiplyMatrixByVector(wtScale, minArr);
maxArr = multiplyMatrixByVector(wtScale, maxArr);
bbValues = new Array(minArr[0] + this.getPosition()[0], minArr[1] + this.getPosition()[1], minArr[2] + this.getPosition()[2],
maxArr[0] + this.getPosition()[0], maxArr[1] + this.getPosition()[1], maxArr[2] + this.getPosition()[2]);
return bbValues;
}
3) Ray-Box Intersection Test
Now that we finally have our ray and bounding box, we can begin our initial picking test: Ray-Box Intersection Test. As mentioned before, we will be applying the inverse transformation matrix to the ray and then perform the test. Why did we need to do this?
1) The bounding box is still in the object’s space (not world space – transformation matrix not applied)
2) The ray is in the world space (applying the object’s inverse transformation matrix will bring the ray into the object’s space)
// Find all objects with bounding box intersecting with mouse vector
for (var i = 0; i < scn.getObjListSize(); i++) {
var testObj = scn.getObj(i);
var boxValues = testObj.getBoundingBox(true);
// getBoundingBox() returns {minX, minY, minZ, maxX, maxY, maxZ} that has not been transformed
// only gets scaled and object's position offset
var minVal = new Array(boxValues[0], boxValues[1], boxValues[2]);
var maxVal = new Array(boxValues[3], boxValues[4], boxValues[5]);
// Move the mouse vector into the object's space
var objTransMat = makePoseMatrix(testObj.getLeft(), testObj.getUp(), testObj.getDirection(), testObj.getPosition());
var objInvTransMat = inverseMatrix(objTransMat);
var tempOrigin = multiplyMatrixByVector(objInvTransMat, mouseOrigin);
var tempVec = multiplyMatrixByVector(objInvTransMat, mouseVec);
if (CheckLineBox(minVal, maxVal, tempOrigin, tempVec)) {
passRayBoxTest.push(i);
}
}
As for the actual intersection test, it is broken intro three parts:
1) Get Intersection
2) Check if intersection is inside the bounding box
3) Call to the test with the neccessary info
function GetIntersection(fDst1, fDst2, P1, P2) {
if ((fDst1 * fDst2) >= 0) return 0;
if ( fDst1 == fDst2 ) return 0;
var Hit = new Array();
Hit[0] = P1[0] + (P2[0]-P1[0]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
Hit[1] = P1[1] + (P2[1]-P1[1]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
Hit[2] = P1[2] + (P2[2]-P1[2]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
return Hit;
}
function InBox( Hit, B1, B2, Axis) {
if (Hit != 0) {
if ( Axis==1 && Hit[2] > B1[2] && Hit[2] B1[1] && Hit[1] B1[2] && Hit[2] B1[0] && Hit[0] B1[0] && Hit[0] B1[1] && Hit[1] < B2[1]) return 1;
}
return 0;
}
// B1 is array of 3 values, the min X,Y,Z values of bounding box
// B2 is array of 3 values, the max X,Y,Z values of bounding box
// L1 is array of 3 values, the X,Y,Z values of starting position of ray
// L2 is array of 3 values, the X,Y,Z values of direction vector of ray
function CheckLineBox(B1, B2, L1, L2) {
if (L2[0] < B1[0] && L1[0] B2[0] && L1[0] > B2[0]) return false;
if (L2[1] < B1[1] && L1[1] B2[1] && L1[1] > B2[1]) return false;
if (L2[2] < B1[2] && L1[2] B2[2] && L1[2] > B2[2]) return false;
if (L1[0] > B1[0] && L1[0] B1[1] && L1[1] B1[2] && L1[2] < B2[2])
{return true;}
if ( (InBox( GetIntersection( L1[0]-B1[0], L2[0]-B1[0], L1, L2), B1, B2, 1 ))
|| (InBox( GetIntersection( L1[1]-B1[1], L2[1]-B1[1], L1, L2), B1, B2, 2 ))
|| (InBox( GetIntersection( L1[2]-B1[2], L2[2]-B1[2], L1, L2), B1, B2, 3 ))
|| (InBox( GetIntersection( L1[0]-B2[0], L2[0]-B2[0], L1, L2), B1, B2, 1 ))
|| (InBox( GetIntersection( L1[1]-B2[1], L2[1]-B2[1], L1, L2), B1, B2, 2 ))
|| (InBox( GetIntersection( L1[2]-B2[2], L2[2]-B2[2], L1, L2), B1, B2, 3 )))
{
return true;
}
return false;
}
4) Ray-Triangle Intersection Test
The steps for this test will pretty much be the same as the Ray-Box Intersection Test, except the test used will be different. The difference here is that instead of just looping through the objects and passing the bounding box to the intersection test, we are looping through the triangles of each object and pass the vertices of those triangles into the test. The test used is the mathematical approach in finding line-plane intersection.
1) Create two edges from the triangle vertices passed in
2) Calculate the norm of the plane
3) Solve for d in the plane equation (ax + by + cz = d)
4) Check to see if ray is parallel to plane by performing dot product on norm and ray direction vector
5) Solve for t after substituting the ray equation into the plane equation
6) Calculate the point of intersection (POI)
7) Check to see if the POI is inside the triangle by calculating the area of the triangle, and compare it to the sum of the 3 smaller triangles
If the sum is larger than the area, the POI is outside of the triangle, therefore failing the test
function intersect_triangle(orig, dir, vert0, vert1, vert2) {
/* find vectors for two edges sharing vert0 */
var edge1 = new Array(vert1[0] - vert0[0], vert1[1] - vert0[1], vert1[2] - vert0[2]);
var edge2 = new Array(vert2[0] - vert0[0], vert2[1] - vert0[1], vert2[2] - vert0[2]);
// area of triangle
var area = 0.5 * vectorLength(new Array(edge1[1] * edge2[2] - edge1[2] * edge2[1], edge1[0] * edge2[2] - edge1[2] * edge2[0], edge1[0] * edge2[1] - edge1[1] * edge2[0]));
// Plane equation is ax + by + cz = d
// n = [a b c] x = [x y z]
// n.x = d
var norm = new Array(edge1[1] * edge2[2] - edge1[2] * edge2[1], edge1[0] * edge2[2] - edge1[2] * edge2[0], edge1[0] * edge2[1] - edge1[1] * edge2[0]);
var d = norm[0] * vert1[0] + norm[1] * vert1[1] + norm[2] * vert1[2];
// Ray is parallel to plane
var nd = norm[0] * dir[0] + norm[1] * dir[1] + norm[2] * dir[2];
if (nd == 0) {
return false;
}
// solve for t
// R(t) = P + (t x dir)
// t = (d - n.P) / (n.dir)
var nP = norm[0] * orig[0] + norm[1] * orig[1] + norm[2] * orig[2];
var t = (d - nP) / nd;
// Point of Intersection of the Ray and the Plane created by the triangle
var POI = new Array(orig[0] + dir[0] * t, orig[1] + dir[1] * t, orig[2] + dir[2] * t);
// area of smaller triangles formed by the 3 vertices and the point of intersection
edge1 = new Array(vert0[0] - POI[0], vert0[1] - POI[1], vert0[2] - POI[2]);
edge2 = new Array(vert1[0] - POI[0], vert1[1] - POI[1], vert1[2] - POI[2]);
var edge3 = new Array(vert2[0] - POI[0], vert2[1] - POI[1], vert2[2] - POI[2]);
var area1 = 0.5 * vectorLength(new Array(edge1[1] * edge2[2] - edge1[2] * edge2[1], edge1[0] * edge2[2] - edge1[2] * edge2[0], edge1[0] * edge2[1] - edge1[1] * edge2[0]));
var area2 = 0.5 * vectorLength(new Array(edge2[1] * edge3[2] - edge2[2] * edge3[1], edge2[0] * edge3[2] - edge2[2] * edge3[0], edge2[0] * edge3[1] - edge2[1] * edge3[0]));
var area3 = 0.5 * vectorLength(new Array(edge3[1] * edge1[2] - edge3[2] * edge1[1], edge3[0] * edge1[2] - edge3[2] * edge1[0], edge3[0] * edge1[1] - edge3[1] * edge1[0]));
// Calculate the % of error
var diff = (area - (area1 + area2 + area3))/area;
// Check if POI is inside triangle
// Adjust margin of error for accuracy
// The threshold that will allow the triangle test work seems to be around 0.6%
// So the safe range should be around 0.7 - 1.0%
if (Math.abs(diff) >= 0.8)
return false;
else
return true;
}
5) Sorting Picked Objects
After we’ve got all the objects which passed the Ray-Triangle Intersection Test, we can sort them from closest to furthest from the camera. To do this, we use bubble sort and compare the distance of the objects to the camera and swap them.
for (var i = 0; i < intersectObjs.length; i++) {
for (var j = 0; j < intersectObjs.length; j++) {
// Objects Positions
var objAPos = scn.getObj(intersectObjs[i]).getPosition();
var objBPos = scn.getObj(intersectObjs[j]).getPosition();
// Objects x,y,z distances
var dxA = camPos[0] - objAPos[0];
var dyA = camPos[1] - objAPos[1];
var dzA = camPos[2] - objAPos[2];
var dxB = camPos[0] - objBPos[0];
var dyB = camPos[1] - objBPos[1];
var dzB = camPos[2] - objBPos[2];
// Objects distance from camera
var distA = Math.sqrt(dxA * dxA + dyA * dyA + dzA * dzA);
var distB = Math.sqrt(dxB * dxB + dyB * dyB + dzB * dzB);
// Swap
if (distA < distB) {
var tmp = intersectObjs[i];
intersectObjs[i] = intersectObjs[j];
intersectObjs[j] = tmp;
}
}
}
Extra InformationSince the onMouseDown function occurs no matter which mouse button you click, it might be useful to pass back out which mouse button was pressed. On top of that, you might want to disable the right-click menu that appears in the browser.
// Disables Right Click Menu
function clickIE(){
if (document.all){
return false;
}
}
function clickNS(e) {
if(document.layers||(document.getElementById&&!document.all)){
if (e.which==2||e.which==3) {
return false;
}
}
}
if (document.layers){
document.captureEvents(Event.MOUSEDOWN);
document.onmousedown = clickNS;
}
else{
document.onmouseup = clickNS;
document.oncontextmenu = clickIE;
}
document.oncontextmenu = new Function("return false")
To tell which button was pressed, we can use either “which” or “button”. The buttons are represented with the following numbers:
| Button Clicked | Which | Button |
| Left | 1 | 0 |
| Middle | 2 | 1 |
| Right | 3 | 2 |
