UE4 凹多边形渲染

本文思路：在凸多边形的基础上将凹多边形用向量延长线法分割成多个凸多边形，然后按照凸多边形的算法计算。凸多边形比较简单，就不介绍记录了。

几个凹多边形算法的思路：

http://blog.csdn.net/sun_shine_/article/details/18799739   //任意多边形面积计算 http://www.cnblogs.com/wantnon/p/6384771.html   //直线切割凹多边形（不带洞？） http://blog.csdn.net/heyuchang666/article/details/51382757   //向量法和旋转法切割凹多边形

限制： 1.顶点数组必须是有序（顺时针或者逆时针）。 2.不支持带洞的。 3.需要将Z轴值置0.

思路流程： 1.顶点有序化。（此文暂时不记录） 2.顶点数组转换成对应的方向向量数组。 3.依次利用叉乘查找到第一个凹多边形的凹点。 4 .从这个点开始往后找到这个凹点的向量延长先在之后的向量上的第一个交点。（注意顺序，而不是从数组0开始） 5.以这个交点为界限把凹多边形分为两个多边形。 6.递归这个切分算法，直至不再有凹多边形出现为止。 7.得到的多个多边形都是属于凸多边形，利用凸多边形算法计算。

static TArray<TArray<FVector>> t_polygonDividedArr;
/*从多边形的有序的点数组获取顶点和三角面数据信息（凹凸多边形）
	参数1： 顶点数组
	参数2： 是否是逆时针
	*/
static void GetPolygonDataFromOrderVertexs(TArray<FVector> _points,bool _antiClockwise=true);
void ULcq_BlueprintFunctionLibrary::GetPolygonDataFromOrderVertexs(TArray<FVector> _points, bool _antiClockwise)
{
	TArray<FLcq_PolygonData> t_res;
	int t_pointsNum = _points.Num();
	if (t_pointsNum>3)
	{
		t_polygonDividedArr.Empty();
		DividePolygonIfConcave(_points, _antiClockwise);  //递归
		if (t_polygonDividedArr.Num()>0)
		{
			UE_LOG(LogTemp, Warning, TEXT("多边形分割成了%d  个多边形"), t_res.Num());
		}
	}
	else
	    UE_LOG(LogTemp, Error, TEXT("多边形分割失败"));
}

//分割
/*检查多边形是否是凹多边形，如果是就切割
	参数1：点集
	参数2：需要返回的被切割多边形1
	参数2：需要返回的被切割多边形2
	*/
static void DividePolygonIfConcave(TArray<FVector> _points, bool _antiClockwise = true);
void ULcq_BlueprintFunctionLibrary::DividePolygonIfConcave(TArray<FVector> _points, bool _antiClockwise)
{
	int t_pointsNum = _points.Num();	
	if (_points.Num()<3)
	{
		return;
	}
	if (t_pointsNum==3)
	{
		t_polygonDividedArr.Add(_points);
		return;
	}	
	if (t_pointsNum>3)
	{
		TArray<FVector> _dividePolygonA;
		TArray<FVector> _dividePolygonB;
		float t_hei = _points[0].Z;	
		SetPointsZvalueBySpecify(_points,0);

		FVector t_p1;
		FVector t_p2;	
		TArray<FVector> t_dirs=GetVectorArrByPointsArr(_points);

		bool t_divideResult=false;
		int t_indexNew=0;
		for (int i=0;i<t_dirs.Num();i++)
		{			
			t_p1 = t_dirs[i];
			if (i == t_dirs.Num()-1)
			{
				t_p2 = t_dirs[0];
				t_indexNew = 0;
			}
			else
			{
				t_p2 = t_dirs[i + 1];
				t_indexNew = i + 1;
			}
			
			float t_rotateDir = FVector::CrossProduct(t_p1, t_p2).Z;			

			//检查出是凹多边形
			if (t_rotateDir<-0.01f&&_antiClockwise == true || t_rotateDir>0.01f&& _antiClockwise == false)
			{
				//UE_LOG(LogTemp, Warning, TEXT("t_rotateDir:   %f"), t_rotateDir);
				UE_LOG(LogTemp, Warning, TEXT("是凹多边形~~~~~~~~~~~"));
				//求分割点

				t_divideResult = GetRayIntersectionOfVecInVecArr(t_dirs, _points, i, i, t_pointsNum - 1, _dividePolygonA, _dividePolygonB);
				if (t_divideResult == false)
				{
					t_divideResult = GetRayIntersectionOfVecInVecArr(t_dirs, _points, i, 0, i - 1, _dividePolygonA, _dividePolygonB);
				}
				if (t_divideResult == false)
				{
					UE_LOG(LogTemp, Error, TEXT("线段%d  没有得到分割点"), i);
				}
				break;
			}				
		}
		
		if (t_divideResult ==false)
		{	
			SetPointsZvalueBySpecify(_points, t_hei);
			t_polygonDividedArr.Add(_points);
		}
		else
		{
			if (_dividePolygonA.Num()>2)
			{
				SetPointsZvalueBySpecify(_dividePolygonA, t_hei);
				DividePolygonIfConcave(_dividePolygonA, _antiClockwise);
			}
			if (_dividePolygonB.Num()>2)
			{
				SetPointsZvalueBySpecify(_dividePolygonB, t_hei);
				DividePolygonIfConcave(_dividePolygonB, _antiClockwise);
			}
		}
	}
}

