Going to travel back in time for this post. I can't think of a great way to start this off so I am just going to start with providing context.

2019-11-08

It is Friday the 8th of November 2019. I was in the middle of my last semester of my Computer Science undergrad and had just become enamoured with all things related to graphics programming. I had just got my vulkano based renderer working was ready to start implementing some proper interactivity to my game engine.

Having already spent the past couple of years working on websites as part of my work as a research assistant, I wasn't too keen on jumping into the UI straight away. That left mouse picking as the prime candidate for my next big feature.

I had recently come across a video by ThinMatrix which went over basic mouse picking in a 3D game (highly recommend this channel), which got me to this mouse picking and raycasting and tutorial.

Equipped with the video and fantastic visual tutorial, I had everything I needed to get started. I immediately started adding the structures I needed to support the outlined logic. First and foremost I needed to be able to invert my 4x4 matricies in order to go from screen space to world space (if you are unfamiliar with graphics programming this basically means I needed a way to take a pixel on the screen to a point in my 3D world, or rather a direction vector from the camera into the world).

So that was something I hadn't done in a couple years but with google, all things are possible. Within a few hours I was able to perform a refactor on how I handle matrices (in order to make the math easier on my brain), get inversion of a 4x4 matrix working, and get a mouse ray (direction vector which represents the mouse) in world space from screen space.

At this point I was feeling quite good, this wasn't all that bad, just a lot of math. Lots and lots of fiddly math with lots of moving parts I may or may not have fully understood... None the less, now that I had the mouse ray I was ready to start checking for collisions with objects in my world. At this point I only had cubes in my world. I figured the provided example of collision detection with a plane in the tutorial would be a great place to start, since cubes are really just 6 finite planes right?

2019-11-09

Well I was able to finally get 3D picking against planes implemented per the reference material. It had taken me just over 6 hours to get this done and my commit message, 3d picking sort of working, doesn't sound all that confident in the implementation. What happened? This is where our 24 hour debugging story begins.

As far as I can recall this commit wasn't a "feature complete" kind of commit, it was more of a "my brain no longer works so I am pushing my code now and going to sleep" commit. Looking through my OBS directory from that night I found this video timestamped right before this commit time.

The behavior you see in this video is that when a cube is successfully picked it enlarges a bit (this changes to something more sensable in the next videos). The peculiar part is that the cube centered at the origin of the world is always picked properly but when I try to mouse over other cubes they are not picked as you would expect.

I must have really been struggling with understanding the issue at hand in my code, I vividly remember my first thoughts upon waking being about directional vectors in 3D space and trying to visualize the math I had just written code about the night before.

First thing I did once I got back to coding was add some debug drawing which would show the triangles which make up the cube as well as use those lines to indicate a successful pick. This commit message, debug draw to show plane collisions, going to try some crazy stuff now, can give you some indication just how lost I was on this issue. Fortunately I have a video from the state of the project as well.

So I now had a better way of seeing the objects which are being picked. I knew it had something to with how the collision between the mouse ray and the object was being calculated but that was really all I knew. My first thought was that maybe my test to see if the point is on the plane or not is wrong so I practiced a bit more google magic and found this site which inspired hope.

This site covered two ways of checking if a point was inside of a triangle: Same Side and Barycentric. I am not entirely sure where I found my original reference for this calculation but based on what I had initially, I seemed to be doing something similar to the Same Side technique.

At this point, I was grasping at straws in an attempt to fix my mouse picking. Math filled code ahead warning, not important to understand, just an example of my desperation to find a fix. I rip out my Same Side code which looks something like

//...
// calculate distance from camera to plane, from https://antongerdelan.net/opengl/raycasting.html
let t = -((camera_origin.dot(&plane.norm))
    + (plane.norm.dot(&plane_point.truncate(Dim::W))))
    / (mouse_direction.dot(&plane.norm));

// if t > 0, plane is in front of camera so continue with checks
// otherwise it is behind the camera, continue to next plane

// calcuate point in world space where our mouse ray intersects with our cube's plane
let point = t * mouse_direction + camera_origin;
// move our 
let p1 = model * Vec4::from_vec3(tri_one.p1);
let p2 = model * Vec4::from_vec3(tri_one.p2);
let p3 = model * Vec4::from_vec3(tri_one.p3);
let mut in_bounds = true; // this gets flipped to false if fail for first triangle
let p1 = p1.truncate(Dim::W);
let p2 = p2.truncate(Dim::W);
let p3 = p3.truncate(Dim::W);

// this check is 
// edge 1
let edge = p2 - p1;
let vp = point - p1;
let cross = edge.cross(&vp);
if plane.norm.dot(&cross) < 0.0 {
    in_bounds = false;
}
// same checks for edges 2 and 3
// if collision not found in this triangle, check other triangle on same side of cube
// ...

to something a bit more esoteric

// same t calculation and check from above
//...
// On plane, check for triangle bounds
let point = t * mouse_direction + camera_origin;
let p0 = model * Vec4::from_vec3(tri_one.p0);
let p1 = model * Vec4::from_vec3(tri_one.p1);
let p2 = model * Vec4::from_vec3(tri_one.p2);
let p0 = p0.truncate(Dim::W);
let p1 = p1.truncate(Dim::W);
let p2 = p2.truncate(Dim::W);
let v0 = p2 - p0;
let v1 = p1 - p0;
let v2 = point - p0;

// I don't have a great way of explaining this math in text but Sebastian Lague 
// has a great video on this, linked below.
let dot00 = v0.dot(&v0);
let dot01 = v0.dot(&v1);
let dot02 = v0.dot(&v2);
let dot11 = v1.dot(&v1);
let dot12 = v1.dot(&v2);

