Over the past few weeks I've gotten introduced to the Gateware project and started contributing. I've discovered a new Vulkan bug (by accident), implemented a function that outputs an OBB given a transform, and began implementation on another function that finds the minimum penetration distance between two intersecting oriented bounding boxes and returns it to the user. I've learned a lot during this time which I will share in the following post.
During my first week I focused on getting my environment set up, reading through the code base and trying to compile. Given that this was my first time compiling and running the project I expected all tests to pass. Much to my surprise I was greeted with my first test failure. The issue was related to Vulkan and wasn't reproducible on others machines. After some debugging with Lari we found that it was related to the newer versions of Vulkan. We decided to table this for now as I was just getting started with the project and it worked fine on recent versions of the Vulkan SDK.
The next week consisted of implementing a function that would output to the user an oriented bounding box given a transform. An oriented bounding box consists of a center, extents (width, height and depth), and rotation. I was familiar with OBBs on a high level, but never worked with them directly before thus began my research. I learned about the difference between Axis-Aligned Bounding Boxes and Oriented Bounding Boxes and their different use cases. I learned what defined an Oriented Bounding Box and how, given a transform, one can generate the center, extent and rotation of a bounding box. This turned out to be pretty simple and my solution is as follows:
Luckily, Gateware's math library contains functions that already compute the data we need given a transform. This ended up being as easy as plugging the transform into these functions to get the center and rotation of the desired bounding box. The one extra step I needed to do was take the limits vector given by the user and scale it by half since the extents of the bounding box are half width, half height and half depth. After calculating these, I set the appropriate properties of the output bounding box and return SUCCESS to let the user know it was created.
The great thing about Gateware is that we are required to practice test driven development which means my work was not finished there. I then proceeded to create test cases for this function which consisted of:
- Given an identity transform, we output a centered OBB
- Translating an identity transform and then creating the OBB correctly sets the OBB center
- Given a transform with rotation correctly sets the OBBs rotation
- Given non-uniform extents still produces the correct extents for the OBB
- Given zero limits will produce an OBB with zero extents
I then did the same for a double variant, added to the interface and added a fallback function. After this my work was complete! I submitted a merge request, received some feedback and finally merged into the main branch. It was an awesome feeling knowing my code, however small, was live and possibly being used by people building games.
After this I decided to move onto another OBB function. This time the function was supposed to return the minimum penetration distance between two intersecting OBBs. Again, I started with research. I found that in order to detect two intersecting OBBs I would need to implement something called Separate Axis Theorem which luckily is well documented but also much more complex than the method you would use to detect collision between two AABBs. I read
Real-Time Collision Detection by Christer Ericson and started doing other research on topics that were fuzzy to me such as vector projection, cross products and how to use these to derive the information needed to complete this function.
After a talk with Lari I decided to see if there was anything in the codebase that could help me finish this function. Low and behold, I found a little (not so little) piece of code that was commented out with the function name IntersectOBBToOBB. Well that's awesome, someone had already started this and not only that but the function was practically finished! This was a relief but at the same time I felt like I had wasted so much time looking elsewhere and holding up development which would turn into a learning for me. I decided to start dissecting this function and figure out why it wasn't working the way the author intended.
Through debugging I found that we were initializing our out distance to 0.0f and then using this out distance in future comparisons when finding a new penetration depth in the form of (x < out distance) which meant that we were simply never updating out distance because the new penetration depth would never be less than the initialized zero! To solve this issue I created a variable local to the function that initialized to FLT_MAX. I then used this in our comparison so that the first time we found a new penetration distance it would be guaranteed to be less and on subsequent comparisons we would then be comparing against the current minimum penetration distance. There were a couple other issues that popped up after this but this was the root issue. We finally were returning the true minimum distance between these two objects.
I added some tests, clapped my hands together, but wait.. there was a failure. In one of my tests I simulate a separation of the two objects by moving the object by the minimum penetration distance found and then recheck for a collision, expecting no collision. The test was returning collision? After further inspection I realized it's because we add on an epsilon value to each axis. This epsilon value exists to prevent numerical instability when the boxes are near parallel. The problem with this is that we get an inflated projected radii so on the next call to the function (after we've separated the objects) our function will detect another collision even though the objects are geometrically separate. This is the issue I've been stuck on for the past week and I'm not sure what the best way to solve it is just yet. I don't want to just return an estimate as this could cause jitter for the user. I am currently researching open source physics libraries like box2d and qu3e to see how they handle similar situations as well as reading and watching material from other collision experts such as Dirk Gregorius, Erin Catto, and Randy Gaul in hopes to find an elegant solution to this problem.
If I can't resolve this soon, I plan on tabling it while I tackle the original Vulkan issue I encountered during my first week of set up as this is a more pressing issue that is currently affecting users on newer Vulkan SDKs. On to the next week of development!
