-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathblog_decomposition_intro.html
71 lines (52 loc) · 6.4 KB
/
blog_decomposition_intro.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Gabor Makes Games</title>
<meta name="author" content="Gabor Szauer">
<link rel="stylesheet" type="text/css" href="css/shared.css"><link rel="stylesheet" type="text/css" href="css/navigation.css"><link rel="stylesheet" type="text/css" href="css/font-raleway.css"><link rel="stylesheet" type="text/css" href="css/font-oxygen.css"><link rel="stylesheet" type="text/css" href="css/font-worksans.css"><link rel="stylesheet" type="text/css" href="css/codepretty/skins/desert.css"><script type="text/javascript" src="js/codepretty/prettify.js"></script><script type="text/javascript" src="js/navigation.js"></script><!-- Global site tag (gtag.js) - Google Analytics --><script async src="https://www.googletagmanager.com/gtag/js?id=UA-96941899-3"></script><script>window.dataLayer = window.dataLayer || [];function gtag(){dataLayer.push(arguments);}gtag('js', new Date());gtag('config', 'UA-96941899-3');</script> <link rel="stylesheet" type="text/css" href="css/blog.css">
</head>
<body onload="MainNavOnLoad();PR.prettyPrint();"> <div class="nav"> <ul class="menu"> <li class="logo"><a href="https://gabormakesgames.com">Gabor Makes Games</a></li> <li class="item"><a id="main-nav-active" href="blog.html">Blog</a></li> <li class="item"><a href="books.html">Books</a></li> <li class="item"><a href="https://github.com/gszauer/">Github</a></li> <li class="item"><a href="https://twitter.com/gszauer">@gszauer</a></li> <li class="toggle"><a href="#">Open Menu</a></li> </ul></div>
<div id="blog">
<div id="sidebar"><a class="sidebar-item sidebar-first sidebar-gap" href="blog.html">Back to blog</a></li><a class="sidebar-item sidebar-first sidebar-active " href="blog_decomposition_intro.html">Matrix Decomposition</a><a class="sidebar-item" href="blog_decomposition_code.html">Shoemake's Code</a><a class="sidebar-item" href="blog_decomposition_math.html">The Math</a><a class="sidebar-item" href="blog_decomposition_translation.html">Factoring Translation</a><a class="sidebar-item" href="blog_decomposition_polar.html">Polar Decomposition</a><a class="sidebar-item" href="blog_decomposition_qr.html">QR Decomposition</a><a class="sidebar-item" href="blog_decomposition_spect.html">Spectral Decomposition</a><a class="sidebar-item" href="blog_decomposition_adjust.html">Spectral Adjustment</a><a class="sidebar-item" href="blog_decomposition_affine.html">Affine Decomposition</a><a class="sidebar-item" href="blog_decomposition_summary.html">Summary</a></div>
<div id="content">
<h1>Matrix Decomposition</h1>
<p>In my <a href="blog_transforms.html">last blog</a> we discussed transformation hierarchies. A transform having a non uniformly scaled parent lead to some strage side effects. Nameley, rotating such a transform would cause it to skew instead of rotating.</p>
<p>The only way to fix this non uniform scale issue is trough matrix decompositon. The idea is that you take the final matrix with the skewing problem and decompose it into position, rotation, scale and skew components. Once you have all these components, ignore the skew and create a new matrix using only positon, rotation and scale.</p>
<p>This type of decomposition is explained in detail in Shoemake and Duff's <a href="http://research.cs.wisc.edu/graphics/Courses/838-s2002/Papers/polar-decomp.pdf">Matrix Animation and Polar Decomposition</a> paper, as well as Shoemake's chapter on <i>Polar Matrix Decomposition</i> in <a href="https://www.amazon.com/Graphics-Gems-IV-IBM-Version/dp/0123361559">Graphics Gems IV</a>.</p>
<p>This blog post attempts to re-implementation shoemakes method, with code & math that's hopefully easier to read and understand. Shoemakes code for affine decomposition is <a href="https://github.com/erich666/GraphicsGems/tree/master/gemsiv/polar_decomp">on github</a>. Looking at the code, the part of the interface that is interesting for us is this:</p>
<pre class="prettyprint linenums">typedef struct {
HVect t; /* Translation components */
Quat q; /* Essential rotation */
Quat u; /* Stretch rotation */
HVect k; /* Stretch factors */
float f; /* Sign of determinant */
} AffineParts;
void decomp_affine(HMatrix A, AffineParts *parts);</pre>
<p>We can call <code>decomp_affine</code> to find the translation (<code>t</code>), rotation (<code>q</code>) and scale (<code>k</code>) of the transform without shearing. These values can be used to build a new <code>Transform</code> that can then be converted to a <code>Matrix</code>. The code below uses the provided <code>decomp_affine</code> function to do build a correct transform:</p>
<pre class="prettyprint linenums">Matrix GetWorldMatrix(Transform transform) {
Matrix localMatrix = ToMatrix(transform);
Matrix worldMatrix = localMatrix;
if (transform.parent != NULL) {
Matrix parentMatrix = GetWorldMatrix(transform.parent);
worldMatrix = localMatrix * parentMatrix;
if (ContainsNonUniformScale(transform.parent)) {
AffineParts decomp = decomp_affine(worldMatrix, &decomp);
Transform temp;
temp.parent = NULL;
temp.position = decomp.t;
temp.scale = decomp.k;
temp.rotation = decomp.q;
worldMatrix = ToMatrix(temp);
}
}
return worldMatrix;
}</pre>
<p>Using the above code, we can fix the skew artifact, making orientations work as expected:</p>
<img src="images/blog_decompose_compare.gif" alt="Unity compare decomposition" />
<p>If the shearing issue is solved by an affine matrix decomposition, why isn't this technique standard in game engines? To put it simply, polar decomposition is an expensive operation, even if only performed on a few transforms. The technique is much better suited for offline tools.</p>
<!--p class="callout">Shoemake's code for matrix decompositon can be found in many places including <a href="https://github.com/aws/lumberyard/blob/394ca7ee1c2b94d8bd85516436136436bb6ae0e5/dev/Code/Tools/CryCommonTools/Decompose.h">comercial engines</a>, even if only as a part of the editor. Affine decomposition is too expensive to be a part of the runtime.</p-->
</div>
</div>
</body>
</html>