#version 450
// GPU body-to-body contacts for the built-in ECS physics shader, in two
// passes selected by a define. GRID_PASS copies every body into the
// snapshot and files the bodies that collide into a spatial hash; the
// contact pass then moves each dynamic body out of its neighbours, reading
// only the snapshot, so the result does not depend on invocation order.
// Bodies whose cell is full, and bodies too big for one cell, go to the
// fallback list instead, which every body tests: no body is ever left out.
// A body too big for one cell tests every body itself. One thread doing that
// alone stalls the whole step, so OVERSIZED_PASS gives each such body a
// workgroup that splits the bodies between its threads.
layout(local_size_x = 256, local_size_y = 1, local_size_z = 1) in;
#include <physics_abi.glsl>
#include <physics_shapes.glsl>
// Bodies per hash cell before the rest spill into the fallback list.
const uint CELL_SLOTS = 8u;
const float CONTACT_MARGIN = 0.002;
// Pushes a sleeping body ignores. A larger slop (the contact margin) let a
// pile pressed by sideways gravity squeeze a ball into a wall.
const float SLEEP_SLOP = 0.0005;
// Cell counts; the length is a power of two.
layout(set = 0, binding = 8) buffer GridCounts { uint data[]; } grid_counts;
layout(set = 0, binding = 9) buffer GridSlots { uint data[]; } grid_slots;
// data[0] = fallback count, then the fallback body indices.
layout(set = 0, binding = 10) buffer Fallback { uint data[]; } fallback;
layout(set = 0, binding = 11) buffer Snapshot { PhysicsState data[]; } snapshot;
// Indirect dispatch size of OVERSIZED_PASS: one workgroup per oversized body.
layout(set = 0, binding = 13) buffer OversizedDispatch { uint data[3]; } oversized_dispatch;
// data[0] = oversized body count, then the oversized body indices.
layout(set = 0, binding = 14) buffer BigBodies { uint data[]; } big_bodies;
// The smallest maxComputeWorkGroupCount[0] Vulkan allows.
const uint MAX_GROUPS = 65535u;
// Full, Simplified and Space bodies with a solid shape touch each other;
// NoCollision (2) and Custom (3) bodies do not.
bool takes_part(PhysicsState body, BodyShape shape) {
precise float from_no_collision = abs(body.custom_values.x - 2.0);
precise float from_custom = abs(body.custom_values.x - 3.0);
return shape.shape.x < 2.5 && from_no_collision > 0.5 && from_custom > 0.5;
}
float inverse_mass(PhysicsState body) {
bool dynamic = body.properties.z > 0.5 && body.properties.z < 1.5 && body.properties.x > 0.0;
return dynamic ? sim_recip(body.properties.x) : 0.0;
}
ivec3 cell_of(vec3 position) {
precise vec3 scaled = position * sim_recip(pc.grid_cell_size);
return sim_to_int(floor(scaled));
}
uint hash_cell(ivec3 cell) {
uvec3 u = uvec3(cell);
return (u.x * 73856093u ^ u.y * 19349663u ^ u.z * 83492791u) & uint(grid_counts.data.length() - 1);
}
bool oversized(BodyShape shape) {
precise float diameter = bounding_radius(shape.shape) * 2.0;
return diameter > pc.grid_cell_size;
}
#ifdef GRID_PASS
void add_to_fallback(uint body_index) {
uint slot = atomicAdd(fallback.data[0], 1u);
fallback.data[1u + slot] = body_index;
}
void main() {
uint body_index = gl_GlobalInvocationID.x;
if (body_index >= pc.body_count) return;
PhysicsState body = bodies.data[body_index];
snapshot.data[body_index] = body;
BodyShape shape = body_shapes.data[body_index];
if (!takes_part(body, shape)) return;
if (oversized(shape)) {
atomicAdd(event_header.contacts.y, 1u);
add_to_fallback(body_index);
uint slot = atomicAdd(big_bodies.data[0], 1u);
big_bodies.data[1u + slot] = body_index;
return;
}
uint cell = hash_cell(cell_of(body.model[3].xyz));
uint slot = atomicAdd(grid_counts.data[cell], 1u);
if (slot < CELL_SLOTS) {
grid_slots.data[cell * CELL_SLOTS + slot] = body_index;
} else {
atomicAdd(event_header.contacts.x, 1u);
add_to_fallback(body_index);
}
}
#else
PhysicsState own;
BodyShape own_shape;
mat3 own_rotation;
uint own_index;
float own_inverse_mass;
// Per axis, the largest push and velocity change each way. Max and min give
// the same result in any order (the grid and fallback lists fill in atomic
// order), and four supports under a ball lift it once, not four times: a
// sum would bounce a resting ball and make a deep pile boil.
vec3 push_up;
vec3 push_down;
vec3 change_up;
vec3 change_down;
bool touched;
uint hash_collisions;
uint fallback_tests;
// Moves `own` out of `other_index` by its share of the overlap and removes
// its share of the closing velocity, like a collider contact without torque.
// ponytail: the overlap comes from own center to the other surface plus own
// reach, exact for spheres and face contacts but loose on edges; add a
// real narrow phase if stacks of rotated boxes need it.
void touch(uint other_index) {
if (other_index == own_index) return;
PhysicsState other = snapshot.data[other_index];
BodyShape other_shape = body_shapes.data[other_index];
if ((own_shape.layers.x & other_shape.layers.y) == 0u || (other_shape.layers.x & own_shape.layers.y) == 0u) return;
precise vec3 offset = own.model[3].xyz - other.model[3].xyz;
precise float reach = bounding_radius(own_shape.shape) + bounding_radius(other_shape.shape);
precise float reach_squared = reach * reach;
if (sim_dot(offset, offset) >= reach_squared) return;
vec3 normal;
float distance;
shape_distance(other_shape.shape, rotation_of(other.model), other.model[3].xyz, own.model[3].xyz, normal, distance);
precise float depth = support(own_shape.shape, own_rotation, normal) - distance;
// A body within CONTACT_MARGIN counts as touching, so a sleeping body
// that was pushed exactly clear of its support stays asleep.
if (depth <= -CONTACT_MARGIN) return;
touched = true;
if (depth <= 0.0) return;
precise float total = own_inverse_mass + inverse_mass(other);
if (total <= 0.0) return;
float share = sim_div(own_inverse_mass, total);
// Shock propagation: a body below that was supported last step (touch
// flag in velocity.w) counts as immovable, and it ignores the body
// resting on it. One pass then holds a tall stack instead of splitting
// each correction in half and letting the weight sink through.
vec3 gravity = vec3(pc.gravity_x, pc.gravity_y, pc.gravity_z);
if (sim_dot(gravity, gravity) > 0.0) {
float up = sim_dot(normal, -sim_normalize(gravity));
if (up > 0.7 && other.velocity.w > 0.5 && own_inverse_mass > 0.0) share = 1.0;
else if (up < -0.7 && own.velocity.w > 0.5) share = 0.0;
}
precise vec3 correction = normal * depth * share;
push_up = max(push_up, correction);
push_down = min(push_down, correction);
precise vec3 other_velocity = other.velocity.xyz;
// A supporting body sinks only because this pass lags a step; matching
// that sink would add g * dt of fall per level of a stack.
if (share == 1.0) other_velocity -= normal * min(sim_dot(other_velocity, normal), 0.0);
precise vec3 relative = own.velocity.xyz - other_velocity;
float closing = sim_dot(relative, normal);
if (closing >= 0.0) return;
// Bounce only above 1 m/s so resting contacts settle.
float restitution = closing < -1.0 ? max(own_shape.material.y, other_shape.material.y) : 0.0;
precise vec3 change = -normal * closing * (1.0 + restitution);
precise vec3 tangent = relative - normal * closing;
float tangent_speed = sim_length(tangent);
if (tangent_speed > 0.000001) {
precise float friction_squared = own_shape.material.x * other_shape.material.x;
float friction = sim_sqrt(friction_squared);
change -= sim_div(tangent, tangent_speed) * min(tangent_speed, -friction * closing);
}
precise vec3 shared_change = change * share;
change_up = max(change_up, shared_change);
change_down = min(change_down, shared_change);
}
void touch_in_cell(uint other_index, ivec3 cell) {
if (cell_of(snapshot.data[other_index].model[3].xyz) != cell) hash_collisions++;
touch(other_index);
}
void touch_fallback(uint other_index) {
fallback_tests++;
touch(other_index);
}
void begin_body(uint body_index) {
own_index = body_index;
own = snapshot.data[own_index];
own_shape = body_shapes.data[own_index];
touched = false;
hash_collisions = 0u;
fallback_tests = 0u;
push_up = vec3(0.0);
push_down = vec3(0.0);
change_up = vec3(0.0);
change_down = vec3(0.0);
own_rotation = rotation_of(own.model);
own_inverse_mass = inverse_mass(own);
}
// Every body is written so the contact flag starts each step fresh; the
// main pass adds collider contacts to it.
void write_body() {
precise vec3 push = push_up + push_down;
precise vec3 change = change_up + change_down;
// A sleeping body (REST_TICKS in physics.comp) shrugs off pushes and
// nudges smaller than SLEEP_SLOP and the rest speed. Without
// this, a deep pile's sleeping balls creep under their neighbours'
// tiny corrections, the pile spreads, and the creep wakes it again.
if (own.angular_velocity.w >= 20.0 && sim_length(push) < SLEEP_SLOP && sim_length(change) < 0.05) {
push = vec3(0.0);
change = vec3(0.0);
}
precise vec3 position = own.model[3].xyz + push * axis_keep(0u);
precise vec3 velocity = own.velocity.xyz + change * axis_keep(0u);
bodies.data[own_index].model[3].xyz = position;
bodies.data[own_index].velocity = vec4(velocity, touched ? 1.0 : 0.0);
}
#ifdef OVERSIZED_PASS
shared vec3 shared_push_up[256];
shared vec3 shared_push_down[256];
shared vec3 shared_change_up[256];
shared vec3 shared_change_down[256];
shared bool shared_touched[256];
void main() {
uint lane = gl_LocalInvocationID.x;
uint total_tests = 0u;
// Every lane reads the same count, so the barriers below are uniform.
uint count = big_bodies.data[0];
for (uint entry = gl_WorkGroupID.x; entry < count; entry += gl_NumWorkGroups.x) {
begin_body(big_bodies.data[1u + entry]);
for (uint other = lane; other < pc.body_count; other += gl_WorkGroupSize.x) {
if (takes_part(snapshot.data[other], body_shapes.data[other])) touch_fallback(other);
}
total_tests += fallback_tests;
shared_push_up[lane] = push_up;
shared_push_down[lane] = push_down;
shared_change_up[lane] = change_up;
shared_change_down[lane] = change_down;
shared_touched[lane] = touched;
barrier();
// Max, min and or give the same result in any order, so this tree
// matches one thread testing every body in turn.
for (uint stride = gl_WorkGroupSize.x / 2u; stride > 0u; stride /= 2u) {
if (lane < stride) {
shared_push_up[lane] = max(shared_push_up[lane], shared_push_up[lane + stride]);
shared_push_down[lane] = min(shared_push_down[lane], shared_push_down[lane + stride]);
shared_change_up[lane] = max(shared_change_up[lane], shared_change_up[lane + stride]);
shared_change_down[lane] = min(shared_change_down[lane], shared_change_down[lane + stride]);
shared_touched[lane] = shared_touched[lane] || shared_touched[lane + stride];
}
barrier();
}
if (lane == 0u) {
push_up = shared_push_up[0];
push_down = shared_push_down[0];
change_up = shared_change_up[0];
change_down = shared_change_down[0];
touched = shared_touched[0];
write_body();
}
// The next body reuses the shared arrays.
barrier();
}
if (total_tests > 0u) atomicAdd(event_header.contacts.w, total_tests);
}
#else
void main() {
// The grid pass has filed every oversized body by now.
if (gl_GlobalInvocationID.x == 0u) {
oversized_dispatch.data[0] = min(big_bodies.data[0], MAX_GROUPS);
oversized_dispatch.data[1] = 1u;
oversized_dispatch.data[2] = 1u;
}
if (gl_GlobalInvocationID.x >= pc.body_count) return;
begin_body(gl_GlobalInvocationID.x);
if (takes_part(own, own_shape)) {
// OVERSIZED_PASS moves this body.
if (oversized(own_shape)) return;
ivec3 cell = cell_of(own.model[3].xyz);
uint visited[27];
uint visited_count = 0u;
for (int z = -1; z <= 1; z++) {
for (int y = -1; y <= 1; y++) {
for (int x = -1; x <= 1; x++) {
uint hash = hash_cell(cell + ivec3(x, y, z));
// Two neighbour cells can share a hash; visit it once.
bool seen = false;
for (uint index = 0u; index < visited_count; index++) seen = seen || visited[index] == hash;
if (seen) continue;
visited[visited_count++] = hash;
uint count = min(grid_counts.data[hash], CELL_SLOTS);
for (uint entry = 0u; entry < count; entry++) touch_in_cell(grid_slots.data[hash * CELL_SLOTS + entry], cell + ivec3(x, y, z));
}
}
}
for (uint entry = 0u; entry < fallback.data[0]; entry++) touch_fallback(fallback.data[1u + entry]);
}
if (hash_collisions > 0u) atomicAdd(event_header.contacts.z, hash_collisions);
if (fallback_tests > 0u) atomicAdd(event_header.contacts.w, fallback_tests);
write_body();
}
#endif
#endif