BACKGROUND OF THE INVENTION Generally, in computer graphics, objects are represented as surfaces, with the surfaces being represented by meshes. A mesh consists of a set of vertices, or points, in multi-dimensional space, which are interconnected by edges. The edges define polygonal faces, which may be in the form of triangles, quadrilaterals, and so forth. In some computer graphic operations, it is desirable to generate a representation of a surface at a finer resolution than a current representation. For a surface that is represented by one or more triangles, a subdivision surface is typically formed by dividing the upper level triangle into four smaller triangles in a regular manner, thereby to form a set of first level subdivision triangles. One or more of the first-level subdivision triangles may be further subdivided, through any of a number of subdivision levels. The subdivision surfaces defined by the subdivision triangles may be used to provide, for example, complex contours for the surfaces of objects in a scene, which can allow for realistic renderings of images of the objects.

A problem arises in that, since a triangle is defined by three points in space, typically, 3n coordinates are required to define the triangle, "n"coordinates for each of the three points that define the triangle in n-dimensional space. Each of the coordinates will need to be expressed as floating point numbers. Accordingly, it will be appreciated that, for any scene that includes obj ects whose surfaces have any significant degree of complexity, the storage requirements for the database that defines the objects in the scene can be enormous.

SUMMARY OF THE INVENTION The invention provides a new and improved computer graphics system for, and method of, efficiently encoding subdivision surfaces of a triangular surface element and recovering their barycentric coordinates relative to the upper level triangular surface element. The efficient encoding allows for a reduction in the amount of storage that is necessary for the database that defines the objects in a scene in a computer graphics system.

In brief summary, in one aspect the invention provides a system for generating a plurality of identifiers, each associated with one of a like plurality of subdivision surfaces of a surface element. Each subdivision surface has a predetermined position relative to the surface element. The surface element is associated with a higher-level identifier, with the higher level identifier comprising at least one bit, with the higher level identifier being stored in respective bit positions of a word. The system comprises a shifter module, a replication module and a position code insertion module. The shifter module is configured to shift the higher level identifier by a selected number of bit positions thereby to generate a shifted higher level identifier in the word, the number of bit positions being associated with a number corresponding to the number of subdivision surfaces to be associated with the surface element. The replication module is configured to replicate the shifted higher level identifier to generate a plurality of replicated shifted higher level identifiers, each replicated shifted higher level identifier being associated with one of the subdivision triangular surfaces. The position code insertion module is configured to insert, in the vacated portion of each of the shifted replicated higher level identifiers, a position code identifying the position, relative to the surface element, of the subdivision surface that is associated with the respective replicated shifted higher level identifier.

In another aspect, the invention provides a system for generating coordinates for a subdivision surface of an upper level surface element at a predetermined subdivision level from an identifier associated with the subdivision surface. The identifier includes a plurality of position codes each identifying a position relative to a higher level. The system comprises a position code selection module, a relative position determination module and an iteration control. The position code selection module is configured to select from the identifier one of the position codes. The relative position determination module is configured to determine the position of a subdivision surface associated with the position code relative to a higher level subdivision surface. The iteration control is configured to control the position code selection module and the relative position determination module through a plurality of iterations, to enable the position code selection module to iteratively select identifiers associated with successive levels thereby to enable the relative position determination module to determine positions of subdivision surfaces at successive levels, to the predetermined subdivision level.

BRIEF DESCRIPTION OF THE DRAWINGS This invention is pointed out with particularity in the appended claims. The above and further advantages of this invention may be better understood by referring to the following description taken in conjunction with the accompanying drawings, in which: FIG. 1 depicts a computer graphics system for efficiently encoding subdivision surfaces of a triangular surface element and recovering their barycentric coordinates; FIG. 2 is a diagram depicting a triangular surface element and subdivision surfaces thereof, useful in understanding the operation of the computer graphics system depicted in FIG. 1; and FIG. 3 is a flow chart depicting operations performed by the computer graphics system in connection with determining barycentric coordinates, relative to an upper level triangular surface element, of a subdivision surface, using an identifier for the respective subdivision surface; and FIG. 4 is a flow chart depicting operations performed by the computer graphics system in connection with generating identifiers for subdivision surfaces for use in connection with determining barycentric coordinates as described in connection with FIG. 3.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT FIG. 1 depicts a computer graphics system 10 for efficiently encoding subdivision surfaces of a triangular surface element in respective identifiers, each associated with a respective subdivision surface, and for using the identifier associated with a respective subdivision surface to recover the location information for the respective subdivision surface. In the embodiment described herein, the location information is in the form of barycentric coordinates for the subdivision surface relative to an upper level surface element.

With reference to FIG. 1, the computer graphics system 10 in one embodiment includes a processor module 11 and operator interface elements comprising operator input components such as a keyboard 12A and/or a mouse 12B (generally identified as operator input element (s) 12) and an operator output element such as a video display device 13. The illustrative computer graphics system 10 is of the conventional stored-program computer architecture. The processor module 11 includes, for example, one or more processor, memory and mass storage devices, such as disk and/or tape storage elements (not separately shown), which perform processing and storage operations in connection with digital data provided thereto. The operator input element (s) 12 are provided to permit an operator to input information for processing. The video display device 13 is provided to display output information generated by the processor module 11 on a screen 14 to the operator, including data that the operator may input for processing, information that the operator may input to control processing, as well as information generated during processing. The processor module 11 generates information for display by the video display device 13 using a so-called"graphical user interface" ("GUI"), in which information for various applications programs is displayed using various"windows. "Although the computer system 10 is shown as comprising particular components, such as the keyboard 12A and mouse 12B for receiving input information from an operator, and a video display device 13 for displaying output information to the operator, it will be appreciated that the computer system 10 may include a variety of components in addition to or instead of those depicted in FIG. 1.

The processor module 11 generally includes a processor, which may be in the form of one or more microprocessors, a main memory, and will generally include one a mass storage subsystem including one or more disk storage devices. The memory and disk storage devices will generally store data and programs (collectively, "information") to be processed by the processor, and will store processed data which has been generated by the processor. The processor module includes connections to the operator input device (s) 12 and the display device (s) 13, and will receive information input by the operator through the operator input device (s) 12, process the input information, and store the processed information in the memory and/or mass storage subsystem. In addition, the processor module can generate video display information, which can form part of the information obtained from the memory and disk storage device as well as processed data generated by the processor module itself, and provide the video display information to the display device (s) for display to the operator. The processor module 11 may also include connections (not shown) to hardcopy output devices such as printers for facilitating the generation of hardcopy output, as well as connections to modems and/or network interfaces (also not shown) for connecting the system 10 to the public telephony system and/or in a computer network for facilitating the transfer of information, and the like.

The computer graphics system 10 generates, from input provided by the operator, information defining the initial and subsequent shapes, surface characteristics and other information regarding multi-dimensional objects in a scene, which information may, for example, be used to generate a two-dimensional image of the scene. The image that may be generated represents the image of the object (s) in the scene as illuminated by one or more light sources, and as projected onto an image plane of a camera, with the object having a spatial position and rotational orientation relative to the illumination direction and the image plane and a scaling and/or zoom setting as selected by the operator. The surfaces of the objects are typically defined by a lattice of polygons, such as triangles or quadrilaterals, with each polygon being defined by three (in the case of triangles) or four (in the case of quadrilaterals) points in space. In the following, it will be assumed that the surface of the object is defined by a lattice that includes at least one triangle. The triangle may, in response to input from an operator, be subdivided into a plurality of other triangles, which will be referred to as subdivision triangles, as will be described below in connection with FIG. 2. One or more of the first-level subdivision triangles may be further subdivided, and so on through a number of subdivision levels. The invention provides an arrangement for efficiently encoding the subdivision triangles through the respective subdivision levels in respective identifiers. As will be clear from the following, the encoding of each identifier will indicate both the subdivision level of the subdivision triangle associated with the identifier, and the position of the subdivision triangle in relation to higher level triangles, in particular, the upper level triangle.

In addition, the invention provides an arrangement for using the identifier associated with a respective subdivision triangle to recover the barycentric coordinates of the points that define the respective subdivision triangle, relative to a higher-level surface element. In the embodiment described herein, the invention provides an arrangement for recovering the barycentric coordinates of the thee points that define the respective subdivision level.

The invention allows for the compact storage of information relating to the subdivision triangles at the various subdivision levels, since, as will be apparent from the following, a single storage location in the computer graphics system can be used to store sufficient information relating to a subdivision triangle to enable the coordinates of the points defining the subdivision triangle to be determined, instead of the at least three storage locations that would be required to explicitly store the respective coordinates of each of the three points that define the subdivision triangle.

Accordingly, the invention allows the amount of computer data storage that would be required to store information relating to subdivision triangles in a simulated scene in the computer graphics system 10 to be considerably reduced.

