Thread: Re: [Algorithms] VIPM With T&L - what about roam
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Sam K. <sa...@ip...> - 2000-09-06 20:00:51
|
Ok cool, thats what I hoped. This brings me to another thought... Say you had a roam implementation that subdivided down (ignoring camera distance, just using landscape variance) to a fixed level say 500,000 vertices or so and stored them on card for T&L. *then* on subsequent passes of the roam bintree, generate indexed lists into that hardware vertex pool based on the camera distance. This means you get true distance based roam LOD and cached t&l of the used verticies right? sam -----Original Message----- From: Cem Cebenoyan <CCe...@nv...> To: 'sa...@ip...' <sa...@ip...> Date: 06 September 2000 7:47 PM Subject: Re: [Algorithms] VIPM With T&L >Hi Sam, > >a) No, the card doesn't have to TnL the highest res model. TnL cards do TnL >"on demand" so that you only pay for the vertices that are indexed. > >b) All 1000 spaceships can share the same set of vertices, but they must >have their own separate index lists, unless you want them to all be at the >same LOD at all times. Again, only the indexed vertices will be >transformed, but they will be transformed separately for every instance of >the model (unless, of course, there is some vertex cache reuse) > >Let me know if you have any further questions about VIPM. > >-Cem >NVIDIA Developer Relations > >-----Original Message----- >From: Sam Kuhn [mailto:sa...@ip...] >Sent: Wednesday, September 06, 2000 10:49 AM >To: gda...@li... >Subject: [Algorithms] VIPM With T&L > > >Hi all, > >This is bound to have been covered a gazillion times before, but I'm having >trouble searching the archives: >I'm fairly new to VIPM, and have a couple of questions: > >a) I've read that its possible to throw the vertices of a model at the 3d >card (So T&L is possible) >And just maintain the indexed lists into that vertex array using collapses >and merges. >Doesn't that mean you have to make the card (hardware) transform all of the >vertices in the highest resolution representation of the model each frame? >even though the current lod might only need say 100.. or am I missing >something? > >b) Say you wanted 1000 spaceships on screen sharing a single VIPM model, how >does this work with (a)? >Does the card have to transform all the original (high lod) vertices 1000 >times to screen space? > >Is it that the hardware T&L only transforms vertices that are pointed to by >the supplied indexed lists? or what > >Thanks, > >sam >sa...@ip... > > >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Sam K. <sa...@ip...> - 2000-09-06 20:48:25
|
Ok cool, thats what I hoped. This brings me to another thought... Say you had a roam implementation that subdivided down (ignoring camera distance, just using landscape variance) to a fixed level say 500,000 vertices or so and stored them on card for T&L. *then* on subsequent passes of the roam bintree, generate indexed lists into that hardware vertex pool based on the camera distance. This means you get true distance based roam LOD and cached t&l of the used verticies right? sam >-----Original Message----- >From: Cem Cebenoyan <CCe...@nv...> >To: 'sa...@ip...' <sa...@ip...> >Date: 06 September 2000 7:47 PM >Subject: Re: [Algorithms] VIPM With T&L > > >>Hi Sam, >> >>a) No, the card doesn't have to TnL the highest res model. TnL cards do >TnL >>"on demand" so that you only pay for the vertices that are indexed. >> >>b) All 1000 spaceships can share the same set of vertices, but they must >>have their own separate index lists, unless you want them to all be at the >>same LOD at all times. Again, only the indexed vertices will be >>transformed, but they will be transformed separately for every instance of >>the model (unless, of course, there is some vertex cache reuse) >> >>Let me know if you have any further questions about VIPM. >> >>-Cem >>NVIDIA Developer Relations >> >>-----Original Message----- >>From: Sam Kuhn [mailto:sa...@ip...] >>Sent: Wednesday, September 06, 2000 10:49 AM >>To: gda...@li... >>Subject: [Algorithms] VIPM With T&L >> >> >>Hi all, >> >>This is bound to have been covered a gazillion times before, but I'm having >>trouble searching the archives: >>I'm fairly new to VIPM, and have a couple of questions: >> >>a) I've read that its possible to throw the vertices of a model at the 3d >>card (So T&L is possible) >>And just maintain the indexed lists into that vertex array using collapses >>and merges. >>Doesn't that mean you have to make the card (hardware) transform all of the >>vertices in the highest resolution representation of the model each frame? >>even though the current lod might only need say 100.. or am I missing >>something? >> >>b) Say you wanted 1000 spaceships on screen sharing a single VIPM model, >how >>does this work with (a)? >>Does the card have to transform all the original (high lod) vertices 1000 >>times to screen space? >> >>Is it that the hardware T&L only transforms vertices that are pointed to by >>the supplied indexed lists? or what >> >>Thanks, >> >>sam >>sa...@ip... >> >> >>_______________________________________________ >>GDAlgorithms-list mailing list >>GDA...@li... >>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list >> > > |
|
From: Tom F. <to...@mu...> - 2000-09-11 14:40:29
|
Yes. Though ROAM, in other peoples' experience, is limited by the ROAM algorithm running on the CPU, not by a T&L graphics card. So your real bottleneck is the CPU. Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > -----Original Message----- > From: Sam Kuhn [mailto:sa...@ip...] > Sent: 06 September 2000 21:48 > To: gda...@li... > Subject: RE: [Algorithms] VIPM With T&L - what about roam > > > > > Ok cool, thats what I hoped. > > This brings me to another thought... > > Say you had a roam implementation that subdivided down > (ignoring camera > distance, just using landscape variance) to a fixed level say 500,000 > vertices or so and stored them on card for T&L. *then* on > subsequent passes > of the roam bintree, generate indexed lists into that > hardware vertex pool > based on the camera distance. This means you get true > distance based roam > LOD and cached t&l of the used verticies right? > > sam |
|
From: Sam K. <sa...@ip...> - 2000-09-11 22:06:11
|
Yeah, but surely the roam algorithm isn't much slower than vipm's.. I mean roam and vipm are very similar. They both use frame-frame index list coherency and both use splits and merges. My index calculation time is tiny compared to the software D3D tranform time. Anyway, if one was going to implement roam, using T&L would be much faster than not. and free up much cpu time for the roam calculations. Same as using T&L for vipm. This leads me to another question: In VIPM, using T&L hardware you evidently can have a huge VB and supply a small index list. and thing will run swell because the card only transforms and lights the indexed vertices. Using software transforms i.e. D3DHAL, this isn't the case (why not?) D3D tranforms all the vertices in the VB regardless of the passed index list. So to get round this in you store the verts in first-last split order and pass in a vertex range. D3D Tranforms the needed verts and using the index list to render them. O.K. Fine. BUT, what about software transforms in situations where the split order is not known, i.e. VDPM or ROAM where polygons are denser towards the camera? you cant specify a range of verts for the software transform because it quite literally could be any of them. HT&L is fine because of the only transform indexed verts thing. Is there a solution to this? sam -----Original Message----- From: Tom Forsyth <to...@mu...> To: gda...@li... <gda...@li...> Date: 11 September 2000 3:59 PM Subject: RE: [Algorithms] VIPM With T&L - what about roam >Yes. Though ROAM, in other peoples' experience, is limited by the ROAM >algorithm running on the CPU, not by a T&L graphics card. So your real >bottleneck is the CPU. > >Tom Forsyth - Muckyfoot bloke. >Whizzing and pasting and pooting through the day. > >> -----Original Message----- >> From: Sam Kuhn [mailto:sa...@ip...] >> Sent: 06 September 2000 21:48 >> To: gda...@li... >> Subject: RE: [Algorithms] VIPM With T&L - what about roam >> >> >> >> >> Ok cool, thats what I hoped. >> >> This brings me to another thought... >> >> Say you had a roam implementation that subdivided down >> (ignoring camera >> distance, just using landscape variance) to a fixed level say 500,000 >> vertices or so and stored them on card for T&L. *then* on >> subsequent passes >> of the roam bintree, generate indexed lists into that >> hardware vertex pool >> based on the camera distance. This means you get true >> distance based roam >> LOD and cached t&l of the used verticies right? >> >> sam >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Jim O. <j.o...@in...> - 2000-09-12 06:38:58
|
> ...
> BUT, what about software transforms in situations where the split order is
> not known, i.e. VDPM or ROAM where polygons are denser towards the camera?
> you cant specify a range of verts for the software transform because it
> quite literally could be any of them. HT&L is fine because of the only
> transform indexed verts thing.
>
> Is there a solution to this?
You could stream just the used vertices into a 'dynamic' vertexbuffer (i.e.
one you are using with the DISCARDCONTENTS paradigm) before rendering each
frame. Something like this:
(pseudo code warnings apply)
---- 8< ----
void RenderDevice::Draw(Array<Vertex> &verts, Array<ushort> &indices) {
struct VertInfo {
bool isUsed; // is this vertex used?
short newIndex; // new index of this vertex (after streaming).
};
static VertInfo vertInfos[/* max. nr. of verts */];
static short newIndices[/* max. nr. of indices */];
// Clear all vertex info structures.
memset(vertInfos, 0, sizeof(VertInfo) * /* max. nr. of verts */);
// Rebuild the vertex list, using *only* used vertices.
for (short i = 0; i < indices.GetLength(), i++) {
// Get current vertex index.
index = indices[i];
// Check if we're using this vertex already...
if (vertInfos[index].isUsed == false) {
// If not, mark this vertex as used and remember it's index.
vertInfos[index].newIndex = i;
vertInfos[index].isUsed = true;
newIndices[i] = i;
// Write a vertex to our dynamic vertexbuffer
mDynVB->WriteVertex(i, verts[index]);
}
// Remap index.
newIndices[i] = verts[index].newIndex;
}
// Draw everything.
Draw(mDynVB, newIndices, indices.GetLength());
}
---- 8< ----
It remains to be seen whether the above will actually speed up rendering,
but it could.
Jim Offerman
Innovade
The Atlantis Project
http://www.theatlantisproject.com
|
|
From: Johan H. <jh...@mw...> - 2000-09-12 08:58:20
|
Hi since there is a few discussions of ROAM on this list. Has anyone seen a decent implementation of ROAM? What is the amount of cpu time used by the algorithm per frame for a standard scene with about 3000 triangles in the view? The first publication on roam was horribly slow, and in my mind not worth using. Has that changed? Johan Hammes |
|
From: Martin F. <mf...@ac...> - 2000-09-12 09:20:21
|
VIPM stands for view independant progressive meshing. It does not take into account the camera's position or orientation, just a parameter telling it how many polys to display, this can be a function of distance or number of baddies on screen or pretty much anything. VIPM is great for the reasons outlined below, you always transform used verts and no more. The problem with progressive meshing is that because it is view dependant it becomes very expensive. I can't speak for ROAM because I don't have a complete enough understanding of how it works. Here's a question though. If I want to VIPM a heightfield is there anyway to maintain a minimal indexed triangle strip. By minimal I mean as few strips and as few degenerate triangles as possible. A plain heightfield strips very well obviously with one strip per tile, (Assuming a quadtree split) with best case 1 degerenrate triangle per coulomb. It's all swings and roundabouts, there are cruder LOD techniques for heightfields which strip very nicely so I suppose it depends on whether the bottleneck becomes the transforms and extra vertex data or the actual polygon drawing. My current thinking on PC and PS2 is that it's probably better to maintain longer strips and draw more polys. Any thoughts? Cheers, Martin -----Original Message----- From: Sam Kuhn [mailto:sa...@ip...] Sent: 11 September 2000 15:06 To: gda...@li... Subject: Re: [Algorithms] VIPM With T&L - what about roam Yeah, but surely the roam algorithm isn't much slower than vipm's.. I mean roam and vipm are very similar. They both use frame-frame index list coherency and both use splits and merges. My index calculation time is tiny compared to the software D3D tranform time. Anyway, if one was going to implement roam, using T&L would be much faster than not. and free up much cpu time for the roam calculations. Same as using T&L for vipm. This leads me to another question: In VIPM, using T&L hardware you evidently can have a huge VB and supply a small index list. and thing will run swell because the card only transforms and lights the indexed vertices. Using software transforms i.e. D3DHAL, this isn't the case (why not?) D3D tranforms all the vertices in the VB regardless of the passed index list. So to get round this in you store the verts in first-last split order and pass in a vertex range. D3D Tranforms the needed verts and using the index list to render them. O.K. Fine. BUT, what about software transforms in situations where the split order is not known, i.e. VDPM or ROAM where polygons are denser towards the camera? you cant specify a range of verts for the software transform because it quite literally could be any of them. HT&L is fine because of the only transform indexed verts thing. Is there a solution to this? sam -----Original Message----- From: Tom Forsyth <to...@mu...> To: gda...@li... <gda...@li...> Date: 11 September 2000 3:59 PM Subject: RE: [Algorithms] VIPM With T&L - what about roam >Yes. Though ROAM, in other peoples' experience, is limited by the ROAM >algorithm running on the CPU, not by a T&L graphics card. So your real >bottleneck is the CPU. > >Tom Forsyth - Muckyfoot bloke. >Whizzing and pasting and pooting through the day. > >> -----Original Message----- >> From: Sam Kuhn [mailto:sa...@ip...] >> Sent: 06 September 2000 21:48 >> To: gda...@li... >> Subject: RE: [Algorithms] VIPM With T&L - what about roam >> >> >> >> >> Ok cool, thats what I hoped. >> >> This brings me to another thought... >> >> Say you had a roam implementation that subdivided down >> (ignoring camera >> distance, just using landscape variance) to a fixed level say 500,000 >> vertices or so and stored them on card for T&L. *then* on >> subsequent passes >> of the roam bintree, generate indexed lists into that >> hardware vertex pool >> based on the camera distance. This means you get true >> distance based roam >> LOD and cached t&l of the used verticies right? >> >> sam >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Pai-Hung C. <pa...@ac...> - 2000-09-12 09:31:08
|
> Here's a question though. If I want to VIPM a heightfield is there anyway to > > maintain a minimal indexed triangle strip. By minimal I mean as few strips > and > as few degenerate triangles as possible. A plain heightfield strips very > well > obviously with one strip per tile, (Assuming a quadtree split) with best > case > 1 degerenrate triangle per coulomb. > > It's all swings and roundabouts, there are cruder LOD techniques for > heightfields ...... Could you elaborate a little bit on how to get "1 degenerated triangle per tile"? Thank you, Paihung |
|
From: Jamie F. <j.f...@re...> - 2000-09-12 09:31:36
|
> It's all swings and roundabouts, there are cruder LOD techniques for > heightfields > which strip very nicely so I suppose it depends on whether the bottleneck > becomes > the transforms and extra vertex data or the actual polygon drawing. My > current > thinking on PC and PS2 is that it's probably better to maintain longer > strips and > draw more polys. Any thoughts? As we can draw a poly in the time it takes to use fine grain techniques to tell us whether or not we should draw it, that's our plan :) Jamie Virus Scanned and cleared ok |
|
From: Paul F. <pf...@at...> - 2000-09-12 10:52:38
|
Martin Fuller wrote: > VIPM is great for the reasons outlined below, you always transform used > verts > and no more. The problem with progressive meshing is that because it is view > dependant it becomes very expensive. In this case we can just chop the vipm'ed model into many smaller vipm segments thereby approximating a VDPM but using a far smaller amount of cpu time. > Here's a question though. If I want to VIPM a heightfield is there anyway to > maintain a minimal indexed triangle strip. By minimal I mean as few strips > and as few degenerate triangles as possible. A plain heightfield strips very > well obviously with one strip per tile, (Assuming a quadtree split) with best > case 1 degerenrate triangle per coulomb. Hmmm... Triangle strips and VIPM tend not to mix very well, although having said that there was talk a while ago about using degenrate tris to maintain stip-ability through edge-collpases and all. Maybe someone else can go over that idea again? :-) > It's all swings and roundabouts, there are cruder LOD techniques for > heightfields which strip very nicely so I suppose it depends on whether the > bottleneck > becomes the transforms and extra vertex data or the actual polygon drawing. My > > current thinking on PC and PS2 is that it's probably better to maintain longer > > strips and draw more polys. Any thoughts? With gfx cards getting faster and faster there is less and less time to worry about what to draw, so we keep needing faster algos ;-) I was thinking about a kind of ROAM on the PS2 the other day. If sending things to the VU is the bottle-neck, then perhaps sending a bitmap and triangulating that in the VU is a good idea? As long as you spend hardly any time managing the bitmap, I suppose.... Cheers, Paul. |
|
From: Jamie F. <j.f...@re...> - 2000-09-12 11:11:30
|
> I was thinking about a kind of ROAM on the PS2 the other day. If sending things > to the VU is the bottle-neck, then perhaps sending a bitmap and triangulating > that > in the VU is a good idea? As long as you spend hardly any time managing the > bitmap, I suppose.. I'd be happy to continue this discussion on the PS2 newsgroups. Unfortunately, last time I tried LOD discussions there, nobody wanted to say anything (particularly) interesting. My apologies to those who can't go there, but to really deal with such suggestions we'd need to get into technical details that I'm sure are covered by the NDA. Jamie Virus Scanned and cleared ok |
|
From: Jim O. <j.o...@in...> - 2000-09-12 18:38:10
|
> It's all swings and roundabouts, there are cruder LOD techniques for > ... > draw more polys. Any thoughts? These days, with hardware evolving so fast, it may very well be more rewarding to spend your time writing something which will increase the overall speed of your (rendering) engine than to spend time working on something which will only speed up rendering of a certain type of geometry. Jim Offerman Innovade The Atlantis Project http://www.theatlantisproject.com |
|
From: Martin F. <mf...@ac...> - 2000-09-12 10:20:37
|
I assume you mean a single degenerate per coulumb per tile. (which was what I was talking about) Suppose you have a 4x4 heightfield section. If you draw 16 points on a piece of paper, start at the bottom left corner, connect to the point to the right of this, then the point immediatly above the start point, build a vertical strip and you will see at the top in order to get onto the next coulomb you only have to use 1 degenerate triangle. Infact nDegeneratesTriangles = nCoulombs - 1. While a 4x4 is impractically small on current hardware this gets the point made. The larger your tile the better the ratio of degenerates to normal triangles becomes. -----Original Message----- From: Pai-Hung Chen [mailto:pa...@ac...] Sent: 12 September 2000 02:24 To: gda...@li... Subject: Re: [Algorithms] VIPM With T&L - what about roam > Here's a question though. If I want to VIPM a heightfield is there anyway to > > maintain a minimal indexed triangle strip. By minimal I mean as few strips > and > as few degenerate triangles as possible. A plain heightfield strips very > well > obviously with one strip per tile, (Assuming a quadtree split) with best > case > 1 degerenrate triangle per coulomb. > > It's all swings and roundabouts, there are cruder LOD techniques for > heightfields ...... Could you elaborate a little bit on how to get "1 degenerated triangle per tile"? Thank you, Paihung _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Tom F. <to...@mu...> - 2000-09-12 10:56:57
|
There were some thinking-out-loud discussions between myself and Charles Bloom a few weeks ago on a similar subject (doing VIPM with strips rather than lists). If the archives don't work, and you don't have the old messages to search through, I could probably dig them up and repost them. Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > From: Martin Fuller [mailto:mf...@ac...] [snip] > Here's a question though. If I want to VIPM a heightfield is > there anyway to > > maintain a minimal indexed triangle strip. By minimal I mean > as few strips > and > as few degenerate triangles as possible. A plain heightfield > strips very > well > obviously with one strip per tile, (Assuming a quadtree > split) with best > case > 1 degerenrate triangle per coulomb. > > It's all swings and roundabouts, there are cruder LOD techniques for > heightfields > which strip very nicely so I suppose it depends on whether > the bottleneck > becomes > the transforms and extra vertex data or the actual polygon drawing. My > current > thinking on PC and PS2 is that it's probably better to maintain longer > strips and > draw more polys. Any thoughts? > Cheers, > Martin |
|
From: Brian M. <bma...@ra...> - 2000-09-12 17:33:32
|
I've come across 2 papers recently that are worth thinking about with regards VIPM. Efficiently Computing and Updating Triangle Strips for Real-Time Rendering Jihad El-Sana, Francine Evans, Amitabh Varshney, Steven Skiena, Elvir Azanli (Get it from this link, under publications.) http://www.cs.bgu.ac.il/~el-sana/ This is more work like strip, including 'Issues in Integrating Triangle Strips with Multiresolution Hierarchies' which introduces Skip-Strips for maintaining triangle strips as you do edge collapses. Not specific to VIPM as it deals with VDPM and Merge Trees, but well worth a look. Coarse View-Dependant Levels of Detail for Hierarchical and Deformable Models Dieter Schmalsteig, Anton Fuhrmann (Get it from this link, under publications some way down...) http://www.cg.tuwien.ac.at/staff/DieterSchmalstieg.html This includes a neat way of producing chunked VIPM like Charles Bloom demonstrates on his web site (and the discussion here.) The interesting bit is that the authors assign vertices to VIPM clumps and not triangles which allows for some simplification on the boundary. I won't go into details here as the authors do a much better job of explaining it than I can. Hopefully everyone interested in the VIPM discussions will find these of interest. -Brian. [snip] > There were some thinking-out-loud discussions between myself and Charles > Bloom a few weeks ago on a similar subject (doing VIPM with strips rather > than lists). If the archives don't work, and you don't have the old messages > to search through, I could probably dig them up and repost them. > > Tom Forsyth - Muckyfoot bloke. > Whizzing and pasting and pooting through the day. [snip] |
|
From: Sam K. <sa...@ip...> - 2000-09-12 19:15:37
|
Jim,
I though of exactly the same thing a couple of hours after I posed my last
message!
This will certainly do the trick. thanks.
sam
-----Original Message-----
From: Jim Offerman <j.o...@in...>
To: gda...@li...
<gda...@li...>
Date: 12 September 2000 7:50 AM
Subject: Re: [Algorithms] VIPM With T&L - what about roam
>> ...
>> BUT, what about software transforms in situations where the split order
is
>> not known, i.e. VDPM or ROAM where polygons are denser towards the
camera?
>> you cant specify a range of verts for the software transform because it
>> quite literally could be any of them. HT&L is fine because of the only
>> transform indexed verts thing.
>>
>> Is there a solution to this?
>
>You could stream just the used vertices into a 'dynamic' vertexbuffer (i.e.
>one you are using with the DISCARDCONTENTS paradigm) before rendering each
>frame. Something like this:
>
>(pseudo code warnings apply)
>
>---- 8< ----
>void RenderDevice::Draw(Array<Vertex> &verts, Array<ushort> &indices) {
>
> struct VertInfo {
> bool isUsed; // is this vertex used?
> short newIndex; // new index of this vertex (after streaming).
> };
>
> static VertInfo vertInfos[/* max. nr. of verts */];
> static short newIndices[/* max. nr. of indices */];
>
> // Clear all vertex info structures.
> memset(vertInfos, 0, sizeof(VertInfo) * /* max. nr. of verts */);
>
> // Rebuild the vertex list, using *only* used vertices.
> for (short i = 0; i < indices.GetLength(), i++) {
> // Get current vertex index.
> index = indices[i];
> // Check if we're using this vertex already...
> if (vertInfos[index].isUsed == false) {
> // If not, mark this vertex as used and remember it's
index.
> vertInfos[index].newIndex = i;
> vertInfos[index].isUsed = true;
> newIndices[i] = i;
> // Write a vertex to our dynamic vertexbuffer
> mDynVB->WriteVertex(i, verts[index]);
> }
> // Remap index.
> newIndices[i] = verts[index].newIndex;
> }
> // Draw everything.
> Draw(mDynVB, newIndices, indices.GetLength());
>}
>---- 8< ----
>
>It remains to be seen whether the above will actually speed up rendering,
>but it could.
>
>Jim Offerman
>Innovade
>
>
>The Atlantis Project
>http://www.theatlantisproject.com
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
|
|
From: Tom F. <to...@mu...> - 2000-09-12 19:24:38
|
Cool. I'll have a look at the second one of those. The first one (skipstrips) was discussed here a while back, and led to me burbling this, which bears repeating for those who recently joined us (especially as someone asked for it): << Hmmmm... interesting. And got me thinking. I have a bit of a knee-jerk response to strips, because of their worse-than-list vertex caching (up to twice as bad). However, since normal VIPM pretty much destroys the vertex cache anyway, this argument doesn't hold much water! I think the fundamental difference this approach takes is abandoning the attempt to ditch collapsed tris as early as possible, which is what forces the re-ordering of the tris that destroys the vertex cache performance of "standard" VIPM. And thinking about it, that's fair enough. This still bins tris, but by making them degenerate, rather than have them fall off the end of the list and not feeding them to the chip at all. So you still incur the cost of sending the indices, but not the clipping, setup costs, etc associated with a triangle. But of course the bandwidth cost of the indices is tiny compared to the bandwidth of the vertices, and if by sending (say) double the number of indices, you can reduce the number of vertex resends (i.e. how well the vertex cache is working) by even a small amount, you win! The rejection of degenerate tris is lightning-fast (done right at the front-end I would assume - three 16-bit compares), and in parallel with all the "expensive" stuff, so doubling the number of times it does that is not going to affect performance in any measurable way I would guess. So having stated that I dislike strips, I see no reason not to switch the algorithm back to using indexed lists. Arrange your lists optimally for cache use, and do as the algorithm below says - make the binned ones degenerate, and move the others, just like a normal VIPM rout. The only difference from the routine that Charles has in his tutorial is that you don't reduce the number of tris, and when generating the change list, you need to include an index change that makes the binned triangle degenerate. Wow - that's pretty easy, and vertex cache efficiency is nicely maintained all the way through the collapses. A few points that need mulling over: (1) Using indexed lists, you need to make more index changes per collapse than for strips. Three times as many, I think - not 100% sure. This means slightly larger collapse information, slightly more of a cache hit. However, the collapse info is linear, and so very cache-friendly, and since the aim is to be vertex-cache friendly with our tris, the indices that need changing are likely to be close together as well, or at least in just two parts of the index list, so again fairly cache-friendly (remember - it's stepping outside the cache _once_ that hurts - subsequent accesses to that area are very cheap). So actually not much more expensive than strips I think. And better vertex cache performance (using the "fractal gasket" traversal method that I still can't figure out for arbitrary meshes). (2) Once a tri has been made degenerate, does it need to be involved in further collapses? For example, once a tri 1,2,3 has been made into 1,1,3, do we need to update it when a subsequent collapse bins vertex 3? On some hardware, the degenerate rejection may be done right up-front on the indices, and that triangle never makes it any further, so even though it references vertex 3, because no non-degenerate tri ever references it, vertex 3 is never loaded. However, some hardware may not do the rejection until after the vertex cache fetch, which means that vertex 3 gets fetched, and possible T&L'd, even though it is then never used. If the latter, then you may be better off doing slightly more index edits to "fix" already-degenerate tris so that they only reference used vertices, and having more collapse info. Tricky - I can't decide which option has the worse worst-case performance. Maybe having both versions and runtime testing at load time would be the best option. Compared to "my" two-part method, I think it's a lot simpler. The more I think about the two-part scheme, the more I spot gotchas, and tris that need including in the "slow" pool, the more fragmented the remaining "static" tris get (more fragmentation = less vertex-cache coherency). The advantage that my two-part method retains is the ability to share lots of the index data between instances of objects, which will be a definate advantage in some cases. But it is more complex, and my feeling is that it will achieve poorer vertex caching than this new method. >> Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > -----Original Message----- > From: Brian Marshall [mailto:bma...@ra...] > Sent: 12 September 2000 18:28 > To: gda...@li... > Subject: RE: [Algorithms] VIPM With T&L - what about roam > > > I've come across 2 papers recently that are worth thinking about with > regards VIPM. > > Efficiently Computing and Updating Triangle Strips for > Real-Time Rendering > Jihad El-Sana, Francine Evans, Amitabh Varshney, Steven > Skiena, Elvir > Azanli > > (Get it from this link, under publications.) > http://www.cs.bgu.ac.il/~el-sana/ > > This is more work like strip, including 'Issues in > Integrating Triangle > Strips with Multiresolution Hierarchies' which introduces > Skip-Strips for > maintaining triangle strips as you do edge collapses. Not > specific to VIPM > as it deals with VDPM and Merge Trees, but well worth a look. > > Coarse View-Dependant Levels of Detail for Hierarchical and Deformable > Models > Dieter Schmalsteig, Anton Fuhrmann > (Get it from this link, under publications some way down...) > http://www.cg.tuwien.ac.at/staff/DieterSchmalstieg.html > > This includes a neat way of producing chunked VIPM like > Charles Bloom > demonstrates on his web site (and the discussion here.) The > interesting bit > is that the authors assign vertices to VIPM clumps and not > triangles which > allows for some simplification on the boundary. I won't go > into details here > as the authors do a much better job of explaining it than I can. > > Hopefully everyone interested in the VIPM discussions > will find these of > interest. > > -Brian. > > [snip] > > > There were some thinking-out-loud discussions between > myself and Charles > > Bloom a few weeks ago on a similar subject (doing VIPM with > strips rather > > than lists). If the archives don't work, and you don't have the old > messages > > to search through, I could probably dig them up and repost them. > > > > Tom Forsyth - Muckyfoot bloke. > > Whizzing and pasting and pooting through the day. > > [snip] > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Brian M. <bma...@ra...> - 2000-09-13 06:50:19
|
I've been thinking about this more. The requirements for the hardware I'm working with are somewhat different - I get maximum benefit from very long strips, since the hardware has a very different caching scheme to G-Force etc. I'm currently edging towards trying a combination of skip strips and your suggestion Tom, of precomputed strips for various levels. The idea would be to precompute good sets of strips at reasonable values, and use skip strips to maintain the strips during edge collapses. During PM computation you start with doing a full stripification of the model. Then as you do each collapse you rate the current set of strips - how many degeneracies, how long etc. So when the strip quality reaches a user set threshold you regenerate the strips. That way the user can set the trade-off between memory usage (for extra sets of strips.) and rendering efficiency. For an ultimate version you could recompute a new set of strips for each edge collapse to compare the efficiency of the current skip-strips against. Then you can decide exactly when to issue new strips. Not something to do when the art team are working on the model, but should work great overnight. There are a couple of problems I can see: 1. The edge collapse records get more complex - you need to issue sets of strips as well. 2. The runtime memory state required is somewhat larger - you may need 2 sets of strips (the second having excess degenerate tri's removed for efficiency), as well as more complex collapse records and extra data for the sets of strips to restart things. -Brian. > Cool. I'll have a look at the second one of those. The first one > (skipstrips) was discussed here a while back, and led to me burbling this, > which bears repeating for those who recently joined us (especially as > someone asked for it): |
|
From: Rui F. <rui...@mo...> - 2000-09-13 09:09:45
|
A static array of vertices with dynamic indexing sounds interesting, and I thought on that too, especially caching stuff on the lower levels patches, but the problem is; how do guys handle geomorphing with this scheme ??! Personally, I dislike roam, except its basic principles like the binary triangles concept, diamonds, etc, but what you get with roam, because it doesn't reset its mesh every time, is popping when a new child is split, you can minimize it with a morph ratio that takes into account the distance to the "to be split" node, and such, but those are all fake approximations and you will end up with pop artifacts sooner or later. True geomorphing can only be done if you set your morphing values *per node* and based on your split metric. Only then you can have a smooth interpolation from one node base edge height to the child's real height from frame to frame. If you "lock" any subtree and cache away its vertices you just lose geomorphing.... again i can see ways to minimize this... but... you have a mesh, you have vertices connecting edges, you either arrange for your vertices positions to translate smoothly or you don't !... I'm a one true believer in top-down, recurse, apply metric, "split-only" algorithms for this very reason. -Rui Ferreira |
|
From: Tom F. <to...@mu...> - 2000-09-13 09:55:13
|
I think what Jim is saying is "VIPM works for anything, including landscapes - but ROAM only works for landscapes". Which I, as a true Crusader on the Path of VIPM Righteousness, agree with of course. Code the VIPM stuff once, and you can use it for just about everything in your scene. Landscapes take a fairly simple bit of code to be converted to VIPM-friendly chunks. What might take a bit more time is doing the hierarchial VIPM thing, where the chunks can be coalesced into bigger chunks as they get further away. Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > -----Original Message----- > From: Jim Offerman [mailto:j.o...@in...] > Sent: 12 September 2000 13:10 > To: gda...@li... > Subject: Re: [Algorithms] VIPM With T&L - what about roam > > > > It's all swings and roundabouts, there are cruder LOD techniques for > > ... > > draw more polys. Any thoughts? > > These days, with hardware evolving so fast, it may very well be more > rewarding to spend your time writing something which will increase the > overall speed of your (rendering) engine than to spend time working on > something which will only speed up rendering of a certain > type of geometry. > > Jim Offerman > Innovade > > > The Atlantis Project > http://www.theatlantisproject.com > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Aaron D. <ri...@ho...> - 2000-09-13 11:27:00
|
Just thinking out loud a bit here... I havn't tried this as yet. Ignoring increased data on the bus, sending a roughly strip-order triangle mesh to a GeForce 2 is just as fast as sending an explicit strip. For strips in general, the total transforms required is 2+n transforms per strip (where n is the number of triangles). Since the GeForce (and presumably future T&L cards) have a cache of 16 vertices, a 4x4 heightmap (32 triangles when at full detail) could effectively require the same 2+n transforms with no stripification. Now back to VIPM (in the context of terrain only here) - Couldn't a rough sort be done on a (say) 8x8 heighmap array to split its triangles into one of four quadrants (or strips) and render them in these one by one? Wouldn't this have the same effect? (ie. 2+n transforms per section) In a fully connected heightfield, the edges of each set would be entirely cached from the previous set. Obviously after some VIPM merges you won't be able to exactly split the map into segments evenly but a rough division should get close to the ideal 2+n transforms. The biggest problem I see is organising your index list. The traditional split-order style list wouldn't work this way. You'd need a list for each of your sets. I'm not sure if the hit in issuing multiple API calls outweighs the benefits. (But there may even be solutions to this as well). Thoughts? - Aaron > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...]On Behalf Of Tom > Forsyth > Sent: Wednesday, September 13, 2000 7:53 PM > To: gda...@li... > Subject: RE: [Algorithms] VIPM With T&L - what about roam > > > > I think what Jim is saying is "VIPM works for anything, including > landscapes > - but ROAM only works for landscapes". Which I, as a true Crusader on the > Path of VIPM Righteousness, agree with of course. Code the VIPM > stuff once, > and you can use it for just about everything in your scene. > Landscapes take > a fairly simple bit of code to be converted to VIPM-friendly chunks. What > might take a bit more time is doing the hierarchial VIPM thing, where the > chunks can be coalesced into bigger chunks as they get further away. > > Tom Forsyth - Muckyfoot bloke. > Whizzing and pasting and pooting through the day. > > > -----Original Message----- > > From: Jim Offerman [mailto:j.o...@in...] > > Sent: 12 September 2000 13:10 > > To: gda...@li... > > Subject: Re: [Algorithms] VIPM With T&L - what about roam > > > > > > > It's all swings and roundabouts, there are cruder LOD techniques for > > > ... > > > draw more polys. Any thoughts? > > > > These days, with hardware evolving so fast, it may very well be more > > rewarding to spend your time writing something which will increase the > > overall speed of your (rendering) engine than to spend time working on > > something which will only speed up rendering of a certain > > type of geometry. > > > > Jim Offerman > > Innovade > > > > > > The Atlantis Project > > http://www.theatlantisproject.com > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Jim O. <j.o...@in...> - 2000-09-13 16:39:58
|
> I think what Jim is saying is "VIPM works for anything, including landscapes > - but ROAM only works for landscapes". Which I, as a true Crusader on the > ... > might take a bit more time is doing the hierarchial VIPM thing, where the > chunks can be coalesced into bigger chunks as they get further away. Yeah, that is what I was saying... I am personally thinking of preprocessing my terrain meshes to form an RTIN (no sense in rendering hundreds of tris in an essentially flat area) and leave the rest up to something like VIPM, once I get round to that... Jim Offerman Innovade The Atlantis Project http://www.theatlantisproject.com |
|
From: Mark D. <duc...@ll...> - 2000-09-13 17:18:50
|
Tom, As a ROAM crusader I must respond ;-)... ROAM works just fine on arbitrary geometry. We mentioned it in the ROAM paper (but didn't implement it). Since then I've implemented that and it works great using a forest of triangle bintrees. Cover your surface with "patches" that are 2^n + 1 verts on a side, where adjacent patches match vertices on their mutual edge, and you are set to go. The trick is to convert your geometry to "patches" like this. There is the MAPS algorithm from SIGGRAPH (Lee et al, 98), plus a new shrink wrap technique for really wild geometry like turbulent CFD isosurfaces by Bertram et al in Vis 00. Go to http://graphics.cs.ucdavis.edu/Publications-2000.html and look for "Bicubic Subdivision-Surface Wavelets for Large-Scale Isosurface Representation and Visualization." The ROAM dual-queue idea works great on Directed Acyclic Graph (DAG) style hierarchies, a special case of which is VDPM. This was shown in a paper by Bernadini and Schikore "Dynamic viewpoint-dependent level of detail of large triangle meshes" presented at The IASTED International Conference on Computer Graphics and Imaging, Halifax, Canada, June 1-4, 1998. An online preprint is here: http://www.llnl.gov/tid/lof/ (type Schikore as the name to search on, then click on the last item that comes up). Additionally, the priority deferral and incremental stripping ideas work fine for DAGs. The one thing that needs a small re-work is the frustum culling using halfplane labels and recursion. DAGs don't have the simple nesting relationship that triangle bintrees do. VIPM I see as okay for large collections of little objects, if you ignore the fact that you are roughly doubling the transform and download work for back-facing sections of the object (VD methods can easily eliminate those from ever hitting the graphics hardware). If your "little" object isn't, like a ship you decide to walk into, then you really need to do view-dependent processing on finer-grained units than whole objects. Further, you need Yet Another Hierarchy (YAH) to do frustum culling, and other macroscopic logic to decide how to balance the LODs on all the objects. So the simlicity of the VIPM vertex selection for a single object isn't buying you all that much in overall system simplicity. Correct me if I'm wrong, but in your VIPM code you still need to compute the actual strips or indexing on the fly each frame? You can "precompute" in a coarse-grained way only if you keep something like power-of-two static LODs, in which case VIPM isn't all that different from traditional static LODs circa 1976, except that you cut the vertex storage in half in some cases. If you use skip-strips or other techniques you end up doing work on a fine-grained level, and at that point you might as well put some VD smarts in. All that said, it is certainly worth exploring *somewhat* coarser-grained view dependence. Fine-grained view-dependent techniques using ANY algorithm just can't keep up with graphics hardware (unless you move veeeery slowly ;-). Hoppe's 1998 IEEE Vis paper is a step in the right direction, but has a lot of problems and only works with terrain. See: http://www.research.microsoft.com/~hoppe/#svdlod --Mark D. Tom Forsyth wrote: > I think what Jim is saying is "VIPM works for anything, including landscapes > - but ROAM only works for landscapes". Which I, as a true Crusader on the > Path of VIPM Righteousness, agree with of course. Code the VIPM stuff once, > and you can use it for just about everything in your scene. Landscapes take > a fairly simple bit of code to be converted to VIPM-friendly chunks. What > might take a bit more time is doing the hierarchial VIPM thing, where the > chunks can be coalesced into bigger chunks as they get further away. > > Tom Forsyth - Muckyfoot bloke. > Whizzing and pasting and pooting through the day. > > > -----Original Message----- > > From: Jim Offerman [mailto:j.o...@in...] > > Sent: 12 September 2000 13:10 > > To: gda...@li... > > Subject: Re: [Algorithms] VIPM With T&L - what about roam > > > > > > > It's all swings and roundabouts, there are cruder LOD techniques for > > > ... > > > draw more polys. Any thoughts? > > > > These days, with hardware evolving so fast, it may very well be more > > rewarding to spend your time writing something which will increase the > > overall speed of your (rendering) engine than to spend time working on > > something which will only speed up rendering of a certain > > type of geometry. > > > > Jim Offerman > > Innovade |
|
From: Charles B. <cb...@cb...> - 2000-09-13 20:53:32
|
Hi Mark, At 10:18 AM 9/13/2000 -0700, you wrote: >Correct me if I'm wrong, but in your VIPM code you still need to compute >the actual strips or indexing on the fly each frame? You can >"precompute" in a coarse-grained way only if you keep something like >power-of-two static LODs, in which case VIPM isn't all that different >from traditional static LODs circa 1976, except that you cut the vertex >storage in half in some cases. If you use skip-strips or other techniques >you end up doing work on a fine-grained level, and at that point >you might as well put some VD smarts in. VIPM requires very minimal CPU work to update the triangle list. It is not rebuilt from scratch each frame. Instead, you just do some small updates to keep it valid all the time. The work is O(N) in the number of triangle changes per frame (eg. very very low). There's a write-up and pseudo-code on my web page. Also note that memory touches are O(N) in the number of triangle changes per frame, and ZERO triangles or verts that aren't modified are touched. I think some kind of chunked ROAM or VDPM is perhaps the future; it would be nice to find an algorithm which can be seamlessly blended from VIPM (large chunks) to ROAM (small chunks) so that a parameter can be tweaked which controls the CPU vs GPU loading. The brilliant step in this direction is still missing; all attempts at it are way too bulky to compete with VIPM or the minimalist versions of ROAM (ala Treadmarks). -------------------------------------- Charles Bloom www.cbloom.com |
|
From: Mark D. <duc...@ll...> - 2000-09-13 23:20:44
|
Hi Charles, Charles Bloom wrote: > Hi Mark, > > At 10:18 AM 9/13/2000 -0700, you wrote: > >Correct me if I'm wrong, but in your VIPM code you still need to compute > >the actual strips or indexing on the fly each frame? [snip] > VIPM requires very minimal CPU work to update the triangle list. It is > not rebuilt from scratch each frame. Instead, you just do some small > updates to keep it valid all the time. The work is O(N) in the number > of triangle changes per frame (eg. very very low). There's a write-up > and pseudo-code on my web page. Also note that memory touches are O(N) > in the number of triangle changes per frame, and ZERO triangles or verts > that aren't modified are touched. Hmmm...I just skimmed your web page on VIPM and that explains a lot. I am concerned about the three indices per tri rather than what you get with strips (for infinitely long strips this gets down to 1). We are talking dynamic loads to graphics-card memory in general, as you swap in and out chunks, and taking up room on the limited graphics memory, and depending on the chip taking additional bandwidth to access those indices. In short, I think in general you need to minimize the number of indices that you send to the hardware or store there (same for vert coords and texture coords etc). The O(number of new verts) applies mainly to PC memory unless you have really fine-grained ways to send a few more verts/indices here and there to the graphics card. Unless you are assuming that the indices are all getting shipped over the AGP bus every frame? Also, how do you manage to keep the array continguous in graphics card memory if you don't allocate enough space there to ship the whole thing? But these are a quibbles. The term VIPM is misleading and restrictive--the concept deserves better. The idea really has to do with sending things *within* chunks in a "static" progressive order, taking advantage of caching effects to allow only an array-range update or trickle of geometry each frame, and relying on some other VD processing at the macro level. The PM is the restrictive part--you can do this with *any* progressive stream that doesn't move vertices. The results of doing a split-only ROAM without screen-projecting the error produces such a progressive sequence, as does the more general queue-based refinement of a DAG style hierarcy. VIPM is misleading in that it makes one think "view independent" for the big picture, which is not the intention. It is a progressive vertex array, really, and you would like to have a few thousand of them active, with a few hundred verts each. Ideally. I'd be curious what current graphics hardware can handle. > > > I think some kind of chunked ROAM or VDPM is perhaps the future; it would > be nice to find an algorithm which can be seamlessly blended from VIPM > (large chunks) to ROAM (small chunks) so that a parameter can be tweaked > which controls the CPU vs GPU loading. The brilliant step in this > direction is still missing; all attempts at it are way too bulky to compete > with VIPM or the minimalist versions of ROAM (ala Treadmarks). > ROAM the chunks, and VIPM within the chunks. Need to solve the seam problem. Also the issues I raised above, if they are real issues... --Mark D. |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X