+

WO2006018570A2 - Procede et systeme d'identification de zones de proximite entre plusieurs objets geometriques simules numeriquement - Google Patents

Procede et systeme d'identification de zones de proximite entre plusieurs objets geometriques simules numeriquement Download PDF

Info

Publication number
WO2006018570A2
WO2006018570A2 PCT/FR2005/050597 FR2005050597W WO2006018570A2 WO 2006018570 A2 WO2006018570 A2 WO 2006018570A2 FR 2005050597 W FR2005050597 W FR 2005050597W WO 2006018570 A2 WO2006018570 A2 WO 2006018570A2
Authority
WO
WIPO (PCT)
Prior art keywords
objects
during
session
pions
tournament
Prior art date
Application number
PCT/FR2005/050597
Other languages
English (en)
Other versions
WO2006018570A3 (fr
Inventor
Lionnel Joussemet
Flavien Maingreaud
Original Assignee
Commissariat A L'energie Atomique
Haption
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 Commissariat A L'energie Atomique, Haption filed Critical Commissariat A L'energie Atomique
Priority to EP05792025A priority Critical patent/EP1779306A2/fr
Priority to JP2007521997A priority patent/JP4829885B2/ja
Priority to US11/658,125 priority patent/US7774180B2/en
Publication of WO2006018570A2 publication Critical patent/WO2006018570A2/fr
Publication of WO2006018570A3 publication Critical patent/WO2006018570A3/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/12—Computing arrangements based on biological models using genetic models
    • G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2210/00—Indexing scheme for image generation or computer graphics
    • G06T2210/21—Collision detection, intersection

Definitions

  • the present invention relates to a method and system for identifying proximity areas and evaluating distances between several numerically simulated objects.
  • An object is thus constituted by a geometry within a digital environment.
  • a virtual reality platform ( Figure 1) includes interfaces 10 between the virtual environment and the operator (s) participating in the simulation. There are several types of interfaces, each for the stimulation of one of the senses of the operator or operators. It is thus possible to implement in an RV platform for example visual interfaces 11, auditory 12, haptics 13.
  • An RV platform also includes a dynamic simulator
  • a dynamic simulator 20 is comparable to a physical engine whose role will be to govern the evolution of a virtual world composed of objects having dynamic and geometric properties. This task can be broken down into two sub-tasks: the management of the dynamic of the virtual world (dynamic engine 21) and the management of the collisions that take place within it (collision engine 22).
  • Figure 2 illustrates the operating diagram of a dynamic motor 21 in the case of a single object.
  • the first step 211 consists in taking stock of the forces applied to the virtual object. These efforts to which the subject is subject may be of several origins: gravity, joint constraints (also called bilateral links), operator manipulation. Their accumulation will make it possible to obtain a static torsor of effort.
  • the second step 212 will be determined the linear and angular accelerations of the object by applying the fundamental principle of dynamics (PFD).
  • PFD fundamental principle of dynamics
  • the new position and orientation are then directly determined by double integration during the third step 213. It seems interesting to observe that the fact of evolving in discrete time imposes to approximate the integration. For this, several methods are possible (Euler, Tustin, Runge-Kutta, ).
  • the last step 214 is simply to update the position and orientation of the object under consideration.
  • Collision engine 1 22 provides a task that is decomposable into two phases; collision detection and generation of contact forces. Collision detection can be carried out according to several techniques depending on the type of geometry used and the expected performance. In the context of the discrete methods, which constitute the great majority of the techniques used, this first phase consists in detecting the interpenetrations between the different pairs of objects at every moment. On the contrary, continuous methods detect the exact moment of the first contact between objects.
  • this first phase is the heaviest task to be performed by the dynamic simulator. Indeed, the amount of computations to be performed as part of this detection is directly related to the nature of the objects evolving within the virtual world, particularly in terms of geometric complexities.
  • this first phase of collision detection it remains to determine the forces resulting from collisions between the pairs of solids concerned. These are usually decomposed into a normal reaction force and a tangential friction force. It is thus necessary to model these collisions. To do this, three methods are mainly used: penalty, impulse and constraint.
  • the first technique will consist in calculating, at any time, the minimum distance between two objects E and E2 of polyhedral type and thus know the geometric elements el, e2 closest (see Figure 3).
  • Several approaches have thus been implemented in order to obtain this minimum distance as well as the geometric elements concerned.
  • Most of these techniques consider convex objects. These The latter can still be used in the context of simulations involving concave objects by decomposition of the latter into convex elements.
  • a first method for determining this minimum distance and the elements concerned was introduced by Gilbert, Johnson and Keerthi. This method, based on the Minkowsky difference and the convex optimization, makes it possible to determine the distance between two convex envelopes of two sets of points El and £ -?
  • a second approach taking into account a hierarchy of enclosing volumes is to partition the spaces occupied by the objects composing the scene.
  • each object will be approximated by a bounding volume itself decomposed into a tree of subvolumes (generally of similar topology to the enclosing volume "root").
  • the strategy is to spatially locate areas that may be interpenetrating.
  • the presence of overlapping bounding volumes of distinct objects is tested, and then, in the event of an overlap, a similar recursive test is performed at the level of the sub-volumes they contain.
  • This strategy avoids a multitude of irrelevant tests and is widely used within existing physical engines.
  • these overlap tests can be very numerous in some cases (plan / plan for example) and thus compromise the performance of the simulation.
  • updating these volumes can be expensive.
  • spheres 1 isothetic bounding boxes 2 (AABB) and oriented bounding boxes 3 (OBB) (see Figures 4a, 4b, 4c).
  • the all-encompassing spheres have the main advantage of the simplicity of the overlap tests. Indeed, the test of overlap of two spheres is limited to a comparison between the distance separating their center and the sum of their respective rays. However, the spheres generally give a less optimal approximation of the geometry considered, in comparison with the OBBs for example which, despite much heavier overlapping tests (theorem of the separator axes), limit the execution of non-relevant tests by a minimum encompassed volume.
  • the enclosing volume hierarchies are in the form of trees, often binary in order to optimize their course. We also talk about Octrees (8 branches / node), or Quadtrees (4 branches / node more suited to 2D geometries).
  • the volume swept by a moving solid during a time interval corresponds to the union of the zones of space that it has occupied during this period.
  • This geometric tool has several application domains: robotics workspace evaluation, geometric modeling in CAD.
  • FIGS. 5a and 5b which respectively illustrate the initial 4 and final 5 positions of the object and the corresponding swept volume 6.
  • Figures 7a and 7b show a technique based on a hybrid discretization using voxels (or “voxmap”) and the combination of point cloud (or “shell point”) and normals.
  • This technique is illustrated in Figures 7a and 7b.
  • Figure 7a shows a first original object 8 represented as voxels 8a and a second original object 9 represented as a cloud of points and normals 9a.
  • FIG. 7b shows the detail of an interaction between a voxel 8a of a static surface of the object 8 and the cloud of points of the object 9 with the tangent plane 9b to the static surface and the force vector 9a according to the normal to the point cloud of object 9.
  • This hybrid discretization technique requires a relatively long pre-computation phase but allows complex geometric data to be managed.
  • Implicit surfaces are the set of points for which 0, the interior of the model being the points for which / ( ⁇ ,>', - :) ⁇ 0.
  • This method is particularly interesting in the case where the collisions are not very frequent (the collision calculation, the determination of C ⁇ ( ⁇ , is expensive) and in the absence of friction, it has the advantage of not not have any adverse effects on the stability of the overall system.
  • the pulse method is a kinematic approach that equates the interaction between two rigid objects to an impact.
  • the collision is thus considered as a quasi-instantaneous event generating a significant effort (called impulse) on the objects concerned.
  • impulse a significant effort
  • the pulse is calculated to separate them into a single iteration. It is often the condition that the objects concerned have a ballistic trajectory in order to optimize the calculations.
  • the penalty method makes it possible to manage repulsion efforts between rigid or deformable objects. It consists in applying to colliding objects 14, 15 a force proportional to the depth of interpenetration (we speak of stiffness). The "mechanism" of repulsion is thus often equated with a system 16 of derivative proportional type (see Figure 8). This method requires knowing the penetration vector (which can be expensive) and often generates instabilities (especially in cases of multi-point collisions). It follows from the foregoing that the evaluation of distances and the identification of proximity zones, and where appropriate the detection of collisions, between geometric objects evolving within a digital environment, is seen as an essential step in a a large number of disciplines, such as virtual reality or the scripting of robotic system movements.
  • the present invention aims at remedying the drawbacks of the prior art and at making it possible to respond to most of the recurring problems in the evaluation of distances or the identification of proximity zones, and in particular in the detection of collisions by providing solutions. with reduced computation times compatible with real-time applications, with a high degree of performance and simplicity of implementation, even when the interacting objects have complex geometries or different natures or qualities.
  • a method of identifying proximity zones between at least first and second digitally simulated objects characterized in that it comprises the following steps:
  • tournament sessions are organized within the Npions of the created population, where during each session a percentage of the population is subjected to combat during which it is evaluated for each pair of pawns submitted to a fight. , based on an assessment of the quality defined by an aptitude criterion, which has won and which has lost and the winner and the loser are identified by marking which is different at the end of each session of the tournament, (d) after the tournament, an exploratory mutation of the pawns having lost during a first session is carried out, the pions which have lost during a second session are replaced by crossing randomly chosen pions and a redefinition is carried out random pieces lost during a third session,
  • the distances between the identified proximity zones can be evaluated.
  • the data for identifying areas of the space describing the geometry of at least one of the first and second numerically simulated objects may include polyhedral representations, voxel representations, parametric surface representations or point clouds.
  • the aptitude criterion for evaluating the quality of a pion is constituted by a measurement of the distance separating the first and second nucleons defining this pion, the the quaiity of the pawn being all the greater as the measured distance is smaller. This measurement of the distance may for example take into account the square of the distance separating the first and second nucleons defining the pion.
  • the method according to the invention may further comprise, after the step (a) of providing data describing the geometry of each of the first and second digitally simulated objects, the following steps:
  • a proximity card is created containing information defining the proximity properties within the first and second objects and the information of this proximity card is stored in memory.
  • the mutation of the pions having lost during a session of the tournament generating exploratory mutations for lost pions consists in moving the first and second nucleons composing a pion on the surface of the first and second objects to which these first and second nucleons respectively belong.
  • At least one of the first and second nucleons composing this pawn and belonging to the one of the first and second objects represented in a polyhedral form is subjected to a succession of discrete center facet displacements in the facet center by considering the information defining the neighborhood properties stored in memory.
  • At least one of the first and second nucleons composing this pion and belonging to one of the first and second objects represented in a polyhedral form is subjected to displacement on the same facet on a disk having as center the initial position of this point and for radius a maximum displacement amplitude which depends on the area of the facet on which the displacement is made.
  • At least one of the first and second nucleons composing this pawn and belonging to one of the first and second objects represented in a polyhedral shape is subjected to a "wormhole" displacement from one vertex of one facet to another vertex close to another facet that is not necessarily connected, considering the information defining the proximity properties stored in memory.
  • the first and second nucleons composing this pion and respectively belonging to the first and second objects each represented in a polyhedral form with triangular facets are positioned such that they delimit a segment defining the minimum distance between the two triangular facets to which these first and second nucleons respectively belong.
  • the new pion when replacing a pawn having lost during a session of the tournament generating for the pions having lost substitutions by crossing randomly selected pions, to define the new pawn resulting from the crossing of a first and a second selected pawns randomly, the new pion is considered to be composed of the first nucleon of the first randomly selected pawn and the second nucleon of the second randomly selected pawn.
  • the invention relates more generally to a method applied to a set of P objects simulated numerically with P> 2, characterized in that it comprises the following steps: (a) provides data describing the geometry of each of the P graphically simulated objects,
  • tournament sessions are organized within the Npions of the created population, where during each session a percentage of the population is subjected to combat during which it is evaluated for each pair of pawns submitted to a fight. , based on an assessment of the quality defined by an aptitude criterion, which has won and which has lost and the winner and the loser are identified by marking which is different at the end of each session of the tournament,
  • Geometric information is extracted on demand from an updated configuration of the pion population during repetitive execution.
  • the method advantageously comprises the following additional steps after step (a) of providing data describing the geometry of the digitally simulated P objects:
  • a proximity card is created containing information defining the proximity properties within each of the P objects and the information of this proximity card is stored in memory.
  • the invention further relates to a proximity zone identification system between a number P of objects simulated numerically with P> 2, characterized in that it comprises;
  • an initialization module for creating a population consisting of a set of N individuals called pions each defined by first and second nucleons themselves defined as points respectively belonging to the geometries of one of the P objects and another of the P objects,
  • a central processing unit comprising at least:
  • (c) means for selecting a percentage of the population of the N pions to be subjected to pairwise combat during a session of a tournament
  • (c2) means of comparison and calculation for evaluating during a session of a tournament, for each pair of pawns submitted to a fight, the quality of each pawn of the pair of pawns based on an aptitude criterion
  • (c3) marking means for identifying at each session of the tournament which pieces of a pair of pions subject to a fight has won, and which of the pieces of the said pair of pawns submitted to a fight has lost,
  • (c4) iteration means for producing an evolution of the pions that have undergone at least one combat these iteration means being associated at least with an exploratory mutation operator of the pions having lost during a first session of the tournament, at a replacement operator of the pawns having lost during a second session of the tournament by crossing randomly selected pawns and to an operator of redefinition of the pawns having lost during a third session of the tournament, and
  • the system may further include:
  • the central processing unit may comprise a set of computing units operating in parallel.
  • the method and the system according to the invention are thus based on an evolutionary process based on a stochastic approach. This evolutionary process deals with populations of individuals defined by real components and not simply binary.
  • FIG. 1 is a block diagram representing the functional architecture of a virtual reality platform
  • FIG. 2 is a flowchart showing the dynamic evolution diagram of an object contained in the virtual world according to the laws; of physics,
  • FIG. 3 is a diagram illustrating a known method for calculating the minimum distance between two objects of the polyhedral type
  • FIGS. 4a, 4b and 4c show three examples of approximating an object by a bounding volume
  • FIG. 5a illustrates initial and final positions of a spherical object in translation
  • FIG. 5b illustrates the swept volume corresponding to the translation of the object of FIG. 5a
  • FIG. 6 illustrates an example of a voxelic decomposition of an object
  • FIG. 7a shows an example of hybrid representation of an object in the form of voxels cooperating with another object represented in the form of a cloud of points and normals
  • FIG. 7b represents the detail of an interaction zone of the two objects represented in a hybrid manner in FIG. 7a
  • FIG. 8 illustrates the representation of two objects subjected to repulsion efforts according to the penalty method
  • FIG. 9 is a diagram illustrating the genotype of an individual or pion used in the context of the invention
  • FIG. 10 illustrates an example of discrete exploratory displacement of a point on a polyhedron, as part of a mutation
  • FIG. 11 shows an example of an operating operator involved in a mutation
  • FIG. 12a illustrates a process for identifying nearby elements in the context of objects represented in a polyhedral form
  • FIG. 12b illustrates an example of a path without wormhole in the object represented in FIG. 12a
  • FIG. 12c illustrates an example of a path through a wormhole in the object represented in FIG. 12a;
  • FIG. 13 illustrates the principle of the crossing of two pions,
  • FIG. 14 represents the three main phases of the process according to the invention.
  • FIGS. 15a, 15b and 15c illustrate three examples of geometrical configurations making it possible to materialize the segment defining the minimum distance between two triangles of polyhedral representations of objects, to which belong the two points composing a pion,
  • FIG. 16 illustrates the projection of ends of a segment on a plane containing a triangle as part of the determination of the segment defining the minimum distance between two triangles belonging to polyhedra representing two interacting objects
  • FIGS. 17 and 18 illustrate, in the case of the process represented in FIG. 16, the determination of a segment defining a minimum distance, respectively in the case of segment-point and in the segment-segment case,
  • FIG. 19 represents the genotype of several pions defined between different polyhedra representing different objects
  • FIG. 20 illustrates the random replacement of a pawn in the case of an object represented in polyhedral form
  • FIG. 21 illustrates the genotype of a pawn defined between two parameterized surfaces representing two objects
  • FIG. 22 illustrates the genotype of a pawn defined between two point clouds representing two objects
  • FIG. 23 illustrates the genotype of a pawn defined between two voxelic representations of objects
  • FIG. 25 represents hybrid pins defined between geometries of different types representing objects
  • FIG. 26 is a block diagram showing the main modules constituting an exemplary system according to the invention.
  • the method and system according to the invention described according to a particular embodiment, make it possible, starting from digitally simulated objects, or virtual objects, to identify, throughout a real-time dynamic simulation featuring geometrical representations of objects, the geometric zones likely to collide, regardless of the geometric complexity and nature (convexity, rigidity) of the objects.
  • the method according to the invention uses an evolutionary process. In general, it applies a strategy that consists of changing a population of individuals using variation operators (mutation, crossing) to converge this population to an optimal configuration.
  • variation operators mutation, crossing
  • the basic strategy of the method according to the invention consists in changing a population of individuals using variation operators (mutation, crossing) intended to converge the population (set of individuals). to an optimal configuration.
  • Figure 9 illustrates an exemplary definition of the 51 genotype of an individual (which subsequently will also be called "pin") which is defined as a pair of nucleons constituted by points belonging respectively to each of the two meshes Objeti and Object 2 representing the first and second objects whose proximity we wish to evaluate.
  • the genotype 51 of a pawn can thus be expressed as:
  • Face indices (unsigned integers) represent the identifiers of the faces to which belong respectively the points defining the pion, a, and ⁇ t the coordinates of the point belonging to the first polyhedron in the base O 1 , e 2 ) of the relevant face , and respectively for ⁇ 2 and ⁇ 2 in the base (e ⁇ , e ⁇ ). (O ⁇ , ⁇ , 0 ⁇ l ⁇ , ⁇ , + ⁇ t ⁇ i).
  • a pion is simply defined by two nucleons belonging respectively to two objects of any kind. If we consider for example the case of implicit surfaces, in this case a pawn will be defined by the coordinates (* ,, y x , z x ) of the first point and the coordinates (x 2 , y 2 , ⁇ 2 ) ⁇ u second. In the case of voxelic type geometries, the points may be defined by the index of the voxels concerned. Thus, the description of a pawn is directly related to the type of geometry used. It is also possible to define a pion between two geometries of different types, the coordinates of the points being systematically expressed in the Cartesian space at the time of the evaluation.
  • the objective function ("fitness") or aptitude criterion for evaluating the quality of a pion is constituted by measuring the distance separating the first and second nucleons defining the pion. This measure can advantageously be chosen as being the square of the distance separating the two nucleons composing the pion.
  • Quality quality (p) of an individual or p-p is inversely proportional to its fitness goal function (p).
  • the mutation is an evolution operator that is definable as a more or less important variation of the genetic heritage of an individual.
  • to mutate an individual consists in moving the points that compose it on the surface of the objects to which they belong.
  • Figure 10 illustrates the discrete exploratory displacement of a point on a polyhedron with an amplitude of eight jumps, but this value is naturally given only as an example.
  • An exploitation operator that corresponds to another type of mutation, illustrated in Figure 11, is intended to refine the positioning of the points that make up the individual concerned. Unlike the case of the exploratory mutation, these displacements are defined metrically. Thus each point will perform a displacement on a disk of radius ⁇ FxP i o , t i maximum displacement amplitude, having as center the initial position of the point.
  • the maximum displacement amplitude (expressed in meters) may be dependent on the area of the face 56 on which the displacement is performed. Thus, this amplitude is calculated during the pre-calculation phase for each facet 56.
  • Figure 12a illustrates the polyhedral representation 60 of an object having faces 61.
  • the vertices 64, 65 are identified as being closest to the vertices 62, 63.
  • Figure 12b illustrates an example of a path 66 without a wormhole, from the vertex 63 to a point 67.
  • Figure 12c illustrates an alternative path using the "wormhole” mutation operator.
  • the path from the top 63 to the point 67 includes a passage 68 of the "wormhole” type outside the representation 60 of the object, between the vertices 63 and 64 identified as being close.
  • Mutation operators having functions similar to those of the three operators described above can be defined in the simulation framework involving other types of geometries.
  • the invention also implements a variation operator, called "crossover", which is intended to accelerate the convergence of the population (FIG. 13).
  • the principle is to generate a pawn (child) by coupling two pawns coming from the population (spawners).
  • the new pawn thus has genetic properties specific to its two parents.
  • this operator can be used in the following way: the pawn "child” has for nucleon 1 that of the first spawner and for nucleon 2 that of the second.
  • FIG. 14 The general scheme of the method according to the invention is illustrated in FIG. 14, with a first initialization phase 71, a second tournament phase 72 and a third evolution phase 73.
  • initialization phase 71 data is provided to identify points describing the geometry of each of the graphically simulated objects and stores these data in memory.
  • a connectivity map is also created containing information defining the topological neighborhood properties within the objects and the information of this connectivity map is stored in memory.
  • the initialization phase 71 also comprises the establishment of a proximity card containing information defining the proximity properties (wormhole) within the objects and the storage in memory of the information of this proximity card. Finally, during the initialization phase 71, a population consisting of a set of N individuals (which may be called pions) each defined by first and second nucleons constituted by points respectively belonging to the geometries of two objects is created. previously identified.
  • Phase 72 tournament consists of the organization of fights between individuals.
  • a fight between two individuals or pions consists of evaluating which of the two pions proves to be of better quality, that is to say which of the two pions has a goal function (or aptitude criterion) "fitness" the weakest.
  • sessions are organized within the N pions of the created population where, during each of the sessions, a percentage of the population is subjected to fights during which it is evaluated for each pair of pieces. subject to a fight, based on a quality assessment defined on the basis of an aptitude criterion, which has won and which has lost and the winner and the loser are identified by a mark that is different at the end each session of the tournament.
  • the various sessions of the tournament phase 72 may for example comprise a first session Mut% consisting of fights of a percentage of the population which will then generate mutations, a second session Cross% consisting of fights of a percentage of the population which will then generate crosses and a third session Rand% consisting of fights of a percentage of the population which will then generate random redefinitions.
  • the first, second and third sessions, Mut%, Cross% and Rand% can take place in any order.
  • the winning pieces are identified by a marking that is different from that of the losing pieces.
  • the marking of the pieces also differs according to the session during which they have undergone one or more fights.
  • the evolution phase 73 consists in applying the previously defined variation operators to the population according to the results of the tournament and thus includes the mutation of the pieces having lost during the first session Mut% of the tournament, the replacement of the pieces having lost during the second session Cross% of the tournament by crossing randomly selected pieces, and the redefinition of the pieces having lost during the third session Rand% of the tournament.
  • the exploitation of the winners of the combats which are supposed to be good elements makes it possible to determine zones of proximity between two objects.
  • the process is iterative and phases 72 and 73 can be repeated without stopping. It is possible at any moment to exploit an improved configuration by exploiting the only pawns then marked as being winners.
  • the method according to the invention is little dependent on the geometric nature and the quality of the objects. It can be used in the context of simulations involving all types of geometries (polyhedra, voxels, parametric surfaces, etc.) as long as the appropriate variation operators are defined. In addition, it allows the mix of geometries, the points that make up the pions can evolve in a completely different way to the surface of the objects to which they respectively belong. The process is not sensitive to concavities, exploratory mutations and random redefinitions ensuring diversity of the population.
  • an individual or pion of a population of N individuals is composed of two points which can also be called nucleons.
  • This mutation operator makes it possible to minimize locally, according to a deterministic approach, the objective function (fitness) of the pion concerned.
  • This mutation operator is intended to be applied to the elite of the individuals making up the population. It is intended to accelerate the convergence and increase the accuracy of the results resulting from the implementation of the method.
  • the goal of this operator is to position the nucleons that make up the pion concerned so as to materialize the segment defining the minimum distance between the two triangles to which they respectively belong.
  • Figures 15a, 15b, 15c show three different geometrical configurations with two triangles 81, 82; 83, 84 and 85, 86 respectively for which segment 87; 88; 89 respectively materializing the minimum distance between the two triangles corresponds to a vertex / face interaction, vertex / vertex and edge / edge.
  • the first phase consists of orthogonally projecting the ends of the segment onto the plane containing the triangle.
  • the combination of the positions of their projected relative to the triangle will make it possible to identify the possible geometrical configurations and the potentially affected elements.
  • the positions of the projected relative to the triangle are formalized by their belonging to one of the plan portions defined by the straight lines bearing the sides of the triangle. For example, in the case illustrated in FIG. 16, the projections Pi, Qi of the ends Pet Q of the segment belong respectively to the zones Z 2 and Z 4 of the plane containing the triangle (A, B, C).
  • the second phase will consist of determining the optimal counter.
  • the goal is to determine the coefficient ⁇ such that: ⁇ e [0, l], V // e [0, l] (X-PQ) M ⁇ ( ⁇ -PQ) M ⁇
  • the goal is to determine the coefficients X and ⁇ such that:
  • the pions of the same population can evolve not only on one of the pairs of geometries contained in the simulation, but on all the pairs of geometries (or meshes) contained in the simulation.
  • the genotype of a pion is expressed in the following way, with MeSh 1 and Mesh 2 which represent the identification of the meshes (polyhedra) of the objects to which the two points (nucleons) component belong.
  • MeSh 1 and Mesh 2 represent the identification of the meshes (polyhedra) of the objects to which the two points (nucleons) component belong.
  • indices Mesh and Face respectively represent the identifiers of the polyhedra and faces to which belong the nucleons defining the pion, ⁇ x and ⁇ x the coordinates of the point belonging to the first polyhedron in the base (e ,, e 2 ) of the face concerned, and respectively for a 2 and ⁇ 2 in the base (e ⁇ , e ' 2 ). (0 ⁇ 1 ⁇ 1, 0 ⁇ ⁇ , ⁇ 1, a 1 + ⁇ 1 ⁇ 1).
  • Inter-geometry "jumps" of the nucleons are performed during the random replacement phase that covers the entire space to be traveled and not just one of the geometries.
  • genotypes of the four pions in the example of Figure 19 are as follows;
  • the invention is equally applicable to simulations involving polyhedral geometries, which are commonly used in a large number of fields of application such as virtual reality or computer graphics, or to simulations involving non-linear geometries. polyhedral.
  • Figure 21 illustrates the case of objects represented by parametric surfaces (Bézier, B-Spline, %) called "patch”.
  • each of the nucleons of a pion includes the identifier Patchi, resp. Patch 2 of the parametric surface to which it belongs and the coordinates U 1 Vi resp U 2 V 2 of this nucleon within this parameterized surface Patchi, resp Patch 2 to which it belongs.
  • the genotype of a pawn is then the following:
  • Mi and M 2 are the mathematical expressions that respectively define Patchi and Patch 2 .
  • a random repositioning of a nucleon can be done by randomly changing its coordinates.
  • the case of objects represented in the form of point clouds is illustrated in Figure 22 with two representations of objects referenced Nuagei and Nuag ⁇ 2.
  • each of nucleons by the identifier pi resp p 2 from the point to which it belongs, as follows:
  • Figure 23 illustrates the case of objects represented by voxelic geometries called Geometry and Geometry2.
  • each of the nucleons is defined by the identifier ⁇ i resp ⁇ 2 of the voxel to which it belongs as indicated below:
  • the previously defined genotype may be unsuitable in some cases (voxels of different sizes or too large). It may then be necessary to enrich the latter with the coordinates of the nucleons within their respective voxel.
  • mutators can be defined as follows; Discrete Exploration: The nucleon moves from voxel to voxel using a pre-calculated proximity map.
  • the nucleon can move on the surface of the voxel to which it belongs (stochastic variation of its coordinates within the voxel).
  • Deterministic Exploitation The segment "materializing" the minimum distance between two cubes is trivially deterministically deterministic. Deterministic exploitation thus consists in locally minimizing a pawn within a pair of voxels.
  • Random Replacement Random selection of new voxels.
  • Figure 24 represents in its generality the crossing operator to produce from two pawns Géniteuri and Géniteur a child pawn composed of the first nucleon Nucléoni of the pion Géniteur ! and second nucleon Nucleon 2 the pin 2 progenitor.
  • genotypes and mutators that have just been defined are presented as formalisms adapted to the definition and the evolution of nucleons within the different types of selected geometries.
  • the evaluation of the quality of a pion is reduced to the evaluation of the Euclidean distance separating the nucleons that compose it.
  • Figure 26 shows in block diagram form an exemplary proximity area identification system between a number P of graphically simulated objects, with P> 2, according to the invention.
  • This system comprises a memory unit 110 with at least memory areas 111, 112, 113.
  • a first memory area 111 makes it possible to store data describing the geometry of each of the P graphically simulated objects.
  • a second memory area 112 stores information representing a connectivity map and defining neighborhood properties within each of the P objects.
  • a third memory area 113 stores information representing a proximity map and defining the proximity properties within each of the P objects.
  • An initialization module 120 makes it possible to create a population consisting of a set of N pions each defined by first and second points or nucleons respectively belonging to the geometries of one of the P objects and another of the P objects.
  • a display screen 130 allows, if desired, to display the P simulated objects numerically.
  • a central processing unit 140 comprises at least the following subassemblies 141 to 145;
  • comparison and calculation means 142 for evaluating during a session of a tournament, for each pair of pions subjected to a fight, the quality of each of the pieces of the pair of pions based on a criterion of 'aptitude,
  • marking means 143 for identifying at each session of the tournament which pieces of a pair of pawns submitted to a fight have won, and which pieces of said pair of pions subjected to a fight have lost, means for iteration 144 to produce an evolution of the pawns that have undergone at least one fight,
  • an extraction module 145 for retaining only the best pions of the population according to the aptitude criterion, for the determination of the proximity zones between at least two of the P objects.
  • the iteration means 144 are associated with at least one exploratory mutation operator of the pawns having lost during a first session of the tournament, to an operator replacing the pieces having lost during a second session of the tournament by crossing randomly chosen pieces and an operator redefining the pieces that lost during a third session of the tournament.
  • the reference 150 designates an optional interface such as a haptic interface making it possible to exploit the selected and selected pieces. during the repetitive execution of tournaments and the evolutionary process.
  • the invention avoids the sorting phases which are time consuming and, by virtue of the independence of the processing of the individuals, allows a process which is highly parallelizable with a possibility of distribution of the calculations on several microprocessors or microcontrollers, as well as for each nucleon of a pion the possibility of moving from one type of object geometry to another, which gives great flexibility of operation.
  • Populations of individuals may include for example a few hundred individuals.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Biophysics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Evolutionary Biology (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Physiology (AREA)
  • Genetics & Genomics (AREA)
  • Artificial Intelligence (AREA)
  • Biomedical Technology (AREA)
  • Geometry (AREA)
  • Computer Graphics (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Molecular Biology (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Processing Or Creating Images (AREA)

Abstract

Le système d'identification des zones de proximité entre plusieurs objets simulés numériquement comprend : (a) une mémoire (111) pour stocker des données décrivant la géométrie des objets, (b) un module d'initialisation (120) pour créer une population constituée de pions, (c) une unité centrale de traitement (140) comprenant au moins : (c1) une unité (141) de sélection d'un pourcentage de la population des pions devant être soumis à des combats par paires, (c2) une unité de comparaison et de calcul (142) pour évaluer, pour chaque paire de pions soumis à un combat, la qualité de chacun des pions, (c3) une unité de marquage (143) pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné ou a perdu, (c4) une unité d'itération (144) pour produire une évolution des pions qui ont subi au moins un combat, en association avec au moins un opérateur de mutation exploratoire et un opérateur de redéfinition, et (c5) un module d'extraction (145) pour ne retenir que les meilleurs pions de la population pour la détermination des zones de proximité entre au moins deux objets.

Description

Procédé et système d'identification de zones de proximité entre plusieurs objets géométriques simulés numériquement
La présente invention concerne un procédé et un système d'identification de zones de proximité et d'évaluation de distances entre plusieurs objets simulés numériquement. Un objet est ainsi constitué par une géométrie au sein d'un environnement numérique.
A titre d'exemple, la simulation interactive du monde réel au sein d'un environnement numérique est dénommée "réalité virtuelle" (RV). Une plate-forme de réalité virtuelle (Figure 1) comprend des interfaces 10 entre l'environnement virtuel et le ou les opérateurs participant à la simulation. Il existe plusieurs types d'interfaces, chacune étant destinée à la stimulation de l'un des sens du ou des opérateurs. On peut ainsi mettre en œuvre dans une plate-forme RV par exemple des interfaces visuelles 11, auditives 12, haptiques 13.
Une plate-forme RV comprend en outre un simulateur dynamique
20 qui a pour fonction de régir en temps réel l'évolution des composantes de l'environnement virtuel selon les lois de la physique, ainsi que leurs interactions. Ces interactions peuvent être bilatérales (liaisons mécaniques) ou unilatérales (collision).
Un simulateur dynamique 20 est assimilable à un moteur physique dont le rôle va être de régir l'évolution d'un monde virtuel composé d'objets ayant des propriétés dynamiques et géométriques. Cette tâche est décomposable en deux sous-tâches : la gestion de la dynamique du monde virtuel (moteur dynamique 21) et la gestion des collisions qui ont lieu en son sein (moteur de collisions 22).
La gestion de la dynamique du monde virtuel permet de régir l'évolution individuelle des objets contenus dans le monde virtuel selon les lois de la physique. La Figure 2 illustre le schéma de fonctionnement d'un moteur dynamique 21 dans le cas d'un seul objet.
La première étape 211 consiste à faire un bilan des efforts appliqués à l'objet virtuel. Ces efforts auxquels est soumis l'objet peuvent être de plusieurs origines : gravité, contraintes articulaires (également appelées liaisons bilatérales), manipulation de l'opérateur. Leur accumulation va permettre d'obtenir un torseur statique d'effort. Durant la deuxième étape 212 vont être déterminées les accélérations linéaire et angulaire de l'objet par application du principe fondamental de la dynamique (PFD). Les nouvelles position et orientation sont alors directement déterminées par double intégration durant la troisième étape 213. Il paraît intéressant d'observer que le fait d'évoluer en temps discrets impose d'approximer l'intégration. Pour cela, plusieurs méthodes sont envisageables (Euler, Tustin, Runge-Kutta,...). La dernière étape 214 consiste simplement à mettre à jour les position et orientation de l'objet considéré.
Le moteur 1 de collisions 22 assure une tâche qui est décomposable en deux phases ; détection des collisions et génération des forces de contact. La détection des collisions peut être effectuée selon plusieurs techniques en fonction du type de géométrie utilisée et des performances escomptées. Dans le cadre des méthodes discrètes, qui constituent la grande majorité des techniques utilisées, cette première phase consiste à détecter les interpénétrations entre les différentes paires d'objets à chaque instant. A contrario, les méthodes continues détectent l'instant exact du premier contact entre objets.
Quelle que soit la méthode utilisée, cette première phase s'avère la plus lourde des tâches à effectuer par le simulateur dynamique. En effet, la quantité de calculs à effectuer dans le cadre de cette détection est directement liée à la nature des objets évoluant au sein du monde virtuel, particulièrement en termes de complexités géométriques. Après cette première phase de détection des collisions, il reste à déterminer les efforts résultant des collisions entre les paires de solides concernées. Ces derniers sont généralement décomposés en une force normale de réaction et une force tangentielle de frottement. Il est ainsi nécessaire de modéliser ces collisions. Pour ce faire, trois méthodes sont principalement utilisées : pénalité, impulsion et contrainte.
Dans le cadre de simulations dynamiques destinées à fonctionner en temps réel, la gestion des contraintes unilatérales (collisions), que ce soit en termes de détection ou de calcul des forces de contact, engendre une limitation de la complexité géométrique des composants du monde virtuel (nature, nombre et type d'entités élémentaires). On entend par nature de l'objet l'ensemble de ses propriétés de convexité (convexe/concave) et de rigidité (infiniment rigide/déformable). Les entités élémentaires permettant la définition géométrique d'un objet peuvent être de plusieurs types : maillages (triangles, quads), voxels, points, surfaces analytiques. Les principales techniques permettant la détection de collisions entre objets dynamiques sont présentées ci- dessous.
La localisation des zones susceptibles d'entrer en collision se retrouve dans les techniques de détection de collisions classiques et, plus particulièrement, dans les optimisations apportées à celle-ci. Ainsi, trois grandes stratégies pouvant répondre à ce besoin émergent de la littérature scientifique : le calcul de la distance minimale entre objets, les hiérarchies de volumes englobants, la considération des volumes balayés durant le mouvement.
La première technique va ainsi consister à calculer, à tout moment, la distance minimum entre deux objets El et E2 de type polyédrique et ainsi connaître les éléments géométriques el, e2 les plus proches (voir Figure 3). Plusieurs approches ont ainsi été mises en oeuvre afin d'obtenir cette distance minimum ainsi que les éléments géométriques concernés. La plupart de ces techniques considèrent des objets convexes. Ces dernières pourront tout de même s'avérer utilisables dans le cadre de simulations faisant intervenir des objets concaves par décomposition de ces derniers en éléments convexes. Un premier procédé permettant la détermination de cette distance minimum et des éléments concernés fût introduit par Gilbert, Johnson et Keerthi. Ce procédé, basé sur la différence de Minkowsky et l'optimisation convexe, permet de déterminer la distance entre deux enveloppes convexes de deux ensembles de points El et £-? et a au pire des cas pour complexité o{(n + mf ) , n et m étant le nombre de points contenus respectivement dans El et E2. Cependant, il est possible d'optimiser ce procédé en se basant sur les résultats obtenus lors des itérations précédentes et ainsi réduire la complexité à o(n) . Ce procédé ne prend pas en compte la nature des objets considérés et l'évolution de leur géométrie. Il est ainsi utilisé au sein de procédés faisant intervenir des objets autres que rigides et convexes. Lin et Canny introduisent un procédé de calcul permettant la détermination, en temps linéaire, des deux points les plus proches de deux maillages non-déformables convexes. Ce procédé est basé sur le concept de cohérence spatiale et temporelle. Le monde virtuel évoluant selon un modèle dynamique, le déplacement d'un objet durant un pas de temps est infinitésimal, ce qui laisse espérer que, à un cycle donné, les points les plus proches appartiennent au voisinage des points les plus proches au cycle précédent. Ce procédé sous-entendant un changement "continu" des zones d'intérêt sur les maillages considérés, il peut être optimisé via une approche multirésolution permettant d'accélérer le "déplacement du calcul" au sein du maillage, telle que celle proposée par Dobkin et Kirkpatrick.
Une deuxième approche prenant en compte une hiérarchie de volumes englobant consiste à partitionner les espaces occupés par les objets composant la scène. Ainsi, chaque objet va être approximé par un volume englobant lui-même décomposé en une arborescence de sous- volumes (généralement de topologie similaire au volume englobant "racine"). La stratégie consiste à effectuer une localisation spatiale des zones susceptibles de s'interpénétrer. En pratique, on teste la présence de chevauchement des volumes englobants d'objets distincts, puis, dans l'hypothèse d'un chevauchement, on effectue un test récursif similaire au niveau des sous-volumes qu'ils contiennent. Cette stratégie permet d'éviter une multitude de tests non-pertinents et se voit très utilisée au sein des moteurs physiques existants. Cependant, ces tests de chevauchement peuvent s'avérer très nombreux dans certains cas (plan/plan par exemple) et ainsi compromettre les performances de la simulation. De plus, la mise à jour de ces volumes (mouvement, déformation) peut s'avérer coûteuse.
Plusieurs types de géométries peuvent être utilisés dans le cadre de cette segmentation de l'espace. Les plus communément utilisés sont les sphères 1, les boîtes englobantes isothétiques 2 (AABB) et les boîtes englobantes orientées 3 (OBB) (voir Figures 4a, 4b, 4c).
Chacun de ces types de volumes englobants se voit plus ou moins adapté en fonction de la géométrie considérée et du niveau de performance escompté. Ainsi, les sphères englobantes ont pour principal avantage la simplicité des tests de chevauchement. En effet, le test de chevauchement de deux sphères se limite à une comparaison entre la distance séparant leur centre et la somme de leurs rayons respectifs. Cependant, les sphères donnent généralement une approximation moins optimale de la géométrie considérée, en comparaison avec les OBBs par exemple qui, malgré des tests de chevauchement beaucoup plus lourds (théorème des axes séparateurs), limitent l'exécution de tests non- pertinents de par un volume englobé minimal.
Architecturalement, les hiérarchies de volumes englobants se présentent sous forme d'arbres, souvent binaires afin d'optimiser leur parcours. On parle également d'Octrees (8 branches / noeud), ou encore de Quadtrees (4 branches / noeud davantage adapté aux géométries 2D). Le volume balayé par un solide en mouvement durant un intervalle de temps correspond à l'union des zones de l'espace qu'il a occupées au cours de cette période. Cet outil géométrique a plusieurs domaines d'application : évaluation d'espace de travail en robotique, modélisation géométrique en CAO. Le volume balayé par une sphère durant une translation est illustré à titre d'exemple sur les Figures 5a et 5b qui illustrent respectivement les positions initiale 4 et finale 5 de l'objet et le volume balayé correspondant 6.
En considérant la cinématique des objets rigides qui évoluent au sein de la simulation à un instant t0 ainsi que leur géométrie, il est envisageable d'évaluer les volumes qu'ils sont susceptibles de balayer à un horizon tn , n>0 , et ainsi anticiper leurs interactions en déterminant les intersections entre leurs volumes balayés respectifs.
Plusieurs procédés sont décrits dans la littérature. On peut citer par exemple les nombreux travaux de K. Abdel-Malek et al. Un procédé particulièrement intéressant est également présenté par Y J. Kim et al. Ce dernier permet d'identifier de manière rapide et robuste le volume balayé par un polyèdre de complexité relativement importante (milliers de facettes). En plus d'une algorithmique sophistiquée, il utilise le matériel ce qui lui permet d'atteindre un niveau de performance très élevé et utilisable dans le cadre d'une simulation temps réel. Les voxels sont parfois utilisés afin de définir de manière discrète une géométrie quelconque. Le principe est d'identifier et englober les zones de l'espace occupées par de la matière à l'aide de cubes de tailles variables en fonction du degré de résolution escompté (voir Figure 6). Les techniques présentées ci-dessus de hiérarchie de volumes englobants et de volumes balayés sont également applicables dans le cadre d'optimisation de ce type d'approche voxélique.
On peut citer en particulier une technique basée sur une discrétisation hybride utilisant des voxels (ou "voxmap") et l'association de nuage de points (ou "point shell") et de normales. Cette technique est illustrée sur les Figures 7a et 7b. La Figure 7a montre un premier objet original 8 représenté sous forme de voxels 8a et un deuxième objet original 9 représenté sous forme de nuage de points et de normales 9a.
La Figure 7b montre le détail d'une interaction entre un voxel 8a d'une surface statique de l'objet 8 et le nuage de points de l'objet 9 avec le plan tangent 9b à la surface statique et le vecteur force 9a selon la normale au nuage de points de l'objet 9.
Cette technique de discrétisation hybride nécessite une phase de pré-calculs relativement longue mais permet de gérer des données géométriques complexes.
Selon une approche analytique, deux autres types de modèles incluent les surfaces implicites et les surfaces paramétriques. Les premières utilisent des fonctions implicites qui définissent des formes dans l'espace. Les surfaces implicites sont l'ensemble des points pour lesquels
Figure imgf000009_0001
0, l'intérieur du modèle étant les points pour lesquels/(χ,>',-:) < 0.
Pour ces deux méthodes de modélisation, résoudre des problèmes de collision revient donc à manipuler ces fonctions. Ces types de définitions géométriques sont très peu utilisées. Les objets quelconques (non-issus de primitives) et complexes se voient en effet très difficilement représentables de cette manière, particulièrement dans le cas de zones saillantes (discontinuité) très présentes dans les pièces mécaniques par exemple.
Une fois les zones d'interpénétration identifiées, il reste à déterminer les forces de contact, soit, en d'autres termes, les efforts de « répulsion » qui vont permettre de ramener les objets interpénétrés à un simple état de contact. Pour ce faire, trois méthodes émergent de la littérature scientifique : la méthode des contraintes, la méthode d'impulsion et la méthode de pénalité. La méthode des contraintes consiste à prendre explicitement en compte les contraintes de non-interpénétration au niveau des équations du mouvement propres à chacun des objets. Cette contrainte s'exprime comme suit : p(t) = /{force) C(P(O) > 0 où la première équation caractérise le mouvement de chaque objet en fonction des efforts qui lui sont appliqués et la deuxième les contraintes de non-interpénétration.
Cette méthode est particulièrement intéressante dans le cas où les collisions ne sont pas très fréquentes (le calcul de collision, soit la détermination de C{ρ(ή, est coûteux) et en l'absence de frottements. Elle a l'avantage de ne pas avoir d'effets néfastes sur la stabilité du système global.
La méthode d'impulsion est une approche cinématique qui assimile l'interaction entre deux objets rigides à un impact. La collision est ainsi considérée comme un événement quasi-instantané générant un effort important (dit impulsion) sur les objets concernés. On a ainsi la relation suivante entre les vitesses avant et après impact :
V0 ≈ -e V1 OÙ e est appelé coefficient de restitution
Figure imgf000010_0002
: collision élastique,
Figure imgf000010_0001
: collision plastique). e est calculable via l'hypothèse de Poisson : e = ^
Lorsque deux objets sont suffisamment proches, l'impulsion est calculée de manière à les séparer en une seule itération. On pose souvent la condition que les objets concernés ont une trajectoire balistique afin d'optimiser les calculs.
La méthode de pénalité permet de gérer les efforts de répulsion entre des objets rigides ou déformables. Elle consiste à appliquer aux objets en collision 14, 15 un effort proportionnel à la profondeur d'interpénétration (on parle de raideur). Le «mécanisme» de répulsion est ainsi souvent assimilé à un système 16 de type proportionnel dérivé (voir Figure 8). Cette méthode nécessite de connaître le vecteur de pénétration (ce qui peut s'avérer coûteux) et génère bien souvent des instabilités (particulièrement dans les cas de collisions multipoints). II ressort de ce qui précède que l'évaluation des distances et l'identification des zones de proximité, et le cas échéant la détection des collisions, entre objets géométriques évoluant au sein d'un environnement numérique, se voit être une étape essentielle dans un grand nombre de disciplines, telles que par exemple la réalité virtuelle ou la scénarisation de déplacements de systèmes robotiques.
Toutefois, notamment du fait de leur coût en terme de temps de calcul, les différents procédés utilisés à ce jour se voient souvent inutilisables dans le cadre de simulations faisant intervenir des géométries complexes et nécessitant de hauts niveaux de performances. La présente invention vise à remédier aux inconvénients de l'art antérieur et à permettre de répondre à la plupart des problématiques récurrentes dans l'évaluation des distances ou l'identification des zones de proximité, et notamment dans la détection de collisions en fournissant des solutions avec des temps de calcul réduits compatibles avec des applications en temps réel, avec un haut degré de performances et une simplicité de mise en œuvre, même lorsque les objets en interaction présentent des géométries complexes ou des natures ou qualités différentes.
Ces buts sont atteints, conformément à l'invention, grâce à un procédé d'identification de zones de proximité entre au moins des premier et deuxième objets simulés numériquement, caractérisé en ce qu'il comprend les étapes suivantes :
(a) on fournit des données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement et on stocke ces données en mémoire,
(b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux- mêmes définis comme des points appartenant respectivement aux géométries de chacun des premier et deuxième objets,
(c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi, (d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session,
(e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre les premier et deuxième objets, on considère uniquement la population des vainqueurs des combats,
(f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et (g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive.
Au cours de l'étape d'extraction des informations géométriques, on peut évaluer les distances entre les zones de proximité identifiées. Les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement peuvent comprendre des représentations polyédriques, des représentations voxéliques, des représentations par surfaces paramétrées ou encore des nuages de points. Selon une caractéristique particulière, le critère d'aptitude permettant d'évaluer la qualité d'un pion est constitué par une mesure de la distance séparant les premier et second nucléons définissant ce pion, la quaiité du pion étant d'autant plus grande que la distance mesurée est plus faible. Cette mesure de la distance peut par exemple prendre en compte le carré de la distance séparant les premier et second nucléons définissant le pion. Le procédé selon l'invention peut en outre comprendre après l'étape (a) de fourniture de données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement, les étapes suivantes :
(al) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de connectivité,
(a2) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de proximité.
Avantageusement, la mutation des pions ayant perdu durant une session du tournoi engendrant des mutations exploratoires pour les pions ayant perdu consiste à déplacer les premier et second nucléons composant un pion sur la surface des premier et deuxième objets auxquels ces premier et second nucléons appartiennent respectivement.
Selon un mode de réalisation particulier, lors de la mutation d'un pion ayant perdu durant une session du tournoi, engendrant des mutations exploratoires pour les pions ayant perdu, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à une succession de déplacements discrets de centre de facette en centre de facette en considérant les informations définissant les propriétés de voisinage stockées en mémoire.
Selon un autre mode de réalisation particulier, lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sur une même facette sur un disque ayant pour centre la position initiale de ce point et pour rayon une amplitude de déplacement maximum qui dépend de l'aire de la facette sur laquelle est effectué le déplacement.
Selon encore un autre mode de réalisation particulier, lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sous forme de "trou de vers" d'un sommet d'une facette vers un autre sommet proche d'une autre facette qui n'est pas nécessairement connexe, en considérant les informations définissant les propriétés de proximité stockées en mémoire. Selon encore un autre mode de réalisation particulier, lors de la mutation d'un pion vainqueur au cours du tournoi, les premier et second nucléons composant ce pion et appartenant respectivement aux premier et deuxième objets représentés chacun sous une forme polyédrique avec des facettes triangulaires, sont positionnés de telle sorte qu'ils délimitent un segment définissant la distance minimum entre les deux facettes triangulaires auxquelles ces premier et second nucléons appartiennent respectivement.
Avantageusement, lors du remplacement d'un pion ayant perdu durant une session du tournoi engendrant pour les pions ayant perdu des remplacements par croisement de pions choisis aléatoirement, pour définir le nouveau pion résultant du croisement d'un premier et d'un deuxième pions choisis aléatoirement, on considère que le nouveau pion se compose du premier nucléon du premier pion choisi aléatoirement et du second nucléon du deuxième pion choisi aléatoirement. L'invention concerne de façon plus générale un procédé appliqué à un ensemble de P objets simulés numériquement avec P>2, caractérisé en ce qu'il comprend les étapes suivantes : (a) on fournit des données décrivant la géométrie de chacun des P objets simulés graphiquement,
(b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux- mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets,
(c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi,
(d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session, (e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre deux des P objets, on considère uniquement la population des vainqueurs des combats,
(f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et
(g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive.
Dans le cas où les données permettant d'identifier des zones de l'espace décrivant la géométrie des P objets simulés numériquement comprennent des représentations polyédriques, le procédé comprend avantageusement les étapes additionnelles suivantes après l'étape (a) de fourniture de données décrivant la géométrie des P objets simulés numériquement :
(al) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de connectivité,
(al) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de proximité.
L'invention a encore pour objet un système d'identification de zones de proximité entre un nombre P d'objets simulés numériquement avec P>2, caractérisé en ce qu'il comprend ;
(a) des premiers moyens de mémoire pour stocker des données décrivant la géométrie de chacun des P objets,
(b) un module d'initialisation pour créer une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux-mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets,
(c) une unité centrale de traitement comprenant au moins :
(cl) des moyens de sélection d'un pourcentage de la population des N pions devant être soumis à des combats par paires au cours d'une session d'un tournoi, (c2) des moyens de comparaison et de calcul pour évaluer au cours d'une session d'un tournoi, pour chaque paire de pions soumis à un combat, la qualité de chacun des pions de la paire de pions à partir d'un critère d'aptitude,
(c3) des moyens de marquage, pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné, et lequel des pions de ladite paire de pions soumis à un combat a perdu,
(c4) des moyens d'itération pour produire une évolution des pions qui ont subi au moins un combat, ces moyens d'itération étant associés au moins à un opérateur de mutation exploratoire des pions ayant perdu pendant une première session du tournoi, à un opérateur de remplacement des pions ayant perdu durant une deuxième session du tournoi par croisement de pions choisis aléatoirement et à un opérateur de redéfinition des pions ayant perdu durant une troisième session du tournoi, et
(c5) un module d'extraction pour ne retenir que les meilleurs pions de la population en fonction du critère d'aptitude, pour la détermination des zones de proximité entre au moins deux des P objets. Le système peut en outre comprendre :
(al) des deuxièmes moyens de mémoire pour stocker des informations représentant une carte de connectivité et définissant les propriétés du voisinage entre éléments géométriques au sein de chacun des P objets, (a2) des troisièmes moyens de mémoire pour stocker des informations représentant une carte de proximité et définissant les propriétés de proximité au sein de chacun des P objets.
L'unité centrale de traitement peut comprendre un ensemble d'unités de calcul fonctionnant en parallèle. Le procédé et le système selon l'invention se fondent ainsi sur un processus évolutionnaire basé sur une approche stochastique. Ce processus évolutionnaire traite de populations d'individus définis par des composantes réelles et non simplement de manière binaire.
D'autres caractéristiques et avantages de l'invention ressortiront de la description suivante de modes particuliers de réalisation, donnés à titre d'exemples non limitatifs, en référence aux dessins annexés, sur lesquels :
- la Figure 1 est un schéma-bloc représentant l'architecture fonctionnelle d'une plate-forme de réalité virtuelle, - la Figure 2 est un organigramme montrant le schéma d'évolution dynamique d'un objet contenu dans le monde virtuel selon les lois de la physique,
- la Figure 3 est un schéma illustrant un procédé connu de calcul de la distance minimale entre deux objets de type polyédrique, - les Figures 4a, 4b et 4c montrent trois exemples d'approximation d'un objet par un volume englobant,
- la Figure 5a illustre des positions initiale et finale d'un objet sphérique en translation,
- la Figure 5b illustre le volume balayé correspondant à la translation de l'objet de la Figure 5a,
- la Figure 6 illustre un exemple de décomposition voxélique d'un objet,
- la Figure 7a montre un exemple de représentation hybride d'un objet sous forme de voxels coopérant avec un autre objet représenté sous la forme d'un nuage de points et de normales,
- la Figure 7b représente le détail d'une zone d'interaction des deux objets représentés de façon hybride sur la Figure 7a,
- la Figure 8 illustre la représentation de deux objets soumis à des efforts de répulsion selon la méthode de pénalité, - la Figure 9 est un schéma illustrant le génotype d'un individu ou pion utilisé dans le cadre de l'invention,
- la Figure 10 illustre un exemple de déplacement exploratoire discret d'un point sur un polyèdre, dans le cadre d'une mutation,
- la Figure 11 montre un exemple d'opérateur d'exploitation intervenant dans le cadre d'une mutation,
- la Figure 12a illustre un processus d'identification des éléments proches dans le cadre d'objets représentés sous une forme polyédrique, - la Figure 12b illustre un exemple de parcours sans trou de vers dans l'objet représenté sur la Figure 12a,
- la Figure 12c illustre un exemple de parcours via un trou de vers dans l'objet représenté sur la Figure 12a, - la Figure 13 illustre le principe du croisement de deux pions,
- la Figure 14 représente les trois phases principales du procédé selon l'invention,
- les Figures 15a, 15b et 15c illustrent trois exemples de configurations géométriques permettant de matérialiser le segment définissant la distance minimum entre deux triangles de représentations polyédriques d'objets, auxquels appartiennent les deux points composant un pion,
- la Figure 16 illustre la projection d'extrémités d'un segment sur un plan contenant un triangle dans le cadre de la détermination du segment définissant la distance minimum entre deux triangles appartenant à des polyèdres représentant deux objets en interaction,
- les Figures 17 et 18 illustrent, dans le cas du processus représenté sur la Figure 16, la détermination d'un segment définissant une distance minimum, respectivement dans le cas point-segment et dans le cas segment-segment,
- la Figure 19 représente le génotype de plusieurs pions définis entre différents polyèdres représentant différents objets,
- la Figure 20 illustre le replacement aléatoire d'un pion dans le cas d'un objet représenté sous forme polyédrique, - la Figure 21 illustre le génotype d'un pion défini entre deux surfaces paramétrées représentant deux objets,
- la Figure 22 illustre le génotype d'un pion défini entre deux nuages de points représentant deux objets,
- la Figure 23 illustre le génotype d'un pion défini entre deux représentations voxéliques d'objets,
- la Figure 24 illustre la fonction d'un opérateur de croisement, - la Figure 25 représente des pions hybrides définis entre des géométries de types différents représentant des objets, et
- la Figure 26 est un schéma-bloc montrant les principaux modules constituant un exemple de système selon l'invention. Le procédé et le système selon l'invention, décrits selon un mode de réalisation particulier, permettent à partir d'objets simulés numériquement, ou objets virtuels, d'identifier, tout au long d'une simulation dynamique en temps réel mettant en scène des représentations géométriques des objets, les zones géométriques susceptibles d'entrer en collision, et cela indépendamment de la complexité géométrique et de la nature (convexité, rigidité) des objets.
Pour ce faire, le procédé selon l'invention fait appel à un processus évolutionnaire. D'une façon générale, il applique une stratégie qui consiste à faire évoluer une population d'individus en utilisant des opérateurs de variation (mutation, croisement) destinés à faire converger cette population vers une configuration optimale.
L'évaluation de la qualité d'un individu se fait grâce à une fonction nommée "fonction d'objectif ("fitness") destinée à mesurer un ou plusieurs critères qualitatifs. Un tel processus évolutionnaire générant de nouveaux individus présente une grande efficacité et une simplicité de mise en œuvre.
Dans un premier temps, le procédé selon l'invention qui applique un processus évolutionnaire à la réalité virtuelle, sera décrit en référence à des objets représentés par des polyèdres, mais l'invention est plus générale et s'applique à des objets quelle que soit leur représentation géométrique.
Comme on l'a déjà indiqué, la stratégie de base du procédé selon l'invention consiste à faire évoluer une population d'individus en utilisant des opérateurs de variation (mutation, croisement) destinés à faire converger la population (ensemble d'individus) vers une configuration optimale. La Figure 9 illustre un exemple de définition du génotype 51 d'un individu (qui par la suite sera également appelé "pion") qui est défini comme une paire de nucléons constitués par des points appartenant respectivement à chacun des deux maillages Objeti et Objet2 représentant les premier et deuxième objets dont on souhaite évaluer la proximité.
Le génotype 51 d'un pion peut ainsi s'exprimer comme :
Figure imgf000021_0001
où les indices Face (entiers non-signés) représentent les identifiant des faces auxquelles appartiennent respectivement les points définissant le pion, a, et βt les coordonnées du point appartenant au premier polyèdre dans la base O1, e2) de la face concernée, et respectivement pour α2 et β2 dans la base(e^,e^) . (O≤α, <\ ,0<βl ≤ι ,α, +βt ≤i).
Le génotype défini ci-dessus est destiné à être utilisé dans le cadre de simulations d'objets de type polyédrique. Il est important de souligner que, de manière plus générique, un pion est simplement défini par deux nucléons appartenant respectivement à deux objets de nature quelconque. Si l'on considère par exemple le cas de surfaces implicites, dans ce cas un pion sera défini par les coordonnées (*,, yx,zx) du premier point et les coordonnées (x2,y2,∑2) άu deuxième. Dans le cas de géométries de type voxélique, les points pourront être définis par l'indice des voxels concernés. Ainsi, la description d'un pion est directement liée au type de géométrie utilisée. Il est par ailleurs possible de définir un pion entre deux géométries de types différents, les coordonnées des points étant systématiquement exprimées dans l'espace cartésien au moment de l'évaluation.
La fonction d'objectif ("fitness") ou critère d'aptitude permettant d'évaluer la qualité d'un pion est constituée par la mesure de la distance séparant les premier et second nucléons définissant ce pion. On peut avantageusement choisir cette mesure comme étant le carré de la distance séparant les deux nucléons qui composent le pion.
Soit (x,, ^15Z1) et (X25^25Z2) les coordonnées cartésiennes respectives des nucléons composant un pion pλ projetées dans un même repère. L'expression de la fitness de cet individu est la suivante : fitness(px ) = (x2 - x, f + (y2 - yx f + (z2 - zx f .
L'utilisation du carré de la norme est avantageuse car la fonction racine carrée est très coûteuse en terme de temps de calcul.
On notera que la qualité Qualité (p) d'un individu ou pion p est inversement proportionnelle à sa fonction d'objectif fitness (p).
La mutation est un opérateur d'évolution qui est définissable comme une variation plus ou moins importante du patrimoine génétique d'un individu.
De façon plus particulière, dans le cadre de la présente invention, faire muter un individu consiste à déplacer les points qui le composent sur la surface des objets auxquels ils appartiennent.
Plusieurs heuristiques de déplacement peuvent être définies dans le cadre de simulations faisant intervenir des polyèdres.
Ainsi avec un exemple d'opérateur d'exploration illustré sur la Figure 10, les points définissant l'individu concerné vont pouvoir se déplacer sur de grandes distances sur la surface des objets. Cet opérateur génère des déplacements discrets de centres 52 de facettes 53 en centres
52 de facettes 53 en considérant la connexité des objets considérés, obtenue à l'aide de cartes de voisinage des polyèdres pré-calculées. L'amplitude de ces déplacements, qui correspond au nombre de sauts effectués durant la mutation, est déterminée de manière aléatoire. Elle est comprise entre 0 et σEψhr , amplitude de déplacement maximum dépendant de la géométrie de l'objet.
La Figure 10 illustre le déplacement exploratoire discret d'un point sur un polyèdre avec une amplitude de huit sauts, mais cette valeur n'est naturellement donnée qu'à titre d'exemple.
Un opérateur d'exploitation qui correspond à un autre type de mutation, illustré sur la Figure 11, est destiné à affiner le positionnement des points qui composent l'individu concerné. Contrairement au cas de la mutation exploratoire, ces déplacements sont définis de manière métrique. Ainsi chaque point va effectuer un déplacement sur un disque de rayon σ FxPio,t i amplitude de déplacement maximum, ayant pour centre la position initiale du point. L'amplitude de déplacement maximum (exprimé en mètres) peut être dépendante de l'aire de la face 56 sur laquelle est effectué le déplacement. Ainsi, cette amplitude est calculée durant la phase de pré-calculs pour chaque facette 56.
Se déplacer sur les faces 61 d'une représentation polyédrique 60 d'un objet en considérant uniquement la connexité (propriétés de voisinage) peut s'avérer restrictif notamment dans le cas d'objets fins ou fortement courbés. Ainsi, selon un autre aspect de l'invention, il est mis en place une deuxième « carte » basée sur la proximité des sommets. Durant la phase de pré-calculs, pour chaque sommet 62, 63 est établie une liste des sommets les plus proches 64, 65. Lorsque l'un des points (63) qui composent le pion en mutation se trouve sur un sommet à l'issue d'un déplacement, il a la possibilité (et non l'obligation) de glisser vers un sommet proche (64) pas obligatoirement connexe. Ce type de déplacement peut être dénommé "trous de vers", en référence aux ponts Einstein-Rosen (passages assimilables à des raccourcis liant des zones distantes au sein d'un univers courbé).
La Figure 12a illustre la représentation polyédrique 60 d'un objet comportant des faces 61.
Selon une carte de proximité, les sommets 64, 65 sont identifiés comme étant les plus proches des sommets 62, 63. La Figure 12b illustre un exemple de parcours 66 sans trou de vers, depuis le sommet 63 jusqu'à un point 67.
La Figure 12c illustre un parcours alternatif utilisant l'opérateur de mutation "trou de vers". Dans ce cas, le parcours depuis le sommet 63 jusqu'au point 67 inclut un passage 68 du type "trou de vers" en dehors de la représentation 60 de l'objet, entre les sommets 63 et 64 identifiés comme étant proches.
Des opérateurs de mutation ayant des fonctions similaires à celles des trois opérateurs décrits ci-dessus peuvent être définis dans le cadre de simulation faisant intervenir d'autres types de géométries.
L'invention met également en œuvre un opérateur de variation, dénommé "croisement", qui est destiné à accélérer la convergence de la population (Figure 13). Le principe est de générer un pion (enfant) en couplant deux pions issus de la population (géniteurs). Le nouveau pion possède ainsi des propriétés génétiques propres à ses deux géniteurs. En pratique, cet opérateur peut être utilisé de la manière suivante : le pion "enfant" a pour nucléon 1 celui du premier géniteur et pour nucléon 2 celui du deuxième.
Le schéma général du procédé selon l'invention est illustré sur la Figure 14, avec une première phase 71 d'initialisation, une deuxième phase 72 de tournoi et une troisième phase 73 d'évolution.
Au cours de la phase 71 d'initialisation, on fournit des données permettant d'identifier des points décrivant la géométrie de chacun des objets simulés graphiquement et on stocke ces données en mémoire. Au cours de cette même phase 71 d'initialisation, on crée également une carte de connectivité contenant des informations définissant les propriétés de voisinage topologique au sein des objets et on stocke en mémoire les informations de cette carte de connectivité.
La phase 71 d'initialisation comprend encore l'établissement d'une carte de proximité contenant des informations définissant les propriétés de proximité (trou de vers) au sein des objets et le stockage en mémoire des informations de cette carte de proximité. Enfin, lors de la phase 71 d'initialisation, on crée une population constituée par un ensemble de N individus (que l'on peut appeler pions) définis chacun par des premier et second nucléons constitués par des points appartenant respectivement aux géométries de deux objets distincts préalablement identifiés.
La phase 72 de tournoi consiste en l'organisation de combats entre individus. Un combat entre deux individus ou pions consiste à évaluer lequel des deux pions s'avère de meilleure qualité, c'est-à-dire à déterminer lequel des deux pions présente une fonction d'objectif (ou critère d'aptitude) "fitness" la plus faible.
Ainsi, lors de la phase 72 de tournoi, on organise des sessions au sein des N pions de la population créée où, durant chacune des sessions, un pourcentage de la population est soumise à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi.
Les différentes sessions de la phase 72 de tournoi peuvent comprendre par exemple une première session Mut% consistant en des combats d'un pourcentage de la population qui engendreront ensuite des mutations, une deuxième session Cross% consistant en des combats d'un pourcentage de la population qui engendreront ensuite des croisements et une troisième session Rand% consistant en des combats d'un pourcentage de la population qui engendreront ensuite des redéfinitions aléatoires.
Les première, deuxième et troisième sessions, Mut%, Cross% et Rand% peuvent avoir lieu dans des ordres quelconques. A l'issue de la phase de tournoi 72, les pions gagnants sont identifiés par un marquage qui est différent de celui des pions perdants. Le marquage des pions diffère également en fonction de la session pendant laquelle ils ont subi un ou plusieurs combats. La phase 73 d'évolution consiste à appliquer les opérateurs de variation précédemment définis à la population en fonction des résultats du tournoi et comprend ainsi la mutation des pions ayant perdu durant la première session Mut% du tournoi, le remplacement des pions ayant perdu durant la deuxième session Cross% du tournoi par croisement de pions choisis aléatoirement, et la redéfinition des pions ayant perdu durant la troisième session Rand% du tournoi. L'exploitation des gagnants des combats qui sont supposés être de bons éléments permet de déterminer des zones de proximité entre deux objets. Le processus est itératif et les phases 72 et 73 peuvent se répéter sans arrêt. Il est possible à chaque instant d'exploiter une configuration améliorée en exploitant les seuls pions alors marqués comme étant gagnants.
Le procédé selon l'invention est peu dépendant de la nature géométrique et de la qualité des objets. Il est utilisable dans le cadre de simulations faisant intervenir tous types de géométries (polyèdres, voxels, surfaces paramétrées, etc..) dès lors que les opérateurs de variation adéquats sont définis. De plus, il permet la mixité des géométries, les points qui composent les pions pouvant évoluer de manière totalement différente à la surface des objets auxquels ils appartiennent respectivement. Le procédé n'est pas sensible aux concavités, les mutations exploratoires et les redéfinitions aléatoires assurant la diversité de la population.
La qualité des objets (orientation des normales, trous,...) n'affecte nullement le fonctionnement du procédé. Ceci est un avantage considérable (les moteurs physiques actuels sont très sensible à la qualité des objets ce qui affecte souvent considérablement leur bon fonctionnement...).
Les durées d'exécution des deuxième et troisième étapes 72, 73 du procédé (tournoi, évolution) ne sont pas dépendantes du nombre d'entités géométriques élémentaires, mais seulement du nombre de pions qui n'est pas dépendant de la complexité géométrique des objets. Dans tous les cas, les pions se voient beaucoup moins nombreux que les entités géométriques élémentaires. Le procédé est donc au total peu dépendant de la complexité géométrique des objets.
Comme on l'a déjà indiqué, un individu ou pion d'une population de N individus se compose de deux points que l'on peut également appeler nucléons.
Il a été décrit plus haut, plus particulièrement dans le cas d'objets représentés de façon polyédrique, un ensemble d'opérateurs d'évolution ou mutateurs destinés à faire évoluer les pions au sein des polyèdres auxquels ils appartiennent. Un autre opérateur permet un positionnement optimal des nucléons constituant l'individu concerné sur les triangles qui les contiennent au sein des représentations d'objets de type polyédrique.
Cet opérateur de mutation permet de minimiser localement de manière exacte, selon une approche déterministe, la fonction d'objectif (fitness) du pion concerné. Cet opérateur de mutation est destiné à être appliqué à l'élite des individus constituant la population. Il est destiné à accélérer la convergence et augmenter la précision des résultats issus de la mise en œuvre du procédé.
Le but de cet opérateur est de positionner les nucléons qui composent le pion concerné de manière à matérialiser le segment définissant la distance minimum entre les deux triangles auxquels ils appartiennent respectivement.
Les Figures 15a, 15b, 15c montrent trois configurations géométriques différentes avec deux triangles 81, 82 ; 83, 84 et 85, 86 respectivement pour lesquels le segment 87 ; 88 ; 89 matérialisant respectivement la distance minimum entre les deux triangles correspond à une interaction sommet/face, sommet/sommet et arête/arête.
Ces différents cas peuvent être pris en compte avec le procédé de détermination décrit ci-dessous. Afin de déterminer en un temps réduit le positionnement optimal des nucléons composant le pion concerné, on décompose le cas triangle/triangle en 6 cas segment/triangle comme exprimé ci-dessous, couvrant ainsi l'ensemble des configurations géométriques précédemment définies.
P11 ((A1. B, AMA B2A)) \
Figure imgf000028_0001
([C2 , B2UA1- BrA)) I
Où yτs, (S, T) et ψn (Tx, T2) déterminent respectivement les segments matérialisant la distance minimum dans les cas segment/triangle et triangle/triangle. La détermination du segment minimum dans le cas segment/triangle se décompose elle-même en deux phases :
- Identification des configurations géométriques possibles et des éléments concernés (segments, points, face).
- Détermination du segment minimum. La première phase consiste à projeter orthogonalement les extrémités du segment sur le plan contenant le triangle. La combinaison des positions de leurs projetés par rapport au triangle va permettre d'identifier les configurations géométriques possibles et les éléments potentiellement concernés. Les positions des projetés par rapport au triangle sont formalisées par leur appartenance à l'une des portions de plan définies par les droites porteuses des côtés du triangle. Par exemple, dans le cas illustré sur la Figure 16, les projetés Pi, Qi des extrémités Pet Q du segment appartiennent respectivement aux zones Z2 et Z4 du plan contenant le triangle (A,B,C). Ainsi il existe 49 combinaisons possibles :
{(Z,,Zy),l ≤ / ≤ 7,l < / ≤ 7} .
Le tableau suivant décrit les paires d'éléments potentiellement porteurs du segment minimum pour chacune des combinaisons où ψss ([Pi Qi], [P2 Q2])/ et ψps (M,[P Q]) déterminent respectivement les segments matérialisant la distance minimum dans les cas segment/segment et point/segment
Figure imgf000029_0001
La deuxième phase va consister à déterminer Ie pion optimal. Ainsi dans cette partie on définit l'ensemble des fonctions précédemment citées.
Le cas point/segment est illustré sur la Figure 17 et correspond à
Ψ Ps (M, [P Q])
Le but est de déterminer le coefficient λ tel que : Λe[0,l],V//e[0,l] (X-PQ)M < (μ- PQ)M^
Après mise en équation :
PW = X-PQ
PQ MM' = 0
on obtient quatre équations pour 4 inconnues :
XM ' ~ Xp ~ "' \X Q ~ Xp )
zM,-zF=X-(zQ-zp)
(χ Q -Xp)- (**• - χu ) + (y Q -yP)- (y M- - yM ) + (zυ - z,>) - (^ - ZM ) = °
d'où l'on déduit :
X = (χ L) -χp)- (χ,> - % ) + (y o -yP)- (y p - y M ) + (% - ZP) • Of - ZM )
(xo - xp f + (yo - y j, f + (zo - zp f
Afin d'assurer l'appartenance de M' à [PQ]1 on sature le coefficient X , c'est-à-dire que : si X < 0, alors on donne à X la valeur 0 si X > 1, alors on donne à f la valeur 1
Le cas segment/segment est illustré sur la Figure 18 et correspond
Le but est de déterminer les coefficients X et μ tels que :
/te[0,l],//e[0,l],V(tf,/?)€[0,l]2, (X-P1Q1)(M-P2Q2) < (a P^)(P-P2Q2)
Après mise en équation :
Figure imgf000031_0001
P2M2= μ P2Q2 P^Q1-M1M2=O
Υ&2-M~M2=0
on obtient huit équations pour 8 inconnues :
y M,- y ι\ =λ<yQï-yp) 2 M1-2 P1 =ά-(z(Jι-zPι) x M2 ~ Xp2 = ^ ' (xo2 ~ XP2 ) y M1 -y P1 = A-(JQ1 -y h)
2 M2-2 P2 = A' (z(Ji-ZPi)
(XQ1 - xn ) - (χM2 -XM1)+ (y Q1 - y P1 ) • (y M2 -yMt)+ (2 Ql - 2n ) • (2M1 - 2M1 ) = ° (XQ2 - χp2 ) • (χM2 - χ M, ) + (y Q2 - y P2 ) • (y M1 - > v, ) + (2Q2 - 2P2 ) - (%2 -2M1) = 0
d'où l'on déduit :
Figure imgf000031_0002
^P1P1 +2O1P1 ' 2P2PX )
Figure imgf000031_0003
afin d'assurer l'appartenance de M1 et M2 respectivement à [R1Q1] et [P2Q2], on sature les coefficients! et μ comme précédemment.
Dans le cas de la simulation numérique d'objets faisant intervenir plusieurs objets mobiles les uns par rapport aux autres, il est possible de créer une population de pions pour chaque paire d'objets. Cette approche peut être retenue dans le cas où le nombre n d'objets est relativement petit, mais peut s'avérer coûteuse en temps de calcul si le nombre n d'objets est très supérieur à 2. L'invention peut être mise en œuvre en utilisant une seule population de N individus ou pions qui s'applique à l'ensemble des géométries représentatives d'objets présentes au sein de la simulation.
Dans ce cas, les pions d'une même population peuvent évoluer non plus seulement sur une des paires de géométries contenues dans la simulation, mais sur l'ensemble des paires de géométries (ou maillages) contenues dans la simulation.
Afin de privilégier les combinaisons pertinentes, on ne prend cependant pas en compte les paires d'objets ne pouvant rentrer en contact, c'est-à-dire en particulier les objets liés rigidement ou très distants.
Si l'on considère le cas polyédrique, le génotype d'un pion s'exprime de la manière suivante, avec MeSh1 et Mesh2 qui représentent l'identification des maillages (polyèdres) des objets auxquels appartiennent les deux points (nucléons) composant un pion :
Mesh,
Face, α, β.
Mesh 2
Face 2 α2
P2
où les indices Mesh et Face (entiers non-signés) représentent respectivement les identifiant des polyèdres et faces auxquelles appartiennent les nucléons définissant le pion, αx et βx les coordonnées du point appartenant au premier polyèdre dans la base (e,,e2) de la face concernée, et respectivement pour a2 et β2 dans la base (e\,e'2) . ( 0 ≤ al ≤ l , 0 ≤ β, ≤ l , al +βl ≤ l ).
Les mutateurs définis précédemment ne sont pas affectés par ce mode de fonctionnement. Les « sauts » inter-géométries des nucléons sont effectués lors de la phase de replacement aléatoire qui couvre l'ensemble de l'espace à parcourir et non plus seulement l'une des géométries.
L'application générale du procédé à une population de N pions Pioni à PiOn4 couvrant fl représentations géométriques Meshi à Mesfi4 d'objets est illustrée sur la Figure 19 pour le cas n = 4 et N = 4.
Les génotypes des quatre pions dans l'exemple de la Figure 19 sont les suivants ;
Pionx
Figure imgf000033_0001
L'invention s'applique aussi bien à des simulations faisant intervenir des géométries polyédriques, qui sont couramment utilisées dans un grand nombre de domaines d'application comme la réalité virtuelle ou l'infographie, qu'à des simulations faisant intervenir des géométries non-polyédriques.
Les génotypes et opérateurs de mutation adaptés à des géométries polyédriques ont déjà été décrits dans les exemples donnés précédemment. On a simplement représenté sur la Figure 20 un exemple de mutateur procédant au replacement aléatoire d'un nucléon 91, 91' sur les facettes d'une structure polyédrique.
On décrira ci-dessous quelques exemples de mise en œuvre de l'invention faisant intervenir des géométries non polyédriques.
La Figure 21 illustre le cas d'objets représentés par des surfaces paramétrées (Bézier, B-Spline,...) appelées "patch".
Dans ce cas, la définition de chacun des nucléons d'un pion inclut l'identifiant Patchi, resp. Patch2 de la surface paramétrée à laquelle il appartient et les coordonnées U1Vi resp U2V2 de ce nucléon au sein de cette surface paramétrée Patchi, resp Patch2 à laquelle il appartient.
Le génotype d'un pion est alors le suivant :
Figure imgf000034_0001
Sur la Figure 21, Mi et M2 sont les expressions mathématiques qui définissent respectivement Patchi et Patch2.
En ce qui concerne les mutateurs utilisés avec des surfaces paramétrées, on peut noter que l'évolution d'un nucléon sur une surface paramétrée va consister à modifier de manière stochastique ses coordonnées au sein de cette dernière (i.e. (w,v) => (w + Δu,v+Δv) ). Ainsi, le choix des valeurs maximum des coefficients de variations Atι et Δv conditionnera le type de mutation (exploration ou exploitation).
Un repositionnement aléatoire d'un nucléon peut être effectué par un changement aléatoire de ses coordonnées. Le cas d'objets représentés sous forme de nuages de points est illustré sur la Figure 22 avec deux représentations d'objets référencés Nuagei et Nuagβ2.
Dans ce cas, pour déterminer le génotype d'un pion, on définit chacun des nucléons par l'identifiant pi resp p2 du point auquel il appartient, de la façon suivante :
Nuage, p,
Nuage 2
Pour ce qui concerne les opérateurs de mutation, l'évolution d'un nucléon au sein d'un nuage de points va consister à lui faire effectuer des sauts vers les points avoisinant celui auquel il appartient. Pour cela, il est nécessaire afin de limiter les temps de calculs de générer en phase de pré-calcul une carte de proximité similaire à celle utilisée dans le cas polyédrique. La mise en place d'un mutateur de replacement aléatoire est triviale. Elle consiste simplement à mettre à jour de manière aléatoire les paramètres px et p2.
La Figure 23 illustre le cas d'objets représentés par des géométries voxéliques dénommées Géométriei et Géométrie2.
Pour définir le génotype d'un pion, dans le cas voxélique, chacun des nucléons est défini par l'identifiant υi resp υ2 du voxel auquel il appartient comme indiqué ci-dessous :
Géométrie v, 1 Géométrie^
Vn
Toutefois, le génotype précédemment défini peut s'avérer inadapté dans certains cas (voxels de tailles différentes ou trop importantes). Il peut alors s'avérer nécessaire d'enrichir ce dernier des coordonnées des nucléons au sein de leur voxel respectif.
Dans le cas voxélique, on peut définir des mutateurs de la façon suivante ; Exploration discrète : Le nucléon se déplace de voxel en voxel à l'aide d'une carte de proximité pré-calculée.
Exploration continue ; Dans le cas où les voxels s'avèrent de taille importante, le nucléon peut se déplacer à la surface du voxel auquel il appartient (variation stochastique de ses coordonnées au sein du voxel).
Exploitation stochastique : Exploration continue d'amplitude restreinte.
Exploitation déterministe : Le segment "matérialisant" la distance minimum entre deux cubes est trivialement déterminable de manière déterministe. L'exploitation déterministe consiste ainsi à minimiser localement un pion au sein d'une paire de voxels.
Replacement aléatoire : Choix aléatoire de nouveaux voxels.
On notera que l'opérateur de croisement précédemment défini en référence à des géométries polyédriques s'avère également parfaitement adapté à l'ensemble des génotypes proposés avec des représentations sous la forme de surfaces paramétrées, nuages de points ou voxels.
La Figure 24 représente dans sa généralité l'opérateur de croisement pour produire à partir de deux pions Géniteuri et Géniteur un pion Enfant composé du premier nucléon Nucléoni du pion Géniteur! et du deuxième nucléon Nucléon2 du pion Géniteur2.
Les génotypes et mutateurs qui viennent d'être définis se présentent comme des formalismes adaptés à la définition et l'évolution de nucléons au sein des différents types de géométries choisis.
On peut cependant noter que dans le cadre de la mise en œuvre du procédé, l'évaluation de la qualité d'un pion se ramène à l'évaluation de la distance euclidienne séparant les nucléons qui le composent.
Par suite, il est tout à fait possible de faire intervenir au sein d'une même simulation des géométries de types différents et de prendre en considération des pions hybrides constitués de nucléons de natures différentes, comme illustré sur la Figure 25 où, à titre d'exemple, on voit une représentation polyédrique "Mesh" d'un premier objet, une représentation sous forme de nuage de points "Nuage" d'un second objet, une représentation voxélique "Vox" d'un troisième objet et une représentation sous forme de surface paramétrée "Patch" d'un quatrième objet, avec un premier pion Pioni dont les nucléons appartiennent aux représentations géométriques "Vox" et "Patch", un deuxième pion PiOn2 dont les nucléons appartiennent aux représentations géométriques "Patch" et "Nuage" et un troisième pion P3 dont les nucléons appartiennent aux représentations géométriques "Mesh" et "Nuage", ce qui se traduit pour ces trois pions par les génotypes suivants :
Pion,
Figure imgf000038_0001
La Figure 26 montre sous forme de schéma-bloc un exemple de système d'identification de zones de proximités entre un nombre P d'objets simulés graphiquement, avec P>2, conformément à l'invention.
Ce système comprend une unité de mémoire 110 avec au moins des zones de mémoire 111, 112, 113.
Une première zone de mémoire 111 permet de stocker des données décrivant la géométrie de chacun des P objets simulés graphiquement.
Une deuxième zone de mémoire 112 permet de stocker des informations représentant une carte de connectivité et définissant les propriétés du voisinage au sein de chacun des P objets.
Une troisième zone de mémoire 113 permet de stocker des informations représentant une carte de proximité et définissant les propriétés de proximité au sein de chacun des P objets. Un module d'initialisation 120 permet de créer une population constituée par un ensemble de N pions définis chacun par des premier et second points ou nucléons appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets. Un écran de visualisation 130 permet, si on le souhaite, de visualiser les P objets simulés numériquement.
Une unité centrale de traitement 140 comprend au moins les sous- ensembles 141 à 145 suivants ;
- des moyens 141 de sélection d'un pourcentage de la population des N pions devant être soumis à des combats par paires au cours d'une session d'un tournoi,
- des moyens de comparaison et de calcul 142 pour évaluer au cours d'une session d'un tournoi, pour chaque paire de pions soumis à un combat, la qualité de chacun des pions de la paire de pions à partir d'un critère d'aptitude,
- des moyens de marquage 143, pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné, et lequel des pions de ladite paire de pions soumis à un combat a perdu, - des moyens d'itération 144 pour produire une évolution des pions qui ont subi au moins un combat,
- un module d'extraction 145 pour ne retenir que les meilleurs pions de la population en fonction du critère d'aptitude, pour la détermination des zones de proximité entre au moins deux des P objets. Les moyens d'itération 144 sont associés au moins à un opérateur de mutation exploratoire des pions ayant perdu pendant une première session du tournoi, à un opérateur de remplacement des pions ayant perdu durant une deuxième session du tournoi par croisement de pions choisis aléatoirement et à un opérateur de redéfinition des pions ayant perdu durant une troisième session du tournoi.
La référence 150 désigne une interface optionnelle telle qu'une interface haptique permettant d'exploiter les pions sélectionnés et retenus au cours de l'exécution répétitive des tournois et du processus évolutionnaire.
On notera que l'invention évite les phases de tri qui sont coûteuses en temps et, de par l'indépendance du traitement des individus, autorise un processus qui est fortement parallélisable avec une possibilité de répartition des calculs sur plusieurs microprocesseurs ou microcontrôleurs, ainsi que pour chaque nucléon d'un pion la possibilité de passer d'un type de géométrie d'objet à un autre, ce qui donne une grande souplesse de fonctionnement. Les populations d'individus peuvent comprendre par exemple quelques centaines d'individus.

Claims

REVENPICATÏONS
1. Procédé d'identification de zones de proximité entre au moins des premier et deuxième objets simulés numériquement, caractérisé en ce qu'il comprend les étapes suivantes :
(a) on fournit des données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement et on stocke ces données en mémoire,
(b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux- mêmes définis comme des points appartenant respectivement aux géométries de chacun des premier et deuxième objets,
(c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi, (d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session,
(e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre les premier et deuxième objets, on considère uniquement la population des vainqueurs des combats,
(f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et (g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive.
2. Procédé selon la revendication 1, caractérisé en ce que au cours de l'étape d'extraction des informations géométriques, on évalue les distances entre les zones de proximité identifiées.
3. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des représentations polyédriques.
4. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des représentations voxéliques.
5. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des représentations par surfaces paramétrées.
6. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie d'au moins l'un des premier et deuxième objets simulés numériquement comprennent des nuages de points.
7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que le critère d'aptitude permettant d'évaluer la qualité d'un pion est constitué par une mesure de la distance séparant les premier et second nucléons définissant ce pion, la qualité du pion étant d'autant plus grande que la distance mesurée est plus faible.
8. Procédé selon la revendication 7, caractérisé en ce que la mesure de la distance constituant le critère d'aptitude permettant d'évaluer la qualité d'un pion prend en compte le carré de la distance séparant les premier et second nucléons définissant ce pion.
9. Procédé selon la revendication 1, caractérisé en ce qu'il comprend en outre après l'étape (a) de fourniture de données décrivant la géométrie de chacun des premier et deuxième objets simulés numériquement, les étapes suivantes :
(al) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de connectivité,
(a2) on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein des premier et deuxième objets et on stocke en mémoire les informations de cette carte de proximité.
10. Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que la mutation des pions ayant perdu durant une session du tournoi engendrant des mutations exploratoires pour les pions ayant perdu, consiste à déplacer les premier et second nucléons composant un pion sur la surface des premier et deuxième objets auxquels ces premier et second nucléons appartiennent respectivement.
11. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion ayant perdu durant une session du tournoi, engendrant des mutations exploratoires pour les pions ayant perdu, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à une succession de déplacements discrets de centre de facette en centre de facette en considérant les informations définissant les propriétés de voisinage stockées en mémoire.
12. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sur une même facette sur un disque ayant pour centre la position initiale de ce point et pour rayon une amplitude de déplacement maximum qui dépend de l'aire de la facette sur laquelle est effectué le déplacement.
13. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion vainqueur au cours du tournoi, au moins l'un des premier et second nucléons composant ce pion et appartenant à l'un des premier et deuxième objets représentés sous une forme polyédrique est soumis à un déplacement sous forme de "trou de vers" d'un sommet d'une facette vers un autre sommet proche d'une autre facette qui n'est pas nécessairement connexe, en considérant les informations définissant les propriétés de proximité stockées en mémoire.
14. Procédé selon les revendications 3, 9 et 10, caractérisé en ce que lors de la mutation d'un pion vainqueur au cours du tournoi, les premier et second nucléons composant ce pion et appartenant respectivement aux premier et deuxième objets représentés chacun sous une forme polyédrique avec des facettes triangulaires, sont positionnés de telle sorte qu'ils délimitent un segment définissant la distance minimum entre les deux facettes triangulaires auxquelles ces premier et second nucléons appartiennent respectivement.
15. Procédé selon la revendication 1, caractérisé en ce que lors du remplacement d'un pion ayant perdu durant une session du tournoi engendrant pour les pions ayant perdu des remplacements par croisement de pions choisis aléatoirement, pour définir le nouveau pion résultant du croisement d'un premier et d'un deuxième pions choisis aléatoirement, on considère que le nouveau pion se compose du premier nucléon du premier pion choisi aléatoirement et du second nucléon du deuxième pion choisi aléatoirement.
16. Procédé selon l'une quelconque des revendications 1 à 15, appliqué à un ensemble de P objets simulés numériquement avec P>2, caractérisé en ce qu'il comprend les étapes suivantes :
(a) on fournit des données décrivant la géométrie de chacun des P objets simulés graphiquement,
(b) on crée une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux- mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets,
(c) on organise des sessions d'un tournoi au sein des N pions de la population créée, où durant chacune des sessions un pourcentage de la population est soumis à des combats au cours desquels on évalue pour chaque paire de pions soumis à un combat, en fonction d'une évaluation de la qualité définie à partir d'un critère d'aptitude, lequel a gagné et lequel a perdu et on identifie le gagnant et le perdant par un marquage qui est différent à l'issue de chaque session du tournoi,
(d) après le tournoi, on procède à une mutation exploratoire des pions ayant perdu durant une première session, on procède à un remplacement des pions ayant perdu durant une deuxième session, par croisement de pions choisis aléatoirement et on procède à une redéfinition aléatoire des pions ayant perdu durant une troisième session, (e) pour l'exploitation des pions devant servir à déterminer des zones de proximité entre deux des P objets simulés numériquement, on considère uniquement la population des vainqueurs des combats,
(f) on exécute à nouveau les étapes (c), (d) et (e) de façon répétitive, et (g) on extrait à la demande des informations géométriques à partir d'une configuration actualisée de la population de pions, durant l'exécution répétitive,
17. Procédé selon la revendication 16, caractérisé en ce que les données permettant d'identifier des zones de l'espace décrivant la géométrie des P objets simulés numériquement comprennent des représentations polyédriques, et en ce que le procédé comprend en outre, après l'étape (a) de fourniture de données décrivant la géométrie des P objets simulés numériquement, les étapes suivantes :
(al) on crée une carte de connectivité contenant des informations définissant les propriétés de voisinage entre éléments géométriques au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de connectivité, (a2)on crée une carte de proximité contenant des informations définissant les propriétés de proximité au sein de chacun des P objets et on stocke en mémoire les informations de cette carte de proximité.
18. Système d'identification de zones de proximité entre un nombre P d'objets simulés numériquement avec P>2, caractérisé en ce qu'il comprend :
(a) des premiers moyens de mémoire (111) pour stocker des données décrivant la géométrie de chacun des P objets,
(b) un module d'initialisation (120) pour créer une population constituée par un ensemble de N individus appelés pions définis chacun par des premier et second nucléons eux-mêmes définis comme des points appartenant respectivement aux géométries de l'un des P objets et d'un autre des P objets,
(c) une unité centrale de traitement (140) comprenant au moins : (cl) des moyens (141) de sélection d'un pourcentage de la population des N pions devant être soumis à des combats par paires au cours d'une session d'un tournoi,
(c2) des moyens de comparaison et de calcul (142) pour évaluer au cours d'une session d'un tournoi, pour chaque paire de pions soumis à un combat, la qualité de chacun des pions de la paire de pions à partir d'un critère d'aptitude,
(c3) des moyens de marquage (143) pour identifier à chaque session du tournoi lequel des pions d'une paire de pions soumis à un combat a gagné, et lequel des pions de ladite paire de pions soumis à un combat a perdu,
(c4) des moyens d'itération (144) pour produire une évolution des pions qui ont subi au moins un combat, ces moyens d'itération (144) étant associés au moins à un opérateur de mutation exploratoire des pions ayant perdu pendant une première session du tournoi, à un opérateur de remplacement des pions ayant perdu durant une deuxième session du tournoi par croisement de pions choisis aléatoirement et à un opérateur de redéfinition des pions ayant perdu durant une troisième session du tournoi, et (c5) un module d'extraction (145) pour ne retenir que les meilleurs pions de la population en fonction du critère d'aptitude, pour la détermination des zones de proximité entre au moins deux des P objets.
19. Système selon la revendication 18, caractérisé en ce qu'il comprend en outre
(al) des deuxièmes moyens de mémoire (112) pour stocker des informations représentant une carte de connectivité et définissant les propriétés du voisinage entre éléments géométriques au sein de chacun des P objets, (a2) des troisièmes moyens de mémoire (113) pour stocker des informations représentant une carte de proximité et définissant les propriétés de proximité au sein de chacun des P objets.
20. Système selon l'une quelconque des revendications 18 et 19, caractérisé en ce qu'il comprend en outre un écran de visualisation (130) pour visualiser les objets simulés numériquement.
21. Système selon la revendication 20, caractérisé en ce qu'il comprend en outre une interface haptique (150).
22. Système selon l'une quelconque des revendications 18 à 21, caractérisé en ce que l'unité centrale de traitement (140) comprend un ensemble d'unités de calcul fonctionnant en parallèle.
PCT/FR2005/050597 2004-07-22 2005-07-20 Procede et systeme d'identification de zones de proximite entre plusieurs objets geometriques simules numeriquement WO2006018570A2 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
EP05792025A EP1779306A2 (fr) 2004-07-22 2005-07-20 Procede et systeme d'identification de zones de proximite entre plusieurs objets geometriques simules numeriquement
JP2007521997A JP4829885B2 (ja) 2004-07-22 2005-07-20 いくつかのデジタルシミュレーション化幾何学的オブジェクト間で近接領域を同定する方法およびシステム
US11/658,125 US7774180B2 (en) 2004-07-22 2005-07-20 Method and system for identifying proximity areas between several digitally simulated geometrical objects

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0408114 2004-07-22
FR0408114A FR2873472B1 (fr) 2004-07-22 2004-07-22 Procede et systeme d'identification de zones de proximite entre plusieurs objets geometriques simules numeriquement

Publications (2)

Publication Number Publication Date
WO2006018570A2 true WO2006018570A2 (fr) 2006-02-23
WO2006018570A3 WO2006018570A3 (fr) 2006-03-30

Family

ID=34948231

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2005/050597 WO2006018570A2 (fr) 2004-07-22 2005-07-20 Procede et systeme d'identification de zones de proximite entre plusieurs objets geometriques simules numeriquement

Country Status (5)

Country Link
US (1) US7774180B2 (fr)
EP (1) EP1779306A2 (fr)
JP (1) JP4829885B2 (fr)
FR (1) FR2873472B1 (fr)
WO (1) WO2006018570A2 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE102006055958A1 (de) * 2006-11-24 2008-05-29 Siemens Ag Verfahren und Vorrichtung zum Speichern bzw. Darstellen von vorgegebenen geometrischen Objekten und Computerprogrammprodukt
US10822687B2 (en) 2016-02-29 2020-11-03 General Electric Company Environmental barrier coating and methods of preparation

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8669977B2 (en) 2009-10-01 2014-03-11 Intel Corporation Hierarchical mesh quantization that facilitates efficient ray tracing
JP5852384B2 (ja) * 2010-09-27 2016-02-03 啓史 登尾 物体間接触相互作用模擬装置
US8810598B2 (en) 2011-04-08 2014-08-19 Nant Holdings Ip, Llc Interference based augmented reality hosting platforms
JP2015501984A (ja) 2011-11-21 2015-01-19 ナント ホールディングス アイピー，エルエルシー 加入請求書サービス、システムおよび方法
US9582516B2 (en) 2013-10-17 2017-02-28 Nant Holdings Ip, Llc Wide area augmented reality location-based services
CN105488851B (zh) * 2015-11-30 2017-07-07 腾讯科技（深圳）有限公司 实时虚拟场景中碰撞体之间碰撞探测的方法和装置
EP3822920A1 (fr) 2019-11-18 2021-05-19 Dassault Systèmes Procédés pour localiser un objet modélisé numériquement par rapport à un espace modélisé numériquement et pour réaliser des requêtes volumétriques

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3401897B2 (ja) * 1994-02-16 2003-04-28 株式会社セガ 衝突判定処理システムおよびこれを用いた画像処理装置
CA2248909A1 (fr) * 1996-03-15 1997-09-25 Zapa Digital Arts Ltd. Objets graphiques informatiques programmables
US7196702B1 (en) * 1998-07-23 2007-03-27 Freedesign, Inc. Geometric design and modeling system using control geometry
DE19854011A1 (de) * 1998-11-12 2000-05-25 Knoll Alois Einrichtung und Verfahren zum Vermessen von Mechanismen und ihrer Stellung
JP2002063587A (ja) * 2000-08-17 2002-02-28 Sony Corp 情報処理装置および方法、並びに記録媒体
US7200270B2 (en) * 2001-12-13 2007-04-03 Kabushiki Kaisha Toshiba Pattern recognition apparatus and method using distributed model representation of partial images
US7092110B2 (en) * 2002-07-25 2006-08-15 Timbre Technologies, Inc. Optimized model and parameter selection for optical metrology
US7030875B2 (en) * 2002-09-04 2006-04-18 Honda Motor Company Ltd. Environmental reasoning using geometric data structure

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
ELSHAMLI A ET AL: "Genetic algorithm for dynamic path planning" ELECTRICAL AND COMPUTER ENGINEERING, 2004. CANADIAN CONFERENCE ON NIAGARA FALLS, ONT., CANADA 2-5 MAY 2004, PISCATAWAY, NJ, USA,IEEE, US, 2 mai 2004 (2004-05-02), pages 677-680Vol2, XP010733537 ISBN: 0-7803-8253-6 *
LACY, M.: "An Introduction to Genetic Algorithms In Java"[Online] 1 mars 2001 (2001-03-01), pages 1-6, XP002324703 Extrait de l'Internet: URL:http://sys-con.com/story/?storyid=36224&de=1> [extrait le 2005-04-12] *
TOOGOOD R ET AL: "Robot path planning using genetic algorithms" SYSTEMS, MAN AND CYBERNETICS, 1995. INTELLIGENT SYSTEMS FOR THE 21ST CENTURY., IEEE INTERNATIONAL CONFERENCE ON VANCOUVER, BC, CANADA 22-25 OCT. 1995, NEW YORK, NY, USA,IEEE, US, vol. 1, 22 octobre 1995 (1995-10-22), pages 489-494, XP010194305 ISBN: 0-7803-2559-1 *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE102006055958A1 (de) * 2006-11-24 2008-05-29 Siemens Ag Verfahren und Vorrichtung zum Speichern bzw. Darstellen von vorgegebenen geometrischen Objekten und Computerprogrammprodukt
US8417454B2 (en) 2006-11-24 2013-04-09 Continental Automotive Gmbh Method and apparatus for storing or displaying prespecified geometric objects and computer program product
US10822687B2 (en) 2016-02-29 2020-11-03 General Electric Company Environmental barrier coating and methods of preparation

Also Published As

Publication number Publication date
WO2006018570A3 (fr) 2006-03-30
JP4829885B2 (ja) 2011-12-07
EP1779306A2 (fr) 2007-05-02
US20080319718A1 (en) 2008-12-25
FR2873472A1 (fr) 2006-01-27
FR2873472B1 (fr) 2007-02-09
JP2008507056A (ja) 2008-03-06
US7774180B2 (en) 2010-08-10

Similar Documents

Publication Publication Date Title
Firman et al. Structured prediction of unobserved voxels from a single depth image
Jain et al. Autoencoders for level generation, repair, and recognition
EP3292541B1 (fr) Procede des simplification de modele de geometrie
US11100710B2 (en) Extracting a feature tree from a mesh
Weller New geometric data structures for collision detection and haptics
Pediredla et al. Ellipsoidal path connections for time-gated rendering
Dickinson et al. Panel report: The potential of geons for generic 3-d object recognition
US20210383172A1 (en) Three-dimensional map inconsistency detection using neural network
Hegeman et al. Particle-based fluid simulation on the GPU
WO2021025761A1 (fr) Système de simulation de données de sous-pixels
WO2006018570A2 (fr) Procede et systeme d&#39;identification de zones de proximite entre plusieurs objets geometriques simules numeriquement
Sagardia et al. A new fast and robust collision detection and force computation algorithm applied to the physics engine bullet: Method, integration, and evaluation
Leistner et al. Towards multimodal depth estimation from light fields
CN117078809A (zh) 基于图像的动效生成方法、装置、设备和存储介质
Dick et al. A Bayesian estimation of building shape using MCMC
Džijan et al. Towards fully synthetic training of 3D indoor object detectors: Ablation study
Kutzias et al. Recent advances in procedural generation of buildings: From diversity to integration
Song et al. Inferring 3d shapes of unknown rigid objects in clutter through inverse physics reasoning
EP1794718A2 (fr) Procede de compression de donnees de visibilite, systeme de compression et decodeur
Tsirikoglou Synthetic data for visual machine learning: A data-centric approach
Díaz-Más et al. An octree-based method for shape from inconsistent silhouettes
Nunes Procedural generation of synthetic forest environments to train machine learning algorithms
Alcorn et al. Paved2Paradise: Cost-Effective and Scalable LiDAR Simulation by Factoring the Real World
GKIOULEKAS Ellipsoidal Path Connections for Time-Gated Rendering
FR3112412A1 (fr) Procédé de génération d’une maquette numérique

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

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

AL Designated countries for regional patents

Kind code of ref document: A2

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

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

Ref document number: 2007521997

Country of ref document: JP

NENP Non-entry into the national phase

Ref country code: DE

REEP Request for entry into the european phase

Ref document number: 2005792025

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2005792025

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2005792025

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11658125

Country of ref document: US

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载