0
$\begingroup$

I have a set of independent meshes whose results I would like to project onto another non-hierachally related mesh. Until now, I've been accomplishing this by finding the nearest-distance node in the input meshes (by minimizing the $L_2$ error) and assigning its values to the target mesh. This seems to be the most often used way of approaching the problem (ref1, ref2) but due to the requirements of this project I would like to implement something quicker if possible.

As such, I was wondering if there were other, faster, methods for projecting mesh results onto another mesh. Unfortunately, I can't enforce that the input meshes and the target mesh will be related, since the results of the input mesh will be transformed (rotated / translated) during runtime. This takes out the majority of mesh projection methods that I'm at least aware of, which is why I'd like to go to the community for help. I understand that my current method likely retains the most accuracy as far as grid projection methods go, but I'm okay with trading accuracy for speed.

Thanks!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I don't think you've described the first of those references correctly. Finding the nearest node and choosing its value is not what Wolfgang's method suggests at all. His suggestion involves setting up the full $L_2$ projection from one mesh to the other and solving the associated linear system. This is likely much more accurate than your approach, and also much slower. $\endgroup$
    – Bill Barth
    Commented Jan 23, 2015 at 16:45
  • $\begingroup$ Right, I guess I should've clarified, but I'm only interested in carrying out the first half of the method he described. I understand that the time complexity of his method is bounded by the evaluation at each quadrature point, but in the interest of speed I've elected to use the simpler approach. Edit: Oh I see where you're coming from, my last sentence in the original post is incorrect. $\endgroup$
    – vincentjs
    Commented Jan 23, 2015 at 16:51

2 Answers 2

Reset to default
1
$\begingroup$

The MATLAB scatteredInterpolant class I mentioned in one of the posts you refer to works as follows: given a new point where you want interpolated values, scatteredInterpolant first tries to find the triangular cell in the old mesh containing this point and then does a linear interpolation within the cell. The most time-consuming part of the algorithm is finding the cell containing the point.

If I understand correctly, you are interpolating to the new point simply by finding the point in the old mesh closest to the new one. If you are satisfied with this level of accuracy, the performance of the search for the closest point can be dramatically improved. Entire books have been written about algorithms for spatial searching. One common approach is to use a kd-tree. First you add all the points from the old mesh to the tree and then you can quickly query the tree to find the closest points to a set of new points. There are several open-source implementations of kd-trees that you can find on the web, e.g.

https://code.google.com/p/kdtree/

http://www.cs.umd.edu/~mount/ANN/

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think the kd-tree might be what I'm looking for. Adding those references seem to have resulted in miscommunication on my end, but my goal was to reduce the time complexity of my current brute force search algorithm (which runs in $O(n)$) to something better (using either a better search or an entirely different approach altogether), which the kd-tree seems to accomplish. Thanks. $\endgroup$
    – vincentjs
    Commented Jan 23, 2015 at 18:24
1
$\begingroup$

With the approach you describe (using the value of the nearest point), you're essentially projecting not the original function $u_1$ defined on the mesh ${\cal T}_1$ onto mesh ${\cal T}_2$, but a function $Iu_1$ that is piecewise constant. Specifically, $Iu_1$ has the same value at point $x$ as the nearest node of the mesh it is defined on, which corresponds to a piecewise constant interpolation on the dual mesh of ${\cal T}_1$ (the Voronoi mesh corresponding to the nodes). In other words, you're computing $u_2=P_2Iu_i$. Because the interpolation is only ${\cal O}(h)$ accurate, there isn't really any reason to use a ${\cal O}(h^2)$ accurate projection for which you have to compute and invert a mass matrix. Rather, you may as well use an interpolation onto the second mesh. In other words, if an error of size ${\cal O}(h)$ is sufficient for you, then the value $u_2(x_j^{(2)})$ at a node $x_j^{(2)}$ of mesh ${\cal T}_2$ should simply be the value of $u_1(x_k^{(1)})$ where $x_k^{(1)}$ is the nearest node on mesh 1 for $x_j^{(2)}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.