[MOAB-dev] Bug in kdtree?

[Tim Tautges]

I do think the entries should be ordered at the end of the call, after tree traversal is done, though.

- tim

On 07/24/2013 04:35 PM, Iulian Grindeanu wrote:
> the bug is around that logic, that I try to understand.
> It seems that the "ray_end" is reset, which is why some points are missed.
>
> I didn't write that logic, maybe Tim or Paul know who did.
>
> I don't think we should guarantee the order;
> The user should order it if needed;
>
>   The "leafs" of the tree can come in any order, and we should not try to order it there.
>
> Iulian
>
> ------------------------------------------------------------------------------------------------------------------------
>
>
>     Hi iulian
>
>     Thanks for that, additional side question. When you specify the maximum number of intersection to return, the list
>     is ordered in distance from the start point, when you specify 0, the list is unordered. Should we not expect
>     consistent behavior in both cases?
>
>     Thanks
>
>     Andy
>
>
>
>     Sent from my Samsung Galaxy Note™, an AT&T LTE smartphone
>
>     Iulian Grindeanu <iulian at mcs.anl.gov> wrote:
>     it works fine if you do not specify the limit 100 for number of intersections.
>     If you leave it 0, it is fine;
>     (so call with kdtree->ray_intersect_triangles( kdtree_root, 1.0e-6,
>                              dir, box_center,
>                              intersection_facets
>                              , intersections);
>
>     I am still looking, but I think I am close :)
>
>     ------------------------------------------------------------------------------------------------------------------------
>
>         OK, obb tree works fine with the same model, default setting for everything
>         (you do no have to put tetras in the build, only the faces)
>
>         So there might be an issue with the kdtree.
>         I will look at it.
>
>         Iulian
>         ------------------------------------------------------------------------------------------------------------------------
>
>             The problem is on the secondrun, moving the starting point in the to y=4, then we get no intersections
>             beyond 48.5.
>             On 07/24/2013 10:50 AM, Iulian Grindeanu wrote:
>
>                 I see no error
>                 Your fifth slab is at about 49.5;
>                 (first at 9.5, ..., fifth at 49.5)
>
>                 Iulian
>
>                 ------------------------------------------------------------------------------------------------------------------------
>
>                     I think I may have found a bug in kdtree.
>
>                     My test problem consists of a tet mesh that is composed of some 4000
>                     tets. The mesh looks like that in mesh.png, a ray starts at position
>                     (1,0,0) and fires along (1,0,0) and we get the following results back
>                     from my test program swp.cpp
>
>                     Compile the minimum working example as
>
>                     g++ swp.cpp -I/<moab include dir> -L<moab lib dir> -lMOAB
>
>
>                     This is as expected,
>
>                     # of intersections : 20
>                     intersection distances are on 8.5 8.74072 9.25928 9.5 18.5 18.7407
>                     19.2593 19.5 28.5 28.7407 29.2593 29.5 38.5 38.7407 39.2593 39.5 48.5
>                     48.7407 49.2593 49.5 of ray length 900
>
>                     8.5 9.5 18.5 19.5 etc are the boundaries of the faces of the mesh.
>
>                     However, if we recompile and change the starting position to (1,4,0) we get
>
>                     # of intersections : 17
>                     intersection distances are on 8.5 8.63513 9.06064 9.5 18.5 18.6351
>                     19.0606 19.5 28.5 28.6351 29.0606 29.5 38.5 38.6351 39.0606 39.5 48.5 of
>                     ray length 900
>
>                     As far this ray is concerned there is no mesh in the 5th slab.
>
>                     What have I done wrong?
>
>                     Thanks
>
>                     Andy
>
>
>
>
>
>

-- 
================================================================
"You will keep in perfect peace him whose mind is
   steadfast, because he trusts in you."               Isaiah 26:3

              Tim Tautges            Argonne National Laboratory
          (tautges at mcs.anl.gov)      (telecommuting from UW-Madison)
  phone (gvoice): (608) 354-1459      1500 Engineering Dr.
             fax: (608) 263-4499      Madison, WI 53706