Holes in terrain

Does PLSM2 natively support, or have a way to support through an extension API mechanism, the ability to either not render certain tiles or render them with 0% alpha using "nearest" texture filtering? Basically, I need to punch holes in the ground to allow the creation of caves and basements in buildings.

I was working on my own heightmap based terrain scene manager for Ogre a while back (non paging, only performed texture splatting through pixel shaders, no dynamic LOD) and I made sure to include this functionality natively. In my implementation, I simply didn't generate geometry for terrain quads that were supposed to be holes. It created an interesting artifact, in that you could still apply a splat to that quad, which would bleed into the surrounding visible tiles because of the texture filtering of the alpha channel, but even that was kind of a neat 'feature' that you could use or ignore depending on the immediate needs.

Anyhow, I did some searching on this topic before posting. Searching for "hole" only comes back with 2 results, none of them related to the question. Searching for "cave" brought me to "Subsurface?", which was mostly on topic, though the poster's needs would have been better served by portals, and the thread eventually diminished into a discussion about why Crystal Space sucks.

The old discussion about it has been dead since December 2005, so I'm mostly checking to see if there's been any progress along these lines, or if there is an ideal place within the PLSM2 code that something like this could be added.

I'm mostly held up in design meetings with a deadline looming, otherwise I'd take a week and read the code myself. At the minimum, even a generic feasibility/difficulty response would be great, as I need to determine if we should use PLSM2 stock (and throw out all subterrainean areas), attempt to modify it to support holes, or continue work on my old terrain scene manager and get it up to par.

It should be relatively easy to add code to PLM to completely hide a tile since it's simply a renderable.

If you want to do something more fancy then that's more work obviously. I don't think anything is currently supported out of the box though.

Actually, tile level hiding would be too large. I'm looking to hide individual quads.

I used a different terminology in my terrain renderer, defining a "tile" as a single quad ploygon of terrain. (4 heightmap samples, 1 for each corner) To represent the batches of these "tiles" I used the term "tileset". Obviously you don't render this definition of "tile" as single renderables, as the number of display batches would increase very quickly, so I'm assuming that PLSM2 defines a "tile" as an equivilent to my "tileset".

Using my own terminology, the ability to remove a single tile from a tileset is what I am looking for. Though, as you said, PLSM2 doesn't natively support holes in any respect. So that answers my question. I'll have to find some time, probabaly next week, to actually look at the source code and figure out how easily I could modify the geometry creation of the tilesets to take into account another 2d map to represent holes.

I don't really believe that it is going to be that critical of a feature requirement. The level designer should be able to create levels without holes in the terrain. Even still, I might as well at least take a look at it and see for myself how much of a pain it is going to be, should someone decide that it is an absolutely "must have" feature.

Thanks for the response.

Look in the wiki for adding Physics to PLSM2 - there you'll find how to get the geometry from each "tileset" and then you could just take it aside, remove the loaded tileset from view and replace it with your edited version. Just go through the list of verts/indicies and remove the correct ones.

Thanks for the tip! It's always helpful to at least have a known place to start.

I've thought about holes a little bit for things like caves in the past (didn't do anything about it, just thought ).

It seems like the easiest way to add holes would need to be LOD based. In other words, the size of the hole would need to change based upon the LOD of the tile you're drawing. Without that, you'll have to change the way LOD is done to handle creating more adjacent vertices for the various LOD level and still have more geometry than you need around the hole. If you're just removing vertices like suggested above by HexiDave, you'll be changing the size of the hole based upon LOD.

Adjusting the size of the hole sounds like a bad idea, but if you're planning to use this for caves for instance, you would just have to make the LOD of the cave entrance adjust based upon the size of the hole (in other words key off of the LOD of the tile it's in).

I hope I'm explaining that decently...

Keep in mind that altering tile goemetry is only one way of putting a hole in the ground. It would also be possible to sacrifice a splatting texture and use it as an overall alpha value for rendering. In that way, you could simply use the NEAREST filtering method for that texture and it would always give you a square hole in the right spot regardless of what the underlying geometry LOD is doing. It would probably be a little awkward to do using the fixed pipeline, but a pixel shader could make this sort of functionality work easily enough. The downsides are obvious, loss of a texture unit and you end up drawing the holes even though they aren't visibly there, which is going to cost you fill rate. You'd also still be at the mercy of LOD based material changes, but there are limitations in everything when it comes to working in 3D.

