基于边分类的三维模型外轮廓线抽取算法

根据三维模型面片的方向性对边进行分类，筛选出轮廓边即共享可见面与不可见面的边，大幅度地排除那些不可能成为轮廓线的边，筛选过程只是一种比较运算。算法L利用外轮廓线的连通性递归搜索邻接的轮廓边得到若干闭合回路和分离的轮廓边，最终得到外轮廓线，并且自动决定的闭合回路方向和回路之间位置关系决定了回路是否属于外轮廓线；对那些精度不高而可能造成闭合回路搜索失败的三维模型，算法C利用遮挡关系由模型的前向面片对轮廓边进行裁剪得到三维模型的外轮廓线。用四叉树结构对模型投影区域进行划分，尽可能地排除那些不可能对轮廓边有遮挡关系的前向面片，减少裁剪的比较范围，降低算法的复杂度。本文的方法快速准确，适应各类二维流形模型。

Extracting Contour from 3D Model Based on Edge Classification

We sort edges of a 3D model into several classes in order to screen out silhouette edges which are those edges sharing a front- and a back-facing polygon. This process is comprised just with comparative calculations which can greatly exclude the edges that are impossible to be the part of contour. Algorithm L utilizes the connectivity of contour, by tracing one silhouette edge from neighbors, to find out all the edges of contour. This recursive process divides the silhouette edges into loops and separated edges, meanwhile both the directions of loops and the relationship between the loops confirm which loop are part of contour. Algorithm C is suitable for the coarse 3D model while Algorithm L fails to trace the accurate loops in some conditions. Algorithm C relies on the relationship between the position of the visible polygons of model and that of silhouette edges to clip the silhouette edges into contour. Quadtree is introduced to divide the region into sub-regions and exclude the outlying visible polygons. Quadtree can greatly decrease the amount of clipping operations and make the algorithm efficient enough.