Last update: June 17, 2000
Publications by Lee R. Nackman et al., on shape symmetry elicitation :
BibTeX references.
M. S. Karasick, D. Lieber, Lee R. Nackman, V. T. Rajan
Algorithmica 19(1/2), pp. 114-128, 1997
We describe an algorithm for the rapid display of three-dimensional Delaunay meshes (or selected portions thereof) on standard raster displays, without the use of special purpose graphics hardware. The algorithm allows the display of the interior structure as well as the surface of the mesh, and furthermore does not require that the meshed domain be convex, or even connected.
The algorithm computes a depth ordering on the mesh elements. This ordering can be used to display subsets of the mesh, as well as isosurfaces induced by fields represented on the mesh. Furthermore, by utilizing mesh coherence, the depth ordering can be used to view the mesh from front to back as well as back to front.
An implementation of the algorithm has been incorporated in a system for designing and analyzing the performance of three-dimensional semiconductor and electronic packaging structures. The system is in regular use and the mesh-display algorithm has been used to visualize both meshes and fields computed over the meshes.
Srinivasan, V., Nackman, L.R., Tang, J.M., Meshkat, S.N.
Proceedings of the IEEE, vol. 80, pp. 1485-1501, 1992.
Karasick, Michael, Lieber, Derek, Nackman, Lee R.
ACM Transactions on Graphics, Vol.10, No. 1 (Jan. 1991), pp. 71-91.
Many fundamental tests performed by geometric algorithms can be formulated in terms of finding the sign of a determinant. When these tests are implemented using fixed precision arithmetic such as floating point, they can produce incorrect answers; when they are implemented using arbitrary-precision arithmetic, they are expensive to compute. We present adaptive-precision algorithms for finding the signs of determinants of matrices with integer and rational elements. These algorithms were developed and tested by integrating them into the Guibas-Stolfi Delaunay triangulation algorithm. Through a combination of algorithm design and careful engineering of the implementation, the resulting program can triangulate a set of random rational points in the unit circle only four to five times slower than can a floating-point implementation of the algorithm. The algorithms, engineering process, and software tools developed are described.
General Terms:
Nackman, L.R., Stephen M. Pizer.
IEEE Transactions of PAMI, vol. 7, pp. 187-202, 1985.
Partitions an object into three types of primitives (not independent): width, axis & boundary primitives. Width primitives are described by representing the radius function of the SAT as the graph of a function of 2 parameters (since the SAT is generically a surface). This graph can be divided in slopes and/or curvature districts. Critical pts. of this graph are found and another representation is built: the Critical Point Configuration Graph (CPCG; a planar graph). To maintain information about the spatial juxtaposition of the 3 primitves, a Labeled Primitive Adjacency Graph is built.
Nackman, L.R.
IEEE Transactions of PAMI, vol. 6, pp. 442-450, 1984.
Keywords:
Lee R. Nackman
Computer Graphics and Image Processing, vol. 20, pp. 43-57, 1982.
A notion of radius curvature is defined and a relationship between symmetric axis curvature, radius curvature and boundary curvature is derived.
Assumption: Consider a simplified region, S (made of normal contact points), and the radius function, r (of maximal balls), are twice continuously differentiable at any normal point contact, P (second order contact).
Consider a unit vector X in the tangent plane to S at P, TpS. The 1st and 2nd directional derivatives of the radius function. r, at P in the direction X, r_x and r_xx, correspond to the 1st and 2nd derivatves of r w/r to arc length along the geodesic through P in the direction X.
NB: The geodesic through P in the direction X, is the unique curve on S such that its orthogonal projection on TpS is a line in the direction X. Geodesic are such that their (tangential) acceleration is null (they do not turn locally in TpS); in other words their acceleration is along the surface normal at P.
The 2nd directional derivative of the radius function, r_xx, assumes its extrema (max & min) in two orthogonal directions, alike the classical normal curvature of surfaces. Hence, these extrema of r_xx and associated (orthogonal) directions, are called, by analogy, principal curvatures and directions of the radius function.
where N_b and N_c are the normals to the two bounding surface patches defining the symmetry point P on S, such that these normals point away from P to the surface B and C.
This shows that r_xx takes a max and min in orthogonal directions in TpS.
where h and k are the Gaussian and Mean curvatures of the parallel surfaces to B (or C) passing through P (i.e., the wavefronts with sources B and C colliding at P).
NB: We directly have that : H = K (h/k - r)
h and k involved the principal curvatures of the symmetry sheet, S, and of the radius function, r. The former reflect the overall curvature trend of the two-sided piece, i.e., the degree to which the bounding surfaces curve in the SAME direction. Radius curvature, on the other hand, reflects the symmetry of the bouding surfaces about S, i.e., the degree to which both bounding surfaces curve in OPPOSITE directions. This is alike the derivations of Blum and Nagel for the 2D case.
The Gaussian and Mean curvatures, H and K, of the bounding surfaces can then be determined by nine (9) geometric measures:
Nackman, Lee R. (1982), PhD Thesis
Under the direction of Stephen M.
Pizer
Department
of Computer Science, College of Arts and Sciences
The University of North Carolina at Chapel Hill
Blum's transform, variously known as the symmetric axis transform, medial axis transform, or skeleton, and his associated two-dimensional shape description methodology are generalized to three-dimensions. Bookstein's two-dimensional algorithm for finding an approximation to the symmetric axis is also generalized.
The symmetric axis (SA) of an object with a smooth boundary is the locus of points inside the object having at least two nearest neighbors on the object boundary. In three dimensions, the SA is, in general, a collection of smooth surface patches, called simplified segments, connected together in a tree-like structure. Together with the radius function, the distance from each point on the SA to a nearest boundary point, the SA forms the symmetric axis transform. The three-dimensional symmetric axis transform defines a unique, coordinate-system-independent decomposition of an object into disjoint, two-sided pieces, each with its own simplified segment and associated object boundary patches.
Four principal contributions are presented. (1) A relationship among the Gaussian and mean curvatures of a simplified segment, the Gaussian and mean curvatures of the associated object boundary patches, and radius function measures is derived. (2) A further decomposition is proposed wherein each two-sided piece is partitioned into primitives drawn from three separate, but not completely independent, primitive sets: width primitives, boundary primitives, and axis primitives. Width primitives are regions derived from derivatives of the radius function; hence, they capture the behavior of the boundary patches with respect to the simplified segment. Axis and boundary primitives are regions of constant signs of Gaussian and mean curvatures of the simplified segment and boundary patches respectively. The aforementioned curvature relationship is used to derive relationships among the primitive sets. (3) In the course of studying width primitives, it is proved that, under certain non-degeneracy assumptions, the regions of the graph defined by the critical points, ridge lines, and course lines of a scalar valued function over a surface have one of three types of cycle as boundary. (4) An almost linear algorithm that takes a polyhedral approximation to a three-dimensional object and yields a polyhedral surface approximation to that object's SA is developed.
Page created & maintained by Frederic Leymarie,
2000.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu