You can subscribe to this list here.
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}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

S  M  T  W  T  F  S 






1
(28) 
2
(15) 
3
(4) 
4
(22) 
5
(22) 
6
(24) 
7
(4) 
8
(7) 
9
(6) 
10
(13) 
11
(4) 
12
(22) 
13
(55) 
14
(30) 
15
(24) 
16
(1) 
17
(2) 
18
(11) 
19
(28) 
20
(14) 
21
(18) 
22
(15) 
23
(7) 
24

25
(30) 
26
(26) 
27
(43) 
28
(26) 


From: Charles Bloom <cbloom@cb...>  20020206 23:27:52

FYI I just implemented Dean's technique. It looks fantastic. The performance is about what you'd expect from an expensive pixel shader. It takes about 1.25 millis to fill the screen with this shader on my XBox. My only concern is that 3 texture sources isn't very powerful. You can add 3 more with another pass; just make an another mask for the next 3 textures and also store an alpha value for blending them onto the previous 3 textures. You wind up with 6 texture sources and 2 masks running in 2 passes; I'd guesstimate it would use about 3 millis to fill the screen. At 10:37 AM 1/18/2002 +0000, Dean Calver wrote: >It do a similar thing but use the alpha channels (packed into 1 texture) as >the interpolation value in lerp's. So 3 textures, 2 alphas (packed in alpha >and blue).  Charles Bloom cbloom@... http://www.cbloom.com 
From: Tom Hubina <tomh@3d...>  20020206 22:36:50

I've updated the link at the bottom of our lists to the archive pages for each of the lists. The new stuff from SourceForge (instead of Geocrawler) is much nicer. Tom 
From: Tom Hubina <tomh@3d...>  20020206 22:15:48

At 07:50 AM 2/6/2002, John Connors wrote: >Is there an generic algorithm for generating the vertices of an nsided >platonic solid? There are 5 platonic solids, each with a fixed number of sides. Assuming you want to make those, and not an nsided polyhedron, you can check here: http://www.vbhelper.com/tut7.htm There are probably other places as well, but that was what I found from a quick web search. Tom 
From: <sammy@dn...>  20020206 22:06:51

I recently implemented the algorithm found here for performing swept AABB intersection tests: http://www.gamasutra.com/fe= atures/19991018/Gomez_3.htm The implementation on the website contains some errors and will not work as is. I believe I have fixed these errors (the= code seems to be working fine now). My revised implementation is below. Note that I haven't tested this particular imp= lementation, but this is based off the code I have written in my own engine (which uses different structs and is in plain= C), so it should work.  //Intersection test of two swept AABBs by Miguel Gomez (http://www.gamasutra.com/features/19991018/Gomez_3.htm) //with corrections by Sam McGrath (sammy@..., http://www.s2games.com) #include "aabb.h" //Sweep two AABB's to see if and when they first //and last were overlapping const bool AABBSweep ( const VECTOR& Ea, //extents of AABB A const VECTOR& A0, //its previous position const VECTOR& A1, //its current position const VECTOR& Eb, //extents of AABB B const VECTOR& B0, //its previous position const VECTOR& B1, //its current position SCALAR& u0, //normalized time of first collision SCALAR& u1 //normalized time of second collision ) { const AABB A( A0, Ea );//previous state of AABB A const AABB B( B0, Eb );//previous state of AABB B const VECTOR va =3D A1  A0;//displacement of A const VECTOR vb =3D B1  B0;//displacement of B //the problem is solved in A's frame of reference VECTOR v =3D vb  va; //relative velocity (in normalized time) VECTOR u_0(0,0,0); //first times of overlap along each axis VECTOR u_1(1,1,1); //last times of overlap along each axis //check if they were overlapping // on the previous frame if( A.overlaps(B) ) { u0 =3D u1 =3D 0; return true; } if (v[0] =3D=3D 0 && v[1] =3D=3D 0 && v[2] =3D=3D 0) { //velocity is zero and we already tested the bounds SAM return false; } bool cont; //we need this for the following axis tests SAM //find the possible first and last times //of overlap along each axis for( long i=3D0 ; i<3 ; i++ ) { cont =3D false; if( A.max(i)<B.min(i) && v[i]<=3D0 ) { if (v[i] < 0) u_0[i] =3D (A.max(i)  B.min(i)) / v[i]; cont =3D true; } else if( B.max(i)<A.min(i) && v[i]>=3D0 ) { if (v[i] > 0) u_0[i] =3D (A.min(i)  B.max(i)) / v[i]; cont =3D true; } if( B.max(i)>A.min(i) && v[i]<=3D0 ) { if (v[i] < 0) u_1[i] =3D (A.min(i)  B.max(i)) / v[i]; cont =3D true; } else if( A.max(i)>B.min(i) && v[i]>=3D0 ) { if (v[i] > 0) u_1[i] =3D (A.max(i)  B.min(i)) / v[i]; cont =3D true; } if (!cont) return false; //none of the tests passed for this axis, boxes don't intersect SAM } //possible first time of overlap u0 =3D MAX( u_0.x, MAX(u_0.y, u_0.z) ); //possible last time of overlap u1 =3D MIN( u_1.x, MIN(u_1.y, u_1.z) ); //they could have only collided if //the first time of overlap occurred //before the last time of overlap return u0 <=3D u1; }  mail2web  Check your email from the web at http://mail2web.com/ . 
From: Peter Warden <pwarden@ku...>  20020206 21:26:21

