Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 03 Dec 2010
Offline Last Active Jul 13 2013 11:40 PM

Topics I've Started

bi-quadratic interpolation?

06 April 2013 - 07:39 PM

Recently i've been messing around with interpolation methods on scalar fields because im trying to make the scalar field of discrete points, continuous.

I think I understand how bi-linear interpolation works. To my knowledge,In order to interpolate a value(using bilinear interpolation) you have to do three "lerps" using four discrete neighbor points on the field. But when it comes to higher order interpolation methods, I'm lost. I know how to use quadratic interpolation  to interpolate a value using 3 discrete points on a function. How would I use quadratic interpolation on a scalar field?


Ramer–Douglas–Peucker algorithm help

20 January 2013 - 06:10 PM

I recently implemented a marching squares algorithm to generate a polygon for an arbitrary image.


Here is an example of my marching squares implementation:  


As you can see it works,however, the marching squares algorithm gives me more data than I really need for a polygon. So a polygon simplification algorithm would be needed.


I'm currently trying to implement the Ramer–Douglas–Peucker algorithm. The problem is that I don't know what condition's to set to end the recursion. Currently, the either the algorithm runs in an infinite loop or terminates without correctly simplifying the line/polygon.


My interpretation of the algorithm is as followed:

-for the current line segment compute the vertex with the farthest perpendicular distance.

-if the farthest perpendicular distance is greater than the user defined "tolerance" do recursion, otherwise terminate recursion.


Can someone point out what i'm doing wrong here?


Here's my flawed code:

