Sutherland–Hodgman算法

✍ dations ◷ 2025-07-07 08:52:35 #计算机图形学,算法

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表示 ),这可以通过简单地使用叉积 实现。

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

相关

  • 亚特兰蒂斯亚特兰蒂斯(希腊语:Ἀτλαντὶς νῆσος,英语:Atlantis,法语:Atlantide,意为“阿特拉斯的岛屿”),又译阿特兰蒂(提)斯,意译大西洋岛、大西国、大西洲,传说中拥有高度文明发展的古
  • 子房子房是被子植物生长种子的器官,位置不定,依和雌蕊的相对位置可分为上位花、下位花或是周位花。一般略为膨大。子房里面有一至多室,每室内含有一至多个胚珠,胚珠受精后可以发育为
  • 四烯甲萘醌维他命K2(四烯甲萘醌)为一群相似的化合物,可分为短链四烯甲萘醌(如MK-4)和长链四烯甲萘醌(如MK-7、MK-8、MK-9)。维生素K2未有已知的毒性,因维生素K不会在肝脏中过量残留。维生素K皆
  • 人夫人妻(日文汉字又可写成他妻)即“人家的妻子”或“人家的老婆”。而“人家的丈夫”则称为人夫。在古汉语,人妻是指已婚妇女。而在现代日本用语中则通常为丈夫除外其他人对该妇女
  • 马山港坐标:35°11′N 128°33′E / 35.183°N 128.550°E / 35.183; 128.550马山市(韩语:마산시),曾经是大韩民国庆尚南道南部的一个城市,约在釜山以西35公里。古名合浦,元世祖忽必列曾
  • 黄文魁黄文魁(1928年12月1日-1982年12月24日),福建莆田人,中国有机化学家。早年就读于莆田第一中学和上海交通大学化学系。曾任教于交通大学、复旦大学,后成为兰州大学教授和有机化学研
  • 长项栈桥站长项栈桥站(朝鲜语:장항잔교역/長項棧橋驛  */?)曾为韩国铁路长项货物线上的一个车站,位于忠清南道舒川郡长项邑,已于1938年废止。
  • 对氨基苯膦酸对氨基苯膦酸又称4-氨基苯膦酸,是一种有机磷化合物,分子式为C6H8NO3P。对氨基苯膦酸可由对溴苯膦酸在氧化亚铜的存在下和氨水反应得到。
  • 服部让次服部让次(日语:服部譲次)是出生于名古屋市的航空工程师。服部让次在1918年从东京大学毕业后,进入三菱造船就职、并分派到神户一带的造船厂。1923年服部让次升任为名古屋飞机制作
  • 乐高漫威超级英雄《乐高 漫威超级英雄》(英语:LEGO Marvel Super Heroes,港台译作“乐高:惊奇超级英雄”)是一款由TT Games工作室开发并将由华纳兄弟互动娱乐发售在全平台上的乐高题材和美国漫画