POV-Ray : Newsgroups : povray.binaries.images : Convex Hull macro ... (31KB + 28KB) : Re: Convex Hull macro ... (31KB + 28KB) Server Time
22 Jul 2024 00:59:13 EDT (-0400)
  Re: Convex Hull macro ... (31KB + 28KB)  
From: Ken Cecka
Date: 9 Feb 2003 18:11:25
Message: <3e46e01d@news.povray.org>
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

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