python - 通过离散预滤波消除曲线锯齿

Question

我希望实现论文 "Antialiasing of Curves by Discrete Pre-filtering" by A.E. Fabris and A.R. Forrest. 中描述的贝塞尔曲线算法但是，我遗漏了一个核心难题:Corthout 和 Pol 的曲线点包含算法。 Raster Imaging and Digital Typography 一书中对此进行了概述。

我可以简单地遍历每个像素，计算到贝塞尔曲线的最短距离，然后用它来计算画笔的效果。然而，正如论文中提到的那样，这是一种低效的方法。

是否有点包含算法(或等效算法)的大纲或伪代码可以做同样的事情？

Answer 1

我要回答我自己的问题，因为我已经弄明白了。事实证明不需要点遏制，并且已经在论文中进行了概述。

这是在 python 和 wxwidgets 中的实现，使用方框画笔绘制了一些曲线。

遗憾的是，即使在用 C 语言重写并进行多项优化之后，它的实际使用速度也太慢了。我能得到的最好结果是每个贝塞尔曲线大约 30 毫秒，渲染 100 条曲线的图片需要 3 秒。大多数其他矢量应用程序倾向于使用基于路径的贝塞尔渲染算法，这正是我现在要探索的。

#!/usr/bin/python
# test15.py

import wx
import math
import cProfile

class Brush(object):
    def __init__(self, size):
        self._brushsize = size
        self.__halfbrush = self._brushsize / 2
    # returns true if inside or touching box
    def insidebox(self, box):
        minp = box[0]
        maxp = box[1]
        if maxp.x < -self.__halfbrush:
            return False
        if minp.x > self.__halfbrush:
            return False
        if maxp.y < -self.__halfbrush:
            return False
        if minp.y > self.__halfbrush:
            return False
        return True

    def at(self, p):
        px = p.x * p.x # 0.027
        py = p.y * p.y 
        d = math.sqrt(px + py)
        return  d < self.__halfbrush


    def getSize(self):
        return self._brushsize

class BezierPoint(object):
    SCALEFACTOR = 4 # we divide each pixel into 4x4 matrix

    @classmethod
    def newRealPoint(nbs, x,y):
        x=int(x*BezierPoint.SCALEFACTOR)
        y=int(y*BezierPoint.SCALEFACTOR)
        return BezierPoint(x,y)

    def __init__(self,x,y):
        self.x=int(x)
        self.y=int(y)

    def __str__(self):
        return  self.x+ 'x' + self.y

#recalls = 0

