Method for hidden line and surface removal in a three dimensional display

Claim 2

In a computer graphics system for displaying a multiface image, each face comprising a plurality of vertices connected by line segments, the method comprising: (a) establishing a scene partition comprising a series of stripped regions, each region having at least one boundary which intersects an image vertex; (b) selecting a face of said image; (c) inserting into said scene partition, line segments of said selected face and modifying each region in which a line segment appears by contracting a portion of the boundary thereof which extends from a side of said line segment and does not intersect an image vertex; and (d) determining visibility of said modified regions by assigning a temporary visibility value to each said modified region, said value indicating that said region is visible to a viewer in a view plane, and when a new image face is inserted into said scene partition, comparing depth positions of modified regions within said new image face with a set of regions indicted as visible in image faces in said scene partition, and for modified regions which are obscured by said new image face, revising said temporary visibility values to reflect the visibility value of said new image face.

Claim 3

The invention as defined in claim 1 wherein step (b) randomly selects a face of said image.

Claim 4

The invention as defined in claim 2 wherein step (a) further includes: establishing association pointers to said scene vertex from a border of each region which is coincident therewith, and another pointer that associates said image vertex with one of said coincident region borders to enable said image vertex to be located in relation to said border and vice versa.

Claim 5

The invention as defined in claim 3, wherein step (a) further includes: establishing adjacency pointers between adjacent vertices which are visible in adjoining regions, a said adjacency pointer enabling a location to be found of a vertex in one region, from an adjacent vertex in an adjoining region when said adjacent vertex is located.

Claim 6

The invention as defined in claim 1 where in step (a) at least one boundary of each said region is coincident with a vertex of said image.

Claim 7

The invention as defined in claim 5 where in step (c) an intersection between an inserted line segment and a region boundary is determined by examination of successive solutions of an equation for said inserted line segment to determine a sign change, as coordinates of successive vertices visible within said region are substituted therein.

Claim 8

In a computer graphics system for displaying a multiface image, the method comprising: (a) establishing a scene partition comprising a series of parallel stripped regions bounded by attachment lines, at least one boundary of each said region created by the passing of an attachment line through a vertex of said image; (b) randomly selecting a face of said image; (c) finding intersections of a line segment of said image with said attachment lines; (d) shortening each attachment line which is intersected by said line segment, except for those attachment lines defining beginning and end vertices of said line segment, so as to retain that portion of such attachment line which includes the vertex through which it passes; (e) repeating steps (c) and (d) for all further line segments of said selected face, said line segments and shortened attachment lines combining to form additional regions; (f) assigning to each said region a temporary visibility value from a view plane, said visibility value indicating the visibility of said selected face in relation to other faces; (g) repeating steps (b)-(f) for each face of said multiface image until all faces of said image have been selected, and after each face is added to the scene partition, updating said temporary visibility value of any obscured region to indicate the visibility value of the obscuring face; and (h) displaying only regions visible in said view plane.

Claim 9

In a computer graphics system for displaying a multiface image, the method comprising: (a) establishing a scene partition comprising a series of parallel stripped regions bounded by attachment lines, at least one boundary of each said region created by the passing of an attachment line through a vertex of said image; (b) randomly selecting a face of said image; (c) finding intersections of a line segment of said image with said attachment lines; (d) shortening each attachment line which is intersected by said line segment, except for those attachment lines defining beginning and end vertices of said line segment, so as to retain that portion of such attachment line which includes the vertex through which it passes; (e) repeating steps (c) and (d) for all further line segments of said selected face, said line segments and shortened attachment lines combining to form additional regions; (f) assigning to each said region a temporary visibility value from a view plane, said visibility value indicating the visibility of said selected face in relation to other faces; (g) repeating steps (b)-(f) for each face of said multiface image until all faces of said image have been selected, and after each face is added to the scene partition, updating said temporary visibility value of any obscured region to indicate the visibility value of the obscuring face; and (h) displaying only regions visible in said view plane.

Claim 10

The invention as defined in claim 7 wherein said intersection finding step (c) comprises: starting at an end vertex of said line segment and, in an equation which defines said line segment, substituting values of vertices which define limits of a region boundary coincident with said end vertex and solving said equation for each substitution; and identifying an exit point of said line segment from said region when a sign change occurs in successive solutions of said equation.

Claim 11

The invention as defined in claim 8 wherein a region boundary coincident with said end vertex of said line segment may be located by assigning an association pointer value to said end vertex, said pointer value indicating the location of a vertex of said coincident region boundary.

Claim 12

In a computer graphics system for displaying a multiface image, the method comprising: (a) establishing a scene partition comprising a series of stripped regions, each region comprising a set of vertices and boundaries intersecting said vertices; (b) establishing adjacency pointer values between vertices which are visible in adjacent regions, said pointer values enabling one said vertex to be found from the other and vice versa; (c) randomly selecting a face of said image; (d) inserting into said scene partition, line segments of said selected face by determining a first region in which a said line segment is present, and finding for said region, a vertex that is also visible in an adjacent region in which said line segment appears, whereby said adjacency pointer values are used to traverse said regions; (e) modifying the regions in which said line segments appear by contracting selected boundaries thereof to eliminate portions which do not intersect an image vertex; and (f) determining visibility of said modified regions by comparing their Z extents from a view plane with Z extents of regions in a subsequently added image face, and assigning a visibility indication to any non-obscured region.

Claim 13

In a computer graphics system for displaying a multiface image, the method comprising: (a) establishing a scene partition comprising a series of stripped regions, each region comprising a set of vertices and boundaries intersecting said vertices; (b) establishing adjacency pointer values between vertices which are visible in adjacent regions, said pointer values enabling one said vertex to be found from the other and vice versa; (c) randomly selecting a face of said image; (d) inserting into said scene partition, line segments of said selected face by determining a first region in which a said line segment is present, and finding for said region, a vertex that is also visible in an adjacent region in which said line segment appears, whereby said adjacency pointer values are used to traverse said regions; (e) modifying the regions in which said line segments appear by contracting selected boundaries thereof to eliminate portions which do not intersect an image vertex; and (f) determining visibility of said modified regions by comparing their Z extents from a view plane with Z extents of regions in a subsequently added image face, and assigning a visibility indication to any non-obscured region.

Claim 14

The invention as defined in claim 10 wherein step (d) further comprises: substituting in a line equation for a line segment being inserted into the scene partition, only vertex coordinates that define a region to establish a point of intersection between said line segment and a border of said region.

Claim 15

The invention as defined in claim 11 wherein a vertex at a T junction of boundaries of at least three regions is visible in two regions to either side of a vertical bar of the T junction and is invisible in a region above a horizontal bar of the T junction.