6

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?
Improve this question
8
  • Not a clue what this is all about, but +1 nonetheless for what seems like an interesting question. Can we get some code and/or a fiddle, though? Throw a dog a bone. Commented May 28, 2012 at 21:31
  • @JaredFarrish: Thanks. I'll work on getting a fiddle up :) Commented May 28, 2012 at 21:33
  • @JaredFarrish: Added fiddle link, although the code is really messy right now. If you want to enter custom points, note that the x,y origin is in the bottom left. Commented May 28, 2012 at 21:58
  • Here ya go: jsfiddle.net/Pj2Ak/1 I put the JS in the Javascript-oriented area (as opposed to using body-style script tags). Keep in mind, you need someone to come by who knows what the heck this is all about. Commented May 28, 2012 at 22:05
  • This might be off-topic, but have you seen three.js? Commented May 28, 2012 at 22:11

2 Answers 2

Reset to default
4

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:

enter image description here

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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).

Improve this answer

1 Comment

Hey Torious, thanks for the help (+1)! I did some more work and I was eventually able to get this working for concave polygons (as you hinted at in your bottom edit) - I'll post an answer to that effect in a few mins.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.