{"id":231,"date":"2021-06-14T22:00:40","date_gmt":"2021-06-14T14:00:40","guid":{"rendered":"https:\/\/blog.indeex.club\/?p=231"},"modified":"2021-10-13T10:08:13","modified_gmt":"2021-10-13T02:08:13","slug":"%e8%bf%91%e9%82%bb%e6%8e%a2%e5%af%bb","status":"publish","type":"post","link":"https:\/\/blog.indeex.club\/index.php\/2021\/06\/14\/%e8%bf%91%e9%82%bb%e6%8e%a2%e5%af%bb\/","title":{"rendered":"\u8fd1\u90bb\u63a2\u5bfb"},"content":{"rendered":"<hr \/>\n<p><a class=\"wp-editor-md-post-content-link\" href=\"https:\/\/github.com\/gpuweb\/gpuweb\/wiki\/Implementation-Status\">WebGpu<\/a>\u5df2\u7ecf\u4f7f\u7528\u4e00\u6bb5\u65f6\u95f4\u4e86\uff0c\u505a\u4e2a\u8fd1\u90bb\u63a2\u5bfb\u7684\u6d4b\u8bd5\u3002<\/p>\n<p><img src=\"https:\/\/hungking.cc\/assets\/imgs\/indeex.cc\/neighbor1.gif\" alt=\"\u8fd1\u90bb\u63a2\u5bfb\" \/><\/p>\n<p>\u5c4f\u5e55\u88ab\u5206\u62109\u5757\uff0c\u7ea2\u8272\u7c92\u5b50\u4e3a\u89c2\u6d4b\u5bf9\u8c61\uff0c\u540c\u4e00\u5355\u5143\u683c\u4e2d\u7684\u7c92\u5b50\u663e\u793a\u4e3a\u9ec4\u8272\uff0c<br \/>\n\u79fb\u52a8\u5230\u4e0b\u4e00\u4e2a\u5355\u5143\u683c\u4e2d\u7684\u7c92\u5b50\u663e\u793a\u4e3a\u7eff\u8272\uff0c\u5176\u4ed6\u7c92\u5b50\u663e\u793a\u4e3a\u7070\u8272\u3002\u76f8\u90bb\u7c92\u5b50\u5e94\u8be5\u662f\u9760\u8fd1\u76ee\u6807\u5757\u7684\u7c92\u5b50\u3002<\/p>\n<p>\u6b64\u5916\uff0c\u8fd1\u90bb\u63a2\u5bfb\u4e2d\u4f7f\u7528\u4e86<a class=\"wp-editor-md-post-content-link\" href=\"https:\/\/blog.indeex.club\/index.php\/2020\/12\/12\/%e5%8f%8c%e8%b0%83%e6%8e%92%e5%ba%8f\/\">\u53cc\u8c03\u6392\u5e8f<\/a>\u3002<br \/>\n\u3002<\/p>\n<p>\u4e0b\u9762\u662f\u5b8c\u6574\u6d4b\u8bd5\u4f8b\u5b50\uff1a<\/p>\n<pre><code class=\"language-javascript line-numbers\">&lt;!DOCTYPE html&gt;\n&lt;html&gt;\n&lt;head&gt;\n    &lt;title&gt;\u8fd1\u90bb\u63a2\u5bfb\u6d4b\u8bd5-indeex&lt;\/title&gt;\n    &lt;meta charset=\"utf-8\"&gt;\n&lt;\/head&gt;\n&lt;body&gt;\n&lt;canvas id=\"webgpu-canvas\"&gt;&lt;\/canvas&gt;\n&lt;script&gt;\n(async () =&gt; {\n    const [adapter, glslang] = await Promise.all([\n        navigator.gpu.requestAdapter(),\n        import(\"https:\/\/unpkg.com\/@webgpu\/glslang@0.0.15\/dist\/web-devel\/glslang.js\").then(m =&gt; m.default())\n    ]);\n\n    const device = await adapter.requestDevice();\n\n    const canvas = document.getElementById(\"webgpu-canvas\");\n    canvas.width = 400;\n    canvas.height = 400;\n\n    const context = canvas.getContext(\"gpupresent\");\n\n    const swapChainFormat = \"bgra8unorm\"; \n    const swapChain = context.configureSwapChain({\n        device,\n        format: swapChainFormat\n    });\n\n    const powerN = 4;\n    const dataNum = 2 ** powerN;\n    const PARTICLE_NUM = dataNum;\n    const PARTICLE_SIZE = 3;\n    const POINT_SIZE = 0.04; \/\/ 0.02\n\n    const viewRadius = 0.2;\n    const bucketSize = 2.0 * viewRadius;\n    const bucketNum = Math.ceil(1.0 \/ bucketSize);\n    const bucketIndexNum = bucketNum * bucketNum; \/\/ 2d\n    const particleIndex = 0;\n\n    const positionData = new Float32Array(PARTICLE_NUM * PARTICLE_SIZE);\n    const velocityData = new Float32Array(PARTICLE_NUM * PARTICLE_SIZE);\n\n    var buckets = []; \/\/ for test\n\n    for (let i = 0 ; i &lt; positionData.length \/ PARTICLE_SIZE ; i++){\n        positionData[i * PARTICLE_SIZE + 0] = Math.random();\n        positionData[i * PARTICLE_SIZE + 1] = Math.random();\n        positionData[i * PARTICLE_SIZE + 2] = 0;\n\n        velocityData[i * PARTICLE_SIZE + 0] = (Math.random() * 2.0 - 1.0) * 0.002;\n        velocityData[i * PARTICLE_SIZE + 1] = (Math.random() * 2.0 - 1.0) * 0.002;\n        velocityData[i * PARTICLE_SIZE + 2] = 0.0;\n\n        \/\/ \u6d4b\u8bd5\n        var bucketX = Math.floor(positionData[i * PARTICLE_SIZE + 0] \/ bucketSize);\n        var bucketY = Math.floor(positionData[i * PARTICLE_SIZE + 1] \/ bucketSize);\n        var bucketIndex = bucketX + bucketY * bucketNum;\n        buckets.push([bucketIndex, i]);\n    }\n    \/\/console.log(\"position: \", positionData);\n\n    const positionBuffer = device.createBuffer({\n        size: positionData.byteLength,\n        usage: GPUBufferUsage.VERTEX | GPUBufferUsage.COPY_DST | GPUBufferUsage.STORAGE\n    });\n    device.defaultQueue.writeBuffer(positionBuffer, 0, positionData);\n\n    const velocityBuffer = device.createBuffer({\n        size: velocityData.byteLength,\n        usage: GPUBufferUsage.VERTEX | GPUBufferUsage.COPY_DST | GPUBufferUsage.STORAGE\n    });\n    device.defaultQueue.writeBuffer(velocityBuffer, 0, velocityData);\n\n    \/\/console.log(\"buckets: \", buckets);\n    let n = powerN;\n      for (let p = 0; p &lt; n; p++) {\n        for(let q = 0; q &lt;=p; q++) {\n\n            const d = 1 &lt;&lt; (p - q);\n\n            for (let i = 0; i &lt; buckets.length; i++) {\n                const up = ((i &gt;&gt; p) &amp; 2) === 0;\n                if ((i &amp; d) == 0 &amp;&amp; (buckets[i][0] &gt; buckets[i | d][0]) === up) {\n                    const tmp = buckets[i];\n                    buckets[i] = buckets[i | d];\n                    buckets[i | d] = tmp;\n                }\n            }\n        }\n      }\n      console.log(\"bukets sorted: \", buckets);\n\n    const bucketsArray = new Uint32Array(PARTICLE_NUM * 2);\n    const bucketsBuffer = device.createBuffer({\n        size: bucketsArray.byteLength,\n        usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST\n    });\n\n    const workBufferSize = bucketsArray.byteLength;\n    const workBuffer = device.createBuffer({\n        size: workBufferSize,\n        usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST\n    });\n\n    \/\/const resultBufferSize = bucketsArray.byteLength;\n    \/\/const resultBuffer = device.createBuffer({\n    \/\/    size: resultBufferSize,\n    \/\/    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC\n    \/\/    \/\/ \u6ce8\u610f resultBuffer\n    \/\/});\n\n    const bucketRefData = new Uint32Array(bucketIndexNum * 2);\n\n    for (let i = 0 ; i &lt; bucketIndexNum ; i++){\n        bucketRefData[i * 2 + 0] = 65535;\n        bucketRefData[i * 2 + 1] = 65535;\n    }\n    console.log(\"bucketRef: \", bucketRefData);\n\n    const bucketRefBuffer = device.createBuffer({\n        size: bucketRefData.byteLength,\n        usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST\n    });\n    device.defaultQueue.writeBuffer(bucketRefBuffer, 0, bucketRefData);\n\n    const neighbors = new Uint32Array(PARTICLE_NUM);\n    \/\/for (let i = 0 ; i &lt; PARTICLE_NUM ; i++){\n    \/\/    neighbors[i] = 65535;\n    \/\/}\n    \/\/console.log(\"neighbors: \", neighbors);\n\n    const neighborsBuffer = device.createBuffer({\n        size: neighbors.byteLength,\n        usage: GPUBufferUsage.VERTEX | GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST\n    });\n    \/\/device.defaultQueue.writeBuffer(neighborsBuffer, 0, neighbors);\n\n    \/\/const resultBufferSize = bucketRefData.byteLength; \/\/ for bucketRef\n    \/\/const resultBufferSize = neighbors.byteLength; \/\/ for findNeighbors\n    \/\/const resultBuffer = device.createBuffer({\n    \/\/    size: resultBufferSize,\n    \/\/    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC\n    \/\/    \/\/ \u6ce8\u610f resultBuffer: COPY_SRC\n    \/\/});\n\n    var uniformBuffer = device.createBuffer({\n        size: 2 * 4,\n        usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST\n    });\n\n    \/\/const particleUniformBuffer = device.createBuffer({\n    \/\/    size: 4,\n    \/\/    usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST\n    \/\/});\n\n    \/\/ shader (GLSL)\n    const computeShader_initialize_buckets = `\n    #version 450\n\n    \/\/ constants\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKET_NUM ${bucketNum}\n    #define BUCKET_SIZE ${bucketSize}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer Results {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    \/\/uint numbers[ BUCKETIDX_NUM * 2 ]; \/\/ for bucketRef\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    void main()\n    {\n        uint index = gl_GlobalInvocationID.x;\n        if ( index &gt;= PARTICLE_NUM ) { return; }\n\n        vec3 position = vec3(\n            particle.particle[ index * PARTICLE_SIZE + 0 ],\n            particle.particle[ index * PARTICLE_SIZE + 1 ],\n            particle.particle[ index * PARTICLE_SIZE + 2 ]\n        );\n\n        uint bucketX = uint( floor(position.x \/ BUCKET_SIZE) );\n        uint bucketY = uint( floor(position.y \/ BUCKET_SIZE) );\n        uint bucketIndex = bucketX + bucketY * BUCKET_NUM;\n        buckets[index * 2 + 0 ] = bucketIndex;\n        buckets[index * 2 + 1 ] = index;\n    }\n    `;\n\n    const computeShaderSort = `\n    #version 450\n\n    #define N ${powerN}\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer ResultData {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    \/\/uint numbers[ BUCKETIDX_NUM * 2 ]; \/\/ for bucketRef\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    const uint n = N;\n\n    void main() {\n        uint index = gl_GlobalInvocationID.x;\n\n        uint p = uint(pq.x);\n        uint q = uint(pq.y);\n\n        uint d = 1u &lt;&lt; (p - q);\n\n        bool up = ((index &gt;&gt; p) &amp; 2u) == 0u;\n        if ((index &amp; d) == 0 &amp;&amp; (buckets[index * 2 + 0] &gt; buckets[(index + d) * 2 + 0]) == up) {\n            workData.numbers[index * 2 + 0] = buckets[(index + d) * 2 + 0];\n            workData.numbers[index * 2 + 1] = buckets[(index + d) * 2 + 1];\n        } else if ((index &amp; d) == d &amp;&amp; (buckets[(index - d) * 2 + 0] &gt; buckets[index * 2 + 0]) == up) {\n            workData.numbers[index * 2 + 0] = buckets[(index - d) * 2 + 0];\n            workData.numbers[index * 2 + 1] = buckets[(index - d) * 2 + 1];\n        } else {\n            workData.numbers[index * 2 + 0] = buckets[index * 2 + 0];\n            workData.numbers[index * 2 + 1] = buckets[index * 2 + 1];\n        }\n    }\n    `;\n\n    const computeShaderWork = `\n    #version 450\n\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer ResultData {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    \/\/uint numbers[ BUCKETIDX_NUM * 2 ]; \/\/ for bucketRef\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    void main() {\n        uint index = gl_GlobalInvocationID.x;\n\n        buckets[index * 2 + 0] = workData.numbers[index * 2 + 0];\n        buckets[index * 2 + 1] = workData.numbers[index * 2 + 1];\n    }\n    `;\n\n    const computeShader_bucketRef = `\n    #version 450\n\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer ResultData {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    \/\/uint numbers[ BUCKETIDX_NUM * 2 ]; \/\/ for bucketRef\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    void main() {\n        \/\/ dispatch PARTICLE_NUM + 1 ( 0 to PARTICLE_NUM)\n        uint index = gl_GlobalInvocationID.x;\n\n        if (index == 0) {\n            uint refIndex_start = buckets[index * 2 + 0];\n            bucketRef[refIndex_start * 2 + 0] = 0;\n        } else if (index &lt; PARTICLE_NUM) {\n            uint refIndex_start = buckets[index * 2 + 0];\n            uint refIndex_end   = buckets[(index - 1) * 2 + 0];\n            if (refIndex_start != refIndex_end) {\n                bucketRef[refIndex_start * 2 + 0] = index;\n                bucketRef[refIndex_end   * 2 + 1] = index - 1;\n            }\n        } else {\n            uint refIndex_end   = buckets[(index - 1) * 2 + 0];\n            bucketRef[refIndex_end * 2 + 1] = index - 1;\n        }\n    }\n    `;\n\n    const computeShader_findNeighbors = `\n    #version 450\n\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKET_NUM ${bucketNum}\n    #define BUCKET_SIZE ${bucketSize}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n    #define particleIndex ${particleIndex}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer ResultData {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    \/\/uint numbers[ BUCKETIDX_NUM * 2 ]; \/\/ for bucketRef\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    void findNeighbors(uint index, ivec2 bucketPosition, uint neighborFlag) {\n        if (bucketPosition.x &lt; 0 || bucketPosition.x &gt;= BUCKET_NUM || bucketPosition.y &lt; 0 || bucketPosition.y &gt;= BUCKET_NUM) {\n            return;\n        }\n\n        uint bucketIndex = bucketPosition.x + BUCKET_NUM * bucketPosition.y;\n\n        uint cellStart = bucketRef[bucketIndex * 2 + 0];\n        uint cellEnd   = bucketRef[bucketIndex * 2 + 1];\n        if (cellStart == 65535 || cellEnd == 65535) {\n            return;\n        }\n\n        for (uint i = cellStart; i &lt;= cellEnd; i++) {\n            if (buckets[i * 2 + 1] == index) {\n                \/\/neighbors[index] = buckets[i * 2 + 1];\n                neighbors[index] = neighborFlag;\n            }\n        }\n    }\n\n    void main() {\n        uint index = gl_GlobalInvocationID.x;\n\n        uint pIndex = particleIndex;\n\n        vec2 position = vec2(\n            particle.particle[ pIndex * PARTICLE_SIZE + 0 ],\n            particle.particle[ pIndex * PARTICLE_SIZE + 1 ]\n        );\n\n        vec2 bucketPosition = position \/ BUCKET_SIZE;\n\n        int  xOffset = fract(bucketPosition.x) &lt; 0.5 ? -1: 1;\n        int  yOffset = fract(bucketPosition.y) &lt; 0.5 ? -1: 1;\n\n        ivec2 bucketPosition00 = ivec2(bucketPosition);\n        ivec2 bucketPosition10 = bucketPosition00 + ivec2(xOffset, 0);\n        ivec2 bucketPosition01 = bucketPosition00 + ivec2(0, yOffset);\n        ivec2 bucketPosition11 = bucketPosition00 + ivec2(xOffset, yOffset);\n\n        findNeighbors(index, bucketPosition00, 0);\n        findNeighbors(index, bucketPosition10, 100);\n        findNeighbors(index, bucketPosition01, 100);\n        findNeighbors(index, bucketPosition11, 100);\n\n    }\n    `;\n\n    const computeShaderRead = `\n    #version 450\n\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer ResultData {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    \/\/uint numbers[ BUCKETIDX_NUM * 2 ]; \/\/ for bucketRef\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    void main() {\n        uint index = gl_GlobalInvocationID.x;\n\n        \/\/ for buckets\n        \/\/resultData.numbers[index * 2 + 0 ] = buckets[index * 2 + 0];\n        \/\/resultData.numbers[index * 2 + 1 ] = buckets[index * 2 + 1];\n\n        \/\/ for bucketRef\n        \/\/resultData.numbers[index * 2 + 0 ] = bucketRef[index * 2 + 0];\n        \/\/resultData.numbers[index * 2 + 1 ] = bucketRef[index * 2 + 1];\n\n        \/\/ for neighbors\n        \/\/resultData.numbers[index] = neighbors[index];\n    }\n    `;\n\n    const computeShader_integrate = `\n    #version 450\n    #define PARTICLE_NUM ${PARTICLE_NUM}\n    #define PARTICLE_SIZE ${PARTICLE_SIZE}\n    #define BUCKETIDX_NUM ${bucketIndexNum}\n\n    layout(set = 0, binding = 0) buffer Particle {\n        float particle[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } particle;\n\n    layout(set = 0, binding = 1) buffer Velocity {\n        float velocity[ PARTICLE_NUM * PARTICLE_SIZE ];\n    } velocity;\n\n    layout(set = 0, binding = 2) buffer BucketsData {\n        uint buckets[ PARTICLE_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 3) buffer WorkData {\n        uint numbers[ PARTICLE_NUM * 2 ];\n    } workData;\n\n    layout(set = 0, binding = 4) buffer BucketRef {\n        uint bucketRef[ BUCKETIDX_NUM * 2 ];\n    };\n\n    layout(set = 0, binding = 5) buffer Neighbors {\n        uint neighbors[ PARTICLE_NUM ];\n    };\n\n    \/\/layout(set = 0, binding = 6) buffer ResultData {\n    \/\/    \/\/uint numbers[ PARTICLE_NUM * 2 ];\n    \/\/    uint numbers[ PARTICLE_NUM ]; \/\/ for findNeeighbors\n    \/\/} resultData;\n\n    layout(set = 0, binding = 7) uniform StepUniform {\n        vec2 pq;\n    };\n\n    \/\/layout(set = 0, binding = 8) uniform ParticleIndex {\n    \/\/    uint particleIndex;\n    \/\/};\n\n    void main() {\n        uint index = gl_GlobalInvocationID.x;\n        if ( index &gt;= PARTICLE_NUM ) { return; }\n\n        vec3 position = vec3(\n            particle.particle[ index * PARTICLE_SIZE + 0 ] + velocity.velocity[ index * PARTICLE_SIZE + 0 ],\n            particle.particle[ index * PARTICLE_SIZE + 1 ] + velocity.velocity[ index * PARTICLE_SIZE + 1 ],\n            particle.particle[ index * PARTICLE_SIZE + 2 ] + velocity.velocity[ index * PARTICLE_SIZE + 2 ]\n            \/\/    \/\/    particle.particle[ index * PARTICLE_SIZE + 0 ],\n            \/\/    \/\/    particle.particle[ index * PARTICLE_SIZE + 1 ],\n            \/\/    \/\/    particle.particle[ index * PARTICLE_SIZE + 2 ]\n        );\n        \/\/vec3 position =\n            \/\/    particle.particle[ index ] + velocity.velocity[ index ];\n\n        if ( position.x &lt;= 0.001 || position.x &gt;= 0.999 ) {\n            velocity.velocity[ index * PARTICLE_SIZE + 0 ] = - velocity.velocity[ index * PARTICLE_SIZE + 0 ];\n            \/\/velocity.velocity[ index ].x = - velocity.velocity[ index ].x;\n        }\n\n        \/\/if ( abs( position.y ) &gt;= ROOM_SIZE ) {\n        if ( position.y &lt;= 0.001 || position.y &gt;= 0.999 ) {\n            velocity.velocity[ index * PARTICLE_SIZE + 1 ] = - velocity.velocity[ index * PARTICLE_SIZE + 1 ];\n            \/\/velocity.velocity[ index ].y = - velocity.velocity[ index ].y;\n        }\n\n        \/\/if ( abs( position.z ) &gt;= ROOM_SIZE ) {\n        if ( position.z &lt;= 0.001 || position.z &gt;= 0.999 ) {\n            velocity.velocity[ index * PARTICLE_SIZE + 2 ] = - velocity.velocity[ index * PARTICLE_SIZE + 2 ];\n            \/\/velocity.velocity[ index ].z = - velocity.velocity[ index ].z;\n        }\n\n        particle.particle[ index * PARTICLE_SIZE + 0 ] = position.x;\n        particle.particle[ index * PARTICLE_SIZE + 1 ] = position.y;\n        particle.particle[ index * PARTICLE_SIZE + 2 ] = position.z;\n        \/\/particle.particle[ index ] = position;\n    }\n    `;\n\n    const bindGroupLayout = device.createBindGroupLayout({\n        entries: [\n        {\n            binding: 0,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"storage-buffer\"\n        },\n        {\n            binding: 1,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"storage-buffer\"\n        },\n        {\n            binding: 2,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"storage-buffer\"\n        },\n        {\n            binding: 3,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"storage-buffer\"\n        },\n        {\n            binding: 4,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"storage-buffer\"\n        },\n        {\n            binding: 5,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"storage-buffer\"\n        },\n        \/\/{\n        \/\/    binding: 6,\n        \/\/    visibility: GPUShaderStage.COMPUTE,\n        \/\/    type: \"storage-buffer\"\n        \/\/},\n        {\n            binding: 7,\n            visibility: GPUShaderStage.COMPUTE,\n            type: \"uniform-buffer\"\n        }\n        \/\/{\n        \/\/    binding: 8,\n        \/\/    visibility: GPUShaderStage.COMPUTE,\n        \/\/    type: \"uniform-buffer\"\n        \/\/}\n        ]\n    });\n\n    const bindGroup = device.createBindGroup({\n        layout: bindGroupLayout,\n        entries: [\n        {\n            binding: 0,\n            resource: {\n                buffer: positionBuffer\n            }\n        },\n        {\n            binding: 1,\n            resource: {\n                buffer: velocityBuffer\n            }\n        },\n        {\n            binding: 2,\n            resource: {\n                buffer: bucketsBuffer\n            }\n        },\n        {\n            binding: 3,\n            resource: {\n                buffer: workBuffer\n            }\n        },\n        {\n            binding: 4,\n            resource: {\n                buffer: bucketRefBuffer\n            }\n        },\n        {\n            binding: 5,\n            resource: {\n                buffer: neighborsBuffer\n            }\n        },\n        \/\/{\n        \/\/    binding: 6,\n        \/\/    resource: {\n        \/\/        buffer: resultBuffer\n        \/\/    }\n        \/\/},\n        {\n            binding: 7,\n            resource: {\n                buffer: uniformBuffer\n            }\n        }\n        \/\/{\n        \/\/    binding: 8,\n        \/\/    resource: {\n        \/\/        buffer: particleUniformBuffer\n        \/\/    }\n        \/\/}\n        ]\n    });\n\n    const computePipeline_InitializeBackets = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShader_initialize_buckets, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const computePipeline_Sort = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShaderSort, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const computePipeline_Work = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShaderWork, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const computePipeline_bucketRef = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShader_bucketRef, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const computePipeline_findNeighbors = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShader_findNeighbors, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const computePipeline_integrate = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShader_integrate, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const computePipeline_Read = device.createComputePipeline({\n        layout: device.createPipelineLayout({\n            bindGroupLayouts: [bindGroupLayout]\n        }),\n        computeStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(computeShaderRead, \"compute\")\n            }),\n            entryPoint: \"main\"\n        }\n    });\n\n    const vs = `\n    #version 450\n\n    layout(location=0) in vec3 vertexPosition;\n    layout(location=1) in vec3 instancePosition;\n    \/\/\n    layout(location=2) in uint neighbor;\n\n    layout(location = 0) out vec3 vColor;\n\n    const float scale = ${POINT_SIZE};\n\n    void main() {\n        mat4 scaleMTX = mat4(\n            scale, 0, 0, 0,\n            0, scale , 0, 0,\n            0, 0, scale, 0,\n            instancePosition, 1\n        );\n\n        uint id = gl_InstanceIndex;\n        if (id == 0) {\n            vColor = vec3(1.0, 0.0, 0.0);\n        } else if (neighbor == 0) {\n            vColor = vec3(1.0, 1.0, 0.0);\n        } else if (neighbor == 100) {\n            vColor = vec3(0.0, 1.0, 0.0);\n        } else {\n            vColor = vec3(0.7, 0.7, 0.7);\n        }\n\n        gl_Position = scaleMTX * vec4(vertexPosition, 1.0);\n    } \n    `;\n\n    const fs = `\n    #version 450\n\n    layout(location=0) in vec3 vColor;\n\n    layout(location=0) out vec4 fragColor;\n\n    void main() {\n        fragColor = vec4(vColor, 1.0);\n    } \n    `;\n\n    const cubeData = utils.createCube();\n    const numVertices = cubeData.positions.length \/ 3;\n\n    const vertexBuffer = device.createBuffer({\n        size: cubeData.positions.byteLength,\n        usage: GPUBufferUsage.VERTEX | GPUBufferUsage.COPY_DST\n    });\n    device.defaultQueue.writeBuffer(vertexBuffer, 0, cubeData.positions);\n\n    const pipeline = device.createRenderPipeline({\n        layout: device.createPipelineLayout({bindGroupLayouts: []}),\n        vertexStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(vs, \"vertex\")\n            }),\n            entryPoint: \"main\"\n        },\n        fragmentStage: {\n            module: device.createShaderModule({\n                code: glslang.compileGLSL(fs, \"fragment\")\n            }),\n            entryPoint: \"main\"\n        },\n        primitiveTopology: \"triangle-list\",\n        vertexState: {\n            vertexBuffers: [\n                {\n                    arrayStride: 12,\n                    attributes: [{\n                        shaderLocation: 0,\n                        format: \"float3\",\n                        offset: 0\n                    }]\n                },\n                {\n                    arrayStride: 12,\n                    stepMode: \"instance\",\n                    attributes: [{\n                        shaderLocation: 1,\n                        format: \"float3\",\n                        offset: 0\n                    }]\n                },\n                {\n                    arrayStride: 4,\n                    stepMode: \"instance\",\n                    attributes: [{\n                        shaderLocation: 2,\n                        format: \"uint\",\n                        offset: 0\n                    }]\n                },\n            ]\n        },\n        colorStates: [{\n            format: swapChainFormat\n        }]\n    });\n\n\n    \/\/const gpuReadBuffer = device.createBuffer({\n    \/\/    size: resultBufferSize,\n    \/\/    usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ\n    \/\/});\n\n    requestAnimationFrame(function draw() {\n\n        \/\/ clear neighbors\n        for (let i = 0 ; i &lt; PARTICLE_NUM ; i++){\n            neighbors[i] = 65535;\n        }\n        device.defaultQueue.writeBuffer(neighborsBuffer, 0, neighbors);\n\n    var commandEncoder = device.createCommandEncoder();\n    var passEncoder = commandEncoder.beginComputePass();\n\n    passEncoder.setPipeline(computePipeline_InitializeBackets);\n    passEncoder.setBindGroup(0, bindGroup);\n    passEncoder.dispatch(dataNum);\n\n    passEncoder.endPass();\n    device.defaultQueue.submit([commandEncoder.finish()]);\n\n    for (let p = 0; p &lt; powerN; p++) { \/\/ dataNum -&gt; powerN\n        for (let q = 0; q &lt;= p; q++) {\n            Sort(p, q);\n        }\n    }\n\n    var commandEncoder = device.createCommandEncoder();\n    var passEncoder = commandEncoder.beginComputePass();\n\n    passEncoder.setPipeline(computePipeline_bucketRef);\n    passEncoder.setBindGroup(0, bindGroup);\n    passEncoder.dispatch(dataNum + 1);\n\n    passEncoder.endPass();\n    device.defaultQueue.submit([commandEncoder.finish()]);\n\n    \/\/const particleIndexData = new Uint32Array([0]);\n    \/\/device.defaultQueue.writeBuffer(particleUniformBuffer, 0, particleIndexData);\n\n    var commandEncoder = device.createCommandEncoder();\n    var passEncoder = commandEncoder.beginComputePass();\n\n    passEncoder.setPipeline(computePipeline_findNeighbors);\n    passEncoder.setBindGroup(0, bindGroup);\n    passEncoder.dispatch(dataNum);\n\n    passEncoder.endPass();\n    device.defaultQueue.submit([commandEncoder.finish()]);\n\n    var commandEncoder = device.createCommandEncoder();\n    var passEncoder = commandEncoder.beginComputePass();\n\n    \/\/passEncoder.setPipeline(computePipeline_Read);\n    \/\/passEncoder.setBindGroup(0, bindGroup);\n    \/\/passEncoder.dispatch(dataNum);\n    \/\/passEncoder.dispatch(bucketIndexNum); \/\/ for bucketRef\n\n    passEncoder.setPipeline(computePipeline_integrate);\n    passEncoder.setBindGroup(0, bindGroup);\n    passEncoder.dispatch(PARTICLE_NUM);\n\n    passEncoder.endPass();\n\n    \/\/commandEncoder.copyBufferToBuffer( resultBuffer, 0, gpuReadBuffer, 0, resultBufferSize);\n\n    \/\/device.defaultQueue.submit([commandEncoder.finish()]);\n\n    \/\/\n    const textureView = swapChain.getCurrentTexture().createView();\n\n    const renderPass = commandEncoder.beginRenderPass({\n        colorAttachments: [{\n            attachment: textureView,\n            loadValue: [0, 0, 0, 1]\n        }]\n    });\n\n    renderPass.setPipeline(pipeline);\n    renderPass.setVertexBuffer(0, vertexBuffer);\n    renderPass.setVertexBuffer(1, positionBuffer);\n    renderPass.setVertexBuffer(2, neighborsBuffer);\n    \/\/renderPass.setViewport(0, 0, canvas.width, canvas.height, 0, 1);\n    renderPass.draw(numVertices, PARTICLE_NUM, 0, 0);\n\n    renderPass.endPass();\n\n    device.defaultQueue.submit([commandEncoder.finish()]);\n\n    \/\/await gpuReadBuffer.mapAsync(GPUMapMode.READ);\n    \/\/const arrayBuffer = gpuReadBuffer.getMappedRange();\n    \/\/\n    \/\/const arrayData = new Uint32Array(arrayBuffer);\n    \/\/var arrayData2 = [];\n    \/\/for (let i = 0; i &lt; bucketIndexNum; i++) {\n    \/\/    arrayData2.push([arrayData[i * 2 + 0], arrayData[i * 2 + 1]]);\n    \/\/}\n    \/\/console.log(\"resultData: \", new Uint32Array(arrayBuffer));\n    \/\/console.log(\"resultData: \", arrayData);\n    \/\/console.log(\"reultData2: \", arrayData2);\n\n    requestAnimationFrame(draw);\n    });\n\n    \/\/ Sort function\n    function Sort(p, q) {\n        var commandEncoder = device.createCommandEncoder();\n        var passEncoder = commandEncoder.beginComputePass();\n\n        var pq = new Float32Array([p, q]);\n        device.defaultQueue.writeBuffer(uniformBuffer, 0, pq);\n\n        passEncoder.setPipeline(computePipeline_Sort);\n        passEncoder.setBindGroup(0, bindGroup);\n        passEncoder.dispatch(dataNum);\n\n        passEncoder.setPipeline(computePipeline_Work);\n        passEncoder.setBindGroup(0, bindGroup);\n        passEncoder.dispatch(dataNum);\n\n        passEncoder.endPass();\n        device.defaultQueue.submit([commandEncoder.finish()]);\n    }\n})();\n&lt;\/script&gt;\n&lt;\/body&gt;\n&lt;\/html&gt;\n<\/code><\/pre>\n<p>code enjoy! \ud83d\udc3e\ud83d\udc3e\ud83d\udc3e\ud83d\udc3e\ud83d\udc3e\ud83d\udc3e\ud83d\udc3e\ud83d\udc3e\ud83d\udc0c\ud83d\udc1d<\/p>\n<p>\u4f5c\u8005\uff1aindeex<\/p>\n<p>\u94fe\u63a5\uff1a<a class=\"wp-editor-md-post-content-link\" href=\"https:\/\/indeex.club\/\">https:\/\/indeex.club<\/a><\/p>\n<p>\u8457\u4f5c\u6743\u5f52\u4f5c\u8005\u6240\u6709\u3002\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u8054\u7cfb\u4f5c\u8005\u83b7\u5f97\u6388\u6743\uff0c\u975e\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\u3002<\/p>\n<hr \/>\n","protected":false},"excerpt":{"rendered":"<p>WebGpu\u5df2\u7ecf\u4f7f\u7528\u4e00\u6bb5\u65f6\u95f4\u4e86\uff0c\u505a\u4e2a\u8fd1\u90bb\u63a2\u5bfb\u7684\u6d4b\u8bd5\u3002 \u5c4f\u5e55\u88ab\u5206\u62109\u5757\uff0c\u7ea2\u8272\u7c92\u5b50\u4e3a\u89c2\u6d4b\u5bf9\u8c61\uff0c\u540c\u4e00\u5355\u5143\u683c<a href=\"https:\/\/blog.indeex.club\/index.php\/2021\/06\/14\/%e8%bf%91%e9%82%bb%e6%8e%a2%e5%af%bb\/\" class=\"read-more\">Read More<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/posts\/231"}],"collection":[{"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/comments?post=231"}],"version-history":[{"count":2,"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/posts\/231\/revisions"}],"predecessor-version":[{"id":240,"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/posts\/231\/revisions\/240"}],"wp:attachment":[{"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/media?parent=231"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/categories?post=231"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.indeex.club\/index.php\/wp-json\/wp\/v2\/tags?post=231"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}