Tests for correctness, help request

[szaghi]

Dear @Forceflow thank you very much for sharing your work, it is very appreciated.

For my own applications I am developing a library similar to libmorton, but in pure Fortran. I am using a bit interleaving technique (see Stocco 2009) that I guess is similar to your (I have not yet studied your method).

Anyhow, I am looking to your work for validating my implementation (at least for now, when I'll have validated my implementation, I'll try to improve the algorithm performances to match yours, maybe adopting your method) because I am almost sure that my implementation is bugged. Unfortunately, I really have not knowledge of C++ and a very very limited one of C. I tried to read the contents of your test subdirectory, but I cannot understand how you test for correctness of results. Have you hard-coded a list of expected-results into a tests-suite? In particular

Can you give some hints (online-calculator, list of already-validated results, other-validated codes) on how validate my implementation?

I can write my self a list of expected-validated results by means of the Morton definition, but if there are external resources ready to use, I really prefer to use them (for my laziness, but also for safety reasons).

My best regards.

[Forceflow]

Yes, currently I test in two ways:

• A test with hard-coded expected results. Check the lines in libmorton_test.h, like this:

`// correct morton codes for 16 x 16 x 16, with z running fastest, then y, then x (4096 in total) static const uint_fast16_t control_3D_Encode[4096] = { 0, 4, 32, 36, 256, 260, 288, 292, 2048, 2052, 2080, 2084, 2304, 2308, 2336, 2340, 2, 6, 34, 38, 258, 262, 290, 294, 2050, 2054, 2082, 2086, 2306, 2310, 2338, 2342, 16, 20, 48, 52, 272, 276, 304, 308, ...

• A test that checks if coordinates-> encode -> decode returns the same coordinates, testing this with all different methods and mixing them up.

You can easily do this morton encoding/decoding by hand, check the blog post on my blog for more info.

[szaghi]

Dear @Forceflow Thank you for your help. I'll go like you hard-coding expected results, maybe I'll use your implementation to validate mine, for now your seems to be only external validated resource available :smile:

Thank you again, cheers

[szaghi]

@Forceflow

I am sorry to bother you again... I have grabbed your 16x16x16 test matrix and I am trying to using it. Surely there should be something trivial that I have missed. Let us consider an example.

At this line of the Morton's code table I read

    0, 4, 32,...

then in the indexes table at this line I read

{0,0,0}
{1,0,0},{0,1,0},...

If my understanding is right the two tables should be in-sync, thus you are mapping the Morton code 32 to the indexes 0,1,0. Is this conclusion right? If it is, there should be something I am missing, because I think that the Morton's of 0,1,0 is 2 and not 32. Maybe, I am starting from a different mapping? In my Fortran world in am in a column-major world...

Cheers.

[Forceflow]

Hey, nope, those two tables are indepent.

I test the encoding with the first table, the decoding with the second one. They re not linked, although they could be.

I get how it is confusing because in the first one, I let the z-coordinate run fastest, and in the last table, it's based on increasing morton number, the results are actually in morton order. So decode(0) = (0,0,0), decode(1) = (1,0,0) etc ....

For testing the sync you are referring to, I do the test if (x,y,z) = decode(encode((x,y,z))

[szaghi]

@Forceflow Great! I was sure I had not understand your aims correctly, thank you very much for the explanation.

For testing the sync you are referring to, I do the test if (x,y,z) = decode(encode((x,y,z))

Yes, me too, but having you spent some times on hard coding the validated results of both encode/decode algorithms why not use them? What I mean is (x,y,z) = decode(encode((x,y,z)) is a valid test for only the consistency (sync) of the two algorithms encode/decode, but the validity of each singular algorithm cannot be validated by means of this test. Now you have done the great work to hard code 4096 validated results for both the encode and decode algorithms, why do not use in conjunction? You need only a remap of the tables.

For example, if the two tables are in sync you can validate both the encode/decode sync and also the validity of encode/decode results, e.g.

integer(int32), intent(in) :: indexes_validated(3, 4096) ! your hard coded indexes results
integer(int64), intent(in) :: morton_validated(4096) ! your hard coded morton results mapped in sync with your indexes validated

do t=1, 4096
  if (.not.is_encode_decode_ok(indexes_validated(:, t), morton_validated(t)) then
    print*, ' error: test ', t, ' fails' 
  end if
end do

where

function is_encode_decode_ok(indexes_validated, morton_validated) result(is_test_passed)
integer(int32), intent(in) :: indexes_validated(3)
integer(int64), intent(in) :: morton_validated
logical :: is_test_passed

integer(int32) :: indexes(3)
integer(int64) :: morton

morton=encode(indexes_validated(3))
indexes=decode(morton_validated)
is_test_passed = morton==morton_validated.and.all(indexes==indexes_validated)
end function is_encode_decode_ok

(sorry, but I speak only Fortran)

Anyhow, thank you for your patience, I'll try remap your tables to suite my needs.

Cheers.