Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
|
This article covers a triangle tessellation/data structure for procedural meshes that is different from the usual RTIN roams and significantly different from Diamond LoDs. These meshes can dynamically increase and decrease their level of detail dependant on the observers viewpoint, not drawing unnecessary detail if the observer cant see it, the essence of a procedural universe. This structure is something I've worked on for Entropy and is a non-RTIN equilateral spiral wound view dependant mesh. It's perfectly happy with open and closed structures. Incidently I am 99% certain (without access to source) that it is exactly how Frontier: First Encounters tessellates its planets. I haven't written an article like this before, so I'm not entirely sure how to pitch it, how technical to get, how simple to keep it etc. I think familiarity with other LoD structures would probably be helpful, and rudimentary knowledge of vector math for some of the code. Tesselation wise though, you should be able to follow it without any real knowledge of 3d math. I've avoided dealing with texturing, and the procedural fractal/noise algorithms driving data for a planet, as that's the subject for another article. Here we'll concentrate on a sphere, because even without driving data the radial displacement makes for t-junctions, the avoidence of which is part of this article. Finally there are some obvious and not so obvious optimizations which I only briefly touch upon, which I utilize in Entropy. The result of these make a fast tessellation extremely fast. This method also very quickly tessellates out new lod data with fewer operations than rtin-roam, and can be slightly tweaked to provide triangle strip/fan output without having to 'worm' the LoD to find them. In addition to indexing, very quick indeed. Data StructureOur data structure starts with a basic triangle. This structure uses Equilateral triangles. Although during the course of tessellation they will twist slightly through their plane due to the mid-point displacement, they retain equilateralism as viewed towards the center of the sphere along a normalized triangle centric point. The distortion is self correcting and works itself out, so theres no need to worry about it here. The only consequence is you can not just take the length of an edge and assume it still holds true for the other two edges, which would be important if your determination to split triangles was based upon your distance to them and the length of an edge. Rather handily, by choosing to base the decision off lower or higher edges (in terms of radial height), you can decide how tessellated vertical triangles such as cliffs will/wont become to some degree. Anyhow, thats something for part 2 where we deal with LoD driving. These triangles can undergo two different types of LoD operation. They may be Split (into 4 child triangles) or Combined(into their parent if they have one). So each triangle contains four Child pointers, and one Parent pointer. Because were dealing with the tessellation of a surface, and because there can be various sizes of triangle adjacent to one another, we need to keep track of these adjacencies. So each triangle has three Edge pointers, which point to neighboring triangles. Of these pointer types, children, parent and edges, only children are ever constructed into new triangles. And only children ever have delete called upon them. Its vital that whenever children are deleted their pointers are set to NULL. The structure is so interdependent that forgetting a simple thing like this can cause catastrophic recursion and/or crashes. This is because our Splitting function will recurse about these edges sometimes (though with less recursion that ROAM typically). Lastly, our triangles should be nodes in a doubly linked-list. I wont go into the code for those here, I guess you could also use STL but I typically find a fairly straight forward implementation to be faster than the STL templates. 
class cLoDTri; { dVector p[3]; //points cLoDTri* e[3]; //edges cLoDTri* pParent; //parent cLoDTri* child[4]; //children } For our tessellation structure we have a few very strict rules.
|
|
