Graphics Reference
In-Depth Information
Inline Exercise 10.22: Explain where each of the matrices for the minute hand
arose.
Notice how much of this matrix multiplication is shared. We could have com-
puted the product for the circle and reused it in each of the others, for instance.
For a large scene graph, the overlap is often much greater. If there are 70 transfor-
mations applied to an object with only five or six vertices, the cost of multiplying
matrices together far outweighs the cost of multiplying the composite matrix by
the vertex coordinate array.
We can avoid duplicated work by revising our strawman algorithm. We per-
form a depth-first traversal of the scene graph, maintaining a stack of matrices as
we do so. Each time we encounter a new transformation with matrix M ,wemul-
tiply M by the current transformation matrix C (the one at the top of the stack)
and push the result, MC , onto the stack. Each time our traversal rises up through a
transformation node, we pop a matrix from the stack. The result is that whenever
we encounter geometry (like the coordinates of the hand points, or of the ellipse
points), we can multiply the coordinate array on the left by the current transfor-
mation to get the WPF coordinates of those points. In the pseudocode below, we
assume that the scene graph is represented by a Scene class with a method that
returns the root node of the graph, and that a transformation node has a matrix
method that returns the matrix for the associated transformation, while a geometry
node has a vertexCoordinateArray method that returns a 3
×
k array containing
the homogeneous coordinates of the k points in the polygon.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void drawScene(Scene myScene)
s= empty Stack
s.push( 3 × 3 identity matrix )
explore(myScene.rootNode(), s)
void explore(Node n, Stack& s)
if n is a transformation node
push n.matrix() * s.top() onto s
else if n is a geometry node
drawPolygon(s.top() * n.vertexCoordinateArray())
foreach child k of n
explore(k, s)
if n is a transformation node
pop top element from s
In some complex models, the cost of matrix multiplications can be enormous.
If the same model is to be rendered over and over, and none of the transformations
change (e.g., a model of a building in a driving-simulation game), it's often worth
it to use the algorithm above to create a list of polygons in world coordinates that
can be redrawn for each frame, rather than reparsing the scene once per frame.
This is sometimes referred to as prebaking or baking a model.
The algorithm above is the core of the standard one used for scene traversals
in scene graphs. There are two important additions, however.
First, geometric transformations are not the only things stored in a scene
graph—in some cases, attributes like color may be stored as well. In a simple
 
 
Search WWH ::




Custom Search