0.3 Goals Met - Release

Finally, after all the researching, the math reviews, the discussions, the coding, the testing, the back-tracking, it's ready - 0.3 Release.

Before talking about the final stretch to get the release done, lets see what's actually been done:

Modified the Model.js to include the following 2 functions
o getVertices(): returns the vertices of the object
o getBoundingBox(aabb): Returns an array of the min/max XYZ values for the bounding box after it's been scaled

Made Picking.js
o Disabled right-click menu on canvas
o Creates the mouse vector from the camera to the far clipping plane
    - 2 main variables: Mouse Origin and Mouse Direction Vector
o Ray-Bounding Box Intersection Test
    - Takes the min/max XYZ values of the bounding box, mouse origin and direction vector
    - Returns true if intersect
    - Need to transform the mouse origin and direction vector into the object's space before performing test
o Sorts the intersecting objects from closet to furthest from the camera
o Returns an array of object index in the scene

So, to continue from the previous blog, the correct mouse vector has finally been constructed and we've got ourselves a mouse origin and a mouse direction vector. The next part, which is the most important part was to construct a ray-box intersection test. I've found myself 3 different ray-box intersection algorithm and tried to implement them all, but they don't seem to work properly - only works in specific cases.

On Tuesday, went in to work with Andor. We've looked at the codes and did some more research. In the process, I've played around with the transformations and tried the tests again. Finally, it works. So what's been done now, is that I used one of the AABB tests, and to make it work properly, this is what needs to be done:
1) Get bounding box that's axis-aligned (not transformed)
2) Find the inverse of the object's transformation matrix
3) Apply the inverse transformation matrix to the mouse vector (brings the mouse vector into the object's space)
4) Pass in the values into the test

So now I simply run this test through all the objects in the scene and I've got myself a basic picking function. Afterward, I simply sorted the objects from closest to furthest. And to do that, I did some math and calculated the objects distance from the camera position and compared them.

At the end of the picking function, I had it returned an array of index of the objects in the scene.

During today's Skype meeting, I've updated everyone about the progress of the picking and told them where it's at. As it is, with the bounding box test working fine (even when objects are rotates, scaled, or moved the camera around), they are willing to add this into their next release. However, I will try to make this picking function better by implementing the ray-triangle intersection test and hopefully get this finish before their release, if not, they can add it to their next release.

As of now, my 0.3 Release is done, but I will continue to work on it to make it better. And when I get it done, I will post a more updated version of the picking function on the wiki page and have it be included in the next C3DL release.

0.3 Progress Update

Why-oh-why must I test my code so much? What happened? Oh nothing....I basically just had to redo whatever I've had for the mouse vector. However, I managed to make the process of calculating the mouse vector in fewer lines and faster time.

You can ignore all the previous calculations like finding the distance of the camera to the close/far clipping plane using trig, scaling the vector by the ratio, calculating inverse matrix, and everything else that's be done before.

Now, everything's simple. 1 simple trig, and a couple of multiplications and divisions, and we're done. So basically, I just scratched what I've done in the past....2 weeks and went back to what I had originally done in the beginning of the project.

1) Find the dimensions of the far clipping plane
var farWidth = 2 * ((C3DL_FAR_CLIPPING_PLANE) * Math.tan(degreesToRadians(0.5 * C3DL_FIELD_OF_VIEW)));
var farHeight = farWidth * (tempDiv.height/tempDiv.width);

2) Find the ratio between the far clipping plane and the canvas window size
var wRatio = farWidth / tempDiv.width;
var hRatio = farHeight / tempDiv.width;

3) Finding the x,y coordinates of the mouse on the canvas window relative to the far clipping plane. And use the distance between the camera and the far clipping plane as the z value.
var farX = (currX / tempDiv.width) * farWidth;
var farY = (currY / tempDiv.height) * farHeight;
var farZ = C3DL_FAR_CLIPPING_PLANE - camPos[2];

To make the mouse vector be relative to where the camera is, we simply make the viewMatrix of the camera and multiply our mouse vector with it.
viewMatrix = makePoseMatrix(scn.getCamera().getLeft(), scn.getCamera().getUp(), scn.getCamera().getDir(), scn.getCamera().getPosition());
var tempMouseVec = makeVector(farX, farY, farZ);
tempMouseVec = multiplyMatrixByVector(viewMatrix, tempMouseVec);

