Credit to my partner in crime Toby Gilbert who collaborated with me on this project
A link to the paper: Over the Hills and Far Away
Tag: OpenGL
Master Class: Laplacian Mesh Editing – Update 1
So to start here is a bit of back story. Our university (Bournemouth) has partnered up with MPC to give us some R&D assignments for our master class which they will judge and give feed back at the end of the project. We had the choice between creating some kind of terrain generation or animation application or if you’re truly hardcore to implement one of a selection of mesh deforming papers from SIGGRAPH. I (being the hardcore of hardcore) decided that my brain clearly isn’t working hard enough at the moment and have chosen the latter. so here is a quick introduction to laplacian mesh editing and what I understand at the moment. Also theres a demo!!! *screams*
So laplacian mesh editing is a form of deformation in which the user will paint weights to a mesh of their choosing and from the manipulation of these weights can magically deform the object before your eyes. But how does one do that you might say? Good question! Well firstly we have to represent our geometry in a different way. You’re probably used to using relative coordinates to represent points in a mesh i.e. Vec3(1,4,5). Well for laplacian mesh editing we represent the point in relation to its neighbouring points.This is called the implicit representation and goes a little like this…
So here we have a square made from 4 points (mind blowing!). To find the location of V0 from the other points we can use half the sum of V1 and V3 then add this unknown vector d0 (delta). We can calculate this unknown by simply rearranging the equation just like in Fig 1. Now lets get a bit more crazy and represent all these points in implicit matrix form.
From this form you are now ready to create some deformation! You do this by adding these things called “handles” or “anchors” to our matrix. Say if we want V0 and V2 to be our handles this is how it would look.
Now say if we change the position of V0 and V2 in our delta matrix (denoted b in Fig 3) and then solve for x, this will give use different points because deformation has occurred (Huzzuh!). But you may be thinking to yourself, “How in the world do I solve this? These are not square matrices!”. Another great question! Well here is how…
Now we have the basis of our laplacian mesh editing! You can deform simple shapes to your hearts desire! But this is by no means a complete. The way we create our matrix A or our “laplace matrix” only currently works for very uniform geometry. For any complicated shapes we will have to calculate this another way. Sadly I dont know that yet 😦 but keep updated with my posts and one day… just maybe… I will!
Anyway here’s a pretty demo!
Terrain Generation Collaborative Research Project – Update 2: Thermal Erosion & Data Structures
When thinking about generating terrain we must first think about how we are going to store our data to represent it. This is a very crucial aspect as depending on the method you use to represent this data will have a direct effect on what kind of terrain you can generate and how large your data structure will be. In a ideal world we want to be able to represent any kind of terrain using minimal memory. The technique we have been using so far is two dimensional height maps. This is a very small way of representing terrain data in which we use a two dimensional array of elements that store height values. This results with a spacial requirement of n^2 bytes, n being the size of our array. This technique has its limitations in what type of terrain you can represent. Being only able to represent height and location information this restricts us to only being able to represent one layer of a surface and cannot represent natural phenomena such as horizontal caves. On the other hand we can represent our terrain in voxel form. This could be represented in a tree dimensional array which allows us to represent a third dimension of data. Where this representation has its draw backs is the size the data structure will be. Unlike our height maps voxels will be the size n^3 bytes, turning terrain that would be megabytes in height maps into gigabytes in voxel data. Therefore we must compromise and combine the two techniques with the data structure proposed in the paper Layered Data Representation for Visual Simulation of Terrain Erosion by B. Benes and R. Forsback. This paper proposes a method of a two dimensional array of elements which contain information about the underlying layers.
E.g.
typedef struct{
PropertiesT data[MAX_LEVEL];
float height;
} ElmT; //one element of the array
PropertiesT is a structure that contains information about the material possibly such as height of the material layer, material type or even density. Unlike in the voxel representation this clumps together layers of the same material providing information about the block which saves large amounts of data. The overall size of the data structure is now more like n^2 * sizeof(ElmT) * bytes which means as long as sizeof(ElmT) is smaller than n our which it is highly likely to be out data structure will be much smaller than the voxel based approach.
This data structure also gives us the freedom to easily implement erosion techniques. The technique we have used is known as thermal erosion and is sited from the same paper. The thermal erosion algorithm is an attempt to represent long term thermal weathering. A material is dissolve because of changes in temperature which cause there terrain to break up and fall down. The eroded part will fall down in the direction of greatest gradient. To achieve this we use the following equation,
The result of which will give the amount of material to move to neighbouring location i. Delta S is equivalent to 1/2 the largest height difference between the element we wish to erode and its eight neighbours, this must be calculated to stop oscillations in the algorithm. ‘hi’ represents the height of the neighbour we wish to move our material to which is divided by the sum of all our elements neighbouring heights.
Anyway enough of the boring stuff here is pretty video of it all implemented!
Declan Russell 