扫描线填充梯形

我在3D视图中计算了2D地图可视位的四个角。 所以我知道可见的梯形,我想在地图上“访问”这些瓷砖。

所以我的algorithm基本上是一个凸多边形扫描线填充,具体有四点。

但是,我很难find简单的示例代码借用; 都想要应付复杂的凹多边形,并应用缠绕等,这在我的情况是不必要的,混乱。

我已经考虑坐下来写自己的简单的梯形扫描线填充执行从最初的原则,但想知道如果有人有一个经过testing的版本分享,我可以复制呢?

或者,也许我只是用错误的词汇search,网上有一些指向我?

由于梯形是由两个三角形组成的,所以可以将其分解并使用一些三角形的绘图代码,我相信你可以find很多的例子。

如果你想自己实现它,你所需要做的就是在这些点之间的梯形图的水平线的左侧和右侧迭代。 使用像Breshenam's这样的标准线条绘制algorithm来追踪两侧。 您可能还需要剪辑屏幕像素。

如果您绘制水平扫描线,凸多边形(包括四边形)垂直划分为如下部分…

  1. 顶部可能是一个三角形,水平底座。
  2. 一个(可能是空的)四边形序列,顶部和底部水平边缘。
  3. 底部可能是一个三角形,有一个水平的上边缘。

三角形可以被看作四边形,其中一个水平边恰好具有零长度,所以你真正需要担心的是四边形水平边的顶部和底部。

四边形的情况并没有太多的简化,你最多只需要绘制三个部分(不同扫描线上的四个角),但是这并没有多大帮助。

无论如何,当你从上到下扫描时,你总是会有一个下一个显着的扫描线,在这个扫描线上你会改变左边缘,右边缘,或者两者都有。 以下这些边缘可以用Bresenhams的变种来完成。 但请注意,每条扫描线的边缘移动多个像素是有效的 – 这不是您需要的标准Bresenhamsalgorithm。

您可能需要使用每条扫描线剪下顶部和底部的块,但剪切水平超出范围的东西的最简单方法是在绘制之前单独剪切扫描线 – 而不影响两个(左侧和右侧边缘)Bresenhams-algorithm状态。

通常,多边形的顶点以顺时针或逆时针顺序存储以支持可视性计算。 如果是这种情况,它也可以帮助这个“渲染”。 查看顶点列表为一个圆形数组“,查找最高顶点/顶点和最低顶点/顶点,左边顶点位于该圆形数组的一个跨度内,右边顶点位于另一个顶点。这些跨度是按照正确的顺序进行渲染的,而另一个则是以相反的顺序进行的。在开始之前制作左边缘和右边缘顶点列表可能更容易,而不是在圆形数组内工作,但是它应该不管那样困难。

这种事情在16位时代的3Dgraphics书籍中得到了很好的解释,但是在3D显卡成为常态的时候却被忽略了,原因很明显。

所以我实现了我自己的; 这里是python的原型:

class Pt: def __init__(self,x,y): self.x = x self.y = y def __repr__(self): return "(%s,%s)"%(self.x,self.y) class TrapeziumIterator: def __init__(self,map,width,height,a,b,c,d): # create an iterator over the cells in the map that are in the trapezium described by a,b,c,d corners # a,b,c,d describes the CLOCKWISE perimeter of the trapezium, eg tl,tr,br,bl from screenspace self.map = map self.width = width self.height = height # we re-orientate the trapezium so the lowest y is topmost t = [a,b,c,d] start_y = min(pt.y for pt in t) while t[0].y != start_y: t.append(t[0]) del t[0] self.t = t # work out starting position self.y = int(max(0,start_y)) # init y before x! self.x = self._start_x(self.y)-1 # x is iterated in the first call to next() # work out stopping positions self.stop_x = self._stop_x(self.y) self.stop_y = int(min(height,max(pt.y for pt in t)+1)) def next(self): "return True if there is a square to be visited; then the x and y variables member are set; else return False" self.x += 1 while self.x >= self.stop_x: self.y += 1 if self.y >= self.stop_y: return False # reached the end self.x = self._start_x(self.y) self.stop_x = self._stop_x(self.y) assert self.x >= 0 and self.x < self.width, self.x assert self.y >= 0 and self.y < self.height, self.y return True # you can read the x and y member variables def _start_x(self,y): # go down the left side return max(0,self._side(y,0,3)) def _stop_x(self,y): # go down the right side return min(self.width,self._side(y,3,0)+1) def _side(self,y,start,stop): inc = -1 if start < stop else 1 while self.t[stop].y < y: start = stop stop += inc f = (y - self.t[start].y) f /= (self.t[stop].y - self.t[start].y) return int(self.t[start].x + (self.t[stop].x - self.t[start].x) * f) def test(image,col,a,b,c,d): w,h = image.size it = TrapeziumIterator(image,w,h,a,b,c,d) while it.next(): image.putpixel((it.x,it.y),col) # test it import Image w,h = 100,100 image = Image.new("RGB",(w,h),(255,255,255)) test(image,(0,255,0),Pt(-60.3,-10.4),Pt(20.2,25.3),Pt(70,90.2),Pt(60,110)) test(image,(255,0,0),Pt(30.3,40.4),Pt(60.2,25.3),Pt(70,50.2),Pt(33,47.7)) # debug show it a bit larger image = image.resize((w*6,h*6)) image.show() 

四边形按照其顺时针顺序的四个角描述。 该algorithmfind最顶部的角落,然后沿着左侧和右侧走。