How to find the two adjacent faces of an edge?

OpenGL OpenGL: Advanced Coding
1

Hi…

How to find the two adjacent faces of an edge please?

Many thanks

2

Well nico you have to store all needed topological data with your models.
If you don’t know what topology is
take a math class on the subject… :->

3

Well, I don’t think you need a topology class for this…

Depends on how you’re storing geometry - OpenGL doesn’t specify this so there isn’t a “standard” answer. If you’re doing the usual sort of thing - an array of vertices plus three int indices into this array for each triangle - then just take the indices of the endpoints of your edge and look for triangles that use both of them.

That’s the general case; lots of obvious precalculations & special-case optimizations possible, depends what you’re doing.

4

If this is something that you do very rarely, and you have no other need to know edge-face information, you might as well do a simple search (although that’s really slow).

If this operation is used at all frequently,
you should use a data structure that speeds such computations. A good choice is to use a winged-edge data structure (or design your own structure optimized for the types of accesses you are performing). If you can, check out a copy of Computer Graphics: Principles and Practice, that’s almost guaranteed to describe it, as well as other options you might take. Any other decent graphics text would also mention it.

5

I’ll try the easy way then…

I’ve you got any code example that uses the winged-edge data structure please?

Thanks

Nico

6

Hmm, I had to tackle a very similar problem when I tried to write a mesh decimation algorithm. I designed my data structures as essentially two arrays, one of triangles and one of vertices. The neat thing is, each vertex has an array of pointers to the triangles that use it. So, then all you need to do is iterate over these triangles that share a point and find another point that matches between two triangles in this “local” list. Then, you have the edge the two triangles share defined by these two matching points (note that, the first point is assumed to be the same since you already know both triangles use that point).

Is this a wing-edge data structure? Ack, four years of college and I don’t know what a wing-edged data structure is…

William Schroeder refers to this structure as a “Space-efficeient vertex-triangle hierarchical ring structure.” hehe…

7

No, it’s not. Frankly, though, if you’re referring to Schroeder’s algorithm from “Decimation of Triangle Meshes”, that is a better choice for that problem. Making the best data structure on the spot is why you went to college, not learning to memorize trivia, eh? Hehe, otherwise, you could have just bought a book, pasted code, and saved a whole bunch of time of money, right?

8

Thanks…

Have you got a code example of the structure you created

What do I have to add to the following structures to get what you told me?

typedef struct
{
float x,y,z;
float l;
}vertex;

typedef struct
{
vertex p1, p2, p3;
vertex normal;
}face

Thanks

nico