import { vec3 , ReadonlyVec3 , ReadonlyMat4 , vec4 , ReadonlyVec4 , mat4 } from "gl-matrix" ; import { IS_DEPTH_REVERSED } from "./gfx/helpers/ReversedDepthHelpers" ; import { GfxClipSpaceNearZ } from "./gfx/platform/GfxPlatform" ; import { nArray } from "./util" ; const scratchVec4 = vec4 . create ( ) ; const scratchMatrix = mat4 . create ( ) ; export class Plane { private static scratchVec3 : vec3 [ ] = nArray ( 2 , ( ) => vec3 . create ( ) ) ; public n = vec3 . create ( ) ; constructor ( x = 0 , y = 0 , z = 0 , public d = 0 ) { vec3 . set ( this . n , x , y , z ) ; } public set ( n , d ) { vec3 . copy ( this . n , n ) ; this . d = d ; } public copy ( o ) { this . set ( o . n , o . d ) ; } public negate ( ) { vec3 . negate ( this . n , this . n ) ; this . d *= - 1 ; } public distance ( x , y , z ) { const nx = this . n [ 0 ] , ny = this . n [ 1 ] , nz = this . n [ 2 ] ; const dot = x * nx + y * ny + z * nz ; return dot + this . d ; } public distanceVec3 ( p ) { return vec3 . dot ( p , this . n ) + this . d ; } public set4Unnormalized ( nx , ny , nz , d ) { const h = Math . hypot ( nx , ny , nz ) ; vec3 . set ( this . n , nx / h , ny / h , nz / h ) ; this . d = d / h ; } public getVec4v ( dst ) { vec4 . set ( dst , this . n [ 0 ] , this . n [ 1 ] , this . n [ 2 ] , this . d ) ; } public setVec4v ( v ) { vec3 . set ( this . n , v [ 0 ] , v [ 1 ] , v [ 2 ] ) ; this . d = v [ 3 ] ; } public setTri ( p0 , p1 , p2 ) { const scratch = Plane . scratchVec3 ; vec3 . sub ( scratch [ 0 ] , p1 , p0 ) ; vec3 . sub ( scratch [ 1 ] , p2 , p0 ) ; vec3 . cross ( this . n , scratch [ 0 ] , scratch [ 1 ] ) ; vec3 . normalize ( this . n , this . n ) ; this . d = - vec3 . dot ( this . n , p0 ) ; } public intersectLine ( dst , p0 , dir ) { const t = - ( vec3 . dot ( this . n , p0 ) + this . d ) / vec3 . dot ( this . n , dir ) ; vec3 . scaleAndAdd ( dst , p0 , dir , t ) ; } public intersectLineSegment ( dst , p0 , p1 ) { const dir = Plane . scratchVec3 [ 1 ] ; vec3 . sub ( dir , p1 , p0 ) ; this . intersectLine ( dst , p0 , dir ) ; } public transform ( mtx ) { this . getVec4v ( scratchVec4 ) ; mat4 . invert ( scratchMatrix , mtx ) ; mat4 . transpose ( scratchMatrix , scratchMatrix ) ; vec4 . transformMat4 ( scratchVec4 , scratchVec4 , scratchMatrix ) ; this . setVec4v ( scratchVec4 ) ; } } const scratchVec3a = vec3 . create ( ) ; const scratchVec3b = vec3 . create ( ) ; const scratchVec3c = vec3 . create ( ) ; const scratchVec3d = vec3 . create ( ) ; export class AABB { constructor ( public minX = Infinity , public minY = Infinity , public minZ = Infinity , public maxX = - Infinity , public maxY = - Infinity , public maxZ = - Infinity ) { } public transform ( src , m ) { const srcMin = scratchVec3a , srcMax = scratchVec3b ; vec3 . set ( srcMin , src . minX , src . minY , src . minZ ) ; vec3 . set ( srcMax , src . maxX , src . maxY , src . maxZ ) ; const dstMin = scratchVec3c , dstMax = scratchVec3d ; vec3 . set ( dstMin , m [ 12 ] , m [ 13 ] , m [ 14 ] ) ; vec3 . set ( dstMax , m [ 12 ] , m [ 13 ] , m [ 14 ] ) ; for ( let i = 0 ; i < 3 ; i ++ ) { for ( let j = 0 ; j < 3 ; j ++ ) { const a = m [ i * 4 + j ] * srcMin [ i ] ; const b = m [ i * 4 + j ] * srcMax [ i ] ; dstMin [ j ] += Math . min ( a , b ) ; dstMax [ j ] += Math . max ( a , b ) ; } } this . minX = dstMin [ 0 ] ; this . minY = dstMin [ 1 ] ; this . minZ = dstMin [ 2 ] ; this . maxX = dstMax [ 0 ] ; this . maxY = dstMax [ 1 ] ; this . maxZ = dstMax [ 2 ] ; } public set ( minX , minY , minZ , maxX , maxY , maxZ ) { this . minX = minX ; this . minY = minY ; this . minZ = minZ ; this . maxX = maxX ; this . maxY = maxY ; this . maxZ = maxZ ; } public reset ( ) { this . set ( Infinity , Infinity , Infinity , - Infinity , - Infinity , - Infinity ) ; } public copy ( other ) { this . set ( other . minX , other . minY , other . minZ , other . maxX , other . maxY , other . maxZ ) ; } public clone ( ) { const aabb = new AABB ( ) ; aabb . copy ( this ) ; return aabb ; } public setFromPoints ( points ) { this . minX = this . minY = this . minZ = Infinity ; this . maxX = this . maxY = this . maxZ = - Infinity ; for ( let i = 0 ; i < points . length ; i ++ ) { const p = points [ i ] ; this . minX = Math . min ( this . minX , p [ 0 ] ) ; this . minY = Math . min ( this . minY , p [ 1 ] ) ; this . minZ = Math . min ( this . minZ , p [ 2 ] ) ; this . maxX = Math . max ( this . maxX , p [ 0 ] ) ; this . maxY = Math . max ( this . maxY , p [ 1 ] ) ; this . maxZ = Math . max ( this . maxZ , p [ 2 ] ) ; } } public union ( a , b ) { this . minX = Math . min ( a . minX , b . minX ) ; this . minY = Math . min ( a . minY , b . minY ) ; this . minZ = Math . min ( a . minZ , b . minZ ) ; this . maxX = Math . max ( a . maxX , b . maxX ) ; this . maxY = Math . max ( a . maxY , b . maxY ) ; this . maxZ = Math . max ( a . maxZ , b . maxZ ) ; } public unionPoint ( v ) { let changed = false ; if ( v [ 0 ] < this . minX ) { this . minX = v [ 0 ] ; changed = true ; } if ( v [ 1 ] < this . minY ) { this . minY = v [ 1 ] ; changed = true ; } if ( v [ 2 ] < this . minZ ) { this . minZ = v [ 2 ] ; changed = true ; } if ( v [ 0 ] > this . maxX ) { this . maxX = v [ 0 ] ; changed = true ; } if ( v [ 1 ] > this . maxY ) { this . maxY = v [ 1 ] ; changed = true ; } if ( v [ 2 ] > this . maxZ ) { this . maxZ = v [ 2 ] ; changed = true ; } return changed ; } public static intersect ( a , b ) { return ! ( a . minX > b . maxX || b . minX > a . maxX || a . minY > b . maxY || b . minY > a . maxY || a . minZ > b . maxZ || b . minZ > a . maxZ ) ; } public containsPoint ( v ) { const pX = v [ 0 ] , pY = v [ 1 ] , pZ = v [ 2 ] ; return ! ( pX < this . minX || pX > this . maxX || pY < this . minY || pY > this . maxY || pZ < this . minZ || pZ > this . maxZ ) ; } public containsSphere ( v , rad ) { const pX = v [ 0 ] , pY = v [ 1 ] , pZ = v [ 2 ] ; return ! ( pX < this . minX - rad || pX > this . maxX + rad || pY < this . minY - rad || pY > this . maxY + rad || pZ < this . minZ - rad || pZ > this . maxZ + rad ) ; } public extents ( v ) { v [ 0 ] = Math . max ( ( this . maxX - this . minX ) / 2 , 0 ) ; v [ 1 ] = Math . max ( ( this . maxY - this . minY ) / 2 , 0 ) ; v [ 2 ] = Math . max ( ( this . maxZ - this . minZ ) / 2 , 0 ) ; } public diagonalLengthSquared ( ) { const dx = this . maxX - this . minX ; const dy = this . maxY - this . minY ; const dz = this . maxZ - this . minZ ; return dx * dx + dy * dy + dz * dz ; } public centerPoint ( v ) { v [ 0 ] = ( this . minX + this . maxX ) / 2 ; v [ 1 ] = ( this . minY + this . maxY ) / 2 ; v [ 2 ] = ( this . minZ + this . maxZ ) / 2 ; } public cornerPoint ( dst , i ) { if ( i === 0 ) vec3 . set ( dst , this . minX , this . minY , this . minZ ) ; else if ( i === 1 ) vec3 . set ( dst , this . maxX , this . minY , this . minZ ) ; else if ( i === 2 ) vec3 . set ( dst , this . minX , this . maxY , this . minZ ) ; else if ( i === 3 ) vec3 . set ( dst , this . maxX , this . maxY , this . minZ ) ; else if ( i === 4 ) vec3 . set ( dst , this . minX , this . minY , this . maxZ ) ; else if ( i === 5 ) vec3 . set ( dst , this . maxX , this . minY , this . maxZ ) ; else if ( i === 6 ) vec3 . set ( dst , this . minX , this . maxY , this . maxZ ) ; else if ( i === 7 ) vec3 . set ( dst , this . maxX , this . maxY , this . maxZ ) ; else throw "whoops" ; } public boundingSphereRadius ( ) { const extX = ( this . maxX - this . minX ) ; const extY = ( this . maxY - this . minY ) ; const extZ = ( this . maxZ - this . minZ ) ; const chord = Math . hypot ( extX , extY , extZ ) ; return chord / 2 ; } public maxCornerRadius ( ) { const x = Math . max ( this . maxX , - this . minX ) ; const y = Math . max ( this . maxY , - this . minY ) ; const z = Math . max ( this . maxZ , - this . minZ ) ; return Math . sqrt ( x * x + y * y + z * z ) ; } public isEmpty ( ) { this . extents ( scratchVec3a ) ; return scratchVec3a [ 0 ] === 0 && scratchVec3a [ 1 ] === 0 && scratchVec3a [ 2 ] === 0 ; } } class FrustumVisualizer { private canvas : HTMLCanvasElement ; public ctx : CanvasRenderingContext2D ; public scale : number = 1 / 100000 ; constructor ( ) { this . canvas = document . createElement ( 'canvas' ) ; this . canvas . width = 1080 ; this . canvas . height = 768 ; document . body . appendChild ( this . canvas ) ; this . canvas . style . position = 'absolute' ; this . canvas . style . top = '0' ; this . canvas . style . left = '0' ; this . canvas . style . opacity = '0.5' ; this . canvas . style . pointerEvents = 'none' ; this . ctx = this . canvas . getContext ( '2d' ) ! ; } public newFrame ( ) { this . ctx . fillStyle = 'white' ; this . ctx . save ( ) ; this . ctx . setTransform ( 1 , 0 , 0 , 1 , 0 , 0 ) ; this . ctx . fillRect ( 0 , 0 , this . canvas . width , this . canvas . height ) ; this . ctx . restore ( ) ; } public dsx ( n ) { return ( ( n * this . scale ) + 0.5 ) * this . canvas . width ; } public dsy ( n ) { return ( ( n * this . scale ) + 0.5 ) * this . canvas . height ; } public daabb ( aabb ) { const x1 = this . dsx ( aabb . minX ) ; const y1 = this . dsy ( aabb . minZ ) ; const x2 = this . dsx ( aabb . maxX ) ; const y2 = this . dsy ( aabb . maxZ ) ; this . ctx . strokeRect ( x1 , y1 , x2 - x1 , y2 - y1 ) ; } public dsph ( v , rad ) { const xc = this . dsx ( v [ 0 ] ) ; const yc = this . dsy ( v [ 2 ] ) ; this . ctx . beginPath ( ) ; this . ctx . ellipse ( xc , yc , rad * this . scale * this . canvas . width , rad * this . scale * this . canvas . height , 0 , 0 , Math . PI * 2 ) ; this . ctx . closePath ( ) ; this . ctx . stroke ( ) ; } } export enum IntersectionState { FULLY_INSIDE , FULLY_OUTSIDE , PARTIAL_INTERSECT } export class Frustum { public planes : Plane [ ] = nArray ( 6 , ( ) => new Plane ( ) ) ; private visualizer : FrustumVisualizer | null = null ; public makeVisualizer ( ) { if ( this . visualizer === null ) this . visualizer = new FrustumVisualizer ( ) ; return this . visualizer ; } private vizp ( planes , color ) { if ( this . visualizer ) { const ctx = this . visualizer . ctx ; ctx . strokeStyle = color ; ctx . beginPath ( ) ; const drawLine = ( x1 , z1 , x2 , z2 ) => { ctx . moveTo ( this . visualizer ! . dsx ( x1 ) , this . visualizer ! . dsy ( z1 ) ) ; ctx . lineTo ( this . visualizer ! . dsx ( x2 ) , this . visualizer ! . dsy ( z2 ) ) ; } ; const p0 = planes [ 0 ] , p1 = planes [ 1 ] , pn = planes [ 4 ] ; const i0 = ( p0 . n [ 2 ] * p1 . d - p0 . d * p1 . n [ 2 ] ) , i1 = ( p0 . d * p1 . n [ 0 ] - p0 . n [ 0 ] * p1 . d ) , i2 = ( p0 . n [ 0 ] * p1 . n [ 2 ] - p0 . n [ 2 ] * p1 . n [ 0 ] ) ; const ix = i0 / i2 , iz = i1 / i2 ; const G = 10 ; ctx . fillStyle = 'black' ; ctx . fillRect ( this . visualizer ! . dsx ( ix ) - G / 2 , this . visualizer ! . dsy ( iz ) - G / 2 , G , G ) ; const drawPlane = ( p ) => { const x1 = - 100000 , x2 = - x1 ; const z1 = - ( p . d + p . n [ 0 ] * x1 ) / p . n [ 2 ] ; const z2 = - ( p . d + p . n [ 0 ] * x2 ) / p . n [ 2 ] ; const dot = ( pn . n [ 0 ] * x1 + pn . n [ 2 ] * z1 ) ; const px = dot >= 0 ? x2 : x1 ; const pz = dot >= 0 ? z2 : z1 ; drawLine ( px , pz , ix , iz ) ; } ; drawPlane ( p0 ) ; drawPlane ( p1 ) ; ctx . closePath ( ) ; ctx . stroke ( ) ; } } public updateClipFrustum ( m , clipSpaceNearZ ) { this . planes [ 0 ] . set4Unnormalized ( - ( m [ 3 ] + m [ 0 ] ) , - ( m [ 7 ] + m [ 4 ] ) , - ( m [ 11 ] + m [ 8 ] ) , - ( m [ 15 ] + m [ 12 ] ) ) ; this . planes [ 1 ] . set4Unnormalized ( - ( m [ 3 ] - m [ 0 ] ) , - ( m [ 7 ] - m [ 4 ] ) , - ( m [ 11 ] - m [ 8 ] ) , - ( m [ 15 ] - m [ 12 ] ) ) ; this . planes [ 2 ] . set4Unnormalized ( - ( m [ 3 ] + m [ 1 ] ) , - ( m [ 7 ] + m [ 5 ] ) , - ( m [ 11 ] + m [ 9 ] ) , - ( m [ 15 ] + m [ 13 ] ) ) ; this . planes [ 3 ] . set4Unnormalized ( - ( m [ 3 ] - m [ 1 ] ) , - ( m [ 7 ] - m [ 5 ] ) , - ( m [ 11 ] - m [ 9 ] ) , - ( m [ 15 ] - m [ 13 ] ) ) ; if ( clipSpaceNearZ === GfxClipSpaceNearZ . NegativeOne ) { this . planes [ 4 ] . set4Unnormalized ( - ( m [ 3 ] + m [ 2 ] ) , - ( m [ 7 ] + m [ 6 ] ) , - ( m [ 11 ] + m [ 10 ] ) , - ( m [ 15 ] + m [ 14 ] ) ) ; } else if ( clipSpaceNearZ === GfxClipSpaceNearZ . Zero ) { this . planes [ 4 ] . set4Unnormalized ( - ( m [ 2 ] ) , - ( m [ 6 ] ) , - ( m [ 10 ] ) , - ( m [ 14 ] ) ) ; } this . planes [ 5 ] . set4Unnormalized ( - ( m [ 3 ] - m [ 2 ] ) , - ( m [ 7 ] - m [ 6 ] ) , - ( m [ 11 ] - m [ 10 ] ) , - ( m [ 15 ] - m [ 14 ] ) ) ; if ( IS_DEPTH_REVERSED ) { this . planes [ 4 ] . getVec4v ( scratchVec4 ) ; this . planes [ 4 ] . copy ( this . planes [ 5 ] ) ; this . planes [ 5 ] . setVec4v ( scratchVec4 ) ; } this . vizp ( this . planes , 'green' ) ; } public _intersect ( aabb ) { let ret = IntersectionState . FULLY_INSIDE ; for ( let i = 0 ; i < 6 ; i ++ ) { const plane = this . planes [ i ] ; const px = plane . n [ 0 ] >= 0 ? aabb . minX : aabb . maxX ; const py = plane . n [ 1 ] >= 0 ? aabb . minY : aabb . maxY ; const pz = plane . n [ 2 ] >= 0 ? aabb . minZ : aabb . maxZ ; if ( plane . distance ( px , py , pz ) > 0 ) return IntersectionState . FULLY_OUTSIDE ; const fx = plane . n [ 0 ] >= 0 ? aabb . maxX : aabb . minX ; const fy = plane . n [ 1 ] >= 0 ? aabb . maxY : aabb . minY ; const fz = plane . n [ 2 ] >= 0 ? aabb . maxZ : aabb . minZ ; if ( plane . distance ( fx , fy , fz ) > 0 ) ret = IntersectionState . PARTIAL_INTERSECT ; } return ret ; } public intersect ( aabb ) { const res = this . _intersect ( aabb ) ; if ( this . visualizer ) { const ctx = this . visualizer . ctx ; ctx . strokeStyle = res === IntersectionState . FULLY_INSIDE ? 'black' : res === IntersectionState . FULLY_OUTSIDE ? 'red' : 'cyan' ; this . visualizer . daabb ( aabb ) ; } return res ; } public contains ( aabb ) { return this . intersect ( aabb ) !== IntersectionState . FULLY_OUTSIDE ; } private _intersectSphere ( v , radius ) { let res = IntersectionState . FULLY_INSIDE ; for ( let i = 0 ; i < 6 ; i ++ ) { const dist = this . planes [ i ] . distance ( v [ 0 ] , v [ 1 ] , v [ 2 ] ) ; if ( dist > radius ) return IntersectionState . FULLY_OUTSIDE ; else if ( dist > - radius ) res = IntersectionState . PARTIAL_INTERSECT ; } return res ; } public intersectSphere ( v , radius ) { const res = this . _intersectSphere ( v , radius ) ; if ( this . visualizer ) { const ctx = this . visualizer . ctx ; ctx . strokeStyle = res === IntersectionState . FULLY_INSIDE ? 'black' : res === IntersectionState . FULLY_OUTSIDE ? 'red' : 'cyan' ; this . visualizer . dsph ( v , radius ) ; } return res ; } public containsSphere ( v , radius ) { return this . intersectSphere ( v , radius ) !== IntersectionState . FULLY_OUTSIDE ; } public containsPoint ( v ) { for ( let i = 0 ; i < 6 ; i ++ ) if ( this . planes [ i ] . distance ( v [ 0 ] , v [ 1 ] , v [ 2 ] ) > 0 ) return false ; return true ; } public newFrame ( ) { if ( this . visualizer ) this . visualizer . newFrame ( ) ; } } /**
 * Computes the squared distance from a point {@param v} to the AABB {@param aabb}.
 * Will be 0 if the point is inside the AABB. Note that this is *not* the distance
 * to the the AABB's center point.
 */ export function squaredDistanceFromPointToAABB ( v , aabb ) { const pX = v [ 0 ] , pY = v [ 1 ] , pZ = v [ 2 ] ; let sqDist = 0 ; if ( pX < aabb . minX ) sqDist += ( aabb . minX - pX ) ** 2.0 ; else if ( pX > aabb . maxX ) sqDist += ( pX - aabb . maxX ) ** 2.0 ; if ( pY < aabb . minY ) sqDist += ( aabb . minY - pY ) ** 2.0 ; else if ( pY > aabb . maxY ) sqDist += ( pY - aabb . maxY ) ** 2.0 ; if ( pZ < aabb . minZ ) sqDist += ( aabb . minZ - pZ ) ** 2.0 ; else if ( pZ > aabb . maxZ ) sqDist += ( pZ - aabb . maxZ ) ** 2.0 ; return sqDist ; }