[go: up one dir, main page]

EP1537537A1 - Method for the analysis and modification of a footprint - Google Patents

Method for the analysis and modification of a footprint

Info

Publication number
EP1537537A1
EP1537537A1 EP03798897A EP03798897A EP1537537A1 EP 1537537 A1 EP1537537 A1 EP 1537537A1 EP 03798897 A EP03798897 A EP 03798897A EP 03798897 A EP03798897 A EP 03798897A EP 1537537 A1 EP1537537 A1 EP 1537537A1
Authority
EP
European Patent Office
Prior art keywords
footprint
resolution
texture elements
block
size
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP03798897A
Other languages
German (de)
French (fr)
Inventor
Thomas Haaker
Roland Richter
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Trident Microsystems (Far East) Ltd
Original Assignee
Philips Intellectual Property and Standards GmbH
Koninklijke Philips Electronics NV
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Philips Intellectual Property and Standards GmbH, Koninklijke Philips Electronics NV filed Critical Philips Intellectual Property and Standards GmbH
Publication of EP1537537A1 publication Critical patent/EP1537537A1/en
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—3D [Three Dimensional] image rendering
    • G06T15/04—Texture mapping
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—2D [Two Dimensional] image generation
    • G06T11/40—Filling a planar surface by adding surface attributes, e.g. colour or texture
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—3D [Three Dimensional] image rendering
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/40—Analysis of texture

