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

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

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, raycasting).
Jindra
Adam Teasdale Hartshorne wrote:
> 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).
>
> Adam

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, raycasting).
>
> Jindra
>
> Adam Teasdale Hartshorne wrote:
>
>>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).
>>
>>Adam
>
>

Re: Efficient Calculation of a Point Inside/Outside of A Mesh & IntersectionLocation
Its not for collision detection! The problem is exactly as described,
Adam

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
Adam Teasdale Hartshorne wrote:
> 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).
>
> Adam

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
Adam Teasdale Hartshorne wrote:
> 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).
>
> Adam

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

Re: Efficient Calculation of a Point Inside/Outside of A Mesh & Intersection Location
Adam Teasdale Hartshorne wrote:
> 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 floatingpoint 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 axisoriented rays since these are particularly prone to
degeneratecase problems in typical axisoriented structure.)
If you need to detect if the point is on the surface of the mesh (or
relative to your floatingpoint 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.

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 floatingpoint 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 axisoriented rays since these are particularly prone to
> degeneratecase problems in typical axisoriented 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 floatingpoint 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.

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

HansBernhard Broeker (broeker@physik.rwthaachen.de)
Even if all the snow were burnt, ashes would remain.
Similar Threads

By Application Development in forum Graphics
Replies: 6
Last Post: 04042007, 08:04 PM

By Application Development in forum Graphics
Replies: 9
Last Post: 03062007, 04:27 AM

By Application Development in forum Graphics
Replies: 3
Last Post: 09182006, 02:55 AM

By Application Development in forum Graphics
Replies: 2
Last Post: 09272005, 08:01 PM

By Application Development in forum JavaGames
Replies: 3
Last Post: 04042005, 10:26 PM