path: root/tests/general/triangle-rasterization.cpp

/**************************************************************************
 *
 * Copyright 2012 VMware, Inc.
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sub license, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice (including the
 * next paragraph) shall be included in all copies or substantial portions
 * of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 **************************************************************************/

/**
 * Triangle Rasterization Test
 *
 * This tests OpenGL triangle rasterization by comparing it with a software rasteriser
 *
 * There are 2 components to the test;
 *   1. Predefined sanity tests ensuring bounding box calculations are correct
 *   2. Randomised triangle drawing to attempt to test all possible triangles
 */

#include "piglit-util-gl-common.h"
#include "mersenne.hpp"

#include <time.h>
#include <vector>
#include <algorithm>

/* Data structures */
struct Vector
{
   Vector()
   {
   }

   Vector(float x, float y)
      : x(x), y(y)
   {
   }

   float x, y;
};

struct Triangle {
   Triangle()
   {
   }

   Triangle(const Vector& v0, const Vector& v1, const Vector& v2)
   {
      v[0] = v0;
      v[1] = v1;
      v[2] = v2;
   }

   Vector& operator[](int i)
   {
      return v[i];
   }

   const Vector& operator[](int i) const
   {
      return v[i];
   }

   Vector v[3];
};


/* Command line arguments */
bool use_fbo = false;
bool break_on_fail = false;
bool print_triangle = false;
int random_test_count = 100;

/* Fixed point format */
const int FIXED_SHIFT = 4;
const int FIXED_ONE = 1 << FIXED_SHIFT;

/* Default test size */
int fbo_width = 256;
int fbo_height = 256;

/* Piglit variables */

PIGLIT_GL_TEST_MAIN(
    fbo_width /*window_width*/,
    fbo_height /*window_height*/,
    PIGLIT_GL_VISUAL_RGB | PIGLIT_GL_VISUAL_ALPHA | PIGLIT_GL_VISUAL_DOUBLE)

/* Globals */
int test_id = 0;
Mersenne mersenne;
std::vector<Triangle> fixed_tests;


/* std::algorithm min/max with 3 arguments! :D */
namespace std {
   template<typename T>
   T min(T& a, T& b, T& c)
   {
      return (a < b) ? std::min(a, c) : std::min(b, c);
   }

   template<typename T>
   T max(T& a, T& b, T& c)
   {
      return (a > b) ? std::max(a, c) : std::max(b, c);
   }
}

/* Proper rounding of float to integer */
int iround(float v)
{
   if (v > 0.0f) v += 0.5f;
   if (v < 0.0f) v -= 0.5f;
   return (int)v;
}

/* Calculate log2 for integers */
int log2i(int x)
{
   int res = 0 ;
   while (x >>= 1) ++res;
   return res ;
}


/* Based on http://devmaster.net/forums/topic/1145-advanced-rasterization */
void rast_triangle(uint8_t* buffer, uint32_t stride, const Triangle& tri)
{
   float center_offset = -0.5f;

   /* 28.4 fixed point coordinates */
   int x1 = iround(FIXED_ONE * (tri[0].x + center_offset));
   int x2 = iround(FIXED_ONE * (tri[1].x + center_offset));
   int x3 = iround(FIXED_ONE * (tri[2].x + center_offset));

   int y1 = iround(FIXED_ONE * (tri[0].y + center_offset));
   int y2 = iround(FIXED_ONE * (tri[1].y + center_offset));
   int y3 = iround(FIXED_ONE * (tri[2].y + center_offset));

   /* Force correct vertex order */
   const int cross = (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2);
   if (cross > 0) {
      std::swap(x1, x3);
      std::swap(y1, y3);
   }

   /* Deltas */
   const int dx12 = x1 - x2;
   const int dx23 = x2 - x3;
   const int dx31 = x3 - x1;

   const int dy12 = y1 - y2;
   const int dy23 = y2 - y3;
   const int dy31 = y3 - y1;

   /* Fixed-point deltas */
   const int fdx12 = dx12 << FIXED_SHIFT;
   const int fdx23 = dx23 << FIXED_SHIFT;
   const int fdx31 = dx31 << FIXED_SHIFT;

   const int fdy12 = dy12 << FIXED_SHIFT;
   const int fdy23 = dy23 << FIXED_SHIFT;
   const int fdy31 = dy31 << FIXED_SHIFT;

   /* Bounding rectangle */
   int minx = std::min(x1, x2, x3) >> FIXED_SHIFT;
   int maxx = (std::max(x1, x2, x3) - 1) >> FIXED_SHIFT;

   int miny = (std::min(y1, y2, y3) + 1) >> FIXED_SHIFT;
   int maxy = std::max(y1, y2, y3) >> FIXED_SHIFT;

   minx = std::max(minx, 0);
   maxx = std::min(maxx, fbo_width - 1);

   miny = std::max(miny, 0);
   maxy = std::min(maxy, fbo_height - 1);

   /* Half-edge constants */
   int c1 = dy12 * x1 - dx12 * y1;
   int c2 = dy23 * x2 - dx23 * y2;
   int c3 = dy31 * x3 - dx31 * y3;

   /* Correct for fill convention */
   if (dy12 < 0 || (dy12 == 0 && dx12 > 0)) c1++;
   if (dy23 < 0 || (dy23 == 0 && dx23 > 0)) c2++;
   if (dy31 < 0 || (dy31 == 0 && dx31 > 0)) c3++;

   int cy1 = c1 + dx12 * (miny << FIXED_SHIFT) - dy12 * (minx << FIXED_SHIFT);
   int cy2 = c2 + dx23 * (miny << FIXED_SHIFT) - dy23 * (minx << FIXED_SHIFT);
   int cy3 = c3 + dx31 * (miny << FIXED_SHIFT) - dy31 * (minx << FIXED_SHIFT);

   /* Perform rasterization */
   buffer += miny * stride;
   for (int y = miny; y <= maxy; y++) {
      int cx1 = cy1;
      int cx2 = cy2;
      int cx3 = cy3;

      for (int x = minx; x <= maxx; x++) {
         if (cx1 > 0 && cx2 > 0 && cx3 > 0) {
            ((uint32_t*)buffer)[x] = 0x00FF00FF;
         }

         cx1 -= fdy12;
         cx2 -= fdy23;
         cx3 -= fdy31;
      }

      cy1 += fdx12;
      cy2 += fdx23;
      cy3 += fdx31;

      buffer += stride;
   }
}


/* Prints an ascii representation of the triangle */
void triangle_art(uint32_t* buffer)
{
   int minx = fbo_width - 1, miny = fbo_height - 1;
   int maxx = 0, maxy = 0;

   /* Find bounds so we dont have to print whole screen */
   for (int y = 0; y < fbo_height; ++y) {
      for (int x = 0; x < fbo_width; ++x) {
         if (buffer[y*fbo_width + x] & 0xFFFFFF00) {
            if (x < minx) minx = x;
            if (y < miny) miny = y;
            if (x > maxx) maxx = x;
            if (y > maxy) maxy = y;
         }
      }
   }

   /* Nothing drawn */
   if (minx > maxx || miny > maxy)
      return;

   --minx; --miny;
   ++maxx; ++maxy;

   /* Print an ascii representation of triangle */
   for (int y = maxy; y >= miny; --y) {
      for (int x = minx; x <= maxx; ++x) {
         uint32_t val = buffer[y*fbo_width + x] & 0xFFFFFF00;

         if (val == 0xFF000000) {
            printf("+");
         } else if (val == 0x00FF0000) {
            printf("-");
         } else if (val == 0xFFFF0000) {
            printf("o");
         } else if (val == 0) {
            printf(".");
         } else {
            printf("?");
         }
      }

      printf("\n");
   }

   printf("\n");
}


/* Reads buffer from OpenGL and checks for any colour other than black or yellow
 * (black = background, yellow = both opengl AND software rast drew to that pixel)
 */
uint32_t* check_triangle()
{
   static uint32_t* buffer = 0;
   if (!buffer) buffer = new uint32_t[fbo_width * fbo_height];

   glReadPixels(0, 0, fbo_width, fbo_height, GL_RGBA, GL_UNSIGNED_INT_8_8_8_8, buffer);

   for (int y = 0; y < fbo_height; ++y) {
      for (int x = 0; x < fbo_width; ++x) {
         uint32_t val = buffer[y*fbo_width + x] & 0xFFFFFF00;

         if (val != 0 && val != 0xFFFF0000) {
            return buffer;
         }
      }
   }

   return NULL;
}


