Interface and method of interfacing between a parametric modelling unit and a polygon based rendering system

Abstract

An interface for use in a 3-d graphics system comprising a parametric modelling unit for modelling objects as high order surfaces, and a polygon based rendering system for rendering polygon modelled objects for display. The interface comprises an input for receiving data and a subdivision unit coupled to the input for processing the data. The interface includes a converter coupled to the subdivision unit for determining from leaf patch data a first plurality of values representing vertices of tessellating polygons describing the leaf patch, and for determining from sub-leaf patch data a second plurality of values representing the vertices of tessellating polygons describing the sub-leaf patch. The interface also has a combiner, coupled to the converter, for combining the values to form leaf polygon data defining the polygon vertices at a first subdivision level, and an output coupled to the combiner for outputting the leaf polygon data.

1 . An interface for use in a 3-d graphics system comprising a parametric modelling unit for modelling objects as high order surfaces and a polygon based rendering system for rendering polygon modelled objects for display, the interface comprising: 
 a) an input, for receiving data representing at least one high order surface patch;    b) a subdivision unit, coupled to the input, for processing the data to form leaf patch data representing the patch at a first level of subdivision and for further processing the data to form sub-leaf patch data representing the patch at a second level of subdivision;    c) a converter, coupled to the subdivision unit, for determining from the leaf patch data a first plurality of values representing vertices of tessellating polygons describing the leaf patch, and for determining from the sub-leaf patch data a second plurality of value representing the vertices of tessellating polygons describing the sub-leaf patch;    d) a combiner, coupled to the converter, for combining the first and second plurality of values to form leaf polygon data defining the polygon vertices at the first subdivision level; and    e) an output, coupled to the combiner, for outputting the leaf polygon data.    
     
     
         2 . An interface according to  claim 1 , wherein the combiner is a weighting processor for performing a weighted average of the first and second plurality of values.  
     
     
         3 . An interface according to  claim 2 , further comprising a control unit, coupled to the subdivision unit and to the weighting processor, for controlling processing of the data by the subdivision unit and for generating a fractional value, w, for use by the weighting processor in the weighted average of the first and second plurality of values.  
     
     
         4 . A method of interfacing between a parametric modelling unit and a polygon based rendering system in a 3-d graphics systems, the method comprising the steps of 
 a) receiving data representing at least one high order surface patch;    b) processing the data to form leaf patch data representing the patch at a first level of subdivision;    c) determining from the leaf patch data a first plurality of values representing the vertices of a plurality of tessellating polygons describing the leaf patch;    d) further processing the data to form sub-leaf patch data representing the patch at a second level of subdivision;    e) determining from the sub-leaf patch data a second plurality of values representing the vertices of the plurality of tessellating polygons describing the sub leaf patch;    f) combining the first and second plurality of values to form leaf polygon data defining the polygon vertices at the first subdivision level; and    g) outputting the leaf polygon data.    
     
     
         5 . A method according to  claim 4 , wherein processing the data in step (d) requires a single level of subdivision of the leaf patch data.  
     
     
         6 . A method according to either  claim 4  or  claim 5 , wherein the combination of first and second plurality of values in step (f) is a weighted average.  
     
     
         7 . A method according to  claim 6 , further comprising the step of controlling the processing of data by the subdivision unit and generating a fractional value, w, for use in the weighted average.  
     
     
         8 . An interface for a 3-d graphics system comprising a parametric modelling unit and a polygon based rendering system, the interface comprising: 
 a) an input for receiving data representing at least one high order surface patch, patch subdivision data representing a first level of subdivision required for the patch, and edge subdivision data representing a second level of subdivision required for at least one edge of the patch;    b) a subdivision unit, coupled to the input, for processing the data to form leaf patch data representing the patch at the first level of subdivision and further processing the data to form fan patch data representing the patch at the second level of subdivision;    c) a converter, coupled to the subdivision unit, for determining from the leaf patch data a first plurality of values representing the vertices of tessellating polygons describing the leaf patch and for determining from the fan patch data fan patch values representing vertices of additional tessellating polygons to those represented by the first plurality of values further describing the leaf patch;    d) a combiner, coupled to the converter, for combining the first plurality of values and the fan patch values to form irregular leaf polygon data defining the vertices of an irregular pattern of tessellating polygons at the first subdivision level; and    e) an output, coupled to the combiner, for outputting the irregular leaf polygon data.    
     
     
         9 . An interface according to  claim 8 , further comprising a control unit, coupled to the subdivision unit, for controlling the processing of the data by the subdivision unit to subdivide the patch in a first direction to the required level in the first direction and to subsequently subdivide the patch in a second direction to the required level in the second direction.  
     
     
         10 . A method of interfacing between a parametric modelling unit and a polygon based rendering system in a 3-d graphics system, the method comprising the steps of: 
 a) receiving data representing at least one high order surface patch, patch subdivision data representing a first level of subdivision required for the patch, and edge subdivision data representing a second level of subdivision required for at least one edge of the patch;    b) processing the data to form leaf patch data representing the patch at the first level of subdivision;    c) determining from the leaf patch data a first plurality of values representing the vertices of tessellating polygons describing the leaf patch;    d) further processing the data to form fan patch data representing the patch at the second level of subdivision;    e) determining from the fan patch data fan patch values representing vertices of additional tessellating polygons to those represented by the first plurality of values, the additional tessellating polygons further describing the leaf patch;    f) combining the first plurality of values and the fan patch values to form irregular leaf polygon data defining the vertices of an irregular pattern of tessellating polygons at the first subdivision level; and    g) outputting the irregular leaf polygon data.    
     
     
         11 . A method according to  claim 10 , further comprising the step of controlling the processing of the data by the subdivision unit to subdivide the patch in a first direction to the required level in the first direction and to subsequently subdivide the patch in a second direction to the required level in the second direction.  
     
     
         12 . An interface for a 3-d graphics system comprising a parametric modelling unit and a polygon based rendering system, the interface comprising: 
 a) an input for receiving data representing at least one high order surface patch;    b) an input multiplexer, coupled to the input, for rearranging the data;    c) a subdivision unit, coupled to the input multiplexor, for processing the data to form interim data representing one portion of the patch at a level of subdivision in a first subdivision direction;    d) an output multiplexer, coupled to the subdivision unit, for arranging the interim data to form leaf patch data representing the required portion of the patch in the required direction at the level of subdivision;    e) a control unit, coupled to the input multiplexor and to the output multiplexor, for controlling the rearrangement of the data and the arrangement of the interim data to allow generation of the required portion of the patch in the required direction;    f) a polygonisation processor, coupled to the output multiplexor, for determining leaf polygon data representing the vertices of tessellating polygons describing the required portion of the patch at the level or subdivision in the required direction; and    g) an output, coupled to the polygonisation processor, for outputting the leaf polygon data.    
     
     
         13 . An interface according to  claim 12 , wherein the subdivision unit comprises four subcalculation units, coupled in parallel to the input and output multiplexers and to the control unit, each subcalculation unit processing a quarter of the data to form a quarter of the interim data and wherein the control unit selects from the data the quarter of data for processing by each subcalculation unit.  
     
     
         14 . An interface according to  claim 13 , wherein each subdivision unit comprises: 
 a) a first calculation stage, coupled to the input multiplexor for receiving data comprising four values A n−1 , B n−1 , C n−1  and D n−1  and coupled to second and fourth calculation stages, the first calculation stage comprising three adders for performing in parallel the additions:      P=A   n−1   +B   n−1 ;  Q=B   n−1   +C   n−1 ;  R=C   n−1   +D   n−1 ;    and for outputting P to the fourth calculation stage and P, Q and R to the second calculation stage;    b) the second calculation stage, coupled to the first, and fourth calculation stages and to a third calculation stage, comprising two adders for performing in parallel the additions:      S=P+Q;    T=Q+R;      and for outputting S to the fourth calculation stage and S and T to the third calculation stage;    c) the third calculation stage, coupled to the second and fourth calculation stages, comprising one adder for performing the addition:      U−S+T;      and for outputting U to the fourth calculation stage;    d) the fourth calculation stage comprising three dividers for performing in parallel the divisions:      V=P/ 2;  W=S/ 4;  X=U/ 8;     and for outputting V, W and X to an output; and    e) an output, coupled to the first and fourth calculation stages and to the output multiplexor of the subdivision unit, for outputting the quarter interim data A n =A n−1 , B n =V, C n =W and D n =X.    
     
     
         15 . An interface according to any of  claims 12  to  14 , further comprising a recursion buffer coupled to the input multiplexer and to the output multiplexer for storing data representing a root patch and processed data.  
     
     
         16 . A method of interfacing between a parametric modelling unit and a polygon based rendering system in a 3-d graphics system, the method comprising the steps of: 
 a) receiving data representing at least one high order surface patch;    b) rearranging the data;    c) processing the rearranged data to form interim data representing one portion of the patch at a level of subdivision in a first subdivision direction;    d) arranging the interim data to form leaf patch data representing the required portion of the patch in the required direction at the level of subdivision;    e) wherein the steps of rearranging of the data and arranging of the interim data are controlled to generate the required portion of the patch in the required direction;    f) determining leaf polygon data representing the vertices of tessellating polygons describing the required portion of the patch at the level of subdivision in the required direction; and    g) outputting the leaf polygon data;    
     
     
         17 . A method according to  claim 17 , further comprising the steps of separating the data into quarters, processing in parallel the four quarters of data, and assembling the quarter interim data.  
     
     
         18 . A method according to  claim 17 , wherein the processing in each subdivision unit comprises the steps of: 
 a) receiving data comprising four values A n−1 , B n−1 , C n−1  and D n−1 , performing in parallel the additions:      P=A   n—1   +B   n−1 ;  Q=B   n−1   +C   n−1 ;  R=C   n−1   +D   n−1 ;   b) performing in parallel the additions:      S=P+Q;    T=Q+R;     c) performing the addition:    U=S+T;   d) performing in parallel the divisions:      V=P/ 2;  W=S/ 4;  X=U/ 8; and   e) outputting the quarter interim data A n =A n−1 , B n =V, C n =W and D n =X.    
     
     
         19 . A method according to  claim 18 , further comprising the step of storing data representing a root patch and processed data for reducing the processing time.  
     
     
         20 . An interface substantially as hereinbefore described with reference to any of FIGS.  6  to  17 .  
     
     
         21 . A method of interfacing between a parametric modelling unit and a polygon based rendering system substantially as hereinbefore described with reference to any of FIGS.  6  to  17 .  
     
     
         22 . A 3-d graphics system comprising apparatus for determining a surface normal vector for a vertex of a surface patch used in modelling of an object to be shaded by the system, the apparatus comprising: 
 means for subdividing the patch to produce a plurality of sub-patches each having corner vertices;    means for deriving the locations of control points required for derivation of a surface normal for a vertex;    means for deriving a plurality of candidate tangent vectors at a vertex from the control point locations; and    means for deriving a surface normal from the candidate tangent vectors.    
     
     
         23 . A method for determining a surface normal vector for a vertex of a surface patch used in modelling of an object to be shaded in a 3-d graphics system, the method comprising the steps of: 
 subdividing the patch to produce a plurality of sub-patches each having corner vertices;    deriving the locations of control points required for determining a surface normal for a vertex;    deriving a plurality of candidate tangent vectors at a vertex from the control point data; and    deriving a surface normal from the candidate tangent vectors.    
     
     
         24 . A method for determining a surface normal for a vertex according to  claim 23  in which the step of deriving the locations of control points comprises: 
 deriving a first subset of control points along one edge of the patch adjacent to a chosen corner;  
 deriving a second subset of control points along the other edge of the patch adjacent to the chosen corner;  
 deriving a third subset of control points consisting of a control point off-set from the corner of the patch in each of a set of chosen parameter dimensions;  
 wherein the step deriving a plurality of candidate tangent vectors comprises deriving first, second and third candidate tangent vectors from each respective subset of control points and the corner points; and  
 selecting two of the three candidate tangent vectors to derive a surface normal at the chosen corner.  
 
     
     
         25 . A method for determining surface normal vectors for vertexes of a surface patch used in modelling of an object to be shaded in a 3-d graphic system, the method comprising the steps of: 
 deriving surface normals for four corner vertices;    partially subdividing the patch in a first parameter dimension to derive a first subset of control points of a first sub-patch;    partially subdividing in a second parameter dimension to derive a second subset of control points of a second sub-patch;    performing a third partial subdivision to derive a third subset of control points from the first and second subsets of control points;    deriving surface normals for two mid-point vertices using the first subset of control points;    deriving surface normals for the remaining two mid-point vertices from the second subset of control points;    deriving a surface normal for a vertex at the centre of the patch from the third subset of control points.    
     
     
         26 . A method according to  claim 23  and  24  wherein a candidate tangent vector at a corner control point is derived by repeatedly selecting control points from a given subset of control points in any given order; and 
 deriving a first weighted vector by multiplying a chosen control point's components by a weighting component of the corner control point;  
 deriving a second weighting vector by multiplying the components of the corner control point by a weighting vector of a chosen control point;  
 deriving a difference vector between the first and second weighted vectors; and  
 using the difference vector as the candidate tangent vector if it is non-zero, and otherwise progressing to the next control point of the subset.  
 
     
     
         27 . A 3-d graphics system comprising apparatus for determining a surface normal vector for a vertex of a surface patch used in modelling of an object to be shaded by the system substantially as herein described with reference to FIGS.  20 - 24  of the drawings.  
     
     
         28 . A method for determining a surface normal vector for a vertex of a surface patch used in modelling an object to be shaded in a 3-d graphics system substantially as herein described with reference to FIGS.  20 - 24  of the drawings.