## intersection of a line with an arbitrary surface

### intersection of a line with an arbitrary surface

Assume you have an arbitrary, complex 3D surface, defined by a
collection of points (x,y,z) on the surface, but without knowledge of
the function f(x,y,z) defining the surface algebraically.  Assume a
fixed line (ie, passes through a known point and has a known slope)
which intersects this surface at one or more points.  What algorithms
exist for finding the nearest of these intersection points?

I am not familiar with the world of 3D scene generation - hopefully
people here are.   I think there might be standard answers to this
question, because I can see it would apply to many potential scenes, eg,
a ray of light entering a cavern full of stalactites and stalagmites.
For the applications I have in mind, it would be very difficult to
analyse the surface and to approximate it with aggregates of simple
geometric solids.  Are there algorithms which will work directly from
the set of points defining the surface?

Thanks
Ross

### intersection of a line with an arbitrary surface

> Assume you have an arbitrary, complex 3D surface, defined by a
> collection of points (x,y,z) on the surface, but without knowledge of
> the function f(x,y,z) defining the surface algebraically.  Assume a
> fixed line (ie, passes through a known point and has a known slope)
> which intersects this surface at one or more points.  What algorithms
> exist for finding the nearest of these intersection points?

> I am not familiar with the world of 3D scene generation - hopefully
> people here are.   I think there might be standard answers to this
> question, because I can see it would apply to many potential scenes, eg,
> a ray of light entering a cavern full of stalactites and stalagmites.
> For the applications I have in mind, it would be very difficult to
> analyse the surface and to approximate it with aggregates of simple
> geometric solids.  Are there algorithms which will work directly from
> the set of points defining the surface?

The algorithm you are looking for may be an example of ray-tracing, where
the line in question represents a beam of light.

3D surfaces that are not expressed by mathematical functions are normally
expressed, not as a collection of /points,/ but a collection of closed
/polygons./  (The points are connected by /vertices,/ and the vertices are
collected into polygons.)  If the polygons are complicated, they're often
subdivided into triangles ... the simplest polygon ... or squares.

Once you have the shape expressed as polygons, you can calculate whether a
particlar ray intersects the polygon, and if so, at what point.

### intersection of a line with an arbitrary surface

> Assume you have an arbitrary, complex 3D surface, defined by a
> collection of points (x,y,z) on the surface, but without knowledge of
> the function f(x,y,z) defining the surface algebraically.  Assume a
> fixed line (ie, passes through a known point and has a known slope)
> which intersects this surface at one or more points.  What algorithms
> exist for finding the nearest of these intersection points?
> [...]
> For the applications I have in mind, it would be very difficult to
> analyse the surface and to approximate it with aggregates of simple
> geometric solids.  Are there algorithms which will work directly from
> the set of points defining the surface?

No.

Your question is under-specified.  A set of points doesn't specify a unique
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.

-matt
--

=======================================================================
In a cruel and evil world, being cynical can allow you to get some
entertainment out of it. --Daniel Waters

### intersection of a line with an arbitrary surface

> Assume you have an arbitrary, complex 3D surface, defined by a
> collection of points (x,y,z) on the surface, but without knowledge of
> the function f(x,y,z) defining the surface algebraically.  Assume a
> fixed line (ie, passes through a known point and has a known slope)
> which intersects this surface at one or more points.  What algorithms
> exist for finding the nearest of these intersection points?

If it is just a collection of points without a functional relationship there is
no intersection save by chance. A collection of points to not define a surface
although they may approximate a surface. If one assumes they are an
approximation then one can simply find the nearest points to every point on the
line and do with it what you will.

Quote:> I am not familiar with the world of 3D scene generation - hopefully
> people here are.   I think there might be standard answers to this
> question, because I can see it would apply to many potential scenes, eg,
> a ray of light entering a cavern full of stalactites and stalagmites.
> For the applications I have in mind, it would be very difficult to
> analyse the surface and to approximate it with aggregates of simple
> geometric solids.  Are there algorithms which will work directly from
> the set of points defining the surface?

So far as I am aware they all depend upon solving the function.

--
No American seriously expects an imminent attack by Iraq
unless they are the ones who think Iraq is in Nebraska.
-- The Iron Webmaster, 2364

### intersection of a line with an arbitrary surface

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.

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.

> 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' ?

Thanks

Ross

### intersection of a line with an arbitrary surface

Quote:>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.

>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.

I'm still not sure if you're talking about a situation similar to when
POVRay renders isosurfaces. The situation there is that the function
that defines the surface is rather arbitrary, and there may be no
algebraic algorithm that could be used to calculate the intersection of
a ray with the surface. For example the function may contain pattern
expressions that have a fractal nature. POVRay uses a numerical method
of recursive subdivision to approximate the position of the first
intersection of the ray with the surface.

--
Mike Williams
Gentleman of Leisure

### intersection of a line with an arbitrary surface

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 [...]

Ok, now we're getting somewhere.  A google search for "ray tracing
acceleration" comes up with a bunch of slides/notes.  One good one is:

<http://graphics.stanford.edu/courses/cs348b-02/lectures/lecture3/>

You might want to check out Pete Shirley's recent book on ray tracing, or
"An Introduction to Ray Tracing", by Glassner et al, both of which cover
this.

Quote:> 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' ?

For your purposes, an infinite ray is equivalent to a ray that starts
outside the bounds of the environment and passes all the way through it.
So just start the ray from outside and you can get all of the
intersections.

Also, I misspoke when I claimed that it was necessary to generate an
explicit geometric form of the scene for ray-tracing.  Schaufler and Jensen
have a clever technique for directly ray-tracing point data.

Ray Tracing Point Sampled Geometry, Gernot Schaufler and Henrik Wann Jensen.

<http://graphics.lcs.mit.edu/~gs/research/psp/>

-matt
--

=======================================================================
In a cruel and evil world, being cynical can allow you to get some
entertainment out of it. --Daniel Waters

### intersection of a line with an arbitrary surface

> 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
textbooks.

- Show quoted text -

Quote:>  > 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.

Mark

- Show quoted text -

Quote:> Thanks

> Ross

### intersection of a line with an arbitrary surface

Quote:> It's odd that you can use terms like "Delaunay triangulation" and yet
> not know even the most basic techniques used in raytracing.

> ....<snip>

> It's hardly rocket science.

Well, Delaunay triangulation has many uses other than ray tracing, and I
did say I had no background in ray tracing - and for the same reason, no
reference books on hand.  Isn't the whole charm of Usenet the fact that one
can ask for help with things that one isn't already expert in?   I tried to
search the web, but in an area like raytracing, it generates too much
unless you know which named techniques to look for.

Thanks again to the various respondents for the additional info.

Ross

I have a list of points that make up a surface.  These points are
arbitrarily placed on the surface (ie not spaced evenly on a grid, etc.).

I'm looking for an algorithm which will "connect" these points inorder
to view the surface as a connected line surface (poly-lines) or as a
triangular mesh surface.

Any help will be appreciated. Please send responses to me directly.

Thanks,
Larry Coffin