townscaper随机生成城镇算法分析

的几年前曾经写过一个随机生成城镇的算法，生成的城镇房间从门可以进入内部行走，房间之间的走廊也可以走通，每个房间都包含一个寻路节点。但是有个缺点，模型面数很简陋，主要靠贴图来表现效果。随机生成后手动编辑改变也比较困难。

最近看到一个 叫城镇叠叠乐的游戏比较有创意，英文名townscaper，用它生成的模型比较精致，打算研究一下其使用到的算法。

townsaper主要使用的是Marchingcube算法，根据一个体素8个顶点是否为空对应256种情形（模型）来拼接最终的模型。普通的Marchingcube算法考虑到对称性共有15种基本构型（ 考虑二义性是23种）。在townscaper中由于上下不具有对称性，一共有51种基本构型。

首先对体素的顶点进行编号，根据编号产生标记值（2的编号次方），8个顶点的标记值相加为体素的编号。

//右手系
//顶点编号
//        +----------+
//       /|V4       /|v5              y+            
//      / |        / |                |           
//     +----------+  |                |            
//   V7|  |       |v6|                |           
//     |  |       |  |				  |
//     |  |       |  |				  +-------> x+
//     |  +-------|--+               /
//     | / V0     | / V1            /
//     |/         |/               z+ 
//     +----------+                
//    V3          V2 
 
//顶点标记
//        +----------+
//       /|v16      /|v32
//      / |        / |
//     +----------+  |
// v128|  |      v|64|              
//     |  |       |  |             
//     |  |       |  |             
//     |  +-------|--+             
//     | /v1      | /v2            
//     |/         |/               
//     +----------+                
//   v8           v4       

下面列举了必须用到的模型，mesh:  18  rot[129,  72,  36] mirror[ 33,  24, 132,  66];  表示18号体素模型经过旋转90/180/270度可以产生129,72,36号体素模型，经过旋转后再x轴镜像又可以产生33,  24, 132,  66号体素模型。

//mesh:   1  rot[  8,   4,   2] mirror[   ,    ,    ,    ];   (  1 = 0)                              (  1 =   1)
//mesh:   3  rot[  9,  12,   6] mirror[   ,    ,    ,    ];   (  3 = 0 + 1)                          (  3 =   1 +   2)
//mesh:   5  rot[ 10,    ,    ] mirror[   ,    ,    ,    ];   (  5 = 0 + 2)                          (  5 =   1 +   4)
//mesh:   7  rot[ 11,  13,  14] mirror[   ,    ,    ,    ];   (  7 = 0 + 1 + 2)                      (  7 =   1 +   2 +   4)
//mesh:  15  rot[   ,    ,    ] mirror[   ,    ,    ,    ];   ( 15 = 0 + 1 + 2 + 3)                  ( 15 =   1 +   2 +   4 +   8)
//mesh:  16  rot[128,  64,  32] mirror[   ,    ,    ,    ];   ( 16 = 4)                              ( 16 =  16)
//mesh:  17  rot[136,  68,  34] mirror[   ,    ,    ,    ];   ( 17 = 0 + 4)                          ( 17 =   1 +  16)
//mesh:  18  rot[129,  72,  36] mirror[ 33,  24, 132,  66];   ( 18 = 1 + 4)                          ( 18 =   2 +  16)
//mesh:  19  rot[137,  76,  38] mirror[ 35,  25, 140,  70];   ( 19 = 0 + 1 + 4)                      ( 19 =   1 +   2 +  16)
//mesh:  20  rot[130,  65,  40] mirror[   ,    ,    ,    ];   ( 20 = 2 + 4)                          ( 20 =   4 +  16)
//mesh:  21  rot[138,  69,  42] mirror[   ,    ,    ,    ];   ( 21 = 0 + 2 + 4)                      ( 21 =   1 +   4 +  16)
//mesh:  22  rot[131,  73,  44] mirror[ 41,  28, 134,  67];   ( 22 = 1 + 2 + 4)                      ( 22 =   2 +   4 +  16)
//mesh:  23  rot[139,  77,  46] mirror[ 43,  29, 142,  71];   ( 23 = 0 + 1 + 2 + 4)                  ( 23 =   1 +   2 +   4 +  16)
//mesh:  26  rot[133,  74,  37] mirror[   ,    ,    ,    ];   ( 26 = 1 + 3 + 4)                      ( 26 =   2 +   8 +  16)
//mesh:  27  rot[141,  78,  39] mirror[   ,    ,    ,    ];   ( 27 = 0 + 1 + 3 + 4)                  ( 27 =   1 +   2 +   8 +  16)
//mesh:  30  rot[135,  75,  45] mirror[   ,    ,    ,    ];   ( 30 = 1 + 2 + 3 + 4)                  ( 30 =   2 +   4 +   8 +  16)
//mesh:  31  rot[143,  79,  47] mirror[   ,    ,    ,    ];   ( 31 = 0 + 1 + 2 + 3 + 4)              ( 31 =   1 +   2 +   4 +   8 +  16)
//mesh:  48  rot[144, 192,  96] mirror[   ,    ,    ,    ];   ( 48 = 4 + 5)                          ( 48 =  16 +  32)
//mesh:  49  rot[152, 196,  98] mirror[ 50, 145, 200, 100];   ( 49 = 0 + 4 + 5)                      ( 49 =   1 +  16 +  32)
//mesh:  51  rot[153, 204, 102] mirror[   ,    ,    ,    ];   ( 51 = 0 + 1 + 4 + 5)                  ( 51 =   1 +   2 +  16 +  32)
//mesh:  52  rot[146, 193, 104] mirror[ 56, 148, 194,  97];   ( 52 = 2 + 4 + 5)                      ( 52 =   4 +  16 +  32)
//mesh:  53  rot[154, 197, 106] mirror[ 58, 149, 202, 101];   ( 53 = 0 + 2 + 4 + 5)                  ( 53 =   1 +   4 +  16 +  32)
//mesh:  54  rot[147, 201, 108] mirror[ 57, 156, 198,  99];   ( 54 = 1 + 2 + 4 + 5)                  ( 54 =   2 +   4 +  16 +  32)
//mesh:  55  rot[155, 205, 110] mirror[ 59, 157, 206, 103];   ( 55 = 0 + 1 + 2 + 4 + 5)              ( 55 =   1 +   2 +   4 +  16 +  32)
//mesh:  60  rot[150, 195, 105] mirror[   ,    ,    ,    ];   ( 60 = 2 + 3 + 4 + 5)                  ( 60 =   4 +   8 +  16 +  32)
//mesh:  61  rot[158, 199, 107] mirror[ 62, 151, 203, 109];   ( 61 = 0 + 2 + 3 + 4 + 5)              ( 61 =   1 +   4 +   8 +  16 +  32)
//mesh:  63  rot[159, 207, 111] mirror[   ,    ,    ,    ];   ( 63 = 0 + 1 + 2 + 3 + 4 + 5)          ( 63 =   1 +   2 +   4 +   8 +  16 +  32)
//mesh:  80  rot[160,    ,    ] mirror[   ,    ,    ,    ];   ( 80 = 4 + 6)                          ( 80 =  16 +  64)
//mesh:  81  rot[168,  84, 162] mirror[   ,    ,    ,    ];   ( 81 = 0 + 4 + 6)                      ( 81 =   1 +  16 +  64)
//mesh:  82  rot[161,  88, 164] mirror[   ,    ,    ,    ];   ( 82 = 1 + 4 + 6)                      ( 82 =   2 +  16 +  64)
//mesh:  83  rot[169,  92, 166] mirror[163,  89, 172,  86];   ( 83 = 0 + 1 + 4 + 6)                  ( 83 =   1 +   2 +  16 +  64)
//mesh:  85  rot[170,    ,    ] mirror[   ,    ,    ,    ];   ( 85 = 0 + 2 + 4 + 6)                  ( 85 =   1 +   4 +  16 +  64)
//mesh:  87  rot[171,  93, 174] mirror[   ,    ,    ,    ];   ( 87 = 0 + 1 + 2 + 4 + 6)              ( 87 =   1 +   2 +   4 +  16 +  64)
//mesh:  90  rot[165,    ,    ] mirror[   ,    ,    ,    ];   ( 90 = 1 + 3 + 4 + 6)                  ( 90 =   2 +   8 +  16 +  64)
//mesh:  91  rot[173,  94, 167] mirror[   ,    ,    ,    ];   ( 91 = 0 + 1 + 3 + 4 + 6)              ( 91 =   1 +   2 +   8 +  16 +  64)
//mesh:  95  rot[175,    ,    ] mirror[   ,    ,    ,    ];   ( 95 = 0 + 1 + 2 + 3 + 4 + 6)          ( 95 =   1 +   2 +   4 +   8 +  16 +  64)
//mesh: 112  rot[176, 208, 224] mirror[   ,    ,    ,    ];   (112 = 4 + 5 + 6)                      (112 =  16 +  32 +  64)
//mesh: 113  rot[184, 212, 226] mirror[178, 209, 232, 116];   (113 = 0 + 4 + 5 + 6)                  (113 =   1 +  16 +  32 +  64)
//mesh: 114  rot[177, 216, 228] mirror[   ,    ,    ,    ];   (114 = 1 + 4 + 5 + 6)                  (114 =   2 +  16 +  32 +  64)
//mesh: 115  rot[185, 220, 230] mirror[179, 217, 236, 118];   (115 = 0 + 1 + 4 + 5 + 6)              (115 =   1 +   2 +  16 +  32 +  64)
//mesh: 117  rot[186, 213, 234] mirror[   ,    ,    ,    ];   (117 = 0 + 2 + 4 + 5 + 6)              (117 =   1 +   4 +  16 +  32 +  64)
//mesh: 119  rot[187, 221, 238] mirror[   ,    ,    ,    ];   (119 = 0 + 1 + 2 + 4 + 5 + 6)          (119 =   1 +   2 +   4 +  16 +  32 +  64)
//mesh: 120  rot[180, 210, 225] mirror[   ,    ,    ,    ];   (120 = 3 + 4 + 5 + 6)                  (120 =   8 +  16 +  32 +  64)
//mesh: 121  rot[188, 214, 227] mirror[182, 211, 233, 124];   (121 = 0 + 3 + 4 + 5 + 6)              (121 =   1 +   8 +  16 +  32 +  64)
//mesh: 122  rot[181, 218, 229] mirror[   ,    ,    ,    ];   (122 = 1 + 3 + 4 + 5 + 6)              (122 =   2 +   8 +  16 +  32 +  64)
//mesh: 123  rot[189, 222, 231] mirror[183, 219, 237, 126];   (123 = 0 + 1 + 3 + 4 + 5 + 6)          (123 =   1 +   2 +   8 +  16 +  32 +  64)
//mesh: 125  rot[190, 215, 235] mirror[   ,    ,    ,    ];   (125 = 0 + 2 + 3 + 4 + 5 + 6)          (125 =   1 +   4 +   8 +  16 +  32 +  64)
//mesh: 127  rot[191, 223, 239] mirror[   ,    ,    ,    ];   (127 = 0 + 1 + 2 + 3 + 4 + 5 + 6)      (127 =   1 +   2 +   4 +   8 +  16 +  32 +  64)
//mesh: 240  rot[   ,    ,    ] mirror[   ,    ,    ,    ];   (240 = 4 + 5 + 6 + 7)                  (240 =  16 +  32 +  64 + 128)
//mesh: 241  rot[248, 244, 242] mirror[   ,    ,    ,    ];   (241 = 0 + 4 + 5 + 6 + 7)              (241 =   1 +  16 +  32 +  64 + 128)
//mesh: 243  rot[249, 252, 246] mirror[   ,    ,    ,    ];   (243 = 0 + 1 + 4 + 5 + 6 + 7)          (243 =   1 +   2 +  16 +  32 +  64 + 128)
//mesh: 245  rot[250,    ,    ] mirror[   ,    ,    ,    ];   (245 = 0 + 2 + 4 + 5 + 6 + 7)          (245 =   1 +   4 +  16 +  32 +  64 + 128)
//mesh: 247  rot[251, 253, 254] mirror[   ,    ,    ,    ];   (247 = 0 + 1 + 2 + 4 + 5 + 6 + 7)      (247 =   1 +   2 +   4 +  16 +  32 +  64 + 128)

 经过以上处理后，美术的工作量大大减少，townscaper使用的应该就是上述模型。

 其实53个模型的制作依然是不小的工作量。 还有更进一步的算法继续减少建模工作量，可以利用反向思维将碎片自动添加到基本构型中。利用镜像和旋转对称性，我们只需要制作一个角落处的接缝碎片即可。

    //碎片piece拼接规则：
    //碎片名字  ："mTFAAFFAA-TFFFFFFF",
    //第1个字母：  r表示只旋转不镜像（rot），m表示带旋转加镜像（mirror）， 
    //第2~9个字母：[e0==true & e1,4,5==false & eother==any]    ，其中T表示true、F表示false、A表示any。
    //第10个字母： -表示除去

