View Full Version : Vertex Data structure

04 April 2008, 01:48 AM
I just thought I'd throw this out there;

I have a series of vertexes that build a sphere. I can subdivide each triangle, building new points from the data of the previous ones.

1 2

1 1:2 2

That bit's easy - however I want to store them in a meaningful way, so that:

A) I don't have to do the maths to generate each point every time I render it
B) I can store other values of the point
C) I can load or save the object

Currently I'm storing each vertex in a hash-table, with it's name generated from it's parent's names. (as seen above). This works, but I still have to rebuild a lot of the object each time (to get the appropriate names of points). I also fear doing a few thousand lookups in a hash-table might be just as intensive as regenerating the data.

Storing as a linear array doesn't work, as points need to exist at multiple levels of detail.
Out of interest this is the mesh I'm building.

Bryan Y
04 April 2008, 03:07 AM
Each vertex could maintain a list of the faces it is part of, in an order such that the first faces are of level one, the second set are of level two, the third set are of level three, etc.

Each face points to the three vertices it uses.

The age of a vertex (the level at which it was created) will determine how many levels of faces they point to.

04 April 2008, 03:20 AM
That sounds like it could be a little data-heavy;

We played around with the idea here:-

Store a list of points in the order they're needed to create the surface:


Upon subdividing, generate new faces in order:


Each vertex contains detail of which level of detail it is, in this case:


Pulling out an array of vertexes with at the level of detail you're after or lower gives a list of triangles.


Bryan Y
04 April 2008, 03:39 AM
I'd ponder it some more, but I'm not focused enough to provide any more meaningful input at this time. Maybe tomorrow. I do know that I've explored problems like this before.

04 April 2008, 09:14 AM
You could do it using a hierarchical half-edge or winged-edge structure (unless I'm missing some subtlety in what you're doing).

Basically they allow constant lookup time for neighbouring faces, vertices, edges etc. I use it for the subdivision stuff I do, and they're nice and quick for that. Can try to dig you out some links later if you want, however I struggled to find good, complete information on them when I first implemented mine (was planning to summarise and put on the wiki but haven't had a chance to yet)

04 April 2008, 10:43 PM
You've been following my thread in the other forum so you're aware kind of what I'm trying to do.

I'd love to see links, the wiki article even more (I promise that at some point I'll put stuff I've figured out into some articles as well.)

I've looked at the half-edge, and winged edge stuff, and I don't know if they're the solution to this problem, from what I've seen they assume the mesh will have a constant topology.

Unlike traditional LOD stuff - rather than taking a mesh and cutting it back, if I don't want detail, I don't generate it (although if I do want detail, I can always make more).

04 April 2008, 07:23 AM
Well, the half-edge/winged-edge structures can be made hierarchical, so for example, each vertex can have a child vertex, a half-edge can have two child half-edges and the neighbouring half-edges will know to share the newly created vertex. I generate my sub-divisions only when needed as well, when a patch interaction need to be refined.

Didn't have a chance to dig up some links last night, will have a look later, though I can't recall if I ever saw any articles about using them hierarchically (that was something that just suited me a lot better).

For the stuff I do, being able to look up neighbouring vertices, edges, faces, and following edges around a surface without a noticeable overhead, is brilliant. Obviously there is a bit of extra data, though, so it depends how much of an issue that is.

04 April 2008, 08:40 AM
Yeah - you never know I might discover half-way through, I really need functionality that I can't get with my lighter weight 1 dimensional array and have to back-track again.

04 April 2008, 02:31 PM
Does this hierarchical structure look anything like a cross between a KD-Tree and a top down directory structure?

04 April 2008, 03:03 PM
Obudtaig: No.... Unless I don't get what you mean, I'm getting to the point of the day where thinking is an effort;)

Basically for what I'm doing, I know every face can potentially have exactly four children.
Every vertex can have only one child vertex, and every half-edge can have exactly two children. So essentially every original vertex can have one straight line of descendants, every original half-edge forms the root of a binary tree, and every original face forms the root of a quad-tree. (with cross-links between the different trees).

04 April 2008, 11:38 PM
Upon subdividing, generate new faces in order:


Each vertex contains detail of which level of detail it is, in this case:


I should point out, I've managed to do without the second array, so long as I know how many initial triangles there were, it's pretty simple to pull the right points out.

04 April 2008, 04:58 PM
Not unlike what I was thinking of, although for some reason it bypassed me that you're talking about subsurfs so quad-trees would fulfil both the min and the max for the data required. I was thinking along the lines of a directory structure because a relatively unlimited number of child polys would be well suited to LOD stuff in a less rigidly defined mesh.

I was also thinking of a set of data which had pointers for separate structures so it was arranged differently depending on how you looked at it. I asked about the KD-Tree because you brought up spatial relations between faces, edges and such. I'm not really sure what the most useful data struct would be.

CGTalk Moderation
04 April 2008, 04:58 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.