Arches: a Framework for Modeling Complex Terrains ( [tba:eurographics] | pdf | web | 2009 )
A. Peytavie, E. Galin, J. Grosjean, S. Merillou
This paper presents a method for generating and editing terrains that include overhangs.
A discrete block model describes columns of materials. This is covered by a simple implicit surface (using a cubic kernal giving a C-0 continuity) to smooth it. The block model describes which material is present between which heights, this is presented as a lower memory version of a voxel system.
These techniques are intended for use in realtime editing, so instead of complex physical models that can only be used offline, Arches uses a simplistic physical simulation in each column. Where sand and loose rock are clustered above bedrock, the materials are unadjusted to form contiguous columns. Then adjacent columns with the same materials are allowed to settle (with different viscosity etc..).
The bedrock layer can be edited using a tool that adds or removes material from the columns, taking into account the fact the user is viewing the implicit surface. This just adds a sphere of material at a time, and isn't particularly useful when building up large cliffs - so some sweep tools were also introduced.
An erosion tool takes a volume of bedrock, and converts it to loose rock and sand. These are then allowed to settle to give the appearance of decay. Similarly loose rocks are made by tessellating a volume of bedrock using Voronoi cells, then erroding the outlines, leaving contact point unchanged. As these rock piles are not the result of physical simulation, they might not be physically plausible, but the results are good enough.
To render the scene, the implicit surfaces of the bedrock and sand are polgonized. The loose rock's implicit surface is polgonized separately. To avoid computing UV's a 3D volumetric texture is used that includes the normals of the local surface.
This paper contains quantities of unnecessary equations. There's something inside every computer scientist that believes a really good paper has to have lots of equations! It's also an offline system - the textures and meshes are generated from the column model at design time and we only see "normal" meshes and textures at run time - the potential is almost there for real time generation, but it just falls short.
The results are very nicely presented and represent a system that is an obvious improvement on current games-industry practice. I've been meaning to review more terrain generation techniques, because it's one of the best sources of mesh generation literature.
Cheeky note: this system of columns for representing rock was used in a undergrad project ("mudslignin'") to represent a 2D landscape of mud and water - it was even fast enough to calculate 2d "water" (aka jelly) simulations in real time:)
Structure Preserving Reshape for Textured Architectural Scenes ( [tba:eurographics] | pdf | web | 2009 )
Marcio Cabral, Sylvain Lefebvre, Carsten Dachsbacher, George Drettakis
This paper presents a method to intelligently reshape existing 3d models. By using context-sensitivity image resizing and attempting to keep angles constant, an artist's models can be manipulated to a new shape by dragging a few handles around.
An input model is pre-processed into a set of constraints and a solution. Then the model can be reshaped using a set of point handles, while the constraints are satisfied to position each vertex in real time.
There are a few different constraints, edge direction constraint attempt to keep the angle between two consecutive polygons close to the original. Edge length constrains attempt to preserve the length of shorter edges more than longer ones. There is a minimum edge length to stop degeneration. When two parts of the mesh touch, but are not connected, a contact constraint enforces continuity. This constraint triangulates one of the touching faces and constrains the other part of the mesh to this position. To capture the requirement that ornaments (windows etc..) stay the same size, similar sets of faces are detected and (optionally) constrained.
This set of hard and soft constraints is dumped into a matrix and solved using least-squares. At run time the users input is projected using the found solution and analyzed - if it is degenerate, the users edit is rejected.
Unlike the content-aware image resizing that made the front page of digg last year, the texture resizing algorithm is specialized for rectilinear architecture. The input texture analyzed for self-similarity, and only those parts that are self-similar are stretched on a rectangular grid. Sample patches are used to reduce blurring.
This paper is one in a growing trend towards manipulating existing meshes into new forms. I have always felt that this approach isn't competitive with outright procedural generation for the pro-artist due to over constraining the user:
"To enable interactivity, we rely on a simple solver and allow it to fail or reuse user input if this leads to degeneracies (ie collapsing edges or collisions). We argue this behavior is reasonable since the user has full freedom to assign new handles and guide the solver in avoiding degeneracies)"
However as a method for quickly splicing together geometry for a un-trained user this looks really effective. The video is really worth checking out.