Articles on hecris's Blog

Week 11-12 Check-In

hec@bxscience.edu (hecris) — Mon, 26 Aug 2019 03:33:15 +0000

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!

Week 9-10 Check-In

hec@bxscience.edu (hecris) — Fri, 09 Aug 2019 02:10:41 +0000

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!

Week 8 Check-In

hec@bxscience.edu (hecris) — Mon, 22 Jul 2019 17:37:01 +0000

Welcome back!

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!

Week 7 Check-In

hec@bxscience.edu (hecris) — Mon, 22 Jul 2019 17:29:28 +0000

Hello again!

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!

Week 6 Check-In

hec@bxscience.edu (hecris) — Wed, 10 Jul 2019 16:14:34 +0000

Welcome back!

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!

hecris

Week 5 Check-In

hec@bxscience.edu (hecris) — Wed, 10 Jul 2019 14:34:52 +0000

Hello everyone!

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!

hecris

Week 4 - First Evaluations

hec@bxscience.edu (hecris) — Mon, 24 Jun 2019 20:01:38 +0000

Hello! This is my check-in for week 4, right before the first student evaluations. In the past month, I have implemented parabola-into-box and parabola-into-inverse sphere with the help of my mentors. Recently, I attempted box-into-capsule, but after discussion with my mentor, we decided that I would skip ahead to implementing the Heightfield class. I hope to revisit box-into-capsule, perhaps during the "code-break" week, to nail it down. In the meantime (starting week 5) I will begin implementing the Heightfield MVP: being able to construct it using a PNMImage, visualizing it, and an intersection test with an infinite line. Check back next week for more updates!

Week 3 Check-In

hec@bxscience.edu (hecris) — Sat, 22 Jun 2019 01:40:56 +0000

Hello again! Sorry for the late post, I have fallen behind in schedule (I will talk about that later) but nevertheless this post will act as my Week 3 check-in. Let's start with the good news! Last week, I submitted my parabola into inverse sphere collision test. After reviewing with my mentors, I realized that the surface point and surface normal were a little inaccurate. With the help of my mentors, I spent a little bit of week 3 fixing the surface point and normal and now my collision test is merged!

For week 3, my primary objective was to implement a box into capsule collision test, and it is still quite the challenge. There were many approaches that I tried but none of them were sufficient. The approach that I decided to stick with was to represent the capsule as 3 parts: 2 hemispheres and a cylinder. My initial attempt was naive; I tried to convert the box into the capsule's coordinate space, and test the box for intersection with the cylinder. However, I realized that it was difficult to test for intersection when the box was in the capsule's coordinate space. Instead, I converted the capsule into the box's coordinate space, and proceeded to find the nearest point on the box to the capsule's center. After, I convert this point to the capsule's coordinate space where it's aligned with the y axis, and do a cylinder test. This method seemed to work, and after finalizing it I sent in a pull request to the main repository.

After some discussion with my mentors, I realized that finding the point on the box closest to the capsule's center was not reliable. This is because the point closest to the center is not necessarily the point that is intersecting with the capsule, especially when the capsule is slanted to an angle! There is also some discussion on which part of the cylinder should be tested first. Currently, the cylinder part of the capsule is checked first and the endcaps second.

This week (week 4), I was supposed to start implementing the Heightfield class. This consists of being able to construct it using a PNMImage and an line intersection test. As you can see, I am still caught up in box into cylinder but I am determined to nail it down. However, if I continue to struggle with it, then I might have to postpone the capsule test perhaps until the "code-break" week and begin the Heightfield test. I still have hope that I can take the remaining weekend to finish box into capsule. I will update you on how it goes!

Week 2 Check-In

hec@bxscience.edu (hecris) — Sun, 09 Jun 2019 15:32:14 +0000

This second week has been quite busy. Last week, I proposed a simple algorithm for Parabola into Box: iterate through the six planes of the Box and test for intersection with the parabola. Turns out, this algorithm was a bit too simple. After discussion with my mentors, I realized that the intersection point has to be behind all other planes of the box for a collision to exist. I spent a good part of Week 2 fixing my algorithm. One obstacle I came across was that at the corner of the box, it did not seem to pass my collision test. After talking to my mentors, I realized that it was only a matter of perspective. By using a different lens I confirmed that it was working correctly. After updating my pull request the algorithm is now merged!

For the second half of Week 2, I worked on Parabola into Inverse Sphere. As usual, I started off by writing some unit tests. This time, I made a test program (based off of my mentor's) to visualize the parabola and inverse sphere. I implemented the following algorithm: recursively subdivide the parabola into "close-enough" line segments, and test their intersection with the sphere. After passing all tests and appearing to be correct using the visualizer, I submitted a pull request for discussion and review.

Next week, I am scheduled to work on Box into Capsule detection. However, I will discuss with my mentors if it would be better to start working on the Heightfield class. I am excited for whatever comes next!

hecris

Week 1 Check-In

hec@bxscience.edu (hecris) — Sat, 01 Jun 2019 21:42:48 +0000

Hello again!

For this first week, my goal was to implement Parabola into Box detection. I started off by writing some test cases that attempted to collide the CollisionParabola into CollisionBox. Of course, since no detection exists yet, the tests initially failed, but writing them put me in the direction to brainstorm about possible solutions. I decided to implement a simple algorithm: iterate through the 6 faces of the box, test their intersection with the parabola, and find the earliest point of intersection. If an intersection is found, it will return the surface point and surface normal. After passing all test cases, I opened a pull request to the main repository for review and discussion. My first week went well, with no significant obstacles.

For the remainder of the week, I will think about ways to improve my Parabola into Box algorithm. Additionally, I will start looking into the CollisionInvSphere to prepare for next week's goal: Parabola into Inverse Sphere. I anticipate that this will be more challenging and I can't wait to take it on. Stay tuned for next week's update!

hecris

Welcome!

hec@bxscience.edu (hecris) — Wed, 29 May 2019 02:15:58 +0000

Hello and welcome to my blog! This summer, I am excited to be working on Panda3D to accomplish the following goals:

Parabola into Box detection
Parabola into Inverse Sphere detection
Box into Capsule detection
Implement a Heightfield class for collision with uneven terrains

The coding period has officially begun, so stay tuned for my weekly updates!

hecris