2013-10-22-FloodFill.md

FloodFill simple implementation
----

Oct. 22, 2013 看见someone提到Flood fill algorithm, 惭愧，不熟悉这个名字，于是Google一下，竟然跟BFS很像，于是想着要简单实现一下。一直拖，拖到了昨晚, Sunday, Nov. 4, 才弄出个结果。

下面这图是在Windows > Paint软件中画的，一个奇怪的形状，假如用Paint软件中的fill工具可以把这个奇怪的形状填满某一种颜色。那假如手工实现，怎么搞呢?

下面是结果，分别是填了10000次，20000次...的结果。

 

 

从程序的结果来看，在一定次数之后就填满了整个奇怪的形状。如上面的结果中，从10000次到20000次扩展的区域是否跟从20000到30000次拓展的区域一样大呢，跟什么有关？(After some steps, the shape will be filled. From the result images aboved, the extended red region added during from 10000 to 20000 is the same as the region added during from 20000 to 30000? what is the reason behind that.)

New functions learned:
std::stoi, std::to_string functions.

Source code: https://github.com/renc/FloodFill 

weekly update - one list for two item types

这一周都在为之前的设计错误埋单。一个(two dimension) double linked list在当前代码中被广泛使用，其中的ListNode被当作是一种类A了，现在新需求是加入另一种新的种类B，但是要求是用户看到的A跟B是可以混排的，例如A->A->B->A->B->B->A-....。之前为了不影响已有的code，不改当前的list，而重新加入一个新的list，维护那些B，两天时间尝试给这新的ListB来添加维护ListNodeB的功能，例如add / remove/ insert / move等。当作到undo的时候，不行，ListB的操作需要考虑list中前后nodes类型，上下文，A还是B呢？太烦。
于是转肽，把旧的ListNode扩展为默认是typeA, 额外要求的话可以是typeB，于是A and B这两种类型的东西可以mix到一个list里面，因为A and B are objects of the same ListNode。但旧代码对这个list的操作，例如traverse the list to visit every ListNode, 都是把ListNode做为A的，现在要添加判断了：假如是A，照旧，假如是B，新的做法。等于做surgery，但是觉得应该坚持觉得对的而不是避开繁琐的。

这是最简单实例 (one dimention double linked list):
struct ListNode {
  ListNode *m_pPrve, m_pNext;
  bool m_bTypeA; // default is true;
  ...
};
class List {
  ListNode m_pHead;
}; 

this post is written in email, and send to blogger with a secret mail address. 

: hi blogger, do u see me? 

file: 2013-08-14_maya_blendshape.md
title: maya blendshape
date:
////////////////////////////////////////////////////////////

最近接触了一点maya blendshape api programming, 稍微记录一下。

先说明一个特点，当drag一个cube or sphere物体的时候，会生成两个nodes, 具体的细节请看maya scene graph，DAG。

To create a simple blendshape example,
Polygon mode, create a cube, we have ;   
Select cube1, Shift+D, we have , move cube2 a little bit away from cube1.  
Select cube1, Shift+D, we have , move cube3 a little bit away from cube1.  
Select cube3 first, then shift+select cube2, then shift+select cube1,
Animatioin mode, menu Create Deformer > BlendShape, we have a blendshape deformer node, for example called blendShape1.
cube1 is called source shape for this blenshape.
cube2 and cube3 are as target shapes for this blendshape.

select cube1, menu Windows > Connections, we see the connections of these nodes.

**Maya/Fbx API Table.**

source	blendshape	channel	target
MObject	MFnBlendShapeDeformer	Target Weight slider	MObject
FbxGeometry	FbxBlendShape	FbxBlendShapeChannel	FbxShape

有关target weight slider的注意事项:

+ 一个blendshape可以有多个target weight slider, 每一个slider中可以是一个or多个target shapes, 取决于In-Between off/on.

+ 每一个target weight slider 有一个数值叫target weight (value) 表示target shapes对source的effect.

