Abstract
The 3D seed-filling algorithm that fills consecutive object voxels at a time has shown higher efficiency than the method of filling only one voxel at a time. However, it searches seeds for filled voxels already containing no seeds. This paper presents a fast 3D seed-filling algorithm that uses a 2D pointer array of linked lists to avoid the redundant seed searches. The linked lists record the spans of filled voxels. Five comparison cases determine the current filling span, and the neighboring spans for searching seeds are either non-overlapping, or completely or partially overlapping. Seed searches are executed only for the non-overlapping span or part (in the case of the partial overlapping span) to minimize the searches. The experimental results show that the proposed algorithm is effective in eliminating the redundant seed searches and achieves high efficiency.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Albert TA, Slaaf DW (1995) A rapid regional filling technique for complex binary images. Comput Graph 19(4):541–549
Freund J (1997) Accelerated volume rendering using homogeneous encoding. In: Proceedings of IEEE Visualization ’97, Phoenix, Ariz., 19–24 October 1997. IEEE Press, Los Alamitos, CA
Feng L, Soon SH (1998) An effective 3D seed fill algorithm. Comput Graph 22(5):641–644
Fishkin KP, Barsky BA (1985) An analysis and algorithm for filling propagation. In: Graphics Interface Proceedings, Montreal, 27–31 May 1985
Gibson SFF (1999) Using linked volumes to model object collision, deformation, cutting, carving, and joining. IEEE Trans Vis Comput Graph 5(4):333–348
González E, Suárez A, Moreno C, Artigue F (1996) Complementary regions: a surface filling algorithm. In: IEEE international conference on robotics and automation, Minneapolis, Minn., 22–28 April 1996. IEEE Computer Society Press, Los Alamitos, CA
Levoy M (1990) Efficient ray tracing of volume data. ACM Trans Graph 9(3):245–261
Liu S, Ma W (1999) Seed-growing segmentation of 3-D surface from CT-contour data. Comput Aided Design 31(8):517–536
Oikarinen J (1998) Using 2- and 2½-dimensional seed filling in view lattice to accelerate volumetric rendering. Comput Graph 22(6):745–757
Oikarinen JT, Jyrkinen LJ (1998) Maximum intensity projection by 3-dimensional seed filling in view lattice. Comput Networks ISDN Syst 30:2003–2014
Suárez A, González E, Cabo JC, Y. Rollot Y, Manuel B, Moreno C, Artigue F (1995) An autonomous vehicle for surface filling. In: Proceedings of the Intelligent Vehicles ’95 Symposium. IEEE Service Center, Piscataway, NJ
Shareef N, Yagel R. (1995) Rapid previewing via volume-based solid modeling. In: Proceedings of the third ACM symposium on solid modeling and applications. ACM Press, New York
Tsai MD, Jou SB, Hsieh MS (2001a) Accurate surface voxelization for manipulating volumetric surfaces and solids with application in simulating musculoskeletal surgery. In: Ninth Pacific conference on computer graphics and applications, Tokyo, 16–18 October 2001. IEEE Computer Society Press, Los Alamitos, Calif.
Tsai MD, Hsieh MS, Jou SB (2001b) Virtual reality orthopedic surgery simulator. Comput Biol Med 31(3):333–351
Yu YW, Wang JH (1999) Image segmentation based on region growing and edge detection. In: IEEE international conference on systems, man, and cybernetics, Tokyo, 12–15 October 1999. IEEE, Los Alamitos, Calif.
Zhou Y, Toga AW (2000) Turning unorganized points into contours. In: Eighth Pacific conference on computer graphics and applications, Hong Kong, 3–5 October 2000. IEEE Computer Society Press, Los Alamitos, CA
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jou, SB., Tsai, MD. A fast 3D seed-filling algorithm. Vis Comput 19, 243–251 (2003). https://doi.org/10.1007/s00371-003-0192-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-003-0192-4