CODEWITHSUNDEEP
3dgeometrymesh
olivarra1
olivarra1

Reputation: 3409

Find vertices not surrounded by faces

I'm working with a mesh which is roughly represented as

{
   vertices: [{
      x: number,
      y: number,
      z: number
   }, ...],
   faces: [{
      verticeIndices: [number, number, number]
   }, ...]
}

Now given a vertex I'd like to know whether this vertex is surrounded by faces or not. Problem is I don't even know where to start. It seems like it would be something really simple (because when visualising the mesh it's really easy to know whether a vertex is surrounded or not by faces), but I don't know how to express this.

So here's an example picture in 2D:

enter image description here

It's easy to see how the vertices painted in green are not surrounded by faces - And that if we were to connect the two vertices on the bottom left, then the one next to those in the middle would become red.

In this 2D case (probably more simple?) the only way I imagine would be by:

  1. Finding all of the adjacent faces.
  2. Find the angle of each face on that vertex.
  3. If it adds up to 360, then it's all covered, otherwise it's not.

But I think that doesn't really hold up when working in 3D... Is there an easy way of finding out whether a vertex is surrounded or not by faces in 3D?

Upvotes: 2

Views: 225

Answers (2)

Jing Zhao
Jing Zhao

Reputation: 2682

If one of the edges adjacent on a vertex is a boundary edge, then the vertex is not surrounded by faces.

A boundary edge is adjacent on only one face, while interior edges are adjacent on two faces. (Sometimes more than 2, when non-manifoldness occur.)

To use this info, you will need to have access to the edges surrounding a vertex.

If you haven't heard of half edge data structure, you might want to take a look at this introduction.

Your method works great if it's not easy to access the edges surrounding a vertex.

Upvotes: 1

olivarra1
olivarra1

Reputation: 3409

I just found a posible answer, but I'd like to see if there are easier ways:

There's another way of finding that in 2D that scales to 3D:

  1. Find the adjacent vertices of the target vertex.
  2. Make a graph with only those vertices (and without the target vertex)
  3. See if that graph has a cycle.

If all the adjacent vertices make a cycle, then it means that that vertex is surrounded (if I'm not wrong and I'm missing an edge case)

And it looks like this should scale to 3D.

I'll leave this question open in case someone has another better idea.

Upvotes: 2

Related Questions