Bmorphs between bcompatible curves B. Whited, J. Rossignac, ACM Symposium on Solid and Physical Modeling (SPM), 2009. PDF 
MORPHOLOGY  MORPHING  HOMEOMORPHISM  ROUNDING  SHAPE DISCREPANCY We investigate tools for comparing and morphing between pairs of registered, nearly similar shapes, P and Q. The traditional (closest point) cmorph moves a point p of P at constant velocity towards a closest point q on Q. Our new (tangent ball) bmorph moves each point along a circular arc incident orthogonally onto both P and Q. The bmorph has several advantages over the cmorph: 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 bmorphs of bcompatible 2D shapes and extend it to incompatible shapepairs through recursive brounding. 

SOT: Compact representation for Tetrahedral Meshes T. Gurung, J. Rossignac, ACM Symposium on Solid and Physical Modeling (SPM), 2009. PDF 
DATA STRUCTURES  BOUNDARYREPRESENTATIONS  TETRAHEDRA MESHES  STORAGE  ALGORITHMS The Corner Table (CT) provides a simple and efficient representation of triangle meshes, storing 6 integer references per triangle (3 vertex references in the V table and 3 references to opposite corners in the O table). The Compact Half Face (CHF) extends CT to tetrahedral meshes, storing 8 references per tetrahedron (4 in the V table and 4 in the O table). We call it the Vertex Opposite Table (VOT) and propose a sorted variation, SVOT, which does not require any additional storage and yet provides, for each vertex, a reference to an incident corner from which the star of the vertex may be traversed at a constant cost per visited element. We use a set of wedgebased operators for querying and traversing the mesh. Finally, we propose our Sorted O Table (SOT) variation, which eliminates the V table completely and hence reduces storage requirements by 50% to only 4 references and 9 bits per tetrahedron, while preserving the vertextoincidentcorner references and supporting our wedge operators with a linear average cost. 

