J. Jang and J. Rossignac J. Rossignac
GVU Tech Report GIT-GVU-07-12. PDF
Hierarchies of patterns of features, of subassemblies, or of CSG sub-expressions are used in CAD to eliminate laborious repetitions from the design process. Yet, often the placement, shape, or even existence of a selection of the repeated occurrences in the pattern must be adjusted. The specification of a desired selection is often tedious or difficult. OCTOR introduced here addresses these two drawbacks, offering an intuitive solution, which requires only two mouse-clicks.
G. Slabaugh, G. Unal, T. Fang, J. Rossignac, B. Whited
Geometric Modeling and Processing 2008. Springer. PDF
This paper considers the problem of computing an interpolating envelope of an ordered set of 2D balls. By construction, the envelope is constrained to be C^1 continuous, and for each ball, it touches the ball at a point and is tangent to the ball at the point of contact. Using an energy formulation, we derive differential equations that are designed to minimize the envelope's arc length and/or curvature sub ject to these constraints. Given an initial envelope, we update the envelope's parameters using the differential equations until convergence occurs. We demonstrate the method's usefulness in generating interpolating envelopes of balls of different sizes and in various configurations.
B. Whited, J. Rossignac, G. Slabaugh, T. Fang, G. Unal
2007. PDF
We introduce a segmentation technique, called Pearling, for the semi-automatic extraction of idealized models of networks of strokes (variable width curves) in images. These may roads, vessels, or pen-strokes. The operator selects representative areas of good and bad colors and provides a rough trace or simply pick a starting point. Pearling computes the centerlines, bifurcations, and thickness function along each stroke. Simple gestures are used to trim or extend branches. By design, the idealized pearl string model is slightly wider than necessary to ensure that it contains the stroke boundary. The curst is the difference between the pearl string and its core (a narrower core model that fits inside the stroke). The crust contains the boundary of the stroke and may be used to capture, compress, visualize, or analyze the raw image data along the stroke boundary, rather than a single curve through it. -
B. Whited, J. Rossignac, A. Lieutier, F. Chazal,
2007. PDF
We investigate tools for comparing and morphing between pairs of registered, nearly similar shapes, P and Q. The traditional (closest point) c-morph moves a point p of P at constant velocity towards a closest point q on Q. Our new (tangent ball) b-morph moves each point along a circular arc incident orthogonally onto both P and Q. The b-morph has several advantages over the c-morph: it is symmetric, orientation sensitive, and yields smaller travel distance and distortion. It may help to measure and exaggerate the discrepancy between shapes, morph shapes and their textures, represent one shape as the offset of another, and register shapes. We provide an algorithm for computing b-morphs of b-compatible 2D shapes and extend it to incompatible shape-pairs through recursive b-rounding.
J. Rossignac.
2007. PDF. Chapter in the Wiley Encyclopedia of Electrical and Electronics Engineerig. Ed. J. Webster.
This is a summary of the field of Solid and Physical Modeling. It introduces topology concepts and reviews the 10 most popular representation schemes and associated issues. It discusses how to build, compress, simplify, and refine triangulated boundary models. It reviews the basics of Constructive Solid Geometry (CSG) and presents advances (Active Zones, Bist Form), and their use for hardware-assisted CSG rendering and Constructive Solid Trimming (CST). It points out the importance and challenges of supporting features, parameterization, and constraints. It discusses shape deformations, Minkowski operations (growing, rounding, tightening), and resampling. Finally, it illustrates the benefits of 3D input devices for viewing and editing shapes and assembies.
L. Ibarria, P. Lindstron, J. Rossignac.
Journal of Computers, 2(8), 2007. PDF
Scientific, imaging, and geospatial applications produce large scalar fields sampled on a regular grid. Lossless compression of such data uses predictive coding. In hierarchical, incremental, or selective transmission, the spatial pattern of the known neighbors is irregular. To make the best use of known neighboring samples, we propose a spectral predictor that offers optimal prediction by tailoring the weights to each configuration of known nearby samples. We show that it improves compression for various sources of high-precision data.
F. Chazal, A. Lieutier, and J. Rossignac.
Int. J. of Computational Geometry & Applications (IJCGA), 17(5)403-421 Oct. 2007
Revised version of GVU Tech Report GIT-GVU-04-28. PDF
MODELING - SHAPE MAPPING - NORMAL-OFFSETTING - CLOSEST PROJECTION
Two manifolds, A and B, are normal-compatible if their Hausdorff distance is less than c times the smallest of their minimum feature size. The constant c is 2-sqrt(2).
When A and B are normal-compatible: each can be expressed as a normal offset of the other and their Hausdorff distance equals their Frechet distance.
The closest projection and its inverse, the OrthoMap, are homeomorphisms for normal-compatible manifolds in any dimension.
J. Williams, J. Rossignac.
Int. J. of Computational Geometry and Applications (IJCGA), 17(5)487-503, Oct. 2007. PDF
The mortar of a shape is the morphological closing of its boundary. We simplify the shape by tightening its boundary (reducing the perimeter in 2D or the surface area in 3D) inside the mortar. We discuss 2D and 3D algorithms for tightening.
Single ventricle congenital heart defects afflict 2/1000 children. They are surgically treated by connecting the superior and inferior vena cavae to the pulmonary arteries, which produces high energy losses. Hence optimization of the geometry of this connection could significantly improve post-operative performance. We propose a surgical planning framework, in which a pediatric surgeon performes a "virtual surgery" on the reconstruction of the patient's anatomy. The hemodynamics in the modified anatomy is simulated using computational fluid dynamics. The surgeon can explore se3veral surgical options, and compare their predicted post operative hemodynamics.
J. Rossignac, B. Whited, G. Slabaugh, T. Fang, G. Unal
MICCAI workshop on Interaction in Medical Image Analysis and Visualization, Nov. 2007. PDF
Pearling is a novel 3D approach to the interactive segmentation and modeling of tubular structures from a volumetric image. Given a user-supplied initialization, Pearling extracts runs of pearls (balls), where each pearl is specified by a center position and radius. The runs are combined into a graph, with bifurcations and possibly loops. By treating each pearl's center and radius parameters as a control point in 4D space, a continuous tubular model is defined via subdivision. We show that Pearling is both computationally efficient and flexible, providing a convenient mechanism for fast, interactive segmentation of a portion of interest in a tubular network.
J. Rossignac, B. Whited, G. Slabaugh, T. Fang, G. Unal
This paper introduces a novel image segmentation technique, called Pearling, for identifying tubular structures in images. Examples of such structures include, but are not limited to, blood vessels, bones, roads, rivers, electrical wirings, and brush-strokes. Pearling allows the user to extract a higher level parametric representation of each tube or of a net- work of tubes. This representation is comprised of an ordered series of pearls, each defined by the location of its center, by its radius. A final model of the tube is then obtained by estimating continuous functions that inter- polate the discrete series of pearls. Pearling is computationally efficient and well suited to user interactivity. We demonstrate its effectiveness in segmentation of medical images of different modalities as well as satellite imagery.
A. Selle, R. Fedkiw, B. Kim, Y. Liu, J. Rossignac
Journal of Scientific Computing. PDF
The back and forth error compensation and correction (BFECC) method advects the solution forward and then backward in time. The result is compared to the original data to estimate the error and to correct the data before advection, raising the method to second order accuracy. We rewrite the MacCormack method to compare it to the BFECC showing that it uses this error estimate to correct the already computed forward advected data. Thus, it does not require the third advection step of the BFECC, reducing the cost of the method while still obtaining second order accuracy in space and time.
J. Rossignac
GVU Tech Report GIT-GVU-07-10. PDF
Let E be a positive-form Boolean expression with n literals. Let s(n) be the number of steps (operations) and b(n) of bits needed to evaluate E. We propose a new Optimized Blist Form (OBF) that requires only s(n)=n steps and b(n)=log2j bits, where j=log2(2n/3+2). We discuss three applications: (1) Direct CSG rendering, where candidate surfels are each classified against arbitrarily complex Boolean expressions using only 6 stencil bits; (2) Logic Matrix (LM), which evaluates E in one cycle useing a matrix of nxj wires/lines; and (3) Logic Pipe (LP), which uses n gates connected by a pipe of log2j lines and when receiving a staggered stream of input vectors produces a new value of E per cycle.
A. Chica, J. Williams, C. Andujar, P. Brunet, I. Navazo, J. Rossignac, A. Vinacua
The Eurographics Computer Gaphics Forum (CGF).
GVU Tech Report GIT-GVU-07-09. PDF
Pressing, smoothes isosurfaces extracted from binary volumes, while recovering their large planar regions (flats). It uses global optimization to identify flats. It recovers sharp edgess and uses constrained bilaplacian smoothing to fair the rest. The resulting surface correctly separate IN and OUT grid samples and usually is is an accurate approximation of the original shape. The resulting segmentation into flat and curved faces and the sharp/smooth labelling of their edges may be valuable for shape recognition, simplification, compression, and various reverse engineering and manufacturing applications.
B.M. Kim, Y. Liu, I. Llamas, X. Jiao, J. Rossignac
ACM Trans. on Graphics (TOG). Proc. SIGGRAPH 2007.
GVU Tech Report GIT-GVU-07-08. PDF
Liquid and gas interactions often contain bubbles that stay on the surfacewithout bursting, making a dry foam structure. Such long lasting bubbles simulated by the level set method can suffer from a slow but steady volume error that accumulates to a visible amount of volume change. We address this problem by using the volume control method. We track the volume of each connected region, and apply a carefully computed divergence that compensates undesired volume changes. To compute the divergence, we construct a mathematical model of the volume change, choose control strategies that regulate the modeled volume error, and establish methods to compute the control gains that provide robust and fast reduction of the volume error, and (if desired) the control of how the volume changes over time.
L. Ibarria, P. Lindstron, J. Rossignac.
Data Compression Conference, 163-172, March 2007
GVU Tech Report GIT-GVU-07-07. PDF
Many applications produce large high-precision scalar fields sampled on a regular grid. Lossless compression uses weighted combinations of previously coded samples known to both encoder and decoder to predict subsequent nearby samples. In hierarchical, incremental, or selective transmission, the spatial pattern of the known neighbors is often irregular and varies from one sample to the next, which precludes prediction based on a single stencil and fixed set of weights. To handle such situations and make the best use of available neighboring samples, we propose a local spectral predictor that offers optimal prediction by tailoring the weights to each configuration of known nearby samples. These weights may be precomputed and stored in a small lookup table. We show that predictive coding using our spectral predictor improves compression for various sources of high-precision data.
J. Rossignac, S. Schaefer.
GVU Tech Report GIT-GVU-07-06. PDF
The Js refinement proposed here blend the four-point and the cubic B-spline subdivision rules and yield a family of curves parameterized by s with different smoothness (C2 for 0
J. Rossignac, J.J. Kim, S.C. Song, K.C. Suh, C.B. Joung
Computer-Aided Design 39(9):745-755, 2007.
GVU Tech Report GIT-GVU-06-19. PDF
The swept volume of a moving solid provides an excellent aid for path and accessibility planning in robotics and for simulating various manufacturing operations. To compute the boundary of the swept volume, we approximate the motion by a polyscrew (continuous, piecewise-screw), generate candidate faces, compute the two-cells of their arrangement, and use a new point-in-sweep test to select the correct cells whose union forms the boundary of the swept volume.
J. Rossignac
GVU Tech Report GIT-GVU-06-18.
This technical report was delayed and is now available as
Optimized Blist Form (OBF)
J. Rossignac. GVU Tech Report GIT-GVU-07-10. PDF
B.M. Kim, Y. Liu, I. Llamas, J. Rossignac
IEEE Trans. on Visualization and Computer Graphics, 2006
GVU Tech Report GIT-GVU-06-17. PDF
Back and Forth Error Compensation and Correction (BFECC) can be applied to reduce dissipation and diffusion in advection steps, such as velocity, smoke density, and image advections. It can be implemented trivially as a small modification of the first-order upwind or semi-Lagrangian integration of advection equations. It provides second-order accuracy in both space and time and reduces volume loss significantly. We demonstrate its benefits on the simulation of smoke, bubbles, and interaction between water, a solid, and air. Video
John Hable, J. Rossignac
IEEE Trans. on Visualization and Computer Graphics, 13(5):1004-1014, 2007. GVU Tech Report GIT-GVU-06-16. PDF
To eliminate the need to evaluate the intersection curves in surface cutouts or in trimmed faces of BReps, we advocate using Constructive Solid Trimming (CST). A CST face is the intersection of a surface with a Blist representation of a trimming CSG volume. We propose a new, GPU-based, CSG rendering algorithm, which trims the boundary of each primitive using a Blist of its Active Zone. This approach is faster than the previously reported Blister approach, eliminates occasional speckles of wrongly colored pixels, and provides additional capabilities: painting on surfaces, rendering semitransparent CSG models, and highlighting selected features.
J. Rossignac, K. Pekkan, B. Whited, K. Kanter, S. Sharma, A. Yoganathan
GVU Tech Report GIT-GVU-06-15. PDF
Surgem is a surgical planning tool for editing complex patient-specific anatomies and for interfacing with computational fluid dynamics (CFD) analysis. Novel two-hand, shape editing technologies are applied to design and evaluate possible modifications of patient-specific anatomies of congenital heart defects.
F. Chazal, A. Lieutier, J. Rossignac, B. Whited
GVU Tech Report GIT-GVU-06-05. PDF
We introduce the ball-map, BMS,T, between two manifolds, S and T. It maps each point x of S to a point x = BMS,T(x) of T. Its inverse is BMT,S. We define conditions for BMS,T to be a homeomorphism. We show that they hold when the minimum feature size of each surface exceeds their Hausdorff distance. We show that, when S and T are Ck (n-1)-manifolds in Rn, BMT,S is a Ck-1 diffeomorphism and defines a Ck-1 ambient isotopy that smoothly morphs between S to T. In practice, the ball-map yields an excellent map for transferring parameterizations and textures between ball compatible curves or surfaces. Furthermore, it may be used to define a morph, during which each point x of S travels to the corresponding point y of T along a circular arc that is normal to S at x and to T at y.
Alex Powell and Jarek Rossignac
IEEE Computer Graphics and Applications
GVU Tech Report GIT-GVU-05-05. (Initial, Final)
Interpolating the consecutive poses taken by an object during its motion yields a polyscrew motion that is continuous, but usually not smooth at the poses. We propose a very simple polyscrew subdivision scheme for smoothing a polyscrew motion. It extends the polygonal Split&Tweak subdivision to polyscrews. Subdivision and animation of polyscrew is trivial to mplement and works in realtime.
Ghassan Al-Regib, Yussel Altunbasak, and Jarek Rossignac.
IEEE Transactions on Multimedia, 7(4)766:767, August 2005. PDF
We present a packet-loss resilient system for the transmission of progressively compressed 3D models. It is based on a joint source and channel coding approach that trades off geometry precision for increased error resiliency to optimize the decoded model quality on the client side. We derive a theoretical framework for the overall system by which the channel packet loss behavior and the channel bandwidth can be directly related to the decoded model quality at the receiver. First, the 3-D model is progressively compressed into a base mesh and a number of refinement layers. Then, we assign optimal forward error correction code rates to protect these layers according to their importance to the decoded model quality.
B.M. Kim, Y. Liu, I. Llamas, J. Rossignac
Eurographics Workshop on Natural Phenomena. September 2005.
GVU Tech Report GIT-GVU-05-24. PDF
We propose a new physical simulation technique that strikes a compromise between accuracy, simplicity, and speed. The Back and Forth Error Compensation and Correction (BFECC) technique provides such a compromise. It reduces dissipation/diffusion of the momentum, density, or any other peoperty advected along the flow. It avoids the need for particle tracing when simulating the liquid/solid or liquid/air interfaces while preventing volume loss and undesirable advection.
ByungMoon Kim and Jarek Rossignac
Computer Graphics Forum, 24(3):295-302. Proc. Eurographics, September 2005.
By combining previously proposed implicit and explicit formulations, we develop a second order filter that can be used for lowpass, bandpass, highpass, notch, and band exaggeration or attenuation for triangle meshes. The dimensions of an ellipsoid that is automatically fit to a user-selected feature in the mesh may be used to define the parameters for the filter. For example, the size of a bump in a noisy pattern can be used as a cutoff frequency in a lowpass filter, while the size of a nose may be used to smoothen a face or to exaggerate its features as in a caricature.
Jarek Rossignac
The Visual Computer, 21:985-996, 2005.
Much research was focused on reducing shape complexity. But, what exactly is it? We discuss several complexity measures and the corresponding complexity reduction techniques: Algebraic complexity, Topological complexity, Morphological complexity, Combinatorial complexity, and Representational complexity.
Hendrik Mueller and Jarek Rossignac.
Central Europe Multimedia and Virtual Reality Conference, June 2005.
GVU Tech Report GIT-GVU-04-19. PDF
PhotoMeter is an effective and very easy-to-use interactive system for extracting 3D measures from a single uncalibrated photograph. With a mouse click, the user may easily measure vertical and horizontal dimensions of doors, windows, furniture, corridors, and even people.
John Hable and Jarek Rossignac
ACM Transactions on Graphics, Proceedings of SIGGRAPH 2005.
Complex Constructive Solid Geomatry (CSG) models may be rendered in realtime using the GPU to peel the arrangement of the CSG primitives one layer at a time and to classify the candidate surfels of the current layer against the Blist formulation of the CSG expression.
Yong Chen, Hongqing Wang, David Rosen, Jarek Rossignac
ASME Design Engineering Technical Conferences, DETC05/DAC-85408, 533-542. September 2005.
Rounds and fillets are important design features. We introduce a new point-based method for constant radius rounding and filleting. Based on the mathematical definitions of offsetting operations, discrete offsetting operations are introduced. Steps of our approach are discussed and analyzed. The methodology has been implemented and tested. We present the experimental results on accuracy, memory and running time for various input geometries and radius. Based on the test results, the method is very robust for all kinds of geometries.
Yong Chen, Hongqing Wang, David Rosen, Jarek Rossignac
Submitted, May 2005.
We introduce a fast and simple method for offsetting (growing and shrinking) a polyhedral model by an arbitrary distance r. Our approach is based on a hybrid data structure combining point samples, voxels, and continuous surfaces. Each face, edge, and vertex of the original solid generate a set of offset points spaced along the (pencil of) normals associated with it. The offset points and normals are sufficiently dense to ensure that all voxels between the original and the offset surfaces are properly labeled as either too close to the original solid or possibly containing the offset surface. Then the offset boundary is generated as the isosurface using these voxels and the associated offset points. We provide a tight error bound on the resulting surface and report experimental results on a variety of CAD models.
Ghassan Al-Regib, Yucel Altunbasak, Jarek Rossignac
ACM Transactions on Graphics, 24(2)182:208. April 2005.
We provide an overview of error protection schemes and discuss their application to the transmission of multiresolution models over lossy channels. We reduce distortion rates by optimizing the bit allocation between source and channel and between the consecutive refinement batche.
Jason Williams and Jarek Rossignac
Graphical Models, 67(4)285:303, 2005.
GVU Tech Report GIT-GVU-04-05. PDF
The mortar of a shape (2D area or 3D solid) is the alpha-hull (i.e., morphological closing) of its boundary. We simlify a shape S by adding or removing each connected component of its mortar. The choice minimizes changes of area (in 2D) or of volume (in 3D). The result is usually regular (has bounded least feature size) and smooth (has bounded curvature) almost everywhere. We demoustrate the approach on binary images in 2D and on binary volumetric models in 3D.
Marco Attene, Bianca Falcidino, Michela Spagnuolo, Jarek Rossignac
IEEE Transactions on Visualization and Computer Graphics (TVCG), vol 11, no 2, pp 181-192, March/April 2005.
GVU Report GIT-GVU-03-34. PDF
Feature-insensitive samplings of a surface tesselate smooth faces and replace sharp edges by chamfer irregular triangles. We provide a very simple and automatic procedure for extracting sharp features and for subdividing the tesselation so as to restore the smooth faces and bend the sharp edges into smooth curves while maintaining their sharpness.
Urs Bischoff and Jarek Rossignac
Data Compression Conference (DCC), 93-102, March 2005.
GVU Tech Report GIT-GVU-04-26. PDF
We compress the connectivity of a tetrahedron-mesh to less than 2 bits per tetrahedron while transmitting it in back-to-front visibility order, which supports streaming for volumetric visualization with a small footprint, since the client needs only maintain a Corner Table representaiton of a triangle-mesh that is swept through the tetrahedron-mesh.
Ignacio Llamas, Alex Powell, Jarek Rossignac, Chris Shaw.
ACM Symposium on Solid and Physical Modeling (SPM). pp. 89-99, June 2005.
GVU Tech Report GIT-GVU-04-25. PDF
Holding a polhemus tracker in each hand, the designer manipulates a virtual ribbon and uses it to grab, bend, and twist portions of the model. We demonstrate the versatility of this intuitive operation and its application to surgery planning.
Jason Williams and Jarek Rossignac.
ACM Symposium on Solid and Physical Modeling (SPM). pp. 107-112, June 2005.
GVU Tech Report GIT-GVU-04-27. PDF
The mortar of a shape (2D area or 3D solid) is the alpha-hull (i.e., morphological closing) of its boundary. We simlify the shape by tightening its boundary (reducing the perimeter in 2D or the surface area in 3D) inside the mortar. The tightening procedure, which must support topological changes is implemented as a constrained curvature flow using a level set approach.
F. Chazal, A. Lieutier, and J. Rossignac.
ACM Symposium on Solid and Physical Modeling (SPM). pp. 9-14, June 2005.
GVU Tech Report GIT-GVU-04-28. PDF
MODELING - SHAPE MAPPING - NORMAL-OFFSETTING - CLOSEST PROJECTION
Two manifolds, A and B, are conforming if their Hausdorff distance is less than c times the smallest of their minimum feature size. The constant c is 2-sqrt(2).
When A and B are conforming: each can be expressed as a normal offset of the other and their Hausdorff distance equals their Frechet distance.
The closest projection and its inverse, the OrthoMap, are homeomorphisms for conforming manifolds in any dimension.
Jarek Rossignac
in Handbook of Discrete and Computational Geometry (2nd edition), CRC Press, Goodman and O'Rourke Edts. 2004. Chap. 54.
A theoretical introduction, some practical implementations, and a comparative overview of various simplification, resampling, compression, and progressive refinement techniques for triangle meshes.
Jarek Rossignac.
Computer-Aided Design Journal (CAD), Vol 36/14 pp 1461-1469, 2004.
GVU Tech Report GIT-GVU-03-26. PDF
Clear and elegant formulations of prior research results whould be valued as significant research contributions, since they facilitate learning and further research We illustrate the impact of such an Education Driven Research (EDR) approach on subdivision for curves and surfaces, on pointset toplogy for solid modeling, and on the computation of Hausdorff distances for modeling and graphics.
ByungMoon Kim and Jarek Rossignac GVU Tech Report GIT-GVU-04-12. PDF
Partial differential equations (PDEs) with Laplacian or bi-Laplacian terms defined over a surface may be used for mesh fairing, smoothing, surface editing, and simulation. We adapt a finite element method to solve these PDEs directly on the triangle mesh connectivity graph. The solver can be restricted to operate on a sub-domain, which is a portion of the surface defined by user or automatically self-adjusting. Our formulation permits to solve high order terms such as bi-Laplacian by using a simple linear triangle element. We demonstrate the benefits of our approach on two applications: scattered data interpolation over a triangle mesh(painting), and haptic interaction with a deformable surface.
C. Andujar, P. Brunet, A. Chica, J. Rossignac, I. Navazo, A. Vinacua
Computer Graphics Forum 23, pp. 401-410. Proc. Eurographics, September 2004. PDF
We provide an efficient algorithm for recovering large planar faces from discrete (i.e. voxelized binary) 3D models. We show that these planes may be used successfully to support imposters for an image-based graphic acceleration.
Volker Coors and Jarek Rossignac.
The Visual Computer. 20(8-9)507-520, 2004.
GVU Tech Report GIT-GVU-03-30. PDF
Both geoemtry and connectivity are predicted from previously transmitted parts of a triangle-mesh. The parallelogram rule is used to predict the tip of each new triangle during the EdgeBreaker compression. When the predicted tip lies sufficiently close to a border vertex of the previously decoded part, the corresponding Edgebreaker symbol (L,E,R,S) is guessed. Otherwise, the C symbol (meaning new vertex) is guessed. A confirmation bit is transmitted, followed by a correction when the guess was wrong.
M. Mortara, G. Patane, M. Spagnuolo, B. Falcidieno, J. Rossignac.
ACM Symposium on Solid Modeling, 339-344, 2004 (Short paper).
GVU Tech Report GIT-GVU-03-26. PDF
TRIANGLE-MESH - MODELING - SHAPE SEGMENTATION - FEATURE IDENTIFICATION
A triangle-mesh is automatically decomposed into bodies, tubes, joints, and tips.
The decomposition uses the length and topology of the intersection of the mesh with a sphere of a given radius to identify vertices susceptible to lie on tubes.
Then, connected components of triangles boundd by these vertices are filtered to remove noise.
Those having the topology of a cylinder are shrunken and grown back into a tube.
The process may be applied with increasing radius to obtain a multi-resolution decomposition.
M. Mortara, G. Patane, M. Spagnuolo, B. Falcidieno, and J. Rossignac.
Algorithmica. 38(1):227-248 January 2004.
GVU Tech Report GIT-GVU-03-27.PDF
We propose a multi-resolution approach for the automatic decomposition of a surface into flats, limbs, tips, pits, and blends that transition between them. Our approach is based on blowing a spherical bubble at each vertex and studying how the intersection of that bubble with the surface evolves. We describe an efficient approach for computing these characteristics for a sampled set of bubble radii and for using them to identify features, based on easily formulated filters, that may capture the needs of a particular application.
C. Andujar, P. Brunet, A. Chica, I. Navazo, J. Rossignac, A. Vinacua.
Proc. CAD Conf. pp. 503-511, Thayland, May 2004.
The portion P of the iso-surface inside a cube C may consist of one or more connected components, which we call sheets. We distinguish three types of decisions in the construction of the iso-surface connectivity: (1) how to split the with alternating in/out samples, (2) how many sheets to use in a cube, and (3) how to triangulate each sheet. Previously reported techniques make these decisions based on local criteria, We propose global strategies for optimizing several topological and combinatorial measures of the iso-surfaces: triangle count, genus, and number of shells.
CAD'04 Best Paper Award.
C. Andujar, P. Brunet, A. Chica, I. Navazo, J. Rossignac, A. Vinacua.
Journal of Computer-Aided Design & Applications, 37(8):847-857, 2005.
A Journal version of the award-winning "Optimal Iso-Surfaces" paper.
Jarek Rossignac.
Chapter in the Visualization Handbook. Academic Press. Eds. C. Hansen and C. Johnson.
GVU Tech Report GIT-GVU-03-21.PDF
TRIANGLE MESHES - COMPRESSION
A comparative overview of various compression and progressive refinement techniques for triangle meshes.
T. Lewiner, H. Lopes, J. Rossignac and A. Wilson-Vieira1.
SIBGRAPI/SIACG,218-255, 2004. PDF
Edgebreaker and Spirale Reversi are examples of efficient schemes to compress and decompress the connectivity of triangle-mesnes. Here, we extend their simple implementaiotn to surfaces with multiple components, handles, and multiple bounding loops, allowing a direct representation of the surface topology, guaranteeing a linear, one-pass process and improving the Edgebreaker's code entropy. The result is a simple and efficient compression/decompression solution for the broad class of orientable manifold surfaces.
Easy-to-use MonoGraphoMetrics-Visual Metrology from Calibrated Images, Hendrik Mueller
(Master's Thesis) supervised by Jarek Rossignac and Markus Wacker. July 2004. PDF
Hendrik's Master's Thesis with a very nice overview of MonoGraphoMetrics and a detailed discussion and analysis of the PhotoMeter system for erforming 3D measurements from a single photograph.
J. Rossignac. Tutorial Notes. Eurographics 2004.
A lecture on geoemtry compression.
M. Attene, B. Falcidieno, M. Spagnuolo and J. Rossignac.
ACM Transactions in Graphics, 22(4):982-996, October 2003.
GVU Tech Report GIT-GVU-02-04. PDF
SwingWrapper partitions a mesh M into simply connected triangloids, each corresponding to a triangle in the new mesh M'. By construction, the connectivity of M' is fairly regular and can be compressed to less than a bit per triangle using EdgeBreaker. The locations of the vertices of M' are compactly encoded with our new prediction technique, which uses a single correction parameter per vertex. For a variety of popular models, a rate of 0.4 bits/triangle yields an L2 distortion of about 0.01% of the bounding box diagonal.
Alla Safonova and Jarek Rossignac.
Computer-Aided Design, Volume 35, Issue 6, Pages 533-547, May 2003.
GVU Tech Report GIT-GVU-01-05. PDF
Consider a polygonal curve P in 3D of n vertices, generated through adaptive sampling, so that it approximates an original curve, O, within tolerance e0. We present an efficient algorithm for computing a continuous curve C that approximates P within tolerance e1 and is composed of a chain of m circular arcs, whose end-points coincide with a subset of the vertices of P. We represent C using 5m+3 scalars and a typical total of less than 7.5n bits. We observe compression ratios that vary between 15:1 and 36:1
Lutz Kettner, Jarek Rossignac, Jack Snoeyink.
Computational Geometry Theory and Applications (CGTA), vol. 25. No 1-2, pp. 97-116, 2003.
GVU Tech Report GIT-GVU-01-13. PDF
We describe a geometric basis for the visualization of time-varying volume data of one or several variables as they occur in scientific and engineering applications. We demonstrate a prototype interface for gridded data, extending the contour spectrum interface of Bajaj, Pascucci, and Schikore to higher dimensions and to topological properties that are not decomposable.
Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares.
Computers&Graphics International Journal, Vol. 27, No. 4, pp. 553-567, 2003.
Edgebreaker is an efficient scheme for compressing triangulated surfaces. A surprisingly simple implementation of Edgebreaker has been proposed for surfaces homeomorphic to a sphere. It uses the Corner-Table data structure, which represents the connectivity of a triangulated surface by two tables of integers, and encodes them with less than 2 bits per triangle. We extend this simple formulation to deal with triangulated surfaces with handles and present the detailed pseudocode for the encoding and decoding algorithms (which take one page each). We justify the validity of the proposed approach using the mathematical formulation of the Handlebody theory for surfaces, which explains the topological changes that occur when two boundary edges of a portion of a surface are identified.
Marco Attene, Bianca Falcidieno, Jarek Rossignac, and Michela Spagnuolo.
Eurographics Symposium on Geometry Processing (SGP). Aachen, Germany. June 2003.
GVU Tech Report GIT-GVU-03-19. PDF
3D scanners, iso-surface extraction procedures, and several recent geometric compression schemes sample surfaces of 3D shapes in a regular fashion, without any attempt to align the samples with the sharp edges and corners of the original shape. Consequently, the interpolating triangle meshes chamfer these sharp features and thus exhibit significant errors. The new Edge-Sharpener filter introduced here identifies the chamfer edges and subdivides them and their incident triangles by inserting new vertices and by forcing these vertices to lie on intersections of planes that locally approximate the smooth surfaces that meet at these sharp features. This post-processing significantly reduces the error produced by the initial sampling process. For example, we have observed that the L2 error introduced by the SwingWrapper remeshing-based compressor can be reduced down to a fifth by executing Edge-Sharpener after decompression, with no additional information.
L. Ibarria and J. Rossignac.
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), pp. 126-135, San Diego, July 2003.
GVU Tech Report GIT-GVU-03-08. PDF
Dynapack exploits space-time coherence to compress the consecutive frames of the 3D animations of triangle meshes of constant connectivity. We introduce here two extrapolating spacetime predictors: the ELP extension of the Lorenzo predictor, developed originally for compressing regularly sampled 4D data sets, and the Replica predictor. ELP may be computed using only additions and subtractions of points and is a perfect predictor for portions of the animation undergoing pure translations. The Replica predictor is slightly more expensive to compute, but is a perfect predictor for arbitrary combinations of translations, rotations, and uniform scaling.
Sebastien Valette, Jarek Rossignac, Remy Prost.
IEEE International Conference on Image Processing (ICIP), 777-780, 2003.
GVU Tech Report GIT-GVU-03-20. PDF
Wavemesh is a powerful scheme for 3D triangular mesh processing. In sharp contrast with other approaches using wavelets for mesh compression which apply only to meshes having subdivision connectivity, Wavemesh can simplify, approximate, and compress meshes even if they do not respect this constraint, with unmatched results for progressive lossless compression when compared to other approaches. We propose in this paper an improvement for our scheme : higher efficiency for meshes with large subdivision connectivity sets, as shown by experimental results. Also, in some cases, wavemesh can even perform better than mono-resolution approaches in terms of connectivity compression.
Ignacio Llamas, Byungmoon Kim, Joshua Gargus, Jarek Rossignac, and Chris D. Shaw.
ACM Transactions on Graphics (TOG),
Proc. ACM SIGGRAPH. Volume 22, Issue 3, pp. 663-668, July 2000.
GVU Tech Report GIT-GVU-03-18. PDF
A free-form deformation that warps a surface or solid may be specified in terms of one or several point-displacement constraints that must be interpolated by the deformation. The Twister approach introduced here, adds the capability to impose an orientation change, adding three rotational constraints, at each displaced point. Furthermore, it solves for a space warp that simultaneously interpolates two sets of such displacement and orientation constraints. With a 6 DoF magnetic tracker in each hand, the user may grab two points on or near the surface of an object and simultaneously drag them to new locations while rotating the trackers to tilt, bend, or twist the shape near the displaced points. Using a new formalism based on a weighted average of screw displacements, Twister computes in realtime a smooth deformation, whose effect decays with distance from the grabbed points, simultaneously interpolating the 12 constraints. It is continuously applied to the shape, providing realtime graphic feedback. The two-hand interface and the resulting deformation are intuitive and hence offer an effective direct manipulation tool for creating or modifying 3D shapes.
Isabel Navazo, Jarek Rossignac, Joan Jou, Rahim Shariff.
Computer Graphics Forum 22(3):291-302. Proc. of Eurographics, 2003.
GVU Tech Report GIT-GVU-03-14. PDF
We present a novel Cell-To-Cell Visibility (C2CV) algorithm, which given two polyhedra, A and B, and a connected and oriented manifold triangle mesh, S, offers a simple, fast, and conservative test for detecting when A and B are occluded from each other by S. Previously disclosed C2CV algorithms either relied on costly occlusion fusion or were restricted to convex (or "apparently convex") occluders, which makes them inappropriate for scenes where potential occluders are arbitrary triangulated surfaces, such as the body of a car or a portion of a terrain. The simplicity of our C2CV algorithm, named ShieldTester, stems from a new Occlusion Theorem, introduced here which permits to establish occlusion by computing the intersection of S with a single ray from a vertex of A to a vertex of B. ShieldTester may be used to establish that pairs of cells in a subdivision of space are hidden from each other by a relatively large surface occluder, so that when the viewer is in one cell, the objects in the other cell need not be displayed.
Lorenzo Ibarria, Peter Lindstrom, Jarek Rossignac, Andrzej Szymczak.
Proc. of Eurographics, pp. 343-348, September 2003.
GVU Tech Report GIT-GVU-03-28. PDF
Also available as Report UCRL-JC-151934 from the DOE.
We present a simple method for compressing very large and regularly sampled scalar fields. Our method is particularly attractive when the entire data set does not fit in memory and when the sampling rate is high relative to the feature size of the scalar field in all dimensions. Although we report results for R3 and R4 data sets, the proposed approach may be applied to higher dimensions. The method is based on the new Lorenzo predictor, introduced here, which estimates the value of the scalar field at each sample from the values at processed neighbors. The predicted values are exact when the n-dimensional scalar field is an implicit polynomial of degree n-1. Surprisingly, when the residuals (differences between the actual and predicted values) are encoded using arithmetic coding, the proposed method often outperforms wavelet compression in an L1 sense. The proposed approach may be used both for lossy and lossless compression and is well suited for out-of-core compression and decompression, because a trivial implementation, which sweeps through the data set reading it once, requires maintaining only a small buffer in core memory, whose size barely exceeds a single (n-1)-dimensional slice of the data.
ByungMoon Kim and Jarek Rossignac,
ACM Symposium in Solid Modeling and Applications, pp. 4-10, June 2003.
GVU Tech Report GIT-GVU-03-12. PDF
The prediction of collisions amongst N rigid objects may be reduced to a series of computations of the time to first contact for all pairs of objects. We propose a collision prediction strategy, where we approximate the relative motion between pairs of objects by a sequence of screw motion segments, each defined by the relative position and orientation of the two objects at the beginning and at the end of the segment. We reduce the computation of the exact collision time and of the corresponding face/vertex and edge/edge collision points to the numeric extraction of the roots of simple univariate analytic functions. Furthermore, we propose a series of simple rejection tests, which exploit the particularity of the screw motion to immediately decide that some objects do not collide or to speed-up the prediction of collisions by about 30%, avoiding on average 3/4 of the root-finding queries even when the object actually collide.
Michael Kaess, Ronald C. Arkin, Jarek Rossignac.
11th International Conference on Advanced Robotics (ICAR), 2003.
GVU Tech Report GIT-GVU-03-22. PDF
This work focuses on real-time compression of laser data on board a mobile robot platform. Data is trans- mitted from the robot over low-bandwidth channels or incrementally in short bursts to a host, where it can be further processed for visualization. For compres- sion purposes, the data is represented as a gray scale depth image. Considered are existing lossless image and le compression schemes (Unix compress, gzip, bzip2, PNG, Jpeg-LS), as well as wavelet transforma- tions tailored to the speci c nature of the data. Test- ing is done on several sets of indoor data acquired by a robot moving through rooms and hallways. The re- sults show that Jpeg-LS compression performs best in this setting.
Rossignac, Allen, Book, Glezer, Ebert-Uphoff, Shaw, Rosen, Askins, Bai, Bosscher, Gargus, Kim, Llamas, Nguyen, Yuan, Zhu.
Shape Modeling International Conference Korea, Seoul, May, 2003. GVU Tech Report GIT-GVU-03-05. PDF
The NSF Digital Clay project is focused on the design, prototyping, integration, and validation of a computercontrolled physical device capable of taking any of a wide range of possible shapes in response to changes in a digital 3D model or to changes in the pressure exercised upon it by human hands. Although it clearly is a natural and unavoidable evolution of 3D graphical user interfaces, its unprecedented capabilities constitute a major leap in technologies and paradigms for 3D display, for 3D input, and for collaborative 3D design. In this paper, we provide an overview of the Digital Clay project and discuss the challenges, design choices, and initial solutions for a new Finger Sculpting interface designed for the Digital Clay and prototyped using conventional 3D I/O hardware.
Ram Somani and Jarek Rossignac.
April 2003.
GVU Tech Report GIT-GVU-03-11. PDF
The FanGrower algorithm segments a triangle mesh into regions (called caps), which may each be closely approximated by a triangle-fan. Once the caps are formed, their rims, which form the inter-cap boundaries, are simplified, replacing each fan by its frame--a fan with the same apex but fewer triangles. The resulting collection of frames is an approximation of the original mesh with a guaranteed maximum error bound. As such, it may be viewed as a powerful extension of Kalvin and Taylor's super-faces, which were restricted to nearly planar configurations and approximated by nearly planar fans. We discuss several cap-growing approaches.
ByungMoon Kim and Jarek Rossignac.
ASME Journal of Computing and Information Science in Engineering (JCISE), vol. 3, no. 4, pp. 295-301, Dec. 2003.
Abstract
Joshua Gargus, Byungmoon Kim, Ignacio Llamas, Jarek Rossignac, and Chris Shaw.
October 2002.
GVU Tech Report GIT-GVU-02-22. PDF
Abstract
Vivek Kwatra and Jarek Rossignac.
International Journal of Shape Modeling, 8(2):119-137. December 2002.
GVU Tech Report GIT-GVU-02-23. PDF
Abstract
A. Szymczak, J. Rossignac, and D. King.
Graphical Models, Volume 64, pp.183-198, May 2002. PDF
Abstract
Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares.
ACM Symposium on Solid Modeling and Applications, pp. 289-296, June 2002.
GVU Tech Report GIT-GVU-02-03. PDF
Abstract
Ghassan Al-Regib, Yucel Altunbasak and Jarek Rossignac.
International Conf. on Acoustics, Speech and Signal Processing ICASSP'02. Vol. 2, pp. 2041-2044, Orlando, May 2002.
Abstract
Yucel Altunbasak, Ghassan Al-Regib and Jarek Rossignac.
IEEE International Conference on Image Processing (ICIP), Rochester NY, Vol. 2, pp. 161-164, Sept. 2002.
Abstract
Ghassan Al-Regib, Yucel Altunbasak, Jarek Rossignac, and Russell Mersereau.
IEEE International Conference on Multimedia and Expo (ICME), Lausanne, Switzerland, Vol. 1, pp. 353 -356, Lausanne, August 26-29, 2002.
Abstract
A. Crosnier and J.R. Rossignac. Chapter 13 in Teleoperation et realite virtuelle, Eds. A. Kheddar and P. Coiffet, Pub. Lavoisier, 2002. (In French.)
L'autonomie d'un système robotique est fortement liée à sa capacité de perception de l'environnement et d'évaluation de sa situation dans cet environnement. Pour un tel système la maîtrise de l'espace est un problème central qui implique une modélisation géométrique de l'environnement et une capacité de raisonnement sur les modèles afin de planifier et contrôler des mouvements. En fonction des applications, les problèmes de modélisation géométrique à résoudre sont souvent de natures très différentes car la connaissance (connaissance a priori, connaissance résultant de mesures) dont on dispose sur l'environnement, est aussi de nature différente. Cela implique la manipulation de modèles géométriques et d'outils de modélisation hétérogènes. En ce sens l'évolution des outils de modélisation géométrique [Foley90, Hoffmann89], et plus particulièrement les développements de la géométrie algorithmique [Preparata87, Boissonnat95], sont des facteurs favorables à l'amélioration des performances des applications en Robotique. Dans ce chapitre nous présentons quelques approches issues de la modélisation géométrique et pour lesquelles les retombées sur la représentation des environnements en Robotique nous semblent importantes. Nous nous intéressons plus particulièrement au problème de la conception et de la manipulation d'environnements 3D faisant appel à des représentations géométriques multirésolution
Jarek Rossignac, Alla Safonova, Andrzej Szymczak.
Chapter in Hierarchical and Geometrical Methods in Scientific Visualization, Farin, G., Hagen, H. and Hamann, B., eds. Springer-Verlag, Heidelberg, Germany. pp 41-50, January 2003.
GVU Tech Report GIT-GVU-01-12. PDF
Abstract
Justin Jang and Jarek Rossignac. July 2001.
GVU Tech Report GIT-GVU-01-05. PDF
Abstract
J. Rossignac and J. Kim.
Journal of Computer-Aided Design, vol. 33, no. 4, pp. 279-291, April 2001.
An interpolating screw motion can be automatically computed from the starting and ending poses of a moving body. By interactively introducing intermediate poses, the designer can approximate any smooth motion to the desired accuracy by a sequence of screw motions. The first advantage of the screw motion is the relative simplicity of the computation of the boundary of the region swept by the moving object. Indeed, the characteristic curve of the moving object, i.e.: the edges subset that generates the envelope containing the sweep boundary, remains constant throughout the entire screw motion and is simple to compute. Note that pure linear translations and pure constant axis rotations also offer these advantages, but are not general enough to smoothly and efficiently approximate arbitrary rigid motions. On the other hand, arbitrary combinations of linear translations and constant axis rotations result in a changing characteristic curve. The second advantage of a screw motion over a more general motion is its suitability for realtime rendering (animation) on standard graphic architectures, which provide hardware support for the pre-multiplication of the 4x4 matrix defining the world-to-screen mapping by any 4x4 matrix. The consecutive positions that correspond to constant time steps of a screw motion may be obtained by pre-multiplying the world-to-screen matrix by a constant increment matrix. The presentation will cover algorithms for computing the screw motion from interpolated positions, for animating the objects motion in realtime with interactive control of time flow, for computing the characteristic curve, and for displaying the sweep envelope. These algorithms are the primary building blocks for our interactive motion editor.
Award.
A. Szymczak, D. King, J. Rossignac.
Computational Geometry: Theory and Applications, Vol 20, No 2, pp. 53-68, Oct 2001.
Abstract
Vivek Kwatra and Jarek Rossignac,
Shape Modeling International, 2001.
Abstract
Pere Brunet, Jarek Rosignac, Isabel Navazo, Carlos Saona-Vazquez.
Computer Graphics Forum, Proc. Eurographics, 19(3):499-506, 2001.
Abstract
L. Kettner, A. Mascarenhas, J. Rossignac and J. Snoeyink
17th European Workshop on Computational Geometry, 2001, 13-16.
Abstract
Jarek Rossignac, Alla Safonova, and Andezej Szymczak
Shape Modeling International Conference, pp: 278-283, Genoa, Italy May 2001.
Abstract
Renato Pajarola and Jarek Rossignac
IEEE Transactions on Visualization and Computer Graphics, Vol. 6, No. 1, pp. 79-93, January-March 2000.
GVU Tech Report GIT-GVU-00-04. PDF
The CPM approach proposed here uses a new insert-spray technique, which refines the topology of the mesh in batches that each increase the number of vertices by up to 50%. Yet, the total cost of this progressive refinement, when amortized over the entire mesh, is less than 4 bits per triangle for connectivity information. To compress vertex coordinates, CPM estimates each new vertex from the positions of its neighbors. Our new estimator is based on an extension of the butterfly subdivision scheme and leads to representations of vertex coordinates that are 20% more compact than previously reported geometry compression schemes. As a result, the CPM format offers a crude approximation of the model after 1% of the data is received, then provides several successive refinements, and finally restores the full resolution model in less total time than previously reported non-progressive techniques need to restore the fixed-resolution model.
Jay Kim and Jarek Rossignac
International Journal of the Japan Society of Mechanical Engineers, 2000.
GVU Tech Report GIT-GVU-99-35. PDF
The free motion of a shape in 3D may be intuitively designed and edited by inserting and adjusting control poses that should be interpolated by th emoving shape at the desired values of time. We propose to use screw interpolating motions and present simple and effective tools for computing and animating them.
Andrzej Szymczak and Jarek Rossignac
Computer-Aided Design, 32(8/9), 527-538, July/August, 2000.
Abstract
Renato Pajarola and Jarek Rossignac
Computer Graphics International Conference, Switzerland, pp. 173-182, June 2000.
GVU Tech Report GIT-GVU-00-05. PDF
Compression techniques for triangle-mesh representations of 3D models have been the focus of many recent efforts from the graphics, modeling, and theory research community; from developers of computer graphics hardware and software; and from organizations that define international standard. An ideal compression technology would simultaneously support the following three objectives: (1) progressive refinements of the received mesh during decompression, (2) nearly optimal compression ratios for both geometry and connectivity, and (3) inline, real-time decompression algorithms for hardware or software implementations. Because these three objectives impose contradictory constraints on the compressed format, previously reported efforts focus primarily on one-sometimes two-of these objectives. The SQUEEZE technique introduced here for the Fast and Progressive Decompression of Triangle Meshes addresses all three constraints simultaneously and attempts to provide the best possible compromise for the needs of common Internet applications that require frequent access to remote 3D databases. For a typical mesh of T triangles, SQUEEZE compresses the connectivity to 3.7T bits, which is competitive with the best progressive compression techniques reported so far. The geometry prediction techniques introduced here lead to an additional 20% improvement in geometry compression over previous schemes. Our initial 250Mhz CPU. Finally, in general SQUEEZE downloads a model through 10 successive refinements, providing the full benefit of progressivity. After each refinement, the user may manipulate the current resolution model as SQUEEZE decompresses the next upgrade, or temporarily stop the transmission until a higher level-of-detail is needed.
Andrzej Szymczak, Davis King, Jarek Rossignac
12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, August 16-19, 2000.
Abstract
J. Rossignac
Eurographics 2000.
Abstract
Davis King, Jarek Rossignac. 1999
GVU Tech Report GIT-GVU-99-36. PDF
Abstract
Jarek Rossignac and Andrzej Szymczak
Journal of Computational Geometry, Theory and Applications, Volume 14, Issue 1-3, pp. 119-135, November 1999.
GVU Tech Report GIT-GVU-99-08. PDF
Abstract
Andre Crosnier and Jarek Rossignac
Computers&Graphics, Vol. 23, No. 3, pp. 429-438, March 1999.
Best Paper Award.
Abstract
Best Paper Award.
Davis King and Jarek Rossignac
Journal of Computational Geometry, Theory and Applications. Volume 14, Issue 1-3, pp. 91-118. November 1999.
GVU Tech Report GIT-GVU-99-07. PDF
To use 3D models on the Internet or in other bandwidth-limited applications, it is often necessary to compress their triangle mesh representations. Compression often requires making quick decisions among various compression options and among different levels of detail. We propose a heuristic for estimating the tradeoff between accuracy and representation size, in order to help make such choices in cases where exact information on error is difficult to obtain. Let A be a triangle mesh approximation for an original model O, with V vertices and B bits per vertex coordinate. Given a desired error level E, how many vertices are needed? Given V for a level of detail or a progressive update , what is the likely change in error? We develop answers to these questions by introducing a shape complexity measure that allows us to express the relationship between V and E in terms of model shape. We give formulas linking V,E, and K, and we provide a simple algorithm for computing K for an existing triangle mesh.
Award.
Jarek Rossignac.
IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 1, pp. 47-61, January - March 1999.
GVU Tech Report GIT-GVU-98-35. PDF
Best Paper Award.
Abstract
Best Paper Award.
Renato Pajarola, Jarek Rossignac, and Andrzej Szymczak.
IEEE Visualization, San Francisco, October 24-29, 1999.
GVU Tech Report GIT-GVU-99-16. PDF
Abstract
Davis King and Jarek Rossignac.
11th Canadian Conference on Computational Geometry (CCCG'99), pp. 146-149, Vancouver, CA, August 15-18, 1999.
GVU Tech Report GIT-GVU-99-17. PDF
Abstract
Jarek Rossignac and David Cardoze.
Proceedings of the ACM Symposium on Solid Modeling, pp. 31-41, June 1999.
GVU Tech Report GIT-GVU-99-03. PDF
Abstract
Nicholas Patrikalakis, Paul J. Fortier, Yannis E. Ioannidis, Christos N. Nikolaou, Allan R. Robinson, Jarek R. Rossignac, Alvar Vinacua, and Stephen L. Abrams.
Harvard University Library. April 1999.
Abstract
Andrzej Szymczak and Jarek Rossignac
Proc. ACM Symposium on Solid Modeling, pp. 54-64, June 1999.
GVU Tech Report GIT-GVU-99-02. PDF
Abstract
Jarek Rossignac and Aristides Requicha
Chapter in the Encyclopedia of Electrical and Electronics Engineering, Ed. J. Webster, John Wiley & Sons. 1999.
GVU Tech Report GIT-GVU-99-09. PDF
Abstract
J. Rossignac. October1998.
GVU Tech Report GIT-GVU-99-04. PDF
Abstract
Gabriel Taubin, William Horn, Frederic Lazarus, and Jarek Rossignac
Proceedings of the IEEE, pp. 1228-1243, vol. 96, no. 6, June 1998.
Abstract
Gabriel Taubin and Jarek Rossignac. ACM Transactions on Graphics, Volume 17, Number 2, pp. 84-115, April 1998.
Best Paper Award.
Abstract
Best Paper Award.
Jarek Rossignac
Computer Graphics International Congress (CGI '98 congress), Hanover, pp. 324-335, June 24-26, 1998.
Abstract
Jarek Rossignac
Proceedings of the ACM Symposium on Solid Modeling, pp. 1-9, 1997.
GVU Tech Report GIT-GVU-96-26.PDF
Abstract
J. Rossignac
International Conference on Shape Modeling and Applications, Aizu-Wakamatsu, Japan, IEEE Computer Society Press, pp. 64-70, March 1997. GVU Tech Report GIT-GVU-96-29.
The manufacturing industry has invested vast amounts of resources in the deployment and use of solid modeling technology. Although expensive to generate and poten-tially very valuable in many product related activities, 3D models have rarely been exploited to support product management, documentation, collaborative review, and promotion, because they were only accessible to trained designers equipped with expensive graphics workstations. Intranet access, popular 3D exchange formats, and af-fordable 3D graphics chips permit to download and view 3D models using a personal computer. Although these basic capabilities are revolutionizing the entertainment and marketing industry and have reduced the cost of a design station, they are of little help to non-designers in the manufacturing industry. The author articulates a vision where 3D data is available and exploited at all phases of a product life cycle. The paper investigates the shortcomings of the current technology, identifies the fun-damental research issues, and reviews recent advances in 3D data compression, in the automatic generation of levels-of-detail for interactive rendering, and in the innova-tive exploitation of 3D input devices for an intuitive and effective navigation.
J. Rossignac
Tutorial. Eurographics, 1997.
Abstract
J. Rossignac
Lecture in Course 29 on Representations of Geometry for Computer Graphics at SIGGRAPH 1996.
Survey of boundary representation schemes for non-manifold, mixed-dimensional structures. Including Selective Geometric Complexes (SGC), their the Next cell Around cell In a cell's List (NAIL) extension for capturing cyclic ordering of adjacency relations, and the COnstructive Non-Regularized Geometry (CNRG) extension sof CSG to non-manifold modeling. The file contains the lecture notees, a glossary of key topological concepts, and the lecture slides.
Raja Banerjee and Jarek Rossignac
Computer Graphics Forum, Vol. 15, No. 4, pp. 205-217, 1996.
PDF(.pdf?)
Floating point round-off causes erroneous and inconsistent decisions in geometric modeling algorithms. These errors lead to the generation of topologically invalid boundary models for CSG objects and significantly reduce the reliability of CAD applications. Previously known methods that guarantee topological consistency by relying on arbitrary precision rational arithmetic or on symbol-manipulation techniques are too expensive for practical purposes. This paper presents a new solution which takes as input a fixed precision, regularized Boolean combination of linear half-spaces and produces a polyhedral boundary model that has the exact topology of the corresponding solid. Each half-space is represented by four homogeneous coefficients in fixed precision format (A bits for each one of the three direction cosigns and D bits for the constant term, i.e. the distance to the origin). Exact answers to all topological and ordering questions are computed using a fixed length, 3A+D+2 bits, integer format. This new guaranteed tight limit on the number of bits necessary for performing intermediate calculations is achieved by expressing all of the topological decisions based on geometric computations in terms of the signs of 4x4 determinants of the input coefficients. The coordinates of intersection vertices are not required for making the correct topological decisions and vertices and lines are represented implicitly in terms of planes. (Floating point approximations of vertices may be produced a posteriori for graphics and other applications.) Efficiency concerns impose a limit on the values of A and D, requiring that the primitive's geometry manipulated by the designers be approximated before it may be used for boundary evaluation. Prior to this approximation, designers may view their CSG primitives as simple Boolean combinations of loose linear half-spaces, each having the freedom to snap to a nearby half-space representable with the prescribed precision. As a consequence, the topology of certain solid primitives may be altered by these geometric perturbations, no matter how small. Nevertheless, moving the uncertainty into the primitive half-spaces, away from the geometric calculations, yields a simple and totally robust boundary evaluation algorithm.
Remi Ronfard and Jarek Rossignac
Computer Graphics Forum, Proceedings of Eurographics, pp. C-67, Vol. 15, No. 3, August 1996.
PDF (10MB, low quality)
Abstract
Chris Hoffmann and Jarek Rossignac
IEEE Transactions on Visualization and Computer Graphics, vol. 2, No. 1, pp. 3-10, March 1996.
Abstract
Jarek Rossignac
Proceedings of the Blaubeuren Workshop on Graphics and Modeling, Germany 1996.
Abstract
Jarek Rossignac
CSG'96: Set-theoretic solid modeling techniques and applications, Information Geometers, Ed. John Woodwark. 1996.
Abstract
Paul Borrel, K. Cheng, Pierre Darmon, Peter Kirchner, Jim Lipscomb, Jai Menon, Josh Mittleman, Jarek Rossignac, Bengt-Olaf Schneider, Bob Wolfe
IBM Technical Report. 1995.
Abstract
Bengt-Olaf Schneider and Jarek Rossignac
Computers&Graphics, Volume 19, Issue 2, Pages 239-246, March-April 1995.
Abstract
Bengt-Olaf Schneider, Paul Borrel, Jai Menon, Josh Mittleman, Jarek Rossignac
In Rendering Techniques, Proc. 5th Eurographics Workshop on Rendering, Springer-Verlag, 389-399, New York, 1995.
Abstract
Remi Ronfard and Jarek Rossignac.
Computer Graphics Forum, Proc. Eurographics, Vol 13, No 3, pp. C281-C292, Sept 1994.
Best Paper Award.
PDF (11MB, Low Quality)
Abstract
Best Paper Award.
Jarek Rossignac and M. Novak
IEEE Computer Graphics & Applications, Vol. 14., No 2., pp. 83-85, March 1994.
Abstract
Jarek Rossignac and Anil Kaul
Computer Graphics Forum, Proc. Eurographics, Oslo, Norway, Vol 13, No 3, pp. C179-C184, Sept 1994.
Abstract
Jarek Rossignac
Proceedings of CSG 94: Set-theoretic Solid Modelling Techniques and Applications, Information Geometers, pp. 55-70, Winchester, UK, April 1994.
Disjunctive forms of CSG expressions are used in computer graphics instead of the equivalent CSG graphs because they alleviate the need for a stack of arbitrary length when evaluating CSG expressions. This advantage is especially important in SIMD architectures, where the same expression must be evaluated in parallel for a large number of datasets (for example for each pixel). Algorithmic techniques based on rewrite rules for constructing a disjunctive form from a binary CSG tree have been proposed. The drawback of these techniques is their need for storing an explicit representation of the disjunctive form, which may grow exponentially with the number of leaves in the original graph. The present paper proposes a new approach for processing the disjunctive form directly off the original CSG graph, thus avoiding the expensive rewrite mechanism and eliminating the associated storage requirements. The technique is articulated around two algorithms. The first one computes the total number of products in the disjunctive sum for each node. The second one takes as arguments a valid product id-number and traverses the relevant portions of the CSG graph to visit all and only the primitives of that product. The proposed technique is well suited for early culling of groups of empty products. It also provides an effective means for computing optimal mini-max bounds for CSG solids. An application of this technique to the hardware assisted rendering of CSG models with sculptured primitives will be briefly presented.
Jarek Rossignac
In From Object Modelling to Advanced Visualization, Eds. S. Coquillart, W. Strasser, P. Stucki, Springer Verlag, pp. 1-75, 1994.
Abstract
Jarek Rossignac
In Scientific Visualization: Advances and Challenges, Academic Press. Ed. L Rosenblum. pp. 337-348, 1994.
Abstract
Martin van Emmerik, Ari Rappoport, and Jarek Rossignac
The Visual Computer, vol. 9, No. 5, pp. 239-254, March 1993.
We propose a new representation for scene graphs and CSG graphs that supports combinations of hierarchical patterns and recursive patterns. We also propose a multi-modal Graphical User Interface (GUI) which combines a simple text editor for specifying and editing the graph and direct manipulation for controling the transformations defined in the scene graph. We also propose a novel widget for the precise editing of numeric values (angles, translations) defining these transformations. These new tools have been integrated in our ABCSG system and interfaced to the CATIA modeller.
Jarek Rossignac and Paul Borrel
In Geometric Modeling in Computer Graphics, pp. 455-465, Springer Verlag, Eds. B. Falcidieno and T.L. Kunii, Genova, Italy, June 28-July 2, 1993.
We present a novel approach to the simplification of triangle meshes and more generally simplicial complexes in 2D and 3D. Our Vertex-Clustering approach uses quantization to group vertices and replace each group by a carefully chosen single representative vertex. Degenerate simplices (such as a triangle with two identical vertices) that are no longer needed are discarded. The approach is capable of more aggressive simplifications that many subsequently developed solutions because it eliminates small topological details. A bound on the Hausdorff error can be used to control the degree of simplification. The Vertex-Clustering method was used in several commercial products, products and academic multi-resolution systems to accelerate the rendering of complex 3D scenes.
J. Rossignac
In Geometry and Optimization Techniques for Structural Design, pp. 1-44, Eds. S. Kodiyalam, M. Saxena, Computational Mechanics Publications, Southhampton, 1993.
Abstract
Anil Kaul and Jarek Rossignac
Computers&Graphics. Vol. 16, No. 1, pp. 107-115, 1992.
Best Paper Award at Eurographics 91.
Abstract
Best Paper Award.
Aristides Requicha and Jarek Rossignac
IEEE Computer Graphics&Applications, Special issue on CAGD, pp. 31-44, September 1992.
Best Paper Award.
Abstract
Jarek Rossignac, Abe Megahed, and Bengt-Olaf Schneider
Proc. ACM Siggraph, ACM Computer Graphics, Vol. 26, No. 2, pp. 353-360, July 1992.
Abstract
Bengt-Olaf. Schneider and Jarek Rossignac
Proc. 7th Eurographics Workshop on Computer Graphics Hardware, Cambridge, UK, September 1992.
Abstract