Re: [Algorithms] Triangle strips still useful?
Brought to you by:
vexxed72
From: Juhani H. <ju...@al...> - 2006-10-09 05:52:58
|
Thanks a lot Tom~! I had implemented a similar algorithm based on your notes earlier, but never had time to fine tune a vertex scoring system so the results were not that perfect. Now I just reimplemented that vertex scoring part according to your paper and the results are much better - I'm now getting vertex/tri ratio about ~0.75 for irregular meshes when it was close to ~0.9 earlier. Juhani Tom Forsyth wrote: >I finally got around to writing up this algorithm. The paper itself is here: >http://www.eelpi.gotdns.org/papers/fast_vert_cache_opt.html > >...and my rather less formal blog entry is here: >http://www.eelpi.gotdns.org/blog.wiki.html > >If there's anything that needs clarifying, just ask and I'll add it to >whichever is appropriate. I'd like to get hold of some of the meshes used in >the other papers referenced and do an actual apples-to-apples. > > > >>You won't normally get anything like a Hilbert >>curve, which seems to be more ideal, at least judging from >>the papers out there. >> >> > >Curiously, you can get something surprisingly close, and the experimental >cache simulation results say that it's very close. I was pleasantly >surprisied at how well this fairly dumb (but fast!) algorithm did. > > > >>Speaking of which, I was asking Sung-Eui Yoon about his research on >>cache-oblivious mesh layouts, http://gamma.cs.unc.edu/COL/. Code >>(non-commercial use only, sigh) is at >> >> > >Oops - I missed this reference, sorry Eric. I'll have a read of it and see >if my paper needs updating to include a comparison with these numbers. At >the very least I should mention them. Frankly, *all* of the papers so far >are so close to being perfect that people probably don't care about the >slight difference in results. We're really not vertex-processing bound at >the moment (maybe tri-setup-bound - that's a different problem), so fussing >over a few percent here and there might just be us geeks indulging our >inappropriate optimisation fetishes :-) > > >TomF. > > > > >>-----Original Message----- >>From: gda...@li... >>[mailto:gda...@li...] On >>Behalf Of Eric Haines >>Sent: 11 September 2006 08:57 >>To: Game Development Algorithms >>Subject: Re: [Algorithms] Triangle strips still useful? >> >> >>First, now that this thread has calmed down, thanks very much to >>everyone answering my question. I'll do my best to sum things >>up in the >>book, though I'll probably have to leave out some of the subtleties >>discussed here. >> >>Tom Forsyth wrote about his greedy algorithm (full post at bottom): >> > Yes. There's a vertex->triangle map, and obviously there's a >>triangle->vertex map (indices), but there's no lookahead >> >>Interesting, I was thinking more along the lines of a >>triangle->triangle >>neighbor list and labelling the vertices as to when they were last >>placed in the cache. Starting with an unprocessed triangle, >>examine its >>neighbors and choose the one (if any) whose third (non-shared) vertex >>has the highest vertex label number (i.e. whose third vertex >>was put in >>the cache latest). Then update the vertex label numbers, and put the >>other neighbors on a stack for possible processing later (when a >>triangle has no neighbors that have not already been processed). >>Continue with the new triangle you just added, checking its >>neighbors, >>etc. Of course, I haven't coded it up... >> >>Whatever the case, it seems to me that a greedy approach will >>probably >>give a back-and-forth pattern on a regular grid of triangles, right? >>That is, left-to-right along one row, then right to left on the next, >>and so on. You won't normally get anything like a Hilbert >>curve, which >>seems to be more ideal, at least judging from the papers out >>there. That >>said, it's way easier to code such methods vs. the more involved >>algorithms out there. >> >>Speaking of which, I was asking Sung-Eui Yoon about his research on >>cache-oblivious mesh layouts, http://gamma.cs.unc.edu/COL/. Code >>(non-commercial use only, sigh) is at >>http://gamma.cs.unc.edu/COL/OpenCCL/. I thought I'd pass on >>this tidbit, >>in case it's of interest. >> >>I wrote him: Have you compared it with the D3DXOptimizeFaces function >>provided by Microsoft in DirectX? >> >>His reply: >> >>Yes. The cache miss ratio of our cache-oblivious layout was >>around 10% >>higher than that of D3DXOptimizeFaces when we set a cache >>size 16 during >>rendering the bunny. But, if we set cache size 8 or 64, our >>cache-oblivious layout showed a better cache miss ratio. (Hoppe >>mentioned that D3DXOptimizeFaces was optimized at cache sizes >>12 or 16.) >> >>But, for very irregular models such as power plant model, our layout >>showed better performance even at cache size 16. Probably, the method >>employed in the D3DXOptimizeFaces is not that good for such types of >>models. >> >>You can check out some detail info about comparison at page 6 >>and 7 of >>http://gamma.cs.unc.edu/COL/mesh-layouts-block-based-caches.pdf >> >>---- >> >>Eric >> >> >>Tom Forsyth wrote: >> >> >>>Yes. There's a vertex->triangle map, and obviously there's a >>>triangle->vertex map (indices), but there's no lookahead - >>> >>> >>at each stage, >> >> >>>the algorithm looks at the history of which triangles it >>> >>> >>already added, the >> >> >>>adjacency info, and then decides on the next triangle to >>> >>> >>add, and that's it >> >> >>>- it never backtracks or changes its mind. So fundamentally >>> >>> >>the algorithm is >> >> >>>O(n) (ignoring the effects of CPU data caches on the adjacency map). >>> >>>TomF. >>> >>> >>>-----Original Message----- >>>From: gda...@li... >>>[mailto:gda...@li...] On >>> >>> >>Behalf Of Matt J >> >> >>>Sent: 05 September 2006 12:15 >>>To: Game Development Algorithms >>>Subject: Re: [Algorithms] Triangle strips still useful? >>> >>> >>>Hi Tom, >>> >>>When you say non-lookahead, do you mean your reordering the >>> >>> >>indices based >> >> >>>soley on data from an adjacency buffer? >>> >>>Thanks, >>> >>>Matthew >>> >>> >>>In practice, I've found the simple greedy non-lookahead >>> >>> >>reorderer I did for >> >> >>>the big G gets you within 10% of either Hoppe or the >>> >>> >>Hilbert stuff, works >> >> >>>for a large range of cache sizes and types, and is really >>> >>> >>fast to run (no >> >> >>>lookahead!), which gets quite important now we're looking >>> >>> >>at million-poly >> >> >>>meshes and the like. Once you throw in the randomness of >>> >>> >>real-world meshes >> >> >>> >>> >>> >>-------------------------------------------------------------- >>----------- >> >> >>>Using Tomcat but need to do more? Need to support web >>> >>> >>services, security? >> >> >>>Get stuff done quickly with pre-integrated technology to >>> >>> >>make your job easier >> >> >>>Download IBM WebSphere Application Server v.1.0.1 based on >>> >>> >>Apache Geronimo >> >> >>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057& >> >> >dat=121642 > > >>_______________________________________________ >>GDAlgorithms-list mailing list >>GDA...@li... >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>Archives: >>http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >> >> >> >> > >------------------------------------------------------------------------- >Using Tomcat but need to do more? Need to support web services, security? >Get stuff done quickly with pre-integrated technology to make your job >easier >Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo >http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > >------------------------------------------------------------------------- >Take Surveys. Earn Cash. Influence the Future of IT >Join SourceForge.net's Techsay panel and you'll get the chance to share your >opinions on IT & business topics through brief surveys -- and earn cash >http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > |