Thread Subject: tsearchn for triangle mesh?

Hi

I'd like to check if a point is inside or outside a 3D triangle mesh using tsearchn. A triangle mesh is defined as a set of vertices that represents a 3D surface of an object as well as indices for triangles. tsearchn requires a n+1 dimensional array of delaunay tessellation, i.e., 4D array for this case. However, I only have a 3D array of triangular tessellation. I wonder how I can do tsearchn for this.

Actually I didn't do delaunayn for tessellation, but used that calculated using a separate program. delaunayn fails to compute accurate tessellation due to a complex geometry of an object containing lots of concave shapes.

I'd appreciate any suggestions.

Thanks,

Tony

"Hiro" <toki.yamamoto@gmail.com> wrote in message <gs29sf$sj8$1@fred.mathworks.com>...
> Hi
>
> I'd like to check if a point is inside or outside a 3D triangle mesh using tsearchn. A triangle mesh is defined as a set of vertices that represents a 3D surface of an object as well as indices for triangles. tsearchn requires a n+1 dimensional array of delaunay tessellation, i.e., 4D array for this case. However, I only have a 3D array of triangular tessellation. I wonder how I can do tsearchn for this.
>

You cannot. You have the equivalent of a manifold,
like a convex hull. tsearchn woks only on a volume
tessellation, and even then may not work on any
general tessellation not created by delaunayn.

> Actually I didn't do delaunayn for tessellation, but used that calculated using a separate program. delaunayn fails to compute accurate tessellation due to a complex geometry of an object containing lots of concave shapes.
>

tsearchn will not work for you.

John

Thanks for your reply. Is it possible to build a volume tessellation equivalent to that generated by delaunayn based on a set of vertices and indices for triangles? Delaunayn fails to build an accurate tessellation due to the complexity of an object shape, thus I need to use the triangle data.

Thanks,

Tony

"Hiro" <toki.yamamoto@gmail.com> wrote in message <gs2fk6$kev$1@fred.mathworks.com>...
> Thanks for your reply. Is it possible to build a volume tessellation equivalent to that generated by delaunayn based on a set of vertices and indices for triangles? Delaunayn fails to build an accurate tessellation due to the complexity of an object shape, thus I need to use the triangle data.
>

Starting from a triangulated, non-convex domain?

If this boundary surface is not TOOOOO complicated,
then you can just add a single point in the interior.
Connect each triangle on the boundary surface with
the central point.

This scheme will only fail if some of the triangles on
the boundary surface are hidden from the central point,
so it will still work nicely on many simple non-convex
domains. I once played with a scheme that did a search
over the interior to see if any such point existed, then
creating the volume tessellation. This was a success
more often, but not always, as you might expect on
a really nasty problem. There are other schemes that
might work better. You might look for meshnd on
Google.

Even then, this meshed domain will still probably not
work in tsearchn, as tsearchn requires convex delaunay
based tessellations. I've written code that handles
a fully general meshed volume complex, testing if
points are in or out. This is available if and when you
need it.

John

Hi John,

Thank you very much. Your reply is so helpful. Actually I've already tried using a point inside the object, but tsearchn did not work well as you mentioned because I'm dealing with a quite complicated non-convex domain.

Your code sounds great. I'd really appreciate if you could provide me with this code.

Thanks,

Tony

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gs2hq3$sku$1@fred.mathworks.com>...
> "Hiro" <toki.yamamoto@gmail.com> wrote in message <gs2fk6$kev$1@fred.mathworks.com>...
> > Thanks for your reply. Is it possible to build a volume tessellation equivalent to that generated by delaunayn based on a set of vertices and indices for triangles? Delaunayn fails to build an accurate tessellation due to the complexity of an object shape, thus I need to use the triangle data.
> >
>
> Starting from a triangulated, non-convex domain?
>
> If this boundary surface is not TOOOOO complicated,
> then you can just add a single point in the interior.
> Connect each triangle on the boundary surface with
> the central point.
>
> This scheme will only fail if some of the triangles on
> the boundary surface are hidden from the central point,
> so it will still work nicely on many simple non-convex
> domains. I once played with a scheme that did a search
> over the interior to see if any such point existed, then
> creating the volume tessellation. This was a success
> more often, but not always, as you might expect on
> a really nasty problem. There are other schemes that
> might work better. You might look for meshnd on
> Google.
>
> Even then, this meshed domain will still probably not
> work in tsearchn, as tsearchn requires convex delaunay
> based tessellations. I've written code that handles
> a fully general meshed volume complex, testing if
> points are in or out. This is available if and when you
> need it.
>
> John

I thing what you need is an InPoliedron Test:

http://www.mathworks.com/matlabcentral/fileexchange/24631

http://www.advancedmcode.org/