# Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation - Graphics

This is a discussion on Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation - Graphics ; Hi All, I am looking for an efficient way of calculating if a point in 3d space is inside or outside a given closed mesh, and where abouts on the mesh it intersects (which face or nearest mesh vertex is ...

1. ## Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation

Hi All,

I am looking for an efficient way of calculating if a point in 3d space
is inside or outside a given closed mesh, and where abouts on the mesh
it intersects (which face or nearest mesh vertex is fine).

2. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location

Hi,
I would search for "Point location", "Point containment", also some
"point in polygon" algorithms can be easily generalized to 3D (e.g.,
winding number, ray-casting).

Jindra

> Hi All,
>
> I am looking for an efficient way of calculating if a point in 3d space
> is inside or outside a given closed mesh, and where abouts on the mesh
> it intersects (which face or nearest mesh vertex is fine).
>

3. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation

There's a whole literature on this. But if you're doing
collision detection, you're headed in the wrong direction.
There are better approaches, most of which have been
discussed here.

John Nagle
Animats

jindra wrote:
> Hi,
> I would search for "Point location", "Point containment", also some
> "point in polygon" algorithms can be easily generalized to 3D (e.g.,
> winding number, ray-casting).
>
> Jindra
>
>
>>Hi All,
>>
>>I am looking for an efficient way of calculating if a point in 3d space
>>is inside or outside a given closed mesh, and where abouts on the mesh
>>it intersects (which face or nearest mesh vertex is fine).
>>

>
>

4. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation

Its not for collision detection! The problem is exactly as described,

5. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location

Efficient or accurate?

Arash Partow
________________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

> Hi All,
>
> I am looking for an efficient way of calculating if a point in 3d space
> is inside or outside a given closed mesh, and where abouts on the mesh
> it intersects (which face or nearest mesh vertex is fine).
>

6. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location

Efficient or accurate?

Arash Partow
________________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

> Hi All,
>
> I am looking for an efficient way of calculating if a point in 3d space
> is inside or outside a given closed mesh, and where abouts on the mesh
> it intersects (which face or nearest mesh vertex is fine).
>

7. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation

Well I would hope both, but accuracy is more important than efficiency
in the end.

8. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location

> Well I would hope both, but accuracy is more important than efficiency
> in the end.

Construct a randomly directed ray from the point and count the number
of surfaces of the mesh it intersects:
http://cgafaq.info/wiki/Ray_Triangle_Intersection

If the ray intersects an even number of surfaces, it's outside the
mesh. If odd, it's inside.

Since floating-point precision may give you a false indication of
whether the ray intersects a triangle (i.e., the ray may squeeze
through a crack along the edge of the polyhedron or intersect two
slightly intersecting faces), run this test an odd number of times
using differently directed rays, and go with the majority result.
(Don't use axis-oriented rays since these are particularly prone to
degenerate-case problems in typical axis-oriented structure.)

If you need to detect if the point is on the surface of the mesh (or
relative to your floating-point precision, very near the surface of the
mesh), just compute the distance from each triangle of the mesh and if
the minimum of those distances is less than some epsilon, you declare
it coincident with that closest edge.

9. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location

> Construct a randomly directed ray from the point and count the number
> of surfaces of the mesh it intersects:
> http://cgafaq.info/wiki/Ray_Triangle_Intersection
>
> If the ray intersects an even number of surfaces, it's outside the
> mesh. If odd, it's inside.

Not necessarily, imagine two adjoined tetrahedra and a point
located inside one of them - ray tracing can go through the face of
containing tetrahedron or can intersect 2 faces of both figures. The
situation is the same with large number of mesh elements.

> Since floating-point precision may give you a false indication of
> whether the ray intersects a triangle (i.e., the ray may squeeze
> through a crack along the edge of the polyhedron or intersect two
> slightly intersecting faces), run this test an odd number of times
> using differently directed rays, and go with the majority result.
> (Don't use axis-oriented rays since these are particularly prone to
> degenerate-case problems in typical axis-oriented structure.)

How many rays would you recommend? It may happen, that pretty
large number of rays won't be enough to conclude whether point is
inside
or not. This technique will work pretty well with external points only.
The
major part of the problem to identify internal points.

> If you need to detect if the point is on the surface of the mesh (or
> relative to your floating-point precision, very near the surface of the
> mesh), just compute the distance from each triangle of the mesh and if
> the minimum of those distances is less than some epsilon, you declare
> it coincident with that closest edge.

10. ## Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location

P. Galibarov <pavel.galibarov@gmail.com> wrote:

> > If the ray intersects an even number of surfaces, it's outside the
> > mesh. If odd, it's inside.

> Not necessarily, imagine two adjoined tetrahedra and a point
> located inside one of them - ray tracing can go through the face of
> containing tetrahedron or can intersect 2 faces of both figures.

Only if you hit an edge or vertex of either tetrahedron, or
mis-applied the algorithm to the data structures you used. In the
general case, a ray going through the joint surface will go through an
odd number of faces. Either because shared surfaces are counted as
two intersections (their two sides are stored individually in a
representation of the scene as isolated polyhedra), or because the
test counts faces as zero or two faces (in a volumetric mesh including
information on shared faces just like a polygon mesh includes
information on shared edges).

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.