Search   Memberlist   Usergroups
 Page 1 of 1 [13 Posts]
Author Message
Jaco van Niekerk
science forum beginner

Joined: 13 Jun 2005
Posts: 11

Posted: Mon Jun 13, 2005 1:03 pm    Post subject: Interesting, irritating problem ;-)

Hello

I am stuck with a mathematical problem in a graphics application I am
writing. My mathematics is limited and I apologise for my ignorance in

I am plotting a parameterised surface in 3D space. At any point the curve
is defined by x = f(u, v); y = g(u, v) and z = h(u, v). Lastly the domain of
u and v is from 0 to 1.

Now, consider two arbitrary points P0(u0, v0) and P1(u1, u2). Imagine that
these are connected by a straight line. Now in some way I need to know
where on this line the error between the line and the actual curve is the
greatest.

Guest

Posted: Mon Jun 13, 2005 2:35 pm    Post subject: Re: Interesting, irritating problem ;-)

Jaco van Niekerk wrote:
 Quote: Hello I am stuck with a mathematical problem in a graphics application I am writing. My mathematics is limited and I apologise for my ignorance in advance. Here is my problem. I am plotting a parameterised surface in 3D space. At any point the curve is defined by x = f(u, v); y = g(u, v) and z = h(u, v). Lastly the domain of u and v is from 0 to 1. Now, consider two arbitrary points P0(u0, v0) and P1(u1, u2).

Possibly you mean P1(u1, v1)?

 Quote: Imagine that these are connected by a straight line. Now in some way I need to know where on this line the error between the line and the actual curve is the greatest. Where do I begin? Please help. Does someone have an example for me?

How is the "error" measured? Is it the shortest distance from a point
on the line to the surface? Or the distance in some specified
direction? Or something else?
Lynn Kurtz
science forum Guru

Joined: 02 May 2005
Posts: 603

Posted: Mon Jun 13, 2005 3:09 pm    Post subject: Re: Interesting, irritating problem ;-)

On Mon, 13 Jun 2005 17:03:47 +0200, "Jaco van Niekerk"
<sparky@lantic.net> wrote:

 Quote: Now, consider two arbitrary points P0(u0, v0) and P1(u1, u2). Imagine that these are connected by a straight line. Now in some way I need to know where on this line the error between the line and the actual curve is the greatest.

What is the "actual curve" to which you refer? Is it a curve lying on

--Lynn
Jaco van Niekerk
science forum beginner

Joined: 13 Jun 2005
Posts: 11

Posted: Mon Jun 13, 2005 4:08 pm    Post subject: Re: Interesting, irritating problem ;-)

"Lynn Kurtz" <kurtzDELETE-THIS@asu.edu> wrote in message
news:Hr2tQnQgRMujznSiMNpHGJ3qUHaM@4ax.com...
 Quote: On Mon, 13 Jun 2005 17:03:47 +0200, "Jaco van Niekerk" sparky@lantic.net> wrote: Now, consider two arbitrary points P0(u0, v0) and P1(u1, u2). Imagine that these are connected by a straight line. Now in some way I need to know where on this line the error between the line and the actual curve is the greatest. What is the "actual curve" to which you refer? Is it a curve lying on the surface? Details please. --Lynn The "actual curve" is some function given in the form x = f(u, v); y = g(u,

v) and z = h(u, v). The parameters u and v are in the domain [0, 1]. I now
consider two points p0(u0, v0) and p1(u1, v1). My graphics program
approximates the drawing of this curve by a straight line. I need to find
the value between p0 and p1 (that is the values of u and v) where the error
between the actual curve and the approximated curve (straight line) is the
greatest. For a circle, this would always be exactly between p0 and p1. Hope
I explain myself a bit better this time...

Thank you for all the interest. I appreciate any help ;-)

Regards
Micky Molar
science forum beginner

Joined: 23 Apr 2005
Posts: 21

 Posted: Mon Jun 13, 2005 4:25 pm    Post subject: Re: Interesting, irritating problem ;-) Unless you decide a priori in which direction to look, you'll have to look for the "least worst" maximum distance. That is, of all the curves formed by the intersection of the surface with a plane through the P0/P1 line, you presumably want the maximum point which comes closest to the P0/P1 line. Otherwise, it makes no sense. For a SMOOTH (i.e. continuous partial derivatives) surface, this will be a point where the normal to the surface actually intersects the line P0/P1 (a very unusual occurence in 3-D), and the normal is in the direction of grad{F(x,y,z)} where F(x,y,z)=0 is the equation for your surface.