Moreover, the invention reduces the amount of time that is required to generate subdivision triangles associated with a higher-level triangle. To generate the subdivision triangles, computer graphics system 10 needs only to generate the respective identifiers for the respective subdivision triangles, instead of the explicit multi-dimensional coordinates for the points that are necessary to define the subdivision triangles. Generally, the identifiers can be generated using integer arithmetic, whereas generating the explicit coordinates typically requires floating point arithmetic. The computer graphics system 10 can, using a methodology described below, generate the explicit coordinates of the points defining a subdivision triangle only when it needs to make use of the explicit coordinates. As will be further described below, the computer graphics system 10 can make extensive use of integer arithmetic when generating the coordinates of the points defining a subdivision triangle when it needs to generate them.

The arrangement for efficiently encoding subdivision triangles will be described in connection with FIG. 2. With reference to FIG. 2, that FIG. depicts an upper-level triangle 20, defined by points ABC, that has been subdivided into four subdivision triangles 21 (0), 21 (1), 21 (2) and 21 (3) (generally identified by reference numeral 21 (tl) (t, =0, 1,2, or 3), with the subscript to the index"t"indicating the subdivision level). Subdivision triangle 21 (0) is defined by points ADE, subdivision triangle 21 (1) is defined by points DBF, subdivision triangle 21 (2) is defined by points EFC, and subdivision triangle 21 (3) is defined by points DEF. The subdivision triangles 21 (t,) are formed such that point D is at the midpoint of line segment AB, point E is at the midpoint of line segment AC, and point F is at the midpoint of line segment BC. The illustrative upper-level triangle 20 depicted in FIG. 2 is an equilateral triangle, but it will be appreciated that the upper level triangle may have any triangular shape.

Each of the subdivision triangles 21 (t,) is identified by an identifier that comprises three binary digits, or"bits,""bZblbo."The high order bit b2 of the identifier is set to"one, "and the binary- encoded value of the two low-order bits blbo correspond to the value of the index"t,". Thus, subdivision triangle 21 (0) is identified by the bit pattern 100, subdivision triangle 21 (1) is identified by the bit pattern 101, subdivision triangle 21 (2) is identified by bit pattern 110 and subdivision triangle 21 (3) is identified by bit pattern 111, all of which are shown in FIG. 2. As is well known, typically, computer systems store information in the form of words comprising a predetermined number of bits, and the computer graphics system 10 can store each identifier in a word.

One or more of the subdivision triangles 21 (tl) can be further subdivided in a similar manner, to form second level subdivision triangles. As shown in FIG. 2, each of subdivision triangles 21 (0) and 21 (3) is further subdivided into four subdivision triangles. One or more of subdivision triangles 21 (1) and 21 (2) may also be subdivided into respective sets of subdivision triangles, but, as will be appreciated by those skilled in the art, if a subdivision triangle at a particular subdivision level is further subdivided, it is not required that the other subdivision triangles at that same level be subdivided. In the illustration depicted in FIG. 2, subdivision triangle 21 (0) is divided into subdivision triangles 22 (0) (0) through 22 (0) (3), and subdivision triangle 21 (3) is divided into subdivision triangles 22 (3) (0) through 22 (3) (3). The second level subdivision triangles will generally be identified by reference numeral 22 (tl) (t2), where index"t,"identifies the first-level subdivision triangle in which the second-level subdivision triangle was formed, and index"t2" (t2=0, 1,2 or 3) refers to the particular second-level subdivision triangle. Subdivision triangle 22 (0) (0) is defined by points AHI, subdivision triangle 22 (0) (1) is defined by points HDG, subdivision triangle 22 (0) (2) is defined by points IGE and subdivision triangle 22 (0) (3) is defined by points HIG.

Subdivision triangle 22 (3) (0) is defined by points FJK, subdivision triangle 22 (3) (1) is defined by points GEK, subdivision triangle 22 (3) (2) is defined by points DGJ and subdivision triangle 22 (3) (3) is defined by points GJK. Similar to the positioning of the points D, E and F that serve to define, along with points A, B and C, the first level subdivision triangles 21 (t,), points H, I and G, that, along with points A, D and E serve to define the second level subdivision triangles 22 (0) (t2), are at the midpoints of line segments AD, AE and DE, respectively. Similarly, the points J and K, which, along with points D, E, F, and G, serve to define the second level subdivision triangles 22 (3) (t2), are at the midpoints of line segments DF and EF, respectively.

Similarly to the first-level subdivision triangles 21 (tl), each of the second-level subdivision triangles 22 (tl) (t2) is associated with an identifier. In each case, the identifier comprises five bits b4b3b2blbo, where bits in bit positions b4b3b2 of the identifier for the second-level subdivision triangle 22 (t,) (t2) correspond to the bits in bit positions b2blbo comprising the identifier associated with the first-level subdivision triangle 21 (tl) in which the second level subdivision triangles were formed, and the binary-encoded value of the bits in bit positions blbo of the identifier for the second-level subdivision triangle 22 (tl) (t2) correspond to the value of the index"t2"of the particular second-level subdivision triangle 22 (tl) (t2) associated with the identifier. Accordingly, the second-level subdivision triangle 22 (0) (0) is identified by the bit pattern 10000, subdivision triangle 22 (0) (1) is identified by the bit pattern 10001, subdivision triangle 22 (0) (2) is identified by bit pattern 10010 and subdivision triangle 22 (0) (3) is identified by bit pattern 10011, are as shown in FIG. 2.

Similarly, subdivision triangle 22 (3) (0) is identified by the bit pattern 11100, subdivision triangle 22 (3) (1) is identified by the bit pattern 11101, subdivision triangle 22 (3) (2) is identified by bit pattern 11110 and subdivision triangle 22 (3) (3) is identified by bit pattern 11111, as shown in FIG.

2. As with the identifiers for the first-level subdivision triangles 21 (t,), each identifier for a second- level subdivision triangle 22 (tl) (t2) can be stored as a word by the computer graphics system 10.

It will be apparent from examining FIG. 2 that the first level subdivision triangles 21 (0) through 21 (2) all have the same alignment as the upper level triangle 20. On the other hand, the first level subdivision triangle 21 (3) is rotated 180 degrees relative to the upper level triangle 20.

Similarly, it will be apparent from examining FIG. 2 that, for the second level subdivision triangles 22 (0) (tu), the indices t2 that are used to identify the second level subdivision triangles 22 (0) (t2) in the first-level subdivision triangle 21 (0), are in the same relative positions within the triangle 21 (0) as the indices t, for the first-level subdivision triangles 21 (tl) in the upper level triangle 20. That is, (i) the second-level subdivision triangle 22 (0) (0) is at the top (as shown in FIG. 2) in first- level subdivision triangle 21 (0) and is in the same alignment as subdivision triangle 21 (0), which is similar to the positioning and alignment of the first-level subdivision triangle 21 (0) relative to the upper-level triangle 20; (ii) the second-level subdivision triangle 22 (0) (1) is at the lower left in the first-level subdivision triangle 21 (0) and is in the same alignment as subdivision triangle 21 (0), which is similar to the positioning and alignment of the first level subdivision triangle 21 (1) relative to the upper- level triangle 20; (iii) the second-level subdivision triangle 21 (0) (2) is at the lower right in the first-level subdivision triangle 21 (0) and is in the same alignment as subdivision triangle 21 (0), which is similar to the positioning and alignment of the first level subdivision triangle 21 (2) relative to the upper- level triangle 20; and (iv) the second-level subdivision triangle 21 (0) (3) is in the middle of the lower half in the first level subdivision triangle 21 (0), and has an alignment rotated by 180 degrees relative to the first- level subdivision triangle 21 (0), similar to the positioning and alignment ofthe first level subdivision triangle 21 (3) relative to the upper-level triangle 20.

If either or both of the first-level subdivision triangles 21 (1) or 21 (2) are also subdivided, their second-level subdivision triangles will be associated with indices, and associated identifiers, in similar locations and alignments relative to the first-level subdivision triangle 21 (0). That is, if any of those first-level subdivision triangles has been subdivided, its second-level subdivision triangles will be labeled in a similar manner as the second-level subdivision triangles 22 (0) (0) through 22 (0) (3). Accordingly if one or both of the first-level subdivision triangles 21 (1) or 21 (2) is further subdivided, (v) the second-level subdivision triangle at the top (respecting the alignment depicted in FIG.

2) of the first-level subdivision triangle 21 (1) or 21 (2) will be associated with the same index t2= (0), and the same two low order bits blbo=00, as second-level subdivision triangle 22 (0) (0) (reference item (i) above), while keeping the index tl= (l) or (2) of the respective first-level subdivision triangle 21 (1) or 21 (2); (vi) the second-level subdivision triangle at the lower left will be associated with the same index t2= (l), and the same two low-order bits b lbo=01, as second-level subdivision triangle 22 (0) (1) (reference item (ii) above), while keeping the index tl= (l) or (2) of the respective first-level subdivision triangle 21 (1) or 21 (2); (vii) the second-level subdivision triangle at the lower right will be associated with the same index t2= (2), and the same two low order bits blbo=10 as the second-level subdivision triangle 22 (0) (2) (reference item (iii) above), while keeping the index tl= (l) or (2) of the respective first-level subdivision triangle 21 (1) or 21 (2); and (viii) the second-level subdivision triangle at the middle of the lower half of the respective first level subdivision triangle 21 (1), 21 (2), will be associated with the same index t2= (3), and the same two low-order bits b, bo=l l, as second level subdivision triangle 22 (0) (3) (reference item (iv) above), while keeping the index tl= (l) or (2) of the respective first-level subdivision triangle 21 (1) or 21 (2).