1号碎片"TFAAAAAA-NNNNNNNN",// 面1: e0true 、e1false 、 other any -    except  none

表示只要体素满足：顶点0为TRUE 并且 顶点1为FALSE 并且 排除无，那么体素的构型中就会包含该面片。

static const char* pieceName[PieceNum] =
{
	"TFAAAAAA",// 面1: 0true - 1false - other any - 
	"FTAAAAAA",// 面2: 1true - 0false - other any - 
	"TAAAFAAA",// 面3: 0true - 4false - other any - 
	"FAAATAAA",// 面4: 4true - 0false - other any - 
	"AAAATFAA",// 面5: 4true - 5false - other any - 
	"AAAAFTAA",// 面6: 5true - 4false - other any - 
 
	"TFAAFFAA",// 面7: 0true - 1,4,5false - other any - 	
	"FTAAFFAA",// 面8: 1true - 0,4,5false - other any - 
 
	"TAAAFTAA",// 面9: 0,5true - 4false - other any - 
	"ATAATFAA",// 面10: 1,4true - 5false - other any - 
};
bool HasPiece(int voxel,int piece)
{
	const char* name = pieceName[piece];
	const char* rule = name;
	//piece拼接规则：
	//"mTFAAFFAA-TFFFFFFF",
	//第1个字母：  r表示只旋转不镜像（rot），m表示带旋转加镜像（mirror）， 
	//第2~9个字母：[e0==true & e1,4,5==false & eother==any]    
	//第10个字母： -表示除去
 
	if (name[0]=='r' || name[0]=='m')
	{
		rule = name+1;
		bool match = true;
		for (int i=0;i<8;++i,++rule)
		{
			if ('T'==(*rule) && ((voxel&(1<<i))==0))
			{
				//match = false;
				return false;
			}
			if ('F'==(*rule) && ((voxel&(1<<i))!=0))
			{
				return false;
			}
			//if ('N'==(*name) )
			//{
			//	return false;
			//}
		}
	}
	else	
	{
		return false;
	}
 
	//extra
	if (name[9]=='+') //todo 需要和相邻的voxel相关？
	{
		//rule = name+10;
	}
	//execpt
	else if (name[9]=='-')
	{
		rule = name+10;
		for (int i=0;i<8;++i,++rule)
		{
			if ('T'==(*rule) && ((voxel&(1<<i))==0))
			{
				//execpt = false;
				return true;
			}
			if ('F'==(*rule) && ((voxel&(1<<i))!=0))
			{
				return true;
			}
 
			if ('N'==(*rule) )
			{
				return true;
			}
 
			//if ('A'==(*name))
			//{
			//}
		}
	}
	else	
	{
		return false;
	}
 
	return false;
}

