Finding the outside of arbitrary shape

Hello all,

I am working on a C++/OpenGL game where a user draws arbitrary, closed shapes using horizontal and vertical lines only. These closed shapes may be nested in each other, but do not overlap. For the purposes of the next step of the game, the users must place objects around the exterior border of the largest shape. Of course, this means that I must know where the outside is so I can designate that exterior area.

I have no problem finding the largest shape and of course know the coordinates of the lines that make it up, but I need help figuring out how to find the "outside" of the object for the entire perimeter.

I understand the theory behind using ray-tracing to find out if a point is inside or outside of an object, but this does not seem to be an efficient algorithm for my needs.

Does anyone have any suggestions?

Thanks,
Jack

So long as the shapes are closed you can basically create what amounts to inward-facing planes. A point is inside the shape if it is in front of each of these inward facing planes, and outside the shape if the point is behind at least one of the planes.

Why do you need to find the entire perimeter? I would have thought that you could just check when they try an place an object. For this a raytracing approach should not be too expensive. You could split them into two groups: horizontal and vertical. Then trace an x_ray scanning lines where the y_pos falls between the upper and lower limit. I would think that it should be fast enough, since none of the lines are at angles.

Alternatively if the area can be split into cells of a fixed size you could just make a boolean array for the grid and check of whether its inside or outside of your area. That would be faster.

Thanks for the quick reply, BobMcGee123.

I may be missing something, but how would you determine the position of those planes?

It seems like what you suggest would work well for regular shapes like rectangles, but the shapes in my program will be more complex than squares or rectangles. Think of starting out with a rectangle, then cutting other rectangles of varying dimensions from its edges. What is left of the original rectangle might be what the arbitrary shapes look like.

Thanks,
Jack

mike_g,

Your first suggestion would work perfectly, but unfortunately I do need to find the entire perimeter so I can graphically show where the user can place the objects.

I can break the area up into a grid. I was hoping to avoid a brute-force search cell by cell, but it seems like the only way right now.

JackR

I dont think you would need to use brute force. As the grid would map to a location on the screen. Then you only need to check each cell that falls under the item to place. Or even just each cell along the perimeter of the item to place.

Ah, good point mike_g.

My plan now is to just check grid square next to the lines. That will suit my purposes.

Thanks for the help, all.

Jack

The edges of the poly already create infinite planes. You just have to find the normal of these planes and based on the 'winding order' of your normal calculation you may have to invert the normal to have them face inward.

Once you get this far you just do the simple ax + by + cz +d = 0 and plug in your point for x,y,z and the normalized plane in a,b,c and d. This will tell you if the point in question is inside or outside of the polygon. Be sure to normalize your planes prior to performing the calculation.

Code:

---

...
...
int inside = 0;
for (int i = 0;i < numPlanesInPoly; ++i)
{
  if (inPositiveHalfSpace(planes[i],testPoint))
  {
      ++inside;
  }
}

if (inside == numPlanesInPoly)
{
  //point is inside polygon or contained by the polygon
}
else
{
  //point is outside of polygon
}
...
...

---

All that's left for you to do is figure out the code for inPositiveHalfSpace() as well as how to form planes from the edges of the polygon.

Quote:

---

It seems like what you suggest would work well for regular shapes like rectangles, but the shapes in my program will be more complex than squares or rectangles

---