/*给定点数组的Z值统一化
	*/
static bool SetPointsZvalueBySpecify(TArray<FVector> &_points, float _zValue);
bool ULcq_BlueprintFunctionLibrary::SetPointsZvalueBySpecify(TArray<FVector> &_points, float _zValue)
{
	if (_points.Num()>0)
	{
		for (int i=0;i<_points.Num();i++)
		{
			_points[i].Z = _zValue;
		}
		return true;
	}

	return false;
}

/*根据点数组获取向量数组
	*/
static TArray<FVector> GetVectorArrByPointsArr(const TArray<FVector> _points);
TArray<FVector> ULcq_BlueprintFunctionLibrary::GetVectorArrByPointsArr(const TArray<FVector> _points)
{
	TArray<FVector> t_res;
	int t_pointsNum = _points.Num();
	if (t_pointsNum>1)
	{
		FVector t_p1;
		FVector t_p2;
		for (int i = 0; i < _points.Num(); i++)
		{
			t_p1 = _points[i];
			if (i == t_pointsNum - 1)
			{
				t_p2 = _points[0];
			}
			else
			{
				t_p2 = _points[i + 1];
			}		

			t_res.Add(t_p2 - t_p1);
		}
	}

	return t_res;
}

/*从向量数组中获取一个向量在这个数组中的延长线与其他向量的交点
	注意：顺序必须先从这个向量的下标开始，不能是0;交点不包括向量端点
	参数1：方向向量数组
	参数2：对应的点数组（长度需保持一致）
	参数3：这个向量的下标
	参数4，5：开始和结束下标
	参数6，7: 根据交点被切分的两组点数组
	返回值：true 为成功,反之无
	*/
	static bool GetRayIntersectionOfVecInVecArr(const TArray<FVector> _dirs, const TArray<FVector> _points, const int _vecIndex, const int _beginIndex, const int _endIndex,
		TArray<FVector> &_dividePolygonA, TArray<FVector> &_dividePolygonB);
bool ULcq_BlueprintFunctionLibrary::GetRayIntersectionOfVecInVecArr(const TArray<FVector> _dirs, const TArray<FVector> _points, const int _vecIndex,const int _beginIndex,const int _endIndex,
	TArray<FVector> &_dividePolygonA,TArray<FVector> &_dividePolygonB)
{
	int t_dirsNum=_dirs.Num();
	int t_pointsNum = _points.Num();
	
	if (t_dirsNum>3&&t_pointsNum>3)
	{
		if (t_dirsNum==t_pointsNum)
		{
			if (_beginIndex>=0&&_beginIndex<t_dirsNum)
			{
				if (_endIndex>=0&&_endIndex<t_dirsNum)
				{
					int t_indexNew = _vecIndex == (t_dirsNum - 1) ? 0 : _vecIndex + 1;
					FVector t_beginA = _points[_vecIndex];
					FVector t_endA = t_beginA + _dirs[_vecIndex];
					FVector t_intersectionPoint;

					for (int j = _beginIndex; j <= _endIndex; j++)
					{
						if (j != _vecIndex&&j != t_indexNew)
						{
							FVector t_beginB = _points[j];
							if (CheckTwoLineIntersectionResult(t_beginA, t_endA, t_beginB, t_beginB + _dirs[j], t_intersectionPoint) == 2)
							{
								//给分割的多边形点组加点
								_dividePolygonA = GetPointsByIndexRange(_points, t_indexNew, j);
								_dividePolygonA.Add(t_intersectionPoint);
								UE_LOG(LogTemp, Warning, TEXT("_dividePolygonA向量数组个数： %d"), _dividePolygonA.Num());

								_dividePolygonB = GetPointsByIndexRange(_points, j, t_indexNew);
								if (_dividePolygonB.Num() > 0)
								{
									_dividePolygonB[0] = t_intersectionPoint;
								}
								UE_LOG(LogTemp, Warning, TEXT("_dividePolygonB向量数组个数： %d"), _dividePolygonB.Num());
								return true;
							}
						}
					}
				}
			}			
		}
	}

	return false;
}