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\$
  • \$\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\$ – Anko Jun 16 '14 at 9:57
  • \$\begingroup\$ Sure, I'll add a diagram showing what I mean. \$\endgroup\$ – ssb Jun 16 '14 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\$ – kat0r Jun 16 '14 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\$ – ssb Jun 16 '14 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\$ – kat0r Jun 16 '14 at 11:52
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: http://i.imgur.com/A2Tcmk9.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\$
  • \$\begingroup\$ Could do with a better diagram I know \$\endgroup\$ – ThorinII Jun 16 '14 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.