US4847789A — Method for hidden line removal

Claim 1

Independent Claim 283 words

A method performed by a general computer for removing hidden lines in a two dimensional surface chart disclosing an image of a three-dimensional surface, including the steps of: (a) storing in a computer memory the X, Y and Z co-ordinates of selected points (A, B, C, D, E) of the surface as a first matrix; (b) transforming in the computer the first matrix into a second matrix indicating a drawing sequence through the selected points; (c) rotation in the computer the points of the second matrix around the z-axis a first angle α; (d) rotating in the computer said rotated second matrix points around the x-axis at a second angle β; and (e) drawing the two-dimensional surface chart in accordance with an indicated sequence using the X and Y coordinate values of the rotated points in step (d), wherein this drawing step includes the steps of: performing a drawing operation of X-traces, and X-trace being defined as a line passing through points having substantially the same Y values in said first matrix; and performing, after an X-trace drawing operation has been performed, a plurality of ΔY-trace drawing operations between last drawn X-trace and a next to be drawn X-trace; a Y-trace being defined as a line passing through points having substantially the same X values in the first matrix, and a ΔY-traces being defined as the part of a Y-trace extending between two adjacent X-traces; said sequential drawing operation proceeding in sequence from low Y-value X-traces toward high Y-value X-traces; and the drawing of X-traces and ΔY-traces during said performed drawing operations being limited to lines drawn outside a forbidden area defined by the computer as an area surrounded by previously drawn lines.

Claim 2

Independent Claim 283 words

A method performed by a general computer for removing hidden lines in a two dimensional surface chart disclosing an image of a three-dimensional surface, including the steps of: (a) storing in a computer memory the X, Y and Z co-ordinates of selected points (A, B, C, D, E) of the surface as a first matrix; (b) transforming in the computer the first matrix into a second matrix indicating a drawing sequence through the selected points; (c) rotation in the computer the points of the second matrix around the z-axis a first angle α; (d) rotating in the computer said rotated second matrix points around the x-axis at a second angle β; and (e) drawing the two-dimensional surface chart in accordance with an indicated sequence using the X and Y coordinate values of the rotated points in step (d), wherein this drawing step includes the steps of: performing a drawing operation of X-traces, and X-trace being defined as a line passing through points having substantially the same Y values in said first matrix; and performing, after an X-trace drawing operation has been performed, a plurality of ΔY-trace drawing operations between last drawn X-trace and a next to be drawn X-trace; a Y-trace being defined as a line passing through points having substantially the same X values in the first matrix, and a ΔY-traces being defined as the part of a Y-trace extending between two adjacent X-traces; said sequential drawing operation proceeding in sequence from low Y-value X-traces toward high Y-value X-traces; and the drawing of X-traces and ΔY-traces during said performed drawing operations being limited to lines drawn outside a forbidden area defined by the computer as an area surrounded by previously drawn lines.

Claim 3

Dependent Claim 25 words

A method according to the claim 21 wherein the forbidden area is defined as an area falling between an upper horizon and a lower horizon.

Claim 4

Dependent Claim 29 words

A method according to the claim 2 wherein the forbidden area between the upper and lower horizon is sequentially increased by the computer when the drawing operation is proceeding.

Claim 5

Dependent Claim 76 words

A method according to the claim 3 wherein the upper horizon in a starting stage of the operation extends from an initial low value at a first bound U1-U2 of said upper horizon up to an end point (E1) of a first Y-trace (A1, B1, C1, D1, E1), follows said Y-trace, follows a X-trace (A1, A2, A3, A4, A5) and drops down to said initial low value at a second bound U3-U4 of said upper horizon.

Claim 6

Dependent Claim 52 words

A method according to the claim 4 wherein the upper horizon in a second stage of an operation (FIG. 6) follows the second X-trace (B1, B2, B3, B4, B5) instead of the first X-trace, whereas the lower horizon remains unchanged, whereby the forbidden area is formed between the first and second X-traces.

Claim 7

Dependent Claim 77 words

A method according to the claim 3 wherein the lower horizon in a starting stage of the operation extends from an initial high value at a first bound L1-L2 of said lower horizon down to an end point (E1) of a first Y-trace (A1, B1, C1, D1, E1), follows said Y-trace, follows a first X-trace (A1, A2, A3, A4, A5) and jumps up to said initial high value at a second bound L3-L4 of said lower horizon.

