对于一个给定的三角形，是否需要对屏幕上所有的像素点都做一次判断？
很容易想到的一个办法是：只对三角形所在包围盒里的所有像素点做判断。这样可以减少很多无用的计算。
下图展示了常见的一些遍历方法。
着重介绍下上图中左下角所示的遍历方式：逐TILE遍历。
TILE是nxn个像素组成的像素块，如果某个TILE的四个角所在的像素点都在三角形外，则可以判定这个TILE中所有像素点都在三角形外。这样做的好处很明显：减少了计算量。
那这个TILE划分多大合适呢？
假设现有一个包围盒大小为64x64的三角形。有一种做法是：
- TILE大小设置为32x32。如果某个TILE的四个角像素有一个或者多个在三角形内部，则继续2；否则丢弃该TILE。
- TILE大小设置为16x16。如果某个TILE的四个角像素有一个或者多个在三角形内部，则继续3；否则丢弃该TILE。
- TILE大小设置为 8x8 。如果某个TILE的四个角像素有一个或者多个在三角形内部，则继续4；否则丢弃该TILE。
- TILE大小设置为 4x4 。如果某个TILE的四个角像素有一个或者多个在三角形内部，则继续5；否则丢弃该TILE。
- TILE大小设置为 2x2 。此时与逐像素判断效果相同。
网友评论