7DFPS – Day 3: Collision Detection/Response
Today I focused on getting a simple physics simulation running. The main work consisted of creating a collision detection system based on the BSP tree. I went for the well described approach from this thesis I have been using previously. I have to say that I don’t like the result yet. There are occasional slips where it seems to miss a polygon. Also slopes and stairs I did not care for yet. Jumping around the world is good enough for now. If I have time, I might go for this more solid “sweep”-based approach.
I also today implemented the split-plane algorithm/metric for the BSP tree generation. It is a very hard problem (actually it is NP-hard :-)) to find a good metric for the tree to be balanced and with minimal number of polygon splits. Currently, some rooms are completly covered in one convex leaf of the tree, but others are split because the algorithm sometimes has to favor a balanced split. I might try on improving the algorithm and add some additional weight if a split produces a convex subregion. This should then cater for all simple convex room to end up in their own leaf.
Here a screenshot of a room in the world, were each color represent one leaf in the BSP. Note how the whole room, because it’s convex, has ended up in a single leaf.
Oh; and I started on the portalizing of the world for the culling algorithm. I am not sure yet if I will be precalculation potential visibility sets on the BSP leafs or just portal-frustum-clipping approach during runtime. Even though I have a powerful laptop, I am always suprised how high the fillrate of modern graphics cards is. I am rendering thousands of polygons and don’t see any performance penalty yet. Ok, I don’t have any complex fragment shaders (using fixed-function pipeline API currently), but anyway…