| 摘要 |
A method for filling the space between two neighboring polyline ribs is disclosed. The method, called ladder triangulation, likens two ribs, which generally outline a complex structure, to the two rails of a ladder. The ladder triangulation is built by adding rungs, each rung connecting a node on one rib to a node on the other rib and thereby (after the first rung) creating one more triangle. In essence the first rung connects node 1 of polyline 1 to node 1 of polyline 2, and the second rung connects either node 1 polyline 1 to node 2 polyline 2 or else node 1 polyline 2 to node 2 polyline 1, whichever rung is shorter. There are (n1+n2)/2 such rungs where n1 and n2 are the respective node counts of the two polylines, and computation is linear with node count. Where there are multiple polylines, the same process is repeated between polylines 2 and 3, 3 and 4, etc. and may also be repeated between the last polyline and the first one (cyclic rib fill). The entire set of ribs is filled in time proportional to the total node count. Moreover, if a single rib is subsequently modified by an editing process, a triangulation can be updated rapidly by recomputation of just the two ladder triangulations involving that rib.
|
