interesting algorithm

I chanced apon this yesterday, and I think I'm finally wrapping my head around it -- its an algorithm that basically allows for transforming a lot of data in a multipass fragment program, really really fast. Its sort of like you can transfer data from each pixel to every other pixel, using only x passes of a shader where x has a logarithmic relationship with the resolution.

The creators have only applied it in a couple ways, but one, which is soft shadows, seems kind of exciting. I'm sure there are even more applications for this in other places, too.

http://www.comp.nus.edu.sg/~tants/jfa.html

Also, I have implemented the Voronoi cells, if anyone wants to take a look at that I'll post it.

 

Voronoi cells are on my "to-do" list. I would love to see it!

 

Code (csharp):

1.  
2. // untested public version
3.  
4. function Start ()
5. {
6.     renderer.material.mainTexture = VoronoiTexture(512, 512, 50);
7. }
8.  
9. function VoronoiTexture (x : float, y : float, seedCount : int) : RenderTexture
10. {
11.     // plant seed pixels using the CPU
12.     var seedTex = new Texture2D(x,y);
13.     seedTex.wrapMode = TextureWrapMode.Repeat;
14.     Random.seed = position.x+position.y;
15.     var i = 0;
16.     for(i = 0; i < seedCount; i ++) {
17.         var xpos = Random.value;
18.         var ypos = Random.value;
19.         seedTex.SetPixel(x*xpos, y*ypos, Color(xpos, ypos, 1, (ypos+xpos) * 0.5));
20.     }
21.     seedTex.Apply();
22.    
23.     // Fill cells using jump flooding on the GPU : [url]http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf[/url]
24.     // You can also just render some cones, but I am trying to be all fancy
25.     var result : RenderTexture;
26.     var jumpMat = Material(Shader.Find("Procedural/VoronoiJumpFlood"));
27.     jumpMat.mainTexture = seedTex;
28.     var div = 2;
29.     while(div <= Mathf.Max(x, y)) {
30.         jumpMat.SetVector("_Offset", Vector4(1.00/div, 1.00/div, 0, 0));
31.         var step1 = Render(x, y, jumpMat);
32.         UnityEngine.Object.DestroyImmediate(jumpMat.mainTexture);
33.         jumpMat.mainTexture = step1;
34.         jumpMat.SetVector("_Offset", Vector4(-1.00/div, -1.00/div, 0, 0));
35.         result = Render(x, y, jumpMat);
36.         UnityEngine.Object.DestroyImmediate(jumpMat.mainTexture);
37.         jumpMat.mainTexture = result;
38.         div *= 2;
39.     }
40.     UnityEngine.Object.DestroyImmediate(jumpMat);
41.     return result;
42. }
43.  
44. static function Render (x : int, y : int, mat : Material) : RenderTexture
45. {
46.     var oldActive = RenderTexture.active;
47.     var result : RenderTexture = new RenderTexture(x,y,16);
48.     result.wrapMode = TextureWrapMode.Repeat;
49.     if(PowerOfTwo(x)  PowerOfTwo(y)) result.isPowerOfTwo = true;
50.     RenderTexture.active = result;
51.     for(var i =0; i < mat.passCount; i++)
52.     {
53.         Shader.SetGlobalVector("_TexelSize", Vector4(1.00/x,1.00/y,0,0));
54.         mat.SetPass(i);
55.         DrawFullScreenQuad ();
56.     }
57.     RenderTexture.active = oldActive;
58.     return result;
59. }
60.  
61. static function DrawFullScreenQuad ()
62. {
63.     GL.Clear(true, true, Color.clear);
64.     GL.PushMatrix();
65.     GL.LoadOrtho();
66.     GL.Begin(GL.QUADS);
67.         GL.TexCoord2(0, 0   );
68.         GL.Vertex3  (0, 0, 0);
69.         GL.TexCoord2(0, 1   );
70.         GL.Vertex3  (0, 1, 0);
71.         GL.TexCoord2(1, 1   );
72.         GL.Vertex3  (1, 1, 0);
73.         GL.TexCoord2(1, 0   );
74.         GL.Vertex3  (1, 0, 0);          
75.     GL.End();
76.     GL.PopMatrix();
77. }
78.  
79. static function PowerOfTwo (x : int) : int
80. {
81.     if(x == 2   ) return 1;
82.     if(x == 4   ) return 2;
83.     if(x == 8   ) return 3;
84.     if(x == 16  ) return 4;
85.     if(x == 32  ) return 5;
86.     if(x == 64  ) return 6;
87.     if(x == 128 ) return 7;
88.     if(x == 256 ) return 8;
89.     if(x == 512 ) return 9;
90.     if(x == 1024) return 10;
91.     if(x == 2048) return 11;
92.     if(x == 4096) return 12;
93.                   return 0;
94. }
95.  

