第1章 四叉树与八叉树

从递归正交分割、复杂度与构建出发，覆盖高度场、等值面、射线投射以及3D和5D八叉树。

先做预测

先预测结果，再观察结构变化并解释偏差。移动采样点靠近单元边界并逐渐提高高度场频率，先预测节点数、叶深、射线访问顺序和等值面裂缝如何变化。再比较固定深度与误差驱动细分，判断何时稀疏场景仍会产生大量空节点。 本页用、、、、建立从对象、表示、查询到证书的完整链路。

第一版权威目录定位

本页一一对应Elmar Langetepe与Gabriel Zachmann在A K Peters出版的2006年第一版《Geometric Data Structures for Computer Graphics》第1章 四叉树与八叉树。出版社页面确认第一版、两位作者、362页和正式10章目录；作者所在研究组同时给出原书信息、ISBN 9781568812359、目录以及第7章材料。

原书小节覆盖

  1. 1.1 Definition
  2. 1.2 Complexity and Construction
  3. 1.3 Height Field Visualization
  4. 1.4 Isosurface Generation
  5. 1.5 Ray Shooting
  6. 1.6 3D Octree
  7. 1.7 5D Octree

核心对象

  1. 四叉树：二维区域每次沿两个坐标轴等分为四个子区域的递归层次。
  2. 八叉树：三维空间每次等分为八个子体素的递归层次。
  3. Morton编码：把各坐标位交错后形成从根到叶的空间路径编码。
  4. 自适应细分：仅在误差或占用条件不满足的单元继续递归。
  5. 邻接平衡：约束相邻叶节点层级差，避免跨层查询和网格连接失控。

查询与表示契约

先固定数据域、维数、闭开边界、查询输出和数值语义。树高或节点数不是独立目标；只有候选完备、结果无重复、复杂度含输出规模且数值分支一致时，结构才算正确。

ℓh=L2h\ell_h=\frac{L}{2^h} N2D(h)=∑i=0h4i=4h+1−13N_{2D}(h)=\sum_{i=0}^{h}4^i=\frac{4^{h+1}-1}{3} c=2bx+byc=2b_x+b_y tenter≤texitt_{enter}\le t_{exit}

根方形在每层把边长减半，深度h的二维单元边长为L除以2的h次方，三维同理。点定位由每层坐标最高有效位决定；Morton编码把这些位交错，父子关系可由移位恢复。高度场可按投影误差细分，等值面生成要共享跨叶边界的顶点，射线则按进入参数从近到远访问子节点。 每个剪枝判断都应能回答两个问题：被排除的集合是什么，以及哪个不变量证明它不含答案。

可核查构建与查询

构建器先计算根包围盒，再递归分配非空或误差超阈值的子节点。查询器必须明确半开单元规则，保证边界点只属于一个叶；射线遍历使用参数区间剪枝。稀疏实现用哈希表保存Morton码，致密实现用连续节点池并比较内存。

def query_with_trace(root, request):
    stack, hits, trace = [root], [], []
    while stack:
        node = stack.pop()
        trace.append(node.id)
        if node.disjoint(request):
            continue
        if node.is_leaf:
            hits.extend(node.exact_matches(request))
        else:
            stack.extend(node.children)
    return sorted(set(hits)), trace

通用骨架必须由本章的具体不变量实例化：区域不相交、包围体不重叠、空邻域、证书未失效或静态块版本有效。不能把候选生成误写成最终答案，叶节点仍需执行本章定义的精确测试。

复杂度与工程取舍

复杂度报告分离构建、查询、更新、内存和输出规模。平均值之外记录P95与最坏样例；同时保存访问节点、候选对象和精确谓词次数，这样才能判断瓶颈来自树质量、数据分布还是数值回退。

metrics = {
    "build_ms": 0.0,
    "visited_nodes": 0,
    "candidates": 0,
    "exact_tests": 0,
    "update_ms": 0.0,
}
assert set(metrics) == {"build_ms", "visited_nodes", "candidates", "exact_tests", "update_ms"}

只在结果集合与基线一致后比较性能。构建更慢可能换来大量查询收益，更新更便宜也可能逐渐恶化结构；因此工作负载中的查询次数、更新比例和生命周期必须写入报告。

边界、退化与反例

所有点重合会把树推到最大深度；点正落在中线时若左右都接收会重复计数；相邻叶深度差过大会让等值面断裂。设置最大深度、最小单元和统一半开区间，并对跨层邻接做平衡或缝合。

audit = {
    "normal": "representative geometry",
    "boundary": "closed-open convention",
    "degenerate": "duplicate or co-located input",
    "baseline": "brute-force exact result",
}
assert all(audit.values())

图形学应用

高度场渲染用屏幕误差选择叶节点，射线投射保存节点进入和离开参数，等值面生成对每个叶计算符号配置。验收既比较像素或三角形结果，也检查树节点覆盖根域且叶域互不重叠。 应用层还要记录从世界坐标到结构坐标的变换，避免把坐标系错误误判为数据结构错误。

  1. 用五到十个对象手算结构，标出节点覆盖、邻接或证书。
  2. 执行一个正常查询和一个恰落在边界的查询，逐节点记录剪枝理由。
  3. 删除一个一般位置或静态假设，构造首个失败样例。
  4. 与穷举答案逐项比较，再扩大规模测构建、查询、更新和内存。

验收证书

验收包包含原始输入、结构参数、节点或图邻接、查询日志、候选集合、精确结果、复杂度计数和失败反例。使用半开区间和唯一子索引，另为根域最大边界保留显式闭合规则。 任何无法重放的截图或孤立耗时都不能替代证书。

常见误区

本章回顾

本页覆盖四叉树、八叉树、Morton编码、自适应细分、邻接平衡。掌握标准是能从查询契约选择表示，推导剪枝或邻近条件，实现构建与更新，并用精确基线、退化输入和复杂度计数形成可重放证书。

术语表

讨论

评论区加载中…