4
\$\begingroup\$

I was looking at a video of a system that extrudes meshes along a curve, connecting them end to end but adjusting the vertices for a smooth connection. It does this with a mesh that as far as I know is guaranteed to have open ends that are later capped with a separate mesh.

Here is a video showing the effect I am trying to reproduce.

Let's suppose I have a mesh, then, that is open like in the picture below. How can I find the vertices that are on one edge only of this mesh? For example the ones that are selected here.

enter image description here

Previously I used a plain cylinder with open caps as an example, and finding edges that were only used for one face might have been able to do the job, but in a case like this, it would end up selecting any vertices in the middle along the bottom as well, which I don't want.

I want to be able to find the ends of a particular side like those that are selected in the picture. Theoretically I can then manipulate these into new positions if I wanted to, for example, string cylindrical segments into a curved cable structure.

For what it's worth, I'm trying to accomplish this in Unity with C#, but it's the algorithm I need help with.

\$\endgroup\$
5
  • \$\begingroup\$ I think you're going to have to define "vertex at the edge", since in a philosophical (and mathematical) sense, every vertex is at the edge of something. \$\endgroup\$ Commented Jun 16, 2014 at 9:57
  • \$\begingroup\$ Sure, I'll add a diagram showing what I mean. \$\endgroup\$ Commented Jun 16, 2014 at 9:58
  • \$\begingroup\$ Are your meshes similar/regular? In your picture, a very trivial way to find vertices that are on the edge would be "vertices that are only in two faces, not four". \$\endgroup\$ Commented Jun 16, 2014 at 10:19
  • \$\begingroup\$ @kat0r Actually, NO. I just thought of a case that would break that method that is included in what I want to accomplish. I'll edit it. \$\endgroup\$ Commented Jun 16, 2014 at 10:28
  • 2
    \$\begingroup\$ Hm, I doubt that your algorithm even exists for arbitrary meshes, as you are defining the open end yourself. How about you mark the relevant edges/vertices as open in blender, and simply use that data in Unity? (You could add vertex colors, and define "red" as open, and everything else as closed.) \$\endgroup\$ Commented Jun 16, 2014 at 11:52

2 Answers 2

Reset to default
2
\$\begingroup\$

You need more info about your mesh geometry and topology than you currently have, otherwise you will need to do alot of tests. Half edge data structure which gives you a directional edge info, can give you this information easily. Boundary half-edges and hence vertices don't have adjacent faces, so you simply check if a half-edge has an adjacent face, if not, it is a boundary edge and hence its vertices.

Half edge data structure deals with each edge as two separate direction edges. Boundary half-edges don't have adjacent faces. keep in mind that half edge data structure stores much more info than the usual vertex-face data structure which makes it able to perform fast geometry queiries and lookups. In case of detecting boundary edges, what you need to do is only asking if a half edge have an adjacent face. Adjacent faces are stored in the half edge info.

But your problem is that you need to build your data structure using half edge data structure.

\$\endgroup\$
0
\$\begingroup\$

Based on your picture, you appear to want to know the vertices that are not fully enclosed in a group of faces.

If kat0r's answer suffices, go with that.

Otherwise, you need to look for vertices that either:

  • Have two or less edges connected to them or,
  • Have edges that all participate in faces, without gaps.

Like this: https://i.sstatic.net/zAaD2.jpg

One way of doing that would be to sort all the edges for a vertex based on angle, then check if there is a face for every edge and it's neighbour.

\$\endgroup\$
1
  • \$\begingroup\$ Could do with a better diagram I know \$\endgroup\$ Commented Jun 16, 2014 at 10:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.