Sutherland–Hodgman算法

✍ dations ◷ 2025-10-29 04:38:49 #计算机图形学,算法

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

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

相关

  • .gp.gp为法国海外属地瓜德罗普国家及地区顶级域(ccTLD)的域名。A .ac .ad .ae .af .ag .ai .al .am .ao .aq .ar .as .at .au .aw .ax .az   B .ba .bb .bd .be .bf .bg .bh
  • 塔特姆爱德华·劳里·塔特姆(Edward Lawrie Tatum,1909年12月14日-1975年11月5日),美国遗传学家。他与乔治·韦尔斯·比德尔发现基因受到特定化学过程的调控而获得1958年诺贝尔生理学或
  • 氰酸铵氰酸铵是一种无机化合物,化学式为NH4OCN。它是无色固体。氰酸铵的结构通过X射线衍射表征。C−O键和C−N键的键长分别为1.174(8)和1.192(7) Å,与O=C=N-一致。NH4+和N(而不是O)形
  • 吴鸿麒日治台湾(1902-1945)吴鸿麒(1902年-1947年),是一位祖籍福建汀州龙岩、生于台湾中坜的客家籍人物。曾于台湾日治时期担任教师、律师,二战结束后任台湾台北地方法院民事庭及台湾高等
  • 方滨兴方滨兴(1960年7月17日-),中华人民共和国著名信息安全专家,中国工程院院士。曾任北京邮电大学校长,国家计算机网络与信息安全管理中心主任兼总工程师、信息产业部互联网应急处理协
  • 凯里学院凯里学院,为中国贵州省凯里市的一所全日制本科公立高等大学。该校全日制在校生10568人。占地面积1659亩,图书馆藏书57万册。设有17个教学分院(部),开设35个本科专业(方向)、26个专
  • 菲利普·斯塔辛斯基菲利普·斯塔辛斯基(波兰语:Filip Starzyński;1991年5月27日-)是一位波兰足球运动员。在场上的位置是攻击型中场。他现在效力于波兰足球甲级联赛球队罗切霍茹夫足球俱乐部。他也
  • 意大利足球甲级联赛最佳青年球员 意甲最佳青年球员(意大利语:Migliore calciatore giovane),是由意大利球员协会(AIC)颁发给每年度最优秀的意甲联赛年轻球员的奖项。该奖项获奖资格为未满24周岁的意甲球员
  • 由比光卫由比光卫(1860年11月27日-1925年9月18日),日本高知县人,大日本帝国陆军陆军大将。他是由比光索(土佐藩士)的长男。早年入土佐海南私塾,后来成为陆军士官学校幼年生。1882年12月,他于
  • 三井住友银行总部大楼三井住友银行总部大楼(日语:三井住友銀行本店ビルディング)是一座位于日本东京都千代田区丸之内的摩天大楼,由三井不动产所有。整栋大楼由三井住友银行租借使用。这座建筑也是三