Graphics Reference
In-Depth Information
problem. To use our algorithm to triangulate trimmed surfaces one would first have
to use some other algorithm to represent the trimming curves in parameter space as
a suitable collection of closed polygonal curves. Additional criteria would have to be
used to determine if the triangulation is fine enough. It should also be noted before-
hand that since our trapezoidation algorithm does not concern itself with the para-
meterization of the trimmed surface, the induced triangulation of the surface may
contain very thin triangles, so that extra work would have to be done to avoid that.
Nevertheless it leads to a quick-and-dirty algorithm for displaying trimmed surfaces
and we shall describe the algorithm with that application in mind. (We should
mention the algorithm in [ZalC99] that seems to be based on similar ideas; however,
the author has used the algorithm we are about to describe for a number of years
even though it was never published until now.)
Our trapezoidation algorithm is based on an idea from Vatti's clipping algorithm
([Vatt92]) that we described in Section 3.3.5. Recall that the central idea of his algo-
rithm is to define polygons in terms of left and right bounds and then to obtain the
final clipped regions using a fairly standard scan line approach with active edge lists.
This idea of polygon bounds can also be used effectively to generate a trapezoidal
decomposition of a polygonal region. The domain can be quite general for our
algorithm. It may have holes or consist of more than one component.
The main task will be to show how to subdivide a given polygonal region into trape-
zoids using the left and right bounds of the bounding curves for the polygons of the
region. (Trapezoids in this discussion will include the “degenerate” case of triangles.)
Because of the application to trimmed surfaces, we also give an algorithm for subdi-
viding a trapezoid appropriately for a wireframe display of the parametric surface
defined on it. This would also apply to a z-buffer type display algorithm. The complete
details for an algorithm that displays trimmed parameterized surfaces (above and
beyond what is discussed here) depend on the type of display that is desired. As an
example of one approach for shaded surfaces using a z-buffer algorithm see [RoHD89]
but replace the regions that are used there with the trapezoids from here.
The discussion in this section will depend heavily on what was done in Section
3.3.5. To be able to handle our regions we can use a simplified version of the algo-
rithm described in Section 3.3.5. Major simplifications arise from the fact that,
although the region may consist of more than one polygon, none intersect here. On
the other hand, we shall need to worry about “knots,” so that the data structures will
be modified slightly to fit our current needs. We shall concentrate the discussion on
those aspects that are different from those in Section 3.3.5. Like in that section
we shall only sketch the main ideas. A more thorough discussion can be found in the
document VattiTrim on the accompanying CD.
Given our planar region, first determine the left and right bounds of the polygons
making up the region and store this information in a local minima list (LML) as
before. Next, compute the trapezoidal decomposition of the region from the LML by
scanning the region from the bottom to the top using scan beams whose y-values are
kept in a scan beam list (SBL). Recall that the values for this list are not generated
all at once. We start with the list of all the local y-minima of the polygon boundaries
and the y-values of the top endpoint of the edges that start at the local minima and
then add to the list incrementally on an edge by edge basis. As we scan the world one
scan beam at a time, an active edge list (AEL) lists all the edges intersecting the current
scan beam just like in Section 3.3.5.