遍历所有的面片判断是否添加到某体素基本构型中，即 产生了构型第一象限中的组成部分。构型 其它三个象限可以通过镜像或旋转变换到第一象限，逐个添加好面片后再将模型逆向变换回原来象限即可。

void  MarchingTownSys::GenMovieLib(int stage,const char* filename)
{
	MovieClip pieceLib;
	pieceLib.LoadFromFile(filename);
	Mesh* pieceMeshArr[PieceNum];
	for (int i=0;i<PieceNum;i++)
	{
		MovieClip* movie = pieceLib.GetMovieClip(pieceName[i]);
		if (movie)
		{
			pieceMeshArr[i] = movie->GetMesh();
		}
		else
		{
			pieceMeshArr[i] = NULL;
		}
	}
 
	for (int voxel=0;voxel<256;voxel++)
	{
		MovieClip* movie = m_voxelMovies[stage][voxel];
		if (movie)
		{
			Mesh* mesh = movie->GetMesh();
			int vVertexNum = 0;
			int trigonNum  = 0;
			int voxelTemp  = voxel;
			//四次旋转对称 计算容量
			for (int r=0;r<4;r++)
			{
				for (int p=0;p<PieceNum;p++)
				{
					Mesh* pieceMesh = pieceMeshArr[p];
					if (HasPiece(voxelTemp,p) && pieceMesh)
					{
						vVertexNum += pieceMesh->m_vVertexNum;
						trigonNum  += pieceMesh->m_trigonNum;
					}
				}
				voxelTemp = MarchingTables::VoxelRotY90[voxelTemp];
			}
			mesh->Resize(vVertexNum,vVertexNum,trigonNum);
 
			//四次旋转对称 
			vVertexNum = 0;
			trigonNum  = 0;
			voxelTemp  = voxel;
			for (int r=0;r<4;r++)
			{
				for (int p=0;p<PieceNum;p++)
				{
					Mesh* pieceMesh = pieceMeshArr[p];
					//旋转到一号角判断有无piece
					if (HasPiece(voxelTemp,p) && pieceMesh)
					{
						
						//将piece逆向旋转添加到模型
						int meshRot = (4-r)%4;
						int mirror  = 0;
 
						Mesh::Vertex*  vDstV = mesh->m_vVertexs + vVertexNum;
						Mesh::TVertex* vDstT = mesh->m_tVertexs + vVertexNum;
						Mesh::Vertex*  vSrcV = pieceMesh->m_vVertexs;
						Mesh::TVertex* vSrcT = pieceMesh->m_tVertexs;
						float posX,posZ,nx,nz;
						for (int i=0;i<pieceMesh->m_vVertexNum;i++)
						{
							posX = vSrcV->x;
							posZ = vSrcV->z;
							nx= vSrcV->nx;
							nz= vSrcV->nz;
							if (mirror)
							{
								posX *= -1;
								nx   *= -1;
							}
 
							switch(meshRot)
							{
							case 0:
								vDstV->x  = posX;
								vDstV->z  = posZ;
								vDstV->nx = nx;
								vDstV->nz = nz;
								break;
							case 1://90
								vDstV->x  =  posZ;
								vDstV->z  = -posX;
								vDstV->nx =  nz;
								vDstV->nz = -nx;
								break;
							case 2://180
								vDstV->x  = -posX;
								vDstV->z  = -posZ;
								vDstV->nx = -nx;
								vDstV->nz = -nz;
								break;
							case 3://270
								vDstV->x  = -posZ;
								vDstV->z  =  posX;
								vDstV->nx = -nz;
								vDstV->nz =  nx;
								break;
							}
 
 
							vDstV->y    = vSrcV->y;
							vDstV->ny   = vSrcV->ny;
 
							vDstT->u = vSrcT->u;
							vDstT->v = vSrcT->v;
							vDstT->w = vSrcT->w;
 
							vSrcV++;
							vSrcT++;
							vDstV++;
							vDstT++;
						}
 
						int offsetIndex = vVertexNum;
						vVertexNum += pieceMesh->m_vVertexNum;
 
						Mesh::Trigon*  srcTrigon = pieceMesh->m_trigons;
						Mesh::Trigon*  dstTrigon = mesh->m_trigons+trigonNum;
						for (int i=0;i<pieceMesh->m_trigonNum;i++)
						{
							if (mirror)
							{
								//时针序
								dstTrigon->vIndex[0] = srcTrigon->vIndex[2] + offsetIndex;
								dstTrigon->vIndex[1] = srcTrigon->vIndex[1] + offsetIndex;
								dstTrigon->vIndex[2] = srcTrigon->vIndex[0] + offsetIndex;
							}	
							else
							{	
								dstTrigon->vIndex[0] = srcTrigon->vIndex[0] + offsetIndex;
								dstTrigon->vIndex[1] = srcTrigon->vIndex[1] + offsetIndex;
								dstTrigon->vIndex[2] = srcTrigon->vIndex[2] + offsetIndex;
							}
 
							srcTrigon++;
							dstTrigon++;
						}
						trigonNum += pieceMesh->m_trigonNum;
					
					}
				}
				voxelTemp = MarchingTables::VoxelRotY90[voxelTemp];
			}
 
			//for test
			mesh->CreateBuff();
 
		}
	}
}