Claim 8

Dependent Claim 20 words

A method according to the claim 1 wherein said matrix transformation includes assigning drawn--no drawn parameters to each matrix row.

Claim 9

Dependent Claim 30 words

A method according to the claim 1 wherein said matrix transformation includes an origin translation and a magnitude transformation of the co-ordinate values before the rotation step in step (c).

Claim 10

Dependent Claim 32 words

A method according to the claim 1 wherein an origin translation and a magnitude transformation is executed after the rotation operation of step (d) but before the drawing operation of step (e).

Claim 11

Dependent Claim 37 words

A method according to claim 1 including the steps of: storing in computer memory information defining upper and lower horizons and continuously updating said upper and lower horizons for each drawing operation outside the present forbidden area.

Claim 12

Dependent Claim 29 words

A method according to claim 1 wherein drawing rules for the X and Y co-ordinates are exchanged when the frotation angle α around the Z-axis exceeds a predetermined value.

Claim 13

Dependent Claim 38 words

A method according to claim 1 wherein the number of co-ordinate points stored for the upper and lower horizon is a magnitude higher than the number of co-ordinate points stored for the selected points of the three-dimensional surface.

Claim 14

Dependent Claim 70 words

A method according to claim 1 wherein the performing of each drawing operation between any two points along a trace includes making incremental line segments where some increments for lines drawn are in the Y direction and other increments for lines drawn are in the X direction, and wherein a check is made by the computer inhibiting the subsequent drawing of line segment increments that fall within that forbidden area.

Claim 15

Dependent Claim 29 words

A method according to claim 13 including the further step of updating in the computer, the horizon information stored for each incremental drawing operation step outside the forbidden area.

Claim 16

Dependent Claim 60 words

A method according to claim 13 wherein the making of incremental line segments includes computing the angle between the line to be drawn and the X axis, and positioning increments along the X direction when the computed angle is less than 45°, and positioning increments along the Y direction when the computed angle is greater than or equal to 45°.

Claim 17

Dependent Claim 257 words

A computerized method for displaying, from a given desired point of viewing, a three-dimensional surface on a two-dimensional display having a first coordinate and a second coordinate, the method comprising the steps of: (a) storing in computer memory (first coordinate, second coordinate) respective pairs of values for points lying on the surface of the object; and (b) where an first-coordinate trace corresponds to stored points which lie along the surface of the object and have the same stored first-coordinate value, and where a ΔCOORD--trace corresponds to points along a line that extends between adjacent first-coordinate traces, and where succesive first-coordinate traces are successively further away from the point of viewing, (i) performing, on the display, a drawing operation along a previously undrawn first-coordinate trace T i (where i is an integer) which is nearest the point of viewing; (ii) performing, on the display, a drawing operation along ΔCOORD--traces extending from trace T i to trace T i+1 ; (iii) repeating steps (b)(i) and (b)(ii) in alternation; and (iv) where a forbidden area is defined as the largest area surrounded by lines previously drawn in performed drawing operations, updating the forbidden area after each first-coordinate trace and each ΔCOORD--trace drawing operation is performed; wherein said step (b)(i) includes the step of drawing a line only along that portion of the previously undrawn first-coordinate trace T i which is not in the forbidden area; and wherein said step (b)(ii) includes the step of drawing a line only along that portion of ΔCOORD--traces which are not in the forbidden area.

Claim 18

Dependent Claim 257 words

A computerized method for displaying, from a given desired point of viewing, a three-dimensional surface on a two-dimensional display having a first coordinate and a second coordinate, the method comprising the steps of: (a) storing in computer memory (first coordinate, second coordinate) respective pairs of values for points lying on the surface of the object; and (b) where an first-coordinate trace corresponds to stored points which lie along the surface of the object and have the same stored first-coordinate value, and where a ΔCOORD--trace corresponds to points along a line that extends between adjacent first-coordinate traces, and where succesive first-coordinate traces are successively further away from the point of viewing, (i) performing, on the display, a drawing operation along a previously undrawn first-coordinate trace T i (where i is an integer) which is nearest the point of viewing; (ii) performing, on the display, a drawing operation along ΔCOORD--traces extending from trace T i to trace T i+1 ; (iii) repeating steps (b)(i) and (b)(ii) in alternation; and (iv) where a forbidden area is defined as the largest area surrounded by lines previously drawn in performed drawing operations, updating the forbidden area after each first-coordinate trace and each ΔCOORD--trace drawing operation is performed; wherein said step (b)(i) includes the step of drawing a line only along that portion of the previously undrawn first-coordinate trace T i which is not in the forbidden area; and wherein said step (b)(ii) includes the step of drawing a line only along that portion of ΔCOORD--traces which are not in the forbidden area.

