この記事は Web グラフィックス Advent Calendar 2021 の7日目の記事です。
はじめに
前回はFlutter Webに触発されてAssemblyScriptで簡単な描画処理を書いてみました。
今回はその延長で、パスで指定した領域の塗りつぶし処理をAssemblyScriptで実装してみました。
仮にFlutterのようにUIを描画しようとした場合、少なくとも角丸四角形とフォントの描画機能くらいは必要だからです。そして、その両方を実現するには、パスで囲まれた領域の描画ができれば、とりあえずなんとかなります。
なお、実用レベルのものを作ろうというわけではなく、実装を体験してみるという程度のモチベーションです。
開発環境
- Visual Studio Code
- AssmblyScript 0.19.19
- Google Chrome 96 (FireFox 94で試したところうまく動きませんでした)
塗りつぶしのアルゴリズム
閉じた領域を塗りつぶすアルゴリズムとして、"Solid Area Scan Conversion"と呼ばれるアルゴリズムがあるそうです。
大雑把にいうと、スキャンラインに沿ってピクセルをスキャンしていって、領域の境界（＝今回の場合、パスを構成する直線や曲線）を通り過ぎるごとに「塗りつぶす」か「塗りつぶさないか」を切り替えていくと、最終的に領域の内部だけを塗りつぶすことができる、というアルゴリズムです。
今回実装してみた所感としては、領域の境界情報をどのように表現し積み上げるかがキモです。それができれば、スキャンしながら塗りつぶす部分は難しくありません。
今回は以下のような形で表現することにしました。
x … ピクセルの横位置
len … xの位置から連続するピクセル数
ln … そのピクセルを通過している直線の数
（実際のプログラムではもっと長いフィールド名にしてます）
jsonで表現した境界情報
[
[],
[{ x: 5, len: 5, ln: 2 }],
[{ x: 2, len: 1, ln: 1 }, { x: 8, len: 1, ln: 1 }],
[{ x: 3, len: 1, ln: 1 }, { x: 7, len: 1, ln: 1 }],
[{ x: 4, len: 1, ln: 1 }, { x: 6, len: 1, ln: 1 }],
[{ x: 5, len: 1, ln: 2 }],
[],
...
]
これは座標
(5, 1), (8, 2), (5, 5), (2, 2)
を頂点とするようなひし形の例です。
図にすると下のようになります。ピクセルの左上が座標値が整数になる位置なので少し不思議な感じがしますが、今回の実装では計算上こうなります。
一番上のところが５ピクセル繋がって通過する直線の数が２になっていること、左右の頂点のところは通過している直線の数が１になっていることが注意すべき点です。
一つの頂点があるピクセルには常に二つの線分が含まれるわけですが、スキャンのとき通過する境界の数として数えるのはピクセルを「通過」している数を数えるので、上向きまたは下向きの角のときは直線の数を２（０でもよい）、横向きの角のときは１として数えるのです。
この形にするには、同じピクセルを複数回パスが通った場合には境界情報を結合したりしないといけないのですが、そのあたりはソースコードを見ていただければと思います。正直いうと怪しいケースがあるのも気づいています。まあ、参考程度ということで…。
TypeScriptで実装してみた
TypeScriptのほうが書くのが楽でビルドも速いはわかっていたので、先にTypeScriptで書いてみて、AssmblyScriptに移植しました。
ちと長いですがGitHubを見るのも面倒だと思いますのでindex.tsを掲載します。
ちなみに筆者は趣味プロではセミコロン無し派です。
index.ts
// 領域全体の情報
class RegionInfo {
// キャンバスのサイズ
canvasWidth = 0
canvasHeight = 0
// 領域を構成するパス
pathSegments: PathSegment[] | null = null
// 塗りつぶしの基準となるエッジ情報（一次元目の要素数はcanvasHeightと一致、二次元目は可変）
edgeInfos: EdgeInfo[][] | null = null
// 領域の矩形範囲
minX = 0
minY = 0
maxX = 0
maxY = 0
constructor(canvasWidth: number, canvasHeight: number) {
this.canvasWidth = canvasWidth
this.canvasHeight = canvasHeight
this.minX = canvasWidth
this.minY = canvasHeight
}
}
// 領域こ構成する線分
class PathSegment {
constructor(public x1: number, public y1: number, public x2: number, public y2: number) {
}
}
// 領域のエッジ情報
class EdgeInfo {
constructor(public x: number, public pixelLength: number, public passingLineCount: number) {
}
}
// エッジ情報構築処理の状態
class EdgeProcessState {
x = 0
y = 0
beginXIndex = 0
lastXIndex = 0
lastYIndex = 0
passingLineCount = 0
}
// 領域情報の作成
function createRegionInfo(width: number, height: number) {
const regionInfo = new RegionInfo(width, height)
resetRegionInfo(regionInfo)
return regionInfo
}
function resetRegionInfo(regionInfo: RegionInfo) {
regionInfo.minX = regionInfo.canvasWidth - 1
regionInfo.minY = regionInfo.canvasHeight -1
regionInfo.maxX = 0
regionInfo.maxY = 0
regionInfo.pathSegments = []
regionInfo.edgeInfos = new Array(regionInfo.canvasHeight)
for (let index = 0; index < regionInfo.edgeInfos.length; index++) {
regionInfo.edgeInfos[index] = []
}
}
// エッジ情報の構築
function constructEdgeInfo(regionInfo: RegionInfo) {
const pathSegments = regionInfo.pathSegments
if (pathSegments.length < 3) {
return
}
const state = new EdgeProcessState()
const first_PathSegment = pathSegments[0]
state.x = Math.floor(first_PathSegment.x1)
state.y = Math.floor(first_PathSegment.y1)
state.beginXIndex = state.x
state.lastXIndex = state.x
state.lastYIndex = state.y
state.passingLineCount = 0
const last_PathSegment = pathSegments[pathSegments.length - 1]
// 最後の線分から最初の線分に戻る部分の状態をさかのぼって計算
backProcessEdgeInfoConstructionForLast(state, last_PathSegment)
// 各線分のエッジ情報を構築
for (let index = 0; index < pathSegments.length; index++) {
const current_PathSegment = pathSegments[index]
const previous_PathSegment = (
index > 0
? pathSegments[index - 1]
: pathSegments[pathSegments.length - 1]
)
processEdgeInfoConstruction(regionInfo, state, current_PathSegment, previous_PathSegment)
}
}
function processEdgeInfoConstruction(regionInfo: RegionInfo, state: EdgeProcessState, current_PathSegment: PathSegment, previous_PathSegment: PathSegment) {
let x = state.x
let y = state.y
let beginXIndex = state.beginXIndex
let lastXIndex = state.lastXIndex
let lastYIndex = state.lastYIndex
let passingLineCount = state.passingLineCount
const current_yDifference = current_PathSegment.y2 - current_PathSegment.y1
const previous_yDifference = previous_PathSegment.y2 - previous_PathSegment.y1
const x1 = current_PathSegment.x1
const y1 = current_PathSegment.y1
const x2 = current_PathSegment.x2
const y2 = current_PathSegment.y2
// エッジ情報の積み上げ
const startX = Math.floor(x1)
const startY = Math.floor(y1)
const endX = Math.floor(x2)
const endY = Math.floor(y2)
const xDifference = endX - startX
const yDifference = endY - startY
// currentとpreviousに挟まれた頂点が、線が一方向に通過する角（＝横向きの角）であることの判定
const isPassingCorner = ( (current_yDifference < 0 && previous_yDifference < 0)
|| (current_yDifference > 0 && previous_yDifference > 0)
|| (current_yDifference == 0 && previous_yDifference != 0)
|| (current_yDifference != 0 && previous_yDifference == 0))
// 一方向に通過する角でない（＝上下向きの角）場合は、ピクセルに入って同じ方向に出ていく二本の線分が存在することとして扱います
if (!isPassingCorner) {
passingLineCount = 2
}
// エッジ情報の積み上げ: 縦方向の線分の場合
if (Math.abs(xDifference) <= Math.abs(yDifference)) {
const scanDirection = Math.sign(yDifference)
while (y != endY) {
// 縦方向に移動
y += scanDirection
// 横方向の位置を計算
const currentX = startX + xDifference / yDifference * (y - startY)
const xIndex = Math.floor(currentX)
// 縦方向に移動したため、確定済みピクセルに登録
{
const startXIndex = Math.min(lastXIndex, beginXIndex)
const endXIndex = Math.max(lastXIndex, beginXIndex)
registerEdgeInfo(regionInfo, startXIndex, lastYIndex, Math.abs(endXIndex - startXIndex) + 1, passingLineCount)
}
// 横方向に移動
x = xIndex
// 確定済みピクセルの範囲を次のピクセルに移動
beginXIndex = Math.floor(currentX)
lastXIndex = beginXIndex
lastYIndex = y
// 頂点以外のエッジは常に交差する線1本として扱う
passingLineCount = 1
}
}
// エッジ情報の積み上げ: 横方向の線分の場合
else {
const scanDirection = Math.sign(xDifference)
while (x != endX) {
// 横方向に移動
x += scanDirection
// 縦方向の位置を計算
const currentY = startY + yDifference / xDifference * (x - startX)
const yIndex = Math.floor(currentY)
// 縦方向の移動が発生する場合
if (yIndex != lastYIndex) {
// 縦方向に移動
y = yIndex
// 縦方向に移動したため、確定済みピクセルに登録
{
const startXIndex = Math.min(lastXIndex, beginXIndex)
const endXIndex = Math.max(lastXIndex, beginXIndex)
registerEdgeInfo(regionInfo, startXIndex, lastYIndex, Math.abs(endXIndex - startXIndex) + 1, passingLineCount)
}
// 確定済みピクセルの範囲を次のピクセルに移動
beginXIndex = x
lastXIndex = beginXIndex
lastYIndex = y
// 頂点以外のエッジは常に交差する線1本として扱う
passingLineCount = 1
}
// 確定済みピクセルの範囲を更新
lastXIndex = x
}
}
// 描画範囲の更新
regionInfo.minX = Math.min(regionInfo.minX, x1, x2)
regionInfo.minY = Math.min(regionInfo.minY, y1, y2)
regionInfo.maxX = Math.max(regionInfo.maxX, x1, x2)
regionInfo.maxY = Math.max(regionInfo.maxY, y1, y2)
regionInfo.minX = Math.max(regionInfo.minX, 0)
regionInfo.minY = Math.max(regionInfo.minY, 0)
regionInfo.maxX = Math.min(regionInfo.maxX, regionInfo.canvasWidth - 1)
regionInfo.maxY = Math.min(regionInfo.maxY, regionInfo.canvasHeight -1)
// 状態の更新
state.x = x
state.y = y
state.beginXIndex = beginXIndex
state.lastXIndex = lastXIndex
state.lastYIndex = lastYIndex
state.passingLineCount = passingLineCount
}
function backProcessEdgeInfoConstructionForLast(state: EdgeProcessState, current_PathSegment: PathSegment) {
let x = state.x
let beginXIndex = state.beginXIndex
let lastXIndex = state.lastXIndex
let lastYIndex = state.lastYIndex
const x1 = current_PathSegment.x1
const y1 = current_PathSegment.y1
const x2 = current_PathSegment.x2
const y2 = current_PathSegment.y2
// エッジ情報の積み上げ
const startX = Math.floor(x1)
const startY = Math.floor(y1)
const endX = Math.floor(x2)
const endY = Math.floor(y2)
const xDifference = endX - startX
const yDifference = endY - startY
// エッジ情報の積み上げ: 縦方向の線分の場合
if (Math.abs(xDifference) <= Math.abs(yDifference)) {
// 縦方向の場合、必ず縦の移動があるため特に処理は必要ありません
}
// エッジ情報の積み上げ: 横方向の線分の場合
else {
const scanDirection = -Math.sign(xDifference)
while (x != startX) {
// 横方向に移動
x += scanDirection
// 縦方向の位置を計算
const currentY = startY + yDifference / xDifference * (x - startX)
const yIndex = Math.floor(currentY)
// 縦方向の移動が発生する場合
if (yIndex != lastYIndex) {
// 確定済みピクセルの範囲を設定
beginXIndex = lastXIndex
break
}
// 確定済みピクセルの範囲を更新
lastXIndex = x
}
}
// 状態の更新
state.beginXIndex = beginXIndex
}
function registerEdgeInfo(regionInfo: RegionInfo, x: number, y: number, pixelLength: number, passingLineCount: number) {
const xIndex = Math.floor(x)
const yIndex = Math.floor(y)
const edgeInfos = regionInfo.edgeInfos[yIndex]
// 登録済みのエッジ情報を検索し、挿入/追加/結合いずれかを決定します
let insertIndex = -1
let combineIndex = -1
for (let index = 0; index < edgeInfos.length; index++) {
const edgeInfo = edgeInfos[index]
if (xIndex + pixelLength - 1 < edgeInfo.x) {
insertIndex = index
break
}
else if (xIndex <= edgeInfo.x + edgeInfo.pixelLength - 1) {
combineIndex = index
break
}
}
if (insertIndex != -1) {
// 挿入
edgeInfos.splice(insertIndex, 0, new EdgeInfo(xIndex, pixelLength, passingLineCount))
}
else if (combineIndex != -1) {
// 結合
const edgeInfo = edgeInfos[combineIndex]
const minX = Math.min(xIndex, edgeInfo.x)
const maxX = Math.max(xIndex + pixelLength - 1, edgeInfo.x + edgeInfo.pixelLength - 1)
edgeInfo.x = minX
edgeInfo.pixelLength = maxX - minX + 1
edgeInfo.passingLineCount += passingLineCount
}
else {
// 追加
edgeInfos.push(new EdgeInfo(xIndex, pixelLength, passingLineCount))
}
}
// 塗りつぶし処理
function rasterizeRegionFill(data: Uint8ClampedArray, regionInfo: RegionInfo) {
const pixelBytes = 4
const lineBytes = regionInfo.canvasWidth * pixelBytes
for (let y = regionInfo.minY; y <= regionInfo.maxY; y++) {
const edgeInfos = regionInfo.edgeInfos[y]
if (edgeInfos.length == 0) {
continue
}
let passingLineCount = 0
for (let index = 0; index < edgeInfos.length; index++) {
const edgeInfo = edgeInfos[index]
let startX = edgeInfo.x
let endX = startX + edgeInfo.pixelLength - 1
// 通過する線分の数が奇数である間のピクセルを塗りつぶします
passingLineCount += edgeInfo.passingLineCount
if ((passingLineCount % 2) == 1) {
for (let indexTo = index + 1; indexTo < edgeInfos.length; indexTo++) {
const edgeInfoTo = edgeInfos[indexTo]
passingLineCount += edgeInfoTo.passingLineCount
// 偶数のところまで継続
if (passingLineCount % 2 == 0) {
endX = edgeInfoTo.x + edgeInfoTo.pixelLength - 1
index = indexTo
break
}
}
}
// 連続する部分の塗りつぶし
let x = startX
let offset = y * lineBytes + x * pixelBytes
for (; x <= endX; x++) {
data[offset + 0] = 0
data[offset + 1] = 0
data[offset + 2] = 0
data[offset + 3] = 255
offset += pixelBytes
}
}
}
}
// パスの作成
let pathCurrentX = 0.0
let pathCurrentY = 0.0
let pathBeginX = 0.0
let pathBeginY = 0.0
function beginPath(regionInfo: RegionInfo, x: number, y: number) {
regionInfo.pathSegments = []
pathCurrentX = x
pathCurrentY = y
pathBeginX = x
pathBeginY = y
}
function lineTo(regionInfo: RegionInfo, x: number, y: number) {
regionInfo.pathSegments.push(new PathSegment(pathCurrentX, pathCurrentY, x, y))
pathCurrentX = x
pathCurrentY = y
}
function closePath(regionInfo: RegionInfo) {
regionInfo.pathSegments.push(new PathSegment(pathCurrentX, pathCurrentY, pathBeginX, pathBeginY))
constructEdgeInfo(regionInfo)
}
// メイン処理
function draw(data: Uint8ClampedArray, width: number, height: number) {
const regionInfo = createRegionInfo(width, height)
resetRegionInfo(regionInfo)
beginPath(regionInfo, 100, 100)
lineTo(regionInfo, 132, 200)
lineTo(regionInfo, 50, 140)
lineTo(regionInfo, 150, 140)
lineTo(regionInfo, 68, 200)
closePath(regionInfo)
rasterizeRegionFill(data, regionInfo)
// printRegionInfo(regionInfo) // エッジ情報を見たい場合
resetRegionInfo(regionInfo)
beginPath(regionInfo, 200, 100)
lineTo(regionInfo, 240, 200)
lineTo(regionInfo, 200, 190)
lineTo(regionInfo, 160, 200)
closePath(regionInfo)
rasterizeRegionFill(data, regionInfo)
// printRegionInfo(regionInfo)
resetRegionInfo(regionInfo)
beginPath(regionInfo, 300, 100)
lineTo(regionInfo, 340, 113)
lineTo(regionInfo, 300, 200)
lineTo(regionInfo, 260, 113)
closePath(regionInfo)
beginPath(regionInfo, 300, 105)
lineTo(regionInfo, 270, 115)
lineTo(regionInfo, 300, 180)
lineTo(regionInfo, 320, 125)
closePath(regionInfo)
beginPath(regionInfo, 298, 111)
lineTo(regionInfo, 298, 122)
lineTo(regionInfo, 280, 117)
closePath(regionInfo)
rasterizeRegionFill(data, regionInfo)
// printRegionInfo(regionInfo)
}
function printRegionInfo(regionInfo: RegionInfo) {
for (const [index, edgeInfos] of regionInfo.edgeInfos.entries()) {
if (edgeInfos.length > 0) {
console.log(index, edgeInfos)
}
}
}
window.onload = () => {
const canvas = document.getElementById('canvas') as HTMLCanvasElement
canvas.width = 400
canvas.height = 300
const ctx = canvas.getContext('2d')
const canvasImageData = ctx.createImageData(canvas.width, canvas.height)
document.getElementById('execute').onclick = () => {
draw(canvasImageData.data, canvas.width, canvas.height)
ctx.putImageData(canvasImageData, 0, 0)
}
draw(canvasImageData.data, canvas.width, canvas.height)
ctx.putImageData(canvasImageData, 0, 0)
}
AssemblyScriptで実装してみた
これも長いですが比較のためにindex.tsを掲載します。
index.ts
// 領域全体の情報
class RegionInfo {
// キャンバスのサイズ
canvasWidth: i32 = 0
canvasHeight: i32 = 0
// 領域を構成するパス
pathSegments: PathSegment[] = []
// 塗りつぶしの基準となるエッジ情報（一次元目の要素数はcanvasHeightと一致、二次元目は可変）
edgeInfos: EdgeInfo[][] = []
// 領域の矩形範囲
minX: i32 = 0
minY: i32 = 0
maxX: i32 = 0
maxY: i32 = 0
constructor(canvasWidth: i32, canvasHeight: i32) {
this.canvasWidth = canvasWidth
this.canvasHeight = canvasHeight
this.minX = canvasWidth
this.minY = canvasHeight
}
}
// 領域こ構成する線分
class PathSegment {
constructor(public x1: number, public y1: number, public x2: number, public y2: number) {
}
}
// 領域のエッジ情報
class EdgeInfo {
constructor(public x: number, public pixelLength: i32, public passingLineCount: i32) {
}
}
// エッジ情報構築処理の状態
class EdgeProcessState {
x: i32 = 0
y: i32 = 0
beginXIndex: i32 = 0
lastXIndex: i32 = 0
lastYIndex: i32 = 0
passingLineCount: i32 = 0
}
// 領域情報の作成
function createRegionInfo(width: i32, height: i32): RegionInfo {
const regionInfo = new RegionInfo(width, height)
resetRegionInfo(regionInfo)
return regionInfo
}
function resetRegionInfo(regionInfo: RegionInfo): void {
regionInfo.minX = regionInfo.canvasWidth - 1
regionInfo.minY = regionInfo.canvasHeight -1
regionInfo.maxX = 0
regionInfo.maxY = 0
regionInfo.pathSegments = []
regionInfo.edgeInfos = new Array(regionInfo.canvasHeight)
for (let index = 0; index < regionInfo.edgeInfos.length; index++) {
regionInfo.edgeInfos[index] = []
}
}
// エッジ情報の構築
function constructEdgeInfo(regionInfo: RegionInfo): void {
const pathSegments = regionInfo.pathSegments
if (pathSegments.length < 3) {
return
}
const state = new EdgeProcessState()
const first_PathSegment = pathSegments[0]
state.x = i32Math.floor(first_PathSegment.x1)
state.y = i32Math.floor(first_PathSegment.y1)
state.beginXIndex = state.x
state.lastXIndex = state.x
state.lastYIndex = state.y
state.passingLineCount = 0
const last_PathSegment = pathSegments[pathSegments.length - 1]
// 最後の線分から最初の線分に戻る部分の状態をさかのぼって計算
backProcessEdgeInfoConstructionForLast(state, last_PathSegment)
// 各線分のエッジ情報を構築
for (let index = 0; index < pathSegments.length; index++) {
const current_PathSegment = pathSegments[index]
const previous_PathSegment = (
index > 0
? pathSegments[index - 1]
: pathSegments[pathSegments.length - 1]
)
processEdgeInfoConstruction(regionInfo, state, current_PathSegment, previous_PathSegment)
}
}
function processEdgeInfoConstruction(regionInfo: RegionInfo, state: EdgeProcessState, current_PathSegment: PathSegment, previous_PathSegment: PathSegment): void {
let x = state.x
let y = state.y
let beginXIndex = state.beginXIndex
let lastXIndex = state.lastXIndex
let lastYIndex = state.lastYIndex
let passingLineCount = state.passingLineCount
const current_yDifference = current_PathSegment.y2 - current_PathSegment.y1
const previous_yDifference = previous_PathSegment.y2 - previous_PathSegment.y1
const x1 = current_PathSegment.x1
const y1 = current_PathSegment.y1
const x2 = current_PathSegment.x2
const y2 = current_PathSegment.y2
// エッジ情報の積み上げ
const startX = Math.floor(x1)
const startY = Math.floor(y1)
const endX = Math.floor(x2)
const endY = Math.floor(y2)
const xDifference = endX - startX
const yDifference = endY - startY
// currentとpreviousに挟まれた頂点が、線が一方向に通過する角（＝横向きの角）であることの判定
const isPassingCorner = ( (current_yDifference < 0 && previous_yDifference < 0)
|| (current_yDifference > 0 && previous_yDifference > 0)
|| (current_yDifference == 0 && previous_yDifference != 0)
|| (current_yDifference != 0 && previous_yDifference == 0))
// 一方向に通過する角でない（＝上下向きの角）場合は、ピクセルに入って同じ方向に出ていく二本の線分が存在することとして扱います
if (!isPassingCorner) {
passingLineCount = 2
}
// エッジ情報の積み上げ: 縦方向の線分の場合
if (Math.abs(xDifference) <= Math.abs(yDifference)) {
const scanDirection = i32Math.sign(yDifference)
while (y != endY) {
// 縦方向に移動
y += scanDirection
// 横方向の位置を計算
const currentX = startX + xDifference / yDifference * (y - startY)
const xIndex = i32Math.floor(currentX)
// 縦方向に移動したため、確定済みピクセルに登録
{
const startXIndex = i32Math.min(lastXIndex, beginXIndex)
const endXIndex = i32Math.max(lastXIndex, beginXIndex)
registerEdgeInfo(regionInfo, startXIndex, lastYIndex, i32Math.abs(endXIndex - startXIndex) + 1, passingLineCount)
}
// 横方向に移動
x = xIndex
// 確定済みピクセルの範囲を次のピクセルに移動
beginXIndex = i32Math.floor(currentX)
lastXIndex = beginXIndex
lastYIndex = y
// 頂点以外のエッジは常に交差する線1本として扱う
passingLineCount = 1
}
}
// エッジ情報の積み上げ: 横方向の線分の場合
else {
const scanDirection = i32Math.sign(xDifference)
while (x != endX) {
// 横方向に移動
x += scanDirection
// 縦方向の位置を計算
const currentY = startY + yDifference / xDifference * (x - startX)
const yIndex = i32Math.floor(currentY)
// 縦方向の移動が発生する場合
if (yIndex != lastYIndex) {
// 縦方向に移動
y = yIndex
// 縦方向に移動したため、確定済みピクセルに登録
{
const startXIndex = i32Math.min(lastXIndex, beginXIndex)
const endXIndex = i32Math.max(lastXIndex, beginXIndex)
registerEdgeInfo(regionInfo, startXIndex, lastYIndex, i32Math.abs(endXIndex - startXIndex) + 1, passingLineCount)
}
// 確定済みピクセルの範囲を次のピクセルに移動
beginXIndex = x
lastXIndex = beginXIndex
lastYIndex = y
// 頂点以外のエッジは常に交差する線1本として扱う
passingLineCount = 1
}
// 確定済みピクセルの範囲を更新
lastXIndex = x
}
}
// 描画範囲の更新
regionInfo.minX = i32Math.min3(regionInfo.minX, x1, x2)
regionInfo.minY = i32Math.min3(regionInfo.minY, y1, y2)
regionInfo.maxX = i32Math.max3(regionInfo.maxX, x1, x2)
regionInfo.maxY = i32Math.max3(regionInfo.maxY, y1, y2)
regionInfo.minX = i32Math.max(regionInfo.minX, 0)
regionInfo.minY = i32Math.max(regionInfo.minY, 0)
regionInfo.maxX = i32Math.min(regionInfo.maxX, regionInfo.canvasWidth - 1)
regionInfo.maxY = i32Math.min(regionInfo.maxY, regionInfo.canvasHeight -1)
// 状態の更新
state.x = x
state.y = y
state.beginXIndex = beginXIndex
state.lastXIndex = lastXIndex
state.lastYIndex = lastYIndex
state.passingLineCount = passingLineCount
}
function backProcessEdgeInfoConstructionForLast(state: EdgeProcessState, current_PathSegment: PathSegment): void {
let x = state.x
let beginXIndex = state.beginXIndex
let lastXIndex = state.lastXIndex
let lastYIndex = state.lastYIndex
const x1 = current_PathSegment.x1
const y1 = current_PathSegment.y1
const x2 = current_PathSegment.x2
const y2 = current_PathSegment.y2
// エッジ情報の積み上げ
const startX = Math.floor(x1)
const startY = Math.floor(y1)
const endX = Math.floor(x2)
const endY = Math.floor(y2)
const xDifference = endX - startX
const yDifference = endY - startY
// エッジ情報の積み上げ: 縦方向の線分の場合
if (Math.abs(xDifference) <= Math.abs(yDifference)) {
// 縦方向の場合、必ず縦の移動があるため特に処理は必要ありません
}
// エッジ情報の積み上げ: 横方向の線分の場合
else {
const scanDirection = -i32Math.sign(xDifference)
while (x != startX) {
// 横方向に移動
x += scanDirection
// 縦方向の位置を計算
const currentY = startY + yDifference / xDifference * (x - startX)
const yIndex = i32Math.floor(currentY)
// 縦方向の移動が発生する場合
if (yIndex != lastYIndex) {
// 確定済みピクセルの範囲を設定
beginXIndex = lastXIndex
break
}
// 確定済みピクセルの範囲を更新
lastXIndex = x
}
}
// 状態の更新
state.beginXIndex = beginXIndex
}
function registerEdgeInfo(regionInfo: RegionInfo, x: number, y: number, pixelLength: i32, passingLineCount: i32): void {
const xIndex = i32Math.floor(x)
const yIndex = i32Math.floor(y)
const edgeInfos = regionInfo.edgeInfos[yIndex]
// 登録済みのエッジ情報を検索し、挿入/追加/結合いずれかを決定します
let insertIndex = -1
let combineIndex = -1
for (let index = 0; index < edgeInfos.length; index++) {
const edgeInfo = edgeInfos[index]
if (xIndex + pixelLength - 1 < edgeInfo.x) {
insertIndex = index
break
}
else if (xIndex <= edgeInfo.x + edgeInfo.pixelLength - 1) {
combineIndex = index
break
}
}
if (insertIndex != -1) {
// 挿入
// ※AssemblyScriptではspliceの仕様が異なり、挿入に使用できないため以下相当の処理をしています
// edgeInfos.splice(insertIndex, 0, new EdgeInfo(xIndex, pixelLength, passingLineCount))
edgeInfos.push(edgeInfos[0])
for (let shiftIndex = edgeInfos.length - 1; shiftIndex > insertIndex; shiftIndex--) {
edgeInfos[shiftIndex] = edgeInfos[shiftIndex - 1]
}
edgeInfos[insertIndex] = new EdgeInfo(xIndex, pixelLength, passingLineCount)
}
else if (combineIndex != -1) {
// 結合
const edgeInfo = edgeInfos[combineIndex]
const minX = i32Math.min(xIndex, edgeInfo.x)
const maxX = i32Math.max(xIndex + pixelLength - 1, edgeInfo.x + edgeInfo.pixelLength - 1)
edgeInfo.x = minX
edgeInfo.pixelLength = maxX - minX + 1
edgeInfo.passingLineCount += passingLineCount
}
else {
// 追加
edgeInfos.push(new EdgeInfo(xIndex, pixelLength, passingLineCount))
}
}
// 塗りつぶし処理
function rasterizeRegionFill(data: Uint8Array, regionInfo: RegionInfo): void {
const pixelBytes: i32 = 4
const lineBytes = regionInfo.canvasWidth * pixelBytes
for (let y = regionInfo.minY; y <= regionInfo.maxY; y++) {
const edgeInfos = regionInfo.edgeInfos[y]
if (edgeInfos.length == 0) {
continue
}
let passingLineCount = 0
for (let index = 0; index < edgeInfos.length; index++) {
const edgeInfo = edgeInfos[index]
let startX = edgeInfo.x
let endX = startX + edgeInfo.pixelLength - 1
// 通過する線分の数が奇数である間のピクセルを塗りつぶします
passingLineCount += edgeInfo.passingLineCount
if ((passingLineCount % 2) == 1) {
for (let indexTo = index + 1; indexTo < edgeInfos.length; indexTo++) {
const edgeInfoTo = edgeInfos[indexTo]
passingLineCount += edgeInfoTo.passingLineCount
// 偶数のところまで継続
if (passingLineCount % 2 == 0) {
endX = edgeInfoTo.x + edgeInfoTo.pixelLength - 1
index = indexTo
break
}
}
}
// 連続する部分の塗りつぶし
let x = startX as u32
let offset = y * lineBytes + x * pixelBytes
for (; x <= endX; x++) {
data[offset + 0] = 0
data[offset + 1] = 0
data[offset + 2] = 0
data[offset + 3] = 255
offset += pixelBytes
}
}
}
}
// パスの作成
let pathCurrentX: number = 0.0
let pathCurrentY: number = 0.0
let pathBeginX: number = 0.0
let pathBeginY: number = 0.0
function beginPath(regionInfo: RegionInfo, x: number, y: number): void {
regionInfo.pathSegments = []
pathCurrentX = x
pathCurrentY = y
pathBeginX = x
pathBeginY = y
}
function lineTo(regionInfo: RegionInfo, x: number, y: number): void {
regionInfo.pathSegments.push(new PathSegment(pathCurrentX, pathCurrentY, x, y))
pathCurrentX = x
pathCurrentY = y
}
function closePath(regionInfo: RegionInfo): void {
regionInfo.pathSegments.push(new PathSegment(pathCurrentX, pathCurrentY, pathBeginX, pathBeginY))
constructEdgeInfo(regionInfo)
}
// メイン処理
export function draw(data: Uint8Array, width: u32, height: u32): void {
const regionInfo = createRegionInfo(width, height)
resetRegionInfo(regionInfo)
beginPath(regionInfo, 100, 100)
lineTo(regionInfo, 132, 200)
lineTo(regionInfo, 50, 140)
lineTo(regionInfo, 150, 140)
lineTo(regionInfo, 68, 200)
closePath(regionInfo)
rasterizeRegionFill(data, regionInfo)
resetRegionInfo(regionInfo)
beginPath(regionInfo, 200, 100)
lineTo(regionInfo, 240, 200)
lineTo(regionInfo, 200, 190)
lineTo(regionInfo, 160, 200)
closePath(regionInfo)
rasterizeRegionFill(data, regionInfo)
resetRegionInfo(regionInfo)
beginPath(regionInfo, 300, 100)
lineTo(regionInfo, 340, 113)
lineTo(regionInfo, 300, 200)
lineTo(regionInfo, 260, 113)
closePath(regionInfo)
beginPath(regionInfo, 300, 105)
lineTo(regionInfo, 270, 115)
lineTo(regionInfo, 300, 180)
lineTo(regionInfo, 320, 125)
closePath(regionInfo)
beginPath(regionInfo, 298, 111)
lineTo(regionInfo, 298, 122)
lineTo(regionInfo, 280, 117)
closePath(regionInfo)
rasterizeRegionFill(data, regionInfo)
}
class i32Math {
static max(a: f64, b: f64): i32 {
return Math.max(a, b) as i32
}
static max3(a: f64, b: f64, c: f64): i32 {
const d = Math.max(a, b)
return Math.max(d, c) as i32
}
static min(a: f64, b: f64): i32 {
return Math.min(a, b) as i32
}
static min3(a: f64, b: f64, c: f64): i32 {
const d = Math.min(a, b)
return Math.min(d, c) as i32
}
static floor(a: f64): i32 {
return Math.floor(a) as i32
}
static sign(a: f64): i32 {
return Math.sign(a) as i32
}
static abs(a: f64): i32 {
return Math.abs(a) as i32
}
}
export const Uint8ArrayID = idof<Uint8Array>()
感想、いいわけ等
アルゴリズムをプログラムにするのはわりあいきつかったですが、AssmblyScriptへの移植はわりあい簡単でした。
ただ、Mathがf64を返すとかmaxの引数が二つまでだとかをどう移植するか悩んだすえ、i32バージョンのMathを作ったりしました。
また、いいわけですが、完全なものを作ることが目的ではないため、以下のことは考慮していません。
- アンチエイリアシング … 難易度が高いため。
- クリッピング … めんどうなので。
- もっといろいろな形状に対応 … やればやるほど特定の場合に破綻することが判明するため。
- 不要になったメモリの扱い … AssemblyScriptはガーベージコレクションをサポートしているので、それまかせにしています。しかしどうもFireFoxで動かないのはメモリ関連が原因みたいなので、調査中です。
まとめ
- AssemblyScriptでパス領域の塗りつぶし描画処理を実装してみた
- 単純なTypeScriptであればAssemblyScriptへの移植はしやすい
- 完全な実装ではありませんので使用にはご注意を。
以上、Webグラフィックスアドベントカレンダー7日目でした。
ご覧いただきありがとうございました。