7
$\begingroup$

I have a scalar function defined over the vertices of a surface mesh. I want to compute an approximate (and generalized, I suppose) "Gaussian blur/convolution" of this function over the surface.

I can imagine for each vertex, taking an average of the function at vertices in it's (multi-hop) neighborhood weighted according to the Gaussian of their Euclidean distance (in R3) from the current vertex multiplied by the local area they represent. This approximation would be good if the surface isn't too curved at the scale of the Gaussian kernel. However it would still be computationally prohibitive.

Is there a more efficient convolving algorithm, perhaps based on some kind of iterated "flow" or partial exchange through edges of the mesh?

The mesh can have either triangular or quadrilateral faces - whichever is more convenient in answering this question. But the edge lengths are not constant, so local neighborhood geometry differs between vertices.

$\endgroup$
  • $\begingroup$ Do you require a neighbourhood that extends beyond immediate neighbours or would you be interested in approximations based on repeated application of a nearest neighbour approach? $\endgroup$ – trichoplax May 13 '16 at 16:18
  • $\begingroup$ @trichoplax As long as the number of iterations required to reach a 10-hop standard deviation isn't going to be prohibitive. (I guess it wouldn't be, because at least in the 1D case a 10-hop deviation can be reached by mixing nearest neighbors 100 times.) I just wouldn't know how to weight the neighbors in this case. $\endgroup$ – Museful May 13 '16 at 17:11
  • $\begingroup$ @joojaa It is separable when applied on a flat surface/grid but is it still separable when you have edges going off in arbitrary directions from each vertex? $\endgroup$ – Museful May 14 '16 at 11:56
  • $\begingroup$ @Museful Ok whereabout iterative smaller blurs that are a bigger that way you can do it only over edge connections and let the iterations propagete the effect. This is used in FEM and fluid sims to high efficiency $\endgroup$ – joojaa May 15 '16 at 15:49
  • 1
    $\begingroup$ Im not sure, im not so deeply invested in the lore of FEM. All I know that they can solve the diffusion over irregular meshes and that is entirely analogous with gaussian blur. $\endgroup$ – joojaa May 15 '16 at 18:04
6
$\begingroup$

A few different approaches

I'll consider a few variations on your specific request, since you mention efficiency and I suspect your specific request may be the least efficient. I'll also suggest ways of improving the efficiency without varying from your intended approach, so you can weigh up the alternatives.

Blurring the volume instead of the surface

If you want the distance metric to be 3D Euclidean distance instead of 2D Euclidean distance within the surface, then you could perform the blur on a regular 3D grid to which the scalar function you have in mind has been applied. Then you can use the final result of your Difference of Gaussians to calculate the scalar values at the vertices of your irregular mesh. This avoids having to take into account the mesh shape for the bulk of the calculation.

The 3D grid is likely to have a much larger number of vertices than the 2D mesh, but they will all be equally spaced and the large kernel blur can be achieved by repeated application of a small kernel blur taking into account only the 6 nearest neighbours, which will always be at a constant distance away. This approach involves potentially more calculation, but the ease with which the regular grid could be GPU accelerated may appeal.

This will give a different result from performing the blur on the mesh vertices using 3D Euclidean distance. For example, the 3D grid approach will be affected by distinctive regions of the 3D scalar function that are near but not on the mesh. This may be desirable or not depending on your specific purpose.

Using 2D distance instead of 3D distance

If you find that you need the distance metric to be 2D Euclidean within the surface, then you can get a good approximation to a larger kernel Gaussian blur by repeatedly applying a smaller kernel Gaussian blur. If there is not too much variation in the edge lengths within your mesh you may be able to choose a kernel size which allows for only including vertices one edge away at each iteration. This allows for only using single edge lengths to calculate the size of the contribution of a vertex, rather than calculating a 2D multi-edge distance.

3D distance using the surface without the volume

