Re: [xmoto-dev] SDL_gfx help

["Rasmus Neckelmann" <neckelmann@xxxxxxxxx>]

On 1/25/07, Kees Jongenburger <kees.jongenburger@xxxxxxxxx> wrote:
> > transformations or anything. I don't know about SDL_gfx, but making
> > such a drawing function should be quite basic - interpolate the x
> > (screen) coordinate and the u,v (texture) coordinates over the edges
> > of the polygon, and then render the horizontal lines of the polygon
> > (with interpolated u,v coordinates). Nice thing about x-moto is that
> > no perspective correction or shading is required - i.e. it can be
> > implemented quite efficiently in plain c/c++ (even with no asm).
> This will not work when the object is rotated like the wheels
> and the width/height ration of the body is changed. or am I missing something?

The usual way to draw textured polygons, at least when talking
(modern) 3d, is to seperate transformation and texturing:

1. Polygons are first transformed according to how the scene is set up
- i.e. they are moved as specified by the camera and individual
rotations, etc.

2. Then they are projected unto the screen. I.e. converted to 2d.

3. The actual drawing (rasterization) of the polygons. At this point
all transformations are totally forgotten, the polygons are reduced to
simply being a list of 2d vertices (each both containing x,y on the
screen and u,v on the texture). These polygons can be of any shape,
rotated, stretched, scaled, etc.

I've cleaned up some old code of mine which draws textured polygons.
Unfortunately not as fast as I remembered, it will probably require
major optimizations to be of any use :)

Haven't tried the code on anything but windows. Needs SDL.

Note: it probably needs some tweaking of <= and <'s to handle adjecant
polygons probably. Have never been tested for that.

--
Rasmus Neckelmann

#include <string.h>

#include "PolyDraw.h"

#if defined(MIN)
  #undef MIN
#endif
#define MIN(a,b) ((a)<(b)?(a):(b))

#if defined(MAX)
  #undef MAX
#endif
#define MAX(a,b) ((a)>(b)?(a):(b))

PolyDraw::PolyDraw(Buffer *pBuf) {
  /* Set defaults */
  m_pLeftEdge = NULL;
  m_pRightEdge = NULL;
  m_pBuf = NULL;

  setRenderBuffer(pBuf);
}

PolyDraw::~PolyDraw() {
  /* Anything to be released? */
  _ReleaseEdgeBuffers();
}

void PolyDraw::setRenderBuffer(Buffer *pBuf) {
  /* Do we need to allocate new edge buffers? */
  if(m_pBuf == NULL || m_pBuf->nHeight != pBuf->nHeight) {
    /* Yup, do it - but first free old ones */
    _ReleaseEdgeBuffers();
    
    m_pLeftEdge = new EdgeValue[pBuf->nHeight];
    m_pRightEdge = new EdgeValue[pBuf->nHeight];
    
    memset(m_pLeftEdge,0,pBuf->nHeight * sizeof(EdgeValue));
    memset(m_pRightEdge,0,pBuf->nHeight * sizeof(EdgeValue));
  }

  /* Set target rendering buffer */
  m_pBuf = pBuf;    
}

