koen@prisma.cv.ruu.nl (Koen Vincken) (03/12/91)
Since I couldn't find any algorithm for creating a volume model of a sphere
in a 3D image (or a collection of spheres) -- not in this newsgroup, nor in
some references mentioned in the Freq. Asked Questions -- I wrote my own
program. It is very simple, and very accurate.
(I may be wrong about the references, please correct me if I have invented
the wheel again).
The basic idea is to use a recursive octree-like method. Each voxel is given
a value proportional to the part inside the sphere:
(partial volume in sphere)
-------------------------- * (value of sphere)
(volume of one voxel)
Thus, only edge voxels of each sphere have to be checked for their partial
volume. This is done by counting the number of corner points of each voxel
that is inside the sphere (an edge voxel contains 1 to 7 corner points
inside a sphere).
Every edge voxel is subdivided into eight new subvoxels, after which every
subvoxel is subjected to the same test again. This subdividing will continue
until a certain depth is reached (this is the stop criterion). Then, the
location of the midpoint of such a subvoxel determines that subvoxel being
inside or outside the sphere.
For example, a depth of 1 means that no subdivision will take place, i.e.
a binary discretization will be the result. Since computation time grows
strongly with increasing depth, one must choose the smallest depth possible
for each application. I have made an accuracy table for some cases.
My experience is that for a volume rendered image of a sphere a depth of 3
is sufficient to avoid aliasing artefacts (the ugly circles on the surfaces).
If anyone is interested in this algorithm, or wants some more information
(e.g. what to do in case of 2 intersecting spheres), please e-mail me for
information.
The code is written in C, but also uses some image processing routines that
have become the standard here. However, with enough responses I'll post or
mail the most important part (the recursion), together with some piece of
pseudo-code.
Koen Vincken -- koen@cv.ruu.nl
/ / Koen Vincken, AZU E 02.222, Heidelberglaan 100,
/ / _ / ___/ \ / 3584 CX Utrecht, The Netherlands.
/ \ / / _/ / \ / e-mail: koen@cv.ruu.nl,
__/ _\ ____/ ____/ _/ _/ phone: +31-30-506711