我希望实现论文 "Antialiasing of Curves by Discrete Pre-filtering" by A.E. Fabris and A.R. Forrest. 中描述的贝塞尔曲线算法但是，我遗漏了一个核心难题:Corthout 和 Pol 的曲线点包含算法。 Raster Imaging and Digital Typography 一书中对此进行了概述。
我可以简单地遍历每个像素，计算到贝塞尔曲线的最短距离，然后用它来计算画笔的效果。然而，正如论文中提到的那样，这是一种低效的方法。
是否有点包含算法(或等效算法)的大纲或伪代码可以做同样的事情？
请您参考如下方法:
我要回答我自己的问题，因为我已经弄明白了。事实证明不需要点遏制，并且已经在论文中进行了概述。
这是在 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()
