Hello everyone, and welcome back to another update! The past weeks been quite busy, but I am happy to announce I've made significant progress on the `CollisionHeightfield`, and a MVP is pretty much implemented! My next steps would be to finalize everything by extensively testing, adding documentation, and improving the collision tests. Right now `CollisionHeightfield` has collision tests for rays, spheres and boxes. One challenge I had this week was that different terrain renderers have different ways of generating triangles given a heightfield. I discussed this with my mentors and we decided to follow the tesselation order of ShaderTerrainMesh. I looked into ShaderTerrainMesh as will as Bullet's CollisionHeightfieldShape and I implemented a tesselation order that is more or less universal. I would like for it to be compatible with all the terrain renderers of Panda3D, which includes HeightfieldTesselator, GeoMipTerrain, and ShaderTerrainMesh. Currently I am using GeoMipTerrain to test it and it is looking great so far. Also, if time permits, I would like to create a sample case that showcases `CollisionHeightfield`, for example something like a character walking on uneven terrain. You can follow my progress of `CollisionHeightfield` by taking a look at my draft pull request: https://github.com/panda3d/panda3d/pulls/691. See you next week!
This week, I continue my implementation of CollisionHeightfield by implementing collision tests from box and from sphere. Much of this week consisted of conducting research to find box-triangle, box-box, sphere-triangle, sphere-box intersection tests. Using Christer Ericson's realtime collision detection book, I was able to implement those intersection tests into CollisionHeightfield. Having those tests available, I was able to complete box collision test and sphere collision test. My next step is to do some bug fixing, writing extensive unit tests, and adding BAM serialization. BAM is one of Panda3d's native file format, and implementing BAM serialization allows a user to import/export the CollisionHeightfield from/to files. I would also like to make the sphere collision test more efficient by implementing Bresenhaum's circle algorithm, which will reduce the number of triangles tested. Hopefully I will be able to add some extra features, such as a collision test from capsule. In the final two weeks, I will be looking forward to making a sample game that demonstrates the use of the new CollisionHeightfield class. See you next week!
Last week, I finished setting up the quad tree given a heightfield. This was a big step, because this week I was able to start implementing collision tests. The first one is from a ray. I started this week by implementing line into box algorithm (using the slab method), and then line into triangle (Möller–Trumbore) algorithm. Using the box intersection test, I was able to find the quad tree nodes that are intersected by the ray. After, I use Bresenhaum's line drawing algorithm to get the heightmap elements that are intersected by the ray. Finally, using line into triangle I find the intersection between the ray and the triangles at those heightfield elements. Future collision tests will most likely follow the same format: first a box intersection test and then a triangle intersection test. Next week, I will focus on implementing collision tests from sphere and box. See you then!
This week, I started to implement the CollisionHeightfield class. My implementation is based off of Tim Sjostrand's "Efficient Intersection of Terrain Geometry in Real-Time Applications". The idea is to reduce the amount of polygon intersection tests by dividing the heightfield into smaller sub-rectangles using a quadtree data structure. So, collision tests with the terrain will resemble a box intersection test, followed by a triangle intersection test. This week, I successfully set up the quad tree, and made good progress in the ray-terrain intersection test. Next week, I will be finishing up the ray-terrain intersection test and starting the box and sphere intersection tests. The highlight of this week is setting up the quad tree, because now the intersection tests should resemble intersection tests that Panda already supports (box, polygon, etc). See you next week!
At the start of this week, I revisited the box-into-capsule test and re-implemented a different algorithm. Instead of representing the capsule as two hemispheres and a cylinder, my mentor suggested to see it as a line segment defined the by its two endpoints. So, the algorithm finds the closest point on the box to the line segment, and then tests for intersections accordingly. One obstacle that came up was that I couldn't find the surface normal when the box directly intersected the line segment. I pushed my code to my PR and asked my mentors for some suggestions, and they recommended to use the box's center to determine the surface normal. I did so and am currently awaiting review on my PR! In the meantime, I also started on my collision heightfield by setting up the interface and generic CollisionSolid member functions. Next week, I will start implementing collision tests with the heightfield. See you then!