/*=============================================================================
Function for rendering n-side convex polygons.

Screen vertices are supplied in an integer array ordered like this:
{x1,y1,x2,y2,x3,y3,...}, the same goes for the texture (u,v) coordinates. Note
that the texture coordinates aren't given in actual texel coordinates, instead
they are in an 8-bit format, with (0,0) indicating the
upper left corner of the texture, and (255,255) indicating the lower right. 
Textures are repeated if these values are exceeded.

Important: Texture buffers must have n^2 pixel alignment, and must be of n^2
sizes. Maximum size is 256x256. They don't need to be square.

Another important restriction is that the texture pixel format must be the 
same as the one for the screen.

Probably more restrictions I don't remember :)

TODO: better clipping and culling. Easiest would be to check the bounding box
      of the polygon to be rendered against the screen box. If no touch, don't
      bother to interpolate anything.
      A more 3d'ish approach would be to actually clip the polygons against 
      edge planes. It would also remove the need for clipping in 
      _RenderHLine*() and friends.
      
TODO: assembler. :)  I simply don't think this code is fast enough to be of 
      practical use.
=============================================================================*/
void PolyDraw::render(int *pnScreenVerts,int *pnTexVerts,int nNumCorners,
                      Buffer *pTexture) {
  /* If no buffers, abort */
  if(m_pBuf == NULL || m_pLeftEdge == NULL || m_pRightEdge == NULL)
    return; /* TODO: maybe an exception instead? */                      
                      
  /* Determine topmost and bottommost screen vertex */
  int nTop = -1,nTopY = 0,
      nBottom = -1,nBottomY = 0;
  
  for(int i=0,*pn=pnScreenVerts;i<nNumCorners;i++,pn+=2) {
    if(nTop < 0 || *(pn+1) < nTopY) {
      /* This is the new topmost vertex */
      nTop = i;
      nTopY = *(pn+1);
    }
    
    if(nBottom < 0 || *(pn+1) > nBottomY) {
      /* This is the new bottommost vertex */
      nBottom = i;
      nBottomY = *(pn+1);
    }
  }
  
  /* Interpolate x (screen) and u,v (texture) coordinates along the left polygon edges */
  int nCurrentVertex = nTop;
  
  do {
    /* What's the next corner down along the edge? */
    int nNextVertex = nCurrentVertex - 1; /* Minus one because we're using "right winding" polygons */
    if(nNextVertex < 0) nNextVertex = nNumCorners - 1;
      
    /* Get y-value of current vertex and next */
    int nY1 = pnScreenVerts[nCurrentVertex*2 + 1];
    int nY2 = pnScreenVerts[nNextVertex*2 + 1];
    
    /* If the next one is LOWER on the screen we can interpolate the edge (in case they are equal we
       can just ignore the edge) */
    if(nY2 > nY1) {
      /* Get vertex data to be interpolated */
      int nX1 = pnScreenVerts[nCurrentVertex*2];
      int nX2 = pnScreenVerts[nNextVertex*2];

      int nU1 = pnTexVerts[nCurrentVertex*2];
      int nU2 = pnTexVerts[nNextVertex*2];

      int nV1 = pnTexVerts[nCurrentVertex*2 + 1];
      int nV2 = pnTexVerts[nNextVertex*2 + 1];
      
      /* Interpolate edge (left) */
      _LerpEdge(nY1,nY2,m_pLeftEdge,nX1,nX2,nU1,nU2,nV1,nV2);      
    }
    
    nCurrentVertex = nNextVertex;
    
  } while(nCurrentVertex != nBottom);
  
  /* Now, do the same for the right edge */
  nCurrentVertex = nTop;
    
  do {
    int nNextVertex = nCurrentVertex + 1;
    if(nNextVertex >= nNumCorners) nNextVertex = 0;
      
    int nY1 = pnScreenVerts[nCurrentVertex*2 + 1];
    int nY2 = pnScreenVerts[nNextVertex*2 + 1];
    
    if(nY2 > nY1) {
      int nX1 = pnScreenVerts[nCurrentVertex*2];
      int nX2 = pnScreenVerts[nNextVertex*2];

      int nU1 = pnTexVerts[nCurrentVertex*2];
      int nU2 = pnTexVerts[nNextVertex*2];

      int nV1 = pnTexVerts[nCurrentVertex*2 + 1];
      int nV2 = pnTexVerts[nNextVertex*2 + 1];
      
      /* Interpolate edge (right) */
      _LerpEdge(nY1,nY2,m_pRightEdge,nX1,nX2,nU1,nU2,nV1,nV2);
    }

    nCurrentVertex = nNextVertex;
    
  } while(nCurrentVertex != nBottom);
  
  /* Determine 2^n size of texture */
  int nWSq = _TexSq(pTexture->nWidth);
  int nHSq = _TexSq(pTexture->nHeight);
  
  if(nWSq == 0 || nHSq == 0) {
    return; /* TODO: maybe a "non-power of two texture size" exception? */
  }
  
  /* Max texture size is 256x256 */
  if(nWSq > 8 || nHSq > 8) {
    return; /* TODO: maybe throw a "texture too large" exception? */
  }
  
  /* Other precalc stuff */
  int nASq = _TexSq(pTexture->nPixelAlign);
  int nPitchSq = _TexSq(pTexture->nPitch);
  
  if(nASq == 0) {
    return; /* TODO: maybe a "non-power of two pixel alignment" exception */
  }
  
  if(nPitchSq == 0) {
    return; /* TODO: maybe a "non-power of two texture pitch" exception */
  }
  
  /* At this point we know everything we need about the edges - now for the 
     time consuming part: rendering of the individual pixels */
  int nStartY = MAX(nTopY,0);
  int nEndY = MIN(nBottomY,m_pBuf->nHeight-1);
     
  /* 16-bit color code (fast) or general code (slow)? */    
  if(m_pBuf->nPixelSize == 2) {
    /* This loop only works with 16-bit pixels */
    for(int y=nStartY;y<=nEndY;y++) {
      _RenderHLine16(y,&m_pLeftEdge[y],&m_pRightEdge[y],pTexture,nWSq,nHSq,nPitchSq);
    }
  }
  else {
    /* This loop works with all pixel sizes */
    for(int y=nStartY;y<=nEndY;y++) {
      _RenderHLine(y,&m_pLeftEdge[y],&m_pRightEdge[y],pTexture,nWSq,nHSq,nPitchSq,nASq);
    }
  }
}

