voronoi
voronoi copied to clipboard
JCash
Running generator yields faulty edges
The input yields edges that goes through the entire diagram, running from 0 y to 2048 (max y). Several of these edges only have 2 corners and those corners only get one edge.
https://gist.github.com/lundmark/548d4b9184ff1a64d40fc9040cdb6475
The rect is: jcv_rect rect = { { 0, 0 }, { 2048, 2048 } };
It's compiled with vs2019, with the following flags: -Od", "-Oi", "-fp:fast", "-Gm-", "-GR-", "-EHa-", "-FC", "-GF", "-WL", "-WX", "-Wall", "-MP"
Small update:
Running fp:strict or fp:precise under O2 seems to remove the chance for this to happen. I haven't really discovered if it still can happen during -Od but I'm guessing that the compiler is doing something about the order of float operations that are causing this behavior.
I haven't been able to nail it down further, and I'm not sure that I will be able to. In general I need to be able to discover where the issue can possibly handle within the jc voronoi and then riddle it with asserts to see if I can get an early hit and look at the disassembly.
If you have any ideas where inside the voronoi generation this is likely to happen, that would be greatly appriciated.
I haven't had time to look into it yet. perhaps this weekend, otherwise, during holidays. :/
Would it mayhaps be possible to do the generator in integer-space instead of using floating points?
I mean, it probably is possible, but it's probably a big rewrite, and might be slower too, since you (probably) want to recalculate the fractions many times. Suffice to say, I won't have time to look into that.
The biggest issue is the it generates invalid values. The integer-space based was only a suggestion.
After some debugging, I found that it was my previous "optimization" of finding edges in the beach line, that was acting up in some cases. If I do a full search in the beachline (currently a linked list), then the issue disappears in this case (See screenshot below). My plan has always been to make a proper optimization and store the beach line in a binary search tree, and that's what I'll do now. In the mean time, I'll remove the optimization (doesn't do much anyways in this case, and above all, it produces bad data).
Repro:
./compile.sh && ./build/main -i testdata.txt -w 2048 -h 2048