PDA

View Full Version : Vertex Data structure


salmonmoose
04-14-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.

http://moose3d.com/images/planet_02.png
Out of interest this is the mesh I'm building.

Bryan Y
04-14-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.

salmonmoose
04-14-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:

{1,2,3}

Upon subdividing, generate new faces in order:

{{1,1:2,1:3},{2,2:3,1:2},{3,1:3,2:3},{1:2,2:3,1:3}}

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

{{1,2,2},{1,2,2},{1,2,2},{2,2,2}}

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

Thoughts?

Bryan Y
04-14-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.

Carina
04-15-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)

salmonmoose
04-15-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).

Carina
04-16-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.

salmonmoose
04-16-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.

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

Carina
04-16-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).

salmonmoose
04-16-2008, 11:38 PM
Upon subdividing, generate new faces in order:

{{1,1:2,1:3},{2,2:3,1:2},{3,1:3,2:3},{1:2,2:3,1:3}}

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

{{1,2,2},{1,2,2},{1,2,2},{2,2,2}}


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.

UrbanFuturistic
04-18-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-18-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.