import { Sphere } from "../../geometries/sphere.ts";
import type World from "../world.js";
import { AABB3d } from "./aabb3d.ts";
import type { Broadphase } from "./broadphase.ts";
/**
 * 8-octant spatial subdivision for `Camera3d` workloads. Sibling to
 * {@link QuadTree}: same public surface (`insert`, `remove`,
 * `retrieve`, `insertContainer`, `removeContainer`, `clear`,
 * `getIndex`, `isPrunable`, `hasChildren`), plus 3D-specific
 * region queries (`queryAABB`, `querySphere`). Selected
 * automatically by {@link World} when `world.sortOn === "depth"`
 * (which `Camera3d.defaultSortOn` sets on stage reset).
 *
 * Implementation notes:
 * - Bounding primitive is {@link AABB3d}; subnode bounds are POJOs
 *   with the same shape so node split is allocation-free apart from
 *   the eight literal objects (recycled via the global node pool).
 * - Per-frame clear/insert reuses both an octree-node pool
 *   (`OT_ARRAY`) and a result scratch (`_retrieveScratch`), so the
 *   steady state allocates nothing.
 * - Item z is read via `getAbsolutePosition()` — same convention as
 *   `Camera3d.isVisible` and the container depth sort, so the
 *   broadphase agrees with the renderer on which octant an item
 *   lives in even under nested transforms.
 */
/**
 * Minimal axis-aligned box shape consumed by `Octree`. Both
 * {@link AABB3d} and the POJOs emitted by `split` satisfy it
 * structurally.
 */
export interface OctRect {
    left: number;
    top: number;
    front: number;
    width: number;
    height: number;
    depth: number;
}
/**
 * Structural shape for an item inserted into the `Octree`. Same
 * shape as {@link QuadTree}'s item, with the addition that
 * `getAbsolutePosition()` is consulted for z (so nested transforms
 * still classify into the right octant).
 */
export interface OctreeItem {
    getBounds(): {
        left: number;
        top: number;
        width: number;
        height: number;
    };
    getAbsolutePosition?(): {
        x: number;
        y: number;
        z: number;
    };
    /**
     * 2D items expose Vector2d here (no z); 3D items expose Vector3d.
     * `getAbsolutePosition()` is the preferred path; this fallback
     * applies only to test doubles that skip `getAbsolutePosition`.
     */
    pos?: {
        x: number;
        y: number;
        z?: number;
    };
    isFloating?: boolean;
    isKinematic?: boolean;
    name?: string;
}
export type OctreeSortFn = (a: OctreeItem, b: OctreeItem) => number;
/**
 * Structural shape consumed by {@link Octree.queryFrustum} —
 * matches the shape exposed by `Frustum#planes` (see
 * `camera/frustum.ts`). Each plane satisfies `nx·x + ny·y + nz·z + d = 0`;
 * positive side is the interior of the frustum.
 */
export interface FrustumPlane {
    nx: number;
    ny: number;
    nz: number;
    d: number;
}
/**
 * an Octree implementation for 3D broadphase / spatial queries
 * under `Camera3d`.
 * @category Physics
 * @see World.broadphase
 */
