Skip to main content
gamedev.net
🔒 Locked

terrain patch stitching

Started by pammatt 12 replies 2.3k views
Original Post
pammatt
pammatt
So i've been working on my terrain code lately but i am stuck on stitching the seams between my patches. My terrain is rendered using one index buffer per LOD and a big vertex buffer. I determine which lod to use and issue the draw call using the index buffer for that lod level therefore they are shared amoung the patches. And those index buffers store one big tri-strip with degenerate tris connecting them. I'm having a big problem figuring out how to modify the base lod index buffers to stitch the patches together. Currently I make a copy the appropriate index buffer and i know when i have to modify it (i.e. i know when one of the patch neighbors has a lower level of detail than the current patch.) The problem is, how do I break up the long tri-strip the patch uses and put in tris to fix the seam? Thanks and I have been reading papers and such but I seem to still be having a mental block.
gamelife
gamelife
I'd suggest just use skirts. It's fast and straightforward to implement.
pammatt
pammatt
would you mind giving me a decent reference to an article or something?

Thanks.

Zakwayda
Zakwayda
Try the article on 'terrain using interlocking tiles' - it's in one of the first two GPG books. If you don't have or can't get those, however...

If you're using tristrips, I think you'll have to render the interior separately from the edges (I assume those are the skirts the other poster was refering to). The interior is rendered at the patch's level of detail, using degenerate tristrips if you wish. The edges are then rendered separately and are tesselated so as to blend the higher interior lod with the lower neighboring lod (assuming higher always accomodates lower).

