Incomplete Light Circle

Question

I've made a lighting engine which allows for shadows. It works on a grid system where each pixel has a light value stored as an integer in an array. Here is a demonstration of what it looks like:

The shadow and the actual pixel coloring works fine. The only problem is the unlit pixels further out in the circle, which for some reason makes a very interesting pattern(you may need to zoom into the image to see it). Here is the code which draws the light.

public void implementLighting(){
    lightLevels = new int[Game.WIDTH*Game.HEIGHT];
    //Resets the light level map to replace it with the new lighting
    for(LightSource lightSource : lights) {
        //Iterates through all light sources in the world
        double circumference =  (Math.PI * lightSource.getRadius() * 2),
                segmentToDegrees = 360 / circumference, distanceToLighting = lightSource.getLightLevel() / lightSource.getRadius();
                //Degrades in brightness further out
        for (double i = 0; i < circumference; i++) {
            //Draws a ray to every outer pixel of the light source's reach
            double radians =  Math.toRadians(i*segmentToDegrees),
                    sine =  Math.sin(radians),
                    cosine =  Math.cos(radians),
                    x = lightSource.getVector().getScrX() + cosine,
                    y = lightSource.getVector().getScrY() + sine,
                    nextLit = 0;
            for (double j = 0; j < lightSource.getRadius(); j++) {
                int lighting = (int)(distanceToLighting * (lightSource.getRadius() - j));
                        double pixelHeight = super.getPixelHeight((int) x, (int)y);
                if((int)j==(int)nextLit) addLighting((int)x, (int)y, lighting);
                //If light is projected to have hit the pixel
                if(pixelHeight > 0) {
                    double slope = (lightSource.getEmittingHeight() - pixelHeight) / (0 - j);
                    nextLit = (-lightSource.getRadius()) / slope;
                    /*If something is blocking it
                    * Using heightmap and emitting height, project where next lit pixel will be
                     */
                }
                else nextLit++;
                //Advances the light by one pixel if nothing is blocking it
                x += cosine;
                y += sine;
            }
        }
    }
    lights = new ArrayList<>();
}

The algorithm i'm using should account for every pixel within the radius of the light source not blocked by an object, so i'm not sure why some of the outer pixels are missing. Thanks.

EDIT: What I found is, the unlit pixels within the radius of the light source are actually just dimmer than the other ones. This is a consequence of the addLighting method not simply changing the lighting of a pixel, but adding it to the value that's already there. This means that the "unlit" are the ones only being added to once. To test this hypothesis, I made a program that draws a circle in the same way it is done to generate lighting. Here is the code that draws the circle:

    BufferedImage image = new BufferedImage(WIDTH, HEIGHT, 
    BufferedImage.TYPE_INT_RGB);
    Graphics g = image.getGraphics();
    g.setColor(Color.white);
    g.fillRect(0, 0, WIDTH, HEIGHT);
    double radius = 100,
            x = (WIDTH-radius)/2,
            y = (HEIGHT-radius)/2,
            circumference = Math.PI*2*radius,
            segmentToRadians = (360*Math.PI)/(circumference*180);
    for(double i = 0; i < circumference; i++){
        double radians = segmentToRadians*i,
                cosine = Math.cos(radians),
                sine = Math.sin(radians),
                xPos = x + cosine,
                yPos = y + sine;
        for (int j = 0; j < radius; j++) {
            if(xPos >= 0 && xPos < WIDTH && yPos >= 0 && yPos < HEIGHT) {
                int rgb = image.getRGB((int) Math.round(xPos), (int) Math.round(yPos));
                if (rgb == Color.white.getRGB()) image.setRGB((int) Math.round(xPos), (int) Math.round(yPos), 0);
                else image.setRGB((int) Math.round(xPos), (int) Math.round(yPos), Color.red.getRGB());
            }
            xPos += cosine;
            yPos += sine;
        }
    }

Here is the result:

The white pixels are pixels not colored The black pixels are pixels colored once The red pixels are pixels colored 2 or more times

So its actually even worse than I originally proposed. It's a combination of unlit pixels, and pixels lit multiple times.

Answer 1

You should iterate over real image pixels, not polar grid points.

So correct pixel-walking code might look as

for(int x = 0; x < WIDTH; ++x) {
  for(int y = 0; y < HEIGHT; ++y) {
    double distance = Math.hypot(x - xCenter, y - yCenter);
    if(distance <= radius) {
      image.setRGB(x, y, YOUR_CODE_HERE);
    }
  }
}

Of course this snippet can be optimized choosing good filling polygon instead of rectangle.

Answer 2

This can be solved by anti-aliasing.

Because you push float-coordinate information and compress it , some lossy sampling occur.

double x,y  ------(snap)---> lightLevels[int ?][int ?]

To totally solve that problem, you have to draw transparent pixel (i.e. those that less lit) around that line with a correct light intensity. It is quite hard to calculate though. (see https://en.wikipedia.org/wiki/Spatial_anti-aliasing)

Workaround

An easier (but dirty) approach is to draw another transparent thicker line over the line you draw, and tune the intensity as needed.

Or just make your line thicker i.e. using bigger blurry point but less lit to compensate.
It should make the glitch less obvious.
(see algorithm at how do I create a line of arbitrary thickness using Bresenham?)

An even better approach is to change your drawing approach.
Drawing each line manually is very expensive.
You may draw a circle using 2D sprite.
However, it is not applicable if you really want the ray-cast like in this image : http://www.iforce2d.net/image/explosions-raycast1.png

Split graphic - gameplay

For best performance and appearance, you may prefer GPU to render instead, but use more rough algorithm to do ray-cast for the gameplay.

Nonetheless, it is a very complex topic. (e.g. http://www.opengl-tutorial.org/intermediate-tutorials/tutorial-16-shadow-mapping/ )

Reference

Here are more information:

• http://what-when-how.com/opengl-programming-guide/antialiasing-blending-antialiasing-fog-and-polygon-offset-opengl-programming/ (opengl-antialias with image)

• DirectX11 Non-Solid wireframe (a related question about directx11 with image)