请问一下三角形扫描线算法

lexchou

我打算尝试自己做一个软3D渲染引擎。已经做了一个星期了，在多边型光栅化为了偷懒只写了画线框三角形。现在其他基本上都做完了，随手写了一个三角形扫描线算法。
思路是这样的，将一个三角形三个顶点根据y排序后选择中间的顶点并做平行于x轴的直线交对面的边与一点，这两点将三角形分割成两个三角形，然后来通过计算每个三角形每一条边上根据y的两个x值，通过扫描线段填充来画出整个三角形


不过随手写的用的点斜式来确定扫描线边界，这个效率啊……用这个三角形算法和线框比起来，速度相差3个数量级……而直线的算法我只知道点斜式以及Bresenham……但是Bresenham的中点线算法用在这里则过于复杂了。

不知道大家有什么好一点的三角形光栅化算法呢？

AndersonX

具体可参考《3d游戏编程大师技巧一书》。我已经实现了一个软件3d引擎，不过是基于gdi，里面就用到了该书里讲到的光栅算法，也是分成上下两个三角形。呵呵，内容太多你还是看书上怎么说的吧。

lexchou

那个代码太长了……我还是就用原来的吧，改进一下速度也能提上去

raven

软件scanline引擎？目前软件的还是raytracer多，scanline的资料太少了。

不知道RenderMan的资料怎么样

AndersonX

呵呵，建议使用一下intel c++编译器和vc6的profile。在我的引擎里只是使用intel c重新编译了一下，cpu占用率就由原来的90％降到了50％（而剩下的50％基本上都是gdi的开销），然后再用profile查看那个函数开销大，再对它进行优化，速度就能提上了。