Raylib: [models] Unable to load certain OBJ models.

[BaconOFBurger]

Unable to load certain OBJ models.

When I try loading certain models such as model.zip, or model_2.zip with their corresponding .mtl files, the program freezes indefinitely and causes a segfault in a debugger.

Environment

Windows, Windows 10, OpenGL 4.6, GeForce GT 640.

Issue Screenshot

(ignore altarStone.obj and altarWood.obj in the screenshot they load just fine)

Code Example

#include <raylib.h>

int main() {
  //some init code...

  Model model = LoadModel("path/to/model.obj"); 
  printf("This will never be reached.");
}

[masterex1000]

After spending some time with a debugger I have figured out that its a problem with tinyobjloader's hashmap implementation.

In tinyobj_loader.h you have this code

// void hash_table_set()...
/* Expand if necessary
   * Grow until the element has been added
   */
  do
  {
    hash_table_maybe_grow(hash_table->n + 1, hash_table);
  }
  while (hash_table_insert(hash, (long)val, hash_table) != HASH_TABLE_SUCCESS);

Which tries to insert the value into the hashmap, but if it can't then it tries to expand the hashmap

If the table has enough space then hash_table_maybe_grow won't expand it at all

static void hash_table_maybe_grow(unsigned int new_n, hash_table_t* hash_table) {
//...
    if (new_n <= hash_table->capacity) {
        return;
    }
//...
}

When its trying to add an object it loops through different indices trying to find one that works, but the hashing algorithm exits before it finds one

static int hash_table_insert_value(unsigned long hash, long value, hash_table_t* hash_table) {
//...
    for (i = 1; hash_table->entries[index].filled; i++)
      {
        if (i >= hash_table->capacity)
          return HASH_TABLE_ERROR;
        index = (start_index + (i * i)) % hash_table->capacity; 
      }
//...
}

So what ends up happening is that it keeps trying to find a spot, can't. tries to expand the table, doesn't. then does it again, and again, and again.....

TLDR: tinyobj loader's hashmap implementation is broken

[rhf104]

The hash table implementation seems to be Quadratic probing...

/* Insert with quadratic probing */
static int hash_table_insert_value(unsigned long hash, long value, hash_table_t* hash_table)
{
  /* Insert value */
  unsigned int start_index = hash % hash_table->capacity;

I found this explanation of the algorithm on Wikipedia
An interesting disclaimer:

When using quadratic probing, [...] there is no guarantee of finding an empty cell once the table becomes more than half full, or even before this if the table size is composite, because collisions must be resolved using half of the table at most.

I haven't been able to fix the algorithm yet but it seems like there are ways to guarantee an empty cell is found by adding constraints to the possible table sizes and search indexing. In the meantime I was able to load an obj model with 8 materials by increasing the initial table size from 10 to 17. I assume 17 works because after adding 8 materials it still leaves more than half the table empty.

#define HASH_TABLE_DEFAULT_SIZE <number of unique materials * 2 + 1>

[raysan5]

@masterex1000 @rhf104 thank you very much for reviewing this issue, it seems it's related to https://github.com/syoyo/tinyobjloader-c project, maybe you can open an issue on their repo an link with this one.

[chriscamacho]

is it worth comparing with https://github.com/jpcy/objzero ?

it does at least seem to triangulate meshed - something that makes the current loader fail with a lot of kenney.nl assets.

Not sure about the hashmap implementation ?

[BaconOFBurger]

Seems like I missed a few stuff here as I see, I was overwhelmed with school stuff and completely forgot about this lol.
Anyway thank you so much guys for spending your free time on finding what the issue is, I guess like @rhf104 said I could temporarily fix this issue by recompiling raylib with this modification:

#define HASH_TABLE_DEFAULT_SIZE 21

meanwhile tinyobjloader-c fixes their algorithm.

edit: ill use this instead

#define HASH_TABLE_DEFAULT_SIZE 19

because 21 is apparently a composite number

[BaconOFBurger]

Update: Okay, I recompiled raylib with an increased HASH_TABLE_DEFAULT_SIZE size (set to 29) in tinyobj_loader_c.h, it did indeed fix patch a few models like the ambulance but I still have 4 models out of 458 that simply refuses to load.

I'm pretty sure there's still another issue unrelated to this cursed algorithm since increasing the hash table size doesn't affect anything.

models.zip

[raysan5]

@BaconOFBurger it seems issue is not related to raylib but tinyobjloader-c, did you open an issue on their repo? They should be aware of this problem...

[BaconOFBurger]

Done 😅

[chriscamacho]

@BaconOFBurger @rhf104 are you actively working on this issue?

https://github.com/raysan5/raylib/issues/1406#issuecomment-704760368

do you want to combine our work into a single PR ?

[chriscamacho]

@BaconOFBurger I tried your models, but none of them induced the hashmap bug

I have applied a number of my own bug fixes to tinyobj_loader.h to allow proper material meshes, I think I might have accidentality fixed your hashmap issue ? (can you provide an obj where the hashmap definitely DOES NOT work for you please)

The only issue I did see is that the OBJ's weren't triangulated - as this can be done automagically with tools and manually with blender (simple import then output with triangulate obj selected!!) I don't feel its worth the effort to triangulate on the fly while loading...

[BaconOFBurger]

@chriscamacho

do you want to combine our work into a single PR ?

That would be a good idea since both issues are sort of related.

are you actively working on this issue?

Uh sorry I'm really not familiar with C code at all, I really dislike working with C and I'm afraid I can't contribute a lot.

The only issue I did see is that the OBJ's weren't triangulated

Didn't notice that, ill triangulating them with blender then. Ill let you know when I done that

[chriscamacho]

@BaconOFBurger news! (of the good variety!)

I managed to replicate the issue by setting

#define HASH_TABLE_DEFAULT_SIZE 1

:scream: the solution was to ask for twice what was being asked for (which was twice anyhow) this allows space plus space for collisions...

so don't break your neck triangulating everything in sight :WINK:

[raysan5]

Closing issue!