3D nearest point program announcement

[W. Randolph Franklin]

NEARPT3 is a pair of subroutines to find nearest points in
E3.  PREPROCESS takes a list of fixed points, and
preprocesses them into a data structure.  QUERY takes a
query point, and returns the closest fixed point to it.

Nearpt3 is very fast and very small.  It is designed to
process datasets with hundreds of millions of points.  Test
data from the following sources was used:

- The Stanford 3D Scanning Repository,
- Stanford University's Digital Michelangelo Project Archive of 3D Models,
- Georgia Institute of Technology's Large Geometric Models Archive, and
- The University of North Carolina at  Chapel Hill Walkthru Project

We used the largest available PLY file datasets from each
source.  The largest dataset tested to date is the St
Matthew PLY file from the Digital Michelangelo Project
Archive, with 184,098,599 vertices.  We used 184,088,599 as
fixed points and 10,000 as queries.  Total I/O,
preprocessing, and query time on a 2.2MHz Xeon was 160 CPU
seconds.

Quite large datasets can be processed on a laptop computer.
Preprocessing the David dataset with 28,158,109 vertices and
performing 10,000 queries took only 47 CPU seconds on an IBM
T30.

More info  is at
http://wrfranklin.org/Research/nearpt3/index.html

That includes a paper describing the algorithm, test
results, and the code.


--
W. Randolph Franklin
ECSE Dept., 6026 JEC,
Rensselaer Polytechnic Inst,
110 8th St,
Troy NY, 12180 USA

mail at wrfranklin.org or wrf at ecse.rpi.edu 
+1 (518) 276-6077
Fax: +1 (518) 276-6261

http://wrfranklin.org/





-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.