Central Israel SIGGRAPH Professional Chapter
meeting on July 2, 2004

Chair: Dani Lischinski
School of Computer Science & Engineering
The Hebrew University of Jerusalem

The following program is also available in PDF format.

Time Speaker Title Abstract

8:45 REFRESHMENTS

9:15
Erez Sayer

School of

Computer Science

Tel Aviv University

Aggressive Visibility for Rendering Extremely Complex Foliage Scenes

This paper introduces a method to accelerate the rendering of extremely complex scenes by representing large portions of the scene with simplified representations. The method uses aggressive visibility to tag large and mostly occluded portions of the scene as background. The background scene is rendered by low cost imposters. The method masks any parallax errors that might be introduced by the imposters by ensuring that the foreground geometry is dense enough in image space, so that the background image is merely visible through small and sparse holes. We apply our method on large and complex scenes with moderate density, such as foliage scenes, consisting of a huge number of small disconnected pieces. We show that the presented method accelerates the rendering of such scenes while maintaining high visual fidelity and suppressing the parallax error.

*Joint work with Daniel Cohen-Or and Alan Lerner and Yiorgos Chrysanthou and Oliver Deussen

9:45
Andrei Sharf

School of

Computer Science

Tel Aviv University

Context-based Surface Completion
Sampling complex, real-world geometry with range scanning devices almost always yields imperfect surface samplings. These “holes” in the surface are commonly filled with a smooth patch that conforms with the boundary. We introduce a context-based method: the characteristics of the given surface are analyzed, and the hole is iteratively filled by copying patches from valid regions of the given surface. In particular, the method needs to determine best matching patches, and then, fit imported patches by aligning them with the surrounding surface. The completion process works top down, where details refine intermediate coarser approximations. To align an imported patch with the existing surface, we apply a rigid transformation followed by an iterative closest point procedure with non-rigid transformations. The surface is essentially treated as a point set, and local implicit approximations aid in measuring the similarity between two point set patches. We demonstrate the method at several point-sampled surfaces, where the holes either result from imperfect sampling during range scanning or manual removal.

*Joint work with Marc Alexa and Daniel Cohen-Or

10:15
Joon-Kyung Seong

Seoul National University

South Korea
Trimming Local and Global Self-intersections in Offset Curves/Surfaces using Distance Maps.
We present a robust and reasonably efficient scheme to trim both local and global self-intersections in offset curves and surfaces. The presented scheme is based on the derivation of an analytic distance map between the original curve or surface and its offset. By simultaneously solving one or three equations in the parameter space, we detect all the local and global self-intersection regions of offset curves or surfaces, respectively. The trimming of those regions is completed by projecting the zero set into the desired parameteric domain. The proposed scheme is robust in the sense that the trimmed offset curve or surface is at least trimming distance away, a bit more than the offset distance, apart from the original curve or surface. A sequence of numerical marching post processing steps yield a highly precise self-intersection result for both offset curves and offset surfaces. We have conducted several experiments in order to demonstrate the efficacy of our approach.

*Joint work with Gershon Elber and Myung-Soo Kim

10:45
COFFEE BREAK

11:15
Yotam Livny

Department of Computer Science

Ben-Gurion University

Dual Adaptive Paths for Multi-Resolution Hierarchies
The recent increase in the generated polygonal dataset sizes has out paced the performance of the graphics hardware. Several solutions such as multi-resolution hierarchies and level of detail rendering have been proposed to bridge the increasing gap. However, the discrete level of detail generates annoying popping effects and the current multi-resolution schemes can not perform drastic change on the selected level of detail on the span of small number of frames. In this work we are presenting a novel data structure for multi-resolution hierarchy that supports dual paths - aggressive and smooth - to reach the same level of detail representation. The proposed multi-resolution hierarchy is based on a fan-merge operator and its reverse operator fan-split. The fan-merge operation for a vertex v is performed by collapsing all the adjacent vertices to v, which forms the parent of all the merged vertices. The aggressive operation path is achieved by directly applying the fan-merge/split operator while the smooth operation is performed by executing the sequence of vertex-merge/split operations. The sequence of the vertex-merge/split is encoded implicitly by the order of the children that participate in the fan-merge/split operator. We shall refer to this multi-resolution hierarchy as fan hierarchy. Fan hierarchy provides a compact data-structure for multi-resolution hierarchy since it stores 7/6 pointers instead of 3 pointers for each vertex on the average. In addition, the resulting depth of the fan hierarchy is usually smaller that the depth of hierarchy generated by previous multi-resolution schemes. It is also important to note that fan-hierarchy inherently utilizes the fans representation to further accelerate the rendering process.

*Joint work with Jihad El-Sana

11:45
M. Ramanathan

Indian Institute of Science

Bangalore
India

Constructing Medial Axis Transform (MAT) of Objects Bound by Freeform Curves in the Planar Domain
The Medial Axis Transform (MAT) was first introduced by Blum to describe biological shapes. It can be viewed as the locus of the centre of a maximal disk/ball as it rolls inside a 2D/3D object. Since its introduction, MAT has found use in a wide variety of applications that primarily involve reasoning about geometry or shape. However, the usage of MAT has been restricted to analytical shapes because of the lack of algorithms for free-form objects. Existing algorithms that claim to handle free-form objects either discretise the nonlinear entities into polygonal/polyhedral convex edges/faces or use a sampled point set.
The focus of this work is on developing and implementing a simple and efficient geometric algorithm for generating MAT of planar domain bound by free-form curves. The objective is to use the exact representation of the domain boundary to obtain a discrete representation of the MAT that is exact within the precision of computation.
The algorithm works by tracing the footpoint of a normal MAT point on one edge given the footpoint on another edge. The algorithm replaces the intersection of nonlinear bisectors (favoured by current art) with intersection of linear normals, thereby reducing the computational effort and complexity considerably. Efficient distance check methods have been proposed to identify branch points of the MAT. Results of the implementation are then presented.

*Joint work with B. Gurumoorthy