Since we're discussing speeding up matrix inversions: In cases where you have 'simple' orthogonal 3x3 matrices containing only rotations and no scaling or skewing, the inverse is just the transpose of the original matrix. One thing I have found occasionally useful in the past is extending this to simple 4x4 matrices containing just a rotation and a translation by transposing the 3x3 rotation part of the matrix as before. Then feed the original translation through this transpose and multiply it by 1 to get the inverted translation. (IIRC? I don't have the code in front of me) Of course you should only use this if your profiler is telling you that doing the inverse properly is a performance problem _and_ you're sure that the matrices you're dealing with are orthogonal. There may be other problems with this approach, YMMV, etc, but it did the job for me at the time. Pete Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Idahosa Edokpayi Sent: Wednesday, February 06, 2002 9:39 AM To: Algorithms List Subject: RE: [Algorithms] matrix inverse I wanted it for an explicit inverse. I actually only use the inverse for the camera so yes that is what I wanted. Idahosa Edokpayi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Willmott, Andrew Sent: Tuesday, February 05, 2002 9:46 PM To: Algorithms List Subject: RE: [Algorithms] matrix inverse > Well, I have contraditory results from Intel: > > http://developer.intel.com/design/pentiumiii/sml/24504301.pdf > > Cramer's rule seems pretty efficient even with a 4x4. When coupled > with SIMD, it totally rocks! Note that these results aren't inconsistent: Graham's link is measuring Cramer's rule against Gaussian elimination for solving Ax = b, whereas the Intel guys are measuring it against computing the entire inverse iteratively. It's not surprising elimination does better for the first case. FWIW I use cramer's rule for 3x3 and 4x4 matrix inversion and swap to iterative methods thereafter. As everyone else has said, you should be using elimination to solve most Ax = b cases, but having to have an explicit inverse does crop up a fair bit in camera calculations, enough to care about having a fast explicit inverse. Cheers, Andrew _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: Graham Rhodes <grhodes@se...>  20020206 20:19:45

