<h1>A few different approaches</h1>

<p>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.</p>

<h1>Blurring the volume instead of the surface</h1>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<h1>Using 2D distance instead of 3D distance</h1>

<p>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.</p>

<h1>3D distance using the surface without the volume</h1>

<p>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.)</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<h1>Effects from arbitrarily many edges away</h1>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-05-14T23:28:35.730Z
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.
Museful
CC BY-SA 3.0
2016-05-14T23:28:54.640Z
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.
Museful
CC BY-SA 3.0
2016-05-14T23:29:34.767Z
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.)
Museful
CC BY-SA 3.0
2016-05-14T23:30:08.583Z
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?
Museful
CC BY-SA 3.0
2016-05-15T00:44:22.903Z
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.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-05-15T07:42:21.683Z
If the blur is to be performed by repeated convolution with a local (1-hop-neighborhood) kernel, that kernel (or "box") would have to vary from vertex to vertex, because the valence and/or neighborhood geometry may vary from vertex to vertex. I think what matters most is that the (per-vertex) kernels' means/centroids and variances/moments of inertia must be consistent. These constraints would fully determine a valence-3 vertex's kernel's weights, but in cases of higher valence perhaps any kernel complying with these constraints will eventually converge to the effect of a Gaussian kernel.
Museful
CC BY-SA 3.0
2016-05-15T11:38:20.457Z
I see. Rereading the question I see I misread the start and thought the main focus was a 3D distance approach. I'll have another look and edit the answer in a while.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-05-16T18:02:46.193Z
I have a feeling that [this discretization of the Laplace-Beltrami operator](http://computergraphics.stackexchange.com/a/1721/3294) ("cotan formula") may give the right weights to attribute to the edges in the mesh. When applied to (ambient space) coordinates of the surface itself, the operator yields the mean curvature normal, but in general when applied to some function defined over the surface, the operator yields the (generalized) Laplacian, or divergence of the function's gradient on that surface, I think.
Museful
CC BY-SA 3.0
2016-05-16T18:14:58.950Z
Once we have the Laplacian we can diffuse the initial function over the surface just like heat i.e. $\frac{\partial f}{\partial t}=-\Delta_S f$. Doing so with explicit Euler method may be tantamount to the local mixing we had in mind. Not sure what time-step to choose for good numerical properties. A large time-step means higher variance per iteration and therefore fewer iterations needed, but it would also mean we aren't staying true to the PDE, and I'm not sure at what step-size that begins to matter.
Museful
CC BY-SA 3.0
2016-05-14T12:59:19.210Z
2016-05-14T13:09:26.750Z
2016-05-14T13:09:26.750Z
trichoplax is on Codidact now
<p>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.</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2016-05-13T16:18:50.413Z
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?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-05-13T17:11:29.177Z
@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.
Museful
CC BY-SA 3.0
2016-05-14T11:56:59.197Z
@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?
Museful
CC BY-SA 3.0
2016-05-15T15:49:26.570Z
@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
joojaa
CC BY-SA 3.0
2016-05-15T17:38:45.307Z
@joojaa Yes I think that is the best approach but how exactly does the small blur work, as the connections/edges of a mesh are not generally regular, like they are between, say, pixels in an image. The mesh geometry should somehow influence how "conductive" each edge is relative to other edges in its neighborhood. How?
Museful
CC BY-SA 3.0
2016-05-15T18:04:02.593Z
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.
joojaa
CC BY-SA 3.0
2016-05-16T18:26:40.580Z
@joojaa Thanks for helping me realize it's just diffusion ala $\frac{\partial f}{\partial t}=-\nabla_S f$ with the Laplace-Beltrami operator. I'm thinking of running explicit Euler using [this discretization of the operator](http://computergraphics.stackexchange.com/a/1721/3294). Not sure what time-step to use.
Museful
CC BY-SA 4.0
2019-04-15T12:35:31.833Z
(Know it's a bit late to contribute to this post). You can also try to discretize the convolution integral, but in tangent space. Namely if $U$ is the patch of your mesh $$g = \int_U K f dU \approx  \sum_{v_i} K(v_i)f(v_i) \Delta A_i, $$
where $\Delta A_i$ is the differential area that should come out from your discretization, few approaches of this discretization are given in the link mentioned in the previous comment.
user8469759
<mesh><gaussian-blur>
Gaussian blurring a function defined over a surface mesh
Museful
# Gaussian blurring a function defined over a surface mesh

(Asked by: username_0 on 2016-05-13)

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.

**Tags:** mesh, gaussian-blur

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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.  
> **username_0**: @username_2 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?  
> **username_2**: @username_0 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  
> **username_0**: @username_2 Yes I think that is the best approach but how exactly does the small blur work, as the connections/edges of a mesh are not generally regular, like they are between, say, pixels in an image. The mesh geometry should somehow influence how "conductive" each edge is relative to other edges in its neighborhood. How?  
> **username_2**: 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.  
> **username_0**: @username_2 Thanks for helping me realize it's just diffusion ala $\frac{\partial f}{\partial t}=-\nabla_S f$ with the Laplace-Beltrami operator. I'm thinking of running explicit Euler using [this discretization of the operator](http://computergraphics.stackexchange.com/a/1721/3294). Not sure what time-step to use.  
> **username_3**: (Know it's a bit late to contribute to this post). You can also try to discretize the convolution integral, but in tangent space. Namely if $U$ is the patch of your mesh $$g = \int_U K f dU \approx  \sum_{v_i} K(v_i)f(v_i) \Delta A_i, $$ where $\Delta A_i$ is the differential area that should come out from your discretization, few approaches of this discretization are given in the link mentioned in the previous comment.  

---

## 1 answers

### Answer by username_1 on 2016-05-14. Score: 7 | Accepted answer

# 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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: 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.)  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: If the blur is to be performed by repeated convolution with a local (1-hop-neighborhood) kernel, that kernel (or "box") would have to vary from vertex to vertex, because the valence and/or neighborhood geometry may vary from vertex to vertex. I think what matters most is that the (per-vertex) kernels' means/centroids and variances/moments of inertia must be consistent. These constraints would fully determine a valence-3 vertex's kernel's weights, but in cases of higher valence perhaps any kernel complying with these constraints will eventually converge to the effect of a Gaussian kernel.  
> **username_1**: I see. Rereading the question I see I misread the start and thought the main focus was a 3D distance approach. I'll have another look and edit the answer in a while.  
> **username_0**: I have a feeling that [this discretization of the Laplace-Beltrami operator](http://computergraphics.stackexchange.com/a/1721/3294) ("cotan formula") may give the right weights to attribute to the edges in the mesh. When applied to (ambient space) coordinates of the surface itself, the operator yields the mean curvature normal, but in general when applied to some function defined over the surface, the operator yields the (generalized) Laplacian, or divergence of the function's gradient on that surface, I think.  
> **username_0**: Once we have the Laplacian we can diffuse the initial function over the surface just like heat i.e. $\frac{\partial f}{\partial t}=-\Delta_S f$. Doing so with explicit Euler method may be tantamount to the local mixing we had in mind. Not sure what time-step to choose for good numerical properties. A large time-step means higher variance per iteration and therefore fewer iterations needed, but it would also mean we aren't staying true to the PDE, and I'm not sure at what step-size that begins to matter.  

---

