說明
【跟月影學可視化】學習筆記。
圖形學中的多邊形是什麼？
多邊形又可以分為簡單多邊形和複雜多邊形。
- 簡單多邊形：如果一個多邊形的每條邊除了相鄰的邊以外，不和其他邊相交。
- 凸多邊形：如果一個多邊形中的每個内角都不超過 180°。
不同的圖形系統如何填充多邊形？
1. Canvas2D 如何填充多邊形？
Canvas2D 的 fill 還支援兩種填充規則：
- nonzero：不管有沒有相交的邊，隻要是由邊圍起來的區域都一律填充。
- evenodd：根據重疊區域是奇數還是偶數來判斷是否填充的
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Canvas2D 如何填充多邊形</title>
<style>canvas {
border: 1px dashed salmon;
}</style>
</head>
<body>
<canvas width="512" height="512"></canvas>
<script type="module">import { Vector2D } from "./common/lib/vector2d.js";
const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");
const { width, height } = canvas;
const w = 0.5 * width,
h = 0.5 * height;
ctx.translate(w, h);
ctx.scale(1, -1);
// 繪制坐标軸
function drawAxis() {
ctx.save();
ctx.strokeStyle = "#ccc";
ctx.beginPath();
ctx.moveTo(-w, 0);
ctx.lineTo(w, 0);
ctx.stroke();
ctx.beginPath();
ctx.moveTo(0, -h);
ctx.lineTo(0, h);
ctx.stroke();
ctx.restore();
}
drawAxis();
// nonzero：不管有沒有相交的邊，隻要是由邊圍起來的區域都一律填充。
// evenodd：根據重疊區域是奇數還是偶數來判斷是否填充的
function draw(
context,
points,
{ fillStyle = "salmon", close = false, rule = "nonzero" } = {}
) {
context.beginPath();
context.moveTo(...points[0]);
for (let i = 1; i < points.length; i++) {
context.lineTo(...points[i]);
}
if (close) context.closePath();
context.fillStyle = fillStyle;
context.fill(rule);
}
// 建構多邊形的頂點,這裡來5個
const points = [new Vector2D(0, 100)];
for (let i = 1; i <= 4; i++) {
const p = points[0].copy().rotate(i * Math.PI * 0.4);
points.push(p);
}
// 繪制正五邊形
const polygon = [...points]; // polygon 數組是正五邊形的頂點數組
ctx.save();
ctx.translate(-128, 0);
draw(ctx, polygon);
ctx.restore();
console.log("polygon--->", polygon);
// 繪制正五角星
const stars = [
points[0],
points[2],
points[4],
points[1],
points[3],
]; // stars 數組是把正五邊形的頂點順序交換之後，構成的五角星的頂點數組。
ctx.save();
ctx.translate(128, 0);
draw(ctx, stars);
// draw(ctx, stars, {rule: 'evenodd'});
ctx.restore();</script>
</body>
</html> 
如果改成
rule: 'evenodd'
繪制五角星
draw(ctx, stars, {rule: 'evenodd'}); 2. WebGL 如何填充多邊形？
将多邊形分割成若幹個三角形的操作，在圖形學中叫做三角剖分（Triangulation）。對 3D 模型，WebGL 在繪制的時候，也需要使用三角剖分，而 3D 的三角剖分又被稱為網格化（Meshing）。
推薦學習：Delaunay Triangulation In Two and Three Dimensions
可以使用下面庫來對多邊形進行三角剖分：
- earcut
- tess2.js
- cdt2d
以最簡單的 Earcut 庫（代碼：https://github.com/mapbox/earcut/blob/master/src/earcut.js）為例，來了解 WebGL 填充多邊形的過程
以下面這個多邊形為例子，我們利用 Earcut 庫對其進行三角剖分
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>WebGL 如何填充多邊形</title>
<style>canvas {
border: 1px dashed salmon;
}</style>
</head>
<body>
<canvas width="512" height="512"></canvas>
<script type="module">const canvas = document.querySelector("canvas");
const gl = canvas.getContext("webgl");
const vertex = `
attribute vec2 position;
void main() {
gl_PointSize = 1.0;
gl_Position = vec4(position, 1.0, 1.0);
}
`;
const fragment = `
precision mediump float;
void main() {
gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0);
}
`;
const vertexShader = gl.createShader(gl.VERTEX_SHADER);
gl.shaderSource(vertexShader, vertex);
gl.compileShader(vertexShader);
const fragmentShader = gl.createShader(gl.FRAGMENT_SHADER);
gl.shaderSource(fragmentShader, fragment);
gl.compileShader(fragmentShader);
const program = gl.createProgram();
gl.attachShader(program, vertexShader);
gl.attachShader(program, fragmentShader);
gl.linkProgram(program);
gl.useProgram(program);
// 不規則多邊形的頂點
const vertices = [
[-0.7, 0.5],
[-0.4, 0.3],
[-0.25, 0.71],
[-0.1, 0.56],
[-0.1, 0.13],
[0.4, 0.21],
[0, -0.6],
[-0.3, -0.3],
[-0.6, -0.3],
[-0.45, 0.0],
];
// 使用 Earcut 庫進行三角剖分：Earcut 庫隻接受扁平化的定點資料
import { earcut } from "./common/lib/earcut.js";
// 使用數組的 flat 方法将頂點扁平化
const points = vertices.flat();
// 進行三角剖分
const triangles = earcut(points);
const position = new Float32Array(points);
const cells = new Uint16Array(triangles);
const pointBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, pointBuffer);
gl.bufferData(gl.ARRAY_BUFFER, position, gl.STATIC_DRAW);
const vPosition = gl.getAttribLocation(program, "position");
gl.vertexAttribPointer(vPosition, 2, gl.FLOAT, false, 0, 0);
gl.enableVertexAttribArray(vPosition);
const cellsBuffer = gl.createBuffer();
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, cellsBuffer);
gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, cells, gl.STATIC_DRAW);
gl.clear(gl.COLOR_BUFFER_BIT);
gl.drawElements(gl.TRIANGLES, cells.length, gl.UNSIGNED_SHORT, 0);
// 用描邊 LINE_STRIP 代替填充 TRIANGLES
// gl.drawElements(gl.LINE_STRIP, cells.length, gl.UNSIGNED_SHORT, 0);</script>
</body>
</html> 可以通過用描邊 LINE_STRIP 代替填充 TRIANGLES 就可以清晰的看到這個多邊形被分割成了多個三角形
// 用描邊LINE_STRIP 代替填充 TRIANGLES
gl.drawElements(gl.LINE_STRIP, cells.length, gl.UNSIGNED_SHORT, 0); 注意：三角剖分後傳回的數組裡的值是頂點資料的 index。
如何判斷點在多邊形内部？
判斷一個點是否在多邊形内部時，需要先對多邊形進行三角剖分，然後判斷該點是否在其中一個三角形内部。
1. Canvas2D 如何判斷點在多邊形内部？
我們先使用 canvas2d 繪制出來上面的多邊形
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Canvas2D 如何判斷點在多邊形内部</title>
<style>canvas {
border: 1px dashed salmon;
}</style>
</head>
<body>
<canvas width="512" height="512"></canvas>
<script type="module">const vertices = [
[-0.7, 0.5],
[-0.4, 0.3],
[-0.25, 0.71],
[-0.1, 0.56],
[-0.1, 0.13],
[0.4, 0.21],
[0, -0.6],
[-0.3, -0.3],
[-0.6, -0.3],
[-0.45, 0.0],
];
const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");
const { width, height } = canvas;
ctx.translate(0.5 * width, 0.5 * height);
ctx.scale(1, -1);
const poitions = vertices.map(([x, y]) => [x * 256, y * 256]);
function draw(
ctx,
points,
strokeStyle = "salmon",
fillStyle = null
) {
ctx.strokeStyle = strokeStyle;
ctx.beginPath();
ctx.moveTo(...points[0]);
for (let i = 1; i < points.length; i++) {
ctx.lineTo(...points[i]);
}
ctx.closePath();
if (fillStyle) {
ctx.fillStyle = fillStyle;
ctx.fill();
}
ctx.stroke();
}
draw(ctx, poitions, "transparent", "salmon");
// draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
const { left, top } = canvas.getBoundingClientRect();
canvas.addEventListener("mousemove", (evt) => {
const { x, y } = evt;
// 坐标轉換
const offsetX = x - left;
const offsetY = y - top;
ctx.clearRect(-256, -256, 512, 512);
if (ctx.isPointInPath(offsetX, offsetY)) {
draw(ctx, poitions, "transparent", "green");
// draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'green');
} else {
draw(ctx, poitions, "transparent", "salmon");
// draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
}
});</script>
</body>
</html> 滑鼠放上去也是可以變色的
我們放開那個小多邊形的注釋代碼
我們發現滑鼠隻有放在小三角形裡的時候才會變色
因為 isPointInPath 方法隻能對目前繪制的圖形生效。僅能判斷滑鼠是否在最後一次繪制的小三角形内，是以大多邊形就沒有被識别出來。
解決方法：在繪制的過程中擷取每個圖形的 isPointInPath 結果。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Canvas2D 如何判斷點在多邊形内部2</title>
<style>canvas {
border: 1px dashed salmon;
}</style>
</head>
<body>
<canvas width="512" height="512"></canvas>
<script type="module">const vertices = [
[-0.7, 0.5],
[-0.4, 0.3],
[-0.25, 0.71],
[-0.1, 0.56],
[-0.1, 0.13],
[0.4, 0.21],
[0, -0.6],
[-0.3, -0.3],
[-0.6, -0.3],
[-0.45, 0.0],
];
const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");
const { width, height } = canvas;
ctx.translate(0.5 * width, 0.5 * height);
ctx.scale(1, -1);
const poitions = vertices.map(([x, y]) => [x * 256, y * 256]);
function draw(
ctx,
points,
strokeStyle = "salmon",
fillStyle = null
) {
ctx.strokeStyle = strokeStyle;
ctx.beginPath();
ctx.moveTo(...points[0]);
for (let i = 1; i < points.length; i++) {
ctx.lineTo(...points[i]);
}
ctx.closePath();
if (fillStyle) {
ctx.fillStyle = fillStyle;
ctx.fill();
}
ctx.stroke();
}
function isPointInPath(ctx, x,) {
// 根據ctx重新clone一個新的canvas對象出來
const cloned = ctx.canvas.cloneNode().getContext("2d");
cloned.translate(0.5 * width, 0.5 * height);
cloned.scale(1, -1);
let ret = false;
// 繪制多邊形，然後判斷點是否在圖形内部
draw(cloned, poitions, "transparent", "salmon");
ret |= cloned.isPointInPath(x, y);
if (!ret) {
// 如果不在，在繪制小三角形，然後判斷點是否在圖形内部
draw(cloned, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
ret |= cloned.isPointInPath(x, y);
}
return ret;
}
draw(ctx, poitions, "transparent", "salmon");
draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
const { left, top } = canvas.getBoundingClientRect();
canvas.addEventListener("mousemove", (evt) => {
const { x, y } = evt;
// 坐标轉換
const offsetX = x - left;
const offsetY = y - top;
ctx.clearRect(-256, -256, 512, 512);
if (isPointInPath(ctx, offsetX, offsetY)) {
draw(ctx, poitions, "transparent", "green");
draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'green');
} else {
draw(ctx, poitions, "transparent", "salmon");
draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
}
});</script>
</body>
</html> 2. 實作通用的 isPointInPath 方法
三角形有一個非常簡單的方法可以判斷點是否在其中。
已知一個三角形的三條邊分别是向量 a、b、c，平面上一點 u 連接配接三角形三個頂點的向量分别為 u1、u2、u3，那麼 u 點在三角形内部的充分必要條件是：u1 X a、u2 X b、u3 X c 的符号相同。
當點 u 在三角形 a、b、c 内時，因為 u1到 a、u2到 b、u3到 c 的小角旋轉方向是相同的（這裡都為順時針），是以 u1 X a、u2 X b、u3 X c 要麼同正，要麼同負。當點 v 在三角形外時，v1到 a 方向是順時針，v2到 b 方向是逆時針，v3到 c 方向又是順時針，是以它們叉乘的結果符号并不相同。
左圖是點u和a不在一條直線上，右圖是點u和a在一條直線上
隻有當 u1 和 a 的比值在 0 到 1 之間時，才能說明點在三角形的邊上。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>實作通用的 isPointInPath 方法</title>
<style>canvas {
border: 1px dashed salmon;
}</style>
</head>
<body>
<canvas width="512" height="512"></canvas>
<script type="module">import { Vector2D } from "./common/lib/vector2d.js";
import { earcut } from "./common/lib/earcut.js";
// 判斷點是否在三角形裡面
function inTriangle(p1, p2, p3,) {
const a = p2.copy().sub(p1);
const b = p3.copy().sub(p2);
const c = p1.copy().sub(p3);
const u1 = point.copy().sub(p1);
const u2 = point.copy().sub(p2);
const u3 = point.copy().sub(p3);
const s1 = Math.sign(a.cross(u1));
let p = a.dot(u1) / a.length ** 2;
if (s1 === 0 && p >= 0 && p <= 1) return true;
const s2 = Math.sign(b.cross(u2));
p = b.dot(u1) / b.length ** 2;
if (s2 === 0 && p >= 0 && p <= 1) return true;
const s3 = Math.sign(c.cross(u3));
p = c.dot(u1) / c.length ** 2;
if (s3 === 0 && p >= 0 && p <= 1) return true;
return s1 === s2 && s2 === s3;
}
// 判斷點是否在多邊形裡面
function isPointInPath({ vertices, cells },) {
let ret = false;
for (let i = 0; i < cells.length; i += 3) {
const p1 = new Vector2D(...vertices[cells[i]]);
const p2 = new Vector2D(...vertices[cells[i + 1]]);
const p3 = new Vector2D(...vertices[cells[i + 2]]);
if (inTriangle(p1, p2, p3, point)) {
ret = true;
break;
}
}
return ret;
}
const canvas = document.querySelector("canvas");
const gl = canvas.getContext("webgl");
const vertex = `
attribute vec2 position;
uniform vec4 u_color;
varying vec4 vColor;
void main() {
gl_PointSize = 1.0;
gl_Position = vec4(position, 1.0, 1.0);
vColor = u_color;
}
`;
const fragment = `
precision mediump float;
varying vec4 vColor;
void main() {
gl_FragColor = vColor;
}
`;
const vertexShader = gl.createShader(gl.VERTEX_SHADER);
gl.shaderSource(vertexShader, vertex);
gl.compileShader(vertexShader);
const fragmentShader = gl.createShader(gl.FRAGMENT_SHADER);
gl.shaderSource(fragmentShader, fragment);
gl.compileShader(fragmentShader);
const program = gl.createProgram();
gl.attachShader(program, vertexShader);
gl.attachShader(program, fragmentShader);
gl.linkProgram(program);
gl.useProgram(program);
const vertices = [
[-0.7, 0.5],
[-0.4, 0.3],
[-0.25, 0.71],
[-0.1, 0.56],
[-0.1, 0.13],
[0.4, 0.21],
[0, -0.6],
[-0.3, -0.3],
[-0.6, -0.3],
[-0.45, 0.0],
];
const points = vertices.flat();
const triangles = earcut(points);
console.log("triangles---->", triangles);
const position = new Float32Array(points);
const cells = new Uint16Array(triangles);
const pointBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, pointBuffer);
gl.bufferData(gl.ARRAY_BUFFER, position, gl.STATIC_DRAW);
const vPosition = gl.getAttribLocation(program, "position");
gl.vertexAttribPointer(vPosition, 2, gl.FLOAT, false, 0, 0);
gl.enableVertexAttribArray(vPosition);
const cellsBuffer = gl.createBuffer();
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, cellsBuffer);
gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, cells, gl.STATIC_DRAW);
const colorLoc = gl.getUniformLocation(program, "u_color");
gl.uniform4fv(colorLoc, [1, 0, 0, 1]);
gl.clear(gl.COLOR_BUFFER_BIT);
gl.drawElements(gl.TRIANGLES, cells.length, gl.UNSIGNED_SHORT, 0);
const { left, top } = canvas.getBoundingClientRect();
canvas.addEventListener("mousemove", (evt) => {
const { x, y } = evt;
// 坐标轉換
const offsetX = (2 * (x - left)) / canvas.width - 1.0;
const offsetY = 1.0 - (2 * (y - top)) / canvas.height;
gl.clear(gl.COLOR_BUFFER_BIT);
const colorLoc = gl.getUniformLocation(program, "u_color");
if (
isPointInPath(
{ vertices, cells },
new Vector2D(offsetX, offsetY)
)
) {
gl.uniform4fv(colorLoc, [0, 0.5, 0, 1]);
} else {
gl.uniform4fv(colorLoc, [1, 0, 0, 1]);
}
gl.drawElements(gl.TRIANGLES, cells.length, gl.UNSIGNED_SHORT, 0);
});</script>
</body>
</html>