So now, wherever I rotate or move my camera to, the mouse vector will always be shooting from what we see from where the camera is to where we see as the far clipping plane in the back of the canvas.

How did this process get simplify to such an extend, I must thank Cathy and our 1 hr discussion we had and all the diagrams we kept drawing on the white board. That discussion really helped me get a clear image of how the 3D world is shown in that 2D canvas window. What was causing the main problem for having the mouse vector always being skewed towards the center, is because we ended up doing multiple matrix transformations. For what we see on the canvas, the 3D space that we see (perspective) has already been skewed (transformed) so it's in a more rectangular form than a triangle, and then flatten before being put on the screen. I've drawn a simple diagram to show what's been done from a bird's eye view(please excuse the poor drawing).


1) What we see in 3D space
2) Skewed (Perspective) and then Compressed
3) 2D (Canvas/Screen)

At least this is my understanding of it. And now that the mouse vector works properly, and FINAL (maybe minor improvements), I have to do the following:
1) Decide on an appropriate intersection test (have 2 right now)
2) Need to aligned mouse vector with testing object before testing intersection
3) Aligned object and mouse vector to axis to perform AABB test (Axis-Aligned Bounding Box)

I hope tomorrow's session with Andor will get these done. And afterward, I want to make the test do a more thorough intersection test rather than just the bounding box.

Solving other problems, help find hidden mistakes

After some more testing, I've realized that there were some major problems I need to fix before proceeding any further:
1) the center point (0, 0) on the canvas has some offset (about 3 pixels) in the browser
2) the (x, y) point of the mouse has not been converted from pixel to 3D coord

To quickly fix the first problem, I borrowed some code from a sample C3D demo:

function findPos(obj) {
 var curleft = curtop = 0;
 if (obj.offsetParent) {
  do {
   curleft += obj.offsetLeft;
   curtop += obj.offsetTop;
  } while (obj = obj.offsetParent);
  return [curleft,curtop];
 }
}

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];
}

As for the second problem, it took a little bit to figure out, but then I've came up with a temporary solution. I simply applied the same idea for getting the width of the far clipping plane, except here, I'm using the distance from position of the camera to the point it is looking at. And with that, I've calculated the ratio of the canvas to the actual space.

