WO2006108988A2 - Procede de conversion d'une image a trois dimensions en image a deux dimensions - Google Patents

Procede de conversion d'une image a trois dimensions en image a deux dimensions Download PDF

Info

Publication number
WO2006108988A2
WO2006108988A2 PCT/FR2006/050323 FR2006050323W WO2006108988A2 WO 2006108988 A2 WO2006108988 A2 WO 2006108988A2 FR 2006050323 W FR2006050323 W FR 2006050323W WO 2006108988 A2 WO2006108988 A2 WO 2006108988A2
Authority
WO
WIPO (PCT)
Prior art keywords
image
dimensional image
vector
contour
components
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/FR2006/050323
Other languages
English (en)
Other versions
WO2006108988A3 (fr
Inventor
Gaspard Breton
David Cailliere
Alexandre Audoin
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.)
Orange SA
Original Assignee
France Telecom SA
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 France Telecom SA filed Critical France Telecom SA
Publication of WO2006108988A2 publication Critical patent/WO2006108988A2/fr
Publication of WO2006108988A3 publication Critical patent/WO2006108988A3/fr
Anticipated expiration legal-status Critical
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/10—Geometric effects

Definitions

  • the present invention generally relates to the field of image processing, and in particular to methods for converting three-dimensional images into two-dimensional images.
  • two-dimensional vector image formats that allow an intermediate representation between a three-dimensional image and the rendering image on a terminal. These have the advantage of removing part of the calculation on the terminal, with a reduced representation format compared to a two-dimensional pixel image.
  • Three-dimensional image conversion systems in two-dimensional vector images are based on the projection of each polygon or triangle of the three-dimensional image on a projection surface, each polygon or triangle being projected one by one. Each projected triangle or polygon is then encoded in vector form, with adjacent triangles or polygons sometimes being merged into a single vector outline. These systems nevertheless have the disadvantage of using a lot of memory space, since each triangle or polygon of the initial image is encoded in vector form. In addition, these systems do not effectively solve the problems of overlap between several triangles or to distinguish if a triangle is in front or behind another triangle when the two triangles are intersected.
  • the conversion process resolves the overlap problems between intersecting triangles.
  • the vector image resulting from the method minimizes the memory resources required for storage according to the desired accuracy.
  • the vector images resulting from the invention can be used in an animation by limiting the phenomena of discontinuity of movement between the successive vector images.
  • the invention proposes a method for converting a three-dimensional image into a two-dimensional image, characterized in that it comprises the steps of:
  • the invention advantageously makes it possible to overcome the problems of overlap between triangles of the components of the three-dimensional image during their projection.
  • the three-dimensional image thus converted by the method according to the invention is for example used to be sent to a terminal of low capacity.
  • the latter thus benefits from displaying a three-dimensional image of acceptable quality while using less computational resources than if he himself computed a conventional rendering of three-dimensional image.
  • the method comprises the additional step of detecting, in the first pixel image obtained at the end of the first application step, the exterior and interior contours of the color and topologically independent regions. said pixel image.
  • This saving of memory resources may be essential to allow a low-capacity terminal using the invention to provide a good quality of service, especially in the case of a video service.
  • the method comprises the additional step of polygonal approximation by subdivision of the contours detected at the end of the additional detection step, in vector contours, to obtain a two-dimensional vector image.
  • This vector coding simplifies the coding of the two-dimensional image obtained, and makes it possible to further reduce the memory resources necessary for this coding.
  • each vector contour obtained is oriented along a direction of travel, which indicates whether said vector contour is an inner contour or an outer contour of a colored region of the obtained two-dimensional vector image.
  • This orientation obeys a recognized convention of vector coding and makes it possible to obtain a vector image easily reusable by formats of type SVG, according to the English Scalable Vector Graphics.
  • the contours detected at the end of the additional detection step pass between the adjacent pixels of each colored and topologically independent region of the first pixel image obtained at the end of the step. first application.
  • This positioning of the contours makes it possible to dilate the external contours and to contract the inner contours, which has the advantage of eliminating any parasitic pixels between two regions. Indeed, the numerical approximation due to the projection step may cause pixels of image background between regions which should instead be touching.
  • the method comprises the additional steps of:
  • the method comprises the additional steps of detecting, in the second pixel image obtained at the end of the second application step, distinct sets of pixels marking fold lines, and polygonal approximation by subdivision of said fold lines into vector fold lines.
  • the coding of the fold lines in vector form makes it possible to integrate them into the coding format of the vector image obtained previously, containing the vector contours of the two-dimensional image resulting from the process.
  • the invention also relates to a method of using successive vector images obtained at the end of the additional polygonal approximation step of the conversion method, said conversion method being applied to three-dimensional images of an animation for producing said successive vector images, characterized in that a current vector image of said successive vector images is corrected using a previous vector image, in order to limit the discontinuities of movement between said vector images.
  • the invention also relates to a computer program comprising instructions for implementing the methods of converting a three-dimensional image into a two-dimensional image, and using images. vectors in an animation, according to the invention, when said program is executed on a computer.
  • the invention also relates to a device for converting a three-dimensional image into a two-dimensional image containing means for implementing the previously presented methods.
  • the invention also relates to a graphics engine containing means for implementing the previously presented methods.
  • the device for converting a three-dimensional image into a two-dimensional image and the graphics engine have advantages similar to those of the processes.
  • FIG. 1 represents the different steps of the method according to the invention
  • FIG. 2 represents the steps of the algorithm used during the first step of the method according to the invention
  • FIG. 3 represents a three-dimensional image inside a pyramid of view formed by the angle of view of an observer
  • FIG. 4 represents a pixel image obtained at the end of the second step of the method according to the invention
  • FIG. 5 represents a triangle of a three-dimensional image seen from the front and a triangle of a three-dimensional image seen from behind, from the point of view of an observer
  • FIG. 6 represents an image of pixels obtained at the end of the second step of the method according to the invention, carried out according to a first variant
  • FIG. 7 represents an image of pixels obtained at the end of the second step of the method according to the invention, carried out according to a second variant
  • FIG. 8 represents the steps of carrying out the second step of the method according to the invention, according to a second variant
  • FIG. 9 represents an outer contour of a pixel region
  • FIG. 10 represents the steps of an edge detection algorithm used during the third step of the method according to the invention.
  • FIG. 11 represents the steps of a polygonal approximation algorithm by subdivision of an edge of pixel regions, used during the fourth step of the method according to the invention
  • FIG. 12 represents an outline of a region of pixels subdivided into two outlines
  • FIG. 13 represents a contour of a region of pixels subdivided into four outlines
  • FIG. 14 shows the use of an enlarged pixel image to expand outward contours of regions and to contract interior contours of regions.
  • the elements of the meshes of a three-dimensional image are converted into a set of two-dimensional zones, which can be represented by minimizing the number of vectors per contour.
  • the elements of a mesh of the three-dimensional image are described in terms of vertices, edges between these vertices, and triangles or polygons formed by these vertices and edges. These elements describe one or more three-dimensional objects in the image that have a common property, for example the same texture.
  • a mesh can therefore be represented as a graph, in which each vertex of the graph is a vertex of the mesh, and in which the edges of the graph are the edges that connect the vertices of the mesh.
  • the meshes of the three-dimensional image do not include polygons with more than three sides. It should be noted that a three-dimensional image mesh also contains many other data about its elements, which will not be detailed here, such as data on their texture, color or lighting.
  • a first step E1 of the method according to the invention represented in FIG. 1, the meshes of the three-dimensional image are divided into components.
  • the components of a three-dimensional mesh are the elements of the mesh that are not topologically related to each other.
  • each eye forms a component of the mesh.
  • the graph formed by this mesh is traversed vertex by vertex, so as to determine the elements of the graph which are independent of each other, of a topological point of view.
  • steps E2, E3 and E4 of the process according to the invention correspond respectively to: - The creation of a symbolic image, corresponding to a visualization of the three-dimensional image according to the point of view of an observer, - The detection of the different colored regions of this symbolic image, - And to an approximation of the contours of these regions by vector contours.
  • All these steps of the method according to the invention can be implemented in a graphics rendering engine, such as OpenGL or DirectX.
  • a graphics rendering engine such as OpenGL or DirectX.
  • the realization of the symbolic image can use an engine of graphic rendering initialized so that lighting and anti-aliasing options are not used.
  • intermediate data are stored in specific memories, as detailed below. Nevertheless the other intermediate data, even if not explicitly indicated, may be stored in memory until the final two-dimensional image resulting from the method according to the invention is obtained.
  • Step E1 is explained through the steps of the flow chart of Figure 2, which are as follows:
  • the first step ai is the initialization to zero of a counter called
  • ComponentNum which makes it possible to number all the components of all the meshes of the three-dimensional image in a unique way. It should be noted that although the numbering of a component of the image does not include a reference to the mesh to which this component belongs, this membership is retained in the data associated with each component obtained during step E1. This allows the end of the process to recolor each area of the two-dimensional image from the process in a color approximated to that of the three-dimensional component at the origin of this area.
  • the next step a2 is the selection of a mesh M not already scanned in the three-dimensional image. For example, if the list of meshes of the image is copied into a variable in which the meshes traversed are deleted as and when, just select the first mesh of this variable.
  • the next step a3 is the verification that the mesh M selected in step a2 exists, that is to say that all the meshes of the image have not already been browsed. If all the meshes of the image have been traveled, the step E1 is completed, all the components of the image being identified by a component number. Otherwise the next step is step a4. Step a4 is the search for the first vertex S in the selected mesh M that is not already marked as belonging to a component.
  • the next step a5 is the verification of the existence of this vertex S sought in step a4. If no untagged vertex has been found, it is because the selected mesh M is completely traversed, and the next step is step a6. In the opposite case, that is to say if the vertex S exists, the next step is step a1.
  • Step a6 is the marking of the mesh M as a traversed mesh, for example by deleting it from the list of meshes, and the transition to the next mesh that has not already been traversed by returning to step a2.
  • Step a7 is the recursive path of all the vertices connected to the vertex S, marking them as belonging to the number component "ComponentNum".
  • step a8 is the incrementation of a unit of the counter "ComponentNum" to find a possible other component not yet identified in the mesh M selected.
  • step a ⁇ is followed by step a4.
  • step E2 of the method according to the invention.
  • FIG. 1 Two variant embodiments of step E2 are presented.
  • the components of the three-dimensional image, represented in FIG. 3 in an orthonormal frame (O, x, y, z) are projected onto a local reference projection surface Sf (O ', X , Y), from the point of view Po of an observer.
  • Sf a local reference projection surface
  • Compi which is a rectangular surface
  • Comp2 which is a triangular surface
  • each pixel of the surface Sf is initialized without color marking and recorded in a memory space called "frame-buffer".
  • the depths of each pixel of the surface Sf are initialized with a depth much greater than that of the components of the three-dimensional image, and are recorded in a memory space called "Z-buffer”.
  • Each projected component is assigned a different color for each component, and then this component is scanned pixel by pixel on the surface Sf, according to the conventional algorithm called "Z-buffer”: during this course, the depth and the color of a pixel of the component are respectively stored in the memory “Z-buffer” and the memory “frame-buffer” if the depth of this pixel is less important than the depth of the corresponding pixel stored in the memory "Z- buffer ".
  • the pixel depth of a component is calculated from the depth coordinates retained for each component during its projection on the surface Sf Thus, only the data corresponding to the pixels closest to the observer are stored in the memories "Z-buffer” and "frame-buffer".
  • a symbolic pixel image is obtained in which each projected component is associated with a color and in which portions of the three-dimensional image that are not visible from the observer are not represented.
  • the symbolic image IS1 obtained at the end of step E2 in the example given in FIG. 3 is represented in FIG. 4.
  • step E2 only the triangles seen from the front of the components of the three-dimensional image on the surface Sf are projected from the point of view Po. These triangles are then applied to these triangles.
  • 'Z-buffer' algorithm as in the first variant previously described, the triangles of different components being colored with different colors.
  • the triangles seen from behind components of the three-dimensional image are then projected in turn on the surface Sf.
  • the triangles of different components are colored with different colors, not previously used during the first application of the "Z-buffer” algorithm.
  • the triangles seen from the front of a component are distinguished from the triangles seen from behind by this same component by the orientation of the normal vectors associated with each of the triangular surfaces of the component.
  • These normal vectors are usually used by graphics engines to calculate lighting on different surfaces of a three-dimensional object from a light source.
  • the orientation of the normal vectors of each of the triangles of a component with respect to the projection surface Sf makes it possible to determine whether a given triangle is seen from the front or seen from behind from the point of view Po of an observer , represented in FIG. 5.
  • the vector normal to a triangle TrA is directed towards the space of the observer, this triangle is seen from the front.
  • the vector normal to a triangle TrB is directed to the other side, this triangle is seen from behind.
  • This second variant embodiment of the step E2 makes it possible to obtain a symbolic image in which the elements of a component seen from the front have a color different from the elements of this same component seen from behind. This allows in some cases to better visualize the perspective of objects in three dimensions, such as a ribbon which we see a part of the back.
  • FIG. 6 represents the symbolic image IS2 obtained with a ribbon when this second variant of step E2 is used, and FIG.
  • step E2 represents the symbolic image IS3 obtained with this same ribbon when it is sufficient to use the first variant of step E2.
  • step E2 The flowchart of FIG. 8 explains the steps of the second variant embodiment of step E2, detailed below.
  • the first step b1 is the initialization of variables useful for the realization of this variant:
  • CompNum a number called “CompNum” of the component to be processed in the three-dimensional image, is initialized to zero, the coloring color called “CouleurNum”, used during the application of the "Z-buffer” algorithm, is initialized to a very low gray level,
  • the memory "Z-buffer" which preserves the depths of all the pixels of the projection surface Sf, is initialized to a maximum depth for all the pixels, for example an infinite depth
  • the "frame-buffer” memory which keeps the colors of all the pixels of the surface Sf, is also initialized with a so-called background color, which is not used as coloring color "ColorNum", for all the pixels .
  • the next step b2 is the selection of the component c of number "CompNum" in a list of components of the three-dimensional image.
  • the next step b3 is the verification of the existence of the component c obtained in step b2. If the component c does not exist, it is because all the components of the three-dimensional image have been processed. In this case the next step is step b9, otherwise the next step is step b4.
  • Step b4 is the determination of the triangles seen from the front of the component c. This determination uses the normal vectors associated with these triangles, as explained previously.
  • the next step b5 is the projection of the triangles obtained in step b4 on the projection surface Sf, with respect to the point of view Po. The depths of the vertices of these triangles are kept in the coordinates of the projected triangles.
  • the next step b6 is the application of the "Z-buffer" algorithm to the triangles projected in step b5, each triangle being colored with the gray level "ColorNum”.
  • the next step b7 is the incrementation of a unit of the "CompNum" number of the component to be processed, to consider a next component.
  • the next step b ⁇ is likewise the incrementation of a unit of the gray level "CouleurNum”.
  • the next step is again step b2, to process another component, all the triangles seen from the front of all the components of the three-dimensional image to be projected and then subjected to the Z-buffer algorithm before go to step b9.
  • Step b9 is the reset to zero of the "CompNum” number of the component to be processed. It should be noted that the color "CouleurNum” to be applied during the algorithm of the "Z-buffer” is not reinitialized, since the elements of the components seen from behind will not be colored of the same color as those seen from before . At this stage, all components of the three-dimensional image have already passed through steps b4 to b6.
  • the "Z-buffer” memory as well as the "frame-buffer” memory contain the depth and color data of the pixels of the elements seen from the front of the three-dimensional image, projected onto the surface Sf. is the selection of the number c component
  • the next step b11 is the verification of the existence of component c. If the component c does not exist, it is because all the components of the three-dimensional image have been processed. In this case, the step E2 according to the second embodiment is completed, and the "frame-buffer" memory contains the symbolic image made of pixels colored with the various "ColorNum” gray levels used. Otherwise the next step is step b12.
  • Step b12 is the determination of the triangles seen from behind of the component c. This determination uses the normal vectors associated with these triangles, as explained previously.
  • the next step b13 is the projection of the triangles obtained in step b12 on the projection surface Sf, with respect to the point of view Po. The depths of the vertices of these triangles are kept in the coordinates of the projected triangles.
  • the next step b14 is the application of the "Z-buffer" algorithm to the triangles projected in step b13, each triangle being colored with the "ColorNum” gray level.
  • the next step b15 is the incrementation of a unit of the "CompNum" number of the component to be processed, to consider a next component.
  • the next step b16 is likewise the incrementation of a unit of the gray level "ColorNum”.
  • the next step is again step b10, to process another component, all the triangles seen from behind all the components of the three-dimensional image to be projected and then submitted to the Z-buffer algorithm to obtain the symbolic image.
  • the symbolic image obtained at the end of step E2 has the following properties: It contains as many or more zones of different colors as there are components present in the three-dimensional image. It contains at most the same number triangles than triangles in the three-dimensional image.
  • the finality of the symbolic image obtained is not to be visualized, given, among other things, that it consists of pixels, which is very expensive in memory resources, and that its colors are not those of the original three-dimensional image.
  • One way of coding this symbolic image in a less expensive way in memory resources is to have a description of the contours of each zone of different color in the symbolic image. These areas are in the following called regions. This detection of the outlines of the regions of the symbolic image is the object of step E3, represented in FIG.
  • a region is defined by a set of pixels of the same component color, contained within an outer contour, and possibly outside one or more inner contours if holes or other regions are present within this first region.
  • a hole is defined by an inner contour of a region, and may contain both unicoloured, i.e., non-component, and colored pixels of other regions.
  • the unicoloured pixels indeed correspond to the background color of the symbolic image. It should be noted that several regions of the symbolic image may have the same color, for example if from the point of view Po a sectional component another in two.
  • An outline is defined by a sequence of pixel vertices, and by a direction of travel of this sequence of pixels.
  • an outer contour is a series of vertices of pixels that travels in the opposite direction of the trigonometric direction the outer contour of the region with which it is associated.
  • An example of an outer contour is given in FIG. 9.
  • the outer contour of the region formed by the pixels p22, p23, p33 and p34, the pixel pij denoting the pixel located on the line i and the column j of a symbolic image is the sequence of vertices ⁇ s22, s23, s24, s34, s35, s45, s44, s43, s33, s32 ⁇ , where sij denotes the top left vertex of the pixel pij.
  • An inner contour is a series of vertices of pixels that trigonometrically traverses the edge of a hole in the region associated with that contour.
  • an outline is described as a list of left superior vertices of pixels ⁇ si, ..., s n ⁇ , which must be traversed in the order of this list, and where n is an integer greater than one.
  • an oriented edge (sij, ski) of this contour is the edge coming from the vertex sij and from the ski end, where sij and ski are the upper left vertices respectively of the pixels pij and pkl.
  • An example of an algorithm for monitoring the external course of a region uses as a starting point an oriented edge (sij, ski) belonging to the outer contour of this region.
  • an example of an algorithm for tracking an inner course of a region uses as a starting point an oriented edge (sij, ski) belonging to this inner contour. From this edge, we look for the vertex smn such that the oriented edge (ski, smn) belongs to an edge of the region and is directed as far as possible to the left with respect to (sij, ski), without returning to back. We do the same from the oriented edge (ski, smn), and recursively we build a list of vertices until we return to the starting vertex sij. The list of vertices thus obtained at the end of the algorithm describes an inner contour of the region.
  • this image is traveled line by line from left to right.
  • a buffer image is used to store the contours and regions detected as the symbolic image travels. In particular, it makes it possible to determine whether a pixel of the symbolic image has already been traversed, whether it is on an already detected region, or whether one of its edges belongs to an already traversed contour. It should be noted that following step E2, the colors of the pixels of the symbolic image make it possible to connect each region of the buffer image to a component of the three-dimensional image.
  • the first step d is the initialization of the buffer image, so that it does not contain any contours or regions at this stage of the algorithm.
  • the current pixel p of course of the image defined as located at the current line "line” and the current column "col" is also initialized to the first upper left pixel of the image.
  • the current line is therefore initialized to the first line and the current column in the first column of the image.
  • the next pixel is defined as located on the same line as the current pixel but on the column immediately to the right of the current column. It is therefore initialized in the first line and in the second column of the image.
  • the next step c2 is a test on the current pixel.
  • next step is step c3, otherwise the next step is step c7.
  • Step c3 is again a test on the current pixel. If the current pixel belongs to a region of the buffer image, it is that the detected contour is an inner contour of this region. In this case the next step is step c11.
  • Step c4 is the creation of new region R variables and outer contour C, corresponding to the new region and new contour detected in steps c2 and c3.
  • the next step c5 is the tracking of the outer contour C, using the algorithm described above with the initial edge as the upper edge of the next pixel, oriented to the right.
  • the next step c6 is updating the buffer image with the contour
  • next step c7 is a test on the next pixel. If the next pixel is at the end of the line, we go to step c ⁇ , otherwise we go to step c10. Step c ⁇ is again a test on the next pixel. If this one is on the last line, then the image has been completely traversed, the algorithm of course is finished. Otherwise the next step is step c9.
  • Step c9 is updating the current pixel p to the first column of the line that follows the current line.
  • the current line, the current column, and the next pixel are also updated according to this new pixel current.
  • the next step is then again step c2, to continue the path of the image.
  • Step c10 is also the updating of the current pixel p to the next pixel, but in the case where the current pixel p was not at the end of the line.
  • the current line, the current column, and the next pixel are updated according to the new current pixel.
  • the next step is again step c2, to continue the path of the image.
  • Step d 1 is the creation of a new inner contour variable, corresponding to the new contour detected in step c2.
  • the next step c12 is the tracking of the inner contour created in step d 1, using the algorithm described above with the left edge of the next pixel downward as the initial edge.
  • the next step c13 is the update of the buffer image with the inner contour created in step c11 and completed in step c12, associated with the region to which the current pixel belongs.
  • the next step c14 is a test on the color of the current pixel. If the current pixel has the same color as the background of the image, the process of moving the image is continued by going to step c7. Otherwise, it means that a new region has just been detected inside the hole previously detected in step c3. The next step is then step c4, in order to determine the new detected region and its associated external contour
  • the buffer image contains all the regions and outlines of the symbolic image.
  • the outer contours obtained are dilated and the inner contours are contracted to remove any parasitic pixels having the background color between the regions of the symbolic image. Indeed the calculations necessary for the projection of the components during the step E2 induce numerical approximation errors likely to cause the appearance of these parasitic pixels.
  • One way to effect this expansion of the outer contours and contraction of the inner contours is to use an ISA symbolic image shown in FIG. 14, enlarged by one pixel in width and one pixel in height relative to the symbolic image. original ISO. The original symbolic image is superimposed on this enlarged image, centered on the enlarged symbolic image.
  • the contours of the regions contained in the buffer image are then plotted on the original symbolic image.
  • the buffer image contains an inner contour CIO and an outer contour CEO.
  • the outer contours are then plotted on the enlarged symbolic image by rounding the outer contours of the original image to the nearest outer edges in the enlarged image.
  • the inner contours are likewise drawn on the enlarged symbolic image but round the inner contours of the original image to the nearest inner edges in the enlarged image.
  • the outer outline OWC is rounded to the outer contour CEA on the enlarged symbolic image, while the inner contour CIO disappears on the enlarged symbolic image, thus eliminating a parasitic pixel.
  • the outlines of the enlarged symbolic image thus obtained are then reduced to the format of the original symbolic image to obtain new inner and outer contours respectively contracted and dilated.
  • the last step E4 of the method represented in FIG. buffer image in a series of vector contours of regions.
  • the colors of the regions associated with these contours are stored in memory in order to produce, by correspondence with the initial colors of the meshes of the three-dimensional image, a two-dimensional image that looks like the visualization of the initial three-dimensional image, from the point of view Po.
  • Step E4 uses the algorithm shown in FIG. 11 to transform a contour of the buffer image, formed by successive pixel vertices, into a limited sequence of vectors reproducing the contour according to the desired accuracy.
  • the steps of this algorithm are as follows, the first four steps used to initialize the algorithm:
  • the first step d1 consists in finding the vertices S 1 and S 2 furthest away from a contour C 0 of the buffer image, represented in FIG. 12.
  • the next step d2 is the construction of two contours Ci and C 2 associated respectively with the vectors ⁇ ⁇ and V 2 , such that ⁇ ⁇ is the vectors ⁇ ,
  • contour C 0 is defined by the following vertexes - n is an integer greater than 1
  • contour Ci is defined by the following of vertices ⁇ if S ⁇ i, Si, S 2 ,
  • the next step d3 is the creation of a vector contour C v , initially empty and which will contain at the end of the algorithm the sequence of vectors describing C 0 .
  • the next step d4 is the creation of a list of contours to subdivide, each contour of the list being associated with a vector.
  • This list is initialized with the contours Ci and C 2 , associated respectively with the vectors Vi and V 2 .
  • the next step d5 is the selection in the list of contours to be subdivided, of a current contour C 1 associated with a current vector Vi.
  • This current contour is for example the first contour of the contour list to be subdivided.
  • the next step d6 is a test on the existence of the current contour Cj. If this contour does not exist, it means that the list of contours to be subdivided is empty, which means that the algorithm is finished. Otherwise the next step is step 61.
  • Step d7 is the determination in the current contour C 1 of the vertex S Ma ⁇ belonging to this current contour which is furthest from the current vector Vi.
  • Step d8 is a test on the distance D max between the vertex S Ma ⁇ and the current vector Vi. If this distance is greater than a threshold D seu ii, which sets the desired accuracy of approximation of the contour C 0 by the vector contour C v , then the determination of other vectors closer to the current contour C 1 than the vector is continued. current Vi by going to step d11. In the opposite case, the precision obtained is acceptable and the next step is step d9.
  • Step d9 is the addition to the contour C v of the inverse -Vi of the current vector
  • the next step d10 is the deletion of the current contour C 1 in the list of contours to be subdivided. Indeed the accuracy of the current vector Vi is sufficient to approach the current contour C 1 , it no longer needs to be subdivided.
  • the next step is step d5, in order to continue the algorithm with the processing of the remaining contours to be subdivided.
  • Step d11 is the subdivision of the current contour into two contours C k and
  • Ci associated respectively with the vectors Vk and V / such that if the current contour C 1 is defined by the sequence of vertices ⁇ si, ..., s h , ..., s m ⁇ , where: h and m are integers such that 1 ⁇ h ⁇ m,
  • the current vector is the vector S 1n S 1 , and S Ma ⁇ is the vertex s h , then the contour C k is the contour defined by the sequence of vertices ⁇ s h , s h- i, ..., S 2 , Si ⁇ and the contour d by the following of vertices ⁇ s m , s m- i, ..., s h + i, s h ⁇ , the vector Vk being the vector ⁇ and the vector V / being the vector s h s m .
  • the next step d12 is the addition of the contours C k and d associated respectively with the vectors Vk and V /, in the list of contours to be subdivided, for example at the beginning of the list.
  • the next step d13 is the deletion of the current contour C 1 in the list of contours to be subdivided, since this contour has just been replaced by two other contours.
  • the next step is step d5, the contours to be subdivided being processed until the vectors satisfactorily approach the contours with which they are associated.
  • the contour C 0 has been subdivided into four contours C 3 , C 4 , C 5 and C 6 , associated respectively with the vectors V 3 , V 4 , V 5 and V 6 .
  • the final vector contour C v corresponding to the contour C 0 is therefore the contour ⁇ -V 6 , -V 5 , -V 4 , -V 3 ⁇ .
  • a two-dimensional vector representation of the initial three-dimensional image is obtained for each from which the direction of travel makes it possible to determine whether it is an outer contour or an inner region contour. It is then sufficient to reassociate each region of this representation with the original color of the corresponding mesh in the initial three-dimensional image, to obtain a visualization of the initial three-dimensional image from a point of view of an observer under shape of a two-dimensional vector image.
  • This vector image is easily reusable by image presentation software using the SVG format for example, according to the English Scalable Vector Graphics, and is very inexpensive in memory resources.
  • the application of the invention to a three-dimensional image animation may present visual discomfort due to discontinuity phenomena, the different two-dimensional vector images obtained being calculated independently of one another.
  • the coherence of the temporal movement of the different vector contours associated with these images is indeed affected by the different steps of the conversion process, in particular the polygonal approximation step, which does not take into account the notion of movement of the processed image. in an animation.
  • step E4 to soften the movements of the vector contours during the animation, instead of using the polygonal approximation algorithm, the vector contours of the previous image in the animation are used.
  • Each vector contour of the preceding image is applied to the corresponding inner or outer contour in the current buffer image of the animation, by a method of elasticity: from the center of the inner or outer contour, the vertices of the contour are deformed vector that is superimposed on them by projecting them on the inner or outer contour of the current image. For each region of the current image, one thus obtains one or more corresponding vector contours.
  • a vector contour and its associated region contour form a series of contours, comparable to an intermediate result of the polygon approximation algorithm previously described, that is to say to a list of contours to be subdivided.
  • We can therefore use this algorithm to correct the vector contour the algorithm being initialized with a list of contours to subdivide containing this sequence of outlines. So if the vector outline is close enough to the corresponding contour, it is used as is in the animation, otherwise it is subdivided using the polygon approximation algorithm.
  • This use of the previous vector contours to obtain current vector contours makes it possible to soften the movements, because the vertices of the vector contours move less, which improves the visualization of the animation.
  • the first embodiment of the method according to the invention described above is enriched by adding, in the two-dimensional image resulting from the process, lines which mark the folds. important components of the initial three-dimensional image.
  • This second embodiment is interesting when the detection of these fold lines by the graphics rendering engine that uses this method does not use excessive computing resources.
  • the fold lines are treated independently of the other components of the initial three-dimensional image, which is processed according to the steps E1 to E4 described above.
  • the important fold lines of the three-dimensional image are first identified.
  • One way of detecting these fold lines is, for example, to traverse all the pairs of adjacent triangles within each of the components identified in step E1. During this course, if two adjacent triangles form an acute angle less than a certain threshold at their common edge, then this edge is potentially an important fold line to take into account.
  • edges There are two types of edges to distinguish:
  • the silhouette edges are edges that share two triangles, one of which is a front face and the other a back side, that is, the normals of these triangles point in different directions from the point of view Po.
  • the folding edges are edges which share two triangles forming a very pronounced angle, but which are either both front faces are both rear faces.
  • the silhouette lines are reproduced as contour lines after the projection on the surface Sf during the step E2 and therefore do not require a separate projection.
  • the "frame-buffer” memory and the "Z-buffer” memory obtained at the end of step E2 which contain the symbolic image, are copied for use in processing fold lines. These are projected onto the projection surface Sf, from the point of view Po, the depths of the vertices that compose them being stored in memory, then processed according to the "Z-buffer” algorithm from the copy of the memories "Z-buffer” and "frame-buffer” obtained at the end of step E2.
  • the fold lines are colored during this treatment with a color distinct from those used in step E2, for example in black. This makes it possible to obtain only the parts visible from the point of view Po, fold lines in the three-dimensional image. At the end of this treatment we obtain a symbolic image enriched with fold lines, and distinct from that used in step E3.
  • This symbolic image enriched with folding lines is then scanned pixel by pixel in order to code these features as distinct sets of pixels. These pixel sequences are considered as undirected contours.
  • step E4 the algorithm used in step E4 can be reused, but starting directly at step d4 shown in FIG. 11.
  • the list of contours to be subdivided at step d4 of initialization of the algorithm contains only this contour, the latter being associated with a vector joining the pixels which are located at the ends of the fold line by their vertices.
  • the algorithm of step E4 is reused without modifications.
  • the vector fold lines are then added to the vector image obtained at the end of step E4.
  • a visualization of the initial three-dimensional image from the point is obtained. view of an observer in the form of a two-dimensional vector image, but enriched with fold lines that better reflect the perspective of the objects represented.

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Geometry (AREA)
  • Computer Graphics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Image Generation (AREA)

Abstract

L'invention concerne un procédé de conversion d'une image à trois dimensions en image à deux dimensions, caractérisé en ce qu'il comporte les étapes de: Détermination (E1) de composantes indépendantes du point de vue topologique, de ladite image à trois dimensions, Projection (E2) sur une surface (Sf) depuis un point de vue (Po), d'au moins une partie de chacune des composantes déterminées, les profondeurs, dans une pyramide de vue formée par ledit point de vue, des sommets des parties des composantes déterminées étant conservées dans les données des parties de composantes projetées, Première application (E2) de l'algorithme dit du 'Z-buffer' aux parties de composantes ainsi projetées, et coloriage uniforme desdites parties de composantes projetées, des couleurs distinctives, sans corrélation avec leurs couleurs d'origine, étant attribuées à respectivement chacune desdites parties de composantes, afin d'obtenir une première image de pixels.

Description

Procédé de conversion d'une image à trois dimensions en image à deux dimensions
La présente invention concerne de manière générale le domaine du traitement d'images, et en particulier les procédés de conversion d'images à trois dimensions en images à deux dimensions.
Les systèmes actuels de traitement d'images à trois dimensions permettent de visualiser des images fixes ou animées d'objets à trois dimensions. Lorsque ces systèmes, ou moteurs graphiques, sont utilisés sur un terminal de faible capacité de calcul de rendu graphique, par exemple sur un terminal mobile, la visualisation, ou rendu, d'une image à trois dimensions sur le terminal utilise d'importantes ressources de calcul, et dégrade la qualité du service qui utilise le moteur graphique du terminal.
Une façon de diminuer les ressources de calcul nécessaires, par exemple lorsqu'un terminal mobile doit afficher des images à trois dimensions reçues depuis un système distant, est de convertir ces images à trois dimensions en images à deux dimensions, plus simples que les rendus correspondants.
Il existe notamment des formats d'images vectorielles à deux dimensions qui permettent une représentation intermédiaire entre une image à trois dimensions et l'image de rendu sur un terminal. Ceux-ci présentent l'avantage de supprimer une partie du calcul sur le terminal, avec un format de représentation réduit par rapport à une image de pixels à deux dimensions. Les systèmes de conversion d'images à trois dimensions en images vectorielles à deux dimensions sont basés sur la projection de chaque polygone ou triangle de l'image à trois dimensions sur une surface de projection, chaque polygone ou triangle étant projeté un par un. Chaque triangle ou polygone projeté est ensuite codé sous forme vectorielle, les triangles ou polygones adjacents pouvant parfois être fusionnés dans un même contour vectoriel. Ces systèmes présentent néanmoins l'inconvénient d'utiliser beaucoup de place mémoire, puisque chaque triangle ou polygone de l'image initiale est codé sous forme vectorielle. De plus, ces systèmes ne permettent pas de régler efficacement les problèmes de chevauchements entre plusieurs triangles ni de distinguer si un triangle est devant ou derrière un autre triangle lorsque les deux triangles sont intersectés.
La présente invention a pour but de résoudre les inconvénients de la technique antérieure en fournissant un procédé et des dispositifs permettant de convertir une image à trois dimensions en image à deux dimensions, et de coder l'image obtenue en image vectorielle, éventuellement enrichie de traits de pliure. Le procédé de conversion règle les problèmes de chevauchements entre triangles intersectés. De plus l'image vectorielle issue du procédé minimise les ressources mémoires nécessaires à son stockage en fonction de la précision souhaitée. Enfin les images vectorielles issues de l'invention sont utilisables dans une animation en limitant les phénomènes de discontinuité de mouvement entre les images vectorielles successives.
A cette fin, l'invention propose un procédé de conversion d'une image à trois dimensions en image à deux dimensions, caractérisé en ce qu'il comporte les étapes de:
- Détermination de composantes indépendantes du point de vue topologique, de ladite image à trois dimensions,
- Projection sur une surface depuis un point de vue, d'au moins une partie de chacune des composantes déterminées, les profondeurs, dans une pyramide de vue formée par ledit point de vue, des sommets des parties des composantes déterminées étant conservées dans les données des parties de composantes projetées,
- Première application de l'algorithme dit du "Z-buffer" aux parties de composantes ainsi projetées, et coloriage uniforme desdites parties de composantes projetées, des couleurs distinctives, sans corrélation avec leurs couleurs d'origine, étant attribuées à respectivement chacune desdites parties de composantes, afin d'obtenir une première image de pixels.
L'invention permet avantageusement de s'affranchir des problèmes de chevauchements entre triangles des composantes de l'image à trois dimensions lors de leur projection. L'image en trois dimensions ainsi convertie par le procédé selon l'invention est par exemple utilisée pour être envoyée à un terminal de faible capacité. Ce dernier bénéficie ainsi d'un affichage de l'image à trois dimensions de qualité acceptable tout en utilisant moins de ressources de calcul que s'il calculait lui-même un rendu classique d'image à trois dimensions.
Selon une caractéristique préférée, le procédé comporte l'étape supplémentaire de détection, dans la première image de pixels obtenue à l'issue de l'étape de première application, des contours extérieurs et intérieurs des régions coloriées et indépendantes du point de vue topologique de ladite image de pixels.
Ceci permet de limiter les ressources mémoires nécessaires au codage de l'image de pixels obtenues. Cette économie de ressources mémoires peut s'avérer indispensable pour permettre à un terminal de faible capacité utilisant l'invention de rendre une bonne qualité de service, notamment dans le cas d'un service vidéo.
Selon une caractéristique préférée, le procédé comporte l'étape supplémentaire d'approximation polygonale par subdivision des contours détectés à l'issue de l'étape supplémentaire de détection, en des contours vectoriels, afin d'obtenir une image vectorielle à deux dimensions.
Ce codage vectoriel simplifie le codage de l'image à deux dimensions obtenue, et permet de diminuer encore les ressources mémoires nécessaires à ce codage.
Selon une caractéristique préférée, chaque contour vectoriel obtenu est orienté suivant un sens de parcours, qui indique si ledit contour vectoriel est un contour intérieur ou un contour extérieur d'une région coloriée de l'image vectorielle à deux dimensions obtenue. Cette orientation obéit à une convention reconnue de codage vectoriel et permet d'obtenir une image vectorielle facilement réutilisable par des formats de type SVG, d'après l'anglais Scalable Vector Graphics.
Selon une caractéristique préférée, les contours détectés à l'issue de l'étape supplémentaire de détection passent entre les pixels limitrophes de chaque région coloriée et indépendante du point de vue topologique de la première image de pixels obtenue à l'issue de l'étape de première application.
Ce positionnement des contours permet de dilater les contours extérieurs et de contracter les contours intérieurs, ce qui a l'avantage de supprimer d'éventuels pixels parasites entre deux régions. En effet l'approximation numérique due à l'étape de projection peut faire apparaître des pixels de fond d'image entre régions qui devraient au contraire se toucher.
Selon une caractéristique préférée, le procédé comporte les étapes supplémentaires de:
Détection de traits de pliure des composantes de ladite image à trois dimensions,
Projection desdits traits de pliure sur une surface depuis un point de vue, les profondeurs, dans une pyramide de vue formée par ledit point de vue, des sommets desdits traits de pliure étant conservées dans les données des traits de pliure projetés, Deuxième application auxdits traits de pliure de l'algorithme du "Z-buffer", initialisé avec des données issues de l'étape de première application, et coloriage desdits traits de pliure avec une couleur distincte de celles utilisées à l'étape de première application, afin d'obtenir une seconde image de pixels.
Le fait de projeter aussi certains traits de pliure importants permet d'obtenir une image à deux dimensions plus réaliste, puisqu'elle met en avant la perspective de certaines composantes de l'image à trois dimensions initiale. Selon une caractéristique préférée, le procédé comporte les étapes supplémentaires de détection, dans la seconde image de pixels obtenue à l'issue de l'étape de deuxième application, des ensembles distincts de pixels marquant des traits de pliure, et d'approximation polygonale par subdivision desdits traits de pliure en des traits de pliure vectoriels.
Le codage des traits de pliure sous forme vectorielle permet de les intégrer dans le format de codage de l'image vectorielle obtenue précédemment, contenant les contours vectoriels de l'image à deux dimensions issue du procédé.
L'invention concerne aussi un procédé d'utilisation d'images vectorielles successives obtenues à l'issue de l'étape supplémentaire d'approximation polygonale du procédé de conversion, ledit procédé de conversion étant appliqué à des images en trois dimensions d'une animation pour produire lesdites images vectorielles successives, caractérisé en ce qu'une image vectorielle courante desdites images vectorielles successives est corrigée en utilisant une image vectorielle précédente, afin de limiter les discontinuités de mouvement entre lesdites images vectorielles.
Cela permet de limiter les discontinuités lors de la visualisation d'une animation utilisant le procédé de conversion d'image selon l'invention.
L'invention concerne aussi un programme d'ordinateur comportant des instructions pour mettre en œuvre les procédés de conversion d'une image à trois dimensions en image à deux dimensions, et d'utilisation d'images vectorielles dans une animation, selon l'invention, lorsque ledit programme est exécuté sur un ordinateur.
L'invention concerne encore un dispositif de conversion d'une image à trois dimensions en image à deux dimensions contenant des moyens de mise en œuvre des procédés précédemment présentés.
L'invention concerne aussi un moteur graphique contenant des moyens de mise en œuvre des procédés précédemment présentés.
Le dispositif de conversion d'une image à trois dimensions en image à deux dimensions et le moteur graphique présentent des avantages analogues à ceux des procédés.
D'autres caractéristiques et avantages apparaîtront à la lecture de modes de réalisation préférés décrits en référence aux figures dans lesquelles
- la figure 1 représente les différentes étapes du procédé selon l'invention,
- la figure 2 représente les étapes de l'algorithme utilisé lors de la première étape du procédé selon l'invention,
- la figure 3 représente une image à trois dimensions à l'intérieur d'une pyramide de vue formée par l'angle de vue d'un observateur,
- la figure 4 représente une image de pixels obtenue à l'issue de la deuxième étape du procédé selon l'invention,
- la figure 5 représente un triangle d'une image à trois dimensions vu de devant et un triangle d'une image à trois dimensions vu de derrière, depuis le point de vue d'un observateur,
- la figure 6 représente une image de pixels obtenue à l'issue de la deuxième étape du procédé selon l'invention, réalisée selon une première variante, - la figure 7 représente une image de pixels obtenue à l'issue de la deuxième étape du procédé selon l'invention, réalisée selon une seconde variante,
- la figure 8 représente les étapes de réalisation de la deuxième étape du procédé selon l'invention, selon une seconde variante,
- la figure 9 représente un contour extérieur d'une région de pixels,
- la figure 10 représente les étapes d'un algorithme de détection de contour utilisé lors de la troisième étape du procédé selon l'invention,
- la figure 11 représente les étapes d'un algorithme d'approximation polygonale par subdivision d'un contour de régions de pixels, utilisé lors de la quatrième étape du procédé selon l'invention,
- la figure 12 représente un contour d'une région de pixels subdivisé en deux contours,
- la figure 13 représente un contour d'une région de pixels subdivisé en quatre contours,
- la figure 14 représente l'utilisation d'une image de pixels agrandie pour dilater des contours extérieurs de régions et contracter des contours intérieurs de régions.
Selon un premier mode de réalisation du procédé selon l'invention, les éléments des maillages d'une image à trois dimensions sont convertis en un ensemble de zones à deux dimensions, représentables en minimisant le nombre de vecteurs par contour. Les éléments d'un maillage de l'image à trois dimensions sont décrits en termes de sommets, d'arêtes entre ces sommets, et de triangles ou polygones formés par ces sommets et arêtes. Ces éléments décrivent un ou plusieurs objets à trois dimensions dans l'image qui ont une propriété commune, par exemple une même texture. Un maillage peut donc être représenté sous forme de graphe, dans lequel chaque sommet du graphe est un sommet du maillage, et dans lequel les arêtes du graphe sont les arêtes qui relient les sommets du maillage. Pour simplifier la description du procédé selon l'invention, on suppose dans la suite que les maillages de l'image à trois dimensions ne comprennent pas de polygones à plus de trois côtés. II est à noter qu'un maillage d'image à trois dimensions contient aussi de nombreuses autres données sur ses éléments, qui ne seront pas détaillées ici, telles que des données sur leur texture, leur couleur ou leur éclairage.
Dans une première étape E1 du procédé selon l'invention, représentée à la figure 1 , les maillages de l'image à trois dimensions sont découpés en composantes. Les composantes d'un maillage à trois dimensions sont les éléments du maillage qui ne sont pas reliés de manière topologique entre eux.
Par exemple dans un maillage qui associe deux yeux d'un personnage parce qu'ils ont la même texture, chaque œil forme une composante du maillage. Afin d'effectuer ce découpage en composantes, pour chaque maillage de l'image à trois dimensions, le graphe formé par ce maillage est parcouru sommet par sommet, de manière à déterminer les éléments du graphe qui sont indépendants les uns des autres, d'un point de vue topologique.
Les étapes suivantes E2, E3 et E4 du procédé selon l'invention seront détaillées plus loin. Elles correspondent respectivement à: - La création d'une image symbolique, correspondant à une visualisation de l'image à trois dimensions suivant le point de vue d'un observateur, - La détection des différentes régions coloriées de cette image symbolique, - Et à une approximation des contours de ces régions par des contours vectoriels.
Toutes ces étapes du procédé selon l'invention peuvent être implémentées dans un moteur de rendu graphique, tel que OpenGL ou DirectX. En particulier, la réalisation de l'image symbolique peut utiliser un moteur de rendu graphique initialisé de telle sorte que les options d'éclairage et d'anti- crénelage ne soient pas utilisées.
Dans la suite, on suppose que l'invention est implémentée de manière logicielle, à travers différents algorithmes utilisés dans les étapes E1 à E4. Les données des maillages de l'image à trois dimensions initiale sont donc conservées en mémoire et traitées au fur et à mesure par ces algorithmes.
Certaines données intermédiaires sont conservées dans des mémoires spécifiques, comme détaillé dans la suite. Néanmoins les autres données intermédiaires, même non explicitement indiquées, pourront être conservées en mémoire jusqu'à l'obtention de l'image à deux dimensions finale issue du procédé selon l'invention.
L'étape E1 est explicitée à travers les étapes de l'organigramme de la figure 2, qui sont les suivantes: La première étape ai est l'initialisation à zéro d'un compteur appelé
"ComposanteNum", qui permet de numéroter toutes les composantes de tous les maillages de l'image à trois dimensions de manière unique. Il est à noter que bien que la numérotation d'une composante de l'image n'inclut pas de référence au maillage auquel appartient cette composante, cette appartenance est conservée dans les données associées à chaque composante obtenue au cours de l'étape E1. Ceci permet à la fin du procédé de recolorier chaque zone de l'image à deux dimensions issue du procédé selon une couleur approchée de celle de la composante à trois dimensions à l'origine de cette zone.
L'étape suivante a2 est la sélection d'un maillage M non déjà parcouru dans l'image à trois dimensions. Par exemple, si la liste des maillages de l'image est recopiée dans une variable dans laquelle les maillages parcourus sont supprimés au fur et à mesure, il suffit de sélectionner le premier maillage de cette variable.
L'étape suivante a3 est la vérification du fait que le maillage M sélectionné à l'étape a2 existe bien, c'est-à-dire que tous les maillages de l'image n'ont pas déjà été parcourus. Si tous les maillages de l'image ont été parcourus, l'étape E1 est terminée, toutes les composantes de l'image étant identifiées par un numéro de composante. Sinon l'étape suivante est l'étape a4. L'étape a4 est la recherche du premier sommet S dans le maillage M sélectionné qui ne soit pas déjà marqué comme appartenant à une composante.
L'étape suivante a5 est la vérification de l'existence de ce sommet S recherché à l'étape a4. Si aucun sommet non marqué n'a été trouvé, c'est que le maillage M sélectionné est entièrement parcouru, et l'étape suivante est l'étape a6. Dans le cas contraire, c'est-à-dire si le sommet S existe, l'étape suivante est l'étape al.
L'étape a6 est le marquage du maillage M comme maillage parcouru, par exemple en le supprimant de la liste des maillages, et le passage au maillage suivant non déjà parcouru en retournant à l'étape a2.
L'étape a7 est le parcours récursif de tous les sommets reliés au sommet S, en les marquant comme appartenant à la composante de numéro "ComposanteNum".
L'étape suivante a8, est l'incrémentation d'une unité du compteur "ComposanteNum" pour trouver une éventuelle autre composante non encore identifiée dans le maillage M sélectionné. Pour cela l'étape aδ est suivie de l'étape a4.
Une fois les composantes de l'image à trois dimensions identifiées, on crée une image symbolique, intermédiaire entre l'image à trois dimensions et l'image vectorielle à deux dimensions issue du procédé, selon une deuxième étape E2 du procédé selon l'invention, représentée à la figure 1. Deux variantes de réalisation de l'étape E2 sont présentées. Dans une première variante, les composantes de l'image à trois dimensions, représentées à la figure 3 dans un repère orthonormé (O,x,y,z), sont projetées sur une surface de projection Sf de repère local (O',X,Y), depuis le point de vue Po d'un observateur. On considère un angle de vue correspondant qui forme une pyramide de vue régulière Pv, englobant toutes les composantes de l'image à trois dimensions. Dans l'exemple de la figure 3, deux composantes, Compi , qui est une surface rectangulaire, et Comp2, qui est une surface triangulaire, forment l'image à trois dimensions. Ces composantes ont une intersection non vide dans l'espace de la pyramide de vue Pv.
Au cours de cette projection, on conserve les coordonnées de profondeur de chacune des composantes dans la pyramide de vue Pv par rapport à la surface Sf. Ainsi la projection du sommet (xi,yi,zi) de la composante Comp2 est conservée en mémoire sous la forme (Xi1Yi1Z1), où seules les coordonnées (Xi1Yi) correspondent à cette projection proprement dite, la coordonnée Z1 étant la profondeur initiale de ce sommet dans la pyramide de vue Pv.
Les couleurs de chaque pixel de la surface Sf sont initialisées sans marquage de couleur et enregistrées dans un espace mémoire appelé "frame- buffer". Les profondeurs de chaque pixel de la surface Sf sont initialisées avec une profondeur très supérieure à celle des composantes de l'image à trois dimensions, et sont enregistrées dans un espace mémoire appelé "Z-buffer".
A chaque composante projetée est attribuée une couleur, différente pour chaque composante, et on parcourt ensuite cette composante pixel par pixel sur la surface Sf, suivant l'algorithme classique dit du "Z-buffer": au cours de ce parcours, la profondeur et la couleur d'un pixel de la composante sont mémorisées respectivement dans la mémoire "Z-buffer" et la mémoire "frame- buffer" si la profondeur de ce pixel est moins importante que la profondeur du pixel correspondant enregistré dans la mémoire "Z-buffer". La profondeur du pixel d'une composante est calculée à partir des coordonnées de profondeur conservées pour chaque composante lors de sa projection sur la surface Sf. Ainsi ne sont conservées dans les mémoires "Z-buffer" et "frame-buffer" que les données correspondant aux pixels les plus proches de l'observateur.
On obtient une image symbolique, constituée de pixels, dans laquelle à chaque composante projetée est associée une couleur, et dans laquelle les parties de l'image à trois dimensions non visibles depuis l'observateur ne sont pas représentées. L'image symbolique IS1 obtenue à la fin de l'étape E2 dans l'exemple donné à la figure 3 est représentée à la figure 4.
Dans une deuxième variante de réalisation de l'étape E2, on commence par projeter seulement les triangles vus de devant des composantes de l'image à trois dimensions sur la surface Sf, depuis le point de vue Po. On applique ensuite à ces triangles l'algorithme du "Z-buffer", comme dans la première variante précédemment décrite, les triangles de composantes différentes étant coloriés avec des couleurs différentes. Les triangles vus de derrière des composantes de l'image à trois dimensions sont alors projetés à leur tour sur la surface Sf. On applique ensuite à ces nouveaux triangles projetés l'algorithme du "Z-buffer", initialisé avec les données des mémoires "Z-buffer" et "frame- buffer" issues de la première application de l'algorithme du "Z-buffer" sur les triangles vus de devant. Lors de cette deuxième application de l'algorithme du "Z-buffer", les triangles de composantes différentes sont coloriés avec des couleurs différentes, non précédemment utilisées lors de la première application de l'algorithme du "Z-buffer".
Les triangles vus de devant d'une composante se distinguent des triangles vus de derrière de cette même composante par l'orientation des vecteurs normaux associés à chacune des surfaces triangulaires de la composante. Ces vecteurs normaux sont habituellement utilisés par les moteurs graphiques pour calculer l'éclairage sur les différentes surfaces d'un objet à trois dimensions depuis une source lumineuse. En effet, l'orientation des vecteurs normaux de chacun des triangles d'une composante par rapport à la surface de projection Sf permet de déterminer si un triangle donné est vu de devant ou vu de derrière depuis le point de vue Po d'un observateur, représenté à la figure 5. Ainsi si le vecteur normal à un triangle TrA est dirigé vers l'espace de l'observateur, ce triangle est vu de devant. Si le vecteur normal à un triangle TrB est dirigé de l'autre côté, ce triangle est vu de derrière.
Dans la suite, pour simplifier, les expressions "vu de devant" ou "vu de derrière" pour un triangle d'une composante signifieront respectivement "vu de devant depuis le point de vue Po" ou "vu de derrière depuis le point de vue Po".
Cette deuxième variante de réalisation de l'étape E2 permet d'obtenir une image symbolique dans laquelle les éléments d'une composante vus de devant ont une couleur différente des éléments de cette même composante vus de derrière. Cela permet dans certain cas de mieux visualiser la perspective d'objets à trois dimensions, comme par exemple un ruban dont on voit une partie de l'envers. La figure 6 représente l'image symbolique IS2 obtenue avec un ruban lorsque cette seconde variante de l'étape E2 est utilisée, et la figure
7 représente l'image symbolique IS3 obtenue avec ce même ruban lorsqu'on se contente d'utiliser la première variante de l'étape E2.
L'organigramme de la figure 8 explicite les étapes de la deuxième variante de réalisation de l'étape E2, détaillées ci-après.
La première étape b1 est l'initialisation de variables utiles à la réalisation de cette variante:
- un numéro appelé "CompNum" de la composante à traiter dans l'image à trois dimensions, est initialisé à zéro, - la couleur de coloriage appelée "CouleurNum", utilisée pendant l'application de l'algorithme du "Z-buffer", est initialisée à un niveau de gris très bas,
- la mémoire "Z-buffer" qui conserve les profondeurs de tous les pixels de la surface de projection Sf, est initialisée à une profondeur maximale pour tous les pixels, par exemple une profondeur infinie,
- la mémoire "frame-buffer", qui conserve les couleurs de tous les pixels de la surface Sf, est également initialisée avec une couleur dite de fond, qui n'est pas utilisée comme couleur de coloriage "CouleurNum", pour tous les pixels.
L'étape suivante b2 est la sélection de la composante c de numéro "CompNum" dans une liste des composantes de l'image à trois dimensions.
L'étape suivante b3 est la vérification de l'existence de la composante c obtenue à l'étape b2. Si la composante c n'existe pas, c'est que toutes les composantes de l'image à trois dimensions ont été traitées. Dans ce cas l'étape suivante est l'étape b9, sinon l'étape suivante est l'étape b4.
L'étape b4 est la détermination des triangles vus de devant de la composante c. Cette détermination utilise les vecteurs normaux associés à ces triangles, comme expliqué précédemment.
L'étape suivante b5 est la projection des triangles obtenus à l'étape b4 sur la surface Sf de projection, par rapport au point de vue Po. Les profondeurs des sommets de ces triangles sont conservées dans les coordonnées des triangles projetés. L'étape suivante b6 est l'application de l'algorithme du "Z-buffer" aux triangles projetés à l'étape b5, chaque triangle étant colorié avec le niveau de gris "CouleurNum".
L'étape suivante b7 est l'incrémentation d'une unité du numéro "CompNum" de la composante à traiter, pour considérer une composante suivante. L'étape suivante bδ est de même l'incrémentation d'une unité du niveau de gris "CouleurNum". L'étape suivante est de nouveau l'étape b2, pour traiter une autre composante, tous les triangles vus de devant de toutes les composantes de l'image à trois dimensions devant être projetés puis soumis à l'algorithme du Z-buffer avant de passer à l'étape b9.
L'étape b9 est la réinitialisation à zéro du numéro "CompNum" de la composante à traiter. Il est à noter que la couleur "CouleurNum" à appliquer lors de l'algorithme du "Z-buffer" n'est pas réinitialisée, puisque les éléments des composantes vus de derrière ne seront pas coloriés de la même couleur que ceux vus de devant. A cette étape, toutes les composantes de l'image à trois dimensions sont déjà passées par les étapes b4 à b6. La mémoire "Z- buffer" ainsi que la mémoire "frame-buffer" contiennent les données de profondeurs et de couleurs des pixels des éléments vus de devant de l'image à trois dimensions, projetés sur la surface Sf. L'étape suivante b10 est la sélection de la composante c de numéro
"CompNum" dans la liste des composantes de l'image à trois dimensions.
L'étape suivante b11 est la vérification de l'existence de la composante c. Si la composante c n'existe pas, c'est que toutes les composantes de l'image à trois dimensions ont été traitées. Dans ce cas l'étape E2 suivant la deuxième variante de réalisation est terminée, et la mémoire "frame-buffer" contient l'image symbolique faite de pixels coloriés avec les différents niveaux de gris "CouleurNum" utilisés. Sinon l'étape suivante est l'étape b12.
L'étape b12 est la détermination des triangles vus de derrière de la composante c. Cette détermination utilise les vecteurs normaux associés à ces triangles, comme expliqué précédemment.
L'étape suivante b13 est la projection des triangles obtenus à l'étape b12 sur la surface Sf de projection, par rapport au point de vue Po. Les profondeurs des sommets de ces triangles sont conservées dans les coordonnées des triangles projetés. L'étape suivante b14 est l'application de l'algorithme du "Z-buffer" aux triangles projetés à l'étape b13, chaque triangle étant colorié avec le niveau de gris "CouleurNum".
L'étape suivante b15 est l'incrémentation d'une unité du numéro "CompNum" de la composante à traiter, pour considérer une composante suivante.
L'étape suivante b16 est de même l'incrémentation d'une unité du niveau de gris "CouleurNum". L'étape suivante est de nouveau l'étape b10, pour traiter une autre composante, tous les triangles vus de derrière de toutes les composantes de l'image à trois dimensions devant être projetés puis soumis à l'algorithme du Z-buffer pour obtenir l'image symbolique.
L'image symbolique obtenue à l'issue de l'étape E2 possède les propriétés suivantes: - Elle contient autant ou plus de zones de couleurs différentes que de composantes présentes dans l'image à trois dimensions, - Elle contient au plus le même nombre de triangles que de triangles dans l'image à trois dimensions.
Cependant la finalité de l'image symbolique obtenue n'est pas d'être visualisée, étant donné, entre autres, qu'elle est constituée de pixels, ce qui est très coûteux en ressources mémoire, et que ses couleurs ne sont pas celles de l'image à trois dimensions d'origine. Un moyen de coder cette image symbolique de manière moins coûteuse en ressources mémoire est d'avoir une description des contours de chaque zone de différente couleur dans l'image symbolique. Ces zones sont dans la suite appelées régions. Cette détection des contours des régions de l'image symbolique est l'objet de l'étape E3, représentée à la figure 1.
Une région est définie par un ensemble de pixels d'une même couleur de composante, contenu à l'intérieur d'un contour extérieur, et éventuellement à l'extérieur d'un ou plusieurs contours intérieurs si des trous ou d'autres régions sont présents à l'intérieur de cette première région. Un trou est défini par un contour intérieur d'une région, et peut contenir à la fois des pixels non coloriés, c'est-à-dire n'appartenant à aucune composante, et des pixels coloriés d'autres régions. Suite à l'étape E2, les pixels non coloriés correspondent en effet à la couleur de fond de l'image symbolique. Il est à noter que plusieurs régions de l'image symbolique peuvent avoir la même couleur, par exemple si depuis le point de vue Po une composante en coupe une autre en deux.
Un contour est défini par une suite de sommets de pixels, et par un sens de parcours de cette suite de pixels. Ainsi un contour extérieur est une suite de sommets de pixels qui parcourt dans le sens inverse du sens trigonométrique le contour extérieur de la région à laquelle il est associé. Un exemple de contour extérieur est donné à la figure 9. Le contour extérieur de la région formée des pixels p22, p23, p33 et p34, le pixel pij désignant le pixel situé à la ligne i et la colonne j d'une image symbolique, est la suite de sommets {s22, s23, s24, s34, s35, s45, s44, s43, s33, s32}, où sij désigne le sommet supérieur gauche du pixel pij. Un contour intérieur est une suite de sommets de pixels qui parcourt dans le sens trigonométrique le bord d'un trou dans la région associée à ce contour. Dans la suite, un contour est décrit comme une liste de sommets supérieurs gauches de pixels {si,...,sn}, qui doit être parcouru suivant l'ordre de cette liste, et où n est un entier supérieur à un. De même une arête orientée (sij, ski) de ce contour est l'arête issue du sommet sij et d'extrémité ski, où sij et ski sont les sommets supérieurs gauches respectivement des pixels pij et pkl. Un exemple d'algorithme de suivi du parcours extérieur d'une région utilise comme point de départ une arête orientée (sij, ski) appartenant au contour extérieur de cette région. A partir de cette arête, on cherche le sommet smn tel que l'arête orientée (ski, smn) appartienne à un bord de cette région et soit dirigée le plus possible vers la droite par rapport à (sij, ski), sans revenir en arrière. On procède de même à partir de l'arête orientée (ski, smn), et récursivement on construit une liste de sommets jusqu'à revenir au sommet de départ sij. La liste de sommets ainsi obtenue à la fin de l'algorithme décrit le contour extérieur de la région.
De façon similaire, un exemple d'algorithme de suivi d'un parcours intérieur d'une région utilise comme point de départ une arête orientée (sij, ski) appartenant à ce contour intérieur. A partir de cette arête, on cherche le sommet smn tel que l'arête orientée (ski, smn) appartienne à un bord de la région et soit dirigée le plus possible vers la gauche par rapport à (sij, ski), sans revenir en arrière. On procède de même à partir de l'arête orientée (ski, smn), et récursivement on construit une liste de sommets jusqu'à revenir au sommet de départ sij. La liste de sommets ainsi obtenue à la fin de l'algorithme décrit un contour intérieur de la région.
Pour extraire les contours des régions de l'image symbolique obtenue à l'étape E2, cette image est parcourue ligne par ligne de gauche à droite. Une image tampon est utilisée pour stocker les contours et régions détectés au fur et à mesure du parcours de l'image symbolique. Elle permet notamment de déterminer si un pixel de l'image symbolique a déjà été parcouru, s'il est sur une région déjà détectée, ou si une de ses arêtes appartient à un contour déjà parcouru. II est à noter que suite à l'étape E2, les couleurs des pixels de l'image symbolique permettent de relier chaque région de l'image tampon à une composante de l'image à trois dimensions.
Les étapes de l'algorithme de parcours de l'image symbolique sont représentées à la figure 10:
La première étape d est l'initialisation de l'image tampon, afin qu'elle ne contienne ni contours ni régions à cette étape de l'algorithme. Le pixel courant p de parcours de l'image, défini comme situé à la ligne courante "ligne" et à la colonne courante "col", est également initialisé au premier pixel supérieur gauche de l'image. La ligne courante est donc initialisée à la première ligne et la colonne courante à la première colonne de l'image. Le pixel suivant est défini comme situé sur la même ligne que le pixel courant mais sur la colonne immédiatement à droite de la colonne courante. Il est donc initialisé à la première ligne et à la deuxième colonne de l'image. L'étape suivante c2 est un test sur le pixel courant. Si le pixel courant est d'une couleur différente de celle du pixel suivant, et si l'arête droite du pixel courant n'appartient pas à un contour de l'image tampon, cela signifie qu'un nouveau contour a été rencontré. Dans ce cas l'étape suivante est l'étape c3, sinon l'étape suivante est l'étape c7. L'étape c3 est à nouveau un test sur le pixel courant. Si le pixel courant appartient à une région de l'image tampon, c'est que le contour détecté est un contour intérieur de cette région. Dans ce cas l'étape suivante est l'étape c11.
Dans le cas contraire, le contour détecté est un contour extérieur d'une nouvelle région, et l'étape suivante est l'étape c4. L'étape c4 est la création de nouvelles variables R de région et C de contour extérieur, correspondant à la nouvelle région et au nouveau contour détectés aux étapes c2 et c3.
L'étape suivante c5 est le suivi du contour extérieur C, en utilisant l'algorithme décrit précédemment avec comme arête initiale l'arête supérieure du pixel suivant, orientée vers la droite.
L'étape suivante c6 est la mise à jour de l'image tampon avec le contour
C ainsi parcouru, et avec la région R délimitée par ce contour extérieur C.
L'étape suivante c7 est un test sur le pixel suivant. Si le pixel suivant est en fin de ligne, on passe à l'étape cδ, sinon on passe à l'étape c10. L'étape cδ est à nouveau un test sur le pixel suivant. Si celui-ci est sur la dernière ligne, alors l'image a été entièrement parcourue, l'algorithme de parcours est donc terminé. Sinon l'étape suivante est l'étape c9.
L'étape c9 est la mise à jour du pixel courant p à la première colonne de la ligne qui suit la ligne courante. La ligne courante, la colonne courante, et le pixel suivant sont également mis à jour en fonction de ce nouveau pixel courant. L'étape suivante est alors à nouveau l'étape c2, pour continuer le parcours de l'image.
L'étape c10 est également la mise à jour du pixel courant p au pixel suivant, mais dans le cas où le pixel courant p n'était pas en fin de ligne. La ligne courante, la colonne courante et le pixel suivant sont mis à jour en fonction du nouveau pixel courant. L'étape suivante est à nouveau l'étape c2, pour continuer le parcours de l'image.
L'étape d 1 est la création d'une nouvelle variable de contour intérieur, correspondant au nouveau contour détecté à l'étape c2. L'étape suivante c12 est le suivi du contour intérieur créé à l'étape d 1 , en utilisant l'algorithme décrit précédemment avec comme arête initiale l'arête gauche du pixel suivant, orientée vers le bas.
L'étape suivante c13 est la mise à jour de l'image tampon avec le contour intérieur créé à l'étape c11 et complété à l'étape c12, associé à la région à laquelle appartient le pixel courant.
L'étape suivante c14 est un test sur la couleur du pixel courant. Si le pixel courant a la même couleur que le fond de l'image, on poursuit le processus de parcours de l'image en passant à l'étape c7. Sinon cela signifie qu'une nouvelle région vient d'être détectée à l'intérieur du trou précédemment détecté à l'étape c3. L'étape suivante est alors l'étape c4, afin de déterminer la nouvelle région détectée et son contour extérieur associé
L'algorithme de parcours de l'image symbolique terminé, l'image tampon contient l'ensemble des régions et contours de l'image symbolique. A la fin de cette étape E3 du procédé, les contours extérieurs obtenus sont dilatés et les contours intérieurs sont contractés afin de faire disparaître d'éventuels pixels parasites ayant la couleur de fond entre les régions de l'image symbolique. En effet les calculs nécessaires à la projection des composantes lors de l'étape E2 induisent des erreurs d'approximation numérique susceptibles de provoquer l'apparition de ces pixels parasites. Un moyen d'effectuer cette dilatation des contours extérieurs et contraction des contours intérieurs est d'utiliser une image symbolique ISA représentée à la figure 14, agrandie d'un pixel de largeur et d'un pixel de hauteur par rapport à l'image symbolique originale ISO. L'image symbolique originale est superposée à cette image agrandie, de manière centrée sur l'image symbolique agrandie. Les contours des régions contenus dans l'image tampon sont ensuite tracés sur l'image symbolique originale. Dans l'exemple de la figure 14, l'image tampon contient un contour intérieur CIO et un contour extérieur CEO. Les contours extérieurs sont ensuite tracés sur l'image symbolique agrandie en arrondissant les contours extérieurs de l'image originale aux arêtes externes les plus proches dans l'image agrandie. Les contours intérieurs sont de même tracés sur l'image symbolique agrandie mais en arrondissant les contours intérieurs de l'image originale aux arêtes internes les plus proches dans l'image agrandie. Ainsi le contour extérieur CEO est arrondi au contour extérieur CEA sur l'image symbolique agrandie, tandis que le contour intérieur CIO disparaît sur l'image symbolique agrandie, supprimant ainsi un pixel parasite. Les contours de l'image symbolique agrandie ainsi obtenus sont ensuite réduits au format de l'image symbolique originale pour obtenir de nouveaux contours intérieurs et extérieurs respectivement contractés et dilatés.
Afin de limiter encore les ressources mémoires nécessaires au stockage de l'image, et d'obtenir une image à deux dimensions plus facilement utilisable que l'image tampon, la dernière étape E4 du procédé, représentée à la figure 1 , permet de transformer l'image tampon en une suite de contours vectoriels de régions. Les couleurs des régions associées à ces contours sont conservées en mémoire afin de produire, par correspondance avec les couleurs initiales des maillages de l'image à trois dimensions, une image à deux dimensions qui ressemble à la visualisation de l'image à trois dimensions initiale, depuis le point de vue Po.
L'étape E4 utilise l'algorithme représenté à la figure 11 afin de transformer un contour de l'image tampon, formé de sommets de pixels successifs, en une suite limitée de vecteurs reproduisant le contour suivant la précision souhaitée. Les étapes de cet algorithme sont les suivantes, les quatre premières étapes servant à l'initialisation de l'algorithme:
La première étape d1 consiste à trouver les sommets Si et S2 les plus éloignés d'un contour C0 de l'image tampon, représenté à la figure 12.
L'étape suivante d2 est la construction de deux contours Ci et C2 associés respectivement aux vecteurs \Λ et V2, tels que \Λ est le vecteurs^,,
et V2 le vecteur S2S1. Si le contour C0 est défini par la suite de sommets
Figure imgf000024_0001
- n est un entier supérieur à 1
Si = si et S2 = sj, où i et j sont des entiers tels que 1 ≤i ≤j≤n
Alors le contour Ci est défini par la suite de sommets {si Sμi,Si, S2,
Sj+1, ...,sn}, et C2 par la suite de sommets {Si, si+i,... Sj_i, ...S2J.
L'étape suivante d3 est la création d'un contour vectoriel Cv, initialement vide et qui contiendra à la fin de l'algorithme la suite de vecteurs décrivant C0.
L'étape suivante d4 est la création d'une liste de contours à subdiviser, chaque contour de la liste étant associé à un vecteur. Cette liste est initialisée aux contours Ci et C2, associés respectivement aux vecteurs Vi et V2.
L'étape suivante d5 est la sélection dans la liste de contours à subdiviser, d'un contour courant C1 associé à un vecteur courant Vi . Ce contour courant est par exemple le premier contour de la liste de contours à subdiviser. L'étape suivante d6 est un test sur l'existence du contour courant Cj. Si ce contour n'existe pas, c'est que la liste de contours à subdiviser est vide, ce qui signifie que l'algorithme est terminé. Sinon l'étape suivante est l'étape 61.
L'étape d7 est la détermination dans le contour courant C1, du sommet SMaχ appartenant à ce contour courant qui est le plus éloigné du vecteur courant Vi .
L'étape d8 est un test sur la distance Dmax entre le sommet SMaχ et le vecteur courant Vi . Si cette distance est supérieure à un seuil Dseuii, qui fixe la précision souhaitée d'approximation du contour C0 par le contour vectoriel Cv, alors on poursuit la détermination d'autres vecteurs plus proches du contour courant C1 que le vecteur courant Vi en passant à l'étape d11. Dans le cas contraire la précision obtenue est acceptable et l'étape suivante est l'étape d9.
L'étape d9 est l'ajout au contour Cv de l'inverse -Vi du vecteur courant
Vi associé au contour courant Q. Le fait d'inverser le vecteur courant Vi permet de conserver le sens de parcours initial des sommets du contour C0, dans le contour vectoriel final Cv.
L'étape suivante d10 est la suppression du contour courant C1 dans la liste de contours à subdiviser. En effet la précision du vecteur courant Vi étant suffisante pour approcher le contour courant C1, celui-ci n'a plus besoin d'être subdivisé. L'étape suivante est l'étape d5, afin de poursuivre l'algorithme avec le traitement des contours restants à subdiviser.
L'étape d11 est la subdivision du contour courant en deux contours Ck et
Ci associés respectivement aux vecteurs Vk et V/ tels que si le contour courant C1 est défini par la suite de sommets {si, ..., sh, ..., sm}, où: h et m sont des entiers tels que 1 ≤h≤m,
Le vecteur courant est le vecteur S1nS1 , Et SMaχ est le sommet sh, alors le contour Ck est le contour défini par la suite de sommets {sh, sh-i,..., S2, Si} et le contour d par la suite de sommets {sm, sm-i,..., sh+i, sh}, le vecteur Vk étant le vecteurs^ et le vecteur V/ étant le vecteur shsm . L'étape suivante d12 est l'ajout des contours Ck et d associés respectivement aux vecteurs Vk et V/ , dans la liste des contours à subdiviser, par exemple en début de liste.
L'étape suivante d13 est la suppression du contour courant C1 dans la liste des contours à subdiviser, puisque ce contour vient d'être remplacé par deux autres contours. L'étape suivante est l'étape d5, les contours à subdiviser étant traités jusqu'à obtention de vecteurs approchant de manière satisfaisante les contours auxquels ils sont associés.
Dans l'exemple de la figure 13, à la fin de l'algorithme le contour C0 a été subdivisé en quatre contours C3, C4, C5 et C6, associés respectivement aux vecteurs V3, V4, V5 et V6. Le contour vectoriel final Cv correspondant au contour C0 est donc le contour { -V6, -V5,- V4,- V3}.
Une fois tous les contours de l'image tampon transformés en contours vectoriels suivant l'étape E4 d'approximation polygonale, on obtient une représentation vectorielle à deux dimensions de l'image à trois dimensions initiale, faite de contours vectoriels de régions, pour chacun desquels le sens de parcours permet de déterminer s'il s'agit d'un contour extérieur ou d'un contour intérieur de région. Il suffit ensuite de réassocier chaque région de cette représentation à la couleur d'origine du maillage correspondant dans l'image à trois dimensions initiale, pour obtenir une visualisation de l'image à trois dimensions initiale depuis un point de vue d'un observateur sous forme d'une image vectorielle à deux dimensions. Cette image vectorielle est facilement réutilisable par des logiciels de présentation d'images utilisant le format SVG par exemple, d'après l'anglais Scalable Vector Graphics, et est très peu coûteuse en ressources mémoire.
Néanmoins, l'application de l'invention à une animation en images à trois dimensions peut présenter un inconfort visuel dus à des phénomènes de discontinuité, les différentes images vectorielles à deux dimensions obtenues étant calculées indépendamment les unes des autres. La cohérence du mouvement temporel des différents contours vectoriels associés à ces images est en effet affectée par les différentes étapes du procédé de conversion, notamment l'étape d'approximation polygonale, qui ne tient pas compte de la notion de mouvement de l'image traitée dans une animation.
Pour remédier à ce problème de continuité de mouvement des contours vectoriels, une amélioration est apportée à l'invention lorsqu'elle est utilisée dans le cadre d'une animation. En effet dans ce cas, le calcul d'une image vectorielle donnée de l'animation tient compte d'une image vectorielle précédente. Par exemple à l'étape E4, pour adoucir les mouvements des contours vectoriels lors de l'animation, au lieu d'utiliser l'algorithme d'approximation polygonale, on utilise les contours vectoriels de l'image précédente dans l'animation. Chaque contour vectoriel de l'image précédente est appliqué au contour intérieur ou extérieur correspondant dans l'image tampon courante de l'animation, par un procédé d'élasticité: à partir du centre du contour intérieur ou extérieur, on déforme les sommets du contour vectoriel qui lui est superposé en les projetant sur le contour intérieur ou extérieur de l'image courante. Pour chaque région de l'image courante, on obtient ainsi un ou plusieurs contours vectoriels correspondants.
Un contour vectoriel et son contour de région associé forment une suite de contours, assimilable à un résultat intermédiaire de l'algorithme d'approximation polygonale précédemment décrit, c'est-à-dire à une liste de contours à subdiviser. On peut donc utiliser cet algorithme pour corriger le contour vectoriel, l'algorithme étant initialisé avec une liste de contours à subdiviser contenant cette suite de contours. Ainsi si le contour vectoriel est assez proche du contour qui lui correspond, il est utilisé tel quel dans l'animation, sinon il est subdivisé en utilisant l'algorithme d'approximation polygonale. Cette utilisation des contours vectoriels précédents pour obtenir des contours vectoriels courants permet d'adoucir les mouvements, car les sommets des contours vectoriels se déplacent moins, ce qui améliore la visualisation de l'animation.
Selon un deuxième mode de réalisation du procédé selon l'invention, le premier mode de réalisation du procédé selon l'invention décrit précédemment est enrichi par l'ajout, dans l'image à deux dimensions issue du procédé, de traits qui marquent les pliures importantes des composantes de l'image à trois dimensions initiale. Ce deuxième mode de réalisation est intéressant lorsque la détection de ces traits de pliure par le moteur de rendu graphique qui utilise ce procédé n'utilise pas de ressources de calcul excessives.
Dans ce deuxième mode de réalisation de l'invention, les traits de pliure sont traités de manière indépendante des autres composantes de l'image à trois dimensions initiale, qui est traitée suivant les étapes E1 à E4 décrites précédemment.
Les traits de pliure importants de l'image à trois dimensions sont tout d'abord identifiés. Un moyen de détecter ces traits de pliure est par exemple de parcourir tous les couples de triangles adjacents à l'intérieur de chacune des composantes identifiées à l'étape E1. Lors de ce parcours, si deux triangles adjacents forment un angle aigu inférieur à un certain seuil au niveau de leur arête commune, alors cette arête est potentiellement un trait de pliure important à prendre en compte. Deux types d'arêtes sont à distinguer:
Les arêtes de silhouette sont des arêtes qui se partagent deux triangles dont l'un est une face avant et l'autre une face arrière, c'est-à-dire que les normales de ces triangles pointent dans des sens différents depuis le point de vue Po. Les arêtes de pliure sont des arêtes qui se partagent deux triangles formant un angle très prononcé, mais qui sont soit tous deux des faces avant soit tous deux des faces arrières.
Seuls les secondes arêtes sont à prendre en compte comme traits de pliure d'une composante ainsi parcourue. En effet les traits de silhouette sont reproduits comme traits de contour après la projection sur la surface Sf lors de l'étape E2 et ne nécessitent donc pas une projection à part. Une fois les traits de pliure détectés, la mémoire "frame-buffer" et la mémoire "Z-buffer" obtenues à la fin de l'étape E2, qui contiennent l'image symbolique, sont recopiées afin d'être utilisées pour le traitement des traits de pliure. Ceux-ci sont projetés sur la surface de projection Sf, depuis le point de vue Po, les profondeurs des sommets qui les composent étant conservées en mémoire, puis traités suivant l'algorithme du "Z-buffer" à partir de la copie des mémoires "Z-buffer" et "frame-buffer" obtenues à la fin de l'étape E2. Les traits de pliure sont coloriés pendant ce traitement avec une couleur distincte de celles utilisées lors de l'étape E2, par exemple en noir. Ceci permet d'obtenir uniquement les parties visibles depuis le point de vue Po, des traits de pliure dans l'image à trois dimensions. A la fin de ce traitement on obtient une image symbolique enrichie de traits de pliure, et distincte de celle utilisée à l'étape E3.
Cette image symbolique enrichie de traits de pliure est ensuite parcourue pixel par pixel afin de coder ces traits sous formes d'ensembles distincts de pixels. Ces suites de pixels sont considérées comme des contours non orientés.
Ces contours sont ensuite transformés en traits de pliure vectoriels, de manière indépendante de l'étape E4. A cette fin l'algorithme utilisé à l'étape E4 peut être réutilisé, mais en commençant directement à l'étape d4 représentée à la figure 11. Pour chaque contour à traiter, la liste de contours à subdiviser à l'étape d4 d'initialisation de l'algorithme contient uniquement ce contour, celui- ci étant associé à un vecteur joignant les pixels qui sont situés aux extrémités du trait de pliure par leurs sommets. Cependant dans le cas où le trait de pliure forme un contour fermé, l'algorithme de l'étape E4 est réutilisé sans modifications.
Les traits de pliure vectoriels sont ensuite ajoutés à l'image vectorielle obtenue à la fin de l'étape E4. A la fin de ce deuxième mode de réalisation du procédé selon l'invention, on obtient, de la même manière que dans le premier mode de réalisation du procédé selon l'invention, une visualisation de l'image à trois dimensions initiale depuis le point de vue d'un observateur sous forme d'une image vectorielle à deux dimensions, mais enrichie de traits de pliure qui permettent de mieux rendre la perspective des objets représentés.

Claims

REVENDICATIONS
1. Procédé de conversion d'une image à trois dimensions en image à deux dimensions, caractérisé en ce qu'il comporte les étapes de:
- Détermination (E1 ) de composantes indépendantes du point de vue topologique, de ladite image à trois dimensions,
- Projection (E2) sur une surface (Sf) depuis un point de vue (Po), d'au moins une partie de chacune des composantes déterminées, les profondeurs, dans une pyramide de vue formée par ledit point de vue, des sommets des parties des composantes déterminées étant conservées dans les données des parties de composantes projetées,
- Première application (E2) de l'algorithme dit du "Z-buffer" aux parties de composantes ainsi projetées, et coloriage uniforme desdites parties de composantes projetées, des couleurs distinctives, sans corrélation avec leurs couleurs d'origine, étant attribuées à respectivement chacune desdites parties de composantes, afin d'obtenir une première image de pixels.
2. Procédé de conversion d'une image à trois dimensions en image à deux dimensions selon la revendication 1 , caractérisé en ce qu'il comporte l'étape supplémentaire (E3) de détection, dans la première image de pixels obtenue à l'issue de l'étape de première application (E2), des contours extérieurs et intérieurs des régions coloriées et indépendantes du point de vue topologique de ladite image de pixels.
3. Procédé de conversion d'une image à trois dimensions en image à deux dimensions selon la revendication 2, caractérisé en ce qu'il comporte l'étape supplémentaire (E4) d'approximation polygonale par subdivision des contours détectés à l'issue de l'étape supplémentaire de détection (E3) en des contours vectoriels, afin d'obtenir une image vectorielle à deux dimensions.
4. Procédé de conversion d'une image à trois dimensions en image à deux dimensions selon la revendication 3, caractérisé en ce que chaque contour vectoriel obtenu est orienté suivant un sens de parcours, qui indique si ledit contour vectoriel est un contour intérieur ou un contour extérieur d'une région coloriée de l'image vectorielle à deux dimensions obtenue.
5. Procédé de conversion d'une image à trois dimensions en image à deux dimensions selon l'une quelconque des revendications 2 à 4, caractérisé en ce que les contours détectés à l'issue de l'étape supplémentaire de détection (E3) passent entre les pixels limitrophes de chaque région coloriée et indépendante du point de vue topologique de la première image de pixels obtenue à l'issue de l'étape de première application (E2).
6. Procédé de conversion d'une image à trois dimensions en image à deux dimensions suivant l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comporte les étapes supplémentaires de:
Détection de traits de pliure des composantes de ladite image à trois dimensions,
Projection desdits traits de pliure sur une surface (Sf) depuis un point de vue (Po), les profondeurs, dans une pyramide de vue formée par ledit point de vue, des sommets desdits traits de pliure étant conservées dans les données des traits de pliure projetés,
Deuxième application auxdits traits de pliure de l'algorithme du "Z-buffer", initialisé avec des données issues de l'étape de première application (E2), et coloriage desdits traits de pliure avec une couleur distincte de celles utilisées à l'étape de première application (E2), afin d'obtenir une seconde image de pixels.
7. Procédé de conversion d'une image à trois dimensions en image à deux dimensions suivant la revendication 6, caractérisé en ce qu'il comporte les étapes supplémentaires de détection, dans la seconde image de pixels obtenue à l'issue de l'étape de deuxième application, des ensembles distincts de pixels marquant des traits de pliure, et d'approximation polygonale par subdivision desdits traits de pliure en des traits de pliure vectoriels.
8. Procédé d'utilisation d'images vectorielles successives obtenues à l'issue de l'étape supplémentaire d'approximation polygonale du procédé de conversion suivant l'une quelconque des revendications 3 à 7, ledit procédé de conversion étant appliqué à des images en trois dimensions d'une animation pour produire lesdites images vectorielles successives, caractérisé en ce qu'une image vectorielle courante desdites images vectorielles successives est corrigée en utilisant une image vectorielle précédente, afin de limiter les discontinuités de mouvement entre lesdites images vectorielles.
9. Programme d'ordinateur comportant des instructions pour mettre en œuvre le procédé selon l'une quelconque des revendications 1 à 8, lorsqu'il est exécuté sur un ordinateur.
10. Dispositif de conversion d'une image à trois dimensions en image à deux dimensions contenant des moyens de mise en œuvre du procédé selon l'une quelconque des revendications 1 à 8.
11. Moteur graphique contenant des moyens de mise en œuvre du procédé selon l'une quelconque des revendications 1 à 8.
PCT/FR2006/050323 2005-04-11 2006-04-10 Procede de conversion d'une image a trois dimensions en image a deux dimensions Ceased WO2006108988A2 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0503597 2005-04-11
FR0503597 2005-04-11

Publications (2)

Publication Number Publication Date
WO2006108988A2 true WO2006108988A2 (fr) 2006-10-19
WO2006108988A3 WO2006108988A3 (fr) 2007-02-22

Family

ID=34955037

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2006/050323 Ceased WO2006108988A2 (fr) 2005-04-11 2006-04-10 Procede de conversion d'une image a trois dimensions en image a deux dimensions

Country Status (1)

Country Link
WO (1) WO2006108988A2 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115965712A (zh) * 2023-03-16 2023-04-14 深圳市规划和自然资源数据管理中心(深圳市空间地理信息中心) 一种建筑物二维矢量图构建方法、系统、设备及存储介质

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU5702596A (en) * 1996-05-16 1997-12-05 Original Design Inc. Method and apparatus for generation of projection image data
JPH09330423A (ja) * 1996-06-13 1997-12-22 Fujitsu Ltd 三次元形状データ変換装置

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115965712A (zh) * 2023-03-16 2023-04-14 深圳市规划和自然资源数据管理中心(深圳市空间地理信息中心) 一种建筑物二维矢量图构建方法、系统、设备及存储介质

Also Published As

Publication number Publication date
WO2006108988A3 (fr) 2007-02-22

Similar Documents

Publication Publication Date Title
Newson et al. Video inpainting of complex scenes
CN112102477B (zh) 三维模型重建方法、装置、计算机设备和存储介质
CN114170311B (zh) 一种双目立体匹配方法
US11164319B2 (en) Machine learning feature vector generator using depth image foreground attributes
Sasaki et al. Joint gap detection and inpainting of line drawings
EP1059611A1 (fr) Appareil de traitement d'images
WO2001099052A1 (fr) Raffinement d'un maillage triangulaire en trois dimensions
US9224238B2 (en) Seamless texturing of 3D meshes of objects from multiple views
CN112508991B (zh) 一种前后景分离的熊猫照片卡通化方法
KR20050030569A (ko) 화상 처리 장치 및 그 방법
Zhou et al. Drawingspinup: 3d animation from single character drawings
CN112308804B (zh) 图像处理方法、装置、电子设备及计算机可读介质
CN118096601A (zh) 基于小波变换与多尺度残差网络的图像修复方法及系统
EP2297705B1 (fr) Procede de composition temps reel d'une video
CN112132750A (zh) 一种视频处理方法与装置
CN115115399A (zh) 对象推荐方法、装置、设备、介质及计算机程序产品
FR2781907A1 (fr) Procede de codage d'un maillage source tenant compte des discontinuites, et applications correspondantes
WO2014023887A1 (fr) Procédé de rendu d'image en temps réel
Alliez et al. Efficient view-dependent refinement of 3D meshes using sqrt {3}-subdivision
CN115937343A (zh) 一种基于结构张量的图像局部纹理稳定场重建方法
EP1121665B1 (fr) Procede de codage d'un maillage source, avec optimisation de la position d'un sommet resultant d'une fusion d'arete, et applications correspondantes
CN119515733B (zh) 基于自适应人脸对称的人脸阴影消除方法及装置
Feldman et al. Depth completion with rgb prior
CN121746446B (zh) 基于分层最小曲面重构的激光雷达深度补全方法
Boldyš et al. Exemplar-based inpainting with rotation invariant patch matching

Legal Events

Date Code Title Description
NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Country of ref document: DE

NENP Non-entry into the national phase

Ref country code: RU

WWW Wipo information: withdrawn in national office

Country of ref document: RU

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 06726329

Country of ref document: EP

Kind code of ref document: A2

122 Ep: pct application non-entry in european phase

Ref document number: 06726329

Country of ref document: EP

Kind code of ref document: A2

WWW Wipo information: withdrawn in national office

Ref document number: 6726329

Country of ref document: EP