To compute the entire inverse of a 4x4 matrix using Gaussian Elimination requires (very roughly) twice as many multiply/divide and add/subtract operations when compared to just solving a system of equations once (with one righthandside). Depending on how the determinants are calculated using Cramer's rule, an efficient implementation of Cramer's rule can require less operations for a 4x4 matrix. I think the subtle difference between the Rice University book and the Intel study is that Rice University (and pure math analysis of numerical method costs in general) assumed all math operations require equal CPU time (one trillionth of a second for a multiply, divide, add, subtract, whatever), while the Intel study was looking at processor cycles. When it comes down to it, if you're really looking for speed, processor cycles are more important. And so Sebastien's post was certainly appropriate! Graham > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of > Willmott, Andrew > Sent: Tuesday, February 05, 2002 10:46 PM > To: Algorithms List > Subject: RE: [Algorithms] matrix inverse > > > > Well, I have contraditory results from Intel: > > > > http://developer.intel.com/design/pentiumiii/sml/24504301.pdf > > > > Cramer's rule seems pretty efficient even with a 4x4. When > > coupled with > > SIMD, it totally rocks! > > Note that these results aren't inconsistent: Graham's link is measuring > Cramer's rule against Gaussian elimination for solving Ax = b, whereas the > Intel guys are measuring it against computing the entire inverse > iteratively. It's not surprising elimination does better for the > first case. > > FWIW I use cramer's rule for 3x3 and 4x4 matrix inversion and swap to > iterative methods thereafter. As everyone else has said, you > should be using > elimination to solve most Ax = b cases, but having to have an explicit > inverse does crop up a fair bit in camera calculations, enough to > care about > having a fast explicit inverse. > > Cheers, > > Andrew > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Duncan Hewat <duncanhewat@ho...>  20020206 20:02:38

Does anyone have any code lying around to do fast swept sphere AABB intersection? Preferably one that gives me a parameter 't' (0 <= t <= 1) for the swept sphere as well as a yes/no answer. Thanks, Duncan. _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp. 
From: Leaf Garland <leaf@ta...>  20020206 19:58:06

You can search the archive at sourceforge, with the soon to be replacement for geocrawler. http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > I think it was Tom Forsyth who mentioned this originally, but > using Google to search the archive works very well (better > than the geocrawler search, IMO). > > Just use the following search criteria: > > site:geocrawler.com GDAlgorithms > > and then append your search terms to the end of that. > (e.g. site:geocrawler.com GDAlgorithms quaternion camera) 
From: Idahosa Edokpayi <idahosae@sw...>  20020206 17:40:14

I wanted it for an explicit inverse. I actually only use the inverse for the camera so yes that is what I wanted. Idahosa Edokpayi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Willmott, Andrew Sent: Tuesday, February 05, 2002 9:46 PM To: Algorithms List Subject: RE: [Algorithms] matrix inverse > Well, I have contraditory results from Intel: > > http://developer.intel.com/design/pentiumiii/sml/24504301.pdf > > Cramer's rule seems pretty efficient even with a 4x4. When > coupled with > SIMD, it totally rocks! Note that these results aren't inconsistent: Graham's link is measuring Cramer's rule against Gaussian elimination for solving Ax = b, whereas the Intel guys are measuring it against computing the entire inverse iteratively. It's not surprising elimination does better for the first case. FWIW I use cramer's rule for 3x3 and 4x4 matrix inversion and swap to iterative methods thereafter. As everyone else has said, you should be using elimination to solve most Ax = b cases, but having to have an explicit inverse does crop up a fair bit in camera calculations, enough to care about having a fast explicit inverse. Cheers, Andrew _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: Dave Hill <dhatdgp@ya...>  20020206 16:15:27

I think it was Tom Forsyth who mentioned this originally, but using Google to search the archive works very well (better than the geocrawler search, IMO). Just use the following search criteria: site:geocrawler.com GDAlgorithms and then append your search terms to the end of that. (e.g. site:geocrawler.com GDAlgorithms quaternion camera) HTH, dh ________________________ Dave Hill http://www.dgp.toronto.edu/~dh > At 07:35 2/6/02 +0100, Stefan Maton wrote: > >Hi, > > > >I wondered how to search the archive of this > >mailing list. I've tried to find a search > >function on the webpages pointed to by the > >withcoming link (see bottom/end of mail) but > >all I can do is swap through the pages of > >headlines of mails. _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com 
From: John Connors <jconnors@re...>  20020206 15:57:06

Is there an generic algorithm for generating the vertices of an nsided platonic solid?  John Connors  Animation Programmer  ICQ # 94052423  http://www.yagc.demon.co.uk Virus scanned and cleared ok 
From: Thatcher Ulrich <tu@tu...>  20020206 14:57:56

On Feb 06, 2002 at 02:02 0600, David Clyde wrote: > Im also new here but Looking at the original link to the code Mark Found > > 1458/*FCN*/gdImageRoundRectangle(gdImagePtr im, > 1469 int x1, int y1, int x2, int y2, > 1470 int oval_w, int oval_h, > 1471 int color, Nlm_Boolean fill) > 1472 { > 1473 int X1 = MIN(x1, x2); > 1474 int Y1 = MIN(y1, y2); > 1475 int X2 = MAX(x1, x2); > 1476 int Y2 = MAX(y1, y2); > 1477 > 1478 int w = x2  x1 + 1; > 1479 int h = y2  y1 + 1; > 1480 > 1481 if (oval_w > w/2) > 1482 oval_w = w/2; // this here is division by 2 > of an int > 1483 if (oval_h > h/2) > 1484 oval_h = h/2; // so is htis > > would not w/2 when odd result in a loss of data ex 3/2 = 1 because were > dealing with integer division? Yes. > was it planned for this algorithm to lose some info when doing int division > on odd numbers? I'm guessing yes, because I bet this routine draws the oval in symmetrical quadrants. One way to fix it: detect the odd case and separate the quadrants by one pixel (and fill in the onepixel gaps explicitly).  Thatcher Ulrich <tu@...> http://tulrich.com 
From: Tom Forsyth <tomf@mu...>  20020206 11:38:53

> you take a high polycount model (100.000 and up), > and create a low polycount model on which normal > maps are applied to do some kind of bump mapping (?). Correct. you do normalmap bumpmapping, also known as DotProduct3 bumpmapping. there are many tutorials on Dot3 bumpmapping all over the place  nvidia's site, ATI's site, the DirectX site, etc. As for generating the model and bumpmap  well, you can either just draw the bumpmap by hand (probably the easiest method), or you can generate it from a highpoly mesh. A good reference for this is something like "Texture mapping progressive meshes"  P. Sander, J. Snyder, S. Gortler, H. Hoppe (available at http://www.research.microsoft.com/~hoppe/)  but it can be quite daunting reducing a highpoly mesh down to a simpler one. Tom Forsyth  Muckyfoot bloke. What's he up to now (and can I have a go)? http://www.eidosinteractive.com/downloads/search.html?gmid=86 > Original Message > From: Stefan Maton [mailto:metron@...] > Sent: 06 February 2002 06:36 > To: Algorithms > Subject: [Algorithms] Search on list plus question on normal maps > > > Hi, > > I wondered how to search the archive of this > mailing list. I've tried to find a search > function on the webpages pointed to by the > withcoming link (see bottom/end of mail) but > all I can do is swap through the pages of > headlines of mails. > > If anyone could give an advice on this. > > I wanted to use the search because I've > somewhere in my mind the slight idea that > the following question has been answered here : > > How are normal maps used to give the gamer the > impression to have more polygons in front of > him than he actually has ? In my understanding > you take a high polycount model (100.000 and up), > and create a low polycount model on which normal > maps are applied to do some kind of bump mapping (?). > > Kind regards, > Stefan Maton >  > Programmer Resources Site > http://www.sunamoon.org >  > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Chris Hecker <checker@d6...>  20020206 08:25:47

Can the moderators change the blurb at the bottom to include this link until the overall archive situation is fixed? I assume the blurb is editable... Courtesy of Paul Crowder. You can construct your own search thus: http://www.geocrawler.com/search/?config=4856&words=quaternion and replace quaternion with the words of your choice. Add extra words with +word: words=quaternion+interpolation. At 07:35 2/6/02 +0100, Stefan Maton wrote: >Hi, > >I wondered how to search the archive of this >mailing list. I've tried to find a search >function on the webpages pointed to by the >withcoming link (see bottom/end of mail) but >all I can do is swap through the pages of >headlines of mails. > >If anyone could give an advice on this. > >I wanted to use the search because I've >somewhere in my mind the slight idea that >the following question has been answered here : > >How are normal maps used to give the gamer the >impression to have more polygons in front of >him than he actually has ? In my understanding >you take a high polycount model (100.000 and up), >and create a low polycount model on which normal >maps are applied to do some kind of bump mapping (?). > >Kind regards, >Stefan Maton > >Programmer Resources Site >http://www.sunamoon.org > > > >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: David Clyde <dclyde@am...>  20020206 08:04:24

Im also new here but Looking at the original link to the code Mark Found 1458/*FCN*/gdImageRoundRectangle(gdImagePtr im, 1469 int x1, int y1, int x2, int y2, 1470 int oval_w, int oval_h, 1471 int color, Nlm_Boolean fill) 1472 { 1473 int X1 = MIN(x1, x2); 1474 int Y1 = MIN(y1, y2); 1475 int X2 = MAX(x1, x2); 1476 int Y2 = MAX(y1, y2); 1477 1478 int w = x2  x1 + 1; 1479 int h = y2  y1 + 1; 1480 1481 if (oval_w > w/2) 1482 oval_w = w/2; // this here is division by 2 of an int 1483 if (oval_h > h/2) 1484 oval_h = h/2; // so is htis would not w/2 when odd result in a loss of data ex 3/2 = 1 because were dealing with integer division? was it planned for this algorithm to lose some info when doing int division on odd numbers? It deffinately results in a loss of 1. Although I dont know which part exactly of the algorithms mark is using, this is just a part I found odd. I would have thought to do all comparing as (oval_w*2 > w) then later when about to actual use oval_w use (oval_w / 2.0) Like I said maybe it was intended to lose 1 on odds and im just missing it 
From: Stefan Maton <metron@sk...>  20020206 06:33:15

Hi, I wondered how to search the archive of this mailing list. I've tried to find a search function on the webpages pointed to by the withcoming link (see bottom/end of mail) but all I can do is swap through the pages of headlines of mails. If anyone could give an advice on this. I wanted to use the search because I've somewhere in my mind the slight idea that the following question has been answered here : How are normal maps used to give the gamer the impression to have more polygons in front of him than he actually has ? In my understanding you take a high polycount model (100.000 and up), and create a low polycount model on which normal maps are applied to do some kind of bump mapping (?). Kind regards, Stefan Maton  Programmer Resources Site http://www.sunamoon.org  
From: Alex Lindsay <alindsay@au...>  20020206 05:21:26

The algorithms you're trying aren't relying on the rounding or carry behaviour of the x86 PC that doesn't port to the Mac? i.e. round down vs round to nearest. Does it work on a PC? :) Alex > Original Message > From: Mark Speir [mailto:maspeir@...] > Sent: Wednesday, 6 February 2002 4:00 PM > To: GDAlgorithms > Subject: Re: [Algorithms] New here. Need help, might be slightly off > topic... > > > > How about ... > > > > if(iWidth % 2) > > iWidth++; > > > > seems like it would solve the problem ... > > I wish it were that simple. Regardless of what I set the x or > y radius to, > it only draws ovals with odd radii. In other words, if I set > the radius to > (100,200), I actually get an oval with a radius of (99,199). > Increasing the > radii by one wont solve the problem. The bug is somewhere in > the algorithm. > > This bug seems to be in all of the Bresenham ellipse and > circle algorithms > that I have found online. I find it real odd that no one has > ever tried to > fix it or even mention that there is a problem. Am I just a > spoiled Mac > programmer or is the accepted quality for PC graphics > software really that > low? No offence intended, but for many years, PC programmers relied on > graphics libraries for primative drawing. If this is what > they had, why was > there never an effort to fix it and then post the correction? > > I know that there is a way to do it right. Just look at QuickDraw's > FrameOval and whatever the simular function is called in > Windows. They work > correctly, so someone knows how to do it right. Like I said > in a previous > email, It's a tightly guarded secret of the software companies... > > Sorry if I seem a bit annoyed. I am, but at no one person. > It's just that I > have been trying to find this "simple" algorithm for several > years off and > on for various reasons. This time I am not going to rest > until I find it (I > can see myself at 90, curled up in a rocking chair cursing > Jack Bresenham's > name... LOL). > > Mark > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Jon Watte <hplus@mi...>  20020206 05:17:41

Foley, van Dam has a discussion of it, although they call it "the Midpoint algorithm" and try to hide the reference to Bresenham in a dusty corner somewhere. Have you tried cracking the book open and typing it in? If that doesn't work, how about stepping through it in the debugger to figure out why it only deals with odd axis lengths? I also found a PDF which describes an algorithm which claims to have a smaller error metric than the Bresenham one: http://wscg.zcu.cz/wscg2001/Papers_2001/R18.pdf There's C code at the back of the PDF. Cheers, / h+ > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Mark > Speir > Sent: Tuesday, February 05, 2002 9:00 PM > To: GDAlgorithms > Subject: Re: [Algorithms] New here. Need help, might be slightly > offtopic... > > > > How about ... > > > > if(iWidth % 2) > > iWidth++; > > > > seems like it would solve the problem ... > > I wish it were that simple. Regardless of what I set the x or y radius to, > it only draws ovals with odd radii. In other words, if I set the radius to > (100,200), I actually get an oval with a radius of (99,199). > Increasing the > radii by one wont solve the problem. The bug is somewhere in the > algorithm. > > This bug seems to be in all of the Bresenham ellipse and circle algorithms > that I have found online. I find it real odd that no one has ever tried to > fix it or even mention that there is a problem. Am I just a spoiled Mac > programmer or is the accepted quality for PC graphics software really that > low? No offence intended, but for many years, PC programmers relied on > graphics libraries for primative drawing. If this is what they > had, why was > there never an effort to fix it and then post the correction? > > I know that there is a way to do it right. Just look at QuickDraw's > FrameOval and whatever the simular function is called in Windows. > They work > correctly, so someone knows how to do it right. Like I said in a previous > email, It's a tightly guarded secret of the software companies... > > Sorry if I seem a bit annoyed. I am, but at no one person. It's > just that I > have been trying to find this "simple" algorithm for several years off and > on for various reasons. This time I am not going to rest until I > find it (I > can see myself at 90, curled up in a rocking chair cursing Jack > Bresenham's > name... LOL). > > Mark > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Mark Speir <maspeir@sa...>  20020206 05:00:08

> How about ... > > if(iWidth % 2) > iWidth++; > > seems like it would solve the problem ... I wish it were that simple. Regardless of what I set the x or y radius to, it only draws ovals with odd radii. In other words, if I set the radius to (100,200), I actually get an oval with a radius of (99,199). Increasing the radii by one wont solve the problem. The bug is somewhere in the algorithm. This bug seems to be in all of the Bresenham ellipse and circle algorithms that I have found online. I find it real odd that no one has ever tried to fix it or even mention that there is a problem. Am I just a spoiled Mac programmer or is the accepted quality for PC graphics software really that low? No offence intended, but for many years, PC programmers relied on graphics libraries for primative drawing. If this is what they had, why was there never an effort to fix it and then post the correction? I know that there is a way to do it right. Just look at QuickDraw's FrameOval and whatever the simular function is called in Windows. They work correctly, so someone knows how to do it right. Like I said in a previous email, It's a tightly guarded secret of the software companies... Sorry if I seem a bit annoyed. I am, but at no one person. It's just that I have been trying to find this "simple" algorithm for several years off and on for various reasons. This time I am not going to rest until I find it (I can see myself at 90, curled up in a rocking chair cursing Jack Bresenham's name... LOL). Mark 
From: Tom Hubina <tomh@3d...>  20020206 04:22:54

At 11:36 PM 2/4/2002, Mark Speir wrote: >It works great and draws both filled and hollow elipses. The problem is that >the algorithm, for some reason, seems to subtract 1 from the radius if the >radius is an even number, i.e., an ellipse with a radius of (2,3) would be >drawn 1 pixel wide by 3 pixels tall. Regardless of what the radii is, it >will only be drawn correctly if the radii is an odd number. How about ... if(iWidth % 2) iWidth++; seems like it would solve the problem ... Tom 
From: Mark Speir <maspeir@sa...>  20020206 04:07:52

> First, if you use the toolbox drawing to generate the tool, you > only need a bitmap that's the size of the tool, not the size of > the destination. > > Second, I can't see how drawing one ellipse into a b/w bitmap > using QuickDraw can be slow enough to matter, compared to all > the memory you'll be touching and/or updating on the screen > for all the tiles you changed. > > Third, you only need to regenerate the bitmap when the size of > the tool changes; this is a single operation that only happens > when the user accepts a resize change for the tool in your UI > somehow (do you use a typein? x/y size sliders? Doesn't matter; > only regenerate the bitmap when the user presses return or lets > go of the slider). > > I'm assuming the mapping from an NxN bitmap centered on some > coordinate (where the user clicked) to which tiles to affect in > your world map is reasonably obvious. I can think of several optimizations to this method. I can speed it up dramatically, but I did this in the first place simply because I could not find a ellipse drawing algorithm. Regardless if I can speed this up, it is not the way I want to do this. BTW, the tools are used just like in a drawing program. You click and drag to draw the line/rect/oval, et. al. I really want the oval algorithm seperate because I plan on releasing several functions to the SpriteWorld library dealing with drawing lines, rectangles and ovals of tiles. I know that here is a correct version of the Bresenham algorithm in the world somewhere, however I am begining to think it is a tightly guarded of the software companies. Mark 
From: Willmott, Andrew <AW<illmott@ma...>  20020206 03:46:06

> Well, I have contraditory results from Intel: > > http://developer.intel.com/design/pentiumiii/sml/24504301.pdf > > Cramer's rule seems pretty efficient even with a 4x4. When > coupled with > SIMD, it totally rocks! Note that these results aren't inconsistent: Graham's link is measuring Cramer's rule against Gaussian elimination for solving Ax = b, whereas the Intel guys are measuring it against computing the entire inverse iteratively. It's not surprising elimination does better for the first case. FWIW I use cramer's rule for 3x3 and 4x4 matrix inversion and swap to iterative methods thereafter. As everyone else has said, you should be using elimination to solve most Ax = b cases, but having to have an explicit inverse does crop up a fair bit in camera calculations, enough to care about having a fast explicit inverse. Cheers, Andrew 
From: Jon Watte <hplus@mi...>  20020206 00:39:18

> >  If choosing the compiler way, should they output C++ code, some custom > bytecode or platformobject code ? > > If I was writing a compiler, I would output some bytecode. > Writing a simple VM is an easy task. Banging out an *efficient* VM and bytecode rep is no easy task, though. You might as well treat your CPU instruction set as a kind of bytecode and emit that  at least the interpreter is fast and readily available, not to mention debuggers. Honestly, outputting unoptimized x86 code (or MIPS, or whatever) is no harder than outputting bytecode for any other VM. Worst case, you'll just output a bunch of call:s. Make it tabledriven so you can easily port it later. For the special case of config file parsing, here's all you need: // simple config file parser, supporting comment lines // starting with '#' and variable assignment in the form // variable = string // Sorry, no leading spaces in "string" allowed. using namespace std; map<string,string> variables; char line[ 1024 ], varname[ 1024 ]; while( true ) { line[ 0 ] = 0; fgets( line, 1024, file ); if( !line[ 0 ] ) break; if( line[ 0 ] == '\n'  line[ 0 ] == '#' ) continue; char * nl = strchr( line, '\n' ); if( nl ) *nl = 0; int offset = 0; sscanf( line, " %[^ \t\n=] = %n", varname, &offset ); if( !offset ) { error( line ); } else { variables[string(varname)] = string(&line[ offset ]); } } For more expressive power, I'd suggest looking into Lua, as it's small in footprint, high in expressivity, and very very easy to integrate into your application. It's been used in several commercial apps (including games). Cheers, / h+ 
From: Jon Watte <hplus@mi...>  20020206 00:39:16

First, if you use the toolbox drawing to generate the tool, you only need a bitmap that's the size of the tool, not the size of the destination. Second, I can't see how drawing one ellipse into a b/w bitmap using QuickDraw can be slow enough to matter, compared to all the memory you'll be touching and/or updating on the screen for all the tiles you changed. Third, you only need to regenerate the bitmap when the size of the tool changes; this is a single operation that only happens when the user accepts a resize change for the tool in your UI somehow (do you use a typein? x/y size sliders? Doesn't matter; only regenerate the bitmap when the user presses return or lets go of the slider). I'm assuming the mapping from an NxN bitmap centered on some coordinate (where the user clicked) to which tiles to affect in your world map is reasonably obvious. Cheers, / h+ > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Mark > Speir > Sent: Monday, February 04, 2002 11:37 PM > To: gdalgorithmslist@... > Subject: [Algorithms] New here. Need help, might be slightly off > topic... > > > I am making a tile based game with the SpriteWorld library for the Mac. > Currently, I am in the process of writing the game's level editor. I want > the editor to resemble a standard painting/drawing app and as > such, I have a > fairly complete set of tools. Naturally, since the game is tile based, all > of the tools draw tiles instead of pixels. > > My problem is with the oval tool. I have searched the internet for any > source code relating to Bresenham's ellipse algorithm, but with very poor > luck. I did finally find some code here: > http://www.ncbi.nlm.nih.gov/IEB/ToolBox/C_DOC/lxr/source/corelib/gifgen.c > > It works great and draws both filled and hollow elipses. The > problem is that > the algorithm, for some reason, seems to subtract 1 from the radius if the > radius is an even number, i.e., an ellipse with a radius of (2,3) would be > drawn 1 pixel wide by 3 pixels tall. Regardless of what the radii is, it > will only be drawn correctly if the radii is an odd number. > > I then did another search and found some more code, but it has the same > problem. I also notice this with the rather abundant Bresenham circle > algorithms available on the net. > > The other option for me, and the one that I current use and am > trying to get > rid of, is to use the Mac's built in primitive drawing functions > to draw the > primitive into a 1bit bitmap the size of the tile map in pixels. > Then read > the bits, four bytes at a time, and set up to 32 tiles at a time. The > problem with this method is that it is extremely slow and I do not have as > much control over the primative drawing as I would like. The largest level > is 1024 x 1024 tiles and this requires a 1024 x 1024 pixel bit > map. This is > not only very slow, but a big waste of memory. > > I am really at my wits end. I have been searching the internet > for months. I > am remaking an old game that my father started and have all of > the graphics > and sounds. However, I cannot even begin thinking about writing the game's > code until I can make a level. > > I really appreciate any help. > > Thanks, > Mark Speir > maspeir @satx.net > > P.S. If this is off topic, I appologize. > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 