/*=============================================================================
Various helper functions
=============================================================================*/
void PolyDraw::_ReleaseEdgeBuffers(void) {
  /* Free edge buffer memory */
  if(m_pLeftEdge != NULL)
    delete [] m_pLeftEdge;

  if(m_pRightEdge != NULL)
    delete [] m_pRightEdge;
    
  m_pLeftEdge = NULL;
  m_pRightEdge = NULL;
}

void PolyDraw::_LerpEdge(int y1,int y2,EdgeValue *pEdgeBuf,
                         int x1,int x2,int u1,int u2,int v1,int v2) {
  int nYRange = y2-y1;                         
  
  /* This function is called once per polygon edge - that is, the code
     inside the loop is invoked twice per horizontal line of the screen
     occupied by the polygon.
     
     Optimization is therefore not superimportant here. */
                      
  if(nYRange > 0) {
    /* TODO: optimize this loop with fixed-point math, so we can avoid the 
             3 divides and the 3 multiplications */
  
    /* Linear interpolation along a polygon edge */    
    for(int y=MAX(y1,0);y<=MIN(y2,m_pBuf->nHeight-1);y++) {
      EdgeValue *pV = &pEdgeBuf[y];
      
      int i = y - y1;
      
      pV->x = x1 + (i * (x2 - x1)) / nYRange;
      pV->u = u1 + (i * (u2 - u1)) / nYRange;
      pV->v = v1 + (i * (v2 - v1)) / nYRange;
    }                         
  }
}

int PolyDraw::_TexSq(int n) {
  /* If n==256 return 8, if n==32 return 5, etc */
  /* if x^2 = n can't be solved for a positive integer x, then return 0 */  
  int nSq = 0;
  for(int i=0;i<31;i++) {
    if(n & (1<<i)) {
      if(nSq > 0) return 0; /* invalid texture size */
      nSq = i;
    }
  }  
  return nSq;
}

