Modeling object interactions and facial expressions

• US 20040095352A1
• Filed: 10/06/2003
• Published: 05/20/2004
• Est. Priority Date: 11/27/2000
• Status: Active Grant

• Current Assignee: Dean Huang
• Original Assignee: Dean Huang
• Inventors: Huang, Ding
• Granted Patent: US 8,988,419 B2
• Time in Patent Office: Days
• US Class Current: 345/473
• CPC Class Codes: G06T 13/40 of characters, e.g. humans, animals or virtual beings
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics

Abstract

A method of using parametrical representations in modeling and animation is disclosed. This method is built directly on the inherent properties of parametric curves. Parametric curves are constructed and associated with geometric models, while at the same time the properties are used to represent the underlying mechanism of deformation. This method includes the steps of building parametrical representations on a geometric model, associating vertices of the model with different ones of the parametrical representations to effect movement thereof, and animating movement of the vertices to simulate relative motion therebetween.

The invention discloses a method in which simulation of object interaction and object deformation can be integrated into a unified framework through skeletal trees. The method preprocesses a graphic object and segments the object into a number of contexts at surface slope and curvature discontinuities. Then, control points are generated to represent these contexts. Based on these control points, a skeletal tree of the object can be built. Assisted by spatial decomposition, the skeletal trees can be directly used in the simulation of object interaction.

Claims

1. A method of context based skeletal tree generation for use in animation and simulation of object interactions, said method comprising the steps of preprocessing graphic objects, segmenting processed graphic objects into a plurality of contexts at surface slope and curvature discontinuities, generating control points to represent said contexts, building a volumetric skeletal representation from said control points, and wherein said volumetric skeletal representation is manipulated to facilitate animation and simulation of object interactions.

2. The method according to claim 1, wherein the volumetric skeletal representation is in one form a skeletal tree and the means to generate the skeletal tree includes both bottom-up and top-down.

3. The method according to claims 1 or 2, wherein rule based fuzzy logic is used to generate said control points.

4. The method according to cany one of claims 1 to 3, wherein the step of segmenting preprocessed graphic objects into a plurality of contexts, includes edge detection, edge tracking and curvature discontinuity detection.

5. The method according to claim 4, wherein said edge detection is accomplished by using gradient or Laplacian operators, said edge tracking by using omnidirectional tracking, and curvature discontinuity detection is accomplished by measuring the k-slope and k-curvature and comparing them to predetermined threshold values.

6. The method according to claim 5, wherein the threshold values and kare Application dependent, the value of k being set to 5 to 10 for images of various sizes.

7. The method according to claim 6, wherein the absolute value for threshold of k-curvature (C¹) is set to 10 degrees;

the absolute value for threshold of the change in k-slope (C⁰) between neighboring pixels being set to 20 degrees.

8. The method according to claim 5, including the steps of providing data structures representing contexts of the segmenting process, said data structures having a queue containing x-y co-ordinates and/or chain code values of context points and pointers to neighbouring contexts.

9. The method according to claim 6, including the steps of applying context dimension estimation and/or resegmentation.

10. The method according to claim 7, wherein the step of applying context dimension estimation is accomplished by scanning the context both horizontally and vertically, constructing a run-length histogram which gives the occurrence of length of different runs within the context, the dimension of the context being the run-length corresponding to the maximum value of the histogram.

11. The method according to claim 10, further including the steps of comparing dimensions of different contexts and selecting a standard dimension, and using the standard dimension as aparameter to re-segment.

12. The method according to claim 11, wherein the step of applying fuzzy logic includes the step of providing a quadtree or octree to represent the object for space efficiency.

13. The method according to any one of the preceeding claims wherein there are two types of threads, one type runs at a general level, which roughly tests if objects will collide, the other type runs at a detailed level, which accurately and in time checks the interactions of objects and a general level thread can spawn a detailed level thread whenever necessary.

14. The method according to claim 13, wherein if multiple objects are involved, the scheduling scheme of multiple objects can be built on the top, wherein the objects are individually modeled in their local coordinate system and skeletal trees are set up for them respectively, and in the course of their movement, their control points are queried by a general level thread to check if there will be a collision.

15. The method according to claim 14, wherein the general level thread maps variables in individual local coordinate systems to a world coordinate system, and take account of object orientation, relative moving directions, a search is initialized from the root of a skeletal tree, towards those control points that are closer to another object in space, and if the general level thread conservatively determines, that the contexts where one pair of control points are situated, may collide at some time, then a new detailed level thread can be spawned to carry out accurate detection, and pass the pair of control points to this detailed level thread.