var camDist = Math.sqrt(Math.pow(camPos[0] - camLook[0], 2) + Math.pow(camPos[1] - camLook[1], 2) + Math.pow(camPos[2] - camLook[2], 2));
var midSpaceWidth = 2 * (camDist * Math.tan(degreesToRadians(theta));
var ratio = midSpaceWidth / tempDiv.width;
var tempX = ratio * currX;
var tempY = ratio * currY;

Now, this temporary solution only works when the object is at the look at position. So now I need to fix it so it'll work for objects at any position.

While coding this part, Andor and I also found a mistake that might have been causing a lot of problems from before. When we were calculating dz in the beginning, we did this:

var dz = dx / Math.tan(theta);

Mathematically, it seems right, but then we realize that the Math.tan needs to take a radian and not a degree number, so we quickly fixed that by changing it to:

var dz = dx / Math.tan(degreesToRadians(theta));

Luckily we saw this as we were making the pixel to 3D coord conversion, otherwise, we might have been stuck for a long time later on without realizing the problem has been there from the very beginning.

OSD Lab Reviews

Just like the previous labs, our last lab of the course did not turn out to be as difficult as I thought it might be. With the detailed instructions given, the lab was completed pretty smoothly. The main trouble I had was still the overall structure of where everything goes. Unfortunately, my previous and current project did not have much to do with plugin/extension, and hence the lack of knowledge and understanding of the tree structure was present. Other than that, everything was pretty much as easy as 1-2-3.

Afterwards, I've decided to look back at all the previous labs to make sure I didn't miss any of them. There was the:
• Ubiquity
• Mozilla Build Lab
• Patches Lab
• Thunderbird Bug posted on Bugzilla with Thunderbird Fix
• Mozilla Tab Patch Lab
• Mozilla Extension Lab
• XPCOM Component Lab
• Chrome Lab

As can be seen, the class has really gone a long way. Started with being introduced to add-ons, to building FireFox, to making and submitting patches. The only thing that I think could have been better was for the labs to be assigned earlier in the course instead of near the end. Because for people who were actually working with FireFox projects, I'm pretty sure they've been doing those things already. But for people like me, who worked on projects outside of FireFox, it truly was an interesting experience.

So Close Yet So Far

After spending the Friday afternoon with Andor trying to find ray-box intersection samples, we've finally narrowed it down to 3-4 tests to try.
- From www.blitzbasic.com
- Notes from University of Utah
- From 3D Programming Weekly
- And samples from "3D Game Engine Architecture" by David H. Eberly

Spending the weekend trying out the different sample tests, starting from what seemed the simpliest (blitzbasic), I've found the code from 3D Programming to work close to what I needed. This code is mainly used for testing AABB (Axis Aligned Bounding Box), and so, when the camera is set at positions that is not aligned with an axis, it doesn't work.
This test involves 3 separate functions:

// fDst1 and fDst2 are the distance between P1/P2 and the bounding box
// Hit is use to store where the intersection point is
function GetIntersection(fDst1, fDst2, P1, P2, Hit) {
  if ((fDst1 * fDst2) >= 0) return 0;
  if ( fDst1 == fDst2 ) return 0;
  
  var tmp = new Array();
  
  tmp[0] = P1[0] + (P2[0]-P1[0]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
  tmp[1] = P1[1] + (P2[1]-P1[1]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
  tmp[2] = P1[2] + (P2[2]-P1[2]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
  
  Hit = tmp;
  
  return Hit;
 }

// Checks to see if the Hit point is in the box and which axis it's aligned with
function InBox( Hit, B1, B2, Axis) {
  if (Hit != 0) {
   if ( Axis==1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return 1;
   if ( Axis==2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return 1;
   if ( Axis==3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return 1;
  }   
  return 0; 
 }

// Check whether the line hit the box or not
function CheckLineBox(B1, B2, L1, L2, Hit) {
  if (L2[0] < B1[0] && L1[0] < B1[0]) return false;
  if (L2[0] > B2[0] && L1[0] > B2[0]) return false;
  if (L2[1] < B1[1] && L1[1] < B1[1]) return false;
  if (L2[1] > B2[1] && L1[1] > B2[1]) return false;
  if (L2[2] < B1[2] && L1[2] < B1[2]) return false;
  if (L2[2] > B2[2] && L1[2] > B2[2]) return false;
  if (L1[0] > B1[0] && L1[0] < B2[0] &&
   L1[1] > B1[1] && L1[1] < B2[1] &&
   L1[2] > B1[2] && L1[2] < B2[2]) 
   {Hit = L1; 
   return true;}
  if ( (InBox( GetIntersection( L1[0]-B1[0], L2[0]-B1[0], L1, L2, Hit), B1, B2, 1 ))
    || (InBox( GetIntersection( L1[1]-B1[1], L2[1]-B1[1], L1, L2, Hit), B1, B2, 2 )) 
    || (InBox( GetIntersection( L1[2]-B1[2], L2[2]-B1[2], L1, L2, Hit), B1, B2, 3 )) 
    || (InBox( GetIntersection( L1[0]-B2[0], L2[0]-B2[0], L1, L2, Hit), B1, B2, 1 )) 
    || (InBox( GetIntersection( L1[1]-B2[1], L2[1]-B2[1], L1, L2, Hit), B1, B2, 2 )) 
    || (InBox( GetIntersection( L1[2]-B2[2], L2[2]-B2[2], L1, L2, Hit), B1, B2, 3 )))
    {
   return true;
    }
  return false;
 }

Knowing that this test is for AABB, I've tested it to make sure that it at least works when being aligned at an axis at a time. Now, I need to figure out which of the suspected issue is causing the test failure:
- Applying transformation matrix to either box, ray, or camera
- The initial conversion of 2D to 3D coord of mouse is wrong
- Other unnoticeable bugs

But before I look for these errors, I think I will try out the other tests to see if they work any better. And maybe having another session with Andor will clear things up.