Quad-Edge Data Structure and Library

Motivation for the Quad-Edge Data Structure

The Quad-Edge Data Structure

How to Use our Quad-Edge Library

Edge

Duality

The dual of a polyhedron is the polyhedron resulting from rotating edges 90 degrees, replacing vertices with faces, and faces with vertices. The new vertex locations can be taken to be the centroids of the old faces. For example, the dual of a cube is an octahedron, and vice versa; and dodecahedra and icosahedra are duals of each other, also. A tetrahedron is dual with a rotated copy of itself.

The quad-edge data structure gets its name because the duality is built in at a low level by storing quadruples of directed edges together:

• Edge *e - directed edge
• Edge *e->Sym() - edge pointing opposite to e
• Edge *e->Rot() - dual edge pointing to the left of e
• Edge *e->InvRot() - dual edge pointing to the right of e

Vertex

class Cell {
    Edge *makeVertexEdge(Vertex *v, Face *left, Face *right);
    Edge *makeFaceEdge(Face *f, Vertex *org, Vertex *dest);
    void killVertexEdge(Edge *e);
    void killFaceEdge(Edge *e);
};

Also, these routines (and the rest of the library) do not enforce linearity of edges or planarity of faces. It is permissible to have vertices and faces of degree 1 or 2, for example.

Given Cell *c, the calls do the following:

• c->makeVertexEdge(v, left, right) splits vertex v, creating a new edge and vertex that both lie between faces left and right. The new edge has left on its left and right on its right, v at its origin and the new vertex at its destination. The new edge is returned; the new vertex is easily found by taking Dest() of the return value. The new vertex and edge are stored in the sets associated with cell c. If left and right are not adjacent to v then an error message will be printed and core dumped.
• c->makeFaceEdge(f, org, dest) is the dual of this. It splits face f, creating a new edge and face that both lie between vertices org and dest. The new edge has org as its origin and dest as its destination, f as its left face and the new face as its right face. The new edge is returned; the new face is easily found by taking Right() of the return value. The new face and edge are stored in the sets associated with cell c. If org and dest are not adjacent to f then an error message will be printed and core dumped.
• c->killVertexEdge(e) is the inverse of makeVertexEdge. It removes edge e and vertex e->Dest(). Thus, c->killVertexEdge(c->makeVertexEdge(v, left, right)) is a no-op.
• c->killFaceEdge(e) is the inverse of makeFaceEdge. It removes edge e and face e->Right(). Thus, c->killFaceEdge(c->makeFaceEdge(f, org, dest)) is a no-op.

For debugging or display purposes, you'll often want to loop over all the vertices, edges, or faces of a cell.

To loop over the vertices of Cell *c:

CellVertexIterator cellVerts(c);
Vertex *v;
while ((v = cellVerts.next()) != 0)
    <do something with vertex v>

CellFaceIterator cellFaces(c);
Face *f;
while ((f = cellFaces.next()) != 0)
    <do something with face f>

#include <stdlib.h>
double frand() {return (double)rand()/RAND_MAX;}
CellFaceIterator cellFaces(c);
Face *f;
while ((f = cellFaces.next()) != 0) {
    glColor3f(frand(), frand(), frand()};
    glBegin(GL_POLYGON);
    FaceEdgeIterator faceEdges(f);
    Edge *edge;
    while ((edge = faceEdges.next()) != 0)
	glVertex3dv(&edge->Org()->pos[0]);
    glEnd();
}

CellFaceIterator cellFaces(c);
Face *f;
while ((f = cellFaces.next()) != 0) {
    // visit each face of cell c
    FaceEdgeIterator faceEdges(f);
    Edge *edge;
    while ((edge = faceEdges.next()) != 0) {
	// visit each edge of face f
	// if edge passes the following, its Sym will not,
	// and vice-versa
	if (edge->Org() < edge->Dest())
	    <do something with edge>
    }
}

OBJ File I/O

To solve this, we can store a "splitme" bit for each edge in its data field (assuming data isn't being used for other purposes). Since data is a void *, it's necessary to cast when reading it. In our case we'll be storing an int in data.

Edge *split(Edge *e) {
    // split edge e, putting new vertex at midpoint

    // get Cell pointer from vertex (Edges don't have one)
    Cell *c = e->Org()->getCell();

    // split, creating new edge and vertex (sets topology only)
    Edge *enew = c->makeVertexEdge(e->Org(), e->Left(), e->Right());

    // At this point enew->Dest()==e->Org(),
    // and enew->Dest(), the new vertex, is between enew and e.
    // You might want to check the defn of makeVertexEdge to
    // convince yourself of this.

    // position new vertex at midpoint (note use of Vec3::operator+)
    enew->Dest()->pos = .5*(enew->Org()->pos + e->Dest()->pos);

    return enew;	// return new edge
}

void splitAll(Cell *c) {
    {
	// first, set the splitme bits of all original edges
	CellFaceIterator cellFaces(c);
	Face *f;
	while ((f = cellFaces.next()) != 0) {
	    // visit each face of cell c
	    FaceEdgeIterator faceEdges(f);
	    Edge *edge;
	    while ((edge = faceEdges.next()) != 0) {
		// visit each edge of face f
		int splitme = edge->Org() < edge->Dest();
		// splitme = 0 or 1
		// my Sym's bit will be the complement of mine
		edge->data = splitme;	// set bit
	    }
	}
    }
    {
	// go through again, splitting marked edges
	// need to construct a new iterator, hence the {}'s
	CellFaceIterator cellFaces(c);
	Face *f;

	while ((f = cellFaces.next()) != 0) {
	    // visit each face of cell c
	    FaceEdgeIterator faceEdges(f);
	    Edge *edge;
	    while ((edge = faceEdges.next()) != 0) {
		// visit each edge of face f
		// if its "splitme" bit set then split it
		if ((int)edge->data) {
		    Edge *enew = split(edge);

		    // clear splitme bits on two sub-edges and
		    // their Syms to avoid recursive splitting
		    edge->data = 0;
		    edge->Sym()->data = 0;
		    enew->data = 0;
		    enew->Sym()->data = 0;
		}
	    }
	}
    }
}

void main() {
    Cell *c;
    c = objReadCell("cube.obj");	// read cube.obj
    if (!c) exit(1);
    splitAll(c);			// split all edges
}