Jump to content

  • Log In with Google      Sign In   
  • Create Account


Determining if a 3D point is in a 3D polygon


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 AnEverydayGuy   Members   -  Reputation: 172

Like
0Likes
Like

Posted 04 June 2014 - 03:26 PM

Hey guys, I need help in determining if a point is in a polygon (in 3D).

 

I found this: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html, which works great in 2D. But now I'm expanding into 3D and this method no longer works. When I Google, all i find is how to do this in 2D (such as winding numbers, or edge counting) but nothing for 3D.

 

Ideally, I would like an explanation of the solution with pesudo code solving the problem. This way I can understand what is going on and can confirm that I know what is going on by programing it and having it work.



Sponsor:

#2 clb   Members   -  Reputation: 1780

Like
0Likes
Like

Posted 04 June 2014 - 05:28 PM

MathGeoLib has such a function, here:

 

http://clb.demon.fi/MathGeoLib/nightly/docs/Polygon_Contains.php

https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Polygon.cpp#L361

 

The idea is to first do a 3D point-plane test, and then reduce the test back to a 2D case. Hope that helps!


Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

#3 Álvaro   Crossbones+   -  Reputation: 12473

Like
1Likes
Like

Posted 04 June 2014 - 06:15 PM

Testing if a point is on a plane requires testing floating-point numbers for equality, which might not behave very well in most situations. What exactly are you trying to do? Perhaps you want to test if a point is in a polyhedron?

#4 AnEverydayGuy   Members   -  Reputation: 172

Like
0Likes
Like

Posted 05 June 2014 - 09:54 AM

Yes, sorry I ment a polyhedron.

 

I'm learning navigation meshes so I'm making a mapping system to assist in the learning process. I'm starting small and adding/changing functionaliy as I get more and more indepth with navigation meshes. At this stage and had I very basic 2D implementation and am now expanding it into 3D. I have a fixed starting point (that will become moveable further down the line) and I'm trying to get the shortest path to 'area A'. When the pathfinding system intializes, it goes through all of the (at this point, fixed) destinations and tries to determine which nav mesh points are inside it; those points are stored as goal points so that when pathfinding is executed the system says 'okay, I'm starting at point #37 and I'm looking for the shortest route to either point #98, 99 or 100'.

 

I found http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html to determine if a 2D point is in a 2D space (polygon), and now I'm trying to figure out how to determine if a 3D point is in a 3D space (polyhedron).

 

 

 

*** Edit ***

Of course, now that I'm using the, you know, correct term, I'm hitting some hits on Google. Funny how that works. I'll Google around but I'd still appreciate any help. I'm thinking I good / easy way to go about it is to extend PNPoly into 3D, but unfortantly I don't understand the Math. Conceptually I understand it's firing a ray to the right and counting the number of edge's it crosses, but the Math is flying over my head.


Edited by AnEverydayGuy, 05 June 2014 - 10:12 AM.


#5 Álvaro   Crossbones+   -  Reputation: 12473

Like
0Likes
Like

Posted 05 June 2014 - 11:18 AM

I found http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html to determine if a 2D point is in a 2D space (polygon), and now I'm trying to figure out how to determine if a 3D point is in a 3D space (polyhedron).


There is a section at the bottom of that page that discusses what you can do in the 3D case.

#6 AnEverydayGuy   Members   -  Reputation: 172

Like
0Likes
Like

Posted 05 June 2014 - 12:49 PM

I saw that but I don't understand what he's talking about.

 

<quote>

Run a semi-infinite ray up from the point, P

</quote>

 

I'm assuming 'up' is any direction you want.

 

<quote>

P lies below the plane of F

</quote>

 

I'm assuming a point is below a plane if the triple product is negative?

 

 

 

As I said before I don't understand the math being used in the 2D section, and I don't really understand want he means in the 'Testing Point Inclusion in a Polyhedron' section. As well he says 'If the ray intersects a vertex or an edge, then you're in trouble. Consider perturbing P slightly. Simulation of Simplicity provides a better, more complicated, solution'. So because of these things, I was hoping to find another answer that would be easier to understand and not be that complicated to code.


