在使用地形时,会遇到一种需求: 检测某个坐标点的真实高度,用于某些业务判断或显示. 因为地形也是由顶点构成的,且不可能有所有坐标点的顶点信息, 所以要获取地形范围内的任意坐标点的高(本地坐标)只能通过额外计算得到.
一般情况下可以通过离线导出数据进行粗略处理,但会导致精度和效率(增加离线工作效率)都不一定令人满意,如果能实时计算,实时获取最好.
可以的方式有:
1. Unity的Terrain自带了一个方法SampleHeight(Vector3 pos),就是用来获取地形中任意坐标点下的高.
2. 使用Physics.Raycast()射线方式获取全局坐标,并转换为本地坐标,但需要模型有Mesh Collider. 如果要获取绝对精确值,就不要使用建议模型代替检查或Convex.
但如果只是普通模型,且又不添加Mesh Collider时, 就需要自己写一个方法来获取高. 实际上就是通过指定的X,Z坐标来得到较为精确的Y坐标(本地坐标). 方法如下:
一:
Mesh带有顶点和三角形索引信息(vertices和triangles属性),通过三角形索引构建的三角形与一个平行于Y轴的方向向量(X和Z为指定的位置)相互计算,可以得到与三角形较为精确的交点, 参考前文:https://www.jianshu.com/p/e4375b34295c
二:
最简单的方式是: 循环遍历Mesh的triangles(循环步长为3),将每个三角形都与方向向量进行计算,可以得到与之相交的点,然后取得Y的最大值,即是高.但当mesh中三角形数量较多时,循环遍历会很消耗时间.
解决方案:
构建一个空间数据索引来对这种大量的空间数据进行划分(比如传统的四叉树),将mesh中的顶点数据构建起来,这样在查找任意坐标附近的顶点(及其三角形)都会比较快速,避免了全局查找,以达到提高查询速度的目的.
此应用场景中模型数据一般情况是固定的,构建好之后变动几率低,同时对实时查询速度要求更高,所以此处选择深度更低的 R树.
代码如下:
using UnityEngine;
using System.Collections.Generic;
/// <summary>
/// 使用mesh(的三角形)构建一个R树,该R树外边界是固定的(因为mesh大小是已知和固定的:mesh.bounds),不动态往外扩展.
/// 类似四叉树,但不是直接划分为4个子节点(象限),而是先分裂同一级(平行)节点,直到节点数量超过m个(类似R树)才进行下一级分裂.
/// 分裂原则是:根据mesh的x,z进行排序后取固定m个数量,形成一个节点.如果多个三角形都重叠在一起,那也不会都放到一个节点中,而是分裂为多个重合的节点分别存放.
/// 查找:在这里简化查找为只查找一个点,直接循环子节点,使用bounds.contains()来确定查找点是否位于子节点的矩形内部(没有做常规R树的跨节点判定).
/// 插入时会有性能消耗,但降低了深度(平行节点个数更多),使得容纳的个数更多.
/// </summary>
public class MeshRTree
{
public RNode root;
public float width;
public float height;
/// childrenCapacity: 当子节点数量大于此值时会使得当前插入的point所在的node触发分裂.
private int childrenCapacity = 4;
/// nodeDataCapacity: 当一个node下的数据容量超过此值时会使得所在node触发分裂.
private int nodeDataCapacity = 4;
// 查找时的计数
private int findCount = 0;
// private System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
public MeshFilter meshFilter;
public void Build(float width, float height, int childrenCapacity = 15, int nodeDataCapacity = 15)
{
if (this.childrenCapacity < 4) this.childrenCapacity = 4;
if (this.nodeDataCapacity < 4) this.nodeDataCapacity = 4;
this.childrenCapacity = childrenCapacity;
this.nodeDataCapacity = nodeDataCapacity;
this.root = new RNode();
this.width = width;
this.height = height;
root.bounds = new Bounds();
root.bounds.min = new Vector3(0, 0, 0);
root.bounds.max = new Vector3(width, 0, height);
}
public void FastBuildFromMesh(MeshFilter meshFilter, int childrenCapacity = 15, int nodeDataCapacity = 15)
{
this.meshFilter = meshFilter;
var mesh = meshFilter.sharedMesh;
var vertices = mesh.vertices;
var triangles = mesh.triangles;
var datas = new List<VertexRect>();
// Debug.Log("顶点数:" + vertices.Length + " 三角形数:" + triangles.Length + " 宽高:" + this.root.bounds.size);
for (int i = 0; i < triangles.Length; i += 3)
{
var t0 = triangles[i];
var t1 = triangles[i + 1];
var t2 = triangles[i + 2];
var v0 = vertices[t0];
var v1 = vertices[t1];
var v2 = vertices[t2];
VertexRect data = new VertexRect();
data.AddVertexs(v0, v1, v2);
datas.Add(data);
}
var bounds = mesh.bounds;
this.FastBuild(bounds.size.x, bounds.size.z, datas, childrenCapacity, nodeDataCapacity);
root.bounds = mesh.bounds;
}
/// <summary>
/// 通过一组Vertex2Triangle数据,快速分裂出tree,该方法比循环datas进行单个添加快4倍左右,但分布不精确.
/// </summary>
public void FastBuild(float width, float height, List<VertexRect> datas, int childrenCapacity = 15, int nodeDataCapacity = 15)
{
this.Build(width, height, childrenCapacity, nodeDataCapacity);
this.root.SetDatas(datas);
this.DirectSplit(this.root);
}
public void Add(Vector3 v0, Vector3 v1, Vector3 v2)
{
VertexRect vr = new VertexRect();
vr.AddVertexs(v0, v1, v2);
this.Add(vr);
}
public void Add(VertexRect vertexRect)
{
// 从根节点往下查找point所属的叶子节点
findCount = 0;
var node = this.GetLeafNodeOnAdd(this.root, vertexRect);
if (node == null)
{
// 需要进行区域扩展
// ...
Debug.Log("警告:超出添加范围 (" + vertexRect + ")");
// this.GetLeafNode(this.root, vertexRect);
return;
}
// 如果叶子节点内数据容量超过capacity,则需要分裂
if (node.GetDatas().Count + 1 > this.nodeDataCapacity)
{
this.SplitAndAdd(node, vertexRect);
}
else
{
node.AddData(vertexRect);
}
}
/// 查找位于哪些node内
public List<RNode> Search(Vector3 pos)
{
// pos = meshFilter.transform.InverseTransformVector(pos);
this.findCount = 0;
var p = new Vector3(pos.x, this.root.bounds.center.y, pos.z);
var rs = new List<RNode>();
this._Search(this.root, p, rs);
return rs;
}
private void _Search(RNode currNode, Vector3 point, List<RNode> rs)
{
this.findCount++;
if (currNode.IsLeaf())
{
if (this.Conatains(currNode.bounds, point))
{
rs.Add(currNode);
}
else
{
return;
}
}
if (!this.Conatains(currNode.bounds, point)) return;
var children = currNode.children;
for (int i = 0; i < children.Count; i++)
{
this._Search(children[i], point, rs);
}
}
public int GetFindStepCount()
{
return this.findCount;
}
// -----------------------------------------------------
private bool Conatains(Bounds bounds, Vector3 point)
{
var min = bounds.min;
var max = bounds.max;
var b1 = point.x >= min.x || Mathf.Abs(point.x - min.x) <= 0.0001f;
var b2 = point.z >= min.z || Mathf.Abs(point.z - min.z) <= 0.0001f;
var b3 = point.x <= max.x || Mathf.Abs(point.x - max.x) <= 0.0001f;
var b4 = point.z <= max.z || Mathf.Abs(point.z - max.z) <= 0.0001f;
return b1 && b2 && b3 && b4;
// return bounds.Contains(point);
}
private bool Conatains(Bounds bounds, VertexRect vertexRect)
{
var vertexs = vertexRect.GetVertexs();
for (int i = 0; i < vertexs.Length; i++)
{
var point = vertexs[i];
if (this.Conatains(bounds, point)) return true;
}
return false;
}
/// 选择所属的叶子节点
private RNode GetLeafNodeOnAdd(RNode node, VertexRect vertexRect)
{
findCount++;
if (node.IsLeaf())
{
if (this.Conatains(node.bounds, vertexRect)) return node;
return null;
}
var children = node.children;
for (int i = 0; i < children.Count; i++)
{
// 父区域对point有包含才继续往下查找
if (this.Conatains(children[i].bounds, vertexRect))
{
var _node = GetLeafNodeOnAdd(children[i], vertexRect);
findCount++;
if (_node != null) return _node;
}
}
return null;
}
/// 直接分裂
private void DirectSplit(RNode node)
{
this._SplitAndAdd(node, null);
var children = node.children;
if (children.Count >= this.childrenCapacity)
{
for (int i = 0; i < children.Count; i++)
{
if (children[i].IsLeaf() && children[i].GetDatas().Count > this.nodeDataCapacity)
this.DirectSplit(children[i]);
}
}
}
/// <summary>
/// 分裂节点:
/// 当leafNode的平行节点数量大于childrenCapacity时,才会增加深度---leafNode扩展出子节点
/// 增加深度时,平行节点内的数据量应该是饱和的,平行节点的所有数据总量应该不大于 T = childrenCapacity*nodeDataCapacity
/// </summary>
private void SplitAndAdd(RNode node, VertexRect newData)
{
// 优化: 插入的点和上次没变化,直接添加
if (!this.NeedSplit(node, newData))
{
node.AddData(newData);
return;
}
if (node == this.root)
{
this._SplitAndAdd(node, newData);
return;
}
if (node.parent.children.Count >= this.childrenCapacity)
{
// 如果父级不能再分裂,直接分裂当前节点
this._SplitAndAdd(node, newData);
}
else
{
this._SplitAndAdd(node.parent, newData);
}
}
/// 在容量已满时检查是否需要分裂:如果添加的数据和node中上次添加的数据信息是一样的,则不需要分裂
private bool NeedSplit(RNode node, VertexRect newData)
{
var datas = node.GetDatas();
if (datas.Count < 1) return true;
var lastData = datas[datas.Count - 1];
// var pos1 = lastData.pos;
// var pos2 = newData.pos;
// return !((pos1.x == pos2.x && pos1.z == pos2.z) || (Mathf.Abs(pos1.x - pos2.x) <= 0.0001f && Mathf.Abs(pos1.z - pos2.z) <= 0.0001f));
return newData != null && lastData.Equals(newData);
}
/*
节点分裂.
将当前节点(不管是叶子节点还是容器节点)的所有数据拿出进行一次x和z的排序,然后将排序结果进行分裂
如: 假设要对A节点进行分裂(nodeDataCapacity=5)
step1: 先将A节点下的所有叶子节点清空,但保留数据,并按照x(从小到大)-z(从小到大)进行排序,如下图:
A----|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯|
| p p p |
| p p p p |
| |
| p p |
| p p |
|__________________|
step2: 将这些数据按顺序分为2个部分,形成1,2号2个子节点,这2个节点都是叶子节点,如下图:
A----|¯¯¯¯¯¯¯¯¯¯¯|¯¯¯¯¯¯|
| p |p p |
1---| p p| p p |
| | |
| p |p |
| p p| |---2
|___________|______|
step3: 1号节点内的数据依然大于5,继续分裂1号节点,得到3号节点,如下图:
A----|¯¯¯¯¯¯¯¯¯¯¯|¯¯¯¯¯¯|
| p |p p |
3---| p p| p p |
|-----------| |
| p |p |
1---| p p| |---2
|___________|______|
end: 每个节点内的数据数量满足条件,完成对A节点的分裂,1,2,3号节点这些节点都是A节点下的子节点,达到了平行扩展的需求.
只有当子节点数量达到childrenCapacity,才则重复上述步骤对子节点进行分裂,即增加高度.
分裂后,各个叶子节点的bounds可能会重叠,但节点不会重复,所以即使添加的VertexRect是同一个位置,那也会被分配到不同的node中
*/
private bool _SplitAndAdd(RNode node, VertexRect newData)
{
// 叶子节点
List<VertexRect> currDatas;
Bounds nodeDataBounds = new Bounds();
if (node.IsLeaf())
{
if (node.GetDatas().Count < this.nodeDataCapacity)
{
if (newData != null) node.AddData(newData);
return false;
}
if (newData != null) node.AddData(newData); // 触发一次bounds更新
nodeDataBounds = node.GetDataBounds();
currDatas = node.GetDatas();
node.EmptyData();
}
else
{
var paralleledNodes = node.children;
currDatas = new List<VertexRect>();
for (int i = 0; i < paralleledNodes.Count; i++)
{
if (newData != null)
{
if (this.Conatains(paralleledNodes[i].bounds, newData))
{
// 触发一次bounds更新
paralleledNodes[i].AddData(newData);
}
}
currDatas.AddRange(paralleledNodes[i].GetDatas());
}
nodeDataBounds = node.GetDataBounds();
node.EmptyChildren();
}
var currNodeChildren = node.children;
// 循环处理分裂结果
var nextDatas = currDatas;
var j = -1;
// 对node的持续分裂
while (true)
{
var info = this.GetSplitInfo(nextDatas);
if (info == null) // 不能分裂
{
if (j == -1)
{
var child = new RNode();
child.heap = node.heap + 1;
child.index = 0;
child.parent = node;
child.SetDatas(nextDatas);
child.GetDataBounds();
currNodeChildren.Add(child);
}
else
{
currNodeChildren[j].SetDatas(nextDatas);
currNodeChildren[j].GetDataBounds();
}
break;
}
if (j == -1)
{ // j表示当前正在分裂的节点index,-1表示第一次分裂,需要添加
var child = new RNode();
child.heap = node.heap + 1;
child.index = 0;
child.parent = node;
child.SetDatas(info.group1);
child.GetDataBounds();
currNodeChildren.Add(child);
}
else
{
// 如果已经分裂出来的节点总数超过容量,则不能直接添加,需要增加高度,进行下一级分裂
if (currNodeChildren.Count + 1 > this.childrenCapacity)
{
// 此时currNodeChildren中各个节点数据已经包含了newData,所以无需重复添加
this._SplitAndAdd(currNodeChildren[j], null);
break;
}
// j>-1表示基于上次的节点进行分裂
currNodeChildren[j].SetDatas(info.group1);
currNodeChildren[j].GetDataBounds();
}
// 第二个节点是分裂出来的,直接添加为新节点
var child2 = new RNode();
child2.heap = node.heap + 1;
child2.index = currNodeChildren.Count;
child2.parent = node;
child2.SetDatas(info.group2);
child2.GetDataBounds();
currNodeChildren.Add(child2);
// 选取节点数量较多的一组进行进一步的分裂
var _nextIndex = -1;
var cap = -1;
for (int i = 0; i < currNodeChildren.Count; i++)
{
var _datas = currNodeChildren[i].GetDatas();
if (_datas.Count > this.nodeDataCapacity && _datas.Count > cap)
{
_nextIndex = i;
cap = _datas.Count;
}
}
// 没有可以进一步分裂的节点了
if (_nextIndex == -1) break;
nextDatas = currNodeChildren[_nextIndex].GetDatas();
j = _nextIndex;
}
// sw.Stop();
// Debug.Log(string.Format("t: {0}-{1} ms", sw.ElapsedMilliseconds, sw.ElapsedTicks));
return true;
}
/// 分割信息
private SplitInfo GetSplitInfo(List<VertexRect> allDatasInNode)
{
List<VertexRect> group1 = new List<VertexRect>();
List<VertexRect> group2 = new List<VertexRect>();
// 对allDatasInNode进行一次排序: 从做到右,从上到下
allDatasInNode.Sort((VertexRect a, VertexRect b) =>
{
if (a.minX < b.minX) return -1;
if (a.minX > b.minX) return 1;
if (a.minZ < b.minZ) return -1;
if (a.minZ > b.minZ) return 1;
return 0;
});
// 将排序后的结果分为2类
var len = (int)(allDatasInNode.Count * 0.5f);
for (int i = 0; i < len; i++)
{
group1.Add(allDatasInNode[i]);
}
for (int i = len; i < allDatasInNode.Count; i++)
{
group2.Add(allDatasInNode[i]);
}
var info = new SplitInfo();
info.group1 = group1;
info.group2 = group2;
return info;
}
override public string ToString()
{
var sb = new System.Text.StringBuilder();
sb.Append("MeshRectTree={");
sb.Append(this.root.ToString());
sb.Append("}");
return sb.ToString();
}
/// -------------------------------------------
#if UNITY_EDITOR
private List<RNode> searchResult;
// private Color[] debugColors;
private Color showTreeColor = new Color(94f / 255f, 154f / 255f, 154f / 255f, 1f);
public bool showTree = false;
public void FixedUpdate()
{
if (this.showTree) this._ShowTreeRect(this.root, this.showTreeColor);
this._ShowSearchResult();
}
public void ShowSearchResult(List<RNode> result)
{
this.searchResult = result;
}
// public void ShowSearchResult(List<VertexRect> result)
private void _ShowSearchResult()
{
if (this.searchResult == null) return;
for (int i = 0; i < searchResult.Count; i++)
{
var datas = searchResult[i].GetDatas();
for (int j = 0; j < datas.Count; j++)
{
var vertices = datas[j].GetVertexs();
var v0 = vertices[0];
var v1 = vertices[1];
var v2 = vertices[2];
Debug.DrawLine(v0, v1, Color.white);
Debug.DrawLine(v1, v2, Color.white);
Debug.DrawLine(v2, v0, Color.white);
}
this._ShowTreeRect(searchResult[i], Color.yellow);
}
}
private void _ShowTreeRect(RNode node, Color _color)
{
var min = node.bounds.min;
var max = node.bounds.max;
Vector3 p0 = new Vector3(min.x, this.root.bounds.center.y, min.z);
Vector3 p1 = new Vector3(p0.x, p0.y, max.z);
Vector3 p2 = new Vector3(max.x, p1.y, p1.z);
Vector3 p3 = new Vector3(p2.x, p2.y, p0.z);
Debug.DrawLine(p0, p1, _color);
Debug.DrawLine(p1, p2, _color);
Debug.DrawLine(p2, p3, _color);
Debug.DrawLine(p3, p0, _color);
if (!node.IsLeaf())
{
for (int i = 0; i < node.children.Count; i++)
{
_ShowTreeRect(node.children[i], showTreeColor);
}
}
else
{
var datas = node.GetDatas();
var dist = 0.2f;
var offx = Mathf.Cos(Mathf.Deg2Rad * 30) * dist;
var offz = Mathf.Sin(Mathf.Deg2Rad * 30) * dist;
for (int i = 0; i < datas.Count; i++)
{
var vertexs = datas[i].GetVertexs();
// 对每个vertex画个小三角,方便查看
for (int j = 0; j < vertexs.Length; j++)
{
var p = vertexs[j];
Gizmos.color = Color.red;
var pos0 = new Vector3(p.x - offx, p.y, p.z - offz);
var pos1 = new Vector3(p.x, pos0.y, pos0.z + dist);
var pos2 = new Vector3(pos1.x + offx, pos0.y, pos1.z - offz);
Debug.DrawLine(pos0, pos1, Color.red);
Debug.DrawLine(pos1, pos2, Color.red);
Debug.DrawLine(pos2, pos0, Color.red);
}
}
}
}
#endif
}
public class RNode
{
public int heap;
public int index;
public RNode parent;
public Bounds bounds;
/// 数据
private List<VertexRect> datas = new List<VertexRect>();
/// 子节点
public List<RNode> children = new List<RNode>();
/// 将child的bounds缓存下来,避免频繁计算bounds
private bool _childrenBoundsDirty = true;
private Bounds _childrenBounds;
public void MarkChildrenBoundsDirty()
{
this._childrenBoundsDirty = true;
}
public bool childrenBoundsDirty
{
get { return this._childrenBoundsDirty; }
set
{
if (value)
{
// 向上传播脏标记
var p = this.parent;
while (p != null)
{
p.MarkChildrenBoundsDirty();
p = p.parent;
}
}
this._childrenBoundsDirty = value;
}
}
public void EmptyData()
{
this.childrenBoundsDirty = true;
this.datas = new List<VertexRect>();
}
public void EmptyChildren()
{
this.children = new List<RNode>();
}
public void AddData(VertexRect data)
{
this.childrenBoundsDirty = true;
this.datas.Add(data);
}
public void SetDatas(List<VertexRect> datas)
{
this.childrenBoundsDirty = true;
this.datas = datas;
}
public List<VertexRect> GetDatas()
{
return datas;
}
public bool IsLeaf()
{
if (this.children.Count > 0) return false;
return true;
}
public List<VertexRect> GetAllDatas()
{
var list = new List<VertexRect>();
list.AddRange(this.datas);
for (int i = 0; i < this.children.Count; i++)
{
list.AddRange(children[i].GetAllDatas());
}
return list;
}
/// 获取data在本节点分布下形成的bounds
public Bounds GetDataBounds()
{
if (this.childrenBoundsDirty == false) return this._childrenBounds;
this.childrenBoundsDirty = false;
var min = new Vector3(float.MaxValue, 0, float.MaxValue);
var max = new Vector3(float.MinValue, 0, float.MinValue);
if (this.IsLeaf())
{
for (int i = 0; i < datas.Count; i++)
{
VertexRect vr = datas[i];
var vertexs = vr.GetVertexs();
for (int j = 0; j < vertexs.Length; j++)
{
var p = vertexs[j];
if (p.x < min.x) min.x = p.x;
if (p.z < min.z) min.z = p.z;
if (p.x > max.x) max.x = p.x;
if (p.z > max.z) max.z = p.z;
}
}
}
else
{
for (int i = 0; i < this.children.Count; i++)
{
var childBounds = children[i].GetDataBounds();
var chiMin = childBounds.min;
var chiMax = childBounds.max;
if (chiMin.x < min.x) min.x = chiMin.x;
if (chiMin.z < min.z) min.z = chiMin.z;
if (chiMax.x > max.x) max.x = chiMax.x;
if (chiMax.z > max.z) max.z = chiMax.z;
}
}
this._childrenBounds = new Bounds();
_childrenBounds.SetMinMax(min, max);
if (this.parent != this && this.parent != null)
{
// 非根节点的bounds就是dataBounds
this.bounds = this._childrenBounds;
}
return this._childrenBounds;
}
override public string ToString()
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
for (int i = 1; i < this.heap + 1; i++)
{
sb.Append(" ");
}
sb.Append("RN:{");
sb.Append("h=");
sb.Append(heap);
sb.Append(",i=");
sb.Append(index);
// sb.Append(",leaf=");
// sb.Append(this.IsLeaf());
// sb.Append(",bund=[");
// sb.Append(this.bounds.min);
// sb.Append(",");
// sb.Append(this.bounds.max);
// sb.Append("]");
sb.Append(",ds=[L:");
sb.Append(datas.Count);
sb.Append("> ");
for (int i = 0; i < datas.Count; i++)
{
// sb.Append(datas[i].pos);
// sb.Append(",");
}
sb.Append("],");
sb.Append("ch=[L:");
sb.Append(this.children.Count);
sb.Append(">");
for (int i = 0; i < this.children.Count; i++)
{
sb.Append("\n");
sb.Append(children[i].ToString());
sb.Append(",");
}
sb.Append("]");
sb.Append("}");
return sb.ToString();
}
}
/// 顶点构成的三角形区域
public class VertexRect
{
// public int[] triangle;
private float _minX;
public float minX
{
get { return this._minX; }
}
private float _maxX;
public float maxX
{
get { return this._maxX; }
}
private float _minZ;
public float minZ
{
get { return this._minZ; }
}
private float _maxZ;
public float maxZ
{
get { return this._maxZ; }
}
private Vector3[] vertexs = new Vector3[3];
public void AddVertexs(Vector3 v0, Vector3 v1, Vector3 v2)
{
this.vertexs[0] = v0;
this.vertexs[1] = v1;
this.vertexs[2] = v2;
this._minX = Mathf.Min(v0.x, v1.x, v2.x);
this._maxX = Mathf.Min(v0.x, v1.x, v2.x);
this._minZ = Mathf.Min(v0.z, v1.z, v2.z);
this._maxZ = Mathf.Min(v0.z, v1.z, v2.z);
}
public Vector3[] GetVertexs()
{
return this.vertexs;
}
public bool Equals(VertexRect tag)
{
var v0 = vertexs[0];
var v1 = vertexs[1];
var v2 = vertexs[2];
var _v0 = tag.GetVertexs()[0];
var _v1 = tag.GetVertexs()[1];
var _v2 = tag.GetVertexs()[2];
var b1 = Mathf.Abs(v0.x - _v0.x) <= 0.0001f;
var b2 = Mathf.Abs(v0.y - _v0.y) <= 0.0001f;
var b3 = Mathf.Abs(v0.z - _v0.z) <= 0.0001f;
return b1 && b2 && b3;
}
override public string ToString()
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
sb.Append("{v0={");
sb.Append(vertexs[0]);
sb.Append(",v1=");
sb.Append(vertexs[1]);
sb.Append(",v2=");
sb.Append(vertexs[2]);
sb.Append("},");
sb.Append("}");
return sb.ToString();
}
}
internal class SplitInfo
{
public List<VertexRect> group1;
/// 划分后右|上的数据
public List<VertexRect> group2;
}
}
image.png
image.png
说明:
- 生成的结构不包含mesh的空间转换信息,所以是相对于世界坐标的(0,0,0)来显示的
- 红色的点是顶点(_ShowTreeRect()方法中进行的处理)
- 青色的框线就是包含顶点的一层层的矩形区域(节点),这些节点最终形成了R树结构
第三步:
通过第二步,我们已经能够获取到查询点附近的三角形信息了,其数量低于mesh.triangles.Count,再写一个类来从这些三角形获取指定点下的高.
代码如下:
using UnityEngine;
using System.Collections.Generic;
using XLua;
#if UNITY_EDITOR
using UnityEditor;
#endif
namespace DCG
{
/// mesh高度获取
/// @author Danny Yan
[LuaCallCSharp, DisallowMultipleComponent, RequireComponent(typeof(MeshFilter))]
public class SampleMeshHeight : MonoBehaviour
{
private MeshRTree _tree;
public MeshRTree tree
{
get { return _tree; }
}
private MeshFilter targetMesh;
private Vector3 measuringStartPoint;
private Vector3 measuringEndPoint;
// [Header("构建方式. 0:慢速 1:快速"), Range(0, 1)]
// public int buildTreeType = 1;
// #if UNITY_EDITOR
[BlackList]
public List<RNode> lastSearchAroundData;
[Header("测量点在RectTree中消耗步骤"), BlackList]
public int searchPointCostStep;
[Header("获取高度消耗时间(ms)"), BlackList]
public float searchPointCostTime;
[Header("构建RectTree消耗时间(ms)")]
public float buildTreeTime;
// #endif
public bool measureCostTime = false;
private System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
private void Awake()
{
this.Init();
}
#if UNITY_EDITOR
[Header("显示测量位置的射线"), BlackList]
public bool showMeasuringLine = false;
[Header("显示RectTree结构"), BlackList]
public bool showTree = false;
[Header("显示搜索结果"), BlackList]
public bool showSearch = false;
[BlackList]
public bool showDebug = true;
private void FixedUpdate()
{
if (this.tree != null)
{
this.tree.showTree = this.showTree;
this.tree.ShowSearchResult(this.showSearch ? this.lastSearchAroundData : null);
this.tree.FixedUpdate();
}
if (showMeasuringLine)
{
Debug.DrawLine(this.measuringStartPoint, this.measuringEndPoint, Color.cyan);
Debug.DrawLine(this.tree.meshFilter.transform.TransformPoint(this.measuringStartPoint), this.tree.meshFilter.transform.TransformPoint(this.measuringEndPoint), Color.cyan);
}
}
private void OnDrawGizmos()
{
if (EditorApplication.isPlaying) return;
if (this.tree == null)
{
this.Init();
}
this.FixedUpdate();
}
#endif
public void Init()
{
_tree = new MeshRTree();
this.targetMesh = this.GetComponent<MeshFilter>();
if (measureCostTime) sw.Restart();
tree.FastBuildFromMesh(this.targetMesh);
if (measureCostTime)
{
sw.Stop();
this.buildTreeTime = sw.ElapsedMilliseconds;
// Debug.Log(string.Format("顶点数:{0:G}, 构建消耗时间:{1:G}ms", targetMesh.sharedMesh.vertexCount, this.buildTreeTime));
}
this.lastSearchAroundData = null;
}
/// <summary>获取高度</summary>
public float SampleHeight(Vector3 localPos)
{
var meshFilter = tree.meshFilter;
localPos.y -= 1000;
this.measuringStartPoint = localPos;
if (measureCostTime)
{
sw.Restart();
}
List<RNode> rs = this.tree.Search(localPos);
if (rs == null || rs.Count < 1)
{
lastSearchAroundData = null;
return 0;
}
this.searchPointCostStep = tree.GetFindStepCount();
this.lastSearchAroundData = rs;
measuringEndPoint = new Vector3(measuringStartPoint.x, measuringStartPoint.y + 2000f, measuringStartPoint.z);
var dir = Vector3.Normalize(measuringEndPoint - measuringStartPoint);
var samples = new List<Vector3>();
for (int i = 0; i < rs.Count; i++)
{
RNode node = rs[i];
var datas = node.GetDatas();
for (int j = 0; j < datas.Count; j++)
{
var vertices = datas[j].GetVertexs();
var v0 = vertices[0];
var v1 = vertices[1];
var v2 = vertices[2];
float t, u, v;
var b = Util.IntersectTriangle(measuringStartPoint, dir, v0, v1, v2, out t, out u, out v);
if (b)
{
var p = (1 - u - v) * v0 + u * v1 + v * v2;
samples.Add(p);
}
}
}
if (samples.Count < 1)
{
if (measureCostTime)
{
sw.Stop();
this.searchPointCostTime = sw.ElapsedMilliseconds;
}
return 0;
}
var h = float.MinValue;
for (int i = 0; i < samples.Count; i++)
{
if (samples[i].y > h) h = samples[i].y;
}
if (measureCostTime)
{
sw.Stop();
this.searchPointCostTime = sw.ElapsedMilliseconds;
// Debug.Log(string.Format("查找消耗时间:{0:G}ms", searchPointCostTime));
}
return h;
}
}
#if UNITY_EDITOR
[CustomEditor(typeof(SampleMeshHeight))]
internal class SampleMeshHeightEditor : Editor
{
private Vector3 samplePos;
private bool showTreeRect = false;
private bool showTreeSearchAround = false;
public override void OnInspectorGUI()
{
base.OnInspectorGUI();
GUILayout.Space(15);
this.samplePos = EditorGUILayout.Vector3Field("测量位置", this.samplePos);
GUILayout.Space(5);
GUILayout.BeginHorizontal();
if (GUILayout.Button("获取高度"))
{
var meshHeight = this.target as SampleMeshHeight;
if (meshHeight.tree == null)
{
meshHeight.Init();
}
var h = meshHeight.SampleHeight(samplePos);
SceneView.lastActiveSceneView.Repaint();
Debug.Log("高度: " + h);
}
if (GUILayout.Button("Reset", GUILayout.Width(60)))
{
var meshHeight = this.target as SampleMeshHeight;
meshHeight.Init();
}
GUILayout.EndHorizontal();
}
}
#endif
Util.IntersectTriangle()方法参考前文: https://www.jianshu.com/p/e4375b34295c
验证测量
假如现在要测量红圈的位置(-151.9,0,55.3),测量位置是mesh的gameobject内的localPosition:
image.png
image.png
在R树中形成的测量结果为:
image.png
说明
- 黄色的线框是查找到的节点,白色的线条是这些节点下的数据(顶点)的连线.
- 淡青色的线条是测量用的射线
image.png
再换个角度(去掉模型的空间转换,将其归位到(0,0,0)):
image.png
image.png
现在验证下此高度是否正确,在该mesh的gameobject下建立一个plane,设置localPosition坐标为(-151.9, 7.925237, 55.3),结果如下:
image.png
放大一点:
image.png
总结
- 只实现了从mesh整体构建, 暂未实现添加单个节点行为(一个一个的添加顶点来动态构建树), 暂未实现删除节点行为
- 直接将SampleMeshHeight组件添加到mesh所在的gameobject上
- 查找时是使用相对于这个gameobject的localPosition,所以在构建树时也没有代入gameobject的transform信息(只使用原始顶点和三角形信息),这也同时避免在transform变化时重复构建
-
对于1组5K顶点的mesh,(在PC上)构建树消耗大约为40-60ms:
nodeDataCapacity==15时:
image.png
nodeDataCapacity==9时:image.png
如果mesh顶点数过多,可以自行增加缓存机制,只在进入游戏或第一次使用时构建一次.
- 查询耗时,第一查询为1ms左右,此后大约0.1ms左右;
-
本方式比
Physics.Raycast()速度更慢(慢至少5倍),如果业务简单,MeshCollider不参与复杂物理处理,仅仅用于高度检查,则还是推荐使用Physics.Raycast方式. 但如果模型因为需要参与复杂物理处理,导致不能添加MeshCollider,则可以使用本方式; - 可以通过扩展为多线程来提升批量查询速度;
转载请注明出处: https://www.jianshu.com/p/a22cc95b33bd
R树相关参考:
http://baige5117.github.io/blog/R*-Tree.html
https://blog.csdn.net/wzf1993/article/details/79547037
http://www.sohu.com/a/137533865_642762
https://blog.csdn.net/sjyttkl/article/details/70226192
