python - Antialiasing of Curves by Discrete Pre-filtering -
i'm looking implement bezier curve algorithm described in paper "antialiasing of curves discrete pre-filtering" a.e. fabris , a.r. forrest. i'm missing core piece of puzzle: point containment algorithm curves corthout , pol. it's outlined in book raster imaging , digital typography.
i iterate on every pixel, calculate shortest distance bezier, , use calculate effect of brush. mentioned in paper it's inefficient approach.
is there outline or pseudo code point containment algorithm (or equivalent) same thing?
i'm going answer own question seeing i've figured out. turns out point containment isn't needed, , outlined in paper.
here's implementation in python , wxwidgets, rendering few curves using box brush.
sadly it's slow practical use, after rewriting in c , making several optimisations. best 30ms per bezier, , rendering picture of 100 curves took 3 seconds. other vector applications tend use path based bezier rendering algorithms i'll exploring now.
#!/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 # divide each pixel 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 paper, control vertices need performed @ # higher precision discrete space allow 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) # each pixel in image x in xrange(xstart, xend): 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 stroke h = 0 n = numberofbrushes - 1 in range(n,-1,-1): if mstroke.stroke(stackofbrushes[i]) == quadbezier.covered: h = else: if h == 0: return quadbezier.not_covered, 0 return quadbezier.covered, h return quadbezier.covered, h def basecase(self): """ returns true if curve primitive, length of curve <= 1 of 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 , mx <= distance: if > -distance , <= 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 in xrange(6): yplus = * 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 undocumented native pixel data because 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() x in xrange(width): 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 discrete pre-filtering') frame.show(true) return true app = myapp(0) app.mainloop()
Comments
Post a Comment