Fast Voxel Grid Traversal Algorithm

GridTraversal.java

public static void calcPoints( double y1, double x1, double y2, double x2,
        PointEmitter emitter )
{
    int x = (int) x1, y = (int) y1;
    int endX = (int) x2, endY = (int) y2;

    // deltaX and Y is how far we have to move in ray direction until we find a new cell in x or y direction
    // y = u + t * v, where u=(x1,x2) and v=(stepX,stepY) is the direction vector
    final double gridCellWidth = 1, gridCellHeight = 1;

    double deltaX = gridCellWidth / Math.abs(x2 - x1);
    int stepX = (int) Math.signum(x2 - x1);
    // frac(tmp) = tmp - (int) tmp
    double tmp = x1 / gridCellWidth;
    double maxX = deltaX * (1.0 - (tmp - (int) tmp));

    double deltaY = gridCellHeight / Math.abs(y2 - y1);
    int stepY = (int) Math.signum(y2 - y1);
    tmp = y1 / gridCellHeight;
    double maxY = deltaY * (1.0 - (tmp - (int) tmp));

    boolean reachedY = false, reachedX = false;

    emitter.set(y, x);
    // trace primary ray
    while (!(reachedX && reachedY))
    {
        if (maxX < maxY)
        {
            maxX += deltaX;
            x += stepX;
        } else
        {
            maxY += deltaY;
            y += stepY;
        }

        emitter.set(y, x);

        if (stepX > 0.0)
        {
            if (x >= endX)
                reachedX = true;

        } else if (x <= endX)
        {
            reachedX = true;
        }

        if (stepY > 0.0)
        {
            if (y >= endY)
                reachedY = true;

        } else if (y <= endY)
        {
            reachedY = true;
        }
    }
}


public static void calcPoints( final double lat1, final double lon1,
        final double lat2, final double lon2,
        final PointEmitter emitter,
        final double offsetLat, final double offsetLon,
        final double deltaLat, final double deltaLon )
{
    double y1 = (lat1 - offsetLat) / deltaLat;
    double x1 = (lon1 - offsetLon) / deltaLon;
    double y2 = (lat2 - offsetLat) / deltaLat;
    double x2 = (lon2 - offsetLon) / deltaLon;

    calcPoints(y1, x1, y2, x2, new PointEmitter()
    {
        @Override
        public void set( double lat, double lon )
        {
            // +.1 to move more near the center of the tile
            emitter.set((lat + .1) * deltaLat + offsetLat, (lon + .1) * deltaLon + offsetLon);
        }
    });
}