Advanced Graphics,
Dr Neil Dodgson,
University of Cambridge
Computer Laboratory
Part II course, 2002 and 2003
Part 1: Basic 3D Modelling
A: Ray tracing vs polygon scan conversion
B: Polygon mesh management & hardware PSC quirks
on to part 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
normal. The direction of the normal tells you 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 normal vector 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.
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. With regard to surface properties, 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.
In general, we will want a polygon mesh to form a manifold
surface. This is where the neighbourhood of every point is
topologically equivalent to a disc (except at the edges of the
manifold, where it is topologically equivalent to a half disc). The
principal upshot of this is that each edge in the polygon mesh can be
the edge of either one or two polygons, no more and no less. The
trade-off is between ease of extracting information and ease of
updating the data structure.
Hardware PSC quirks
A piece of PSC hardware, such as the Silicon Graphics Reality Engine or the
NVIDIA GeForce family of graphics
cards, 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. Modern graphics cards
allow for user programming in both the geometry and rendering
engine. Machine instructions are provided for the usual operations
(addition, multiplication), and also for such necessary things as
taking the dot product of two vectors. In both geometry and rendering
engine the user is extremely limited in the number of instructions
(currently about 128 maximum in the program), the number of available
working registers (about 12), and the fact that there is no mechanism
for jumps or loops, nor for general memory access. On recent NVIDIA
cards, the information which is passed to the geometry engine, for a
single vertex, is position, weight, normal, primary and secondary
colour, fog coordinate, and eight texture coordinates; all sixteen of
these are floating-point four-component vectors. The output from the
geometry engine is homogeneous clip space position, primary and
secondary colours for front and back faces of the polygon, fog
coordinate, point size, and texture coordinate set; where they are all
again floating-point four-component vectors except for the output fog
coordinate and the point size. You are not expected to remember all of
these input and output registers, but they give you an idea of the
complexity of the processing which can go on inside a graphics card.
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.
The vertex cache
The triangle strip and fan sets work because there is a vertex cache
which can hold all the relevant data about two vertices. More recent
graphics cards have a vertex cache which can hold the twenty most
recently used vertices, hence obviating the need to be explicitly
specify fan sets and strip sets, although you still need to send the
triangles to the card in some reasonably coherent order.
Exercises
- Calculate both surface normal vectors (left-handed and
right-handed) for a triangle with points (1, 1, 0), (2, 0, 1), (-1,
-2, -1).
- Confirm that the following statements provide a good definition of a
reasonable polygon mesh:
- A vertex belongs to at least
two edges.
- A vertex is a vertex of at least one polygon.
- An
edge has exactly two end points.
- An edge is an edge of either one
or two polygons.
- A polygon has at least three vertices.
- A
polygon has at least three edges.
- 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).
- [2002/7/9] Describe the situations in which it is sensible to use a winged-edged data
structure to represent a polygon mesh and, conversely, the situations in which a
winged-edged data structure is not a sensible option for representing a polygon
mesh. What is the minimum information which is required to successfully draw
a polygon mesh using Gouraud shading? [4 marks]
|
Part 1: Basic 3D Modelling
A: Ray tracing vs polygon scan conversion
B: Polygon mesh management & hardware PSC quirks
on to part 2...
Neil Dodgson |
Advanced Graphics |
Computer Laboratory
Source file: p1b.html
Page last updated on Mon Oct 14 11:52:45 BST 2002
by Neil Dodgson (nad@cl.cam.ac.uk)
Advanced Graphics Study Guide