Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1996-12-18
2001-09-18
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S440000
Reexamination Certificate
active
06292190
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to the generation and display of computerized drawings and more particularly to a computerized system for automatically identifying possible geometric relationships (such as “terminated by” or “parallel to”) between individual points, lines, and other drawing elements.
BACKGROUND ART
In conventional computer assisting drafting, the individual elements (such as line segments, circles, and arcs) of a drawing are typically specified as vector-based data. For example, in Cartesian coordinates, a point is represented by (x,y), with x representing the horizontal distance from a vertical y-axis, and y representing the vertical distance from a horizontal x-axis. In a similar fashion, a circle can be represented as a center point (x
c
,y
c
) having an associated radius (r), and a line segment can be represented as two points (x
a
,y
a
),(x
b
,y
b
). In theory, if each of the relevant elements is accurately dimensioned and its position fixed with respect to the two coordinate axes, then any geometric relationship between elements will be inherent and need not be explicitly specified. However, because dimensional data is subject to round-off errors and/or measurement errors, and because geometric constraint information is not subject: to such errors and is invariant during scaling and other manipulation of the image, manually generated geometrical constraints (such as coincident with, terminated by or parallel to) have been used to supplement absolute dimensional information (position, length, radius, etc.) to specify a vector-based image.
It is a relatively trivial matter to determine whether the Cartesian coordinates of corresponding points of two specified elements are identical (within a given tolerance) and thus whether the respective elements defined by those points are coincident. Determining whether two specified sets of non-coincident endpoints define respective lines which are perpendicular or parallel requires computing a trigonometric formula corresponding to the difference in slope of the two lines, but is also relatively simple. In a similar manner, a straightforward trigonometric formula will determine whether a specified point is on a specified line. Determining whether a specified point is on a specified circle or whether a specified line is tangent to a specified circle is only a slightly more complex trigonometric calculation, particularly if the Cartesian coordinates have been translated so that the center of the circle is at the origin. However, it is still a difficult and time consuming computation to find all possible geometric constraints between a large number of elements. Since each possible pair of elements must be reviewed for all possible constraints, the computation time using a simple search strategy will increase in proportion to the square of the number of elements. Moreover, computing the trigonometric formulas associated with angle and tangential relationships requires more computational resources than the simple comparison of numbers associated with coincident points. The problem of providing sufficient computational resources is exacerbated when the constraints are being generated and displayed in real time.
A quadtree index is a two-dimensional equivalent to a conventional binary index used to locate data within a linear array, and is typically used to locate points in a two-dimensional space. Such a quadtree index is based on the subdivision of a two-dimensional space into four not necessarily identical subspaces (quadrants) and on the recursive division of each of those quadrants into a hierarchical sequence of quadrants within quadrants until there is at most only one point (or several points that are coincident within a predetermined tolerance) in each. The final result is a not necessarily symmetric “tree” structure whose “root” is at the center of the original space, and whose “leaves” are at the end of the branches. If the tree containing a known set of points is optimized (i.e., does not contain any unnecessary nodes), then each node will either be a root node or a branch node that does not contain any points, or else will be one of a set of four related leaf nodes which collectively contain at least one point; if the points are not uniformly distributed, the size of many of the individual leaf nodes in the optimized quadtree will be significantly larger than dictated by the tolerance dimension, thereby significantly reducing the number of leaf nodes. Once such an optimized quadtree index has been constructed, locating any data associated with a particular point is accomplished by following the tree from the root node to the relevant leaf node, using the relative location of the point with respect to the center of the current node to determine whether to branch up or down and left or right.
The quadtree concept is extendible to more than two dimensions (for example, an “octree” for use with 3 dimensional data) and to non-Cartesian coordinate systems. A quadtree based on polar coordinates is called a “polar quadtree”. A two dimensional binary tree (“bintree”) is similar to a quadtree, but recursively decomposes the two-dimensional space into two subspaces along only one axis for the even-numbered divisions, and along the other axis for the odd-numbered divisions.
The use of an evenly divided Cartesian quadtree as a spatial index for two dimensional data (such as points and lines in a computer-aided design system) is a particular application of polygonal decomposition (“tiling”) of a two dimensional space and is described at length in Hanan Samet:
The Design and Analysis of Spatial Data Structures
, copyrighted by Addison Wesley Publishing company in 1990. That reference also discusses the decomposition of two-dimensional space based on non-polygonal tiles using a “sector” bintree to divided the polar plane into sectors of equal angular intervals &thgr; and a “polar” quadtree to partition the polar plane on the basis of both &rgr; and &thgr;. However, the author notes that “generally for a decomposition scheme to be useful in geometric applications, it must have pixel-sized squares (i.e., 1×1) as the primitive tiles” [§1.4.1, p 24], and that a space decomposition based on polygonal tiles is “the prevalent method in use today” [§1.4.2, p 26]. The author also notes that in the sector tree, rotation is “not simple”and that translation is “computationally expensive”.
In order to perform a parametric transformation of the underlying computer model of an object depicted in a computerized drawing, it is necessary to specify not only dimensions of individual components (such as lines and circles) and identity which are subject to change during the parametric transformation, but also to specify geometric constraints between elements (including reflexive constraints such as relative orientation (e.g., “parallel”) or touching end-to-end (“mutual relimitation”), and non-reflexive constraints such as “point-on” a line or a T-shaped intersection (“non-reflexive relimitation”) which are to remain invariant during the transformation process. Software is commercially available to process a constrained model to provide exact dimensional and position data for each element of each component, before and after any indicated transformation has taken place, while keeping the various elements connected in accordance with the specified constraints. Geometrical and/or dimensional constraints are also useful for eliminating the requirement to provide accurate dimensional data for all Components. Thus if four line segments are constrained geometrically as being connected end-to-end at right angles and two adjacent sides are constrained dimensionally to be the same length, the resultant model is already constrained to be a square and it should only be necessary to specify the initial orientation of one of the lines and the length of one side in order to define the entire object.
Since computerized drawing systems typically operate in real time in response to data input by a human operator, i
Blakely , Sokoloff, Taylor & Zafman LLP
Dassault Systemes of America Corp.
Jankus Almis R.
LandOfFree
Automatic identification of geometric relationships between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic identification of geometric relationships between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic identification of geometric relationships between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476101