Drawing outline of intersecting circles

Question

I have a set of points and each one has an area of "influence" or essentially a radius. I would like to be able to draw each one of these influence circles for all the points as a simple circular line.

They will overlap however I wish to draw the outside of the shape formed. I know this would probably require me working out where they intersect and somehow forming a total shape to draw. The problem is that some points might not even touch others! So I need to be able to work that out too.

I have attempted to illustrate what I mean simply:

Note that I wish to draw simply the black line, no fill. This is because I wish background images and other geometry to show through.

I would be doing this in openGL so the circle would be probably made using GL_LINES or some such with various vertices forming the curves but I really just don't have any idea about how I would work out this perimeter.

If anyone has any advice or could point me at how I might go about working this out it would be greatly appreciated!

This might be more of a maths question, I am not looking for bits of code but actually how to go about working out these shapes. I just can't think about how to do it!

*****Edit: with the solution I came up with, hopefully might help someone else!

So I used the suggested ideas and basically decided the best way would be to draw using the stencil buffer. This now means that I loop through my points 3 times but I need to do some careful sorting of them to find only visible ones anyway.

So code wise I now have this:

private void stencilCircleAroundStars()
{
    //Lets try and draw something here using stencil
    glColorMask(false, false, false, false); //Disable colour mask
    glEnable(GL_STENCIL_TEST); // Enable Stencil Buffer For "marking" the outer circle
    glDisable(GL_DEPTH_TEST);// Disable Depth Testing

    for (Object value : stars.values())
    {
        Star star = (Star)value;

        glStencilFunc(GL_ALWAYS, 1, 1); // Always Passes, 1 Bit Plane, 1 As Mask
        glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE); // We Set The Stencil Buffer To 1 Where We Draw Any Polygon

        //Draw the large circle
        starOb.location.copy(star.location);
        starOb.setScale(2000);
        starOb.draw();
    }

    for (Object value : stars.values())
    {
        Star star = (Star)value;
        //Now we change the functions and remove a slightly smaller circle from buffer.
        glStencilFunc(GL_ALWAYS, 0, 0); // Always passes, 0 bit plane, 0 as mask;
        glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE); // We Set The Stencil Buffer To 0 Where We Draw Any Polygon
        starOb.location.copy(star.location);
        starOb.setScale(1900);
        starOb.draw();
    }

    //Now we enable the colour
    glColorMask(true, true, true, true);
    glStencilFunc(GL_EQUAL, 1, 1); // We Draw Only Where The Stencil Is 1
    glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP); // Don't Change The Stencil Buffer

    glColor4f(0.5f, 1.0f, 0.5f, 0.5f);
    for (Object value : stars.values())
    {
        Star star = (Star)value;
        starOb.location.copy(star.location);
        starOb.setScale(2000);
        starOb.draw();
    }

    //Now we are done .. disable
    glDisable(GL_STENCIL_TEST);  
}

My points are in essence entities called "stars" for the purpose of my program and StarOb is a collection of quads I have loaded from a file which form a nice smooth circle.

I disable colour mask and I loop through once, drawing the largest circle I can into the stencil buffer and setting a value of 1. I then loop around again drawing the smaller scaled circle into the stencil buffer but this time setting a value of 0. This should leave a border around any star that is not touching other stars and will effectively remove where they overlap.

I finally re-enable the colour mask and actually draw the coloured circles. the stencil buffer stops the insides from being rendered and I get what I wanted! I then disable the stencil buffer.

If you really wanted to see it, here's a video of generating several increasing amounts of points: Video of it running

Here is a low quality version of how it came out (background was not drawn while testing):

Answer 1

First, imagine the background was not there. I'm pretty sure you'd know how to do it, draw each circle then draw their insides (as in a filled circle) to remove the arcs that are inside.

Now to do the same over an image, you could do either of these things. One thing you can do is to disable writing on the color buffer, do that procedure and change the stencil buffer. Then enable writing on the color buffer and draw a whole screen rectangle which consequently fills the pixels you have marked in the stencil buffer.

The stencil buffer may not be usable to you however for a couple of reasons, such as you are using it for something else. In this case, an alternative would be to do the same thing, but instead of rendering in the stencil buffer, you render in a texture. Then bind that texture and draw a rectangle on the screen.

I'm quite certain you could achieve this with the accumulation buffer too, but I have never used it so I can't really tell (if anyone knows about that, please edit my answer and tell us how)

Answer 2

Two passes:

1. Draw all your circle outlines via GL_LINES or GL_LINE_LOOP. Make sure you set your glLineWidth() to 3 or greater.
2. Draw filled circles (GL_TRIANGLE_STRIP can be useful) with your "background" color and the same radius as the circles from step 1.

The filled circles in step 2 will overwrite all the outline pixels from step 1 but only where they overlap. That leaves you with non-overlapping outlines intact.

If you want a wider range of outline widths (i.e., greater than the ~10 that most OpenGL implementations allow glLineWidth()) you should reuse the filled-circle renderer from step 2 in step 1 except with a larger radius.