Got Questions? Get Answers.
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:
Polygon edges

Subject: Polygon edges

From: Darryl D'Lima

Date: 15 Dec, 2002 17:26:48

Message: 1 of 5

Hi,


Is there an easy method in Matlab to extract the outline of an object
made up to triangular facets? What I want is to simulate the
projection of a 3D object and extract its silhouette. In its
simplest form, I can compute the 2D projection of the 3D triangles
making up the facets of the object. Then use any of the Matlab
functions fill, patch, etc to plot the triangles. Extract the image
data from the plot and run an edge detection. The catch is Matlab
takes several seconds to display the plot on my 1 GHz PIII (since my
object has thousands of triangles). And I need to do this several
hundred times in my algorithm. So I was hoping to be able to
directly extract the edges of the triangles that make up the
silhouette of the 3D image or the perimeter of the 2D projection. I
have searched the archives and even looked up some 3D computer
graphics texts. Although I found some interesting information on
ray-tracing and hidden line removal algorithms I could not find any
efficient method of just detecting the edges of the silhouette.


Thanks,


Darryl

Subject: Polygon edges

From: John D'Errico

Date: 15 Dec, 2002 20:52:15

Message: 2 of 5

In article <eeb6843.-1@WebX.raydaftYaTP>, "Darryl D'Lima"
<dd'lima@scrippsclinic.com> wrote:

> Is there an easy method in Matlab to extract the outline of an object
> made up to triangular facets? What I want is to simulate the
> projection of a 3D object and extract its silhouette. In its
> simplest form, I can compute the 2D projection of the 3D triangles
> making up the facets of the object. Then use any of the Matlab
> functions fill, patch, etc to plot the triangles. Extract the image
> data from the plot and run an edge detection. The catch is Matlab
> takes several seconds to display the plot on my 1 GHz PIII (since my
> object has thousands of triangles). And I need to do this several
> hundred times in my algorithm. So I was hoping to be able to
> directly extract the edges of the triangles that make up the
> silhouette of the 3D image or the perimeter of the 2D projection. I
> have searched the archives and even looked up some 3D computer
> graphics texts. Although I found some interesting information on
> ray-tracing and hidden line removal algorithms I could not find any
> efficient method of just detecting the edges of the silhouette.

Yes, it is possible to do. Is it easy? That depends
on your skill at matlab. I can give you an outline of
my code, which runs quite rapidly, although I am also
sure that other variations on my code are quite possible.
I do know that everything I do in my code is vectorized.

I assume that you have a complex composed of tetrahedra.
I have not assumed they form a convex object in 3d.
A projection of a 3d shape into a plane requires a
definition of the plane. What is important here is
the normal to that plane. Thus, projection into the
x-y plane means the normal to that plane is [0 0 1].

1. List all faces of every simplex.
2. Using sort and then sortrows, sort the faces,
   so that pairs of shared faces fall consecutively
   in the list of all faces.
3. Each shared face is internal to the tessellation,
   so delete the shared faces. What remain are the
   surface faces.
4. Form the normal to each face. Use cross.
5. Ensure the face normals point outward from the
   object. Use knowledge of the original tetrahedron
   the face belongs to to orient the normals properly.
6. Determine whether a given face is "seen" by the
   observer. Is the dot product of the projection
   plane normal with the face normals for each surface
   face positive? If so, then that face is potentially
   visible. Keep only those faces with a positive DP.
7. Project all the vertices in the tessellation into
   the plane of interest.

At this point, you have a reasonably small set of
triangles, projected into the plane of interest. Think
of the approach as hidden face removal. Some of the
triangles may overlap others, this is only a problem
if the original tessellation was not a convex one.

What I have not shown you how to do is how to deal
with the case of overlap. My approach is to compute
a set union of a list of triangles in the plane,
some of which may overlap. (It helps that I have
union, intersection and set difference operators
written for a general complex in 2 or 3-d. This part
takes some work.)

