WO2004032060A1 - Verfahren zur analyse und modifikation eines footprints - Google Patents

Verfahren zur analyse und modifikation eines footprints Download PDF

Info

Publication number
WO2004032060A1
WO2004032060A1 PCT/EP2003/010016 EP0310016W WO2004032060A1 WO 2004032060 A1 WO2004032060 A1 WO 2004032060A1 EP 0310016 W EP0310016 W EP 0310016W WO 2004032060 A1 WO2004032060 A1 WO 2004032060A1
Authority
WO
WIPO (PCT)
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.)
Ceased
Application number
PCT/EP2003/010016
Other languages
English (en)
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.)
Philips Intellectual Property and Standards GmbH
Koninklijke Philips NV
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
Priority to JP2004540605A priority Critical patent/JP4106364B2/ja
Priority to EP03798897A priority patent/EP1537537A1/de
Priority to AU2003266371A priority patent/AU2003266371A1/en
Publication of WO2004032060A1 publication Critical patent/WO2004032060A1/de
Anticipated expiration legal-status Critical
Priority to US11/080,776 priority patent/US7221372B2/en
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—Three-dimensional [3D] image rendering
    • G06T15/04—Texture mapping
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—Two-dimensional [2D] image generation
    • G06T11/40—Filling planar surfaces by adding surface attributes, e.g. adding colours or textures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—Three-dimensional [3D] 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

Bei einem 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, wird zunächst eine Abmessung oder eine Form des Footprints bestimmt (104). Basierend auf der festgelegten Anzahl der Texturelemente und basierend auf der bestimmten Abmessung oder Form wird die Auflösung der dem Footprint zugeordneten Texturelemente festgelegt (114). Dann wird bestimmt, ob das Graphiksystem Texturelemente mit der festgelegten Auflösung bereitstellt. Falls das Graphiksystem Texturelemente mit der festgelegten Auflösung bereitstellt, wird der Footprint beibehalten. Falls das Graphiksystem keine Texturelemente mit der festgelegten Auflösung bereitstellt,werden die durch das Graphiksystem bereitgestellten Texturelemente mit entsprechender Auflösung ausgewählt, und die des Footprints wird derart reduziert, dass die Anzahl der Texturelemente, die durch den Footprint mit reduzierter Grösse berührt werden, im wesentlichen gleich oder kleiner als die festgelegte Anzahl ist.

Description

Verfahren zur Analyse und Modifikation eines Footprints
Beschreibung
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.
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.
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.
Ausgehend von diesem Stand der Technik liegt der vorliegenden Erfindung die Aufgabe zugrunde, ein verbessertes Verfahren zum Modifizieren eines Footprints zu schaffen.
Diese Aufgabe wird durch ein Verfahren gemäß Anspruch 1 ge- löst.
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:
(a) Bestimmen einer Abmessung oder einer Form des Footprints;
(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
(c) Bestimmen, ob das Graphiksystem Texturelemente mit der im Schritt (b) festgelegten Auflösung bereitstellt,
(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.
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.
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.
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.
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.
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.
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.
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.
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.
Allgemein können die durch das erfindungsgemäße Verfahren erzeugten Daten jedem Texel-oientierten Rasterverfahren bereitgestellt werden.
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.
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.
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.
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:
Bestimmen einer Drehrichtung des Footprints, die entweder im Uhrzeigersinn oder entgegen dem Uhrzeigersinn sein kann;
- Berechnen eines anisotropen Ausdehnungsparameters, welcher den Grad der longitudinalen Verformung des Footprints beschreibt;
Bestimmen eines Begrenzungsrechteckes (bounding box) für den Footprint; und
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.
Ein Vorteil der vorliegenden Erfindung besteht somit darin, dass ankommende Footprint-Koordinaten derart modifiziert werden, dass
eine Kantenbreite oder Kantenhöhe, vorzugsweise eine hardwaremäßig codierte, maximale Länge Emax nicht über- schreiten,
- 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,
die Form des Footprints beibehalten wird, wenn eine Verkleinerung durch eine MipMap-Stufe größer als 0 ausgewählt wird, und
eine räumliche und zeitliche Diskontinuität des wiedergewonnenen Bildes vermieden wird.
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.
Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend anhand der beiliegenden Zeichnungen näher erläutert. Es zeigen:
Fig. 1A und B ein Flussdiagramm, das das Verfahren gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung im Überblick zeigt;
Fig. 2 eine Darstellung der Scheitelpunkt- und Kantenvektoren eines beispielhaften Footprints in einem Texturraum;
Fig. 3 eine Darstellung des Footprints und des dem Footprints zugeordneten Ausdehnungsparameters;
Fig. 4 den Verlauf der Beschränkungsgröße abhängig von einer Ausdehnung des Footprints; und
Fig. 5 ein Beispiel für die Verkleinerung des Footprints .
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.
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.
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) .
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.
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.
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) .
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.
Nachfolgend werden die einzelnen Blöcke aus Fig. 1 näher erläutert.
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.
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.
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.
Basierend auf den in Fig. 3 dargestellten Parametern er- folgt die Berechnung des Ausdehnungsparameters t gemäß der nachfolgend wiedergegebenen Berechnungsvorschrift:
fiJ = vj+2 - J ) = °>l
Figure imgf000015_0001
h = h0 x h, h 2 = ho,χ " hι.y 0,y l,x
Figure imgf000015_0002
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:
d =sign(hz)
A = F/2
mit:
F = Fläche des durch h0 und hi aufgespannten Parallelo- gramms .
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.
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:
Figure imgf000016_0001
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.
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.
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:
min(vo,x > vι,χ'v 2.χ> v 3,χ ) b„!n = min(v0>y,vl y,v2jy,v3
'm 1UaOxΛ(1v V0nιX ..,.v VI, x ..,.v V,2jX ..,.v V3,ι .. max(v0>y,vIιy,v2ty,v3ty) b = t> -b
Figure imgf000018_0001
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.
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 :
m =min(Mmax,mreq)
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 17
Mip-Map-korrigierten Beschränkungsgröße cm berechnet, welche gemäß der nachfolgenden Berechnungsvorschrift bestimmt wird:
cm=max(p.2m,c+(2m-l)-Emax)
Der Verlauf des Parameters der korrigierten Beschränkungsgröße cm ist in Fig. 4 ebenfalls aufgetragen.
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:
Figure imgf000019_0001
mit: fx, fy = Skalierungsfaktoren für die x- und y-Richtung.
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:
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.
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:
(1) f = t(vj)
Figure imgf000020_0001
(3) t' =t.min(fx,fy)
Das mit (2) beschriebene Verfahren wird, wie oben erläu- tert, bevorzugt.
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:
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.
Ä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ämlich
1) r*=r'-2-m
2) r*=r'
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.
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.
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.

