在GLSL中计算点到线的距离
Calculating point to line distance in GLSL
我正在尝试计算 GSLS 中的点到线的距离 - 恰好在 turbo.js turbo.js
中
这是一个更普遍的问题的一部分，在这个问题中，我尝试找到与一组 GeoJSON 点相对应的 [GeoJSON 多行上最近的点] - 在 1000 条线段末端设置的 500 个点的计算次数高达 500k 点到距离计算。
这在浏览器中（即使在 worker 中）处理起来太多了，因此并行性很有帮助。
诀窍是 AFAIK 我只能使用 vec4 作为输入，这意味着我只能对点对进行计算。
到目前为止，我已经计算了所有线对的距离和方位 - 但无法计算点到线的距离。
所以问题是-给定3点a,b,c，并且知道
- 他们在经度和纬度中的位置
- 他们成对的方位和距离
是否可以使用使用 vec2、vec3 或 vec4 作为输入参数的变换计算从 a 到 b 和 c 定义的直线的距离？
作为一个子问题——我知道如果三角形的高度 (a, b, c) 不与线 (a, b) 相交，因为它是 min(distance(a, b), 距离(a, c)).
但是，如果相交怎么计算呢？
我不太确定我理解你的问题。
听起来你想知道 500 个输入点，1000 条线段，对于每个点，哪条线段最近。
如果这就是您要问的，那么将所有点放在浮点纹理中（纹理的另一个词是二维数组）。绘制一个 -1 到 +1 的四边形，它是结果数量的大小（500 个结果，所以 50x10 或 25x20 等。）传递纹理的分辨率。使用 gl_FragCoord 计算索引以获得输入 A，并循环遍历所有其他行。通过将最接近的对的索引编码为颜色，通过 readPixels 读取结果。
precision highp float;
uniform sampler2D aValues;
uniform vec2 aDimensions; // the size of the aValues texture in pixels (texels)
uniform sampler2D bValues;
uniform vec2 bDimensions; // the size of the bValues texture in pixels (texels)
uniform sampler2D cValues;
uniform vec2 cDimensions; // the size of the cValues texture in pixels (texels)
uniform vec2 outputDimensions; // the size of the thing we're drawing to (canvas)
// this code, given a sampler2D, the size of the texture, and an index
// computes a UV coordinate to pull one RGBA value out of a texture
// as though the texture was a 1D array.
vec3 getPoint(in sampler2D tex, in vec2 dimensions, in float index) {
vec2 uv = (vec2(
floor(mod(index, dimensions.x)),
floor(index / dimensions.x)) + 0.5) / dimensions;
return texture2D(tex, uv).xyz;
}
// from
float distanceFromPointToLine(in vec3 a, in vec3 b, in vec3 c) {
vec3 ba = a - b;
vec3 bc = c - b;
float d = dot(ba, bc);
float len = length(bc);
float param = 0.0;
if (len != 0.0) {
param = clamp(d / (len * len), 0.0, 1.0);
}
vec3 r = b + bc * param;
return distance(a, r);
}
void main() {
// gl_FragCoord is the coordinate of the pixel that is being set by the fragment shader.
// It is the center of the pixel so the bottom left corner pixel will be (0.5, 0.5).
// the pixel to the left of that is (1.5, 0.5), The pixel above that is (0.5, 1.5), etc...
// so we can compute back into a linear index
float ndx = floor(gl_FragCoord.y) * outputDimensions.x + floor(gl_FragCoord.x);
// find the closest points
float minDist = 10000000.0;
float minIndex = -1.0;
vec3 a = getPoint(aValues, aDimensions, ndx);
for (int i = 0; i < ${bPoints.length / 4}; ++i) {
vec3 b = getPoint(bValues, bDimensions, float(i));
vec3 c = getPoint(cValues, cDimensions, float(i));
float dist = distanceFromPointToLine(a, b, c);
if (dist < minDist) {
minDist = dist;
minIndex = float(i);
}
}
// convert to 8bit color. The canvas defaults to RGBA 8bits per channel
// so take our integer index (minIndex) and convert to float values that
// will end up as the same 32bit index when read via readPixels as
// 32bit values.
gl_FragColor = vec4(
mod(minIndex, 256.0),
mod(floor(minIndex / 256.0), 256.0),
mod(floor(minIndex / (256.0 * 256.0)), 256.0) ,
floor(minIndex / (256.0 * 256.0 * 256.0))) / 255.0;
}
我只是猜测，虽然一般来说，通过某种空间结构可以更好地解决这个问题，这样你就不必检查每一行的每一点，但像上面的代码这样的东西应该可以工作并且非常平行。每个结果将由另一个 GPU 核心计算。
const v3 = twgl.v3;
// note: I'm using twgl to make the code smaller.
// This is not lesson in WebGL. You should already know what it means
// to setup buffers and attributes and set uniforms and create textures.
// What's important is the technique, not the minutia of WebGL. If you
// don't know how to do those things you need a much bigger tutorial
// on WebGL like https://webglfundamentals.org
function main() {
const gl = document.createElement('canvas').getContext('webgl');
const ext = gl.getExtension('OES_texture_float');
if (!ext) {
alert('need OES_texture_float');
return;
}
const r = max => Math.random() * max;
const hsl = (h, s, l) => `hsl(${h * 360},${s * 100 | 0}%,${l * 100 | 0}%)`;
function createPoints(numPoints) {
const points = [];
for (let i = 0; i < numPoints; ++i) {
points.push(r(300), r(150), 0, 0); // RGBA
}
return points;
}
function distanceFromPointToLineSquared(a, b, c) {
const ba = v3.subtract(a, b);
const bc = v3.subtract(c, b);
const dot = v3.dot(ba, bc);
const lenSq = v3.lengthSq(bc);
let param = 0;
if (lenSq !== 0) {
param = Math.min(1, Math.max(0, dot / lenSq));
}
const r = v3.add(b, v3.mulScalar(bc, param));
return v3.distanceSq(a, r);
}
const aPoints = createPoints(6);
const bPoints = createPoints(15);
const cPoints = createPoints(15);
// do it in JS to check
{
// compute closest lines to points
const closest = [];
for (let i = 0; i < aPoints.length; i += 4) {
const a = aPoints.slice(i, i + 3);
let minDistSq = Number.MAX_VALUE;
let minIndex = -1;
for (let j = 0; j < bPoints.length; j += 4) {
const b = bPoints.slice(j, j + 3);
const c = cPoints.slice(j, j + 3);
const distSq = distanceFromPointToLineSquared(a, b, c);
if (distSq < minDistSq) {
minDistSq = distSq;
minIndex = j / 4;
}
}
closest.push(minIndex);
}
drawResults(document.querySelector('#js'), closest);
}
const vs = `
attribute vec4 position;
void main() {
gl_Position = position;
}
`;
const fs = `
precision highp float;
uniform sampler2D aValues;
uniform vec2 aDimensions; // the size of the aValues texture in pixels (texels)
uniform sampler2D bValues;
uniform vec2 bDimensions; // the size of the bValues texture in pixels (texels)
uniform sampler2D cValues;
uniform vec2 cDimensions; // the size of the cValues texture in pixels (texels)
uniform vec2 outputDimensions; // the size of the thing we're drawing to (canvas)
// this code, given a sampler2D, the size of the texture, and an index
// computes a UV coordinate to pull one RGBA value out of a texture
// as though the texture was a 1D array.
vec3 getPoint(in sampler2D tex, in vec2 dimensions, in float index) {
vec2 uv = (vec2(
floor(mod(index, dimensions.x)),
floor(index / dimensions.x)) + 0.5) / dimensions;
return texture2D(tex, uv).xyz;
}
// from
float distanceFromPointToLine(in vec3 a, in vec3 b, in vec3 c) {
vec3 ba = a - b;
vec3 bc = c - b;
float d = dot(ba, bc);
float len = length(bc);
float param = 0.0;
if (len != 0.0) {
param = clamp(d / (len * len), 0.0, 1.0);
}
vec3 r = b + bc * param;
return distance(a, r);
}
void main() {
// gl_FragCoord is the coordinate of the pixel that is being set by the fragment shader.
// It is the center of the pixel so the bottom left corner pixel will be (0.5, 0.5).
// the pixel to the left of that is (1.5, 0.5), The pixel above that is (0.5, 1.5), etc...
// so we can compute back into a linear index
float ndx = floor(gl_FragCoord.y) * outputDimensions.x + floor(gl_FragCoord.x);
// find the closest points
float minDist = 10000000.0;
float minIndex = -1.0;
vec3 a = getPoint(aValues, aDimensions, ndx);
for (int i = 0; i < ${bPoints.length / 4}; ++i) {
vec3 b = getPoint(bValues, bDimensions, float(i));
vec3 c = getPoint(cValues, cDimensions, float(i));
float dist = distanceFromPointToLine(a, b, c);
if (dist < minDist) {
minDist = dist;
minIndex = float(i);
}
}
// convert to 8bit color. The canvas defaults to RGBA 8bits per channel
// so take our integer index (minIndex) and convert to float values that
// will end up as the same 32bit index when read via readPixels as
// 32bit values.
gl_FragColor = vec4(
mod(minIndex, 256.0),
mod(floor(minIndex / 256.0), 256.0),
mod(floor(minIndex / (256.0 * 256.0)), 256.0) ,
floor(minIndex / (256.0 * 256.0 * 256.0))) / 255.0;
}
`;
// compile shader, link program, lookup locations
const programInfo = twgl.createProgramInfo(gl, [vs, fs]);
// calls gl.createBuffer, gl.bindBuffer, gl.bufferData for a -1 to +1 quad
const bufferInfo = twgl.primitives.createXYQuadBufferInfo(gl);
// make an RGBA float texture for each set of points
// calls gl.createTexture, gl.bindTexture, gl.texImage2D, gl.texParameteri
const aTex = twgl.createTexture(gl, {
src: aPoints,
width: aPoints.length / 4,
type: gl.FLOAT,
minMag: gl.NEAREST,
});
const bTex = twgl.createTexture(gl, {
src: bPoints,
width: bPoints.length / 4,
type: gl.FLOAT,
minMag: gl.NEAREST,
});
const cTex = twgl.createTexture(gl, {
src: cPoints,
width: cPoints.length / 4,
type: gl.FLOAT,
minMag: gl.NEAREST,
});
const numOutputs = aPoints.length / 4;
gl.canvas.width = numOutputs;
gl.canvas.height = 1;
gl.viewport(0, 0, numOutputs, 1);
gl.useProgram(programInfo.program);
// calls gl.bindBuffer, gl.enableVertexAttribArray, gl.vertexAttribPointer
twgl.setBuffersAndAttributes(gl, programInfo, bufferInfo);
// calls gl.activeTexture, gl.bindTexture, gl.uniform
twgl.setUniforms(programInfo, {
aValues: aTex,
aDimensions: [aPoints.length / 4, 1],
bValues: cTex,
bDimensions: [bPoints.length / 4, 1],
cValues: bTex,
cDimensions: [cPoints.length / 4, 1],
outputDimensions: [aPoints.length / 4, 1],
});
// draw the quad
gl.drawElements(gl.TRIANGLES, 6, gl.UNSIGNED_SHORT, 0);
// get result
const pixels = new Uint8Array(numOutputs * 4);
const results = new Uint32Array(pixels.buffer);
gl.readPixels(0, 0, numOutputs, 1, gl.RGBA, gl.UNSIGNED_BYTE, pixels);
drawResults(document.querySelector('#glsl'), results);
function drawResults(canvas, closest) {
const ctx = canvas.getContext('2d');
// draw the lines
ctx.beginPath();
for (let j = 0; j < bPoints.length; j += 4) {
const b = bPoints.slice(j, j + 2);
const c = cPoints.slice(j, j + 2);
ctx.moveTo(...b);
ctx.lineTo(...c);
}
ctx.strokeStyle = '#888';
ctx.stroke();
// draw the points and closest lines
for (let i = 0; i < aPoints.length; i += 4) {
const a = aPoints.slice(i, i + 2);
const ndx = closest[i / 4] * 4;
const b = bPoints.slice(ndx, ndx + 2);
const c = cPoints.slice(ndx, ndx + 2);
const color = hsl(i / aPoints.length, 1, 0.4);
ctx.fillStyle = color;
ctx.strokeStyle = color;
ctx.fillRect(a[0] - 2, a[1] - 2, 5, 5);
ctx.beginPath();
ctx.moveTo(...b);
ctx.lineTo(...c);
ctx.stroke();
}
}
}
main();
canvas { border: 1px solid black; margin: 5px; }
<script src="https://twgljs.org/dist/4.x/twgl-full.min.js"></script>
<div>glsl</div>
<canvas id="glsl"></canvas>
<div>js</div>
<canvas id="js"></canvas>
如果你使用 WebGL2 那么你可以使用 texelFetch 所以 getPoint 变成
vec3 getPoint(in sampler2D tex, in int index) {
ivec2 size = textureSize(tex, 0);
ivec2 uv = ivec2(index % size.x, index / size.x);
return texelFetch(tex, uv, 0).xyz;
}
并且您不需要传递输入纹理的大小，只需传递输出大小。您也可以使输出 R32U 并输出无符号整数索引，因此无需对结果进行编码。
注意：该代码假定您为每个 a、b 和 c 执行的值少于 2048 个值，因此大部分代码都假定一维纹理。如果您需要超过 2048 个，则需要调整代码以制作大小适合您的数据的矩形纹理，例如，如果您有 9000 个值，那么 9x1000 纹理就可以了。如果你有 8999 个值，那么你仍然需要一个 9x1000 的纹理来填充一个矩形，因为纹理是二维数组。
另请注意，调用 readPixels 被认为很慢。例如，如果您只想绘制上面的结果，而不是渲染到 canvas 并通过 readPixels 读取值，您可以将结果渲染到纹理，然后将纹理传递到另一个着色器。
附录
这可能是错误的地方，但作为对此类内容的 GLSL 的简洁解释，您可以将 GLSL 视为 Array.prototype.map 的奇特版本。当您使用 map 时，您不会直接选择要写入的内容。它是间接发生的。
const a = [1, 2, 3, 4, 5];
const b = a.map((v, index) => { return v * 2 + index; });
{ return v * 2 + index}部分类似于着色器。在 JavaScript 中映射 returns 中的函数值。在 GLSL ES 1.0 中，着色器将 gl_FragColor 设置为输出。在 Javascript index 中是正在写入的数组的索引（并且恰好也是输入数组的索引）。在 GLSL 中 gl_FragCoord 起着同样的作用。
否则，顶点着色器的输出决定将写入哪些像素（二维数组的哪些数组元素），从而使其成为 map 的更具选择性的版本。在上面的代码中，我们绘制了一个 -1 到 +1 的四边形，有效地表示“映射所有像素”。
实际上这是上面代码的一个版本，没有 GLSL，只是 JavaScript，但是 JavaScript re-structured 看起来更像 GLSL。
const v3 = twgl.v3;
function main() {
const r = max => Math.random() * max;
const hsl = (h, s, l) => `hsl(${h * 360},${s * 100 | 0}%,${l * 100 | 0}%)`;
function createPoints(numPoints) {
const points = [];
for (let i = 0; i < numPoints; ++i) {
points.push(r(300), r(150), 0, 0); // RGBA
}
return points;
}
function distanceFromPointToLineSquared(a, b, c) {
const ba = v3.subtract(a, b);
const bc = v3.subtract(c, b);
const dot = v3.dot(ba, bc);
const lenSq = v3.lengthSq(bc);
let param = 0;
if (lenSq !== 0) {
param = Math.min(1, Math.max(0, dot / lenSq));
}
const r = v3.add(b, v3.mulScalar(bc, param));
return v3.distanceSq(a, r);
}
const aPoints = createPoints(6);
const bPoints = createPoints(15);
const cPoints = createPoints(15);
const gl_FragCoord = {};
let gl_FragColor;
const aValues = aPoints;
const aDimensions = {}; // N/A
const bValues = bPoints;
const bDimensions = {}; // N/A
const cValues = cPoints;
const cDimensions = {}; // N/A
const outputDimensions = {x: aPoints.length / 4, y: 1 };
function getPoint(sampler, dimension, ndx) {
return sampler.slice(ndx * 4, ndx * 4 + 3);
}
function javaScriptFragmentShader() {
// gl_FragCoord is the coordinate of the pixel that is being set by the fragment shader.
// It is the center of the pixel so the bottom left corner pixel will be (0.5, 0.5).
// the pixel to the left of that is (1.5, 0.5), The pixel above that is (0.5, 1.5), etc...
// so we can compute back into a linear index
const ndx = Math.floor(gl_FragCoord.y) * outputDimensions.x + Math.floor(gl_FragCoord.x);
// find the closest points
let minDist = 10000000.0;
let minIndex = -1.0;
const a = getPoint(aValues, aDimensions, ndx);
for (let i = 0; i < bPoints.length / 4; ++i) {
const b = getPoint(bValues, bDimensions, i);
const c = getPoint(cValues, cDimensions, i);
const dist = distanceFromPointToLineSquared(a, b, c);
if (dist < minDist) {
minDist = dist;
minIndex = i;
}
}
// convert to 8bit color. The canvas defaults to RGBA 8bits per channel
// so take our integer index (minIndex) and convert to float values that
// will end up as the same 32bit index when read via readPixels as
// 32bit values.
gl_FragColor = [
minIndex % 256.0,
Math.floor(minIndex / 256.0) % 256.0,
Math.floor(minIndex / (256.0 * 256.0)) % 256.0,
Math.floor(minIndex / (256.0 * 256.0 * 256.0)),
].map(v => v / 255.0);
}
// do it in JS to check
{
// compute closest lines to points
const closest = [];
const width = aPoints.length / 4;
const height = 1;
// WebGL drawing each pixel
for (let y = 0; y < height; ++y) {
for (let x = 0; x < width; ++x) {
gl_FragCoord.x = x + 0.5; // because pixels represent a rectangle one unit wide in pixel space
gl_FragCoord.y = y + 0.5; // so the center of each pixel in the middle of that rectangle
javaScriptFragmentShader();
const index = gl_FragColor[0] * 255 +
gl_FragColor[1] * 255 * 256 +
gl_FragColor[2] * 255 * 256 * 256 +
gl_FragColor[3] * 255 * 256 * 256 * 256;
closest.push(index);
}
}
drawResults(document.querySelector('#js'), closest);
}
function drawResults(canvas, closest) {
const ctx = canvas.getContext('2d');
// draw the lines
ctx.beginPath();
for (let j = 0; j < bPoints.length; j += 4) {
const b = bPoints.slice(j, j + 2);
const c = cPoints.slice(j, j + 2);
ctx.moveTo(...b);
ctx.lineTo(...c);
}
ctx.strokeStyle = '#888';
ctx.stroke();
// draw the points and closest lines
for (let i = 0; i < aPoints.length; i += 4) {
const a = aPoints.slice(i, i + 2);
const ndx = closest[i / 4] * 4;
const b = bPoints.slice(ndx, ndx + 2);
const c = cPoints.slice(ndx, ndx + 2);
const color = hsl(i / aPoints.length, 1, 0.4);
ctx.fillStyle = color;
ctx.strokeStyle = color;
ctx.fillRect(a[0] - 2, a[1] - 2, 5, 5);
ctx.beginPath();
ctx.moveTo(...b);
ctx.lineTo(...c);
ctx.stroke();
}
}
}
main();
canvas { border: 1px solid black; margin: 5px; }
<script src="https://twgljs.org/dist/4.x/twgl-full.min.js"></script>
<canvas id="js"></canvas>
我正在尝试计算 GSLS 中的点到线的距离 - 恰好在 turbo.js turbo.js
中这是一个更普遍的问题的一部分，在这个问题中，我尝试找到与一组 GeoJSON 点相对应的 [GeoJSON 多行上最近的点] - 在 1000 条线段末端设置的 500 个点的计算次数高达 500k 点到距离计算。
这在浏览器中（即使在 worker 中）处理起来太多了，因此并行性很有帮助。
诀窍是 AFAIK 我只能使用 vec4 作为输入，这意味着我只能对点对进行计算。
到目前为止，我已经计算了所有线对的距离和方位 - 但无法计算点到线的距离。
所以问题是-给定3点a,b,c，并且知道
- 他们在经度和纬度中的位置
- 他们成对的方位和距离
是否可以使用使用 vec2、vec3 或 vec4 作为输入参数的变换计算从 a 到 b 和 c 定义的直线的距离？
作为一个子问题——我知道如果三角形的高度 (a, b, c) 不与线 (a, b) 相交，因为它是 min(distance(a, b), 距离(a, c)).
但是，如果相交怎么计算呢？
我不太确定我理解你的问题。
听起来你想知道 500 个输入点，1000 条线段，对于每个点，哪条线段最近。
如果这就是您要问的，那么将所有点放在浮点纹理中（纹理的另一个词是二维数组）。绘制一个 -1 到 +1 的四边形，它是结果数量的大小（500 个结果，所以 50x10 或 25x20 等。）传递纹理的分辨率。使用 gl_FragCoord 计算索引以获得输入 A，并循环遍历所有其他行。通过将最接近的对的索引编码为颜色，通过 readPixels 读取结果。
precision highp float;
uniform sampler2D aValues;
uniform vec2 aDimensions; // the size of the aValues texture in pixels (texels)
uniform sampler2D bValues;
uniform vec2 bDimensions; // the size of the bValues texture in pixels (texels)
uniform sampler2D cValues;
uniform vec2 cDimensions; // the size of the cValues texture in pixels (texels)
uniform vec2 outputDimensions; // the size of the thing we're drawing to (canvas)
// this code, given a sampler2D, the size of the texture, and an index
// computes a UV coordinate to pull one RGBA value out of a texture
// as though the texture was a 1D array.
vec3 getPoint(in sampler2D tex, in vec2 dimensions, in float index) {
vec2 uv = (vec2(
floor(mod(index, dimensions.x)),
floor(index / dimensions.x)) + 0.5) / dimensions;
return texture2D(tex, uv).xyz;
}
// from
float distanceFromPointToLine(in vec3 a, in vec3 b, in vec3 c) {
vec3 ba = a - b;
vec3 bc = c - b;
float d = dot(ba, bc);
float len = length(bc);
float param = 0.0;
if (len != 0.0) {
param = clamp(d / (len * len), 0.0, 1.0);
}
vec3 r = b + bc * param;
return distance(a, r);
}
void main() {
// gl_FragCoord is the coordinate of the pixel that is being set by the fragment shader.
// It is the center of the pixel so the bottom left corner pixel will be (0.5, 0.5).
// the pixel to the left of that is (1.5, 0.5), The pixel above that is (0.5, 1.5), etc...
// so we can compute back into a linear index
float ndx = floor(gl_FragCoord.y) * outputDimensions.x + floor(gl_FragCoord.x);
// find the closest points
float minDist = 10000000.0;
float minIndex = -1.0;
vec3 a = getPoint(aValues, aDimensions, ndx);
for (int i = 0; i < ${bPoints.length / 4}; ++i) {
vec3 b = getPoint(bValues, bDimensions, float(i));
vec3 c = getPoint(cValues, cDimensions, float(i));
float dist = distanceFromPointToLine(a, b, c);
if (dist < minDist) {
minDist = dist;
minIndex = float(i);
}
}
// convert to 8bit color. The canvas defaults to RGBA 8bits per channel
// so take our integer index (minIndex) and convert to float values that
// will end up as the same 32bit index when read via readPixels as
// 32bit values.
gl_FragColor = vec4(
mod(minIndex, 256.0),
mod(floor(minIndex / 256.0), 256.0),
mod(floor(minIndex / (256.0 * 256.0)), 256.0) ,
floor(minIndex / (256.0 * 256.0 * 256.0))) / 255.0;
}
我只是猜测，虽然一般来说，通过某种空间结构可以更好地解决这个问题，这样你就不必检查每一行的每一点，但像上面的代码这样的东西应该可以工作并且非常平行。每个结果将由另一个 GPU 核心计算。
const v3 = twgl.v3;
// note: I'm using twgl to make the code smaller.
// This is not lesson in WebGL. You should already know what it means
// to setup buffers and attributes and set uniforms and create textures.
// What's important is the technique, not the minutia of WebGL. If you
// don't know how to do those things you need a much bigger tutorial
// on WebGL like https://webglfundamentals.org
function main() {
const gl = document.createElement('canvas').getContext('webgl');
const ext = gl.getExtension('OES_texture_float');
if (!ext) {
alert('need OES_texture_float');
return;
}
const r = max => Math.random() * max;
const hsl = (h, s, l) => `hsl(${h * 360},${s * 100 | 0}%,${l * 100 | 0}%)`;
function createPoints(numPoints) {
const points = [];
for (let i = 0; i < numPoints; ++i) {
points.push(r(300), r(150), 0, 0); // RGBA
}
return points;
}
function distanceFromPointToLineSquared(a, b, c) {
const ba = v3.subtract(a, b);
const bc = v3.subtract(c, b);
const dot = v3.dot(ba, bc);
const lenSq = v3.lengthSq(bc);
let param = 0;
if (lenSq !== 0) {
param = Math.min(1, Math.max(0, dot / lenSq));
}
const r = v3.add(b, v3.mulScalar(bc, param));
return v3.distanceSq(a, r);
}
const aPoints = createPoints(6);
const bPoints = createPoints(15);
const cPoints = createPoints(15);
// do it in JS to check
{
// compute closest lines to points
const closest = [];
for (let i = 0; i < aPoints.length; i += 4) {
const a = aPoints.slice(i, i + 3);
let minDistSq = Number.MAX_VALUE;
let minIndex = -1;
for (let j = 0; j < bPoints.length; j += 4) {
const b = bPoints.slice(j, j + 3);
const c = cPoints.slice(j, j + 3);
const distSq = distanceFromPointToLineSquared(a, b, c);
if (distSq < minDistSq) {
minDistSq = distSq;
minIndex = j / 4;
}
}
closest.push(minIndex);
}
drawResults(document.querySelector('#js'), closest);
}
const vs = `
attribute vec4 position;
void main() {
gl_Position = position;
}
`;
const fs = `
precision highp float;
uniform sampler2D aValues;
uniform vec2 aDimensions; // the size of the aValues texture in pixels (texels)
uniform sampler2D bValues;
uniform vec2 bDimensions; // the size of the bValues texture in pixels (texels)
uniform sampler2D cValues;
uniform vec2 cDimensions; // the size of the cValues texture in pixels (texels)
uniform vec2 outputDimensions; // the size of the thing we're drawing to (canvas)
// this code, given a sampler2D, the size of the texture, and an index
// computes a UV coordinate to pull one RGBA value out of a texture
// as though the texture was a 1D array.
vec3 getPoint(in sampler2D tex, in vec2 dimensions, in float index) {
vec2 uv = (vec2(
floor(mod(index, dimensions.x)),
floor(index / dimensions.x)) + 0.5) / dimensions;
return texture2D(tex, uv).xyz;
}
// from
float distanceFromPointToLine(in vec3 a, in vec3 b, in vec3 c) {
vec3 ba = a - b;
vec3 bc = c - b;
float d = dot(ba, bc);
float len = length(bc);
float param = 0.0;
if (len != 0.0) {
param = clamp(d / (len * len), 0.0, 1.0);
}
vec3 r = b + bc * param;
return distance(a, r);
}
void main() {
// gl_FragCoord is the coordinate of the pixel that is being set by the fragment shader.
// It is the center of the pixel so the bottom left corner pixel will be (0.5, 0.5).
// the pixel to the left of that is (1.5, 0.5), The pixel above that is (0.5, 1.5), etc...
// so we can compute back into a linear index
float ndx = floor(gl_FragCoord.y) * outputDimensions.x + floor(gl_FragCoord.x);
// find the closest points
float minDist = 10000000.0;
float minIndex = -1.0;
vec3 a = getPoint(aValues, aDimensions, ndx);
for (int i = 0; i < ${bPoints.length / 4}; ++i) {
vec3 b = getPoint(bValues, bDimensions, float(i));
vec3 c = getPoint(cValues, cDimensions, float(i));
float dist = distanceFromPointToLine(a, b, c);
if (dist < minDist) {
minDist = dist;
minIndex = float(i);
}
}
// convert to 8bit color. The canvas defaults to RGBA 8bits per channel
// so take our integer index (minIndex) and convert to float values that
// will end up as the same 32bit index when read via readPixels as
// 32bit values.
gl_FragColor = vec4(
mod(minIndex, 256.0),
mod(floor(minIndex / 256.0), 256.0),
mod(floor(minIndex / (256.0 * 256.0)), 256.0) ,
floor(minIndex / (256.0 * 256.0 * 256.0))) / 255.0;
}
`;
// compile shader, link program, lookup locations
const programInfo = twgl.createProgramInfo(gl, [vs, fs]);
// calls gl.createBuffer, gl.bindBuffer, gl.bufferData for a -1 to +1 quad
const bufferInfo = twgl.primitives.createXYQuadBufferInfo(gl);
// make an RGBA float texture for each set of points
// calls gl.createTexture, gl.bindTexture, gl.texImage2D, gl.texParameteri
const aTex = twgl.createTexture(gl, {
src: aPoints,
width: aPoints.length / 4,
type: gl.FLOAT,
minMag: gl.NEAREST,
});
const bTex = twgl.createTexture(gl, {
src: bPoints,
width: bPoints.length / 4,
type: gl.FLOAT,
minMag: gl.NEAREST,
});
const cTex = twgl.createTexture(gl, {
src: cPoints,
width: cPoints.length / 4,
type: gl.FLOAT,
minMag: gl.NEAREST,
});
const numOutputs = aPoints.length / 4;
gl.canvas.width = numOutputs;
gl.canvas.height = 1;
gl.viewport(0, 0, numOutputs, 1);
gl.useProgram(programInfo.program);
// calls gl.bindBuffer, gl.enableVertexAttribArray, gl.vertexAttribPointer
twgl.setBuffersAndAttributes(gl, programInfo, bufferInfo);
// calls gl.activeTexture, gl.bindTexture, gl.uniform
twgl.setUniforms(programInfo, {
aValues: aTex,
aDimensions: [aPoints.length / 4, 1],
bValues: cTex,
bDimensions: [bPoints.length / 4, 1],
cValues: bTex,
cDimensions: [cPoints.length / 4, 1],
outputDimensions: [aPoints.length / 4, 1],
});
// draw the quad
gl.drawElements(gl.TRIANGLES, 6, gl.UNSIGNED_SHORT, 0);
// get result
const pixels = new Uint8Array(numOutputs * 4);
const results = new Uint32Array(pixels.buffer);
gl.readPixels(0, 0, numOutputs, 1, gl.RGBA, gl.UNSIGNED_BYTE, pixels);
drawResults(document.querySelector('#glsl'), results);
function drawResults(canvas, closest) {
const ctx = canvas.getContext('2d');
// draw the lines
ctx.beginPath();
for (let j = 0; j < bPoints.length; j += 4) {
const b = bPoints.slice(j, j + 2);
const c = cPoints.slice(j, j + 2);
ctx.moveTo(...b);
ctx.lineTo(...c);
}
ctx.strokeStyle = '#888';
ctx.stroke();
// draw the points and closest lines
for (let i = 0; i < aPoints.length; i += 4) {
const a = aPoints.slice(i, i + 2);
const ndx = closest[i / 4] * 4;
const b = bPoints.slice(ndx, ndx + 2);
const c = cPoints.slice(ndx, ndx + 2);
const color = hsl(i / aPoints.length, 1, 0.4);
ctx.fillStyle = color;
ctx.strokeStyle = color;
ctx.fillRect(a[0] - 2, a[1] - 2, 5, 5);
ctx.beginPath();
ctx.moveTo(...b);
ctx.lineTo(...c);
ctx.stroke();
}
}
}
main();
canvas { border: 1px solid black; margin: 5px; }
<script src="https://twgljs.org/dist/4.x/twgl-full.min.js"></script>
<div>glsl</div>
<canvas id="glsl"></canvas>
<div>js</div>
<canvas id="js"></canvas>
如果你使用 WebGL2 那么你可以使用 texelFetch 所以 getPoint 变成
vec3 getPoint(in sampler2D tex, in int index) {
ivec2 size = textureSize(tex, 0);
ivec2 uv = ivec2(index % size.x, index / size.x);
return texelFetch(tex, uv, 0).xyz;
}
并且您不需要传递输入纹理的大小，只需传递输出大小。您也可以使输出 R32U 并输出无符号整数索引，因此无需对结果进行编码。
注意：该代码假定您为每个 a、b 和 c 执行的值少于 2048 个值，因此大部分代码都假定一维纹理。如果您需要超过 2048 个，则需要调整代码以制作大小适合您的数据的矩形纹理，例如，如果您有 9000 个值，那么 9x1000 纹理就可以了。如果你有 8999 个值，那么你仍然需要一个 9x1000 的纹理来填充一个矩形，因为纹理是二维数组。
另请注意，调用 readPixels 被认为很慢。例如，如果您只想绘制上面的结果，而不是渲染到 canvas 并通过 readPixels 读取值，您可以将结果渲染到纹理，然后将纹理传递到另一个着色器。
附录
这可能是错误的地方，但作为对此类内容的 GLSL 的简洁解释，您可以将 GLSL 视为 Array.prototype.map 的奇特版本。当您使用 map 时，您不会直接选择要写入的内容。它是间接发生的。
const a = [1, 2, 3, 4, 5];
const b = a.map((v, index) => { return v * 2 + index; });
{ return v * 2 + index}部分类似于着色器。在 JavaScript 中映射 returns 中的函数值。在 GLSL ES 1.0 中，着色器将 gl_FragColor 设置为输出。在 Javascript index 中是正在写入的数组的索引（并且恰好也是输入数组的索引）。在 GLSL 中 gl_FragCoord 起着同样的作用。
否则，顶点着色器的输出决定将写入哪些像素（二维数组的哪些数组元素），从而使其成为 map 的更具选择性的版本。在上面的代码中，我们绘制了一个 -1 到 +1 的四边形，有效地表示“映射所有像素”。
实际上这是上面代码的一个版本，没有 GLSL，只是 JavaScript，但是 JavaScript re-structured 看起来更像 GLSL。
const v3 = twgl.v3;
function main() {
const r = max => Math.random() * max;
const hsl = (h, s, l) => `hsl(${h * 360},${s * 100 | 0}%,${l * 100 | 0}%)`;
function createPoints(numPoints) {
const points = [];
for (let i = 0; i < numPoints; ++i) {
points.push(r(300), r(150), 0, 0); // RGBA
}
return points;
}
function distanceFromPointToLineSquared(a, b, c) {
const ba = v3.subtract(a, b);
const bc = v3.subtract(c, b);
const dot = v3.dot(ba, bc);
const lenSq = v3.lengthSq(bc);
let param = 0;
if (lenSq !== 0) {
param = Math.min(1, Math.max(0, dot / lenSq));
}
const r = v3.add(b, v3.mulScalar(bc, param));
return v3.distanceSq(a, r);
}
const aPoints = createPoints(6);
const bPoints = createPoints(15);
const cPoints = createPoints(15);
const gl_FragCoord = {};
let gl_FragColor;
const aValues = aPoints;
const aDimensions = {}; // N/A
const bValues = bPoints;
const bDimensions = {}; // N/A
const cValues = cPoints;
const cDimensions = {}; // N/A
const outputDimensions = {x: aPoints.length / 4, y: 1 };
function getPoint(sampler, dimension, ndx) {
return sampler.slice(ndx * 4, ndx * 4 + 3);
}
function javaScriptFragmentShader() {
// gl_FragCoord is the coordinate of the pixel that is being set by the fragment shader.
// It is the center of the pixel so the bottom left corner pixel will be (0.5, 0.5).
// the pixel to the left of that is (1.5, 0.5), The pixel above that is (0.5, 1.5), etc...
// so we can compute back into a linear index
const ndx = Math.floor(gl_FragCoord.y) * outputDimensions.x + Math.floor(gl_FragCoord.x);
// find the closest points
let minDist = 10000000.0;
let minIndex = -1.0;
const a = getPoint(aValues, aDimensions, ndx);
for (let i = 0; i < bPoints.length / 4; ++i) {
const b = getPoint(bValues, bDimensions, i);
const c = getPoint(cValues, cDimensions, i);
const dist = distanceFromPointToLineSquared(a, b, c);
if (dist < minDist) {
minDist = dist;
minIndex = i;
}
}
// convert to 8bit color. The canvas defaults to RGBA 8bits per channel
// so take our integer index (minIndex) and convert to float values that
// will end up as the same 32bit index when read via readPixels as
// 32bit values.
gl_FragColor = [
minIndex % 256.0,
Math.floor(minIndex / 256.0) % 256.0,
Math.floor(minIndex / (256.0 * 256.0)) % 256.0,
Math.floor(minIndex / (256.0 * 256.0 * 256.0)),
].map(v => v / 255.0);
}
// do it in JS to check
{
// compute closest lines to points
const closest = [];
const width = aPoints.length / 4;
const height = 1;
// WebGL drawing each pixel
for (let y = 0; y < height; ++y) {
for (let x = 0; x < width; ++x) {
gl_FragCoord.x = x + 0.5; // because pixels represent a rectangle one unit wide in pixel space
gl_FragCoord.y = y + 0.5; // so the center of each pixel in the middle of that rectangle
javaScriptFragmentShader();
const index = gl_FragColor[0] * 255 +
gl_FragColor[1] * 255 * 256 +
gl_FragColor[2] * 255 * 256 * 256 +
gl_FragColor[3] * 255 * 256 * 256 * 256;
closest.push(index);
}
}
drawResults(document.querySelector('#js'), closest);
}
function drawResults(canvas, closest) {
const ctx = canvas.getContext('2d');
// draw the lines
ctx.beginPath();
for (let j = 0; j < bPoints.length; j += 4) {
const b = bPoints.slice(j, j + 2);
const c = cPoints.slice(j, j + 2);
ctx.moveTo(...b);
ctx.lineTo(...c);
}
ctx.strokeStyle = '#888';
ctx.stroke();
// draw the points and closest lines
for (let i = 0; i < aPoints.length; i += 4) {
const a = aPoints.slice(i, i + 2);
const ndx = closest[i / 4] * 4;
const b = bPoints.slice(ndx, ndx + 2);
const c = cPoints.slice(ndx, ndx + 2);
const color = hsl(i / aPoints.length, 1, 0.4);
ctx.fillStyle = color;
ctx.strokeStyle = color;
ctx.fillRect(a[0] - 2, a[1] - 2, 5, 5);
ctx.beginPath();
ctx.moveTo(...b);
ctx.lineTo(...c);
ctx.stroke();
}
}
}
main();
canvas { border: 1px solid black; margin: 5px; }
<script src="https://twgljs.org/dist/4.x/twgl-full.min.js"></script>
<canvas id="js"></canvas>