Computer Graphics 2, 15-463
Paul Heckbert
Carnegie Mellon University
Revision 5: 18 Feb. 1999.
This document has the following sections:
All of these can be created by doing truncations (cutting off each vertex), stellations (building a prism on each face), or other simple operations on the Platonic solids ( some pictures ). It would be interesting to write code to generate such polyhedra, possibly even to animated transformations (3-D morphs) between them, but what data structure should we use for this?
First Try: list of polygons. The first, and simplest data structure we might think of is a simple list of polygons, each one storing (redundantly) all of its vertex coordinates. That is, in C++:
struct Vert {double x, y, z;}; // vertex position
Vert tri[NFACES][3]; // array of triangles, each with 3 vertices
Second Try: vertex and face lists. A better alternative would be to store the vertices separately, and make the faces be pointers to the vertices:
Vert vert[NVERTS]; // array of vertices
struct Tri {Vert *p, *q, *r;}; // triangular face holds 3 vertex pointers
Tri tri[NFACES]; // array of triangular faces
We can do better. To do so we'll need to store even more topological information, so that we can find the vertices/edges/faces immediately adjacent to a given vertex/edge/face in constant time.
In the quad-edge data structure, there are classes for vertices, edges, and faces, but edges play the leading role. The edges store complete topological information; all of the topological information stored by the faces and vertices is redundant with information in the edges. Figuratively speaking, the edges form the skeleton, and the vertices and faces are optional decorations, hanging off of the edges. Vertices hold most of the geometric (shape) information.
We now describe our implementation of quad-edge. We emphasize the high level public routines that you are encouraged to use. The full details are in the code in the cell directory.
The following member function returns a unique integer ID for each edge.
Using Lnext, we could loop around the edges of the face on the left of edge estart in ccw order:
void leftFromEdge(Edge *estart) {
Edge *e = estart;
do {
<do something with edge e>
e = e->Lnext();
} while (e!=estart);
}
The number of edges of a face (the face degree or valence) is 3 or greater for "real" polyhedra, but sometimes during construction of data structures, it is useful to have faces with 1 or 2 edges, which would correspond geometrically to loops or degenerate sliver polygons.
Similarly, the edges around the origin vertex of edge estart can be visited in ccw order like so:
void orgFromEdge(Edge *estart) {
Edge *e = estart;
do {
<do something with edge e>
e = e->Onext();
} while (e!=estart);
}
Since visiting the edges around a face (or edges around a vertex) is quite common, we have set up some iterator classes to simplify your code. Using the iterator, an alternative to leftFromEdge is:
void edgesOfFace(Face *face) {
// visit edges of face in ccw order; edges have face on the left
FaceEdgeIterator faceEdges(face);
Edge *edge;
while ((edge = faceEdges.next()) != 0)
<do something with edge e>
}
Using an iterator, the alternative to orgFromEdge is:
void edgesOfVertex(Vertex *vert) {
// visit edges of vertex in ccw order; edges have vert as origin
VertexEdgeIterator vertEdges(vert);
Edge *edge;
while ((edge = vertEdges.next()) != 0)
<do something with edge e>
}
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:
class Vertex {
Vec3 pos; // (x,y,z) position of this vertex
const void *data; // data pointer for this vertex
Edge *getEdge(); // an outgoing edge of this vertex
unsigned int getID(); // id# of this vertex (unique for this Cell)
};
There is a data pointer for each vertex, for extensibility.
You can store arbitary (4 byte) information there, or pointers to
additional memory (e.g. for colors, normals, or texture coordinates).
Face
Each face stores one piece of topological
information, a pointer to one of the ccw-oriented edges of the face,
plus optional attribute information (color, etc).
The public interface you should use is summarized below
(see
cell/face.hh
code).
class Face {
Edge *getEdge(); // a ccw-oriented edge of this face
const void *data; // data pointer for this vertex
unsigned int getID(); // id# of this face (unique for this Cell)
};
The data pointer here is just like that for vertices.
Given Cell *c, the calls do the following:
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:
Cell, and Euler Operators
A Cell is a single polyhedron, which includes sets of vertices,
edges, and faces.
The routines you will need most are the following four:
which are called Euler operators, since they maintain Euler's formula
V-E+F=2 interrelating
the number of vertices, edges, and faces of a polyhedron
of genus 0 (topologically equivalent to a sphere).
If the topology is a valid polyhedron before the call,
it will be valid after the call, as well.
Note that these routines update the topology, but they use the
default constructors for Vertex and Face, so
the positions of new vertices are (0,0,0) --
you'll have to set them yourself.
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);
};
It is possible to build up a quad-edge data structure without using
these routines, by using only the lower level routines, but it is
many times more difficult and error-prone, so we discourage it.
To loop over the faces of Cell *c:
CellVertexIterator cellVerts(c);
Vertex *v;
while ((v = cellVerts.next()) != 0)
<do something with vertex v>
Thus, to draw all the faces with OpenGL,
using random colors:
CellFaceIterator cellFaces(c);
Face *f;
while ((f = cellFaces.next()) != 0)
<do something with face f>
In the above, edge->Org() is the origin of
the current edge of the face, and the &...->pos[0] takes the
address of its x coordinate.
We could equally well use Dest.
Stepping through the (undirected) edges of a cell is more complex, as we have
things set up.
Note that there are twice as many directed edges as undirected edges.
The above code visits all directed edges once, so it visits each undirected
edge twice.
But for wireframe drawing and many other purposes
you would want to operate on each undirected edge just once.
A clever way to guarantee this,
without marking edges or
any additional arrays or lists, is to visit each undirected edge twice,
but use the fact that the pointers to the two vertices are addresses,
one of which is larger than the other:
#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();
}
One could create a "CellEdgeIterator" using this approach, I suppose.
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
So far we've seen how to modify polyhedra, but how would you create one
in the first place?
The easiest way is by reading a file.
We have code to read and write polyhedral models in Wavefront's OBJ file
format.
Full documentation on the format is available from a
3-D format collection,
and are here some complex
models in OBJ format.
The subset of the format that we read and write
consists of lines with the syntax
# commentwhere the ith v line defines vertex i, with i starting at 1. x, y, and z are floating point numbers. Each f line defines an n-sided face, where the vj are vertex indices. For example, the following defines a tetrahedron:
v x y z
f v1 v2 ... vn
where vertex 1 (v1) is at (-1,-1,-1) and face 1 has vertices v2, v3, v4. Faces are counterclockwise when viewed from the outside, by convention. OBJ files for Platonic solids are in the model directory. These are the recommended test objects for this assignment.v -1 -1 -1 v 1 1 -1 v -1 1 1 v 1 -1 1 f 2 3 4 f 1 4 3 f 1 3 2 f 1 2 4
To read an OBJ file, use the function
Cell *objReadCell(char *filename), and to write one,
call the function
objWriteCell(Cell *cell, char *filename).
The former returns NULL on error.
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.
Acknowledgments:
The quad-edge data structure was
first described in the excellent, but rather abstract article
[
Leonidas Guibas and Jorge Stolfi,
Primitives for the manipulation of general subdivisions
and the computation of Voronoi diagrams,
ACM Transactions on Graphics,
4(2),
1985,
75-123.
].
Andrew Bernard wrote this quad-edge library based on
previous code from
[
Dani Lischinski,
Incremental Delaunay Triangulation,
Graphics Gems IV,
Paul Heckbert, ed.,
Academic Press,
1994,
47-59.
PS for article ,
C++ code.
].
Michael Garland provided advice.
I wrote the OBJ-to-quad-edge converter.
Quad-edge is a variant of the earlier winged-edge data structure,
which was described in the excellent, highly readable article
[
Bruce G. Baumgart,
A polyhedron representation for computer vision,
Natl. Computer Conf. Proc.,
AFIPS, 1975,
589-596
].
Our quad-edge library is partially based on Pat Hanrahan's
winged-edge library from the New York Institute of Technology.
15-463, Computer Graphics 2
A Complete Quad-Edge Program
To put all the pieces together, we'll now show a program that reads in
a cube file and then splits each edge in two (the first step in the
construction of a cuboctahedron, perhaps).
You might think that this will be a trivial application of the
visit-all-edges code shown earlier, visiting each undirected edge once
and calling makeVertexEdge on one of its vertices to split the edge.
This would start to work, but note that the edge visiting algorithm
operates sequentially, so as new edges are added to the cell, they will
get traversed and split again!
This is a problem!
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
}
The Assignment
With all of that background on the quad-edge data structure,
the assignment is pretty easy to state.
Requirements
Write an interactive program for doing simple topological/geometric
operations on polyhedra, namely:
Tips
These are not requirements, but recommendations.
#include <assert.h>
assert(enew->Dest()==e->Org());
Extra Credit
Paul Heckbert