Fundamentals of Fractals 4: The Sierpinski carpet

image

In the last tutorial, we plotted a Sierpinski gasket using dots. I figured that I wanted to introduce the Sierpinski Carpet as well, before moving into more heavy fractals.

The Sierpinski Carpet is very simple as well, but we are approaching this problem from another perspective. In this example, we are going to draw a grid of white quads, where each quad is evaluated towards a function that decides if a given quad is in the Sierpinski carpet or not. If yes, we draw the quad, if not, we don,t.

First of all, we need to set up our grid. We are doing this by rendering 200×200 squares, each square representing a “pixel” in our image. If we render the whole thing, we will get a big white square:
image

Now, this white square is made up of 200×200 small squares. Removing a square will make a green spot where the square was located, making this a drawing area with two colors, white and green.

To render our white square, we iterate through all the quads and render them one by one. Each quad is also scaled by 0,5 to make them fit with no space between each quad, or any overlap with neighboring quads.

for(int x = 0; x < 200; x++)
    {
        for(int y = 0; y < 200; y++)
        {
            g_World1 =  XMMatrixScaling( 0.5f, 0.5f, 1.0f ) * XMMatrixTranslation( -100+x, -100+y, 1.0f );

            CBShaderParameters cb1;
            cb1.mWorld = XMMatrixTranspose( g_World1 );
            cb1.mView = XMMatrixTranspose( g_View );
            cb1.mProjection = XMMatrixTranspose( g_Projection );
            g_pImmediateContext->UpdateSubresource( g_pCBShaderParameters, 0, NULL, &cb1, 0, 0 );

            // Render a triangle
            g_pImmediateContext->VSSetShader( g_pVertexShader, NULL, 0 );
            g_pImmediateContext->VSSetConstantBuffers( 0, 1, &g_pCBShaderParameters );
            g_pImmediateContext->PSSetShader( g_pPixelShader, NULL, 0 );
            g_pImmediateContext->PSSetConstantBuffers( 0, 1, &g_pCBShaderParameters );
            g_pImmediateContext->UpdateSubresource( g_pCBShaderParameters, 0, NULL, &cb1, 0, 0 );
            bool isInside = isSierpinskiCarpetPixelFilled(x,y,200,200);
            g_pImmediateContext->Draw( 6, 0 );
        }
    }

Now, we will work on the function that will decide if we want to draw a quad or not. If we don’t want to draw a given quad, we must skip the code (marked in red above) that renders the quad.

This is where our evaluation function comes into play. This function will return true or false if a given quad is inside or outside the Sierpinski carpet.

To generate a Sierpinski Carpet, we must start with a quad (1). This quad is cut into 9 similar quads in a 3×3 grid, where the interior of the center quad is removed(2).

image

Next, we do the same for each of the solid quads in 2, remove the middle quad from each.(3). Then we repeat the same step to get to 4 and forward.

Let’s take a look at the code:

bool isInsideSierpinskiCarpet(int x, int y, int w, int h)
{
    if (x <= 1)
    {
        return true;
    }

    // This is where we split the quad into 9 parts
    // Now, the pixel/quad we are processing, what
    // part of the 9 quads does this belong?
    int x2 = x * 3 / w;
    int y2 = y * 3 / h;

    // Is the quad we are inside of the center?
    // if yes, this quad must not be rendered
    if (x2 == 1 && y2 == 1)
        return false;

    // Not center? prepare us for a recursice call in
    // order to split the current cube into even
    // smaller cubes
    x -= x2 * w / 3;
    y -= y2 * h / 3;

    // ..and go!
    return isInsideSierpinskiCarpet(x, y, (w / 3) + 1, (h / 3) + 1);
}
This code is based on the code found on this subject at Wikipedia

In here, we see that we are splitting the quad being processed into 9 smaller quads, and find out what quad the point x,y is inside:

    int x2 = x * 3 / w;
    int y2 = y * 3 / h;

 

Then we check if the the new x is in the middle-quad, and if so, return from the function and indicate that this quad should not be rendered.

if (x2 == 1 && y2 == 1)
    return false;

If not, we move forward and prepare to split the smaller quad into an additional 9 quads and use the same function again on the subset. The resolution is divided by 3, so the next function is only working on that subset of the Sierpinski carpet.

x -= x2 * w / 3;
y -= y2 * h / 3;

return isInsideSierpinskiCarpet(x, y, (w / 3) + 1, (h / 3) + 1);

Now that we got out function to evaluate if a quad should be drawn or not, we can use this to finish our fractal. In the render code, use this function to evaluate if quad x,y should be drawn:

for(int x = 0; x < 200; x++)
{
    for(int y = 0; y < 200; y++)
    {
        if(isInsideSierpinskiCarpet(x,y,200,200))
        {
            g_World1 =  XMMatrixScaling( 0.5f, 0.5f, 1.0f ) * XMMatrixTranslation( -100+x, -100+y, 1.0f );

            CBShaderParameters cb1;
            cb1.mWorld = XMMatrixTranspose( g_World1 );
            cb1.mView = XMMatrixTranspose( g_View );
            cb1.mProjection = XMMatrixTranspose( g_Projection );
            g_pImmediateContext->UpdateSubresource( g_pCBShaderParameters, 0, NULL, &cb1, 0, 0 );

            // Render a triangle
            g_pImmediateContext->VSSetShader( g_pVertexShader, NULL, 0 );
            g_pImmediateContext->VSSetConstantBuffers( 0, 1, &g_pCBShaderParameters );
            g_pImmediateContext->PSSetShader( g_pPixelShader, NULL, 0 );
            g_pImmediateContext->PSSetConstantBuffers( 0, 1, &g_pCBShaderParameters );
            g_pImmediateContext->UpdateSubresource( g_pCBShaderParameters, 0, NULL, &cb1, 0, 0 );

            g_pImmediateContext->Draw( 6, 0 );
        }
    }
}

This is done by using the return value from our function on a given quad, and render it based on the result.

The result should be something like this:
image

Download: Source and Executable (DirectX11, Visual Studio 2010)

Advertisements
This entry was posted in DirectX11, Fractal, Math, Tutorial. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s