Managing Transformations in Hierarchy

• Introduction

One of the most fundamental aspects of 3D engine design is management of spatial relationship between objects. The most intuitive way of handling this issue is to organize objects in a tree structure (hierarchy), where each node stores its local transformation, relative to its parent.

The most common way to define the local transformation is to use a socalled TRS system, where the transformation is composed of translation, rotation, and scale. This system is very easy to use for both programmers using the engine as well as non-technical users like level designers. In this chapter we describe the theory behind such a system.

One problem with the system is decomposition of a matrix back to TRS. It turns out that this problem is often ill-defined and no robust solution exists. We present an approximate solution that works reasonably well in the majority of cases.

• Theory

树结构

Keeping objects in hierarchy is a well-known concept. Every object can have a number of children and only one parent.  It can also be convenient to store and manage a list of pointers to the children so that we have fast access to them. The aforementioned structure is in fact a tree.

节点结构

We assume that a node stores its translation, rotation, and scale (TRS) that are relative to its parent. Therefore, we say these properties are local. When we move an object, we drag all its children with it. If we increase scale of the object, then all of its children will become larger too.

例：

变换矩阵与RTS

对于单个节点的变换矩阵和RTS的关系

Local TRS uniquely defines a local transformation matrix M. We transform vector v in the following way:

where S is an arbitrary scale matrix, R is an arbitrary rotation matrix, T is a translation matrix, and T is the vector matrix T is made of.

系统层次结构的变换矩阵关系

To render an object, we need to obtain its global (world) transformation by composing local transformations of all the object’s ancestors up in the hierarchy.

The composition is achieved by simply multiplying local matrices. Given a vector v0, its local matrix M0, and the local matrix M1 of v0’s parent, we can find the global position v2:

Using vector notation for translation, we get

这里需要注意的就是

RS != S’R’

Skew Problem

问题描述：

Applying a nonuniform scale (coming from object A) that follows a local rotation (objects B and C) will cause objects (B and C) to be skewed. Skew can appear during matrices composition but it becomes a problem during the decomposition, as it cannot be expressed within a single TRS node. We give an approximate solution to this issue in Section 3.2.4.

解决方法：

Let an object have n ancestors in the hierarchy tree. Let M1,M2, · · · ,Mn be their local transformation matrices, M0 be a local transformation matrix of the considered object, and Mi = SiRiTi.

MTRSΣ = M0M1 · · ·Mn

MTR = R0T0R1T1 · · ·RnTn

TR可以很好的叠加来获得世界坐标的TR

MSΣ = MRSΣMR

here we have the skew and the scale combined. We use diagonal elements of MSΣ to get the scale, and we choose to ignore the rest that is responsible for the skew.

Scale 的话用这边算出来的对角线来表示，其他的结果丢弃采用上面的TR，这样的结果就可以避免skew.

父节点变化处理

In a 3D engine we often need to modify objects’ parent-children relationship.

we want to change the local transformation such that the global transformation is still the same. Obviously, that forces us to recompute local TRS values of the object whose parent we’re changing.

To get from the current local space to a new local space (parent changes, global transform stays the same), we first need to find the global transform of the object by going up in the hierarchy to the root node. Having done this we need to go down the hierarchy to which our new parent belongs.

LetM’0 be the new parent’s local transformation matrix. Let that new parent have n’ ancestors in the hierarchy tree with local transformations M’1,M’2, · · · ,M’n’, where M’i = S’iR’iT’i. The new local transformation matrix can thus be found using the following formula:

通过此公式就可以求出新的RTS

Alternative Systems

这边主要讲 Scale 处理，和skew相关

做法：除了叶节点存储x,y,z不相同的，各项异的scale值（三维向量）（nonuniform scale in last node），其他节点存储的是uniform scale值（不是三维向量，是值）这样可以有效的解决skew问题且实现简单。

• Implementation

节点结构：

Reducing Texture Memory Usage by 2-channel Color Encoding

原理：

简单地说就是贴图一般所使用到的色域都很小，因此可以利用这个特征来减少表示texture的数据量。

These single-material textures often do not exhibit large color variety and contain a limited range of hues, while using a full range of brightness resulting from highlights and dark (e.g., shadowed), regions within the material surface.

基本做法就是传输亮度和饱和度

The method presented here follows these observations and aims to encode any given texture into two channels: one channel preserving full luminance information and the other one dedicated to hue/saturation encoding.

Texture Encoding Algorithm

编码就是三维映射到二维的过程，就是找出一个平面，使得所有的三维顶点到该平面的距离最小来保证误差最小。

Approximating this space with two channels effectively means that we have to find a surface (two-dimensional manifold) embedded within this unit cube that lies as close as possible to the set of texels from the source texture.

步骤：

1. 重估颜色空间

sRGB颜色值转到线性颜色空间。

RGB值对亮度的贡献的非线性和不同的，因此我们要赋予RGB不同的权重。

上面两步得到新的可以线性运算的三维空间坐标

然后在此基础上去计算平面。

点到平面距离：

所有点到平面距离的平方和

通过如下计算方法计算得到。参考 estimate_image 函数和书本。

2. 算出两个base的颜色向量

这里很简单如图：已知道 bc1（0,1,m）bc2（1,0,n）初始化以后利用平面的信息求的。见函数

find_components() 求解。

3. 亮度编码

公式：

4. 饱和度编码

四步走：首先获得三维点在平面的投影，然后就有(0,0,0)到该投影点的向量，另外还可以计算得到两个base颜色向量，让这个投影向量用两个基本颜色向量表示。最终再通过公式求的饱和度值。

Decoding Algorithm

这个很简单，就是也需要两个base颜色值和亮度混合参数，然后反解得到。

• 实现：

vec3 estimate_image(BITMAP *src) ：

整个拆成 rr, gg, bb, rg, rb, gb 六个分量。首先计算整个image的六个分量的均值。

然后暴力法遍历预设好的法线取值范围（例 n.xyz 在 0 到 100）

求出误差公示最小的法线值。

void stamp_color_probe(BITMAP *bmp)：

这个是图片颜色预处理

编码：

BITMAP *encode_image(BITMAP *src,vec3 n)：

平面法线normalize，并找出两个基本的颜色。

然后通过这两个基本颜色构建2d位置坐标系和对应的颜色坐标系。

接着创建输出bitmap，然后对于每一个输出mipmap的像素点：

获得RGB值

应用 gamma 2.0

计算 2D 坐标系下面的坐标位置和颜色

构建饱和度 float hue = -da/(db-da+0.00000001f);（da, db是2d坐标下的颜色值）

构建亮度  float lum = sqrt(c.dot(to_scale))

编码成 hue, lum 两个分量。

解码

BITMAP *decode_image(BITMAP *src,const vec3 &base_a,const vec3 &base_b)：

初始化目标Bitmap对于它的每一个像素点

首先获得传过来的 hue, lum

解码颜色 vec3 c = base_a + (base_b-base_a)*hue;

解码亮度 float clum = 0.2126f*c.x + 0.7152f*c.y + 0.0722f*c.z;

应用 gamma 2.0 回到 sRGB 值