Surface patches for 3D sketching

Fatemeh Abbasinejad, Pushkar Joshi, Cindy Grimm, Nina Amenta, Lance Simons
Proc. of the International Symposium on Sketch-Based Interfaces and Modeling (SBIM) 2013

3D sketching is an appealing approach for creating concept shapes in the early stages of design. While curve networks alone can convey shape, surfacing the network can dramatically help with visualization and interaction. Unfortunately, surfacing a curve network is an inherently ambiguous problem, and even if the correct surface patches are identified, they can have an arbitrarily complex 3D geometry, making it challenging to produce a reasonable tessellation. In this paper we address the problem of creating light-weight surface tessellations on the fly. Our approach is to identify potential patches in the curve network, and then break complicated patches into simpler ones which can be tessellated using any simple algorithm. Our surfacing approach relies on the observation that breaking a complicated patch into a set of nearly planar ones with small total area seems to create a simple, natural-looking surfaces. We demonstrate our approach on curve networks generated by two different 3D sketching systems.


shifted input
kANN on the GPU via Shifted Sorting

Shengren Li, Lance C. Simons, Jagaseesh Bhaskar Pakaravoor, Fatemeh Abbasinejad, John D. Owens, Nina Amenta
Proc. of High Performance Graphics (HPG) 2012

We describe the implementation of a simple method for finding k approximate nearest neighbors (ANNs) on the GPU. While the performance of most ANN algorithms depends heavily on the distributions of the data and query points, our approach has a very regular data access pattern. It performs as well as state of the art methods on easy distributions with small values of k, and much more quickly on more difficult problem instances. Irrespective of the distribution and also roughly of the size of the set of input data points, we can find 50 ANNs for 1M queries at a rate of about 1200 queries/ms.


Surface Patches from Unorganized Space Curves

Fatemeh Abbasinejad, Pushkar Joshi, Nina Amenta
Computer Graphics Forum,Volume 30, Issue 5
Proc. of Eurographics Symposium on Geometry Processing (SGP) 2011

NEW: see more detailed video published in the Symposium on Computational Geometry (SoCG) 2012 - video/multimedia track [SocG'12 VIDEO]

Recent 3D sketch tools produce networks of three-space curves that suggest the contours of shapes. The shapes may be non-manifold, closed three-dimensional, open two-dimensional, or mixed. We describe a system that automatically generates intuitively appealing piecewise-smooth surfaces from such a curve network, and an intelligent user interface for modifying the automatically chosen surface patches. Both the automatic and the semi-automatic parts of the system use a linear algebra representation of the set of surface patches to track the topology. On complicated inputs from ILoveSketch [BBS08], our system allows the user to build the desired surface with just a few mouse-clicks.


Real-time Parallel Hashing on the GPU

Dan A. Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubho Sengupta, John Owens, Michael Mitzenmacher, Nina Amenta
Transactions on Graphics (TOG), Volume 28, Issue 5

We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.
[Webpage] [PDF] [Video]

Rotating Scans for Systematic Error Removal
Fatemeh Abbasinejad, Yong J. Kil, Andrei Sharf, Nina Amenta
Computer Graphics Forum, Volume 28, Issue 5
Proc. of Eurographics Symposium on Geometry Processing (SGP) 2009

Awarded 2nd Best Paper

Abstract: Optical triangulation laser scanners produce errors at surface discontinuities and sharp features. These systematic errors are anisotropic. We examine the causes of these errors theoretically, and we study the correlation of systematic error with edge size and orientation experimentally. We then present a novel processing method for removing systematic errors, by combining scans taken at several different orientations. We apply an anisotropic filter to the separate scans, and use it to weight the data in a final combination step. Unlike previous approaches, our method does not require access to the scanner's internal data or firmware. We demonstrate the technique on data from laser range scanners by two different manufacturers.
[Webpage] [PDF]


[Home]  [Research]  [Projects]  [Teaching]  [Courses]  [About Me]  + add link