andrel <a_l### [at] hotmailcom> wrote:
> Grassblade wrote:
> > -Pick the first point on the sphere and shoot a single trace toward the
> > center of the bounding sphere: if no hit ensues, proceed to next geodesic
> > point; otherwise store the point returned by trace.
> That only works for objects that are star convex. i.e. objects where for
> every point an outward pointing ray does not cut through the shape. It
> will never work for e.g. a Klein bottle.
Good point. Let's change it to : for a given point shoot trace; if it hits,
store position and shoot another trace from a point that is position +
epsilon further along the ray. Repeat until you have a satisfactory number
of hits (just in case the object has infinite intersections with the ray).
Then go to next ray.
> > -Repeat for all points.
> > You now have a cloud of points. I haven't figured out how to transform them
> > in faces yet,
> When you do let me know. I need such an algorithm for many of my
> projects and so do many others. ;)
I have skimmed through papers, and apparently there are at least three ways
of doing it:
-ball pivoting algorithm: a sphere of given radius is pivoted around an edge
until it hits a third point. Start with small radius sphere to get the finer
details and repeat as needed with bigger radiuses (see
http://citeseer.ist.psu.edu/bernardini99ballpivoting.html).
-an extrapolating method that projects cube vertices on the normal plane of
any given point of the point cloud. Since trace can also return normals, we
don't need to estimate it from the point cloud, which saves a step. Paper:
Surface reconstruction from unorganized points, available at
http://research.microsoft.com/~hoppe/#recon. There's even code in C++
available at that page.
-And a gazillion of papers based on Delaunay triangulation and/or its dual
Voronoy diagrams. Since crackle is based on voronoy sets, I was wondering if
it
was possible to somehow feed POVray the cloud point and let whatever
procedure handles voronoy diagrams do the dirty work. Lots of C/C++ codes
available at
http://www-users.informatik.rwth-aachen.de/~roberts/software.html.
I sure wish I knew C. :-(
> > but a possibility is to calculate the distance between
> > points, if it is less than an user supplied treshold, then the two points
> > form an edge.
>  From experience I can tell you that that does not work.
Ah, ok. I guess it would have been too easy. :-p

Post a reply to this message