16. The method according to claim 15, wherein the hierarchical depth in the skeletal tree where a general level thread spawns a detailed level thread can vary, and depending on the objects and the task-sharing requirements, it can be a user defined control point, or a context level control point, or a sub-division level control point.

17. The method according to claim 16, wherein for context level tree nodes, the triggering condition for detailed level threads can be that, if the distance between the control points is less than 1.5 times the sum of the context dimensions, which have been calculated during the segmentation process.

18. The method according to claim 17 wherein the detailed level thread can use either a passive or an active method to detect collision, in a passive method, for each skeletal tree node in skeletal subtrees where control points are situated, from its coordinates, the quadtree or octree node which contains the skeletal tree node can be found whereby the passive method then translates the positions of terminal quadtree nodes branched from the nodes just determined to a world coordinate system and check if there is any overlay or collision, if the terminal nodes of quadtrees or octrees, which are being checked, have only been subdivided into larger dimensions (length, height and width), they can be further subdivided by the detail level thread at run time, wherein in an active method, wave fronts resembling context surfaces are pre-sent along the objects'"'"' movement directions, again in a world coordinate system, thus predicting contact point and time, the wave fronts are constructed as parametric surfaces if available, or they can use the node comparison approach as in the passive method.

19. The method according to claim 18, wherein for collision response, the skeletal tree can be conveniently used in the analytical simulation and the animation afterwards, after calculating for deformation, the coordinates associated with the relevant nodes in the skeletal tree will be updated. Then, the skeletal tree can be used to guide the update of the quadtree (octree) representing objects, and the movement of nearby elements, such as other tree nodes of the quadtree (octree), can be interpolated. If an object is properly segmented and subdivided, and the nodes in the skeletal tree represent the object in sufficient details, the updated quadtree (octree) will faithfully represent the object after the update.

20. The method according to claim 19, wherein the event driven methods are used in general level and detailed level threads to speed up processing.

21. The method according to claim 20, wherein usage of multithreads is to increase responsiveness and efficiently use system resources for interaction modeling without conflicting with the main tasks.

22. A method to use a volumetric skeletal representation representing an object for interaction detection and response, wherein nodes are searched for detection and position of nodes are updated for response, said representations being generated either bottom-up or top-down or both.

23. The method according to claim 22, wherein the skeletal representations include a tree and he nodes includes treenodes.

24. The method according to claim 23, wherein the method to generate the skeletal tree includes context-based approach, fuzzy rule approach, automation in processing.

25. The method according to claim 24, wherein the use of trees in tree/concurrent computing in detecting interactions includes multithreads.

26. The method according to claim 25, wherein collision locations and time are predicted and he skeletal trees are updated in interaction in response for continuous stimulation.

27. The method according to claim 26, wherein the method includes an active method which dynamically generates the tree in greater detail in prospective locations of the collision.

28. A method of using parametrical representation to control and represent surface deformation to simulate movement in animation, said method including the steps of building parametrical representations to represent vertices in the topography of the surface, associating said vertices with different ones of the parametrical representations to effect movement thereof, and animating movement of the vertices to simulate relative motion therebetween.

29. The method according to claim 28, wherein said method is used to animate facial expression, whereby the vertices in the topography of the surface are assigned to various portions of facial anatomy including muscles.

30. The method according to claim 29, wherein the parametrical representations are weighted to differentiate the different portions of the facial anatomy.

31. The method according to claim 30, wherein weighting parameter is changed to simulate facial expressions.

32. The method according to claims 28 to 31, wherein the parametrical representations are NURBS curves.

33. The method according to claim 32, wherein position of the NURBS curves are predetermined by the location where simulated muscles are attached to facial bone, each NURBS curve having at least one control point.

34. The method according to claim 33, wherein fuzzy logic is used to determine the association of vertices with NURBS curves.

35. The method according to claim 34, wherein the weights of the NURBS curves are variable to modify the NURBS curves.

36. The method according to any one of claims 28 to 35, wherein the parametrical represntations and/or their changes are sent to a remote location via a communication link to generate deformation at remote location.

37. A method of using parametrical representation to control and represent surface deformation to simulate movement in animation, said method including the steps of building parametrical representations to represent vertices in the topography of the surface, associating said vertices with different ones of the parametrical representations to effect movement thereof, and animating movement of the vertices to simulate relative motion therebetween whereby quantitative simulation is achieved.

38. The method according to claim 37, wherein the parametrical representation/vector analysis, parametrical representation/physical based methods. Parametrical representation/vector analysis/physical based methods are combined