import PIL.Image
import math
image = PIL.Image.open('crab_nebula.png')
# Round the image width and height to multiples of 256.
image = image.crop((0, 0, math.ceil(image.width/256)*256,math.ceil(image.height/ 256)*256))
# Add a 2-pixel padding on tile edges.
padding = 2
# Each level halve the width/height, 
# hence we need log(256) levels to shrink a tile into a single pixel.
for lv in range(0,math.floor(math.log(256,2))+1):
    # How much we need to resize the original image for this level.
    resize_ratio = math.pow(2, lv)
    scaled_width = int(image.width / resize_ratio)
    scaled_height = int(image.height / resize_ratio)
    resized_image = image.resize((scaled_width, scaled_height))
    # h,v are the horizontal and vertical tile counts.
    h = math.ceil(scaled_width / 256)
    v = math.ceil(scaled_height / 256)
    for y in range(0,v):
        for x in range(0,h):
            # Crop a tile, the size of a tile is 260x260 including the padding.
            cropped_image = resized_image.crop((x*256-padding, y*256-padding, (x+1)*256+padding,(y+1)* 256+padding))
            # Save the tile into a png file.
            cropped_image.save('../crab_nebula/crab_'+str(lv)+'_'+str(y)+'_'+str(x)+'.png')

const imageWidth = 10752;
const imageHeight = 9216;
const tileSizeWithoutPadding = 256;
const textureSizeWithoutPadding = 2048;
const padding = 2;
const maxVisibleTileCountOnTexture = textureSizeWithoutPadding * textureSizeWithoutPadding / (tileSizeWithoutPadding * tileSizeWithoutPadding);
const levelCount = Math.log2(tileSizeWithoutPadding) + 1;

const tileH = Math.ceil(imageWidth / tileSizeWithoutPadding);
const tileV = Math.ceil(imageHeight / tileSizeWithoutPadding);

let levelTileCount = [];

for (let l = 0; l < levelCount; ++l) {
    const leveltileSizeWithoutPadding = tileSizeWithoutPadding * Math.pow(2, l);

    const levelTileH = Math.ceil(imageWidth / leveltileSizeWithoutPadding);
    const levelTileV = Math.ceil(imageHeight / leveltileSizeWithoutPadding);

    levelTileCount.push(...[levelTileH, levelTileV, leveltileSizeWithoutPadding, 0]);
}

let overallTileCount = 0;

for (let i = 0; i < levelCount; ++i) {
    overallTileCount += levelTileCount[i * 4] * levelTileCount[i * 4 + 1];
}

function keyToLevel(key) {
    let keyRemain = key;
    let level = 0;

    while (keyRemain >= levelTileCount[level * 4] * levelTileCount[level * 4 + 1]) {
        keyRemain -= levelTileCount[level * 4] * levelTileCount[level * 4 + 1];
        level += 1;
    }

    return { level, tileH: levelTileCount[level * 4], tileV: levelTileCount[level * 4 + 1], tileSizeWithoutPadding: levelTileCount[level * 4 + 2], keyRemain }
}

function key(width, height, x, y, level) {
    let base = 0;
    let tileH = 0;
    let tileV = 0;
    for (let i = 0; i < level; ++i) {
        tileH = Math.ceil(width / (tileSizeWithoutPadding * Math.pow(2, level)));
        tileV = Math.ceil(height / (tileSizeWithoutPadding * Math.pow(2, level)));
        base += tileH * tileV;
    }

    return y * tileH + x + base;
}

@group(0) @binding(0)
var transform: mat4x4;
@group(0) @binding(1)
var projection: mat4x4;

const tileSizeWithoutPadding:f32 = 256.0;

struct VertexOutput {
    @builtin(position) clip_position: vec4,
    @location(0) tex:vec2,
    @location(1) @interpolate(flat) tile:vec2
};

@vertex
fn vs_main(
    @location(0) inPos: vec4,
    @location(1) loc: vec2
) -> VertexOutput {
    var out: VertexOutput;
    out.tile = loc;
    out.tex = inPos.zw ;
    out.clip_position = projection * transform * vec4(inPos.xy + vec2(loc)*tileSizeWithoutPadding, 0.0, 1.0);
    return out;
}

