【游戏算法】 - 八叉树

宋 游戏开发
  2021-05-07 22:16:55 2021-05-07 22:16:55 创建   2021-03-15 20:30:40 2021-03-15 20:30:40 更新      1.1k 字  6 分钟

八叉树

八叉树是一种树状数据结构，其每个节点代表一个立方体空间。根节点覆盖整个三维空间，每个内部节点最多有8个子节点，分别对应父节点立方体的8个子区域（通过中心点等分）。

八叉树其实和四叉树很类似，只不过更适合3D空间的计算。
八叉树

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <vector>
#include <array>

enum class Heuristic {
    DepthBased,
    CapacityBased,
    Hybrid
};

struct Point {
    float x, y, z;
};

struct BoundingBox {
    Point min;
    Point max;
    bool contains(const Point& p) const {
        return p.x >= min.x && p.x <= max.x &&
               p.y >= min.y && p.y <= max.y &&
               p.z >= min.z && p.z <= max.z;
    }
};

class OctreeNode {
private:
    BoundingBox bounds;
    std::vector<Point> points;
    std::array<OctreeNode*, 8> children;
    int depth;
    const int maxDepth;
    const int capacity;
    Heuristic heuristic;

    void subdivide() {
        // 简化实现：实际需计算8个子立方体
        for (int i = 0; i < 8; ++i) {
            children[i] = new OctreeNode(BoundingBox(), depth + 1, maxDepth, capacity, heuristic);
        }
    }

public:
    OctreeNode(BoundingBox bounds, int depth, int maxDepth, int capacity, Heuristic h)
        : bounds(bounds), depth(depth), maxDepth(maxDepth), capacity(capacity), heuristic(h) {
        children.fill(nullptr);
    }

    ~OctreeNode() {
        for (auto child : children) delete child;
    }

