Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Creating a logical mask from a 3D convex hull

Subject: Creating a logical mask from a 3D convex hull

From: Jonas

Date: 5 Aug, 2009 00:44:25

Message: 1 of 15

I have a list of coordinates (~50) that lie on a closed surface. I would like to have a list of all the pixels that are inside this surface.
I can create a reasonable approximation to the surface using convhulln.m, but there does not seem to be a 3D version of poly2mask. Is there a function I have been overlooking?

Subject: Creating a logical mask from a 3D convex hull

From: W. Dale Hall

Date: 6 Aug, 2009 01:29:07

Message: 2 of 15

Jonas wrote:
> I have a list of coordinates (~50) that lie on a closed surface. I
> would like to have a list of all the pixels that are inside this
> surface. I can create a reasonable approximation to the surface using
> convhulln.m, but there does not seem to be a 3D version of poly2mask.
> Is there a function I have been overlooking?

If you can form a list of the supporting hyperplanes (that is, the
planar surfaces that form the boundary of the convex hull), then
you can. Suppose each of these planes is of the form

V'x = k

where x denotes a point in R^3, V the normal vector pointing
towards the half-space containing your data, and k the common value
of V'x along the plane.

Let W = [V_1 V_2 ... V_n] be the concatenation of all the V's
describing the supporting hyperplanes, and K = [k_1; k_2; ... k_n]
a vector containing all the k's. Then your masking function is