The relative locations of the indices t2, and the low-order bits b, bo of the associated identifiers, of the second-level subdivision triangles 22 (3) (t2) formed in first-level subdivision triangle 21 (3) differ from those formed in triangles 21 (0) through 21 (2). First-level subdivision triangle 21 (3) is rotated by 180 degrees relative to upper-level triangle 20, and the indices t2 and bit patterns blbo of the second level subdivision triangle 22 (3) (t2) are also. That is, for the second-level subdivision triangles 22 (3) (t2), (ix) the second-level subdivision triangle 22 (3) (0) is at the bottom (as shown in FIG. 2) of the first-level subdivision triangle 21 (3), in contrast to the positioning of second-level subdivision triangle 22 (0) (0) at the top in the first-level subdivision triangle 21 (0) (reference item (i) above); (x) the second-level subdivision triangle 22 (3) (1) is at the upper right of the first-level subdivision triangle 21 (3), in contrast to the positioning of the second-level subdivision triangle 22 (0) (1) at the lower left in the first-level subdivision triangle 21 (0) (reference item (ii) above); (xi) the second-level subdivision triangle 22 (3) (2) is at the upper left of the first-level subdivision triangle 21 (3), in contrast to the positioning of the second-level subdivision triangle 22 (0) (2) at the lower right in the first-level subdivision triangle 21 (0) (reference item (iii) above); and (xii) the second-level subdivision triangle 22 (3) (3) is at the middle of the upper half of the first-level subdivision triangle 21 (3), in contrast to the positioning of the second-level subdivision triangle 22 (0) (3) at the middle of the lower half in the first-level subdivision triangle 21 (0) (reference item (iv) above).

It will be appreciated that one or more of the second-level subdivision triangles 22 (t,) (t2) may also be subdivided into respective third-level subdivision triangles (not shown). Each third-level subdivision triangle will be associated with a set of indices (tl) (t2) (t3) (t3=0, 1,2 or 3), with the portion of the sequence (tl) (t2) corresponding to the indices (tj) (t2) that are associated with the second-level subdivision triangle 22 (tl) (t2) from which the respective third level subdivision triangle was formed, and the index (t3) uniquely identifying the respective third-level subdivision triangle within the second-level subdivision triangle 22 (tl) (t2). The locations of the third-level subdivision triangles associated with indices (t1) (t2) (0), (tl) (t2) (1), (t) (t2) (2) and (tl) (t2) (3), relative to the respective second-level subdivision triangle in which they were formed, will depend on the alignment of the particular second-level subdivision triangle in which third-level subdivision triangles have been formed. For example, if the second-level subdivision triangle that has be subdivided is second-level subdivision triangle 22 (0) (0), 22 (0) (1), 22 (0) (2) or 22 (3) (3), all of which have alignments similar to upper level triangle 20, or first-level subdivision triangles 21 (0), 21 (1) or 21 (2), the relative locations of the indices will be similar to that described above in connection with items (v) through (viii) above. On the other hand, if the second-level subdivision triangle that is to be subdivided is second level subdivision triangle 22 (0) (3), 22 (3) (0), 22 (3) (1) or 22 (3) (2), whose alignments are rotated one hundred and eighty degrees relative to the upper-level triangle 20, the relative locations of the indices will be similar to that described above in connection with items (ix) through (xii) above. Each of the third-level subdivision triangles will also be associated with an identifier having a bit pattern b7... bo whose upper five bits b7... b3 correspond to the bit pattern of bits b5... bo of the identifier of the second level subdivision triangle 22 (t,) (t2) in which the respective third-level subdivision triangle was formed, with the binary-encoded value of the two low order bits bjbo corresponding to the value of the index t3 of the respective third-level subdivision triangle.

Subdivision triangles at subsequent levels may also be formed in a similar manner. A subdivision triangle at the"n-th"subdivision level will be associated with an index (tl)... (tn), similar to those indicated in the various reference numerals depicted in FIG. 2. In addition, the subdivision triangle at the"n-th"subdivision level will be associated with an identifier b2nb2n l... bon in which bit b2n has the value "one," and each pair of bits bx+1bx (index x=2n-2, 2n-4,..., 0) that is associated with a level l,..., n will correspond to the binary-encoded value of the particular portion of the index (tl) x for the respective level n--. As with the identifiers for the first-and second-level subdivision triangles 21 (t,), 22 (t,) (t2), each identifier for an n-th level subdivision triangle 22 (t1)... (tn) can be stored in a word by the computer graphics system 10. It will be appreciated that, since two bits bu+, box are required for each subdivision level, and one bit is utilized for the high order b of the identifier, a thirty-two bit word will accommodate identifiers for up to fifteen subdivision levels. In that case, the bit or bits in bit positions b3l... b2n+, will all have the value"zero,"so that bit bu will be the most significant bit in the word having the value"one, "thereby indicating the beginning of the identifier in bit positions bu"... bo As noted above, the invention also provides an arrangement that, given an identifier b2n... bo for a subdivision triangle, generates coordinates of the points defining the subdivision triangle. In the embodiment described herein, the arrangement generates the the barycentric coordinates, relative to the upper-level triangle, of the points defining the respective subdivision triangle. As is well- Imown, if the barycentric coordinates of a point P (not shown) in a plane containing the triangle defined by the three points A, B, C are given by (αA,ßA,#A), (αB,ßB,#B) and (αC,ßC,#C), each of the"a," "ß"and"X"will cor espond to the weighs that correspond to the relative distances from points A, B and C, to the point P, respectively. Thus, for example, the barycentric coordinates of points A, B and C are (1,0, 0), (0,1, 0) and (0,0, 1) respectively. Similarly, the barycentric coordinates of points D, E and F, which, together with points A, B, and C, define the first-level subdivision triangles 21 (tl), are respectively. Similarly, the barycentric coordinates of points G, H, I, J and K, which, together with other points, define the second-level subdivision triangles 22 (tl) (t2), are respectively. It will be appreciated that the barycentric coordinates of point A contains a"one"for the"aA"component of the coordinates and"zero"for the"iA"and"xA"components and similarly for the barycentric coordinates of points B and C. On the other hand, the barycentric coordinates of a point, such as point F, on line segment BC, contains a"zero"for the"aF"component and values for the"PF"and |XF coordinates that indicate the relative distance of the point from points B and C, respectively, and similarly for the barycentric coordinates of points, such as points E and D, on line segments AC and AB, respectively. Since the barycentric coordinates are weights, barycentric coordinates (xa, xß, xX) for any constant value"x"identify the same point as barycentric coordinates (a, ß, x).

As noted above, the barycentric coordinates of points A, B and C, respectively, which defining the top-level triangle in FIG. 2, are (1,0, 0), (0,1, 0) and (0,0, 1), respectively. These three coordinates can be combined into a single three-element triple, with each element of the triple representing the barycentric coordinates of one of the three points A, B and C defining upper level triangle 20 as follows: where the coefficients"1,""0,""0"of the first element"la+Ob+Oc"of the triple in (1) correspond to the barycentric coordinates (1,0, 0) of point A, the coefficients"O,""1,""0"of the second element "Oa+lb+Oc"correspond to the barycentric coordinates (0,1, 0) of point B, and the coefficients"0," "O,""1"of the third element correspond to the barycentric coordinates (0,0, 1) of point C.

The foregoing can be extended to the first-level subdivision triangles 21(t1). As noted above, the barycentric coordinates of points D, E and F, which, together with points A, B, and C define the first-level subdivision triangles 21 (tu), are respectively.

In that case, the triple, analogous to (1) above, that defines the first-level subdivision triangle 21 (0), can be established as follows: where the coefficients"1,""0,""0"of the first element"la+Ob+Oc"of the triple in (2) correspond to the barycentric coordinates (1,0, 0) of point A, the coefficients"1/2,""1/2,""0"of the second element correspond to the barycentric coordinates of point D, and 1 1 the coefficients "1/2", "0", "1/2" of the third element"2a+0b+ 2c"correspond to the barycentric coordinates of point E.

The triple, analogous to (1) above, that defines the first-level subdivision triangle 21 (1), can be established as follows: where the coefficients"1/2,""1/2,""0"of the first element of the triple in (3) correspond to the barycentric coordinates of point D, the coefficients"O,""1,""O"ofthe second element"Oa+lb+Oc"correspond to the barycentric coordinates (0,1, 0) of point B, and the 1 1 coefficients"O,""1/2","1/2"of the third element"Oa+-b+-c"correspond to the barycentric coordinates of point F.

The triple, analogous to (1) above, that defines the first-level subdivision triangle 21 (2), can be established as follows: where the coefficients "1/2," "0," "1/2," of the first element "1/2a + 0b + 1/2c" of the triple in (4) correspond to the barycentric coordinates of point E, the coefficients"0,""1/2","1/2" of the second element correspond to the barycentric coordinates point F, and the coefficients"O,""O,""1"of the third element"Oa+Ob+lc"correspond to the barycentric coordinates (0,0, 1) of point C.

