1 /* 2 Copyright (c) 2008 Seneca College 3 Licenced under the MIT License (http://www.c3dl.org/index.php/mit-license/) 4 Author: Patrick Lam & Andor Salga 5 */ 6 7 /** 8 @private 9 @class A Picking class 10 */ 11 c3dl.Picking = function(scene) 12 { 13 var scn = scene; 14 var cam = scn.getCamera(); 15 16 /** 17 @private 18 Returns an array of 2 elements. The mouse button clicked and an array of object 19 index number in the current scene in sorted order (closet to farthest). 20 21 @param {} event 22 23 @returns {Array} The mouse button clicked and the array of object index number. 24 */ 25 this.onMouseDown = function(event) 26 { 27 // user may have switched the camera or the user may have moved the camera 28 // and then clicked, so everytime the user tries to pick something, get the 29 // camera being used at the time of the click. 30 cam = scn.getCamera(); 31 32 var canvasTag = scn.getCanvas(); 33 34 // Get the viewport coordinates, that is the coordinates where the user clicked 35 // on the canvas. 36 // The viewport coordinates system: 37 // 38 // 0,0 _______ w, 0 39 // | | 40 // | | 41 // 0,h |_______| w,h 42 // 43 var clickedCanvasCoords = getClickedCoords(event); 44 45 // Convert the viewport coordinates into NDC. Since NDC is normalized, 46 // it's as if we are calculating percentages. Note Y is flipped for NDC. 47 // NDC space: 48 // 49 // -1,1 _______ 1, 1 50 // | | 51 // | | 52 // -1,-1 |_______| 1,-1 53 // 54 // go from viewport coords to normalized device coords 55 var normalizedDeviceCoords = [ ( 2 * clickedCanvasCoords[0] / canvasTag.width) -1, 56 -((2 * clickedCanvasCoords[1] / canvasTag.height) -1), 57 1,1]; 58 59 var iproj = c3dl.inverseMatrix(scene.getProjectionMatrix()); 60 61 // To get the clip coords, we multiply the viewspace coordinates by 62 // the projection matrix. 63 // Working backwards across the pipeline, we have to take the normalized 64 // device coordinates and multiply by the inverse projection matrix to get 65 // the clip coordinates. 66 var clipCoords = c3dl.multiplyMatrixByVector(iproj, normalizedDeviceCoords); 67 68 // perspective divide 69 clipCoords[0] /= clipCoords[3]; 70 clipCoords[1] /= clipCoords[3]; 71 clipCoords[2] /= clipCoords[3]; 72 73 // flip Y 74 clipCoords[2] = -clipCoords[2]; 75 76 // The start of the ray is wherever the camera is. 77 var rayInitialPoint = cam.getPosition(); 78 79 var x = clipCoords[0]; 80 var y = clipCoords[1]; 81 var z = clipCoords[2]; 82 83 // After this code was written a small bug was found in the freecamera class 84 // until I have time to fix it, I'm putting in a quick fix. 85 var kludge = c3dl.multiplyVector(cam.getLeft(), -1); 86 var viewMatrix = c3dl.makePoseMatrix(kludge, cam.getUp(), cam.getDir(), cam.getPosition()); 87 88 // place the ray from clip space into view space 89 // 90 // 91 var rayTerminalPoint = c3dl.multiplyMatrixByVector(viewMatrix, [x,y,z,0]); 92 var rayDir = c3dl.normalizeVector(rayTerminalPoint); 93 94 // This array will hold the indices of the objects which pass the boundingSphere/Ray test. 95 // The indices are the ones the scene uses to identify objects. 96 // All the objects which passed the rough bouding volume test can later on be more thouroughly 97 // tested against the ray. Objects which do 98 var passedBoundsTest = new Array(); 99 100 // Collada objects must pass an enclosure test first before their individual 101 // triangles are tested against the ray, to speed up this test. 102 for (var i = 0; i < scn.getObjListSize(); i++) 103 { 104 var currObj = scn.getObj(i); 105 106 // Make sure the object is a Collada before calling getPickable() since 107 // not all objects in the scene will have that function. 108 if(currObj instanceof c3dl.Collada && currObj.getPickable() ) 109 { 110 // do the bounding volumes of the geometry nodes intersect with the given ray? 111 if( currObj.rayIntersectsEnclosures(rayInitialPoint, rayDir)) 112 { 113 passedBoundsTest.push(currObj); 114 } 115 } 116 } 117 118 // references of objects which have passed their respective picking tests. 119 var objectsPicked = new Array(); 120 121 // if the user only wants to only run the test against bounding volumes, just 122 // make the array which holds the objects which passed the triangle test point to 123 // the array we just filled up with object indices. There is no need to recopy 124 // everything into the array which holds the passed triangle tests. 125 if(scn.getPickingPrecision() == c3dl.PICK_PRECISION_BOUNDING_VOLUME) 126 { 127 objectsPicked = passedBoundsTest; 128 } 129 130 // otherwise we will need to run the ray/triangle tests for every object 131 else 132 { 133 // We only test the objects which have passed the bounding volume test. 134 // If the ray has not intersected the bounding volume, it can't possibly intersect 135 // with any triangle in the object. 136 for (var i = 0; i < passedBoundsTest.length; i++) 137 { 138 var currObject = passedBoundsTest[i]; 139 140 // if the object is a collada object 141 if(currObject instanceof c3dl.Collada && currObject.getPickable() ) 142 { 143 // if the collada object confirms the ray has intersected it, it will be 144 // added to the list of objects the user picked. 145 if( currObject.rayIntersectsTriangles(rayInitialPoint, rayDir)) 146 { 147 objectsPicked.push(passedBoundsTest[i]); 148 } 149 } 150 } 151 } 152 153 154 155 // POINT PICKING 156 157 // get the projection tranformation (either perspective or orthographic) 158 var projMatrix = cam.getProjectionMatrix(); 159 var viewMatrix = cam.getViewMatrix(); 160 var viewProjMatrix = c3dl.multiplyMatrixByMatrix(projMatrix, viewMatrix); 161 162 if( scn.getPointRenderingMode() == c3dl.POINT_MODE_POINT) 163 { 164 // for every point in the scene 165 for(var i = 0; i < scn.getObjListSize(); i++) 166 { 167 if( scn.getObj(i) instanceof c3dl.Point ) 168 { 169 // save attenuation factors for the pointList 170 var attenuation = scene.getPointAttenuation(); 171 172 var point = scn.getObj(i); 173 174 // get the distance from the point to the camera. The distance is 175 // used to calculate the attenuation of the point. 176 var pointCoords = point.getPosition(); 177 var d = c3dl.vectorLength( c3dl.subtractVectors(pointCoords, cam.getPosition())); 178 179 // save the points pixel width. Get the pixel width by calculating 180 // the attenuation factors of the point. 181 var pointPixelSize = 1.0/ (attenuation[0] + (attenuation[1] * d) + (attenuation[2] * d *d )); 182 183 // the coordinates in world space. 184 var worldSpaceCoords = [pointCoords[0],pointCoords[1],pointCoords[2],1]; 185 186 // project current point to 2D plane 187 var clipCoords = c3dl.multiplyMatrixByVector(viewProjMatrix, worldSpaceCoords); 188 189 // perspective divide. 190 var normalizedDeviceCoords = [ clipCoords[0]/clipCoords[3], 191 clipCoords[1]/clipCoords[3], 192 clipCoords[2]/clipCoords[3]]; 193 194 // transform the point from NDC space to viewport space. 195 var viewportCoords = [ (normalizedDeviceCoords[0] +1)/2 * canvasTag.width, 196 (1-normalizedDeviceCoords[1])/2 * canvasTag.height]; 197 198 // if points are rendered as circles, 199 // test if x,y coords of mouse click falls within circle 200 // if passed, add point index to list of points that passed test. 201 // add pointList as a list which has one of its points picked. 202 if(( scn.getPointSmooth() && isPointInCircle(clickedCanvasCoords, viewportCoords, pointPixelSize)) 203 ||( !scn.getPointSmooth() && isPointInSquare(clickedCanvasCoords, viewportCoords, pointPixelSize))) 204 { 205 objectsPicked.push(point); 206 } 207 } 208 } 209 } 210 211 // We can run the rayBounding Sphere test if the points are rendered 212 // as spheres. 213 else if(scn.getPointRenderingMode() == c3dl.POINT_MODE_SPHERE) 214 { 215 // for every point in the scene 216 for(var i = 0; i < scn.getObjListSize(); i++) 217 { 218 if( scn.getObj(i) instanceof c3dl.Point ) 219 { 220 if(c3dl.rayIntersectsSphere(rayInitialPoint, rayDir, scn.getObj(i).getPosition(), scn.getPointSize())) 221 { 222 objectsPicked.push(scn.getObj(i)); 223 } 224 } 225 } 226 } 227 228 229 // Give the option for the user to do whatever they want to objects 230 // which were behind the objects picked. 231 c3dl.sortObjectsFromCam(scn, cam, objectsPicked); 232 233 // the picking callback is the function the user wants the library to call once 234 // someone clicks on the canvas. 235 var pickingCB = scn.getPickingCallback(); 236 237 // create the object which will contain the methods the user will need to call. 238 var pickingResult = createPickingResult(canvasTag, event.which, objectsPicked); 239 pickingCB(pickingResult); 240 } 241 242 /** 243 @private 244 245 @param {HTMLCanvasElement} cvs; 246 @param {int} btnUsed The button clicked 247 @param {Array} objList Array of renferences of objects 248 @param {Array} pointLists Array of references of pointsLists which had at least one of their 249 points picked. 250 @param {Array} points Array of 251 252 @returns {c3dl.PickingResult} a pickingresult with added variables and overridden methods. 253 */ 254 function createPickingResult(cvs, btnUsed, objList) 255 { 256 var pickingObj = new c3dl.PickingResult(); 257 258 // 259 pickingObj["canvas"] = cvs; 260 pickingObj["getCanvas"] = function (){ return this.canvas;}; 261 262 // 263 pickingObj["buttonUsed"] = btnUsed; 264 pickingObj["getButtonUsed"] = function (){ return this.buttonUsed;}; 265 266 // 267 pickingObj['objects'] = objList; 268 pickingObj['getObjects'] = function(){ return this.objects;}; 269 270 return pickingObj; 271 } 272 273 /** 274 @private 275 276 Is the 2D point pointCoords within the squre located at squareCoords with 277 a width and height of pointPixelSize 278 279 @param pointCoords {Array} Two components [x,y] which defines the 280 point which will be tested to see if is lies within the square. 281 282 @param squareCoords {Array} Two components [x,y] which defines the 283 center of the square. 284 285 @param squareSize {float} The number of pixels from the center of 286 the square to each edge. 287 288 @returns {bool} true if the point is within the square, false otherwise. 289 */ 290 function isPointInSquare( pointCoords, squareCoords, squareSize) 291 { 292 // if the clicked coordinates are inside the square 293 if( pointCoords[0] >= squareCoords[0] - squareSize/2 && 294 pointCoords[0] <= squareCoords[0] + squareSize/2 && 295 pointCoords[1] >= squareCoords[1] - squareSize/2 && 296 pointCoords[1] <= squareCoords[1] + squareSize/2) 297 { 298 return true; 299 } 300 301 return false; 302 } 303 304 305 /** 306 @private 307 308 Is the point 'pointCoords' within the circle with position circleCoords and diameter 309 circleDiameter? If points have a small Diameter, only a few pixels in width, either 310 this of isPointInSquare can be called. However, if the diamater get larger, we have to 311 reject clicking on the circles 'corners' as valid 'hits'. 312 313 @param {Array} pointCoords 314 315 @param {Array} circleCoords 316 317 @param {Array} circleDiameter 318 319 @return {bool} true if the point is within the cirlce, otherwise false. 320 */ 321 function isPointInCircle(pointCoords, circleCoords, circleDiameter) 322 { 323 // Get the vector from pointCoords to circleCoords 324 var vec = [ pointCoords[0] - circleCoords[0], pointCoords[1] - circleCoords[1]]; 325 326 // distance from point to circle 327 var d = Math.sqrt( (vec[0] * vec[0]) + (vec[1] * vec[1]) ); 328 329 return (d < circleDiameter/2 ? true : false); 330 } 331 332 /** 333 @private 334 Get the coordinates where the user clicked on the canvas. 335 336 Screen space is left handed with 0,0 at the top left of the canvas. 337 338 @returns {Array} Array of 2 integers, x and y coordinates where the user clicked 339 on the canvas. 340 */ 341 function getClickedCoords( event ) 342 { 343 var canvas = scn.getCanvas(); 344 345 var canvasPosition = c3dl.getObjectPosition(scn.getCanvas()); 346 347 // event.clientX and event.clientY contain where the user clicked 348 // on the client area of the browser 349 // canvasPosition holds the coordinate of the top left corner where the canvas resides 350 // on the client area. 351 // window.pageXOffset, window.pageYOffset hold how much the user has scrolled. 352 var X = event.clientX - canvasPosition[0] + window.pageXOffset - 1; 353 var Y = event.clientY - canvasPosition[1] + window.pageYOffset - 1; 354 355 return [X,Y]; 356 } 357 358 } 359 360 /** 361 This will sort the objects which have been picked. This function is O(n2). 362 363 Should this function be sped up? It is currently O(n2), however using a faster sorting algorithm may 364 create more overhead than a bubble sort. If less than 10 objects need to be sorted, the speed of 365 this function should not be an issue. 366 367 @param {c3dl.Scene} scene Scene is needed because we have an array of indices, not actual objects. Since 368 scene has the actual list, we can query it with getObj(i) to get the actual object, then its position. 369 @param {Array} pickedObjects An array of indices of objects which have passed a bounds test or triangle test. 370 @param {c3dl.FreeCamera} camera The camera used in the scene. 371 372 @private 373 */ 374 c3dl.sortObjectsFromCam = function(scene, camera, pickedObjects) 375 { 376 var cameraPos = camera.getPosition(); 377 var objAPos, objBPos; 378 var distA, distB; 379 var camToObjADist, camToObjBDist; 380 381 // used to swap objects 382 var temp; 383 384 // Sort all intersecting objects from closet to farthest 385 for(var i = 0; i < pickedObjects.length; i++) 386 { 387 for(var j = 0; j < pickedObjects.length; j++) 388 { 389 objAPos = pickedObjects[i].getPosition(); 390 objBPos = pickedObjects[j].getPosition(); 391 392 // calculate the distance from the camera to the object's center. 393 camToObjADist = c3dl.subtractVectors(cameraPos, objAPos); 394 camToObjBDist = c3dl.subtractVectors(cameraPos, objBPos); 395 396 // Objects distance from camera 397 distA = c3dl.vectorLength(camToObjADist); 398 distB = c3dl.vectorLength(camToObjBDist); 399 400 // Swap 401 if (distA < distB) 402 { 403 temp = pickedObjects[i]; 404 pickedObjects[i] = pickedObjects[j]; 405 pickedObjects[j] = temp; 406 } 407 } 408 } 409 410 return pickedObjects; 411 } 412 413 /** 414 Does the given ray intersect the sphere? When using this function to test 415 the ray created by a user click against a boundingsphere, keep the following 416 in mind: When trying to pick the bounding sphere the test will fail if a few 417 pixels from the edges of the sphere. Either it will seem that the test is passing 418 when it should not or the test is failing when it should should pass. 419 420 This could be because the 'pixel point' associated with the cursor is not at the 421 very tip of the cursor where it is expected it to be. This occurs on osx. 422 423 @param {Array} rayInitialPoint The initial point of the ray in world space. 424 @param {Array} rayDir A normalized vector which has the ray's direction. 425 @param {Array} spherePos position of the sphere. 426 @param {float} sphereRadius radius of the sphere. 427 428 @returns {boolean} true if the given ray intersects the boundingsphere, otherwise false. 429 */ 430 c3dl.rayIntersectsSphere = function(rayInitialPoint, rayD, spherePos, sphereRadius) 431 { 432 // this will hold the result if there was an intersection. 433 var hasIntersected = false; 434 435 var rayDir = c3dl.normalizeVector(rayD); 436 437 // 438 var v = c3dl.subtractVectors(rayInitialPoint, spherePos); 439 440 // 441 var b = 2.0 * c3dl.vectorDotProduct(rayDir, v); 442 443 // 444 var c = c3dl.vectorDotProduct(v,v); 445 446 // 447 c = c - Math.pow( sphereRadius, 2); 448 449 // 450 var discriminant = (b*b) - (4.0 * c); 451 452 // these will hold the intersection values. 453 var s0, s1; 454 455 // If the discriminant is less than 0, we cannot get the square root 456 // since it would result in an imaginary number. 457 if( discriminant > 0) 458 { 459 discriminant = Math.sqrt(discriminant); 460 461 s0 = (-b + discriminant ) / 2; 462 s1 = (-b - discriminant ) / 2; 463 464 if(s0 >= 0.0 || s1 >= 0.0) 465 { 466 hasIntersected = true; 467 } 468 } 469 470 return hasIntersected; 471 } 472 473 /** 474 Test if a ray defined by point 'orig' and direction 'dir' intersects with 475 triangle defined by vertices vert0, vert1 and vert2. 476 477 @param {Array} orig The ray's origin, which is a vector of 3 values. 478 @param {Array} dir The ray's direction, a vector of 3 values. 479 @param {Array} vert0 Vertex 0 of the triangle, going counter-clockwise. 480 @param {Array} vert1 Vertex1 of the triangle 481 @param {Array} vert2 Vertex2 of the triangle 482 483 @returns {boolean} true if ray intersects with triangle, false otherwise. 484 485 @private 486 */ 487 c3dl.rayIntersectsTriangle = function(orig, dir, vert0, vert1, vert2) 488 { 489 // find vectors for the two edges of the triangle which share vert0 490 var edge1 = c3dl.subtractVectors(vert1, vert0); 491 var edge2 = c3dl.subtractVectors(vert2, vert0); 492 493 // to calculate the area of the triangle: 494 // first calculate the area of the parallelogram the two vectors define, 495 // then take half of that result leaving us with the area of the triangle. 496 var area = 0.5 * c3dl.vectorLength( c3dl.vectorCrossProduct(edge1, edge2)); 497 498 // we'll need the normal of the triangle 499 var norm = c3dl.vectorCrossProduct(edge1,edge2); 500 501 // calculate this first to see if we can stop processing. 502 var normDotDir = c3dl.vectorDotProduct(norm, dir); 503 504 // if the dot product of two vectors returns 0, that means the vectors are perpendicular. If 505 // that is the case, the ray will never intersect the plane and we can return false right here 506 // to prevent further processing. 507 if (normDotDir == 0) { 508 return false; 509 } 510 511 // If the ray is not parallel to the plane, we need to do the following: 512 513 // 1) find out at what point the ray will intersect the plane (which is defined by the triangle). 514 // 2) find out if that point is within the triangle if it is, we have a ray/triangle intersection. 515 516 // The parametric equation of a ray is: 517 // R(t) = p + tu 518 // where, 519 // p is a point, which is the origin of the ray. 520 // u is a vector, which is the direction of the ray. 521 // t is a scalar value, which scales the direction of the ray. 522 523 // by passing in values greater than 0 into the equation, we can generate 524 // different points along the ray. 525 526 // The equation of a plane is: 527 // Ax + By + Cz = D 528 // where, 529 // (ABC) is the normal of the plane. 530 // (xyz) is a point on the plane. 531 532 // we can re-write the equation for a plane 533 // n . x = d 534 // n is the normal of the plane. 535 // x is a point on the plane. 536 537 // So, with the equation of the plane and the ray, we can now 538 // substitute the ray equation into the plane equation. What this does 539 // is it tells us what value we need we have to set 't' to in order for 540 // the ray to intersect the plane, which gives us the point of 541 // intersection. Or, what scalar value must we multiply the direction 542 // of the ray for it to intersect with the ray? 543 544 // we substite R into the plane equation 545 // n . R(t) = d 546 547 // R(t) is expanded... 548 // n . [p+tu] = d 549 550 // distribute n 551 // n.p + tn . u = d 552 553 // We isolate t because we need to find out what scalar value the direction 554 // of the ray needs to be scaled by for it to intersect with the plane. 555 // t = (d - n.p) / (n.dir) 556 // 557 558 var d = c3dl.vectorDotProduct(norm, vert1); 559 var normDotRayorig = c3dl.vectorDotProduct(norm, orig); 560 var t = (d - normDotRayorig) / normDotDir; 561 562 // Now we have 't', which is the scalar value needed to scale the ray's direction 563 // for it to intersect with the plane the triangle defines. 564 565 // We scale the ray's direction 't' times and then add it to the ray's origin to 566 // get the point of intersection, POI. 567 var scaledDir = c3dl.multiplyVector(dir, t); 568 var POI = c3dl.addVectors(orig, scaledDir); 569 570 // area of smaller triangles formed by the 3 vertices and the point of intersection 571 edge1 = c3dl.subtractVectors(vert0, POI); 572 edge2 = c3dl.subtractVectors(vert1, POI); 573 edge3 = c3dl.subtractVectors(vert2, POI); 574 575 // get the area of the three triangles 'created' where the 576 // ray intersects the triangle's plane. 577 var area1 = 0.5 * c3dl.vectorLength( c3dl.vectorCrossProduct(edge1, edge2) ); 578 var area2 = 0.5 * c3dl.vectorLength( c3dl.vectorCrossProduct(edge2, edge3) ); 579 var area3 = 0.5 * c3dl.vectorLength( c3dl.vectorCrossProduct(edge3, edge1) ); 580 581 // get the difference between the area of the triangle and the area of the three triangles 582 // created where the user clicked. If the user clicked inside the triangle, the difference 583 // should be near zero. 584 var diff = area - (area1 + area2 + area3); 585 586 // delete edg1, edge2, edge3, area1, area2, area3, normDotDir, normDotRayorig, t, POI, area; 587 588 // since we have done quite a few calculations on floats, 589 // allow a small margin of error. 590 return (Math.abs(diff) <= 0.0001); 591 } 592