How do I partition an oriented bounding box?

Question

I am writing code that will build an oriented bounding box (obb) tree for a (not necessarily convex) polygon in 2 dimensions.

So far, I'm able to find the area-minimal obb of a polygon by finding its convex hull and using rotating calipers on the hull.

The picture below is an example of this. The yellow-filled polygon with red lines and red points depicts the original polygon. The convex hull is shown in blue with black lines and the obb is shown as purple lines.

(Edit) As requested: Interactive Version - tested only in chrome

Now I want to extend my code to build an OBB tree, instead of just an OBB. This means I have to cut the polygon, and compute new OBBs for each half of the polygon.

The recommended way to do this seems to be to cut the polygon by cutting the OBB in half. But if I cut the obb through the middle in either of its axes it looks like I would have to create new vertices on the polygon (otherwise how do I find the convex hull of that partition?).

1. Is there a way to avoid adding vertices like this?
2. If not, what is the easiest way to do it (with respect to implementation difficulty)? What is the most runtime-efficient way?

Answer 1

Here's an example of a concave polygon that we want to create an OBB tree for:

In order to split it into a new set of concave polygons, we can simply cut our current polygon by cutting the bounding box down the middle and adding new 'intersection' vertices as appropriate:

:

This can be done in O(vertices) time because we can simply iterate through all of the edges, and add an intersection vertex if the edge crosses the red splitting line.

The polygon can then be divided in terms of these intersection vertices to get a new set of smaller (but still possibly concave) polygons. There will be at least two such polygons (one per side of the red line) but there may be more. In this next picture, the new polygons have been colored for emphasis:

Recursively computing the oriented bounding boxes for these smaller polygons gives the desired result. For example, here are the boxes from recursion depth 2:

Hopefully this is clear enough to help someone who's struggling the same way I was!

Answer 2

I'm not really sure this is what you need without further context, but here goes...

Subdividing a concave polygon into a set of convex polygons

In my comment above I suggested recursively subdividing the concave polygon in order to obtain a set of convex polygons instead. One (common) approach is the following:

1. If the polygon is convex, stop. (add the polygon to an array, I suppose)
2. Select an unmarked edge of the polygon. Mark the edge.
3. Split the polygon across the edge (actually: the infinite line coinciding with the edge).
4. Recursively repeat this algorithm for both result polygons (if non-empty).

Note: This is exactly how a BSP tree is built. Except in the algorithm above we're not building tree nodes and storing polygons in them. Maybe a BSP-only solution would be a solution to your problem as well (instead of using OBBs).

Testing a polygon for convexity (step 1)

For each edge, classify each vertex as on, in front or behind the edge. All vertices should be on or in front of the edge. If not (at least 1 vertex behind the edge), the polygon is concave. For details on the 'classifying' part, see my answer to a different question, which does this as well.

The rest

Once you have the list of convex sub-polygons, you could generate OBBs for them as you've done in your original post. You would not have an OBB tree though...

With the subdividing, you are adding vertices (a concern in your question). Depending on your application you may not need to use the subdivided polygons though: If you were to use a BSP tree and only needed simple collision you'd just traverse the tree and do some point/edge classifications and not deal with any polygon vertices.

Anyway, not really sure what to recommend further since I don't know what you want your application to do, but hopefully this is of some help.

Edit: I just realized that maybe this is what you want to do: Build a BSP tree and generate OBBs for each node, from root to leaf nodes. So the root node OBB would contain the entire concave polygon, and leaf nodes only convex sub-polygons. I remember the original Doom engine does something similar (except with axis-aligned BBs).