本次項目，主要概念從這裡得到啟發 : https://tedsieblog.wordpress.com/2017/02/22/field-of-view/
對 Ray 及 RaycastHit 進行擴建, 並整合自己常用的工具，達到有效開發為前題，來實現這次的項目。
畢竟，二分法射線這種現實可用的技巧還是有其實驗價值。
二分法很簡單的達成，但問題是如何快速進行運算， 實作的時候又進一步了解到 Raycast 的運作，其實真正要處理是如何在大量資料處理時有效分配資源。
簡單說就是資源分配。
二分法射線並不應該直接用在遊戲中，在 Unity 中還提供更快的 SphereCast, SphereCastAll, BoxCast …等等，
Ref : https://docs.unity3d.com/ScriptReference/Physics.SphereCastAll.html
直接上影像.
以下是整合 Ray 及 RaycastHit 的 Struct 這部份需留意(並不是class) ，這有助大量資訊操作的處理。
RayData.cs
using System;
using UnityEngine;
namespace Kit.Physic
{
public struct RayData : IEquatable<RayData>
{
public static RayData NONE { get { return default(RayData); } }
#region Core & constructor
private Ray m_Ray;
public Vector3 origin { get { return m_Ray.origin; } set { m_Ray.origin = value; } }
public Vector3 direction { get { return m_Ray.direction; } set { m_Ray.direction = value; } }
public Quaternion rotation
{
get { return Quaternion.Euler(m_Ray.direction); }
set { m_Ray.direction = value * Vector3.forward; }
}
public float distance;
public RaycastHit hit;
public bool hitted { get { return hit.transform != null; } }
public RayData(Ray ray, float distance)
{
m_Ray = ray;
this.distance = distance;
hit = new RaycastHit();
}
public RayData(Vector3 origin, Vector3 direction, float distance)
: this(new Ray(origin, direction), distance)
{ }
#endregion
#region Util tools
public static bool IsNullOrEmpty(RayData obj)
{
return ReferenceEquals(null, obj) || obj.Equals(RayData.NONE);
}
/// <summary>Reuse the RayData for something else instead of alloc new memory</summary>
/// <param name="_origin"></param>
/// <param name="_direction"></param>
/// <param name="_distance"></param>
/// <param name="reset"></param>
public void Update(Vector3 _origin, Vector3 _direction, float _distance)
{
origin = _origin;
direction = _direction;
distance = _distance;
}
/// <summary>Reuse the RayData for something else instead of alloc new memory</summary>
/// <param name="other"></param>
/// <param name="hitReferences">include the RaycastHit reference.</param>
public void Update(RayData other, bool hitReferences = false)
{
Update(other.origin, other.direction, other.distance);
if (hitReferences)
hit = other.hit;
}
public void Reset()
{
origin = direction = Vector3.zero;
distance = 0f;
hit = new RaycastHit();
}
/// <summary>Physics.Raycast</summary>
/// <param name="layerMask">default = Everything</param>
/// <param name="queryTriggerInteraction">default = UseGlobal</param>
/// <returns>return true when hitted.</returns>
public bool Raycast(int layerMask = Physics.DefaultRaycastLayers, QueryTriggerInteraction queryTriggerInteraction = QueryTriggerInteraction.UseGlobal)
{
return Physics.Raycast(m_Ray, out hit, distance, layerMask, queryTriggerInteraction);
}
/// <summary>Compare with hit result are hitting same object</summary>
/// <param name="raycastHit"></param>
/// <param name="includeNull"></param>
/// <returns></returns>
public bool IsHittingSameObject(RaycastHit raycastHit, bool includeNull = false)
{
return (includeNull || hitted) ? hit.transform == raycastHit.transform : false;
}
/// <summary>Compare with hit result are hitting same object</summary>
/// <param name="raycastHit"></param>
/// <param name="includeNull"></param>
/// <returns></returns>
public bool IsHittingSameObject(RayData raydata, bool includeNull = false)
{
return IsHittingSameObject(raydata.hit, includeNull);
}
/// <summary>Compare angle based on normal</summary>
/// <param name="normal">World Up</param>
public float AngleBetweenDirectionSigned(RayData rayB, Vector3 normal = default(Vector3))
{
return AngleBetweenDirectionSigned(rayB.m_Ray, normal);
}
/// <summary>Compare angle based on normal</summary>
/// <param name="normal">World Up</param>
public float AngleBetweenDirectionSigned(Ray otherRay, Vector3 normal = default(Vector3))
{
if (normal == default(Vector3))
normal = Vector3.up;
return Mathf.Rad2Deg * Mathf.Atan2(Vector3.Dot(normal, Vector3.Cross(m_Ray.direction, otherRay.direction)), Vector3.Dot(m_Ray.direction, otherRay.direction));
}
public void DrawGizmos(Color color = default(Color), Color hitColor = default(Color))
{
if (color == default(Color))
return;
Color cache = Gizmos.color;
if (hitted)
{
if (hitColor == default(Color))
{
hitColor = color;
color.a = Mathf.Lerp(0f, color.a, .5f);
}
}
Gizmos.color = color;
Gizmos.DrawLine(m_Ray.origin, m_Ray.origin + m_Ray.direction * distance);
#if UNITY_EDITOR
Gizmos.DrawWireCube(m_Ray.origin, Vector3.one * 0.1f * UnityEditor.HandleUtility.GetHandleSize(m_Ray.origin));
#endif
if (hitted)
{
Gizmos.color = hitColor;
Gizmos.DrawLine(m_Ray.origin, hit.point);
}
Gizmos.color = cache;
}
#endregion
#region overload methods
public override string ToString()
{
return (hitted) ?
string.Format("{0}, Distance: {1:F2}, Hit: {2} ({3:F2})", m_Ray.ToString("F2"), distance, hit.transform.name, hit.point) :
string.Format("{0}, Distance: {1:F2}, Hit: None", m_Ray.ToString("F2"), distance);
}
public override int GetHashCode()
{
return m_Ray.GetHashCode();
}
public override bool Equals(object obj)
{
return Equals(NONE) ? obj == null : Equals((RayData)obj);
}
/// <summary>Approximately Equal, based on Ray and distance, exclude hit result.</summary>
/// <param name="other"></param>
/// <returns></returns>
public bool Equals(RayData other)
{
if (GetHashCode() != other.GetHashCode())
return false;
else
{
return
Mathf.Approximately(distance, other.distance) &&
Mathf.Approximately(m_Ray.origin.x, other.origin.x) &&
Mathf.Approximately(m_Ray.origin.y, other.origin.y) &&
Mathf.Approximately(m_Ray.origin.z, other.origin.z) &&
Mathf.Approximately(m_Ray.direction.x, other.direction.x) &&
Mathf.Approximately(m_Ray.direction.y, other.direction.y) &&
Mathf.Approximately(m_Ray.direction.z, other.direction.z);
}
}
#endregion
}
}
以上的 RayData.cs, 用來存 position, direction, distance, raycasthit 等的資料.
它是一個 struct 架構，優勢則在於資源管理.
Ref: Choosing Between Class and Struct
https://msdn.microsoft.com/en-us/library/ms229017(v=vs.110).aspx
用圖片看就很簡單易明, 這是 Array of Class
以下則是 Array of struct
因為處理物理邊沿時需要大量處理這類的物理資訊，如果大量的建立 object 必然需要吃掉相對應的內存。
這時候如果重用變量 (reuse variables) 就變得相對嚴格。
接下來就是本次的主角 EdgeFinder, 使用二分法搜尋對象的邊沿。
EdgeFinder.cs
//#define BULLET_TIME
// ^ enable this if you want to visualize the progress with delay.
using UnityEngine;
using System.Collections;
namespace Kit.Physic
{
public class EdgeFinder : MonoBehaviour
{
[Header("Ray Setting")]
[SerializeField]
int m_Density = 150;
[SerializeField]
float m_Distance = 10f;
[SerializeField]
float m_Threshold = float.Epsilon;
const float MAX_THRESHOLD = 1f;
[Header("Physics")]
[SerializeField]
LayerMask m_LayerMask = Physics.DefaultRaycastLayers;
[SerializeField]
QueryTriggerInteraction m_QueryTriggerInteraction = QueryTriggerInteraction.UseGlobal;
[Header("Debug")]
[SerializeField]
Color m_Color = Color.white;
[SerializeField]
Color m_HitColor = Color.red;
#if BULLET_TIME
[SerializeField] bool m_PreviewInEditor = false;
[Range(-float.Epsilon, 0.1f)]
[SerializeField] float m_WaitSec = 0.1f;
#endif
RayData[] m_Sensors;
RayData m_Finder;
void OnValidate()
{
m_Density = Mathf.Clamp(m_Density, 0, int.MaxValue);
m_Distance = Mathf.Clamp(m_Distance, 0f, float.MaxValue);
m_Threshold = Mathf.Clamp(m_Threshold, float.Epsilon, MAX_THRESHOLD);
Init();
}
void Awake()
{
Init();
}
void Init()
{
m_Sensors = new RayData[m_Density];
#if BULLET_TIME && UNITY_EDITOR
if (m_PreviewInEditor)
{
StopAllCoroutines();
Start();
}
#else
GetBisectionEdge(transform.position, transform.forward, transform.up, m_Threshold);
#endif
}
public void OnDrawGizmos()
{
if (!Application.isPlaying)
Init();
for (int i = 0; i < m_Sensors.Length; i++)
{
if (!RayData.IsNullOrEmpty(m_Sensors[i]))
m_Sensors[i].DrawGizmos(m_Color, m_HitColor);
}
}
#if BULLET_TIME
public void Start()
{
StartCoroutine(IntervalTrigger());
}
private IEnumerator IntervalTrigger()
{
while (true)
{
yield return GetBisectionEdge(transform.position, transform.forward, transform.up, m_Threshold);
}
}
#else
void FixedUpdate()
{
GetBisectionEdge(transform.position, transform.forward, transform.up, m_Threshold);
}
#endif
private void CacheRayResult(Vector3 point, Vector3 startDirection, Vector3 normal, bool raycastTest = false)
{
Vector3 dir;
float currAngle = 0f;
float angleStep = 360f / m_Density;
for (int i = 0; i < m_Density; i++)
{
dir = Quaternion.AngleAxis(currAngle, normal) * startDirection;
m_Sensors[i].Update(point, dir, m_Distance);
if (raycastTest)
m_Sensors[i].Raycast(m_LayerMask, m_QueryTriggerInteraction);
currAngle += angleStep;
}
}
#if BULLET_TIME
private IEnumerator GetBisectionEdge(Vector3 point, Vector3 startDirection, Vector3 normal, float threshold)
#else
private void GetBisectionEdge(Vector3 point, Vector3 startDirection, Vector3 normal, float threshold)
#endif
{
CacheRayResult(point, startDirection, normal, true);
if (m_Density <= 1)
{
Debug.Log(GetType().Name + " at least two Raycast are required.");
}
else if (m_Density > 2)
{
int pt = m_Density, nextPt;
while (pt-- > 0)
{
nextPt = Mathf.CeilToInt(Mathf.Repeat(pt - 1, m_Density));
if (!m_Sensors[pt].hitted)
{
m_Sensors[pt] = RayData.NONE;
}
else if (!RayData.IsNullOrEmpty(m_Sensors[nextPt]))
{
// let's find the edge in between
TryLocateBisectionEdge(ref m_Sensors[pt], ref m_Sensors[nextPt], ref m_Finder, m_LayerMask, m_QueryTriggerInteraction, threshold);
}
#if BULLET_TIME
if (m_WaitSec > 0f)
yield return new WaitForSeconds(m_WaitSec);
#endif
}
}
#if BULLET_TIME
yield return null;
#endif
}
/// <summary>Locate edge within two ray. limit by angle threshold</summary>
/// <param name="start">Start arc direction</param>
/// <param name="end">End arc direction</param>
/// <param name="finder">Cache Helper</param>
/// <param name="layerMask"></param>
/// <param name="queryTriggerInteraction"></param>
/// <param name="threshold">min angle</param>
private void TryLocateBisectionEdge(ref RayData start, ref RayData end, ref RayData finder,
int layerMask = Physics.DefaultRaycastLayers, QueryTriggerInteraction queryTriggerInteraction = QueryTriggerInteraction.UseGlobal,
float threshold = float.Epsilon)
{
if (start.origin != end.origin)
{
Debug.LogWarning("Start origin should always equal.", this);
start.origin = end.origin;
}
if (start.IsHittingSameObject(end, includeNull: true))
{
// both hit same thing || nothing, may cause by m_Density too low, we don't care at this point.
finder.Reset();
return;
}
else
{
if (!start.hitted && end.hitted)
{
// hit something, and one of it are Empty.
// to combine case, alway making start as Empty. (locate direction will change)
finder.Update(start, hitReferences: false);
start.Update(end, hitReferences: false);
end.Update(finder, hitReferences: false);
}
// else hit different object, no change.
// reach angle threshold.
threshold = Mathf.Clamp(threshold, float.Epsilon, MAX_THRESHOLD);
if (threshold > Vector3.Angle(start.direction, end.direction))
{
finder.Reset();
return;
}
// Bisection
// recursive logic : assume origin point of start & end are equal.
finder.Update(start.origin, Vector3.LerpUnclamped(start.direction, end.direction, .5f), start.distance);
if (finder.Raycast(layerMask, queryTriggerInteraction))
{
// found the object, Move "end" closer
end.Update(finder, hitReferences: true);
}
else
{
// not found, Move "start" closer
end.Update(finder, hitReferences: true);
}
TryLocateBisectionEdge(ref start, ref end, ref finder, layerMask, queryTriggerInteraction, threshold);
}
}
}
}
使用 Recursive 及 pass by reference 的方式，接近 Zero Garbage collect 來達到目的. 測試可見 360 支射線外加二分搜尋平均花 1.17ms 產生 100kb 拉圾.
主要的 GC 問題完全產生在 GetHashCode() 的配對上(嗯…或許我可以利用 cache 再減少一 30% ? 這有待試驗)
基本的二分法已經是 0 gc.
而本次的測試大概在 密度(Density) 設在 75, 180, 360 有相對佳的 C/P 值.
更多的密度對效果沒有太大提升而且浪費大量的 CPU 資源。
如果有更好或可改進的地方，歡迎留言討論。
Enjoy, happy coding
Wonderful implementation, but what about finding the edge of objects that are above, below – including the visual angles of such?
Kinda like a 360 degree (or sphere) around the protagonist.
thanks, but we shouldn’t use this method in gaming, it’s too slow.
since Unity provided more effective API, we should use them.
you can locate the object near by using Physics.OverlapSphereNonAlloc,
and if the objects attach Collider component, you can find their distance easier by using Collider.ClosestPointOnBounds
well, get direction between objects, and them find their closest point based on that direction. easy right ?
Sample Sphere
ref:
https://docs.unity3d.com/ScriptReference/Physics.OverlapSphereNonAlloc.html
https://docs.unity3d.com/ScriptReference/Collider.ClosestPointOnBounds.html
Pingback: 實作, Triangular field of view by BoxOverlap + Raycast – Clonefactor