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:
contour generator of surface mesh

Subject: contour generator of surface mesh

From: Ben

Date: 26 Nov, 2010 06:26:03

Message: 1 of 11

Hello everyone,

This should be a classical computer graphics work.

Given a viewing point, I want to extract the contour generator form a given triangulated surface mesh. Specifically, given a 3D position and a triangulated surface mesh in a 3D coordinate system, how to extract the vertices that form the contour (outer boundary)?

For the surface mesh, it also includes the surface normals and vertex normals.

I have a naive idea as follows
1 Calculate the visual rays for all the vertices,
2 Check each surface using the criterion: A facet is partially visible if and only if not all its three vertices are visible or non-visible. This can be done by checking the angle between the visual ray and the vertex normal.

However, this method has two problems.

First, going through all the facets is time-consuming. It take several minutes in my case.

Second, it also produces the contours within the outline of the surface mesh. To eliminate them, further complex check should be taken. This will additionally slow down the program.

Is here anyone know an efficient way to do it? Or does someone know where I can download a C/C++ code to do this if matlab could not do it efficiently?

Best,
Ben

Subject: contour generator of surface mesh

From: Bruno Luong

Date: 26 Nov, 2010 07:33:08

Message: 2 of 11

It is not clear whereas you have difficulty to find the contour or display the contour?

There is a file on FEX to find the contour of triangular mesh. To display, Matlab stock graphic routines should be able to carry out the task.

Bruno

Subject: contour generator of surface mesh

From: Ben

Date: 26 Nov, 2010 08:22:05

Message: 3 of 11

Hi Bruno,

My difficulties are
1. my method is too time consuming
2. the inner contours are still there

Could you give me the url of the FEX file you mentioned?

Thanks,
Ben

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <icnnrk$a70$1@fred.mathworks.com>...
> It is not clear whereas you have difficulty to find the contour or display the contour?
>
> There is a file on FEX to find the contour of triangular mesh. To display, Matlab stock graphic routines should be able to carry out the task.
>
> Bruno

Subject: contour generator of surface mesh

From: Rune Allnor

Date: 26 Nov, 2010 08:29:16

Message: 4 of 11

On Nov 26, 7:26 am, "Ben " <gogo...@gmail.com> wrote:
> Hello everyone,
>
> This should be a classical computer graphics work.

It is.

> Given a viewing point, I want to extract the contour generator form a given triangulated surface mesh.  Specifically, given a 3D position and a triangulated surface mesh in a 3D coordinate system, how to extract the vertices that form the contour (outer boundary)?
>
> For the surface mesh, it also includes the surface normals and vertex normals.
>
> I have a naive idea as follows
> 1 Calculate the visual rays for all the vertices,
> 2 Check each surface using the criterion:  A facet is partially visible if and only if not all its three vertices are visible or non-visible.  This can be done by checking the angle between the visual ray and the vertex normal.

A lot of ridiculously smart people have worked on this problem,
which is at the core of gomputer graphics.

> However, this method has two problems.
>
> First, going through all the facets is time-consuming.  It take several minutes in my case.
>
> Second, it also produces the contours within the outline of the surface mesh.  To eliminate them, further complex check should be taken.  This will additionally slow down the program.

Check out the literature on efficient computer graphics.
A book on OpenGL might be a good starting point.

> Is here anyone know an efficient way to do it?  Or does someone know where I can download a C/C++ code to do this if matlab could not do it efficiently?

Your question might seem easy to ask, but requires very
advanced solutions. Don't expect to get fast solutions
in matlab. Or even working solutions; the people who can
do these kinds of things would never accept the low
run-time efficiency of matlab.

Rune

Subject: contour generator of surface mesh

From: Bruno Luong

Date: 26 Nov, 2010 08:40:08

Message: 5 of 11

"Ben " <gogo.xa@gmail.com> wrote in message <icnqnd$clu$1@fred.mathworks.com>...

> Could you give me the url of the FEX file you mentioned?
>

http://www.mathworks.com/matlabcentral/fileexchange/10408-contours-for-triangular-grids
http://www.mathworks.com/matlabcentral/fileexchange/25262-trisurfc

Bruno

Subject: contour generator of surface mesh

From: Bruno Luong

