# Faster methods for projecting a mesh onto a hierachally unrelated mesh?

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!

• 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. – Bill Barth Jan 23 '15 at 16:45
• 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. – vincentjs Jan 23 '15 at 16:51

• 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. – vincentjs Jan 23 '15 at 18:24
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)}$.