I thought this would be an interesting topic to share, as there is a lot to be said about this algorithm and its use in 3D engines on Scratch.


WHAT IS BSP?
BSP, which is short for binary space partitioning, is a recursive algorithm which subdivides a scene into convex sets using hyperplanes(these are lines in 2D, and planes in 3D) and stores them in a binary tree. This data structure is useful for visible surface determination(VSD), and for collision detection. The BSP tree can be traversed in linear time. See this for more information: Binary Space Partitioning on Wikipedia.

SIMPLY PUT:
Very simply put, it can take a 3D scene, chop it up and render those pieces in an order as to efficiently and perfectly sort the scene.

A SHORT HISTORY ON BSP
BSP was developed in 1969 for the U.S. Air Force to accelerate graphics for a virtual environment. At the time, the hardware acceleration which many computers have today, was not available. In 1980, a fully automated algorithm was used to generate the BSP tree. This is the original paper on the implementation. In 1991, a new BSP algorithm was created to render the scene front-to-back as opposed to back-to-front. It was later used to render maps in the videogame Doom with minimal overdraw. Rasterizing the scenes in Doom took a lot of processing, therefore avoiding overdraw was critical for ensuring real-time rendering.

SOME HISTORY AND INFORMATION ON BSP IN SCRATCH
The first ever implementation of BSP on Scratch may have been https://scratch.mit.edu/projects/212388708/ by @ajzat25 in 2018. This project seems to use 2D space partitions, much like Doom. It also seems to use a special algorithm “portal occlusion” which uses “visibility portals” in order to speed up rendering. All of the data generation seems to have been external and imported. Another possible first-ever implementation of BSP was made by @Vadik1 in the same year: https://scratch.mit.edu/projects/206092388/. Vadik1's implementation was quite different in that it was recursive but did not actually generate a tree structure. This made it possible for geometries to be fully dynamic, and be autopartitioned in real time(autopartitioning is the term for the fully automated method presented in the SIGGRAPH paper, this paper will also be important context for later). The project was also a 3D rasterizer, unlike ajzat25's.

It was not until a few years later when I made an engine based off of Vadik1's accurate sorting method in 2021. This rendering code was used in my Gamma Engine(BETA): https://scratch.mit.edu/projects/637062431. I would also like to point out that I did experiment with BSP in 2019, but the code was too slow and buggy. Gamma Engine BETA features many novel graphics effects which are made possible by partitioning algorithms. It renders polygons without typical artifacts, it features dynamic shadows, and different types of portals.

Up to this point, many of the fastest of all 3D engines of Scratch did not seem to have any significant room for optimization. Vadik1's method of BSP got exponentially slower as polygons were added to the scene. As a result, Gamma Engine was among the slowest of all engines. Even the fastest 3D engines weren't really capable of rendering models of any more than a few hundred polygons in 30 FPS.

Soon later, Vadik1 posted another project: https://scratch.mit.edu/projects/649528399/, which employs the aforementioned portal occlusion, as well as BSP which was pre-generated and traversed in real-time. This time it was in 3D. This engine could handle very large scenes because of its linear, as opposed to exponential, relation to polygon count and time taken to render. The only problem was that this engine could only render axis-aligned rectangles, and could therefore not render any polygonal model.

Around a month later, @Chrome_Cat created a project with all the code to generate a BSP tree with arbitrary 2D lines: https://scratch.mit.edu/projects/701091508/. It was less than 1000 blocks of code. Chrome_Cat used this algorithm for his “3D Tilt Maze” project. It was based off of the previously mentioned paper in the ‘80 SIGGRAPH journal. This code would also eventually be the basis for his ChromeEngine development, as well as my Gamma Engine(GAMMA). Both are upcoming 3D engines. At this time, it was clear that Chrome_Cat’s 3D engine was the fastest of many other Scratch 3D game engines. The upcoming ChromeEngine will support both dynamic and static geometries.

Chrome_Cat is planning to share a tutorial on the exact BSP sorting algorithm, which he wrote in a document, as well as a few other tutorials and documentation.

I would also like to note that as of 21 Jun 2023(I started writing this during May 2023 but forgot about it), Chrome_Cat released a demo of his ChromeEngine: https://scratch.mit.edu/projects/868045282/.

Also, ajzat25 shared a 3.0 compatible demo project on 12 Jun 2023: https://scratch.mit.edu/projects/411164977/

A few other Scratchers have also tried making their own engines which use BSP to speed up rendering and to sort scenes perfectly. @alltrue recently shared https://scratch.mit.edu/projects/848051377/.

WHAT NEXT?
I personally think there is a lot to expand on with 3D BSP on Scratch. It is hard to implement and use, which seems to deter a lot of Scratch 3D programmers and make it a lesser-known method. However, I believe that many possibilities can be unlocked with BSP.

