Hidden Surface Removal


June 2018
Download link: Click here

There's a common problem in computer science known as hidden surface removal, essentially 2d occlusion culling. The solution is a divide and conquer algorithm which runs in O(n logn). The problem goes something like this:

We say a line is uppermost at a given x-coordinate if it's y-coordinate at x is greater than all the other lines. Inuitively, a line is visible if at least some portion of it can be seen if you look down from y = ∞. You can assume that there are no points where three or more lines intersect, there are no vertical lines, and no two lines are parallel.



This problem comes with a few different flavors, so here are a list of a few:



My solution is a modified merge sort which gives a Line two extra variables, the range of x over which the line is visible. When a line intersects, then the left or right bound is decreased. If a line's interval completely overlaps another line, then the other line cannot be visible. Lines that aren't visible are "decreased" in the merge sort.