[petsc-users] Finding which cell an arbitrary point belongs to in DMPlex

[Matthew Knepley]

On Thu, Sep 24, 2020 at 6:09 PM Jeremy Theler <jeremy at seamplex.com> wrote:

> On Wed, 2020-09-16 at 14:29 +0000, Hapla  Vaclav wrote:
> > There is also DMPlexFindVertices() which finds the nearest vertex to
> > the given coords in the given radius.
>
> At first I had understood that this function performed a nearest-
> neighbor search but after a closer look it sweeps the local DM and
> marks whether the sought points coincide with a mesh node within eps or
> not. Neat.
>
>
> > You can then get support or its transitive closure for that vertex.
>
> Not directly because in general the sought points will not coincide
> with a mesh node, but a combination of this function and
> DMLocatePoints() seems to do the trick.
>
> > I wrote it some time ago mainly for debug purposes. It uses just
> > brute force. I'm not sure it deserves to exist :-) Maybe we should
> > somehow merge these functionalities.
>
> It works, although a kd-tree-based search would be far more efficient
> than a full sweep over the DM.
>

We should not need to do that. LocatePoints() does not sweep the mesh.
It just does grid hashing. kd is a little better with really irregular
distributions,
but hashing should be fine.

  Thanks,

    Matt


> Thanks
> --
> jeremy
>
> >
> > Thanks,
> >
> > Vaclav
> >
> > > On 16 Sep 2020, at 01:44, Matthew Knepley <knepley at gmail.com>
> > > wrote:
> > >
> > > On Tue, Sep 15, 2020 at 6:18 PM Jeremy Theler <jeremy at seamplex.com>
> > > wrote:
> > > > On Mon, 2020-09-14 at 20:28 -0400, Matthew Knepley wrote:
> > > > > On Mon, Sep 14, 2020 at 6:15 PM Jeremy Theler <
> > > > jeremy at seamplex.com>
> > > > > wrote:
> > > > > > Hello all
> > > > > >
> > > > > > Say I have a fully-interpolated 3D DMPlex and a point with
> > > > > > arbitrary
> > > > > > coordinates x,y,z. What's the most efficient way to know
> > > > which cell
> > > > > > this point belongs to in parallel? Cells can be either tets
> > > > or
> > > > > > hexes.
> > > > >
> > > > > I should make a tutorial on this, but have not had time so far.
> > > >
> > > > Thank you very much for this mini-tutorial.
> > > >
> > > > >
> > > > > The intention is that you use
> > > > >
> > > > >
> > > > >
> > > >
> https://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/DM/DMLocatePoints.html
> > > > >
> > > > > This will just brute force search unless you also give
> > > > >
> > > > >   -dm_plex_hash_location
> > > >
> > > > Well, for a 3D DMplex PETSc (and git blame) tells me that you
> > > > "have
> > > > only coded this for 2D." :-)
> > > >
> > >
> > > Crap. I need to do 3D. It's not hard, just work.
> > >
> > > > > which builds a grid hash to accelerate it. I should probably
> > > > expose
> > > > >
> > > > >   DMPlexLocatePoint_Internal()
> > > > >
> > > > > which handles the single cell queries. If you just had one
> > > > point,
> > > > > that might make it simpler,
> > > > > although you would still write your own loop.
> > > >
> > > > I see that DMLocatePoints() loops over all the cells until it
> > > > finds the
> > > > right one. I was thinking about finding first the nearest vertex
> > > > to the
> > > > point and then sweeping over all the cells that share this vertex
> > > > testing for DMPlexLocatePoint_Internal(). The nearest node ought
> > > > to be
> > > > found using an octree or similar. Any direction regarding this
> > > > idea?
> > > >
> > >
> > > So you can imagine both a topological search and a geometric
> > > search. Generally, people want geometric.
> > > The geometric hash we use is just to bin elements on a regular
> > > grid.
> > >
> > > > >  If your intention is to interpolate a field at these
> > > > > locations, I created
> > > > >
> > > > >
> > > > >
> > > >
> https://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/SNES/DMInterpolationCreate.html
> > > > >
> > > > > which no one but me uses so far, but I think it is convenient.
> > > >
> > > > Any other example apart from src/snes/tutorials/ex63.c?
> > > >
> > >
> > > That is the only one in PETSc. The PyLith code uses this to
> > > interpolate to seismic stations.
> > >
> > >   Thanks,
> > >
> > >      Matt
> > >
> > > > Thank you.
> > > >
> > > > >
> > > > >   Thanks,
> > > > >
> > > > >     Matt
> > > > >
> > > > > > Regards
> > > > > > --
> > > > > > jeremy theler
> > > > > > www.seamplex.com
> > > > > >
> > > > > >
> > > > >
> > > > >
> > > > >
> > > >
> > > >
> > >
> > >
> > > --
> > > What most experimenters take for granted before they begin their
> > > experiments is infinitely more interesting than any results to
> > > which their experiments lead.
> > > -- Norbert Wiener
> > >
> > > https://www.cse.buffalo.edu/~knepley/
>
>

-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener

https://www.cse.buffalo.edu/~knepley/ <http://www.cse.buffalo.edu/~knepley/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20200924/a47b4a66/attachment.html>