Created
October 22, 2022 11:27
-
-
Save aolo2/e74a513a59d01fae7f2fab76669f17d0 to your computer and use it in GitHub Desktop.
Collision bench
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdint.h> | |
#include <time.h> | |
#include <math.h> | |
#include <stdlib.h> | |
#include <stdbool.h> | |
struct rect { | |
float x, y; | |
float w, h; | |
}; | |
const float map_width = 1000.0f; | |
const float map_hidth = 1000.0f; | |
const float min_rect_side = 0.1f; | |
const float max_rect_side = 1.5f; | |
const int32_t repeats = 10; | |
static uint64_t | |
nsec_now(void) | |
{ | |
struct timespec ts = { 0 }; | |
clock_gettime(CLOCK_MONOTONIC, &ts); | |
return(ts.tv_nsec + ts.tv_sec * 1000000000ULL); | |
} | |
static void | |
generate_rects(struct rect *rects, uint64_t n) | |
{ | |
srand(123); // for reproducibility | |
for (uint64_t i = 0; i < n; ++i) { | |
float x = ((float) rand() / (float) RAND_MAX) * map_width; | |
float y = ((float) rand() / (float) RAND_MAX) * map_hidth; | |
float w = ((float) rand() / (float) RAND_MAX) * (max_rect_side - min_rect_side) + min_rect_side; | |
float h = ((float) rand() / (float) RAND_MAX) * (max_rect_side - min_rect_side) + min_rect_side; | |
rects[i].x = x; | |
rects[i].y = y; | |
rects[i].w = w; | |
rects[i].h = h; | |
} | |
} | |
static inline bool | |
rects_intersect(struct rect *r1, struct rect *r2) | |
{ | |
float r1_left = r1->x; | |
float r1_right = r1->x + r1->w; | |
float r2_left = r2->x; | |
float r2_right = r2->x + r2->w; | |
float r1_top = r1->y; | |
float r1_bottom = r1->y + r1->h; | |
float r2_top = r2->y; | |
float r2_bottom = r2->y + r2->h; | |
if (r1_left < r2_right && r1_right > r2_left && r1_top < r2_bottom && r1_bottom > r2_top) { | |
return(true); | |
} | |
return(false); | |
} | |
static uint64_t | |
count_collisions_naive(struct rect *rects, uint64_t n) | |
{ | |
uint64_t n_intersections = 0; | |
for (uint64_t r1 = 0; r1 < n; ++r1) { | |
struct rect *rect1 = rects + r1; | |
for (uint64_t r2 = 0; r2 < n; ++r2) { | |
struct rect *rect2 = rects + r2; | |
if (rects_intersect(rect1, rect2)) { | |
n_intersections++; | |
} | |
} | |
} | |
return(n_intersections); | |
} | |
static void | |
bench_naive_collision(struct rect *rects, uint64_t n) | |
{ | |
uint64_t before = nsec_now(); | |
uint64_t ncollisions = count_collisions_naive(rects, n); | |
uint64_t after = nsec_now(); | |
float elapsed_msec = (float) (after - before) / 1000000.0f; | |
float nsec_per_rect = (float) (after - before) / n; | |
printf("NAIVE: Found %lu collisions in %.2fmsec (~%.0fnsec / rect)\n", ncollisions, elapsed_msec, nsec_per_rect); | |
} | |
static inline uint64_t | |
count_collisions_in_cell(struct rect *rect1, uint64_t *rects_from, struct rect *grid, int32_t cell_index) | |
{ | |
uint64_t result = 0; | |
uint64_t from = rects_from[cell_index]; | |
uint64_t to = rects_from[cell_index + 1]; | |
for (uint64_t r2 = from; r2 < to; ++r2) { | |
struct rect *rect2 = grid + r2; | |
if (rects_intersect(rect1, rect2)) { | |
++result; | |
} | |
} | |
return(result); | |
} | |
static uint64_t | |
count_collisions_grid(struct rect *rects, uint64_t n, uint64_t *rects_from, struct rect *grid, | |
float cell_size, int32_t n_cellsx, int32_t n_cellsy) | |
{ | |
uint64_t n_intersections = 0; | |
for (uint64_t r1 = 0; r1 < n; ++r1) { | |
struct rect *rect1 = rects + r1; | |
int32_t cellx = rect1->x / cell_size; | |
int32_t celly = rect1->y / cell_size; | |
int32_t cell_index = celly * n_cellsx + cellx; | |
// should probably also check diagonal cells | |
// check own cell | |
n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index); | |
// to the left | |
if (cellx > 0) { | |
int32_t cell_index_left = cell_index - 1; | |
n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_left); | |
} | |
// above | |
if (celly > 0) { | |
int32_t cell_index_below = cell_index - n_cellsx; | |
n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_below); | |
} | |
// to the right | |
if (cellx < n_cellsx - 1) { | |
int32_t cell_index_right = cell_index + 1; | |
n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_right); | |
} | |
// below | |
if (celly < n_cellsy - 1) { | |
int32_t cell_index_above = cell_index + n_cellsx; | |
n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_above); | |
} | |
} | |
return(n_intersections); | |
} | |
static void | |
bench_grid_collision(struct rect *rects, uint64_t n) | |
{ | |
float cell_size = 2.0f; | |
int32_t n_cellsx = ceilf(map_width / cell_size); | |
int32_t n_cellsy = ceilf(map_hidth / cell_size); | |
// i DO NOT account for rects intersecting multiple cells here for simplicity | |
// csr format | |
uint64_t *rects_from = calloc(1, sizeof(uint64_t) * n_cellsx * n_cellsy + 1); | |
struct rect *grid = malloc(sizeof(struct rect) * n); | |
// count | |
for (uint64_t i = 0; i < n; ++i) { | |
struct rect *r = rects + i; | |
int32_t rect_cellx = r->x / cell_size; // truncated down to the cell index | |
int32_t rect_celly = r->y / cell_size; | |
int32_t cell_index = rect_celly * n_cellsx + rect_cellx; | |
rects_from[cell_index + 1] += 1; | |
} | |
for (uint64_t i = 1; i < n_cellsx * n_cellsy; ++i) { | |
rects_from[i + 1] += rects_from[i]; | |
} | |
// store | |
uint64_t *head = calloc(1, sizeof(uint64_t) * n_cellsx * n_cellsy); | |
for (uint64_t i = 0; i < n; ++i) { | |
struct rect r = rects[i]; | |
int32_t rect_cellx = r.x / cell_size; // truncated down to the cell index | |
int32_t rect_celly = r.y / cell_size; | |
int32_t cell_index = rect_celly * n_cellsx + rect_cellx; | |
uint64_t store_at = rects_from[cell_index] + head[cell_index]; | |
grid[store_at] = r; | |
head[cell_index]++; | |
} | |
uint64_t total_elapsed = 0; | |
uint64_t ncollisions = 0; | |
for (int32_t repeat = 0; repeat < repeats; ++repeat) { | |
uint64_t before = nsec_now(); | |
ncollisions = count_collisions_grid(rects, n, rects_from, grid, cell_size, n_cellsx, n_cellsy); | |
uint64_t after = nsec_now(); | |
total_elapsed += (after - before); | |
} | |
float elapsed_msec = (float) total_elapsed / 1000000.0f / repeats; | |
float nsec_per_rect = (float) total_elapsed / n / repeats; | |
printf("GRID: An average found %lu collisions in %.2fmsec (~%.0fnsec / rect)\n", ncollisions, elapsed_msec, nsec_per_rect); | |
} | |
int | |
main(int argc, char **argv) | |
{ | |
if (argc != 2) { | |
fprintf(stderr, "Usage: %s nrects\n", argv[0]); | |
return(1); | |
} | |
uint64_t n = strtoll(argv[1], NULL, 10); | |
struct rect *rects = malloc(sizeof(struct rect) * n); | |
if (!rects) { | |
perror("malloc"); | |
return(1); | |
} | |
generate_rects(rects, n); | |
// bench_naive_collision(rects, n); | |
bench_grid_collision(rects, n); | |
return(0); | |
} |
Author
aolo2
commented
Oct 22, 2022
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment