FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Recreational
Interesting, irritating problem ;-)
Post new topic   Reply to topic Page 1 of 1 [13 Posts] View previous topic :: View next topic
Author Message
Jaco van Niekerk
science forum beginner


Joined: 13 Jun 2005
Posts: 11

PostPosted: Mon Jun 13, 2005 1:03 pm    Post subject: Interesting, irritating problem ;-) Reply with 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). 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?
Back to top
Guest






PostPosted: Mon Jun 13, 2005 2:35 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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?
Back to top
Lynn Kurtz
science forum Guru


Joined: 02 May 2005
Posts: 603

PostPosted: Mon Jun 13, 2005 3:09 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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
the surface? Details please.

--Lynn
Back to top
Jaco van Niekerk
science forum beginner


Joined: 13 Jun 2005
Posts: 11

PostPosted: Mon Jun 13, 2005 4:08 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

"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
Back to top
Micky Molar
science forum beginner


Joined: 23 Apr 2005
Posts: 21

PostPosted: Mon Jun 13, 2005 4:25 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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.
Back to top
Lynn Kurtz
science forum Guru


Joined: 02 May 2005
Posts: 603

PostPosted: Mon Jun 13, 2005 5:58 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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
Back to top
Jaco van Niekerk
science forum beginner


Joined: 13 Jun 2005
Posts: 11

PostPosted: Tue Jun 14, 2005 4:00 am    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

Sorry for all the misunderstanding Wink 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. Smile
Back to top
Micky Molar
science forum beginner


Joined: 23 Apr 2005
Posts: 21

PostPosted: Tue Jun 14, 2005 4:16 am    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

My response gave you the answer. Did you not understand it?
Back to top
Timothy Little
science forum Guru Wannabe


Joined: 30 May 2005
Posts: 295

PostPosted: Tue Jun 14, 2005 6:44 am    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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
Back to top
Guest






PostPosted: Tue Jun 14, 2005 9:28 am    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

Jaco van Niekerk wrote:
Quote:
Sorry for all the misunderstanding Wink 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,
give different answers.
Back to top
Lynn Kurtz
science forum Guru


Joined: 02 May 2005
Posts: 603

PostPosted: Tue Jun 14, 2005 8:15 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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
normal that intersects your line.

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
Back to top
Mike1156
science forum beginner


Joined: 14 Jun 2005
Posts: 11

PostPosted: Tue Jun 14, 2005 9:44 pm    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

In article <d8lrpi$dla$1@ctb-nnrp2.saix.net>,
sparky@lantic.net says...
Quote:
Sorry for all the misunderstanding Wink 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.
Back to top
Jaco van Niekerk
science forum beginner


Joined: 13 Jun 2005
Posts: 11

PostPosted: Wed Jun 15, 2005 4:11 am    Post subject: Re: Interesting, irritating problem ;-) Reply with quote

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
news:1118729775.281097.141380@f14g2000cwb.googlegroups.com...
Quote:
My response gave you the answer. Did you not understand it?
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [13 Posts] View previous topic :: View next topic
The time now is Fri Nov 24, 2017 9:08 am | All times are GMT
Forum index » Science and Technology » Math » Recreational
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0383s ][ Queries: 16 (0.0064s) ][ GZIP on - Debug on ]