@group(0)
@binding(2)
var level_tile_count: array, 8>; //must align to 16bytes
@group(0)
@binding(3)
var visible_tiles: array;
@fragment
fn fs_main(in: VertexOutput) -> @location(0) vec4 {
    var dx:vec2 = dpdx(in.tex * tileSizeWithoutPadding);
    var dy:vec2 = dpdy(in.tex * tileSizeWithoutPadding);
    var d:f32 = max(dot(dx, dx), dot(dy, dy));
    var level:f32 = min(max(f32(floor(0.5*log2(d))),0.0),8.0);

    var edge_size:f32 = pow(2, level) * tileSizeWithoutPadding;

    var x:f32 = (f32(in.tile.x) * tileSizeWithoutPadding + in.tex.x*tileSizeWithoutPadding) / edge_size;
    var y:f32 = (f32(in.tile.y) * tileSizeWithoutPadding + in.tex.y*tileSizeWithoutPadding) / edge_size;

    var base:i32 = 0;
    if (level > 0) {
        for(var i:i32 = 0;i
5_04_mega_texture/index.html:32-85 가시성 셰이더

const positionAttribDesc = {
    shaderLocation: 0, // @location(0)
    offset: 0,
    format: 'float32x4'
};

const positionBufferLayoutDesc = {
    attributes: [positionAttribDesc],
    arrayStride: 4 * 4, // sizeof(float) * 4
    stepMode: 'vertex'
};

const positions = new Float32Array([
    tileSizeWithoutPadding, 0.0, 1.0, 0.0,
    tileSizeWithoutPadding, tileSizeWithoutPadding, 1.0, 1.0,
    0.0, 0.0, 0.0, 0.0,
    0.0, tileSizeWithoutPadding, 0.0, 1.0
]);

this.positionBuffer = createGPUBuffer(device, positions, GPUBufferUsage.VERTEX);

let tiles = [];

for (let y = 0; y < tileV; ++y) {
    for (let x = 0; x < tileH; ++x) {
        tiles.push(x);
        tiles.push(y);
    }
}

const tileLocAttribDesc = {
    shaderLocation: 1, // @location(0)
    offset: 0,
    format: 'uint32x2'
};

const tileLocBufferLayoutDesc = {
    attributes: [tileLocAttribDesc],
    arrayStride: 4 * 2, // sizeof(int) * 3
    stepMode: 'instance'
};

this.tileLocBuffer = createGPUBuffer(device, new Uint32Array(tiles), GPUBufferUsage.VERTEX);

const levelTileCountBuffer = createGPUBuffer(device, new Uint32Array(levelTileCount), GPUBufferUsage.UNIFORM);

this.tileVisibilityBufferZeros = createGPUBuffer(device, new Uint32Array(overallTileCount), GPUBufferUsage.COPY_SRC);
this.tileVisibilityBuffer = createGPUBuffer(device, new Uint32Array(overallTileCount), GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC | GPUBufferUsage.COPY_DST);
this.tileVisibilityBufferRead = createGPUBuffer(device, new Uint32Array(overallTileCount), GPUBufferUsage.MAP_READ | GPUBufferUsage.COPY_DST);

encodeVisibility(encoder) {
    encoder.setPipeline(this.visibilityPipeline);
    encoder.setBindGroup(0, this.uniformBindGroupVisibility);
    encoder.setVertexBuffer(0, this.positionBuffer);
    encoder.setVertexBuffer(1, this.tileLocBuffer);
    encoder.draw(4, tileH * tileV);
}

commandEncoder.copyBufferToBuffer(tile.tileVisibilityBufferZeros, 0,
    tile.tileVisibilityBuffer, 0, overallTileCount * 4);
const passEncoder = commandEncoder.beginRenderPass(renderPassDesc);
passEncoder.setViewport(0, 0, canvas.width, canvas.height, 0, 1);
tile.encodeVisibility(passEncoder);
passEncoder.end();
commandEncoder.copyBufferToBuffer(tile.tileVisibilityBuffer, 0,
    tile.tileVisibilityBufferRead, 0, overallTileCount * 4);

await tile.tileVisibilityBufferRead.mapAsync(GPUMapMode.READ, 0, overallTileCount * 4);

let vb = tile.tileVisibilityBufferRead.getMappedRange(0, overallTileCount * 4);

vb = new Uint32Array(vb);
let vt = [];
for (let i = 0; i < overallTileCount; ++i) {
    if (vb[i] == 1) {
        vt.push(i);
    }
}
tile.tileVisibilityBufferRead.unmap();

await visibleTiles.assembleTexture(device, imageWidth,
    imageHeight, vt);

class KeyIdManager {

    constructor() {
        this.used = new Map();
        this.available = [];

        for (let i = 0; i < maxVisibleTileCountOnTexture; ++i) {
            this.available.push(i);
        }
    }

    async generate(keys, loadTileIntoTexture) {
        let newUsed = new Map();
        let result = [];

        //1. gather tiles that should be visible for the next round
        let keySet = new Set();
        for (let k of keys) {
            keySet.add(k);
        }

        //2. eliminate tiles that are not visible this round but was visible in the previous round, by
        // adding them into the available array
        for (const [uk, uv] of this.used) {
            if (!keySet.has(uk)) {
                this.available.push(uv);
            }
        }

        //3. for all visible tiles
        console.log("number of keys", keys);
        for (let k of keys) {

            const l = keyToLevel(k);
            console.log("debug level", l)

            // if this tile was visible before, skip updating texture map
            if (this.used.has(k)) {
                const id = this.used.get(k);
                newUsed.set(k, id);
                result.push({ key: k, id });
            }
            else {
                const id = this.available.shift();
                newUsed.set(k, id);
                result.push({ key: k, id });
                const level = l.level;
                const x = l.keyRemain % l.tileH;
                const y = Math.floor(l.keyRemain / l.tileH);
                console.log("debug load tex", x, y, level);
                loadTileIntoTexture(x, y, level, k, id);
            }
        }
        this.used = newUsed;
        return result;
    }
}

async loadTileIntoTexture(device, bufferUpdate, imageWidth, imageHeight, x, y, level, tileKey, id) {
    const writeArray = new Float32Array(bufferUpdate.getMappedRange(tileKey * 2 * 4, 8));
    writeArray.set([(tileSizeWithoutPadding / textureSizeWithoutPadding) * (id % (textureSizeWithoutPadding / tileSizeWithoutPadding)),
    (tileSizeWithoutPadding / textureSizeWithoutPadding) * Math.floor(id / (textureSizeWithoutPadding / tileSizeWithoutPadding))]);

    const url = '../crab_nebula/crab_' + level + '_' + y + '_' + x + '.png';

    const response = await fetch(url);
    const blob = await response.blob();
    const imgBitmap = await createImageBitmap(blob);
    //console.log(url,imgBitmap.width, imgBitmap.height,{ width: tileSizeWithoutPadding+padding*2, height: tileSizeWithoutPadding+padding*2 });

    device.queue.copyExternalImageToTexture({ source: imgBitmap }, {
        texture: this.texture,
        origin: { x: (padding * 2 + tileSizeWithoutPadding) * (id % (textureSizeWithoutPadding / tileSizeWithoutPadding)), y: (padding * 2 + tileSizeWithoutPadding) * Math.floor(id / (textureSizeWithoutPadding / tileSizeWithoutPadding)) }
    }, { width: tileSizeWithoutPadding + padding * 2, height: tileSizeWithoutPadding + padding * 2 });
}

class VisibleTileHashTable {
    constructor() {
        this.texture = null;
        this.tileTexCoordBuffer = null;
        this.tileTexCoordBufferUpdate = null;
        this.keyIdManager = new KeyIdManager();
    }

    setup(device) {
        const textureDesc = {
            size: [textureSizeWithoutPadding + textureSizeWithoutPadding / tileSizeWithoutPadding * padding * 2, textureSizeWithoutPadding + textureSizeWithoutPadding / tileSizeWithoutPadding * padding * 2, 1],
            dimension: '2d',
            format: 'rgba8unorm',
            usage: GPUTextureUsage.RENDER_ATTACHMENT | GPUTextureUsage.TEXTURE_BINDING | GPUTextureUsage.COPY_DST | GPUTextureUsage.COPY_SRC
        };
        this.texture = device.createTexture(textureDesc);
        this.tileTexCoordBuffer = createGPUBuffer(device, new Float32Array(overallTileCount * 2), GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST);
        this.tileTexCoordBufferUpdate = createGPUBuffer(device, new Float32Array(overallTileCount * 2), GPUBufferUsage.COPY_SRC | GPUBufferUsage.MAP_WRITE);
    }

    async assembleTexture(device, imageWidth, imageHeight, tiles) {
        await this.tileTexCoordBufferUpdate.mapAsync(GPUMapMode.WRITE, 0, overallTileCount * 2 * 4);

        tiles = await this.keyIdManager.generate(tiles, async (x, y, level, k, id) => {
            await this.loadTileIntoTexture(device, this.tileTexCoordBufferUpdate, imageWidth, imageHeight, x, y, level, k, id);
        });

        console.log(tiles);

        this.tileTexCoordBufferUpdate.unmap();
    }
}

@group(0)
@binding(2)
var level_tile_count: array, 8>; //must align to 16bytes
@group(0)
@binding(3)
var hash: array >;
@group(0) @binding(4)
var t_diffuse: texture_2d;
@group(0) @binding(5)
var s_diffuse: sampler;

@fragment
fn fs_main(in: VertexOutput) -> @location(0) vec4 {
    var dx:vec2 = dpdxFine(in.tex * tileSizeWithoutPadding);
    var dy:vec2 = dpdyFine(in.tex * tileSizeWithoutPadding);
    var d:f32 = max(dot(dx, dx), dot(dy, dy));
    var level:f32 = min(max(f32(floor(0.5*log2(d))),0.0), 8.0);
    var edge_size:f32 =  pow(2, level) * tileSizeWithoutPadding;

    var x:f32 = (f32(in.tile.x) * tileSizeWithoutPadding + in.tex.x * tileSizeWithoutPadding) / edge_size;
    var y:f32 = (f32(in.tile.y) * tileSizeWithoutPadding + in.tex.y * tileSizeWithoutPadding) / edge_size;

    var base:i32 = 0;
    if (level > 0) {
        for(var i:i32 = 0;i
5_04_mega_texture/index.html:118-151 실제 렌더링을 수행하는 셰이더

let translateMatrix = glMatrix.mat4.lookAt(glMatrix.mat4.create(),
    glMatrix.vec3.fromValues(0, 0, 10), glMatrix.vec3.fromValues(0, 0, 0), glMatrix.vec3.fromValues(0.0, 1.0, 0.0));

let orthProjMatrix = glMatrix.mat4.ortho(glMatrix.mat4.create(), canvas.width * -0.5 * scale, canvas.width * 0.5 * scale, canvas.height * 0.5 * scale, canvas.height * -0.5 * scale, -1000.0, 1000.0);

let translateMatrixUniformBuffer = createGPUBuffer(device, translateMatrix, GPUBufferUsage.UNIFORM);

let projectionMatrixUniformBuffer = createGPUBuffer(device, orthProjMatrix, GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST);

    canvas.onmousedown = (e) => {
        isDragging = true;
        var rect = canvas.getBoundingClientRect();
        prevX = event.clientX - rect.left;
        prevY = event.clientY - rect.top;
        e.preventDefault();
        e.stopPropagation();
    }

    canvas.onmousemove = (e) => {
        if (isDragging) {
            var rect = canvas.getBoundingClientRect();
            x = event.clientX - rect.left;
            y = event.clientY - rect.top;

            let deltaX = prevX - x;
            let deltaY = prevY - y;

            pivotX += deltaX * scale;
            pivotY += deltaY * scale;

            updatedProjectionMatrix = glMatrix.mat4.ortho(glMatrix.mat4.create(), pivotX - canvas.width * 0.5 * scale, pivotX + canvas.width * 0.5 * scale, pivotY + canvas.height * 0.5 * scale, pivotY - canvas.height * 0.5 * scale, -1000.0, 1000.0);

            prevX = x;
            prevY = y;
            //requestAnimationFrame(render);
        }
        e.preventDefault();
        e.stopPropagation();
    }

    canvas.onmouseup = (e) => {
        isDragging = false;
        e.preventDefault();
        e.stopPropagation();
    }

    canvas.onwheel = (e) => {
        scale += e.deltaY * 0.01
        if (scale < 0.01) {
            scale = 0.01;
        }
        else if (scale > 100.0) {
            scale = 100.0;
        }

        console.log(scale);
        e.preventDefault();
        e.stopPropagation();

        updatedProjectionMatrix = glMatrix.mat4.ortho(glMatrix.mat4.create(), pivotX - canvas.width * 0.5 * scale, pivotX + canvas.width * 0.5 * scale, pivotY + canvas.height * 0.5 * scale, pivotY - canvas.height * 0.5 * scale, -1000.0, 1000.0);
    }
}