HTH,
John D'Errico

--

Subject: Polygon edges

From: Michael Garrity

Date: 16 Dec, 2002 10:05:18

Message: 3 of 5


"Darryl D'Lima" <dd'lima@scrippsclinic.com> wrote in message news:eeb6843.-1@WebX.raydaftYaTP...
> Hi,
>
>
> Is there an easy method in Matlab to extract the outline of an object
> made up to triangular facets?
>
>[snip current algorithm description]
>

 It depends. If you can assume that the objects are closed and
convex, then it is really easy. In that case, the silhouette edges are
those edges that are shared by two triangles whose normals have
Z components of opposite sign.

 The general case is quite a bit more complex. All of the edges
selected by the first rule (and any unshared edges) are candidate
silhouette edges, but further visibility rejection tests are required.
As you have discovered, there is quite a literature in this area.
Note that you even have to worry about the case where just a
portion of one of the object's edges is a silhouette.

 In between the most simple and most general cases, there are
a few cases that aren't too bad. For example, in some cases it
is possible to take the set selected by the first rule, and then use
2D operations to get the outermost polygon of the result. This
obviously only works for closed surfaces genus 0.

    -MPG-

Subject: Polygon edges

From: Darryl D'Lima

Date: 16 Dec, 2002 11:55:37

Message: 4 of 5

Thanks Michael & John,


(Actually I read quite a few of John's posts regarding polygon and
voronoi/delaunay operations.) I did look for edges shared by
triangles whose normals face in different directions. Unfortunately
my 3D model can be concave, hence the reason for my request for a
more general algorithm.


I am not sure what you mean by "closed surface genus 0". I would
like to do exactly what you proposed, Mike: "2D operations to get the
outermost polygon of the result". Any pointers?


Darryl

Subject: Polygon edges

From: Michael Garrity

Date: 16 Dec, 2002 14:02:56

Message: 5 of 5


"Darryl D'Lima" <dd'lima@scrippsclinic.com> wrote in message news:eeb6843.2@WebX.raydaftYaTP...
> Thanks Michael & John,
>
>
> (Actually I read quite a few of John's posts regarding polygon and
> voronoi/delaunay operations.) I did look for edges shared by
> triangles whose normals face in different directions. Unfortunately
> my 3D model can be concave, hence the reason for my request for a
> more general algorithm.
>
>
> I am not sure what you mean by "closed surface genus 0". I would
>
 Sorry, that's graphics weeny talk for "no holes". Imagine a donut. From
some angles it has an outer silhouette and an inner silhouette. Just projecting
all of the edges and finding the outside doesn't work then. Instead, you
need to find the unshared edges of the visible polygons.

>
> like to do exactly what you proposed, Mike: "2D operations to get the
> outermost polygon of the result". Any pointers?
>
 Well, if you really are genus 0, then it is pretty simple conceptually,
but kind of a pain in practice. Set a transparent glass on your desk and
look at it at an angle. You'll see several edges where the dot product of
the surface normal and your eye's direction vector changes sign. There
are a couple of straight, vertical ones, and two sets of concentric ellipses
at the top and bottom. Not all of these edges are the ones you want though.
You only want the "outermost" of them (1). As John said, this boils down to
the "union" operator on polygons. That's a bit complex to right if you're not
familiar with that sort of code.

 There are several good books on that cover this sort of thing. I particularly
like:

  Computational Geometry: Algorithms & Applications
  M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf

and maybe also:

  Geometric Tools for Computer Graphics
  Philip J. Schneider, David H. Eberly

or:

  Computational Geometry in C
  Joseph O'Rourke

 They are fairly thorough without being too intimidating in their use
of jargon.

    -MPG-



1) You can see why genus 0 is important if you do the same
experiment with a coffee mug. If you just take the union of all
of the polygons, you'll fill in the hole in the handle. A coffee
cup (like a donut) is genus 1.

Tags for this Thread

No tags are associated with 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