我的后记解释器当前实现了Hodgeman-Sutherland限幅算法,但这仅限于更简单的形状,并且没有提供利用各种绕数规则的规定。因此,这对我实现奇数填充或处理复杂的自相交形状没有帮助。
Weiler-Atherton算法有望提供所有这些功能,但是每次我坐下来使用它时,我都会热衷于实现基本结构。具体来说,它要求在节点之间建立双向关联,然后可以在任一方向上遍历它们。但是,您该怎么做?
如果我用Postscript(或任何基于动态对象的语言)将我的路径列表实现为点数组,则这些点本身将实现为坐标数组,我列出了索引对,并进行线性搜索以进行遍历?或者我可以使用关联数组进行映射,并且同时添加(node1-> node2)和(node2-> node1)是否足够?
或者如果路径位于链接中怎么办-用类似C的语言列出,并带有指向下一个顶点的指针和一个指定末尾的NULL指针,您是否只需向节点添加更多链接(指针)?
您不需要寻址全部我在这里的问题足以描述为任何一种语言(不一定是Postscript或C)构建此数据结构的策略,并且我应该能够将其应用于我的特定情况,该情况通常是Postscript的原型并进行翻译到C,以提高速度。
评论
欢迎来到Computer Graphics.SE,很高兴看到熟悉的面孔,相信您将对我们的小型社区非常有用。抱歉,我无法回答您的问题。抱歉,但是您打算做什么却让我有些困惑。您是否要编写一个“任意多边形”填充例程,例如也要剪辑到查看矩形的侧面?
@SimonF抱歉,直到现在我才注意到您的评论。我正在尝试为复杂的自相交形状和复杂的自相交裁剪区域实现完全概括的裁剪例程,并使用绕数规则进行参数化。但是,如果我可以用具体的术语可视化数据结构,通常可以使我动起来。
如果您已经解决了“未修剪”的任意多边形的填充问题,则“仅”需要使用交集(即AND)运算符进行CSG,然后将其裁剪到另一个树桩上。聚。那有意义吗?在屏幕/扫描线空间中,CSG相对容易。 OTOH如果您需要矢量模型,在我看来,可以扩展扫描线模型,以便为描述以下各项的每个构造梯形集(mathworld.wolfram.com/Trapezium.html-英国定义(即正确的def))。内饰。将它们相交以生成最终模型应该相对容易。
碰巧的是,我最近才用C ++实现了这种算法,而且实际上并不那么困难,我发现比Wikipedia上的解释更好的简短解释。我将看看能否提出一个伪代码答案,希望能解决您的问题。但是话又说回来,我还拥有一个多边形作为三角形的奢侈。