Lynn Kurtz
science forum Guru

Joined: 02 May 2005
Posts: 603

Posted: Mon Jun 13, 2005 5:58 pm    Post subject: Re: Interesting, irritating problem ;-)

On Mon, 13 Jun 2005 20:08:54 +0200, "Jaco van Niekerk"
<sparky@lantic.net> wrote:

 Quote: What is the "actual curve" to which you refer? Is it a curve lying on the surface? Details please. --Lynn The "actual curve" is some function given in the form x = f(u, v); y = g(u, v) and z = h(u, v).

But that is not a curve, it is a surface.

 Quote: The parameters u and v are in the domain [0, 1]. I now consider two points p0(u0, v0) and p1(u1, v1). My graphics program approximates the drawing of this curve by a straight line.

What curve? You don't normally "approximate a surface" with a straight
line. Are you talking about some sort of wireframe approximation to
the surface?

-- Lynn
Jaco van Niekerk
science forum beginner

Joined: 13 Jun 2005
Posts: 11

Posted: Tue Jun 14, 2005 4:00 am    Post subject: Re: Interesting, irritating problem ;-)

Sorry for all the misunderstanding Let met try again - I am starting to
think this problem cannot be solved. Here I go again:

Consider a surface in the form x = f(u,v); y = g(u,v) and z = h(u,v). For
example, I have a sphere:

x = f(u,v) = sin(v) * cos(u)

y = g(u,v) = sin(v) * sin(u)

z = h(u, v) = cos(v)

In this case u = [-pi, pi] and v = [-pi, pi] In my program I tweak these
values so that both u and v are [0,1].

I am now approximating the surface by a wire-frame, but lets consider just a
single line for now. We have two points on the surface. Call them p0 and
p1. For both these values a unique u and v exists, such that:

p0 = (f(u0,v0), g(u0,v0), h(u0,v0)) and

p1 = (f(u1,v1), g(u1,v1), h(u1,v1))

I can now easily connect these two points with a straight line. (If I
select a large number of these points and connect them in the correct way, I
will end with a wire-frame approximation.)

My question now, where on this straight line, is the approximation the least
accurate?

For example, if I choose:

u2 = u0 + (u1-u0)/2 and

v2 = v0 + (v1-v0)/2

won't that give me the point on the surface, directly below the middle of
the straight line approximation? (Directly below would be defined as
finding the normal on the surface and when extending it, it will intersect
with line p0-p1.)

Intuitively, I think it does, but my I'm not sure how to prove this
easily:-(

The problem is, this "middle" point may not be the least accurate, it may be
somewhere else on the straight line. Lastly, "partial derivatives" may hold
the key, but my knowledge on that has become a bit rusty. Hopefully, I can
still calculate du/dx, dv/dx from f(u,v), du/dy, dv/dy from g(u,v) and
du/dz, dv/dz from h(u,v). Do I set them all to 0 and simplify? How do I
restrict u and v do be directly below the line?

I need this information, *sigh* as I am actually experimenting on using
Bezier curves (with 3 control points) to improve the approximation, and
therefore, I need to find u2, v2 on the surface that is "furthest away" from
the line.

I may be speaking in circles and I am very embarrassed by my rusty math. I
apologise. Perhaps using the sphere parameterization above as an example,
would make things clearer?

Regards

PS. I will definitely give credit in my program for the help received
today.
Micky Molar
science forum beginner

Joined: 23 Apr 2005
Posts: 21

 Posted: Tue Jun 14, 2005 4:16 am    Post subject: Re: Interesting, irritating problem ;-) My response gave you the answer. Did you not understand it?
Timothy Little
science forum Guru Wannabe

Joined: 30 May 2005
Posts: 295

Posted: Tue Jun 14, 2005 6:44 am    Post subject: Re: Interesting, irritating problem ;-)

Jaco van Niekerk wrote:
 Quote: My question now, where on this straight line, is the approximation the least accurate?

Short answer: In general, yes, near the midpoint.

This does assume various fairly sensible things about the surface
you're modelling, and that your lines are "sufficiently short".

In particular the surface should be at least piecewise twice
differentiable. If we choose a point P on the surface and look at
line segments of length L between it and another point on the surface,
the error from a point on the line at distance s will be of the form
(A s (L-s) + O(s^3)) for some constant A depending upon the second
derivatives of the parametric equations at P in the direction of the
locally normal projection from the line onto the surface.

In particular, in the limit as L -> 0, the error has a maximum at
s = L/2 unless A = 0. If the surface is not pathological, the set of
points and directions where A = 0 should have measure zero.

However it should be noted that in general, points having A = 0 will
exist, and so it will not *always* be the case that the greatest error
is at the midpoint. If you're only interested in "almost always",
then you can just use the midpoint. If you want something that
*always* works, the problem becomes much more difficult and it may
depend upon some rather messy manipulations of the parametric
equations.

For a 2-dimensional example where the midpoint does not have the
greatest error, consider line segments approximating the curve y = x^3
through x = 0. The line segment will have equation y = L^2 x, while
the curve has equation y = x^3. The maximum error occurs in y occurs
at x/L = 1/sqrt(3) instead of x/L = 1/2. (Measuring distances
vertically rather than orthogonally does not actually change the
limiting result, but the algebra in between is much easier)

For an even worse example, consider what happens if line segments are
actually from x = -L to x = +L. In that case, the midpoint actually
lies on the curve, but it is the only point (apart from the endpoints)
that does.

- Tim
Guest

Posted: Tue Jun 14, 2005 9:28 am    Post subject: Re: Interesting, irritating problem ;-)

Jaco van Niekerk wrote:
 Quote: Sorry for all the misunderstanding Let met try again - I am starting to think this problem cannot be solved. Here I go again: Consider a surface in the form x = f(u,v); y = g(u,v) and z = h(u,v). For example, I have a sphere: x = f(u,v) = sin(v) * cos(u) y = g(u,v) = sin(v) * sin(u) z = h(u, v) = cos(v) In this case u = [-pi, pi] and v = [-pi, pi] In my program I tweak these values so that both u and v are [0,1]. I am now approximating the surface by a wire-frame, but lets consider just a single line for now. We have two points on the surface. Call them p0 and p1. For both these values a unique u and v exists, such that: p0 = (f(u0,v0), g(u0,v0), h(u0,v0)) and p1 = (f(u1,v1), g(u1,v1), h(u1,v1)) I can now easily connect these two points with a straight line. (If I select a large number of these points and connect them in the correct way, I will end with a wire-frame approximation.) My question now, where on this straight line, is the approximation the least accurate?

If I am being dim, or if the other replies have answered your question,
then ignore me!

I am still unclear what exactly you are trying to do. I can think of
many different ways to measure the "error" (i.e. the accuracy of the
approximation) at any point, P, on your straight line.

For example, you could find the minimum distance, in any direction,
from P to the surface.

Or, you could project your wireframe of straight line segments onto the
surface (in some specified direction), so as to form a network of
curved lines lying on the surface. Then you could measure the minimum
distance from P to the corresponding line on the surface.

Or you could measure the distance from P to the corresponding line on
the surface in a specified direction (say parallel to the z-axis).

All these (and any others you might come up with) will, in general,
Lynn Kurtz
science forum Guru

Joined: 02 May 2005
Posts: 603

Posted: Tue Jun 14, 2005 8:15 pm    Post subject: Re: Interesting, irritating problem ;-)

On Tue, 14 Jun 2005 08:00:12 +0200, "Jaco van Niekerk"
<sparky@lantic.net> wrote:

 Quote: My question now, where on this straight line, is the approximation the least accurate? For example, if I choose: u2 = u0 + (u1-u0)/2 and v2 = v0 + (v1-v0)/2 won't that give me the point on the surface, directly below the middle of the straight line approximation?

For sufficiently well behaved surfaces, nice parameterizations, and
sufficiently small step sizes, probably it would be close. But your
parameterization may be very nonlinear at some points, and half way
along the parameter space may not correspond to half way between the
points on the surface.

 Quote: (Directly below would be defined as finding the normal on the surface and when extending it, it will intersect with line p0-p1.)