    void insert(const Point& point) {
        if (!bounds.contains(point)) return;

        if (children[0] == nullptr) {
            if ((heuristic == Heuristic::CapacityBased && points.size() < capacity) ||
                (heuristic == Heuristic::DepthBased && depth >= maxDepth) ||
                (heuristic == Heuristic::Hybrid && (depth >= maxDepth || points.size() < capacity))) {
                points.push_back(point);
            } else {
                subdivide();
                for (auto child : children) {
                    child->insert(point);
                }
            }
        } else {
            for (auto child : children) {
                child->insert(point);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using System;
using System.Collections.Generic;

public enum Heuristic {
    DepthBased,
    CapacityBased,
    Hybrid
}

public class Point {
    public float X { get; set; }
    public float Y { get; set; }
    public float Z { get; set; }
}

public class BoundingBox {
    public Point Min { get; set; }
    public Point Max { get; set; }
    
    public bool Contains(Point p) {
        return p.X >= Min.X && p.X <= Max.X &&
               p.Y >= Min.Y && p.Y <= Max.Y &&
               p.Z >= Min.Z && p.Z <= Max.Z;
    }
}

public class OctreeNode {
    private BoundingBox bounds;
    private List<Point> points;
    private OctreeNode[] children;
    private int depth;
    private readonly int maxDepth;
    private readonly int capacity;
    private readonly Heuristic heuristic;

    private void Subdivide() {
        // 简化实现：实际需计算8个子立方体
        children = new OctreeNode[8];
        for (int i = 0; i < 8; i++) {
            children[i] = new OctreeNode(new BoundingBox(), depth + 1, maxDepth, capacity, heuristic);
        }
    }

    public OctreeNode(BoundingBox bounds, int depth, int maxDepth, int capacity, Heuristic h) {
        this.bounds = bounds;
        this.depth = depth;
        this.maxDepth = maxDepth;
        this.capacity = capacity;
        this.heuristic = h;
        points = new List<Point>();
        children = null;
    }

    public void Insert(Point point) {
        if (!bounds.Contains(point)) return;

        if (children == null) {
            if ((heuristic == Heuristic.CapacityBased && points.Count < capacity) ||
                (heuristic == Heuristic.DepthBased && depth >= maxDepth) ||
                (heuristic == Heuristic.Hybrid && (depth >= maxDepth || points.Count < capacity))) {
                points.Add(point);
            } else {
                Subdivide();
                foreach (var child in children) {
                    child.Insert(point);
                }
            }
        } else {
            foreach (var child in children) {
                child.Insert(point);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
type Heuristic = 'DepthBased' | 'CapacityBased' | 'Hybrid';

interface Point {
    x: number;
    y: number;
    z: number;
}

interface BoundingBox {
    min: Point;
    max: Point;
    contains(p: Point): boolean;
}

class OctreeNode {
    private bounds: BoundingBox;
    private points: Point[];
    private children: OctreeNode[] | null;
    private depth: number;
    private readonly maxDepth: number;
    private readonly capacity: number;
    private readonly heuristic: Heuristic;

    constructor(
        bounds: BoundingBox,
        depth: number,
        maxDepth: number,
        capacity: number,
        heuristic: Heuristic
    ) {
        this.bounds = bounds;
        this.depth = depth;
        this.maxDepth = maxDepth;
        this.capacity = capacity;
        this.heuristic = heuristic;
        this.points = [];
        this.children = null;
    }

    private subdivide(): void {
        // 简化实现：实际需计算8个子立方体
        this.children = [];
        for (let i = 0; i < 8; i++) {
            this.children.push(
                new OctreeNode({ min: {x:0,y:0,z:0}, max: {x:0,y:0,z:0} }, 
                              this.depth + 1, this.maxDepth, this.capacity, this.heuristic)
            );
        }
    }

    public insert(point: Point): void {
        if (!this.bounds.contains(point)) return;

        if (this.children === null) {
            const shouldInsert = 
                (this.heuristic === 'CapacityBased' && this.points.length < this.capacity) ||
                (this.heuristic === 'DepthBased' && this.depth >= this.maxDepth) ||
                (this.heuristic === 'Hybrid' && (this.depth >= this.maxDepth || this.points.length < this.capacity));
                
            if (shouldInsert) {
                this.points.push(point);
            } else {
                this.subdivide();
                for (const child of this.children) {
                    child.insert(point);
                }
            }
        } else {
            for (const child of this.children) {
                child.insert(point);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
Heuristic = {
    DepthBased = 1,
    CapacityBased = 2,
    Hybrid = 3
}

Point = {}
function Point:new(x, y, z)
    local p = {x = x or 0, y = y or 0, z = z or 0}
    setmetatable(p, self)
    self.__index = self
    return p
end

BoundingBox = {}
function BoundingBox:new(min, max)
    local b = {min = min or Point:new(), max = max or Point:new()}
    setmetatable(b, self)
    self.__index = self
    return b
end

function BoundingBox:contains(p)
    return p.x >= self.min.x and p.x <= self.max.x and
           p.y >= self.min.y and p.y <= self.max.y and
           p.z >= self.min.z and p.z <= self.max.z
end

OctreeNode = {}
function OctreeNode:new(bounds, depth, maxDepth, capacity, heuristic)
    local node = {
        bounds = bounds,
        points = {},
        children = nil,
        depth = depth,
        maxDepth = maxDepth,
        capacity = capacity,
        heuristic = heuristic
    }
    setmetatable(node, self)
    self.__index = self
    return node
end

function OctreeNode:subdivide()
    -- 简化实现：实际需计算8个子立方体
    self.children = {}
    for i = 1, 8 do
        table.insert(self.children, 
            OctreeNode:new(BoundingBox:new(), 
                          self.depth + 1, 
                          self.maxDepth, 
                          self.capacity, 
                          self.heuristic))
    end
end

function OctreeNode:insert(point)
    if not self.bounds:contains(point) then return end

    if self.children == nil then
        local shouldInsert = false
        if self.heuristic == Heuristic.CapacityBased and #self.points < self.capacity then
            shouldInsert = true
        elseif self.heuristic == Heuristic.DepthBased and self.depth >= self.maxDepth then
            shouldInsert = true
        elseif self.heuristic == Heuristic.Hybrid and 
              (self.depth >= self.maxDepth or #self.points < self.capacity) then
            shouldInsert = true
        end

        if shouldInsert then
            table.insert(self.points, point)
        else
            self:subdivide()
            for _, child in ipairs(self.children) do
                child:insert(point)
            end
        end
    else
        for _, child in ipairs(self.children) do
            child:insert(point)
        end
    end
end
  • 标题: 【游戏算法】 - 八叉树
  • 作者: 宋
  • 创建于 : 2021-05-07 22:16:55
  • 更新于 : 2021-03-15 20:30:40
  • 链接: https://sxl-space.tk/2021/05/07/001_3D-Octree/
  • 版权声明: 版权所有 © 宋，禁止转载。
目录
【游戏算法】 - 八叉树
  1. 1. 八叉树
    1. 1.1. 代码实现