Tweet
Dear list readers:
Recently (8/11/92) I posted a query for public domain programs
which can reconstruct 3D surfaces from contour data, using
triangular tiles. I have received several requests from
individuals who have wanted me to share the results of my search,
so I'd like to give the following summary:
1) Dr. Michael S. Sacks and Dr. Matthias Eck have independently
mentioned a software called MOVIE.BYU, developed at the
Engineering Computer Graphics Laboratory, Brigham Young
University (801-378-2812). A subset of this software,
MOSAIC.BYU, can handle surface reconstructions from contours.
However, the opinions of these two researchers have differed as
to the success of that software. I called BYU to get additional
information and I found out that MOVIE.BYU has been superseded by
CQUEL.BYU ($1,500, or $750 with the educational discount), which
unfortunately does not contain MOSAIC.BYU in its current release
(but it will at a future date). I asked whether MOSAIC.BYU could
be purchased separately, but I have not received an answer yet.
2) Dr. Lewis L. Sadler has reported success using CAD software:
I don't know of any public domain software that does what
you want, but any CAD software can be used. We use three
or four different packages for this purpose and it is a
relatively simple task to enter the curves or splines at
a given magnification and to establish the distance
between layers (sections). The non-trivial task is in
the registration of these sections to each other. Unless
there is a built in fiducial or some convenient method of
re-establishing the relationship of the sections, it can
be a nightmare.
Good Luck, Lewis L. Sadler
3) Dr. Scott Selbie has mentioned that a good overview of the
problem is available in Computers and Graphics, 1989, vol 13, No.
3, Complex contour organization for surface reconstruction, B.
Sinclair et al.
4) Mr. Dan Karron has kindly provided me with a manuscript
describing his "SpiderWeb Algorithm for Surface Construction from
Medical Volume Data: Geometric Properties of its Surface," co-
authored with James L. Cox and Bud Mishra. I have found it easy
to read and conceptually straightforward to implement (but have
not done so yet). Mr. Karron's article is available by anonymous
ftp to karron.med.nyu.edu, and he welcomes any comments and/or
suggestions.
5) Mr. Jeff Weiss has generously contributed the following
message:
I am doing some finite element work on the knee joint,
and have looked into different mesh generation techniques
including CT scans. The closest thing that I have seen
to what you describe follows.
A group of researchers at the University of Utah have
been involved in modeling electrical activity in the
human thorax. To construct 3-D finite element models of
the thorax and the internal organs, they used 116 MRI
scans recorded in 5mm increments from just above the
pelvis to just above the shoulders. For each image, the
borders of the subcutaneous fat/muscle, the inner border
of the skeletal muscle, and the epicardial surface of the
heart were manually digitized. The points from each of
these layers were fit to a parametric, bicubic spline,
then regenerated at a constant spatial resolution. Some
smoothing was also applied to the data at this time.
Two adjacent layers formed a three dimensional slice.
Points from the same surfaces in both layers were then
laced into triangles according to an algorithm that
sought to construct optimal (Delaunay) triangles. This
methodology provided a complete surface model.
For their finite element model, tetrahedral volume
elements were used. To each layer of points obtained
previously to describe the boundarys of the different
tissues/organs, a regular grid of additional nodes was
applied, and then all points that fell within some
tolerance of any existing surface point were removed.
They extended the principles of Delaunay
triangularization to three dimensions in order to define
criteria for optimal tetrahedral volume elements. Using
their own custom software they generated tetrahedral
connectivities for each slice, and then concatenated all
the individual slices into the complete finite element
model.
The main people involved in this research are Chris
Johnson and Robert MacLeod. Some references to their
work and related areas are:
C.R. Johnson, R.S. MacLeod, and P.R. Ershler, A computer
model for the study of electrical current flow in the
human thorax, Computers in Biology and Medicine, in
press, 1992.
C.R. Johnson, R.S. MacLeod and Mike A. Matheson, Computer
simulations reveal complexity of electrical activity in
the human thorax, Computers in Physics, 6(3):230, 1992.
P.R. Ershler et al., Determination of three-dimensional
torso, heart, and electrode geometries from magnetic
resonance images, in IEEE Engineering in Medicine and
Biology Society, 10th Annual International Conference,
pp. 121-122, 1988.
D.T. Lee and B.J. Schacter, Int J Comp Inf Sci 9:219,
1980. (reference on Delaunay triangles)
Chris Johnson can be reached at the following mail
addresses:
crj@cs.utah.edu
Although I am not currently aware of a software package
that is capable of generating a surface discretization
from serial CT scans, I would be willing to bet that they
have custom fortran code to do very close to what you are
asking. It was not clear from your posting whether you
wanted just surface or volume discretization, so their
approach may be overkill.
There seems to be two different approaches for surface
reconstruction: a) only contour data points are available for
successive layers which are not necessarily equally spaced (see
Dr. Sadler's suggestion), or b) a 3-D volume data array is
available, say from CT or MRI. The second case can be dealt with
algorithms such as Mr. Karron's SpiderWeb, which can readily
handle bifurcations ("multi-furcations"?). The first case seems
to be more problematic when it comes to bifurcations. In any
case, I will not venture to make more comments until I read all
of the references listed above!
I would like to thank everyone for their contributions,
including those that I have not mentioned above. The unfortunate
conclusion from everyone's suggestions is that no public domain
software is available at this time for performing the task of
surface reconstruction from contour sections, but there does seem
to be a lot of interest for such routines. Several people have
offered to share their programs when they do get to develop them,
and I'd like to do the same. If anyone has suggestions please
let me know.
Sincerely,
Gerard A. Ateshian, Ph.D.
Assistant Professor of Mechanical Engineering
Columbia University, New York, NY, USA
ateshian@cuorma.orl.columbia.edu
Recently (8/11/92) I posted a query for public domain programs
which can reconstruct 3D surfaces from contour data, using
triangular tiles. I have received several requests from
individuals who have wanted me to share the results of my search,
so I'd like to give the following summary:
1) Dr. Michael S. Sacks and Dr. Matthias Eck have independently
mentioned a software called MOVIE.BYU, developed at the
Engineering Computer Graphics Laboratory, Brigham Young
University (801-378-2812). A subset of this software,
MOSAIC.BYU, can handle surface reconstructions from contours.
However, the opinions of these two researchers have differed as
to the success of that software. I called BYU to get additional
information and I found out that MOVIE.BYU has been superseded by
CQUEL.BYU ($1,500, or $750 with the educational discount), which
unfortunately does not contain MOSAIC.BYU in its current release
(but it will at a future date). I asked whether MOSAIC.BYU could
be purchased separately, but I have not received an answer yet.
2) Dr. Lewis L. Sadler has reported success using CAD software:
I don't know of any public domain software that does what
you want, but any CAD software can be used. We use three
or four different packages for this purpose and it is a
relatively simple task to enter the curves or splines at
a given magnification and to establish the distance
between layers (sections). The non-trivial task is in
the registration of these sections to each other. Unless
there is a built in fiducial or some convenient method of
re-establishing the relationship of the sections, it can
be a nightmare.
Good Luck, Lewis L. Sadler
3) Dr. Scott Selbie has mentioned that a good overview of the
problem is available in Computers and Graphics, 1989, vol 13, No.
3, Complex contour organization for surface reconstruction, B.
Sinclair et al.
4) Mr. Dan Karron has kindly provided me with a manuscript
describing his "SpiderWeb Algorithm for Surface Construction from
Medical Volume Data: Geometric Properties of its Surface," co-
authored with James L. Cox and Bud Mishra. I have found it easy
to read and conceptually straightforward to implement (but have
not done so yet). Mr. Karron's article is available by anonymous
ftp to karron.med.nyu.edu, and he welcomes any comments and/or
suggestions.
5) Mr. Jeff Weiss has generously contributed the following
message:
I am doing some finite element work on the knee joint,
and have looked into different mesh generation techniques
including CT scans. The closest thing that I have seen
to what you describe follows.
A group of researchers at the University of Utah have
been involved in modeling electrical activity in the
human thorax. To construct 3-D finite element models of
the thorax and the internal organs, they used 116 MRI
scans recorded in 5mm increments from just above the
pelvis to just above the shoulders. For each image, the
borders of the subcutaneous fat/muscle, the inner border
of the skeletal muscle, and the epicardial surface of the
heart were manually digitized. The points from each of
these layers were fit to a parametric, bicubic spline,
then regenerated at a constant spatial resolution. Some
smoothing was also applied to the data at this time.
Two adjacent layers formed a three dimensional slice.
Points from the same surfaces in both layers were then
laced into triangles according to an algorithm that
sought to construct optimal (Delaunay) triangles. This
methodology provided a complete surface model.
For their finite element model, tetrahedral volume
elements were used. To each layer of points obtained
previously to describe the boundarys of the different
tissues/organs, a regular grid of additional nodes was
applied, and then all points that fell within some
tolerance of any existing surface point were removed.
They extended the principles of Delaunay
triangularization to three dimensions in order to define
criteria for optimal tetrahedral volume elements. Using
their own custom software they generated tetrahedral
connectivities for each slice, and then concatenated all
the individual slices into the complete finite element
model.
The main people involved in this research are Chris
Johnson and Robert MacLeod. Some references to their
work and related areas are:
C.R. Johnson, R.S. MacLeod, and P.R. Ershler, A computer
model for the study of electrical current flow in the
human thorax, Computers in Biology and Medicine, in
press, 1992.
C.R. Johnson, R.S. MacLeod and Mike A. Matheson, Computer
simulations reveal complexity of electrical activity in
the human thorax, Computers in Physics, 6(3):230, 1992.
P.R. Ershler et al., Determination of three-dimensional
torso, heart, and electrode geometries from magnetic
resonance images, in IEEE Engineering in Medicine and
Biology Society, 10th Annual International Conference,
pp. 121-122, 1988.
D.T. Lee and B.J. Schacter, Int J Comp Inf Sci 9:219,
1980. (reference on Delaunay triangles)
Chris Johnson can be reached at the following mail
addresses:
crj@cs.utah.edu
Although I am not currently aware of a software package
that is capable of generating a surface discretization
from serial CT scans, I would be willing to bet that they
have custom fortran code to do very close to what you are
asking. It was not clear from your posting whether you
wanted just surface or volume discretization, so their
approach may be overkill.
There seems to be two different approaches for surface
reconstruction: a) only contour data points are available for
successive layers which are not necessarily equally spaced (see
Dr. Sadler's suggestion), or b) a 3-D volume data array is
available, say from CT or MRI. The second case can be dealt with
algorithms such as Mr. Karron's SpiderWeb, which can readily
handle bifurcations ("multi-furcations"?). The first case seems
to be more problematic when it comes to bifurcations. In any
case, I will not venture to make more comments until I read all
of the references listed above!
I would like to thank everyone for their contributions,
including those that I have not mentioned above. The unfortunate
conclusion from everyone's suggestions is that no public domain
software is available at this time for performing the task of
surface reconstruction from contour sections, but there does seem
to be a lot of interest for such routines. Several people have
offered to share their programs when they do get to develop them,
and I'd like to do the same. If anyone has suggestions please
let me know.
Sincerely,
Gerard A. Ateshian, Ph.D.
Assistant Professor of Mechanical Engineering
Columbia University, New York, NY, USA
ateshian@cuorma.orl.columbia.edu