I think the concept of "below" has problems for a parameterized
surface. And certainly, given the mid point (u2, v2) there is no
reason to expect that the point R(u2, v2) on the surface will have a

 Quote: Intuitively, I think it does, but my I'm not sure how to prove this easily:-(

I don't think you can prove it because it probably isn't true.

-- Lynn
Mike1156
science forum beginner

Joined: 14 Jun 2005
Posts: 11

Posted: Tue Jun 14, 2005 9:44 pm    Post subject: Re: Interesting, irritating problem ;-)

In article <d8lrpi\$dla\$1@ctb-nnrp2.saix.net>,
sparky@lantic.net says...
 Quote: Sorry for all the misunderstanding Let met try again - I am starting to think this problem cannot be solved. Here I go again: Consider a surface in the form x = f(u,v); y = g(u,v) and z = h(u,v). For example, I have a sphere: x = f(u,v) = sin(v) * cos(u) y = g(u,v) = sin(v) * sin(u) z = h(u, v) = cos(v) In this case u = [-pi, pi] and v = [-pi, pi] In my program I tweak these values so that both u and v are [0,1]. I am now approximating the surface by a wire-frame, but lets consider just a single line for now. We have two points on the surface. Call them p0 and p1. For both these values a unique u and v exists, such that: p0 = (f(u0,v0), g(u0,v0), h(u0,v0)) and p1 = (f(u1,v1), g(u1,v1), h(u1,v1)) I can now easily connect these two points with a straight line. (If I select a large number of these points and connect them in the correct way, I will end with a wire-frame approximation.) My question now, where on this straight line, is the approximation the least accurate? For example, if I choose: u2 = u0 + (u1-u0)/2 and v2 = v0 + (v1-v0)/2 won't that give me the point on the surface, directly below the middle of the straight line approximation? (Directly below would be defined as finding the normal on the surface and when extending it, it will intersect with line p0-p1.)

I don't think you can guarantee that this will work because
you cannot guarantee that the 'physical' path between p0 and
p1 bears any relationship to the path formed by varying the
parameters u0 -> u1 and v0 -> v1.

For example. If you replace your three equations with
something messily contrived like
x = f(u,v)
= sin((sin(2*v)^2+2*v)/2) * cos(2*pi*u^(1/7)-pi)
y = g(u,v)
= sin((sin(2*v)^2+2*v)/2) * sin(2*pi*u^(1/7)-pi)
z = h(u,v)
= cos((sin(2*v)^2+2*v)/2)
(with 0<=u<=1, -pi<=v<=pi)
your surface will still be a sphere, but if you chose some
p0(u0,v0) and p1(u1,v1) then the point p2(u2,v2), as defined
above, will still obviously be somewhere on the surface of
the sphere but it won't necessarily lie on the great circle
between p0 and p1. The point on the surface of the sphere
directly above the point (p0+p1)/2 on the line p0-p1 may be
given by P(u',v') where u' .neq. (u0+u1)/2 and v' .neq. (v1
+v2)/2.
Jaco van Niekerk
science forum beginner

Joined: 13 Jun 2005
Posts: 11

Posted: Wed Jun 15, 2005 4:11 am    Post subject: Re: Interesting, irritating problem ;-)

Yes, thank you Mickey. I sat yesterday and figured it out. One or two
things remain unclear, but I'll post it after I've fiddled with the math a
bit.

Thank you very much for your help.

"Micky Molar" <tony.tooth@btinternet.com> wrote in message
 Quote: My response gave you the answer. Did you not understand it?

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [13 Posts]
 The time now is Fri Nov 24, 2017 9:08 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics help on problem brb003 Math 0 Mon Aug 28, 2006 3:31 am fraction problem mikerule Research 0 Thu Aug 24, 2006 5:10 am Mod computer problem William Elliot Math 4 Fri Jul 21, 2006 12:07 pm Divine apparitions in the tethered goat problem? jpalmour@gmail.com Math 6 Thu Jul 20, 2006 8:26 pm possible to use Generalized Method of Moments for this pr... comtech Math 1 Thu Jul 20, 2006 12:49 am