Date: 26 Nov, 2010 09:17:03

Message: 6 of 11

Sorry, I reread your post and I completely misunderstood the problem you want to solve. Please ignore then my post the FEX links.

Bruno

Subject: contour generator of surface mesh

From: Bruno Luong

Date: 26 Nov, 2010 09:26:06

Message: 7 of 11

"Ben " <gogo.xa@gmail.com> wrote in message <icnjtr$47b$1@fred.mathworks.com>...

>
> First, going through all the facets is time-consuming. It take several minutes in my case.

How do you do this? How big is the mesh? If you do correctly using Matlab vectorization it should take a fraction of second.

I think you should consider edges rather than faces. The edge is shared by two faces. The change of sign of the scalar product between normal and view direction between two faces indicates they share an outer edge.

If your solid does not have hole, no more process is necessary.

Bruno

Subject: contour generator of surface mesh

From: Ben

Date: 26 Nov, 2010 23:12:03

Message: 8 of 11

Hi Bruno,

> I think you should consider edges rather than faces.
> The edge is shared by two faces.
>The change of sign of the scalar product between normal and view direction
> between two faces indicates they share an outer edge.

For thousands of faces, so doing takes time. Do you know how to do this without using loop? Could you kindly give me an example script?

Ben

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <icnufe$h9o$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <icnjtr$47b$1@fred.mathworks.com>...
>
> >
> > First, going through all the facets is time-consuming. It take several minutes in my case.
>
> How do you do this? How big is the mesh? If you do correctly using Matlab vectorization it should take a fraction of second.
>
> I think you should consider edges rather than faces. The edge is shared by two faces. The change of sign of the scalar product between normal and view direction between two faces indicates they share an outer edge.
>
> If your solid does not have hole, no more process is necessary.
>
> Bruno

Subject: contour generator of surface mesh

From: Bruno Luong

Date: 27 Nov, 2010 08:17:05

Message: 9 of 11

"Ben " <gogo.xa@gmail.com> wrote in message <icpes3$6ou$1@fred.mathworks.com>...

>
> For thousands of faces, so doing takes time. Do you know how to do this without using loop? Could you kindly give me an example script?
>

Here is an example, it take less than 1 ms second on my computer for 2000 triangles.

% Data
n = 50;
xg = linspace(0,1,n);
yg = linspace(0,1,n);
m = 1000;
x = rand(1,m);
y = rand(1,m);
z = griddata(xg,yg,0.1*peaks(n),x,y);
T = delaunay(x,y);

% Compute the normal vector and the mid-point of all (~2000) triangles
tic
xyz = [x(:) y(:) z(:)]; % m x 3
xyzT = reshape(xyz(T,:),[size(T) 3]);
e1 = xyzT(:,2,:)-xyzT(:,1,:);
e2 = xyzT(:,3,:)-xyzT(:,2,:);
n = [e1(:,2).*e2(:,3)-e1(:,3).*e2(:,2) ...
     e1(:,3).*e2(:,1)-e1(:,1).*e2(:,3) ...
     e1(:,1).*e2(:,2)-e1(:,2).*e2(:,1)];
n = bsxfun(@rdivide, n, sqrt(sum(n.^2,2)));
xyzmid = squeeze(mean(xyzT,2));
toc; % 0.000647 seconds.

% Graphic
figure
trimesh(T,x,y,z);
hold on
quiver3(xyzmid(:,1),xyzmid(:,2),xyzmid(:,3), ...
        n(:,1),n(:,2),n(:,3));
axis equal

% Bruno

Subject: contour generator of surface mesh

From: Ben

Date: 30 Nov, 2010 05:43:03

