I am happy to announce that `CollisionHeightfield` is near completion! This week, I added some finalizations to `CollisionHeightfield`, which included improving the collision tests and adding the getter/setters of the class. My next steps would be to push my unit tests to the PR, and provide sample code which demonstrates the new CollisionSolid in action. One goal that I did not get to accomplish was to implement BAM serialization for `CollisionHeightfield`. BAM is one of Panda3D's native file formats, allowing users to export Panda3D objects. Additionally, I did not add collision tests for lines and line segments. `CollisionHeightfield` currently has a collision test for rays, which is probably used more commonly than line/segments in regards to terrain. However, it would be nice to add these tests, especially since they are only slight variants of the ray collision test. Regardless, I am happy to announce that `CollisionHeightfield` is pretty functional as is. That is all for this week, check back next week for my final blog post!
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!