Edited by AnEverydayGuy, 05 June 2014 - 12:59 PM.


#7 clb   Members   -  Reputation: 1780

Like
1Likes
Like

Posted 05 June 2014 - 01:01 PM

One needs to be very careful with the definitions. Usually a polyhedron is a closed volume of space defined by polygonal faces, which subdivides a space into two disjoint regions ("inside" and "outside"). Navigation meshes aren't usually like this - they don't form a closed volume, but instead they are just a connected set of planar polygon faces in a 3D space.

 

For keeping a point-polygon containment test numerically robust, one usual solution is to compute the closest point on such a polygon list to the target point, and the compare the distance of the closest point to the target point, and use that a threshold value. Another way is to imagine the polygons have a "thickness" and they get extruded in both positive and negative direction by this thickness amount by the purposes of the test. This is what MathGeoLib does in the link I posted above.


Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

#8 AnEverydayGuy   Members   -  Reputation: 172

Like
0Likes
Like

Posted 05 June 2014 - 02:29 PM

I've looked at the links you've provide clb but they don't work for me. They are (from what I can see) calculating whether or not a point is contained within a polygon. This is not what I'm looking for. I used the wrong word because I was jumping back and forth between 2D and 3D and got confused. I'm looking for how to determine whether or not a point is in a polyhedron.

 

I have a destination 'box' in 3D and I'm trying to determine which (if any) 3D navigation mesh points are inside of it. I say my navigation meshes are in 3D is because a nav mesh at point 1,2,0 is NOT the same as a nav mesh at point 1,2,1 because the z component is different (the points are on different floors). This means the starting point can be on floor 1 and my destination area could span floors 1 and 2 with the only entrance on floor 2. So the system must figure that it needs to path to a ladder/staircase/elevator/whatever to get to level 2 so it can reach the area's goal point.

 

I apologize for the confusion. I never said my mapping implementation spanned multiple levels and I can see how that has caused some confusion.



#9 clb   Members   -  Reputation: 1780

Like
0Likes
Like

Posted 05 June 2014 - 06:11 PM

I have a destination 'box' in 3D and I'm trying to determine which (if any) 3D navigation mesh points are inside of it.

 

This sounds like completely something different than a point-in-polygon or a point-in-polyhedron test. If by "3D navigation mesh points" you mean the corner vertices of the navigation mesh, then what I'd do is populate a spatial subdivision acceleration structure (quadtree, octree, bsptree, kdtree, regular grid, etc. there's plenty to choose from) with the vertices and then do a box query into the structure ("find all the vertices inside this box").

 

If instead by "3D navigation mesh points" you meant the set intersection of the space taken up by the 3D navigation mesh and a given box, then I'd populate a spatial subdivision acceleration structure with the face polygons of the navigation mesh, and do a box clip operation into the structure ("find all polygons inside or intersecting the box, and clip each intersecting one to fit inside the contents of the box").

 

 

Perhaps one of those methods could help. If the navigation mesh has relatively few faces, then instead of using a spatial subdivision acceleration structure, you can try just using a flat list of faces as the structure, and linearly iterate over them while processing. "Upgrading" to a spatial subdivision structure can then be done optionally when necessary, it's more just an optimization for large data sets.


Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

#10 AnEverydayGuy   Members   -  Reputation: 172

Like
0Likes
Like

Posted 06 June 2014 - 09:24 AM

I'll explain what I'm doing (the fun part of learning something new is you think you're explaing things / using the right lingo but you're not). Keep in mind this is a rough and simple implementation for learning purposes, but by all means critique it and offer suggestions.

 