let inv_denom = 1.0 / ((dot00 * dot11) - (dot01 * dot01));

let u = ((dot11 * dot02) - (dot01 * dot12)) * inv_denom;
let v = ((dot00 * dot12) - (dot01 * dot02)) * inv_denom;
// ...

That was about an hour of work, finding that math and swapping it out based on the commit timestamps. Unfortunately this made no difference as far as a I could tell. I was completely at a loss.

For the next few hours I can't really recall what transpired, I think I may have taken a shower and stared into space, hoping the answer to my problem would come from some sort of epiphany.

2019-11-10

It is now Sunday, but I haven't slept yet. Based on the screen recordings I have, I seem to have had a different epiphany of sorts around 3:34 AM. I had the fantastic idea (fantastic to me at the time anyways), to draw all of the information I had. Previously I was logging this information but it's really all gibberish after a certain point.

In this video you can see I implemented several new debug line drawings. When I pressed the middle mouse button, I would store the following debug lines and draw them until another middle mouse button press was recorded

• Drawing the 3 unit vectors which make up the camera's orientation in the world
• Any collisions with any entity in the world, this included:
  • the point of collision on the plane
  • the normal vector of the plane (this is the key to saving my sanity)

Along with these collision drawings, I had begun drawing the normal vectors of each cube face to rule out any other possibilities. I believe I spent a few hours getting these cube faces correct, I had previously been drawing a few of the backwards but hadn't noticed due to render settings.

In a second pass of using these new debug drawings I discover the key to my issue, something is mirrored!

Just before this video ends I noticed that the surface normal of the plane which is registered as the picked plane is pointing up instead of the expected down. Beyond this we are seeing collisions no where near the cube and it was the only object in the world at the time so I knew I needed to go over all of my math and double check I had my signs right.

Within 15 minutes I had found the culprit, when parsing the raycasting component of the Anton Gerdelan tutorial, I had blindly implemented the distance calculation using the same symbols and signs as depicted in the diagram. After a careful analysis of the math I realzied 2 things I had wrong in my distance calcuation

1. I was transforming a world space coordinate into world space again accidentaly, this explained why the cube centered at the origin was working mostly as expected while others weren't.
2. My plane point of collision offset sign was flipped. I saw that the dot product of the plane's normal and the point of collision plus some scalar d equaled 0, and I also saw that the t calculation added d to some other value so I blindly used the result of plane's normal and the point of collision as d; when in reality d is meant to perform the cancellation of this value, i.e. take the negative value of that result. This is why I was seeing a mirroring effect in some cases.

And below shows the extent of the changes I needed to make in my collision detection code to get mouse picking working

Before

let plane_point = model * Vec4::from_vec3(plane.point);
let t = -((camera_origin.dot(&plane.norm))
        + (plane.norm.dot(&plane_point.truncate(Dim::W))))
        / (mouse_direction.dot(&plane.norm));

After

let t = -((camera_origin.dot(&plane.norm)) - (plane.norm.dot(&plane.point)))
            / (mouse_direction.dot(&plane.norm));

This was a super gnarly combination of miscalculations. On their own, either one of these would have caused failure with the mouse picking, but having both of these at the same time made it quite the task to debug due to the chaotic nature displayed by both of these bugs compounding one anothers error.

Finally at 3:47 AM I pushed the working version of 3D mouse picking in my game engine, with overwhelming joy and quite evident sleep deprivation I pushed the final commit with the message, ladies and gentlmen, we got em [sic]. Here is one final video showing it working in all its glory.

I had implemented very simple logic for moving the objects, but it seems I already had my next task lined up just as soon as the previous one wrapped up.

Even though this was entirely my fault in not properly understanding the math I was referencing, this process gave me the opportunity to really solidify my understanding of a few topics that were a bit fuzzy to me. It also gave me the confidence that no matter how silly the bug, if you draw enough lines you will eventually find the flipped vector or something.

Likely my fondest memory out of all of this will probably be the feeling I had at 3 AM on a Sunday night analyzing random vectors in 3D space trying to make sense of it, in all honesty it made me feel like Batman from Arkham City when he goes into detective mode.

Here is the git log of the commits that transpired over the course of getting 3D picking working:

commit ad126a4d3017e67df96342c99dca5c7f7a05f681
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Sun Nov 10 03:47:45 2019 -0500

    ladies and gentlmen, we got em

commit 21a554443f8a5119777e7878bb8c1beda649373b
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Sat Nov 9 15:43:50 2019 -0500

    swap bounds check on plane to use barycentric test, seems my planes are off a bit

commit 7fdd1ba0799b976d6bcf714ba495e9d8a4fddd2b
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Sat Nov 9 14:56:12 2019 -0500

    debug draw to show plane collisions, going to try some crazy stuff now

commit f7a861b37ced0af66a13d1d1e250306e3c5f6684
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Sat Nov 9 01:52:36 2019 -0500

    3d picking sort of working

commit 06870a4aa62438d2fc0a76756a85a06b06aae443
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Fri Nov 8 19:19:17 2019 -0500

    getting direction ray in world space from mouse

commit 8251d19f2bccccba61e7f42ce4fca3f67fce9eca
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Fri Nov 8 18:19:59 2019 -0500

    can invert Mat4 now

commit e4b90657b9091e5373bc5a1f2adf2553193e09bc
Author: Alec Goncharow <Alec.Goncharow@gmail.com>
Date:   Fri Nov 8 16:12:56 2019 -0500

    we column major now