In a computer graphics system comprising a computer and a display element operable to receive a display-controlling electrical output from the computer and to generate in response to the display-controlling electrical output a a human-perceptible image, the computer being operable to generate the display-controlling electrical output in response to calculations, executable by the computer, of respective pixel values for respective pixels in the image, each pixel corresponding to a point in the image, the calculations of pixel values being executable by the computer in response to coordinates determined for points defining a subdivision surface for the images,
- a method for generating coordinates for points defining a subdivision surface of an upper level surface element at a predetermined subdivision level from a identifier associated with the subdivision surface, the identifier including a plurality of position codes each identifying a position relative to a higher level, the method comprising:
- A. selecting from the identifier one of the position codes;
- B. determining the position of a subdivision surface associated with the position code relative to a higher level subdivision surface;
- and
- C. executing the selecting and determining through a plurality of iterations, to enable iterative selecting of identifiers associated with successive levels, thereby to enable determining the positions of subdivision surface at successive levels, to the predetermined subdivision level;
- in which the upper level surface element and the subdivision surfaces are triangular;
- in which in at least one level the number of subdivision surfaces in a surface at a higher level is four, the subdivision surfaces being defined by (i) three line segments interconnecting three points that define the surface at the higher level, and (ii) three line segments, each interconnecting (a) a point that defines the surface at the higher level, and (b) a point on the line segment interconnecting the other two points that define the surface at the higher level, the point dividing the line segment according to a selected ratio;
- in which the ratio is such that the point dividing line segment bisects the line segment;
- and
- in which the determining of relative position includes determining the position of the subdivision surface relative to the upper level surface element in accordance with
- M
- i
- 1
- 1
-
-
- …
-
-
- M
- i
- n
- n
- (
- e
- 1
- e
- 0
- )
- ,
- where
- (i) “n” refers to the subdivision surface's subdivision level relative to the upper level surface element,
- (ii) the superscripts “1 . . . n” refer to successive subdivision levels relative to the upper level surface element,
- (iii) each
- “Misx”
- is associated with the value of the position code “ix” (“x” ranging from “1” to “n”) associated with the “x-th” subdivision level, where
- (a) ix=0, 1 and 2 refer to a position at level “x” refer to a top, lower left and lower right position, respectively, relative to a level “x−1” and an alignment corresponding to an alignment at level “x−1,” and
- (b) ix=3 refers to a lower center position relative to a level “x−1” and an alignment rotated relative to an alignment at level “x−1,”
- (iv) each
- “Misx”
- represents a matrix
- M
- =
- 0
-
- :
-
-
- M
- 0
- =
- (
- 1
- 0
- a
- 2
- 1
- 2
- )
- M
- =
- 1
-
- :
-
-
- M
- 1
- =
- (
- 1
- 0
- b
- 2
- 1
- 2
- )
- M
- =
- 2
-
- :
-
-
- M
- 2
- =
- (
- 1
- 0
- c
- 2
- 1
- 2
- )
- M
- =
- 3
-
- :
-
-
- M
- 3
- =
- (
- 1
- 0
- a
- +
- b
- +
- c
- 2
- -
- 1
- 2
- )
- (v) where e1=(1,1,1)T and e2=(a,b,c)T, the result of
- M
- ?
- 1
-
-
- …
-
-
- M
- ?
- n
-
- (
- e
- 1
- e
- 0
- )
- ?
-
- indicates text missing or illegible when filed
- being a vector containing a triple
- (α1a+β1b+χ1c,α2a+β2b+χ2c,α3a+β3b+Z3c),
- where
- (α1,β1,χ1), (α2,β2,χ2) and
- (α3,β3,χ3)
- comprise barycentric coordinates of the three points defining the subdivision surface relative to the upper level surface element,
- the coordinates of points defining the subdivision surface being surface being usable by the computer to calculate pixel values for the image to generate the display-controlling electrical output, and to enable the display element to display a human-perceptible image in response to the display-controlling electrical output