Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2002-02-22
2004-11-09
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S670000, C345S671000, C345S472000, C345S472100, C345S472200
Reexamination Certificate
active
06816170
ABSTRACT:
TECHNICAL FIELD
The present invention relates in general to systems and methods for representing polygons and determining the result of a resizing operation performed on a polygon, and more specifically to a system and method for accurately and efficiently computing a simple polygon (i.e., non-self-intersecting polygon) that results from a resizing operation performed on an original simple polygon.
BACKGROUND OF THE INVENTION
Polygons are commonly utilized in a wide range of applications. For instance, polygons are often used in computer graphics. For example, computer-executable design applications often utilize polygons in defining a particular design (or layout). For instance, computer-executable applications for designing circuit layout, micro-mechanical device layout, and/or micro-electromechanical system (MEMS) layout, as examples, commonly use polygons in representing such layouts. Other example applications of polygons include uses in design and/or manufacturing in, for instance, generation of architectural designs of buildings, generation of representation of geographical terrain, generation of ornamental patterns for numerical control of sewing machines in the textile industry, numerical control of milling machines in the car body industry, mould design, design of solid fuel combustion chambers, the propagation of travelling shock waves, and obstacle avoidance problems of robotics. See e.g., Pham, B., “Offset curves and surfaces: a brief survey,” Computer Aided Design 24, pp. 223-229, 1992.
Many applications utilize “simple polygons,” which as used herein refers to polygons that are non-self-intersecting (but which may include holes therein). That is, a simple polygon is a polygon that does not intersect with itself (i.e., does not include edges that intersect each other). It should be noted that self-intersecting polygons can be decomposed into simple polygons. Thus, applications that include self-intersecting polygons may use simple polygons for representing the self-intersecting polygons and/or for manipulating the polygons (e.g., resizing the polygons).
Once a polygon is defined, it is often desired to resize it. That is, it is often desired to have the edges of the polygon moved outward (by a particular offset amount) to enlarge the polygon or moved inward (by a particular inset amount) to decrease the size of the polygon. Offsetting a polygon involves moving its boundary outward a particular distance (e.g., which is typically some user-specified distance in most applications) in a direction normal to the polygon's boundary. Insetting moves the edges into the polygon. Resizing of a polygon (i.e., offsetting or insetting of the polygon) is a primitive operation that is required in a variety of applications, such as the example applications identified above. Resizing (e.g., offsetting or insetting) a polygon is sometimes referred to as polygon growth or polygon envelope.
As is well known in the art, various problems may be encountered when resizing a simple polygon. For instance, when resizing a polygon, any of several different types of events (which may be referred to herein as “resizing events” or as “critical events”) may be encountered. More specifically, the geometry of a polygon may change significantly when an offset or inset operation is performed. One event that may be encountered is referred to herein as a “self-intersection” event in which a simple polygon intersects with itself as a result of a resizing operation. Another event that may be encountered is referred to herein as an “edge-collapse” event in which an edge of the polygon effectively disappears as a result of a resizing operation. That is, the two vertices of an edge may become one as a result of a resizing operation, thereby causing such edge to effectively disappear. Another event that may be encountered is referred to herein a “polygon-split” event in which the polygon is effectively split into two (or more) separate polygons as a result of a resizing operation. Accordingly, it becomes desirable to have an algorithm for resizing polygons that robustly and efficiently handles such events that may be encountered during a resizing operation to accurately determine the polygon that results from such resizing operation.
The above events have been recognized in the prior art as events that need to be accounted for when performing resizing operations on a polygon. Various techniques for handling such events have been proposed in the prior art. As one example, a common approach for addressing the problems associated with offsetting a simple polygon is described by Tiller, W. and Hanson, H.G., “Offsets of two-dimensional profiles,” IEEE Computer Graphics and Applications 5, pp. 36-46, 1984. In this approach, a local offset of each edge of the polygon is performed first (i.e., every edge is moved a user-specified distance), and then an attempt is made to eliminate self-intersections and loops produced in the resulting polygon. That is, the local offsetting may lead to self-intersections and/or loops in the resulting offset polygon, and the ones of such self-intersections and/or loops that are “not needed” are discarded. The process of identifying the loops that are “not needed” is heuristic and is not guaranteed to work for all inputs. Accordingly, this procedure is heuristic in nature and does not provide a robust solution for resizing polygons.
More robust algorithms for performing resizing operations on a polygon have been proposed in the prior art that utilize the “straight skeleton” (which may also be referred to as the “lineal axis”) of the polygon in performing the resizing operation in order to handle one or more of the above-identified types of resizing events that may be encountered. That is, robust polygon resizing techniques of the prior art require first computing the straight skeleton of the polygon being resized. In general, the straight skeleton of a simple polygon is defined by shrinking the polygon by translating each of its edges at a fixed rate, keeping sharp corners at the reflex vertices, and monitoring where the vertices go. The straight skeleton is quite similar to the medial axis. In fact, the two are equivalent for convex polygons. However, the straight skeleton of a non-convex polygon has fewer edges than the medial axis, and all of its edges are line segments (the medial axis also has parabolic arcs around each reflex vertex). Computing the straight skeleton of a polygon is further described by Petr Felkel and Stepan Obdrzalek in “Straight Skeleton Implementation,” Proceedings of Spring Conference on Computer Graphics, Budmerice, Slovakia, ISBN 80-223-0837-4, pp. 210-218, 1998, and by Letlibe Phahlamohlaka in “Offset Problems for Polygons,” Masters thesis, Dept. of Mathematics, Statistics and Computer Science, Dalhousie University, Canada, 1991.
Once the straight skeleton data structure of a polygon has been computed, one can easily compute the insetted polygon. That is, the straight skeleton, by definition, detects all events when the polygon is inset. I am unaware of any teaching in the prior art of extending the straight skeleton algorithm to detect events that occur during an offset operation. Also, the straight skeleton provides a solution for edge-collapse and polygon-split events, but further computation is still required to generate a correct result when a self-intersection event is encountered.
As described further below, the robust resizing techniques of the prior art that require computation of the straight skeleton of a polygon are computationally expensive. In the case of convex polygons, resizing events can be determined by determining the medial axis of the polygon being resized. See Letlibe Phahlamohlaka, “Offset Problems for Polygons,” Masters thesis, Dept. of Mathematics, Statistics and Computer Science, Dalhousie University, Canada, 1991. The medial axis of a polygon can be constructed in linear time (see e.g., Francis Chin, Jack Snoeyink, and Cao An Wang, “Finding the Medial Axis of a Simple Polygon in Linear Time,” Proc. 6
th
Ann. Int. Symp. A
Bella Matthew C.
Haynes and Boone, LLP.
Tran Tam
Zyvex Corporation
LandOfFree
System and method for robust and efficient resizing of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for robust and efficient resizing of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for robust and efficient resizing of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3307373