/*=============================================================================
Functions for rendering horizontal line spans of polygons. This is probably 
where optimization efforts should be placed.

  _RenderHLine16() works only with 16-bit pixels with a 16-bit alignment.
  _RenderHLine() works with any size of pixel, as long as the alignment is n^2, 
  i.e. 1, 2, 4, etc).
  
TODO: implement a _RenderHLine32(), although it probably would be too slow.
TODO: lots and lots of optimization to do :)
=============================================================================*/
void PolyDraw::_RenderHLine16(int y,EdgeValue *pLeft,EdgeValue *pRight,Buffer *pTexture,int nWSq,int nHSq,int nPitchSq) {
  /* Determine pointer to beginning of line in target buffer */
  short *pn = (short *)&m_pBuf->pcData[y * m_pBuf->nPitch + MAX(0,pLeft->x) * m_pBuf->nPixelAlign];

  int nXRange = pRight->x - pLeft->x;
  int nURange = pRight->u - pLeft->u;
  int nVRange = pRight->v - pLeft->v;
  
  int nWRightShift = 8 - nWSq;
  int nHRightShift = 8 - nHSq;
  
  int nPixelAlign = m_pBuf->nPixelAlign;
  int nPixelSize = m_pBuf->nPixelSize;

  int nTexelAlign = pTexture->nPixelAlign;
  
  if(nPixelSize != pTexture->nPixelSize) return; /* eeeerrorrr */

  short *pnT = (short *)pTexture->pcData;

  if(nXRange > 0) {  
    /* Linear interpolation of texture coordinates over a horizontal line of a polygon */
    int nStartX = MAX(pLeft->x,0);
    int nEndX = MIN(pRight->x,m_pBuf->nWidth-1);

    /* Fixed-point slope of u and v interpolations */    
    int nUSlope = (nURange << 8) / nXRange;
    int nVSlope = (nVRange << 8) / nXRange;
    
    int nSkip = nStartX - pLeft->x;
    int nUSum = nSkip * nUSlope;
    int nVSum = nSkip * nVSlope;
    
    for(int x=nStartX;x<=nEndX;x++) {
      /* Interpolate (u,v) */
      int nU = pLeft->u + (nUSum >> 8);
      int nV = pLeft->v + (nVSum >> 8);
       
      nUSum += nUSlope;
      nVSum += nVSlope;
            
      /* Make sure (u,v) are inside the texture space (defined to be (0,0) to (0xff,0xff)) */
      nU &= 0xff;
      nV &= 0xff;
      
      /* Map (u,v) to actual texture coordinates - and do trick to get texture offset */
      int k = (nU >> nWRightShift) + ((nV >> nHRightShift) << nWSq);

      /* Copy texel to pixel - note that no memcpy() is needed */      
      *pn = pnT[k];
      
      /* Next pixel */
      pn ++;
    }
  }
}

void PolyDraw::_RenderHLine(int y,EdgeValue *pLeft,EdgeValue *pRight,Buffer *pTexture,int nWSq,int nHSq,int nPitchSq,int nASq) {
  /* Determine pointer to beginning of line in target buffer */
  char *pc = &m_pBuf->pcData[y * m_pBuf->nPitch + MAX(0,pLeft->x) * m_pBuf->nPixelAlign];
  
  int nXRange = pRight->x - pLeft->x;
  int nURange = pRight->u - pLeft->u;
  int nVRange = pRight->v - pLeft->v;
  
  int nWRightShift = 8 - nWSq;
  int nHRightShift = 8 - nHSq;
  
  int nPixelAlign = m_pBuf->nPixelAlign;
  int nPixelSize = m_pBuf->nPixelSize;

  int nTexelAlign = pTexture->nPixelAlign;
  
  if(nPixelSize != pTexture->nPixelSize) return; /* eeeerrorrr */
  
  char *pcT = pTexture->pcData;
  
  if(nXRange > 0) {  
    /* Linear interpolation of texture coordinates over a horizontal line of a polygon */
    int nStartX = MAX(pLeft->x,0);
    int nEndX = MIN(pRight->x,m_pBuf->nWidth-1);

    /* Fixed-point slope of u and v interpolations */    
    int nUSlope = (nURange << 8) / nXRange;
    int nVSlope = (nVRange << 8) / nXRange;
    
    int nSkip = nStartX - pLeft->x;
    int nUSum = nSkip * nUSlope;
    int nVSum = nSkip * nVSlope;
    
    for(int x=nStartX;x<=nEndX;x++) {
      /* Interpolate (u,v) */
      int nU = pLeft->u + (nUSum >> 8);
      int nV = pLeft->v + (nVSum >> 8);
       
      nUSum += nUSlope;
      nVSum += nVSlope;
            
      /* Make sure (u,v) are inside the texture space (defined to be (0,0) to (0xff,0xff)) */
      nU &= 0xff;
      nV &= 0xff;
      
      /* Map (u,v) to actual texture coordinates - and do trick to get texture offset */
      int k = ((nU >> nWRightShift) << nASq) + ((nV >> nHRightShift) << nPitchSq);
      
      /* Copy texel to pixel */
      memcpy(pc,&pcT[k],nPixelSize);
      
      /* Next pixel */
      pc += nPixelAlign;
    }
  }
}


