Pankaj K. Agarwal
Jeff Erickson
John Hershberger
Christian Jensen
Lydia Kavraki
David Mount
Subhash Suri
Skip Abstract Section
Abstract
This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.
- Agarwal, P. K., Arge, L., and Erickson, J. 2000. Indexing moving points. In Proceedings of the Annual ACM Symposium on the Principles of Database Systems. 175--186.]] Google Scholar
- Agarwal, P. K., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2000. Deformable free space tiling for kinetic collision detection. In Proc. 4th Workshop Algorithmic Found. Robot., to appear.]]Google Scholar
- Agarwal, P. K. and Erickson, J. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack, eds. Contemporary Mathematics, vol. 223. American Mathematical Society, R.I., pp. 1--56.]]Google Scholar
- Agarwal, P. K., Guibas, L. J., Hershberger, J., and Veach, E. 1997. Maintaining the extent of a moving point set. In Proceedings of the 5th Workshop on Algorithms Data Structure. Lecture Notes in Computer Science, vol. 1272. Springer-Verlag, New York, pp. 31--44.]] Google Scholar
- Agarwal, P. K. and Har-Peled, S. 2001. Maintaining approximate extent measures of moving points. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms.]] Google Scholar
- Agarwal, P. K. and Procopiuc, C. M. 2002. Advances in indexing mobile objects. IEEE Bull. Data Eng. 25, 25--34.]]Google Scholar
- Agarwal, P. K. and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V. North-Holland, Amsterdam, The Netherlands, pp. 49--119.]]Google Scholar
- Alm, E. and Baker, D. 1999. Prediction of protein-folding mechanisms from free-energy landscapes derived from native structures. Proc. Nat. Acad. Sci. USA, 96, 11305--11310.]]Google Scholar
- Amadei, A., Linssen, B. M., and Berendsen, H. J. C. 1993. Essential dynamics of protein. Proteins: Structure, Function, and Genetics 17, 412--425.]]Google Scholar
- Amato, N. M., Dill, K. A., and Song, G. 2002. Using motion planning to map protein folding landscapes and analyze folding kinetics of known naive structures. In Proceedings of the 6th International Conference in Computational Molecular Biology. pp. 2--11.]] Google Scholar
- Apaydin, M., Brutlag, D., Guestrin, C., Hsu, D., and Latombe, J. 2002. Stochastic roadmap simulation: An efficient representation and algorithm for analyzing molecular motion. In Proceedings of the 6th International Conference in Computational Molecular Biology. pp. 12--21.]] Google Scholar
- Apaydin, M., Singh, A., Brutlag, D., and Latombe, J. 2001. Capturing molecular energy landscapes with probabilistic conformational roadmaps. In Proceedings of the IEEE Conference on Robotics and Automation.]]Google Scholar
- Arulampalam, S., Maskell, S., Gordon, N., and Clapp, T. 2002. A tutorial on particle filters for on-line non-linear/non-gaussian bayesian tracking. IEEE Trans. Sig. Proc. 50, 174--188.]]Google Scholar
- Atallah, M. J. 1985. Some dynamic computational geometry problems. Comput. Math. Appl. 11, 1171--1181.]]Google Scholar
- Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. Comput. Graph 23, 223--232.]] Google Scholar
- Baraff, D. and Witkin, A. P. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH. pp. 43--54.]] Google Scholar
- Barraquand, J. and Latombe, J.-C. 1991. Robot motion planning: A distributed representation approach. Internat. J. Robot. Res. 10, 628--649.]] Google Scholar
- Basch, J., Guibas, L. J., and Hershberger, J. 1997. Data structures for mobile data. In Proceedings of the 8th ACM-SIAM Symposium Discrete Algorithms. pp. 747--756.]] Google Scholar
- Bern, M. and Plassmann, P. 2000. Mesh generation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers, B. V. North-Holland, Amsterdam, The Netherlands, 291--332.]]Google Scholar
- Black, M. and Yacoob, Y. 1997. Recognizing facial expressions in image sequences using local parameterized models of image motion. Int. J. Comput. Vis. 25, 23--48.]] Google Scholar
- Black, M. J. and Jepson, A. D. 1998. Eigentracking: Robust matching and tracking of articulated objects using a view-based representation. Int. J. Comput. Vis. 26, 63--84.]] Google Scholar
- Blake, A., North, B., and Isard, M. 1999. Learning multi-class dynamics. In Advances in Neural Information Processing Systems. vol. 11. MIT Press, pp. 389--395.]] Google Scholar
- Bonnet, P., Gehrke, J. E., and Seshadri, P. 2000. Querying the physical world. IEEE Pers. Commun. 7, 10--15.]]Google Scholar
- Bonnet, P., Gehrke, J. E., and Seshadri, P. 2001. Towards sensor database systems. In Proceedings of the 2nd International Conference on Mobile Data Management.]] Google Scholar
- Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of SIGGRAPH 2002. ACM Press, pp. 594--603.]] Google Scholar
- Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C., and Jetcheva, J. 1998. A performance comparison of multi-hop wireless ad hoc network routing protocols. In ACM Mob. Comput. Netwo. (MobiCom). 85--97.]] Google Scholar
- Brown, J., Sorkin, S., Bruyns, C., Latombe, J.-C., Montgomery, K., and Stephanides, M. 2001. Real-time simulation of deformable objects: Tools and application. Proc. Comput. Animat.]]Google Scholar
- Bryant, R., Edelsbrunner, H., Koehl, P., and Levitt, M. 2000. Inclusion-exclusion formulas for the area derivative of a space-filling diagram. manuscript.]]Google Scholar
- Chen, T. and Metaxas, D. 2000. Image segmentation based on the integration of Markov random fields and deformable models. In Proceedings of MICAI 2000. pp. 11--14.]] Google Scholar
- Cheng, H.-L., Dey, T. K., Edelsbrunner, H., and Sullivan, J. 2001. Dynamic skin triangulation. Disc. Comput. Geom. 25, 525--568.]]Google Scholar
- Chomicki, J. and Revesz, P. Z. 1999. A geometric framework for specifying spatiotemporal objects. In Proceedings of the 6th International Workshop on Time Representation and Reasoning. pp. 41--46.]] Google Scholar
- Cockburn, B., Karniadakis, G., and Shu, C. W. 2000. Discontinuous Galerkin Methods: Theory, Computation and Applications. Springer-Verlag, New York.]]Google Scholar
- Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space & time adaptive sampling. In Proceedings of ACM SIGGRAPH. pp. 31--36.]] Google Scholar
- DeCarlo, D. and Metaxas, D. 2000. Optical flow constraints on deformable models with applications to face tracking. Int. J. Comput. Vis. 32, 99--127.]] Google Scholar
- Dill, K. A., Bromberg, S., Yue, K. Z., and Fiebig, K. M. 1995. Principles of protein folding. a perspective from simple exact models. Protein Sci. 4, 561--602.]]Google Scholar
- Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2000. Topological persistence and simplification. In Proceedings of the 41st IEEE Symposium on Foundations on Computer Science, pp. 454--463.]] Google Scholar
- Erickson, J., Guoy, D., Sullivan, J. M., and Üngör, A. 2002. Building space-time meshies over arbitrary spatial domains. In Proceedings of the 11th International Meshing Roundtable, 391--402.]]Google Scholar
- Gao, J., Guibas, L., Hershberger, J., Zhang, L., and Zhu, A. 2001. Discrete mobile centers. Manuscript.]]Google Scholar
- Guibas, L., Nguyen, A., Russel, D., and Zhang, L. 2002. Collision detection for deforming necklaces. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. pp. 33--42.]] Google Scholar
- Halperin, D., Kavraki, L. E., and Latombe, J.-C. 1997. Robotics. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds. CRC Press LLC, Boca Raton, Fla, pp. 755--778.]] Google Scholar
- Hartley, R. I. and Zisserman, A. 2000. Multiple View Geometry in Computer Vision. Cambridge University Press.]] Google Scholar
- Isard, M. and Blake, A. 1998. Condensation---Conditional density propagation for visual tracking. Int. J. Comput. Vis. 29, 5--28.]] Google Scholar
- Kahan, S. 1991. A model for data in motion. In Proceedings of the 23th Annual ACM Symposium on the Theory of Computing. pp. 267--277.]] Google Scholar
- Karp, B. and Kung, H. T. 2000. Greedy perimeter stateless routing (gpsr) for wireless networks. ACM Mob. Comput. Netw. (MobiCom). 243--254.]] Google Scholar
- Kavraki, L. E., Latombe, J.-C., Motwani, R., and Raghavan, P. 1995. Randomized query processing in robot path planning. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing. pp. 353--362.]] Google Scholar
- Kavraki, L. E., Ŝvestka, P., Latombe, J.-C., and Overmars, M. H. 1996. Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Trans. Robot. Autom. 12, 566--580.]]Google Scholar
- Kirkpatrick, D., Snoeyink, J., and Speckmann, B. 2000. Kinetic collision detection for simple polygons. In Proceedings of the 16th Symposium on Computational Geometry. pp. 322--330.]] Google Scholar
- Kirkpatrick, D. and Speckmann, B. 2000. Separation sensitive kinetic collision detection for simple polygons. In Proceedings of the Japan Conference on Discrete and Computational Geometry.]] Google Scholar
- Kirkpatrick, D. and Speckmann, B. 2002. Kinetic maintenance of context-sensitive hierarchical representations of disjoint simple polygons. In Proceedings of the 13th Annual ACM Symposium on Computational Geometry.]] Google Scholar
- Kry, P. G. and Pai, D. K. 2002. Continuous contact simulation for smooth surfaces. ACM Trans. Graphics, to appear.]] Google Scholar
- Lamiraux, F. and Kavraki, L. 2001. Planning paths for elastic objects under manipulation constraints. Int. J. Roboti. Res. 20, 188--208.]]Google Scholar
- Lang, J., Pai, D. K., and Woodham, R. J. 2002. Robotic acquisition of deformable models. In Proceedings of the IEEE International Conference on Robotics and Automation. pp. 933--938.]]Google Scholar
- Larson, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Fast distance queries using rectangular swept sphere volume. In Proceedings of the IEEE International Conference on Robotics and Automation, 3719--3726.]]Google Scholar
- Laszlo, J., van de Panne, M., and Fiume, E. L. 2000. Interactive control for physically-based animation. In Proceedings of ACM SIGGRAPH, pp. 201--208.]] Google Scholar
- Latombe, J.-C. 1991. Robot Motion Planning. Kluwer Academic Publishers, Boston, Mass.]] Google Scholar
- Leach, A. R. 1996. Molecular Modeling: Principles and Applications. Addison-Welsley Longman, Rssex, England.]]Google Scholar
- Levitt, M., Gerstein, M., Huang, E., Subbiah, S., and Tsai, J. 1997. Protein folding: The endgame. Ann. Rev. Biochem. 66, 549--579.]]Google Scholar
- Lin, M. and Gottschalk, S. 1998. Collision detection between geometric models: A survey. In Proceedings of the IMA Conference on Mathematics of Surfaces.]]Google Scholar
- Lindeberg, T. 1994. Scale-Space Theory in Computer Vision. Kluwer Academic Publishers, Bostan, Mass.]] Google Scholar
- Longuet-Higgins, H. C. 1981. A computer algorithm for reconstructing a scene from two projections. Nature 293, 133--135.]]Google Scholar
- Lotstedt, P. 1981. Coulomb friction in two-dimensional rigid body systems. ZAMM 61, 605--613.]]Google Scholar
- Lowrie, R. B., Roe, P. L., and van Leer, B. 1998. Space-time methods for hyperbolic conservation laws. In Barriers and Challenges in Computational Fluid Dynamics. ICASE/LaRC Interdisciplinary Series in Science and Engineering, vol. 6. Kluwer, pp. 79--98.]]Google Scholar
- Mason, M. T. 2001. Mechanics of Robotic Manipulation. MIT Press.]] Google Scholar
- Matouŝek, J. 1994. Geometric range searching. ACM Comput. Surv. 26, 421--461.]] Google Scholar
- Meyer, M., Debunne, G., Desbrun, M., and Barr, A. H. 2001. Interactive animation of cloth-like objects in virtual reality. J. Vis. Comput. Animat. 12, 1--12.]]Google Scholar
- Mirtich, B. V. 1996. Impulse-based dynamic simulation of rigid body systems. Ph.D. dissertation, Univ. California at Berkeley.]] Google Scholar
- Mirtich, B. 1998. V-clip: Fast and robust polyhedral collision detection. ACM Trans. Graph. 17, 177--208.]] Google Scholar
- Mirtich, B. 2000. Timewarp rigid body simulation. In Proceedings of ACM SIGGRAPH. pp. 193--200.]] Google Scholar
- Onuchic, J. N., Luthey-Schulten, Z., and Wolynes, P. G. 1997. Theory of protein folding: The energy landscape perspective. Ann. Rev. Phys. Chem. 48, 545--600.]]Google Scholar
- Pai, D. K., van den Doel, K., James, D. L., Lang, J., Lloyd, J. E., Richmond, J. L., and Yau, S. H. 2001. Scanning physical interaction behavior of 3d objects. In Proceedings of ACM SIGGRAPH. pp. 87--96.]] Google Scholar
- Pfoser, D., Jensen, C. J., and Theodoridis, Y. 2000. Novel approaches to the indexing of moving object trajectories. In Proceedings of the 26th International Conference on Very Large Databases. 395--406.]] Google Scholar
- Richmond, J. L. and Pai, D. K. 2000. Active measurement and modeling of contact sounds. In Proceedings of the IEEE International Conference on Robotics and Automation. pp. 2146--2152.]]Google Scholar
- Richter, G. R. 1994. An explicit finite element method for the wave equation. Appl. Num. Math. 16, 65--80.]] Google Scholar
- Royer, E. and Toh, C. 1999. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Pers. Commun. 6, 46--55.]]Google Scholar
- Ŝaltenis, S., Jensen, C. S., Leutenegger, S. T., and Lopez, M. A. 2000. Indexing the positions of continuously moving objects. In Proceedings of the ACM SIGMOD International Conference on Management of Data. pp. 331--342.]] Google Scholar
- Schirra, S. 2000. Robustness and precision issues in geometric computation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers, B. V. North-Holland, Amsterdam, The Netherlands, pp. 597--632.]]Google Scholar
- Sistla, A. P. and Wolfson, O. 1995. Temporal conditions and integrity constraints in active database systems. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. pp. 269--280.]] Google Scholar
- Sistla, A. P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the International Conference on Data Engineering. pp. 422--432.]] Google Scholar
- Song, G. and Amato, N. M. 2002. Using motion planning to study protein folding pathways. J. Comput. Biol. 9, 149--168.]]Google Scholar
- Sorenson, H. 1985. Kalman Filtering: Theory and Applications. IEEE Press.]]Google Scholar
- Tayeb, J., Ulusoy, O., and Wolfson, O. 1998. A quadtree-based dynamic attribute indexing method. Comput. J., 185--200.]]Google Scholar
- Teodoro, M., Phillips, G., and Kavraki, L. 2000. Singular value decomposition of protein conformational motions: Application to HIV-1 protease. In Currents in Computational Molecular Biology. Universal Academy Press Inc., Tokyo, Japan, pp. 198--199.]]Google Scholar
- Torr, P. H. S., Szeliski, R., and Anandan, P. 2001. An integrated Bayesian approach to layer extraction from image sequences. IEEE Trans. Patt. Anal. Mach. Int. 23, 297--303.]] Google Scholar
- Üngör, A. and Sheffer, A. 2002. Pitching tents in space-time: Mesh generation for discontinuous Galerkin method. Int. J. Found. Comput. Sci. 13, 201--222.]]Google Scholar
- Üngör, A., Sheffer, A., Haber, R. B., and Teng, S.-H. 2002. Layer based solutions for constrained space-time meshing. Appl. Numer. Math., to appear.]]Google Scholar
- van den Doel, K., Kry, P., and Pai, D. K. 2001. FoleyAutomatic: Physically-based sound effects for inter active simulation and animation. Computer Graphics (ACM SIGGRAPH 2001 Conference Proceedings). pp. 537--544.]] Google Scholar
- Vogler, C. and Metaxas, D. 2000. A linguistics-based approach to american sign language recognition. In Proceedings of the International Conference on Gestures: Meaning and Use.]]Google Scholar
- Wolfson, O., Chamberlain, S., Jiang, L., and Mendez, G. 1998. Cost and imprecision in modeling the position of moving objects. In Proceedings of the International Conference Data Engineering. pp. 588--596.]] Google Scholar
- Wolfson, O., Jiang, L., Sistla, A. P., Chamberlain, S., and Deng, M. 1999. Databases for tracking mobile units in real time. In Proceedings of the International Conference Database Theory. pp. 169--186.]] Google Scholar
- Wolfson, O., Sistla, A. P., Xu, B., Zhou, S. J., and Chamberlain, S. 1999. Domino: Databases for moving objects tracking. In Proceedings of the SIGMOD International Conference on Management of Data. pp. 547--559.]] Google Scholar
- Yin., L., Acharya., A., Sobh, N., Haber, R. B., and Tortorelli, D. A. 2000. A space-time discontinuous Galerkin method for elastodynamic analysis. In Discontinuous Galerkin Methods: Theory, Computation and Applications, B. Cockburn, G. Karniadakis, and C. Shu, Eds. Lecture Notes in Computational Science and Engineering, vol. 11. Springer-Verlag, New York, pp. 459--464.]]Google Scholar
- Zilles, C. B. and Salisbury, J. K. 1995. A constraint-based god-object method for haptic display. In Proceedings of the IEEE International Conference on Robotics and Automation. pp. 146--151.]] Google Scholar
Recommendations
Morphing as a Tool for Motion Modeling
ICIAP '99: Proceedings of the 10th International Conference on Image Analysis and ProcessingThis study merges the methodologies of computer graphics and image processing by using the morphing techniques in motion modeling problem. The proposed method morphs the final frame of a sequence of motion frames from the initial frame for modeling the ...
A Factorization-Based Approach for Articulated Nonrigid Shape, Motion and Kinematic Chain Recovery From Video
Recovering articulated shape and motion, especially human body motion, from video is a challenging problem with a wide range of applications in medical study, sport analysis and animation, etc. Previous work on articulated motion recovery generally ...
Motion Volume: Visualization of Human Motion Manifolds
VRCAI '19: Proceedings of the 17th International Conference on Virtual-Reality Continuum and its Applications in IndustryThe understanding of human motion is important in many areas such as sports, dance, and animation. In this paper, we propose a method for visualizing the manifold of human motions. A motion manifold is defined by a set of motions in a specific motion ...
Comments