POV-Ray : Newsgroups : povray.binaries.images : Convex Hull macro ... (31KB + 28KB) : Convex Hull macro ... (31KB + 28KB) Server Time
18 Jul 2024 07:57:50 EDT (-0400)
  Convex Hull macro ... (31KB + 28KB)  
From: Michael Andrews
Date: 8 Feb 2003 18:58:12
Message: <3e459994@news.povray.org>
Hi Folks,

I've written a macro which produces the 3d convex hull of an arbitrary 
point cloud using a 'beneath-beyond' type algorithm.

It grew out of a simple wish to triangulate the surface of a sphere for 
use in a mechanics simulation. My first few attempts failed rather too 
easily, so I read up on the problem and this came out of it.

It can get a bit slow - 500 co-spherical points takes about three and a 
half minutes to parse on my 1GHz Athlon - and it probably scales at 
something between O(n^2) and O(n^3) with the worst case being all points 
on the hull.

The two images are:

200 co-spherical points giving a hull of all points, 594 edges and 396 
triangles;

400 points from VRand_In_Box() giving a hull of 55 points, 159 edges and 
106 triangles.

I'll post the files to p.b.s-f in a moment. Please let me know if anyone 
finds them useful ...

Bye for now,
	Mike Andrews.


Post a reply to this message


Attachments:
Download 'convhull3.jpg' (31 KB) Download 'convhull5.jpg' (26 KB)

Preview of image 'convhull3.jpg'
convhull3.jpg

Preview of image 'convhull5.jpg'
convhull5.jpg


 

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.