Ordererd 1-ring/neighbourhood

[snk_kid 1312]

Hi, given a list of neighbours for a particular vertex in some arbitrary order what would be the best method of making this ordered in a counter clockwise rotation around that particular vertex. My initial thought is to find the best fitting plane of the 1-ring, project every vertex onto this plane and then sort the list by lexicographical order of each coordinate i.e. compare by x then by y. Is there a better way to solve this problem?

[robotichrist 193]

Probably your best bet is to use a winged edge data structure. This requires a bit more book keeping, but for the types of queries you just described it is provably optimal.

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html

[snk_kid 1312]

Quote:

Original post by robotichrist Probably your best bet is to use a winged edge data structure. This requires a bit more book keeping, but for the types of queries you just described it is provably optimal. http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html

We're already using a structure that provides similar information to winged-edge but the mapping of vertex index to a list of edge indices that a vertex is connected to is not ordered (or in an order i need) besides these structures are actually too bloated and expensive for what i'm working on at the moment (subdivision surfaces using catmull-clark with various extensions).

I've already decided earlier on I'm going to change the structures where using for something more simple yet flexible enough and more efficient like Vertex-Vertex Systems.

However right now since we already have structures that provide the necessary information (and more than I actually need) i'm just doing the implementation with what we've got already and worrying about efficiency towards the end.

So as i've current the list of edges connected by a particular vertex
as the 1-ring/neighbourhood has served me well but the problem is that when computing vertex normals for a sub-d using tangent stencils (which computes the tangent vectors on the limit surface) the 1-ring/neighbourhood needs to be an ordered list to compute the correct tangent vectors and computing normals which all face in the right direction.

Anyways if there isn't a better method (untill i've change representation) could someome tell me if what i was saying earlier would be correct and in all cases?

