Sutherland–Hodgman算法

✍ dations ◷ 2025-09-18 10:23:42 #计算机图形学,算法

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

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

相关

  • 遗传多样性遗传多样性又称为基因多样性(英语:genetic diversity)。同种个体间因为其生活环境的不同,经历长时间的天择、突变所产生的结果。如果遗传多样性越高,则族群中可提供环境天择的基
  • 幺米本页米 (又称米) 为单位,按长度大小列出一些例子,以帮助理解不同长度的概念。
  • 老挝中央银行坐标:17°57′57″N 102°36′25″E / 17.965772°N 102.607003°E / 17.965772; 102.607003老挝人民民主共和国银行(老挝语:ທະນາຄານ ແຫ່ງ ສ.ປ.ປ.ລາວ;英语:Bank
  • 德国元帅以下是获授德国陆军元帅(德语:Generalfeldmarschall)军衔的军官和王室成员的列表。
  • 西泠印社坐标:30°15′11″N 120°08′07″E / 30.25306°N 120.13528°E / 30.25306; 120.13528西泠印社(泠,音灵),位于中国浙江省杭州市西湖孤山西南麓,是中国研究金石篆刻的一个百年学
  • 巧克力布朗尼巧克力布朗尼(英语:Chocolate brownie)又称为布朗尼、波士顿布朗尼,是一种体积较小、味道浓厚、形状酷似饼干的巧克力蛋糕。布朗尼因其巧克力色的外表而得名(布朗尼与英文当中的
  • 穆罕默德·伊本·卡西木穆罕默德·伊本·卡西木(阿拉伯语:محمد بن القاسم الثقفي‎;695年12月31日-715年7月18日)倭马亚王朝将军。生于塔伊夫,并在该城长大。其父卡西木·伊本·优素福
  • 漂砾漂砾(erratic)是和周边石料相比形状和材质截然不同的天然石块,小则数厘米,大可达数米甚至数十米。其成因是冰川的活动,故又称冰川漂砾(英语:glacial erratic)。冰川的搬运能力相当强
  • 威廉·史威特威廉·史威特(英语:William Sweet),加拿大哲学家,曾任加拿大哲学学会主席。史威特曾在加拿大、法国和德国学习政治学、神学和哲学。他在巴黎大学政治学院取得政治学硕士学位,在渥
  • 广岛烧广岛烧(日语:ひろしまやき),是御好烧的一个种类,主要流行于日本广岛地区。但是广岛地方并没有将其称呼为“広岛焼き”。基本材料有小麦粉(薄力粉)、水、猪肉、鸡蛋、荞麦面、葱、酱