本算法用到的一套模型碎片：

也可以不预先将碎片拼接成基本体素，而是在最终拼接模型时直接使用碎片拼接这样更方便处理随机效果（在多套模型中随机取一个即可，给相邻的碎片使用相同的随机种子，这样就不会出现裂缝）。 

通过四边形变形技术将正方形的Marchingcube变为不规则的形状，可以使建筑物不总是看起来像方块。这一步使用的是FFD2*2*2算法，或者简单的双线性差值也可以做到。（也可以使用FD3*3*3，中心控制点是可以随机偏移的，不会导致裂缝出现）

效果图：

 源码：

//========================================================
//  @Date:     2016.05
//  @File:     Include/Math/MarchingTowns.h
//  @Brief:     MarchingTowns
//  @Author:     LouLei
//  @Email:  twopointfive@163.com
//  @Copyright (Crapell) - All Rights Reserved
//========================================================
 
#ifndef  __MarchingTowns__H__
#define  __MarchingTowns__H__
 
#include "Math/MathLib.h"
#include "Texture.h"
 
namespace RendSys
{
	class MovieClip;
	class Mesh;
};
 
 
class VertexBuffer;
class IndexBuffer;
 
class MarchingTownSys
{
public:
	typedef int IndexInt;
#define FVF_VERTEX (D3DFVF_XYZ|D3DFVF_NORMAL|D3DFVF_TEX1)
	struct SVertex
	{
		float pos[3];
		float normal[3];
		float uvw[3];
	};
 