export default class Octree implements Broadphase<OctreeItem> {
    world: World;
    bounds: OctRect | AABB3d;
    max_objects: number;
    max_levels: number;
    level: number;
    objects: OctreeItem[];
    nodes: Octree[];
    /**
     * see {@link QuadTree._subtreeCount} — same invariant.
     * @ignore
     */
    _subtreeCount: number;
    /**
     * see {@link QuadTree._retrieveScratch} — same contract.
     * @ignore
     */
    _retrieveScratch: OctreeItem[] | null;
    /**
     * @param world - the physic world this Octree belongs to
     * @param bounds - bounds of the node
     * @param [max_objects=4] - max objects a node can hold before splitting into 8 subnodes
     * @param [max_levels=4] - total max levels inside root Octree
     * @param [level] - depth level, required for subnodes
     */
    constructor(world: World, bounds: OctRect | AABB3d, max_objects?: number, max_levels?: number, level?: number);
    /**
     * Split this node into 8 octants. The naming mirrors the
     * QuadTree's `top` / `bottom` / `left` / `right` ordering, with
     * `near` (smaller z) before `far` (larger z) — matches the
     * Y-down + +Z forward convention from {@link Camera3d}.
     *
     * Octant index layout (used by `getIndex`):
     * ```
     *   near (lower z)        far (higher z)
     *   0: TR-near  1: TL-near   4: TR-far  5: TL-far
     *   3: BR-near  2: BL-near   7: BR-far  6: BL-far
     * ```
     */
    split(): void;
    /**
     * Classify an item into an octant.
     *
     * Returns -1 (keep at this level) when the item straddles ANY
     * midpoint OR sits outside this node's bounds entirely. The
     * out-of-bounds guard matters for `querySphere`: a sphere walks
     * subnodes by AABB overlap, so an item assigned to a subnode
     * whose bounds don't actually contain it would be invisible to
     * any query whose sphere doesn't overlap that subnode's AABB.
     * Items outside the root live at `root.objects` and are visited
     * by every query unconditionally — they degrade to a linear scan
     * but stay findable.
     * @param item - the object to classify
     * @returns octant index (0-7) or -1
     */
    getIndex(item: OctreeItem): number;
    /**
     * Insert the given object container into the node — recursively
     * walks `Container.getChildren()` and inserts each non-kinematic
     * leaf. Mirrors `QuadTree.insertContainer`.
     * @param container - group of objects to be added
     */
    insertContainer(container: ContainerLike): void;
    /**
     * Insert the given object into the node. If this node exceeds
     * `max_objects`, it splits and redistributes existing items into
     * subnodes. Mirrors `QuadTree.insert` — same subtree-count
     * accounting (bump on insert, no bump on redistribution).
     * @param item - object to be added
     */
    insert(item: OctreeItem): void;
    /**
     * Recursively remove the given container and its descendants from
     * the octree. Mirror of `QuadTree.removeContainer`.
     * @param container - group of objects to be removed
     */
    removeContainer(container: ContainerLikeOptional): void;
    /**
     * Return every object that could collide with the given item.
     * Re-entrancy contract identical to {@link QuadTree.retrieve}: the
     * default (scratch) path is allocation-free but cannot be safely
     * re-entered while iterating; pass an explicit `result` for safe
     * re-entry.
     * @param item - object to be checked against
     * @param [fn] - sorter applied to the returned array (root only)
     * @param [result] - caller-supplied result array (re-entrancy-safe)
     * @returns the collected candidates
     */
    retrieve(item: OctreeItem, fn?: OctreeSortFn, result?: OctreeItem[]): OctreeItem[];
    /**
     * Return every object whose subtree overlaps the given AABB.
     * Walks only octants whose bounds overlap the query — same
     * pruning shape as `retrieve(item)`, just driven by an explicit
     * region instead of an item's own bounds.
     *
     * Re-entrancy: same contract as {@link Octree.retrieve}. Pass an
     * explicit `result` for safe re-entry.
     * @param aabb - the AABB region to query
     * @param [result] - caller-supplied result array (re-entrancy-safe)
     * @returns the collected candidates
     */
    queryAABB(aabb: AABB3d, result?: OctreeItem[]): OctreeItem[];
    /**
     * Return every object whose containing octant overlaps the given
     * sphere. Replaces the hand-rolled O(n²) sphere-vs-sphere loops
     * common in arcade 3D code with a broadphase that scales.
     *
     * Two call shapes — both forms route to the same internal walk:
     * - `querySphere(cx, cy, cz, r, result?)` — loose floats
     * - `querySphere(sphere, result?)` — packaged {@link Sphere}
     *
     * Re-entrancy: same contract as {@link Octree.retrieve}.
     */
    querySphere(sphere: Sphere, result?: OctreeItem[]): OctreeItem[];
    /**
     * @param cx - sphere center x
     * @param cy - sphere center y
     * @param cz - sphere center z
     * @param r - sphere radius (must be ≥ 0; r=0 becomes a point query)
     * @param [result] - caller-supplied result array (re-entrancy-safe)
     * @returns the collected candidates
     */
    querySphere(cx: number, cy: number, cz: number, r: number, result?: OctreeItem[]): OctreeItem[];
    /**
     * Loose-floats implementation. Recursive subnode walks call this
     * directly to bypass the Sphere/floats dispatch on every node.
     * @ignore
     */
    _querySphereInternal(cx: number, cy: number, cz: number, r: number, result?: OctreeItem[]): OctreeItem[];
    /**
     * Return every object whose containing octant lies on the
     * positive side of all six frustum planes — i.e. every potential
     * candidate the frustum can see. Uses Gribb–Hartmann positive-
     * vertex pruning at each node: a subtree is skipped iff its
     * octant's most-positive corner along a plane normal is on that
     * plane's negative side (i.e. wholly outside the frustum).
     *
     * Mirrors {@link Frustum#intersectsSphere} on the renderer side —
     * use this as the broadphase pass before per-item narrow-phase
     * checks (sphere / OBB / etc.).
     *
     * Re-entrancy: same contract as {@link Octree.retrieve}. Pass an
     * explicit `result` for safe re-entry.
     * @param planes - 6 frustum planes (left, right, bottom, top, near, far) — `Frustum#planes` shape
     * @param [result] - caller-supplied result array (re-entrancy-safe)
     * @returns the collected candidates
     */
    queryFrustum(planes: FrustumPlane[], result?: OctreeItem[]): OctreeItem[];
    /**
     * Return every object whose containing octant the ray segment
     * `from + t·dir`, `t ∈ [0, tMax]`, crosses. Slab AABB test prunes
     * subtrees the ray misses entirely — much tighter than enclosing
     * the segment in a single AABB and walking `queryAABB`. The
     * candidates aren't sorted by hit-distance (front-to-back walk
     * would require a per-octant DDA step); callers that need
     * nearest-hit sort the narrow-phase results themselves.
     *
     * Re-entrancy: same contract as {@link Octree.retrieve}.
     * @param fromX - ray origin x
     * @param fromY - ray origin y
     * @param fromZ - ray origin z
     * @param dirX - ray direction x (`to - from`; not unit-length)
     * @param dirY - ray direction y
     * @param dirZ - ray direction z
     * @param tMax - maximum t along the ray (usually `1` if `dir = to - from`)
     * @param [result] - caller-supplied result array (re-entrancy-safe)
     * @returns the collected candidates
     */
    queryRay(fromX: number, fromY: number, fromZ: number, dirX: number, dirY: number, dirZ: number, tMax: number, result?: OctreeItem[]): OctreeItem[];
    /**
     * Remove the given item from the octree. Mirror of
     * `QuadTree.remove` — same stale-bounds fallback walk, same
     * collapse-on-removal pool recycling.
     * @param item - object to be removed
     * @returns true if the item was found and removed.
     */
    remove(item: OctreeItem): boolean;
    /**
     * @returns true if this subtree holds no items at any level.
     */
    isPrunable(): boolean;
    /**
     * @returns true if this node has any descendants (items in
     * subnodes, not at this level).
     */
    hasChildren(): boolean;
    /**
     * Empty this octree and recycle every subnode back to the pool.
     * If `bounds` is supplied, resizes the root bounds to match —
     * called by `World` on `LEVEL_LOADED` so the broadphase tracks
     * level boundary changes.
     * @param [bounds] - the new root bounds (resize on clear)
     */
    clear(bounds?: AABB3d): void;
    /**
     * Conservative outside-frustum test using the positive-vertex
     * method (Gribb–Hartmann). Returns true iff the octant is
     * provably outside ANY one plane, i.e. wholly outside the
     * frustum.
     * @ignore
     */
    _outsideFrustum(planes: FrustumPlane[]): boolean;
    /**
     * Slab method for ray–AABB intersection. Returns true iff the
     * segment `from + t·dir`, `t ∈ [0, tMax]`, intersects this
     * node's octant. dir components may be zero; the axis with zero
     * direction degenerates to a point-in-slab test.
     * @ignore
     */
    _overlapsRay(fromX: number, fromY: number, fromZ: number, dirX: number, dirY: number, dirZ: number, tMax: number): boolean;
    /** @ignore */
    _overlapsAABB(aabb: AABB3d): boolean;
    /** @ignore */
    _overlapsSphere(cx: number, cy: number, cz: number, r: number): boolean;
}
/**
 * Structural shape consumed by `insertContainer` / `removeContainer`
 * — captures only the fields the walk inspects. Same approach as
 * QuadTree. `getChildren` is optional because leaf renderables don't
 * have it; the recursive walk narrows via {@link hasGetChildren}.
 * @ignore
 */
interface ContainerOrChild extends OctreeItem {
    addChild?: (...args: unknown[]) => unknown;
    getChildren?: () => ContainerOrChild[];
}
/** @ignore */
type ContainerLike = {
    getChildren(): ContainerOrChild[];
};
/** @ignore */
type ContainerLikeOptional = {
    getChildren?(): ContainerOrChild[];
};
export {};
//# sourceMappingURL=octree.d.ts.map