As for figuring out the triangulation for the edges, you can hard-code it (that's what the GPG article and code does) or write a function that figures it out and caches it. I wrote such a function for my Bezier patch class (which also allowed for lower-to-higher lod as well as higher-to-lower), and, well, it was really hard. So as long as you know the highest possible lod in advance, hard-coding might be preferable.

Hm, there are a lot of details involved, so I don't know how helpful that was.
pammatt
pammatt
I have the article in gpg and have read it. However, I wanted to keep my existing triangulation. I definantly do not like the hard-coded approach either. In any case, thanks for the references. I guess I'm just having a hard time figuring out how to triangulate the edges whilst maintaining the interior tri-striped with degenerates format.
Soiled
Soiled
What they said.

If you're having a hard time triangulating with tristrips then perhaps trilists would be easier (they should be roughly same as strips performance-wise - at least on the PC).

Also there's Jonathon Blow's "Unified rendering LOD" articles at http://www.number-none.com/product/index.html that describes a sensible way to generate the edge tris but I think it's targeted at arbitrary geometry but general idea is still applicable to heightfields.
technobot
technobot
One simple option is simply to change the indices to transform two adjacent traingles into one bigger one, as illustrated below. Or in your case, since you're using a shared index buffer, you could adjust the vertices instead. But it does have the associated cost of updating the index or vertex buffer each time a LOD changes. Then again, if you're doing that anyway already, then perhaps the extra cost would be small..

2-4-6      2---4,6|\|\|  --> |\ /|1-3-5      1-3-5
Michael K.
pammatt
pammatt
The shift approach is what i've been trying. What I do is use a static index buffer for patches that do not have neighbors of differing LODs and a dynamic buffer when needed to build indices for patches of differing levels of detail.

Therefore, i have been trying to implement the shift idea but like i said have been having difficulties. Going by your example, what happens to index 6? does it just get removed from the index buffer due to shifting?

Probably a dumb question, and i am a little frustrated that i can't seem to visualize it right.

Thanks.
gamelife
gamelife
More info about skirts:
Skirts are vertical quads placed around the perimeter of each patch. The top of the skirt matches the edge, while the bottom extends below until it covers any possible gaps between adjacent patches.
Advantages:
Skirts are associated with each patch/lod individually. No need to match neighbouring patches. Thus no need to concern adjacent patches of different LOD, different geomorphing parameters, etc. Hence it's simple & fast to generate.
Disadvantages:
More geometry than necessary is used for crack fixing.
But it's usually negligible, as compared with computing a list of perfectly matched tris at runtime (consumes cpu power) or compile time (need different versions for different LOD combinations, need deal with morphing issues, etc).

(another problem is texture stretching on the skirts - it depends on your LOD settings)
Trienco
Trienco
Quote:
Original post by pammatt
I have the article in gpg and have read it. However, I wanted to keep my existing triangulation. I definantly do not like the hard-coded approach either.


no need to hardcode it. take a piece of paper, draw a lot of edges and you will figure out a simple way to generate "linkers" to all lower pieces in all combinations. so it wont stop you from changing patch sizes or whatever.

be warned, its looking ugly and the effective level might be confusing, as im using two alternating subdivision schemes and there are always two levels (one of each) that use the same linkers.

int Terrain::BuildLinker(int level, int side, int low, unsigned short* buffer) {	int PS=PatchSize+1;	int effective_level_high= (level+1)>>1;	int effective_level_low= (low+1)>>1;	if (effective_level_high==effective_level_low) return 0;	int step_high=1<<effective_level_high, step_low=1<<effective_level_low;	int start_high, start_low, end_high, end_low;	int idx_step_high, idx_step_low;	int sign = (side==0 || side==3) ? -1 : 1;	int low_to_high;		switch (side) {	case 0: 		start_high=(PatchSize-step_high)*PS + PatchSize-step_high;		start_low=PS*PS -1;		end_high=step_high*PS + PS-(1+step_high);		end_low=PatchSize;		idx_step_high=-PS*step_high;		idx_step_low=-PS*step_low;		low_to_high=-step_high;		break;	case 1:		start_high=(PatchSize-step_high)*PS +step_high;		start_low=PatchSize*PS;		end_high=(PatchSize-step_high)*PS + PatchSize-step_high;		end_low=PatchSize*PS +PatchSize;		idx_step_high=step_high;		idx_step_low=step_low;		low_to_high=-step_high*PS;		break;	case 2:		start_high=step_high*PS + step_high;		start_low=0;		end_high=(PatchSize-step_high)*PS +step_high;		end_low=PatchSize*PS;		idx_step_high=PS*step_high;		idx_step_low=PS*step_low;		low_to_high=step_high;		break;	case 3:		start_high=step_high*PS + PatchSize-step_high;		start_low=PatchSize;		end_high=step_high*PS + step_high;		end_low=0;		idx_step_high=-step_high;		idx_step_low=-step_low;		low_to_high=step_high*PS;		break;	}	int num=0;	for (int iter_low=start_low; iter_low*sign <= end_low*sign; iter_low+=idx_step_low) {		int loop_start_high=(iter_low+low_to_high)-idx_step_low/2;		int loop_end_high=(iter_low+low_to_high)+idx_step_low/2;		if (iter_low*sign<end_low*sign) {			buffer[num++]=iter_low;			buffer[num++]=iter_low+low_to_high+idx_step_low/2;			buffer[num++]=iter_low+idx_step_low;		}				for (int iter_high=loop_start_high; iter_high*sign < loop_end_high*sign; iter_high+=idx_step_high) {			if (iter_high*sign<start_high*sign || iter_high*sign>=end_high*sign) continue;			buffer[num++]=iter_high;			buffer[num++]=iter_high + idx_step_high;			buffer[num++]=iter_low;		}	}	Lvl[level].Link[side].LowLvl[(low-level)-1].Size=num;	return num;}
f@dzhttp://festini.device-zero.de
Thorin_nz
Thorin_nz
I drew this up a while ago...

http://img86.exs.cx/img86/7880/dlod.gif

Not sure how efficent it is, but it seems to work nicely
pammatt
pammatt
Thanks all, for the replies. I haven't had much time to work on it due to a lot of "real" work i've had to due today but hopefully tommorrow i'll get a chance to work on it some more.

Thanks again!
technobot
technobot
Quote:
Original post by pammatt
Therefore, i have been trying to implement the shift idea but like i said have been having difficulties. Going by your example, what happens to index 6? does it just get removed from the index buffer due to shifting?

Index 6 stays just where it was. The only change is to index 4 - after the shift it points to the same vertex as index 6. You just copy index 6 to index 4, and leave all the rest as they were. You still have the 546 triangle, but it becomes degenerate (zero area). Modern hardware usually just ignores such traingles entirely. Again, note that instead of copying indices you can copy the corresponding vertices if it works better for you.
Michael K.
pammatt
pammatt
Awesome, the shift method is working great. All my stitching code works now. Thanks again for the help guys and looking back on the resulting code it wasn't really that painful. Guess I just had a mental block on how to triangulate it properly.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.