This is a discussion on Finding the outside of arbitrary shape within the Game Programming forums, part of the General Programming Boards category; Originally Posted by BobMcGee123 Well the OP did define this to be for 'closed' shapes, which to me says convex ...
One way to handle arbitrary shapes is by triangularization (Delaunay) into convex shapes, or as you point out, by casting rays.
Last edited by Sang-drax; 08-21-2008 at 05:32 AM.
Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Yeah, especially re-reading and he says 'horizontal and vertical lines only' (which means that they often won't be convex, as the definition is that the inner angle between adjacent lines is less than 180).No, from his description I think it is clear that he meant arbitrary shapes.
as sang drax said you either need to use Bubba's method of simple ray casting from the outside of the object (to determine if the point is inside the geometry), or you need to subdivide each shape into convex regions. The former would probably be easier.
I wasn't familiar with Delauney triangulation, I did some reading up on it and while it'd work, I really think the op'd be better off using a raycasting technique or something similar (esp. considering the assumption of only horizontal and vertical lines).
Another method, considering the fact that you're using OpenGL, is to do an offline render using the gl occlusion query extension. Render the geometry in question, then (with occlusion query turned on) render a primitive (a square, circle or just a point) that represents the cursor position somewhere further down the z-axis. The occlusion query will tell you how many pixels of the depth-test passed (if none passed, then the cursor is inside the geometry). This may seem complicated, but it'd actually spare you of basically all of the math details. It isn't relatively computationally efficient, but it'd work and it's an interesting solution. However I don't know what you'd do if the end user's card doesn't support the occlusion query.
Anyway just an idea, the ray casting idea is still ultimately probably the best option.
Last edited by BobMcGee123; 08-21-2008 at 04:08 PM.
I'm not immature, I'm refined in the opposite direction.