Я на самом деле не продумал это, но вот код, который может дать вам идеи.
Проблема в том, что в WebGL2 AFAIK нет способа условно выводить данные.Вы можете отбросить в фрагментном шейдере, но здесь это не кажется полезным.
Так что, в любом случае, первое, о чем нужно подумать, это то, что шейдеры распараллеливают базу на выходе.Если для рисования 32 тыс. Пикселей, то графический процессор имеет 32 тыс. Элементов, которые он может распараллелить.Если есть 1 пиксель, который проверяет 32 тыс. Вещей, то графическому процессору нечего распараллеливать.
Итак, вот одна из идей, разделить 3D-текстуру на ячейки NxNxN большие, ищите в каждой ячейке по вокселям.Если ячейка имеет размер 32x32x32, то для входа 512x512x512 есть 4096 вещей для распараллеливания.Для каждой ячейки обойдите ячейку и суммируйте позиции совпадений
sum = vec4(0)
for each voxel in cell
if voxel === 1
sum += vec4(positionOfVoxel, 1);
outColor = sum;
В результате, если в этой ячейке всего 1 совпадение, то sum.xyz будет содержать позицию, а sum.w будет 1Если существует более одного совпадения, sum.w будет> 1
. Приведенный ниже код создает текстуру 4096x1 и отдает ей четверку.Он использует gl_FragCoord.x, чтобы вычислить, какой ячейке соответствует каждый отображаемый пиксель, и суммирует результаты для соответствующей ячейки.
Затем он использует readPixels для чтения результата, проходит и распечатывает их.В идеале мне бы хотелось, чтобы сама графическая карта вычисляла результаты, но, учитывая, что вы не можете условно отбросить, у меня не было никаких идей.
Для ячейки с одним результатом выводится результат.Для ячейки с множественным результатом другой шейдер, который сканирует ячейку.Мы знаем, сколько результатов в конкретной ячейке, поэтому мы можем визуализировать numResults на 1 пиксель.Затем шейдер перебирает ячейку и смотрит только на N-й результат, который он находит
int idOfResultWeWant = int(gl_FragCoord.x)
int resultId = 0
for (z...) {
for (y...) {
for (x...) {
if (voxel) {
if (resultId === idOfResultWeWant) {
outColor = position
}
++resultId
}
}
}
Приведенный ниже код ленив и использует 1D текстуры результатов, что означает, что большинство ячеек, которые он может обработать, составляет gl.getParameter(gl.MAX_TEXTURE_SIZE),Для больших размеров пришлось бы немного измениться.
Не знаю, является ли это самым быстрым или даже быстрым способом, но концепция параллелизма, основанная на том, что делается, важна, а также делит проблему на меньшие.частей.
Как, может быть, лучше использовать ячейки 16x16x16, и, возможно, вместо второго шейдера нам нужно просто снова использовать первый шейдер, разделив саму ячейку на более мелкие ячейки.
function main() {
const gl = document.createElement('canvas').getContext('webgl2');
if (!gl) {
return alert('need webgl2');
}
const ext = gl.getExtension('EXT_color_buffer_float');
if (!ext) {
return alert('need EXT_color_buffer_float');
}
const size = 512;
const cellSize = 32;
const cellsPer = size / cellSize;
const numCells = (size * size * size) / (cellSize * cellSize * cellSize);
const dataTexture = twgl.createTexture(gl, {
target: gl.TEXTURE_3D,
width: size,
height: size,
depth: size,
minMag: gl.NEAREST,
internalFormat: gl.R8,
auto: false,
});
function setData(x, y, z) {
log('set voxel:', x, y, z);
gl.texSubImage3D(
gl.TEXTURE_3D, 0, x, y, z, 1, 1, 1,
gl.RED, gl.UNSIGNED_BYTE, new Uint8Array([255]));
}
for (let i = 0; i < 3; ++i) {
const x = randInt(size);
const y = randInt(size);
const z = randInt(size);
setData(x, y, z);
}
setData(128, 267, 234);
setData(128 + 4, 267, 234);
setData(128 + 9, 267, 234);
const cellVS = `#version 300 es
in vec4 position;
void main() {
gl_Position = position;
}
`;
const cellFS = `#version 300 es
precision highp float;
uniform highp sampler3D data;
uniform int cellSize;
out vec4 outColor;
void main() {
// really should use 2D but I'm lazy
int ndx = int(gl_FragCoord.x);
// assumes equal sides
int size = textureSize(data, 0).x;
int cellsPer = size / cellSize;
int cellZ = ndx / cellsPer / cellsPer;
int cellY = ndx / cellsPer % cellsPer;
int cellX = ndx % cellsPer;
ivec3 cell = ivec3(cellX, cellY, cellZ) * cellSize;
vec4 sum = vec4(0);
for (int z = 0; z < cellSize; ++z) {
for (int y = 0; y < cellSize; ++y) {
for (int x = 0; x < cellSize; ++x) {
ivec3 pos = cell + ivec3(x, y, z);
// assumes data is 0 or 1
float occupied = texelFetch(
data,
pos,
0).r;
sum += vec4(pos, 1) * occupied;
}
}
}
outColor = sum;
}
`;
const cellScanFS = `#version 300 es
precision highp float;
uniform highp sampler3D data;
uniform int cellSize;
uniform ivec3 cell; // offset into cell
out vec4 outColor;
void main() {
// really should use 2D but I'm lazy
int idWeWant = int(gl_FragCoord.x);
// assumes equal sides
int size = textureSize(data, 0).x;
int cellsPer = size / cellSize;
vec4 result = vec4(0);
int id = 0;
for (int z = 0; z < cellSize; ++z) {
for (int y = 0; y < cellSize; ++y) {
for (int x = 0; x < cellSize; ++x) {
ivec3 pos = cell + ivec3(x, y, z);
float occupied = texelFetch(
data,
pos,
0).r;
if (occupied > 0.0) {
if (id == idWeWant) {
result = vec4(pos, 1);
}
++id;
}
}
}
}
outColor = result;
}
`;
const cellProgramInfo = twgl.createProgramInfo(gl, [cellVS, cellFS]);
const cellScanProgramInfo = twgl.createProgramInfo(gl, [cellVS, cellScanFS]);
const quadBufferInfo = twgl.primitives.createXYQuadBufferInfo(gl, 2);
// as long as numCells is less than the max
// texture dimensions we can use a
// numCells by 1 result texture.
// If numCells is > max texture dimension
// we'd need to adjust the code to use
// a 2d result texture.
const cellResultWidth = numCells;
const cellResultHeight = 1;
const cellResultFBI = twgl.createFramebufferInfo(gl, [
{ internalFormat: gl.RGBA32F, minMag: gl.NEAREST }
], cellResultWidth, cellResultHeight);
twgl.bindFramebufferInfo(gl, cellResultFBI);
twgl.setBuffersAndAttributes(gl, cellProgramInfo, quadBufferInfo);
gl.useProgram(cellProgramInfo.program);
twgl.setUniforms(cellProgramInfo, {
cellSize,
data: dataTexture,
});
// draw the quad
twgl.drawBufferInfo(gl, quadBufferInfo);
const data = new Float32Array(numCells * 4);
gl.readPixels(0, 0, numCells, 1, gl.RGBA, gl.FLOAT, data);
gl.useProgram(cellScanProgramInfo.program);
{
for (let i = 0; i < numCells; ++i) {
const off = i * 4;
const numResultsInCell = data[off + 3];
if (numResultsInCell) {
if (numResultsInCell === 1) {
log('result at: ', ...data.slice(off, off + 3));
} else {
getResultsForCell(i, numResultsInCell);
}
}
}
}
function getResultsForCell(i, numResultsInCell) {
const cellZ = (i / cellsPer | 0) / cellsPer | 0;
const cellY = (i / cellsPer | 0) % cellsPer;
const cellX = i % cellsPer;
twgl.setUniforms(cellScanProgramInfo, {
cellSize,
data: dataTexture,
cell: [cellX * cellSize, cellY * cellSize, cellZ * cellSize],
});
twgl.drawBufferInfo(gl, quadBufferInfo);
// note: cellResultsFBI is still bound. It's 4096x1
// so we can only get up to 4096 results without switching to
// a 2D texture
gl.viewport(0, 0, numResultsInCell, 1);
const result = new Float32Array(numResultsInCell * 4);
gl.readPixels(0, 0, numResultsInCell, 1, gl.RGBA, gl.FLOAT, result);
for (let j = 0; j < numResultsInCell; ++j) {
const off = j * 4;
log('result at:', ...result.slice(off, off + 3));
}
}
function randInt(min, max) {
return Math.floor(rand(min, max));
}
function rand(min, max) {
if (max === undefined) {
max = min;
min = 0;
}
return Math.random() * (max - min) + min;
}
function log(...args) {
const elem = document.createElement('pre');
elem.textContent = [...args].join(' ');
document.body.appendChild(elem);
}
}
main();
pre { margin: 0; }
<script src="https://twgljs.org/dist/4.x/twgl-full.min.js"></script>