Claim 19

Dependent Claim 261 words

A computerized method for displaying, from a given desired point of viewing, a three-dimensional surface on a two-dimensional display in which points thereon have an X-coordinate and a Y-coordinate, the method comprising the steps of: (a) storing, in computer memory, coordinates for points lying on the three-dimensional surface; and (b) where an X-trace corresponds to stored points which lie along the three-dimensional surface and have at least substantially the same stored X-coordinate value, and where a ΔY--trace corresponds to points along a line of characterized by a substantially uniform Y-cordinate value wherein each ΔY--trace extends between two adjacent X-traces, and where successive X-traces are successively further away from the point of viewing, (i) performing, on the display, a drawing operation along a previously undrawn X-trace X j (where j is an integer) which is nearest the point of viewing; (ii) performing, on the display, a drawing operation along ΔY-traces extending from trace X j to trace X j+1 ; (iii) repeating steps (b)(i) and (b)(ii) in alternation for successive values of j; and (iv) where a forbidden area is defined as the largest area surrounded by lines previously drawn in performed drawing operations, updating the forbidden area after each X-trace and ΔY-trace drawing operation is performed; wherein said step (b)(i) includes the step of drawing a line only along that portion of the previously undrawn X-trace x i which is not in the forbidden area; and wherein said step (b)(ii) includes the step of drawing a line only along those portions of the Δy-traces which are not in the forbidden area.

Claim 20

Dependent Claim 261 words

A computerized method for displaying, from a given desired point of viewing, a three-dimensional surface on a two-dimensional display in which points thereon have an X-coordinate and a Y-coordinate, the method comprising the steps of: (a) storing, in computer memory, coordinates for points lying on the three-dimensional surface; and (b) where an X-trace corresponds to stored points which lie along the three-dimensional surface and have at least substantially the same stored X-coordinate value, and where a ΔY--trace corresponds to points along a line of characterized by a substantially uniform Y-cordinate value wherein each ΔY--trace extends between two adjacent X-traces, and where successive X-traces are successively further away from the point of viewing, (i) performing, on the display, a drawing operation along a previously undrawn X-trace X j (where j is an integer) which is nearest the point of viewing; (ii) performing, on the display, a drawing operation along ΔY-traces extending from trace X j to trace X j+1 ; (iii) repeating steps (b)(i) and (b)(ii) in alternation for successive values of j; and (iv) where a forbidden area is defined as the largest area surrounded by lines previously drawn in performed drawing operations, updating the forbidden area after each X-trace and ΔY-trace drawing operation is performed; wherein said step (b)(i) includes the step of drawing a line only along that portion of the previously undrawn X-trace x i which is not in the forbidden area; and wherein said step (b)(ii) includes the step of drawing a line only along those portions of the Δy-traces which are not in the forbidden area.

Claim 21

Dependent Claim 102 words

The method of claim 17 comprising the further steps of: initially drawing the nearest X-trace to the point of viewing and drawing a Y-trace that starts at one end of the initially drawn X-trace and that extends to successive stored points that have (i) the same X-coordinate value as said one end of the initially drawn X-trace and (ii) Y-coordinate values that are successively more distant from the initially drawn X-trace; wherein the initially drawn X-trace and Y-trace together with the lines drawn in accordance with steps (b)(i) and (b)(ii) define the lines that form the two-dimensional image with hidden lines removed.

Claim 22

Dependent Claim 33 words

The method of claim 18 comprising the further step of: rotating the X-coordinates and Y-coordinates about predefined angles so that the two-dimensional display projects the three-dimensional surface from the desired point of viewing.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1992-07-10	1993-01-09	1993-07-11	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1996-07-10	1997-01-09	1997-07-11	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2000-07-10	2001-01-09	2001-07-11	$7700.00	Window Closed / Lapsed

Method for hidden line removal

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag