



Surface patches for 3D sketching
Fatemeh Abbasinejad, Pushkar Joshi, Cindy Grimm, Nina Amenta, Lance Simons
Proc. of the International Symposium on SketchBased 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 lightweight 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, naturallooking surfaces. We demonstrate our approach on curve networks generated by two different 3D sketching systems.
[PDF]



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.
[PDF]



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 threespace curves that suggest the contours of shapes. The shapes may be nonmanifold, closed threedimensional, open twodimensional, or mixed. We describe a system that automatically generates intuitively appealing piecewisesmooth surfaces from such a curve network, and an intelligent user interface for modifying the automatically chosen surface patches. Both the automatic and the semiautomatic 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 mouseclicks.
[Webpage][PDF][Video]




Realtime 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 Proc. of ACM SIGGRAPH ASIA 2009
We demonstrate an efficient dataparallel algorithm for building
large hash tables of millions of elements in realtime. 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 realtime performance on large
datasets: for 5 million keyvalue 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]



