research-article

Achieving good connectivity in motion graphs

Authors:

Alla SafonovaAuthors Info & Claims

SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 127 - 136

Published: 07 July 2008 Publication History

Abstract

Motion graphs provide users with a simple yet powerful way to synthesize human motions. While motion graph-based synthesis has been widely successful, the quality of the generated motion depends largely on the connectivity of the graph and the quality of transitions in it. However, achieving both of these criteria simultaneously in motion graphs is difficult. Good connectivity requires transitions between less similar poses, while good motion quality results only when transitions happen between very similar poses. This paper introduces a new method for building motion graphs. The method first builds a set of interpolated motion clips, which contain many more similar poses than the original dataset. Using this set, the method then constructs a motion graph and reduces its size by minimizing the number of interpolated poses present in the graph. The outcome of the algorithm is a motion graph called a well-connected motion graph with very good connectivity and only smooth transitions. Our experimental results show that well-connected motion graphs outperform standard motion graphs across a number of measures, result in very good motion quality, allow for high responsiveness when used for interactive control, and even do not require post-processing of the synthesized motions.

References

[1]

{AF02} Arikan O., Forsyth D. A.: Interactive motion generation from examples. ACM Trans. on Graphics 21, 3 (2002), 483--490.

Digital Library

[2]

{AFO03} Arikan O., Forsyth D. A., O'Brien J. F.: Motion synthesis from annotations. ACM Trans. on Graphics 22, 3 (2003).

Digital Library

[3]

{BEL57} Bellman R.: Dynamic Programming. Princeton University Press, 1957.

Digital Library

[4]

{CB06} Callennec B. L., Boulic R.: Robust kinematic constraint detection for motion data. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (2006), pp. 281--290.

Digital Library

[5]

{FP03} Fang A. C., Pollard N. S.: Efficient synthesis of physically valid human motion. ACM Trans. on Graphics 22, 3 (2003), 417--426.

Digital Library

[6]

{GSKJ03} Gleicher M., Shin H., Kovar L., Jepsen A.: Snap-together motion: Assembling run-time animation. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (2003), pp. 181--188.

Digital Library

[7]

{HG07} Heck R., Gleicher M.: Parametric motion graphs. In ACM Symposium on Interactive 3D Graphics (2007), pp. 129--136.

Digital Library

[8]

{IAF06} Ikemoto L., Arikan O., Forsyth D.: Knowing when to put your foot down. In ACM Symposium on Interactive 3D Graphics (2006), pp. 49--53.

Digital Library

[9]

{IAF07} Ikemoto L., Arikan O., Forsyth D.: Quick transitions with cached multi-way blends. In ACM Symposium on Interactive 3D Graphics (2007), pp. 145--151.

Digital Library

[10]

{KG03} Kovar L., Gleicher M.: Flexible automatic motion blending with registration curves. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (Aug. 2003), pp. 214--224.

Digital Library

[11]

{KGP02} Kovar L., Gleicher M., Pighin F.: Motion graphs. ACM Trans. on Graphics 21, 3 (2002), 473--482.

Digital Library

[12]

{KS05} Kwon T., Shin S. Y.: Motion modeling for on-line locomotion synthesis. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (July 2005), pp. 29--38.

Digital Library

[13]

{LCR*02} Lee J., Chai J., Reitsma P. S. A., Hodgins J. K., Pollard N. S.: Interactive control of avatars animated with human motion data. ACM Trans. on Graphics 21, 3 (2002), 491--500.

Digital Library

[14]

{LL04} Lee J., Lee K. H.: Precomputing avatar behavior from human motion data. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (2004), pp. 79--87.

Digital Library

[15]

{LP02} Liu C. K., Popović Z.: Synthesis of complex dynamic character motion from simple animations. ACM Trans. on Graphics 21, 3 (2002), 408--416.

Digital Library

[16]

{MP07} McCann J., Pollard N. S.: Responsive characters from motion fragments. ACM Trans. on Graphics (SIGGRAPH 2007) (2007).

Digital Library

[17]

{Nil71} Nilsson N.: Problem-Solving Methods in Artificial Intelligence. McGraw-Hill, 1971.

Digital Library

[18]

{PB02} Pullen K., Bregler C.: Motion capture assisted animation: texturing and synthesis. ACM Trans. on Graphics 22, 2 (2002), 501--508.

Digital Library

[19]

{PSKS04} Park S. I., Shin H. J., Kim T. H., Shin S. Y.: On-line motion blending for real-time locomotion generation. Computer Animation and Virtual Worlds 15, 3--4 (2004), 125--138.

Digital Library

[20]

{PSS02} Park S. I., Shin H. J., Shin S. Y.: On-line locomotion generation based on motion blending. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (July 2002), pp. 105--112.

Digital Library

[21]

{RP07} Reitsma P. S. A., Pollard N. S.: Evaluating motion graphs for character animation. ACM Trans. Graph. (2007), 18.

Digital Library

[22]

{SH05} Safonova A., Hodgins J. K.: Analyzing the physical correctness of interpolated human motion. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (2005), pp. 171--180.

Digital Library

[23]