Finally, the triple, analogous to (1) above, that defines the first-level subdivision triangle 21 (3), can be established as follows: where the coefficients"0,""1/2,""1/2,"of the first element of the triple in (5) correspond to the barycentric coordinates of point F, the coefficients"1/2","0,""1/2" of the second element correspond to the barycentric coordinates point E, and the coefficients"1/2","O,""1/2"of the third element"Oa+Ob+lc"correspond to the barycentric coordinates (0,0, 1) of point C.

It will be appreciated that, in each of (1) through (5), and in the following, the terms with coefficients of"0"need not be depicted, although it will be appreciated that the particular variable "a, ""b"or"c"whose coefficient is"0"will represent a"0"in the barycentric coordinates of the point associated with the respective triple. Similarly, a coefficient whose value of"1"need not be depicted. That is, (1) can be depicted as" (a, b, c), " (2) can be depicted as and so forth.

Using the notation as described above, the operation of generating first-level subdivision triangles 21 (tl) can be considered an"action"on upper-level triangle 20, with the actions", A4" being given as Examining equations (6), and with reference to the discussion above in connection with (1) through (5), it will be apparent that, in the first line, the triple represents the barycentric coordinates of points A, D and E, respectively, that define first-level subdivision triangle 21 (0). Similarly, in the second line, the triple represents the barycentric coordinates of points D, B, and F, respectively, that define the first-level subdivision triangle 21 (1).

In the third line, the triple represents the barycentric coordinates and (0, 0, 1) of points E, F, and C, respectively, that define the first-level subdivision triangle 21 (2). Finally, in the fourth line, the triple represents the barycentric coordinates of the points F, E, and D, respectively, that define the first-level subdivision triangle 21 (3). It will be appreciated that, for first-level subdivision triangles 21 (0), 21 (1) and 21 (2), which have a similar alignment as the upper-level triangle 20, the triples that represent the barycentric coordinates of the points defining the first level subdivision triangles are such that the first element of each triple represents the barycentric coordinates of the point A, D and E at the top (as shown in FIG. 2) of the respective subdivision triangle, the second element represents the barycentric coordinates of the point D, B and F at the lower left, and the third element represents the barycentric coordinates of the point E, F and C at the lower right. On the other hand, for first level subdivision triangle 21 (3), the first element of the triple represents the barycentric coordinates of the point F at the bottom, the second element represents the barycentric coordinates of the point E at the upper right, and the third element represents the barycentric coordinates of the point D at the upper left, since the first-level subdivision triangle 21 (3) is rotated by 180 degrees relative to the upper-level triangle 20.

With continued reference to equations (6), for respective actions M=O, 1,2 and 3, the following two-by-two matrices are defined : Examining the matrices Mi (index i=O, 1, 2, or 3) defined in equations (7) it will be apparent that, for each matrix"M,,"the matrix elements comprising the first row in each matrix Mi contain the values (1,0), and the left and right hand matrix elements comprising the second row contains the values corresponding to the coefficients of triples (1,1, 1) and (a, b, c), respectively in equations (6). As will be made apparent below, the subscript"i"for each matrix corresponds to the binary-encoded value of the bit pattern"bx +, bx"of bits of a subdivision triangle's identifier that are associated with a subdivision triangle associated with index (t1)... (tl)... (ton) at a particular subdivision level In the general case, the triple (a, b, c) will not be a multiple of the triple (1,1, 1) (reference equations (6)), that is, they are linearly independent, and so the triples (1, 1, 1) and (a, b, c) (reference equations (6) above) can be considered as bases of a form of pseudo-vector space. With that construction, the triple (1,1, 1) will be deemed to be associated with a basis that will be labeled"el" and the triple (a, b, c) will be deemed to be associated with a basis that will be labeled"eo,"and the pseudo-vector (el, eo) T (where"T"represents the transpose operation) can be formed. If the pseudo- vector (el, eo) T is multiplied by matrices Mi defined in equations (7), the following are obtained: Examining the equations (8) through (11), it will be apparent that, in the pseudo-vector comprising the last line of each equation, the triple in the second row corresponds to the respective triple in equation (6). Thus, as indicated above in connection with equation (8), the multiplication of the pseudo-vector (el, eo) by the matrix Mo that is associated with action M=O provides, in the second row, the triple which, as described above in connection with the first line of equation (6), represents the barycentric coordinates (1, 0, 0), points A, D and E that define the first-level subdivision triangle 21 (0). Similarly, as indicated above in connection with equation (9), the multiplication of the pseudo-vector (el, eo) by the matrix M, that is associated with action M=l provides, in the second row, the triple which, as described above in connection with the second line of equation (6), represent the barycentric coordinates of points D, B, and F that define the first-level subdivision triangle 21 (1). Similarly, the triples in the second rows of the last lines of equations (10) and (11), which describes the multiplication of the pseudo-vector (el, eo) by the matrices M2 and M3 that are associated with actions M=2 and M=3, respectively, provide triples which, in turn, represent the barycentric coordinates and (0,0, 1) ofpoints E, F and C, and of points F, E, and D, which define first-level subdivision triangles 21 (2) and 21 (3) respectively.

The creation of a set of second-level subdivision triangles 22 (tl) (t2) in a first-level subdivision triangle 21 (tl) can similarly be considered an action on the first-level subdivision triangle 21 (tl), and the matrices Mi can be used in a similar manner to obtain the coordinates of the points defining the second-level subdivision triangles 22 (t,) (t2). This will be apparent from the following. For example, considering the second-level subdivision triangles 22 (0) (t2) formed in first-level subdivision triangle 21(0), the matrices M0 and Mi (i=0,..., 3) can be multiplied together and applied to the pseudo-vector (el, eo) with following results: Examining the equations (12) through (15), it will be apparent that, in the pseudo-vector comprising the last line of each equation, the triple in the second row provides the coordinates of the points defining the second-level subdivision triangles 22 (0) (0), 22 (0) (1), 22 (0) (2) and 22 (0) (3), respectively. For example, from equation (12), the triple represents the barycentric coordinates of the points A, H and I, respectively, which define the second-level subdivision triangle 22 (0) (0). Similarly, the triple from equation (13) represents the barycentric coordinates of points H, D and G, respectively, which define the second-level subdivision triangle 22 (0) (1), the triple from equation (14) represents the barycentric coordinates of points I, G and E which define the second-level subdivision triangle 22 (0) (2), and the from equation (15) represents the barycentric coordinates of points G, I and H, respectively, which define the second-level subdivision triangle 22 (3).

As noted above, second level subdivision triangles 22 (tl) (t2) can be formed in the first-level subdivision triangles 21 (1), 21 (2) and 21 (3). In the case of second-level subdivision triangles 22 (1) (t2) formed in first level subdivision triangle 21 (1), the barycentric coordinates of the points defining the second-level subdivision triangles 22 (1) (t2), relative to points A, B and C defining the upper-level triangle 20, can be determined using Similarly, in the case of second-level subdivision triangles 22 (2) (t2) formed in first level subdivision triangle 21 (2), the barycentric coordinates of the points defining the second-level subdivision triangles 22 (2) (t2), relative to points A, B and C defining the upper-level triangle 20, can be determined using It will be appreciated that, for each value of index"i, "the relative positions of the second-level subdivision triangles 22 (1) (t2) and22 (2) (t2) in the first level subdivision triangles 21 (1) and 21 (2) will be the same as the positions of the second level subdivision triangles 22 (0) (t2) in the frst level subdivision triangle 21 (0). That is, the for"i"equal to"zero, " provide the barycentric coordinates of the second-level subdivision triangles 22 (1) (0) and 22 (2) (2) (not shown in FIG. 2) comprising the upper half (as shown in FIG. 2) of the first-level subdivision triangles 21 (1) and 21 (2), respectively, which is the same position as second level subdivision triangle 22 (0) (0) relative to first level subdivision triangle 21 (0). Similarly, for"i"equal to"one," provide the barycentric coordinates of the second-level subdivision triangles 22 (1) (1) and 22 (2) (1) (not shown in FIG. 2) toward the left of the lower half (as shown in FIG. 2) of the first-level subdivision triangles 21 (1) and 21 (2), respectively, which is the same position as second level subdivision triangle 22 (0) (1) relative to first level subdivision triangle 21 (1). Similarly for other values of index"i." Similarly, in the case of second-level subdivision triangles 22 (3) (t2) formed in first level subdivision triangle 21 (3), the barycentric coordinates of the points defining the second-level subdivision triangles 22 (3) (t2), relative to points A, B and C defining the upper-level triangle 20, can be determined using In this case, however, for"i"equal to"zero," provides the barycentric coordinates of the points defining the second-level subdivision triangle 22 (3) (0) comprising the lower half (as shown in FIG. 2) of the first-level subdivision triangle 21 (3). Similarly, for"i"equal to"one,"to"three," provides the barycentric coordinates of the points defining the second-level subdivision triangle 22 (3) (1), provides the barycentric coordinates of the points defining the second-level subdivision triangle 22 (3) (2), and provides the barycentric coordinates of the points defining the second-level subdivision triangle 22 (3) (3), as can be seen from the following: and Examining the equations (16) through (19), it will be apparent that, in the pseudo-vector comprising the last line of each equation, the triple in the second row provides the coordinates of the points defining the second-level subdivision triangles 22 (3) (0), 22 (3) (1), 22 (3) (2) and 22 (3) (3), respectively. For example, from equation (16), the triple represents the barycentdc coordinates of the points F, K and J, respectively, which define the second-level subdivision triangle 22 (3) (0). Similarly, the triple from equation (17) represents the barycentric coordinates of points K, E and G, respectively, which define the second-level subdivision triangle 22 (3) (1), the triple from equation (18) represents the barycentric coordinates of points J, G and D which define the second- level subdivision triangle 22 (3) (2), and the triple from equation (19) represents the barycentric coordinates of points G, J and K, respectively.

Barycentric coordinates of subdivision triangles at third and subsequent levels can be determined in a similar manner using matrices Mo through M3. That is, if a subdivision triangle is at the"n-th"subdivision level, the barycentric coordinates of the three points that define the subdivision triangle, relative to the upper-level triangle 20, can be recovered using where, for each matrix the superscript refers to the subdivision level l,..., n, and the subscript refers to the particular matrix Mi (i=O, 1,2 or 3) that is to be applied for the respective subdivision level. As noted above, the subscript"i"for each matrix corresponds to the binary- encoded value of the bit pattern"b,,, b,," of a subdivision triangle's identifier that is associated with a subdivision triangle associated with index (tl)... (t1)...(tn) at a particular subdivision level x l = n - @/2. That is, for an identifier having a bit pattern b2n... b,, Ib,,... bo (x=2n-2, 2n-4,...) for a subdivision triangle at a particular"n-th"level, where bX+lbx are the bits of the identifier associated with the portion of the subdivision triangle's index (tl), with the pair of bits in bit positions bx+1bx of the index being associated with that subdivision level identifies which of matrices M ; (reference equation (7) ) is to be applied at that subdivision triangle in recovering the barycentric coordinates of the points defining the subdivision triangle..

The matrix product Mil1 ... Minn can be generated iteratively. Examining equations (8) through (19), it will be apparent that, if the result of multiplying the matrices through"I"subdivision levels is where the sign of the lower right-hand matrix element may be either positive or negative (the determination of the sign will be described below), if the matrix product Ml multiplies matrix Mo, the result is It will be appreciated that, in equation (21), if there is to be a subsequent"1+2d"iteration, which will be the case if level/+ 1 g n, then αl+1 = 2α1 ~ 1, ßl+1 = 2ß and #l+1 = 2#l for use in the next "l+2d"iteration. Equation (21) indicates that the result is that, for the "l+1-st" iteration, (a) the values in the first row are unchanged, that is, the left-hand matrix element has the value"one"and the right hand matrix element has the value"zero;" (b) for the values in the second row, (i) the value of the left hand matrix element is the sum or the difference of the left hand a matrix element generated during the"I-th"iteration, and ; if the sign of the matrix element on the right hand side of the second row of MI that was generated during the"I-th"iteration is positive, the result will be the sum, but if the sign of the matrix element on the right hand side of the second row generated during the"I-th" iteration is negative, the result will be the difference, and (ii) the value of the right hand matrix element is the product of the right hand matrix 1 element generated during the"I-th"iteration and 2 Corresponding results will be generated for Ml Ml and Ml M2. Accordingly, with reference to the second row of equation (21), in the left-hand matrix element, the numerator is still a polynomial in"a, ""b"and"c,"and with the denominator the"I+l-st"power of"two."In addition, in the right-hand matrix element, the denominator is the"I+l-st"power of"two, "and the sign will be the same as for the"I-th"iteration.

On the other hand, if the matrix product MI multiplies the matrix M3, the result is It will be appreciated that, in equation (22), if there is to be a subsequent"1+2d"iteration, the αl+1 = 2α1 ~ 1, ßl+1 = 2ßl ~ 1 and #l+1 = 2#l ~ 1 for use in the next "l+2d" iteration. Equation (22) indicates that the result is that, for the"1+1-st"iteration, (c) the values in the first row are unchanged, that is, the left-hand matrix element has the value"one"and the right hand matrix element has the value"zero;" (d) for the values in the second row, (i) the value of the left hand matrix element is either the sum or the difference of the left a+b+c hand matrix element generated during the"I-th"iteration, and ; if the sign of the matrix element on the right hand side of the second row of MI generated during the "l-th" iterastion is positive, the result will be the sum, but if the sign of the matrix element on the right hand side of the second row generated during the"I-th" iteration is negative, the result will be the difference, and (ii) the value of the right hand matrix element is the product of the right hand matrix - 1 element generated during the"I-th"iteration multiplied by-.

Accordingly, with reference to the second row of equation (22), in the left-hand matrix element, the numerator is still a polynomial in"a,""b"and"c,"and with the denominator the"1+1-st"power of "two. "In addition, in the right-hand matrix element, the denominator is the"1+1-st"power of "two, "and the sign will be the opposite as for the previous"l-th"iteration.

Thus, after "n"iterations, the matrix product Ml1... Mlnn is given by where, in the second row, l''and"X""in the left hand matrix element and the sign of the right hand matrix element are generated as described above in connection with equations (20) through (22).

Moreover, further examining equations (8) through (19), it will also be appreciated that, after the matrix product Ml....'2 has been generated as described above in connection with equations (20) through (23), the left hand matrix element of the second row multiplies the basis vector el, that is" (1, 1, 1)," and the right hand matrix element multiplies the basis vector eo, that is" (a, b, c)," and the products are combined. Comparing equations (8) through (19) and equations (6), the el basis vector enables a triple to be formed all of whose elements correspond to the left hand matrix element of the second row. That is, The eo basis vector" (a, b, c") enables the right hand matrix element of the second row to be added to the"a"term of the first element of the triple, the"b"term of the second element of the triple, and the "c"term of the third element of the triple, that is as is evident from equations (6), with the sum being used if the sign of the right hand matrix element of the second row of the matrix product Mi1l... Minn is positive, and the difference being used if the sign is negative. Examining equation (25), it will be appreciated that the barycentric coordinates of the points defining the subdivision triangle, relative to the upper level triangle 20, correspond to It will be appreciated that, in view of the discussion above in connection with equations (21) and (22), it is unnecessary to generate the actual matrix products MI, but instead it will be sufficient to generate the values for the matrix elements for the second row. This can also be accomplished in an iterative manner, as will be described below.

As noted above, an identifier b2n... bo can be stored as a fixed-length word in the computer graphics system 10. In that case, the word in which the identifier is stored can have one or more high-order bits (that is, bits in bit positions bmsv... bz"+, (where"msb"refers to"most significant bit) to the"left"of bit bu in the word) all of which have the value"zero, "followed by the bits in bit positions b2n... bo comprising the identifier itself. The bit in bit position b2n, which, as described above, always has the value"one, "will identify the high-order bit of the identifier. The binary- encoded value of each subsequent pair of bits "b2n-1b2n-2," "b2n-3b2n-4,"..., "b1b0" in the identifier will identify the particular matrix Mi (equations (7) ) that is to be applied for a particular subdivision level to facilitate the recovery of the barycentric coordinates, relative to the upper level triangle 20, of the subdivision triangle that is associated with the identifier. In determining the barycentric coordinates, the computer graphics system 10 can make use of variables, represented here by"a,""b"and"c," "sign" and an iteration index"i."The variables"a, ""b"and"c"will be used to keep track of the values of the coefficients"aZ,""ßl"and"X/,"respectively, for the left-hand matrix of the second row of the matrix Ml. The variable"sign"will be used to keep track of the sign of the right-hand element in the second row of the matrix MI. If the value of the variable"sign"is positive"one, " the sign of the matrix element is positive, and if the value of the variable"sign"is a negative"one, the sign of the matrix element is negative. It will be appreciated that the number of iterations will correspond to the number"n"of subdivision levels. The computer graphics system-will initialize the variables"a, ""b"and"c"to the value"zero,"and the variable"sign"to positive"one. "After determining the number"n"of subdivision levels, the computer graphics system will initialize the iteration index"i"to"n-l."It will be appreciated that, after initialization, "2i"identifies the bit position b2n2, which, in turn, corresponds to the low-order bit of the pair of bits b2n-1b2n-2 corresponding to the index t, of the subdivision triangle.

During each of"n"iterations the computer graphics system 10 performs several operations, namely (i) using the binary-encoded value ofthe pair of bits in bit positions b2i+lb2i tha-t are associated with the subdivision level, the computer graphics system 10 determines which of the matrices Mo, MI, M2 or M3 (reference equations (7) ) is to be associated with the iteration; (ii) the computer graphics system 10 updates the appropriate variable"a,""b"and/or"c" based on the determination in step (i), that is, (A) if the computer graphics system determines in step (i) that the matrix Mo, M, or M2 is to be applied during the iteration, which will be the case if the binary-encoded value of the bits b2i+1b2i, is zero, one or two, respectively, the computer graphics system updates variable "a," "b" or "c," respectively by adding the value "sign/2n-i" thereto (reference item (b) (i) immediately above, recognizing that the value of the exponent"n-i"in the denominator here corresponds to the value of exponent "l + 1"in the denominator of item (b) (i) immediately above), but (B) if the computer graphics system determines in step (i) that the matrix M3 is to be applied for the iteration, which will be the case if the binary-encoded value of the bits b2i+1b2 is"three,"the computer graphics system updates all three variables"a, ""b"and"c"by adding to each the value sigz "2, ?," (reference item (d) (i) immediately above), and (II) updates the variable"sign"by multiplying it by"-1,"that is, by complementing the sign (this will be used in connection with item (d) (ii) immediately above); (iii) the computer graphics system decrements the index"i"and, if the value of index"i"is positive or zero, it returns to step (i), but if the value of index"i"is less than zero, it proceeds to step (iv); it will be appreciated that, if the value of index"i"is positive or zero, "2i"identifies the bit position of the low-order bit b2n-4, b2n-6,... b0 of the bit pair b2i+1b2i corresponding to the index t2, t3,... tn of the subdivision triangle.

After the computer graphics system has performed steps (i) through (iii) through the"n"iterations, referencing equation (23), the values of variables"a,""b"and"c"will correspond to the values of "αn," "ßn" and "#n," respectively. Thereafter, the computer graphics system combines the 2n 2n 2n information related to the left and right hand matrix elements of the second row of the matrix product Mil... Minn to generate the barycentric coordinates, as follows: (iv) the computer graphics system generates a value for a variable"fze"as"2"," (v) the computer graphics system generates a tripl e (the semi-colons delimiting the three elements of the triple) using the values for"a, ""b"and"c"generated in steps (i) through (iii) (reference equation (24) above); and (vi) the computer graphics system adds the value "sign/@" to "αn/@" in the first element of size 2n the triple, to in the second element of the triple, and to"X"in the third element of the triple (reference equation (25) above), thereby to combine the two matrix elements comprising the second row.

It will be appreciated that "2n," the value of variable"size,"that is generated in step (iv) above corresponds to the denominator in the right hand matrix element in the second row of the matrix product Mi1... Minn. Similarly, thevalue of"sign,"whichmaybe either"positive one"or"negative one"at the end of the iterations described above in connection with steps (i) through (iii), corresponds to the numerator of the right hand matrix element of the matrix product Mi'... M" <BR> <BR> <BR> <BR> <BR> <BR> sign 1 a<BR> <BR> <BR> <BR> Thus, adding the value in step (vi) is corresponds to adding the value to in the<BR> "size" "2n" "2n" first element of the triple, to "ßn/2n" in the second element, and to "#n/2n" in the third element if the value of "sign" is positive, and subtracting the value 1/2n if the value of "sign" is negative, as described above in connection with equation (25). Accordingly, step (vi) corresponds to the step of combining the two matrix elements in the second row, as described above in connection with equation (25). Thus, the result following step (vi) is the triple that defines the barycentric coordinates comprising the first element of the triple, comprising the second element of the triple, and comprising the third element of the triple, relative to the upper level triangle 20, of the three points defining the subdivision triangle associated with the respective identifier. FIG. 3 is a flow chart depicting operations performed by the computer graphics system in connection with the steps (i) through (vi) described above.

As noted above, in one particular embodiment, instead of performing the specific operations described above in connection with steps (i) through (iii), which would require use of floating-point arithmetic, the computer graphics system 10 can make extensive use of integer arithmetic, which can <BR> <BR> <BR> <BR> <BR> sign 1<BR> <BR> <BR> <BR> simplify the operations and speed up processing during those steps. Since 2n-i = 2n sign*2i, and since the value of divisor"2n"depends only on"n, "the number of subdivision levels, instead sign of adding the value"2nz_1"during each iteration, which would require that the variables"a,""b" and"c"be floating point numbers and floating-point arithmetic be used to generate the value <BR> <BR> <BR> <BR> <BR> sign<BR> <BR> <BR> "2l t"for addition to the respective variable (s), the computer graphics system can add the value "sign*2i" to the respective variable (s) during each iteration. It will be appreciated that if sign * 2'"is an integer, in which case the variables"a, ""b"and"c"can be integers and the iterations can be performed using integer arithmetic. It will also be appreciated that"2"" corresponds to the value of the variable"size,"which is generated in step (iv). Accordingly, after the computer graphics system 10 has completed the"n"iterations, it can generate the value for variable"size" (step (iv) ), divide the variables"a, ""b"and"c"by the value of that variable"size," and proceed to step (v). In that case, only steps (v) and (vi) would make use of floating point arithmetic.

Code Segment 1 depicts a code segment in the C programming language for generating the barycentric coordinates of a subdivision triangle with the above considerations.

Code Segment 1 (1) sign = 1 (2) a=b=c=0 (3) for (i = n-l ; i >= 0 ; i--) { (4) switch ((code#(i#1))&3) { (5) case 0: (6) a +=sign*(1#i) (7) break ; (8) case 1: (9) b += sign* (1#i) (10) break; (11) case 2: (12) c += sign* (l<<i) (13) break; (14) case 3: (15) a +=sign*(1#i) (16) b += sign* (l<<i) (17) c += sign* (l<<i) (18) sign *= (-1) ; (19) break; } } (20) size = 1#n (21) bary_O_a = bary_l_a = bary_2_a = a/size ; (22) bary0b = bary_1_b = bary_2_b = b/size; (23) bary_0_c = bary_l_c = bary_2_c = c/size ; (24) bars 0 a += sign/size; (25) barylb += sign/size; (26) bary_2_c += sign/size; In Code Segment 1, it is assumed that a word"code"has been provided to the computer graphics system. The word"code"comprises a multiple-bit word including an identifier for the subdivision triangle whose barycentric coordinates are to be generated in bit positions b2n... bo. The word"code"may also have bits in more significant bit positions b", Sb... b2n+, (where"msb"refers to "most significant bit"of the word), all of which have the value"zero. "It is also assumed in Code Segment 1 that the bit position"2n"of the highest-order bit b2n in the word"code"that has the value "one"has been determined. Further it is assumed in Code Segment 1 that"n, "the number of subdivision levels, has also been determined. It will be appreciated that the number of subdivision levels"n"can be determined in relation to the bit position b2n of the highest order bit that has the value"one." With reference to the Code Segment 1, lines (1) and (2) enable the variable"sign"and the variables"a, ""b"and"c"to be initialized.

The portion of Code Segment 1 comprising lines (3) through (19) relates to steps (i) through (iii) described above. As will be apparent to those skilled in the art, the portion of Code Segment 1 comprising lines (3) through (19) can be performed using integer arithmetic. As noted above, steps (i) through (iii) are performed in a loop comprising one or more iterations, and Line (3) is the beginning of the loop. The loop is indexed by variable"i, "and in line (3), the portion"i=n-l" enables the variable"i"to be initialized to correspond to"n-l."As noted above, "n"corresponds to the number of subdivision levels for the subdivision triangle that is associated with the identifier that is contained in the word"code."The"i--"portion of line (3) enables the value of variable"i"to be decremented by"one"at the end of each iteration. The"i >= 0"portion of line (3) specifies the loop termination criterion, as will be described below.

Line (4) controls the selection of one of four code fragments, identified as"case 0" comprising lines (5) through (7), "case 1"comprising lines (8) through (10), "case 2"comprising lines (11) through (13), and case (3) comprising lines (14) through (19), that is is to be executed during the respective"i-th"iteration. It will be appreciated that, in each"case c," (c=O, 1,2 or 3) the value of"c"corresponds to the binary-encoded value of a bit pair bX+, bx from the word"code"that will be used for the iteration. As will be clear from the following, in each"case c, "the value of"c" is associated with the value of the subscript of the particular matrix M, (reference equations (7) ) that is to be applied during the iteration. If the binary-encoded value of the bit pair bX+lbx is"zero", the code fragment"case 0"is to be executed during the iteration; if the binary-encoded value is"one," code fiagment"case 1"is to be executed during the iteration; if the binary-encoded value is"two," code fragment"case 2"is to be executed during the iteration; and, if the binary-encoded value is "three, "code fragment"case 3"is to be executed during the iteration.

Line (4) controls the selection of the code fragment that is to be executed in the following manner. First, the"i<<l"portion of line (4) enables the bits of the word defining the loop index"i" to be shifted to the left, that is, toward more significant bit positions, by one bit position. This serves to multiply the value of"i"by"two."As noted above, "i"is initialized to"n-l,"which is"one"less than the number"n"of subdivision levels associated with the subdivision triangle whose barycentric coordinates are to be determined. Thus, if the number of subdivision levels associated with a subdivision triangle is fifteen, the value of"i"will be initialized to fourteen for use during the first iteration. In that case, the"i<<l"portion of line (4) will provide the value"twenty-eight. "Similarly, if the value of"i"is thirteen, the"i<<l"portion of line (4) would provide the value"twenty-six." This may occur if, for example, the subdivision triangle is at level fourteen, in which case the value of"i"will be initialized at the value"thirteen"for use during the first iteration. On the other hand, this may occur if, for example, the subdivision triangle is at level 15 and the value of"i, "after being initialized at the value"fourteen, "has been decremented to the value"thirteen"for use during a second iteration. Corresponding values will be generated for the"i<<l"portion of line (4) for various values of"i." As noted above, the word"code"refers to the word containing the identifier for the subdivision triangle. Continuing with line (4), the"code »" portion of line (4) enables the bits of the word"code,"including the identifier, to be shifted to the right, that is, toward less-significant bit positions. The number of bit positions that the bits will be shifted corresponds to the value generated in response to the"i<<l"portion of line (4). Thus, if, for example, the value of"i"is fourteen, which may occur if, as noted above, the number of levels associated with the subdivision triangle is fifteen, the"code>>"portion of line (4) enables the word"code"to be shifted twenty-eight bit positions toward the right. In that case, the bits that were originally in bit positions b29b28 in the word"code" containing the identifier will be shifted to bit positions also in the shifted word. It will be appreciated that these bits will correspond to the (tl) portion of the identifier for a subdivision triangle at subdivision level fifteen. In addition, the bit that was originally in bit position b30, which corresponds to the high-order bit of the word"code"containing the identifier, which indicates the start of the identifier, will be shifted to bit position s2 in the shifted word. The bits that were originally in bit positions b27... bo of the word"code"will be shifted out and will not be represented in the shifted word. Generally, the bits in bit positions s---S3 (where"msb"refers to"most significant bit") of the shifted word will all have the value"zero, "that is, bits having the value"zero" will be shifted into the more significant bit positions as the shift occurs, although since, as will be described below, the shifted word is subsequently bit-wise ANDED with a mask word, the bits in bit positions smSb... s3 of the shifted word may take on any value.

On the other hand, if the value of"i"is thirteen, the bits that were originally in bit positions b27b26 of the word"code"containing the identifier, will be shifted to bit positions s, So in the shifted word. It will be appreciated that these bits correspond to the (t,) portion of the identifier for a subdivision triangle at subdivision level fourteen, and the (t2) portion of the identifier for a subdivision triangle at subdivision level fifteen. If the subdivision triangle is at subdivision level fourteen, the high-order bit of the identifier, which indicates the start of the identifier, was originally in bit position b28 of the word"code"and will be shifted to bit position s2 of the shifted word. On the other hand, if the subdivision triangle is at subdivision level fifteen, the high-order bit of the identifier, which was originally in bit position b30 of the word"code"will be shifted to bit position S4 of the shifted word, and the bits of the identifier that were originally in bit position b29b28 in the word"code,"which correspond to the (tl) portion of the identifier, will be shifted to bit positions s3s2 of the shifted word. The bits that were originally in bit positions b25... bo will be shifted out and will not be represented in the shifted word. Generally, the bits in bit positions Smsb... S5 of the shifted word will all have the value"zero, "that is, bits having the value"zero"will be shifted into the more significant bit positions as the shift occurs, although since, as will be described below, the shifted word is subsequently bit-wise ANDED with a mask word, the bits in bit positions sm5b... s5 of the shifted word may take on any value.

The"code »" portion of line (4) will enable similar shifts of the word"code"to occur for various values of"i." Finally, the"&3"portion of line (4) enables the shifted word to be bit-wise ANDed with a mask word that comprises bits whose binary-encoded value has the value"three. "It will be appreciated that such a mask word has bits in the least significant bit positions memo both of which have the value"one, "with the bits in the higher-order bit positions rn"Sb... m2 ("msb"referring to "most significant bit"position) all having the value"zero. "This operation serves to produce a masked word whose least signficant bit positions two correspond to bits in bit positions s, so of the shifted word, with the bits in the higher-order bit positions WmSb... W2 all having the value"zero."This serves to mask, that is, set to"zero, "any bits in bit positions smsb*,. s2of the shifted word, which may comprise, for example, the bit bn that indicates the beginning of the identifier, and bits in bit positions that are associated with indices tl, t2... for any subdivision levels that have already been processed, as well as any non-zero bits that may have been shifted into the shifted word.

It will be appreciated that the masked word has a binary-encoded value of one of"zero," "one,""two,"or"three."That binary-encoded value corresponds to the value of"c"in"case c" described above, and is used to select one of the code fragments"case 0"comprising lines (5) through (7), "case 1"comprising lines (8) through (10),"case 2"comprising lines (11) through (13), and"case 3"comprising lines (14) through (19), that will be executed during the respective iteration.

Line (4) enables the operations described above to occur during each iteration, for each subdivision level of the subdivision triangle.

As noted above, during each iteration, line (4) enables one of the four code fragments to be selected for processing during the iteration based on the binary-encoded value of the bits in bit positions wlwO of the masked word. As described above, the bits in bit positions wlwo of the masked ,, lb,, of the word"code, "which, in turn, correspond to the index (tj+l) that is associated with the current"i+l-st"subdivision level for the iteration. Thus, if the binary-encoded value of the bits in bit positions b, +Ib,, associated with the current subdivision level is"zero, "code fragment"case 0"is executed. In case 0, the portion of line (6) "1#i" enables the value"2"'to be generated. In that operation, the"1 « i" portion enables a word to be generated whose binary-encoded value is"one, "after which the word is shifted to the left, that is, toward more significant bit positions, by"i"bit positions. It will be appreciated that the word whose binary- encoded value is"one"will have a bit in the least-significant bit position with the value"one,"with the bits in the other bit positions having the value"zero. "As the bit with the value"one"is shifted to each successive higher-order bit position, the binary-encoded value contained in the shifted word is multiplied by"two, "so that, after the bit has been shifted by"i"bit positions, the binary-encoded value contained in the shifted word is"2'."The"sign*"portion of line (6) enables the"2"'to be multiplied by the current value of the variable"sign,"thereby to generate the value"sign * 2'"and the"a +="portion of line (6) enables that value"sigf2'* 2'"to be added to the current value of variable"a." Similarly, if the binary-encoded value of the bits in bit positions bu+, box is"one, "the"case 1" is executed, in which line (9) enables the value"2"'to be generated and multiplied by the current value of the variable"sign,"and the result added to the current value of variable"b."Continuing, if the binary-encoded value of the bits in bit positions bX+, bx is"two,"the"case 2"is executed, in which line (12) enables the value"2"'to be generated and multiplied by the current value of the variable"sign,"and the result added to the current value of variable"c. "The operations that are enabled by the respective code fragments"case 0,""case 1"and"case 2"update the values of variables"a,""b"and"c,"respectively, as described above in connection with equation (21), in particular the left-hand matrix element of the second row, with the proviso that the common factor 1 "-"has yet to be applied.<BR> <BR> <P> 2 n If the binary-encoded value of the bits in bit positions bX+, bx is"three, "the code fragment "case 3"is executed. In that code fragment, the value"2"'is multiplied by the current value of the variable "sign," with the result being added to the current values of all variables"a,""b"and"c" (reference lines (15) through (17) ). Thereafter, the value of the variable"sign"is negated (reference line (18)) for use in the next iteration, if any. Code fragment"case 3"updates the values of variables "a,""b,""c"and"sigf."as described above in connection with equation (22), in particular the left- 1 hand matrix element of the second row, also with the proviso that the common factor"2}"has yet to be applied.

As noted above, line (3) controls the Code Segment 1 to enable the operations described above in connection with lines (4) through (19) to be executed through a number of iterations, the number corresponding to the number of subdivision levels associated with the subdivision triangle associated with"code. "Returning to line (3), and as noted above, line (3) enables the variable"i" to be initialized to correspond to"n-l,"that is, "one"less than the number"n"of subdivision levels associated with the word"code, "and the value of variable"i"to be decremented by"one"at the end of each iteration. Accordingly, if, for example, the word"code"is associated with a subdivision triangle at level fifteen, for the fifteen iterations the value of"i"will sequence from"fourteen"to through"zero, "At the end ofthe fifteenth iteration, the value of"i"will be decremented to"negative one. "On the other hand, if the word"code"is associated with a subdivision triangle at level fourteen, for the fourteen iterations the value of"i"will sequence from"thirteen"through"zero,"and similarly with subdivision triangles at other subdivision levels. The portion of line (3) "i >= O", which, as noted above, specifies the loop termination criterion, indicates that iterations are to be performed while the value of"i"is either positive or zero, and so, when, in the"n-th"iteration,"i" is decremented to a value below"zero, "line (3) enables iterations to cease. At that point, control will sequence to line (20) of Code Segment 1.

The portion of Code Segment 1 comprising lines (20) through (26) relates to steps (iv) through (vi) described above, and is the only portion of the Code Segment 1 that makes use of floating-point arithmetic. Line (20) of Code Segment 1 enables the generation of the common divisor"2 which is assigned to the variable"size."Lines (21) through (23) of Code Segment 1 enable the initialization of the components of the triple that is to be generated for the barycentric coordinates of the points defining the subdivision triangle. Line (21) enables the first"a"-related component of all of the elements of the triple to be initialized, line (22) enables the second"&num "- related component of all of the elements to be initialized and line (23) enables the third""-related component of all of the elements to be initialized. As is apparent from the description above relating to the second lines of equations (8) through (19), in particular the portion relating to the portion of the computation associated with the basis vector el= (1, 1, 1) described above in connection with equation (24), the portion relating to the computation with basis vector el= (l, 1, 1) provides a triple comprising three elements, all of which have the same value for the first component, the same value for the second component and the same value for the third component. Variables bary_O_a, α bary_l_a and bary2a comprise the first component (referred to as"Ln"above in connection with equation (24)) of the first, second and third element, respectively, of the triple. Similarly, bary_O_b, barylb and bary_2_b comprise the second component (referred to as") 8""above in connection with equation (24)) of the first, second and third element, respectively, of the triple, and bary_0_c, <BR> <BR> <BR> <BR> <BR> bary_1_c and bary_2_c comprise the third component (referred to as "#n/2n" above in connection with equation (24) ) of the first, second and third element, respectively, of the triple, thereby facilitating the performance of step (v) noted above.

Lines (24) through (26) of Code Segment 1 enable the values of the triples that were initialized in lines (21) through (23) to be combined with the portion of equations (8) through (19) relating to the additional computation with basis vector eo= (a, b, c). In that computation, as described Sigf 7 above in connection with equation (25), the value""is added to the first component of the first size element of the triple, the second component of the second element of the triple, and the third component of the third element of the triple, thereby facilitating the performance of step (vi) noted above. Thus, since the value of'sign"is either positive or negative"one, "the result after execution of lines (24) through (26) are values that define the barycentric coordinates (bary_l_a, barylb, barylc) = and (bary_2_ relative to the upper level triangle 20, of the three points defining the subdivision triangle associated with the identifier in that was provided in the variable"code. "It will be appreciated that (i) for the point whose barycentric coordinates are (bary_O_a, bary_O_b, bary_O c) (a) for the subdivision triangles, such as triangles 21 (0), 21 (2) and 21 (3) that have the same alignment as the upper level triangle 20, the point will be at the top of the respective triangle, such as points A in triangle 21 (0), D in triangle 21 (1) and E in triangle 21 (2), but (b) for the subdivision triangles, such as triangle 21 (3) that has an alignment rotated one hundred and eighty degrees relative to the upper level triangle 20, the point will be at the bottom of the respective triangle, such as point F in subdivision triangle 21 (3); (ii) for the point whose barycentric coordinates are (baryla, barylb, barylc) (a) for the subdivision triangles, such as triangles 21 (0), 21 (2) and 21 (3) that have the same alignment as the upper level triangle 20, the point will be at the lower left of the respective triangle, such as points D in triangle 21 (0), B in triangle 21 (1) and F in triangle 21 (2), but (b) for the subdivision triangles, such as triangle 21 (3) that has an alignment rotated one hundred and eighty degrees relative to the upper level triangle 20, the point will be at the upper right of the respective triangle, such as point E in subdivision triangle 21 (3); and (iii) for the point whose barycentric coordinates are (bary_2_a, bary_2_b, bary_2_c) (a) for the subdivision triangles, such as triangles 21 (0), 21 (2) and 21 (3) that has the same alignment as the upper level triangle 20, the point will be at the lower right of the respective triangle, such as points E in triangle 21 (0), F in triangle 21 (1) and C in triangle 21 (2), but (b) for the subdivision triangles, such as triangle 21 (3) that has an alignment rotated one hundred and eighty degrees relative to the upper level triangle 20, the point will be at the upper left of the respective triangle, such as point D in subdivision triangle 21 (3).

It will further be appreciated that, since the coordinates for each point are barycentric coordinates, the sum of the values of the coordinates for each point equals"one. "That is, for example, for the coordinates of one point, αn ~ 1<BR> t7 + + X"= 1, and similarly for the coordinates of the other points. Accordingly, it will be unnecessary for the computer graphics system to actually perform the calculation to generate a value for one of the variables as described above in connection with Code Segment 1. For example, instead ofproviding a code fragment for case"case 0" (lines (5) through (7) of Code Segment 1) and generating values for bary0a, baryla and bary2a, as described above in connection with. lines (21) and (24), a code segment can be provided with code fragments for two of the three cases, for example, cases"case 1"and"case 2, "in which individual variables are updated. In addition, the <BR> <BR> <BR> code fragment for"case 3"can have lines for updating only variables"b,""c"and"sigf2." Continuing with that example, the code segment will have lines (not shown) that enable the computer <BR> <BR> <BR> <BR> αn # 1<BR> <BR> graphics system to generate the value for bary_0_a, which corresponds to "," as<BR> <BR> 2n "l- (bary0b + bary0c),"which corresponds to Similarly, the computer graphics system can generate the values for bary_1_a and bary-2 a, both of which correspond to "αn/2n," as either "1-(bary_1_b + bary_1_c), which corresponds to "1-(bary_2_b + bary2c),"which corresponds to Alternatively, since the "corresponds and since the values for bary_l_a and bary_2_a both correspond to "αn/2n," after the computer graphisc system has generated the value for sign bary_0_a, it can generate the values for bary_l_a and bary_2_a by subtracting the value" sie from the value generated for bary_0_a.

FIG. 4 depicts a flow chart of operations performed by the computer graphics system 10 in connection with generating identifiers for subdivision triangles for a triangle, given the identifier for the triangle from which the subdivision triangles are to be formed. The operations will be apparent to those skilled in the art from the description above in connection with FIG. 2. It will be apparent that, when subdivision triangles are generated at any level for a triangle, the triangle will be divided into four subdivision triangles, and so the computer graphics system 10 will generate four identifiers, one identifier for each of the subdivision triangles. In the flow chart depicted in FIG. 1, it is assumed that the upper level triangle is associated with an identifier in which the low-order bit bo in the word containing the identifier is set to the value"one"as the bit bo of the identifier. In that case, the computer graphics system 10 can, for each subdivision level, generate the identifiers for the respective subdivision triangles by shifting the contents of the word containing the identifier for the triangle that is to be subdivided to the"left"by two bit positions, copying the shifted word into sufficient numbers of storage locations to accommodate the identifiers for the respective subdivision triangles, and providing the appropriate bit values in the least significant bit positions of the word for the index"tn"that is associated with the respective subdivision triangle.

The invention provides a number of advantages. In particular, the invention provides an arrangement for efficiently encoding a subdivision triangle such that its barycentric coordinates can be readily recovered. It will be apparent that the coordinates for a subdivision triangle can be encoded in the identifiers b2n... bo. Accordingly, only one word is needed to specify the coordinates for a subdivision triangle, instead of one word for each of the components of the actual coordinates.

Moreover, it is apparent that the word containing the identifier can be stored as an integer, whereas the words that contain the components of the coordinates will need to comprise floating point numbers.

Another advantage is that the identifiers are spatially coherent. That is, identifiers b2n... bo that are associated with subdivision triangles in an upper-level triangle 20, and whose binary-encoded values are relatively close to one another will also be spatially close, within the upper-level triangle 20.

Furthermore, the methodology, described above in connection with equations (6) through (22) and FIG. 3, for determining the barycentric coordinates of a subdivision triangle using its identifier is efficient, since the coordinates can be recovered in generally constant time.

Moreover, it will be appreciated that, during generation of the subdivision triangles, it is sufficient for the computer graphics system 10 to generate the identifiers for the subdivision triangles as described in connection with FIG. 4; the computer graphics system 10 need not, for example generate the multi-dimensional coordinates for the points that define the respective subdivision triangles at that point. It will be apparent that, when the computer graphics system 10 is generating the identifiers as described above, it is essentially engaged in manipulation of integers, whereas generation of the coordinates of the points that define the respective subdivision triangles would require use of floating-point arithmetic. The computer graphics system 10 can delay generating the coordinates for the points until the operator determines that the actual coordinates of respective ones of the points defining particular ones of the subdivision triangles are required, which may not occur.

It will be appreciated that, once the barycentric coordinates of the three points defining the subdivision triangle at the respective subdivision level have been determined, if necessary the actual the coordinates in multi-dimensional space can be determined using the coordinates (a, b, c) of the points A, B, and C defining the upper level triangle 20 in a conventional manner.

It will be appreciated that a system in accordance with the invention can be constructed in whole or in part from special purpose hardware or a general purpose computer system, or any combination thereof, any portion of which may be controlled by a suitable program. Any program may in whole or in part comprise part of or be stored on the system in a conventional manner, or it may in whole or in part be provided in to the system over a network or other mechanism for transferring information in a conventional manner. In addition, it will be appreciated that the system may be operated and/or otherwise controlled by means of information provided by an operator using operator input elements (not shown) which may be connected directly to the system or which may transfer the information to the system over a network or other mechanism for transferring information in a conventional manner.

The foregoing description has been limited to a specific embodiment of this invention. It will be apparent, however, that various variations and modifications may be made to the invention, with the attainment of some or all of the advantages of the invention. It is the object of the appended claims to cover these and such other variations and modifications as come within the true spirit and scope of the invention.

What is claimed as new and desired to be secured by Letters Patent of the United States is: