Collision detection still not always correct

[Chris Richardson]

There is still a bug in collision detection of a point and a cell. Here is a MWE to demonstrate it:

from dolfin import *

big = 1e6
p1 = Point(0.1, 0.06)
p3 = Point(big*2.1, big*0.1)
p2 = Point(0.0, big*3.0)
p0 = Point(big*3.0, 0.0)

mesh = Mesh()
ed = MeshEditor()
ed.open(mesh, 2, 2)

t = 1e-3
ed.init_cells(3)
ed.init_vertices(4)
ed.add_vertex(0, p0)
ed.add_vertex(1, p1)
ed.add_vertex(2, p2)
ed.add_vertex(3, p3)

ed.add_cell(0, 2, 3, 0)
ed.add_cell(1, 0, 1, 3)
ed.add_cell(2, 1, 2, 3)

ed.close()

xdmf = XDMFFile("a.xdmf")
xdmf.write(mesh)

print mesh.cells()
print mesh.coordinates()

bb = mesh.bounding_box_tree()

# Find a point on line somewhere between p3 and p1
j = 4
pq = (p3*j + p1*(50-j))/50.0
c = bb.compute_entity_collisions(pq)
print pq.str(), c

# Check neighbouring points
step = 1e-6
for i in range(-1, 2):
    for j in range(-1, 2):
        pt = pq + Point(step*i, step*j)
        c = bb.compute_entity_collisions(pt)
        print pt.str(), c

The problem only occurs on highly deformed irregular meshes where neighbouring cells have different vertex order orientations.

[Chris Richardson]

Refer back to original Issue #296 reported by @blechta

[Jan Blechta]

Note also of #766.

[Jan Blechta]

How is this a multimesh issue? Chris' examples has nothing to do with multimesh.

[Anders Logg (Chalmers)]

It's part of collision detection which is closely related to ongoing work on robustness of geometric tests as part of multimesh work (branch logg/multimesh). I changed the label to highlight this issue to be fixed in that branch. Other issues with the label geometry are very different: mesh generation interface, point sources, etc.

[Jan Blechta]

Note that @chris_richardson seem to work on this as well https://bitbucket.org/fenics-project/dolfin/branch/chris/fix-collision.

[Anders Logg (Chalmers)]

Interesting. In that case, perhaps the geometry tag is more suitable.

[August Johansson]

This is a good test for the geometry predicates we're working on. I can replace the geometry computations in BoundingBoxTreeXd with the our new collision predicates and test this.

[Chris Richardson]

I have got a solution in my branch, as noted by @blechta. The important point is that the test should be computationally the same from both sides of an interface.

[August Johansson]

With the new collision predicates we're working on I get the same result as your branch. I'll add this as a test.

[August Johansson]

Can we close this issue? What do you thing @chris_richardson ?

[Chris Richardson]

I haven't checked my MWE above against master since your merge, but if it now works, then please close. I still worry about neighboring cells across a process boundary... Does it work in parallel?

[August Johansson]

I'll have to check how it works in parallel. It works in serial. I'll close if it works in parallel.

[Anders Logg (Chalmers)]

@augustjohansson Did you check if it works in parallel?

[Anders Logg (Chalmers)]

With n processes I get 9n intersections. I assume this is correct? @chris_richardson

[August Johansson]

That's the result I got too, which I guess means the test works in a trivial parallelization. This is of course good, but I thought the real parallel test would be to see if it works when the mesh is partitioned.

[Anders Logg (Chalmers)]

This looks correct to me now.