I have several 2D SVG maps. On each map I use 1 layer for destinations (areas) and on another layer I have my nav meshes. I import the map into my program and on system startup, the pathfinding system provides a bunch of operations so pathfinding can occur faster when it's needed.

 

  • It goes through each point (vertex) and determines its neighbours. It does this by comparing each nav mesh edge to all the others and determines if they are parallel, colinear, coplanar or disjoint for O(n2) complexity. Each point is then stored in an array (so I can reference them via index) and each point's neighbour is stored in a hash with the point ID (index) as the key and it's neighbours as the value.
  • Then it iterates through each destination and determines which points are inside it. This is stored in another hash with the destination as the key and the point IDs inside it as the value. This is done by checking each nav mesh point (vertex) is within it's area.
  • The starting point's neighbours are determined by checking which nav mesh it's inside of and making each nav mesh vertice a neighbour of the starting point.

 

I'm stuck on the determining whether or not a nav mesh vertex is inside a destination area. In my first implementation, PNPOLY worked great as I had one map, with this iteration I am adding several 2D floors so the problem is now, I have a 3D point and I am trying to determine if it's side the 2D destination (polygon). However, my next step is to extrude the floors to make them 3D and the problem becomes if a 3D point is inside a 3D area (polyhedron) and I figured to just skip the 'multiple 2D floors' step and go straight 3D.



#11 Erik Rufelt   Crossbones+   -  Reputation: 3181

Like
0Likes
Like

Posted 06 June 2014 - 11:01 AM

I you're destinations are convex then just check the point-plane distance of each polygon in the destination, and if the point is on the same side of all polygons then it's inside.

 

If they're concave, then the easiest is probably to divide them into convex subsections, for example with a BSP tree.



#12 WiredCat   Members   -  Reputation: 215

Like
0Likes
Like

Posted 06 June 2014 - 03:49 PM



bool 		__fastcall IntersectedPolygon(LIGHT_TRAIL vPoly, t3dpoint vLine[2],int verticeCount)
{

Extended  MATCH_FACTOR = 0.9999999999;
 t3dpoint vNormal;
t3dpoint  vIntersection;
Extended  originDistance;
Extended  distance1;
Extended  distance2;
t3dpoint  vVector1;
t3dpoint  vVector2;
double  m_magnitude;
t3dpoint  vPoint;
t3dpoint  vLineDir;
Extended  Numerator;
Extended    Denominator;
Extended    dist;
Extended    Angle,tempangle;
t3dpoint	vA, vB;
int  i;
Extended    dotProduct;
Extended    vectorsMagnitude;

	vNormal.x = 0.0;
  vNormal.y = 0.0;
  vNormal.z = 0.0;

	originDistance = 0.0;
  distance1 = 0.0;
  distance2 = 0.0;
  vPoint.x = 0.0f;
  vPoint.y = 0.0f;
  vPoint.z = 0.0f;

  vLineDir.x = 0.0f;
  vLineDir.y = 0.0f;
  vLineDir.z = 0.0f;

	Numerator = 0.0;
  Denominator = 0.0;
  dist = 0.0;
  Angle = 0.0;




  vVector1.x = vPoly[2].x - vPoly[0].x;
	vVector1.y = vPoly[2].y - vPoly[0].y;
	vVector1.z = vPoly[2].z - vPoly[0].z;

  vVector2.x = vPoly[1].x - vPoly[0].x;
	vVector2.y = vPoly[1].y - vPoly[0].y;
	vVector2.z = vPoly[1].z - vPoly[0].z;




	vNormal.x = ((vVector1.y * vVector2.z) - (vVector1.z * vVector2.y));

	vNormal.y = ((vVector1.z * vVector2.x) - (vVector1.x * vVector2.z));

	vNormal.z = ((vVector1.x * vVector2.y) - (vVector1.y * vVector2.x));




  m_magnitude = sqrt((vNormal.x * vNormal.x) +
					  (vNormal.y * vNormal.y) +
					  (vNormal.z * vNormal.z) );



	vNormal.x = vNormal.x/m_magnitude;
	vNormal.y = vNormal.y/m_magnitude;
	vNormal.z = vNormal.z/m_magnitude;
	  if ( (IsNan(vNormal.x)== true) || (IsNan(vNormal.y)== true) || (IsNan(vNormal.z)== true) )
	  {
	  return false;
	  }
  originDistance = -1.0f * ((vNormal.x * vPoly[0].x) +
						  (vNormal.y * vPoly[0].y) +
						  (vNormal.z * vPoly[0].z));


	distance1 = ((vNormal.x * vLine[0].x)  +
				 (vNormal.y * vLine[0].y)  +
				 (vNormal.z * vLine[0].z)) + originDistance;

	distance2 = ((vNormal.x * vLine[1].x)  +
				 (vNormal.y * vLine[1].y)  +
				 (vNormal.z * vLine[1].z)) + originDistance;

	if(distance1 * distance2 >= 0.0f)
										return false;



  vLineDir.x = vLine[1].x - vLine[0].x;
	vLineDir.y = vLine[1].y - vLine[0].y;
	vLineDir.z = vLine[1].z - vLine[0].z;

  m_magnitude = sqrt((vLineDir.x * vLineDir.x) +
					  (vLineDir.y * vLineDir.y) +
					  (vLineDir.z * vLineDir.z) );


	vLineDir.x = vLineDir.x/m_magnitude;
	vLineDir.y = vLineDir.y/m_magnitude;
	vLineDir.z = vLineDir.z/m_magnitude;



	Numerator = -1.0f * (vNormal.x * vLine[0].x +
						   vNormal.y * vLine[0].y +
							 vNormal.z * vLine[0].z + originDistance);




	Denominator = ( (vNormal.x * vLineDir.x) + (vNormal.y * vLineDir.y) + (vNormal.z * vLineDir.z) );

	if( Denominator == 0.0f)    {
	vIntersection = vLine[0];
	temp_intersect_v = vIntersection;
	} else	{


	dist = Numerator / Denominator;



	vPoint.x = (vLine[0].x + (vLineDir.x * dist));
	vPoint.y = (vLine[0].y + (vLineDir.y * dist));
	vPoint.z = (vLine[0].z + (vLineDir.z * dist));

  temp_intersect_v = vPoint;								// Return the intersection point
}

//temp_intersect_v.x := vIntersection.x;
//temp_intersect_v.y := vIntersection.y;
//temp_intersect_v.z := vIntersection.z;
//temp_intersect_v2 :=  vPoint;
//CLIP_INTERSECT_POS := temp_intersect_v;

for (i = 0; i < verticeCount; i++) {


	vA.x = vPoly[i].x - temp_intersect_v.x;

	  vA.y = vPoly[i].y - temp_intersect_v.y;

	  vA.z = vPoly[i].z - temp_intersect_v.z;


	vB.x = vPoly[(i + 1) % verticeCount].x - temp_intersect_v.x;

	  vB.y = vPoly[(i + 1) % verticeCount].y - temp_intersect_v.y;

	  vB.z = vPoly[(i + 1) % verticeCount].z - temp_intersect_v.z;


	dotProduct = ( (vA.x * vB.x) +
					(vA.y * vB.y) +
					(vA.z * vB.z) );


	  vectorsMagnitude = sqrt(
					 (vA.x * vA.x) +
					 (vA.y * vA.y) +
					 (vA.z * vA.z)
						  )
						  *
					 sqrt(
					 (vB.x * vB.x) +
					 (vB.y * vB.y) +
					 (vB.z * vB.z)
						  );

	 tempangle = ArcCos( dotProduct / vectorsMagnitude );


	  if(IsNan(tempangle) == true)		tempangle = 1990.0f;



	  Angle = Angle + tempangle;
}



	if(Angle >= (MATCH_FACTOR * (2.0f * 3.140f)) )   return true;





return false;
}


#13 AnEverydayGuy   Members   -  Reputation: 172

Like
0Likes
Like

Posted 10 June 2014 - 11:03 AM

Thanks WiredCat, I'll give your code a try but I don't understand what it's doing.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS