gdalgorithms-list

Re: [Algorithms] Octree leaf neighbours

[<SHA...@ao...>]

In a message dated 15/07/00 20:59:35 !!!First Boot!!!, sa...@ip... writes:

<< I'm creating an octree, and need to maintain pointers between neighbouring
<< *leaves*, and do it quick. The only way I can think of is to skip back up
<<the tree and down the neighbouring branches to locate each of the 6
<< neighbours. This doesn't seem very fast.

Surely you mean 7 neighbours?

 
<< There is a method called "linear octrees" which supposedly let you use the
<< so called "morton number" to directly hash a neighbour from is location in 
3
<< space. But I believe you *have to subdivide the whole octree evenly* so
<< every leaf is stored and can be hashed properly. (i.e. a 3d array!). Fat 
use
<< since the reason i'm using an octree is to avoid a memory hungry grid in 
the
<< first place, or am I missing the point?
 
 Any insights would be appriciated!
 
 Sam.
>>

Looks like you need to provide a 'pointer to parent node' member in your 
structure to allow you to go back up a step and access the current nodes 
neighbours.

In my original octree implimentation I had such a pointer but later found I 
didn't need it so I took it out.

Why do you need access a parent nodes neighbours at this point?

Your code should have dealt with that node when it was 'in play' during the 
recursive traversal procedure.

You must know of course that when you are looking at a particular node you 
have access to all of it's children or as you call them, neighbours.

Maybe I am missing something here, but isn't your octree traversal recursive?

Each node that you subdivide, are you subdividing it into 8 equal parts?


And yes you are right, if you use a linear octree you will be creating many 
more nodes than you need.

Regards,

John. 

RE: [Algorithms] C++ inherited constructors

[Aaron D. <ri...@ho...>]

Why not have your base class constructor call a virtual private member
function and overload that function in the derived class?

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Matt
> Adams
> Sent: Saturday, July 15, 2000 9:19 PM
> To: gda...@li...
> Subject: Re: [Algorithms] C++ inherited constructors
>
>
>
> I need this for aesthetic reasons :)
> I've got an abstract CThread class. If a want to create a new thread, I
> build my process class and inherit CThread, which creates a new thread by
> construction.
> Now I want my main-threadloop-class to inherit CThread, too, to
> provide all
> the thread functionality to my main thread. But that thread already exists
>  created by compiler ), and shouldn't be created again by CThread.
> Of course I can put CThread () and ~CThread () in functions like Create()
> and Destroy() and leave the constructor / destructor empty. But it'd be
> nicer if it could be done in another way...
>
> ----- Original Message -----
> From: Favnir
> To: gda...@li...
> Sent: Saturday, July 15, 2000 1:32 PM
> Subject: Re: [Algorithms] C++ inherited constructors
>
> The only way you can do this is to define a (preferably) protected
> do-nothing constructor for the base class, and inherit it in the subclass
> constructor.
>
> But, why in the world would you need to do this, in the first place?
>
> Are,
> F
>
> ----- Original Message -----
> From: Matt Adams
> To: gda...@li...
> Sent: Saturday, July 15, 2000 12:22 PM
> Subject: [Algorithms] C++ inherited constructors
>
>
> Hi,
>
> I got a question about the C++ class hierarchy.
>
> class a
> {
>     a () {...}; // constr a
> };
>
> class b : a
> {
>     b () {...}; // constr b
> };
>
> b instance;
>
> When creating an instance of b, constructors for both class a and class b
> are called.
> Is there a way to suppress the automatic calling of constructor a ?
> Or something like 'overloading' the old constructor by a new one ?
> I couldn't find anything like that in the compiler docs.
>
> Any help appreciated,
> Matt
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Byte Swapping

[Jens A. <jAy...@ne...>]

Tom Hubina:
> Jens Ayton:
>> Tom Hubina:
>>>
>>> I can do the obvious method, but I was wondering if anyone
>>> have any cool/fast code snippets for byte swapping integers
>>> and floats?
>>
>> Depends on the platform. PowerPCs have "load word byte-
>> reversed indexed" (lwbrx) and "load halfword byte-reversed
>> indexed" (lhbrx) instructions, for instance.
> 
> Since that happens to be my platform, perhaps you would have
> some routines handy that work in Codewarrior for the Mac that
> make those calls to reverse the bytes I'm loading?

These instructions are available as intrinsics. If you have an aligned
array theLittleEndianArrayOfLongs of wrong-endian longs, this:

long theLong = __lwbrx(theLittleEndianArrayOfLongs, n);

is equivalent to

long theLong = theBigEndianArrayOfLongs[n];

for right-endian data. Similarly, you can use

short theShort = __lhbrx(theLittleEndianArrayOfShorts, n);
                    ^
Note the "w" vs. "h" as marked.

-- 
Jens Ayton

Re: [Algorithms] Byte Swapping

[Tom H. <to...@3d...>]

At 08:42 AM 7/16/2000 +0200, you wrote:
> > I can do the obvious method, but I was wondering if anyone have any
> > cool/fast code snippets for byte swapping integers and floats?
>
>Depends on the platform. PowerPCs have "load word byte-reversed indexed"
>(lwbrx) and "load halfword byte-reversed indexed" (lhbrx) instructions,
>for instance.

Since that happens to be my platform, perhaps you would have some routines 
handy that work in Codewarrior for the Mac that make those calls to reverse 
the bytes I'm loading?

Tom

Re: [Algorithms] Byte Swapping

[Jens A. <jAy...@ne...>]

> I can do the obvious method, but I was wondering if anyone have any 
> cool/fast code snippets for byte swapping integers and floats?

Depends on the platform. PowerPCs have "load word byte-reversed indexed"
(lwbrx) and "load halfword byte-reversed indexed" (lhbrx) instructions,
for instance.


-- 
Jens Ayton

[Algorithms] Byte Swapping

[Tom H. <to...@3d...>]

I can do the obvious method, but I was wondering if anyone have any 
cool/fast code snippets for byte swapping integers and floats?

Tom

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Peter Dimov  wrote:

>> >> how to you get scalars (u,v) such that u*a + v*b = p?
>> >> Ie. decompose p onto a and b.
>> >
>> >Easy. dot the equation with a and b, correspondingly:
>> >
>> >u * (a dot a) + v * (b dot a) = p dot a;
>> >v * (a dot b) + v * (b dot b) = p dot b.
>> >
>> >Solve the system.
>>
>> In the 2D case this is more complicated than it need be, but will give
>> the correct solution (provided, of course that one knows dot product
>> and how to solve a 2x2 system).
>>
>> In the 3D case, this will give the correct solution only if p is
>> indeed in the plane of a and b.  It will not detect that there is no
>> solution if p is not coplanar with a and b.
>
>This works for any number of dimensions. Whenever a solution exists, the (u,
>v) pair determined by this approach will have the property u * a + v * b =
>p. (Easy to prove.)

Agree that it works for any number of dimensions provided that p does
indeed lie in the plane of a and b.  My point was that it will not
detect the case that p does not lie in that plane, that is, will not
detect the case that no solution exisits.  

Re: [Algorithms] decompose onto non-orthogonal vectors

[Peter D. <pd...@mm...>]

> >> how to you get scalars (u,v) such that u*a + v*b = p?
> >> Ie. decompose p onto a and b.
> >
> >Easy. dot the equation with a and b, correspondingly:
> >
> >u * (a dot a) + v * (b dot a) = p dot a;
> >v * (a dot b) + v * (b dot b) = p dot b.
> >
> >Solve the system.
>
> In the 2D case this is more complicated than it need be, but will give
> the correct solution (provided, of course that one knows dot product
> and how to solve a 2x2 system).
>
> In the 3D case, this will give the correct solution only if p is
> indeed in the plane of a and b.  It will not detect that there is no
> solution if p is not coplanar with a and b.

This works for any number of dimensions. Whenever a solution exists, the (u,
v) pair determined by this approach will have the property u * a + v * b =
p. (Easy to prove.)

--
Peter Dimov
Multi Media Ltd.

[Algorithms] RE: [GDAlgorithms-List] New List

[Steve W. <Ste...@im...>]

Excellent! The list is back to working great.  Can't thank you enough.
R&R

> -----Original Message-----
> From: Tom Hubina [mailto:to...@3d...]
> Sent: Thursday, July 13, 2000 8:38 PM
> To: gda...@li...
> Subject: [GDAlgorithms-List] New List
> 
> 
> If everyone seems to get this email I'll be setting up the 
> alg...@3d... address to forward emails to the new 
> address at 
> GDA...@li.... That should make 
> replies to old 
> emails end up on the new list. Everyone will need to adjust 
> their mail 
> filters to pick up the new list topics and To: fields and 
> people who used 
> to receive digests will need to reset themselves with the new list.
> 
> I'm sure there will be a few minor configuration changes over 
> the next day 
> or two, but hopefully they will resolve themselves quickly. 
> After that I'll 
> work with the SourceForge people to get the complete archives 
> (I still have 
> every email ever sent to this list) up and sorted properly. 
> Thank you for 
> you understanding, and hopefully we'll have a very clean, robust list 
> server very shortly!
> 
> Tom
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

[Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

Hi,

I'm creating an octree, and need to maintain pointers between neighbouring
*leaves*, and do it quick. The only way I can think of is to skip back up
the tree and down the neighbouring branches to locate each of the 6
neighbours. This doesn't seem very fast.

There is a method called "linear octrees" which supposedly let you use the
so called "morton number" to directly hash a neighbour from is location in 3
space. But I believe you *have to subdivide the whole octree evenly* so
every leaf is stored and can be hashed properly. (i.e. a 3d array!). Fat use
since the reason i'm using an octree is to avoid a memory hungry grid in the
first place, or am I missing the point?

Any insights would be appriciated!

Sam.

Re: [Algorithms] C++ inherited constructors

[Will P. <wi...@cs...>]

I don't completely understand your problem, but it might be solvable by
using containment rather than inheritance, i.e. a process *has* a thread
rather than *is* a thread.  I think it would allow for the semantics you
want.  You could pass in an external thread for the process/main loop to
"have" through a constructor argument, or you could just have the
process/main loop create a thread through it's default argumentless
constructor.

The same goes with your main loop class: it has a thread, not is a
thread.

It's an idea, anyway. :)

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will

On Sat, 15 Jul 2000, Matt Adams wrote:

> I need this for aesthetic reasons :)
> I've got an abstract CThread class. If a want to create a new thread, I
> build my process class and inherit CThread, which creates a new thread by
> construction.
> Now I want my main-threadloop-class to inherit CThread, too, to provide all
> the thread functionality to my main thread. But that thread already exists
>  created by compiler ), and shouldn't be created again by CThread.
> Of course I can put CThread () and ~CThread () in functions like Create()
> and Destroy() and leave the constructor / destructor empty. But it'd be
> nicer if it could be done in another way...
> 
> ----- Original Message -----
> From: Favnir
> To: gda...@li...
> Sent: Saturday, July 15, 2000 1:32 PM
> Subject: Re: [Algorithms] C++ inherited constructors
> 
> The only way you can do this is to define a (preferably) protected
> do-nothing constructor for the base class, and inherit it in the subclass
> constructor.
> 
> But, why in the world would you need to do this, in the first place?
> 
> Are,
> F
> 
> ----- Original Message -----
> From: Matt Adams
> To: gda...@li...
> Sent: Saturday, July 15, 2000 12:22 PM
> Subject: [Algorithms] C++ inherited constructors
> 
> 
> Hi,
> 
> I got a question about the C++ class hierarchy.
> 
> class a
> {
>     a () {...}; // constr a
> };
> 
> class b : a
> {
>     b () {...}; // constr b
> };
> 
> b instance;
> 
> When creating an instance of b, constructors for both class a and class b
> are called.
> Is there a way to suppress the automatic calling of constructor a ?
> Or something like 'overloading' the old constructor by a new one ?
> I couldn't find anything like that in the compiler docs.
> 
> Any help appreciated,
> Matt
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] C++ inherited constructors

[Adam M. <amo...@dp...>]

That, together with the fact that constructors can't return error codes
(only throw exceptions) when something goes wrong, has me following a very
simple design heuristic ever since I can remember:  Don't make a constructor
do anything other than initializing member variables.  In other words, don't
let it do anything that can go wrong.  Put that code (for example the thread
creation code in your case) in another method that has to be called after
construction.  If you had done that when you designed the CThread class, you
wouldn't have a problem.
--
--Adam Moravanszky
http://www.n.ethz.ch/student/adammo

-----Original Message-----
From: Matt Adams <de...@gm...>
To: gda...@li...
<gda...@li...>
Date: Saturday, July 15, 2000 1:19 PM
Subject: Re: [Algorithms] C++ inherited constructors


>I need this for aesthetic reasons :)
>I've got an abstract CThread class. If a want to create a new thread, I
>build my process class and inherit CThread, which creates a new thread by
>construction.
>Now I want my main-threadloop-class to inherit CThread, too, to provide all
>the thread functionality to my main thread. But that thread already exists
> created by compiler ), and shouldn't be created again by CThread.
>Of course I can put CThread () and ~CThread () in functions like Create()
>and Destroy() and leave the constructor / destructor empty. But it'd be
>nicer if it could be done in another way...
>
>----- Original Message -----
>From: Favnir
>To: gda...@li...
>Sent: Saturday, July 15, 2000 1:32 PM
>Subject: Re: [Algorithms] C++ inherited constructors
>
>The only way you can do this is to define a (preferably) protected
>do-nothing constructor for the base class, and inherit it in the subclass
>constructor.
>
>But, why in the world would you need to do this, in the first place?
>
>Are,
>F
>
>----- Original Message -----
>From: Matt Adams
>To: gda...@li...
>Sent: Saturday, July 15, 2000 12:22 PM
>Subject: [Algorithms] C++ inherited constructors
>
>
>Hi,
>
>I got a question about the C++ class hierarchy.
>
>class a
>{
>    a () {...}; // constr a
>};
>
>class b : a
>{
>    b () {...}; // constr b
>};
>
>b instance;
>
>When creating an instance of b, constructors for both class a and class b
>are called.
>Is there a way to suppress the automatic calling of constructor a ?
>Or something like 'overloading' the old constructor by a new one ?
>I couldn't find anything like that in the compiler docs.
>
>Any help appreciated,
>Matt
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Reprise:

In the 3D case:

If  you are certain that p lies in the plane spanned by a and b, then
Peter Dimov's solution is the best.  (assuming you understand dot
products and 2x2 linear systems).

And, in fact,  that is exactly what I use in my code to find the
intersection of a ray with a triangle with given vertices V0, V1, V2:
First find the intersection P of the ray with the plane of the
triangle.  Refer everything, i.e. the intersection point and two of
the vertices, to any one vertex V0, so that, to cast it into Ben's
notation, p = P - V0, a=V1-V0 and b=V2-V0, and we are certain that p
lies in the plane through V0 spanned by a and b.  Form the dot
products as Peter indicates, and solve the resulting 2x2 system for u
and v.  The result V0 + ua + vb will lie in the triangle if and only
if 0<=u, 0<=v and u+v<=1.

But if you do not know a priori that p is a linear combination of a
and b, then the only way to determine that (finding u and v in the
process) is by Gaussian elimination on the underdetermined system as I
described. Of course, you can organize the Gaussian elimination
efficiently by thinking of it as row operations on the matrix of the
system, rather than elementary operations on the equations.  The
matrix approach is simply a tabular organization of the manipulation
of the equations themselves.

RE: [Algorithms] decompose onto non-orthogonal vectors

[Tom F. <to...@mu...>]

True - I did take a few short-cuts when describing the solution. :-)

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> Sent: 15 July 2000 18:22
> To: gda...@li...
> Subject: Re: [Algorithms] decompose onto non-orthogonal vectors
> 
> 
> I  wrote:
> 
> >Tom Forsyth  wrote:
> >
> >>Throw one of the dimensions away (any one) - then you have only two
> >>equations. NOW can you solve it? :-)
> >>
> >>The third dimension will just give the same answer if p 
> lies in the plane of
> >>a and b. If it isn't, then it's not a well-formed question, 
> and you'll need
> >>another axis (c) to define a suitable basis. 
> >
> >Not true.  p can very well lie in the plane of a and b without that
> >plane being a coordinate plane.  In that case, the problem is well
> >formed and your solution will give the wrong answer.
> 
>  Ooops, you are indeed correct.   But your solution does not detect
> the ill-formed case.  And moreover, you do have to be careful about
> which dimension to throw away.  If the thing does lie in one of the
> coordinate planes then you can't throw away that dimension.  And you
> can also use some intellegence about which coordiate plane to throw
> away to minimize the errors.
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

I  wrote:

>Tom Forsyth  wrote:
>
>>Throw one of the dimensions away (any one) - then you have only two
>>equations. NOW can you solve it? :-)
>>
>>The third dimension will just give the same answer if p lies in the plane of
>>a and b. If it isn't, then it's not a well-formed question, and you'll need
>>another axis (c) to define a suitable basis. 
>
>Not true.  p can very well lie in the plane of a and b without that
>plane being a coordinate plane.  In that case, the problem is well
>formed and your solution will give the wrong answer.

 Ooops, you are indeed correct.   But your solution does not detect
the ill-formed case.  And moreover, you do have to be careful about
which dimension to throw away.  If the thing does lie in one of the
coordinate planes then you can't throw away that dimension.  And you
can also use some intellegence about which coordiate plane to throw
away to minimize the errors.

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

I  wrote:

>.  For the party
>they'd built a perfectly working model guillotine, about three feet
>tall, and used it to chop up the frogs for the frog-leg barbecue. 
>

I hasten to clarify that the frogs were already dead and skinned,
looking much like plucked chickens in texture, but quite humanoid in
form.

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Tom Forsyth  wrote:

>Throw one of the dimensions away (any one) - then you have only two
>equations. NOW can you solve it? :-)
>
>The third dimension will just give the same answer if p lies in the plane of
>a and b. If it isn't, then it's not a well-formed question, and you'll need
>another axis (c) to define a suitable basis. 

Not true.  p can very well lie in the plane of a and b without that
plane being a coordinate plane.  In that case, the problem is well
formed and your solution will give the wrong answer.

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Klaus Hartmann  wrote:

>
>----- Original Message -----
>From: Scott Justin Shumaker <sjs...@um...>
>To: <gda...@li...>
>Sent: Saturday, July 15, 2000 9:15 AM
>Subject: Re: [Algorithms] decompose onto non-orthogonal vectors
>
>
>> Okay, let me try and explain this as simply as possible.  You want to find
>> scalars u,v such that u*a + v*b = p.  Since these are 3-dimensional
>> vectors, you have 3 equations and 2 unknowns:
>>
>> u*a1 + v*b1 = p1
>> u*a2 + v*b2 = p2
>> u*a3 + v*b3 = p3
>>
>> where p1,p2,p3 are the coordinates of the point p, likewise for a1,a2,a3
>> and a, and b1,b2,b3 and b.
>>
>> How do you solve a system of 3 linear equations with 2 unknowns?  If you
>> don't know Gaussian elimination, this can be done with some simple
>> algebraic rules and substituion.
>
>Okay, this may become very embarrassing for me now... :) How can you solve a
>system of 3 linear equations in two unknows, u, v, if they cannot be reduced
>to two linear equations 

The system of three equations is equivalent to (i.e, has exactly the
same solutions as) a system of two equations if and only if one of the
equations is a linear combination of the other two.  And you determine
whether or not this is the case by Gaussian elimination. "Elimination"
entails eliminating unknowns from equations.  If there are more
equations than unknowns,  then Gaussian elimination will get you to a
step where one of the equations has no remaining unknowns.  If this
unknownless equation is a TRUE equation, e.g.  0=0 or 127 = 127, then
it is irrelevant, the three equations were indeed linearly dependent,
and the Gaussian elimination will have left you with a system of two
equations in two unknowns.   If this unknownless equation is a FALSE
equation, e.g.  0 = 1,  then we know that the original system of three
equations is inconsistent and has NO solutions.

Each step of Gaussian elimination consists of multiplying an equation
term wise by a constant, or replacing one of the equations by the
term-wise sum of itself with a multiple of one of the other equations.
One can easily see that this does not change the set of possible
solutions to the system.  The trick then is to choose the two
equations and the multiplier at each step so that it results in
eliminating one of the unknowns from one of the equations.  It's not a
hard trick and I'm not going to say any more about it here, except to
point out that there are various versions of the algorithm motivated
by minimizing the number of steps or minimizing the potential
numerical errors in the result.

This is all VERY ELEMENTARY LINEAR ALGEBRA,  It discourages me that a
mail list supposedly on game algorithms spends so much time on stuff
that everyone ought to have had in their basic formation, and which is
better learned from math courses and text books than from mail lists.

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Peter Dimov  wrote:

>> Given a point p and two unit vectors a and b like this:
>> 
>>       b
>>      /
>>    v/----p
>>    /    /
>>   /    /
>>  /    /
>> ---------a
>>     u
>> 
>> how to you get scalars (u,v) such that u*a + v*b = p?
>> Ie. decompose p onto a and b.
>
>Easy. dot the equation with a and b, correspondingly:
>
>u * (a dot a) + v * (b dot a) = p dot a;
>v * (a dot b) + v * (b dot b) = p dot b.
>
>Solve the system.

In the 2D case this is more complicated than it need be, but will give
the correct solution (provided, of course that one knows dot product
and how to solve a 2x2 system).

In the 3D case, this will give the correct solution only if p is
indeed in the plane of a and b.  It will not detect that there is no
solution if p is not coplanar with a and b.  

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Discoe, Ben  wrote:

>
>> From: ro...@do... [mailto:ro...@do...]
>>
>> Chapter 1 in any linear algebra book.
>
>I assure i looked in chapters 1 though 18 of my book ("calculus and analytic
>geomtry", thomas/finney) and nothing resemling a formula for decomposing a
>vector is anywhere in it. 

Ah, while that is a fine calculus book, it is not an elementary linear
algebra book.  The main point you missed is that the single vector
equation is a set of two (in 2D) or three (in 3D) scalar equations.

> In general, math textbooks tend to be concerned
>with axioms and definitions, not with formulas that actually prove to be
>useful.
>

This assertion betrays an utterly mathophobic attitude, which is
likely to hinder your continuing progress.  The fact is that a lot of
the math nonsense we see posted to lists like this simply results from
people not taking sufficient care to define their terms.

>> That is A SYSTEM OF TWO LINEAR EQUATIONS IN TWO UNKNOWNS u, v,
>> which you ought to have learned to solve in intermediate algebra,
>
>I was asking if somebody knew the solution, not for how to do the math,
>which i'm willing to leave to people who enjoy re-deriving solutions to math
>problems.
>
>> 	u = (p1 b2 - p2 b1)/(a1 b2 - a2 b1)
>> 	v = (a1 p2 - a2 p1)/(a1 b2 - a2 b1)
>

Again a statement that doesn't make much sense to me.  You can't learn
in advance all solutions to all problems. Education consists of
learning how to have the courage to attack problems whose solution you
don't already know.  It would have been no benefit at all to you to to
simply write down the above formulas, in fact it would have been wrong
because, as it turns out, you were actually thinking of the 3D version
of the problem.

That's another important relevant point.  There is no hope of solving
a problem, or even having a sensible discussion about it, if it is not
clearly and completely stated.  An enormous number of the math queries
that we see posted to newsgroups and email lists are impossible to
answer because they are not clearly stated, the problem statement
doesn't make sense.  Taking math courses from good teachers is one of
the best ways to improve ones understanding of when a problem
statement makes sense.

>OK, i'll believe that after solving for v and substituting twice (a page or
>so of algebra) you get that 2d solution.
>



>> If the denominator (a1 b2 - a2 b1) is zero then it means that a and b
>> are linearly dependent (i.e. collinear) and either it has no solution
>> (if p is not also collinear with a and b) or infinitely many different
>> solutions (if p is collinear with a and b)
>
>The picture i drew showed a nondegenerate case.
>

Yes, but whenever one writes down an algebraic formula that involves
division, one MUST ask under what conditions the divisor can be zero.
For good reasons, computers don't like to divide by zero.  

>> Now suppose that you are given this as a 3D problem, say
>> 	a = (a1,  a2,  a3) and b = (b1, b2, b3)
>
>Yes.  I'm sorry i forgot to state that i do have 3d vectors, and p is known
>to lie in the plane formed by a and b.
>

Apology accepted. See comment above. 

>> It may or may no have solutions..
>> Cramer's rule does not apply here, but Gaussian elimination
>> still does.
>
>Is this your way of saying you don't know the answer?
>
OF COURSE NOT.  

>It would be pretty sad if not a single person on the list knows the answer.
>I was kinda hoping *you* would, Ron :)
>

The point you have evidently missed is that in the 3D case nobody
knows the answer a prior, nobody can write down a simple algebraic
formula giving the answer.    The point is that the algorithm for
finding the answer in ANY case is just one of the basic techniques
that we learn in elementary linear algebra. 
 
Talk about "sad":    What makes me sad is prevalence of mathophobia.
What makes me sadder is that so few participants in this list could
help you here.  What makes me saddest is the posting of completely
erroneous solutions to problems such as this.

>> No, I will not belabor the list with a review of Gaussian elimination
>> algorithms.  You will find one in Chapter 1 of your favorite linear
>> algebra book.
>
>The index in my textbook does not list "Gaussian elimination".
>

Try a linear algebra textbook, not a calculus and analytic geometry
text book.

>Thanks,

Welcome

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

I  wrote:

>Jonathan Blow  wrote:
>
>>Just build a transformation matrix from R to S, and
>>call that matrix T.  Then p' = Tp and you are done.
>>
>>For instructions on how to make a matrix that goes from
>>one space to another, given the basis vectors of each 
>>space, consult any one of a trillion graphics books.
>
>Again, you don't need matrices (maybe chapter 3) but just high school
>algebra.
>

Since I was rushing out the door to a Bastille Day party I didn't get
a chance to add that your "change of basis" approach DOES have the
benefit that when you get this matrix, then you can solve the same
problem for ANY OTHER vector p, simply by a matrix multiplication.  

But again, that was a much more complicated problem than that which
was asked, involving just one given vector p.  And also it would apply
only in the case that Ben was thinking of a 2D problem and we have
learned from a subsequent post that it is the 3D problem he had in
mind. (It takes three indepdent vectors, not two, to form a basis of
3-space).

P.S. The Bastille Day party was great fun.  It was held in the studio
of a Berkeley company called Scientific Arts, the folks who built the
giant baseball mitt and Coke-bottle kiddy slide that grace the
lefr-field bleachers of the new SF Giants ballpark.  For the party
they'd built a perfectly working model guillotine, about three feet
tall, and used it to chop up the frogs for the frog-leg barbecue. 

RE: [Algorithms] decompose onto non-orthogonal vectors

[Tom F. <to...@mu...>]

Throw one of the dimensions away (any one) - then you have only two
equations. NOW can you solve it? :-)

The third dimension will just give the same answer if p lies in the plane of
a and b. If it isn't, then it's not a well-formed question, and you'll need
another axis (c) to define a suitable basis. Then you have three dimensions
and three unknowns, which you solve as you stated.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Klaus Hartmann [mailto:k_h...@os...]
> Sent: 15 July 2000 15:01
> To: gda...@li...
> Subject: Re: [Algorithms] decompose onto non-orthogonal vectors
> 
> 
> 
> ----- Original Message -----
> From: Scott Justin Shumaker <sjs...@um...>
> To: <gda...@li...>
> Sent: Saturday, July 15, 2000 9:15 AM
> Subject: Re: [Algorithms] decompose onto non-orthogonal vectors
> 
> 
> > Okay, let me try and explain this as simply as possible.  
> You want to find
> > scalars u,v such that u*a + v*b = p.  Since these are 3-dimensional
> > vectors, you have 3 equations and 2 unknowns:
> >
> > u*a1 + v*b1 = p1
> > u*a2 + v*b2 = p2
> > u*a3 + v*b3 = p3
> >
> > where p1,p2,p3 are the coordinates of the point p, likewise 
> for a1,a2,a3
> > and a, and b1,b2,b3 and b.
> >
> > How do you solve a system of 3 linear equations with 2 
> unknowns?  If you
> > don't know Gaussian elimination, this can be done with some simple
> > algebraic rules and substituion.
> 
> Okay, this may become very embarrassing for me now... :) How 
> can you solve a
> system of 3 linear equations in two unknows, u, v, if they 
> cannot be reduced
> to two linear equations (for example, a2 = a3, b2 = b3, and 
> p2 = p3)???
> 
> Let's assume that we change the 3 linear equations as follows:
> 
> u*a1 + v*b1 + w*c1 = p1
> u*a2 + v*b2 + w*c2 = p2
> u*a3 + v*b3 + w*c3 = p3
> 
> Then there's a unique solution, if
> 
>       | a1 b1 c1 |
> det | a2 b2 c2 | != 0
>       | a3 b3 c3 |
> 
> If we set c1 = c2 = c3 = 0, then we have the same system as 
> above (yours),
> but with 3 unknowns:
> 
> u*a1 + v*b1 + w*0 = p1
> u*a2 + v*b2 + w*0 = p2
> u*a3 + v*b3 + w*0 = p3
> 
> Then
>                | a1 b1 0 |
> Dn = det | a2 b2 0  | = 0
>                | a3 b3 0 |
> 
> Since Dn = 0, we get a division by zero, and thus there's an 
> infinite number
> of solutions.
> 
> ... or did I just miss something???
> 
> Niki
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] decompose onto non-orthogonal vectors

[Klaus H. <k_h...@os...>]

----- Original Message -----
From: Scott Justin Shumaker <sjs...@um...>
To: <gda...@li...>
Sent: Saturday, July 15, 2000 9:15 AM
Subject: Re: [Algorithms] decompose onto non-orthogonal vectors


> Okay, let me try and explain this as simply as possible.  You want to find
> scalars u,v such that u*a + v*b = p.  Since these are 3-dimensional
> vectors, you have 3 equations and 2 unknowns:
>
> u*a1 + v*b1 = p1
> u*a2 + v*b2 = p2
> u*a3 + v*b3 = p3
>
> where p1,p2,p3 are the coordinates of the point p, likewise for a1,a2,a3
> and a, and b1,b2,b3 and b.
>
> How do you solve a system of 3 linear equations with 2 unknowns?  If you
> don't know Gaussian elimination, this can be done with some simple
> algebraic rules and substituion.

Okay, this may become very embarrassing for me now... :) How can you solve a
system of 3 linear equations in two unknows, u, v, if they cannot be reduced
to two linear equations (for example, a2 = a3, b2 = b3, and p2 = p3)???

Let's assume that we change the 3 linear equations as follows:

u*a1 + v*b1 + w*c1 = p1
u*a2 + v*b2 + w*c2 = p2
u*a3 + v*b3 + w*c3 = p3

Then there's a unique solution, if

      | a1 b1 c1 |
det | a2 b2 c2 | != 0
      | a3 b3 c3 |

If we set c1 = c2 = c3 = 0, then we have the same system as above (yours),
but with 3 unknowns:

u*a1 + v*b1 + w*0 = p1
u*a2 + v*b2 + w*0 = p2
u*a3 + v*b3 + w*0 = p3

Then
               | a1 b1 0 |
Dn = det | a2 b2 0  | = 0
               | a3 b3 0 |

Since Dn = 0, we get a division by zero, and thus there's an infinite number
of solutions.

... or did I just miss something???

Niki

Re: [Algorithms] decompose onto non-orthogonal vectors

[Peter D. <pd...@mm...>]

> Given a point p and two unit vectors a and b like this:
> 
>       b
>      /
>    v/----p
>    /    /
>   /    /
>  /    /
> ---------a
>     u
> 
> how to you get scalars (u,v) such that u*a + v*b = p?
> Ie. decompose p onto a and b.

Easy. dot the equation with a and b, correspondingly:

u * (a dot a) + v * (b dot a) = p dot a;
v * (a dot b) + v * (b dot b) = p dot b.

Solve the system.

--
Peter Dimov
Multi Media Ltd.

Re: [Algorithms] decompose onto non-orthogonal vectors

[Pierre T. <p.t...@wa...>]

         b
        /
      v/----p
      /    /
     /    /
    /    /
c  ---------a
        u

- Add a point c to form a triangle abc.
- Now you can use the standard raytracing code which computes (u,v) =
ray-triangle impact (texture) coordinates, then check if  0<u<1, 0<v<1 and
0<u+v<1 to keep or discard the impact.

The underlying method is the same as the one already suggested (expressing p
in the abc basis). But in the raytracing field you'll find less formal and
more pragmatic/optimized-to-death answers/code.

/*
Pierre Terdiman       *   Home: p.t...@wa...
Software engineer    *   Zappy's Lair:  www.codercorner.com
*/

----- Original Message -----
From: Discoe, Ben <ben...@in...>
To: <gda...@li...>
Sent: Saturday, July 15, 2000 4:08 AM
Subject: [Algorithms] decompose onto non-orthogonal vectors


>
> I thought it would be a simple problem, but all usual sources failed to
> answer, so perhaps it will be obvious to someone on this list.
>
> Given a point p and two unit vectors a and b like this:
>
>
> how to you get scalars (u,v) such that u*a + v*b = p?
> Ie. decompose p onto a and b.
>
> I promise i consulted an academic, a linear algebra textbook and the WWW
> (all failed) before resorting the list :)
>
> Thanks,
> Ben
> http://vterrain.org/
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list