Mesh data structures, vol. 2: Vertex one-rings

So let’s suppose you’re a developer working on triangle meshes. You’ve read my first article on vertex-face lists (and, inexplicably, nothing else), and now you’re running into problems with connectivity. Perhaps you want to apply a subdivision operator to your mesh, but you can’t easily figure out which vertices are neighbours, or where the edges are. Fortunately, there’s an easy way to add basic connectivity information to a vertex-face list: keep track of each vertex’s neighbours, its one-ring.

Vertex one-ring

Looking at our little diagram here, the vertex v has a one-ring of {a, b, c, d, e, f}. Generally it’s easiest to work with one-rings in some sort of order — counterclockwise is preferred, because that’s how trig functions work — but you don’t necessarily need that kind of complexity.

Adding one-rings to your vertices is pretty simple. Obviously, you’ll need a container in each vertex to store one-ring indices:

typedef struct {
  float x, y, z;
  size_t n_nbrs;
  size_t* one_ring;
} vertex;

Next, every time you add a face to the mesh, you update the one-rings of its vertices. For example, when you add face vab, you add a and b to v‘s one-ring, v and b to a‘s one-ring, and v and a to b‘s one-ring.

Keeping around a one-ring list for each vertex lets you walk from vertex to vertex (and, implicitly, from edge to edge) on a mesh, which is most of what you need to do for subdivision. However, it doesn’t let you walk from face to face without some extra book-keeping.

19 Responses to “Mesh data structures, vol. 2: Vertex one-rings”

  1. January 5, 2013 at 16:48

    Hey! Someone in my Facebook group shared this website with us so I came to check it out.
    I’m definitely loving the information. I’m bookmarking and will be tweeting this to my
    followers! Outstanding blog and outstanding style and design.

  2. February 13, 2013 at 17:43

    Admiring the time and energy you put into your blog and in depth information
    you offer. It’s nice to come across a blog every once in a while that isn’t the same unwanted rehashed information.
    Fantastic read! I’ve bookmarked your site and I’m adding
    your RSS feeds to my Google account.

  3. March 12, 2013 at 11:12

    Hello, i think that i saw you visited my site thus i came to “return the favor”.
    I am attempting to find things to enhance my website!

    I suppose its ok to use a few of your ideas!!

  4. June 18, 2013 at 09:47

    Hi there, i read your blog from time to time and i own a
    similar one and i was just wondering if you get a lot of spam responses?
    If so how do you prevent it, any plugin or anything you can advise?
    I get so much lately it’s driving me insane so any help is very much appreciated.

  5. June 22, 2013 at 09:58

    These are the best alternatives to steroids. ‘This determination, by two of the leading dietary supplement firms in the world, is ‘just what
    the doctor ordered’ for the members of our growing agricultural industry,’ Coplan said.
    One of the more popular releases is Hyper – GH 14x.

  6. June 23, 2013 at 10:48

    fantastic issues

    altogether, you just gained a new reader.
    What could you recommend

    in regards to your submit that you just made a few days in the
    past? Any


  7. July 11, 2013 at 12:27

    I constantly emailed this webpage post page to all my friends, as if like to read it
    after that my friends will too.

  8. July 15, 2013 at 17:16

    Hello! I just wanted to ask if you ever have any trouble with hackers?
    My last blog (wordpress) was hacked and I ended up losing months of hard work due to no backup.

    Do you have any solutions to prevent hackers?

  9. July 17, 2013 at 04:11

    Howdy! Quick question that’s entirely off topic. Do you know how to make your site mobile friendly? My web site looks weird when browsing from my iphone. I’m trying to find a theme or plugin that might be able to correct this problem.
    If you have any recommendations, please share. Cheers!

  10. July 18, 2013 at 01:51

    I’m wondering which blogging and site-building platform you are running? I’m new to running a blog and have
    been thinking about using the Tripod platform. Do you consider this is a good foundation to start with?
    I would be very thankful if I could ask you some questions through e-mail so I
    can learn a bit more before getting started. When you have some free time, please be sure to contact me at:
    sondradobbs@t-online.de. Appreciate it

  11. August 4, 2013 at 08:17

    Hi to all, because I am in fact keen of reading this blog’s post to be updated daily. It carries pleasant information.

  12. August 7, 2013 at 15:28

    Hi everyone, it’s my first go to see at this site, and post is genuinely fruitful for me, keep up posting these posts.

  13. August 10, 2013 at 01:16

    My family members always say that I am killing my time here at net, except I know I am getting experience daily by reading such nice
    articles or reviews.

  14. February 4, 2014 at 01:38

    Hurrah, that’s what I was exploring for, what a stuff! present here at this website, thanks admin of this site.

  15. February 5, 2014 at 22:48

    Spot on with this write-up, I really believe this amazing site needs a great deal more attention.
    I’ll probably be returning to see more, thanks for the info!

  16. September 15, 2014 at 00:13

    It’s really a great and useful piece of info. I am satisfied that you shared this useful info with us.
    Please keep us up to date like this. Thanks for sharing.

Leave a reply; use raw HTML for markup. Please blockquote quotations from the post or other comments.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

anarchocapitalist agitprop

Be advised

I say fuck a lot



Statistics FTW

%d bloggers like this: