Post Reply 
HHC 2021 - Lines and graphs presentation
10-16-2021, 01:24 PM
Post: #4
RE: HHC 2021 - Lines and graphs presentation
Semi-related: Linear programming can be useful in rendering. (Skip this post if you're not interested in that.)

I once wrote a software renderer. Not much came of it afterwards (other than this), but I learned a lot about rendering in the process. It uses Binary Space Partitioning, and a well-performing algorithm for an important function on BSP trees (merging two together) relies on linear programming.

The role of linear programming there is to check if the constraints given by "on this side of this plane, on that side of that plane, etc." can be satisfied by any point at all. If they can't, then the algorithm knows that it's pointless to keep iterating into child nodes of the BSP tree, since points / polygons / nodes will always be outside this impossible space.

In its simplest description (as above), the algorithm uses linear programming in a space with the same dimensions as the trees (i.e. 3D in real-world cases), but I'm proud of the fact that I managed to break it down for my particular implementation into 1-dimensional linear programming. For those who understand BSP in general and want to replicate that:
- When merging BSP trees, you iterate through one tree and repeatedly cut the other along the plane representing the current node. This gives us the opportunity to work in that (2D) plane only, instead of the whole space.
- To cut a tree along a plane, you iterate through that tree and cut each node's plane along the input plane. This is the step where the linear programming problem actually needs to gets solved. Since we're traversing a tree, you can make it so that the solution found for the parent is handed down into the child's problem, and the linear programming problem is shaped such that you can build on this solution by adding a piece that has one less dimension than the whole problem - in each step descending along a tree you add a single constraint, so you only check if that switches the problem from feasible to infeasible.

Anyway, just wanted to get a real-world application of this concept off my chest. Carry on!
Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
RE: HHC 2021 - Lines and graphs presentation - 3298 - 10-16-2021 01:24 PM

User(s) browsing this thread: 1 Guest(s)