Personally, I think the overall best method would be to run a sort of postfilter routine on the actual geometry after the LOD geometry generation, and cut the polygons as you needed to put the holes in the tiles according to some 2D holemap in system memory. This sort of operation isn't really that expensive in terms of CPU time, it doesn't waste texture units or create additional overdraw, and it creates perfectly square holes in the terrain at every LOD level without distortion. I wrote a similar routine for OpenGUI to perform geometry based scissor rect operations and it works pretty well.

There are really only a few downsides to this method:

1. The 2d holemap is going to eat 1 byte per tile resolution (as a uchar is the smallest addressable unit), unless you decide to utilize more cpu time and use bit packing and unpacking. It doesn't sound like much, but as I'm sure you know, 1 byte * 512 * 512 = 262,144 bytes, and most of it will be wasted space, as the number of holes in the terrain will be far far less than the number of non-holes. You could probably save yourself a fair amount of memory and use std::maps to create a type of 2d array that is more efficient, only having entries for locations with holes. That would add overhead that gets worse and worse with every additional hole in the terrain, but I don't really expect you'll find many people that need more than 3% of their map to be a hole.

2. The number of polygons in the tile is almost guaranteed to increase every time you perform a cut, and there are 4 cuts per hole. This has to do with the fact that there are only 4 possible outcomes from cutting a 3 sided polygon against a plane. You either 1) cut out the whole polygon; 2) cut out none of the polygon; 3) cut off 2 vertices, and end up with 1 resulting triangle; or 4) cut off 1 vertex, and end up with a quad as the result, which must then be split into 2 triangles. From a purely abstract analytical standpoint, you could assume that the 4 operations have an equal chance of occuring, which means that your net gain in polygon count will be 0 per polygon evaluated, as shown in this formula:

However, in real world situations with OpenGUI I've found that this formula just doesn't hold true, as it does not take into account the size of the input polygons or the relative position of the clipping plane. In OpenGUI, I've seen geometric scissor rects create up to 50% more polygons than were initially input, and I've also seen it create 90% less output than input. In a terrain engine setting, I can almost guarantee an increase in polygon count for all but the most detailed LOD levels, but it would likely be no where near as bad at 50% net gain. As a rough guess, I'd say you'd probably see between 5% and 20% net gain on the average, depending on how many holes you make and what LOD you're working with. At first, additional holes will increase your net gain, but eventually you'll start clipping out so many polygons that you'll end up with a net loss.

stl has a bitarray class that will create a static (you cannot change the size once constructed) bit array that takes up 1 bit per size, rounded up to the nearest 8 bits (obviously). You could have it reference all points on the tile and that would tell you what needs to be there and what doesn't without needing to do bit fiddling yourself.

If you wanted to use packed bits to represent the hole map, then I would agree that using an existing STL bitarray class would be the ideal method. Unfortunately it still burns an amazing amount of memory ( 512 * 512 / 8 = 32,768 ) considering that most of the map won't be a hole in the first place. If I were to implement it, I would use the std::map(int,bool) method instead, as it only creates entries for the spaces that are holes.

Also keep in mind that eventually you'll need to iterate over the list of holes, and using a bitarray means you need to evaluate every position before you know if a hole needs to be punched. Using an std::map has the advantage that iterating the list of holes does not require the "hole punch" routine to evaluate every location in order to determine if a hole is necessary, as each entry in the map is known to be a hole and the key itself is the position of the hole. [X,Y] = (Y * MaxX) + X

Looking at it even more, std::map(int,bool) seems redundant, as the mere existence of the entry in the map implies a hole (making the bool just unneeded data), so std::set(int) would be even more efficient.

Honestly I have no idea what you guys are talking about

I'd add some code to PLM to allow hiding a specific page or even tile, export that tile as a mesh file so I can open it up in a modeller like 3ds max, cut the hole as I wanted, and then display the mesh in the scene instead of the tile.

You could texture the mesh using the same splatting texture that's applied to the original tile, and presto. Hole.

Honestly I have no idea what you guys are talking about

I'd add some code to PLM to allow hiding a specific page or even tile, export that tile as a mesh file so I can open it up in a modeller like 3ds max, cut the hole as I wanted, and then display the mesh in the scene instead of the tile.

You could texture the mesh using the same splatting texture that's applied to the original tile, and presto. Hole.

You'd have to make that work for all of the LODs for that tile, right? Otherwise it would be obvious when adjacent tiles had a different LOD, right?

I think it would be cool to have the tools (mapsplitter) have an option which meant absolute 0 (black) meant a hole (or possibly another value), and then took care of all of the other problems (LOD creation etc.).

You'd have to make that work for all of the LODs for that tile, right? Otherwise it would be obvious when adjacent tiles had a different LOD, right?


I doubt it'd be necessary for all lods for that tile nor would you have to match it up perfectly so that your mesh has exactly the same vertex positions to what the surround lod terrain does, but I guess you'd have to see what it looked like in action to find out. Morphing would have problems where a mesh met the morphing terrain.

Maybe using a mesh isn't the best idea, but again I'd have to know exact requirements for a hole cut in the terrain. Do you need a cave? Can you use a mesh for the cave entrance then when you move deep enough into the cave mesh just hide the tile at that point? (No cutting involved). Can you use tricks like render texture or portals instead of cutting? etc.

What about the simplest trick in the book? Do a render pass prior to the terrain rendering which uses a mesh where the hole should be and renders to the depth buffer but doesn't render to the colour buffer (it's basically invisible but rendering to the depth buffer), so that when the terrain renders it later it doesn't render at that spot because of the depth buffer?

There are lots of tricks that could be used.

Perhaps tuan has some thoughts. Map splitter idea sounds interesting but I don't think it's just the map splitter that would need to be updated - all the LOD rendering, morphing, etc. would have to be updated to support holes.

Yeah, I'm mainly thinking of seamless caves with portals in between landscape and "indoor" scenemanagers.

If the LODs didn't match up, I think gaps would start to show up where the tiles didn't match up. I haven't experimented with this, but I've definitely seen it in other demos when adjacent tiles with different LOD causes vertices not to match up. Small cracks etc. start to appear.

Your "simplest trick in the book" is very interesting, and something I hadn't considered. I'll have to think about that one, but that has some possibility.

As far as mapsplitter goes, it would definitely only be the starting point of a potentially deep rabbit hole .

I'm really only starting to think about this stuff again recently since that portal Summer of Code project started getting worked on by farakon. I'd REALLY like to see a seamless (no "zoning") transition working in OGRE someday .

Disclaimer: Keep in mind, everything I say is mostly theoretical, since I've yet to even run PLSM2, let alone look at the source code.

Altering the depth buffer is a very touchy subject. You only get 1 depth buffer per frame (unless you get crazy with the API), and altering its contents in non-standard ways can make for cool effects just as easily as it can become a horrid pain in your side. In order to use the depth buffer as you're suggesting, you would need to guarantee that terrain is the very last rendering stage, otherwise the altered depth buffer can cause non-terrain related pixels to become depth clipped. It's a good idea, but it is also very situation specific. The most reasonable solution to me still sounds like geometry cutting after the LOD mesh is generated. It touches the least amount of code, works in every concievable situation, provides a native solution that doesn't require additional work in an external modelling program, and it doesn't break the tile stitching when LOD changes. The only thing I'm unsure about is the effect it could have on the LOD morph vertex program.

The entire subject of holes in PLSM2 terrain no longer matters to me, as I've convinced everyone in my project that avoiding the need for holes is a much better solution than trying to add them to PLSM2. So I came up with a hackish solution for providing basements to buildings that no one will ever notice, and caves (and other structures that require navigatable areas covered by terrain) are removed from the design. Sometimes the pain of explaining why something isn't a good idea to non-programmers is far less than the pain of giving in and later having to make it work.