Skip to content

Instantly share code, notes, and snippets.

@aolo2

aolo2/rects.c

Created October 22, 2022 11:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aolo2/e74a513a59d01fae7f2fab76669f17d0 to your computer and use it in GitHub Desktop.
Save aolo2/e74a513a59d01fae7f2fab76669f17d0 to your computer and use it in GitHub Desktop.
Download ZIP
Collision bench
Raw
rects.c
#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);
}
@aolo2
Copy link
Author

aolo2 commented Oct 22, 2022 

#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

struct rect {
	float x, y;
};

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;
		rects[i].x = x;
		rects[i].y = y;
	}
}

static inline bool
rects_intersect(struct rect *r1, struct rect *r2)
{
	float r1_left   = r1->x;
	float r1_right  = r1->x + 1.0f;
	float r2_left   = r2->x;
	float r2_right  = r2->x + 1.0f;
    
	float r1_top    = r1->y;
	float r1_bottom = r1->y + 1.0f;
	float r2_top    = r2->y;
	float r2_bottom = r2->y + 1.0f;
    
	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 = r1 + 1; 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 cell_index = 0; cell_index < n_cellsx * n_cellsy; ++cell_index) {
        uint64_t cell_from = rects_from[cell_index];
        uint64_t cell_to = rects_from[cell_index + 1];
        for (uint64_t r1 = cell_from; r1 < cell_to; ++r1) {
            struct rect *rect1 = grid + r1;
            int32_t celly = cell_index / n_cellsx;
            int32_t cellx = cell_index % n_cellsx;
            
            bool has_left = (cellx > 0);
            bool has_right = (cellx < n_cellsx - 1);
            bool has_above = (celly > 0);
            bool has_below = (celly < n_cellsy - 1);
            
            // fast path (check everything)
            if (has_left && has_right && has_above && has_below) {
                // do three rows instead of 9 cells
                uint64_t row1_intersections = 0;
                uint64_t row2_intersections = 0;
                uint64_t row3_intersections = 0;
                
                uint32_t row1_cell_index = cell_index - n_cellsx;
                uint32_t row2_cell_index = cell_index - 0;
                uint32_t row3_cell_index = cell_index + n_cellsx;
                
                uint64_t row1_from = rects_from[row1_cell_index - 1];
                uint64_t row1_to   = rects_from[row1_cell_index + 2];
                
                for (uint64_t r2 = row1_from; r2 < row1_to; ++r2) {
                    struct rect *rect2 = grid + r2;
                    if (rects_intersect(rect1, rect2)) {
                        ++row1_intersections;
                    }
                }
                
                uint64_t row2_from = rects_from[row2_cell_index - 1];
                uint64_t row2_to   = rects_from[row2_cell_index + 2];
                
                for (uint64_t r2 = row2_from; r2 < row2_to; ++r2) {
                    struct rect *rect2 = grid + r2;
                    if (rects_intersect(rect1, rect2)) {
                        ++row2_intersections;
                    }
                }
                
                uint64_t row3_from = rects_from[row3_cell_index - 1];
                uint64_t row3_to   = rects_from[row3_cell_index + 2];
                
                for (uint64_t r2 = row3_from; r2 < row3_to; ++r2) {
                    struct rect *rect2 = grid + r2;
                    if (rects_intersect(rect1, rect2)) {
                        ++row3_intersections;
                    }
                }
                
                n_intersections += row1_intersections + row2_intersections + row3_intersections;
            } else {
                // slow path (for boundary 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);
                    
                    // left and above
                    if (celly > 0) {
                        int32_t cell_index_left_above = cell_index - 1 - n_cellsx;
                        n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_left_above);
                    }
                    
                    // left and below
                    if (celly < n_cellsy - 1) {
                        int32_t cell_index_left_below = cell_index - 1 + n_cellsx;
                        n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_left_below);
                    }
                }
                
                // 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);
                    
                    // right and above
                    if (celly > 0) {
                        int32_t cell_index_right_above = cell_index + 1 - n_cellsx;
                        n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_right_above);
                    }
                    
                    // right and below
                    if (celly < n_cellsy - 1) {
                        int32_t cell_index_right_below = cell_index + 1 + n_cellsx;
                        n_intersections += count_collisions_in_cell(rect1, rects_from, grid, cell_index_right_below);
                    }
                }
                
                // 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 = 1.1f;
    
    int32_t n_cellsx = ceilf(map_width / cell_size);
    int32_t n_cellsy = ceilf(map_hidth / cell_size);
    
    // 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;
    for (int32_t repeat = 0; repeat < repeats; ++repeat) {
        uint64_t before = nsec_now();
        uint64_t ncollisions = count_collisions_grid(rects, n, rects_from, grid, cell_size, n_cellsx, n_cellsy);
        uint64_t after = nsec_now();
        printf("%lu collisions\n", ncollisions / 2); // use the result so it doesn't get optimized out
        total_elapsed += (after - before);
    }
    
    float elapsed_msec  = (float) total_elapsed / 1000000.0f / repeats;
    float nsec_per_rect = (float) total_elapsed / n / repeats;
    
    printf("GRID: Average time %.2fmsec (~%.0fnsec / rect)\n", 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);
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment