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

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? 

Back to top 


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

Back to top 


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" <kurtzDELETETHIS@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

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 3D), 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

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 

Back to top 


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 wireframe, 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 wireframe approximation.)
My question now, where on this straight line, is the approximation the least
accurate?
For example, if I choose:
u2 = u0 + (u1u0)/2 and
v2 = v0 + (v1v0)/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 p0p1.)
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. 

Back to top 


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? 

Back to top 


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 (Ls) + 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 2dimensional 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

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 wireframe, 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 wireframe 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 zaxis).
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

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 + (u1u0)/2 and
v2 = v0 + (v1v0)/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 p0p1.)

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

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



In article <d8lrpi$dla$1@ctbnnrp2.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 wireframe, 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 wireframe approximation.)
My question now, where on this straight line, is the approximation the least
accurate?
For example, if I choose:
u2 = u0 + (u1u0)/2 and
v2 = v0 + (v1v0)/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 p0p1.)

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

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



The time now is Fri Nov 24, 2017 9:08 am  All times are GMT