Time	Speaker	Title	Abstract
8:45		REFRESHMENTS
9:15	Erez Sayer School of Computer Science Tel Aviv University	Aggressive Visibility for Rendering Extremely Complex Foliage Scenes	This paper introduces a method to accelerate the rendering of extremely complex scenes by representing large portions of the scene with simplified representations. The method uses aggressive visibility to tag large and mostly occluded portions of the scene as background. The background scene is rendered by low cost imposters. The method masks any parallax errors that might be introduced by the imposters by ensuring that the foreground geometry is dense enough in image space, so that the background image is merely visible through small and sparse holes. We apply our method on large and complex scenes with moderate density, such as foliage scenes, consisting of a huge number of small disconnected pieces. We show that the presented method accelerates the rendering of such scenes while maintaining high visual fidelity and suppressing the parallax error. *Joint work with Daniel Cohen-Or and Alan Lerner and Yiorgos Chrysanthou and Oliver Deussen
9:45	Andrei Sharf School of Computer Science Tel Aviv University	Context-based Surface Completion	Sampling complex, real-world geometry with range scanning devices almost always yields imperfect surface samplings. These “holes” in the surface are commonly filled with a smooth patch that conforms with the boundary. We introduce a context-based method: the characteristics of the given surface are analyzed, and the hole is iteratively filled by copying patches from valid regions of the given surface. In particular, the method needs to determine best matching patches, and then, fit imported patches by aligning them with the surrounding surface. The completion process works top down, where details refine intermediate coarser approximations. To align an imported patch with the existing surface, we apply a rigid transformation followed by an iterative closest point procedure with non-rigid transformations. The surface is essentially treated as a point set, and local implicit approximations aid in measuring the similarity between two point set patches. We demonstrate the method at several point-sampled surfaces, where the holes either result from imperfect sampling during range scanning or manual removal. *Joint work with Marc Alexa and Daniel Cohen-Or
10:15	Joon-Kyung Seong Seoul National University South Korea	Trimming Local and Global Self-intersections in Offset Curves/Surfaces using Distance Maps.	We present a robust and reasonably efficient scheme to trim both local and global self-intersections in offset curves and surfaces. The presented scheme is based on the derivation of an analytic distance map between the original curve or surface and its offset. By simultaneously solving one or three equations in the parameter space, we detect all the local and global self-intersection regions of offset curves or surfaces, respectively. The trimming of those regions is completed by projecting the zero set into the desired parameteric domain. The proposed scheme is robust in the sense that the trimmed offset curve or surface is at least trimming distance away, a bit more than the offset distance, apart from the original curve or surface. A sequence of numerical marching post processing steps yield a highly precise self-intersection result for both offset curves and offset surfaces. We have conducted several experiments in order to demonstrate the efficacy of our approach. *Joint work with Gershon Elber and Myung-Soo Kim
10:45		COFFEE BREAK
11:15	Yotam Livny Department of Computer Science Ben-Gurion University	Dual Adaptive Paths for Multi-Resolution Hierarchies	The recent increase in the generated polygonal dataset sizes has out paced the performance of the graphics hardware. Several solutions such as multi-resolution hierarchies and level of detail rendering have been proposed to bridge the increasing gap. However, the discrete level of detail generates annoying popping effects and the current multi-resolution schemes can not perform drastic change on the selected level of detail on the span of small number of frames. In this work we are presenting a novel data structure for multi-resolution hierarchy that supports dual paths - aggressive and smooth - to reach the same level of detail representation. The proposed multi-resolution hierarchy is based on a fan-merge operator and its reverse operator fan-split. The fan-merge operation for a vertex v is performed by collapsing all the adjacent vertices to v, which forms the parent of all the merged vertices. The aggressive operation path is achieved by directly applying the fan-merge/split operator while the smooth operation is performed by executing the sequence of vertex-merge/split operations. The sequence of the vertex-merge/split is encoded implicitly by the order of the children that participate in the fan-merge/split operator. We shall refer to this multi-resolution hierarchy as fan hierarchy. Fan hierarchy provides a compact data-structure for multi-resolution hierarchy since it stores 7/6 pointers instead of 3 pointers for each vertex on the average. In addition, the resulting depth of the fan hierarchy is usually smaller that the depth of hierarchy generated by previous multi-resolution schemes. It is also important to note that fan-hierarchy inherently utilizes the fans representation to further accelerate the rendering process. *Joint work with Jihad El-Sana
11:45	M. Ramanathan Indian Institute of Science Bangalore India	Constructing Medial Axis Transform (MAT) of Objects Bound by Freeform Curves in the Planar Domain	The Medial Axis Transform (MAT) was first introduced by Blum to describe biological shapes. It can be viewed as the locus of the centre of a maximal disk/ball as it rolls inside a 2D/3D object. Since its introduction, MAT has found use in a wide variety of applications that primarily involve reasoning about geometry or shape. However, the usage of MAT has been restricted to analytical shapes because of the lack of algorithms for free-form objects. Existing algorithms that claim to handle free-form objects either discretise the nonlinear entities into polygonal/polyhedral convex edges/faces or use a sampled point set. The focus of this work is on developing and implementing a simple and efficient geometric algorithm for generating MAT of planar domain bound by free-form curves. The objective is to use the exact representation of the domain boundary to obtain a discrete representation of the MAT that is exact within the precision of computation. The algorithm works by tracing the footpoint of a normal MAT point on one edge given the footpoint on another edge. The algorithm replaces the intersection of nonlinear bisectors (favoured by current art) with intersection of linear normals, thereby reducing the computational effort and complexity considerably. Efficient distance check methods have been proposed to identify branch points of the MAT. Results of the implementation are then presented. *Joint work with B. Gurumoorthy

Central Israel SIGGRAPH Professional Chapter meeting on July 2, 2004

Central Israel SIGGRAPH Professional Chapter
meeting on July 2, 2004