Unity - 撸一个简单版本的 四叉树 + 视锥cascaded，用于场景剔除

环境

Unity : 2019.4.0f1

这个内容时前端时间写的

整体效果

• 蓝色空心矩形 就是被 剔除的 cube 集合
• 红色实心矩形 就是在四叉树 + 视锥cascaded 内的 cube 集合

更加精准

Code QuadTree.cs

#define __ENABLE_COMPLETE_CONTAINS_BRANCH_HANDLE__  // 启用完全包含 枝干 优化的处理
#define __ENABLE_QT_PROFILER__                      // 启用 Profiler

using System;
using System.Collections.Generic;
using UnityEngine;

#if __ENABLE_QT_PROFILER__
using UnityEngine.Profiling;
#endif

// jave.lin : 下面的 ListPool 类可以单独放到另一个通用的工具类下管理
// 便于外部所有地方可以使用，但是如果这么做的话，最好声明为 static 静态类

/// 
/// date    : 2020/11/11
/// author  : jave.lin
/// 外部大量的 new List 也是导致大量 GC.Collect 频繁触发的原因
/// 可以使用 ListPool.FromPool, ToPool 来专门替代外部的 new List 的临时变量
/// 可大大降低：GC.Collect 的触发周期
/// List 的对象池管理，专用于 C# 层的处理，因为 lua 做不了 C# 编译时决定的泛型
/// 
/// 元素类型
public class ListPool : IDisposable
{
    private Stack _list_pool = new Stack();
    public List FromPool()
    {
        return _list_pool.Count > 0 ? _list_pool.Pop() : new List();
    }

    public void ToPool(List list)
    {
        list.Clear();
        _list_pool.Push(list);
    }

    public void Clear()
    {
        _list_pool.Clear();
    }

    public void Dispose()
    {
        if (_list_pool != null)
        {
            _list_pool.Clear();
            _list_pool = null;
        }
    }
}

[Serializable]
/// 
/// QuadTree 使用的 AABB（后续完善其实可以尝试支持 OOB）
/// date    : 2021/02/18
/// author  : jave.lin
/// 
public struct QTAABB : IEquatable
{
    public static readonly QTAABB Zero = new QTAABB();

    /// 
    /// 获取 cam frustum 的 aabb 的垂直方向的 分层级别，默认是 3 个级别
    /// 
    public const int DEFAULT_GET_CAM_FRUSTUM_TO_AABB_LEVEL = 3;
    /// 
    /// 获取 cam frustum 的 aabb 的水平方向的 padding，默认是 unity 的 0 个 units 的大小
    /// 
    public const float DEFAULT_GET_CAM_FRUSTUM_AABB_H_PADDING = 0;

    public float x;
    public float y;
    public float w;
    public float h;
    
    public float left       { get => x; set => x = value; }
    public float top        { get => y; set => y = value; }
    public float right      { get => x + w; set => w = value - x; }
    public float bottom     { get => y + h; set => h = value - y; }

    public float centerX    { get => x + w * 0.5f; set => x = value - (w * 0.5f); }
    public float centerY    { get => y + h * 0.5f; set=> y = value - (h * 0.5f); }
    public Vector2 center   { get => new Vector2(centerX, centerY); set { centerX = value.x; centerY = value.y; } }

    public float extentX    { get => w * 0.5f; set => w = value * 2; }
    public float extentY    { get => y * 0.5f; set => h = value * 2; }
    public Vector2 extent   { get => new Vector2(extentX, extentY); set { extentX = value.x; extentY = value.y; } }

    public Vector2 min { get => new Vector2(left, top); set { left = value.x; top = value.y; } }
    public Vector2 max { get => new Vector2(right, bottom); set { right = value.x; bottom = value.y; } }

    public Vector2 top_left { get => new Vector2(left, top); }
    public Vector2 top_right { get => new Vector2(right, top); }
    public Vector2 bottom_left { get => new Vector2(left, bottom); }
    public Vector2 bottom_right { get => new Vector2(right, bottom); }

    public bool IsZero()
    {
        return left == right || top == bottom;
    }
    public void Set(float x, float y, float w, float h)
    {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
    }
    /// 
    /// 当前 AABB 与 other 的 AABB 是否有交集，并返回交集的 AABB
    /// 
    /// 其他的 AABB
    /// 返回交集的 AABB
    /// 如果当前 AABB 与 other 的 AABB 是否有交集，则返回 true
    public bool IsIntersect(ref QTAABB other, out QTAABB outAABB)
    {
        outAABB         = new QTAABB();
        outAABB.x       = Mathf.Max(left, other.left);
        outAABB.right   = Mathf.Min(right, other.right);
        outAABB.y       = Mathf.Max(top, other.top);
        outAABB.bottom  = Mathf.Min(bottom, other.bottom);
        return !outAABB.IsZero();
    }
    /// 
    /// 当前 AABB 与 other 的 AABB 是否有交集
    /// 
    /// 其他的 AABB
    /// 如果当前 AABB 与 other 的 AABB 是否有交集，则返回 true
    public bool IsIntersect(ref QTAABB other)
    {
        return x  other.y;
    }
    public bool IsIntersect(QTAABB other)
    {
        return IsIntersect(ref other);
    }
    /// 
    /// 是否完整包含另一个 AABB（做优化用，一般如果整个 AABB 都被另一个 AABB 包含就不用精确检测了）
    /// 
    /// 另一个 AABB
    /// 如果完整包含另一个 AABB，则返回 true
    public bool Contains(ref QTAABB other)
    {
        return other.x >= x && other.y >= y && other.right