+ 每一个target weight slider 有一个名字target weight or target weight slider name or name of target weight. 这个name是用transform node的名字，例如上述例子的两个target weights的名字分别是pCube2 and pCube3. tricky的是这个名字可以被改掉, 改成whatever u like, 例如这里改成pCube2x. 于是在code里面就有个问题了，给出一个target weight name, how to find out the target shape (or the transform node of the target shape) associated with this target weight name?

一些调试的MEL commands:
```                
objExists pCube2  
objExists |pCube2
objExists pCube2|pCubeShape2
objExists pCubeShape2
objExists |pCubeShape2

objExists blendShape1.pCube2x;  
// Results: 1 //  
 
blendShape -q -g blendShape1;
// Result: pCubeShape1 //  the source shape's name, not transform node's name.
blendShape -q -target blendShape1;  
// Result: pCube2 pCube3 // the target shape ‘s transform node’s name.
blendShape -q -t blendShape1;
// Result: pCube2 pCube3 // the flag -target is the same as -t
blendShape –q –weightCount blendShape1;  
// Result: 2 //            这里返回的数字应该就是刚好上面targets数目
       blendShape -q -w blendShape1;
// Result: 0.5 0 //  每一个target weight's value.

listAttr -sn blendShape1.weight[0];  
// Result: pCube2x //  
listAttr -m blendShape1.w;
// Result: pCube2x pCube3 // names of target weight, not the name of target shape or transform node.

aliasAttr -q blendShape1;  
// Result: pCube2x weight[0] pCube3 weight[1] // 对应关系
aliasAttr -q blendShape1.pCube2x;  
// Result: pCube2x //  
aliasAttr smile blendShape1.weight[0];
aliasAttr smile blendShape1.w[0]; // weight[0] == w[0]
// Result: 1 //  把weight[0]改名为smile, 而不是上面的pCube2x了.

setAttr blendShape1.pCube2x 0.5;  //成功, 调target weight slider的value.  
setAttr "blendShape1.pCube2x" 0.8; //成功, 调target weight slider的value.  
setAttr blendShape1.smile 0.6; // Succeed,
setAttr blendShape1.w[0] 0.7;  // Succeed, w[0] == weight[0] has been renamed as smile.

```  
在Script Editor中输入 help 会返回help information.  而且在C++ source里面也可以用这些mel commands, 以objExists为例:
```
MString command = "objExists pCube1";
int result = 0; // false;
MStatus status = MGlobal::executeCommand(command, result);
```  

updated about getting the target shapes from the blendshape deformer node.

updated 2013/10/11. blendShape是线性操作，deformed result = source * (1 - target_weight) + target * target_weight;
source and target可以说shape mesh, 也可以是别的blendshape deformation node的结果。

udated 2013/10/12. 遇到一个使用objExists mel command的bug. 假如Face + FaceShape是面部的transform + shape nodes, 它在DAG中的path是:
|man|head_group|Face|FaceShape
那么在Script Editor里面执行:
objExists |Face
的结果是什么呢? false, 找不到|Face ? 场景中不是明明有Face这个node的吗? 试试执行:
objExists Face
结果是true。 原来不是找不到Face, 而是找不到|Face. 两者有什么区别? |Face表示这个face node是直接在root下面. 所以我觉得用objExists命令还是别加|为好. 在maya scene graph的资料中有提到|.


MFnBlendShapeDeformer::addTarget(base shape, channel/target weight index, target shape, weight value);
可否多次add相同的targets呢？还是每次add target之前先判断假如已经有得话就先removeTarget呢?


