I'm currently attempting to create a minimal "3D" engine that renders voxels and planes, but I'm having a bit of a hiccup. Right now, I'm trying to make an algorithm that sorts objects based off of their position from the camera. Things further in the back are always drawn first, and if their Z axis (distance directly in front of the camera) is the same, it draws which ever is further away from the center of the screen.
I have a version that I know works on my PC, using both gcc and clang, but as soon as I compile it using the toolchain for the device I'm developing for, it starts glitching out and doesn't do exactly what I want. The output changes every other time. Could I have any pointers as to what I could do to fix it or implement a qsort function separate from the toochain I am using?
// includes
int8_t player_x = 0;
int8_t player_y = 0;
int8_t player_z = 0;
int compareCoordinates(const void *a, const void *b) {
int8_t *coord1 = (int8_t *)a;
int8_t *coord2 = (int8_t *)b;
if ((coord2[2] - coord1[2]) != 0) {
return (coord2[2] - coord1[2]);
}
int value = (abs(coord2[0] - player_x) + abs(coord2[1] - player_y)) - (abs(coord1[0] - player_y) + abs(coord1[1] - player_y));
if (value == 0){
return 1;
}
return value;
}
void sortCoordinateList(int8_t coordinates[][3], int numCoordinates) {
qsort(coordinates, numCoordinates, sizeof(coordinates[0]), compareCoordinates);
}
int8_t coordinates[][3] = {
{1, 2, 5},
{-1, 2, 5},
{-3, 2, 5},
};
int main(void)
{
sortCoordinateList(coordinates, LEN(coordinates));
for (int i = 0; i < LEN(coordinates); i++) {
dbg_printf("(%d, %d, %d)\n", coordinates[i][0], coordinates[i][1], coordinates[i][2]);
}
dbg_printf("\n\n");
}
This is a snippet of the code, removing the moving functions, but this is the main thing. I am fairly new to C programming, but I know that qsort treats items with the same value randomly or something along those lines, called stable sorting, but I am pretty confident that this is not the case.
I tried multiple different ways of debugging and testing, but I am just completely stumped. Usually when I come across an error, I figure it out myself, but I had to cave in and ask my first StackOverflow question. BTW, I've been working on this for at least 13-15 hours between today and yesterday, so yes I have tried everything I can.
This line looks suspicious:
int value = (abs(coord2[0] - player_x) + abs(coord2[1] - player_y)) - (abs(coord1[0] - player_y) + abs(coord1[1] - player_y));
There's 4 expressions in that "value" computation:
This subexpression: (abs(coord1[0] - player_y) doesn't doesn't seem right. It's subtracing an "x" value with a "y" value.
If I had to guess, you are sorting based on z-depth first. Then as a tie breaker for items on the same z index, sort based on distance from the player's {x,y,z} coordinate.
I think you really want this:
int compareCoordinates(const void* a, const void* b) {
int8_t* coord1 = (int8_t*)a;
int8_t* coord2 = (int8_t*)b;
int8_t x1 = coord1[0];
int8_t y1 = coord1[1];
int8_t z1 = coord1[2];
int8_t x2 = coord2[0];
int8_t y2 = coord2[1];
int8_t z2 = coord2[2];
if (z2 != z1) {
return z2 - z1;
}
int distance1 = (x1 - player_x) * (x1 - player_x) + (y1 - player_y) * (y1 - player_y);
int distance2 = (x2 - player_x) * (x2 - player_x) + (y2 - player_y) * (y2 - player_y);
return distance2 - distance1;
return 0;
}
Where distance1 and distance2 are the "squared distances". No need to take the square root for purposes of computing distance.
None of this explains why you'd be getting different results. That's why I think SPD's answer is likely the source of the bug you are seeing.
Update
To address the issue of sorting "an array of arrays", with qsort, it's helpful to use a typedef:
typedef int8_t COORD[3];
Then your sort function is a quick adjustment;
int compareCoordinates(const void* a, const void* b) {
COORD* coord1 = (COORD*)a;
COORD* coord2 = (COORD*)b;
int8_t x1 = *(coord1)[0];
int8_t y1 = *(coord1)[1];
int8_t z1 = *(coord1)[2];
int8_t x2 = *(coord2)[0];
int8_t y2 = *(coord2)[1];
int8_t z2 = *(coord2)[2];
if (z2 != z1) {
return z2 - z1;
}
int distance1 = (x1 - player_x) * (x1 - player_x) + (y1 - player_y) * (y1 - player_y);
int distance2 = (x2 - player_x) * (x2 - player_x) + (y2 - player_y) * (y2 - player_y);
return distance2 - distance1;
return 0;
}
And then everything else is a quick fix to use the COORD struct
void sortCoordinateList(COORD* coordinates, size_t numCoordinates) {
qsort(coordinates, numCoordinates, sizeof(coordinates[0]), compareCoordinates);
}
COORD coordinates[3] = {
{1, 2, 5},
{-1, 2, 5},
{-3, 2, 5},
};
int main(void)
{
sortCoordinateList(coordinates, sizeof(coordinates) / sizeof(COORD));