> Thanks for the reply, Matt (and also to Matt Giwer, and to the person
> from 'Sundial Services')
> All three of you have focussed on the problem of deciding exactly what
> surface is specified by a set of points.
> This is not really what I wanted to ask about. As you will have seen
> from the example I mentioned, I was presenting the problem as a
> practical one that might arise in ray-tracing, for example. Therefore,
> I was assuming that the points specified the surface "well enough" for
> practical purposes - ie, the points are fairly densely spaced relative
> to the local changes in conformation. To put it another way, the
> surface could be adequately represented by *any* simple form of local
> interpolation, such as polynomial interpolation with smoothness
> requirements on the first few spatial derivatives or even just by
> triangulation. Changes in representation will cause only minor variations
> in the location of the ray intersection, in the general case.
Isn't it rather obvious that the choice of intersection test might depend
on the exact nature of the interpolation scheme?
Quote:> The issue I wanted to ask about was the problem of efficiently finding
> the first intercept of the ray with the surface. Assume the points are
> used to build some representation of the surface, eg, a Delaunay
> triangulation with N triangles. Assume also that the surface is complex
> and deeply infolded. It then not very clear which part of the surface
> the ray will strike first. One *could* run through all N triangles and
> calculate whether the the ray intersects each triangle in turn, but
> presumably there are better ways. I don't think depth-ordering
> apply methods here, because there is no privileged point along
> the line of the ray, and from any arbitrarily chosen point on the ray,
> the nearest surface element is, in general, NOT the one that will
> contain the point of intersection with the surface.
It's odd that you can use terms like "Delaunay triangulation" and yet
not know even the most basic techniques used in raytracing. Typically
triangulations are inserted into acceleration structures such as grids,
octrees, BSP trees, or K-d trees, and rays are intersected against these
structures using spatial locality to order the search. Such techniques
are well known and well described in most introductory computer graphics
> > Your question is under-specified. A set of points doesn't specify a
> > unique surface; depending on the additional assumptions you make
> > or additional information about the geometric form of the surface, any
> > number of surfaces could result. (e.g. consider three points the same
> > distance from each other. Are they from an equilateral triangle?
> > A circle? A square?)
> > So you need to create some representation of the surface. Amenta et
> > al's crust software might do the trick for you:
> > <http://www.cs.utexas.edu/users/amenta/powercrust/welcome.html>
> > Given some representation, then standard ray-object intersection
> > algorithms can be applied.
> OK - this sounds closer to it. Where do I look up these 'standard'
> algorithms? The ones I've heard about assume a point of origin in R3,
> and this is undefined in the model I'm using. Which of these algorithms
> are applicable to 'an infinite ray' as distinct from 'a ray from a
> point' ?
Introduction to Raytracing, by Glassner.
Realistic Ray Tracing, by Shirley
It's hardly rocket science.