Thread: [Algorithms] 2D Polygon Simplification
Brought to you by:
vexxed72
From: Paul at H. <pa...@ru...> - 2007-12-29 11:06:23
|
I have a 2D outline of the world (literally, the Earth) and it's in = monstrously high detail. I need to simplify it but I'm struggling for = ideas. I've written my own edge collapse routine and it kinda works but I can't = help but feel it should be a lot better. I'm wondering if there's a = resource on the net for a standard algorithm or something ? I've = searched but I can't find anything due to being swamped by tri-mesh = algorithms that just aren't solving the same problem. The best results I've had whilst experimenting are just removing smaller = edges first and putting one of the ends at the midpoint. Not a dot = product in sight. This just implies that I'm not using corner sharpness = the best way when I've tried that. When you want extreme simplification, the trivial "easy" answers I've = tried just aren't cutting it. They don't preserve area well enough, nor = general shape (even when I favour bend-acuteness over length). I think I need edge-collapse (over point collapse), but the "strength" = calculation needs to take into account how bendy the adjoining corners = are, combined with overal length of the edge and maybe some area = calculation. Or something. Anyone ? Regards, Paul Johnson. www.rubicondev.com |
From: Stefan S. <kef...@gm...> - 2007-12-29 11:20:43
|
Just off the top of my head as I read this, I wonder if it would be possible to shrinkwrap a higher order spline around your data, and convert the problem to a parametric one, which could then be tweaked by any number of available techniques, like tessellate based on curvature etc.. Not saying that would work, but it was the first thing that entered my head :) Btw, if this is to be used for a 2d game (windowing a certain portion of that data), you'd already be set to tess. in runtime, which we all know is cool :) Paul at Home wrote: > I have a 2D outline of the world (literally, the Earth) and it's in > monstrously high detail. I need to simplify it but I'm struggling for > ideas. > > I've written my own edge collapse routine and it kinda works but I > can't help but feel it should be a lot better. I'm wondering if > there's a resource on the net for a standard algorithm or something > ? I've searched but I can't find anything due to being swamped by > tri-mesh algorithms that just aren't solving the same problem. > > The best results I've had whilst experimenting are just removing > smaller edges first and putting one of the ends at the midpoint. Not a > dot product in sight. This just implies that I'm not using corner > sharpness the best way when I've tried that. > > When you want extreme simplification, the trivial "easy" answers I've > tried just aren't cutting it. They don't preserve area well enough, > nor general shape (even when I favour bend-acuteness over length). > > I think I need edge-collapse (over point collapse), but the "strength" > calculation needs to take into account how bendy the adjoining corners > are, combined with overal length of the edge and maybe some area > calculation. Or something. > > Anyone ? > > Regards, > Paul Johnson. > www.rubicondev.com <http://www.rubicondev.com> > > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2005. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Paul at H. <pa...@ru...> - 2007-12-29 17:29:06
|
Why does it have to be homebrew ? ;) We do a lot of 'official' DS development here, but the target in question is a piss-poor cellphone/pda running ARM7 at 66Mhz. I can't mention it by name due to the usual NDA stuff. I am thinking of refactoring this problem as a catmull-rom spline and simplifying that as we go, which would be far easier than a conventional spline, but I'd still like to see a decent algorithm that works on the data as-is. Someone mentioned taking area into account, and I've not tried that yet. However even how I bias between "length" and "straightness" seems totally arbitrary right now. I'd love to see a precis on this by someone who's spent a lot of time on it in the past, as I can't believe this isn't an "already solved" problem. Regards, Paul Johnson. www.rubicondev.com ----- Original Message ----- From: "Sylvain G. Vignaud" <vi...@ii...> To: <kef...@gm...>; "Game Development Algorithms" <gda...@li...> Sent: Saturday, December 29, 2007 2:38 PM Subject: Re: [Algorithms] 2D Polygon Simplification > From: Stefan Sandberg <kef...@gm...> >> Paul at Home wrote: >> > handheld machine which doesn't have an FPU, and this is coupled >> > with a CPU speed that's not worth repeating as it'd look like a >> > typo! >> Just out of curiosity, what's the handheld specs? :) > > Sounds like a DS (or a cell phone, but I vote for DS homebrew). > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2005. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > |
From: Paul at H. <pa...@ru...> - 2007-12-29 12:24:12
|
That's not a bad idea, but real-time is definitely out - this is for a handheld machine which doesn't have an FPU, and this is coupled with a CPU speed that's not worth repeating as it'd look like a typo! If I get nowhere with other discrete methods, I'll give this one a run out, thanks. It won't be easy though, so simpler implementation ideas are still welcome :) Regards, Paul Johnson. www.rubicondev.com ----- Original Message ----- From: "Stefan Sandberg" <kef...@gm...> To: "Game Development Algorithms" <gda...@li...> Sent: Saturday, December 29, 2007 11:20 AM Subject: Re: [Algorithms] 2D Polygon Simplification > Just off the top of my head as I read this, I wonder if it would be > possible to shrinkwrap a higher order spline around your data, and > convert the problem to a parametric one, > which could then be tweaked by any number of available techniques, like > tessellate based on curvature etc.. > Not saying that would work, but it was the first thing that entered my > head :) > > Btw, if this is to be used for a 2d game (windowing a certain portion of > that data), you'd already be set to tess. in runtime, which we all know > is cool :) > > > > Paul at Home wrote: >> I have a 2D outline of the world (literally, the Earth) and it's in >> monstrously high detail. I need to simplify it but I'm struggling for >> ideas. >> >> I've written my own edge collapse routine and it kinda works but I >> can't help but feel it should be a lot better. I'm wondering if >> there's a resource on the net for a standard algorithm or something >> ? I've searched but I can't find anything due to being swamped by >> tri-mesh algorithms that just aren't solving the same problem. >> >> The best results I've had whilst experimenting are just removing >> smaller edges first and putting one of the ends at the midpoint. Not a >> dot product in sight. This just implies that I'm not using corner >> sharpness the best way when I've tried that. >> >> When you want extreme simplification, the trivial "easy" answers I've >> tried just aren't cutting it. They don't preserve area well enough, >> nor general shape (even when I favour bend-acuteness over length). >> >> I think I need edge-collapse (over point collapse), but the "strength" >> calculation needs to take into account how bendy the adjoining corners >> are, combined with overal length of the edge and maybe some area >> calculation. Or something. >> >> Anyone ? >> >> Regards, >> Paul Johnson. >> www.rubicondev.com <http://www.rubicondev.com> >> >> >> ------------------------------------------------------------------------ >> >> ------------------------------------------------------------------------- >> This SF.net email is sponsored by: Microsoft >> Defy all challenges. Microsoft(R) Visual Studio 2005. >> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ >> ------------------------------------------------------------------------ >> >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2005. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > |
From: Stefan S. <kef...@gm...> - 2007-12-29 12:32:46
|
You could still use the shrinkwrap concept, and instead of edge-collapsing where there's too much frequency, you swap the problem around, and start with a coarse approximation and subdivide where it seems needed according to some threshold, like 'angle', or 'stretch'. Sortof how you build a geo-sphere by recursively subdividing a coarse mesh, say a cube, but instead subdividing to reach the parametric surface of a sphere, you do it towards your hires basemesh. If this is purely an offline preprocessing stage, you could get very good results from something like that I think. (but again, this is all theory coming out of my coffecup this time, not the bed) Just out of curiosity, what's the handheld specs? :) Paul at Home wrote: > That's not a bad idea, but real-time is definitely out - this is for a > handheld machine which doesn't have an FPU, and this is coupled with a > CPU speed that's not worth repeating as it'd look like a typo! > > If I get nowhere with other discrete methods, I'll give this one a run > out, thanks. It won't be easy though, so simpler implementation ideas > are still welcome :) > > Regards, > Paul Johnson. > www.rubicondev.com > > > ----- Original Message ----- From: "Stefan Sandberg" > <kef...@gm...> > To: "Game Development Algorithms" > <gda...@li...> > Sent: Saturday, December 29, 2007 11:20 AM > Subject: Re: [Algorithms] 2D Polygon Simplification > > >> Just off the top of my head as I read this, I wonder if it would be >> possible to shrinkwrap a higher order spline around your data, and >> convert the problem to a parametric one, >> which could then be tweaked by any number of available techniques, like >> tessellate based on curvature etc.. >> Not saying that would work, but it was the first thing that entered my >> head :) >> >> Btw, if this is to be used for a 2d game (windowing a certain portion of >> that data), you'd already be set to tess. in runtime, which we all know >> is cool :) >> >> >> >> Paul at Home wrote: >>> I have a 2D outline of the world (literally, the Earth) and it's in >>> monstrously high detail. I need to simplify it but I'm struggling for >>> ideas. >>> >>> I've written my own edge collapse routine and it kinda works but I >>> can't help but feel it should be a lot better. I'm wondering if >>> there's a resource on the net for a standard algorithm or something >>> ? I've searched but I can't find anything due to being swamped by >>> tri-mesh algorithms that just aren't solving the same problem. >>> >>> The best results I've had whilst experimenting are just removing >>> smaller edges first and putting one of the ends at the midpoint. Not a >>> dot product in sight. This just implies that I'm not using corner >>> sharpness the best way when I've tried that. >>> >>> When you want extreme simplification, the trivial "easy" answers I've >>> tried just aren't cutting it. They don't preserve area well enough, >>> nor general shape (even when I favour bend-acuteness over length). >>> >>> I think I need edge-collapse (over point collapse), but the "strength" >>> calculation needs to take into account how bendy the adjoining corners >>> are, combined with overal length of the edge and maybe some area >>> calculation. Or something. >>> >>> Anyone ? >>> >>> Regards, >>> Paul Johnson. >>> www.rubicondev.com <http://www.rubicondev.com> >>> >>> >>> ------------------------------------------------------------------------ >>> >>> >>> ------------------------------------------------------------------------- >>> >>> This SF.net email is sponsored by: Microsoft >>> Defy all challenges. Microsoft(R) Visual Studio 2005. >>> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ >>> ------------------------------------------------------------------------ >>> >>> >>> _______________________________________________ >>> GDAlgorithms-list mailing list >>> GDA...@li... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>> >> >> >> ------------------------------------------------------------------------- >> >> This SF.net email is sponsored by: Microsoft >> Defy all challenges. Microsoft(R) Visual Studio 2005. >> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> >> >> > > |
From: Lorenzo P. <pas...@ul...> - 2007-12-29 12:30:34
|
I remember that John Ratcliff had a nice piece of code that might be useful looking at : http://www.codesuppository.blogspot.com/#115463356104713295 I'm not sure how it would perform in 2D but might be worth a try... Paul at Home a écrit : > I have a 2D outline of the world (literally, the Earth) and it's in > monstrously high detail. I need to simplify it but I'm struggling for ideas. > > I've written my own edge collapse routine and it kinda works but I can't > help but feel it should be a lot better. I'm wondering if there's a > resource on the net for a standard algorithm or something ? I've > searched but I can't find anything due to being swamped by tri-mesh > algorithms that just aren't solving the same problem. > > The best results I've had whilst experimenting are just removing smaller > edges first and putting one of the ends at the midpoint. Not a dot > product in sight. This just implies that I'm not using corner sharpness > the best way when I've tried that. > > When you want extreme simplification, the trivial "easy" answers I've > tried just aren't cutting it. They don't preserve area well enough, nor > general shape (even when I favour bend-acuteness over length). > > I think I need edge-collapse (over point collapse), but the "strength" > calculation needs to take into account how bendy the adjoining corners > are, combined with overal length of the edge and maybe some area > calculation. Or something. > > Anyone ? > > Regards, > Paul Johnson. > www.rubicondev.com <http://www.rubicondev.com> > > > > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2005. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Sylvain G. V. <vi...@ii...> - 2007-12-29 14:38:23
|
From: Stefan Sandberg <kef...@gm...> > Paul at Home wrote: > > handheld machine which doesn't have an FPU, and this is coupled > > with a CPU speed that's not worth repeating as it'd look like a > > typo! > Just out of curiosity, what's the handheld specs? :) Sounds like a DS (or a cell phone, but I vote for DS homebrew). |
From: Sigurd S. <sig...@gm...> - 2007-12-29 22:22:32
|
Since the problem is similar to mesh simplification, this might give you a nice metric (Garlands quadratic error metric is the first that comes to mind). |
From: Peter-Pike S. <pp...@wi...> - 2007-12-30 03:33:25
|
You can build quadrics for lines. I've done this in the past for streamlin= es, but never published it. I think you just create the quadrics for two p= lanes whose intersection defines the line (this was in 3D, in 2D you could = do something even simpler - since a line is just a 2D plane equation...) Y= ou might want to also weight them by length or something, small segments th= at are "noise" could overly constrain things otherwise... Peter-Pike (There are papers on this kind of thing, look in the medical segmentation l= iterature, and I think it is an example in the wavelets for graphics book..= .) -----Original Message----- From: gda...@li... [mailto:gdalgorithms-= lis...@li...] On Behalf Of Sigurd Seteklev Sent: Saturday, December 29, 2007 2:23 PM To: Game Development Algorithms Subject: Re: [Algorithms] 2D Polygon Simplification Since the problem is similar to mesh simplification, this might give you a nice metric (Garlands quadratic error metric is the first that comes to mind). ------------------------------------------------------------------------- This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2005. http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-list |
From: Robin G. <rob...@gm...> - 2007-12-30 04:27:56
|
There you go, Finkelstein and Salesin, "Multiresolution Curves", Siggraph 1994 http://www.cs.princeton.edu/gfx/pubs/Finkelstein_1994_MC/finkelstein_1994_mc.pdf By the way, Stollnitz's book "Wavelets for Computer Gaphics" is utterly useless - a gentle introduction to the uses of wavelets, it was written before Lifting was concieved and now it just's confuses everyone. I wish we could remove the pages from every copy and instead insert a note directing people to: http://www.multires.caltech.edu/teaching/courses/waveletcourse/ - Robin Green. On Dec 29, 2007 7:33 PM, Peter-Pike Sloan <pp...@wi...> wrote: > > (There are papers on this kind of thing, look in the medical segmentation literature, and I think it is an example in the wavelets for graphics book...) |
From: Eric H. <eri...@gm...> - 2008-01-03 00:37:36
|
Ke-Sen Huang has recently updated his wonderful page http://kesen.huang.googlepages.com/ with conferences that are of interest to people here. See http://kesen.huang.googlepages.com/i3d2008Papers.htm for I3D 2008 papers and http://kesen.huang.googlepages.com/eg2008Papers.htm for Eurographics 2008 papers (yes, Eurographics moved to the Spring). Looking around, there are some interesting things going on relevant to game graphics, e.g. Polypostors http://isg.cs.tcd.ie/kavanl/ and deep opacity maps http://www.cemyuksel.com/research/deepopacity/. I3D in seven seconds: http://graphics.cs.williams.edu/i3d08/, it's the weekend before GDC at EA's campus, which is 30 minutes from San Francisco; GDC attendees and IGDA members get a discount. Early registration ends January 15th. (OK, I'll take my general co-chair hat off now.) Eric |
From: Gernot Z. <gz...@ge...> - 2008-01-07 15:58:41
|
Hej folks! I thought you guys might be interested in some stuff that I have=20 developed over the last two years:=20 HistoPyramids are mipmap-like data structures that can be used for=20 geometry shader-like functionality, on _any_ hardware that is capable of=20 dependent texture lookups, like NV30/40-hardware or even mobile graphics=20 hardware (!). (On GeForce 8 hardware, it currently outperforms geometry=20 shaders by a factor of 4-5, hehe ;) ) Up to now, we have used it for real-time 3D model-to-point cloud=20 decomposition, physical light simulations, real-time quadtree analysis of= =20 DVD-res video and a very fast Marching Cubes implementation on nVidia=20 geForce 6-8 hardware, but I am sure you can come=20 up with a lot more fun ideas :)=20 If you are curious, please take a look at my homepage http://www.mpi-inf.mpg.de/~gziegler This presentation might be best at explaining HistoPyramids: http://www.mpi-inf.mpg.de/~gziegler/ljus/sketch.pdf Sourcecode? Is available on http://nvision.sf.net :-)=20 A good place for more discussion (if not on this list) is probably the=20 GPGPU-forum "GPU Data Compaction V2.0", see http://www.gpgpu.org/forums/viewtopic.php?t=3D3577&postdays=3D0&postorder= =3Dasc&start=3D0&sid=3D83b3722d55faf748fb67bb19abdc360b Looking forward to hearing your feedback! :)=20 Servus from Saarbr=FCcken, Gernot GPU. 3D Vision. Europe. Future. Now. Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu |
From: Stefan S. <kef...@gm...> - 2008-01-07 20:00:21
|
How would the wavefront solution handle large simulations, ie teapot-in-a-stadium type of things, being a volumetric approach? Does the volume have to enclose the entire scene or just the teapot, and the stadium gets the result "projected" on it from the volume? Gernot Ziegler wrote: > Hej folks! > > I thought you guys might be interested in some stuff that I have > developed over the last two years: > > HistoPyramids are mipmap-like data structures that can be used for > geometry shader-like functionality, on _any_ hardware that is capable of > dependent texture lookups, like NV30/40-hardware or even mobile graphics > hardware (!). (On GeForce 8 hardware, it currently outperforms geometry > shaders by a factor of 4-5, hehe ;) ) > > Up to now, we have used it for real-time 3D model-to-point cloud > decomposition, physical light simulations, real-time quadtree analysis of > DVD-res video and a very fast Marching Cubes implementation on nVidia > geForce 6-8 hardware, but I am sure you can come > up with a lot more fun ideas :) > > If you are curious, please take a look at my homepage > http://www.mpi-inf.mpg.de/~gziegler > > This presentation might be best at explaining HistoPyramids: > http://www.mpi-inf.mpg.de/~gziegler/ljus/sketch.pdf > > Sourcecode? Is available on http://nvision.sf.net :-) > > A good place for more discussion (if not on this list) is probably the > GPGPU-forum "GPU Data Compaction V2.0", see > http://www.gpgpu.org/forums/viewtopic.php?t=3577&postdays=0&postorder=asc&start=0&sid=83b3722d55faf748fb67bb19abdc360b > > Looking forward to hearing your feedback! :) > > Servus from Saarbrücken, > Gernot > > GPU. 3D Vision. Europe. Future. Now. > Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2005. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Gernot Z. <gz...@ge...> - 2008-01-07 20:05:55
|
Hej Stefan! > How would the wavefront solution handle large simulations, ie=20 > teapot-in-a-stadium type of things, being a volumetric approach? > Does the volume have to enclose the entire scene or just the teapot, and= =20 > the stadium gets the result "projected" on it from the volume? The volume _is_ the entire scene of refractive indices - the rest of the=20 surrounding 3D scene can just contribute with environment mapping.=20 Of course, the wavefront may progress=20 outside the volume, but nothing will happen there anymore (that's why it=20 is culled as soon as it leaves the caustics volume to save calculations). Mind you that light simulation takes 10 secs, it is not real-time. :-) >=20 >=20 > Gernot Ziegler wrote: > > Hej folks! > > > > I thought you guys might be interested in some stuff that I have=20 > > developed over the last two years:=20 > > > > HistoPyramids are mipmap-like data structures that can be used for=20 > > geometry shader-like functionality, on _any_ hardware that is capable o= f=20 > > dependent texture lookups, like NV30/40-hardware or even mobile graphic= s=20 > > hardware (!). (On GeForce 8 hardware, it currently outperforms geometry= =20 > > shaders by a factor of 4-5, hehe ;) ) > > > > Up to now, we have used it for real-time 3D model-to-point cloud=20 > > decomposition, physical light simulations, real-time quadtree analysis = of=20 > > DVD-res video and a very fast Marching Cubes implementation on nVidia= =20 > > geForce 6-8 hardware, but I am sure you can come=20 > > up with a lot more fun ideas :)=20 > > > > If you are curious, please take a look at my homepage > > http://www.mpi-inf.mpg.de/~gziegler > > > > This presentation might be best at explaining HistoPyramids: > > http://www.mpi-inf.mpg.de/~gziegler/ljus/sketch.pdf > > > > Sourcecode? Is available on http://nvision.sf.net :-)=20 > > > > A good place for more discussion (if not on this list) is probably the= =20 > > GPGPU-forum "GPU Data Compaction V2.0", see > > http://www.gpgpu.org/forums/viewtopic.php?t=3D3577&postdays=3D0&postord= er=3Dasc&start=3D0&sid=3D83b3722d55faf748fb67bb19abdc360b > > > > Looking forward to hearing your feedback! :)=20 > > > > Servus from Saarbr=FCcken, > > Gernot > > > > GPU. 3D Vision. Europe. Future. Now. > > Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu > > =20 > > -----------------------------------------------------------------------= - > > > > -----------------------------------------------------------------------= -- > > This SF.net email is sponsored by: Microsoft > > Defy all challenges. Microsoft(R) Visual Studio 2005. > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > -----------------------------------------------------------------------= - > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-= list >=20 >=20 > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketpl= ace > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-li= st >=20 Servus, Gernot GPU. 3D Vision. Europe. Future. Now. Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu |
From: Gernot Z. <gz...@ge...> - 2008-01-07 19:41:00
|
No application has been filed, and the HistoPyramid publication is even=20 beyond the 1 year grace period in the US. So don't be afraid to use it.=20 > What is the patent status of the algorithm? >=20 >=20 > Gernot Ziegler wrote: > > Hej folks! > > > > I thought you guys might be interested in some stuff that I have develo= ped > > over the last two years:=20 > > > > HistoPyramids are mipmap-like data structures that can be used for geom= etry > > shader-like functionality, on _any_ hardware that is capable of depende= nt > > texture lookups, like NV30/40-hardware or even mobile graphics hardware= (!). > > (On GeForce 8 hardware, it currently outperforms geometry shaders by a > > factor of 4-5, hehe ;) ) > > > > Up to now, we have used it for real-time 3D model-to-point cloud > > decomposition, physical light simulations, real-time quadtree analysis = of > > DVD-res video and a very fast Marching Cubes implementation on nVidia > > geForce 6-8 hardware, but I am sure you can come up with a lot more fun > > ideas :)=20 > > > > If you are curious, please take a look at my homepage > > http://www.mpi-inf.mpg.de/~gziegler > > > > This presentation might be best at explaining HistoPyramids: > > http://www.mpi-inf.mpg.de/~gziegler/ljus/sketch.pdf > > > > Sourcecode? Is available on http://nvision.sf.net :-)=20 > > > > A good place for more discussion (if not on this list) is probably the > > GPGPU-forum "GPU Data Compaction V2.0", see > > http://www.gpgpu.org/forums/viewtopic.php?t=3D3577&postdays=3D0&postord= er=3Dasc&start=3D0&sid=3D83b3722d55faf748fb67bb19abdc360b > > > > Looking forward to hearing your feedback! :)=20 > > > > Servus from Saarbr=FCcken, > > Gernot > > > > GPU. 3D Vision. Europe. Future. Now. > > Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu > > ---------------------------------------------------------------------= --- > > > > -----------------------------------------------------------------------= -- > > This SF.net email is sponsored by: Microsoft > > Defy all challenges. Microsoft(R) Visual Studio 2005. > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > -----------------------------------------------------------------------= - > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-= list >=20 > --=20 > -- Go is to Western chess what philosophy is to double entry accounting. >=20 Servus, Gernot GPU. 3D Vision. Europe. Future. Now. Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu |
From: Stefan S. <kef...@gm...> - 2008-01-07 20:29:24
|
So if you had say a football field with two refractive footballs on opposite ends of the field, the volume would have to cover a huge amount of empty space, or would there be one volume for each of them? I guess this discussion is not game related anymore :) Gernot Ziegler wrote: > Hej Stefan! > > >> How would the wavefront solution handle large simulations, ie >> teapot-in-a-stadium type of things, being a volumetric approach? >> Does the volume have to enclose the entire scene or just the teapot, and >> the stadium gets the result "projected" on it from the volume? >> > > The volume _is_ the entire scene of refractive indices - the rest of the > surrounding 3D scene can just contribute with environment mapping. > Of course, the wavefront may progress > outside the volume, but nothing will happen there anymore (that's why it > is culled as soon as it leaves the caustics volume to save calculations). > > Mind you that light simulation takes 10 secs, it is not real-time. :-) > > >> Gernot Ziegler wrote: >> >>> Hej folks! >>> >>> I thought you guys might be interested in some stuff that I have >>> developed over the last two years: >>> >>> HistoPyramids are mipmap-like data structures that can be used for >>> geometry shader-like functionality, on _any_ hardware that is capable of >>> dependent texture lookups, like NV30/40-hardware or even mobile graphics >>> hardware (!). (On GeForce 8 hardware, it currently outperforms geometry >>> shaders by a factor of 4-5, hehe ;) ) >>> >>> Up to now, we have used it for real-time 3D model-to-point cloud >>> decomposition, physical light simulations, real-time quadtree analysis of >>> DVD-res video and a very fast Marching Cubes implementation on nVidia >>> geForce 6-8 hardware, but I am sure you can come >>> up with a lot more fun ideas :) >>> >>> If you are curious, please take a look at my homepage >>> http://www.mpi-inf.mpg.de/~gziegler >>> >>> This presentation might be best at explaining HistoPyramids: >>> http://www.mpi-inf.mpg.de/~gziegler/ljus/sketch.pdf >>> >>> Sourcecode? Is available on http://nvision.sf.net :-) >>> >>> A good place for more discussion (if not on this list) is probably the >>> GPGPU-forum "GPU Data Compaction V2.0", see >>> http://www.gpgpu.org/forums/viewtopic.php?t=3577&postdays=0&postorder=asc&start=0&sid=83b3722d55faf748fb67bb19abdc360b >>> >>> Looking forward to hearing your feedback! :) >>> >>> Servus from Saarbrücken, >>> Gernot >>> >>> GPU. 3D Vision. Europe. Future. Now. >>> Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu >>> >>> ------------------------------------------------------------------------ >>> >>> ------------------------------------------------------------------------- >>> This SF.net email is sponsored by: Microsoft >>> Defy all challenges. Microsoft(R) Visual Studio 2005. >>> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ >>> ------------------------------------------------------------------------ >>> >>> _______________________________________________ >>> GDAlgorithms-list mailing list >>> GDA...@li... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>> >> ------------------------------------------------------------------------- >> Check out the new SourceForge.net Marketplace. >> It's the best place to buy or sell services for >> just about anything Open Source. >> http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> >> > > Servus, > Gernot > > GPU. 3D Vision. Europe. Future. Now. > Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Gernot Z. <gz...@ge...> - 2008-01-07 20:47:05
|
Hej Stefan! > So if you had say a football field with two refractive footballs on=20 > opposite ends of the field, the volume would have to cover a huge amount= =20 > of empty space, > or would there be one volume for each of them? There would be a volume for each of them ... just like in the museum scene= =20 of the demo video. But both would only influence each other via env=20 mapping, nothing special.=20 > I guess this discussion is not game related anymore :) Since it was about the real-time part (scene refraction, not light=20 refraction), I still answered to gd-algo :-)=20 >=20 > Gernot Ziegler wrote: > > Hej Stefan! > > > > =20 > >> How would the wavefront solution handle large simulations, ie=20 > >> teapot-in-a-stadium type of things, being a volumetric approach? > >> Does the volume have to enclose the entire scene or just the teapot, a= nd=20 > >> the stadium gets the result "projected" on it from the volume? > >> =20 > > > > The volume _is_ the entire scene of refractive indices - the rest of th= e=20 > > surrounding 3D scene can just contribute with environment mapping.=20 > > Of course, the wavefront may progress=20 > > outside the volume, but nothing will happen there anymore (that's why i= t=20 > > is culled as soon as it leaves the caustics volume to save calculations= ). > > > > Mind you that light simulation takes 10 secs, it is not real-time. :-) > > > > =20 > >> Gernot Ziegler wrote: > >> =20 > >>> Hej folks! > >>> > >>> I thought you guys might be interested in some stuff that I have=20 > >>> developed over the last two years:=20 > >>> > >>> HistoPyramids are mipmap-like data structures that can be used for=20 > >>> geometry shader-like functionality, on _any_ hardware that is capable= of=20 > >>> dependent texture lookups, like NV30/40-hardware or even mobile graph= ics=20 > >>> hardware (!). (On GeForce 8 hardware, it currently outperforms geomet= ry=20 > >>> shaders by a factor of 4-5, hehe ;) ) > >>> > >>> Up to now, we have used it for real-time 3D model-to-point cloud=20 > >>> decomposition, physical light simulations, real-time quadtree analysi= s of=20 > >>> DVD-res video and a very fast Marching Cubes implementation on nVidia= =20 > >>> geForce 6-8 hardware, but I am sure you can come=20 > >>> up with a lot more fun ideas :)=20 > >>> > >>> If you are curious, please take a look at my homepage > >>> http://www.mpi-inf.mpg.de/~gziegler > >>> > >>> This presentation might be best at explaining HistoPyramids: > >>> http://www.mpi-inf.mpg.de/~gziegler/ljus/sketch.pdf > >>> > >>> Sourcecode? Is available on http://nvision.sf.net :-)=20 > >>> > >>> A good place for more discussion (if not on this list) is probably th= e=20 > >>> GPGPU-forum "GPU Data Compaction V2.0", see > >>> http://www.gpgpu.org/forums/viewtopic.php?t=3D3577&postdays=3D0&posto= rder=3Dasc&start=3D0&sid=3D83b3722d55faf748fb67bb19abdc360b > >>> > >>> Looking forward to hearing your feedback! :)=20 > >>> > >>> Servus from Saarbr=FCcken, > >>> Gernot > >>> > >>> GPU. 3D Vision. Europe. Future. Now. > >>> Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu > >>> =20 > >>> ---------------------------------------------------------------------= --- > >>> > >>> ---------------------------------------------------------------------= ---- > >>> This SF.net email is sponsored by: Microsoft > >>> Defy all challenges. Microsoft(R) Visual Studio 2005. > >>> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > >>> ---------------------------------------------------------------------= --- > >>> > >>> _______________________________________________ > >>> GDAlgorithms-list mailing list > >>> GDA...@li... > >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >>> Archives: > >>> http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithm= s-list > >>> =20 > >> ----------------------------------------------------------------------= --- > >> Check out the new SourceForge.net Marketplace. > >> It's the best place to buy or sell services for > >> just about anything Open Source. > >> http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marke= tplace > >> _______________________________________________ > >> GDAlgorithms-list mailing list > >> GDA...@li... > >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >> Archives: > >> http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms= -list > >> > >> =20 > > > > Servus, > > Gernot > > > > GPU. 3D Vision. Europe. Future. Now. > > Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu > > =20 > > -----------------------------------------------------------------------= - > > > > -----------------------------------------------------------------------= -- > > Check out the new SourceForge.net Marketplace. > > It's the best place to buy or sell services for > > just about anything Open Source. > > http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/market= place > > -----------------------------------------------------------------------= - > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-= list >=20 >=20 > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketpl= ace > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgorithms-li= st >=20 Servus, Gernot GPU. 3D Vision. Europe. Future. Now. Drop by: www.mpi-sb.mpg.de/~gziegler - www.geofront.eu |