#ifndef __POLYDRAW_H__
#define __POLYDRAW_H__

class PolyDraw {
  public:  
    /* Types */
    struct Buffer {
      int nWidth,nHeight;       /* Width and height of buffer */
      int nPitch;               /* Size of a horizontal line (in bytes) */
      char *pcData;             /* Pointer to pixel data */
      int nPixelSize;           /* Size of a pixel (in bytes) */
      int nPixelAlign;          /* Pixels are aligned to occupy this number of bytes */
    };
    
    struct EdgeValue {
      int x;                    /* Interpolated x-value (screen) */
      int u;                    /* Interpolated u-value (texture) */
      int v;                    /* Interpolated v-value (texture) */
    };
    
    /* Construction/destruction */
    PolyDraw(Buffer *pBuf = NULL);
    ~PolyDraw();    
  
    /* Methods */
    void setRenderBuffer(Buffer *pBuf);
    void render(int *pnScreenVerts,int *pnTexVerts,int nNumCorners,Buffer *pTexture);
                                               
  private:
    /* Data */
    Buffer *m_pBuf;
    EdgeValue *m_pLeftEdge,*m_pRightEdge;
    
    /* Helpers */
    void _ReleaseEdgeBuffers(void);
    void _LerpEdge(int y1,int y2,EdgeValue *pEdgeBuf,
                   int x1,int x2,int u1,int u2,int v1,int v2);
    
    void _RenderHLine(int y,EdgeValue *pLeft,EdgeValue *pRight,Buffer *pTexture,int nWSq,int nHSq,int nPitchSq,int nASq);
    void _RenderHLine16(int y,EdgeValue *pLeft,EdgeValue *pRight,Buffer *pTexture,int nWSq,int nHSq,int nPitchSq);          

    int _TexSq(int n);
};

#endif

#include <stdio.h>
#include <string.h>
#include <math.h>

#include "SDL/SDL.h"

#include "PolyDraw.h"

unsigned char m_cTexture[] = {
  0xff,0xff,  0x08,0x08,
  0x08,0x08,  0xff,0xff,
};

unsigned char m_cTexture2[] = {
  0x84,0x04,  0x00,0x80,
  0x00,0x80,  0x84,0x04,
};

int nPolyVertices[4 * 2] = {
  -20, -40,
  50, -30,
  60, 70,
  -30, 80,
};

int nPolyTextureVertices[4 * 2] = {
  -3*0xff,  -3*0xff,
  3*0xff, -3*0xff,
  3*0xff, 3*0xff,
  -3*0xff,      3*0xff,
};


#define SCREEN_WIDTH 320 
#define SCREEN_HEIGHT 240

#define TEXTURE_WIDTH 2
#define TEXTURE_HEIGHT 2

int main(int nNumArgs,char **ppcArgs) {
  SDL_Init(SDL_INIT_VIDEO|SDL_INIT_TIMER);
  SDL_Surface *pSDLScreen = SDL_SetVideoMode(SCREEN_WIDTH,SCREEN_HEIGHT,16,SDL_DOUBLEBUF);
  if(pSDLScreen == NULL) return 0;
  
  SDL_Event Event;
  bool bRun = true; 
  
  PolyDraw::Buffer ScreenBuf;
  ScreenBuf.nPixelAlign = 2;
  ScreenBuf.nPixelSize = 2;
  ScreenBuf.nWidth = SCREEN_WIDTH;
  ScreenBuf.nHeight = SCREEN_HEIGHT;
  
  PolyDraw Renderer(&ScreenBuf);
  
  /* Setup texture 1 */
  PolyDraw::Buffer TestTexture;
  
  TestTexture.pcData = (char *)m_cTexture;
  TestTexture.nPitch = TEXTURE_WIDTH * 2;
  TestTexture.nPixelAlign = 2;
  TestTexture.nPixelSize = 2;
  TestTexture.nWidth = TEXTURE_WIDTH;
  TestTexture.nHeight = TEXTURE_HEIGHT;

  /* Setup texture 2 */
  PolyDraw::Buffer TestTexture2;
  
  TestTexture2.pcData = (char *)m_cTexture2;
  TestTexture2.nPitch = TEXTURE_WIDTH * 2;
  TestTexture2.nPixelAlign = 2;
  TestTexture2.nPixelSize = 2;
  TestTexture2.nWidth = TEXTURE_WIDTH;
  TestTexture2.nHeight = TEXTURE_HEIGHT;

  int nNumFrames = 0;
  int nStart = SDL_GetTicks();
  while(bRun) {
  
    SDL_PumpEvents();
    
    while(SDL_PollEvent(&Event)) {
      switch(Event.type) {
        case SDL_QUIT:
          bRun = false;
          break;
        case SDL_KEYDOWN:
          if(Event.key.keysym.sym == SDLK_ESCAPE) bRun = false;
          break;
      }
    }

    /* Clear screen */
    SDL_FillRect(pSDLScreen,NULL,0); 
    
    /* Render stuff */
    SDL_LockSurface(pSDLScreen);
    ScreenBuf.pcData = (char *)pSDLScreen->pixels;
    ScreenBuf.nPitch = pSDLScreen->pitch;    
    
    int nScreenV[4 * 2];
    
    float fScale = 4 + 3 * sin((float)SDL_GetTicks() / 300.0f);

    for(int i=0;i<4;i++) {
      nScreenV[i*2] = (cos((float)SDL_GetTicks() / 800.0f) * (float)nPolyVertices[i*2] * fScale) 
                      + (-sin((float)SDL_GetTicks() / 800.0f) * (float)nPolyVertices[i*2+1] * fScale) 
                      + SCREEN_WIDTH / 2;
      nScreenV[i*2+1] = (sin((float)SDL_GetTicks() / 800.0f) * (float)nPolyVertices[i*2] * fScale) 
                        + (cos((float)SDL_GetTicks() / 800.0f) * (float)nPolyVertices[i*2+1] * fScale)  
                        + SCREEN_HEIGHT / 2;
    }        
    Renderer.render(nScreenV,nPolyTextureVertices,4,&TestTexture2);

    fScale = 4 + 3 * cos((float)SDL_GetTicks() / 300.0f);
    for(int i=0;i<4;i++) {
      nScreenV[i*2] = (cos((float)SDL_GetTicks() / 600.0f) * (float)nPolyVertices[i*2] * fScale) 
                      + (-sin((float)SDL_GetTicks() / 600.0f) * (float)nPolyVertices[i*2+1] * fScale) 
                      + SCREEN_WIDTH / 2;
      nScreenV[i*2+1] = (sin((float)SDL_GetTicks() / 600.0f) * (float)nPolyVertices[i*2] * fScale) 
                        + (cos((float)SDL_GetTicks() / 600.0f) * (float)nPolyVertices[i*2+1] * fScale)  
                        + SCREEN_HEIGHT / 2;
    }        
    Renderer.render(nScreenV,nPolyTextureVertices,4,&TestTexture);
            
    SDL_UnlockSurface(pSDLScreen);
    
    SDL_Flip(pSDLScreen); 
    nNumFrames++;
  }  
  int nEnd = SDL_GetTicks();
  
  SDL_Quit();
  
  printf("%d frames rendered in %.2f seconds: %.2f fps\n",
         nNumFrames,(float)(nEnd-nStart)/1000.0f, ((float)nNumFrames) / ((float)(nEnd-nStart)/1000.0f)); 

  return 0;
}