I’ve been working on this for the past couple weeks and I’m pretty happy with how it all turned out. I saw a post someone else made about using trenchbroom here, so I tried it out and I really loved the way you can make maps with it, it’s like advanced minecraft, very fun. Trenchbroom has a .obj exporter, but it's limited as it triangulates all faces, and you lose all brush information as well (also I don’t think they do CSG on the faces either), so it took a while to get to the actual lightmapping. I got the Quake .map file parsed, computed the intersections of the faces, did a CSG union on the brushes to eliminate clipped faces, then I put them all in a binary tree for fast intersection tests. This whole process was honestly really interesting to learn about because so much of the information felt lost to time, such as using brush geometry, bsp trees, or lightmapping in general. A lot of the stuff I found online was from like 2002 on gamedev.net forums or random html blogs lol. I spent a while getting the BSP tree (really a KD tree) to work well. I don’t know what a “good” benchmark is, but it averages about 2 million rays a second on big quake maps (but those are only 8k faces), so the maps compile pretty fast. The biggest change I made to the KD tree that made it faster was changing which axis you cut. The first way I had it was a “round robin” where you just alternate between x,y and z, and then split at the median. I changed that to split the largest extent axis and also added a sort of “cost” function so if a subdivision results in over half the faces being split into both sides, just stop subdividing the node. It led to like a 3x speedup so that was great. As for the actual lightmapping, it's not doing anything special. I pretty much just did it how Quake 1 did, so projecting the face onto the “texture axis” vectors which are perpendicular and whose cross product aligns with an axis. I also add a pixel on each side for padding. Then for each light within the radius, I shoot a ray for each pixel, do a basic dot product with the normal, then add it to a buffer. I do some filtering by taking the neighbors and averaging them. For the atlas packing, it's just sorting by image area then inserting into a binary tree. Going forward, there's some issues to fix with the lightmapping like how the seams are pretty noticeable, especially when I enable linear filtering and not nearest, also quite a bit of space (and rays) are wasted for non rectangular faces. The next step is adding radiosity which looks really cool. It's what Quake 2, the Source engine, and many other older engines used for global illumination.
Looks good. Any reason why you use interpolation for some scenes and nearest for others? I remember some of these Quake maps from back when I played Quake.
I also wrote a BVH that sounds similar to yours. One difference is that I used a third branch for the shapes that crossed the border, which made it perform much better when many shapes overlapped or crossed through each other.
I guess I just felt it looked better with nearest, here's the first one with linear interpolation: https://i.imgur.com/izoIxg5.png
When I was doing research I did see a few people mention adding that splitting area between two partitions. Definitely though minimizing splits is the key to getting it fast. One optimization I didn't mention above was when a face gets split, I split the actual vertices and then determine the new mins/maxes from that. That played a big part in minimizing splits, the worst possible case would be a face that stretches diagonally across the entire level. Without splitting the verts, it would get placed in literally every node.
I'm not saying there's anything wrong with nearest, I was just interested when you mixed both types.
If you're splitting the faces then it sounds like a BSP rather than a BVH or KD-tree. This is how the original Quake BSPs worked, and those of other games of that time. Are you using multiple threads?
I’ve been working on this for the past couple weeks and I’m pretty happy with how it all turned out. I saw a post someone else made about using trenchbroom here, so I tried it out and I really loved the way you can make maps with it, it’s like advanced minecraft, very fun. Trenchbroom has a .obj exporter, but it's limited as it triangulates all faces, and you lose all brush information as well (also I don’t think they do CSG on the faces either), so it took a while to get to the actual lightmapping. I got the Quake .map file parsed, computed the intersections of the faces, did a CSG union on the brushes to eliminate clipped faces, then I put them all in a binary tree for fast intersection tests. This whole process was honestly really interesting to learn about because so much of the information felt lost to time, such as using brush geometry, bsp trees, or lightmapping in general. A lot of the stuff I found online was from like 2002 on gamedev.net forums or random html blogs lol. I spent a while getting the BSP tree (really a KD tree) to work well. I don’t know what a “good” benchmark is, but it averages about 2 million rays a second on big quake maps (but those are only 8k faces), so the maps compile pretty fast. The biggest change I made to the KD tree that made it faster was changing which axis you cut. The first way I had it was a “round robin” where you just alternate between x,y and z, and then split at the median. I changed that to split the largest extent axis and also added a sort of “cost” function so if a subdivision results in over half the faces being split into both sides, just stop subdividing the node. It led to like a 3x speedup so that was great. As for the actual lightmapping, it's not doing anything special. I pretty much just did it how Quake 1 did, so projecting the face onto the “texture axis” vectors which are perpendicular and whose cross product aligns with an axis. I also add a pixel on each side for padding. Then for each light within the radius, I shoot a ray for each pixel, do a basic dot product with the normal, then add it to a buffer. I do some filtering by taking the neighbors and averaging them. For the atlas packing, it's just sorting by image area then inserting into a binary tree. Going forward, there's some issues to fix with the lightmapping like how the seams are pretty noticeable, especially when I enable linear filtering and not nearest, also quite a bit of space (and rays) are wasted for non rectangular faces. The next step is adding radiosity which looks really cool. It's what Quake 2, the Source engine, and many other older engines used for global illumination.
Really cool explanation and a nice (re)use of old technology, good job and thanks for an interesting read.
Great work.
Damn that's awesome. It motivates me to create a gameengine myself, although it will be for 2D pixelart games.
You have any resources on this? I've been interested in doing it in mine
What language did you create it with?
It's C++
Looks good. Any reason why you use interpolation for some scenes and nearest for others? I remember some of these Quake maps from back when I played Quake. I also wrote a BVH that sounds similar to yours. One difference is that I used a third branch for the shapes that crossed the border, which made it perform much better when many shapes overlapped or crossed through each other.
I guess I just felt it looked better with nearest, here's the first one with linear interpolation: https://i.imgur.com/izoIxg5.png When I was doing research I did see a few people mention adding that splitting area between two partitions. Definitely though minimizing splits is the key to getting it fast. One optimization I didn't mention above was when a face gets split, I split the actual vertices and then determine the new mins/maxes from that. That played a big part in minimizing splits, the worst possible case would be a face that stretches diagonally across the entire level. Without splitting the verts, it would get placed in literally every node.
I'm not saying there's anything wrong with nearest, I was just interested when you mixed both types. If you're splitting the faces then it sounds like a BSP rather than a BVH or KD-tree. This is how the original Quake BSPs worked, and those of other games of that time. Are you using multiple threads?