I do it for arbitrary shapes in 3D, the only requisite is that the edge vertices lay on the same plane (the edge vertices lay on the same plane, this isn't to say that the inward facing normals are the same). To get the 'position' of the planes you take the dotproduct between the normal of the edge in question and one of the points on the edge. Note that for Bubba's equation you have to take the negative dot product, or reverse the direction of the normal, or reverse the direction of the algorithmic logic (the point must be *behind* all edges to be inside the face, etc etc, you get the idea).

To extend into 3D, you must first find where a ray intersects the face normal, then traverse the inward-facing edge normals and determine if the point is behind any of the inward facing normals. If this is the case, the ray isn't pointed at the geometry.

And also I believe Bubba's code addresses this issue:

Quote:

---

Originally Posted by Bubba

Code:

---

...
...
int inside = 0;
for (int i = 0;i < numPlanesInPoly; ++i)
{
  if (inPositiveHalfSpace(planes[i],testPoint))
  {
      ++inside;
  }
}

if (inside == numPlanesInPoly)
{
  //point is inside polygon or contained by the polygon
}
else
{
  //point is outside of polygon
}
...
...

---

---

Bubba, your code will fail for anything but convex shapes.

You could also break the for loop so that you don't perform unnecessary tests:

Code:

---

bool inside = true;
for (int i = 0;i < numPlanesInPoly; ++i)
{
  if ( ! inPositiveHalfSpace(planes[i],testPoint))
  {
      inside = false;
      break;
  }
}

if (inside)
{
  //point is inside polygon or contained by the polygon
}
else
{
  //point is outside of polygon
}
...
...

---

Quote:

---

Bubba, your code will fail for anything but convex shapes.

---

Well the OP did define this to be for 'closed' shapes, which to me says convex polygons.

This isn't the most elegant implementation, but it does work. What I do to alleviate the problem presented in the picture above is to only test for a point, rather than a sphere. I do this by moving the test point from the center of the circle inward radius units towards the center. Yes, I have to do a vector normalize to accomplish this, but in my testing using a sqrt approximation only gives results that are 5% different (and subsequently my tolerance values for the fast sqrt implementation of this are about 6% bigger than the floating point tolerances for the regular sqrt implementation).

Code:

---

BOOL        PointInBSPFace(BSP        *pBSP,int        faceindex,Vector3 & Pos,float        Radius)
{
        tBSPFace        & face_ref = pBSP->mpFaces[faceindex];

        Vector3        dir = face_ref.center - Pos;

        float        startd_sq = dir.BasicLength();

        float        rad_sq = Radius * Radius;

        if(startd_sq <= rad_sq)
                return        TRUE;        //intersects with the center

        dir.Normalize(Faster_Sqrtf(startd_sq));

        Vector3        testpoint = Pos + (dir * Radius);
       
        Plane3        *pPlane = NULL;
        float        d(0);
        for(int plane = 0; plane < face_ref.numInPlanes; plane++)
        {
                pPlane = &face_ref.mpInplanes[plane];
                       
                d = DotProduct(&pPlane->mNormal,&testpoint) - pPlane->mDist;

                if(d < -FastBSPFacetolerance)
                        return        FALSE;
        }
        return        TRUE;
}

---

@Bob: I'm assuming you are using a Taylor series approximation to get the square root?

@Sang-drax:

Quote:

---

Code:

---

for (int i = 0;i < numPlanesInPoly; ++i)
{
  if ( ! inPositiveHalfSpace(planes[i],testPoint))
  {
      inside = false;
      break;
  }
}

---

---

This early out will assume that if the point is not in the positive half space of any plane then the point is out. This is not always the case. My case tests all planes and ensures that the point is indeed not in the positive half space of any of them. This means then that when the number of planes that fail match the number of planes created by the poly then the point must be out. This early out would almost ensure it does not work with concave shapes. I'm a bit confused why you bring this up and then add code that definitely breaks it for concave shapes. I know for sure that this type of testing in frustum culling will absolutely NOT work yet it is prolific all over the internet. The correct test is to test against all planes and count in's and out's. It's slower but that's the price of accuracy. Even a 6 plane frustum test will fail with volumes that span the frustum. Each corner of the AABB will be out and the (radius + center) of a sphere will also fail...even though the center of the sphere is in.



My impl of the algo was designed to work for convex shapes. I believe that was inferred in the original post. However one could extend this basic algo to work with more convex shapes which may in turn make up a concave shape. However that is more a lesson in geometry and data structures than with the task at hand. However it should be noted that whether convex or concave we are still talking about the result of ax + by + cz + d which will not change with concave shapes. I'm not so sure it completely falls apart with concave shapes. As Bob points out as long as the point is not in the positive half space of any planes whether the shape is convex or concave the algo will work. However there are probably some concave shapes that would form planes in such a manner that the algo would fall apart.

The only sure way I know of finding if a point is inside of a complex concave shape is to first find a known point that is outside of the shape and call it the origin. Then cast a ray toward the point in question from the origin and count how many times it crosses a plane. If the result is odd then the point is inside the shape else it is outside the shape. For very complex shapes you would want to cull the number of planes you test down to those that actually could affect the result which could be done via a simple dot product.

Quote:

---

I'm assuming you are using a Taylor series approximation to get the square root?

---

Nopers, it's this one:

Code:

---


/*
        -From tricks of the 3d game programming gurus
        Uses regular registers to manipulate a float, basically just shifts the exponent to the right, but you
                need to do some jumping jacks in order to do that.
*/
float        Faster_Sqrtf(float f)
{
        float        result;
       
        _asm
        {
                mov eax, f
                sub eax, 0x3f800000
                sar eax, 1
                add eax, 0x3f800000
                mov result, eax
        }
       
        return result;
}

---

general note: it aint gonna work for doubles (it's manipulating a float outside of the fpu!)


I wrote this one which does the newton-raphson iteration you refer to, but it's ultimately useless because it won't ever beat sqrt(), it's just an interesting exercise, and there's no reason for me to post it really

Code:

---

float        IterSqrtf(float        r, int numtries)
{
        float        m(0.0f);
        float        b(0.0f);
        float        currx=r;
        float        curry(0.0f);
        float        root(0.0f);

        while(numtries--)
        {
                curry = (currx*currx) - r; //y1
                //Check to see if curry is < 0
                m = 2 * currx;
                b = (-m*currx)  + curry;
                root = -b / m;
                currx = root;
        }
        return root;
}

---

Quote:

---

Even a 6 plane frustum test will fail with volumes that span the frustum

---

To anyone that is confused what he means, see the picture above!

Quote:

---

The correct test is to test against all planes and count in's and out's

---

Or the method I've shown above *shameless plug*.

Quote:

---

The only sure way I know of finding if a point is inside of a complex concave shape is to first find a known point that is outside of the shape and call it the origin. Then cast a ray toward the point in question from the origin and count how many times it crosses a plane

---

This intrigues me, I haven't thought of that before. The map editor I use can create faces that aren't convex, e.g. if you create two separate blocks and have them meet to form an L shape the editor may do a CSG operation and the top/bottom face of the unified solid won't be convex. I never actually implemented a fix for it. My initial thinking was to just break the face down into convex sections, but I never implemented it (I are lazy).

Quote:

---

Originally Posted by BobMcGee123

Well the OP did define this to be for 'closed' shapes, which to me says convex polygons.

---

No, from his description I think it is clear that he meant arbitrary shapes.

Quote:

---

Originally Posted by Bubba

I'm a bit confused why you bring this up and then add code that definitely breaks it for concave shapes.

---

Yeah sorry, the code I posed was certainly not intended to work with non-convex shapes either. But am fairly certain that was intended by the OP. It is equivalent to your code.

One way to handle arbitrary shapes is by triangularization (Delaunay) into convex shapes, or as you point out, by casting rays.

Quote:

---

No, from his description I think it is clear that he meant arbitrary shapes.

---

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

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.