OniSplit/Akira/QuadtreeNode.cs

using System;
using System.Collections.Generic;

namespace Oni.Akira
{
    internal class QuadtreeNode
    {
        public const int ChildCount = 4;
        private QuadtreeNode[] nodes = new QuadtreeNode[ChildCount];
        private OctreeNode[] leafs = new OctreeNode[ChildCount];
        private readonly Vector3 center;
        private readonly float size;
        private readonly OctreeNode.Face face;
        private int index;

        public enum Axis
        {
            U = 0,
            V = 1
        }

        public struct ChildPosition
        {
            private readonly int index;

            public ChildPosition(int index)
            {
                this.index = index;
            }

            public int Index => index;

            public int U => this[Axis.U];
            public int V => this[Axis.V];

            public int this[Axis axis] => ((index >> (int)axis) & 1);

            public static IEnumerable<ChildPosition> All
            {
                get
                {
                    for (int i = 0; i < 4; i++)
                        yield return new ChildPosition(i);
                }
            }
        }

        public QuadtreeNode(Vector3 center, float size, OctreeNode.Face face)
        {
            this.center = center;
            this.size = size;
            this.face = face;
        }

        public QuadtreeNode[] Nodes => nodes;
        public OctreeNode[] Leafs => leafs;

        public void Build(OctreeNode adjacentNode)
        {
            float childSize = size * 0.5f;

            foreach (var position in ChildPosition.All)
            {
                var childCenter = GetChildNodeCenter(position);
                var adjacentCenter = OctreeNode.MovePoint(childCenter, face, childSize * 0.5f);
                var childAdjacentNode = adjacentNode.FindLargestOrEqual(adjacentCenter, childSize);

                if (childAdjacentNode.IsLeaf)
                {
                    leafs[position.Index] = childAdjacentNode;
                }
                else
                {
                    var child = new QuadtreeNode(childCenter, childSize, face);
                    child.Build(childAdjacentNode);
                    nodes[position.Index] = child;
                }
            }
        }

        private Vector3 GetChildNodeCenter(ChildPosition position)
        {
            float offset = size * 0.25f;

            float u = (position.U == 0) ? -offset : offset;
            float v = (position.V == 0) ? -offset : offset;

            var result = center;

            if (face.Axis == OctreeNode.Axis.X)
            {
                result.Y += u;
                result.Z += v;
            }
            else if (face.Axis == OctreeNode.Axis.Y)
            {
                result.X += u;
                result.Z += v;
            }
            else
            {
                result.X += u;
                result.Y += v;
            }

            return result;
        }

        public int Index => index;

        public List<QuadtreeNode> GetDfsList()
        {
            var list = new List<QuadtreeNode>();

            DfsTraversal(node => {
                node.index = list.Count;
                list.Add(node);
            });

            return list;
        }

        private void DfsTraversal(Action<QuadtreeNode> action)
        {
            action(this);

            foreach (var node in nodes)
            {
                if (node != null)
                    node.DfsTraversal(action);
            }
        }
    }
}
Revision:	1114
Committed:	Wed Jan 22 14:08:57 2020 UTC (5 years, 8 months ago) by iritscen
File size:	3710 byte(s)
Log Message:	Adding OniSplit source code (v0.9.99.0). Many thanks to Neo for all his work over the years.
#	Content
1	using System;
2	using System.Collections.Generic;
3
4	namespace Oni.Akira
5	{
6	internal class QuadtreeNode
7	{
8	public const int ChildCount = 4;
9	private QuadtreeNode[] nodes = new QuadtreeNode[ChildCount];
10	private OctreeNode[] leafs = new OctreeNode[ChildCount];
11	private readonly Vector3 center;
12	private readonly float size;
13	private readonly OctreeNode.Face face;
14	private int index;
15
16	public enum Axis
17	{
18	U = 0,
19	V = 1
20	}
21
22	public struct ChildPosition
23	{
24	private readonly int index;
25
26	public ChildPosition(int index)
27	{
28	this.index = index;
29	}
30
31	public int Index => index;
32
33	public int U => this[Axis.U];
34	public int V => this[Axis.V];
35
36	public int this[Axis axis] => ((index >> (int)axis) & 1);
37
38	public static IEnumerable<ChildPosition> All
39	{
40	get
41	{
42	for (int i = 0; i < 4; i++)
43	yield return new ChildPosition(i);
44	}
45	}
46	}
47
48	public QuadtreeNode(Vector3 center, float size, OctreeNode.Face face)
49	{
50	this.center = center;
51	this.size = size;
52	this.face = face;
53	}
54
55	public QuadtreeNode[] Nodes => nodes;
56	public OctreeNode[] Leafs => leafs;
57
58	public void Build(OctreeNode adjacentNode)
59	{
60	float childSize = size * 0.5f;
61
62	foreach (var position in ChildPosition.All)
63	{
64	var childCenter = GetChildNodeCenter(position);
65	var adjacentCenter = OctreeNode.MovePoint(childCenter, face, childSize * 0.5f);
66	var childAdjacentNode = adjacentNode.FindLargestOrEqual(adjacentCenter, childSize);
67
68	if (childAdjacentNode.IsLeaf)
69	{
70	leafs[position.Index] = childAdjacentNode;
71	}
72	else
73	{
74	var child = new QuadtreeNode(childCenter, childSize, face);
75	child.Build(childAdjacentNode);
76	nodes[position.Index] = child;
77	}
78	}
79	}
80
81	private Vector3 GetChildNodeCenter(ChildPosition position)
82	{
83	float offset = size * 0.25f;
84
85	float u = (position.U == 0) ? -offset : offset;
86	float v = (position.V == 0) ? -offset : offset;
87
88	var result = center;
89
90	if (face.Axis == OctreeNode.Axis.X)
91	{
92	result.Y += u;
93	result.Z += v;
94	}
95	else if (face.Axis == OctreeNode.Axis.Y)
96	{
97	result.X += u;
98	result.Z += v;
99	}
100	else
101	{
102	result.X += u;
103	result.Y += v;
104	}
105
106	return result;
107	}
108
109	public int Index => index;
110
111	public List<QuadtreeNode> GetDfsList()
112	{
113	var list = new List<QuadtreeNode>();
114
115	DfsTraversal(node => {
116	node.index = list.Count;
117	list.Add(node);
118	});
119
120	return list;
121	}
122
123	private void DfsTraversal(Action<QuadtreeNode> action)
124	{
125	action(this);
126
127	foreach (var node in nodes)
128	{
129	if (node != null)
130	node.DfsTraversal(action);
131	}
132	}
133	}
134	}