Search code examples
glslprocedural-generationtexturing

How to find the intersection points in cell noise / voronoi in GLSL?

I am extremely curious about how I can find the intersection points of voronoi cells. How can I find the positions of the points?

Basically, I would like to create a small circle at the points of intersection. Much like this:

enter image description here

I want a pure glsl implementation. I have tried a lot but cannot get my head around it. One possible algorithm I found was from this video on youtube: https://www.youtube.com/watch?v=Y5X1TvN9TpM

However, it's very unclear to me how to implement that.

I know a possible solution which is to find the points using some algorithm such as harris corner detection but that isn't really a glsl solution.

Glsl code that produces normal voronoi:

#ifdef GL_ES
precision mediump float; 
#endif

uniform vec2 u_resolution; 
uniform vec2 u_mouse; 
uniform float u_time; 


vec2 rand(vec2 co){
    return vec2(fract(sin(dot(co, vec2(12.9898, 78.233))) * 43758.5453), fract(sin(dot(co, vec2(78.9898, 32.233))) * 237374.5453));
}

void main() {
    vec2 st = vec2(gl_FragCoord.xy) / u_resolution.xy; 

    st *= 10.;
    vec2 i_st = floor(st);
    vec2 f_st = fract(st); 
    float m_dist = 1.;
    float intensity = u_mouse.x / u_resolution.x;

    for (int x = -1; x <= 1; ++x) {
        for (int y = -1; y <= 1; y++){
            vec2 neighbor = vec2(x, y); 
            vec2 point = rand(i_st + neighbor); 
            vec2 diff = neighbor + point * intensity - f_st; 
            float dist = length(diff); 
            m_dist = min(dist,m_dist);
        } 
    }


    gl_FragColor = vec4(vec3(m_dist), 1.);
}
Solution

  • The intersection points of a voronoi diagram are always equidistant from the three nearest cell-cores so they are the circumcenter of the triangle formed by those three points. Here is a formula to compute it's coordinates.

    If your goal is to draw circles around the intersections, you can first find the three nearest cell-cores coordinates from the point you consider. Then then compute the coordinates of the circumcenter and finaly the distance from it to your point. You can then use a smoothstep() to draw a small circle and not a cicular gradient.