Sutherland–Hodgman算法

✍ dations ◷ 2025-07-19 07:59:33 #计算机图形学,算法

Sutherland–Hodgman算法是裁剪多边形的算法。它通过轮流延长每个凸多边形的边,并且只选择在可见一侧的顶点来完成任务。

该算法从目标多边形中所有顶点的输入列表开始。接下来,剪裁多边形的一条边在两个方向上无限延伸,同时遍历目标多边形的边。如果输入列表中的顶点位于扩展的剪裁多边形线的可见侧,则它们会插入到输出列表中,并且目标多边形与剪裁多边形的延长后的边相交的顶点会添加到输出列表。

使用一个阶段的输出列表作为下一个阶段的输入列表,对每个剪辑多边形侧重复进行此过程。剪裁多边形的所有边都经过处理后,最终生成的顶点列表将定义一个完全可见的新单个多边形。请注意,如果目标多边形在剪裁多边形外部的顶点处凹入 ,则新多边形可能具有重叠的边缘——这对于渲染是可接受的,但不适用于其他应用程序,例如计算阴影。

给定一个剪裁多边形的一组边,和一个目标多边形的顶点列表,下面的过程将目标多边形根据剪裁多边形进行剪裁。

   List outputList = subjectPolygon;        for (Edge clipEdge in clipPolygon) do      List inputList = outputList;      outputList.clear();          for(int i = 0 ; i < inputList.count ; i += 1) do         Point current_point = inputList;         Point prev_point = inputList;             Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)             if (current_point inside clipEdge) then            if (prev_point not inside clipEdge) then               outputList.add(Intersecting_point);            end if            outputList.add(current_point);                  else if (prev_point inside clipEdge) then            outputList.add(Intersecting_point);         end if          done   done

当算法终止时,将在找到裁剪后多边形的顶点。请注意,如果它位于该边缘作为多边形的剩余部分的相同侧上的点被定义为边缘 。如果剪裁多边形的顶点始终沿逆时针方向列出,那么这等效于测试该点是否位于直线的左侧(left表示 ,right表示 ),这可以通过简单地使用叉积 实现。

是一个函数,为清楚起见在此省略了该函数,它返回线段和无限边的交点。请注意,仅在已知存在这种相交的情况下才调用它,因此可以简单地将两条线都视为无限长。

相关

  • 生物安全柜生物安全柜(英语:biosafety cabinet, biological safety cabinet,一般简称BSC),是生物安全实验室常见的重要设备,异于化学实验室内的通风柜(Fume Hood),或者是层流柜(Laminar flow ca
  • 气生根气生根(英语:Aerial root)是一部分植物的主要部分,用以在空气中吸收水汽,在热带雨林中十分普遍。 气根的分类有四种:
  • 韦特伦韦特伦(荷兰语:Wetteren)是位于比利时东佛兰德省部的一座城市,人口23,209人(2006年)。
  • 科技创新局中国人民解放军军徽中央军委科学技术委员会科技创新局,位于北京市,是中央军委科学技术委员会下属局,负责全军科技创新工作。在深化国防和军队改革中,2016年1月组建中央军委科学
  • 史密斯先生《史密斯先生》(英语:)是一部2007年美国动作喜剧片,由克里夫·欧文、莫妮卡·贝露琪、保罗·贾麦提主演,迈克尔·戴维斯编导,于2007年11月2日发行,这部电影以高超的对战与神准的用
  • 天主教立陶宛军中教长区天主教立陶宛军中教长区(拉丁语:Ordinariatus Militaris Lituaniae、立陶宛语:Lietuvos kariuomenes ordinariatas)是立陶宛一个罗马天主教军中教长区,直属圣座,负责牧养信奉天主
  • 盎司盎司(英语:ounce;符号:oz),或作盎斯,港译“安士”或“盎士”,为英制质量、重量或体积的单位,旧称英两或唡。1盎司力(Ounce-force)等于1⁄16磅力或0.2780139牛顿。液盎司(Fluid ounce,又称
  • MAMAMOO影视作品列表《MAMAMOO影视作品列表》主要列举韩国女子音乐组合MAMAMOO历年参与之各类电视节目、固定节目、电视剧及音乐录影带演出。
  • Heroine (单曲)《Heroine》(韩语:주인공;中文:主人公)为韩国歌手善美的一首单曲,此单曲由MakeUS娱乐在2018年1月18日发行。1月18日,善美在首尔江南区举办新曲记者会,善美在记者会中表示此次作品为
  • 隅岛隅岛(朝鲜语:우도/隅島  */?)是大韩民国西部海域中的一座岛屿,是西海五岛之一,行政区域上属于仁川广域市江华郡西岛面管辖。隅岛面积有0.21平方公里,在延坪岛以东25公里、北方界