Target weight上的connection (MPlug的应用)
----
来一个简单的例子。建一个blendShape1(cube1 as source, cube2 and cube3 as target shapes, rename the weight to be weight1 and weight2)。
blendshape1.weight1 是一个plug的名字，其实这个weight1也同时是对应target slider的名字。上面提到可以用listAttr and aliasAttr来找有什么plugs和改它们的名字. 下面来看怎么获得obtain这些sliders/weights:
```
// mel commands
blendShape -q -wc blendShapeName; // return the weight count;
listAttr -m blendShapeName.w; // return all the names of weights.
aliasAttr -q blendShapeName; // return all the weights' names and associated weight[i]

// c++ code
unsigned int iWeightCount = MFnBlendShapeDeformer::numWeights();
MFnBlendShapeDeformer::weightIndexList( MIntArray &indexList );
assert( iWeightCount == indexList.length() );

MPlug plugs = blendShapeNode.findPlug("weight", &status);
assert( iWeightCount == plugs.numElements() ); // one weight <-> one "weight" plug

for (unsigned int i = 0; i < iWeightCount; ++i)
{
MPlug weightPlug = plugs[i]; // we can get the slider/weight name.

// indexList[] is only a small set of the indices of a very large weight array[],
// some items of the big weight array[] are not used, some items are
// deleted and invalid if some targets are removed from weight.
const int iWeightIndexOfWeightArray = indexList[i];
// this iWeightIndexOfWeightArray can be used to get the weight value and targets.
...

// btw, one weightPlug / slider / weight <--> one FbxBlendShapeChannel
// the target shapes of this channel become some objects of FbxShape.
}

```

一般情况下我们是通过拖动这slider来调blendshape的效果。对应的mel and c++ code:
```
setAttr "blendshape1.weight1" 0.5

weightPlug.setDouble( 0.5 ); // MPlug weightPlug; weightPlug.name() == "blendshape1.wieght1";
```

也可以把别的值connect到这个target weight上来, 例如通过动画animation或者locator等控制target weight的值的变化。每一个connection是由source plug and destination plug组成的. 在上面的blendShape1例子上增加一点:
建一个plane1, 打开Window > Node Editor 把plane1的translateX连到blendShape1.weight1, 把plane1的translateY连到blendShape1.weight2, UI上这两个sliders都变成黄色了, DG窗口中blendShape1这个node的形状也从长方形变成的菱形.
上面的过程其实我们建立了两个connections. 其中一个connection是 (pPlane1.translateX, blendshape1.weight1)，其中pPlane1.translateX称为source plug, blendShape1.weight1称为destination plug.
下面的代码显示怎么获得一个blendShape的plug, 以及这些plug的连接connections:
```
// given MFnDependencyNode blendShapeNode, and MStatus status;
MPlug plugs = blendShapeNode.findPlug("weight", &status);
for (unsigned int i = 0; i < plugs.numElements(); ++i)
{
MPlug weightPlug = plugs[i]; // as destination plug for connection.
MPlugArray inPlug; // as source plug for connection.
weightPlug.connectedTo(inPlug, true, false);
for (unsigned int i = 0; i < inPlug.length(); ++i)
MGlobal::displayInfo(inPlug[i].name() + " + " + weightPlug.name()); // for debug.
}

// mel command below:
listAttr -m blendShape1.w;
// for example returns weight1 weight2 ...
connectionInfo -sourceFromDestination blendShape1.weight1;
// for example returns pPlane1.translateX, the source of the connection (string, empty if null).
connectionInfo -destinationFromSource pPlane1.translateX;
// for example returns blendShape1.weight1

```