If you need the calculation to be precisely as described in your question, being calculated within the mesh rather than within the surrounding volume, but also using the 3D Euclidean distance, then using nearest neighbours and several iterations will not work. Unless the mesh is near to flat, the repeated application of a nearest neighbour blur will result in an approximation to the 2D Euclidean distance case, since the values will only be able to bleed from vertex to vertex, not directly along the shortest path as they would in a single pass. This will give less spread than would be achieved by a single pass that calculates the 3D distance to a vertex 10 edges away. (I have used 10 edges since you mention a 10-hop in your comment on the question.)

Implementing the blur in a single pass will mean calculating the 3D Euclidean distance between every vertex and every other vertex within a 10 edge radius. This will be expensive, but perfectly possible. Since you mention efficiency, consider that there are some redundancies you can eliminate provided you have sufficient available memory.

The two blurs that you produce prior to taking the Difference of Gaussians will use the same set of 3D distances up to the edge radius of the smaller kernel blur. If you can save these then you only need to calculate them once, rather than once per blur.

Also, each distance will be used twice per blur - once in each direction as the length from vertex A to vertex B is the same as the length from B to A. Caching/memoising these distances will avoid calculating them twice.

Effects from arbitrarily many edges away

If the surface curves such that some vertices which are many edges away are still near enough to affect each other in 3D distance, then rather than considering vertices within a certain number of edges away, you may need to consider all vertices within a certain 3D radius, regardless of how long the path via edges. In this case you can consider fewer vertices by using space partitioning, choosing a specific method which suits the mesh.

If you don't want parts of the surface which approach each other to influence each other, then you probably want a 2D distance metric rather than the 3D one.

If you have a wide range of different edge lengths then you may find the same problem of not being able to define a set number of edges to traverse, even if the mesh is fairly flat. Again you may need to define a 3D distance instead of a number of edges, and consider all vertices that lie within that radius.

$\endgroup$
  • $\begingroup$ Thank you. My mention of the 3D Euclidean distance may have done more harm than good. I only meant it as an expensive (and conditional) approximation that is simple to explain. I wouldn't pursue the approximation if it is less attainable than the ideal answer. $\endgroup$ – Museful May 14 '16 at 23:28
  • $\begingroup$ What I am ideally after is what you call "using 2D distance". On a regular grid (with consistent local geometry) it is easy because the same symmetrical 1-hop-neighborhood kernel can be applied (repeatedly) throughout the grid. My real problem is determining the kernel-weights of 1-hop neighbors around each vertex from the local geometry of that 1-hop neighborhood. $\endgroup$ – Museful May 14 '16 at 23:28
  • $\begingroup$ Each vertex has valence 4 but edge lengths and directions vary. (Alternatively (if for some reason planar faces make the problem tractable) each quadrilateral face can be broken along its shortest diagonal into two (now planar) triangles, in which case vertex valence varies from 4 to 8, and edge lengths become even more varied.) $\endgroup$ – Museful May 14 '16 at 23:29
  • $\begingroup$ Ultimately, I have a vertex with a ring of neighbors at different distances and angles, and I need to know the local kernel weights over these neighbors. Constraining the mean/centroid of the kernel to lie "in the center" (which in this case presumably means along the mean curvature normal's span from the vertex) already constrains 2DoF in the kernel's weights. Choosing some variance provides another constraint. But the system is still underdetermined since valence>3. How to choose the weights? $\endgroup$ – Museful May 14 '16 at 23:30
  • $\begingroup$ Yes, "using 2D distance" is a little vague. I guess we should distinguish between "shortest edgewise distance" and "shortest distance within the surface" (which won't necessarily stay on edges). Fortunately the difference becomes less relevant the more times you apply the blur (even a box filter will approximate a Gaussian blur if applied several times). If you can determine whether you need a Gaussian blur with a precise parameter or just a blur that is Gaussian with an adjustable parameter, then you'll be able to decide whether a repeated box-style filter will be sufficient. $\endgroup$ – trichoplax May 15 '16 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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