WHERE TO FOLLOW THE CURRENT PROGRESS
You can follow the work of most of the mentioned Scratchers(everyone mentioned but ajzat25) at the 3D Graphics on Scratch studio: https://scratch.mit.edu/studios/32030084/



If there are any issues or inaccuracies in this post, please tell me. Also, if you want to link a project which implements BSP(of yours, or one that you found), feel free! I would love to see more of them! Thanks!

And have a nice day!

bump… also, should this be moved to the Advanced Topics forum?

littlebunny06 wrote:

bump… also, should this be moved to the Advanced Topics forum?

I mean It's advertising scratch projects and not really too much like other stuff but ST can decide if they think it's better.

Bump. I will report my post to be moved to the AT forum, I think it is more fit to be there.

I recently become more aware of Carmack's/idTech's work with DOOM and Quake(Quake especially). Fuchs' autopartitioning algorithm does not seem to create trees that are good for Occlusion culling stuff. The solution which can be seen in both idTech games: Leafy BSP. This is where the geometries are stored entirely within the leaves of the tree.

The “Matt's Ramblings” channel on YouTube has some good in-depth explanation on how BSP works in Quake, while still being quite comprehendible to someone who knows little about it. I also learned of some of this through the “Graphics Programming Black Book” by Michael Abrash, a coworker of Carmack. It is a heavy read but certain chapters detail the many graphics techniques the developers employed to get quake running like it did back then. Not only that, it explains what they tried, what failed, and what stuck… and for what reason.

I think something crazy to try might be the Potentially Visible Set(PVS), which can be seen in Quake. One problem might be that Quake used “brushes” for geometry, while my engine uses a “polygon soup”. Even still, learning about PVS from Quake should be helpful.

I think I will work on either two things next(If I do): Making an algorithm that converts non-leafy polygon aligned BSP trees(produced by autopartitioning which I already have) into leafy BSP trees, Making an algorithm that creates a leafy tree directly from a polygon soup.

I'm not sure which is best, but one might be harder than the other. I think former is easier but results in poor-quality maps, while latter is harder but
likely reduces splits.

This 1991 paper explains some technical details behind the PVS algorithms which Quake used, and was referenced in Abrash's Black Book:
Teller's Visibility Preprocessing For Interactive Walkthroughs

So is BSP just rasterization but faster?

jakey13l wrote:

So is BSP just rasterization but faster?

Kinda! So far, many of us who implemented it into Scratch have used BSP to rasterize scenes using painter's algo. There is much more to it than painting perfectly and quickly though! Also, BSP in practice is usually actually no faster than fast z-sort rasterizers (assuming both use painter's).

The “more to it” things are stuff that idTech popularized in Quake and DOOM. Occlusion culling(Relatively simpler front-to-back BSP traversal in DOOM, PVS and other advanced stuff in Quake), and collision optimization.

I found a pretty interesting high-level description of BSP which may be helpful for understanding some graphics applications of this algorithm, particularly the concept of “Adjacency, portals and neighborhoods”: https://github.com/rschifflin/bsp

It also contains an implementation in the Scheme language.

I have implemented a “leafy” BSP heuristic. Its far more robust as it pushes polygons down the tree instead of storing them in intermediate nodes, resulting in convex sectors bound by the partitioning planes. These sectors can then be tested for adjacency and used to form a graph that can be traversed for potentially visible sets, as detailed in Teller's Ph.D. thesis, and implemented in Quake. To form the graph, there must also be a new geometry type called the “portal”, which forms the faces between each sector. These portals can be used to determine whether two sectors have a shared gap between them. This forms the basis of PVS culling.

An issue with this heuristic is that it generates more nodes per tree and tends to also generate more splits, and therefore more total polygons. Since I'm aiming for gameplay/scenery that would benefit from sectorization and occlusion culling, this shouldn't be too much of a problem.

littlebunny06 wrote:

I have implemented a “leafy” BSP heuristic.

*Algorithm, not heuristic ^^;

Some time has passed since I last posted many updates. I have been looking into the code of the Quake and Source engines. I already got an automatic portal generation algorithm in progress. It uses the BSP tree to insert and cull portals which end up covering the boundaries between empty leaves(back to this term later). I still have to improve the algorithm before it can be used to generate scene PVS.

Quake used a “leafy” BSP tree to store its geometry in a tree. It called its geometry “brushes”. Brushes, in Quake lingo, are basic shapes of tacit convexity, as they are defined by plane partitioning operations. Furthermore, the faces on the brushes are pushed into the “empty leaves” of the tree. It is assumed that the space behind the faces are made up of solid material, and the space in front of the faces are just air. You will always end up on a leaf when traversing down the tree. Upon locating this leaf, if it has no faces stored in it, it can be assumed that it is solid space. Ironically, it is the leaves with faces which are considered empty.

Right now, I am working on collision and quake-style movement. The collision detection involves tracing an AABB through the tree, and finding the nearest intersection point, as well as the brush/face of contact.

I will post links to relevant resources once I complete the movement in my 3D engine.