Thread: Finding the outside of arbitrary shape

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    27

    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

  2. #2

    Join Date
    May 2005
    Posts
    1,042
    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.
    I'm not immature, I'm refined in the opposite direction.

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    27
    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

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    27
    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

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    27
    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

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.
    Last edited by VirtualAce; 08-18-2008 at 02:31 PM.

  9. #9

    Join Date
    May 2005
    Posts
    1,042
    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.
    Last edited by BobMcGee123; 08-20-2008 at 12:21 PM.
    I'm not immature, I'm refined in the opposite direction.

  10. #10

    Join Date
    May 2005
    Posts
    1,042
    And also I believe Bubba's code addresses this issue:
    I'm not immature, I'm refined in the opposite direction.

  11. #11
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by Bubba View Post
    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
    }
    ...
    ...
    Last edited by Sang-drax; 08-20-2008 at 01:02 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  12. #12

    Join Date
    May 2005
    Posts
    1,042
    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.
    I'm not immature, I'm refined in the opposite direction.

  13. #13

    Join Date
    May 2005
    Posts
    1,042
    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;
    }
    I'm not immature, I'm refined in the opposite direction.

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    @Bob: I'm assuming you are using a Taylor series approximation to get the square root?

    @Sang-drax:
    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.
    Last edited by VirtualAce; 08-20-2008 at 05:42 PM.

  15. #15

    Join Date
    May 2005
    Posts
    1,042
    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;
    }


    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!

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

    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).
    Last edited by BobMcGee123; 08-20-2008 at 06:29 PM.
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Filling a shape
    By SlayerBlade in forum C Programming
    Replies: 5
    Last Post: 10-07-2005, 08:26 PM
  2. Newbie- having trouble with functions
    By bnmwad in forum C Programming
    Replies: 7
    Last Post: 02-22-2005, 04:41 PM
  3. Area of irregular shape
    By Brian in forum Game Programming
    Replies: 4
    Last Post: 06-23-2004, 10:54 AM
  4. CDC shape Helps
    By cfrost in forum C++ Programming
    Replies: 3
    Last Post: 05-13-2004, 05:49 AM
  5. MFC :: Finding Child Window of a CWnd* Object?
    By SyntaxBubble in forum Windows Programming
    Replies: 2
    Last Post: 09-06-2003, 09:06 AM