all(W'x >= K)

or

all(W'x - K >= 0)

for a single point x, and for a list X = [x_1 ... x_N] of points,
it's

all( bsxfun(@minus, W'X ,K) >= 0)

You'll get an array of size 1 x N containing ones for the points
within the volume, and zeros for those points not in it.

Replace >= by > for the points strictly in the interior.

BTW, I'm not sure how to get that list of hyperplanes from the
output of convhulln.m, so I'll go check on that.

Dale

Subject: Creating a logical mask from a 3D convex hull

From: Jonas

Date: 6 Aug, 2009 16:24:02

Message: 3 of 15

Thank you very much! This is great help.

I think I should be able to get the equations for the surface by taking the cross product of two of the edges of each face. However, I am not quite sure how I could be sure to only get normals that point inward. Flipping signs till the divergence is at a maximum?

Subject: Creating a logical mask from a 3D convex hull

From: Matt

Date: 6 Aug, 2009 17:29:06

Message: 4 of 15

"Jonas" <remove_this_iop@gmx.at> wrote in message <h5f032$8d4$1@fred.mathworks.com>...
> Thank you very much! This is great help.
>
> I think I should be able to get the equations for the surface by taking the cross product of two of the edges of each face. However, I am not quite sure how I could be sure to only get normals that point inward. Flipping signs till the divergence is at a maximum?

On the file exchange, there is a function called vert2con.m that will essentially figure this out for you.

Subject: Creating a logical mask from a 3D convex hull

From: Bruno Luong

Date: 6 Aug, 2009 20:43:03

Message: 5 of 15

"Jonas" <remove_this_iop@gmx.at> wrote in message <h5f032$8d4$1@fred.mathworks.com>...
> Thank you very much! This is great help.
>
> I think I should be able to get the equations for the surface by taking the cross product of two of the edges of each face. However, I am not quite sure how I could be sure to only get normals that point inward. Flipping signs till the divergence is at a maximum?

The normal must point in the direction opposite to the all other vertices of the hull (from the faces). Take P any vertice that belongs to the face, n exterior normal must satisfies:

<PQ,n> <= 0 for all Q in the hull.

This help you to fix the sign

Bruno

Subject: Creating a logical mask from a 3D convex hull

From: Jonas

Date: 9 Aug, 2009 00:39:02

Message: 6 of 15

"Matt " <xys@whatever.com> wrote in message <h5f3t2$jgl$1@fred.mathworks.com>...
> "Jonas" <remove_this_iop@gmx.at> wrote in message <h5f032$8d4$1@fred.mathworks.com>...
> > Thank you very much! This is great help.
> >
> > I think I should be able to get the equations for the surface by taking the cross product of two of the edges of each face. However, I am not quite sure how I could be sure to only get normals that point inward. Flipping signs till the divergence is at a maximum?
>
> On the file exchange, there is a function called vert2con.m that will essentially figure this out for you.

Thank you very much for the tip! It allowed me to create code to create a mask from a surface.

Subject: Creating a logical mask from a 3D convex hull

From: Troy

Date: 7 Jul, 2010 20:01:10

Message: 7 of 15

"W. Dale Hall" <wdunderscorehallatpacbelldotnet@last> wrote in message <VuWdnWUuevd6rOfXnZ2dnUVZ_gydnZ2d@giganews.com>...
> Jonas wrote:
> > I have a list of coordinates (~50) that lie on a closed surface. I
> > would like to have a list of all the pixels that are inside this
> > surface. I can create a reasonable approximation to the surface using
> > convhulln.m, but there does not seem to be a 3D version of poly2mask.
> > Is there a function I have been overlooking?
>
> If you can form a list of the supporting hyperplanes (that is, the
> planar surfaces that form the boundary of the convex hull), then
> you can. Suppose each of these planes is of the form
>
> V'x = k
>
> where x denotes a point in R^3, V the normal vector pointing
> towards the half-space containing your data, and k the common value
> of V'x along the plane.
>
> Let W = [V_1 V_2 ... V_n] be the concatenation of all the V's
> describing the supporting hyperplanes, and K = [k_1; k_2; ... k_n]
> a vector containing all the k's. Then your masking function is
>
> all(W'x >= K)
>
> or
>
> all(W'x - K >= 0)
>
> for a single point x, and for a list X = [x_1 ... x_N] of points,
> it's
>
> all( bsxfun(@minus, W'X ,K) >= 0)
>
> You'll get an array of size 1 x N containing ones for the points
> within the volume, and zeros for those points not in it.
>
> Replace >= by > for the points strictly in the interior.
>
> BTW, I'm not sure how to get that list of hyperplanes from the
> output of convhulln.m, so I'll go check on that.
>
> Dale

I am attempting to create a logical mask as well, but I do not fully understand the process you outlined above. I have the following matrices at my disposal: the hull faces (connectivity matrix), the co-ordinates of the hull vertices, the co-ordinates of the centroid of each triangle, and the normal vectors (located at the centroid of each triangle).

My main problem is that I do not understand the apostrophe notation that you used above (examples: V'x and W'x). Can you please explain what this notation means? MATLAB does not recognize it. Lastly, 'V' is an N-by-3 matrix for N normal vectors and 'x' is an M-by-3 sized matrix for M points of interest, correct?

Thank you for your help!

Subject: Creating a logical mask from a 3D convex hull

From: Troy

Date: 7 Jul, 2010 20:01:10

Message: 8 of 15

"W. Dale Hall" <wdunderscorehallatpacbelldotnet@last> wrote in message <VuWdnWUuevd6rOfXnZ2dnUVZ_gydnZ2d@giganews.com>...
> Jonas wrote:
> > I have a list of coordinates (~50) that lie on a closed surface. I
> > would like to have a list of all the pixels that are inside this
> > surface. I can create a reasonable approximation to the surface using
> > convhulln.m, but there does not seem to be a 3D version of poly2mask.
> > Is there a function I have been overlooking?
>
> If you can form a list of the supporting hyperplanes (that is, the
> planar surfaces that form the boundary of the convex hull), then
> you can. Suppose each of these planes is of the form
>
> V'x = k
>
> where x denotes a point in R^3, V the normal vector pointing
> towards the half-space containing your data, and k the common value
> of V'x along the plane.
>
> Let W = [V_1 V_2 ... V_n] be the concatenation of all the V's
> describing the supporting hyperplanes, and K = [k_1; k_2; ... k_n]
> a vector containing all the k's. Then your masking function is
>
> all(W'x >= K)
>
> or
>
> all(W'x - K >= 0)
>
> for a single point x, and for a list X = [x_1 ... x_N] of points,
> it's
>
> all( bsxfun(@minus, W'X ,K) >= 0)
>
> You'll get an array of size 1 x N containing ones for the points
> within the volume, and zeros for those points not in it.
>
> Replace >= by > for the points strictly in the interior.
>
> BTW, I'm not sure how to get that list of hyperplanes from the
> output of convhulln.m, so I'll go check on that.
>
> Dale

I am attempting to create a logical mask as well, but I do not fully understand the process you outlined above. I have the following matrices at my disposal: the hull faces (connectivity matrix), the co-ordinates of the hull vertices, the co-ordinates of the centroid of each triangle, and the normal vectors (located at the centroid of each triangle).

My main problem is that I do not understand the apostrophe notation that you used above (examples: V'x and W'x). Can you please explain what this notation means? MATLAB does not recognize it. Lastly, 'V' is an N-by-3 matrix for N normal vectors and 'x' is an M-by-3 sized matrix for M points of interest, correct?

Thank you for your help!

Subject: Creating a logical mask from a 3D convex hull

From: Matt J

Date: 7 Jul, 2010 20:15:23

Message: 9 of 15

"Troy " <meal0016@umn.edu> wrote in message <i12me6$q02$1@fred.mathworks.com>...

> I am attempting to create a logical mask as well, but I do not fully understand the process you outlined above. I have the following matrices at my disposal: the hull faces (connectivity matrix), the co-ordinates of the hull vertices, the co-ordinates of the centroid of each triangle, and the normal vectors (located at the centroid of each triangle).
============

All you need are the hull vertices to implement the solution in Message #4.

vert2con will give you equations representing the hull

A*x<=b

You can use these equations to populate your logical mask

Subject: Creating a logical mask from a 3D convex hull

From: Troy

Date: 7 Jul, 2010 21:03:20

Message: 10 of 15

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i12n8r$k9l$1@fred.mathworks.com>...
> "Troy " <meal0016@umn.edu> wrote in message <i12me6$q02$1@fred.mathworks.com>...
>
> > I am attempting to create a logical mask as well, but I do not fully understand the process you outlined above. I have the following matrices at my disposal: the hull faces (connectivity matrix), the co-ordinates of the hull vertices, the co-ordinates of the centroid of each triangle, and the normal vectors (located at the centroid of each triangle).
> ============
>
> All you need are the hull vertices to implement the solution in Message #4.
>
> vert2con will give you equations representing the hull
>
> A*x<=b
>
> You can use these equations to populate your logical mask

I'm sorry - I misspoke when I described my volume as a convex hull. The volume to be masked is a model of an artery in the shape of an 'L' with closed ends. I am afraid vert2con will connect the two ends of the model and output equations for a convex hull with a shape similar to a 30-60-90 triangle (sort of like 'L\').

I know how to create a mask using the DelaunayTri class. However, as I described above, many of the vertices are incorrectly connected. This is because the hull functions create faces from the outermost points, whereas my volume requires specific connections (given by the 'faces' matrix that I described earlier).

I felt that the solution in message #4 would allow me to define a more specific and appropriate mask, but I don't understand the apostrophe notation that was being used.

Any help would be appreciated!

Subject: Creating a logical mask from a 3D convex hull

From: Matt J

Date: 7 Jul, 2010 21:30:20

Message: 11 of 15

"Troy " <meal0016@umn.edu> wrote in message <i12q2o$m8s$1@fred.mathworks.com>...


> I felt that the solution in message #4 would allow me to define a more specific and appropriate mask, but I don't understand the apostrophe notation that was being used.
=====

I think you mean Message #2. The apostrophe notation V'x in message #2 is V'*x, i.e., the dot product of the normal vector V to one of the face with a vector x.

Message #4 proposes the same solution as in Message #2 with the only difference being that vert2con would do much of the work in setting up the equations.

All of this is moot for you, however, because all of the techniques proposed in this thread are applicable only for a convex hull.

Subject: Creating a logical mask from a 3D convex hull

From: Anusha

Date: 20 Sep, 2012 03:01:15

Message: 12 of 15


> I know how to create a mask using the DelaunayTri class. However, as I described above, many of the vertices are incorrectly connected. This is because the hull functions create faces from the outermost points, whereas my volume requires specific connections (given by the 'faces' matrix that I described earlier).

May i know how you created the mask using Delaunay TRi. I have problem creating mask for a concave object too.

Thnks.

Subject: Creating a logical mask from a 3D convex hull

From: Steven_Lord

Date: 20 Sep, 2012 13:41:44

Message: 13 of 15



"Anusha " <anusha@cs.usm.my> wrote in message
news:k3e0tr$69o$1@newscl01ah.mathworks.com...
>
>> I know how to create a mask using the DelaunayTri class. However, as I
>> described above, many of the vertices are incorrectly connected. This is
>> because the hull functions create faces from the outermost points,
>> whereas my volume requires specific connections (given by the 'faces'
>> matrix that I described earlier).
>
> May i know how you created the mask using Delaunay TRi. I have problem
> creating mask for a concave object too.

Your problem is ambiguous. See a 2D example that demonstrates the ambiguity
of creating a "concave hull" here:

http://www.mathworks.com/matlabcentral/newsreader/view_thread/256591#785780

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Creating a logical mask from a 3D convex hull

From: Anusha

Date: 20 Sep, 2012 14:16:08

Message: 14 of 15

"Steven_Lord" <slord@mathworks.com> wrote in message <k3f6en$bfv$1@newscl01ah.mathworks.com>...
>
>
> "Anusha " <anusha@cs.usm.my> wrote in message
> news:k3e0tr$69o$1@newscl01ah.mathworks.com...
> >
> >> I know how to create a mask using the DelaunayTri class. However, as I
> >> described above, many of the vertices are incorrectly connected. This is
> >> because the hull functions create faces from the outermost points,
> >> whereas my volume requires specific connections (given by the 'faces'
> >> matrix that I described earlier).
> >
> > May i know how you created the mask using Delaunay TRi. I have problem
> > creating mask for a concave object too.
>
> Your problem is ambiguous. See a 2D example that demonstrates the ambiguity
> of creating a "concave hull" here:
>
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/256591#785780

Actually I have a set of 3D points. I need to create a logical mask from these points. How can I do this? I thought Delaunay triangulation can be utilized to construct the object trinagulation, then steps for creating the logical mask is not clear.
>
> --
> Steve Lord
> slord@mathworks.com
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

Subject: Creating a logical mask from a 3D convex hull

From: Steven_Lord

Date: 20 Sep, 2012 15:23:54

Message: 15 of 15



"Anusha " <anusha@cs.usm.my> wrote in message
news:k3f8f8$js2$1@newscl01ah.mathworks.com...
> "Steven_Lord" <slord@mathworks.com> wrote in message
> <k3f6en$bfv$1@newscl01ah.mathworks.com>...
>>
>>
>> "Anusha " <anusha@cs.usm.my> wrote in message
>> news:k3e0tr$69o$1@newscl01ah.mathworks.com...
>> >
>> >> I know how to create a mask using the DelaunayTri class. However, as I
>> >> described above, many of the vertices are incorrectly connected. This
>> >> is because the hull functions create faces from the outermost points,
>> >> whereas my volume requires specific connections (given by the 'faces'
>> >> matrix that I described earlier).
>> >
>> > May i know how you created the mask using Delaunay TRi. I have problem
>> > creating mask for a concave object too.
>>
>> Your problem is ambiguous. See a 2D example that demonstrates the
>> ambiguity of creating a "concave hull" here:
>>
>> http://www.mathworks.com/matlabcentral/newsreader/view_thread/256591#785780
>
> Actually I have a set of 3D points. I need to create a logical mask from
> these points. How can I do this? I thought Delaunay triangulation can be
> utilized to construct the object trinagulation, then steps for creating
> the logical mask is not clear.

Use the pointLocation method for the DelaunayTri object. Points
corresponding to NaN values in the output of pointLocation are outside the
convex hull of your set of points; the rest are inside the convex hull.

Note that this only applies to the CONVEX hull. The problem is ambiguous if
you're trying to determine the set of points inside a CONCAVE region -- in
3D, consider an empty coffee mug and a half filled coffee mug. If you don't
have any points in your set corresponding to the surface of the liquid in
the half-filled mug, those point sets will look the same but the two objects
have different volumes. [Even if you do I can tweak the problem slightly by
adding in ice cubes or marshmallows (depending on what's in your mug) at
scattered locations on the surface of the liquid where you don't have
points.]

http://www.mathworks.com/help/matlab/ref/delaunaytri.pointlocation.html

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us