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'

Preview of image 'convhull5.jpg'

Michael Andrews wrote:
> Hi Folks,
> 
> I've written a macro which produces the 3d convex hull of an arbitrary 
> point cloud using a 'beneath-beyond' type algorithm.
> 


Looks very cool.  I was about to give it a try when :


Parsing...Could not find file 'rand.inc'
//
// +w400 +h400 +a0.2 +kff5

#include "rand.inc"
  <----ERROR

./ConvHull.pov:10: error: Cannot open include file rand.inc.


Where is this file?  Hopefully not in Pov ver 3.5 as I only have version 3.1g.

Dennis

Post a reply to this message

Dennis Clarke wrote:
> Looks very cool.  I was about to give it a try when :
> 
> 
> Parsing...Could not find file 'rand.inc'
> //
> // +w400 +h400 +a0.2 +kff5
> 
> #include "rand.inc"
>  <----ERROR
> 
> ./ConvHull.pov:10: error: Cannot open include file rand.inc.
> 
> 
> Where is this file?  Hopefully not in Pov ver 3.5 as I only have version 
> 3.1g.
> 
> Dennis
> 
Hi Dennis,

I'm afraid it is a v3.5 file. That one isn't too important, but I use 
math.inc (another v3.5 standard include) macros in the hull calculation, 
sorry.

Mike.

Post a reply to this message

Michael Andrews wrote:
> Dennis Clarke wrote:
> 
>> Looks very cool.  I was about to give it a try when :
>>
>>
>> Parsing...Could not find file 'rand.inc'
>> //
>> // +w400 +h400 +a0.2 +kff5
>>
>> #include "rand.inc"
>>  <----ERROR
>>
>> ./ConvHull.pov:10: error: Cannot open include file rand.inc.
>>
>>
>> Where is this file?  Hopefully not in Pov ver 3.5 as I only have 
>> version 3.1g.
>>
>> Dennis
>>
> Hi Dennis,
> 
> I'm afraid it is a v3.5 file. That one isn't too important, but I use 
> math.inc (another v3.5 standard include) macros in the hull calculation, 
> sorry.
> 
> Mike.
> 


damn.

I sure wish that there was a build of Pov-Ray for Solaris.

Dennis

http://www.blastwave.org/dclarke/Sun_Gnome_too_cool.jpg

Post a reply to this message

> > I'm afraid it is a v3.5 file. That one isn't too important, but I use
> > math.inc (another v3.5 standard include) macros in the hull calculation,

> I sure wish that there was a build of Pov-Ray for Solaris.

It might work fine if you just get the include files; it's unlikely they
require any special 3.5 features.

 - Slime
[ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:
>>>I'm afraid it is a v3.5 file. That one isn't too important, but I use
>>>math.inc (another v3.5 standard include) macros in the hull calculation,
> 
> 
>>I sure wish that there was a build of Pov-Ray for Solaris.
> 
> 
> It might work fine if you just get the include files; it's unlikely they
> require any special 3.5 features.
> 
>  - Slime
> [ http://www.slimeland.com/ ]
> 
> 
You're right, I just didn't think of that last night :-/

The two macros I use from math.inc are VProject_Plane() and VRotation(), 
neither of which uses anything new in v3.5.

Nor do the VRand_In_Sphere() and VRand_In_Box() macros from rand.inc.

So if you get a copy of math.inc and rand.inc, with a little 
cut-and-paste it should work with v3.1.

Bye for now,
	Mike.

Post a reply to this message

Wohoo! Just yesterday evening I wanted some code that distributes points
evenly on a sphere. Actually not just the code (it already exists) but to
understand how it's done. So far it's been too messy to understand, and the
articles I found were too mathematical.

Maybe your code will give me the answer. Thanks, I'll look into it!

Regards,
Hugo

Post a reply to this message

Ehm, I guess you misunderstood the algorithm's concept.

It takes a cloud of points and creates a mesh which
tries to build a surface out of those points.
Look at
http://graphics.stanford.edu/~fedkiw/
for scientific examples, especially the images with
blue shapes.

If you're interested in how to spread points equally on
a sphere, you might want to search for "electrostatic
repulsion", or look at this:

http://www.math.niu.edu/~rusin/known-math/index/spheres.html

It has some useful links on how you might generate what
you need. I've found almost no method which actually places
one point after another with best distribution...

Regards,
Tim



--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

> Wohoo! Just yesterday evening I wanted some code that distributes points
> evenly on a sphere. Actually not just the code (it already exists) but to
> understand how it's done. So far it's been too messy to understand, and the
> articles I found were too mathematical.
>
> Maybe your code will give me the answer. Thanks, I'll look into it!
>
> Regards,
> Hugo
>
>

Post a reply to this message

Don't have any pov script for you, but here's a quick run-down on a method
I've used to distribute points on a sphere that seems fairly simple if
you're comfortable with vectors and how to do a little arithmetic with
them.

First consider the problem in two dimensions: a circle.  Rather than try to
to distribute points on a circle, I like to think of it as problem of
approximating a circle with line segments.  What's the smallest number of
line segments you can make a two-dimensional shape out of? Three - our
friend the triangle.

If you're really generous, you can think of an equilateral triangle as a
*really* crude approximation of a circle.  The 2d unit vectors for the
three corners of this triangle are <1,0>, <cos(120),sin(120)>, and
<cos(240),sin(240)>.

If an equilateral triangle is not a good enough approximation for you, maybe
a hexagon would work better?  To get a hexagon, you can just divide each
side of the equilateral triangle in half, and nudge the new point out till
it hits the edge of the circle.  Mathematically, you do this by adding the
two vectors that represent the two ends of the side, and normalize the
result.  This gives you a new point on the circle that is exactly halfway
between the original two points.  If you do this for each of the three
sides of your equilateral triangle, you end up with a perfect hexagon.

Now, if you're not happy with the hexagon, you can repeat the same process
by splitting each side of the hexagon to get a dodecagon (12 sided figure),
and split its sides any number of times until you evetually get a perfect
circle.

Extending this concept to three dimensions is relatively trivial.  In three
dimensions, you need at least four surfaces to make a three-dimensional
shape.  If we stick with our equilateral triangles, we get a three-sided
pyramid which is a really crude approximation of a sphere.

To refine it, you divide each triangle into four triangles, and nudge their
corners out to the surface of the sphere.  Specifically, for each side of
the triangle you divide the triangles sides in half like we did in the 2d
case (add and normalize) and make a new triangle out of the three new
points, with three triangles hanging off each of its sides.

Hope that wasn't too complicated.  One side note is that this approach
doesn't really solve the problem of placing an arbitrary number of points
on a sphere.  Instead, it gives you a method for generating a sphere of
arbitrary triangle density.

Ken

Hugo Asm wrote:

> Wohoo! Just yesterday evening I wanted some code that distributes points
> evenly on a sphere. Actually not just the code (it already exists) but to
> understand how it's done. So far it's been too messy to understand, and
> the articles I found were too mathematical.
> 
> Maybe your code will give me the answer. Thanks, I'll look into it!
> 
> Regards,
> Hugo

Post a reply to this message

This was very helpful, because you visualised it! That's the kind of
description I was searching for, but couldn't find.

I will try it. :o)

Best regards,
Hugo

Post a reply to this message