preparing play-area from boundary

Since Quest link has been introduced there was one thing that was a bit problematic. It was impossible to read “play area”. It was incorrect, too big, rotated, reaching outside the actual boundary. I reported it only to learn that there were other developers before me who also reported the issue but it has not been fixed.

When providing details for the bug and possible solution I found out that Oculus API is reading the boundary points correctly. The only problem was that the play area instead of being the biggest rectangle that fits INTO the boundary was just a rectangle that contained the boundary (with orientation just “as it is”). The same results I got for SteamVR.

For OpenXR it was also additionally offset but it seems that it was only because OpenXR by default has a centre in point 0,0,0 while Oculus API allows for offset centre.

I had everything I needed to try to implement an algorithm that would find the best rectangle that fits into the boundary. I heard that it is not a trivial task. I heard that it might be even impossible. And I was actually surprised to hear that as at least for the most common cases (more or less convex boundary) it seemed quite easy to do. For a few weeks, I had this task back in my head, coming up with better ways to find such a rectangle. And after 3 hours I had a working algorithm that successfully passed initial tests.

My approach is quite straightforward.

1. Reduce the number of points in the boundary – just remove all points that are closer than 5cm to the last added point.
2. Calculate the centre from the average of points – this should give a good enough central point that hopefully lies inside. For odd and twisted boundaries this is where the algorithm may fail.
3. Do the following points for angles -45 to 45 (no need to check more as all other angles are either the same or rotated by 90 degrees) I chose 5 degreeS interval
   1. move boundary points into local coordinates
   2. check intersections along x-axis
   3. divide that into 5cm segments
   4. for each segment check how far it can go in both directions along y-axis – this is an important step – it caches rectangles so there’s no need to do a bit more expensive segment intersections, note that the upper end is above 0 and the lower end is below 0
   5. for all possible rectangles along x-axis (two loops: left-x goes for all rectangles, right-x goes from right-most to left-x) find the rectangle that fits into chosen rectangles prepared in the step above (min for upper ends, max for lower ends) and check if that rectangle is the best match so far

Initially the “best match” was based purely on size but I modified it a bit to prefer rectangles that have a bit smaller difference between sides. Might still change that, though.

It works fast enough (at least when I tried for a maximum of 4×3 spaces).

There’s no need to try all possible rectangles. There could be some further optimisations. There should be a way to make sure that the “centre” is within the boundary. But for 3 hours of work, I’m quite happy with the results.

And most important, it should make it much easier for people to play the game as currently when starting the game, the play area was incorrectly read, it was too small, too big, offset or just completely wrong.