Relative blending B. Whited, J. Rossignac Journal of Computer AidedDesign (JCAD). 2009 PDF. 
VARIABLERADIUS BLENDING  FILLETS  ROUND  CANAL SURFACES Solid models may be blended through filleting or rounding operations that typically replace the vicinity of concave or convex edges by blends that smoothly connect to the rest of the solid's boundary. Circular blends, which are popular in manufacturing, are each the subset of a canal surface that bounds the region swept by a ball of constant or varying radius as it rolls on the solid while maintaining two tangential contacts. We propose to use a second solid to control the radius variation. This new formulation supports global blending (simultaneous rounding and filleting) operations and yields a simple settheoretic formulation of the relative blending R_{B}(A) of a solid A given a control solid B. We propose userinterface options, describe practical implementations, and show results in 2 and 3 dimensions.  
OCTOR: Subset selection in recursive pattern hierarchies J. Jang, J. Rossignac Graphical Models (GMOD), 71:92106, 2009. PDF 
DESIGN  PATTERNS  HIERARCHIES  GUI  SELECTION  PERSISTENT NAMING This is an expanded version of the OCTOR paper, extending the selection technique to models that may involve combination of repetitions and recursive formulations of patterns of features.  
Ballmap: Homeomorphism between compatible surfaces F. Chazal, A. Lieutier, J. Rossignac, B. Whited GVU Tech Report GITGVU0605. PDF To appear in the International Journal of Computational Geometry and Applications. 
MODELING  DISTANCE  MAPPING  SHAPE SIMILARITY We introduce the ballmap, BM_{S,T}, between two manifolds, S and T. It maps each point x of S to a point x = BM_{S,T}(x) of T. Its inverse is BM_{T,S}. We define conditions for BM_{S,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 C^{k} (n1)manifolds in R^{n}, BM_{T,S} is a C^{k1} diffeomorphism and defines a C^{k1} ambient isotopy that smoothly morphs between S to T. In practice, the ballmap 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. 

3D Ball Skinning using PDEs for Generation of Smooth Tubular Surfaces G. Slabaugh, J. Rossignac, B. Whited, T. Fang, G. Unal Journal of Computer AidedDesign (JCAD). 2009 PDF. 
CANAL SURFACES  ENVELOOPES  SHAPE OPTIMIZATION We present an approach to compute a smooth, interpolating skin of an ordered set of 3D balls. By construction, the skin is constrained to be C^{1} continuous, and for each ball, it is tangent to the ball along a circle of contact. Using an energy formulation, we derive differential equations that are designed to minimize the skin's surface area, mean curvature, or convex combination of both. Given an initial skin, we update the skin's parametric representation using the differential equations until convergence occurs. We demonstrate the method's usefulness in generating interpolating skins of balls of different sizes and in various configurations.  
Ringing subdivision of curves and surfaces J. Rossignac, A. Venkatesh IEEE Computer Graphics & Applications PDF. 
CURVES  SURFACES  SUBDIVISION  BSPLINES  GPU  GEOMETRY SHADER  STREAMING  ANIMATION Jspline subdivisions iteratively refine a polygon by inserting a vertex in the middle of each edge (Split) and then moving each vertex to an affine combination of five consecutive vertices (Tweak). Applying d refinement steps to a control polygon of n vertices requires temporary storage space for (n5)2^{d}+5 vertices. Rendering each span independently reduces temporary storage requirement (footprint) to 2^{d}+5 vertices, but increases computation. The ringing approach introduced here reduces the footprint to 4d vertices. We describe an efficient implementation, show applications to surfaces and animations, and report timings comparing CPU and GPU implementations of ringing with the global and perspan approaches.  
Jsplines J. Rossignac, S. Schaefer Journal of Computer AidedDesign (JCAD), 40(1011):10241032, OctNov 2008. DOI. PDF. 
SUBDIVISION  CURVES  SURFACES  CONTINUITY  INTERPOLATION  BSPLINES The Jspline subdivision scheme yields a family of limit curves (J_{s}) the shape of which is parameterized by s. They include fourpoint subdivision curves (J_{0}), uniform cubic Bspline curves (J_{1}), and uniform quintic Bspline curves (J_{1.5}). Js is at least C^{2} when s is in [0,4] and is C^{4} when s=3/2. We generalize the J_{s} scheme to a twoparameter family J_{a,b} and propose datadependent and dataindependent solutions for computing values of parameters a and b that minimize various objective functions (distance to the control vertices, deviation from the control polygon, change in surface area, and popping when switching levels of subdivision in multiresolution rendering). We extend the Jspline subdivision to open curves and to a smooth surface subdivision scheme for quadmeshes with arbitrary connectivity.  
Patientspecific surgical planning and hemodynamic computational fluid dynamics optimization through freeform haptic anatomy editing tool (SURGEM) K. Pekkan, B. Whited, K. Kanter, S. Sharma, D. de Zelicourt, K. Sundareswaran, D. Frakes, J. Rossignac, A. Yoganathan Journal of Medical and Biological Engineering and Computing, Springer. 46(11):11391152, Nov 2008. DOI. 
SUBDIVISION  CURVES  SURFACES  CONTINUITY  INTERPOLATION  BSPLINES Surgem is used at the surgery planning phase to design and evaluate possible modifications of patientspecific anatomies for patients with congenital heart defects. Surgem makes it possible to freely deform the lumen surface and to bend and position baffles through realtime, direct manipulation of the 3D models with both hands, thus eliminating the tedious and timeconsuming phase of entering the desired geometry using traditional computeraided design (CAD) systems. The 3D models of the modified anatomies are seamlessly exported and meshed for patientspecific CFD analysis. Using SURGEM, more than 30 new anatomical designs (or candidate configurations) are created, and the corresponding user times presented. CFD performances for eight of these candidate configurations are also presented.  
OCTOR: OCcurrence selecTOR in pattern hierarchies J. Jang and J. Rossignac IEEE International Conference on Shape Modeling and Applications (SMI), 205212, 2008. 
DESIGN  PATTERNS  HIERARCHIES  GUI  SELECTION  PERSISTENT NAMING Hierarchies of patterns of features, of subassemblies, or of CSG subexpressions 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 mouseclicks.  
Variational Skinning of an Ordered Set of Discrete 2D Balls G. Slabaugh, G. Unal, T. Fang, J. Rossignac, B. Whited Geometric Modeling and Processing 2008. Springer. PDF 
CANAL SURFACES  SHAPE FITTING  ENVELOPES 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. 

Pearling: Stroke segmentation with crusted pearl strings B. Whited, J. Rossignac, G. Slabaugh, T. Fang, G. Unal The First International Workshop on Image Mining Theory and Applications (IMTA), 2008. Also: Journal of Pattern Recognition and Image Analysis, Pleiades Publishing 19(2)277283, 2009. PDF 
IMAGE SEGMENTATION  STROKE EXTRACTION  VESSEL EXTRACTION  MEDIAL AXIS We introduce a segmentation technique, called Pearling, for the semiautomatic extraction of idealized models of networks of strokes (variable width curves) in images. These may roads, vessels, or penstrokes. 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.  

Solid and Physical Modeling J. Rossignac. 2007. PDF. Chapter in the Wiley Encyclopedia of Electrical and Electronics Engineerig. Ed. J. Webster. 
SOLID MODELING  CSG  CST  GEOMETRIC COMPLEXES 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 hardwareassisted 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. 

Spectral Interpolation on 3x3 Stencils for Prediction and Compression L. Ibarria, P. Lindstron, J. Rossignac. Journal of Computers, 2(8)5363, 2007. PDF 
COMPRESSION  PREDICTION  STREAMING  HIGHPRECISION IMAGES 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 highprecision data. 

Normal map between normalcompatible manifolds F. Chazal, A. Lieutier, and J. Rossignac. Int. J. of Computational Geometry & Applications (IJCGA), 17(5)403421 Oct. 2007. Revised version of GVU Tech Report GITGVU0428. PDF 
MODELING  SHAPE MAPPING  NORMALOFFSETTING  CLOSEST PROJECTION 

Tightening: Morphological Simplification J. Williams, J. Rossignac. Int. J. of Computational Geometry and Applications (IJCGA), 17(5)487503, Oct. 2007. PDF 
MORPHOLOGY  SHAPE ANALYSIS  ROUNDING  REGULARITY  SIMLIFICATION 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. 

Anatomically Realistic PatientSpecific Surgical Planning of Complex Congenital Heart Defects Using MRI and CFD. K. Sundareswaran, D. de Zelicourt, K. Pekkan, G. Jayaprakash, D. Kim, B. Whited, J. Rossignac, M. Fogel, K. Kanter, A. Yoganathan. International Conference of the IEEE Engineering in Medicine and Biology Society. PDF  SURGERY PLANNING  SHAPE DEFORMATIONS  COMPUTATIONAL FLUID DYAMICS 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 postoperative 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. 

Pearling: 3D Interactive extraction of tubular structures from volumetric images J. Rossignac, B. Whited, G. Slabaugh, T. Fang, G. Unal MICCAI workshop on Interaction in Medical Image Analysis and Visualization, Nov. 2007. PDF 
MEDICAL IMAGING  IMAGE SEGMENTATION  CURVE TRACING Pearling is a novel 3D approach to the interactive segmentation and modeling of tubular structures from a volumetric image. Given a usersupplied 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. 

Pearling: Medical Image Segmentaiton with Pearl Strings J. Rossignac, B. Whited, G. Slabaugh, T. Fang, G. Unal 
MEDICAL IMAGING  VOLUME SEGMENTATION  ISOSURFACES  VESSEL EXTRACTION 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 brushstrokes. 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. 

An Unconditionally Stable MacCormack Method A. Selle, R. Fedkiw, B. Kim, Y. Liu, J. Rossignac Journal of Scientific Computing. PDF 
ANIMATION  FLUID SIMULATION  PDE  ADVECTION  LEVELSETS 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. 

Ordered Bolean List (OBL) J. Rossignac GVU Tech Report GITGVU0710. PDF 
CSG  BOOLEAN  LOGIC  OBDD  OBF An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators, nor any repeated subexpression. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into an Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and constant (more precisely, loglog n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of five bits suffices for all EBEs of up to 6 billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their CSG representation. We also compare the OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to logic circuit design.  
Pressing: Smooth Isosurfaces with Flats from Binary Grids A. Chica, J. Williams, C. Andujar, P. Brunet, I. Navazo, J. Rossignac, A. Vinacua The Eurographics Computer Gaphics Forum (CGF). GVU Tech Report GITGVU0709. PDF 
VISUALIZATOIN  ISOSURFACES  SEGMENTATION  SMOOTHING  SHARPENING  SHAPE RECOGNITION 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. 

Simulation of Bubbles in Foam by Volume Control B.M. Kim, Y. Liu, I. Llamas, X. Jiao, J. Rossignac ACM Trans. on Graphics (TOG). 26(3):98. Proc. SIGGRAPH GVU Tech Report GITGVU0708. PDF 
ANIMATION  SIMULATION  FLUID  FOAM  PDE  LEVELSET 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. 

Spectral prediction L. Ibarria, P. Lindstron, J. Rossignac. Data Compression Conference, 163172, March 2007 GVU Tech Report GITGVU0707. PDF 
COMPRESSION  PREDICTION  STREAMING  HIGHPRECISION IMAGES Many applications produce large highprecision 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 highprecision data. 

Boundary of the volume swept by a freeform solid in screw motion J. Rossignac, J.J. Kim, S.C. Song, K.C. Suh, C.B. Joung ComputerAided Design 39(9):745755, 2007. GVU Tech Report GITGVU0619. PDF 
CAD/CAM  SWEPT VOLUME  ENVELOPE  SOLID MODELING  SCREW MOTION 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, piecewisescrew), generate candidate faces, compute the twocells of their arrangement, and use a new pointinsweep test to select the correct cells whose union forms the boundary of the swept volume. 

Blist: Small footprint evaluation of Boolean expressions J. Rossignac GVU Tech Report GITGVU0618. 
BOOLEAN LOGIC  CSG  BLIST This technical report was delayed and is now available as Optimized Blist Form (OBF) J. Rossignac. GVU Tech Report GITGVU0710. PDF 

Advections with Significantly Reduced Dissipation and Diffusion, B.M. Kim, Y. Liu, I. Llamas, J. Rossignac IEEE Trans. on Visualization and Computer Graphics, 2006 GVU Tech Report GITGVU0617. PDF 
ANIMATION  FLUID SIMULATION  LEVEL SETS 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 firstorder upwind or semiLagrangian integration of advection equations. It provides secondorder 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 

CST: Constructive Solid Trimming for rendering BReps and CSG J. Hable, J. Rossignac IEEE Trans. on Visualization and Computer Graphics, 13(5):10041014, 2007. GVU Tech Report GITGVU0616. PDF 
GRAPHICS  GPU  CSG RENDERING  TRIMMED FACES  ACTIVE ZONES  BLIST  CAD 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, GPUbased, 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. 

Surgem: Next Generation CAD Tools for Interactive PatientSpecific Surgical Planning and Hemodynamic Analysis J. Rossignac, K. Pekkan, B. Whited, K. Kanter, S. Sharma, A. Yoganathan GVU Tech Report GITGVU0615. PDF 
MEDICAL  SURGERY PLANNING  HUMANSHAPE INTERACTION  DEFORMATIONS Surgem is a surgical planning tool for editing complex patientspecific anatomies and for interfacing with computational fluid dynamics (CFD) analysis. Novel twohand, shape editing technologies are applied to design and evaluate possible modifications of patientspecific anatomies of congenital heart defects. 

ScrewBender: Smoothing Piecewise Helical Motions Alex Powell and Jarek Rossignac IEEE Computer Graphics and Applications, 28(1):5663 Jan/Feb 2008. GVU Tech Report GITGVU0505. (PDFl 
ANIMATION  DESIGN  MOTION  SMOOTHING  SUBDIVISION 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. 

An unequal error protection method for progressively compressed 3D models Ghassan AlRegib, Yussel Altunbasak, and Jarek Rossignac. IEEE Transactions on Multimedia, 7(4)766:767, August 2005. PDF 
COMPRESSION  SIMPLIFICATION  TRIANGLEMESHES  ERROR CORRECTION We present a packetloss 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 3D 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. 

FlowFixer: Using BFECC for Fluid Simulation B.M. Kim, Y. Liu, I. Llamas, J. Rossignac Eurographics Workshop on Natural Phenomena. September 2005. GVU Tech Report GITGVU0524. PDF 
SIMULATION  PHYSICS  FLUIDS  PDEs 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. 

GeoFilter: Geometric Selection of Mesh Filter Parameters ByungMoon Kim and Jarek Rossignac Computer Graphics Forum, 24(3):295302. Proc. Eurographics, September 2005. 
MODELING  TRIANGLE MESHES  EXAGERATION  SMOOTHING  USER INTERFACES 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 userselected 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. 

ParabolaBased Discrete Curvature Estimation Hyoungseok Kim and Jarek Rossignac 2005. 
Curves  Polygon  Curvature In this paper, we point out the limitation of a popular discrete curvature estimation and present a new discrete sectionalcurvature estimation, which is based on the parabola interpolation and the geometric properties of Bezier curve. 

Shape Complexity Jarek Rossignac The Visual Computer, 21:985996, 2005. 
MODELING  SIMPLIFICATION  COMPRESSION  RESAMPLING  MORPHOLOGY 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. 

PhotoMeter: Easytouse MonoGraphoMetrics Hendrik Mueller and Jarek Rossignac. Central Europe Multimedia and Virtual Reality Conference, June 2005. GVU Tech Report GITGVU0419. PDF  IMAGE PROCESSING  3D RECONSTRUCTION  USER INTERFACES PhotoMeter is an effective and very easytouse 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. 

Blister: GPUbased rendering of Boolean combinations of freeform triangulated shapes John Hable and Jarek Rossignac ACM Transactions on Graphics, Proceedings of SIGGRAPH 2005. 
MODELING  CSG  RENDERING  GPU  SHADOW  TRANSPARENCY 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. 

Filleting and rounding using a pointbased method Yong Chen, Hongqing Wang, David Rosen, Jarek Rossignac ASME Design Engineering Technical Conferences, DETC05/DAC85408, 533542. September 2005. 
MODELING  FILLETING  ROUNDING  DISTANCE FIELD Rounds and fillets are important design features. We introduce a new pointbased 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. 

A PointBased Offsetting Method of Polygonal Meshes Yong Chen, Hongqing Wang, David Rosen, Jarek Rossignac Submitted, May 2005. 
MODELING  OFFSETTING  MORPHOLOGY 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. 

ErrorResilient Transmission of 3D Models Ghassan AlRegib, Yucel Altunbasak, Jarek Rossignac ACM Transactions on Graphics, 24(2)182:208. April 2005. 
COMPRESSION  NOISY CHANNEL  ERROR CORRECTION  PROGRESSIVE MESHES 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. 

Mason: Morphological Simplification Jason Williams and Jarek Rossignac Graphical Models, 67(4)285:303, 2005. GVU Tech Report GITGVU0405. PDF 
SIMLIFICATION  MORPHOLOGY  IMAGE PROCESSING  ALPHAHULL The mortar of a shape (2D area or 3D solid) is the alphahull (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. 

Sharpen&Bend: Recovering curved edges in triangle meshes produced by featureinsensitive sampling Marco Attene, Bianca Falcidino, Michela Spagnuolo, Jarek Rossignac IEEE Transactions on Visualization and Computer Graphics (TVCG), vol 11, no 2, pp 181192, March/April 2005. GVU Report GITGVU0334. PDF 
TRIANGLEMESHES SAMPLING  FEATURE RECOVERY  SUBDIVISION Featureinsensitive 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. 

TetStreamer: Compressed BacktoFront Transmission of Delaunay Tetrahedra Meshes Urs Bischoff and Jarek Rossignac Data Compression Conference (DCC), 93102, March 2005. GVU Tech Report GITGVU0426. PDF 
COMPRESSION  TETRAHEDRONMESHES  VISUALIZATION  VISIBILITY  STREAMING We compress the connectivity of a tetrahedronmesh to less than 2 bits per tetrahedron while transmitting it in backtofront visibility order, which supports streaming for volumetric visualization with a small footprint, since the client needs only maintain a Corner Table representaiton of a trianglemesh that is swept through the tetrahedronmesh. 

Bender: A Virtual Ribbon for Deforming 3D Shapes in Biomedical and Styling Applications Ignacio Llamas, Alex Powell, Jarek Rossignac, Chris Shaw. ACM Symposium on Solid and Physical Modeling (SPM). pp. 8999, June 2005. GVU Tech Report GITGVU0425. PDF 
DESIGN  HUMANSHAPE INTERACTION  FREEFORM DEFORMATIONS 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. 

Tightening: CurvatureLimiting Morphological Simplification. Jason Williams and Jarek Rossignac. ACM Symposium on Solid and Physical Modeling (SPM). pp. 107112, June 2005. GVU Tech Report GITGVU0427. PDF 
SIMLIFICATION  MORPHOLOGY  CONSTRAINEDHULL The mortar of a shape (2D area or 3D solid) is the alphahull (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. 

OrthoMap: Homeomorphismguaranteeing normalprojection map between surfaces F. Chazal, A. Lieutier, and J. Rossignac. ACM Symposium on Solid and Physical Modeling (SPM). pp. 914, June 2005. GVU Tech Report GITGVU0428. PDF 
MODELING  SHAPE MAPPING  NORMALOFFSETTING  CLOSEST PROJECTION 

Surface simplification and 3D geometry compression Jarek Rossignac in Handbook of Discrete and Computational Geometry (2nd edition), CRC Press, Goodman and O'Rourke Edts. 2004. Chap. 54. 
TRIANGLE MESHES  SIMPLIFICATION  COMPRESSION  RESAMPLING A theoretical introduction, some practical implementations, and a comparative overview of various simplification, resampling, compression, and progressive refinement techniques for triangle meshes. 

EducationDriven Research in CAD Jarek Rossignac. ComputerAided Design Journal (CAD), Vol 36/14 pp 14611469, 2004. GVU Tech Report GITGVU0326. PDF 
EDUCATION  SUBDIVISION  HAUSDORFF DISTANCE  TOPOLOGY 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. 

Localized biLaplacian Solver on a Triangle Mesh and Its Applications ByungMoon Kim and Jarek Rossignac GVU Tech Report GITGVU0412. PDF 
TRIANGLEMESHES  LAPLACEBELTRAMI OPERATOR  SMOOTHING  PDE  FEM Partial differential equations (PDEs) with Laplacian or biLaplacian 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 subdomain, which is a portion of the surface defined by user or automatically selfadjusting. Our formulation permits to solve high order terms such as biLaplacian 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. 

Computing Maximal Tiles and Applications to ImpostorBased Simplification C. Andujar, P. Brunet, A. Chica, J. Rossignac, I. Navazo, A. Vinacua Computer Graphics Forum 23, pp. 401410. Proc. Eurographics, September 2004. PDF 
GRAPHICS  VOXELS  SIMPLIFICAITON  IMAGEBASED RENDERING 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 imagebased graphic acceleration. 

Delphi Encoding: Improving Edgebreaker by Geometry based Connectivity Prediction Volker Coors and Jarek Rossignac. The Visual Computer. 20(89)507520, 2004. GVU Tech Report GITGVU0330. PDF 
COMPRESSION  TRIANGLEMESHES  CONNECTIVITY PREDICTION Both geoemtry and connectivity are predicted from previously transmitted parts of a trianglemesh. 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. 

Plumber: A method for a multiscale decomposition of 3D shapes into tubular primitives and bodies M. Mortara, G. Patane, M. Spagnuolo, B. Falcidieno, J. Rossignac. ACM Symposium on Solid Modeling, 339344, 2004 (Short paper). GVU Tech Report GITGVU0326. PDF 
TRIANGLEMESH  MODELING  SHAPE SEGMENTATION  FEATURE IDENTIFICATION 

Blowing Bubbles for the Multiscale Analysis and Decomposition of TriangleMeshes M. Mortara, G. Patane, M. Spagnuolo, B. Falcidieno, and J. Rossignac. Algorithmica. 38(1):227248 January 2004. GVU Tech Report GITGVU0327.PDF 
MODELING  TRIANGLEMESHES  SHAPEANALYSIS  FEATUREEXTRACTION We propose a multiresolution 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. 

Optimal IsoSurfaces C. Andujar, P. Brunet, A. Chica, I. Navazo, J. Rossignac, A. Vinacua. Proc. CAD Conf. pp. 503511, Thayland, May 2004. 
ISOSURFACE The portion P of the isosurface 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 isosurface 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 isosurfaces: triangle count, genus, and number of shells. CAD'04 Best Paper Award. 

Optimizing the topological and combinatorial complexity of iIsoSurfaces C. Andujar, P. Brunet, A. Chica, I. Navazo, J. Rossignac, A. Vinacua. Journal of ComputerAided Design & Applications, 37(8):847857, 2005. 
ISOSURFACE A Journal version of the awardwinning "Optimal IsoSurfaces" paper. 

3D Mesh Compression Jarek Rossignac. Chapter in the Visualization Handbook. Academic Press. Eds. C. Hansen and C. Johnson. GVU Tech Report GITGVU0321.PDF 
TRIANGLE MESHES  COMPRESSION A comparative overview of various compression and progressive refinement techniques for triangle meshes. 

Efficient Edgebreaker for surfaces of arbitrary topology T. Lewiner, H. Lopes, J. Rossignac and A. WilsonVieira1. SIBGRAPI/SIACG,218255, 2004. PDF 
COMPRESSION  TRIANGLEMESHES Edgebreaker and Spirale Reversi are examples of efficient schemes to compress and decompress the connectivity of trianglemesnes. 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, onepass 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. 

PhotoMeter Easytouse MonoGraphoMetricsVisual Metrology from Calibrated Images, Hendrik Mueller (Master's Thesis) supervised by Jarek Rossignac and Markus Wacker. July 2004. PDF  COMPUTER VISION  3D RECONSTRUCTION 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.  
Compressing volumes and animations J. Rossignac. Tutorial Notes. Eurographics 2004. 
MODELING  COMPRESSION  ANIMATION  VOLUMES A lecture on geoemtry compression. 

SwingWrapper: Retiling Triangle Meshes for Better Compression M. Attene, B. Falcidieno, M. Spagnuolo and J. Rossignac. ACM Transactions in Graphics, 22(4):982996, October 2003. GVU Tech Report GITGVU0204. PDF 
MODELING  COMPRESSION  RESAMPLING  TRIANGLE MESHES 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 L_{2} distortion of about 0.01% of the bounding box diagonal. 

Compressed Piecewise Circular Approximation of 3D Curves Alla Safonova and Jarek Rossignac. ComputerAided Design, Volume 35, Issue 6, Pages 533547, May 2003. GVU Tech Report GITGVU0105. PDF 
MODELING  COMPRESSION  SIMPLIFICATION  CURVES  ERROR Consider a polygonal curve P in 3D of n vertices, generated through adaptive sampling, so that it approximates an original curve, O, within tolerance e_{0}. We present an efficient algorithm for computing a continuous curve C that approximates P within tolerance e_{1} and is composed of a chain of m circular arcs, whose endpoints 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 

The SAFARI Interface for Visualizing Timedependent Volume Data Using IsoSurfaces and Contour Spectra Lutz Kettner, Jarek Rossignac, Jack Snoeyink. Computational Geometry Theory and Applications (CGTA), vol. 25. No 12, pp. 97116, 2003. GVU Tech Report GITGVU0113. PDF 
SCIENTIFIC VISUALIZATION  4D  ANIAMTION  ISOSURFACES We describe a geometric basis for the visualization of timevarying 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. 

Edgebreaker: A Simple Compression Algorithm for Surfaces with Handles Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares. Computers&Graphics International Journal, Vol. 27, No. 4, pp. 553567, 2003. 
COMPRESSION  TOPOLOGY 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 CornerTable 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. 

EdgeSharpener: A geometric filter for recovering sharp features in uniform triangulations Marco Attene, Bianca Falcidieno, Jarek Rossignac, and Michela Spagnuolo. Eurographics Symposium on Geometry Processing (SGP). Aachen, Germany. June 2003. GVU Tech Report GITGVU0319. PDF 
MODELING  SAMPLING  TRIANGLEMESHES  SURFACE ANALYSIS  SHARP FEATURES 3D scanners, isosurface 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 EdgeSharpener 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 postprocessing significantly reduces the error produced by the initial sampling process. For example, we have observed that the L2 error introduced by the SwingWrapper remeshingbased compressor can be reduced down to a fifth by executing EdgeSharpener after decompression, with no additional information. 

Dynapack: SpaceTime compression of the 3D animations of triangle meshes with fixed connectivity L. Ibarria and J. Rossignac. ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), pp. 126135, San Diego, July 2003. GVU Tech Report GITGVU0308. PDF 
COMPRESSION  TRIANGLEMESHES  ANIAMTIONS Dynapack exploits spacetime 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. 

An efficient subdivision inversion for Wavemeshbased progressive compression of 3d triangle meshes Sebastien Valette, Jarek Rossignac, Remy Prost. IEEE International Conference on Image Processing (ICIP), 777780, 2003. GVU Tech Report GITGVU0320. PDF 
COMPRESSION  TRIANGLEMESHES  WAVELETS 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 monoresolution approaches in terms of connectivity compression. 

Twister: A spacewarp operator for the twohanded editing of 3D shapes 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. 663668, July 2000. GVU Tech Report GITGVU0318. PDF 
DESIGN  HUMANSHAPE INTERACION  FREEFORM DEFORMATION  WARPING  SCULPTING A freeform deformation that warps a surface or solid may be specified in terms of one or several pointdisplacement 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 twohand interface and the resulting deformation are intuitive and hence offer an effective direct manipulation tool for creating or modifying 3D shapes. 

ShieldTester: Celltocell visibility test for surface occluders Isabel Navazo, Jarek Rossignac, Joan Jou, Rahim Shariff. Computer Graphics Forum 22(3):291302. Proc. of Eurographics, 2003. GVU Tech Report GITGVU0314. PDF 
VISIBILITY  SURFACEOCCLUDERS  TOPOLOGY We present a novel CellToCell 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. 

Outofcore compression & decompression of large ndimensional scalar fields Lorenzo Ibarria, Peter Lindstrom, Jarek Rossignac, Andrzej Szymczak. Proc. of Eurographics, pp. 343348, September 2003. GVU Tech Report GITGVU0328. PDF Also available as Report UCRLJC151934 from the DOE.  COMPRESSION  STRUCTURED HIGHERDIMENSIONAL GRIDS  SCIENTIFIC COMPUTATION  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 ndimensional scalar field is an implicit polynomial of degree n1. 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 outofcore 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 (n1)dimensional slice of the data. 

Collision Prediction for Polyhedra under Screw Motions ByungMoon Kim and Jarek Rossignac, ACM Symposium in Solid Modeling and Applications, pp. 410, June 2003. GVU Tech Report GITGVU0312. PDF 
ANIAMTION  COLLISION PREDICTION  SCREW MOTIONS 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 speedup the prediction of collisions by about 30%, avoiding on average 3/4 of the rootfinding queries even when the object actually collide. 

Compact RobotGenerated 3D Maps for Efficient Wireless Transmission Michael Kaess, Ronald C. Arkin, Jarek Rossignac. 11th International Conference on Advanced Robotics (ICAR), 2003. GVU Tech Report GITGVU0322. PDF 
COMPRESSION  3D SCANNING  DEPTH FIELDS  ROBOTICS This work focuses on realtime compression of laser data on board a mobile robot platform. Data is trans mitted from the robot over lowbandwidth 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, JpegLS), 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 JpegLS compression performs best in this setting. 

Finger Sculpting with Digital Clay: 3D Shape Input and Output through a ComputerControlled Real Surface Rossignac, Allen, Book, Glezer, EbertUphoff, Shaw, Rosen, Askins, Bai, Bosscher, Gargus, Kim, Llamas, Nguyen, Yuan, Zhu. Shape Modeling International Conference Korea, Seoul, May, 2003. GVU Tech Report GITGVU0305. PDF 
DESIGN  HUMANSHAPE INTERACTION  DIGITAL CLAY 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. 

FanGrower: A simple biresolution trianglemesh Ram Somani and Jarek Rossignac. April 2003. GVU Tech Report GITGVU0311. PDF 
MODELING  TRIANGLEMESH  SIMPLIFICATION  LOD  GRAPHIC ACCELERATION  FACECLUSTERING The FanGrower algorithm segments a triangle mesh into regions (called caps), which may each be closely approximated by a trianglefan. Once the caps are formed, their rims, which form the intercap boundaries, are simplified, replacing each fan by its framea 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 superfaces, which were restricted to nearly planar configurations and approximated by nearly planar fans. We discuss several capgrowing approaches. 

Collision Prediction ByungMoon Kim and Jarek Rossignac. ASME Journal of Computing and Information Science in Engineering (JCISE), vol. 3, no. 4, pp. 295301, Dec. 2003. 
ANIAMTION  COLLISION PREDICTION  SCREW MOTION Abstract 

Finger Sculpting with Digital Clay Joshua Gargus, Byungmoon Kim, Ignacio Llamas, Jarek Rossignac, and Chris Shaw. October 2002. GVU Tech Report GITGVU0222. PDF 
HUMANCOMPUTER INTERACTION  HAPTICS  DIGITAL CLAY Abstract 

Spacetime surface simplification and Edgebreaker compression of cel animations Vivek Kwatra and Jarek Rossignac. International Journal of Shape Modeling, 8(2):119137. December 2002. GVU Tech Report GITGVU0223. PDF 
ANIAMTION  SIMPLIFICATION  COMPRESSION  CEL ANIAMTION Abstract 

Piecewise Regular Meshes: Construction and Compression A. Szymczak, J. Rossignac, and D. King. Graphical Models, Volume 64, pp.183198, May 2002. PDF 
TRIANGLEMESHES  SAMPLING  COMPRESSION  DEPTHMAPS Abstract 

Edgebreaker: A Simple Compression Algorithm for Surfaces with Handles Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares. ACM Symposium on Solid Modeling and Applications, pp. 289296, June 2002. GVU Tech Report GITGVU0203. PDF 
TRIANGLEMESHS  COMPRESSION  HANDLES  TOPOLOGY Abstract 

An Unequal Error Protection Method for Progressively Compressed 3D Meshes Ghassan AlRegib, Yucel Altunbasak and Jarek Rossignac. International Conf. on Acoustics, Speech and Signal Processing ICASSP'02. Vol. 2, pp. 20412044, Orlando, May 2002. 
TRIANGLEMESHES  PROGRESSIVE TRANSMISSION  COMPRESSION  SIMPLIFICATION  ERROR CORRECTION Abstract 

A Joint Source and Channel Coding Approach for Progressively Compressed 3D Mesh Transmission, Yucel Altunbasak, Ghassan AlRegib and Jarek Rossignac. IEEE International Conference on Image Processing (ICIP), Rochester NY, Vol. 2, pp. 161164, Sept. 2002. 
TRIANGLEMESHES  PROGRESSIVE TRANSMISSION  COMPRESSION  SIMPLIFICATION  ERROR CORRECTION Abstract 

Protocol for Streaming Compressed 3D Animations over Lossy Channels Ghassan AlRegib, Yucel Altunbasak, Jarek Rossignac, and Russell Mersereau. IEEE International Conference on Multimedia and Expo (ICME), Lausanne, Switzerland, Vol. 1, pp. 353 356, Lausanne, August 2629, 2002. 
TRIANGLEMESHES  PROGRESSIVE TRANSMISSION  COMPRESSION  SIMPLIFICATION  ERROR CORRECTION Abstract 

Modeles CAO multiresolution A. Crosnier and J.R. Rossignac. Chapter 13 in Teleoperation et realite virtuelle, Eds. A. Kheddar and P. Coiffet, Pub. Lavoisier, 2002. (In French.) 
MODELING  SIMLIFICATION  LEVELSOFDETAIL 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 

Edgebreaker on a Corner Table: A simple technique for representing and compressing triangulated surfaces Jarek Rossignac, Alla Safonova, Andrzej Szymczak. Chapter in Hierarchical and Geometrical Methods in Scientific Visualization, Farin, G., Hagen, H. and Hamann, B., eds. SpringerVerlag, Heidelberg, Germany. pp 4150, January 2003. GVU Tech Report GITGVU0112. PDF 
COMPRESSION  TRIANGLEMESHES  EDGEBREAKER Abstract 

Determination of the correct eye position for viewing perspective images of 3D scenes Justin Jang and Jarek Rossignac. July 2001. GVU Tech Report GITGVU0105. PDF 
COMPUTER VISTION  PERSPECTIVE  VANISHING POINTS  IMAGE PROCESSING Abstract 

Computing and visualizing poseinterpolating 3D motions J. Rossignac and J. Kim. Journal of ComputerAided Design, vol. 33, no. 4, pp. 279291, April 2001. 
ANIMATION  INTERPOLATING MOTION  SCREWMOTION  SWEPT VOLUMES  ENVELOPES 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 premultiplication of the 4x4 matrix defining the worldtoscreen mapping by any 4x4 matrix. The consecutive positions that correspond to constant time steps of a screw motion may be obtained by premultiplying the worldtoscreen 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. 

An Edgebreakerbased Efficient Compression Scheme for Connectivity of Regular Meshes A. Szymczak, D. King, J. Rossignac. Computational Geometry: Theory and Applications, Vol 20, No 2, pp. 5368, Oct 2001. 
COMPRESSION  TRIANGLEMESHES  EDGEBREAKER Abstract 

Surface simplification and Edgebreaker compression for 2D Cell Animations Vivek Kwatra and Jarek Rossignac, Shape Modeling International, 2001. 
COMPRESSION  SMPLIFICATION  CEL ANIMATION  EDGEBREAKER Abstract 

Hoops: 3D curves as conservative occluders for cell visibility Pere Brunet, Jarek Rosignac, Isabel Navazo, Carlos SaonaVazquez. Computer Graphics Forum, Proc. Eurographics, 19(3):499506, 2001. 
VISIBILITY  OCCLUSION  SURFACE OCCLUDERS Abstract 

A prototype system for visualizing timedependent volume data L. Kettner, A. Mascarenhas, J. Rossignac and J. Snoeyink 17th European Workshop on Computational Geometry, 2001, 1316. 
SCIETIFIC VISUALIZATION  VOLUMES  ANIMATIONS  USERINTERFACE  ISOSURFACES Abstract 

3D compression made simple: Edgebreaker on a Corner Table Jarek Rossignac, Alla Safonova, and Andezej Szymczak Shape Modeling International Conference, pp: 278283, Genoa, Italy May 2001. 
COMPRESSION  TRIANGLEMESHES  EDGEBREAKER Abstract 

Compressed Progressive Meshes Renato Pajarola and Jarek Rossignac IEEE Transactions on Visualization and Computer Graphics, Vol. 6, No. 1, pp. 7993, JanuaryMarch 2000. GVU Tech Report GITGVU0004. PDF 
COMPRESSION  SIMPLIFICATION  PROGRESSIVE TRANSMISSION  TRIANGLE MESHES The CPM approach proposed here uses a new insertspray 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 nonprogressive techniques need to restore the fixedresolution model. 

Screw motions for the animation and analysis of mechanical assemblies Jay Kim and Jarek Rossignac International Journal of the Japan Society of Mechanical Engineers, 2000. GVU Tech Report GITGVU9935. PDF 
ANIMATION  MOTIONEDITING  POSEINTERPOLATION  SCREWMOTION 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. 

Grow&Fold: Compressing the connectivity of tetrahedral meshes Andrzej Szymczak and Jarek Rossignac ComputerAided Design, 32(8/9), 527538, July/August, 2000. 
COMPRESSION  TETRAHEDRAMESHES Abstract 

Squeeze: Fast and Progressive Decompression of Triangle Meshes Renato Pajarola and Jarek Rossignac Computer Graphics International Conference, Switzerland, pp. 173182, June 2000. GVU Tech Report GITGVU0005. PDF 
SIMPLIFICATION  PROGRESSIVE TRANSMISSION  TRIANGLEMESHES Compression techniques for trianglemesh 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, realtime decompression algorithms for hardware or software implementations. Because these three objectives impose contradictory constraints on the compressed format, previously reported efforts focus primarily on onesometimes twoof 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 levelofdetail is needed. 

An Edgebreakerbased efficient compression scheme for regular meshes Andrzej Szymczak, Davis King, Jarek Rossignac 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, August 1619, 2000. 
COMPRESSION  TRIANGLEMESHES  EDGRBREAKER  REGULAR MESHES Abstract 

Dealing with Shape complexity and compression for Internet access and graphic applications J. Rossignac Eurographics 2000. 
COMPRESSION  SIMPLIFICATION  PROGRESSIVE TRANSMISSION  INTERNET Abstract 

Connectivity Compression for Irregular Quadrilateral Meshes Davis King, Jarek Rossignac. 1999 GVU Tech Report GITGVU9936. PDF 
COMPRESSION  TRIANGLEMESHES  QUADMESHES  POLYHEDRA Abstract 

Wrap&Zip decompression of the connectivity of triangle meshes compressed with Edgebreaker Jarek Rossignac and Andrzej Szymczak Journal of Computational Geometry, Theory and Applications, Volume 14, Issue 13, pp. 119135, November 1999. GVU Tech Report GITGVU9908. PDF 
COMPRESSION  TRIANGLEMESHES  EDGEBREAKER  DECOMPRESSION Abstract 

Triboxbased simplification of threedimensional objects Andre Crosnier and Jarek Rossignac Computers&Graphics, Vol. 23, No. 3, pp. 429438, March 1999. Best Paper Award.  SIMPLIFICATION  CONSTRAINED CONVEX HULL  LOD Abstract Best Paper Award. 

Optimal Bit Allocation in Compressed 3D Models Davis King and Jarek Rossignac Journal of Computational Geometry, Theory and Applications. Volume 14, Issue 13, pp. 91118. November 1999. GVU Tech Report GITGVU9907. PDF  COMPRESSION SIMPLIFICATION  TRIANGLE MESHES  SHAPE COMPLEXITY To use 3D models on the Internet or in other bandwidthlimited 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. 

Edgebreaker: Connectivity compression for triangle meshes Jarek Rossignac. IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 1, pp. 4761, January  March 1999. GVU Tech Report GITGVU9835. PDF Best Paper Award.  COMPRESSION  TRIANGLEMESHES  EDGEBREAKER Abstract Best Paper Award. 

Implant Sprays: Compression of Progressive Tetrahedral Mesh Connectivity Renato Pajarola, Jarek Rossignac, and Andrzej Szymczak. IEEE Visualization, San Francisco, October 2429, 1999. GVU Tech Report GITGVU9916. PDF  COMPRESSION  TRIANGLEMESHES  SIMPLIFICATION  PROGRESSIVE TRANSMISSION Abstract 

Guaranteed 3.67V bit encoding of planar triangle graphs Davis King and Jarek Rossignac. 11th Canadian Conference on Computational Geometry (CCCG'99), pp. 146149, Vancouver, CA, August 1518, 1999. GVU Tech Report GITGVU9917. PDF  COMPRESSION  TRIANGLEMESHES  EDGEBREAKER Abstract 

Matchmaker: Manifold BReps for nonmanifold rsets Jarek Rossignac and David Cardoze. Proceedings of the ACM Symposium on Solid Modeling, pp. 3141, June 1999. GVU Tech Report GITGVU9903. PDF  MODELING  TOPOLOGY  NONMANIFOLD SINGULARITIES  PSEUDOMANIFOLDS Abstract 

Distributed Information and Computation in Scientific and Engineering Environments 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. 
COMPRESSION  SIMPLIFICATION  VISUALIZATION Abstract 

Grow&Fold: Compression of Tetrahedral Meshes Andrzej Szymczak and Jarek Rossignac Proc. ACM Symposium on Solid Modeling, pp. 5464, June 1999. GVU Tech Report GITGVU9902. PDF  COMPRESSION  TETRAHEDRAMESHES Abstract 

Solid Modeling Jarek Rossignac and Aristides Requicha Chapter in the Encyclopedia of Electrical and Electronics Engineering, Ed. J. Webster, John Wiley & Sons. 1999. GVU Tech Report GITGVU9909. PDF  SOLID MODELING  ROBUSTNESS  BOUNDARYEVALUATION  OFFSETTING  TOPOLOGY Abstract 

Blist: A Boolean list formulation of CSG trees J. Rossignac. October1998. GVU Tech Report GITGVU9904. PDF  CSG  BOOLEAN EXPRESSIONS  MODELING Abstract 

Geometry coding and VRML Gabriel Taubin, William Horn, Frederic Lazarus, and Jarek Rossignac Proceedings of the IEEE, pp. 12281243, vol. 96, no. 6, June 1998.  COMPRESSION  TRIANGLEMESHES  VRML Abstract 

Geometric Compression through Topological Surgery Gabriel Taubin and Jarek Rossignac. ACM Transactions on Graphics, Volume 17, Number 2, pp. 84115, April 1998. Best Paper Award.  COMPRESSION  TRIANGLEMESHES  MPEG4 Abstract Best Paper Award. 

3D server for Interacting with Complex Remote Models Jarek Rossignac Computer Graphics International Congress (CGI '98 congress), Hanover, pp. 324335, June 2426, 1998. 
COMPRESSION  TRIANGLEMESHES  SIMPLIFICATION  PROGRESSIVE TRANSMISSION Abstract 

Structured Topological Complexes: A featurebased API for nonmanifold topologies Jarek Rossignac Proceedings of the ACM Symposium on Solid Modeling, pp. 19, 1997. GVU Tech Report GITGVU9626.PDF  MODELING  TOPOLOGY  STRUCTURES  SIMPLICIAL COMPLEXES Abstract 

The 3D revolution: CAD access for all J. Rossignac International Conference on Shape Modeling and Applications, AizuWakamatsu, Japan, IEEE Computer Society Press, pp. 6470, March 1997. GVU Tech Report GITGVU9629.  MODELING  3D ACCESS  INTERNET The manufacturing industry has invested vast amounts of resources in the deployment and use of solid modeling technology. Although expensive to generate and potentially 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 affordable 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 nondesigners 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 fundamental research issues, and reviews recent advances in 3D data compression, in the automatic generation of levelsofdetail for interactive rendering, and in the innovative exploitation of 3D input devices for an intuitive and effective navigation. 

Simplification and Compression of 3D Scenes J. Rossignac Tutorial. Eurographics, 1997.  COMPRESSION  TRIANGLEMESHES  SIMPLIFICATION  PROGRESSIVE TRANSMISSION  Abstract  
Specification, representation, and construction of nonmanifold geoemtric structures J. Rossignac Lecture in Course 29 on Representations of Geometry for Computer Graphics at SIGGRAPH 1996.  SOLID MODELING  BREP  NONMANIFOLD REPRESENTATIONS  TOPOLOGY  SGC  MAIL  CNRG Survey of boundary representation schemes for nonmanifold, mixeddimensional 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 NonRegularized Geometry (CNRG) extension sof CSG to nonmanifold modeling. The file contains the lecture notees, a glossary of key topological concepts, and the lecture slides. 

Topologically exact evaluation of polyhedra defined in CSG with loose primitives Raja Banerjee and Jarek Rossignac Computer Graphics Forum, Vol. 15, No. 4, pp. 205217, 1996. PDF(.pdf?) 
MODELING  CSG  BOUNDARY EVALUATIION  ROBUSTNESS  BOOLEANS Floating point roundoff 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 symbolmanipulation 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 halfspaces and produces a polyhedral boundary model that has the exact topology of the corresponding solid. Each halfspace 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 halfspaces, each having the freedom to snap to a nearby halfspace 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 halfspaces, away from the geometric calculations, yields a simple and totally robust boundary evaluation algorithm. 

Fullrange approximations of triangulated polyhedra Remi Ronfard and Jarek Rossignac Computer Graphics Forum, Proceedings of Eurographics, pp. C67, Vol. 15, No. 3, August 1996. PDF (10MB, low quality) 
SIMPLIFICATION  TRIANGLEMESHES  LOD  EDGECOLLAPSE  QUADRIC ERROR Abstract 

A Road Map to Solid Modeling Chris Hoffmann and Jarek Rossignac IEEE Transactions on Visualization and Computer Graphics, vol. 2, No. 1, pp. 310, March 1996. 
MODELING  SURVEY Abstract 

MAGISET: Architecture and Programming Interface for a Universal Modeler Jarek Rossignac Proceedings of the Blaubeuren Workshop on Graphics and Modeling, Germany 1996. 
MODELING  TOPOLOGY  NONMANIFOLD  MULTIUMATERIAL Abstract 

CSG formulations for identifying and for trimming faces of CSG models Jarek Rossignac CSG'96: Settheoretic solid modeling techniques and applications, Information Geometers, Ed. John Woodwark. 1996. 
MODELING  CSG Abstract 

The IBM 3D Interaction Accelerator (3DIX) Paul Borrel, K. Cheng, Pierre Darmon, Peter Kirchner, Jim Lipscomb, Jai Menon, Josh Mittleman, Jarek Rossignac, BengtOlaf Schneider, Bob Wolfe IBM Technical Report. 1995.  SIMPLIFICATION  GRAPHICS Abstract 

MBuffer: a flexible MISD architecture for advanced graphics BengtOlaf Schneider and Jarek Rossignac Computers&Graphics, Volume 19, Issue 2, Pages 239246, MarchApril 1995.  GRAPHICS  HARDWARE  DEPTHINTERVAL BUFFER  STENCILS Abstract 

BRUSH as a Walkthrough System for Architectural Models BengtOlaf Schneider, Paul Borrel, Jai Menon, Josh Mittleman, Jarek Rossignac In Rendering Techniques, Proc. 5th Eurographics Workshop on Rendering, SpringerVerlag, 389399, New York, 1995. 
MODELING  Abstract 

Triangulating multiplyconnected polygons: A simple, yet efficient algorithm Remi Ronfard and Jarek Rossignac. Computer Graphics Forum, Proc. Eurographics, Vol 13, No 3, pp. C281C292, Sept 1994. Best Paper Award. PDF (11MB, Low Quality) 
MODELING  Abstract Best Paper Award. 

Research Issues in Modelbased Visualization of Complex Data Sets Jarek Rossignac and M. Novak IEEE Computer Graphics & Applications, Vol. 14., No 2., pp. 8385, March 1994.  MODELING  Abstract 

AGRELs and BIPs: Metamorphosis as a Bezier curve in the space of polyhedra Jarek Rossignac and Anil Kaul Computer Graphics Forum, Proc. Eurographics, Oslo, Norway, Vol 13, No 3, pp. C179C184, Sept 1994.  MODELING  Abstract 

Processing Disjunctive forms directly from CSG graphs Jarek Rossignac Proceedings of CSG 94: Settheoretic Solid Modelling Techniques and Applications, Information Geometers, pp. 5570, Winchester, UK, April 1994.  MODELING  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 idnumber 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 minimax bounds for CSG solids. An application of this technique to the hardware assisted rendering of CSG models with sculptured primitives will be briefly presented. 

Through the cracks of the solid modeling milestone Jarek Rossignac In From Object Modelling to Advanced Visualization, Eds. S. Coquillart, W. Strasser, P. Stucki, Springer Verlag, pp. 175, 1994.  MODELING  Abstract 

Representing and visualizing complex continuous geometric models Jarek Rossignac In Scientific Visualization: Advances and Challenges, Academic Press. Ed. L Rosenblum. pp. 337348, 1994.  MODELING  Abstract 

Simplifying interactive design of solid models: A hypertext approach Martin van Emmerik, Ari Rappoport, and Jarek Rossignac The Visual Computer, vol. 9, No. 5, pp. 239254, March 1993. 
MODELING  DESIGN  GUI  SCENE GRAPH  HYPERTEXT  FEATURES  PATTERNS  RECURSION  CSG We propose a new representation for scene graphs and CSG graphs that supports combinations of hierarchical patterns and recursive patterns. We also propose a multimodal 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. 

Multiresolution 3D approximations for rendering complex scenes Jarek Rossignac and Paul Borrel In Geometric Modeling in Computer Graphics, pp. 455465, Springer Verlag, Eds. B. Falcidieno and T.L. Kunii, Genova, Italy, June 28July 2, 1993. 
MODELING  TRIANGLE MESHES  SIMPLIFICATION  VERTEX CLUSTERING  LOD We present a novel approach to the simplification of triangle meshes and more generally simplicial complexes in 2D and 3D. Our VertexClustering 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 VertexClustering method was used in several commercial products, products and academic multiresolution systems to accelerate the rendering of complex 3D scenes. 

Representing Solids and Geometric Structures J. Rossignac In Geometry and Optimization Techniques for Structural Design, pp. 144, Eds. S. Kodiyalam, M. Saxena, Computational Mechanics Publications, Southhampton, 1993.  MODELING  Abstract 

SolidInterpolating Deformations: Construction and Animation of PIPs Anil Kaul and Jarek Rossignac Computers&Graphics. Vol. 16, No. 1, pp. 107115, 1992. Best Paper Award at Eurographics 91.  MODELING  Abstract Best Paper Award. 

Solid Modeling and Beyond Aristides Requicha and Jarek Rossignac IEEE Computer Graphics&Applications, Special issue on CAGD, pp. 3144, September 1992. Best Paper Award.  MODELING  Abstract 

Interactive Inspection of Solids: CrossSections and Interferences Jarek Rossignac, Abe Megahed, and BengtOlaf Schneider Proc. ACM Siggraph, ACM Computer Graphics, Vol. 26, No. 2, pp. 353360, July 1992.  MODELING  Abstract 

MBuffer: A flexible MISD Architecture for Advanced Graphics BengtOlaf. Schneider and Jarek Rossignac Proc. 7th Eurographics Workshop on Computer Graphics Hardware, Cambridge, UK, September 1992.  MODELING  Abstract 

Hidden contours on a framebuffer Jarek Rossignac and Martin van Emmerik Proceedings of the 7th Eurographics Workshop on Computer Graphics Hardware, Cambridge, UK, September 1992.  MODELING  Abstract 

Correct Shading of Regularized CSG solids using a DepthInterval Buffer Jarek Rossignac and Jeff Wu In Advances in Computer Graphics Hardware V, Proc of the Eurographics Workshop on Graphics Hardware. Eds. R.L. Grimsdale and A. Kaufman, Springer Verlag, pp. 117138, 1992. PDF 
GRAPHICS  CSG  HARDWARWE A convenient interactive design environment requires efficient facilities for shading solid models represented in CSC. Shading techniques based on boundary evaluation or ray casting that require calculations of geometric intersections are too inefficient for interactive graphics when CSC primitives with curved (parametric) surfaces are involved. Projective approaches, where the primitive surfaces are scanconverted using standard hardwaresupported graphic functions are preferred. Since not all the points of the faces of a CSC primitive lie on the CSC solid, scan conversion must be combined with a procedure that tests the produced 3D surfacepoints against the original CSC expression. Point classifications against primitives defined by arbitrary curved boundaries may be performed, without geometric intersections, through depthcomparisons at each pixel. This approach has been implemented for the PixelPower machine by researchers at UNC. It deals with complex CSC trees by converting CSC expressions into sumofproduct form and repeatedly scanconverting the primitives of each product. The Trickle algorithm, which considerably reduces the number of scanconversions in the general case has been developed at IBM Research and presented elsewhere. This paper discusses several recent improvements to the original Trickle algorithm. The overall algorithm has been simplified. The" scanconversion process and the point classification tests have been modified to correctly handle cases where several primitive faces coincide within an arbitrary numerical resolution. These enhancements are not only necessary for on/on cases in regularized Boolean expressions, but also for processing pairs of faces near their common edges. Finally, we point out that a simple twopass extension of the trickle algorithm using an auxiliary shadow buffer suffices to compute directly from CSC shaded images with shadows. 

BIERPAC: Basic Interactive Editing for the Relative Positions of Assembly Components Jarek Rossignac, Paul Borrel, J. Mastrogiulio, Jai Kim IBM Research Report RC 17339, 1991. 
HUMANSHAPE INTERACTION  MOTIONS  SCENE GRAPHS Abstract 

Constructive NonRegularized Geometry Jarek Rossignac, and Aristides Requicha ComputerAided Design, Vol. 23, No. 1, pp. 2132, Jan./Feb. 1991.  MODELING  NONREGULARIZED OPERATIONS  CSG  TOPOLOGY Solid modeling is concerned with the construction and manipulation of unambiguous computer representations of solid objects. These representations permit to distinguish between the interior, the boundary, and the complement of a solid. They are conveniently specified in CSG (Constructive Solid Geometry) by a construction tree that has solid primitives as leaves and rigid body motions or regularized Boolean operations as internal nodes. Algorithms for classifying sets with respect to CSG trees and for evaluating the boundaries of the corresponding solids are known, at least for simple geometric domains. Emerging CAD applications require that we extend the domain of solid modelers to support more general and more structured geometric objects. This paper focuses on dimensionally nonhomogeneous, nonclosed pointsets with internal structures. These entities are well suited for dealing with mixeddimensional nonmanifold objects in Rn that have dangling or missing boundary elements, and that may be composed of several regions. A boundary representation for such objects has been described elsewhere. In this paper, we propose to specify and represent inhomogeneous objects in terms of Constructive NonRegularized Geometry (CNRG) trees that extend the domain of CSG by supporting nonregularized primitive shapes as leaves and by providing more general settheoretic and topological operators at interior nodes. We present a syntax and semantics of the operators in CNRG and outline some basic algorithms for classifying pointsets with respect to the regions of objects represented by CNRG trees. Award. 

Accurate scanconversion of triangulated surfaces Jarel Rossignac In Advances in Computer Graphics Hardware VI, Proc. of 6th Eurographcis Workshop on Computer Graphics Hardware, Ed. A. Kaufman, Springer Verlag, Berlin. Vienna, September 1991. 
MODELING  Abstract 

Zbuffer rendering from CSG: The Trickle Algorithm David Epstein, Frederik Jansen, and Jarek Rossignac IBM Research Report RC 15182. 1990.  MODELING  Abstract 

Issues on featurebased editing and interrogation of solid models Jarek Rossignac Computers&Graphics, Vol. 14, No. 2, pp. 149172, 1990. 
DESIGN  CSG  FEATURES Abstract Best Paper Award. 

Multiple depthbuffer rendering of CSG David Epstein, Nader Gharachorloo, Frederik Jansen, Jarek Rossignac, and Christos Zoulos IBM Research Report, January, 1989. 
MODELING  Abstract 

Active Zones in CSG for Accelerating Boundary Evaluation, Redundancy Elimination, Interference Detection and Shading Algorithms Jarek Rossignac and Herbert Voelcker ACM Transactions on Graphics, Vol. 8, pp. 5187, 1989.  SOLID MODELING  SIMPLIFICATION  REDUNDANCY Solids defined by Boolean combinations of solid primitives may be represented in Constructive Solid Geometry (CSG) as binary trees. Most CSGbased algorithms (e.g. for boundary evaluation, graphic shading, interference detection) do various forms of set membership classification by traversing the tree associated with the solid. These algorithms usually generate intermediate results that do not contribute to the final result, a nd hence may be regarded as redundant and a source of inefficiency. To reduce such inefficiencies, we associate with each primitive A in a tree S an :hp2.active zone:ehp2. Z that represents the region of space where changes to A affect the solid represented by S, and we use a representation of Z instead of S for set membership classification. In the paper we develop a mathematical theory of active zones, prove that they correspond to the intersection of certain nodes of the original trees, and show how they lead to efficient new algorithms for boundary evaluation, for detecting and eliminating redundant nodes in CSG trees, for interference (nullset) detection, and for graphic shading. 

SGC: A DimensionIndependent Model for Pointsets with Internal Structures and Incomplete Boundaries Jarek Rossignac and Michael O'Connor In Geometric Modeling for Product Engineering, Proceedings of the IFIP Workshop on CAD/CAM, Eds. M. Wosny, J. Turner, K. Preiss, NorthHolland, pp. 145180, 1989.  MODELING  Abstract 

Considerations on the Interactive Rendering of Fourdimensional Volumes Jarek Rossignac Proc. of the Chapel Hill Workshop on Volume Visualization, pp. 6776, 1989.  MODELING  VISUALIZATION  FOURDIMENSIONS  INHOMOGENEOUS MATERIAL  PROCESS SIMULATION Fourdimensional geometric models are convenient for representing and analyzing the variation of physical properties across the volume of a part, the evolution of the shape of several objects through time, the topological properties of algebraic surfaces, and many other phenomena. Geometric calculations in four dimensions have been extensively studied in mathematics and recently several data structures for representing hypersolids (i.e., 4D objects) have been proposed and algorithms for interrogating and performing Boolean and other operations among such hypersolids have been developed. Graphics is an inherent part of geometric design and should be used to visualize and inspect 4D shapes. Unfortunately, projections from the 4D space to a 2D screen are accompanied with an inevitable loss of information and thus produce ambiguous and intuitively puzzling pictures. This paper reviews some known techniques for displaying hypersolids in wireframes and considers improvements based on shading information and graphic interaction. To reduce processing cost and exploit the human ability to focus on relevant portions of an image, interactive manipulations of projections of the entire hypersolid onto the screen are preferable to families of 3D crosssections obtained by moving a sectioning hyperplane. Interaction with pictures obtained by direct projection onto the screen is limited to 4D transformations and does not take advantage of the current hardware capabilities for shading and for hidden surface removal. An indirect approach is proposed, in which a projection onto a selected 3D hyperplane is computed and the resulting 3D solid interactively manipulated to interrogate its internal structures using extensions of standard 3D graphics. Award. 

Relationship between Sbounds and Active Zones in Constructive Solid Geometry Stephen Cameron and Jarek Rossignac Proceedings of Theory and Practice of Geometric Modeling, pp. 369348, Blaubeuren, Germany, October, 1988. PDF  MODELING  CSG  ACTIVE ZONES  SBOUNDS We show that Sbounds are an approximation of the active zones of CSG primitives. 

Procedural Models for Design and Fabrication Jarek Rossignac, Paul Borrel, and Lee Nackman In Automation in the Design and Manufacture of Large Marine Systems, Proc. of the MIT Sea Grant Symposium, Ed. C. Chrissostomidis, pp. 147175, Hemisphere Publishing Co., 1990.  MODELING  Abstract 

Interactive Design with Sequences of Parameterized Transformations Jarek Rossignac, Paul Borrel, and Lee Nackman Proc. 2nd Eurographics Workshop on Intelligent CAD Systems: Implementation Issues, April 1115, Veldhoven, The Netherlands, pp. 95127, 1988.  DESIGN  SOLID MODELING  FEATURES Design shapes as a sequence of operations that measure and change the shape. 

AML/X tools for primitive geometric calculations: Points, Vectors, Coordinate Frames, and Linear Transformations Jarek Rossignac IBM Research Report, April, 1987.  SOFTWARE  GEOMETRIC MODELING A toolkit for computing with vectors. 

PiecewiseCircular Curves for Geometric Modeling Jarek Rossignac and Aristides Requicha IBM Journal of Research and Development, Vol. 13, pp. 296313, 1987.  MODELING  INTERPOLATION  CURVES  BIARCS 3D curves may be closely approximated by smooth piecewise biarcs curves. 

Offsetting Operations in Solid Modelling, Jarek Rossignac and Aristides Requicha ComputerAided Geometric Design, Vol. 3, pp. 129148, 1986.  SOLID MODELING  OFFSETTING Theory and algorithms for computing offset of curved models. 

Depth Buffering Display Techniques for Constructive Solid Geometry Jarek Rossignac and Aristides Requicha IEEE Computer Graphics&Applications, Vol. 6, pp. 2939, 1986.  SOLID MODELING  CSG  GRAPHIC  DIRECT SHADING FROM CSG  SURFELS Surfels are generated on the boundary of each primitive P in a CSG model and tested against the Izone of P. Surfels in the Izone are guaranteed to lie on or in the CSG solid and are rendered into a zbuffer. 

Constraints in Constructive Solid Geometry Jarek Rossignac Proc. ACM Workshop on Interactive 3D Graphics, ACM Press, pp. 93110, Chapel Hill, 1986.  SOLID MODELING  CSG  CONSTRAINTS Efficient technique for specifying distance and tangency constraints on curved surfaces within the CSG scheme. 

Blending and Offsetting Solid Models Jarek Rossignac PhD Dissertation, Electrical Engineering Department, University of Rochester, NY, June 1985. PDF  SOLID MODELING  BLENDING  FILLETING  OFFSETTING  SURFACE INTERSECTIONS Theory and algorithms for blending, filleting, and offsetting solid models and for incorporating these operations defined in CSG. Intersections of curved surfaces are approximated using smooth piecewise circular curves (PCCs), which yield smooth piecewise canalsurfaces that approximate blends and portions of offset surfaces. (PCCs) 

ConstantRadius Blending in Solid Modeling Jarek Rossignac and Aristides Requicha ASME Computers In Mechanical Engineering (CIME), Vol. 3, pp. 6573, 1984.  SOLID MODELING  BLENDING  FILLETING Theory and algorithms for creating constant radius blends on solid models. 