Tessellation of Arbitrarily Shaped Objects
Posted by Martha on October 7th, 2006
[ MSc AAC - UCL // THESIS ABSTRACT ]
During the past decades the use of programming as a design approach has widen the architect’s creative perception and has set a new dynamic equilibrium between digital and physical space models. Frequently this newly acquired programmatic freedom leads to a wide spectrum of geometrically challenging double curved surfaces. The problem then lies on defining these objects in terms of constructible components.
Various custom tessellation algorithms have thus been developed in response to the problem mentioned above. Most of them are based on a top-down method of mapping triangular grids on the generated surface. This thesis will try to investigate whether it is possible to create a more efficient, quadrilateral tessellation algorithm by using a bottom-up approach. The hypothesis rests on the fact that by having agents estimating the curvature along the surface by making very small, fixed steps, one can have a better approximation of it, as the agents will not overstep any curve inflections. As there is no standard solution to this problem, the method will be tested against two other algorithms more commonly used to solve tessellation problems. The first is the traditional gradient descent algorithm, where the agent’s step size varies based on iterative estimations of the optimal deviation measured from the curved surface. The second emulates an original top-down approach to the problem, where the surface is defined topologically in advance and is solved globally.
Eventually, the results of this comparison show how the ‘walking agent’ method is in some ways advantageous against the other two, while capable of producing interesting tessellation patterns. Ultimately the usefulness of this new tool rests on the fact that the surface is explored based on its local curvature conditions without having to specify the mesh’s node topology in advance. Furthermore the surface is tessellated with respect to a predefined acceptable deviation threshold and maximum tile size.
[ CODE EXCERPT ]
//set the basis functions in u-direction, based on the mathematical formula
//u defines the current u-coordinate, k the control point d the degree of the b-spline //surface in u
float basisnU(float u, int k, int d) {
if (d == 0) {
return basis0U(u,k);
}
else {
float b1 = basisnU(u,k,d-1) * (u - knotsU[k]) / (knotsU[k+d] - knotsU[k]);
float b2 = basisnU(u,k+1,d-1) * (knotsU[k+d+1] - u) / (knotsU[k+d+1] - knotsU[k+1]);
return b1 + b2;
}
}
float basis0U(float u, int k){
if (u >= knotsU[k] && u < knotsU[k+1]){// && knotsU[k]
return 1;
}
else{
return 0;
}
}
//set the basis functions in v-direction, based on the mathematical formula
//u defines the current v-coordinate, m the control points and d the degree of the b-spline
//surface in v
float basisnV(float v, int m, int d) {
if (d == 0) {
return basis0V(v,m);
}
else {
float b1 = basisnV(v, m, d-1) * (v - knotsV[m]) / (knotsV[m+d] - knotsV[m]);
float b2 = basisnV(v,m+1,d-1) * (knotsV[m+d+1] - v) / (knotsV[m+d+1] - knotsV[m+1]);
return b1 + b2;
}
}
float basis0V(float v, int m){
if (v >= knotsV[m] && v < knotsV[m+1]){//&& knotsV[m]
return 1;
}
else{
return 0;
}
}
