核心函数

//基于DP的搜索函数。
//prim_cluster, 记录prim所属的cluster, 也顺便作为了是否已搜索到的凭据。为-1时代表没搜到、不属于任何cluster。
//prim_depth, 记录prim的四个方向(上、下、左、右)能搜到的最大深度(以cluster不为-1的prim为深度搜索边界)。
//prim_neighPrimsOff, 记录prim的四个方向的邻居prim。
//prim_maxAreaInfo和prim_searchingDir是记录搜索结果的变量，用于后续迭代和对prim属性的传递。
void
GL_SOP_gridPartition::searchMaxAreaFromStartPrimoff(GA_Offset startPrimoff, int searchDir_x, int searchDir_z) {
	const int32 x = min(parm_maxLength, prim_depth[startPrimoff][searchDir_x]);			//源点向右(X+轴---也是1号方向)，最大能看到的搜索深度
	const int32 z = min(parm_maxLength, prim_depth[startPrimoff][searchDir_z]);			//源点向下(Z+轴---也是2号方向)，最大能看到的搜索深度, 用于DP状态的2D数组初始化

	int32* XMinDepth = new int32[x];					//X+轴上的每个点，存储一个(源点->当前点) 能向下(Z+轴)搜索的最大深度, 类似于一个Z+轴的一个线扫
	int32* ZMinDepth = new int32[z];					//Z+轴上的每个点，存储一个(源点->当前点) 能向右(X+轴)搜索的最大深度, 类似于一个X+轴的一个线扫

	//START 初始化XMinDepth ZMinDepth
	GA_Offset cur_primoff = startPrimoff;
	int count = 0;
	while (cur_primoff != -1 && prim_cluster[cur_primoff] == -1 && count < x) {
		XMinDepth[count] = count == 0 ? prim_depth[cur_primoff][searchDir_z] : min(XMinDepth[count - 1], prim_depth[cur_primoff][searchDir_z]);
		cur_primoff = prim_neighPrimsOff[cur_primoff][searchDir_x], count++;
	}
	cur_primoff = startPrimoff, count = 0;
	while (cur_primoff != -1 && prim_cluster[cur_primoff] == -1 && count < z) {
		ZMinDepth[count] = count == 0 ? prim_depth[cur_primoff][searchDir_x] : min(ZMinDepth[count - 1], prim_depth[cur_primoff][searchDir_x]);
		cur_primoff = prim_neighPrimsOff[cur_primoff][searchDir_z], count++;
	}
	//END 初始化XMinDepth ZMinDepth

	//START 动态规划	从源点出发，每个X_i,Z_j点的maxArea，maxArea_coord.x, maxArea_coord.z的递推式求解。
	UT_Vector3I** maxAreaInfo = new UT_Vector3I * [x];		//x->Area, y->Coord.X z->Coord.Z
	for (int i = 0; i < x; i++)
		maxAreaInfo[i] = new UT_Vector3I[z];

	for (int i = 0; i < x; i++)	maxAreaInfo[i][0] = UT_Vector3I(i + 1, i + 1, 1);
	for (int i = 0; i < z; i++)	maxAreaInfo[0][i] = UT_Vector3I(i + 1, 1, i + 1);
	for (int i = 1; i < x; i++)
		for (int j = 1; j < z; j++) {
			int32 areaXForward = maxAreaInfo[i - 1][j].x() + (XMinDepth[i] < (j + 1) ? 0 : (j + 1));
			int32 areaZForward = maxAreaInfo[i][j - 1].x() + (ZMinDepth[j] < (i + 1) ? 0 : (i + 1));
			if (areaXForward > areaZForward) 
				maxAreaInfo[i][j] = UT_Vector3I(areaXForward, 
												maxAreaInfo[i - 1][j].y() + (XMinDepth[i] < (j + 1) ? 0 : 1), 
												maxAreaInfo[i - 1][j].z());
			else
				maxAreaInfo[i][j] = UT_Vector3I(areaZForward, 
												maxAreaInfo[i][j - 1].y(), 
												maxAreaInfo[i][j - 1].z() + (ZMinDepth[j] < (i + 1) ? 0 : 1));
		}
	//END 动态规划	从源点出发，每个X_i,Z_j点的maxArea，maxArea_coord.x, maxArea_coord.z的递推式求解。

	//startPrimoff;																		//该轮次搜索源点
	if (maxAreaInfo[x - 1][z - 1].x() > prim_maxAreaInfo[startPrimoff].x()) {
		prim_maxAreaInfo[startPrimoff] = UT_Vector3I(maxAreaInfo[x - 1][z - 1].x(),		//该轮次搜索到的最大面积
													 maxAreaInfo[x - 1][z - 1].y(),		//该轮次最大面积的X下标
													 maxAreaInfo[x - 1][z - 1].z());	//该轮次最大面积的Z
		prim_searchingDir[startPrimoff] = UT_Vector2I(searchDir_x, searchDir_z);
	}
	//清除指针数组
	for (int i = 0; i < x; i++)	delete[] maxAreaInfo[i];
	delete[] maxAreaInfo, delete[] XMinDepth, delete[] ZMinDepth;
}