Advanced Graphics

Dr Neil Dodgson, University of Cambridge Computer Laboratory
Part II course, 1998


Lecture 1 Index
Part A: Ray tracing vs polygon scan conversion
Part B: Polygon mesh management & hardware PSC quirks
Part C: Ray tracing primitives
on to lecture 2...

1B) Polygon mesh management

Relevant mainly to PSC and LD.

Drawing polygons

In order to draw a polygon, you obviously need to know its vertices. To get the shading correct you also need to know its orientation: which side is the front of the polygon and which is the back. Many systems assume one-sided polygons: the front side is shaded and the back side either is coloured matt grey or black or is not even considered. This is sensible if the polygon is part of a closed polyhedron. In many applications, all objects consist of closed polyhedra; but you cannot guarantee that this will always be the case, which means that you will get unexpected results when the back sides of polygons are actually visible on screen.

The orientation of a polygon is specified by its normal vector. This does not need to be specified independently of the polygon's vertices because it can be calculated from the vertices. As an example: assume a polygon has three vertices, A, B and C. The normal vector can be calculated as: n = (C-B) x (A-B).

Any three adjacent vertices in a polygon can be used to calculate the normal vector but the order in which the vertices are specified is important: it changes whether the vector points up or down relative to the polygon. In a right-handed co-ordinate system the three vertices must be specified anti-clockwise round the polygon as you look down the desired normal vector (i.e. as you look at the front side of the polygon). Note that, if there are more than three vertices in the polygon, they must all lie in the same plane, otherwise the shape will not be a polygon!

Thus, for drawing purposes, we need to know only the vertices and surface properties of the polygon. The vertices naturally give us both edge and orientation information. The surface properties are such things as the specular and diffuse colours, and details of any texture mapping which may be applied to the polygon.

Interaction with polygon mesh data

The above is fine for drawing but, if you wish to manipulate the polygon mesh (for example, in a 3D modelling package), then is is useful to know quite a lot more about the connectivity of the mesh. For example: if you want to move a vertex, which is shared by four polygons, you do not want to have to search through all the polygons in your data structure trying to find the ones which contain a vertex which matches your vertex data.

The winged-edge data structure is particularly useful for handling polygon mesh data. It contains explicit links for all of the relationships between vertices, edges and polygons, thus making it easy to find, for example, which polygons are attached to a given vertex, or which polygons are adjacent to a given polygon (by traversing the edge list for the given polygon, and finding which polygon lies on the other side of each edge).

The vertex object contains the vertex's co-ordinates, a pointer to a list of all edges of which this vertex is an end-point, and a pointer to a list of all polygons of which the vertex is a vertex.

The polygon object contains (a pointer to) the polygon's surface property information, a pointer to a list of all edges which bound this polygon, and a pointer to an ordered list of all vertices of the polygon.

The edge object contains pointers to its start and end vertices, and pointers to the polygons which lie to the left and right of it.

<Image: diagram showing
the winged edge data structure as presented in the lecture>

The above diagram shows just one possible implementation of a polygon mesh data structure. FvDFH section 12.5.2 describes another winged-edge data structure which contains slightly less information, and therefore requires more accesses to find certain pieces of information than the one shown above. The implementation that would be chosen depends on the needs of the particular application which is using the data structure. Another alternative would be to attach shading information to vertices rather than to polygons. This could then be used to Gouraud shade or Phong shade the polygons.

F&vD section 13.2 also contains a bit of information on polygon meshes.

Hardware PSC quirks

A piece of PSC hardware, such as the Silicon Graphics Reality Engine, will generally consist of a geometry engine and a rendering engine. The geometry engine will handle the transformations of all vertices and normals (and possibly handle some of the shading calculations). The rendering engine will implement the PSC algorithm on the transformed data.

Triangles only

When making a piece of hardware to render a polygon, it is much easier to make the hardware handle a fixed number of vertices per polygon, than a variable number. Many hardware implementations thus simply implement triangle drawing. This is not a serious drawback. Polygons with more vertices are simply split into triangles.

The triangle strip set and triangle fan set

In addition to simple triangle drawing, Silicon Graphics machines implement both the triangle strip set and triangle fan set to speed up processing through the geometry engine. Each triangle in the set has two vertices in common with the previous triangle. Each vertex is transformed only once by the geometry engine, giving a factor of three speed up in geometry processing.

For example, assume we have triangles ABC, BCD, CDE and DEF. In standard triangle rendering, the vertices would be sent to the geometry engine in the order ABC BCD CDE DEF; each triangle's vertices being sent separately. With a triangle strip set the vertices are sent as ABCDEF; the adjacent triangles' vertices overlapping.

A triangle fan set is similar. In the four triangle case we would have triangles ABC, ACD, ADE and AEF. The vertices would again be sent just as ABCDEF. It is obviously important that the rastering engine be told whether it is drawing standard triangles or a triangle strip set or a triangle fan set.

Exercises
  1. When would you choose left-handedness or right-handedness for your PSC system?
  2. Calculate both surface normal vectors (left-handed and right-handed) for a triangle with points (1, 1, 0), (2, 0, 1), (-1, -2, -1).
  3. Confirm that the following statements are correct for a reasonable polygon mesh:
    1. A vertex belongs to at least two edges.
    2. A vertex is a vertex of at least one polygon.
    3. An edge has exactly two end points.
    4. An edge is an edge of either one or two polygons.
    5. A polygon has at least three vertices.
    6. A polygon has at least three edges.
  4. Work out the algorithm that is required to modify a winged-edge data structure when an edge is split. You may ignore surface property information for the polygons and you may assume that the edge that is split is split exactly in half. The algorithm could by called by the function call:
    split_edge( vertex_list v, edge_list e, polygon_list p, edge edge_to_split)
    where the winged-edge data structure is made up of the three linked lists of objects (vertices, edges, and polygons).


Lecture 1 Index
Part A: Ray tracing vs polygon scan conversion
Part B: Polygon mesh management & hardware PSC quirks
Part C: Ray tracing primitives
on to lecture 2...


Neil Dodgson | Advanced Graphics | Computer Laboratory

Source file: l1b.html
Page last updated on Tue Sep 8 16:01:39 BST 1998
by Neil Dodgson (nad@cl.cam.ac.uk)