	class VoxelBlock;
	class EnergyCell
	{
	public:
		int   IntersectRay (const vec3 &start, const vec3 &end, vec3 &resPos);
		//3~6边形面围成5~8面体 将能量点围在中间，两个能量点连线穿过多面体的面。 边界位置的面可能不完整（只有两个点）不被记录
		//            e      e
		//            :     .
		//        +----------+
		//       /|v4 :   . /|v5                          
		//      / |   :  . / |                y+           
		//     +----------+  |                |            
		//   v7|  |   :.  |v6|                |           
		// e...|..|...e...|..|....e  	      |
		//     |  |  .:   |  |				  +-------> x+
		//     |  +-------|--+               /
		//     | / v0 :   | / v1            /
		//     |/ .   :   |/               z+ 
		//     +----------+                
		//    v3.     :   v2       
		//     .      e
		//    e
		class Face
		{
		public:
			bool  IntersectRay (const vec3 &start, const vec3 &end, vec3 &resPos);
			VoxelBlock* vox[6]; //多面体顶点为邻接体素的中心 
			int         vNum;
			EnergyCell* nei;  //穿过面连接到另一个能量点
			//多面体的边穿过两个相邻体素的公共面
		};		
 
		float energy;
		unsigned int seed;
 
		vec3I index;
		vec3  pos;
		Face  faces[8];
		int   faceNum;
	};
	class VoxelBlock
	{
	public:
		bool  IsPointIn(const vec3& point) const;
		//        +----------+
		//       /|e4       /|e5                         
		//      / |        / |                y+           
		//     +----------+  |                |            
		//   e7|  |       |e6|                |           
		//     |  |   v   |  |				  |
		//     |  |       |  |				  +-------> x+
		//     |  +-------|--+               /
		//     | / e0     | / e1            /
		//     |/         |/               z+ 
		//     +----------+                
		//    e3          e2       
		vec3I index;
		vec3  cen;
		int   voxelCase;
		EnergyCell* energy8[8]; //平行六面体boundbox  ffd自由变形
 
