# QuadTreeMap

**Repository Path**: iceRabbit/quad-tree-map

## Basic Information

- **Project Name**: QuadTreeMap
- **Description**: 四叉树，流式加载
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-07-11
- **Last Updated**: 2026-07-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# QuadTreeMap

四叉树空间分割 + 视锥体/矩形裁剪，实现大场景物体的动态加载/卸载。

引擎无关核心库（.NET Standard 2.0），已在 Unity 和 Godot 4 中验证。

## 项目结构

```
QuadTreeMap.Core/                     ← 引擎无关核心库
  ├── QuadTree.cs                     四叉树根节点
  ├── QuadTreeNode.cs                 四叉树节点（分割/裁剪/引用计数）
  ├── SplitPlane.cs                   子节点划分坐标平面枚举 (XZ / XY / YZ)
  ├── IQuadTreeNode.cs                节点接口
  ├── QBounds.cs                      AABB 包围盒
  ├── QFrustum.cs                     视锥体裁剪算法
  ├── ObjData.cs                      场景物体数据
  ├── ILoadHandler.cs                 加载/卸载接口
  ├── IDebugDraw.cs                   调试绘制接口
  └── QColor.cs                       RGBA 颜色

QuadTreeMap.LoadHandler/              ← 通用加载管理器（引擎无关）
  ├── IObjectFactory.cs               引擎工厂接口（引擎只需实现此接口）
  ├── SceneObjData.cs                 对象包装（ObjData + 状态 + 实例）
  ├── LoadHandlerBase.cs              通用 ILoadHandler 实现
  └── SceneObjStatus.cs               加载状态枚举

quad-tree-map-demo-(godot)/            ← Godot 4 演示项目
  ├── Scripts/
  │   ├── GodotDemo.cs                3D 演示（Node3D + 视锥体裁剪）
  │   ├── GodotCamera.cs              3D 相机控制（Camera3D）
  │   ├── GodotDemo2D.cs              2D 演示（Node2D + 矩形裁剪）
  │   ├── GodotCamera2D.cs            2D 相机控制（Camera2D）
  │   ├── GodotLoadHandler.cs         3D ILoadHandler 实现
  │   ├── GodotSpriteFactory.cs       2D IObjectFactory 实现
  │   ├── GodotDebugDraw.cs           3D IDebugDraw 桩
  │   └── GodotDebugDraw2D.cs         2D IDebugDraw 实现
  ├── Scenes/
  │   ├── Main.tscn                   3D 演示场景
  │   └── Main2D.tscn                 2D 演示场景
  └── QuadTreeMap_Demo_Godot.csproj
```

## 快速开始

### 前置要求

- .NET 8 SDK
- Godot 4.6+（.NET 版本，用于 Godot 演示）

### 引用库

```xml
<!-- Godot .csproj -->
<ItemGroup>
  <ProjectReference Include="..\QuadTreeMap.Core\QuadTreeMap.Core.csproj" />
  <ProjectReference Include="..\QuadTreeMap.LoadHandler\QuadTreeMap.LoadHandler.csproj" />
</ItemGroup>
```

### 3D 场景（视锥体裁剪）

```csharp
using WCC.QuadTree.Core;

// 1. 创建四叉树
QBounds worldBounds = new QBounds(
    System.Numerics.Vector3.Zero,
    new System.Numerics.Vector3(2000, 200, 2000)
);
QuadTree tree = new QuadTree(worldBounds);
tree.LoadHandler = new MyLoadHandler(this);

// 2. 插入物体
for (int i = 0; i < 10000; i++)
{
    ObjData obj = new ObjData(
        resPath: null, uid: i,
        pos: new System.Numerics.Vector3(x, 0, z),
        rot: System.Numerics.Quaternion.Identity,
        scale: new System.Numerics.Vector3(1, 1, 1),
        size: new System.Numerics.Vector3(1, 1, 1)
    );
    tree.InsertObjData(obj);
}

// 3. 每帧更新视锥裁剪
public override void _Process(double delta)
{
    QFrustum frustum = BuildFrustum(GetViewport().GetCamera3D());
    tree.Inside(frustum);
}
```

### 2D 场景（矩形裁剪）

设置 `SplitPlane.XY` 让四叉树在 XY 平面划分：

```csharp
QuadTree tree = new QuadTree(new QBounds(
    System.Numerics.Vector3.Zero,
    new System.Numerics.Vector3(2000, 2000, 0)  // Z=0
));
tree.splitPlane = SplitPlane.XY;  // ← 在 XY 平面划分

// 每帧传入视口矩形
QBounds viewRect = new QBounds(
    new System.Numerics.Vector3(cameraPos.X, cameraPos.Y, 0),
    new System.Numerics.Vector3(viewportW, viewportH, 0)
);
tree.InsideRect(viewRect);
```

### 使用通用加载管理器

引擎只需实现 `IObjectFactory`，其余由 `LoadHandlerBase` 处理：

```csharp
// 引擎实现
public class MyFactory : IObjectFactory
{
    public object CreateObj(ObjData data) { /* 创建 */ }
    public void CreateObjAsync(ObjData data, Action<object> onCreated) { /* 异步创建 */ }
    public void DestroyObj(object instance) { /* 销毁 */ }
}

// 使用
var handler = new LoadHandlerBase(new MyFactory());
tree.LoadHandler = handler;

// 每帧调用
handler.Tick(delta);
```

## 核心概念

| 概念 | 说明 |
|---|---|
| **空间分割** | 四叉树递归划分为子区域，物体插入对应节点 |
| **坐标平面** | 可选 XZ（3D 默认）/ XY（2D）/ YZ，通过 `SplitPlane` 指定 |
| **视锥体裁剪** | 3D：`Inside(QFrustum)` 计算相机视锥体，只加载可见节点 |
| **矩形裁剪** | 2D：`InsideRect(QBounds)` 用 AABB 矩形判断可见性 |
| **引用计数** | 物体可被多个节点引用，归零后才卸载 |
| **延迟卸载** | `LoadHandlerBase` 内置 5s 缓冲，避免频繁加载/卸载抖动 |
| **静态区域** | `UnitInside(Vector3[])` 强制加载指定位置所在节点 |
| **调试绘制** | `DrawBound(IDebugDraw)` 绘制树结构（红=视野内，蓝=有物体，绿=空） |
| **叶子调试** | `CollectLeafDebug()` 收集所有叶子节点状态用于自定义绘制 |

## 配置参数

| 参数 | 默认值 | 说明 |
|---|---|---|
| `maxDepth` | 5 | 最大递归深度 |
| `maxChildCount` | 4 | 子节点数量 |
| `viewRatio` | 1 | 视锥/矩形缩放比例，>1 扩大加载范围 |
| `splitPlane` | XZ | 划分坐标平面 |
| `UnloadInterval` | 5.0s | 延迟卸载等待时间 |

## 演示场景

| 场景 | 文件 | 说明 |
|---|---|---|
| 3D | `Scenes/Main.tscn` | 10000 个随机物体，Camera3D 视锥体裁剪 |
| 2D | `Scenes/Main2D.tscn` | 10000 个随机 Sprite2D，Camera2D 矩形裁剪，带调试绘制 |