问题描述
我正在尝试在GSLS中精确地计算出点到线的距离-在turbo.js中 turbo.js
I am trying to calculate a point to line distance in GSLS - precisely in turbo.js turbo.js
这是一个更普遍的问题的一部分，在该问题中，我尝试查找与一组GeoJSON点相对应的[GeoJSON多行上的最近点]-在1000条线段上设置500个点的计算结果最终是50万个点到距离的计算.
This is part of a more general problem in which I try to find the [closest points on GeoJSON multiline] respective to a set of GeoJSON points - the number of calculations for a 500-points set on 1000 segments line ends up being 500k point-to-distance calculations.
这在浏览器中(甚至在工作程序中)无法处理太多，因此并行性有很大帮助.
This is way too much to handle in the browser (even in workers) so parallelism helps a lot.
诀窍是AFAIK我只能将vec4用作输入，这意味着我只能对成对的点进行计算.
The trick is that AFAIK I can only use a vec4 as an input, which means I can only do calculations on pairs of points.
到目前为止，我已经开始计算所有对的距离和方位-但是无法算出点到线的距离.
So far I've progressed to calculating distance and bearing of all pairs - but can't make the last leg to calculating point-to-line distance.
所以问题是-给a，b和c 3点，并知道
So the question is - given 3 points a, b and c, and knowing
- 他们在lon和lat中的位置
- 它们的成对方位和距离
是否可以使用将vec2，vec3或vec4作为输入参数的转换来计算从a到b和c定义的线的距离?
Is it possible to calculate the distance from a to the line defined by b and c using transforms that use vec2, vec3 or vec4 as input argument?
作为一个子问题-我知道如果三角形的高度(a，b，c)不与线(a，b)相交时如何计算距离，因为它的min(distance(a，b)，距离(a，c)).
As a sub-problem - I know how to calculate the distance if the height of the triangle (a, b, c) doesn't intersect the line (a, b) because it's min(distance(a, b), distance(a, c)).
但是，如何计算它是否相交?
But then, how do I calculate if it intersects?
推荐答案
我不确定我是否完全理解你的问题.
I'm not totally sure I understand your question.
听起来像您想知道500个输入点，1000个线段，每个点中哪个段最接近.
It sounds like for 500 input points you want to know, for 1000 line segments, for each point, which segment is closest.
如果这就是您要的内容，则将所有点放在浮点纹理中(纹理的另一个词是2D数组).绘制一个-1到+1的四边形，该四边形是结果数的大小(500个结果，即50x10或25x20等.)传递纹理的分辨率.使用 gl_FragCoord 计算索引以获取输入A，并在所有其他行上循环.通过将最接近的对的索引编码为颜色，通过readPixels读取结果.
If that's what you're asking then put all the points in a floating point textures (another word for a texture is a 2D array). Draw a -1 to +1 quad that's the size of the number of results (500 results so 50x10 or 25x20 etc..) Pass in the resolution of the textures. Use gl_FragCoord to calculate an index to get the input, A, and loop over all the other lines. Read the results via readPixels by encoding the index of the closest pair as a color.
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 https://stackoverflow.com/a/6853926/128511
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内核计算.
I'm only going to guess though that in general this is better solved with some spatial structure that somehow makes it so you don't have to check every line with every point but something like the code above should work and be very parallel. Each result will be computed by another GPU core.
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 https://stackoverflow.com/a/6853926/128511
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 变为
If you use WebGL2 then you can use texelFetch so getPoint becomes
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和输出无符号整数索引，因此无需对结果进行编码.
and you don't need to pass in the size of the input textures, only the output size. Also you could make your output R32U and output unsigned integer indices so no need to encode the result.
注意:该代码假定您对a，b和c的运算量少于2048，因此大部分代码假定为一维纹理.如果您需要超过2048个，则需要调整代码以使矩形纹理的大小适合您的数据，例如，如果您具有9000个值，则可以使用9x1000纹理.如果您有8999个值，那么由于纹理是2D数组，您仍然需要填充一个9x1000纹理来制作一个矩形.
note: The code assumes you are doing less then 2048 values for each a, b and c so much of the code assumes 1 dimensional textures. If you need more than 2048 you'll need to adjust the code to make rectangular textures of a size that fits your data for example if you had 9000 values then a 9x1000 texture would work. If you have 8999 values then you still need a 9x1000 texture just padded to make a rectangle since textures are 2D arrays.
还要注意，调用readPixels被认为是缓慢的.例如，如果您只想按上述方式绘制结果，而不是渲染到画布上并通过readPixels读取值，则可以将结果渲染到纹理上，然后将纹理传递到另一个着色器中.
Also note that calling readPixels is considered slow. For example, if you just wanted to draw the results as above, instead of rendering to the canvas and reading the values out via readPixels you could render the result to a texture, then pass the texture into another shader.
这可能是错误的地方，但是作为对GLSL的简短解释，您可以将GLSL视为 Array.prototype.map 的精美版本.使用 map 时，您不会选择直接写入的内容.它是间接发生的.
This is probably the wrong place for this but as a terse explanation of GLSL for stuff like this you can think of GLSL as a fancy version of Array.prototype.map. When you use map you don't choose what is being written to directly. It happens indirectly.
const a = [1, 2, 3, 4, 5];
const b = a.map((v, index) => { return v * 2 + index; });
{return v * 2 + index} 部分类似于着色器.在JavaScript中，地图内部的函数会返回值.在GLSL ES 1.0中，着色器将 gl_FragColor 设置为输出.在Javascript中， index 是要写入的数组的索引(也恰好是输入数组的索引).在GLSL中， gl_FragCoord 发挥相同的作用.
The { return v * 2 + index} part is analogous to a shader. In JavaScript the function inside map returns in value. in GLSL ES 1.0 the shader sets gl_FragColor as the output. In the Javascript index is the index of the array being written to (and happens to be the index of the input array as well). In GLSL gl_FragCoord serves the same role.
否则，顶点着色器的输出确定将写入哪些像素(2D数组的哪些数组元素)，从而使其成为 map 的更具选择性的版本.在上面的代码中，我们绘制了一个-1到+1的四边形，实际上是说在所有像素上映射".
Otherwise, the output of the vertex shader determines which pixels (which array elements of a 2D array) will get written to so that makes it a more selective version of map. In the code above we're drawing a -1 to +1 quad effectively saying "map over all pixels".
实际上，这是上述代码的一个版本，没有GLSL，只有JavaScript，但是JavaScript进行了重组，看起来更像GLSL.
In fact here's a version of the above code, no GLSL, just JavaScript, but the JavaScript re-structured to look more like 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>这篇关于在GLSL中计算点到线的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！