Simple OcTree

OcTreeExample.java

package com.tvd12.example;

import java.util.Arrays;

import lombok.AllArgsConstructor;

public final class OcTreeExample {

    public static class OcTree {
        public final OcTreeNode root;

        public OcTree(GameObject[] worldObjects, float minNodeSize) {
            final Bounds bounds = new Bounds();
            for (GameObject go : worldObjects) {
                bounds.encapsulate(go.bounds);
            }
            root = new OcTreeNode(bounds, minNodeSize);
            addObjects(worldObjects);
        }

        public void addObjects(GameObject[] worldObjects) {
            for (GameObject go : worldObjects) {
                root.addObject(go);
            }
        }

        @Override
        public String toString() {
            return root.toString();
        }
    }

    public static class OcTreeNode {
        private final Bounds bounds;
        private final float minSize;
        private OcTreeNode[] children;
        private final Bounds[] childBounds = new Bounds[8];

        public OcTreeNode(Bounds b, float minNodeSize) {
            bounds = b;
            minSize = minNodeSize;

            final float quarter = bounds.size.y / 4.0f;
            final float childLength = bounds.size.y / 2;
            final Vec3 childSize = new Vec3(childLength, childLength, childLength);
            childBounds[0] = new Bounds(
                bounds.center.add(new Vec3(-quarter, quarter, -quarter)),
                childSize
            );
            childBounds[1] = new Bounds(
                bounds.center.add(new Vec3(quarter, quarter, -quarter)),
                childSize
            );
            childBounds[2] = new Bounds(
                bounds.center.add(new Vec3(-quarter, quarter, quarter)),
                childSize
            );
            childBounds[3] = new Bounds(
                bounds.center.add(new Vec3(quarter, quarter, quarter)),
                childSize
            );
            childBounds[4] = new Bounds(
                bounds.center.add(new Vec3(-quarter, -quarter, -quarter)),
                childSize
            );
            childBounds[5] = new Bounds(
                bounds.center.add(new Vec3(quarter, -quarter, -quarter)),
                childSize
            );
            childBounds[6] = new Bounds(
                bounds.center.add(new Vec3(-quarter, -quarter, quarter)),
                childSize
            );
            childBounds[7] = new Bounds(
                bounds.center.add(new Vec3(quarter, -quarter, -quarter)),
                childSize
            );
        }

        public void addObject(GameObject go) {
            divideAndAdd(go);
        }

        public void divideAndAdd(GameObject go) {
            if (bounds.size.y <= minSize) {
                return;
            }
            for (int i = 0 ; i < 8 ; ++i) {
                if (childBounds[i].intersects(go.bounds)) {
                    if (children == null) {
                        children = new OcTreeNode[8];
                    }
                    if (children[i] == null) {
                        children[i] = new OcTreeNode(childBounds[i], minSize);
                    }
                    children[i].divideAndAdd(go);
                }
            }
        }

        public void draw() {
            if (children != null) {
                for (int i = 0 ; i < 8 ; ++i) {
                    if (children[i] != null) {
                        children[i].draw();
                    }
                }
            }
        }

        @Override
        public String toString() {
            return '(' +
                   "bounds=" + bounds +
                   ", children=" + Arrays.toString(children) +
                   ')';
        }
    }

    @AllArgsConstructor
    public static class GameObject {
        public final Bounds bounds;
    }

    @AllArgsConstructor
    public static class Bounds {
        public Vec3 center;
        public Vec3 size;

        public Bounds() {
            this(Vec3.ZERO, Vec3.ZERO);
        }

        public void encapsulate(Bounds other) {
            final float minX = Math.min(
                center.x - size.x / 2,
                other.center.x - other.size.x / 2
            );
            final float minY = Math.min(
                center.y - size.y / 2,
                other.center.y - other.size.y / 2
            );
            final float minZ = Math.min(
                center.z - size.z / 2,
                other.center.z - other.size.z / 2
            );

            final float maxX = Math.max(
                center.x + size.x / 2,
                other.center.x + other.size.x / 2
            );
            final float maxY = Math.max(
                center.y + size.y / 2,
                other.center.y + other.size.y / 2
            );
            final float maxZ = Math.max(
                center.z + size.z / 2,
                other.center.z + other.size.z / 2
            );
            size = new Vec3(
                maxX - minX,
                maxY - minY,
                maxZ - minZ
            );
            center = new Vec3(
                minX + size.x / 2,
                minY + size.y / 2,
                minZ + size.z / 2
            );
        }

        public boolean intersects(Bounds other) {
            return !((other.center.x - size.x / 2 > center.x + size.x / 2)
                   || (other.center.x + size.x / 2 < center.x - size.x / 2)
                   || (other.center.y - size.y / 2 > center.y + size.y / 2)
                   || (other.center.y + size.y / 2 < center.y - size.y / 2)
                   || (other.center.z - size.z / 2 > center.z + size.z / 2)
                   || (other.center.z + size.z / 2 < center.z - size.z / 2));
        }

        @Override
        public String toString() {
            return center.toString();
        }
    }

    @AllArgsConstructor
    public static class Vec3 {
        public final float x;
        public final float y;
        public final float z;

        public static final Vec3 ZERO = new Vec3(0, 0 , 0);

        public Vec3 add(Vec3 other) {
            return new Vec3(
                x + other.x,
                y + other.y,
                z + other.z
            );
        }

        public Vec3 minus(Vec3 other) {
            return new Vec3(
                x - other.x,
                y - other.y,
                z - other.z
            );
        }

        @Override
        public String toString() {
            return "(" + x + ", " + y + ", " + z + ')';
        }
    }

    public static void main(String[] args) {
        final GameObject[] objects = {
            new GameObject(
                new Bounds(
                    new Vec3(0, 0, 0),
                    new Vec3(5, 5, 5)
                )
            ),
            new GameObject(
                new Bounds(
                    new Vec3(0, 0, 0),
                    new Vec3(20, 20, 20)
                )
            )
        };
        final OcTree ocTree = new OcTree(objects, 5);
        System.out.println(ocTree);
    }
}