Re: determine if point is in a volume

In article <ef37bec.0@xxxxxxxxxxxxxxxx>, helper <spam@xxxxxxxxxx> wrote:

pinpress wrote:


Hello,

Can any one give some hint how to efficiently determine if a 3D
point
is inside a 3D volume specified by a surface triangular mesh? In
2D,
I can simply use "inpolygon". If we know for sure and in advnace
that the 3D volume is a convex, maybe I can use tsearch and
calculate
where the point is relative to its closest triangle. Or, just ust
inpolygon 3 times for each of the 3 projections onto xy,yz and zx
planes. However, how do I solve this problem more generally?
Thanks
a lot!

Use GRIDDATAN. If the value is NaN, it is not in the volume. If it
is non-NaN, it is.

Use of griddatan is very inefficient here. It
computes a delaunay triangulation, then calls
tsearchn, then interpolates.

You could improve this slightly by dropping
the interpolation step. Call delaunayn yourself,
then call tsearchn, which will identify points
as inside the tessellation directly.

Far better is to use inhull, which does not do
a delaunay tessellation. Instead it uses a
convex hull. If you already have the triangular
mesh, AND it is a convex mesh, then inhull will
be immensely faster. Even if you use a convex
hull first and do not have the mesh, inhull will
still be much faster, as this example shows:

n = 500;
m = 100;
p = 5;
xyz = rand(m,p);
testpts = rand(n,p)-.1;

tic
tess = delaunayn(xyz);
in0 = ~isnan(tsearchn(xyz,tess,testpts));
toc
tic
in1 = inhull(testpts,xyz);
toc

tsearchn: Elapsed time is 641.046321 seconds.
inhull: Elapsed time is 1.826386 seconds.


http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=10226&objectType=FILE

In any case, with griddatan, tsearchn, or inhull,
the volume MUST be convex. ABSOLUTELY.

If the volume contained in the mesh is not convex,
then you have a problem. An alpha shape can help
solve it, but there is no 3d alpha shape (that I
know of) implementation in matlab that is freely
available.

HTH,
John D'Errico


--
The best material model of a cat is another, or preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.
Anonymous
.

Relevant Pages

  • Meshing of a curved Nurb surface
    ... I would like to find a simple and robust algorithm for meshing a four ... sided mesh surface. ... The mesh could be triangular but ideally quad with ... Doing it in the nurb internal coordinates ...
    (comp.graphics.algorithms)
  • Re: Projecting a point to a triangular mesh surface
    ... You are absolutely correct, there are many different ways of interpreting ... Let M be a triangular surface mesh and Ti a triangle within the mesh that ... efficient algorithm for projecting a point to the nearest position on a ... triangular mesh surface. ...
    (comp.graphics.algorithms)
  • Re: Meshing of a curved Nurb surface
    ... > I would like to find a simple and robust algorithm for meshing a four ... > sided mesh surface. ... The mesh could be triangular but ideally quad with ... Doing it in the nurb internal coordinates ...
    (comp.graphics.algorithms)
  • Re: Finding closest Triangle to a point
    ... Either the mesh is that of the surface of a convex ... But lets say it is quite sure (The Mesh is one part of a more complex model and every single Mesh gives one surface without "hard" edges, so until deformation one can be quite sure this should work). ... It looks like it fails when there is a long and thin triangle "on the way", so it could just be a matter of precision. ...
    (comp.graphics.algorithms)
  • Re: Finding closest Triangle to a point
    ... i am working on a Triangle Mesh, ... To deform this geometry i have to find the closest triangle to a given ... (The Mesh can be called convex, so i thought this should work so far) ...
    (comp.graphics.algorithms)
Loading