Graphics Reference
In-Depth Information
Require:
Initialize all vertex flags as
non-traversed
1:
while
non-traversed
vertex exists
do
2:
select any
non-traversed
vertex as
q
3:
set
q
flag as
traversed
4:
for
every
non-traversed
vertex
q
sharing edge with
qdo
5:
set
q
flag as
traversed
6:
align
q
to
q
7:
repeat recursively from step 4 for
q
:=
q
8:
end for
9:
end while
Algorithm 1.1.
Quaternion alignment algorithm for UV-mapped meshes.
1.5 Generic Transforms and Instancing
If we compare encoding transformations with quaternions and with matrices,
quaternions will have several advantages. First, a transformation matrix needs
4
3 values to encode position, rotation and scale, while with
SQTs
(scale-
quaternion-translation) we need only eight values provided we assume the scale
to be uniform. Second, reverse rotation comes virtually for free in the case of
quaternions, while for matrices this is a quite costly operation. Finally, multiply-
ing two 3
×
3 rotation matrices will result in 45 scalar operations (additions and
multiplications), while quaternions can be multiplied using a total of 28 scalar
operations.
Therefore, we used quaternions in our engine as widely as possible. However,
we have experienced several caveats with them.
The first one comes from the fact that a normalized quaternion
q
being mul-
tiplied by itself several times (i.e.,
q
n
) becomes significantly unnormalized. For
example, an incremental rotation of an object at a same angle may lead to this. A
straightforward solution to this is normalizing a quaternion multiplication prod-
uct, but this significantly reduces eciency, as normalization is usually a relatively
slow operation. An alternative solution will be keeping a normalization assertion
check for a debug version of an application and eliminating cases of all possible
multiplications of a quaternion on itself.
Another limitation for quaternions is nonuniform scale. In
Skyforge
we needed
a nonuniform scale for a family of effects classified as “channeling.” Figure 1.4
shows an example of a channeling effect. The particular feature of this family of
effects is that an effect is stretched between two arbitrary points in space. Hence,
a nonuniform scale is needed to be applied to them.
While a nonuniform scale may co-exist with quaternions, we have faced several
limitations, which should be taken into consideration at early production stages.
They come from the fact that we effectively decouple scale from rotation (in
contrast to conventional 3
×
×
3 scale-rotation matrices).