Maybe i should just change the creation of edges (and thus the mapping of vertices to it's connnected edges) such that 1-ring/neighbourhood is already ordered but that still leaves me in a similar position.

[Edited by - snk_kid on July 17, 2007 3:28:35 AM]

[d00fus 328]

I'm not sure if the lexicographical sort would do the job correctly when the projected points do not form a convex polygon? Instead perhaps a radial sort may be more reliable. Compute the signed dot product between a reference vector (the vector from the vertex to one of the projected neighbours, chosen arbitrarily) and the vector from the vertex to each of the other projected points, and then sort the vertices by this value. This should order the vertices correctly I think.

[robotichrist 193]

Quote:

Original post by snk_kid We're already using a structure that provides similar information to winged-edge but the mapping of vertex index to a list of edge indices that a vertex is connected to is not ordered (or in an order i need) besides these structures are actually too bloated and expensive for what i'm working on at the moment (subdivision surfaces using catmull-clark with various extensions). I've already decided earlier on I'm going to change the structures where using for something more simple yet flexible enough and more efficient like Vertex-Vertex Systems.

I've never heard of vertex-vertex systems, but they sound interesting. If you can send a link or a pointer to an article, I'd like to find out more.

I really don't understand why a winged-edge/half-edge structure would be so bad. The overhead is only O(1), compared to something like a vertex-array. They even work well with GPUs, since the vertices can be cached within vertex buffer objects.

Edge-based data structures are ideal for subdivision surfaces. For example, here is some psuedocode which should do the traversal that you are looking for using a winged-edge structure:

void traverseVerts(Vertex v)
{
	Edge start_edge = v.edge;
	Edge cur_edge = start_edge;
	
	do
	{
		if(cur_edge.start == v)
		{
			visit(cur_edge.end);
			
			cur_edge = cur_edge.left.next;
		}
		else
		{
			visit(cur_edge.start);
		
			cur_edge = cur_edge.left.prev;
		}
	
	} while(cur_edge != start_edge)
}

That said, they do have limitations. While winged edge data structures are generally quite fast, they are extremely painful to program. I personally try to avoid them since I find them difficult to debug, and usually more trouble than they are worth. Constructing and modifying them is especially difficult, since it is almost impossible to follow what is going inside these things half the time.

[The Reindeer Effect 211]

what is a 1-ring? i've never heard that term before

I'm just guessing you might mean a circle... if that is the case the standard topological term is 1-sphere (if you really dont feel like saying circle)

[snk_kid 1312]

Quote:

Original post by robotichrist I've never heard of vertex-vertex systems, but they sound interesting. If you can send a link or a pointer to an article, I'd like to find out more.

There are a few papers about it on the Algorithmic Botany's website (very cool site!), the main paper to read about them and how it compares to other systems can be read on On Vertex-Vertex Systems and Their Use in Geometric and Biological Modelling.

VV systems are vertex based structures, another vertex based (related to and kind of predecessor of VV systems) structure is the Doubly Linked Face List (DLFL) data structure.

Topmod (Topological modeller) uses DLFL, this software is amazing have a look at some of the stuff you can model with it here. Everyone should have look at it! by the way they have lots of papers on that site including the stuff on DLFL.

Quote:

Original post by robotichrist I really don't understand why a winged-edge/half-edge structure would be so bad. The overhead is only O(1), compared to something like a vertex-array.

I was a little ambiguous what mean't is winged-edge isn't very efficent in terms of space not time and updates are relatively expensive. Half-edge isn't so bad.

Quote:

Original post by robotichrist They even work well with GPUs, since the vertices can be cached within vertex buffer objects.

Now that you mention it i was considering for transforming the control points and seeing the results interactively/(almost) real-time i would do on the fly subdivision and adaptive tessellation completely on the GPU like what is described in GPU Gems 2's Adaptive Tessellation of Subdivision Surfaces with Displacement Mapping. The only problem with GPU Gems 2's approach is that it cannot handle n-gon meshes (as far as i'm aware), so i might have look into the paper A Realtime GPU Subdivision Kernel which supposedly can handle n-gon meshes.

The other idea i had was instead of an incremental subdivision approach i use an exact-evalution approach which allows you generate to subdivsion surface at a particular level directly, you can pretty much treat them as parametric surfaces as i understand it. Apparently Maya takes this approach to Sub-Ds.

I don't know exactly which way i'll go and i would be highly interested to read what others think/do.

Quote:

Original post by robotichrist Edge-based data structures are ideal for subdivision surfaces.

This isn't completely true, from 2000 siggraph course notes on subdivision surfaces:

Quote:

Originally from Subdivision for Modeling and Animation, page 105 ... A variety of representations were proposed in the past for general meshes of this type, sometimes with some of the assumptions relaxed, sometimes with more assumptions added, such as orientability of the surface represented by the mesh. These representations include winged edge, quad edge, half edge end other data structures. The most common one is the winged edge. However, this data structure is far from being the most space efficient and convenient for subdivision. First, most data that we need to store in a mesh, is naturally associated with vertices and polygons, not edges. Edge-based data structures are more appropriate in the context of edge-collapse-based simplification. For subdivision, it is more natural to consider data structures with explicit representations for faces and vertices, not for edges...

Quote:

Original post by robotichrist That said, they do have limitations. While winged edge data structures are generally quite fast, they are extremely painful to program. I personally try to avoid them since I find them difficult to debug, and usually more trouble than they are worth. Constructing and modifying them is especially difficult, since it is almost impossible to follow what is going inside these things half the time.

Bingo! luckly for me someone else wrote the windged-edge-like structures for are meshes and all the required updates, so i just want to get almost everything implementated using what we've got and profile before i do any changes to representation. This also helps me to understand the problem more by increments and refactoring, instead of spending to much time thinking about how to go about it and stuff and wasting time.

Quote:

Original post by The Reindeer Effect what is a 1-ring? i've never heard that term before I'm just guessing you might mean a circle... if that is the case the standard topological term is 1-sphere (if you really dont feel like saying circle)

My terminology (well not mine but you know what i mean) is correct, the 1-ring refers to the first level or the immediate neighbourhood of a particular vertex. The definition is a bit vague but generally it means all vertices surrounding a vertex connected by an edge. 2-ring would mean the neighbourhood of neighbourhood of a vertex and 3-ring ... and so on.

This information is required for implementing things like subdivision surfaces, computing vertex normals, etc, etc.

[Edited by - snk_kid on July 18, 2007 6:18:43 AM]

[dvmorris 122]

Hello everyone,

I just wanted to let you know that there is a brand new version of TopMod available for Windows and OS/X that makes creating sculptures a lot easier. Try it out here:

http://www.ends170.com/topmod

and check out the video tutorials here:

http://topmod.blip.tv

Let me know what you think. I’m redoing the interface and adding new functions for my graduate thesis research, and I’m always looking for new ideas and critiques. Thanks for your help,

Dave Morris

[killah 122]

Hi snk_kid, I just wanted to know which solution do you finally use for the 1-ring construction because I've got similar problems.

At first I tried to use OpenMesh library (http://www.openmesh.org) which implements a halfedge data structure, but each time I had problems with it I didn't find support anywhere... only the OpenMesh site documentation, no forums, nothing... I think that I could do this with simpler structures but I'm not sure how...

Well, can you explain me how you finally did it? is a good solution projecting the points to the best fitting plane and sort them as you said?

Thank you very much

[snk_kid 1312]

Quote:

Original post by killah Hi snk_kid, I just wanted to know which solution do you finally use for the 1-ring construction because I've got similar problems. At first I tried to use OpenMesh library (http://www.openmesh.org) which implements a halfedge data structure, but each time I had problems with it I didn't find support anywhere... only the OpenMesh site documentation, no forums, nothing... I think that I could do this with simpler structures but I'm not sure how... Well, can you explain me how you finally did it? is a good solution projecting the points to the best fitting plane and sort them as you said? Thank you very much

So far I haven't completely changed representation just yet, however i did make it complete with what we have, profiled and made it quite fast. It's just a memory eater now but at the moment I'm working on a few other things as well as allowing for interactive edits to subdivision surfaces.

In the end my idea I could not get working correct or using the radial sort method so i did it via a simpler (a bit hackish) method.

If OpenMesh uses half-edge as it's structure it should be relatively easy to get the 1-ring and it should come out ordered without requiring any sorting, have a look here.

If you still want me to describe how I did it just ask.