3D connected components

2021

• W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Eric N Landis. Fast 3-D Euclidean connected components. In John Krumm, editor, 3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021). ACM, 2 Nov 2021. URL: https://www.spatialgems.net/.
  [abstract▼] [details] [full text] [BibTeX▼]

  We present an efficient algorithm, with implementations, for computing the connected components within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over $10^9$ voxels. The components may be 8-connected or 26-connected. Computing connected components has applications ranging from material failure in concrete under increasing stress to electrical conductivity in complex metal objects to elasticity in 3D printed parts. On key to efficiency is representing voxels by 1-D \emphruns of adjacent voxels. As a special case, 2-D connected components of images may easily be computed.

  @incollection{connect-gem-2021,
      author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Landis, Eric N",
      editor = "Krumm, John",
      title = "Fast {3-D} {Euclidean} connected components",
      booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2021)",
      publisher = "ACM",
      year = "2021",
      month = "2 Nov",
      location = "Beijing, China (virtual)",
      mykey = "recent salles landis connect topology 2021",
      url = "https://www.spatialgems.net/",
      href = "\bibhref{240-connect-gem-2021}"
  }
  

2006

• W. Randolph Franklin and Eric Landis. Connected components on 1000x1000x1000 datasets. In 16th Fall Workshop on Computational Geometry. Smith College, Northampton, MA, 10-11 Nov 2006. (extended abstract).
  [details] [full text] [slides] [BibTeX▼]

  @inproceedings{wrf-connect-fwcg2006,
      author = "Franklin, W. Randolph and Landis, Eric",
      title = "Connected components on 1000x1000x1000 datasets",
      booktitle = "16th Fall Workshop on Computational Geometry",
      address = "Smith College, Northampton, MA",
      month = "10-11 Nov",
      year = "2006",
      mykey = "connect",
      note = "(extended abstract)",
      customlinkslides = "https://wrfranklin.org/p/110-smith-fwcg06-connect-talk.pdf",
      href = "\bibhrefat{110-smith-fwcg06-connect}{110-smith-fwcg06-connect-talk}"
  }
  

• Eric N. Landis, Tong Zhang, Edwin N. Nagy, George Nagy, and W. Randolph Franklin. Cracking, damage and fracture in four dimensions. Materials and Structures, online date: 13 July 2006.
  [abstract▼] [details] [full text] [BibTeX▼]

  Abstract Concrete and cracking are nearly synonymous despite our best efforts and intentions. Relationships between cracking and the stress states that lead to cracking can be instructive. In an effort to better understand these relationships, X-ray microtomography was used to make high-resolution three-dimensional digital images of small concrete specimens under load. Using 3D image analysis, quantitative measurements of internal crack growth were made that include effects of crack tortuosity, branching and microcracking. Successive images at different levels of cracking and damage provide us with a detailed picture of internal crack progression. When coupled with load-deformation response, bulk material properties such as fracture toughness or damage variables can be quantitatively linked with cracking. Measurements to date have shown distinct fracture regimes linked to crack formation and propagation. In addition, the crack measurements offer a way to provide a physical basis for a scalar damage variable.

  @article{landis2006,
      author = "Landis, Eric N. and Zhang, Tong and Nagy, Edwin N. and Nagy, George and Franklin, W. Randolph",
      title = "Cracking, damage and fracture in four dimensions",
      journal = "Materials and Structures",
      publisher = "Springer",
      year = "2006",
      mykey = "connect",
      month = "online date: 13 July",
      href = "\bibhref{109-matstruct2006-cracking-landis}",
      Keywords = "Concrete - Fracture - Damage - Tomography",
      publisher-url = "http://www.springerlink.com/content/ftgmk3m461716833/"
  }
  

• W. Randolph Franklin. CONNECT – find 3D connected components. 2006. URL: https://wrfranklin.org/pmwiki/ConnectedComponents.
  [details] [BibTeX▼]

  @misc{connect-web,
      author = "Franklin, W. Randolph",
      title = "{CONNECT} -- Find {3D} connected components",
      url = "https://wrfranklin.org/pmwiki/ConnectedComponents",
      mykey = "connect",
      year = "2006"
  }
  

2003

• Edwin Nagy, Tong Zhang, Wm Randolph Franklin, George Nagy, and E Landis. 3D analysis of tomographic images. In 16th ASCE Engineering Mechanics Conference. U Washington, Seattle, 16-18 July 2003. electronic proceedings.
  [details] [full text] [BibTeX▼]

  @inproceedings{acse2003,
      author = "Nagy, Edwin and Zhang, Tong and Franklin, Wm Randolph and Nagy, George and Landis, E",
      title = "{3D} Analysis of Tomographic Images",
      booktitle = "16th {ASCE} Engineering Mechanics Conference",
      year = "2003",
      address = "U Washington, Seattle",
      month = "16-18 July",
      mykey = "connect",
      note = "electronic proceedings",
      href = "\bibhref{98-acse03-3danalysis-nagy}"
  }
  

2001

• G Nagy, T Zhang, WR Franklin, E Landis, E Nagy, and D Keane. Volume and surface area distributions of cracks in concrete. In C. Arcelli, L.P. Cordella, and G. Sanniti di Baja, editors, Visual Form 2001: 4th International Workshop on Visual Form IWVF4, volume 2051/2001 of Lecture Notes in Computer Science. Springer-Verlag Heidelberg, Capri, Italy, 28-30 May 2001.
  [details] [full text] [poster] [BibTeX▼]

  @incollection{capri01,
      author = "Nagy, G and Zhang, T and Franklin, WR and Landis, E and Nagy, E and Keane, D",
      editor = "Arcelli, C. and Cordella, L.P. and di Baja, G. Sanniti",
      title = "Volume and Surface Area Distributions of Cracks in Concrete",
      booktitle = "Visual Form 2001: 4th International Workshop on Visual Form {IWVF4}",
      publisher = "Springer-Verlag Heidelberg",
      year = "2001",
      mykey = "connect",
      volume = "2051/2001",
      series = "Lecture Notes in Computer Science",
      address = "Capri, Italy",
      month = "28-30 May",
      href = "\bibhrefpp{95-capri01-paper}{95-capri01-poster.gif}",
      customlinkposter = "https://wrfranklin.org/p/95-capri01-poster.gif"
  }