3
$\begingroup$

Question: Is there a modification of simple component-wise barycentric-based interpolation of vertex values (such as colors) that accounts for arbitrary positive non-zero weights assigned to these contributions to skew resulting values to favor stronger contributions (where magnitude equals strength)? If so, how does it work in algebraic terms (or as close to algebraic terms as possible)?

Background: I am working on an image filter that breaks down an image using statistical clustering into a set number of polygons with [3..8] sides using the average color within its area. I thought it would be interesting to use the centers of these polygons as vertices, build a Delaunay triangulation using these vertices, and then re-render the image by interpolating the vertices' colors across the surfaces of the resulting triangles using each vertex's source polygon's area as a weight to skew its contribution. My theory is that this would result in a stainglass sort of look, especially if I then rendered the edges around the paired Voronoi tessellation.

Ideally, what I am looking for is as follows:

  • If all the vertices have equal weight, the process will yield identical results to basic barycentric-based contributions.
  • If the vertices do not have equal weight, barycentric coordinate values of 0 or 1 will not be changed, but all intermediate values will be skewed to favor vertices with larger magnitudes.

I've tried Googling for a process that works in this way. Probably due to my limited mathematical literacy, I have not found anything close to what I want. If such a method exists, could you explain this process to me so I could implement it in a programming language that supports little more than algebra and select implemented mathematical functions (e.g., Python, Java, C++)?

EDIT:

ccorn's algorithm works! Below are some results from some very basic tests. In each of these pictures, the upper-left corner is red (255,0,0), the upper-right corner is green (0,255,0), and the lower-left corner is blue (0,0,255). Each of these runs represent setting different weights to each of the corners. I will list each of the corners' weights in RGB order (UL, UR, LL).

(1, 1, 1): standard case

standard interpolation

(400, 300, 200):

400,300,200

(100, 400, 900):

100,400,900

$\endgroup$
4
$\begingroup$

Proposal (untested):

  1. Interpolate the vertex weights $a_i>0$ alone, giving an interpolated total weight $a(x,y)$. The effect of this is that $$a(x,y) = \sum_i u_i(x,y)\,a_i>0$$ where $u_i(x,y)$ are the interpolation basis functions (e.g. tent functions), one per vertex, with nonnegative values and $\sum_i u_i(x,y) = 1$ everywhere.

  2. Interpolate the weighed color values $C_i = a_i c_i$, giving an interpolated total-weighed value $C(x,y)$. Behind the scenes, we have now $$C(x,y) = \sum_i u_i(x,y)\,a_i c_i$$

  3. Use $c(x,y) = \frac{C(x,y)}{a(x,y)}$ as interpolated color value. Obviously, we get $$c(x,y) = \sum_i \hat{u}_i(x,y)\,c_i \quad\text{where}\quad \hat{u}_i(x,y) = \frac{u_i(x,y)\,a_i}{a(x,y)}\geq0 \quad\text{and}\quad \sum_i \hat{u}_i(x,y) = 1$$ So this is indeed an interpolation.

Suppose you are interpolating with this method between vertices $i,j,k$ and, for the sake of exposition and without loss of generality, assume $a_i \geq a_j \geq a_k$. Then $a_i \geq a(x,y) \geq a_k$ and therefore $\hat{u}_i(x,y) \geq u_i(x,y)$ and $\hat{u}_k(x,y) \leq u_k(x,y)$. This is the weighing effect you wanted.

Nevertheless, at any vertex $i$, you get $u_i(x,y)=1$ and $u_j(x,y)=0$ for all $j\neq i$. This implies $a(x,y) = a_i$ and $c(x,y) = c_i$, as required.

As long as the interpolation basis functions $u_i$ are continuous across edges, i.e., interpolated values on edges depend only on the values at the two adjacent vertices, that continuity carries over to $a(x,y)$, $C(x,y)$ and therefore to $c(x,y)$.

$\endgroup$
  • $\begingroup$ Sorry it took me so long to approve. It took me a while to be able to test your algorithm. It seems to work very well; I will add some sample screenshots to the question so others can see that your approach works! $\endgroup$ – sadakatsu Sep 27 '14 at 17:40

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.