class QuadBezier(object): # cubic bezier
    COVERED = 0x01
    NOT_COVERED = 0x02

    @classmethod
    def newRealPoint(nbs, x1,y1,x2,y2,x3,y3,x4,y4):
        b = QuadBezier(x1,y1,x2,y2,x3,y3,x4,y4)
        b.p1 = BezierPoint.newRealPoint( x1, y1)
        b.p2 = BezierPoint.newRealPoint( x2, y2)
        b.p3 = BezierPoint.newRealPoint( x3, y3)
        b.p4 = BezierPoint.newRealPoint( x4, y4)
        b._minx = min(b.p1.x,b.p2.x,b.p3.x,b.p4.x)
        b._maxx = max(b.p1.x,b.p2.x,b.p3.x,b.p4.x)
        b._miny = min(b.p1.y,b.p2.y,b.p3.y,b.p4.y)
        b._maxy = max(b.p1.y,b.p2.y,b.p3.y,b.p4.y)
        return b

    def __init__(self,x1,y1,x2,y2,x3,y3,x4,y4):
        self.p1 = BezierPoint(x1,y1)
        self.p2 = BezierPoint(x2,y2)
        self.p3 = BezierPoint(x3,y3)
        self.p4 = BezierPoint(x4,y4)
        self._minx = min(x1,x2,x3,x4)
        self._maxx = max(x1,x2,x3,x4)
        self._miny = min(y1,y2,y3,y4)
        self._maxy = max(y1,y2,y3,y4)

    def __str__(self):
        s = 'p1 = ' + str(self.p1.x) +'x'+ str(self.p1.y) +' p2 = '+str(self.p2.x) +'x'+str(self.p2.y)
        s = s + ' p3 = ' + str(self.p3.x) +'x'+ str(self.p3.y) +' p4 = '+str(self.p4.x) +'x'+str(self.p4.y)
        return  s

    def subdivide(self, left=True):
        # http://antigrain.com/research/adaptive_bezier/
        # according to the paper, we control vertices need to be performed at
        # higher precision than the discrete space will allow to for any accuracy loss 
        x1 = self.p1.x << 2 
        x2 = self.p2.x << 2 
        x3 = self.p3.x << 2
        x4 = self.p4.x << 2
        y1 = self.p1.y << 2
        y2 = self.p2.y << 2
        y3 = self.p3.y << 2
        y4 = self.p4.y << 2
        x12   = (x1 + x2) >> 1
        y12   = (y1 + y2) >> 1
        x23   = (x2 + x3) >> 1
        y23   = (y2 + y3) >> 1
        x34   = (x3 + x4) >> 1
        y34   = (y3 + y4) >> 1
        x123  = (x12 + x23) >> 1
        y123  = (y12 + y23) >> 1
        x234  = (x23 + x34) >> 1
        y234  = (y23 + y34) >> 1
        x1234 = (x123 + x234) >> 1
        y1234 = (y123 + y234) >> 1

        if left:
            return QuadBezier(x1 >> 2, y1 >> 2, x12 >> 2, y12 >> 2, x123 >> 2, y123 >> 2, x1234 >> 2, y1234 >> 2)
        return QuadBezier(x1234 >> 2, y1234 >> 2, x234 >> 2, y234 >> 2, x34 >> 2, y34 >> 2, x4 >> 2, y4 >> 2)

    def getboundingbox(self):
        return BezierPoint(self._minx,self._miny), BezierPoint(self._maxx,self._maxy)


    def area (self):
        m1,m2 = self.getboundingbox()
        return m2.x-m1.x, m2.y-m1.y

    def minus (self, p):
        px = p.x 
        py = p.y 
        return QuadBezier(self.p1.x - px, self.p1.y - py, 
                          self.p2.x - px, self.p2.y - py, 
                          self.p3.x - px, self.p3.y - py, 
                          self.p4.x - px, self.p4.y - py)


    def draw(self, img,pd, stackofbrushes):
        mmin,mmax = self.getboundingbox()
        numberofbrushes = len(stackofbrushes)
        largestbrushsize = stackofbrushes[numberofbrushes-1].getSize()
        print 'largestbrushsize = ', largestbrushsize
        xstart,xend = int(math.floor(mmin.x/BezierPoint.SCALEFACTOR-largestbrushsize)), int(math.ceil(mmax.x/BezierPoint.SCALEFACTOR+largestbrushsize))
        ystart,yend = int(math.floor(mmin.y/BezierPoint.SCALEFACTOR-largestbrushsize)), int(math.ceil(mmax.y/BezierPoint.SCALEFACTOR+largestbrushsize))
        print (xend - xstart) * 4, (yend - ystart) * 4, ' total area = ', ((xend - xstart) * 4) * ((yend - ystart) * 4)
        # for each pixel in the image
        for x in xrange(xstart, xend):
            for y in xrange(ystart, yend):
                pixel = BezierPoint(x*BezierPoint.SCALEFACTOR+2,y*BezierPoint.SCALEFACTOR+2) # todo: fix me
                covered, height = self.antialisedDilate(stackofbrushes, pixel, numberofbrushes)
                if covered == QuadBezier.COVERED:
                    img.MoveTo(pd,x,y)
                    #print height
                    img.Set(41*height,41*height,41*height)

    def antialisedDilate(self, stackofbrushes, p, numberofbrushes):
        mstroke = self.minus(p)  # centre the stroke
        h = 0
        n = numberofbrushes - 1
        for i in range(n,-1,-1):
            if mstroke.stroke(stackofbrushes[i]) == QuadBezier.COVERED:
                h = i
            else:
                if h == 0:
                    return QuadBezier.NOT_COVERED, 0
                return QuadBezier.COVERED, h
        return QuadBezier.COVERED, h

    def baseCase(self):
        """ returns true if the curve is primitive, that is that the length of the curve is <= 1 of the discrete space selected 
        """
        p1,p2 = self.getboundingbox()
        mx,my = p2.x-p1.x, p2.y-p1.y
        #print mx,my
        distance = 2
        if mx >= -distance and mx <= distance:
            if my > -distance and my <= distance:
                return True
        return False

    def stroke(self, b):
        """ http://pdf.aminer.org/000/593/297/antialiasing_of_curves_by_discrete_pre_filtering.pdf
        """
        # NotInDilatedBBox
        if not b.insidebox(self.getboundingbox()):
            return QuadBezier.NOT_COVERED
        if self.baseCase():
            return QuadBezier.NOT_COVERED
        if b.at(self.p1):
            return QuadBezier.COVERED
        if b.at(self.p4):
            return QuadBezier.COVERED

        left = self.subdivide(True)
        if (left.stroke(b)==QuadBezier.COVERED):
            return QuadBezier.COVERED
        right = self.subdivide(False)
        if (right.stroke(b)==QuadBezier.COVERED):
            return QuadBezier.COVERED

        return QuadBezier.NOT_COVERED


pd = None
pixels = None
def timer ():
    stackofbrushes = [Brush(6.0), Brush(7.0), Brush(9.0), Brush(11.0), Brush(13.0), Brush(15.0)] # largest last

    for i in xrange(6):
        yplus = i * 20
        bezier = QuadBezier.newRealPoint(40.0,50.0+yplus, 80.0,46.0+yplus, 120.0,46.0+yplus, 160.0,50.0+yplus)
        bezier.draw(pixels, pd, stackofbrushes)


class MyToolBar(wx.Frame):
    def __init__(self, parent, id, title):
        wx.Frame.__init__(self, parent, id, title, wx.DefaultPosition, wx.Size(700, 700))
        self.Centre()

        self.Bind(wx.EVT_TOOL, self.OnExit, id=4)
        bmp = wx.EmptyBitmap(700,700)
        # we're using the undocumented native pixel data because the memorydx object introduces artifacts on MacOS
        global pd
        global pixels

        pd = wx.NativePixelData(bmp, wx.Point(0,0), wx.Size(700,700))
        width,height = pd.GetWidth(), pd.GetHeight()
        pixels = pd.GetPixels()
        for x in xrange(width):
            for y in xrange(height):
                pixels.MoveTo(pd,x,y)
                pixels.Set(255,255,255)

        cProfile.run('timer()')

        wx.StaticBitmap(self, wx.ID_ANY, bmp)

    def OnExit(self, event):
        self.Close()

class MyApp(wx.App):
    def OnInit(self):
        frame = MyToolBar(None, -1, 'Antialiasing of Curves by Discrete Pre-filtering')
        frame.Show(True)
        return True

app = MyApp(0)
app.MainLoop()