		int   column;           //柱子
 
		//         +-----------------+
		//        /|                /|  
		//       / |               / |            y+           
		//      /  |              /  |            |            
		//     +-----------------+   |            |             
		//     |   |             |   |            |            
		//     |   |             |   |		  	  |
		//     |   |f0       f1  |   |f2		  +-------> x+	
		//     |   +--------+----|---+           / 
		//     |  /              |  /		    /
		//     | +f3      +f4    | +f5         z+    
		//     |/                |/               
		//     +--------+--------+                
		//    f6        f7       f8  
		vec3  ffd3[9];
 
		//for debug
		vec4  planes[6];
	};
 
	enum Stage
	{
		Normal     = 0,  //普通墙体 平房顶
		Tileroof   = 1,  //瓦片屋顶
		Pierground = 2,  //桥墩地基
		Handrail   = 3,  //扶手栏杆
		StageNum,
	};
 
	class MarchingPiece
	{
	public:
		MarchingPiece();
		bool  HasMirror();
		RendSys::Mesh* GetMesh(unsigned int seed);
		bool  Partof(int voxel);
		char  name[32];//去掉rand后缀
		int   randNum;
		RendSys::Mesh* mesh[8]; //同类模型最多8个随机外观
	};
 
public:
	MarchingTownSys();
	~MarchingTownSys();
 
	//!voxelGridSize:体素格子大小，8个格子是一个体素。 正四面体：8个势能格子全1，8格子周围全0。
	void  Init(const vec3I& voxelGridSize,const vec3& groundExtend);
	void  SetMovieLib(const char* movieFile);
	void  SetPieceLib(const char* movieFile);
	void  Free();
	void  DistortStandard(float cornerDistort,float cenDistort);
	void  Rand();
	void  Clear();
	void  Update();
	void  Render();
	void  RenderEdit();
 
	void  SetGroundPos(const vec3& pos);
//protected:
	//!计算势能
	float GetGridEnergy(int cx,int cy,int cz);
	void  SetEnergy(float val,int seed,int cx,int cy,int cz);
	void  MakeBound();
 
	//last 即使为空也拣选
	EnergyCell* PickGrid(const vec3& rayPos,const vec3& rayDir,bool last=true);
	void  ClearEnergys();
 
	void  GenSurface();
	//方案一：
	//!计算体素面片
	bool  GenVoxelFragment(int stage,VoxelBlock* block);
	void  GenMovieLibWithPiece(int stage,const char* filename);//从piece预生成lib，随机性不好
	void  SetTableMovie(int stage,RendSys::MovieClip* movie,const char* name);
 
	//方案二： 冗余顶点比方案一多 最好焊接一下顶点 接头处不好建模时可以使用装饰物遮挡
	//!计算体素面片
	bool  GenVoxelFragmentWithPiece(int stage,VoxelBlock* block);
	void  GenVoxelMeshWithPiece(int stage,int voxelCase,RendSys::Mesh* mesh, unsigned int seed[8]);
	void  SetTablePiece(int stage,RendSys::MovieClip* movie,const char* name);
 
