tests/glean/geomutil.cpp

   1 // BEGIN_COPYRIGHT -*- glean -*-
   2 //
   3 // Copyright (C) 1999,2000  Allen Akin   All Rights Reserved.
   4 //
   5 // Permission is hereby granted, free of charge, to any person
   6 // obtaining a copy of this software and associated documentation
   7 // files (the "Software"), to deal in the Software without
   8 // restriction, including without limitation the rights to use,
   9 // copy, modify, merge, publish, distribute, sublicense, and/or
  10 // sell copies of the Software, and to permit persons to whom the
  11 // Software is furnished to do so, subject to the following
  12 // conditions:
  13 //
  14 // The above copyright notice and this permission notice shall be
  15 // included in all copies or substantial portions of the
  16 // Software.
  17 //
  18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  19 // KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  20 // WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  21 // PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL ALLEN AKIN BE
  22 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23 // AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  24 // OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  25 // DEALINGS IN THE SOFTWARE.
  26 //
  27 // END_COPYRIGHT
  28
  29
  30
  31 // geomutil.cpp:  frequently-used geometric operations
  32
  33 #include "geomutil.h"
  34 #include "rand.h"
  35 #include <cassert>
  36 #include <algorithm>
  37 #include <cmath>
  38 #include <float.h>
  39 #include <stdio.h>
  40
  41 using namespace std;
  42
  43 namespace GLEAN {
  44
  45 ///////////////////////////////////////////////////////////////////////////////
  46 // RandomMesh2D:  Generate 2D array with fixed boundaries but interior points
  47 //      that have been perturbed randomly.
  48 ///////////////////////////////////////////////////////////////////////////////
  49 RandomMesh2D::RandomMesh2D(float minX, float maxX, int xPoints,
  50     float minY, float maxY, int yPoints,
  51     RandomDouble& rand) {
  52         m = new float[xPoints * yPoints * 2];
  53         rowLength = xPoints;
  54
  55         // Loop var; we declare it here and not in the for loop because
  56         // different compilers scope variables differently when
  57         // declared in a for loop.
  58         int iy;
  59
  60         // Drop each point squarely into the center of its grid cell:
  61         for (iy = 0; iy < yPoints; ++iy)
  62                 for (int ix = 0; ix < xPoints; ++ix) {
  63                         float* v = (*this)(iy, ix);
  64                         v[0] = minX + (ix * (maxX - minX)) / (xPoints - 1);
  65                         v[1] = minY + (iy * (maxY - minY)) / (yPoints - 1);
  66                 }
  67         // Now perturb each interior point, but only within its cell:
  68         double deltaX = 0.9 * (maxX - minX) / (xPoints - 1);
  69         double deltaY = 0.9 * (maxY - minY) / (yPoints - 1);
  70         for (iy = 1; iy < yPoints - 1; ++iy)
  71                 for (int ix = 1; ix < xPoints - 1; ++ix) {
  72                         float* v = (*this)(iy, ix);
  73                         v[0] += deltaX * (rand.next() - 0.5);
  74                         v[1] += deltaY * (rand.next() - 0.5);
  75                 }
  76 } // RandomMesh2D::RandomMesh2D
  77
  78 RandomMesh2D::~RandomMesh2D() {
  79         delete[] m;
  80 } // RandomMesh2D::~RandomMesh2D
  81
  82
  83
  84 ///////////////////////////////////////////////////////////////////////////////
  85 // SpiralStrip2D: Generate (x,y) vertices for a triangle strip of arbitrary
  86 //      length.  The triangles are of approximately equal size, and arranged
  87 //      in a spiral so that a reasonably large number of triangles can be
  88 //      packed into a small screen area.
  89 ///////////////////////////////////////////////////////////////////////////////
  90 SpiralStrip2D::SpiralStrip2D(int nPoints, float minX, float maxX,
  91     float minY, float maxY) {
  92
  93         // Most of the complexity of this code results from attempting
  94         // to keep the triangles approximately equal in area.
  95         //
  96         // Conceptually, we construct concentric rings whose inner and
  97         // outer radii differ by a constant.  We then split each ring
  98         // (at theta == 0), and starting from the point of the split
  99         // gradually increase both the inner and outer radii so that
 100         // when we've wrapped all the way around the ring (to theta ==
 101         // 2*pi), the inner radius now matches the original outer
 102         // radius.  We then repeat the process with the next ring
 103         // (working from innermost to outermost) until we've
 104         // accumulated enough vertices to satisfy the caller's
 105         // requirements.
 106         //
 107         // Finally, we scale and offset all the points so that the
 108         // resulting spiral fits comfortably within the rectangle
 109         // provided by the caller.
 110
 111         // Set up the array of vertices:
 112         v = new float[2 * nPoints];
 113         float* lastV = v + 2 * nPoints;
 114
 115         // Initialize the ring parameters:
 116         double innerRadius = 4.0;
 117         double ringWidth = 1.0;
 118         double segLength = 1.0;
 119
 120         float* pV = v;
 121         while (pV < lastV) {
 122                 // Each ring consists of segments.  We'll make the arc
 123                 // length of each segment that lies on the inner
 124                 // radius approximately equal to segLength, but we'll
 125                 // adjust it to ensure there are an integral number of
 126                 // equal-sized segments in the ring.
 127                 int nSegments = static_cast<int>
 128                         (6.2831853 * innerRadius / segLength + 0.5);
 129
 130                 double dTheta = 6.2831853 / nSegments;
 131                 double dRadius = ringWidth / nSegments;
 132
 133                 double theta = 0.0;
 134                 for (int i = 0; i < nSegments; ++i) {
 135                         double c = cos(theta);
 136                         double s = sin(theta);
 137
 138                         *pV++ = innerRadius * c;
 139                         *pV++ = innerRadius * s;
 140                         if (pV >= lastV)
 141                                 break;
 142
 143                         *pV++ = (innerRadius + ringWidth) * c;
 144                         *pV++ = (innerRadius + ringWidth) * s;
 145                         if (pV >= lastV)
 146                                 break;
 147
 148                         theta += dTheta;
 149                         innerRadius += dRadius;
 150                 }
 151         }
 152
 153         // Find the bounding box for the spiral:
 154         float lowX = FLT_MAX;
 155         float highX = - FLT_MAX;
 156         float lowY = FLT_MAX;
 157         float highY = -FLT_MAX;
 158         for (pV = v; pV < lastV; pV += 2) {
 159                 lowX = min(lowX, pV[0]);
 160                 highX = max(highX, pV[0]);
 161                 lowY = min(lowY, pV[1]);
 162                 highY = max(highY, pV[1]);
 163         }
 164
 165         // Find scale and offset to map the spiral into the bounds supplied
 166         // by our caller, with a little bit of margin around the edges:
 167         lowX -= ringWidth;
 168         highX += ringWidth;
 169         lowY -= ringWidth;
 170         highY += ringWidth;
 171         float scaleX = (maxX - minX) / (highX - lowX);
 172         float offsetX = minX - scaleX * lowX;
 173         float scaleY = (maxY - minY) / (highY - lowY);
 174         float offsetY = minY - scaleY * lowY;
 175
 176         // Finally scale and offset the constructed vertices so that
 177         // they fit in the caller-supplied rectangle:
 178         for (pV = v; pV < lastV; pV += 2) {
 179                 pV[0] = scaleX * pV[0] + offsetX;
 180                 pV[1] = scaleY * pV[1] + offsetY;
 181         }
 182 } // SpiralStrip2D::SpiralStrip2D
 183
 184 SpiralStrip2D::~SpiralStrip2D() {
 185         delete[] v;
 186 } // SpiralStrip2D::~SpiralStrip2D
 187
 188
 189
 190
 191 ///////////////////////////////////////////////////////////////////////////////
 192 // SpiralTri2D:  Generate (x,y) vertices for a set of independent triangles,
 193 //      arranged in spiral fashion exactly as in SpiralStrip2D.
 194 //      One may rely on the fact that SpiralTri2D generates exactly the
 195 //      same triangles as SpiralStrip2D, so that comparison of images
 196 //      using the two primitives is meaningful.
 197 ///////////////////////////////////////////////////////////////////////////////
 198 SpiralTri2D::SpiralTri2D(int nTris, float minX, float maxX,
 199     float minY, float maxY) {
 200         SpiralStrip2D ts(nTris + 2, minX, maxX, minY, maxY);
 201         const int nVertices = 3 * nTris;
 202         v = new float[2 * nVertices];
 203
 204         float* pTris = v;
 205         float* pStrip = ts(0);
 206         bool front = true;      // winding order alternates in strip
 207         for (int i = 0; i < nTris; ++i) {
 208                 if (front) {
 209                         pTris[0] = pStrip[0];
 210                         pTris[1] = pStrip[1];
 211
 212                         pTris[2] = pStrip[2];
 213                         pTris[3] = pStrip[3];
 214
 215                         pTris[4] = pStrip[4];
 216                         pTris[5] = pStrip[5];
 217                 } else {
 218                         pTris[0] = pStrip[0];
 219                         pTris[1] = pStrip[1];
 220
 221                         pTris[2] = pStrip[4];
 222                         pTris[3] = pStrip[5];
 223
 224                         pTris[4] = pStrip[2];
 225                         pTris[5] = pStrip[3];
 226                 }
 227
 228                 front = !front;
 229                 pTris += 6;
 230                 pStrip += 2;
 231         }
 232 } // SpiralTri2D::SpiralTri2D
 233
 234 SpiralTri2D::~SpiralTri2D() {
 235         delete[] v;
 236 } // SpiralTri2D::~SpiralTri2D
 237
 238
 239 //////////////////////////////////////////////////////////////////////////////////////////////////////
 240 // Sphere3D: Forms a stacks/slices sphere and can return the vertices and index list for drawing it.
 241 //////////////////////////////////////////////////////////////////////////////////////////////////////
 242 Sphere3D::Sphere3D(float radius, int slices, int stacks)
 243 {
 244     // Loop vars.
 245     int curStack, curSlice;
 246
 247     // Can't have a sphere of less than 2 slices or stacks.
 248     assert(slices >= 2 && stacks >= 2);
 249
 250     // We have 2 verts for the top and bottom point, and then slices*(stacks-1) more for the
 251     // middle rings (it's stacks-1 since the top and bottom points each count in the stack count).
 252     numVertices = 2 + (slices*(stacks-1));
 253     vertices.reserve(numVertices*3);
 254     normals.reserve(numVertices*3);
 255
 256     // The top and bottom slices have <slices> tris in them, and the ones in the middle (since they're
 257     // made of quads) have 2*<slices> each.
 258     numIndices = 3*(2*slices + 2*(stacks-2)*slices);
 259     indices.reserve(numIndices);
 260
 261 #define VX(i) vertices[3*(i)+0]
 262 #define VY(i) vertices[3*(i)+1]
 263 #define VZ(i) vertices[3*(i)+2]
 264 #define VINDEX(st,sl) (1 + (((st)-1)*slices) + (sl))
 265 #ifndef M_PI
 266 #define M_PI 3.14159
 267 #endif
 268
 269     // Generate the verts.  The bottom and top verts are kind of special cases (they
 270     // occupy the first and last vertex slots, respectively).
 271     vertices.push_back(0);
 272     vertices.push_back(0);
 273     vertices.push_back(-radius);
 274     normals.push_back(0);
 275     normals.push_back(0);
 276     normals.push_back(-1);
 277
 278     // Now the inner rings; I can't decide whether it spreads the tri area out better to do this by
 279     // increments in the spherical coordinate phi or in the cartesian z, but I think phi is a better bet.
 280     for (curStack=1; curStack<stacks; curStack++)
 281     {
 282         float phi = M_PI - ((curStack / (float)stacks) * M_PI);
 283         float zVal = radius * cos(phi);
 284         float sliceRadius = sqrt(radius*radius - zVal*zVal);
 285         for (curSlice = 0; curSlice < slices; curSlice++)
 286         {
 287             float theta = 2*M_PI*((float)curSlice / slices);
 288
 289             float xVal = sliceRadius*cos(theta);
 290             float yVal = sliceRadius*sin(theta);
 291
 292             vertices.push_back(xVal);
 293             vertices.push_back(yVal);
 294             vertices.push_back(zVal);
 295             normals.push_back(xVal/radius);
 296             normals.push_back(yVal/radius);
 297             normals.push_back(zVal/radius);
 298         }
 299     }
 300
 301     vertices.push_back(0);
 302     vertices.push_back(0);
 303     vertices.push_back(radius);
 304     normals.push_back(0);
 305     normals.push_back(0);
 306     normals.push_back(1);
 307
 308     // Now to assemble them into triangles.  Do the top and bottom slices first.
 309     for (curSlice=0; curSlice<slices; curSlice++)
 310     {
 311         indices.push_back(0);
 312         indices.push_back((curSlice+1)%slices + 1);
 313         indices.push_back(curSlice+1);
 314
 315         indices.push_back(numVertices - 1);
 316         indices.push_back(numVertices - 2 - ((curSlice+1)%slices));
 317         indices.push_back(numVertices - 2 - curSlice);
 318     }
 319
 320     // Now for the inner rings.  We're already done with 2*slices triangles, so start after that.
 321     for (curStack=1; curStack<stacks-1; curStack++)
 322     {
 323         for (curSlice=0; curSlice<slices; curSlice++)
 324         {
 325             int nextStack = curStack+1;
 326             int nextSlice = (curSlice+1)%slices;
 327             indices.push_back(VINDEX(curStack, curSlice));
 328             indices.push_back(VINDEX(curStack, nextSlice));
 329             indices.push_back(VINDEX(nextStack, nextSlice));
 330
 331             indices.push_back(VINDEX(curStack, curSlice));
 332             indices.push_back(VINDEX(nextStack, nextSlice));
 333             indices.push_back(VINDEX(nextStack, curSlice));
 334         }
 335     }
 336
 337     assert(static_cast<int>(vertices.size()) == numVertices*3);
 338     assert(static_cast<int>(indices.size()) == numIndices);
 339
 340 #undef VX
 341 #undef VY
 342 #undef VZ
 343 #undef VINDEX
 344 }
 345
 346 // This returns the vertices: 3 floats per vertex in a tightly packed array (no padding between vertices).
 347 const float* Sphere3D::getVertices() const { return &(vertices[0]); }
 348 int Sphere3D::getNumVertices() const { return numVertices; }
 349
 350 // This returns the normals; same data format as the vertices.  And of course the number of normals is
 351 // the same as the number of vertices.
 352 const float* Sphere3D::getNormals() const { return &(normals[0]); }
 353
 354 // This returns a series of vertices that form triangles from the vertices (the indices specify loose
 355 // triangles, not tristrips or fans or whatnot.  So each triplet of indices is an individual triangle.)
 356 const unsigned int* Sphere3D::getIndices() const { return &(indices[0]); }
 357 int Sphere3D::getNumIndices() const { return numIndices; }
 358
 359
 360 } // namespace GLEAN