void smoothCurve(Particle* p0, Particle* p1,float tolerance,std::vector<Particle*>& vertexList,std::vector<Particle*>& outPut , std::vector<bool>& isRejected){
    Vector2 displacement;
    Vector2 projectionArm;
    Vector2 projectedPoint;
    Vector2 pointToLineDisp;
    Vector2& x0 = p0->curPos;
    Vector2& x1 = p1->curPos;
    float dot;
    float currentDist = 0;
    float maxDist = 0;
    unsigned int maxIndex = 0;

    displacement = x1- x0;
    //calculates maximum distance from the line segment
    for(unsigned int I = 1; I < vertexList.size()-1;I++){
        Particle*& currentVertex = vertexList[I];
        Vector2& curVertexPos= currentVertex->curPos;
        projectionArm = curVertexPos - x0;
        dot = (projectionArm*displacement)/(displacement*displacement);
        projectedPoint = x0 + (displacement * dot);
        pointToLineDisp = projectedPoint - curVertexPos;
        currentDist = pointToLineDisp.getMagnitude();

        if(currentDist > maxDist){
            maxDist = currentDist;
            maxIndex = I;

    if(maxDist >= tolerance && outPut[maxIndex] == NULL ){
        Particle* criticalParticle = vertexList[maxIndex];
        outPut[maxIndex] = criticalParticle;

void simplifyPolygon(float tolerance,std::vector<Particle*>& vertexList){
    std::vector<Particle*> outPut;
    std::vector<bool> isRejected;


    for(unsigned int I = 0; I < vertexList.size();I++){
        outPut[I] = NULL;
        isRejected[I] = false;

    Particle* x0 = vertexList[0];
    Particle* x1 = vertexList[vertexList.size()-1];
    outPut[0] = x0;
    outPut[vertexList.size()-1] = x1;

    for(unsigned int I = 0; I < outPut.size();I++){
        Particle * cp = outPut[I];
        if(cp == NULL){
            delete vertexList[I];
    for(unsigned int I = 0; I < outPut.size();I++){
        Particle * cp = outPut[I];
        if(cp != NULL){

reading 24 bit per pixel bitmaps issue

05 January 2013 - 09:50 PM

I'm currently trying to read bitmaps without using an image library.

My current implementation can read bitmaps ,however, issues occur when both the width and height are not of base 2. 

To be more specific, when I tired to render a 922x910 bitmap ,the colors didn't come in correctly. Sometimes bitmaps of different resolutions turnout looking "stretched" and without the correct colors.  

To get my bitmaps I let microsoft paint convert png's, jpegs and other formats to .bmp.

The ultimate purpose for all of this is to implement the marching squares method so I can generate polygons from sprites.

How do I deal with this? 


My bitmap code so far:

struct ColorVector{
    unsigned char r;
    unsigned char g;
    unsigned char b;
    unsigned char a;


class uBitmap{
        uBitmap(std::string path,BYTE redColorKey, BYTE greenColorKey,BYTE blueColorKey);
        unsigned int getWidth();
        unsigned int getHeight();
        long int getPixel(int x, int y);
        ColorVector getPixelVector(int x, int y);
        void resizeBuffer(unsigned int size);
        void clearBuffer();
        void putPixel(int x, int y, BYTE r, BYTE g, BYTE b);
        void saveBitmap(std::string filename);
        void renderImage();
        BITMAPFILEHEADER bitmapHeader_;
        BITMAPINFOHEADER bitmapInfoHeader_;
        BYTE* rgbPixelData_;
        BYTE* rgbaPixelData_;
        ColorVector colorKey_;



uBitmap::uBitmap(std::string path,BYTE redColorKey, BYTE greenColorKey,BYTE blueColorKey){
    BITMAPFILEHEADER& fileHeader = bitmapHeader_;
    BITMAPINFOHEADER& infoHeader = bitmapInfoHeader_;
    BYTE*& pixelData = rgbPixelData_;

    bitmapInfoHeader_.biWidth = 0;
    bitmapInfoHeader_.biHeight = 0;
    rgbPixelData_ = NULL;
    rgbaPixelData_ = NULL;

    std::ifstream file(path.data(),std::ios::binary);
        file.read((char*)&bitmapHeader_    ,sizeof(BITMAPFILEHEADER));
        rgbPixelData_ = new BYTE[infoHeader.biSizeImage];

    if(rgbPixelData_ != NULL){
        delete[] rgbPixelData_;

    if(rgbaPixelData_ != NULL){
        delete[] rgbaPixelData_;

unsigned int uBitmap::getWidth(){
    return bitmapInfoHeader_.biWidth;

unsigned int uBitmap::getHeight(){
    return bitmapInfoHeader_.biHeight;

/*long int uBitmap::getPixel(int x, int y){// attempting to pack color components into an integer
    ColorVector pix = getPixelVector(x,y);
    return  (pix.b << 24) | (pix.g << 16)  | (pix.r << 8) ;

ColorVector uBitmap::getPixelVector(int x, int y){
    ColorVector curElement;
    unsigned int firstComponent = (y*getWidth()+x)*3;//which is the blue color vector component
    curElement.b = *(rgbPixelData_+firstComponent);  //reading first component (blue)
    curElement.g = *(rgbPixelData_+firstComponent+1);//reading second component (green)
    curElement.r = *(rgbPixelData_+firstComponent+2);//reading third component (red)
    return curElement;

void uBitmap::renderImage(){
    for(unsigned int y = 0; y < getHeight();y++){
        for(unsigned int x = 0; x < getWidth();x++){
            ColorVector c = getPixelVector(x,getHeight() - y);
            glColor3ub(c.r,c.g ,c.b);

Please note:I realize that using immediate mode to render a bitmap is a horrible idea,however, its more a debugging function than anything else. Just putting that out there. 



I seemed to have fixed the problem. You guys were completely right about the padding. All I did was slightly modify the constructor to fix my problem:

uBitmap::uBitmap(std::string path,BYTE redColorKey, BYTE greenColorKey,BYTE blueColorKey{
    BITMAPFILEHEADER& fileHeader = bitmapHeader_;
    BITMAPINFOHEADER& infoHeader = bitmapInfoHeader_;
    BYTE*& pixelData = rgbPixelData_;
    bitmapInfoHeader_.biWidth = 0;
    bitmapInfoHeader_.biHeight = 0;
    rgbPixelData_ = NULL;
    rgbaPixelData_ = NULL;

    std::ifstream file(path.data(),std::ios::binary);
        file.read((char*)&bitmapHeader_    ,sizeof(BITMAPFILEHEADER));
        int desiredRow = int(ceilf((((float)getWidth())*3.0f) / 4.0f) * 4.0f);
        int rowPadding = desiredRow - (getWidth()*3);
        rgbPixelData_ = new BYTE[ (getWidth()*getHeight()*3) + (rowPadding*getHeight());
        for(unsigned int I = 0; I < getHeight();I++){


MidPoint Method implementation issues

28 December 2012 - 01:36 AM

I'm trying to implement a function that calculates the integral of a function f'(x) using the midpoint method. 

Here's what I came up with:

float CMATH::midPointIntegrate(float steps,float x1, float(*F)(float x)  ){
    float stepSize = x1/steps;
    float integral = 0.0f;
    float xn = 0;
    float y0 = 0.0f;
    float ymid = 0.0f;
    float y1 = 0.0f;

    for(int I = 0; I < steps; I++){
        y0 = F(xn);
        ymid = F(xn+stepSize*0.5f);
        y1 = F(xn+stepSize);
        integral+= y0*stepSize*0.5f + (ymid - y0)*stepSize*0.25f + ymid*stepSize*0.5f + (y1-ymid)*stepSize*0.25f;

    return integral;



It appears to work, however, I was under the impression that the midpoint method requires less steps in order to calculate the integral. 

Can anyone confirm that this is the correct implementation of the midpoint method because ,at the moment, i'm not really sure.

reading binary data using physicsFS[Solved]

13 June 2012 - 04:52 PM

Basically i am trying to read a binary file stored in a zip folder.
The binary file in the zip folder stores information for individual polygons.

This is the class header.
This class is responsible for transferring information from ConvexHull objects that i'd like to store into binary files. Its also responsible for reading information from the binary file. Once that information is read i can create a ConvexHull object and then reinitialize the geometry object. (hope that made sense i dont know a better way to put that)

[source lang="cpp"]class Geometry{ static const unsigned int MAX_VERTEX_ELEMENTS = 50; static const unsigned int MAX_CHAR_ELEMENTS = 10; public: Geometry(); ~Geometry(); ConvexHull * loadGeometryIntoMemory(MultiGrid<ConvexHull> * hullGridPtr); void storeHullData(ConvexHull * ch); void writeHullDataToFile(std::ofstream & file); void readHullDataFromFile(std::ifstream & file); void readHullDataFromBuffer(std::istringstream& file); void initAllFields(); private: unsigned int vrecsFilled_;//V for vertex unsigned int krecsFilled_;//K for keyword char textureKeyword_[MAX_CHAR_ELEMENTS]; float vx_[MAX_VERTEX_ELEMENTS]; float vy_[MAX_VERTEX_ELEMENTS]; bool translate_; float fakeFriction_;};[/source]

This is how i write to my binary file:

[source lang="cpp"]void Geometry::writeHullDataToFile(std::ofstream & file){ file.write((char*)&vrecsFilled_,sizeof(vrecsFilled_)); for(unsigned int K = 0; K < vrecsFilled_;K++){ float & x = vx_[K]; float & y = vy_[K]; file.write((char*)&x,sizeof(x)); file.write((char*)&y,sizeof(y)); } file.write((char*)&krecsFilled_,sizeof(krecsFilled_)); for(unsigned int K = 0; K < krecsFilled_;K++){ char & c = textureKeyword_[K]; file.write((char*)&c,sizeof©); } //write parameters last file.write((char*)&fakeFriction_,sizeof(fakeFriction_)); file.write((char*)&translate_,sizeof(translate_));}[/source]

This is where i load the binary file into a buffer from the zip folder (using PhyicsFS) and attempt to read it.
I try read the binary data by calling the method "readHullDataFromBuffer(file);"

[source lang="cpp"] static void loadGeometryFromArchive(std::vector<std::string>& pathList,HullRegistry* hRegistry,MultiGrid<ConvexHull>* hullGrid){ PHYSFS_sint64 file_size = -1; int length_read = 0; char * bytes = NULL; unsigned int listSize = 0; Geometry primitiveData; ConvexHull * currentHull = NULL; for(unsigned int K = 0; K < pathList.size();K++){ std::string& p = pathList[K]; std::string path ="geometry/"+p; if(PHYSFS_exists(path.data()) == 1){ //create file and stream bytes into a buffer PHYSFS_file* myfile = PHYSFS_openRead(path.data()); file_size = PHYSFS_fileLength(myfile); bytes = new char[file_size]; //writes the bytes from file in archive to bytes array length_read = PHYSFS_read(myfile, bytes,1,PHYSFS_fileLength(myfile)); const char * errList = PHYSFS_getLastError(); _cprintf(errList); //Okay now i've got the binary file loaded in the buffer //i can only read the first number in the file before errors occur std::istringstream file(bytes,std::istringstream::binary | std::istringstream::in); //the first 4 bytes of the geometry file contains a number that represents the amount of polygons written to the file. file.read((char*)&listSize,sizeof(listSize));// i succesfully read the correct number,however,this is where my luck ends for(unsigned int K = 0; K < listSize;K++){ primitiveData.initAllFields(); primitiveData.readHullDataFromBuffer(file);//I then attempt to read each record using the buffer but this fails currentHull = primitiveData.loadGeometryIntoMemory(hullGrid); hRegistry->getStaticHullList().push_back(currentHull); } delete[] bytes; PHYSFS_close(myfile); } } }[/source]

I figured I could use std::istringstream like i would use std::ifsream.
But with this I can only read the first number in the binary file before i get errors.

[source lang="cpp"]void Geometry::readHullDataFromBuffer(std::istringstream& file){ file.read((char*)&vrecsFilled_,sizeof(vrecsFilled_)); for(unsigned int K = 0; K < vrecsFilled_;K++){ float & x = vx_[K]; float & y = vy_[K]; file.read((char*)&x,sizeof(x)); file.read((char*)&y,sizeof(y)); } file.read((char*)&krecsFilled_,sizeof(krecsFilled_)); for(unsigned int K = 0; K < krecsFilled_;K++){ char & c = textureKeyword_[K]; file.read((char*)&c,sizeof©); } file.read((char*)&fakeFriction_,sizeof(fakeFriction_)); file.read((char*)&translate_,sizeof(translate_));}[/source]

Basically, after i read the first number in the array, file.fail() becomes true and, anything after that is 0;
Can someone tell me why the previous method fails at the first character?
Is this an issue with PhysicsFS or is it my own code?

Okay so i solved my own issue. I basically just track the position of the array and then use memcpy to read the values.
Here is what i now use to read the records:

[source lang="cpp"]void Geometry::readHullDataFromBuffer(char * bytes,long & position){ memcpy(&vrecsFilled_,bytes+position,sizeof(vrecsFilled_)); position+=sizeof(vrecsFilled_); for(unsigned int K = 0; K < vrecsFilled_;K++){ float & x = vx_[K]; float & y = vy_[K]; memcpy(&x,bytes+position,sizeof(x)); position+=sizeof(x); memcpy(&y,bytes+position,sizeof(y)); position+=sizeof(y); } memcpy(&krecsFilled_,bytes+position,sizeof(krecsFilled_)); position+=sizeof(krecsFilled_); for(unsigned int K = 0; K < krecsFilled_;K++){ char & c = textureKeyword_[K]; memcpy(&c,bytes+position,sizeof©); position+=sizeof©; } memcpy(&fakeFriction_,bytes+position,sizeof(fakeFriction_)); position+=sizeof(fakeFriction_); memcpy(&translate_,bytes+position,sizeof(translate_)); position+=sizeof(translate_);}[/source]

Thank you all for your help.