Definitions

  • the present invention relates generally to a method of displaying images on a raster display controlled by a computer.
  • the present invention relates to an anisotropic filter mechanism that is required to reconstruct, scale or subject perspective projection to discrete, stored images for display on raster display elements with high quality.
  • the discrete, stored images just mentioned are referred to below as textures.
  • the present invention relates to a method for analyzing and modifying a footprint depending on a defined number of texture elements that are touched by the footprint in a graphics system that provides the texture elements with a resolution.
  • a “footprint” is a perspective projection of a picture element (pixel) of an object onto a curved surface.
  • a “footprint” can be a convex four-sided representation, which is the approximate result of the perspective projection onto a regular texel grid (texture element grid ) of a square picture element (pixel) of an object on a curved surface.
  • Known graphics systems for example OpenGL graphics systems, work in assigning textures to picture elements (pixels) of an object in such a way that one or more texture elements with the desired resolution are assigned to a footprint of a pixel of an object, the footprint being approximated by a square.
  • the disadvantage is that here the approximation is always done by too large or too small a square and the shape of the footprint is not taken into account.
  • For the desired resolution there is a texel size in a texel grid on which the footprint is based.
  • Different MipMap levels exist for predetermined texel sizes. If a resolution is now selected that leads to a texel size for which there is no MipMap with a suitable resolution (level), the texture must be calculated with great effort.
  • the present invention is based on the object of creating an improved method for modifying a footprint.
  • the present invention provides a method for modifying a footprint depending on a fixed number of texture elements that are touched by the footprint in a graphics system that provides the texture elements with a resolution, with the following steps:
  • step (b) determining the resolution of the texture elements associated with the footprint, based on the specified number of texture elements and based on the dimension or shape determined in step (a);
  • step (c) determining whether the graphics system provides texture elements with the resolution specified in step (b),
  • step (cl) if the graphics system provides texture elements with the resolution specified in step (b), maintaining the footprint; and (c.2) if the graphics system does not provide texture elements with the resolution specified in step (b), select the texture elements provided by the graphics system with the corresponding resolution and reduce the size of the footprint in such a way that the number of texture elements that are produced by the Footprint with a reduced size is touched, is substantially equal to or less than the specified number.
  • the present invention teaches instead of the "rough" approximation of the footprint by a square that completely surrounds it or that is contained entirely in the footprint is to optimally distribute a number of available texture elements with a defined resolution and thus also a defined size onto the footprint, in which case the footprint is covered by the texture elements Get texture elements on the footprint.
  • the method according to the invention is used in a graphics system that provides the texture elements with different resolutions, wherein in step (c.2) texture elements with a resolution lower than the specified resolution are selected.
  • the graphics system preferably provides the texture elements with different resolutions in the form of MipMaps of different levels.
  • a rectangle surrounding the footprint is determined in order to determine the resolution in step (b), vertices of the footprint lying on edges of the rectangle. Becomes found that there are no texture elements of a corresponding size, ie resolution, for this rectangle in order to achieve the desired number P, then in a preferred further development of the exemplary embodiment just described, a restriction square is determined which is dependent on that available through the graphics system set resolution and depending on the number of texture elements is defined. Then the size of the footprint is reduced by moving the vertices of the footprint to the edges of the constraint square.
  • the rectangle just described and the square of determination are preferably determined on the basis of an expansion parameter of the footprint, the expansion parameter representing a longitudinal deformation of the footprint.
  • the size of the footprint is reduced until the dimension the edge is less than or equal to the specified dimension.
  • the method according to the invention thus creates a novel approach which, according to one embodiment, can also be controlled by a user in order to analyze and modify a footprint.
  • the method according to the invention enables both the number of texels that are touched by the footprint and the length of the edges of the footprint to be measured. limits.
  • an additional control input signal is provided for this, namely the property parameter (“performance parameter”) P.
  • performance parameter P can be provided by a user.
  • the limitation of the length of the edges of the footprint is determined by a further parameter E max , which is a maximum edge length
  • This parameter E max can be coded, for example, in hardware technology.
  • the advantage of the present invention is that by setting the control input signal P a compromise can be achieved between the recovered / reconstructed image quality (high number of texels used) on the one hand and the processing speed (low number of texels used) on the other.
  • One advantage of delimiting the boundary edges is that the hardware expenditure that is required in subsequent processes for further processing of the footprint can be significantly reduced. Such subsequent processes include, for example, determining the texels covered by the footprint and / or weighting these specific texels. By limiting the edge length, the hardware expenditure associated with these processing steps can be significantly reduced.
  • the data generated by the method according to the invention can be made available to any Texel-oriented raster method.
  • a plurality of so-called image tables with different resolutions which are also referred to as MipMaps, are provided for a texture assigned to the footprint.
  • the size of the texels in a texel grid is determined depending on the size or shape of the footprint and on a desired image quality of the footprint to be displayed be touched by the footprint.
  • the texel size determined in this way it is ascertained whether an image table exists in the plurality of image tables whose assigned texel size corresponds to the specific texel size. If this is the case, then the corresponding image table is used for the representation of the footprint.
  • the size of the footprint is reduced, as described above, so that, depending on the image quality of the footprint, an available image table with a resolution lower than the desired resolution and a corresponding texel size is selected for displaying the footprint.
  • the image quality is preferably determined by the property parameter P, which essentially indicates the number of texels in a texel grid that are touched by the footprint.
  • essentially two approaches or techniques are described in order to limit the number of texels which are used to represent a footprint (depending on the setting of the property parameter P).
  • a suitable MipMap level is calculated based on the expansion information. This then implicitly determines the size of a square texel in the texel grid. This step calculation is based on the actual spatial dimensions and / or on the shape of the footprint.
  • the area of the footprint is reduced by deliberately shrinking the boundaries (edges) of the footprint. This shrinking of the edges or the reduction of the area is based on the shape, the property parameter P and a texel size of the next available image table (MipMap). In the worst case, the next available image table is the original base table itself.
  • the incoming four-sided footprint which is defined by its four vertices, is initially analyzed with regard to its area and / or its shape and / or the spatial dimensions of its edges. This analysis includes the following steps:
  • a clamping box that constrains a linearly shrunk version of the original footprint in such a way that a horizontal width and vertical height of any edge (of the shrunken footprint) does not exceed a predefined limit.
  • This predefined limit value is determined based on the maximum length value for the edges Emax described above.
  • the dimension of the constraint square depends on the expansion parameter and is set such that the number of texels covered by the constraint square does not exceed a limit which is determined by the property parameter P.
  • edge width or edge height not exceed an edge width or edge height, preferably a hardware-coded maximum length E max ,
  • the number of texels covered by the footprint is approximately equal to or less than the number to which the number of these texels has been predetermined by a user
  • the shape of the footprint is retained when a reduction by a MipMap level greater than 0 is selected
  • the method according to the invention is implemented in hardware in the form of a hardware pipeline, which enables accelerated processing of multiple footprints.
  • FIG. 1A and B are a flow chart showing an overview of the method according to a preferred embodiment of the present invention.
  • FIG. 2 shows a representation of the vertex and edge vectors of an exemplary footprint in a texture space
  • Fig. 5 shows an example of the reduction of the footprint.
  • the method according to the invention begins at block 100, in which the data describing the footprint is received.
  • the term footprint is always used, which is a convex four-sided structure, which represents the approximate result of a perspective projection of a square picture element onto a curved surface.
  • the rectangles represent the main processing steps, which are explained in more detail below.
  • the results of the processing steps are stored in data structures which are shown schematically in the parallelograms in FIG. 1. These are used as input signals for the next processing stages.
  • the individual processing steps are described in detail below, with a mathematical vector notation (shown in bold) being chosen to simplify the description.
  • the footprint information provided in block 102 is used to carry out a footprint analysis.
  • this footprint analysis leads to the determination of a direction of rotation d of the footprint, which is provided in block 106 and is provided in block 108 at an output.
  • the footprint analysis in block 104 yields the expansion parameter t, which is provided in block 110.
  • a restriction quantity c 0 is calculated in block 114, which is provided in block 116.
  • the property parameter P defines the number of texels that are touched or covered by the footprint.
  • a calculation of the required MipMap level is carried out.
  • the calculation in block 120 receives, as external parameters, an indication of the maximum paint MipMap level M max from block 122. Furthermore, based on the footprint data provided in block 102, a bounding box is calculated in block 124, the dimensions b ⁇ n , b max of which are provided in block 126 and are provided for calculating the MipMap level in block 120.
  • the MipMap level m calculated in block 120 is then provided in block 128 and output in block 130.
  • a MipMap correction is carried out in block 132 (see point A and FIG. 1B).
  • the MipMap correction leads to a modified restriction variable c m , which is provided in block 134.
  • the modified constraint size c m is provided to block 136 by reducing the footprint to fit within the constraint rectangle defined by the constraint size c m .
  • the calculation in block S136 leads to the fact that modified footprint data 'i and scaling factors f x , f y are provided in blocks 138 and 140. As can also be seen in FIG.
  • the processing stage 136 receives the footprint data provided in block 102 (see point B) and the data relating to the boundary rectangle b m ⁇ r b max calculated in block 124 (see Point C).
  • the modified footprint data v'i provided in block 138 and the MipMap level m are provided to block 142, in which, based on the received data and based on information received from block 132, a conversion to a selected MipMap step is carried out so that provided in block 144, the transformer-optimized / transformed footprint data v i * ⁇ output in block 146 to. Furthermore, based on the scaling factors f x , f y provided in block 140, the extent is reduced in block 148, block 148 receiving the expansion parameter provided in block 110 in addition to the input from block 140 (see point D) , Block 148 also receives from block 150 a suitable algorithm for reducing the extent t. The modified expansion parameter t 'is then output in block 152.
  • the magnification shift is calculated in block 156, so that a magnification level r' is provided in block 158.
  • a transformation to the selected MipMap level takes place in block 162, so that in section 164 a modified magnification level r * that is also output in block 146.
  • FIG. 2 shows an example of a convex footprint 200 which is arranged in a texture space spanned by the x-axis and the y-axis.
  • the texel grid which has a plurality of square texel elements, some of which are covered by the footprint, is also located in this texture space. 2 shows the vertex vectors v 0 to V3 and the edge vectors s 0 to s 3 .
  • the vertex vectors v 0 to v 3 are provided as input data for the method according to the invention.
  • an important parameter that is used to determine a suitable level of detail for the representation of the footprint is the so-called “extent” t of the footprint 3 shows this expansion parameter in more detail for a four-sided footprint.
  • 3 shows the four vertex vectors v 0 to v 3 , and the two height vectors h 0 and hi, which connect the opposite vertexes v 0 and v 2 or vi and v 3 .
  • 3 also shows two expansion parameters to and ti, the final expansion parameter t being determined by the minimum of the two expansion parameters to and t x shown.
  • the expansion parameter t 0 defines the distance between two straight lines that extend through the vertices i and v 3 and are also parallel to the height vector h 0 .
  • the extension vector t x specifies a distance between two straight lines that extend through the vertices v 0 and v 2 and run parallel to the height vector hi.
  • the expansion parameter t is calculated in accordance with the calculation rule given below:
  • a direction of rotation d of the vertex indices can optionally also be calculated, which is then used in a later calculation of specific edge attributes can be used.
  • the area A of the footprint can also be calculated. The direction of rotation d and the area A are calculated in accordance with the calculation rule given below:
  • F area of the parallelogram spanned by h 0 and hi.
  • the direction d has a value of +1 for a clockwise rotation and a value of -1 for a counterclockwise rotation.
  • h 0 0
  • hi 0
  • the footprint degenerates to a point or a line and in this case the direction of rotation d is 0.
  • a restriction size c (clamp size) is subsequently calculated.
  • the restriction quantity c is a linear function over the course of the expansion parameter t, the course lying between the adjustable property parameter P and the maximum length defined by the parameter E max for a resulting edge.
  • an initial restriction quantity Co is then determined in accordance with the following calculation rule:
  • the lower curve shows the initial restriction value or the initial restriction quantity c 0 or its course over the expansion parameter t.
  • the lower curve describes the initially calculated size of the clamp box c 0 for the MipMap level 0. This represents a measure of the resolution to be used.
  • the curve qualitatively describes the following behavior: with a smaller t, ie narrower and thus the footprint with less surface area, the clamp size increases and thus the preferred resolution of the texture or the texel size thereof decreases in relation to the footprint size.
  • the upper limit by E max guarantees the maximum permitted edge length
  • the lower limit by P limits the process duration. The larger P, the later you jump to a lower resolution with increasing footprint area.
  • the upper curve c m corresponds to the coordinate-transformed c 0 for a MipMap level m. This is required if m is not equal to m req and a reduction is therefore necessary.
  • FIG. 5 shows an example of a bounding rectangle 202, and the bounding rectangle 202 and the required MipMap level m req are generated in accordance with the following calculation rules:
  • n min (v 0> y , v ly , v 2jy , v 3
  • the required MipMap level is limited to the highest available level value M max , according to the following calculation rule:
  • the desired MipMap level m is smaller than the MipMap level that is defined by the bounding rectangle, that is to say smaller than m req , it is necessary to reduce the size of the footprint so that it becomes one Constraint square fits.
  • the constraint square is based on a 17
  • Mip-map-corrected restriction size c m calculated, which is determined according to the following calculation rule:
  • FIG. 5 shows the restriction square 204 generated based on the corrected restriction size c m .
  • the size of the footprint 200 is reduced to the reduced footprint 206 in such a way that the vertices v 0 to v 3 of the original footprint are transferred to the vertices vo 'to v 3 ' in such a way that the transferred vertices on the edges of the restriction square 104 are arranged.
  • the original vertices are converted into the modified vertices according to the following calculation rule:
  • the coordinates of the reduced footprint v ⁇ must be transferred to the MipMap level m, which is carried out according to the following calculation rule:
  • the method according to the invention can provide an enlargement level depending on the expansion parameters.
  • ter t which can later be used to enlarge footprints with a partial texel size, in order to avoid temporal and spatial artifacts when displaying a footprint that comprises a plurality of footprints.
  • the expansion parameter t After the expansion parameter t has also been changed due to the reduction in the size of the footprint, it must also be set. Since the expansion parameter t is an anisotropic property, it can be calculated by generating a new expansion parameter for the reduced vertex vectors based on the above calculation rule, which is, however, very computationally expensive. According to a preferred exemplary embodiment, the expansion parameter t is determined approximately, but substantially less expensively, by using the oriented scaling factors f x and f y (method t), so that the following methods are available for determining the set expansion parameter t ':
  • the magnification level r is controlled by an adjustable magnification parameter T, which describes a minimal expansion without magnification.
  • the magnification level is generated according to the following calculation rule:
  • the method labeled 1) maintains the effective filter size for all MipMap levels. However, the compensation of elements smaller than a texel only applies to MipMap level 0 and becomes less effective the higher the MipMap level becomes.
  • Method 3) ensures the consistency of T with all levels. However, the effective filter size experiences a discrete increase between two levels, and the calculation is also more complex.
  • the preferred method 2) is a compromise between 1) and 3), and is of course the easiest method to implement.
  • a color of the footprint can then be calculated in subsequent processing steps.
  • the specific parameters of a further processing stage of the graphics unit are provided, which then generates a color of the footprint in a conventional manner.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Graphics (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Image Generation (AREA)
  • Processing Or Creating Images (AREA)
  • Controls And Circuits For Display Device (AREA)

Abstract

The invention relates to a method for the modification of a footprint dependent on a fixed number of texture elements, covered by the footprint, in a graphic system which provides the texture elements with a resolution, whereby a measurement or a form of the footprint (104) is first determined. Based on the fixed number of texture elements and based on the fixed measurement or form, the resolution of the texture elements corresponding to the footprint is determined (114). It is then determined whether the graphic system provides texture elements with the determined resolution. Should the graphic system provide texture elements with the determined resolution, the footprint is retained. Should the graphic system provide no texture elements with the determined resolution, the texture elements with the corresponding resolution provided by the graphic system are selected and that of the footprint reduced such that the number of texture elements covered by the footprint with reduced size is essentially the same or less than the determined number.

Description

Verfahren zur Analyse und Modifikation eines Footprints Procedure for analyzing and modifying a footprint
Beschreibungdescription
Die vorliegende Erfindung bezieht sich allgemein auf ein Verfahren zum Anzeigen von Bildern in einer Rasteranzeige, welche durch einen Computer gesteuert wird. Insbesondere bezieht sich die vorliegende Erfindung auf einen anisotro- pen Filtermechanismus, der erforderlich ist, um diskrete, abgespeicherte Bilder für die Darstellung auf Rasteranzeigeelementen mit hoher Qualität zu rekonstruieren, zu skalieren oder einer perspektivischen Projektion zu unterwerfen. Die gerade angesprochenen diskreten, gespeicherten Bilder werden nachfolgend als Texturen bezeichnet. Insbesondere bezieht sich die vorliegende Erfindung auf ein Verfahren zur Analyse und Modifikation eines Footprints abhängig von einer festgelegten Anzahl von Texturelementen, die durch den Footprint berührt werden, in einem Graphiksystem, das die Texturelemente mit einer Auflösung bereitstellt.The present invention relates generally to a method of displaying images on a raster display controlled by a computer. In particular, the present invention relates to an anisotropic filter mechanism that is required to reconstruct, scale or subject perspective projection to discrete, stored images for display on raster display elements with high quality. The discrete, stored images just mentioned are referred to below as textures. In particular, the present invention relates to a method for analyzing and modifying a footprint depending on a defined number of texture elements that are touched by the footprint in a graphics system that provides the texture elements with a resolution.
Ein „Footprint" ist eine perspektivische Projektion eines Bildelements (Pixel) eines Objekts auf eine gebogene Oberfläche. Ein „Footprint" kann eine konvexe vierseitige Dar- Stellung sein, die das angenäherte Ergebnis der perspektivischen Projektion auf ein reguläres Texel-Gitter (Texturelement-Gitter) eines quadratischen Bildelements (Pixel) eines Objekts auf eine gebogene Oberfläche wiedergibt.A "footprint" is a perspective projection of a picture element (pixel) of an object onto a curved surface. A "footprint" can be a convex four-sided representation, which is the approximate result of the perspective projection onto a regular texel grid (texture element grid ) of a square picture element (pixel) of an object on a curved surface.
Bekannte Graphiksysteme, z.B. OpenGL Graphiksysteme, arbeiten bei der Zuordnung von Texturen zu Bildelementen (Pixel) eines Objekts derart, dass einem Footprint eines Pixels eines Objekts ein oder mehrere Texturelement mit erwünschter Auflösung zugeordnet werden, wobei der Footprint durch ein Quadrat angenähert wird. Der Nachteil besteht darin, dass hier die Annäherung stets durch ein zu großes oder ein zu kleines Quadrat erfolgt und die Form des Footprints nicht berücksichtigt wird. Für die erwünsche Auflösung ergibt sich eine Texelgröße in einem dem Footprint zugrundeliegenden Texel-Gitter. Für vorbestimmte Texelgrößen existierenden unterschiedliche MipMap-Stufen. Ist nun eine Auflösung gewählt, die zu einer Texelgröße führt, für die keine MipMap mit geeigneter Auflösung (Stufe) vorhanden ist, so muss die Textur aufwendig berechnet werden.Known graphics systems, for example OpenGL graphics systems, work in assigning textures to picture elements (pixels) of an object in such a way that one or more texture elements with the desired resolution are assigned to a footprint of a pixel of an object, the footprint being approximated by a square. The disadvantage is that here the approximation is always done by too large or too small a square and the shape of the footprint is not taken into account. For the desired resolution, there is a texel size in a texel grid on which the footprint is based. Different MipMap levels exist for predetermined texel sizes. If a resolution is now selected that leads to a texel size for which there is no MipMap with a suitable resolution (level), the texture must be calculated with great effort.
Ausgehend von diesem Stand der Technik liegt der vorliegenden Erfindung die Aufgabe zugrunde, ein verbessertes Verfahren zum Modifizieren eines Footprints zu schaffen.Starting from this prior art, the present invention is based on the object of creating an improved method for modifying a footprint.
Diese Aufgabe wird durch ein Verfahren gemäß Anspruch 1 ge- löst.This object is achieved by a method according to claim 1.
Die vorliegende Erfindung schafft ein Verfahren zum Modifizieren eines Footprints abhängig von einer festgelegten Anzahl von Texturelementen, die durch den Footprint berührt werden, in einem Graphiksystem, das die Texturelemente mit einer Auflösung bereitstellt, mit folgenden Schritten:The present invention provides a method for modifying a footprint depending on a fixed number of texture elements that are touched by the footprint in a graphics system that provides the texture elements with a resolution, with the following steps:
(a) Bestimmen einer Abmessung oder einer Form des Footprints;(a) determining a dimension or shape of the footprint;
(b) Festlegen der Auflösung der dem Footprint zugeordneten Texturelemente, basierend auf der festgelegten Anzahl der Texturelemente und basierend auf der im Schritt (a) bestimmten Abmessung oder Form; und(b) determining the resolution of the texture elements associated with the footprint, based on the specified number of texture elements and based on the dimension or shape determined in step (a); and
(c) Bestimmen, ob das Graphiksystem Texturelemente mit der im Schritt (b) festgelegten Auflösung bereitstellt,(c) determining whether the graphics system provides texture elements with the resolution specified in step (b),
(c.l) falls das Graphiksystem Texturelemente mit der im Schritt (b) festgelegten Auflösung bereitstellt, Beibehalten des Footprints; und (c.2) falls das Graphiksystem keine Texturelemente mit der im Schritt (b) festgelegten Auflösung bereitstellt, Auswählen der durch das Graphiksystem bereitgestellten Texturelemente mit ent- sprechender Auflösung und Reduzieren der Größe des Footprints derart, dass die Anzahl der Texturelemente, die durch den Footprint mit reduzierter Größe berührt werden, im wesentlichen gleich oder kleiner als die festgelegte Anzahl ist.(cl) if the graphics system provides texture elements with the resolution specified in step (b), maintaining the footprint; and (c.2) if the graphics system does not provide texture elements with the resolution specified in step (b), select the texture elements provided by the graphics system with the corresponding resolution and reduce the size of the footprint in such a way that the number of texture elements that are produced by the Footprint with a reduced size is touched, is substantially equal to or less than the specified number.
Anders als im Stand der Technik, gemäß dem eine Filterung durchgeführt wird, die auch als isotrope Filterung bezeichnet werden kann, lehrt die vorliegende Erfindung anstelle der „groben" Annäherung des Footprints durch ein Quadrat, das denselben vollständig umgibt oder das vollständig in dem Footprint enthalten ist, eine Anzahl von verfügbaren Texturelementen mit festgelegter Auflösung und damit auch festgelegter Größe optimal auf den Footprint zu verteilen. Der Footprint wird hierbei durch die Texturelemente bedeckt, wobei erfindungsgemäß eine Analyse und Modifikation, wenn erforderlich, des Footprints erfolgt, um die optimale Verteilung der Texturelemente auf den Footprint zu erhalten.Unlike in the prior art, according to which filtering is carried out, which can also be referred to as isotropic filtering, the present invention teaches instead of the "rough" approximation of the footprint by a square that completely surrounds it or that is contained entirely in the footprint is to optimally distribute a number of available texture elements with a defined resolution and thus also a defined size onto the footprint, in which case the footprint is covered by the texture elements Get texture elements on the footprint.
Gemäß einem bevorzugten Ausführungsbeispiel wird das erfindungsgemäße Verfahren in einem Graphiksystem verwendet, das die Texturelemente mit verschiedenen Auflösungen bereitstellt, wobei im Schritt (c.2) Texturelemente mit einer nächstniedrigeren Auflösung als der festgelegten Auflösung ausgewählt werden. Vorzugsweise stellt das Graphiksystem die Texturelemente mit unterschiedlicher Auflösung in Form von MipMaps unterschiedlicher Stufen bereit.According to a preferred embodiment, the method according to the invention is used in a graphics system that provides the texture elements with different resolutions, wherein in step (c.2) texture elements with a resolution lower than the specified resolution are selected. The graphics system preferably provides the texture elements with different resolutions in the form of MipMaps of different levels.
Gemäß einem weiteren bevorzugten Ausführungsbeispiel wird zum Bestimmen der Auflösung im Schritt (b) ein den Footprint umgebendes Rechteck festgelegt, wobei Scheitelpunkte des Footprints auf Kanten des Rechtecks liegen. Wird festgestellt, dass für dieses Rechteck keine Texturelemente mit entsprechender Größe, also Auflösung, existieren, um die erwünschte Anzahl P zu erreichen, so wird in einer bevorzugten Weiterbildung des gerade beschriebenen Ausfüh- rungsbeispiels ein Beschränkungsquadrat festgelegt, das abhängig von der durch das Graphiksystem zur Verfügung gestellten Auflösung und abhängig von der Anzahl der Texturelemente definiert ist. Anschließend wird die Größe des Footprints durch Verschieben der Scheitelpunkte des Footprints auf die Kanten des Beschränkungsquadrats reduziert.According to a further preferred exemplary embodiment, a rectangle surrounding the footprint is determined in order to determine the resolution in step (b), vertices of the footprint lying on edges of the rectangle. Becomes found that there are no texture elements of a corresponding size, ie resolution, for this rectangle in order to achieve the desired number P, then in a preferred further development of the exemplary embodiment just described, a restriction square is determined which is dependent on that available through the graphics system set resolution and depending on the number of texture elements is defined. Then the size of the footprint is reduced by moving the vertices of the footprint to the edges of the constraint square.
Vorzugsweise werden das gerade beschriebene Rechteck und das Bestimmungsquadrat basierend auf einem Ausdehnungspara- meter des Footprints festgelegt, wobei der Ausdehnungsparameter eine longitudinale Verformung des Footprints wiedergibt.The rectangle just described and the square of determination are preferably determined on the basis of an expansion parameter of the footprint, the expansion parameter representing a longitudinal deformation of the footprint.
Gemäß einem weiteren bevorzugten Ausführungsbeispiel wird im Zusammenhang mit der Bestimmung einer Abmessung oder einer Form des Footprints zunächst bestimmt, ob eine Kante des Footprints eine festgelegte Abmessung übersteigt, und wenn dies der Fall ist, wird die Größe des Footprints so lange reduziert, bis die Abmessung der Kante kleiner oder gleich der festgelegten Abmessung ist.According to a further preferred embodiment, in connection with the determination of a dimension or a shape of the footprint, it is first determined whether an edge of the footprint exceeds a defined dimension, and if this is the case, the size of the footprint is reduced until the dimension the edge is less than or equal to the specified dimension.
Das erfindungsgemäße Verfahren schafft somit einen neuartigen Ansatz, der gemäß einem Ausführungsbeispiel auch durch einen Anwender gesteuert werden kann, um einen Footprint zu analysieren und zu modifizieren.The method according to the invention thus creates a novel approach which, according to one embodiment, can also be controlled by a user in order to analyze and modify a footprint.
Um das diskrete Texturbild wiederzugewinnen, müssen alle quadratischen Elemente des regulären Texel-Gitters - die Texel - die durch den Bereich des Footprints bedeckt sind, eingelesen und durch eine Verarbeitungseinheit verarbeitet werden. Das erfindungsgemäße Verfahren ermöglicht sowohl die Anzahl der Texel, die durch den Footprints berührt werden, als auch die Länge der Kanten des Footprints zu be- grenzen. Erfindungsgemäß wird hierfür ein zusätzliches Steuerungseingangssignal bereitgestellt, nämlich der Eigenschaftsparameter („Performance Parameter") P. Dieser Parameter P kann durch einen Anwender bereitgestellt werden. Die Beschränkung der Länge der Kanten des Footprints wird durch einen weiteren Parameter Emax bestimmt, welcher eine maximale Kantenlänge definiert. Dieser Parameter Emax kann beispielsweise in Hardwaretechnik codiert sein.In order to regain the discrete texture image, all square elements of the regular Texel grid - the Texel - that are covered by the area of the footprint must be read in and processed by a processing unit. The method according to the invention enables both the number of texels that are touched by the footprint and the length of the edges of the footprint to be measured. limits. According to the invention, an additional control input signal is provided for this, namely the property parameter (“performance parameter”) P. This parameter P can be provided by a user. The limitation of the length of the edges of the footprint is determined by a further parameter E max , which is a maximum edge length This parameter E max can be coded, for example, in hardware technology.
Der Vorteil der vorliegenden Erfindung besteht darin, dass durch Einstellen des Steuerungseingangssignals P ein Kom- promiss zwischen der wiedergewonnenen/rekonstruierten Bildqualität (hohe Anzahl von verwendeten Texeln) auf der einen Seite und der Verarbeitungsgeschwindigkeit (geringe Anzahl von verwendeten Texeln) andererseits erreicht werden kann. Ein Vorteil der Begrenzung der Begrenzungskanten besteht darin, dass hier der Hardwareaufwand, der bei nachfolgenden Prozessen zur Weiterverarbeitung des Footprints erforderlich ist, signifikant reduziert werden kann. Solche nach- folgenden Prozesse umfassen beispielsweise das Bestimmen der durch den Footprint bedeckten Texel und/oder das Gewichten dieser bestimmten Texel. Durch Beschränken der Kantenlänge kann der mit diesen Verarbeitungsschritten einhergehende Hardwareaufwand deutlich reduziert werden.The advantage of the present invention is that by setting the control input signal P a compromise can be achieved between the recovered / reconstructed image quality (high number of texels used) on the one hand and the processing speed (low number of texels used) on the other. One advantage of delimiting the boundary edges is that the hardware expenditure that is required in subsequent processes for further processing of the footprint can be significantly reduced. Such subsequent processes include, for example, determining the texels covered by the footprint and / or weighting these specific texels. By limiting the edge length, the hardware expenditure associated with these processing steps can be significantly reduced.
Allgemein können die durch das erfindungsgemäße Verfahren erzeugten Daten jedem Texel-oientierten Rasterverfahren bereitgestellt werden.In general, the data generated by the method according to the invention can be made available to any Texel-oriented raster method.
Gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung sind, wie oben bereits beschrieben wurde, für eine dem Footprint zugeordnete Textur eine Mehrzahl von sogenannten Bildtabellen (Image Map) mit unterschiedlicher Auflösung vorgesehen, die auch als MipMaps bezeichnet wer- den. Um die Auflösung festzulegen, wird abhängig von der Abmessung oder der Form des Footprints und abhängig von einer erwünschten Bildqualität des darzustellenden Footprints die Größe der Texel in einem Texel-Gitter bestimmt, die durch den Footprint berührt werden. Abhängig von der so bestimmten Texelgröße wird festgestellt, ob in der Mehrzahl von Bildtabellen eine Bildtabelle existiert, deren zugeordnete Texelgröße mit der bestimmten Texelgröße überein- stimmt. Ist dies der Fall, dann wird die entsprechende Bildtabelle für die Darstellung des Footprints herangezogen. Wenn jedoch keine entsprechende Bildtabelle existiert, wird, wie oben beschrieben, die Größe des Footprints reduziert, so dass abhängig von der Bildqualität des Footprints eine verfügbare Bildtabelle mit einer nächstniedrigeren Auflösung als der erwünschten Auflösung und einer entsprechenden Texelgröße zur Darstellung des Footprints ausgewählt wird.According to a preferred exemplary embodiment of the present invention, as has already been described above, a plurality of so-called image tables with different resolutions, which are also referred to as MipMaps, are provided for a texture assigned to the footprint. In order to determine the resolution, the size of the texels in a texel grid is determined depending on the size or shape of the footprint and on a desired image quality of the footprint to be displayed be touched by the footprint. Depending on the texel size determined in this way, it is ascertained whether an image table exists in the plurality of image tables whose assigned texel size corresponds to the specific texel size. If this is the case, then the corresponding image table is used for the representation of the footprint. If, however, no corresponding image table exists, the size of the footprint is reduced, as described above, so that, depending on the image quality of the footprint, an available image table with a resolution lower than the desired resolution and a corresponding texel size is selected for displaying the footprint.
Die Bildqualität wird vorzugsweise durch den Eigenschaftsparameter P festgelegt, der im wesentlichen angibt, wie groß die Anzahl der Texel in einem Texel-Gitter ist, die durch den Footprint berührt werden.The image quality is preferably determined by the property parameter P, which essentially indicates the number of texels in a texel grid that are touched by the footprint.
Gemäß dem gerade beschriebenen bevorzugten Ausführungsbeispiel werden somit im wesentlichen zwei Ansätze bzw. Techniken beschrieben, um die Anzahl der Texel, welche zur Darstellung eines Footprints herangezogen werden, zu beschränken (abhängig von der Einstellung des Eigenschaftsparame- ters P) . Wenn vorgefilterte Versionen eines Texturbildes mit niedriger Auflösung - die sogenannten MipMaps - verfügbar sind, so wird basierend auf den Ausdehnungsinformationen eine geeignete MipMap-Stufe berechnet. Hierdurch wird dann implizit die Größe eines quadratischen Texels in dem Texel-Gitter bestimmt. Diese Stufenberechnung basiert auf den tatsächlichen räumlichen Abmessungen und/oder auf der Form des Footprints. Ist keine vorgefilterte Bildtabelle (MipMap) mit der erforderlichen Stufe verfügbar, so erfolgt eine Reduzierung der Fläche des Footprints durch ein ge- zieltes Schrumpfen der Grenzen (Kanten) des Footprints. Dieses Schrumpfen der Kanten bzw. das Reduzieren der Fläche erfolgt basierend auf der Form, dem Eigenschaftsparameter P und einer Texelgröße der nächst verfügbaren Bildtabelle (MipMap) . Im ungünstigsten Fall handelt es sich bei der als nächst verfügbaren Bildtabelle um die ursprüngliche Basistabelle selbst.According to the preferred exemplary embodiment just described, essentially two approaches or techniques are described in order to limit the number of texels which are used to represent a footprint (depending on the setting of the property parameter P). If pre-filtered versions of a texture image with low resolution - the so-called MipMaps - are available, a suitable MipMap level is calculated based on the expansion information. This then implicitly determines the size of a square texel in the texel grid. This step calculation is based on the actual spatial dimensions and / or on the shape of the footprint. If no pre-filtered image table (MipMap) with the required level is available, the area of the footprint is reduced by deliberately shrinking the boundaries (edges) of the footprint. This shrinking of the edges or the reduction of the area is based on the shape, the property parameter P and a texel size of the next available image table (MipMap). In the worst case, the next available image table is the original base table itself.
Gemäß einem weiteren bevorzugten Ausführungsbeispiel der vorliegenden Erfindung wird anfänglich zunächst der ankommende vierseitige Footprint, welcher durch seine vier Scheitelpunkte definiert ist, hinsichtlich seiner Fläche und/oder seiner Form und/oder der räumlichen Ausdehnungen seiner Kanten analysiert. Diese Analyse umfaßt die nachfolgenden Schritte:According to a further preferred exemplary embodiment of the present invention, the incoming four-sided footprint, which is defined by its four vertices, is initially analyzed with regard to its area and / or its shape and / or the spatial dimensions of its edges. This analysis includes the following steps:
Bestimmen einer Drehrichtung des Footprints, die entweder im Uhrzeigersinn oder entgegen dem Uhrzeigersinn sein kann;Determining a direction of rotation of the footprint, which can be either clockwise or counterclockwise;
- Berechnen eines anisotropen Ausdehnungsparameters, welcher den Grad der longitudinalen Verformung des Footprints beschreibt;Calculating an anisotropic expansion parameter which describes the degree of longitudinal deformation of the footprint;
Bestimmen eines Begrenzungsrechteckes (bounding box) für den Footprint; undDetermining a bounding box for the footprint; and
Erzeugen eines Beschränkungsquadrats (Clamping Box) , welches eine linear geschrumpfte Version des ursprünglichen Footprints auf eine Art und Weise beschränkt, dass eine horizontale Breite und eine vertikale Höhe einer beliebigen Kante (des geschrumpften Footprints) einen vordefinierten Grenzwert nicht überschreitet. Dieser vordefinierte Grenzwert wird basierend auf dem oben beschriebenen Maximallängenwert für die Kanten Emax festgelegt. Ferner hängt die Abmessung des Beschränkungsquadrats von dem Ausdehnungsparameter ab, und wird derart eingestellt, dass die Anzahl der Te- xel, welche durch das Beschränkungsquadrat überdeckt werden, eine Grenze, die durch den Eigenschaftsparameter P festgelegt ist, nicht überschreitet. Nachdem der ankommende Footprint auf die oben beschriebene Art und Weise analysiert wurde, wird nachfolgend die so erhaltene, analysierte Information beurteilt, um Ausgangsdaten zu erzeugen, welche einen möglicherweise modifizierten Footprint zusammen mit der zugeordneten MipMap-Stufe und einer zugeordneten Vergrößerungsstufe darstellt. Dies beinhaltet hauptsächlich die Umformung der ursprünglichen Koordinaten aller Scheitelpunkte des ursprünglichen Footprints in das Koordinatensystem, welches durch die berechnete Mip- Map-Stufe festgelegt ist. Eine Projektion der Scheitelpunkte des Footprints auf das Beschränkungsquadrat schrumpft den Footprints zusätzlich, wenn dies erforderlich ist.Create a clamping box that constrains a linearly shrunk version of the original footprint in such a way that a horizontal width and vertical height of any edge (of the shrunken footprint) does not exceed a predefined limit. This predefined limit value is determined based on the maximum length value for the edges Emax described above. Furthermore, the dimension of the constraint square depends on the expansion parameter and is set such that the number of texels covered by the constraint square does not exceed a limit which is determined by the property parameter P. After the incoming footprint has been analyzed in the manner described above, the analyzed information thus obtained is subsequently assessed in order to generate output data which represents a possibly modified footprint together with the assigned MipMap level and an associated magnification level. This mainly involves the transformation of the original coordinates of all vertices of the original footprint into the coordinate system, which is determined by the calculated mip map level. A projection of the vertices of the footprint onto the constraint square additionally shrinks the footprints if necessary.
Ein Vorteil der vorliegenden Erfindung besteht somit darin, dass ankommende Footprint-Koordinaten derart modifiziert werden, dassAn advantage of the present invention is therefore that incoming footprint coordinates are modified in such a way that
eine Kantenbreite oder Kantenhöhe, vorzugsweise eine hardwaremäßig codierte, maximale Länge Emax nicht über- schreiten,not exceed an edge width or edge height, preferably a hardware-coded maximum length E max ,
- die Anzahl von Texeln, die durch den Footprint bedeckt werden etwa gleich oder kleiner der Anzahl ist, auf die die Anzahl dieser Texel durch einen Anwender vorab festgelegt wurde,the number of texels covered by the footprint is approximately equal to or less than the number to which the number of these texels has been predetermined by a user,
die Form des Footprints beibehalten wird, wenn eine Verkleinerung durch eine MipMap-Stufe größer als 0 ausgewählt wird, undthe shape of the footprint is retained when a reduction by a MipMap level greater than 0 is selected, and
eine räumliche und zeitliche Diskontinuität des wiedergewonnenen Bildes vermieden wird.a spatial and temporal discontinuity of the recovered image is avoided.
Gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung wird das erfindungsgemäße Verfahren hardwaremäßig in Form einer Hardware-Pipeline implementiert, was die beschleunigte Verarbeitung einer Mehrzahl von Footprints ermöglicht.According to a preferred embodiment of the present invention, the method according to the invention is implemented in hardware in the form of a hardware pipeline, which enables accelerated processing of multiple footprints.
Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend anhand der beiliegenden Zeichnungen näher erläutert. Es zeigen:Preferred exemplary embodiments of the present invention are explained in more detail below with reference to the accompanying drawings. Show it:
Fig. 1A und B ein Flussdiagramm, das das Verfahren gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung im Überblick zeigt;1A and B are a flow chart showing an overview of the method according to a preferred embodiment of the present invention;
Fig. 2 eine Darstellung der Scheitelpunkt- und Kantenvektoren eines beispielhaften Footprints in einem Texturraum;2 shows a representation of the vertex and edge vectors of an exemplary footprint in a texture space;
Fig. 3 eine Darstellung des Footprints und des dem Footprints zugeordneten Ausdehnungsparameters;3 shows a representation of the footprint and the expansion parameter assigned to the footprint;
Fig. 4 den Verlauf der Beschränkungsgröße abhängig von einer Ausdehnung des Footprints; und4 shows the course of the restriction size as a function of an expansion of the footprint; and
Fig. 5 ein Beispiel für die Verkleinerung des Footprints .Fig. 5 shows an example of the reduction of the footprint.
Nachfolgend wird anhand der Fig. 1 das erfindungsgemäße Verfahren gemäß einem bevorzugten Ausführungsbeispiel im Überblick beschrieben, wobei die einzelnen, in Fig. 1 gezeigten Verfahrensschritte nachfolgend anhand der übrigen Figuren noch näher erläutert werden.The method according to the invention according to a preferred exemplary embodiment is described in an overview below with reference to FIG. 1, the individual method steps shown in FIG. 1 being explained in more detail below with reference to the remaining figures.
Das erfindungsgemäße Verfahren beginnt beim Block 100, bei dem die den Footprint beschreibenden Daten empfangen werden. In der nachfolgenden Beschreibung wird stets der Beg- riff Footprint verwendet, der eine konvexe vierseitige Struktur ist, der das angenäherte Ergebnis einer perspektivischen Projektion eines quadratischen Bildelements auf eine gebogene Oberfläche darstellt. Bei dem in Fig. 1 dargestellten Flussdiagramm stellen die Rechtecke die Hauptverarbeitungsschritte dar, die nachfolgend noch näher erläutert werden. Die Ergebnisse der Verar- beitungsschritte sind in Datenstrukturen gespeichert, die schematisch in den Parallelogrammen in Fig. 1 gezeigt sind. Diese werden als Eingangssignale für die nächsten Verarbeitungsstufen herangezogen. Die einzelnen Verarbeitungsschritte werden nachfolgend detailliert beschrieben, wobei zur Vereinfachung der Beschreibung eine mathematische Vektornotation (im Fettdruck dargestellt) gewählt wurde.The method according to the invention begins at block 100, in which the data describing the footprint is received. In the following description, the term footprint is always used, which is a convex four-sided structure, which represents the approximate result of a perspective projection of a square picture element onto a curved surface. In the flowchart shown in FIG. 1, the rectangles represent the main processing steps, which are explained in more detail below. The results of the processing steps are stored in data structures which are shown schematically in the parallelograms in FIG. 1. These are used as input signals for the next processing stages. The individual processing steps are described in detail below, with a mathematical vector notation (shown in bold) being chosen to simplify the description.
Nachdem im Block 100 die den Footprint beschreibenden Daten empfangen wurden, stehen im Block 102 die die Scheitelpunk- te des Footprints beschreibenden Vektoren v± bereit, mit i = 0, 1, 2, 3 (bei der Beschreibung des bevorzugten Ausführungsbeispiels wird von einem vierseitigen Footprint ausgegangen) .After the data describing the footprint has been received in block 100, the vectors v ± describing the vertices of the footprint are available in block 102, with i = 0, 1, 2, 3 (the description of the preferred exemplary embodiment uses a four-sided one) Footprint out).
Im nachfolgenden Block 104 werden die im Block 102 bereitgestellten FootprintInformationen verwendet, um eine Footprintanalyse durchzuführen. Diese Footprintanalyse führt zum einen zur Feststellung einer Drehrichtung d des Footprints, die im Block 106 bereitgestellt wird und im Block 108 an einem Ausgang bereitgestellt wird. Ferner ergibt die Footprintanalyse im Block 104 den Ausdehnungsparameter t, der im Block 110 bereitgestellt wird. Basierend auf dem im Block 110 bereitgestellten Äusdehnungsparameter t und basierend auf einem im Block 112 bereitgestellten, externen Eigenschaftsparameter P wird im Block 114 eine Beschränkungsgröße c0 berechnet, welche im Block 116 bereitgestellt wird. Der Eigenschaftsparameter P legt die Anzahl der Texel fest, die durch den Footprint berührt bzw. bedeckt werden.In the subsequent block 104, the footprint information provided in block 102 is used to carry out a footprint analysis. On the one hand, this footprint analysis leads to the determination of a direction of rotation d of the footprint, which is provided in block 106 and is provided in block 108 at an output. Furthermore, the footprint analysis in block 104 yields the expansion parameter t, which is provided in block 110. Based on the expansion parameter t provided in block 110 and based on an external property parameter P provided in block 112, a restriction quantity c 0 is calculated in block 114, which is provided in block 116. The property parameter P defines the number of texels that are touched or covered by the footprint.
Im Block 120 wird eine Berechnung der erforderlichen MipMap-Stufe durchgeführt. Die Berechnung im Block 120 empfängt als externe Parameter zum einen eine Angabe der maxi- malen MipMap-Stufe Mmax aus dem Block 122. Ferner wird basierend auf den Footprintdaten, die im Block 102 bereitgestellt wurden, im Block 124 ein Begrenzungsrechteck (boun- ding box) berechnet, deren Abmessungen b^n, bmax im Block 126 bereitgestellt werden, und zur Berechnung der MipMap- Stufe im Block 120 bereitgestellt werden. Im Block 128 wird dann die im Block 120 berechnete MipMap-Stufe m bereitgestellt, und im Block 130 ausgegeben.In block 120, a calculation of the required MipMap level is carried out. The calculation in block 120 receives, as external parameters, an indication of the maximum paint MipMap level M max from block 122. Furthermore, based on the footprint data provided in block 102, a bounding box is calculated in block 124, the dimensions b ^ n , b max of which are provided in block 126 and are provided for calculating the MipMap level in block 120. The MipMap level m calculated in block 120 is then provided in block 128 and output in block 130.
Basierend auf der im Block 116 bereitgestellten Beschränkungsgröße c0 und auf der im Block 128 bereitgestellten MipMap-Stufe m wird im Block 132 (siehe Punkt A und Fig. 1B) eine MipMap-Korrektur durchgeführt wird. Die MipMap- Korrektur führt zu einer modifizierten Beschränkungsgröße cm, die im Block 134 bereitgestellt wird. Die modifizierte Beschränkungsgröße cm wird dem Block 136 bereitgestellt, in dem der Footprint so verkleinert wird, dass es in das durch die Beschränkungsgröße cm definierte Beschränkungsrechteck passt. Die Berechnung im Block S136 führt zum einen dazu, dass modifizierte Footprintdaten 'i und Skalierungsfaktoren fx, fy in den Blöcken 138 und 140 bereitgestellt werden. Wie in Fig. 1B ferner zu erkennen ist, empfängt die Verarbeitungsstufe 136 zusätzlich zu der modifizierten Beschränkungsgröße cm die im Block 102 bereitgestellten Footprintdaten (siehe Punkt B) sowie die Daten betreffend das im Block 124 berechnete Begrenzungsrechteck bm^r bmax (siehe Punkt C) .Based on the restriction quantity c 0 provided in block 116 and on the MipMap level m provided in block 128, a MipMap correction is carried out in block 132 (see point A and FIG. 1B). The MipMap correction leads to a modified restriction variable c m , which is provided in block 134. The modified constraint size c m is provided to block 136 by reducing the footprint to fit within the constraint rectangle defined by the constraint size c m . On the one hand, the calculation in block S136 leads to the fact that modified footprint data 'i and scaling factors f x , f y are provided in blocks 138 and 140. As can also be seen in FIG. 1B, in addition to the modified restriction variable c m , the processing stage 136 receives the footprint data provided in block 102 (see point B) and the data relating to the boundary rectangle b m ^ r b max calculated in block 124 (see Point C).
Die im Block 138 bereitgestellten modifizierten Footprint- daten v'i und die MipMap-Stufe m werden dem Block 142 bereitgestellt, in dem basierend auf den empfangenen Daten und basierend auf Informationen, welche vom Block 132 empfangen werden, eine Umformung auf eine gewählte MipMap- Stufe durchgeführt wird, so dass im Block 144 die transfor- mierten/umgeformten Footprintdaten v*i bereitgestellt wer¬ den, die im Block 146 ausgegeben werden. Ferner wird basierend auf den im Block 140 bereitgestellten Skalierungsfaktoren fx, fy im Block 148 die Ausdehnung reduziert, wobei der Block 148 zusätzlich zu der Eingabe aus dem Block 140 den Ausdehnungsparameter, der im Block 110 bereitgestellt wurde, empfängt (siehe Punkt D) . Ferner empfängt der Block 148 vom Block 150 einen geeigneten Algorithmus zur Reduzierung der Ausdehnung t. Im Block 152 wird dann der modifizierte Ausdehnungsparameter t' ausgegeben. Basierend auf einem im Block 154 bereitgestellten Vergröße- rungsparameter und auf dem im Block 152 bereitgestellten modifizierten Ausdehnungsparameter t' erfolgt im Block 156 eine Berechnung der Vergrößerungsverschiebung, so dass im Block 158 eine Vergrößerungsstufe r' bereitgestellt wird. Basierend auf einem im Block 160 bereitgestellten Algorith- mus und basierend auf der durch den Block 158 bereitgestellten Vergrößerungsstufe und der MipMap-Stufe m erfolgt im Block 162 eine Umformung auf die gewählte MipMap-Stufe, so dass sich im Abschnitt 164 eine modifizierte Vergrößerungsstufe r* einstellt, die im Block 146 ebenfalls ausge- geben wird.The modified footprint data v'i provided in block 138 and the MipMap level m are provided to block 142, in which, based on the received data and based on information received from block 132, a conversion to a selected MipMap step is carried out so that provided in block 144, the transformer-optimized / transformed footprint data v i * ¬ output in block 146 to. Furthermore, based on the scaling factors f x , f y provided in block 140, the extent is reduced in block 148, block 148 receiving the expansion parameter provided in block 110 in addition to the input from block 140 (see point D) , Block 148 also receives from block 150 a suitable algorithm for reducing the extent t. The modified expansion parameter t 'is then output in block 152. Based on a magnification parameter provided in block 154 and on the modified expansion parameter t 'provided in block 152, the magnification shift is calculated in block 156, so that a magnification level r' is provided in block 158. Based on an algorithm provided in block 160 and based on the magnification level provided by block 158 and the MipMap level m, a transformation to the selected MipMap level takes place in block 162, so that in section 164 a modified magnification level r * that is also output in block 146.
Nachfolgend werden die einzelnen Blöcke aus Fig. 1 näher erläutert.The individual blocks from FIG. 1 are explained in more detail below.
In Fig. 2 ist ein Beispiel für einen konvexen Footprint 200 gezeigt, der in einem durch die x-Achse und die y-Achse aufgespannten Texturraum angeordnet ist. In diesem Texturraum befinden sich auch das Texel-Gitter, welches eine Mehrzahl von quadratischen Texelelementen aufweist, von de- nen einige durch den Footprint überdeckt sind. In Fig. 2 sind die Scheitelpunktvektoren v0 bis V3 sowie die Kantenvektoren s0 bis s3 gezeigt. Als Eingangsdaten für das erfindungsgemäße Verfahren werden die Scheitelpunktvektoren v0 bis v3 bereitgestellt.FIG. 2 shows an example of a convex footprint 200 which is arranged in a texture space spanned by the x-axis and the y-axis. The texel grid, which has a plurality of square texel elements, some of which are covered by the footprint, is also located in this texture space. 2 shows the vertex vectors v 0 to V3 and the edge vectors s 0 to s 3 . The vertex vectors v 0 to v 3 are provided as input data for the method according to the invention.
Ein wichtiger Parameter, der verwendet wird, um eine geeignete Detailstufe für die Darstellung des Footprints festzulegen, ist die sogenannte „Ausdehnung" t des Footprints. In Fig. 3 ist dieser Ausdehnungsparameter näher dargestellt, für einen vierseitigen Footprint. In Fig. 3 sind die vier Scheitelpunktvektoren v0 bis v3 gezeigt, sowie die zwei Höhenvektoren h0 und hi, welche die gegenüberliegenden Scheitelpunkte v0 und v2 bzw. vi und v3 verbinden. Ferner sind in Fig. 3 zwei Ausdehnungsparameter to und ti dargestellt, wobei der abschließende Ausdehnungsparameter t durch den minimalen der zwei gezeigten Ausdehnungsparameter to und tx bestimmt ist.An important parameter that is used to determine a suitable level of detail for the representation of the footprint is the so-called “extent” t of the footprint 3 shows this expansion parameter in more detail for a four-sided footprint. 3 shows the four vertex vectors v 0 to v 3 , and the two height vectors h 0 and hi, which connect the opposite vertexes v 0 and v 2 or vi and v 3 . 3 also shows two expansion parameters to and ti, the final expansion parameter t being determined by the minimum of the two expansion parameters to and t x shown.
Wie zu erkennen ist, definiert der Ausdehnungsparameter t0 den Abstand zwischen zwei Geraden, die sich durch die Scheitelpunkte i und v3 erstrecken und ferner parallel zum Höhenvektor h0 sind. Ebenso gibt der Ausdehnungsvektor tx eine Abstand zwischen zwei Geraden an, die sich durch die Scheitelpunkte v0 und v2 erstrecken und parallel zu dem Höhenvektor hi verlaufen.As can be seen, the expansion parameter t 0 defines the distance between two straight lines that extend through the vertices i and v 3 and are also parallel to the height vector h 0 . Likewise, the extension vector t x specifies a distance between two straight lines that extend through the vertices v 0 and v 2 and run parallel to the height vector hi.
Basierend auf den in Fig. 3 dargestellten Parametern er- folgt die Berechnung des Ausdehnungsparameters t gemäß der nachfolgend wiedergegebenen Berechnungsvorschrift:Based on the parameters shown in FIG. 3, the expansion parameter t is calculated in accordance with the calculation rule given below:
fiJ = vj+2 - J ) = °>l h = h0 x h, h 2 = ho,χ " hι.y 0,y l,x fi J = v j + 2 - J ) = °> l h = h 0 xh, h 2 = h o, χ "h ι.y 0, yl, x
Gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung kann optional auch noch eine Drehrichtung d der Scheitelpunktindizes berechnet werden, welche dann bei einer späteren Berechnung von spezifischen Kantenattributen herangezogen werden kann. Ferner kann zusätzlich der Flächenbereich A des Footprints berechnet werden. Die Berechnung der Drehrichtung d und der Fläche A erfolgt gemäß der nachfolgend wiedergegebenen Berechnungsvorschrift:According to a preferred embodiment of the present invention, a direction of rotation d of the vertex indices can optionally also be calculated, which is then used in a later calculation of specific edge attributes can be used. In addition, the area A of the footprint can also be calculated. The direction of rotation d and the area A are calculated in accordance with the calculation rule given below:
d =sign(hz)d = sign (h z )
A = F/2A = F / 2
mit:With:
F = Fläche des durch h0 und hi aufgespannten Parallelo- gramms .F = area of the parallelogram spanned by h 0 and hi.
Die Richtung d hat einen Wert von +1 für eine Drehung im Uhrzeigersinn, und einen Wert von -1 für eine Drehung entgegen dem Uhrzeigersinn. Für den Fall dass gilt h0 = 0 ODER hi = 0 degeneriert der Footprint zu einem Punkt oder einer Linie und in diesem Fall ist die Drehrichtung d gleich 0.The direction d has a value of +1 for a clockwise rotation and a value of -1 for a counterclockwise rotation. In the event that h 0 = 0 OR hi = 0, the footprint degenerates to a point or a line and in this case the direction of rotation d is 0.
Nach dem Bestimmen des Ausdehnungsparameters t und der optionalen Bestimmung der Rotationsrichtung d und der Fläche A wird nachfolgend eine Beschränkungsgröße c (clamp size) berechnet. Die Beschränkungsgröße c ist eine lineare Funktion über den Verlauf des Ausdehnungsparameters t, wobei der Verlauf zwischen dem einstellbaren Eigenschaftsparameter P und der durch den Parameter Emax definierten maximalen Länge für eine sich ergebende Kante liegt. Die Beschränkungsgröße c hat einen Wert von P wenn gilt: t = P, wobei sich für diese Einstellung eine maximale Fläche A* des sich ergebenden Footprints einstellt, wobei gilt: A* = P2. Basierend auf der Einstellung des Parameters c erfolgt dann eine Bestimmung einer anfänglichen Beschränkungsgröße Co gemäß der nachfolgenden Berechnungsvorschrift:After determining the expansion parameter t and the optional determination of the direction of rotation d and the area A, a restriction size c (clamp size) is subsequently calculated. The restriction quantity c is a linear function over the course of the expansion parameter t, the course lying between the adjustable property parameter P and the maximum length defined by the parameter E max for a resulting edge. The restriction variable c has a value of P if: t = P, a maximum area A * of the resulting footprint being obtained for this setting, where: A * = P 2 . Based on the setting of parameter c, an initial restriction quantity Co is then determined in accordance with the following calculation rule:
c= 1- max t + Emax c0 = max(P,c) In Fig. 4 ist der Verlauf der Beschränkungsgröße c über dem Ausdehnungsparameter t aufgetragen, und wie zu erkennen ist, ist der Wert des Beschränkungsparameters c = Emax für t = 0 und nimmt ausgehend von diesem Wert linear bis zum Wert P ab, der bei t •= P erreicht wird. Ab diesem Wert bleibt der Wert des Beschränkungsparameters c konstant auf dem Wert P. In Fig. 4 ist in der unteren Kurve der anfängliche Begrenzungswert bzw. die anfängliche Begrenzungsgröße c0 bzw. deren Verlauf über dem Ausdehnungsparameter t gezeigt. In Fig. 4 beschreibt die untere Kurve die zunächst berechnete Größe der Clamp-Box c0 für die MipMap-Stufe 0. Dies stellt ein Maß für die zu verwendende Auflösung dar. Die Kurve beschreibt qualitativ folgendes Verhalten: mit kleinerem t, also schmaleren und somit flächenärmeren Footprint, steigt die Clamp-Größe und somit die bevorzugte Auflösung der Textur bzw. verkleinert sich deren Texelgröße im Verhältnis zu der Footprintgröße. Die Beschränkung nach oben durch Emax garantiert die höchstens erlaubte Kantenlänge, die Beschränkung nach unten durch P limitiert die Pro- zessdauer. Je größer P, desto später wird in eine niedrigere Auflösung gesprungen bei wachsender Fläche des Footprints. Die obere Kurve cm entspricht der koordinatentransformierten c0 für eine MipMap-Stufe m. Diese wird benötigt, wenn m ungleich mreq ist und daher eine Verkleine- rung notwendig ist. c = 1- max t + E max c 0 = max (P, c) 4, the course of the restriction variable c is plotted against the expansion parameter t, and as can be seen, the value of the restriction parameter is c = E max for t = 0 and decreases linearly from this value to the value P, which is t • = P is reached. From this value, the value of the restriction parameter c remains constant at the value P. In FIG. 4, the lower curve shows the initial restriction value or the initial restriction quantity c 0 or its course over the expansion parameter t. In Fig. 4 the lower curve describes the initially calculated size of the clamp box c 0 for the MipMap level 0. This represents a measure of the resolution to be used. The curve qualitatively describes the following behavior: with a smaller t, ie narrower and thus the footprint with less surface area, the clamp size increases and thus the preferred resolution of the texture or the texel size thereof decreases in relation to the footprint size. The upper limit by E max guarantees the maximum permitted edge length, the lower limit by P limits the process duration. The larger P, the later you jump to a lower resolution with increasing footprint area. The upper curve c m corresponds to the coordinate-transformed c 0 for a MipMap level m. This is required if m is not equal to m req and a reduction is therefore necessary.
Nachfolgend wird unter Bezugnahme auf die Fig. 5 die Berechnung der erforderlichen MipMap-Stufe mreq bzw. eine erforderliche Reduzierung der Größe des Footprints näher er- läutert.The calculation of the required MipMap level m req or a required reduction in the size of the footprint is explained in more detail below with reference to FIG. 5.
Zunächst sei der Fall angenommen, dass für den darzustellenden Footprint in seiner ursprünglichen Abmessung und Form eine MipMap-Stufe existiert, welche eine Verkleinerung des Footprints vermeidet. Durch diese minimale MipMap-Stufe wird sichergestellt, dass keine Seite eines Begrenzungsrechtecks für den Footprint größer ist als die Beschränkungsgröße Co, die auf die oben beschriebene Art und Weise bestimmt wurde. In Fig. 5 ist neben dem Footprint 200 beispielhaft ein Begrenzungsrechteck 202 dargestellt, und das Begrenzungsrechteck 202 sowie die erforderliche MipMap- Stufe mreq wird gemäß der nachfolgenden Berechnungsvorschriften erzeugt:First of all, let us assume that there is a MipMap level for the footprint to be displayed in its original dimensions and shape, which avoids a reduction in the footprint. This minimal MipMap level ensures that no side of a bounding rectangle for the footprint is larger than the constraint size Co in the manner described above was determined. In addition to the footprint 200, FIG. 5 shows an example of a bounding rectangle 202, and the bounding rectangle 202 and the required MipMap level m req are generated in accordance with the following calculation rules:
min(vo,x > vι,χ'v 2.χ> v 3,χ ) b„!n = min(v0>y,vl y,v2jy,v3 mi n ( v o, x> v ι , χ ' v 2 .χ > v 3, χ) b „ ! n = min (v 0> y , v ly , v 2jy , v 3
'm 1UaOxΛ(1v V0nιX ..,.v VI, x ..,.v V,2jX ..,.v V3,ι .. max(v0>y,vIιy,v2ty,v3ty) b = t> -b'm 1UaOxΛ (1v V 0 n ιX ..,. v V I , x ..,. v V, 2jX ..,. v V 3 , ι .. max (v 0> y , v Iιy , v 2ty , v 3ty ) b = t> -b
wobei die Funktion „ceil" die Bedeutung hat, dass der in Klammern gesetzte Begriff, auf den nächsten ganzzahligen Wert in Richtung +oo erhöht wird. In Fig. 5 sind die in der obigen Berechnungsvorschrift wiedergegebenen Parameter bmιn und b dargestellt, und der ebenfalls in der Berechnungsvorschrift wiedergegebene Parameter bmax ist der Vektor, der sich vom Ursprung des Koordinatensystems zur Spitze des Vektors b erstreckt, der Übersichtlichkeit halber jedoch nicht dargestellt ist.wherein the "ceil" the importance function is that the term in brackets is to the nearest integer value in the direction + oo increased. In Fig. 5, shown in the above calculation rule parameters b m ι n and b are represented, and The parameter b max , which is also reproduced in the calculation rule, is the vector which extends from the origin of the coordinate system to the tip of the vector b, but is not shown for the sake of clarity.
Um die anzulegende MipMap-Stufe m zu erhalten, wird die er- forderliche MipMap-Stufe auf den höchsten verfügbaren Stufenwert Mmax beschränkt, gemäß der folgenden BerechnungsVorschrift :In order to obtain the MipMap level m to be created, the required MipMap level is limited to the highest available level value M max , according to the following calculation rule:
m =min(Mmax,mreq)m = min (M max , m req )
Wird nun jedoch festgestellt, dass der erwünschte MipMap- Pegel m kleiner als derjenige MipMap-Pegel ist, der durch das Begrenzungsrechteck festgelegt wird, also kleiner als mreq ist, so ist es erforderlich, den Footprint größenmäßig zu reduzieren, so dass dieser in ein Beschränkungsquadrat passt. Das Beschränkungsquadrat wird basierend auf einer 17However, if it is found that the desired MipMap level m is smaller than the MipMap level that is defined by the bounding rectangle, that is to say smaller than m req , it is necessary to reduce the size of the footprint so that it becomes one Constraint square fits. The constraint square is based on a 17
Mip-Map-korrigierten Beschränkungsgröße cm berechnet, welche gemäß der nachfolgenden Berechnungsvorschrift bestimmt wird:Mip-map-corrected restriction size c m calculated, which is determined according to the following calculation rule:
cm=max(p.2m,c+(2m-l)-Emax)c m = max (p.2 m , c + (2 m -l) -E max )
Der Verlauf des Parameters der korrigierten Beschränkungsgröße cm ist in Fig. 4 ebenfalls aufgetragen.The course of the parameter of the corrected restriction variable c m is also plotted in FIG. 4.
In Fig. 5 ist das basierend auf der korrigierten Beschränkungsgröße cm erzeugte Beschränkungsquadrat 204 gezeigt. Die Reduzierung der Größe des Footprints 200 auf den verkleinerten Footprint 206 erfolgt derart, dass die Scheitelpunkte v0 bis v3 des ursprünglichen Footprints in die Scheitelpunkte vo' bis v3' überführt werden, derart, dass die überführten Scheitelpunkte auf den Kanten des Beschränkungsquadrats 104 angeordnet sind. Die Überführung der ursprünglichen Scheitelpunkte in die modifizierten Scheitelpunkte erfolgt gemäß der nachfolgenden Berechnungsvor- schrift:FIG. 5 shows the restriction square 204 generated based on the corrected restriction size c m . The size of the footprint 200 is reduced to the reduced footprint 206 in such a way that the vertices v 0 to v 3 of the original footprint are transferred to the vertices vo 'to v 3 ' in such a way that the transferred vertices on the edges of the restriction square 104 are arranged. The original vertices are converted into the modified vertices according to the following calculation rule:
mit: fx, fy = Skalierungsfaktoren für die x- und y-Richtung.with: f x , f y = scaling factors for the x and y direction.
In einem abschließenden Block müssen die Koordinaten des reduzierten Footprints v\ auf die MipMap-Stufe m übertragen werden, was gemäß der folgenden Berechnungsvorschrift durchgeführt wird:In a final block, the coordinates of the reduced footprint v \ must be transferred to the MipMap level m, which is carried out according to the following calculation rule:
v; = 2- v ; = 2-
Zusätzlich kann das erfindungsgemäße Verfahren vorsehen, eine Vergrößerungsstufe abhängig von dem Ausdehnungsparame- ter t bereitzustellen, welcher später verwendet werden kann, um Footprints mit einer Teil-Texel-Größe zu vergrößern, um zeitliche und räumliche Artefakte bei der Darstellung eines Footprints, welches eine Mehrzahl von Footprints umfaßt, zu vermeiden.In addition, the method according to the invention can provide an enlargement level depending on the expansion parameters. ter t, which can later be used to enlarge footprints with a partial texel size, in order to avoid temporal and spatial artifacts when displaying a footprint that comprises a plurality of footprints.
Nachdem der Ausdehnungsparameter t aufgrund der Reduzierung der Größe des Footprints ebenfalls verändert wurde, uss dieser ebenfalls eingestellt werden. Nachdem der Ausdeh- nungsparameter t eine anisotrope Eigenschaft ist, kann dieser dadurch berechnet werden, dass ein neuer Ausdehnungsparameter für die verkleinerten Scheitelpunktvektoren basierend auf der obigen Berechnungsvorschrift erzeugt wird, was jedoch recht rechenaufwendig ist. Gemäß einem bevorzugten Ausführungsbeispiel wird der Ausdehnungsparameter t näherungsweise, jedoch wesentlich weniger aufwendig, durch Verwenden der orientierten Skalierungsfaktoren fx und fy (Verfahren t) bestimmt, so dass die folgenden Verfahren zum Bestimmen des eingestellten Ausdehnungsparameters t' zur Verfügung stehen:After the expansion parameter t has also been changed due to the reduction in the size of the footprint, it must also be set. Since the expansion parameter t is an anisotropic property, it can be calculated by generating a new expansion parameter for the reduced vertex vectors based on the above calculation rule, which is, however, very computationally expensive. According to a preferred exemplary embodiment, the expansion parameter t is determined approximately, but substantially less expensively, by using the oriented scaling factors f x and f y (method t), so that the following methods are available for determining the set expansion parameter t ':
(1) f = t(vj)(1) f = t (vj)
(3) t' =t.min(fx,fy)(3) t '= t .min (f x , f y )
Das mit (2) beschriebene Verfahren wird, wie oben erläu- tert, bevorzugt.The method described with (2) is preferred, as explained above.
Die Vergrößerungsstufe r wird durch einen einstellbaren Vergrößerungsparameter T gesteuert, welcher eine minimale Ausdehnung ohne Vergrößerung beschreibt. Der Vergrößerungs- pegel wird gemäß der folgenden Berechnungsvorschrift erzeugt:The magnification level r is controlled by an adjustable magnification parameter T, which describes a minimal expansion without magnification. The magnification level is generated according to the following calculation rule:
r =max 0, l 2 ) Je höher der Wert von T ist, desto mehr Verschmierungen werden in das darzustellende Bild eingebracht, jedoch werden gleichzeitig weniger Artefakte festgestellt. Als vorteilhaft hat sich ein Wert von ^2 für T herausgestellt. Wird T = 0 gewählt, so wird jede Vergrößerung deaktiviert.r = max 0, l 2) The higher the value of T, the more smearing is introduced into the image to be displayed, but fewer artifacts are found at the same time. A value of ^ 2 for T has proven to be advantageous. If T = 0 is selected, every enlargement is deactivated.
Ähnlich wie oben bei der Bestimmung des geänderten Ausdehnungsparameters t' existieren auch für die Umwandlung der Verzögerungsstufe r' in die ausgewählte MipMap-Stufe m drei Möglichkeiten (Verfahren r) , nämlichSimilar to the determination of the changed expansion parameter t 'above, there are three options (method r) for converting the delay stage r' into the selected MipMap stage m, namely
1) r*=r'-2-m 1) r * = r'-2 m
2) r*=r'2) r * = r '
3) r*=r'+(2—2-(m+1))-t'3) r * = r '+ ( 2 -2- (m + 1) ) -t'
Das mit 1) bezeichnete Verfahren behält die effektive Fil- tergröße für alle MipMap-Stufen bei. Die Kompensation von Elementen mit einer Größe kleiner als ein Texel gilt jedoch nur für die MipMap-Level 0 und wird weniger effektiv je höher die MipMap-Level wird. Das Verfahren 3) stellt die Konsistenz von T mit allen Stufen sicher. Die effektive Fil- tergröße erfährt jedoch eine diskrete Vergrößerung zwischen zwei Pegeln, und ferner ist die Berechnung aufwendiger. Das bevorzugte Verfahren 2) ist schließlich ein Kompromiss zwischen 1) und 3), und somit selbstverständlich das am einfachsten zu implementierende Verfahren.The method labeled 1) maintains the effective filter size for all MipMap levels. However, the compensation of elements smaller than a texel only applies to MipMap level 0 and becomes less effective the higher the MipMap level becomes. Method 3) ensures the consistency of T with all levels. However, the effective filter size experiences a discrete increase between two levels, and the calculation is also more complex. Finally, the preferred method 2) is a compromise between 1) and 3), and is of course the easiest method to implement.
Mit den auf die oben beschriebene Art und Weise beschriebenen Parametern kann dann in nachfolgenden Verarbeitungsschritten eine Farbe des Footprints berechnet werden. Hierfür werden die bestimmten Parameter einer weiteren Verar- beitungsstufe der Graphikeinheit bereitgestellt, welche dann auf herkömmliche Weise eine Farbe des Footprints erzeugt.With the parameters described in the manner described above, a color of the footprint can then be calculated in subsequent processing steps. For this purpose, the specific parameters of a further processing stage of the graphics unit are provided, which then generates a color of the footprint in a conventional manner.
Obwohl die vorliegende Erfindung bei der obigen Beschrei- bung der bevorzugten Ausführungsbeispiele auf der Grundlage eines Footprints mit vier Seiten beschrieben wurde, kann der erfindungsgemäße Ansatz grundsätzlich auf beliebige Footprints erweitert werden. Although the present invention is based on the above description of the preferred embodiments of a four-page footprint, the approach according to the invention can in principle be extended to any footprints.

Claims

Patentansprüche claims
1. Verfahren zum Modifizieren eines Footprints (200) ab- hängig von einer festgelegten Anzahl (P) von Texturelementen, die durch den Footprint berührt werden, in einem Graphiksystem, das die Texturelemente mit einer Auflösung (m) bereitstellt, mit folgenden Schritten:1. A method for modifying a footprint (200) depending on a defined number (P) of texture elements which are touched by the footprint in a graphics system which provides the texture elements with a resolution (m), with the following steps:
(a) Bestimmen (104) einer Abmessung oder einer Form des Footprints (200);(a) determining (104) a dimension or shape of the footprint (200);
(b) Festlegen (114) der Auflösung (mreq) der dem Footprint zugeordneten Texturelemente, basierend auf der festgelegten Anzahl (P) der Texturelemente und basierend auf der im Schritt (a) bestimmten Abmessung oder Form; und(b) determining (114) the resolution (m req ) of the texture elements associated with the footprint, based on the specified number (P) of the texture elements and based on the dimension or shape determined in step (a); and
(c) Bestimmen (118), ob das Graphiksystem Texturele- mente mit der im Schritt (b) festgelegten Auflösung (mreq) bereitstellt,(c) determining (118) whether the graphics system provides texture elements with the resolution (m req ) defined in step (b),
(c.l) falls das Graphiksystem Texturelemente mit der im Schritt (b) festgelegten Auflösung (πireq) bereitstellt (m = mreq) , Beibehalten des Footprints (200) ; und(cl) if the graphics system provides texture elements with the resolution (πireq) specified in step (b) (m = m req ), maintaining the footprint (200); and
(c.2) falls das Graphiksystem keine Texturelemente mit der im Schritt (b) festgelegten Auflö- sung (mreq) bereitstellt (m ≠ mreq) , Auswählen der durch das Graphiksystem bereitgestellten Texturelemente mit entsprechender Auflösung und Reduzieren (136) der Größe des Footprints (200) derart, dass die Anzahl der Texturelemente, die durch den Footprint mit reduzierter Größe berührt werden, im wesentlichen gleich oder kleiner als die festgelegte Anzahl (P) ist. _. Verfahren nach Anspruch 1, bei dem das Graphiksystem die Texturelemente mit einer Mehrzahl von Auflösungen bereitstellt, wobei im Schritt (c.(c.2) if the graphics system does not provide texture elements with the resolution (m req ) specified in step (b) (m ≠ m req ), select the texture elements provided by the graphics system with a corresponding resolution and reduce (136) the size of the footprint (200) in such a way that the number of texture elements which are touched by the footprint of reduced size is substantially equal to or less than the specified number (P). _. The method of claim 1, wherein the graphics system provides the texture elements with a plurality of resolutions, wherein in step (c.
2) Texturelemente mit einer nächstniedrigeren Auflösung als der festgelegten Auflösung ausgewählt werden.2) Texture elements with a resolution lower than the specified resolution are selected.
3. Verfahren nach Anspruch 1 oder 2, bei dem der Schritt (a) folgende Teilschritte umfaßt:3. The method of claim 1 or 2, wherein step (a) comprises the following substeps:
(a.l) Bestimmen, ob eine Kante (s0, Si, s2, s3) des Footprints (200) eine festgelegte Abmessung (Emax) übersteigt; und(al) determining whether an edge (s 0 , Si, s 2 , s 3 ) of the footprint (200) exceeds a specified dimension (E max ); and
(a.2) Reduzieren der Größe des Footprints bis die Abmessung der Kante kleiner oder gleich der festgelegten Abmessung ist, falls die Abmessung der Kante die festgelegte Abmessung übersteigt.(a.2) Reduce the size of the footprint until the dimension of the edge is less than or equal to the specified dimension if the dimension of the edge exceeds the specified dimension.
4. Verfahren nach einem der Ansprüche 1 bis 3, bei dem das Graphiksystem die Texturelemente mit unterschiedlicher Auflösung in Form von MipMaps unterschiedlicher Stufen (m) bereitstellt.4. The method according to any one of claims 1 to 3, wherein the graphics system provides the texture elements with different resolutions in the form of MipMaps of different levels (m).
5. Verfahren nach einem der Ansprüche 1 bis 4, bei dem der Schritt (b) das Festlegen eines den Footprint (200) umgebenden Rechtecks (202) umfaßt, wobei Scheitelpunkte (v0, vi, v2, v3) des Footprints (200) auf Kanten des Rechtecks (202) liegen.5. The method according to any one of claims 1 to 4, wherein step (b) comprises defining a rectangle (202) surrounding the footprint (200), wherein vertices (v 0 , vi, v 2 , v 3 ) of the footprint ( 200) lie on edges of the rectangle (202).
6. Verfahren nach einem der Ansprüche 1 bis 5, bei dem der Schritt (c.2) folgende Schritte umfaßt:6. The method according to any one of claims 1 to 5, wherein step (c.2) comprises the following steps:
Festlegen eines Beschränkungsquadrats (204), das abhängig von der Auflösung des durch das Graphiksystem bereitgestellten Texturelements, und Reduzieren der Größe des Footprints (200) durch Verschieben der Scheitelpunkte (v0, vi, v2, v3) des Footprints (200) auf Kanten des Beschränkungsquadrats (204) .Defining a constraint square (204) depending on the resolution of the texture element provided by the graphics system, and Reduce the size of the footprint (200) by moving the vertices (v 0 , vi, v 2 , v 3 ) of the footprint (200) to edges of the constraint square (204).
Verfahren nach Anspruch 5 oder 6, bei dem das Rechteck (202) und das Beschränkungsquadrat (204) basierend auf einem Ausdehnungsparameter (t) des Footprints (200) festgelegt werden. The method of claim 5 or 6, wherein the rectangle (202) and the constraint square (204) are determined based on an expansion parameter (t) of the footprint (200).
EP03798897A 2002-09-13 2003-09-09 Method for the analysis and modification of a footprint Withdrawn EP1537537A1 (en)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
DE10242639 2002-09-13
DE10242639A DE10242639A1 (en) 2002-09-13 2002-09-13 Method for analysis and modification of footprint i.e. perspective projection of pixel e.g. for computerized raster image displays, requires initially establishing resolution of textured elements associated with footprint
PCT/EP2003/010016 WO2004032060A1 (en) 2002-09-13 2003-09-09 Method for the analysis and modification of a footprint

Publications (1)

Publication Number Publication Date
EP1537537A1 true EP1537537A1 (en) 2005-06-08

Family

ID=31895970

Family Applications (1)

Application Number Title Priority Date Filing Date
EP03798897A Withdrawn EP1537537A1 (en) 2002-09-13 2003-09-09 Method for the analysis and modification of a footprint

Country Status (9)

Country Link
US (1) US7221372B2 (en)
EP (1) EP1537537A1 (en)
JP (1) JP4106364B2 (en)
KR (1) KR100633029B1 (en)
CN (1) CN1327396C (en)
AU (1) AU2003266371A1 (en)
DE (1) DE10242639A1 (en)
TW (1) TWI257590B (en)
WO (1) WO2004032060A1 (en)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4660254B2 (en) * 2005-04-08 2011-03-30 株式会社東芝 Drawing method and drawing apparatus
US7737988B1 (en) * 2005-11-14 2010-06-15 Nvidia Corporation Using font filtering engines for texture blitting
CN101604443B (en) * 2009-07-29 2011-07-06 腾讯科技（深圳）有限公司 Method and device for generating motion track of emitted object
TWI476640B (en) 2012-09-28 2015-03-11 Ind Tech Res Inst Smoothing method and apparatus for time data sequences
KR102282189B1 (en) 2014-07-02 2021-07-27 삼성전자 주식회사 Mipmap Generation Method and apparatus
KR102477265B1 (en) * 2015-09-24 2022-12-13 삼성전자주식회사 Graphics processing apparatus and method for determining LOD (level of detail) for texturing of graphics pipeline thereof
CN110390012B (en) * 2018-04-13 2023-12-05 北京京东尚科信息技术有限公司 Track aggregation method and device, storage medium and electronic equipment

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100372743B1 (en) * 1995-03-08 2003-05-09 옵티컬디스크코포레이션 Method and apparatus for changing pit depth on optical recording medium
US5877771A (en) * 1996-07-12 1999-03-02 Silicon Graphics, Inc. Method and apparatus for supersampling based on the local rate of change in texture
US6097397A (en) * 1997-11-20 2000-08-01 Real 3D, Inc. Anisotropic texture mapping using silhouette/footprint analysis in a computer image generation system
US6879324B1 (en) * 1998-07-14 2005-04-12 Microsoft Corporation Regional progressive meshes
US7061500B1 (en) * 1999-06-09 2006-06-13 3Dlabs Inc., Ltd. Direct-mapped texture caching with concise tags
US6400370B1 (en) * 1999-09-10 2002-06-04 Intel Corporation Stochastic sampling with constant density in object space for anisotropic texture mapping
US6807290B2 (en) * 2000-03-09 2004-10-19 Microsoft Corporation Rapid computer modeling of faces for animation
US6766281B1 (en) * 2000-05-12 2004-07-20 S3 Graphics Co., Ltd. Matched texture filter design for rendering multi-rate data samples
US6850243B1 (en) * 2000-12-07 2005-02-01 Nvidia Corporation System, method and computer program product for texture address operations based on computations involving other textures
US20020126133A1 (en) * 2001-02-08 2002-09-12 3Dlabs Inc., Ltd. Fast anisotropic/anisotropy sensitive single MIPmap sampled filtering

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2004032060A1 *

Also Published As

Publication number Publication date
AU2003266371A1 (en) 2004-04-23
TWI257590B (en) 2006-07-01
KR100633029B1 (en) 2006-10-11
CN1327396C (en) 2007-07-18
DE10242639A1 (en) 2004-03-25
CN1682246A (en) 2005-10-12
US20050156940A1 (en) 2005-07-21
JP2005538475A (en) 2005-12-15
TW200404266A (en) 2004-03-16
US7221372B2 (en) 2007-05-22
WO2004032060A1 (en) 2004-04-15
JP4106364B2 (en) 2008-06-25
KR20050046775A (en) 2005-05-18

Similar Documents

Publication Publication Date Title
DE69822545T2 (en) Image enhancement using surface interpolation
DE69720131T2 (en) Perspective transformation system and method
DE602004002393T2 (en) ANTIALIASING METHOD AND DEVICE FOR PRESENTING A REGION OF A TWO-DIMENSIONAL DISTANCE FIELD THAT CONSTITUTES AN OBJECT
DE69816824T2 (en) TEXTURE IMAGE IN 3-D COMPUTER GRAPHICS
DE69428491T2 (en) image lens
DE69430336T2 (en) Enlargement of digital images using edge mapping
DE69431294T2 (en) IMAGE PROCESSING METHOD AND SYSTEM
DE69432093T2 (en) Image processing device
DE69626394T2 (en) METHOD AND DEVICE FOR REDUCING THE MEMORY REQUIREMENT FOR DISPLAY DATA
DE68925399T2 (en) Method and device for image transformation
DE3750784T2 (en) Generation of an intrapolated characteristic value for display.
DE69729603T2 (en) Image processing apparatus and method
DE3315148C2 (en)
DE19827726A1 (en) Method and apparatus for providing polygon pixel subsampling information using an incremental device
DE102010046507A1 (en) Calculation of detail level for anisotropic filtering
EP2052550A2 (en) Image processing device for colour image data and method for processing colour image data
DE19920812A1 (en) Interpolated lines creating device for conversion of interlaced video signals to progressively swept format without interlacing
DE69529732T2 (en) Correction of the perspective of textures in graphic images by adaptive approximation
DE69606177T2 (en) METHOD AND DEVICE FOR IMAGING TEXTURE
DE3789091T2 (en) Image processing method and system for image reconstruction.
DE69329564T2 (en) Image processing device
DE602004002291T2 (en) METHOD FOR GENERATING A TWO-DIMENSIONAL DISTANCE FIELD WITHIN A CELL CONTAINING A CORNER OF A TWO-DIMENSIONAL OBJECT
EP1537537A1 (en) Method for the analysis and modification of a footprint
DE68926952T2 (en) Process for performing interactive image processing operations on large images
DE69927269T2 (en) DEVICE AND METHOD FOR RECOGNIZING AND PRODUCING GRAPHIC ELEMENTS

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20050217

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT RO SE SI SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK

DAX Request for extension of the european patent (deleted)
RBV Designated contracting states (corrected)

Designated state(s): DE FR GB

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: KONINKLIJKE PHILIPS ELECTRONICS N.V.

Owner name: PHILIPS INTELLECTUAL PROPERTY & STANDARDS GMBH

RIN1 Information on inventor provided before grant (corrected)

Inventor name: RICHTER, ROLANDC/O PHILIPS INTELLECTUAL PROPERTY

Inventor name: HAAKER, THOMAS

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: NXP B.V.

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: TRIDENT MICROSYSTEMS (FAR EAST) LTD.

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20140401