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.

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!

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.

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

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.

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.

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.

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.

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.