diff options
Diffstat (limited to 'src/img')
| -rw-r--r-- | src/img/bitmap.nim | 620 | ||||
| -rw-r--r-- | src/img/path.nim | 430 |
2 files changed, 1050 insertions, 0 deletions
diff --git a/src/img/bitmap.nim b/src/img/bitmap.nim new file mode 100644 index 00000000..03048f4d --- /dev/null +++ b/src/img/bitmap.nim @@ -0,0 +1,620 @@ +import algorithm +import math +import unicode + +import bindings/zlib +import css/values +import img/path +import types/color +import types/line +import types/vector + +import lib/endians2 + +type + CanvasFillRule* = enum + NON_ZERO = "nonzero" + EVEN_ODD = "evenodd" + + Bitmap* = ref object of RootObj + px: seq[RGBAColor] + width*: uint64 + height*: uint64 + + ImageBitmap* = ref object of Bitmap + +proc newBitmap*(width, height: uint64): Bitmap = + return ImageBitmap( + px: newSeq[RGBAColor](width * height), + width: width, + height: height + ) + +proc setpx(bmp: Bitmap, x, y: uint64, color: RGBAColor) {.inline.} = + bmp.px[bmp.width * y + x] = color + +proc getpx*(bmp: Bitmap, x, y: uint64): RGBAColor {.inline.} = + return bmp.px[bmp.width * y + x] + +proc setpxb(bmp: Bitmap, x, y: uint64, color: RGBAColor) {.inline.} = + if color.a == 255: + bmp.setpx(x, y, color) + else: + bmp.setpx(x, y, bmp.getpx(x, y).blend(color)) + +# https://en.wikipedia.org/wiki/Bresenham's_line_algorithm#All_cases +proc plotLineLow(bmp: Bitmap, x0, y0, x1, y1: int64, color: RGBAColor) = + var dx = x1 - x0 + var dy = y1 - y0 + var yi = 1 + if dy < 0: + yi = -1 + dy = -dy + var D = 2 * dy - dx; + var y = y0; + for x in x0 ..< x1: + if x < 0 or y < 0 or uint64(x) >= bmp.width or uint64(y) >= bmp.height: + break + bmp.setpxb(uint64(x), uint64(y), color) + if D > 0: + y = y + yi; + D = D - 2 * dx; + D = D + 2 * dy; + +proc plotLineHigh(bmp: Bitmap, x0, y0, x1, y1: int64, color: RGBAColor) = + var dx = x1 - x0 + var dy = y1 - y0 + var xi = 1 + if dx < 0: + xi = -1 + dx = -dx + var D = 2 * dx - dy + var x = x0 + for y in y0 ..< y1: + if x < 0 or y < 0 or uint64(x) >= bmp.width or uint64(y) >= bmp.height: + break + bmp.setpxb(uint64(x), uint64(y), color) + if D > 0: + x = x + xi + D = D - 2 * dy + D = D + 2 * dx + +#TODO should be uint64... +proc plotLine(bmp: Bitmap, x0, y0, x1, y1: int64, color: RGBAColor) = + if abs(y1 - y0) < abs(x1 - x0): + if x0 > x1: + bmp.plotLineLow(x1, y1, x0, y0, color) + else: + bmp.plotLineLow(x0, y0, x1, y1, color) + else: + if y0 > y1: + bmp.plotLineHigh(x1, y1, x0, y0, color) + else: + bmp.plotLineHigh(x0, y0, x1, y1, color) + +proc plotLine(bmp: Bitmap, a, b: Vector2D, color: RGBAColor) = + bmp.plotLine(int64(a.x), int64(a.y), int64(b.x), int64(b.y), color) + +proc plotLine(bmp: Bitmap, line: Line, color: RGBAColor) = + bmp.plotLine(line.p0, line.p1, color) + +proc strokePath*(bmp: Bitmap, path: Path, color: RGBAColor) = + for line in path.lines: + bmp.plotLine(line, color) + +func isInside(windingNumber: int, fillRule: CanvasFillRule): bool = + return case fillRule + of NON_ZERO: windingNumber != 0 + of EVEN_ODD: windingNumber mod 2 == 0 + +# Mainly adapted from SerenityOS. +proc fillPath*(bmp: Bitmap, path: Path, color: RGBAColor, + fillRule: CanvasFillRule) = + let lines = path.getLineSegments() + var i = 0 + var ylines: seq[LineSegment] + for y in int64(lines.miny) .. int64(lines.maxy): + for k in countdown(ylines.high, 0): + if ylines[k].maxy < float64(y): + ylines.del(k) # we'll sort anyways, so del is fine + for j in i ..< lines.len: + if lines[j].miny > float64(y): + break + if lines[j].maxy > float64(y): + ylines.add(lines[j]) + inc i + ylines.sort(cmpLineSegmentX) + var w = if fillRule == NON_ZERO: 1 else: 0 + for k in 0 ..< ylines.high: + let a = ylines[k] + let b = ylines[k + 1] + let sx = int64(a.minyx) + let ex = int64(b.minyx) + if isInside(w, fillRule) and y > 0: + for x in sx .. ex: + if x > 0: + bmp.setpxb(uint64(x), uint64(y), color) + if int64(a.p0.y) != y and int64(a.p1.y) != y and int64(b.p0.y) != y and + int64(b.p1.y) != y and sx != ex or a.islope * b.islope < 0: + case fillRule + of EVEN_ODD: inc w + of NON_ZERO: + if a.p0.y < a.p1.y: + inc w + else: + dec w + ylines[k].minyx += ylines[k].islope + if ylines.len > 0: + ylines[^1].minyx += ylines[^1].islope + +proc fillRect*(bmp: Bitmap, x0, x1, y0, y1: uint64, color: RGBAColor) = + for y in y0 ..< y1: + for x in x0 ..< x1: + bmp.setpxb(x, y, color) + +proc strokeRect*(bmp: Bitmap, x0, x1, y0, y1: uint64, color: RGBAColor) = + for x in x0 ..< x1: + bmp.setpxb(x, y0, color) + bmp.setpxb(x, y1, color) + for y in y0 ..< y1: + bmp.setpxb(x0, y, color) + bmp.setpxb(x1, y, color) + +proc clearRect*(bmp: Bitmap, x0, x1, y0, y1: uint64) = + for y in y0 ..< y1: + for x in x0 ..< x1: + bmp.setpx(x, y, rgba(0, 0, 0, 0)) + +proc clear*(bmp: Bitmap) = + bmp.clearRect(0, bmp.width, 0, bmp.height) + +#TODO clean up templates, also move png encoder to a different file +type PNGWriter = object + buf: pointer + i: int + outlen: int + +func pngInt(i: uint32): auto = + doAssert i < uint32(2 ^ 31) + return i.toBytesBE() + +func oq(writer: PNGWriter): ptr UncheckedArray[uint8] = + cast[ptr UncheckedArray[uint8]](writer.buf) + +proc writeStr[T](writer: var PNGWriter, s: T) = + if writer.outlen < writer.i + s.len: + writer.outlen = writer.i + s.len + writer.buf = realloc(writer.buf, writer.outlen) + copyMem(addr writer.oq[writer.i], unsafeAddr s[0], s.len) + writer.i += s.len + +proc writeInt(writer: var PNGWriter, i: uint32) = + writer.writeStr(i.toBytesBE()) + +proc writePngInt(writer: var PNGWriter, i: uint32) = + doAssert i < uint32(2 ^ 31) + writer.writeInt(i) + +proc writeChunk[T](writer: var PNGWriter, t: string, data: T) = + var crc = uint32(crc32(0, cast[ptr uint8](unsafeAddr t[0]), cuint(t.len))) + if data.len > 0: + crc = uint32(crc32(crc, cast[ptr uint8](unsafeAddr data[0]), + cuint(data.len))) + writer.writePngInt(uint32(data.len)) + writer.writeStr(t) + if data.len > 0: + writer.writeStr(data) + writer.writeInt(uint32(crc)) + +type PNGColorType {.size: sizeof(uint8).} = enum + GRAYSCALE = 0 + TRUECOLOR = 2 + INDEXED_COLOR = 3 + GRAYSCALE_WITH_ALPHA = 4 + TRUECOLOR_WITH_ALPHA = 6 + +func u8toc(x: openArray[uint8]): string = + #TODO ew + var s = newString(x.len) + copyMem(addr s[0], unsafeAddr x[0], x.len) + return s + +const PNGSignature = "\x89PNG\r\n\x1A\n" +proc writeIHDR(writer: var PNGWriter, width, height: uint32, + bitDepth: uint8, colorType: PNGColorType, + compressionMethod, filterMethod, interlaceMethod: uint8) = + writer.writeStr(PNGSignature) + let ihdr = u8toc(pngInt(width)) & + u8toc(pngInt(height)) & + char(bitDepth) & + char(uint8(colorType)) & + char(compressionMethod) & + char(filterMethod) & + char(interlaceMethod) + writer.writeChunk("IHDR", ihdr) + +proc writeIDAT(writer: var PNGWriter, bmp: Bitmap) = + #TODO smaller idat chunks + # +1 height for filter + var idat = newSeq[uint8]((bmp.width + 1) * bmp.height * 4) + var j = 0 # idat pointer + for k in 0 ..< bmp.px.len: + if k mod int(bmp.width) == 0: + # begin row + # For now, filter is always 0. TODO implement other filters + inc j + let p = bmp.px[k] + idat[j] = uint8(p.r) + idat[j + 1] = uint8(p.g) + idat[j + 2] = uint8(p.b) + idat[j + 3] = uint8(p.a) + j += 4 + var hlen = compressBound(culong(idat.len)) + var oidat = newSeq[uint8](int(hlen)) + let res = compress(addr oidat[0], addr hlen, addr idat[0], culong(idat.len)) + doAssert res == Z_OK #TODO error handling... + oidat.setLen(int(hlen)) + writer.writeChunk("IDAT", oidat) + +proc toPNG*(bmp: Bitmap, outlen: var int): pointer = + var writer = PNGWriter( + buf: alloc(PNGSignature.len), + outlen: PNGSignature.len + ) + writer.writeIHDR(uint32(bmp.width), uint32(bmp.height), 8, + TRUECOLOR_WITH_ALPHA, 0, 0, 0) + writer.writeIDAT(bmp) + writer.writeChunk("IEND", "") + outlen = writer.outlen + return writer.buf + +type PNGReader = object + bmp: Bitmap + iq: ptr UncheckedArray[uint8] + limit: int + i: int + bitDepth: uint8 + colorType: PNGColorType + background: RGBColor + isend: bool + idatBuf: seq[uint8] + uprow: seq[uint8] + idatAt: int + hasstrm: bool + strm: z_stream + strmend: bool + atline: int + +func width(reader: PNGReader): int {.inline.} = int(reader.bmp.width) + +func height(reader: PNGReader): int {.inline.} = int(reader.bmp.height) + +func spp(reader: PNGReader): int = + case reader.colorType + of TRUECOLOR: return 3 + of GRAYSCALE: return 1 + of INDEXED_COLOR: return 1 + of GRAYSCALE_WITH_ALPHA: return 2 + of TRUECOLOR_WITH_ALPHA: return 4 + +func scanlen(reader: PNGReader): int {.inline.} = + let w = reader.width + 1 + return (w * reader.spp * int(reader.bitDepth) + 7) div 8 + +proc handleError(reader: var PNGReader, msg: string) = + reader.bmp = nil + if reader.hasstrm: + discard inflateEnd(addr reader.strm) + +template err(reader: var PNGReader, msg: string) = + reader.handleError(msg) + return + +template readStr(reader: var PNGReader, L: int): string = + if reader.i + L > reader.limit: + reader.err "too short" + var s = newString(L) + copyMem(addr s[0], addr reader.iq[reader.i], L) + reader.i += L + s + +template readU8(reader: var PNGReader): uint8 = + if reader.i > reader.limit: + reader.err "too short" + let x = reader.iq[reader.i] + inc reader.i + x + +template readU32(reader: var PNGReader): uint32 = + if reader.i + 4 > reader.limit: + reader.err "too short" + let x = fromBytesBE(uint32, toOpenArray(reader.iq, reader.i, reader.i + 3)) + reader.i += 4 + x + +template readPNGInt(reader: var PNGReader): uint32 = + let x = reader.readU32() + if x >= uint32(2 ^ 31): + reader.err "int too large" + x + +template readColorType(reader: var PNGReader): PNGColorType = + case reader.readU8() + of 0u8: GRAYSCALE + of 2u8: TRUECOLOR + of 3u8: INDEXED_COLOR + of 4u8: GRAYSCALE_WITH_ALPHA + of 6u8: TRUECOLOR_WITH_ALPHA + else: reader.err "unknown color type" + +func bitDepthValid(colorType: PNGColorType, bitDepth: uint8): bool = + case colorType + of GRAYSCALE: + return int(bitDepth) in [1, 2, 4, 8, 16] + of INDEXED_COLOR: + return int(bitDepth) in [1, 2, 4, 8] + of TRUECOLOR, GRAYSCALE_WITH_ALPHA, TRUECOLOR_WITH_ALPHA: + return int(bitDepth) in [8, 16] + +proc readIHDR(reader: var PNGReader) = + if reader.readStr(PNGSignature.len) != PNGSignature: + reader.err "wrong signature" + if reader.readPNGInt() != 13: + reader.err "invalid header length" + if reader.readStr(4) != "IHDR": + reader.err "invalid header chunk" + let width = reader.readPNGInt() + let height = reader.readPNGInt() + reader.bitDepth = reader.readU8() #TODO check? + reader.colorType = reader.readColorType() + if not bitDepthValid(reader.colorType, reader.bitDepth): + reader.err "invalid bit depth" + let compressionMethod = reader.readU8() + if compressionMethod != 0: + reader.err "unknown compression method" + let filterMethod = reader.readU8() + if filterMethod != 0: + reader.err "unknown filter method" + let interlaceMethod = reader.readU8() + if interlaceMethod != 0: + reader.err "unknown interlace method" + let crc = crc32(0, addr reader.iq[reader.i - 17], 17) + if uint32(crc) != reader.readU32(): reader.err "wrong crc" + reader.bmp = newBitmap(width, height) + +proc readbKGD(reader: var PNGReader) = + case reader.colorType + of GRAYSCALE, GRAYSCALE_WITH_ALPHA: + discard reader.readU8() #TODO bit depth > 8 + reader.background = gray(reader.readU8()) + of TRUECOLOR, TRUECOLOR_WITH_ALPHA: + discard reader.readU8() #TODO bit depth > 8 + let r = reader.readU8() + discard reader.readU8() + let g = reader.readU8() + discard reader.readU8() + let b = reader.readU8() + reader.background = rgb(r, g, b) + of INDEXED_COLOR: + discard #TODO + +proc unfilter(reader: var PNGReader, irow: openArray[uint8], bpp: int) = + # none, sub, up -> replace uprow directly + # average, paeth -> copy to temp array, then replace uprow + let fil = irow[0] + let w = reader.width + case fil + of 0u8: # none + copyMem(addr reader.uprow[0], unsafeAddr irow[1], w) + of 1u8: # sub + for i in 1 ..< irow.len: + let j = i - 1 # skip filter byte + reader.uprow[j] = irow[i] + if j - bpp >= 0: + reader.uprow[j] += irow[j - bpp] + of 2u8: # up + for i in 1 ..< irow.len: + let j = i - 1 # skip filter byte + reader.uprow[j] += irow[i] + of 3u8: # average + reader.err "average not implemented yet" + of 4u8: # paeth + reader.err "paeth not implemented yet" + else: + eprint fil + reader.err "got invalid filter" + +proc writepxs(reader: var PNGReader, crow: var openArray[RGBAColor]) = + case reader.colorType + of GRAYSCALE: + var i = 0 + var j = 0 + for x in 0 ..< crow.len: + let u = reader.uprow[i] + let n = case reader.bitDepth + of 1: ((u shr (7 - j)) and 1) * 255 + of 2: ((u shr (6 - j)) and 3) * 85 + of 4: ((u shr (6 - j)) and 15) * 17 + of 8: u + of 16: u div 2 + else: 0 + j += int(reader.bitDepth) + i += j div 8 + j = j mod 8 + let nn = int(n) + crow[x] = rgba(nn, nn, nn, 255) + else: discard + +proc readIDAT(reader: var PNGReader) = + if reader.idatAt == reader.idatBuf.len: + reader.err "idat buffer already filled" + if reader.strmend: + reader.err "stream already ended" + reader.strm.avail_in = cuint(reader.limit - reader.i) + reader.strm.next_in = addr reader.iq[reader.i] + let olen = reader.idatBuf.len - reader.idatAt + reader.strm.avail_out = cuint(olen) + reader.strm.next_out = addr reader.idatBuf[reader.idatAt] + let res = inflate(addr reader.strm, Z_NO_FLUSH) + doAssert res != Z_STREAM_ERROR + case res + of Z_NEED_DICT, Z_DATA_ERROR, Z_MEM_ERROR, Z_BUF_ERROR: + # Z_BUF_ERROR is fatal here, as outlen is at least as large as idat. + reader.err "error decompressing idat stream" + of Z_STREAM_END: + reader.strmend = true + of Z_OK: + if reader.strm.avail_out == 0: + reader.err "not enough space for output; is width or height wrong?" + else: doAssert false + reader.idatAt = int(reader.strm.total_out) + reader.i = reader.limit + let maxline = reader.idatAt div int(reader.scanlen) + let bmp = reader.bmp + let bps = if reader.bitDepth <= 8: 1 else: 2 # else 16 bit + let bpp = bps * reader.spp + let sl = int(reader.scanlen) + for y in reader.atline ..< maxline: + let yi = y * sl + assert yi + sl - 1 < reader.idatAt + reader.unfilter(toOpenArray(reader.idatBuf, yi, yi + sl - 1), bpp) + if unlikely(reader.bmp == nil): return + let yj = y * reader.width + reader.writepxs(toOpenArray(bmp.px, yj, yj + reader.width - 1)) + +proc readIEND(reader: var PNGReader) = + if reader.i < reader.limit: + reader.err "IEND too long" + reader.isend = true + +proc readUnknown(reader: var PNGReader, s: string) = + if (int(s[0]) and 0x20) == 0: + reader.err "unrecognized critical chunk " & s + #else: eprint "warning: unknown chunk " & s #debug + reader.i = reader.limit + +proc zlibAlloc(opaque: pointer, items: cuint, size: cuint): pointer {.cdecl.} = + return alloc(items * size) + +proc zlibFree(opaque: pointer, address: pointer) {.cdecl.} = + dealloc(address) + +proc initZStream(reader: var PNGReader) = + let bps = max(int(reader.bitDepth) div 8, 1) + reader.idatBuf = newSeq[uint8](reader.scanlen * reader.height * bps) + reader.uprow = newSeq[uint8](reader.width * bps) + reader.strm = z_stream( + zalloc: zlibAlloc, + zfree: zlibFree + ) + let ret = inflateInit(addr reader.strm) + if ret != Z_OK: + reader.err "failed to init inflate: " & $ret + reader.hasstrm = true + +proc fromPNG*(iq: openArray[uint8]): Bitmap = + if iq.len == 0: return + var reader = PNGReader( + iq: cast[ptr UncheckedArray[uint8]](unsafeAddr iq[0]), + limit: iq.len + ) + reader.readIHDR() + if reader.bmp == nil: return + if reader.width == 0 or reader.height == 0: + reader.err "invalid zero sized png" + if reader.colorType != GRAYSCALE: + reader.err "only grayscale is implemented" + reader.initZStream() + while reader.i < iq.len and not reader.isend: + let len = int(reader.readPNGInt()) + if reader.i + len > iq.len: + reader.err "chunk too long" + let j = reader.i + let t = reader.readStr(4) + reader.limit = reader.i + len + case t + of "IHDR": reader.err "IHDR expected to be first chunk" + of "IDAT": reader.readIDAT() + of "IEND": reader.readIEND() + of "bKGD": reader.readbKGD() + else: reader.readUnknown(t) + if reader.bmp == nil: return + let crc = crc32(0, unsafeAddr iq[j], cuint(len + 4)) + reader.limit = iq.len + let y = reader.readU32() + if uint32(crc) != y: + reader.err "wrong crc" + if not reader.isend: + reader.err "IEND not found" + return reader.bmp + +const unifont = readFile"res/unifont_jp-15.0.05.png" +var unifontBitmap: Bitmap +var glyphCache: seq[tuple[u: uint32, bmp: Bitmap]] +var glyphCacheI = 0 +proc getCharBmp(u: uint32): Bitmap = + # We only have the BMP. + let u = if u <= 0xFFFF: u else: 0xFFFD + if unifontBitmap == nil: + unifontBitmap = fromPNG(toOpenArrayByte(unifont, 0, unifont.high)) + for (cu, bmp) in glyphCache: + if cu == u: + return bmp + # Unifont glyphs start at x: 32, y: 64, and are of 8x16/16x16 size + let gx = uint64(32 + 16 * (u mod 0xFF)) + let gy = uint64(64 + 16 * (u div 0xFF)) + var fullwidth = false + const white = rgba(255, 255, 255, 255) + block loop: + # hack to recognize full width characters + for y in 0 ..< 16u64: + for x in 8 ..< 16u64: + if unifontBitmap.getpx(gx + x, gy + y) != white: + fullwidth = true + break loop + let bmp = newBitmap(if fullwidth: 16 else: 8, 16) + for y in 0 ..< bmp.height: + for x in 0 ..< bmp.width: + let c = unifontBitmap.getpx(gx + x, gy + y) + if c != white: + bmp.setpx(x, y, c) + if glyphCache.len < 256: + glyphCache.add((u, bmp)) + else: + glyphCache[glyphCacheI] = (u, bmp) + inc glyphCacheI + if glyphCacheI >= glyphCache.len: + glyphCacheI = 0 + return bmp + +proc drawBitmap(a, b: Bitmap, p: Vector2D) = + for y in 0 ..< b.height: + for x in 0 ..< b.width: + let ax = uint64(p.x) + x + let ay = uint64(p.y) + y + if ax >= 0 and ay >= y and ax < a.width and ay < a.height: + a.setpxb(ax, ay, b.getpx(x, y)) + +proc fillText*(bmp: Bitmap, text: string, x, y: float64, color: RGBAColor, + textAlign: CSSTextAlign) = + var w = 0f64 + var glyphs: seq[Bitmap] + for r in text.runes: + let glyph = getCharBmp(uint32(r)) + glyphs.add(glyph) + w += float64(glyph.width) + var x = x + #TODO rtl + case textAlign + of TEXT_ALIGN_LEFT, TEXT_ALIGN_START: discard + of TEXT_ALIGN_RIGHT, TEXT_ALIGN_END: x -= w + of TEXT_ALIGN_CENTER: x -= w / 2 + else: doAssert false + for glyph in glyphs: + bmp.drawBitmap(glyph, Vector2D(x: x, y: y - 8)) + x += float64(glyph.width) + +proc strokeText*(bmp: Bitmap, text: string, x, y: float64, color: RGBAColor, + textAlign: CSSTextAlign) = + #TODO + bmp.fillText(text, x, y, color, textAlign) diff --git a/src/img/path.nim b/src/img/path.nim new file mode 100644 index 00000000..4c112f28 --- /dev/null +++ b/src/img/path.nim @@ -0,0 +1,430 @@ +import algorithm +import deques +import math + +import types/line +import types/vector + +type + Path* = ref object + subpaths: seq[Subpath] + needsNewSubpath: bool + tempClosed: bool + + PathLines* = object + lines*: seq[LineSegment] + miny*: float64 + maxy*: float64 + + PathSegmentType = enum + SEGMENT_STRAIGHT, SEGMENT_QUADRATIC, SEGMENT_BEZIER, SEGMENT_ARC, + SEGMENT_ELLIPSE + + PathSegment = object + case t: PathSegmentType + of SEGMENT_QUADRATIC: + cp: Vector2D + of SEGMENT_BEZIER: + cp0: Vector2D + cp1: Vector2D + of SEGMENT_ARC: + oa: Vector2D + r: float64 + ia: bool + of SEGMENT_ELLIPSE: + oe: Vector2D + rx: float64 + ry: float64 + else: discard + + Subpath* = object + points: seq[Vector2D] + segments: seq[PathSegment] + closed: bool + +proc newPath*(): Path = + return Path( + needsNewSubpath: true + ) + +proc addSubpathAt(path: Path, p: Vector2D) = + path.subpaths.add(Subpath(points: @[p])) + +proc addSegment(path: Path, segment: PathSegment, p: Vector2D) = + path.subpaths[^1].segments.add(segment) + path.subpaths[^1].points.add(p) + +proc addStraightSegment(path: Path, p: Vector2D) = + let segment = PathSegment(t: SEGMENT_STRAIGHT) + path.addSegment(segment, p) + +proc addQuadraticSegment(path: Path, cp, p: Vector2D) = + let segment = PathSegment( + t: SEGMENT_QUADRATIC, + cp: cp + ) + path.addSegment(segment, p) + +proc addBezierSegment(path: Path, cp0, cp1, p: Vector2D) = + let segment = PathSegment( + t: SEGMENT_BEZIER, + cp0: cp0, + cp1: cp1 + ) + path.addSegment(segment, p) + +# Goes from start tangent point to end tangent point +proc addArcSegment(path: Path, o, etan: Vector2D, r: float64, ia: bool) = + let segment = PathSegment( + t: SEGMENT_ARC, + oa: o, + r: r, + ia: ia + ) + path.addSegment(segment, etan) + +proc addEllipseSegment(path: Path, o, etan: Vector2D, rx, ry: float64) = + #TODO simplify to bezier? + let segment = PathSegment( + t: SEGMENT_ELLIPSE, + oe: o, + rx: rx, + ry: ry + ) + path.addSegment(segment, etan) + +# https://hcklbrrfnn.files.wordpress.com/2012/08/bez.pdf +func flatEnough(a, b, c: Vector2D): bool = + let ux = 3 * c.x - 2 * a.x - b.x + let uy = 3 * c.y - 2 * a.y - b.y + let vx = 3 * c.x - 2 * b.x - b.x + let vy = 3 * c.y - 2 * b.y - b.y + return max(ux * ux, vx * vx) + max(uy * uy, vy * vy) <= 0.02 + +func flatEnough(a, b, c0, c1: Vector2D): bool = + let ux = 3 * c0.x - 2 * a.x - b.x + let uy = 3 * c0.y - 2 * a.y - b.y + let vx = 3 * c1.x - a.x - 2 * b.x + let vy = 3 * c1.y - a.y - 2 * b.y + return max(ux * ux, vx * vx) + max(uy * uy, vy * vy) <= 0.02 + +iterator items*(pl: PathLines): LineSegment {.inline.} = + for line in pl.lines: + yield line + +func `[]`*(pl: PathLines, i: int): LineSegment = pl.lines[i] +func `[]`*(pl: PathLines, i: BackwardsIndex): LineSegment = pl.lines[i] +func `[]`*(pl: PathLines, s: Slice[int]): seq[LineSegment] = pl.lines[s] +func len*(pl: PathLines): int = pl.lines.len + +iterator quadraticLines(a, b, c: Vector2D): Line {.inline.} = + var points: Deque[tuple[a, b, c: Vector2D]] + let tup = (a, b, c) + points.addFirst(tup) + while points.len > 2: + let (a, b, c) = points.popFirst() + if flatEnough(a, b, c): + yield Line(p0: a, p1: b) + else: + let mid1 = (c + a) / 2 + let mid2 = (c + b) / 2 + let s = (mid1 + mid2) / 2 + points.addFirst((a, s, mid1)) + points.addFirst((s, b, mid2)) + +iterator bezierLines(p0, p1, c0, c1: Vector2D): Line {.inline.} = + var points: Deque[tuple[p0, p1, c0, c1: Vector2D]] + let tup = (p0, p1, c0, c1) + points.addLast(tup) + while points.len > 0: + let (p0, p1, c0, c1) = points.popFirst() + if flatEnough(p0, p1, c0, c1): + yield Line(p0: p0, p1: p1) + else: + let mida1 = (p0 + c0) / 2 + let mida2 = (c0 + c1) / 2 + let mida3 = (c1 + p1) / 2 + let midb1 = (mida1 + mida2) / 2 + let midb2 = (mida2 + mida3) / 2 + let midc = (midb1 + midb2) / 2 + points.addLast((p0, midc, mida1, midb1)) + points.addLast((midc, p1, midb2, mida3)) + +# https://stackoverflow.com/a/44829356 +func arcControlPoints(p1, p4, o: Vector2D): tuple[c0, c1: Vector2D] = + let a = p1 - o + let b = p4 - o + let q1 = a.x * a.x + a.y * a.y + let q2 = q1 + a.x * b.x + a.y * b.y + let k2 = (4 / 3) * (sqrt(2 * q1 * q2) - q2) / a.cross(b) + let c0 = o + a + Vector2D(x: -k2 * a.y, y: k2 * a.x) + let c1 = o + b + Vector2D(x: k2 * b.y, y: -k2 * b.x) + return (c0, c1) + +iterator arcLines(p0, p1, o: Vector2D, r: float64, i: bool): Line {.inline.} = + var p0 = p0 + let pp0 = p0 - o + let pp1 = p1 - o + var theta = pp0.innerAngle(pp1) + if not i: + theta = PI * 2 - theta + while theta > 0: + let step = if theta > PI / 2: PI / 2 else: theta + var p1 = p0 - o + p1 = p1.rotate(step) + p1 += o + let (c0, c1) = arcControlPoints(p0, p1, o) + for line in bezierLines(p0, p1, c0, c1): + yield line + p0 = p1 + theta -= step + +# From SerenityOS +iterator ellipseLines(p0, p1, o: Vector2D, rx, ry, theta_1, rotx, + theta_delta: float64): Line {.inline.} = + if rx > 0 and ry > 0: + var s = p0 + var e = p1 + var theta_1 = theta_1 + var theta_delta = theta_delta + if theta_delta < 0: + swap(s, e) + theta_1 += theta_delta + theta_delta = abs(theta_delta) + # The segments are at most 1 long + let step = arctan2(1f64, max(rx, ry)) + var current_point = s - o + var next_point = Vector2D() + var theta = theta_1 + while theta <= theta_1 + theta_delta: + next_point.x = rx * cos(theta) + next_point.y = ry * sin(theta) + next_point = next_point.rotate(rotx) + yield Line(p0: current_point + o, p1: next_point + o) + current_point = next_point + theta += step + yield Line(p0: current_point + o, p1: e) + +iterator lines(subpath: Subpath, i: int): Line {.inline.} = + let p0 = subpath.points[i] + let p1 = subpath.points[i + 1] + case subpath.segments[i].t + of SEGMENT_STRAIGHT: + yield Line(p0: p0, p1: p1) + of SEGMENT_QUADRATIC: + let c = subpath.segments[i].cp + for line in quadraticLines(p0, p1, c): + yield line + of SEGMENT_BEZIER: + let c0 = subpath.segments[i].cp0 + let c1 = subpath.segments[i].cp1 + for line in bezierLines(p0, p1, c0, c1): + yield line + of SEGMENT_ARC: + let o = subpath.segments[i].oa + let r = subpath.segments[i].r + let i = subpath.segments[i].ia + for line in arcLines(p0, p1, o, r, i): + yield line + of SEGMENT_ELLIPSE: + discard #TODO + +iterator lines*(path: Path): Line {.inline.} = + for subpath in path.subpaths: + assert subpath.points.len == subpath.segments.len + 1 + for i in 0 ..< subpath.segments.len: + for line in subpath.lines(i): + if line.p0 == line.p1: + continue + yield line + +proc getLineSegments*(path: Path): PathLines = + if path.subpaths.len == 0: + return + var miny = Inf + var maxy = -Inf + var segments: seq[LineSegment] + for line in path.lines: + let ls = LineSegment(line) + miny = min(miny, ls.miny) + maxy = max(maxy, ls.maxy) + segments.add(ls) + segments.sort(cmpLineSegmentY) + return PathLines( + miny: miny, + maxy: maxy, + lines: segments + ) + +proc moveTo(path: Path, v: Vector2D) = + path.addSubpathAt(v) + path.needsNewSubpath = false #TODO TODO TODO ???? why here + +proc beginPath*(path: Path) = + path.subpaths.setLen(0) + +proc moveTo*(path: Path, x, y: float64) = + for v in [x, y]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + path.moveTo(Vector2D(x: x, y: y)) + +proc ensureSubpath(path: Path, x, y: float64) = + if path.needsNewSubpath: + path.moveTo(x, y) + path.needsNewSubpath = false + +proc closePath*(path: Path) = + let lsp = path.subpaths[^1] + if path.subpaths.len > 0 and (lsp.points.len > 0 or lsp.closed): + path.subpaths[^1].closed = true + path.addSubpathAt(path.subpaths[^1].points[0]) + +#TODO this is a hack, and breaks as soon as any draw command is issued +# between tempClosePath and tempOpenPath +proc tempClosePath*(path: Path) = + if path.subpaths.len > 0 and not path.subpaths[^1].closed: + path.subpaths[^1].closed = true + let lsp = path.subpaths[^1] + path.addSubpathAt(lsp.points[^1]) + path.addStraightSegment(lsp.points[0]) + path.tempClosed = true + +proc tempOpenPath*(path: Path) = + if path.tempClosed: + path.subpaths.setLen(path.subpaths.len - 1) + path.subpaths[^1].closed = false + path.tempClosed = false + +proc lineTo*(path: Path, x, y: float64) = + for v in [x, y]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + if path.subpaths.len == 0: + path.ensureSubpath(x, y) + else: + path.addStraightSegment(Vector2D(x: x, y: y)) + +proc quadraticCurveTo*(path: Path, cpx, cpy, x, y: float64) = + for v in [cpx, cpy, x, y]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + path.ensureSubpath(cpx, cpy) + let cp = Vector2D(x: cpx, y: cpy) + let p = Vector2D(x: x, y: y) + path.addQuadraticSegment(cp, p) + +proc bezierCurveTo*(path: Path, cp0x, cp0y, cp1x, cp1y, x, y: float64) = + for v in [cp0x, cp0y, cp1x, cp1y, x, y]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + path.ensureSubpath(cp0x, cp0y) + let cp0 = Vector2D(x: cp0x, y: cp0y) + let cp1 = Vector2D(x: cp1x, y: cp1y) + let p = Vector2D(x: x, y: y) + path.addBezierSegment(cp0, cp1, p) + +proc arcTo*(path: Path, x1, y1, x2, y2, radius: float64): bool = + for v in [x1, y1, x2, y2, radius]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + if radius < 0: + return false + path.ensureSubpath(x1, y1) + #TODO this should be transformed by the inverse of the transformation matrix + let v0 = path.subpaths[^1].points[^1] + let v1 = Vector2D(x: x1, y: y1) + let v2 = Vector2D(x: x2, y: y2) + if v0.x == x1 and v0.y == y1 or x1 == x2 and y1 == y2 or radius == 0: + path.addStraightSegment(v1) + elif collinear(v0, v1, v2): + path.addStraightSegment(v1) + else: + let pv0 = v0 - v1 + let pv2 = v2 - v1 + let tv0 = v1 + pv0 * radius * 2 / pv0.norm() + let tv2 = v1 + pv2 * radius * 2 / pv2.norm() + let q = -(pv0.x * tv0.x + pv0.y * tv0.y) + let p = -(pv2.x * tv2.x + pv2.y * tv2.y) + let cr = pv0.cross(pv2) + let origin = Vector2D( + x: (pv0.y * p - pv2.y * q) / cr, + y: (pv2.x * q - pv0.x * p) / cr + ) + path.addStraightSegment(tv0) + path.addArcSegment(origin, tv2, radius, true) #TODO always inner? + return true + +func resolveEllipsePoint(o: Vector2D, angle, radiusX, radiusY, + rotation: float64): Vector2D = + # Stolen from SerenityOS + let tanrel = tan(angle) + let tan2 = tanrel * tanrel + let ab = radiusX * radiusY + let a2 = radiusX * radiusX + let b2 = radiusY * radiusY + let sq = sqrt(b2 + a2 * tan2) + let sn = if cos(angle) >= 0: 1f64 else: -1f64 + let relx = ab / sq * sn + let rely = ab * tanrel / sq * sn + return Vector2D(x: relx, y: rely).rotate(rotation) + o + +proc arc*(path: Path, x, y, radius, startAngle, endAngle: float64, + counterclockwise: bool): bool = + for v in [x, y, radius, startAngle, endAngle]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + if radius < 0: + return false + let o = Vector2D(x: x, y: y) + var s = resolveEllipsePoint(o, startAngle, radius, radius, 0) + var e = resolveEllipsePoint(o, endAngle, radius, radius, 0) + if counterclockwise: + let tmp = s + e = s + s = tmp + if path.subpaths.len > 0: + path.addStraightSegment(s) + else: + path.moveTo(s) + path.addArcSegment(o, e, radius, abs(startAngle - endAngle) < PI) + return true + +proc ellipse*(path: Path, x, y, radiusX, radiusY, rotation, startAngle, + endAngle: float64, counterclockwise: bool): bool = + for v in [x, y, radiusX, radiusY, rotation, startAngle, endAngle]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + if radiusX < 0 or radiusY < 0: + return false + let o = Vector2D(x: x, y: y) + var s = resolveEllipsePoint(o, startAngle, radiusX, radiusY, rotation) + var e = resolveEllipsePoint(o, endAngle, radiusX, radiusY, rotation) + if counterclockwise: + let tmp = s + e = s + s = tmp + if path.subpaths.len > 0: + path.addStraightSegment(s) + else: + path.moveTo(s) + path.addEllipseSegment(o, e, radiusX, radiusY) + return true + +proc rect*(path: Path, x, y, w, h: float64) = + for v in [x, y, w, h]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + path.addSubpathAt(Vector2D(x: x, y: y)) + path.addStraightSegment(Vector2D(x: x + w, y: y)) + path.addStraightSegment(Vector2D(x: x + w, y: y + h)) + path.addStraightSegment(Vector2D(x: x, y: y + h)) + path.addStraightSegment(Vector2D(x: x, y: y)) + path.addSubpathAt(Vector2D(x: x, y: y)) + +proc roundRect*(path: Path, x, y, w, h, radii: float64) = + for v in [x, y, w, h]: + if classify(v) in {fcInf, fcNegInf, fcNan}: + return + #TODO implement + path.rect(x, y, w, h) # :P |