Computer Graphics 2, 15-463
Paul Heckbert
Carnegie Mellon University
Revision 1: 14 Feb. 2001.
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. It would be interesting to write code to generate such polyhedra, possibly even to animate 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++:
With this data structure, the vertices of face f would be at the xyz points tri[f][i] for i=0,1,2. The above scheme is for triangulated models, where each face (polygon) has three sides, but it could obviously be generalized for models with n-sided faces. With this data structure, it would be very clumsy to try to do an operation like vertex truncation, where you need to find all the vertices adjacent (connected by an edge) to a given vertex. To do that you'd need to search through the face list for other vertices with equal coordinates -- inefficient, and inelegant.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:
Again, this is the code for triangular faces only. This second method reduces redundancy, but finding the vertices adjacent to a given vertex would still be costly (O(NFACES)), as you'd have to search the entire face list. The above two data structures record the geometric information (vertex positions) just fine, but they are lacking in topological information that records connectedness (adjacencies) between vertices, edges, and faces. The first data structure stored no topological information, the second stored only pointers from faces to vertices.Vert vert[NVERTS]; // array of vertices struct Tri {Vert *p, *q, *r;}; // triangle 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:
Note that we need "do ... while" as opposed to "for" or "while" because (a) we don't know beforehand how many edges the face has (quad-edge is not limited to triangulated surfaces), (b) following the Lnext's yields a cycle, and (c) we want to visit each edge exactly once. If Lprev were used instead of Lnext we'd visit the left face's edges in cw 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:
The degree of a vertex is 3 or greater for "real" polyhedra, but as with faces, during construction we sometimes build vertices of degree 1 or 2.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:
Note that this functions a bit differently from leftFromEdge; its input is a face pointer, not an edge pointer, so you don't have control over which of the face's edges will get visited first, but that usually doesn't matter, anyway. Once an iterator has gone through its list, it is "spent". If you want to go through the list again, you must construct a new iterator.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:
Here, Vec3 is essentially an array of three doubles, but with many additional operators and functions that will come in quite handy. The Vec3 class comes from the Simple Vector Library (SVL) of former CMU grad student Andrew Willmott. Take the time to skim his documentation; it will pay off.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).
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.
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); };
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:
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:
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> } }
# 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 v_{j} are vertex indices. For example, the following defines a tetrahedron:
v x y z
f v_{1} v_{2} ... v_{n}
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.
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 }
15-463, Computer Graphics 2
Paul Heckbert