Warping geometric objects

Details Warping geometric objects Warping geometric objects

1998-10-21

2003-01-07

Brier, Jeffery (Department: 2779)

Computer graphics processing and selective visual display system

Computer graphics processing

Graph generating

C345S473000, C382S294000

Reexamination Certificate

active

06504541

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention is directed toward the field of warping sets of geometric objects.
2. Description of Related Art
Physical areas are often modeled using geometric objects. Examples of such physical areas include a geographic region and a building's floor plan. One example of a model using two-dimensional geometric objects is a map of a geographic region, such as a city.
FIG. 1
illustrates a map that is formed by a set of geometric objects. The objects in
FIG. 1
include points
60
-
70
, arcs
80
-
91
, and polygons
50
-
51
. Each arc
80
-
91
represents a road and is bounded at each of its ends by a point. For example, arc
80
is bounded at one end by point
60
and at another end by point
62
. Each arc can be co-bounded by one or two polygons. For example, arc
86
is co-bounded by polygons
50
and
51
, while arc
85
is only co-bounded by polygon
50
. Each polygon
50
and
51
is formed by a set of arcs that define the boundary of the polygon. For example, polygon
50
is defined by boundary arcs
81
,
82
,
83
,
84
,
85
, and
86
.
Different models of the same physical area often provide different quality details about the area. Differences between models of the same area can occur, because models can be distorted, so that all the features in the model are not depicted in their true positions. Such distortions are often localized, with different regions of the model being distorted differently. In paper models, distortion can be caused by paper stretching, folding, and scaling. In electronic models, distortion can be caused when the model is transformed into digital form.
By repositioning different models of the same area, a more accurate new model can be created.
FIG. 2
illustrates a map
100
of an area that is neither very smooth nor accurate.
FIG. 3
shows a more accurate map
10
of the same area as map
100
. The differences between maps
100
and
10
are illustrated in
FIG. 4
, which shows an overlay of maps
100
and
110
. A repositioning process can be performed to utilize the details of both maps
100
and
110
to obtain an improved new map.
The use of repositioning is particularly beneficial and practical is generating electronic maps. There are often many different maps available for a particular region. By making use of a computer to reposition the many maps that are available for a region, a very accurate new map can be generated in a time efficient and cost efficient manner.
One known method for repositioning two models is to warp one model based on the weighted sum of local displacements between points in the two models. In this method, a set of matching points in the models is obtained for selected regions of the models. Displacements between matching points in each selected region are then employed to generate a warping transformation for the selected region. The warping transformation is then used to transform points in one of the models into points in a new model.
However, such a method is inadequate, because it does not provide for maintaining the topology of the original models in the new model. Topology refers to the relative connections and orientations of geometric objects in the model, and its preservation is critical to ensuring the accuracy of the new model. For example, if topology is not preserved, arc intersections which do not exist in either of the original models may be inserted into the new model.
In order to better maintain topology, model-based warping can be employed. One known method of such warping includes the creation of a global transformation model that provides for transforming all of the points in a model into points in a new model. In such a method, all matching points from two existing models are employed to determine parameters for the global transformation model using numerical analysis, such as least mean squares techniques. However, this global approach does not provide for eliminating local distortions, which constitute many of the distortions that are encountered.
Accordingly, there is a need for a warping process that can be applied to models to correct local distortions without compromising topology.
SUMMARY OF THE INVENTION
The present invention, roughly described, provides for warping models made from geometric objects, such as electronic maps, to correct local distortions in the models without compromising model topology. The warping is performed by using a set of transformation functions that are derived from relationships between points in a first model that match points in a second model with more accurate positioning. The transformation functions are applied to the points in the first model to generate a new model with reduced distortion.
In order to provide for reducing local distortions, warping is applied to selected corresponding regions of the first model and the second model by triangulating these regions and generating transformation functions for each corresponding pair of triangles. Topology preservation is achieved by identifying matching points in the first model and the second model that have a potential for causing topology deviations. Such matching points are then excluded from the process of developing transformation equations to be used in the warping process.
Matching points with potential for causing topology deviations are identified by triangulating matching points in the selected regions of the first model and the second model and analyzing the resulting triangles. A matching point is identified as having potential for causing topology deviations, if it is a vertex in a triangle in one model that has an inverted corresponding triangle in the other model. A matching point is also identified as having potential for causing topology deviations, if it is a vertex in a triangle having too small an area or height. An iterative process is performed to identify such undesirable matching points.
These and other objects and advantages of the present invention will appear more clearly from the following description in which the preferred embodiment of the present invention has been set forth in conjunction with the drawings.


REFERENCES:
patent: 4805127 (1989-02-01), Hata et al.
patent: 4912664 (1990-03-01), Weiss et al.
patent: 5465323 (1995-11-01), Mallet
patent: 5486822 (1996-01-01), Tenmoku et al.
patent: 5546107 (1996-08-01), Deretsky et al.
patent: 5845228 (1998-12-01), Uekawa et al.
patent: 5850229 (1998-12-01), Edelsbrunner et al.
patent: 5864342 (1999-01-01), Kajiya et al.
patent: 5878164 (1999-03-01), Brown et al.
patent: 6026189 (2000-02-01), Greenspan et al.
patent: 6078701 (2000-06-01), Hsu et al.
Marshall Bern and David Epstein,Mesh Generation and Optimal Triangulation, Computing and Euclidean Geometry, Ding-Zhu Du and Frank Hwang editors, World Scientific, Singapore, pp. 23-90, 1992.
Jonathan Richard Shewchuk,Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, First Workshop on Applied computational Geometry (Philadelphia, Pennsylvania) pp. 124-133, ACM, May 1996.
Jim Ruppert,A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):548-585, May 1995.
Marshall Bern and David Epstein,Mesh Generation and Optimal Triangulation, Computing and Euclidean Geometry, Ding-Zhu Du and Frank Hwang editors, World Scientific, Singapore, pp. 1-78, 1992.
Jonathan Richard Shewchuk,Triangle: Engineering A 2D Quality Mesh Generator and Delaunay Triangulator, First Workshop on Applied Computational Geometry (Philadelphia, Pennsylvania), pp. 1-10, ACM, May 1996.
Jim Ruppert,A Delauney Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms, Journal of Algorithms 18(3): 1-46, May 1995.
Zhu et al.,FORMS: A flexible Object Recognition and Modelling System, IEEE Paper ISBN: 0-8186-7042-8, pp. 465-472, Jun. 1995.
Cakmakov et al,A Model for Polygon Similarity Estimation, IEEE Paper ISBN: 0-8186-2760-3, pp. 701-705, May 1992.
Lu et al.,M5.11: Hierarchical Shape Recognition Using Polygon Approximation and Dynamic Alignment, IEEE Paper C

Affiliated with

Also associated with

Rating

Warping geometric objects does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Warping geometric objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Warping geometric objects will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3009804