“Object-space multiphase implicit functions” by Yuan, Yu and Wang

  • ©Zhan Yuan, Yizhou Yu, and Wenping Wang




    Object-space multiphase implicit functions



    Implicit functions have a wide range of applications in entertainment, engineering and medical imaging. A standard two-phase implicit function only represents the interior and exterior of a single object. To facilitate solid modeling of heterogeneous objects with multiple internal regions, object-space multiphase implicit functions are much desired. Multiphase implicit functions have much potential in modeling natural organisms, heterogeneous mechanical parts and anatomical atlases. In this paper, we introduce a novel class of object-space multiphase implicit functions that are capable of accurately and compactly representing objects with multiple internal regions. Our proposed multiphase implicit functions facilitate true object-space geometric modeling of heterogeneous objects with non-manifold features. We present multiple methods to create object-space multiphase implicit functions from existing data, including meshes and segmented medical images. Our algorithms are inspired by machine learning algorithms for training multicategory max-margin classifiers. Comparisons demonstrate that our method achieves an error rate one order of magnitude smaller than alternative techniques.


    1. 3D-IRCADb. 3d-ircadb (3d image reconstruction for comparison of algorithm database). http://www.ircad.fr/softwares/3Dircadb/3Dircadb1/index.php.Google Scholar
    2. Anderson, J., Garth, C, Duchaineau, M., and Joy, K. 2010. Smooth, volume-accurate material interface reconstruction. Visualization and Computer Graphics, IEEE Transactions on 16, 5, 802–814. Google ScholarDigital Library
    3. Blinn, J. 1982. A generalization of algebraic surface drawing. ACM Transactions on Graphics 1, 235–256. Google ScholarDigital Library
    4. Boissonnat, J.-D., and Memari, P. 2007. Shape reconstruction from unorganized cross-sections. In Fifth Eurographics symposium on Geometry processing, 89–98. Google ScholarDigital Library
    5. Bredensteiner, E., and Bennett, K. 1999. Multicategory classification by support vector machines. Computational Optimization and Applications 12, 1, 53–79. Google ScholarDigital Library
    6. Carr, J., Mitchell, T., Beatson, R., Cherrie, J., Fright, W., McCallum, B., and Evans, T. 2001. Reconstruction and representation of 3d objects with radial basis functions. In SIGGRAPH 2001 Conference Proceedings, 67–76. Google ScholarDigital Library
    7. Feng, P., Ju, T., and Warren, J. 2010. Piecewise tri-linear contouring for multi-material volumes. Advances in Geometric Modeling and Processing, 43–56. Google ScholarDigital Library
    8. Frisken, S., Perry, R., Rockwood, A., and Jones, T. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of SIGGRAPH 2000, 249–254. Google ScholarDigital Library
    9. Gascuel, M.-P. 1993. An implicit formulation for precise contact modeling between flexible solids. In Proceedings of SIGGRAPH 93, Computer Graphics Proceedings, Annual Conference Series, 313–320. Google ScholarDigital Library
    10. Liu, L., Bajaj, C., Deasy, J., Low, D. A., and Ju, T. 2008. Surface reconstruction from non-parallel curve networks. Computer Graphics Forum 27, 2, 155–163.Google ScholarCross Ref
    11. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. Computer Graphics 21, 4, 163–169. Google ScholarDigital Library
    12. Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. In ACM Transactions on Graphics (TOG), vol. 25, ACM, 812–819. Google ScholarDigital Library
    13. Makhorin, A., 2006. GLPK (GNU linear programming kit). http://www.gnu.org/software/glpk/.Google Scholar
    14. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition of unity implicits. In ACM Transactions on Graphics (TOG), vol. 22, ACM, 463–470. Google ScholarDigital Library
    15. Oladunni, O., and Singhal, G. 2009. Piecewise multi-classification support vector machines. In Neural Networks, 2009. IJCNN 2009. International Joint Conference on, IEEE, 2323–2330. Google ScholarDigital Library
    16. Peng, H., Chung, P., Long, F., Qu, L., Jenett, A., Seeds, A., Myers, E., and Simpson, J. 2011. Brainaligner: 3d registration atlases of Drosophila brains. Nature Methods 8, 6, 493–498.Google ScholarCross Ref
    17. Ricci, A. 1973. A constructive geometry for computer graphics. The Computer Journal 16, 2, 157–160.Google ScholarCross Ref
    18. Schölkopf, B., Giesen, J., and Spalinger, S. 2005. Kernel methods for implicit surface modeling. In Advances in Neural Information Processing Systems 17, MIT Press, Cambridge, MA, 1193–1200.Google Scholar
    19. Shen, C., O’Brien, J., and Shewchuk, J. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Transactions on Graphics 23, 3, 896–904. Google ScholarDigital Library
    20. Stalling, D., Zöckler, M., and Hege, H. 1998. Interactive segmentation of 3d medical images with subvoxel accuracy. In Proc. CAR’98 Computer Assisted Radiology and Surgery, 137–142.Google Scholar
    21. Steinke, F., Schlkopf, B., and Blanz, V. 2005. Support vector machines for 3d shape processing. Computer Graphics Forum 24, 3, 285–294.Google ScholarCross Ref
    22. Suykens, J., and Vandewalle, J. 1999. Multiclass least squares support vector machines. In International Joint Conference on Neural Networks (IJCNN’99).Google Scholar
    23. Takayama, K., Sorkine, O., Nealen, A., and Igarashi, T. 2010. Volumetric modeling with diffusion surfaces. In ACM Transactions on Graphics (TOG), vol. 29, ACM, 180. Google ScholarDigital Library
    24. Turk, G., and O’Brien, J. 2002. Modelling with implicit surfaces that interpolate. ACM Transactions on Graphics 21, 4, 855–873. Google ScholarDigital Library
    25. Vapnik, V. 1998. Statistical learning theory. John Wiley & Sons, Inc.Google Scholar
    26. Wang, L., Yu, Y., Zhou, K., and Guo, B. 2011. Multiscale vector volumes. ACM Trans. Graph. 30, 6, 167. Google ScholarDigital Library
    27. Weaire, D., and Phelan, R. 1994. A counter-example to kelvin’s conjecture on minimal surfaces. Philosophical Magazine Letters 69, 2, 107–110.Google ScholarCross Ref
    28. Wyvill, G., McPheeters, C., and Wyvill, B. 1986. Data structure for soft objects. Visual Computer 2, 4, 227–234.Google ScholarCross Ref
    29. Wyvill, B., Guy, A., and Galin, E. 1999. Extending the csg tree. warping, blending and boolean operations in an implicit surface modeling system. Computer Graphics Forum 18, 2, 149–158.Google ScholarCross Ref
    30. Yamazaki, S., Kase, K., and Ikeuchi, K. 2002. Non-manifold implicit surfaces based on discontinuous implicitization and polygonization. In Proc. Geometric Modeling and Processing 2002, 138–146. Google ScholarDigital Library
    31. Zhang, Y., Hughes, T., and Bajaj, C. 2010. An automatic 3d mesh generation method for domains with multiple materials. Computer methods in applied mechanics and engineering 199, 5, 405–415.Google Scholar
    32. Zhao, H.-K., Chan, T., Merriman, B., and Osher, S. 1996. A variational level set approach to multiphase motion. Journal of Computational Physics 127, 179–195. Google ScholarDigital Library

ACM Digital Library Publication: