Welcome, Guest! Log In | Create Account

SourceForge.net > Projects > Game Dev Algorithms > Mail > Archive

Game Dev Algorithms

Email Archive: gdalgorithms-list (read-only)

2000:	_Jan	_Feb	_Mar	_Apr	_May	_Jun	_Jul (390)	_Aug (767)	_Sep (940)	_Oct (964)	_Nov (819)	_Dec (762)
2001:	_Jan (680)	_Feb (1075)	_Mar (954)	_Apr (595)	_May (725)	_Jun (868)	_Jul (678)	_Aug (785)	_Sep (410)	_Oct (395)	_Nov (374)	_Dec (419)
2002:	_Jan (699)	_Feb (501)	_Mar (311)	_Apr (334)	_May (501)	_Jun (507)	_Jul (441)	_Aug (395)	_Sep (540)	_Oct (416)	_Nov (369)	_Dec (373)
2003:	_Jan (514)	_Feb (488)	_Mar (396)	_Apr (624)	_May (590)	_Jun (562)	_Jul (546)	_Aug (463)	_Sep (389)	_Oct (399)	_Nov (333)	_Dec (449)
2004:	_Jan (317)	_Feb (395)	_Mar (136)	_Apr (338)	_May (488)	_Jun (306)	_Jul (266)	_Aug (424)	_Sep (502)	_Oct (170)	_Nov (170)	_Dec (134)
2005:	_Jan (249)	_Feb (109)	_Mar (119)	_Apr (282)	_May (82)	_Jun (113)	_Jul (56)	_Aug (160)	_Sep (89)	_Oct (98)	_Nov (237)	_Dec (297)
2006:	_Jan (151)	_Feb (250)	_Mar (222)	_Apr (147)	_May (266)	_Jun (313)	_Jul (367)	_Aug (135)	_Sep (108)	_Oct (110)	_Nov (220)	_Dec (47)
2007:	_Jan (133)	_Feb (144)	_Mar (247)	_Apr (191)	_May (191)	_Jun (171)	_Jul (160)	_Aug (51)	_Sep (125)	_Oct (115)	_Nov (78)	_Dec (67)
2008:	_Jan (165)	_Feb (37)	_Mar (130)	_Apr (111)	_May (91)	_Jun (142)	_Jul (54)	_Aug (104)	_Sep (89)	_Oct (87)	_Nov (44)	_Dec (54)
2009:	_Jan (283)	_Feb (113)	_Mar (154)	_Apr (395)	_May (62)	_Jun (48)	_Jul (52)	_Aug (54)	_Sep (131)	_Oct (29)	_Nov (32)	_Dec (37)
2010:	_Jan (34)	_Feb (34)	_Mar	_Apr	_May	_Jun	_Jul	_Aug	_Sep	_Oct	_Nov	_Dec


S	M	T	W	T	F	S
						1
						(1)
2	3	4	5	6	7	8
(1)	(18)	(26)	(16)	(51)	(24)	(1)
9	10	11	12	13	14	15
(3)	(9)	(12)	(25)	(6)	(8)	(4)
16	17	18	19	20	21	22
	(6)	(15)	(6)	(5)	(12)	(1)
23	24	25	26	27	28	29
(1)	(3)	(19)	(20)	(12)	(13)	(8)
30
(7)

RE: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Gribb, Gil <ggribb@ra...> - 2003-11-12 14:29

Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Stephen J Baker <sjbaker@li...> - 2003-11-12 15:33

Gribb, Gil wrote:
> There are an infinite number of matrices, or possibly no matrices that will do that. Assuming it is doable, you need to pick one.
>
> Here is what I would do: Discard D and make a new point E.
>
> E = Cross(B-A,C-A) + A

But you need D - the original quadrilateral isn't a rectangle (that would be trivial)
- it's an arbitary (convex/planar/non-degenerate) quad. Any solution that doesn't
include the point D can't be right.

-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

RE: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Gribb, Gil <ggribb@ra...> - 2003-11-12 15:49

Gribb, Gil wrote:
> There are an infinite number of matrices, or possibly no matrices that =
will do that. Assuming it is doable, you need to pick one.
>=20
> Here is what I would do: Discard D and make a new point E.
>=20
> E =3D Cross(B-A,C-A) + A

But you need D - the original quadrilateral isn't a rectangle (that =
would be trivial)=20
- it's an arbitary (convex/planar/non-degenerate) quad. Any solution =
that doesn't
include the point D can't be right.

Well, I assumed:

D - A =3D C - B

So that is an extra degree of freedom we don't need, D =3D A + C - B

If this isn't the case, then a matrix transformation won't work =
anyway....which could very easily explain why you couldn't find a =
solution :)
-Gil

-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

-------------------------------------------------------
This SF.Net email sponsored by: ApacheCon 2003,
16-19 November in Las Vegas. Learn firsthand the latest
developments in Apache, PHP, Perl, XML, Java, MySQL,
WebDAV, and more! http://www.apachecon.com/
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@lists.sourceforge.net /> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188

Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Olivier Galibert <galibert@po...> - 2003-11-12 15:53

On Wed, Nov 12, 2003 at 09:37:01AM -0600, Stephen J Baker wrote:
> But you need D - the original quadrilateral isn't a rectangle (that would
> be trivial) - it's an arbitary (convex/planar/non-degenerate) quad. Any
> solution that doesn't
> include the point D can't be right.

If the original quadrilateral isn't such as AB+AD=AC then there is no
non-degenerate linear transformation that will do what you want. And
a matrix multiply is a linear transformation.

Demonstration is trivial:
A'B'=(1,0); A'C'=(1,1); A'D'=(0,1)
=> A'B'+A'D' = A'C'
=> t(AB)+t(AD) = t(AC) (linear transformation, t(b-a)=t(b)-t(a))
=> t(AB+AD) = t(AC) (same, t(a+b) = t(a)+t(b))
=> AB+AD = AC (non-degenerate)

OG.

Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Stephen J Baker <sjbaker@li...> - 2003-11-12 17:00

Olivier Galibert wrote:
> On Wed, Nov 12, 2003 at 09:37:01AM -0600, Stephen J Baker wrote:
>
>>But you need D - the original quadrilateral isn't a rectangle (that would
>>be trivial) - it's an arbitary (convex/planar/non-degenerate) quad. Any
>>solution that doesn't
>>include the point D can't be right.
>
>
> If the original quadrilateral isn't such as AB+AD=AC then there is no
> non-degenerate linear transformation that will do what you want. And
> a matrix multiply is a linear transformation.

So how does the OpenGL perspective matrix work?

I can draw a trapezium such that AB+AD != AC - then move my camera
around and change it's field of view until the trapezium looks like
a rectangle in screen space. Whatever modelview*projection matrix I
have from that camera position is the one I want to solve my problem.

So I'm tty sure it *can* be done. I just don't cisely understand
how!

-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Charles Bloom <cb@cb...> - 2003-11-12 17:19

At 11:04 AM 11/12/2003 -0600, you wrote:
>So how does the OpenGL perspective matrix work?

Projection is non-linear because there's a divide after the
matrix-multiplies. If you're trying to construct a projection matrix,
that's another matter.

--------------------------------------------------------------------------------------------
Charles Bloom email "cb" http://www.cbloom.com

RE: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Cass Everitt <CEveritt@nv...> - 2003-11-12 17:21

Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: .barr/niji <xbarr@ni...> - 2003-11-12 17:23

On se retrouve qq part si tu veux mais faut que je sache y aller...

On Wed, 12 Nov 2003 09:18:16 -0800, Charles Bloom <cb@cbloom.com> wrote:

>
> At 11:04 AM 11/12/2003 -0600, you wrote:
>> So how does the OpenGL perspective matrix work?
>
> Projection is non-linear because there's a divide after the
> matrix-multiplies. If you're trying to construct a projection matrix,
> that's another matter.
>
>
> --------------------------------------------------------------------------------------------
> Charles Bloom email "cb" http://www.cbloom.com
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>
>
> __________ NOD32 1.549 (20031103) Information __________
>
> This message was checked by NOD32 Antivirus System.
> http://www.nod32.com
>
>

--
.barr/niji
http://xbarr.ninomojo.com

RE: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Cass Everitt <CEveritt@nv...> - 2003-11-12 17:29

It's linear in homogeneous coordinates! :-)

> -----Original Message-----
> From: Charles Bloom [mailto:cb@cbloom.com]
> Sent: Wednesday, November 12, 2003 11:18 AM
> To: gdalgorithms-list@lists.sourceforge.net /> > Subject: Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]
>
>
>
> At 11:04 AM 11/12/2003 -0600, you wrote:
> >So how does the OpenGL perspective matrix work?
>
> Projection is non-linear because there's a divide after the
> matrix-multiplies. If you're trying to construct a
> projection matrix,
> that's another matter.
>
>
> --------------------------------------------------------------
> ------------------------------
> Charles Bloom email "cb" http://www.cbloom.com
>
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL, WebDAV,
> and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>

RE: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Jon Watte <hplus@mi...> - 2003-11-12 17:48

> So how does the OpenGL perspective matrix work?

> a rectangle in screen space. Whatever modelview*projection matrix I
> have from that camera position is the one I want to solve my problem.

Totally different problem. A general quadrilateral is very different
and much more exssive than a quadrilaterla that can be generated by
taking a rectangle in screen space and running it through a modelview/
projection transform.

If you're OK with dealing with the "w" term in 4D, i e not doing the
actual division, then this specific problem is solvable. In fact, you
can just write it out and run the variables through the transform and
out comes your solution.

However, the perspective divide is not a linear operation, so if you
want to involve post-perspective values (such as window coordinates)
then this is, again, not generally solvable using a regular linear
matrix.

If what you're trying to do is draw a full-screen quad, then I'd just
switch to glOrtho() and then back again. If what you're trying to do is
more akin to TexGen, then I'd try doing the texgen in eye space (which
is -divide). Or just do the real math in a vertex or fragment
program.

Cheers,

/ h+

Re: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Stephen J Baker <sjbaker@li...> - 2003-11-12 20:55

Jon Watte wrote:
>>So how does the OpenGL perspective matrix work?
>
>
>>a rectangle in screen space. Whatever modelview*projection matrix I
>>have from that camera position is the one I want to solve my problem.
>
> Totally different problem. A general quadrilateral is very different
> and much more exssive than a quadrilaterla that can be generated by
> taking a rectangle in screen space and running it through a modelview/
> projection transform.

You think so? I'm not sure I believe that. I built a little program
that draws a square - then lets you fly the camera around and alter the
field of view in X and Y - just playing around with it, I couldn't come
up with a convex/planar/non-degenerate quadrilateral that I couldn't
convincingly mimic by dinking around with my little program. That's not
proof of course...

> If you're OK with dealing with the "w" term in 4D, i e not doing the
> actual division, then this specific problem is solvable. In fact, you
> can just write it out and run the variables through the transform and
> out comes your solution.

Right - the result of applying whatever the matrix is to a 3D point will
be a 4D homogeneous point. I understand that I may need to divide by 'w'
if I want a 3D point at the end.

> However, the perspective divide is not a linear operation, so if you
> want to involve post-perspective values (such as window coordinates)
> then this is, again, not generally solvable using a regular linear
> matrix.

Right.

> If what you're trying to do is draw a full-screen quad, then I'd just
> switch to glOrtho() and then back again. If what you're trying to do is
> more akin to TexGen, then I'd try doing the texgen in eye space (which
> is -divide). Or just do the real math in a vertex or fragment
> program.

What I'm trying to do is to figure out how (inside a vertex shader)
to transform the eyepoint into each of several 3D spaces that are distorted
to fit each of several arbitary quadrilaterals. I can compute the matrices
on the CPU.

Trust me - you don't want to know why I need to do this!

-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

RE: [Algorithms] Quadrilateral to 4x4 matrix. [bcc][fake adr]

From: Tyson Jensen <twjensen@sa...> - 2003-11-12 23:53

RE: [Algorithms] Quadrilateral to 4x4 matrix.

From: Peter-Pike Sloan <ppsloan@wi...> - 2003-11-12 15:36

It is much simpler to just reason about this geometrically.

You need a matrix that translates A to the origin (T)

1 0 0 -Ax
0 1 0 -Ay
0 0 1 -Az
0 0 0 1

You need a matrix R that rotates (B-A) so that is along the Y axis and
(D-A) so that is along the X axis - if you want a "correct" determinant
you also want cross((D-A),(B-A)) to be the Z axis (assuming right handed
rotations...)

Since this is a quadrilateral this matrix is (showing row vectors):

(D-A) 0
(B-A) 0
"Z" 0
"0" 1

Where this is assuming we are going to multiply by column vectors on the
right (transpose the matrix otherwise.) The vectors above (after
subtraction) must be normalized (this is a rotation matrix...)

Finaly you need to scale the X/Y axis in this local frame:

Sx 0 0 0
0 Sy 0 0
0 0 1 0
0 0 0 1

Sx =3D 1/Length(D-A)
Sy =3D 1/Length(B-A)

Multiply these 3 matrices:

SRT

Times a point gives you the points position in the desired coordinate
system (with the Z coordinate being signed distance to the plane...)

SRTp

If you are multiplying points from the left (as row vectors) transpose
the above matrix (which is the same as computing TRS with transposed
matrices...)

-Peter-Pike Sloan

-----Original Message-----
From: gdalgorithms-list-admin@lists.sourceforge.net /> [mailto:gdalgorithms-list-admin@lists.sourceforge.net] On Behalf Of Per
Vognsen
Sent: Wednesday, November 12, 2003 7:16 AM
To: gdalgorithms-list@lists.sourceforge.net /> Subject: Re: [Algorithms] Quadrilateral to 4x4 matrix.

Start by translating A to the origin. Since all linear transformations
fix
the
origin and A is in its desired position we should probably consider
those.
Let M be the unknown 3x3 transformation matrix. It has to satisfy the
three vector equations

MB =3D [0,1,0]
MC =3D [1,1,0]
MD =3D [1,0,0]

Each vector equation constitutes three scalar equations and since M has
sixteen independent entries we can thus solve for the entries of M
assuming
that the quadrilateral is nondegenerate, i.e. it doesn't collapse. Just
plug
this
system into a computer algebra package with unknown entries for B, C and
D to get the general exssions. Combining M and the translation into a
4x4
matrix is easy of course.

----- Original Message -----=20
From: "Stephen J Baker" <sjbaker@link.com>
To: <gdalgorithms-list@lists.sourceforge.net>
Sent: Wednesday, November 12, 2003 6:15 AM
Subject: [Algorithms] Quadrilateral to 4x4 matrix.

> I should be able to do this - but it's hurting my brain so it's time
to
beg
> for help!
>
> I have a simple, planar quadrilateral - convex. Let's name it's
points
A,B,C,D.
>
> I want to create a 4x4 matrix that will map those points to:
>
> A =3D (0,0)
> B =3D (0,1)
> C =3D (1,1)
> D =3D (1,0)
>
> ...and I can't seem to get it right.
>
> Help!
>
>
-----------------------------------------------------------------------
> The second law of Frisbee throwing states: "Never cede any maneuver
> by a comment more dictive than "Watch this!"...it turns out that
> this also applies to writing Fragment Shaders.
>
-----------------------------------------------------------------------
> Steve Baker (817)619-2657 (Vox/Vox-Mail)
> L3Com/Link Simulation & Training (817)619-2466 (Fax)
> Work: sjbaker@link.com http://www.link.com
> Home: sjbaker1@airmail.net http://www.sjbaker.org
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188
>

-------------------------------------------------------
This SF.Net email sponsored by: ApacheCon 2003,
16-19 November in Las Vegas. Learn firsthand the latest
developments in Apache, PHP, Perl, XML, Java, MySQL,
WebDAV, and more! http://www.apachecon.com/
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@lists.sourceforge.net /> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188

Re: [Algorithms] Quadrilateral to 4x4 matrix.

From: Stephen J Baker <sjbaker@li...> - 2003-11-12 16:55

Peter-Pike Sloan wrote:
> It is much simpler to just reason about this geometrically.
>
> You need a matrix that translates A to the origin (T)
>
> 1 0 0 -Ax
> 0 1 0 -Ay
> 0 0 1 -Az
> 0 0 0 1
>
> You need a matrix R that rotates (B-A) so that is along the Y axis and
> (D-A) so that is along the X axis - if you want a "correct" determinant
> you also want cross((D-A),(B-A)) to be the Z axis (assuming right handed
> rotations...)
>
> Since this is a quadrilateral this matrix is (showing row vectors):
>
> (D-A) 0
> (B-A) 0
> "Z" 0
> "0" 1
>
> Where this is assuming we are going to multiply by column vectors on the
> right (transpose the matrix otherwise.) The vectors above (after
> subtraction) must be normalized (this is a rotation matrix...)
>
> Finaly you need to scale the X/Y axis in this local frame:
>
> Sx 0 0 0
> 0 Sy 0 0
> 0 0 1 0
> 0 0 0 1
>
> Sx = 1/Length(D-A)
> Sy = 1/Length(B-A)

I don't think this is the correct scale matrix - it has to be something
more like a perspective matrix where the amount of X scale depends on Y
and the amount of Y scale depends on X...but at this point, my brain
shut down again!

> Multiply these 3 matrices:
>
> SRT
>
> Times a point gives you the points position in the desired coordinate
> system (with the Z coordinate being signed distance to the plane...)
>
> SRTp
>
> If you are multiplying points from the left (as row vectors) transpose
> the above matrix (which is the same as computing TRS with transposed
> matrices...)
-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

Re: [Algorithms] Quadrilateral to 4x4 matrix.

From: Charles Bloom <cb@cb...> - 2003-11-12 17:19

As others have said, in general this cannot be done with a linear transform.

With 3 points it's very easy. There's working code in Galaxy3 called

gFrame3Util::MakeBarycentricFrame

This does exactly what you want, Stephen, except that the point D cannot be
mapped to (1,1,0) without applying some non-linear post-transform. The
simplest non-linear transform would start with the linear transform I do,
then just use x*y as its strength factor (post-transform x&y) since A,B, &
C all have a zero for either x or y or both.

--------------------------------------------------------------------------------------------
Charles Bloom email "cb" http://www.cbloom.com

Re: [Algorithms] Quadrilateral to 4x4 matrix.

From: .barr/niji <xbarr@ni...> - 2003-11-12 17:31

My apologies, please disregard my vious mail...
The infamous Opera selection bug.

On Wed, 12 Nov 2003 09:17:11 -0800, Charles Bloom <cb@cbloom.com> wrote:

>
> As others have said, in general this cannot be done with a linear
> transform.
>
> With 3 points it's very easy. There's working code in Galaxy3 called
>
> gFrame3Util::MakeBarycentricFrame
>
> This does exactly what you want, Stephen, except that the point D cannot
> be mapped to (1,1,0) without applying some non-linear post-transform.
> The simplest non-linear transform would start with the linear transform
> I do, then just use x*y as its strength factor (post-transform x&y)
> since A,B, & C all have a zero for either x or y or both.
>
>
> --------------------------------------------------------------------------------------------
> Charles Bloom email "cb" http://www.cbloom.com
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>
>
> __________ NOD32 1.549 (20031103) Information __________
>
> This message was checked by NOD32 Antivirus System.
> http://www.nod32.com
>
>

--
.barr/niji
http://xbarr.ninomojo.com

[Algorithms] Quadrilateral to 4x4 matrix.

From: Stephen J Baker <sjbaker@li...> - 2003-11-12 14:12

I should be able to do this - but it's hurting my brain so it's time to beg
for help!

I have a simple, planar quadrilateral - convex. Let's name it's points A,B,C,D.

I want to create a 4x4 matrix that will map those points to:

A = (0,0)
B = (0,1)
C = (1,1)
D = (1,0)

...and I can't seem to get it right.

Help!

-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

Re: [Algorithms] Quadrilateral to 4x4 matrix.

From: Stephen J Baker <sjbaker@li...> - 2003-11-12 14:41

Stephen J Baker wrote:
> I should be able to do this - but it's hurting my brain so it's time to beg
> for help!
>
> I have a simple, planar quadrilateral - convex. Let's name it's points
> A,B,C,D.
>
> I want to create a 4x4 matrix that will map those points to:
>
> A = (0,0)
> B = (0,1)
> C = (1,1)
> D = (1,0)
>
> ...and I can't seem to get it right.

Oops! I forgot something. I want the results in 3D so that it to maps points
above and below the original quad to points that are the same distance above
and below the Z=0 plane in the result:

So:

A = (0,0,0)
B = (0,1,0)
C = (1,1,0)
D = (1,0,0)

-----------------------------------------------------------------------
The second law of Frisbee throwing states: "Never cede any maneuver
by a comment more dictive than "Watch this!"...it turns out that
this also applies to writing Fragment Shaders.
-----------------------------------------------------------------------
Steve Baker (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sjbaker@link.com http://www.link.com
Home: sjbaker1@airmail.net http://www.sjbaker.org

Re: [Algorithms] Quadrilateral to 4x4 matrix.

From: Per Vognsen <per@ep...> - 2003-11-12 15:15

Start by translating A to the origin. Since all linear transformations fix
the
origin and A is in its desired position we should probably consider those.
Let M be the unknown 3x3 transformation matrix. It has to satisfy the
three vector equations

MB = [0,1,0]
MC = [1,1,0]
MD = [1,0,0]

Each vector equation constitutes three scalar equations and since M has
sixteen independent entries we can thus solve for the entries of M assuming
that the quadrilateral is nondegenerate, i.e. it doesn't collapse. Just plug
this
system into a computer algebra package with unknown entries for B, C and
D to get the general exssions. Combining M and the translation into a 4x4
matrix is easy of course.

----- Original Message -----
From: "Stephen J Baker" <sjbaker@link.com>
To: <gdalgorithms-list@lists.sourceforge.net>
Sent: Wednesday, November 12, 2003 6:15 AM
Subject: [Algorithms] Quadrilateral to 4x4 matrix.

> I should be able to do this - but it's hurting my brain so it's time to
beg
> for help!
>
> I have a simple, planar quadrilateral - convex. Let's name it's points
A,B,C,D.
>
> I want to create a 4x4 matrix that will map those points to:
>
> A = (0,0)
> B = (0,1)
> C = (1,1)
> D = (1,0)
>
> ...and I can't seem to get it right.
>
> Help!
>
> -----------------------------------------------------------------------
> The second law of Frisbee throwing states: "Never cede any maneuver
> by a comment more dictive than "Watch this!"...it turns out that
> this also applies to writing Fragment Shaders.
> -----------------------------------------------------------------------
> Steve Baker (817)619-2657 (Vox/Vox-Mail)
> L3Com/Link Simulation & Training (817)619-2466 (Fax)
> Work: sjbaker@link.com http://www.link.com
> Home: sjbaker1@airmail.net http://www.sjbaker.org
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>

Re[2]: [Algorithms] Archives/Mesh volume

From: Nguyen Binh <ngbinh@gl...> - 2003-11-12 04:18

The doc at MagicSoftware works fine!
It has clear description and easy to follow pseudo code.

>> the same algorithm we used to determine the mass? Using the center of the
>> tetrahedrons and their mass to add a contribution to the resulting vector,
>> then dividing by the total mass... shouldn't that yield the center of
>> gravity? Then, another pass at the model should enable us to get the
JW> inertia
>> tensor... or not?

--
Best regards,

---------------------------------------------------------------------
Nguyen Binh
Software Engineer
Glass Egg Digital Media

E.Town Building
7th Floor, 364 CongHoa Street
Tan Binh District,
HoChiMinh City,
VietNam,

Phone : +84 8 8109018
Fax : +84 8 8109013

www.glassegg.com
---------------------------------------------------------------------

Re: [Algorithms] Archives/Mesh volume

From: Chris Green <chrisg@lp...> - 2003-11-12 09:25

If it was to be an offline thing and I wanted to code it quickly, I'd
probably just do something like
have a routine to determine if a point is inside the mesh, and then
sample the space in a regular grid,
counting each point found to inside the grid as a small volume.

Jonathan Blow wrote:

>I would probably BSP the mesh, which gives you a bunch of convex chunks
>resenting the inside; then add up the volumes of those chunks (which I think
>you can do by carving simplices off one at a time and adding their volumes).
>
>Doing robust BSP (in the face of mesh cracks etc) is sometimes an interesting
>problem, but you would have similar (perhaps worse) problems with something
>like robust marching cubes...
>
>----- Original Message -----
>From: "Diogo de Andrade" <Diogo.Andrade@spellcasterstudios.com>
>To: <gdalgorithms-list@lists.sourceforge.net>
>Sent: Tuesday, November 11, 2003 10:52 AM
>Subject: [Algorithms] Archives/Mesh volume
>
>
>
>
>>Does anyone have any problems accessing the archives of this mailing list?
>>
>>I was trying to search for algorithms of calculating the volume of a mesh,
>>and I couldn't get no hits even searching for simple things like "mesh"...
>>Is it just me?
>>
>>BTW, does anyone have any resources about calculating the volume of a mesh?
>>I want to try to calculate the mass, inertia tensors, and other physical
>>properties like that, but the only idea I have is to use a
>>voxel/marching-something approach, but I think that approach is very
>>programming-intensive and I was wondering if there is a better way... If
>>anyone has any pointers, I would apciate it...
>>
>>Thanks in advance
>>
>>Diogo de Andrade
>>www.spellcasterstudios.com/~diogo.andrade
>>diogo.andrade@spellcasterstudios.com /> >>
>>"Never trust something that bleeds for five days and doesn't die..."
>> Robert A. Heinlein
>>
>>"People say I'm evil, but I have the heart of a little boy... in a jar... on
>>my desk..."
>>
>>
>>
>>
>>-------------------------------------------------------
>>This SF.Net email sponsored by: ApacheCon 2003,
>>16-19 November in Las Vegas. Learn firsthand the latest
>>developments in Apache, PHP, Perl, XML, Java, MySQL,
>>WebDAV, and more! http://www.apachecon.com/
>>_______________________________________________
>>GDAlgorithms-list mailing list
>>GDAlgorithms-list@lists.sourceforge.net /> >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>Archives:
>>http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>>
>>
>
>
>-------------------------------------------------------
>This SF.Net email sponsored by: ApacheCon 2003,
>16-19 November in Las Vegas. Learn firsthand the latest
>developments in Apache, PHP, Perl, XML, Java, MySQL,
>WebDAV, and more! http://www.apachecon.com/
>_______________________________________________
>GDAlgorithms-list mailing list
>GDAlgorithms-list@lists.sourceforge.net /> >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>Archives:
>http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>
>
>

RE: [Algorithms] Animation Technology [was: Jon Blow ranting ;^>]

From: Ben Hinchliffe <SirBuftonTufton@ya...> - 2003-11-12 11:19

There's an interesting demo of "Procedural Character Animation" available at
http://www.reality-1.com/projects_pca.html which was done by a flatmate of
mine for his final year project at uni, which uses keyframed animations as a
base layer, then modifies these in real-time with a 'body language' layer,
then constrains it all using an IK layer. It's cool. :)

Benny H

> -----Original Message-----
> From: gdalgorithms-list-admin@lists.sourceforge.net /> > [mailto:gdalgorithms-list-admin@lists.sourceforge.net]On Behalf Of Alex
> Mohr
> Sent: 09 November 2003 23:37
> To: gdalgorithms-list@lists.sourceforge.net /> > Subject: Re: [Algorithms] Animation Technology [was: Jon Blow ranting
> ;^>]
>
>
> Check out all the great stuff at Wisconsin for real-time animation
> research:
>
> Motion graphs can easily do the "draw a line, find the motion that
> follows it" and lots of other stuff. Unfortunately, it's not suited to
> real-time apps:
>
> http://www.cs.wisc.edu/graphics/Gallery/Kovar/MoGraphs/
>
>
> On the other hand, Snap-Together motion lets you build move trees
> (including doing the blends) almost entirely automatically:
>
> http://www.cs.wisc.edu/graphics/Gallery/Kovar/SnapTogetherMotion/
>
>
> Here's some high quality dynamic timewarping stuff (practical
> algorithms);
>
> http://www.cs.wisc.edu/graphics/Gallery/Kovar/RegistrationCurves/
>
>
> And a simple-to-implement, fast, robust, analytic IK algorithm for
> cleaning up footskate:
>
> http://www.cs.wisc.edu/graphics/Gallery/Kovar/Cleanup/
>
>
> Alex
>
>
>
>
> >Yeah, University of Washington has some cool stuff in this area.
> >
> >One of the guys (Jai-Chi Wu) who worked with us this summer is doing an
> >extremely-physically-based flight model for birds that's capable of some
> >startling realism at great computational expense.
> >
> >My current favorite is a project at UW wherein you draw a line through
> >an arbitrary environment and avatar pieces together animation samples to
> >navigate through the environment intelligently. This is not of course a
> >"twitch" interface, but it's suggestive of some new interaction
> >paradigms that would give the AI more room to make the character seem
> >less like a puppet on bungie cords and more like an autonomous creature.
> >Perhaps a "Real-Time-Tactical" -- command and conquer for
> >
> >Lookie: http://grail.cs.washington.edu/projects/
> >
> >Georgia tech did some of the first interesting stuff I've seen for
> >"truly" adapting animations between skeletons. Haven't checked it out in
> >a while, tho.
> >
> >-----Original Message-----
> >From: gdalgorithms-list-admin@lists.sourceforge.net /> > >[mailto:gdalgorithms-list-admin@lists.sourceforge.net] On Behalf Of
> >Charles Bloom
> >Sent: Friday, November 07, 2003 10:22 AM
> >To: gdalgorithms-list@lists.sourceforge.net /> > >Subject: [Algorithms] Animation Technology [was: Jon Blow ranting ;^>]
> >
> >
> >Animation technology is certainly one of the areas where we can make
> >leaps
> >and bounds in the next few years.
> >
> >A cool old demo is here :
> >
> >http://www.frontier.co.uk/download/demonstrator.zip
> >
> >And I have an old note on simple distorted blends for event-synching in
> >animation blending :
> >
> >http://www.cbloom.com/3d/rambles.html
> >
> >But the things I see coming on are :
> >
> >1. Combining animations with forward kinematics : ala Dave Wu's talk at
> >GDC ;
> >
> >2. Combining #1 with inverse kinematics : for locking feet to the ground
> >
> >and such
> >
> >3. Adapting animations for different skeletons and musculatures; eg. you
> >
> >just animate for a basic biped, and the system can automatically make a
> >good animation for skeletons that are slightly different. Note that I'm
> >
> >not just talking about copying the animation to the skeleton, I'm
> >talking
> >about *changing* it to account for the increased weight, different
> >musculature, whatever.
> >
> >4. Impulse and muscle-driven move selection in an AI sort of way. Like,
> >
> >I'm running straight and I know I want to take a 90 degree turn and run
> >to
> >my left; so I know I need to apply like a 45 degree impulse; well, scan
> >through my possible moves and see what can do that for me, the best fit
> >is
> >a hard-plant with the right leg, now choose a time to do that move that
> >matches what my legs are already doing, eg. when my right leg is in sort
> >of
> >a planting-pose anyway, and then turn on the new anim at an appropriate
> >time too; Dave Wu talks about some of this kind of stuff.
> >
> >A fundamental problem remains with latency, however. In order to do
> >great
> >animation, you need diction, eg. you need to know what that avatar
> >will
> >be doing in a few seconds, or what they want to do next. This is
> >possible
> >with AI guys, but not possible with the player character unless you
> >introduce huge latency.
> >
> >
> >------------------------------------------------------------------------
> >--------------------
> >Charles Bloom email "cb" http://www.cbloom.com
> >
> >
> >
> >
> >-------------------------------------------------------
> >This SF.Net email sponsored by: ApacheCon 2003,
> >16-19 November in Las Vegas. Learn firsthand the latest
> >developments in Apache, PHP, Perl, XML, Java, MySQL,
> >WebDAV, and more! http://www.apachecon.com/
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDAlgorithms-list@lists.sourceforge.net /> > >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >Archives:
> >http://sourceforge.net/mailarchive/forum.php?forum_id=6188
> >
> >
> >-------------------------------------------------------
> >This SF.Net email sponsored by: ApacheCon 2003,
> >16-19 November in Las Vegas. Learn firsthand the latest
> >developments in Apache, PHP, Perl, XML, Java, MySQL,
> >WebDAV, and more! http://www.apachecon.com/
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDAlgorithms-list@lists.sourceforge.net /> > >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >Archives:
> >http://sourceforge.net/mailarchive/forum.php?forum_ida88
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>

Re: [Algorithms] Animation Technology [was: Jon Blow ranting ;^>]

From: suoch <suoch@gm...> - 2003-11-12 11:54

Ben Hinchliffe wrote:

> There's an interesting demo of "Procedural Character Animation" available at
> http://www.reality-1.com/projects_pca.html which was done by a flatmate of
> mine for his final year project at uni, which uses keyframed animations as a
> base layer, then modifies these in real-time with a 'body language' layer,
> then constrains it all using an IK layer. It's cool. :)
>
> Benny H

awesome demo. i tried to accomplish somethin similar for
a project at university but didn't get this far.
some technical background of this project would be interesting.
any papers, source?

Dietmar Suoch

RE: [Algorithms] Animation Technology [was: Jon Blow ranting ;^>]

From: Ben Hinchliffe <SirBuftonTufton@ya...> - 2003-11-12 13:37

I just asked him and he said he'll try to sort something out soon (hopefully
by the weekend) so check his website again in a few days. :)

Benny H

> -----Original Message-----
> From: gdalgorithms-list-admin@lists.sourceforge.net /> > [mailto:gdalgorithms-list-admin@lists.sourceforge.net]On Behalf Of suoch
> Sent: 12 November 2003 11:51
> To: gdalgorithms-list@lists.sourceforge.net /> > Subject: Re: [Algorithms] Animation Technology [was: Jon Blow ranting
> ;^>]
>
> awesome demo. i tried to accomplish somethin similar for
> a project at university but didn't get this far.
> some technical background of this project would be interesting.
> any papers, source?
>
> Dietmar Suoch
>
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>

RE: [Algorithms] Archives/Mesh volume

From: Bob Dowland <Bob.Dowland@bl...> - 2003-11-12 10:03

> have a routine to determine if a point is inside the mesh,

hmm... perhaps you could even knock a dimension off the order of =
complexity here by using some form of scanline/raypicker approach (ie =
interesection-test points on the surface rather than points in the =
volume).

> counting each point found to be inside the grid as a small volume.

the inertia tensor integral/sum then becomes a one-liner

:)

> -----Original Message-----
> From: Chris Green [mailto:chrisg@lplizard.com] /> > Sent: 11 November 2003 18:13
> To: gdalgorithms-list@lists.sourceforge.net /> > Subject: Re: [Algorithms] Archives/Mesh volume
>=20
>=20
> If it was to be an offline thing and I wanted to code it quickly, I'd=20
> probably just do something like
> sample the space in a regular grid,
> counting each point found to inside the grid as a small volume.
>=20
>=20
>=20
>=20
> Jonathan Blow wrote:
>=20
> >I would probably BSP the mesh, which gives you a bunch of=20
> convex chunks
> >resenting the inside; then add up the volumes of those=20
> chunks (which I think
> >you can do by carving simplices off one at a time and adding=20
> their volumes).
> >
> >Doing robust BSP (in the face of mesh cracks etc) is=20
> sometimes an interesting
> >problem, but you would have similar (perhaps worse) problems=20
> with something=20
> >like robust marching cubes...
> >
> >----- Original Message -----=20
> >From: "Diogo de Andrade" <Diogo.Andrade@spellcasterstudios.com>
> >To: <gdalgorithms-list@lists.sourceforge.net>
> >Sent: Tuesday, November 11, 2003 10:52 AM
> >Subject: [Algorithms] Archives/Mesh volume
> >
> >
> > =20
> >
> >>Does anyone have any problems accessing the archives of=20
> this mailing list?
> >>
> >>I was trying to search for algorithms of calculating the=20
> volume of a mesh,
> >>and I couldn't get no hits even searching for simple things=20
> like "mesh"...
> >>Is it just me?
> >>
> >>BTW, does anyone have any resources about calculating the=20
> volume of a mesh?
> >>I want to try to calculate the mass, inertia tensors, and=20
> other physical
> >>properties like that, but the only idea I have is to use a
> >>voxel/marching-something approach, but I think that approach is very
> >>programming-intensive and I was wondering if there is a=20
> better way... If
> >>anyone has any pointers, I would apciate it...
> >>
> >>Thanks in advance
> >>
> >>Diogo de Andrade
> >>www.spellcasterstudios.com/~diogo.andrade
> >>diogo.andrade@spellcasterstudios.com /> > >>
> >>"Never trust something that bleeds for five days and doesn't die..."
> >> =20
> Robert A. Heinlein
> >>
> >>"People say I'm evil, but I have the heart of a little=20
> boy... in a jar... on
> >>my desk..."
> >>
> >>
> >>
> >>
> >>-------------------------------------------------------
> >>This SF.Net email sponsored by: ApacheCon 2003,
> >>16-19 November in Las Vegas. Learn firsthand the latest
> >>developments in Apache, PHP, Perl, XML, Java, MySQL,
> >>WebDAV, and more! http://www.apachecon.com/
> >>_______________________________________________
> >>GDAlgorithms-list mailing list
> >>GDAlgorithms-list@lists.sourceforge.net /> > >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >>Archives:
> >>http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188
> >> =20
> >>
> >
> >
> >-------------------------------------------------------
> >This SF.Net email sponsored by: ApacheCon 2003,
> >16-19 November in Las Vegas. Learn firsthand the latest
> >developments in Apache, PHP, Perl, XML, Java, MySQL,
> >WebDAV, and more! http://www.apachecon.com/
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDAlgorithms-list@lists.sourceforge.net /> > >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >Archives:
> >http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188
> >
> > =20
> >
>=20
>=20
>=20
>=20
> -------------------------------------------------------
> This SF.Net email sponsored by: ApacheCon 2003,
> 16-19 November in Las Vegas. Learn firsthand the latest
> developments in Apache, PHP, Perl, XML, Java, MySQL,
> WebDAV, and more! http://www.apachecon.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@lists.sourceforge.net /> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188
>=20

**********************************************************************
The information contained in this email and its attachments is
confidential. It is intended only for the named addressees=20
and may not be disclosed to anyone else without consent from
Blue 52 Limited. Blue 52 gives no warranty that this email=20
message (including any attachments to it) is free of any virus=20
or other harmful matter and accepts no responsibility for any=20
loss or damage resulting from the recipient receiving, opening
or using it.=20
**********************************************************************

Game Dev Algorithms

Email Archive: gdalgorithms-list (read-only)

About SourceForge

Find Software

Develop Software

Community

Help