Fast sparse kernel summation on Cartesian grids: An on-chip algorithm for 3D implicit surface visualization

Author: 

Zhu, S
Wathen, A

Publication Date: 

8 March 2019

Journal: 

ACM International Conference Proceeding Series

Last Updated: 

2019-06-13T17:44:03.617+01:00

DOI: 

10.1145/3318265.3318278

page: 

20-24

abstract: 

© 2019 Association for Computing Machinery. This paper proposes a fast algorithm for evaluating sum-mations of heterogenous sparse kernels P of the form s(x) = Σ Mi=1 α i φ(ϵ i ∥x-x i ∥) on N points on an arbitrary fine Carte-sian grid in R d . The algorithm takes the advantage of s-parsity and the structure of Cartesian grids. The sparsity admits operations only be done in some active subsets of the Cartesian grids; the structure of Cartesian grids reduce the storage for N points from O(dN) to O(1), a constant, and thus transforms costly memory intensive operations to cheap computationally intensive operations. This results in scalable algorithm with a complexity of O(N) and makes the postprocessing of large 3D implicit surface feasible on a PC or laptop. Numerical examples for 3D surface reconstruction are presented to illustrate the efficiency of the algorithm.

Symplectic id: 

994972

Favourite: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Conference Paper

ISBN-13: 

9781450366380