{SH07} Safonova A., Hodgins J. K.: Construction and optimal search of interpolated motion graphs. In ACM Trans. Graph. (2007), p. 106.

Digital Library

[24]

{SHP04} Safonova A., Hodgins J. K., Pollard N. S.: Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Trans. on Graphics 23, 3 (2004), 514--521.

Digital Library

[25]

{SO06} Shin H. J., Oh H. S.: Fat graphs: Constructing an interactive character with continuous controls. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (Sept. 2006), pp. 291--298.

Digital Library

[26]

{SSSE00} Schödl A., Szeliski R., Salesin D. H., Essa I.: Video textures. In Proceedings of ACM SIGGRAPH 2000 (July 2000), Computer Graphics Proceedings, Annual Conference Series, pp. 489--498.

Digital Library

[27]

{TLP07} Treuille A., Lee Y., Popović Z.: Near-optimal character animation with continuous control. ACM Trans. Graph. (2007), 7.

Digital Library

[28]

{WB04} Wang J., Bodenheimer B.: Computing the duration of motion transitions: an empirical approach. In ACM SIGGRAPH/Eurographics Symp. on Comp. Animation (2004), pp. 335--344.

Digital Library

[29]

{WK88} Witkin A., Kass M.: Spacetime constraints. Computer Graphics (Proceedings of SIGGRAPH 88) 22, 4 (1988), 159--168.

Digital Library

Cited By

Juarez-Perez AKallmann MMcGuire MNowrouzezahari D(2018)Fast behavioral locomotion with layered navigation meshesProceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/3190834.3190841(1-6)Online publication date: 15-May-2018
https://dl.acm.org/doi/10.1145/3190834.3190841
Juarez-Perez AKallmann MNeff MGeraerts RShum H(2016)Full-body behavioral path planning in cluttered environmentsProceedings of the 9th International Conference on Motion in Games10.1145/2994258.2994281(107-112)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2994258.2994281
Mahmudi MKallmann M(2015)Multi-modal data-driven motion planning and synthesisProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822044(119-124)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822044
Show More Cited By

Index Terms

Achieving good connectivity in motion graphs
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Animation

Recommendations

Achieving good connectivity in motion graphs

Motion graphs have been widely successful in the synthesis of human motions. However, the quality of the generated motions depends heavily on the connectivity of the graphs and the quality of transitions in them. Achieving both of these criteria ...
On Group Connectivity of Graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z ₃-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured ...
Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

July 2008

230 pages

ISBN:9783905674101

Conference Chairs:
Eugene Fiume,
Jerry Tessendorf,
Program Chairs:
Markus Gross,
Doug James

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 07 July 2008

Check for updates

Qualifiers

Research-article

Conference

SCA08

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA08: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation

July 7 - 9, 2008

Dublin, Ireland

Acceptance Rates

SCA '08 Paper Acceptance Rate 24 of 60 submissions, 40%;

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
184
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Juarez-Perez AKallmann MMcGuire MNowrouzezahari D(2018)Fast behavioral locomotion with layered navigation meshesProceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/3190834.3190841(1-6)Online publication date: 15-May-2018
https://dl.acm.org/doi/10.1145/3190834.3190841
Juarez-Perez AKallmann MNeff MGeraerts RShum H(2016)Full-body behavioral path planning in cluttered environmentsProceedings of the 9th International Conference on Motion in Games10.1145/2994258.2994281(107-112)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2994258.2994281
Mahmudi MKallmann M(2015)Multi-modal data-driven motion planning and synthesisProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822044(119-124)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822044
Normoyle AJörg SShapiro AAmato NHodgins J(2014)Trade-offs between responsiveness and naturalness for player charactersProceedings of the 7th International Conference on Motion in Games10.1145/2668064.2668087(61-70)Online publication date: 6-Nov-2014
https://dl.acm.org/doi/10.1145/2668064.2668087
Lee YWampler KBernstein GPopović JPopović Z(2014)Motion fields for interactive character locomotionCommunications of the ACM10.1145/260275857:6(101-108)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2602758
Song SLiu WWei RXing WRen C(2014)Path planning directed motion control of virtual humans in complex environmentsJournal of Visual Languages and Computing10.1016/j.jvlc.2014.10.01125:6(772-781)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.jvlc.2014.10.011
Lo WKnaus CZwicker MBoulic RKomura T(2012)Learning motion controllers with adaptive depth perceptionProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2422356.2422378(145-154)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2422356.2422378
Mahmudi MKallmann MBoulic RKomura T(2012)Precomputed motion maps for unstructured motion captureProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2422356.2422376(127-136)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2422356.2422376
Lo WKnaus CZwicker M(2012)Learning motion controllers with adaptive depth perceptionProceedings of the 11th ACM SIGGRAPH / Eurographics conference on Computer Animation10.5555/2421731.2421753(145-154)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2421731.2421753
Mahmudi MKallmann M(2012)Precomputed motion maps for unstructured motion captureProceedings of the 11th ACM SIGGRAPH / Eurographics conference on Computer Animation10.5555/2421731.2421751(127-136)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2421731.2421751
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten