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

+ Reply to Thread
Page 1 of 2 1 2 LastLast
Results 1 to 10 of 12

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

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

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

    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



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

    >
    >


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

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

    Adam

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



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



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

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

+ Reply to Thread
Page 1 of 2 1 2 LastLast

Similar Threads

  1. Locating the triangle containg a point in a flat (2D) triangular Mesh
    By Application Development in forum Graphics
    Replies: 6
    Last Post: 04-04-2007, 08:04 PM
  2. Projecting a point to a triangular mesh surface
    By Application Development in forum Graphics
    Replies: 9
    Last Post: 03-06-2007, 04:27 AM
  3. Replies: 3
    Last Post: 09-18-2006, 02:55 AM
  4. Mesh or surface from CLOUD POINT?
    By Application Development in forum Graphics
    Replies: 2
    Last Post: 09-27-2005, 08:01 PM
  5. Mesh normal direction calculation
    By Application Development in forum Java-Games
    Replies: 3
    Last Post: 04-04-2005, 10:26 PM