Message: 10 of 11

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <icqeq1$2rt$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <icpes3$6ou$1@fred.mathworks.com>...
>
> >
> > For thousands of faces, so doing takes time. Do you know how to do this without using loop? Could you kindly give me an example script?
> >
>
> Here is an example, it take less than 1 ms second on my computer for 2000 triangles.
>
> % Data
> n = 50;
> xg = linspace(0,1,n);
> yg = linspace(0,1,n);
> m = 1000;
> x = rand(1,m);
> y = rand(1,m);
> z = griddata(xg,yg,0.1*peaks(n),x,y);
> T = delaunay(x,y);
>
> % Compute the normal vector and the mid-point of all (~2000) triangles
> tic
> xyz = [x(:) y(:) z(:)]; % m x 3
> xyzT = reshape(xyz(T,:),[size(T) 3]);
> e1 = xyzT(:,2,:)-xyzT(:,1,:);
> e2 = xyzT(:,3,:)-xyzT(:,2,:);
> n = [e1(:,2).*e2(:,3)-e1(:,3).*e2(:,2) ...
> e1(:,3).*e2(:,1)-e1(:,1).*e2(:,3) ...
> e1(:,1).*e2(:,2)-e1(:,2).*e2(:,1)];
> n = bsxfun(@rdivide, n, sqrt(sum(n.^2,2)));
> xyzmid = squeeze(mean(xyzT,2));
> toc; % 0.000647 seconds.
>
> % Graphic
> figure
> trimesh(T,x,y,z);
> hold on
> quiver3(xyzmid(:,1),xyzmid(:,2),xyzmid(:,3), ...
> n(:,1),n(:,2),n(:,3));
> axis equal
>
> % Bruno

Thanks for your code Bruno. But I think that is only for calculating the surface normal, not for extracting the apparent contours. I have a equally fast code for this.

Do you further have a "vectorized" version for extract apparent contour doing what you described?
>
> I think you should consider edges rather than faces. The edge is shared by two faces.
> The change of sign of the scalar product between normal and view direction between
> two faces indicates they share an outer edge.

Ben

Subject: contour generator of surface mesh

From: Bruno Luong

Date: 30 Nov, 2010 12:19:06

Message: 11 of 11

"Ben " <gogo.xa@gmail.com> wrote in message <id22t7$edg$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <icqeq1$2rt$1@fred.mathworks.com>...
> > "Ben " <gogo.xa@gmail.com> wrote in message <icpes3$6ou$1@fred.mathworks.com>...
> >
> > >
> > > For thousands of faces, so doing takes time. Do you know how to do this without using loop? Could you kindly give me an example script?
> > >
> >
> > Here is an example, it take less than 1 ms second on my computer for 2000 triangles.
> >
> > % Data
> > n = 50;
> > xg = linspace(0,1,n);
> > yg = linspace(0,1,n);
> > m = 1000;
> > x = rand(1,m);
> > y = rand(1,m);
> > z = griddata(xg,yg,0.1*peaks(n),x,y);
> > T = delaunay(x,y);
> >
> > % Compute the normal vector and the mid-point of all (~2000) triangles
> > tic
> > xyz = [x(:) y(:) z(:)]; % m x 3
> > xyzT = reshape(xyz(T,:),[size(T) 3]);
> > e1 = xyzT(:,2,:)-xyzT(:,1,:);
> > e2 = xyzT(:,3,:)-xyzT(:,2,:);
> > n = [e1(:,2).*e2(:,3)-e1(:,3).*e2(:,2) ...
> > e1(:,3).*e2(:,1)-e1(:,1).*e2(:,3) ...
> > e1(:,1).*e2(:,2)-e1(:,2).*e2(:,1)];
> > n = bsxfun(@rdivide, n, sqrt(sum(n.^2,2)));
> > xyzmid = squeeze(mean(xyzT,2));
> > toc; % 0.000647 seconds.
> >
> > % Graphic
> > figure
> > trimesh(T,x,y,z);
> > hold on
> > quiver3(xyzmid(:,1),xyzmid(:,2),xyzmid(:,3), ...
> > n(:,1),n(:,2),n(:,3));
> > axis equal
> >
> > % Bruno
>
> Thanks for your code Bruno. But I think that is only for calculating the surface normal, not for extracting the apparent contours. I have a equally fast code for this.

No, I'm just surprised that you wrote:

[ First, going through all the facets is time-consuming. It take several minutes in my case. ]

So my code is to demonstrate it does not necessary take several minute.

What do you do with the faces, beside compute the normal and the dot-product with the direction to the view point?

Comparing neighboring faces orientation is straightforward from the topology of your mesh. After detection of outer-edges, you need to write the algorithm follow them to form a chain and eliminate the hidden one. This need probably more developing time than I could afford to offer.

Bruno

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