RE: [Algorithms] (Multi Layer Terrain) Triangle strips for "broken" square patches
Brought to you by:
vexxed72
Menu
▾
▴
RE: [Algorithms] (Multi Layer Terrain) Triangle strips for "broken" square patches
|
From: Tom F. <tom...@ee...> - 2004-02-17 12:30:58
|
> From: Alen Ladavac >=20 > Sorry, I should have explained the algorithm I'm thinking of. It's the > "recursive graph bisection" (strangely abbreviated as RGB :p=20 > ). What it does > is to find diameter of the graph and split along it. Or in=20 > other words, find > two most distant triangles and center one of the two=20 > submeshes around one of > them. So it wouldn't split the example lenghtways. Any more potential > killers are welcome. ;) Sounds reasonable. > Yes, I get that part, but I wasn't really sure on how you=20 > decide AB-CD vs > CD-AB, since that depends on the choices of A-B vs B-A and C-D vs D-C. > Anyway, I got it answered by one of the authors of original article > (Alexander Bogomjakov). Looks it should be done the other way=20 > around - start > deciding on smaller submeshes. I still have to get hold of their other > article, where he said they explained it in more details. Again, sounds sensible. If you find the article, that would be very interesting. > > I do a brute-force lookahead of then next 6 triangles. It=20 > first tries a > >connected strip-like-thing as a first guess, which gives it=20 > a "best score > so > >far", and then brute-forces from there. >=20 > Do you use connectivity information in this process? If you=20 > are brute-force > testing only vicinity of the last triangle, you should be=20 > O(k*n) where k is > large (depending of number of experiments), but should still=20 > be much better > than O(n^2), right? (When you say it is slow, I assume it is at least > O(n^2).) I do use connectivity information for the first try (I use a = vertex<->tri map for this). The idea is that on average, a well-connected first try = will be close to optimal, so it will cause very early rejection of the = obviously less optimal paths. However, there are cases such as: -Jumping a small distance away and then coming back can give bigger = cache benefits overall. -Going into a dead end and then jumping back out (breaking connectivity) = is better than passing by the dead end because then you don't have to = revisit it later to fill in the gap. -When a section of the mesh is done and there are no more connected = tris, finding the best place to start the next chunk. So you can't exclusively use connection data. Speed is something like O(n^2) - but it's hard to say exactly because of = all the early-outs. If there were no early-outs it would be more like = O(n^7), which is obviously crazy. The graph-splitting and recombination sounds just as good and a lot = quicker - I really don't recommend it to anyone. The one place it might be = better is for wacky things like the PS2 stripification where there is no "cache" = to speak of, and where conventional strippers are poor because they assume = too much - turning corners on the PS2 is much more efficient than normal = strips because it doesn't care about clockwise/anticlockwise stuff. > Alen >=20 >=20 > > > -----Original Message----- > > > From: gda...@li... > > > [mailto:gda...@li...] On > > > Behalf Of Alen Ladavac > > > Sent: 16 February 2004 09:36 > > > To: gda...@li... > > > Subject: Re: [Algorithms] (Multi Layer Terrain) Triangle > > > strips for "broken" square patches > > > > > > > > > >I had a look at it. It's pretty cool, but the maths for > > > either method is > > > >daunting. > > > > > > Actually, recursive cutting should basically be very simple. > > > Though putting > > > it back together afterwards might be complicated. I just > > > don't get the point > > > where they say "Make sure, though, that the exit point from > > the first > > > submesh is close to the entry point into the second=20 > submesh." Sounds > > > non-trivial. Guess I'll go and ask them for a hint. > > > > > > > I thought about implementing the recursive-cut=20 > algorithm, since it > > > > sounds like it could be a lot faster than the greedy > > > lookahead I currently > > > > > > Yup, it should be O(n*log n), I believe. > > > > > > > > > >have. But it's probably not significantly better in > > output, since I'm > > > >getting 0.6-0.7 verts/tri, which is about as good as > > > sensibly possible. > > > >Theoretically I could shave 0.1 or 0.2 off that depending on > > > the mesh, but > > > > > > You are talking about ACMR for a 16-deep vertex FIFO cache, > > > or something > > > else? Theoretically, 0.5+Omega(1/k) should be best possible > > > result. So I'd > > > say you are getting very close to it. > > > > > > Alen > > > > > > > > > > -----Original Message----- > > > > From: gda...@li... > > > > [mailto:gda...@li...] On > > > > Behalf Of Alen Ladavac > > > > Sent: 15 February 2004 09:38 > > > > To: gda...@li... > > > > Subject: Re: [Algorithms] (Multi Layer Terrain) Triangle > > > > strips for "broken" square patches > > > > > > > > > > > > We did report both the leaks and the performance. They said > > > > they'll fix it. > > > > But in the mean time, I thought it would be useful to let > > > > people know it > > > > leaks memory, so they don't have to find out the hard way > > > > (like we did :/). > > > > > > > > I don't think we'll go with fixing the source code for > > > > nvtristrip ourselves > > > > (especially since it uses stl - sic! :) ). > > > > > > > > But, I've been thinking of this idea of using just=20 > cache-coherency > > > > improvements, instead of full stripping. Now that it was > > > > mentioned again, it > > > > got me thinking of it again. I recently found a paper titled > > > > "Universal > > > > Rendering Sequences for Transparent Vertex Caching of > > > > Progressive Meshes" by > > > > Alexander Bogomjakov and Craig Gotsman. > > > > (http://www.cs.technion.ac.il/~gotsman/caching/) It is very > > > > similar to what > > > > Tom Forsyth suggested with space-filling curves, just that > > > > this works for > > > > general meshes. Has anyone tried something like that? > > > > > > > > Alen > > > > > > > > > > > > > > > > ----- Original Message ----- > > > > From: "Gary McTaggart" <ga...@va...> > > > > To: <gda...@li...> > > > > Sent: Friday, February 13, 2004 19:05 > > > > Subject: RE: [Algorithms] (Multi Layer Terrain) Triangle > > > > strips for "broken" > > > > square patches > > > > > > > > > > > > We use NVTristrip for preprocessing to generate cache > > > > friendly trilists. > > > > I wouldn't spend much more effort on tristripping than that > > > if you can > > > > live with the time that it takes to process your data. > > If there are > > > > leaks in their code, I believe that you can download the > > > > source code for > > > > it, or better yet, talk to Nvidia and get them to fix it. > > They are > > > > pretty good about fixing their tools if they are broken. Of > > > > course, if > > > > you are trying to strip at runtime, then you'll probably > > > want to find > > > > something else. > > > > > > > > Gary > > > > > > > > > -----Original Message----- > > > > > From: gda...@li... > > > > > [mailto:gda...@li...] On > > > > > Behalf Of Ivan-Assen Ivanov > > > > > Sent: Friday, February 13, 2004 5:19 AM > > > > > To: gda...@li... > > > > > Subject: RE: [Algorithms] (Multi Layer Terrain) Triangle > > > > > strips for "broken" square patches > > > > > > > > > > > Actually, nvtristrip produces great results, but there is > > > > one more > > > > > > problem with it (apart from the slowness), at that is > > > > memory leaks. > > > > > > Seems it doesn't free some of its buffers sometimes. We > > > > > actually had > > > > > > to disable it in order to enable batch preprocessing at all. > > > > > > Otherwise, we cannot process a large list of meshes at > > > > > once, because > > > > > > we run out of memory. :/ I would be happy to find out that > > > > > the problem > > > > > > is on our side, but after some time checking, we couldn't > > > > > find anything. Are you sure it works ok for you? > > > > > > > > > > I was JUST finishing a long whiney message along the lines of > > > > > "is nvtristrip leaking like a sieve, or am I an idiot?". > > > > > Whew, glad to find out that maybe after all it's not me :-) > > > > > > > > > > NVTriStrip is slow, but it leaks so many small blocks, that > > > > > it takes more time for our debug memory manager to print out > > > > > the leak alerts than for the actual stripification... > > > > > > > > > > > > > > > > > > > > > > > > > ------------------------------------------------------- > > > > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > > > > Build and deploy apps & Web services for Linux with a free > > > > > DVD software kit from IBM. Click Now! > > > > > http://ads.osdn.com/?ad_id=3D1356&alloc_id=3D3438&op=3Dclick > > > > > _______________________________________________ > > > > > GDAlgorithms-list mailing list > > > > > GDA...@li... > > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > > Archives: > > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > > > > > > > > > > > > > > > > > > ------------------------------------------------------- > > > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > > > Build and deploy apps & Web services for Linux with > > > > a free DVD software kit from IBM. Click Now! > > > > http://ads.osdn.com/?ad_id=1356&alloc_id438&op=3Dclick > > > > _______________________________________________ > > > > GDAlgorithms-list mailing list > > > > GDA...@li... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > > > > > > > > > > > > > > ------------------------------------------------------- > > > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > > > Build and deploy apps & Web services for Linux with > > > > a free DVD software kit from IBM. Click Now! > > > > http://ads.osdn.com/?ad_id=3D1356&alloc_id=3D3438&op=3Dclick > > > > _______________________________________________ > > > > GDAlgorithms-list mailing list > > > > GDA...@li... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > > > > > > > > > > > > ------------------------------------------------------- > > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > > Build and deploy apps & Web services for Linux with > > > a free DVD software kit from IBM. Click Now! > > > http://ads.osdn.com/?ad_id=1356&alloc_id438&op=3Dclick > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > > > > > > > > > > ------------------------------------------------------- > > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > > Build and deploy apps & Web services for Linux with > > > a free DVD software kit from IBM. Click Now! > > > http://ads.osdn.com/?ad_id=3D1356&alloc_id=3D3438&op=3Dclick > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDA...@li... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > > > > > > > ------------------------------------------------------- > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > Build and deploy apps & Web services for Linux with > > a free DVD software kit from IBM. Click Now! > > http://ads.osdn.com/?ad_id=1356&alloc_id438&op=3Dclick > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > > > > > > ------------------------------------------------------- > > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > > Build and deploy apps & Web services for Linux with > > a free DVD software kit from IBM. Click Now! > > http://ads.osdn.com/?ad_id=3D1356&alloc_id=3D3438&op=3Dclick > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >=20 >=20 >=20 > ------------------------------------------------------- > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > Build and deploy apps & Web services for Linux with > a free DVD software kit from IBM. Click Now! > http://ads.osdn.com/?ad_id=1356&alloc_id438&op=3Dclick > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >=20 >=20 > ------------------------------------------------------- > SF.Net is sponsored by: Speed Start Your Linux Apps Now. > Build and deploy apps & Web services for Linux with > a free DVD software kit from IBM. Click Now! > http://ads.osdn.com/?ad_id=3D1356&alloc_id=3D3438&op=3Dclick > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 |