## Re: [Algorithms] Huge world, little precision

 Re: [Algorithms] Huge world, little precision From: Alex Walters - 2007-03-01 09:28:04 ```I came across this a while back, a simple, highly accurate approximation=0D= =0Afor sin/cos. I expect this might be 'fixed-point'able. Might be more=0D=0A= effective than a look up table.=0D=0A=0D=0Ahttp://www.devmaster.net/forums/= showthread.php=3Ft=3D5784=0D=0A=0D=0A(Also mirrored on my wiki incase I los= t the link=0D=0Ahttp://www.caffine-powered.co.uk/index.php/Fast=5FSine/Cosi= ne)=20=0D=0A=0D=0ARegards,=0D=0A=0D=0AAlex=0D=0A=0D=0A> -----Original Messa= ge-----=0D=0A> From: gdalgorithms-list-bounces@...=20=0D=0A= > [mailto:gdalgorithms-list-bounces@...] On=20=0D=0A> Beh= alf Of Conor Stokes=0D=0A> Sent: 01 March 2007 01:41=0D=0A> To: Game Develo= pment Algorithms=0D=0A> Subject: Re: [Algorithms] Huge world, little precis= ion=0D=0A>=20=0D=0A> There are plenty of reasonable ways to do fixed point =0D= =0A> rotation. Demo coders did it for years, often in asm. All you=20=0D=0A= > really need are some of the basic operations like fixed point=20=0D=0A> m= ultiply, divide, construct from float (for sin and cos) etc.=20=0D=0A> If y= ou want to avoid floats completely, you can take a leaf=20=0D=0A> from the = demo coders book and use sin/cos LUTs (not that I=20=0D=0A> suggest this on= large scale worlds with available floating point :-)).=0D=0A>=20=0D=0A> If= you wrote a fixed point number wrapper class with=20=0D=0A> overloaded ope= rators it would be a doddle to re-implement=20=0D=0A> vector and matrix mat= h, compared to doing it in x86 assembler=20=0D=0A> on a 386 in real mode. =0D= =0A>=20=0D=0A> ----- Original Message ----=0D=0A> From: Gino van den Bergen= =0D=0A> To: Game Development Algorithms =0D= =0A> =0D=0A> Sent: Thursday, March= 1, 2007 12:51:50 AM=0D=0A> Subject: Re: [Algorithms] Huge world, little pr= ecision=0D=0A>=20=0D=0A> When you are using fixed-point position for vertic= es and view=20=0D=0A> pos, you'd better not do a full world to view space =0D= =0A> transformation because then you'd have to perform rotations=20=0D=0A> = on fixed-point coordinates. There basically is not a nice way=20=0D=0A> to = do this even on a CPU. Rotations are best done using float values.=20=0D=0A= >=20=0D=0A> However, you can compute all your vertex positions relative=20=0D= =0A> to the view pos in world coordinates before converting them=20=0D=0A> = to float vectors.=0D=0A> Distant vertices will drain your relative float ac= curacy but=20=0D=0A> that does not matter so much since they will be render= ed on a=20=0D=0A> much coarser detail and the inaccuracy will disappear in = the=20=0D=0A> projection.=20=0D=0A>=20=0D=0A> You could use int64=5Ft for w= orld coordinates, or use a hybrid=20=0D=0A> approach in which you store the= integer part of a coordinate=20=0D=0A> in an int32=5Ft and the fractional = part in a float. The hybrid=20=0D=0A> approach is nice if you want your vie= wer to move at a finer=20=0D=0A> granularity then your world grid.=0D=0A> =0D= =0A> The only operation that is performed on world coordinates is=20=0D=0A>= subtraction after which the value is converted to a float and=20=0D=0A> ha= nded over to your rendering code. Having=20=0D=0A> view-space-relative worl= d coordinates will probably also come=20=0D=0A> in handy for doing your LOD= -ding.=0D=0A>=20=0D=0A> Gino van den Bergen=0D=0A> http://www.dtecta.com=0D=0A>; =0D= =0A> BTW, you guys are from Eindhoven=3F If you like you could drop=20=0D=0A= > by here in=0D=0A> Breda and discuss this topic further. =20=0D=0A> =0D= =0A> > -----Original Message-----=0D=0A> > From: gdalgorithms-list-bounces@= lists.sourceforge.net=0D=0A> > [mailto:gdalgorithms-list-bounces@...= ceforge.net] On=20=0D=0A> Behalf Of=20=0D=0A> > George van Venrooij=0D=0A> = > Sent: woensdag 28 februari 2007 13:40=0D=0A> > To: Game Development Algor= ithms=0D=0A> > Subject: Re: [Algorithms] Huge world, little precision=0D=0A= > >=20=0D=0A> > Thanks for the link to the article, it is indeed very true = :-)=0D=0A> >=20=0D=0A> > I understand the possible solutions to maintain pr= ecision in the=0D=0A> dataset.=0D=0A> > But the biggest problem I am runnin= g into, is how to "mold"=20=0D=0A> that data=0D=0A> for=0D=0A> > the GPU wh= en rendering. Obviously the GPU cannot render fixed-point=20=0D=0A> > verti= ces, so they need to be processed before sending them.=20=0D=0A> And when =0D= =0A> > sending them they should preferrably be in view-space.=0D=0A> >=20=0D= =0A> > My goal is to keep that processing down to a minimum, but the nature=0D= =0A> of=0D=0A> > the=0D=0A> > data causes a problem:=0D=0A> >=20=0D=0A> > T= he problem with a ROAM-like algorithm is that the mesh can (and=0D=0A> usua= lly=0D=0A> > will) change every frame. And the viewer's position will chang= e as=0D=0A> well.=0D=0A> > The=0D=0A> > only viable solutions I see for thi= s are:=0D=0A> >=20=0D=0A> > 1. Translate the generated vertices to view-spa= ce before rendering=0D=0A> every=0D=0A> > frame (expensive for large meshes= )=0D=0A> > 2. Generate the planet in "patches" that have their own local=0D= =0A> coordinate=0D=0A> > system, and render each "patch" separately. This i= s also something=0D=0A> that=0D=0A> > Jim=0D=0A> > Schuler suggested (this = probably requires doubled vertices or=0D=0A> triangles on=0D=0A> > the "sea= ms" of the patches and hope they fit together nicely when=0D=0A> > rendered= )=0D=0A> >=20=0D=0A> > I'm wondering if there is some kind of third option.= =2E.=0D=0A> >=20=0D=0A> > Regards,=0D=0A> >=20=0D=0A> > George=0D=0A> >= george@...=0D=0A> > http://www.organicvectory.com=0D=0A>; >= =20=0D=0A> >=20=0D=0A> > ----- Original Message -----=0D=0A> > From: "Conor= Stokes" =0D=0A> > To: "Game Develop= ment Algorithms" > list@...>=0D=0A= > > Sent: Wednesday, February 28, 2007 13:12=0D=0A> > Subject: Re: [Algorit= hms] Huge world, little precision=0D=0A> >=20=0D=0A> >=20=0D=0A> > > There = are also lots of neat bit tricks you can do with fixed point=0D=0A> > integ= er=0D=0A> > > coordinates at an object level for building acceleration=20=0D= =0A> structures.=0D=0A> > >=0D=0A> > > ----- Original Message ----=0D=0A> >= > From: "logout@..." =0D=0A> > > To: Game Development = Algorithms > list@...>=0D=0A> > > S= ent: Wednesday, February 28, 2007 8:23:32 PM=0D=0A> > > Subject: Re: [Algor= ithms] Huge world, little precision=0D=0A> > >=0D=0A> > > 64 bit integers=3F=0D= =0A> > >=0D=0A> > > Anyway, I believe you should read TomF's blog, as it =0D= =0A> dealt with this=0D=0A> > > subject:=0D=0A> > >=0D=0A> > >=0D=0A> >=0D=0A= > http://home.comcast.net/~tom=5Fforsyth/blog.wiki.html#%5B%5BA%20=0D=0Amat= ter%20o=0D=0A> f%=0D=0A> > 20precision%5D%5D=0D=0A> > >=0D=0A> > > Regards,=0D= =0A> > >=0D=0A> > > -- Emmanuel Deloget=0D=0A> > >=0D=0A> > >=0D=0A> ------= --------------------------------------------------------=0D=0A> ----------=0D= =0A> > -=0D=0A> > > Take Surveys. Earn Cash. Influence the Future of IT Joi= n=20=0D=0A> > > SourceForge.net's Techsay panel and you'll get the chance t= o=0D=0A> share=0D=0A> > > your=0D=0A> > > opinions on IT & business topics = through brief=20=0D=0A> surveys-and earn cash=0D=0A> > >=0D=0A> >=0D=0A> ht= tp://www.techsay.com/default.php=3Fpage=3Djoin.php&p=3Dsourceforge=0D=0A&CI= D=3DDEVDE=0D=0A> V=0D=0A> > > =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=0D=0A> > > GDAlgorithms-list mailing list=0D=0A> > > = GDAlgorithms-list@...=0D=0A> > > https://lists.sourceforg= e.net/lists/listinfo/gdalgorithms-list=0D=0A> > > Archives:=0D=0A> > > http= ://sourceforge.net/mailarchive/forum.php=3Fforum=5Fid=3D6188=0D=0A> > >=0D=0A= > > >=0D=0A> > >=0D=0A> > >=0D=0A> > >=0D=0A> > >=0D=0A> > >=0D=0A> >=0D=0A= > =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=0D=0A> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=0D= =0A> =5F=5F=0D=0A> > =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=0D=0A> > > Now that's r= oom service! Choose from over 150,000 hotels=20=0D=0A> in 45,000=20=0D=0A>= > > destinations on Yahoo! Travel to find your fit.=0D=0A> > > http://fare= chase.yahoo.com/promo-generic-14795097=0D=0A> > >=0D=0A> > >=0D=0A> -------= -------------------------------------------------------=0D=0A> ----------=0D= =0A> > -=0D=0A> > > Take Surveys. Earn Cash. Influence the Future of IT Joi= n=20=0D=0A> > > SourceForge.net's Techsay panel and you'll get the chance t= o=0D=0A> share=0D=0A> > > your=0D=0A> > > opinions on IT & business topics = through brief=20=0D=0A> surveys-and earn cash=0D=0A> > >=0D=0A> >=0D=0A> ht= tp://www.techsay.com/default.php=3Fpage=3Djoin.php&p=3Dsourceforge=0D=0A&CI= D=3DDEVDE=0D=0A> V=0D=0A> > > =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=0D=0A> > > GDAlgorithms-list mailing list=0D=0A> > > = GDAlgorithms-list@...=0D=0A> > > https://lists.sourceforg= e.net/lists/listinfo/gdalgorithms-list=0D=0A> > > Archives:=0D=0A> > > http= ://sourceforge.net/mailarchive/forum.php=3Fforum=5Fid=3D6188=0D=0A> >=20=0D= =0A> >=20=0D=0A> >=0D=0A> -------------------------------------------------= -------------=0D=0A> ----------=0D=0A> -=0D=0A> > Take Surveys. Earn Cash. = Influence the Future of IT Join=20=0D=0A> > SourceForge.net's Techsay panel= and you'll get the chance to=0D=0A> share=0D=0A> > your=0D=0A> > opinions = on IT & business topics through brief surveys-and earn cash=0D=0A> >=0D=0A>= http://www.techsay.com/default.php=3Fpage=3Djoin.php&p=3Dsourceforge=0D=0A= &CID=3DDEVDE=0D=0A> V=0D=0A> > =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=0D=0A> > GDAlgorithms-list mailing list=0D=0A> > GDAl= gorithms-list@...=0D=0A> > https://lists.sourceforge.net/= lists/listinfo/gdalgorithms-list=0D=0A> > Archives:=0D=0A> > http://sourcef= orge.net/mailarchive/forum.php=3Fforum=5Fid=3D6188=0D=0A>=20=0D=0A> -------= -------------------------------------------------------=0D=0A> -----------=0D= =0A> Take Surveys. Earn Cash. Influence the Future of IT Join=20=0D=0A> Sou= rceForge.net's Techsay panel and you'll get the chance to=20=0D=0A> share y= our opinions on IT & business topics through brief=20=0D=0A> surveys-and ea= rn cash=20=0D=0A> http://www.techsay.com/default.php=3Fpage=3Djoin.php&p=3D= sourceforge=0D=0A&CID=3DDEVDEV=0D=0A> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=0D=0A> GDAlgorithms-list mailing list=0D=0A> GD= Algorithms-list@...=0D=0A> https://lists.sourceforge.net/= lists/listinfo/gdalgorithms-list=0D=0A> Archives:=0D=0A> http://sourceforge= =2Enet/mailarchive/forum.php=3Fforum=5Fid=3D6188=0D=0A>=20=0D=0A>=20=0D=0A>= =20=0D=0A>=20=0D=0A>=20=0D=0A> =20=0D=0A> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=0D=0A> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=0D= =0A> Don't pick lemons.=0D=0A> See all the new 2007 cars at Yahoo! Autos.=0D= =0A> http://autos.yahoo.com/new=5Fcars.html=20=0D=0A>=20=0D=0A>; -----------= ---------------------------------------------------=0D=0A> -----------=0D=0A= > Take Surveys. Earn Cash. Influence the Future of IT Join=20=0D=0A> Source= Forge.net's Techsay panel and you'll get the chance to=20=0D=0A> share your= opinions on IT & business topics through brief=20=0D=0A> surveys-and earn = cash=20=0D=0A> http://www.techsay.com/default.php=3Fpage=3Djoin.php&p=3Dsou= rceforge=0D=0A&CID=3DDEVDEV=0D=0A> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F= =5F=5F=5F=5F=5F=5F=5F=5F=0D=0A> GDAlgorithms-list mailing list=0D=0A> GDAlg= orithms-list@...=0D=0A> https://lists.sourceforge.net/lis= ts/listinfo/gdalgorithms-list=0D=0A> Archives:=0D=0A> http://sourceforge.ne= t/mailarchive/forum.php=3Fforum=5Fid=3D6188=0D=0A>=20=0D=0A>=20=0D=0A-=0D=0A= This message is subject to Imagination Technologies' e-mail terms: http://w= ww.imgtec.com/e-mail.htm=0D=0A-=0D=0A ```