/* Performs test using tri */
GLboolean test_triangle(const Triangle& tri)
{
   static uint32_t* buffer = 0;
   if (!buffer) buffer = new uint32_t[fbo_width * fbo_height];

   /* Clear OpenGL and software buffer */
   glClear(GL_COLOR_BUFFER_BIT);
   memset(buffer, 0, sizeof(uint32_t) * fbo_width * fbo_height);

   /* Software rasterise triangle and blit it to OpenGL */
   rast_triangle((uint8_t*)buffer, fbo_width * 4, tri);
   glDrawPixels(fbo_width, fbo_height, GL_RGBA, GL_UNSIGNED_INT_8_8_8_8, buffer);

   /* Draw OpenGL triangle */
   glEnableClientState(GL_VERTEX_ARRAY);
   glVertexPointer(2, GL_FLOAT, 0, tri.v);
   glDrawArrays(GL_TRIANGLES, 0, 3);
   glDisableClientState(GL_VERTEX_ARRAY);

   /* Check the result and print relevant error messages */
   if (uint32_t* result = check_triangle()) {
      printf("FAIL: %d. (%f, %f), (%f, %f), (%f, %f)\n", test_id,
             tri[0].x, tri[0].y, tri[1].x, tri[1].y, tri[2].x, tri[2].y);

      if (print_triangle) {
         triangle_art(result);
      }

      fflush(stdout);
      return GL_FALSE;
   }

   return GL_TRUE;
}


/* Generate a random triangle */
void random_triangle(Triangle& tri)
{
   int size = 1 << (mersenne.value() % (log2i(fbo_width) + 1));

   for (int i = 0; i < 3; ++i) {
      tri[i].x = (mersenne.value() % (size * FIXED_ONE)) * (1.0f / FIXED_ONE);
      tri[i].y = (mersenne.value() % (size * FIXED_ONE)) * (1.0f / FIXED_ONE);
   }

   test_id++;
}


/* Render */
enum piglit_result
piglit_display(void)
{
   GLuint fb, tex;

   /* If using FBO, set it up */
   if (use_fbo) {
      glDisable(GL_CULL_FACE);

      glGenTextures(1, &tex);
      glBindTexture(GL_TEXTURE_2D, tex);
      glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
      glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
      glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, fbo_width, fbo_height, 0, GL_BGRA, GL_UNSIGNED_BYTE, NULL);

      glGenFramebuffersEXT(1, &fb);
      glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, fb);
      glViewport(0, 0, fbo_width, fbo_height);

      glFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT,
                 GL_COLOR_ATTACHMENT0_EXT,
                 GL_TEXTURE_2D,
                 tex,
                 0);

      assert(glGetError() == 0);
      assert(glCheckFramebufferStatusEXT(GL_FRAMEBUFFER_EXT) == GL_FRAMEBUFFER_COMPLETE_EXT);

      glBindTexture(GL_TEXTURE_2D, 0);
   }

   /* Set render state */
   glColor4f(1.0f, 0.0f, 0.0f, 1.0f);
   glClearColor(0.0f, 0.0f, 0.0f, 1.0f);

   glEnable(GL_BLEND);
   glBlendEquation(GL_FUNC_ADD);
   glBlendFunc(GL_ONE, GL_ONE);

   glViewport(0, 0, fbo_width, fbo_height);
   piglit_ortho_projection(fbo_width, fbo_height, GL_FALSE);

   /* Perform test */
   GLboolean pass = GL_TRUE;
   if (piglit_automatic) {
      int fail_count = 0;

      printf("Running %d fixed tests\n", (int)fixed_tests.size());
      for (std::vector<Triangle>::iterator itr = fixed_tests.begin(); itr != fixed_tests.end() && !(fail_count && break_on_fail); ++itr) {
         if (!test_triangle(*itr))
            ++fail_count;
      }

      printf("Running %d random tests\n", random_test_count);
      for (int i = 0; i < random_test_count && !(fail_count && break_on_fail); ++i) {
         Triangle tri;
         random_triangle(tri);

         if (!test_triangle(tri))
            ++fail_count;
      }

      printf("Failed %d tests\n", fail_count);
      fflush(stdout);

      if (fail_count)
         pass = GL_FALSE;
   } else {
      Triangle tri;
      random_triangle(tri);
      pass &= test_triangle(tri);

      glDisable(GL_BLEND);

      /* If using FBO, draw the fbo to screen */
      if (use_fbo) {
         glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, 0);
         glViewport(0, 0, piglit_width, piglit_height);
         piglit_ortho_projection(piglit_width, piglit_height, GL_FALSE);

         glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_COMBINE);
         glTexEnvi(GL_TEXTURE_ENV, GL_COMBINE_RGB,   GL_REPLACE);
         glTexEnvi(GL_TEXTURE_ENV, GL_COMBINE_ALPHA, GL_REPLACE);

         glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
         glEnable(GL_TEXTURE_2D);
         glBindTexture(GL_TEXTURE_2D, tex);

         piglit_draw_rect_tex(0, 0, piglit_width, piglit_height, 0, 0, 1, 1);

         glDisable(GL_TEXTURE_2D);
      }

      piglit_present_results();
   }

   /* Cleanup FBO if necessary */
   if (use_fbo) {
      glDeleteTextures(1, &tex);
      glDeleteFramebuffersEXT(1, &fb);
      glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, 0);
   }

   assert(glGetError() == 0);

   return pass ? PIGLIT_PASS : PIGLIT_FAIL;
}


/* Create some fixed tests to test bounding box in/exclusivity,
 *
 *  /|\
 * /_|_\  Tests these 4 triangles but shifting them from -1/16 to +1/16
 * \ | /  around the center point
 *  \|/
 */
void init_fixed_tests()
{
   const float mid = 0.5f;
   const float shift = 1.0f / FIXED_ONE;
   const float size  = 3.0f / FIXED_ONE;

   Vector vv[] = {
      Vector(mid, mid + size),
      Vector(mid, mid - size),
   };

   Vector vh[] = {
      Vector(mid - size, mid),
      Vector(mid + size, mid),
   };

   Vector vm(mid, mid);

   /* Loop through the 4 possible triangles */
   for (int vy = 0; vy < 2; ++vy) {
      for (int vx = 0; vx < 2; ++vx) {
         Triangle tri;

         tri[0] = vh[vx];
         tri[1] = vv[vy];
         tri[2] = vm;

         /* Loop through the x and y shifts */
         for (int y = -1; y <= 1; ++y) {
            for (int x = -1; x <= 1; ++x) {
               Triangle shifted = tri;

               for (int i = 0; i < 3; ++i) {
                  shifted[i].x += x * shift;
                  shifted[i].y += y * shift;
               }

               fixed_tests.push_back(shifted);
            }
         }
      }
   }
}


/* Read command line arguments! */
void
piglit_init(int argc, char **argv)
{
   uint32_t seed = 0xfacebeef ^ time(NULL);

   for (int i = 1; i < argc; ++i) {
      if (strcmp(argv[i], "-break_on_fail") == 0){
         break_on_fail = true;
         printf("Execution will stop on first fail\n");
      } else if (strcmp(argv[i], "-print_triangle") == 0){
         print_triangle = true;
      } else if (strcmp(argv[i], "-max_size") == 0){
         glGetIntegerv(GL_MAX_TEXTURE_SIZE, &fbo_width);

         fbo_height = fbo_width;
         piglit_width = fbo_width;
         piglit_height = fbo_height;
      } else if (strcmp(argv[i], "-use_fbo") == 0){
         use_fbo = true;
         printf("FBOs are in use\n");
      } else if (i + 1 < argc) {
         if (strcmp(argv[i], "-count") == 0) {
            random_test_count = strtoul(argv[++i], NULL, 0);
         } else if (strcmp(argv[i], "-seed") == 0) {
            seed = strtoul(argv[++i], NULL, 0);
         }
      }
   }

   printf("Random seed: 0x%08X\n", seed);
   mersenne.init(seed);

   init_fixed_tests();
}