假如这个target weight对应的模型target shape被removeTarget了, 那些connection还在吗？不在了，可能是副作用side effect。 假如重新把模型addTarget回blendShape1，还想重新把那些断开的connection重新连上呢，否则之前key的动画等都失效了/
```
// target shape is removed from this blendshape for some reason.
// target shape is re-added into the blendshape. we want to
// restore those connections before. how to do this?
MString commandString = "connectAttr " + inPlug[i].name() + " " + weightPlug.name();
MGlobal::executeCommand(commandString, true); // true: display the result.
```
上面的代码中我用了connectAttr这个mel command, 貌似MDGModifier::connect(,)也有相似的功能，但网上查阅时候这个东西一般是放到某个custom command class里面用的，而且还要自定义undo/redo的函数，我还没试过。相比而言，直接用mel就没有这些担心。本来UI上的操作给我的感觉就是用相应的参数来调用底下的mel commands (Script Editors往往显示这些命令历史), mel command再底下当然可能是用C++ 函数XX在实现的。
UI operation -> mel command -> c++ XX function (not exposed to user);
而给出一些maya c++ api，可能也能实现某mel命令所做的事，毕竟假如api够用的话就能把XX函数都模拟一次，但是可能有些bugs. 所以是不是这样比较好呢:
mel command有的，就MGlobal::executeCommand(...); mel command实现起来不方便 or 实现不了的(有吗？例如自定义的某些操作?) 才用maya api来做.

Mudbox custom plugin - Remove sculpt layers

Mudbox的SDK有一些例子，提供vs project file on Windows. 我想用CMakeLists.txt尝试一下 how to create a custom plugin using cmake.

遇到的问题是：
1. 在CMakeLists.txt里面除了指定mudbox include目录以外，还需要指定Mudbox自带的Qt各目录，否则编译时候提示找不到Qt头文件.

Do not forget the
  ${MUDBOXSDK_INC_DIR}/QtCore
  ${MUDBOXSDK_INC_DIR}/QtGui
otherwise, there are some compile errors.

2. 代码里面需要先include qt的头文件再include mudbox头文件.

Include the Qt header file, for example QObject.h, before including the mudbox.h file.

3. 假如新建的sculpt layer上并没有做sculpt操作，sculpt layer左边是没有显示lock到某一层的mesh的。这时候，虽然
Geometry::LayerCount()返回的个数中包括了这一空层, 但是在
Geometry::LayerData(...)中返回的LayerMeshData *却是NULL。也就是说无法在插件中删除这些sculpt layer.

If a sculpt layer is created and without any sculpting operation on it, you will see there is no a specified level number before this layer icon, which means this layer is not locked/attached to a level. I call this "empty sculpt layer".
Even if this kind of empty sculpt layer is count of the Geometry::LayerCount() function, the LayerMeshData * returned from Geometry::LayerData(...) is NULL. So no further operations can be done with these empty sculpt layers, especially they cannot be removed by using the RemoveLayer(...).

代码source code:
https://github.com/renc/Mudbox_custom_plugin_CleanLayers 

Fractal-Mandelbrot Set

周末，除了呆在宿舍在网上给阿bou找一个婴儿床和给nico看一个手机以外，我总要折腾点什么嘛。于是...

Mandelbrot set, on the complex plane (two axis, one is the real number line, the other is the imagary number line), at a region from -2 - 1i to 1 + 1i, given a point (x + yi), is this point inside this set or outside this set? For points outsidet this region, they are defintely outside the Mandelbrot set.

The problem is that we can tell a point is outside the set only after some number iteration if magnitude(z) > 2, for a point inside the set after some iteration, it might become outside after another iteration times. So only after infinite number we can truly tell whether this point is inside or outside, otherwise we are only approximate the Manelbrot set.

void main()
{
 vec2 c = p;// pixel position.
 vec2 z = c;

 outputColor = insideColor;
 for (int i = 0; i < maxIterations; ++i)
 {
  // z = z^2 + c.
  z = vec2(z.x * z.x - z.y * z.y, 2 * z.x * z.y) + c; 

  if (dot(z, z) > 4)
  { 
   // this point is outside the set,
   // decorate this point according to the iteration.
   outputColor = func(i);
  } 
 }
}

Given an initial value, to calc a sequence of values based on a formula. This is so called iterated function system.

Reference:
Vedio, http://www.fractalforums.com/fractal-related-links/the-mandelbrot-set
The Mandelbrot Set: Colors of Infinity, from oZone3D.