Claims

Patentansprüche
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:
(a) Bestimmen (104) einer Abmessung oder einer Form des Footprints (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
(c) Bestimmen (118), ob das Graphiksystem Texturele- mente mit der im Schritt (b) festgelegten Auflösung (mreq) bereitstellt,
(c.l) falls das Graphiksystem Texturelemente mit der im Schritt (b) festgelegten Auflösung (πireq) bereitstellt (m = mreq) , Beibehalten des Footprints (200) ; und
(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.
2) Texturelemente mit einer nächstniedrigeren Auflösung als der festgelegten Auflösung ausgewählt werden.
3. Verfahren nach Anspruch 1 oder 2, bei dem der Schritt (a) folgende Teilschritte umfaßt:
(a.l) Bestimmen, ob eine Kante (s0, Si, s2, s3) des Footprints (200) eine festgelegte Abmessung (Emax) übersteigt; und
(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.
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.
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.
6. Verfahren nach einem der Ansprüche 1 bis 5, bei dem der Schritt (c.2) folgende Schritte umfaßt:
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) .
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.
PCT/EP2003/010016 2002-09-13 2003-09-09 Verfahren zur analyse und modifikation eines footprints Ceased WO2004032060A1 (de)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP2004540605A JP4106364B2 (ja) 2002-09-13 2003-09-09 フットプリントの解析および修正方法
EP03798897A EP1537537A1 (de) 2002-09-13 2003-09-09 Verfahren zur analyse und modifikation eines footprints
AU2003266371A AU2003266371A1 (en) 2002-09-13 2003-09-09 Method for the analysis and modification of a footprint
US11/080,776 US7221372B2 (en) 2002-09-13 2005-03-14 Method of analyzing and modifying a footprint

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE10242639.2 2002-09-13
DE10242639A DE10242639A1 (de) 2002-09-13 2002-09-13 Verfahren zur Analyse und Modifikation eines Footprints

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US11/080,776 Continuation US7221372B2 (en) 2002-09-13 2005-03-14 Method of analyzing and modifying a footprint

Publications (1)

Publication Number Publication Date
WO2004032060A1 true WO2004032060A1 (de) 2004-04-15

Family

ID=31895970

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2003/010016 Ceased WO2004032060A1 (de) 2002-09-13 2003-09-09 Verfahren zur analyse und modifikation eines footprints

Country Status (9)

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

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4660254B2 (ja) * 2005-04-08 2011-03-30 株式会社東芝 描画方法及び描画装置
US7737988B1 (en) * 2005-11-14 2010-06-15 Nvidia Corporation Using font filtering engines for texture blitting
CN101604443B (zh) * 2009-07-29 2011-07-06 腾讯科技（深圳）有限公司 一种发射体运行轨迹的生成方法及装置
TWI476640B (zh) 2012-09-28 2015-03-11 Ind Tech Res Inst 時間資料序列的平滑化方法與裝置
KR102282189B1 (ko) 2014-07-02 2021-07-27 삼성전자 주식회사 밉맵 생성 방법 및 장치
KR102477265B1 (ko) * 2015-09-24 2022-12-13 삼성전자주식회사 그래픽스 프로세싱 장치 및 그래픽스 파이프라인의 텍스쳐링을 위한 LOD(level of detail)를 결정하는 방법
CN110390012B (zh) * 2018-04-13 2023-12-05 北京京东尚科信息技术有限公司 轨迹聚合方法、装置、存储介质及电子设备

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
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
US6400370B1 (en) * 1999-09-10 2002-06-04 Intel Corporation Stochastic sampling with constant density in object space for anisotropic texture mapping
US20020126133A1 (en) * 2001-02-08 2002-09-12 3Dlabs Inc., Ltd. Fast anisotropic/anisotropy sensitive single MIPmap sampled filtering

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11501757A (ja) * 1995-03-08 1999-02-09 オプチカル ディスク コーポレイション 光記録媒体のピットの深さを変化させる方法及び手段
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
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

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
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
US6400370B1 (en) * 1999-09-10 2002-06-04 Intel Corporation Stochastic sampling with constant density in object space for anisotropic texture mapping
US20020126133A1 (en) * 2001-02-08 2002-09-12 3Dlabs Inc., Ltd. Fast anisotropic/anisotropy sensitive single MIPmap sampled filtering

Also Published As

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

Similar Documents

Publication Publication Date Title
DE69822545T2 (de) Bildverbesserung unter Benutzung einer Flächeninterpolation
DE69720131T2 (de) System und Verfahren zur Perspektivetransformation
DE602004002393T2 (de) Antialiasing-verfahren und -vorrichtung zur darstellung einer region eines zweidimensionalen distanzfeldes, das ein objekt darstellt
DE69816824T2 (de) Texturabbildung in 3-d-rechnergraphik
DE69428491T2 (de) Bildlinse
DE69430336T2 (de) Vergrösserung von digitalen Bildern mittels Kantenabbildung
DE69431294T2 (de) Bildverarbeitungsverfahren und -system
DE68925399T2 (de) Verfahren und Gerät zur Bildtransformation
DE69626394T2 (de) Verfahren und vorrichtung zur verminderung des speicherbedarfs für anzeigedaten
DE3750784T2 (de) Generation eines intrapolierten charakteristischen Wertes zur Anzeige.
DE60000686T2 (de) Graphisches system mit super-abgetastetem musterpuffer mit erzeugung von ausgangpixeln unter verwendung von selektiven adjustierung der filterung zur artifaktverminderung
DE69729603T2 (de) Bildverarbeitungsgerät und -verfahren
DE3315148C2 (de)
DE19827726A1 (de) Verfahren und Vorrichtung zum Liefern von Polygonpixelunterabtastinformationen unter Verwendung einer Inkrementaleinrichtung
DE102010046507A1 (de) Berechnung der Detailstufe für die anisotrope Filterung
EP2052550A2 (de) Bildverarbeitungsvorrichtung für farb-bilddaten und verfahren zur bildverarbeitung von farb-bilddaten
DE69529732T2 (de) Korrektur der Perspektive von Texturen in graphischen Bildern durch adaptive Approximation
DE19920812A1 (de) Einrichtung zum Erzeugen einer interpolierten Videozeile
DE602004002291T2 (de) Verfahren zur erzeugung eines zweidimensionalen distanzfeldes innerhalb einer zelle, die eine ecke eines zweidimensionalen objektes beinhaltet
EP1537537A1 (de) Verfahren zur analyse und modifikation eines footprints
DE68926952T2 (de) Verfahren zur Ausführung von interaktiven Bildverarbeitungsoperationen auf grossen Bildern
EP1386287B1 (de) Bildverarbeitungsverfahren
DE69927269T2 (de) Vorrichtung und verfahren zum erkennen und erzeugen grafischer elemente
DE69728918T2 (de) Verfahren und Gerät zur wirkungsvollen Bildinterpolation
DE69910980T2 (de) Antialiasing mit unterabtastung für textur-raender

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2003798897

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 20038215373

Country of ref document: CN

WWE Wipo information: entry into national phase

Ref document number: 1020057004335

Country of ref document: KR

WWE Wipo information: entry into national phase

Ref document number: 2004540605

Country of ref document: JP

Ref document number: 11080776

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 1020057004335

Country of ref document: KR

WWP Wipo information: published in national office

Ref document number: 2003798897

Country of ref document: EP