BGE/DepthSort
Alias: BGE.DepthSort
Static Methods
getEmptyScreenBounds(): ScreenBounds
A ScreenBounds that can never overlap anything - used whenever this object's own geometry can't be trusted to produce a meaningful AABB this frame (see MIN_VALID_HULL_POINTS).
Returns
getScreenBounds(
worldPoints: Array.<BGE.Math.Vector>,
rendererObj: BGE.Renderer,
): ScreenBounds
Projects a set of world-space points into a ScreenBounds: a screen-space AABB (via the renderer's own camera projection) and a depth range (via the camera's distanceFromCameraFront, the same function SceneObject.update() already calls once per object - here called once per bounding point instead).
Parameters
worldPoints(Array.<BGE.Math.Vector>)rendererObj(BGE.Renderer)
Returns
boundsOverlap(a: ScreenBounds, b: ScreenBounds): boolean
Whether two ScreenBounds overlap in both screen space and depth - the broad-phase overlap test. Deliberately loose (an AABB overexpands for a rotated/diagonal shape) - true here only means "worth the narrow-phase check", not "these objects actually need to interleave".
Parameters
a(ScreenBounds)b(ScreenBounds)
Returns
boolean
sortByMinXIncremental(
objects: Array.<BGE.SceneObject>,
previousOrderIds: Array.<string>,
screenBoundsById: object,
): dynamic
Reorders objects by ascending screen-space minX, using previousOrderIds (last frame's sorted order, by SceneObject.id) as the starting arrangement before sorting - most objects don't move far frame-to-frame, so this starting point is usually already nearly sorted, and an insertion sort on a nearly-sorted list is close to O(n) rather than the O(n log n) a fresh sort would cost every single frame. An id in previousOrderIds with no matching object this frame is silently skipped (the object was removed, disabled, or culled out of the candidate set); an object with no matching id in previousOrderIds (new this frame, or the very first frame) is appended at the end before sorting, so it still ends up in the right place, just at typical fresh-object cost.
Parameters
objects(Array.<BGE.SceneObject>)previousOrderIds(Array.<string>)screenBoundsById(object) — associative array keyed by SceneObject.id
Returns
dynamic
sweepForCandidatePairIndexes(
sortedObjects: Array.<BGE.SceneObject>,
screenBoundsById: object,
): object
Sweeps sortedObjects (already sorted ascending by minX) left to right, returning only the index pairs whose screen-space X ranges actually overlap - this is the broad phase's real cost-saving step. An object is dropped from the "active" set once its maxX has been passed by the sweep, so a later object is only ever compared against objects it could plausibly overlap, not the whole list - this is what turns the broad phase from O(n^2) into roughly O(n + k) for k actual overlapping pairs in a typical scene, and specifically fixes the diagonal-wall pathology (a wide object's cost is proportional to how many other objects its X range actually overlaps, not the whole scene).
Parameters
sortedObjects(Array.<BGE.SceneObject>) — sorted ascending by ScreenBounds.minX (see sortByMinXIncremental)screenBoundsById(object) — associative array keyed by SceneObject.id
Returns
object— array of 2-element integer arrays [i, j], indexes into sortedObjects
hullsOverlap(
hullA: Array.<BGE.Math.Vector>,
hullB: Array.<BGE.Math.Vector>,
): boolean
Separating-axis theorem (SAT) test between two convex 2D polygons (already-computed hulls - a billboard's 4 corners, or a model's bounding-cube projection reduced to its convex hull via BGE.QuickHull). Two convex shapes overlap unless there exists an axis (perpendicular to one of either shape's edges) that separates them - so this checks every candidate axis from both shapes and returns false the moment one actually separates them.
Parameters
hullA(Array.<BGE.Math.Vector>) — points in perimeter orderhullB(Array.<BGE.Math.Vector>) — points in perimeter order
Returns
boolean— true if the two convex shapes overlap
isValidHull(hull: Array.<BGE.Math.Vector>): boolean
Whether a hull has enough real geometry to be tested for overlap: at least MIN_VALID_HULL_POINTS points, and every one of them an actual Vector, never invalid (which BGE.QuickHull.QuickHull([]) can return - see MIN_VALID_HULL_POINTS).
Parameters
hull(Array.<BGE.Math.Vector>)
Returns
boolean
getEdgeNormals(hull: dynamic): dynamic
Parameters
hull(dynamic)
Returns
dynamic
isSeparatingAxis(
axis: BGE.Math.Vector,
hullA: dynamic,
hullB: dynamic,
): boolean
Parameters
axis(BGE.Math.Vector)hullA(dynamic)hullB(dynamic)
Returns
boolean
projectHull(axis: BGE.Math.Vector, hull: dynamic): dynamic
Parameters
axis(BGE.Math.Vector)hull(dynamic)
Returns
dynamic
groupIntoClusters(
objects: Array.<BGE.SceneObject>,
rendererObj: BGE.Renderer,
previousOrderIds: Array.<string>,
): ClusterResult
Groups objects into overlap clusters: connected components over the "these two objects' bounds overlap" relation (broad phase via sort-and-sweep, then narrow phase to reject false positives). Most objects end up alone in a cluster of one - only objects that mutually, genuinely overlap end up grouped together.
Parameters
objects(Array.<BGE.SceneObject>)rendererObj(BGE.Renderer)previousOrderIds(Array.<string>) — last frame's sorted order (see ClusterResult.sortedIds); pass [] on the first call
Returns
projectPointsToScreen(
worldPoints: dynamic,
rendererObj: BGE.Renderer,
): dynamic
Parameters
worldPoints(dynamic)rendererObj(BGE.Renderer)
Returns
dynamic
find(parent: dynamic, i: integer): integer
Parameters
parent(dynamic)i(integer)
Returns
integer
union(parent: dynamic, i: integer, j: integer): void
Parameters
parent(dynamic)i(integer)j(integer)
Returns
void
Other
MIN_VALID_HULL_POINTS
The minimum number of world-space bounding points that must survive projection to screen space before this object can be trusted to form a real convex hull (3 points is the minimum for a hull with any area/edges at all). Anything short of this - a point behind the camera silently drops out of worldPointToCanvasPoint()'s output (see projectPointsToScreen), or an object like SceneObjectPlane/ SceneObjectParallaxLayer that only ever has one bounding point to begin with (see SceneObject.getPositionsForFrustumCheck()'s single-point default) - is treated as having no valid overlap candidate this frame: it fails closed into its own solo cluster rather than risk a degenerate/invalid hull reaching QuickHull or the SAT test. This also sidesteps a pre-existing landmine in BGE.QuickHull.QuickHull([]): it does not return [] for empty input, it can return [invalid, invalid] (count 2), which would otherwise slip past a naive count-based guard and crash in getEdgeNormals doing VectorOps.subtract against invalid.
Default: 3
ScreenBounds
A screen-space AABB plus a camera-relative depth range, both derived from the same set of world-space bounding points a SceneObject already computes for its frustum check (getPositionsForFrustumCheck) - the broad phase of overlap detection reuses that geometry rather than computing anything new.
Properties
minX(float)maxX(float)minY(float)maxY(float)minDepth(float)maxDepth(float)
EMPTY_SCREEN_BOUNDS_SENTINEL
Sentinel magnitude used by getEmptyScreenBounds() - large enough that no real canvas/depth coordinate could ever reach it, and arranged so min > max on every axis, which makes boundsOverlap()'s comparisons false against literally any other (finite) ScreenBounds. A dedicated valid flag would need every existing bounds literal (including ones hand-built in tests) to grow a new required field; this sentinel keeps the ScreenBounds interface and its callers unchanged.
Default: 1000000000000000000
ClusterResult
The result of groupIntoClusters(): the computed clusters, plus the sorted-by-minX ordering it used this frame - feed sortedIds back in as previousOrderIds next frame to keep the incremental sort cheap (see sortByMinXIncremental).
Properties
clusters(dynamic)sortedIds(dynamic)