Hi folks, What I am ultimately trying to do is trying to pick a (convex) polygon in 3D, given a fixed size (in screen space) picking margin. Because of that last constraint, I am current doing: 1. Project Polygon to screen coordinates (using modelview and projection matrices) 2. Extend the now 2D polygon to all sides by [margin] pixels 3. Do a simple 2D point in polygon test with the mouse coordinates. I've got (1) and (3) basically covered, but (2) is giving me a bit of a problem. How do I extend a 2D polygon by (at least) X pixels to all sides? Simply scaling all vertices out from the centre doesn't work (obviously, but I had to try it out first to get the picture :D). I frankly don't know how to handle this. Perhaps I should, at each vertice, move X pixel in the 'outward normal' direction of one edge, and add an _extra_ vertice at X pixels in the normal direction of the other edge? This would mean effectively doing the point-in-polygon test v.s. the double amount of vertices, but I don't mind doing this as long as I feel assured that this approach makes at least a bit of sense. I apparently don't know now the correct terminology to search for, as google has thus far not resulted in any useful information. Any help is most appreciated!

Quote:Original post by Agony
I suppose if you wanted to keep the same number of vertices, to determine a vertex's new location, extend each of the two edges out the desired amount along each of their respective normals, and then calculate where the new pushed-out edges intersect.

O = Original VertexX = New Vertex           \             \ -------------X------  <- New Extended Edge 1  .           \  /|\           \   |             \ ---------O       \<- New Extended Edge 2Edge 1    \       \            \    __ \             \__--/  \              \       \        Edge 2 \       \                \       \ 

This might make the marge extend out rather far if the angle at a vertex is rather small, but I doubt that will often be much of an issue. Though technically, every extended point should be a circular arc, rather than a 1 or 2 vertex extension. But that's probably overkill in most situations.

nice ASCII art ;)
I´ve got a simpler proposal. It should work, too, however I´ve not completely thought it through:
It should suffice to add the normals of the two edges together, normalize the result and multiply that with the margin you want to have. Add that to your old vertex (O in Agony´s pic) and you should have the new vertex (X in Agony´s pic).
So all in all this should work:

Vector m = Margin * Normalize( Normal(Edge1) + Normal(Edge2) );X = O + m;

I think this should be easier / faster to compute than moving the edges themselves and calculating their intersection again.
The only case I can imagine right now where this should fail is if the normals of the two edges are opposite.... but in that case your polygon is reduced to a line anyway. Furthermore I can´t think of a reason why that (or Agony´s) method shouldn´t work with concave polygons.

Nice replies guys, very insightful, thanks!

You are very right pointing a true fixed-distance margin would yield a curve around each vertex. And indeed that is not necessary for my goal.

Agony: Thanks for the art, very clear! One drawback would indeed be the huge margin at small angles, but that's something all approximations seem to suffer from. The bad news is that small angles are not as infrequent as you would think, as we are talking 3D polygons that are projected onto a 2D screen here, so they often end up as long-and-thin with small angles. Then again, the good news is that a too-big margin is not too much of a problem, as I have some post-processing in place after the pick has been made (I am secretly picking vertices, I am abusing the polygon-picking to make the vertex picking account for occlusion).

Matches81: Nice idea, but does suffer from the same problem as my original approach if you only scale the vertices a unit size vector times the margin. Near vertices with small edges, the margin gets too small. I have attached a little sketch to make this a bit more clear, notice how close the yellow lines approaches the orignal polygon near the top of the triangle?



hplus0603: Isn't it nice to be communicating on the gamedev forums for a change? Thanks for the cos(beta/2) trigonometry! I am still doubting whether I should opt for the moving-towards-unlimited-margins-at-small-angles, leading to rare but potentially bizarre false positives, or add extra vertices, implicating slightly larger cost for calculating the point-in-polygon test. By using two vertices in stead of one, I can create a much nicer bounding volume for the implicit 'fixed margin curve'.



(The yellow margin is the fixed pixel margin I am trying to approach, the blue squares are the vertices I propose to add)

One could take the effort to quantify the error for a given polygon (total area introduced outside fixed margin), but like I said before: I have an heuristic in place to compensate for this errors resulting from a too large picking size afterwards anyway, so it isn't that important. I do however like the fact that this approach does compensate for the 'degenerate' case where the bend is 180 degrees, so no worries about numerical instability when things approach that limit.

Well, I think I will sleep another night on this, and decide in the morning. Thanks again guys for contributing, you have been a great help!