3D point cloud data (fwd)

[John Halleck]

On Mon, 21 Apr 2003, Wookey wrote:

> Date: Mon, 21 Apr 2003 13:09:17 +0100 (BST)
> From: Wookey <wookey@aleph1.co.uk>
> To: surveying forum <cave-surveying@survex.com>
> Subject: 3D point cloud data (fwd)
> 
> I got this message from some guys in the BCRA Cave radio and Electronics
> group, asking about skinning point clouds, now that they have a dataset.
> 
> I know that the Wakulla II project did some software for dealing with point
> clouds, but I haven't seen any skinning done and I've been told that the
> 'skinning' problem is mathematically extremely difficult, although I note
> an example from someone at '3d pipeline corp' in a recent Compass and Tape
> that seemed to work pretty well but no timings or software was provided. I
> also recall Sellers and Chamberlain using autocad to skin a model produced
> by ultrasonic cross-section scanning - maybe it could do point clouds too?

  The full mathematical problem is ugly.  Mostly because of the effects of
  "outlyers" (Random points that don't agree with the rest.)
  But don't let that scare you.   The general case is UGLY.  The typical
  cases aren't that bad.  (I.E. an algorithm that does it right all the
  time is unbelievably grim...  an algotithm that gets it right most of
  the time isn't hard.)

  There is commercial software to do this.  (Aimed at the topgraphic map
  market.)  If someone is willing to throw money at it, I can probably
  dig up some company references.

> Obviously displaying the point cloud is trivial, but the skinning part is
> rather harder. Does anyone know of any existing, available solutions? Or
> have any suggestions as to how it might be done?

  Do a Delaunay triangulation, and remove points with higher than a
  given slope change. In any case there are lots and lots of algorithms
  known for smoothing a surface starting from a triangulation.

  Or...  Do a local least squares fit of the surface, and remove points
  that are outlyers, and then triangulate.

  Or...  Triangulate, and then do local averaging.

  [If you can't tell by now, I'm recomending a search on 3D triangulation.
  The research has often been done.   There are even PHD thesis at this
  University that have attacked the problems.]

> Wookey
> -- 
> Aleph One Ltd, Bottisham, CAMBRIDGE, CB5 9BA, UK  Tel +44 (0) 1223 811679
> work: http://www.aleph1.co.uk/     play: http://www.chaos.org.uk/~wookey/
> ---------- Forwarded message ----------
> Date: Thu, 17 Apr 2003 21:12:01 +0100
> From: Richard Rushton <Richard@yabon.demon.co.uk>
> To: Brian Pease <bpease@99main.com>, wookey@aleph1.co.uk, 
>     Mike Bedford <BEDFORDMD@AOL.COM>, Richard Rushton <r.rushton@fcl.com>
> Subject: 3D point cloud data
> 
> Hi Wookey, Brian,
> 
> Recently we had a go with a 3D laser scanner in Yordas cave - it was
> [...]