	//
	bool  AddMeshFFD2(int meshRot,int mirror,RendSys::Mesh* mesh, VoxelBlock* block);
	bool  AddMeshFFD3(int meshRot,int mirror,RendSys::Mesh* mesh, VoxelBlock* block);
 
	//计算法线
	void  ComputeNormal();
 
	//计算环境光遮蔽
	void  ComputeLumen(SVertex *pVertex,int cx,int cy,int cz);
 
	//EnergyGrid 和VoxelGrid 偏离了半格  
	inline vec3  EnergyToWorld (const vec3 &energyGrid);
	inline vec3  WorldToEnergyI(const vec3 &World);
	inline vec3  WorldToEnergyF(const vec3 &World);
 
public:
	//方案一：
	RendSys::MovieClip* m_movieLib;
	RendSys::MovieClip* m_voxelMovies[StageNum][256];
 
	//方案二：
	RendSys::MovieClip* m_pieceLib;
	int PieceNum;
	#define PieceNum PieceNum
	MarchingPiece pieceArr[256];
 
	//柱子 柱子模型需要坐在原点
	RendSys::MovieClip* m_columnMovies[256];
 
	bool   m_visible;
	int    m_seed;
	int    FFDSTYLE;
	float  m_cornerDistort;
	float  m_cenDistort;
 
	vec3   m_halfGroundExtend;
	vec3   m_groundCen;
	vec3   m_groundMin;
	vec3   m_groundMax;
 
	float  m_threshould;
 
	//!一个体素voxel格子 占 8个1/4势能energy格子
	vec3I  EnergyGridSize;
	int    EnergyGridSizeXY;
 
	vec3I  VoxelGridSize;         //==EnergyGridSize-1
	int    VoxelGridSizeXY;
 
	vec3   VoxelGridExtend;
	vec3   HalfVoxelGridExtend;
 
	EnergyCell* m_gridEnergys;    //EnergyGridSize
	VoxelBlock* m_voxels;         //VoxelGridSize
 
	int            IndexsMax;
	SVertex*       m_vertexs;
	int            m_vertexNum;
	IndexInt*      m_indexs;
	int            m_indexNum;
 
	VertexBuffer*  m_vertexBuffer;
	IndexBuffer*   m_indexBuffer;
 
	int    m_brushType; //0 添加 删除 随机外观
	int    m_continueBrush;
	vec3         m_pickedPos;
	EnergyCell*  m_pickedEnergyCell;
	int          m_pickedEnergyFace;
	VoxelBlock*  m_pickedVoxelBlock;
 
	char debugStr[512];
	TexturePtr   debugTexture;
 
};
 
 
inline vec3 MarchingTownSys ::EnergyToWorld(const vec3 &energyGrid)
{
	//EnergyGrid 从 m_groundMin - HalfVoxelGridExtend开始
	//VoxelGrid  从 m_groundMin开始
	return energyGrid.Mult(VoxelGridExtend) + m_groundMin - HalfVoxelGridExtend;
}
 
inline vec3 MarchingTownSys ::WorldToEnergyI(const vec3 &World)
{
	vec3 energyGrid = (World - m_groundMin + HalfVoxelGridExtend) / VoxelGridExtend;
	energyGrid.x = floor(energyGrid.x);
	energyGrid.y = floor(energyGrid.y);
	energyGrid.z = floor(energyGrid.z);
	return energyGrid;
}
inline vec3 MarchingTownSys ::WorldToEnergyF(const vec3 &World)
{
	vec3 energyGrid = (World - m_groundMin + HalfVoxelGridExtend) / VoxelGridExtend;
	energyGrid.x = (energyGrid.x);
	energyGrid.y = (energyGrid.y);
	energyGrid.z = (energyGrid.z);
	return energyGrid;
}
#endif