simsite/frontend/node_modules/three-stdlib/math/Octree.js

import { Box3, Vector3, Triangle, Plane, Line3, Sphere } from "three";
import { Capsule } from "./Capsule.js";
const _v1 = /* @__PURE__ */ new Vector3();
const _v2 = /* @__PURE__ */ new Vector3();
const _plane = /* @__PURE__ */ new Plane();
const _line1 = /* @__PURE__ */ new Line3();
const _line2 = /* @__PURE__ */ new Line3();
const _sphere = /* @__PURE__ */ new Sphere();
const _capsule = /* @__PURE__ */ new Capsule();
class Octree {
  constructor(box) {
    this.triangles = [];
    this.box = box;
    this.subTrees = [];
  }
  addTriangle(triangle) {
    if (!this.bounds)
      this.bounds = new Box3();
    this.bounds.min.x = Math.min(this.bounds.min.x, triangle.a.x, triangle.b.x, triangle.c.x);
    this.bounds.min.y = Math.min(this.bounds.min.y, triangle.a.y, triangle.b.y, triangle.c.y);
    this.bounds.min.z = Math.min(this.bounds.min.z, triangle.a.z, triangle.b.z, triangle.c.z);
    this.bounds.max.x = Math.max(this.bounds.max.x, triangle.a.x, triangle.b.x, triangle.c.x);
    this.bounds.max.y = Math.max(this.bounds.max.y, triangle.a.y, triangle.b.y, triangle.c.y);
    this.bounds.max.z = Math.max(this.bounds.max.z, triangle.a.z, triangle.b.z, triangle.c.z);
    this.triangles.push(triangle);
    return this;
  }
  calcBox() {
    this.box = this.bounds.clone();
    this.box.min.x -= 0.01;
    this.box.min.y -= 0.01;
    this.box.min.z -= 0.01;
    return this;
  }
  split(level) {
    if (!this.box)
      return;
    const subTrees = [];
    const halfsize = _v2.copy(this.box.max).sub(this.box.min).multiplyScalar(0.5);
    for (let x = 0; x < 2; x++) {
      for (let y = 0; y < 2; y++) {
        for (let z = 0; z < 2; z++) {
          const box = new Box3();
          const v = _v1.set(x, y, z);
          box.min.copy(this.box.min).add(v.multiply(halfsize));
          box.max.copy(box.min).add(halfsize);
          subTrees.push(new Octree(box));
        }
      }
    }
    let triangle;
    while (triangle = this.triangles.pop()) {
      for (let i = 0; i < subTrees.length; i++) {
        if (subTrees[i].box.intersectsTriangle(triangle)) {
          subTrees[i].triangles.push(triangle);
        }
      }
    }
    for (let i = 0; i < subTrees.length; i++) {
      const len = subTrees[i].triangles.length;
      if (len > 8 && level < 16) {
        subTrees[i].split(level + 1);
      }
      if (len !== 0) {
        this.subTrees.push(subTrees[i]);
      }
    }
    return this;
  }
  build() {
    this.calcBox();
    this.split(0);
    return this;
  }
  getRayTriangles(ray, triangles) {
    for (let i = 0; i < this.subTrees.length; i++) {
      const subTree = this.subTrees[i];
      if (!ray.intersectsBox(subTree.box))
        continue;
      if (subTree.triangles.length > 0) {
        for (let j = 0; j < subTree.triangles.length; j++) {
          if (triangles.indexOf(subTree.triangles[j]) === -1)
            triangles.push(subTree.triangles[j]);
        }
      } else {
        subTree.getRayTriangles(ray, triangles);
      }
    }
    return triangles;
  }
  triangleCapsuleIntersect(capsule, triangle) {
    triangle.getPlane(_plane);
    const d1 = _plane.distanceToPoint(capsule.start) - capsule.radius;
    const d2 = _plane.distanceToPoint(capsule.end) - capsule.radius;
    if (d1 > 0 && d2 > 0 || d1 < -capsule.radius && d2 < -capsule.radius) {
      return false;
    }
    const delta = Math.abs(d1 / (Math.abs(d1) + Math.abs(d2)));
    const intersectPoint = _v1.copy(capsule.start).lerp(capsule.end, delta);
    if (triangle.containsPoint(intersectPoint)) {
      return { normal: _plane.normal.clone(), point: intersectPoint.clone(), depth: Math.abs(Math.min(d1, d2)) };
    }
    const r2 = capsule.radius * capsule.radius;
    const line1 = _line1.set(capsule.start, capsule.end);
    const lines = [
      [triangle.a, triangle.b],
      [triangle.b, triangle.c],
      [triangle.c, triangle.a]
    ];
    for (let i = 0; i < lines.length; i++) {
      const line2 = _line2.set(lines[i][0], lines[i][1]);
      const [point1, point2] = capsule.lineLineMinimumPoints(line1, line2);
      if (point1.distanceToSquared(point2) < r2) {
        return {
          normal: point1.clone().sub(point2).normalize(),
          point: point2.clone(),
          depth: capsule.radius - point1.distanceTo(point2)
        };
      }
    }
    return false;
  }
  triangleSphereIntersect(sphere, triangle) {
    triangle.getPlane(_plane);
    if (!sphere.intersectsPlane(_plane))
      return false;
    const depth = Math.abs(_plane.distanceToSphere(sphere));
    const r2 = sphere.radius * sphere.radius - depth * depth;
    const plainPoint = _plane.projectPoint(sphere.center, _v1);
    if (triangle.containsPoint(sphere.center)) {
      return {
        normal: _plane.normal.clone(),
        point: plainPoint.clone(),
        depth: Math.abs(_plane.distanceToSphere(sphere))
      };
    }
    const lines = [
      [triangle.a, triangle.b],
      [triangle.b, triangle.c],
      [triangle.c, triangle.a]
    ];
    for (let i = 0; i < lines.length; i++) {
      _line1.set(lines[i][0], lines[i][1]);
      _line1.closestPointToPoint(plainPoint, true, _v2);
      const d = _v2.distanceToSquared(sphere.center);
      if (d < r2) {
        return {
          normal: sphere.center.clone().sub(_v2).normalize(),
          point: _v2.clone(),
          depth: sphere.radius - Math.sqrt(d)
        };
      }
    }
    return false;
  }
  getSphereTriangles(sphere, triangles) {
    for (let i = 0; i < this.subTrees.length; i++) {
      const subTree = this.subTrees[i];
      if (!sphere.intersectsBox(subTree.box))
        continue;
      if (subTree.triangles.length > 0) {
        for (let j = 0; j < subTree.triangles.length; j++) {
          if (triangles.indexOf(subTree.triangles[j]) === -1)
            triangles.push(subTree.triangles[j]);
        }
      } else {
        subTree.getSphereTriangles(sphere, triangles);
      }
    }
  }
  getCapsuleTriangles(capsule, triangles) {
    for (let i = 0; i < this.subTrees.length; i++) {
      const subTree = this.subTrees[i];
      if (!capsule.intersectsBox(subTree.box))
        continue;
      if (subTree.triangles.length > 0) {
        for (let j = 0; j < subTree.triangles.length; j++) {
          if (triangles.indexOf(subTree.triangles[j]) === -1)
            triangles.push(subTree.triangles[j]);
        }
      } else {
        subTree.getCapsuleTriangles(capsule, triangles);
      }
    }
  }
  sphereIntersect(sphere) {
    _sphere.copy(sphere);
    const triangles = [];
    let result, hit = false;
    this.getSphereTriangles(sphere, triangles);
    for (let i = 0; i < triangles.length; i++) {
      if (result = this.triangleSphereIntersect(_sphere, triangles[i])) {
        hit = true;
        _sphere.center.add(result.normal.multiplyScalar(result.depth));
      }
    }
    if (hit) {
      const collisionVector = _sphere.center.clone().sub(sphere.center);
      const depth = collisionVector.length();
      return { normal: collisionVector.normalize(), depth };
    }
    return false;
  }
  capsuleIntersect(capsule) {
    _capsule.copy(capsule);
    const triangles = [];
    let result, hit = false;
    this.getCapsuleTriangles(_capsule, triangles);
    for (let i = 0; i < triangles.length; i++) {
      if (result = this.triangleCapsuleIntersect(_capsule, triangles[i])) {
        hit = true;
        _capsule.translate(result.normal.multiplyScalar(result.depth));
      }
    }
    if (hit) {
      const collisionVector = _capsule.getCenter(new Vector3()).sub(capsule.getCenter(_v1));
      const depth = collisionVector.length();
      return { normal: collisionVector.normalize(), depth };
    }
    return false;
  }
  rayIntersect(ray) {
    if (ray.direction.length() === 0)
      return;
    const triangles = [];
    let triangle, position, distance = 1e100;
    this.getRayTriangles(ray, triangles);
    for (let i = 0; i < triangles.length; i++) {
      const result = ray.intersectTriangle(triangles[i].a, triangles[i].b, triangles[i].c, true, _v1);
      if (result) {
        const newdistance = result.sub(ray.origin).length();
        if (distance > newdistance) {
          position = result.clone().add(ray.origin);
          distance = newdistance;
          triangle = triangles[i];
        }
      }
    }
    return distance < 1e100 ? { distance, triangle, position } : false;
  }
  fromGraphNode(group) {
    group.updateWorldMatrix(true, true);
    group.traverse((obj) => {
      if (obj.isMesh === true) {
        let geometry, isTemp = false;
        if (obj.geometry.index !== null) {
          isTemp = true;
          geometry = obj.geometry.toNonIndexed();
        } else {
          geometry = obj.geometry;
        }
        const positionAttribute = geometry.getAttribute("position");
        for (let i = 0; i < positionAttribute.count; i += 3) {
          const v1 = new Vector3().fromBufferAttribute(positionAttribute, i);
          const v2 = new Vector3().fromBufferAttribute(positionAttribute, i + 1);
          const v3 = new Vector3().fromBufferAttribute(positionAttribute, i + 2);
          v1.applyMatrix4(obj.matrixWorld);
          v2.applyMatrix4(obj.matrixWorld);
          v3.applyMatrix4(obj.matrixWorld);
          this.addTriangle(new Triangle(v1, v2, v3));
        }
        if (isTemp) {
          geometry.dispose();
        }
      }
    });
    this.build();
    return this;
  }
}
export {
  Octree
};
//# sourceMappingURL=Octree.js.map