I implemented the full Binary Space Partitioning (BSP) Algorithm! This can be used in projects when you need a BSP tree of your scene (e.g for depth sorting by painter's algorithm) After the tree has generated you can move the point P, around the outside of the shape to see how the line depth (indicated by colour: red = far, green = close) changes. ---------------------------------- Controls ---------------------------------- - Move camera: Click and drag on P - Toggle point handles: down arrow - Move point handles: Click and drag
The algorithm first generates a BSP tree from the edges (in O(n^4) time) and then with respect to the camera (P) it depths sorts the edges using a BSP tree traversal (O(n)) The pivot hyperplane used to partition the edges is chosen using a greedy algorithm, this minimizes the number of splits made. This was certainly one of the more difficult algorithms to implement, but after two weeks of debugging it's finally here! This makes use of my depth comparison algorithm: https://scratch.mit.edu/projects/548009733/
