A geometric constraint library for 3D graphical applications

ABSTRACT

Recent computer technologies have enabled fast high-quality 3D graphics on personal computers, and also have made the development of 3D graphical applications easier. However, most of such technologies do not sufficiently support layout and behavior aspects of 3D graphics. Geometric constraints are, in general, a powerful tool for specifying layouts and behaviors of graphical objects, and have been applied to 2D graphical user interfaces and specialized 3D graphics packages. In this paper, we present Chorus3D, a geometric constraint library for 3D graphical applications. It enables programmers to use geometric constraints for various purposes such as geometric layout, constrained dragging, and inverse kinematics. Its novel feature is to handle scene graphs by processing coordinate transformations in geometric constraint satisfaction. We demonstrate the usefulness of Chorus3D by presenting sample constraint-based 3D graphical applications.

References

1. Badler, N. I., Phillips, C. B., and Webber, B. L. Simulating Humans: Computer Graphics, Animation, and Control. Oxford University Press, Oxford, 1993.]]
2. Bertsekas, D. P. Nonlinear Programming, 2nd ed. Athena Scientific, 1999.]]
3. Borning, A., Marriott, K., Stuckey, P., and Xiao, Y. Solving linear arithmetic constraints for user interface applications. In Proc. ACM UIST, 1997, 87-96.]]
4. Carey, R., Bell, G., and Marrin, C. The Virtual Reality Modeling Language (VRML97). ISO/IEC 14772-1:1997, The VRML Consortium Inc., 1997.]]
5. Diehl, S., and Keller, J. VRML with constraints. In Proc. Web3D-VRML, ACM, 2000, 81-86.]]
6. Fletcher, R. Practical Methods of Optimization, 2nd ed. John Wiley & Sons, 1987.]]
7. Freeman-Benson, B. N., Maloney, J., and Borning, A. An incremental constraint solver. Commun. ACM 33, 1 (1990), 54-63.]]
8. Gleicher, M. A graphical toolkit based on differential constraints. In Proc. ACM UIST, 1993, 109-120.]]
9. Gleicher, M. A differential approach to graphical manipulation (Ph.D. thesis). Tech. Rep. CMU-CS-94-217, Sch. Comput. Sci. Carnegie Mellon Univ., 1994.]]
10. Herrera, F., Lozano, M., and Verdegay, J. L. Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artif. Intell. Rev. 12, 4 (1998), 265-319.]]
11. Heydon, A., and Nelson, G. The Juno-2 constraint-based drawing editor. Research Report 131a, Digital Systems Research Center, 1994.]]
12. Hosobe, H. A scalable linear constraint solver for user interface construction. In Principles and Practice of Constraint Programming---CP2000, vol. 1894 of LNCS, Springer, 2000, 218-232.]]
13. Hosobe, H. A modular geometric constraint solver for user interface applications. In Proc. ACM UIST, 2001, 91-100.]]
14. Kamada, T., and Kawai, S. An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31, 1 (1989), 7-15.]]
15. Kitano, H., Ed. Genetic Algorithms. Sangyo-Tosho, 1993. In Japanese.]]
16. Kramer, G. A. A geometric constraint engine. Artif. Intell. 58, 1-3 (1992), 327-360.]]
17. Marriott, K., Chok, S. S., and Finlay, A. A tableau based constraint solving toolkit for interactive graphical applications. In Principles and Practice of Constraint Programming---CP98, vol. 1520 of LNCS, Springer, 1998, 340-354.]]
18. Sannella, M. Skyblue: A multi-way local propagation constraint solver for user interface construction. In Proc. ACM UIST, 1994, 137-146.]]
19. Takahashi, S. Visualizing constraints in visualization rules. In Proc. CP2000 Workshop on Analysis and Visualization of Constraint Programs and Solvers, 2000.]]
20. Zhao, J., and Badler, N. I. Inverse kinematics positioning using nonlinear programming for highly articulated figures. ACM Trans. Gr. 13, 4 (1994), 313-336.]]