Code (csharp):

1.  
2. Shader "VoronoiJumpFlood" {
3. Properties {
4.     _MainTex ("Base (RGB)", 2D) = "white" {}
5. }
6.  
7. SubShader {
8.     Pass {
9.  
10. CGPROGRAM
11. #pragma vertex vert
12. #pragma fragment frag
13. #pragma fragmentoption ARB_fog_exp2
14.  
15. #include "UnityCG.cginc"
16.  
17. float4 _Offset;
18. sampler2D _MainTex;
19.  
20. struct v2f {
21.     float4 pos : POSITION;
22.     float2  uv  : TEXCOORD0;
23. };
24.  
25. v2f vert (appdata_base v)
26. {
27.     v2f o;
28.     o.pos = mul( glstate.matrix.mvp, v.vertex);
29.     o.uv = v.texcoord.xy;
30.     return o;
31. }
32.  
33. inline float SqrMagnitude (float2 lhs, float2 rhs) {
34.     float2 s = lhs - rhs;
35.     return (s.x*s.x) + (s.y*s.y);
36. }
37.  
38. half4 frag (v2f i) : COLOR
39. {
40.     float2 th = tex2D(_MainTex, i.uv).xy;
41.     float2 n1 = tex2D(_MainTex, i.uv + float2(_Offset.x, 0)).xy;
42.     float2 n2 = tex2D(_MainTex, i.uv + float2(0, _Offset.y)).xy;
43.     float2 n3 = tex2D(_MainTex, i.uv + float2(_Offset.x, _Offset.y)).xy;
44.     float2 n4 = tex2D(_MainTex, i.uv + float2(_Offset.x, -_Offset.y)).xy;
45.  
46.     float2 if1 = SqrMagnitude(i.uv, th) < SqrMagnitude(i.uv, n1) ? th : n1;
47.     float2 if2 = SqrMagnitude(i.uv, if1) < SqrMagnitude(i.uv, n2) ? if1 : n2;
48.     float2 if3 = SqrMagnitude(i.uv, if2) < SqrMagnitude(i.uv, n3) ? if2 : n3;
49.     float2 if4 = SqrMagnitude(i.uv, if3) < SqrMagnitude(i.uv, n4) ? if3 : n4;
50.     return float4(if4,0,0);
51. }
52. //os = (os.x + os.y < 0.01) ? float4(-10, -10, 0, 0) : os;
53. ENDCG
54.     }
55. }
56.  
57. Fallback off
58. }
59.  

 

Forest, that is very cool. Do you know, performance-wise how this compares to Fortune's algorithm?

I hadn't though of it, but other things could be handled by the GPU too -- like influence maps for example.

 

This is so cool.

You think this could be used for super fast path finding? I'm about to scale back on game mechanics but if this somehow could be used...

I took the liberty of making it animatable to see performances (see attached). Since I know nothing about texture and shader, it's a good opportunity to learn. Is it this slow because of texture transfer?

Finally, while looking up voronoi, I stumbled upon a couple of cool links.
http://www.cs.unc.edu/~geom/hardware/
http://www.stoneschool.com/Work/Siggraph/2005/

 

I did the quickest conversion to c# because I wanted to play with it