Difference between revisions of "TriForce"
DavidFerri (talk | contribs) (→Assignment 1: Sudoku Solver) |
(→Assignment 1: EasyBMP) |
||
| Line 435: | Line 435: | ||
Attempted to run the program with a number of files (8K resolution): | Attempted to run the program with a number of files (8K resolution): | ||
| + | |||
| + | |||
| + | [[File:Cabin2 small.jpg]] | ||
{| class="wikitable mw-collapsible mw-collapsed" | {| class="wikitable mw-collapsible mw-collapsed" | ||
Revision as of 09:47, 8 March 2019
GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary
Contents
TriForce
Team Members
- David Ferri, Sudoku Solver
- Vincent Terpstra, Julia Sets
- Raymond Kiguru, EasyBMP
Progress
Assignment 1: Sudoku Solver
Sudoku Solver Profiling
Source code from: https://www.geeksforgeeks.org/sudoku-backtracking-7/
Original Code:
// A Backtracking program in C++ to solve Sudoku problem
#include <stdio.h>
// UNASSIGNED is used for empty cells in sudoku grid
#define UNASSIGNED 0
// N is used for the size of Sudoku grid. Size will be NxN
#define N 9
// This function finds an entry in grid that is still unassigned
bool FindUnassignedLocation(int grid[N][N], int &row, int &col);
// Checks whether it will be legal to assign num to the given row, col
bool isSafe(int grid[N][N], int row, int col, int num);
/* Takes a partially filled-in grid and attempts to assign values to
all unassigned locations in such a way to meet the requirements
for Sudoku solution (non-duplication across rows, columns, and boxes) */
bool SolveSudoku(int grid[N][N])
{
int row, col;
// If there is no unassigned location, we are done
if (!FindUnassignedLocation(grid, row, col))
return true; // success!
// consider digits 1 to 9
for (int num = 1; num <= 9; num++)
{
// if looks promising
if (isSafe(grid, row, col, num))
{
// make tentative assignment
grid[row][col] = num;
// return, if success, yay!
if (SolveSudoku(grid))
return true;
// failure, unmake & try again
grid[row][col] = UNASSIGNED;
}
}
return false; // this triggers backtracking
}
/* Searches the grid to find an entry that is still unassigned. If
found, the reference parameters row, col will be set the location
that is unassigned, and true is returned. If no unassigned entries
remain, false is returned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNASSIGNED)
return true;
return false;
}
/* Returns a boolean which indicates whether an assigned entry
in the specified row matches the given number. */
bool UsedInRow(int grid[N][N], int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns a boolean which indicates whether an assigned entry
in the specified column matches the given number. */
bool UsedInCol(int grid[N][N], int col, int num)
{
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns a boolean which indicates whether an assigned entry
within the specified 3x3 box matches the given number. */
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
/* Returns a boolean which indicates whether it will be legal to assign
num to the given row,col location. */
bool isSafe(int grid[N][N], int row, int col, int num)
{
/* Check if 'num' is not already placed in current row,
current column and current 3x3 box */
return !UsedInRow(grid, row, num) &&
!UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row%3 , col - col%3, num)&&
grid[row][col]==UNASSIGNED;
}
/* A utility function to print grid */
void printGrid(int grid[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
printf("%2d", grid[row][col]);
printf("\n");
}
}
/* Driver Program to test above functions */
int main()
{
// 0 means unassigned cells
int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}};
if (SolveSudoku(grid) == true)
printGrid(grid);
else
printf("No solution exists");
return 0;
}
$ g++ sudokuC.cpp -std=c++0x -o Sudoku $ ./Sudoku 3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9 $ gprof -p -b ./Sudoku gmon.out > 9x9.flt
// A Backtracking program in C++ to solve Sudoku problem
#include <stdio.h>
// UNASSIGNED is used for empty cells in sudoku grid
#define UNASSIGNED 0
// N is used for the size of Sudoku grid. Size will be NxN
#define N 16
// This function finds an entry in grid that is still unassigned
bool FindUnassignedLocation(int grid[N][N], int &row, int &col);
// Checks whether it will be legal to assign num to the given row, col
bool isSafe(int grid[N][N], int row, int col, int num);
/* Takes a partially filled-in grid and attempts to assign values to
all unassigned locations in such a way to meet the requirements
for Sudoku solution (non-duplication across rows, columns, and boxes) */
bool SolveSudoku(int grid[N][N])
{
int row, col;
// If there is no unassigned location, we are done
if (!FindUnassignedLocation(grid, row, col))
return true; // success!
// consider digits 1 to 16
for (int num = 1; num <= 16; num++)
{
// if looks promising
if (isSafe(grid, row, col, num))
{
// make tentative assignment
grid[row][col] = num;
// return, if success, yay!
if (SolveSudoku(grid))
return true;
// failure, unmake & try again
grid[row][col] = UNASSIGNED;
}
}
return false; // this triggers backtracking
}
/* Searches the grid to find an entry that is still unassigned. If
found, the reference parameters row, col will be set the location
that is unassigned, and true is returned. If no unassigned entries
remain, false is returned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNASSIGNED)
return true;
return false;
}
/* Returns a boolean which indicates whether an assigned entry
in the specified row matches the given number. */
bool UsedInRow(int grid[N][N], int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns a boolean which indicates whether an assigned entry
in the specified column matches the given number. */
bool UsedInCol(int grid[N][N], int col, int num)
{
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns a boolean which indicates whether an assigned entry
within the specified 4x4 box matches the given number. */
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < 4; row++)
for (int col = 0; col < 4; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
/* Returns a boolean which indicates whether it will be legal to assign
num to the given row,col location. */
bool isSafe(int grid[N][N], int row, int col, int num)
{
/* Check if 'num' is not already placed in current row,
current column and current 4x4 box */
return !UsedInRow(grid, row, num) &&
!UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row%4 , col - col%4, num)&&
grid[row][col]==UNASSIGNED;
}
/* A utility function to print grid */
void printGrid(int grid[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
printf("%2d", grid[row][col]);
printf("\n");
}
}
/* Driver Program to test above functions */
int main()
{
//https://puzzlemadness.co.uk/16by16giantsudoku/
// 0 means unassigned cells
int grid[N][N] = {{0, 8, 0, 0, 0, 0, 0, 3, 0, 0, 0, 10, 9, 7, 11, 0},
{0, 9, 15, 13, 0, 10, 0, 0, 2, 6, 8, 16, 0, 0, 0, 0},
{0, 0, 16, 0, 15, 0, 8, 0, 9, 0, 0, 0, 6, 0, 2, 0},
{1, 0, 2, 0, 9, 11, 4, 6, 15, 3, 5, 7, 0, 0, 12, 0},
{16, 6, 4, 0, 5, 2, 0, 0, 1, 0, 0, 0, 11, 0, 0, 12},
{5, 11, 0, 0, 0, 3, 0, 15, 0, 16, 0, 13, 0, 1, 0, 8},
{0, 0, 3, 0, 0, 6, 11, 14, 0, 5, 7, 0, 0, 9, 0, 0},
{0, 0, 0, 14, 8, 0, 10, 0, 0, 11, 12, 0, 0, 0, 0, 0},
{0, 7, 13, 0, 0, 0, 0, 12, 0, 8, 9, 0, 0, 0, 3, 0},
{0, 0, 11, 9, 0, 7, 0, 0, 0, 0, 0, 12, 0, 8, 16, 5},
{0, 0, 10, 0, 11, 13, 0, 0, 0, 0, 0, 3, 12, 0, 6, 0},
{0, 5, 0, 0, 10, 15, 0, 1, 7, 2, 0, 0, 14, 11, 0, 0},
{0, 0, 5, 0, 0, 12, 14, 0, 0, 10, 0, 0, 15, 0, 0, 4},
{9, 0, 14, 6, 0, 0, 1, 0, 16, 0, 2, 0, 3, 0, 13, 0},
{8, 13, 0, 4, 0, 0, 0, 0, 12, 7, 3, 0, 0, 6, 0, 0},
{0, 16, 12, 0, 0, 5, 0, 9, 0, 13, 14, 4, 1, 0, 0, 0}};
if (SolveSudoku(grid) == true)
printGrid(grid);
else
printf("No solution exists");
return 0;
}
25x25 Puzzle:
int grid[N][N] = {{1, 0, 4, 0, 25, 0, 19, 0, 0, 10, 21, 8, 0, 14, 0, 6, 12, 9, 0, 0, 0, 0, 0, 0, 5},
{5, 0, 19, 23, 24, 0, 22, 12, 0, 0, 16, 6, 0, 20, 0, 18, 0, 25, 14, 13, 10, 11, 0, 1, 15},
{0, 0, 0, 0, 0, 0, 21, 5, 0, 20, 11, 10, 0, 1, 0, 4, 8, 24, 23, 15, 18, 0, 16, 22, 19},
{0, 7, 21, 8, 18, 0, 0, 0, 11, 0, 5, 0, 0, 24, 0, 0, 0, 17, 22, 1, 9, 6, 25, 0, 0},
{0, 13, 15, 0, 22, 14, 0, 18, 0, 16, 0, 0, 0, 4, 0, 0, 0, 19, 0, 0, 0, 24, 20, 21, 17},
{12, 0, 11, 0, 6, 0, 0, 0, 0, 15, 0, 0, 0, 0, 21, 25, 19, 0, 4, 0, 22, 14, 0, 20, 0},
{8, 0, 0, 21, 0, 16, 0, 0, 0, 2, 0, 3, 0, 0, 0, 0, 17, 23, 18, 22, 0, 0, 0, 24, 6},
{4, 0, 14, 18, 7, 9, 0, 22, 21, 19, 0, 0, 0, 2, 0, 5, 0, 0, 0, 6, 16, 15, 0, 11, 12},
{22, 0, 24, 0, 23, 0, 0, 11, 0, 7, 0, 0, 4, 0, 14, 0, 2, 12, 0, 8, 5, 19, 0, 25, 9},
{20, 0, 0, 0, 5, 0, 0, 0, 0, 17, 9, 0, 12, 18, 0, 1, 0, 0, 7, 24, 0, 0, 0, 13, 4},
{13, 0, 0, 5, 0, 2, 23, 14, 4, 18, 22, 0, 17, 0, 0, 20, 0, 1, 9, 21, 12, 0, 0, 8, 11},
{14, 23, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 20, 25, 0, 3, 4, 13, 0, 11, 21, 9, 5, 18, 22},
{7, 0, 0, 11, 17, 20, 24, 0, 0, 0, 3, 4, 1, 12, 0, 0, 6, 14, 0, 5, 25, 13, 0, 0, 0},
{0, 0, 16, 9, 0, 17, 11, 7, 10, 25, 0, 0, 0, 13, 6, 0, 0, 18, 0, 0, 19, 4, 0, 0, 20},
{6, 15, 0, 19, 4, 13, 0, 0, 5, 0, 18, 11, 0, 0, 9, 8, 22, 16, 25, 10, 7, 0, 0, 0, 0},
{0, 0, 0, 2, 0, 0, 10, 19, 3, 0, 1, 0, 22, 9, 4, 11, 15, 0, 20, 0, 0, 8, 23, 0, 25},
{0, 24, 8, 13, 1, 0, 0, 4, 20, 0, 17, 14, 0, 0, 18, 0, 16, 22, 5, 0, 11, 0, 10, 0, 0},
{23, 10, 0, 0, 0, 0, 0, 0, 18, 0, 6, 0, 16, 0, 0, 17, 1, 0, 13, 0, 0, 3, 19, 12, 0},
{25, 5, 0, 14, 11, 0, 17, 0, 8, 24, 13, 0, 19, 23, 15, 9, 0, 0, 12, 0, 20, 0, 22, 0, 7},
{0, 0, 17, 4, 0, 22, 15, 0, 23, 11, 12, 25, 0, 0, 0, 0, 18, 8, 0, 7, 0, 0, 14, 0, 13},
{19, 6, 23, 22, 8, 0, 0, 1, 25, 4, 14, 2, 0, 3, 7, 13, 10, 11, 16, 0, 0, 0, 0, 0, 0},
{0, 4, 0, 17, 0, 3, 0, 24, 0, 8, 20, 23, 11, 10, 25, 22, 0, 0, 0, 12, 13, 2, 18, 6, 0},
{0, 0, 7, 16, 0, 0, 6, 17, 2, 21, 0, 18, 0, 0, 0, 19, 0, 0, 8, 0, 0, 0, 0, 4, 0},
{18, 9, 25, 1, 2, 11, 0, 0, 13, 22, 4, 0, 21, 0, 5, 0, 23, 7, 0, 0, 15, 0, 3, 0, 8},
{0, 21, 10, 0, 0, 12, 0, 20, 16, 0, 19, 0, 0, 0, 0, 15, 14, 4, 2, 18, 23, 25, 11, 7, 0}};
For 9x9 Sudoku Puzzle (3x3 squares)
Flat profile: Each sample counts as 0.01 seconds. no time accumulated % cumulative self self total time seconds seconds calls Ts/call Ts/call name 0.00 0.00 0.00 6732 0.00 0.00 isSafe(int (*) [9], int, int, int) 0.00 0.00 0.00 6732 0.00 0.00 UsedInRow(int (*) [9], int, int) 0.00 0.00 0.00 2185 0.00 0.00 UsedInCol(int (*) [9], int, int) 0.00 0.00 0.00 1078 0.00 0.00 UsedInBox(int (*) [9], int, int, int) 0.00 0.00 0.00 770 0.00 0.00 FindUnassignedLocation(int (*) [9], int&, int&) 0.00 0.00 0.00 1 0.00 0.00 SolveSudoku(int (*) [9]) 0.00 0.00 0.00 1 0.00 0.00 printGrid(int (*) [9])
For 16x16 Sudoku Puzzle (4x4 squares) Puzzle from: [1]
Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 39.04 15.00 15.00 28071636 0.00 0.00 FindUnassignedLocation(int (*) [16], int&, int&) 36.19 28.90 13.90 449145092 0.00 0.00 UsedInRow(int (*) [16], int, int) 10.60 32.97 4.07 120354547 0.00 0.00 UsedInCol(int (*) [16], int, int) 4.97 34.88 1.91 41212484 0.00 0.00 UsedInBox(int (*) [16], int, int, int) 4.59 36.65 1.76 1 1.76 38.39 SolveSudoku(int (*) [16]) 4.55 38.39 1.75 449145092 0.00 0.00 isSafe(int (*) [16], int, int, int) 0.01 38.40 0.01 frame_dummy 0.00 38.40 0.00 1 0.00 0.00 printGrid(int (*) [16])
For 25x25 Sudoku Puzzle (5x5 squares) Puzzle from: http://www.sudoku-download.net/sudoku_25x25.php
Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls Ks/call Ks/call name 48.76 1052.18 1052.18 425478951 0.00 0.00 UsedInRow(int (*) [25], int, int) 25.24 1596.81 544.63 876012758 0.00 0.00 FindUnassignedLocation(int (*) [25], int&, int&) 12.48 1866.03 269.21 590817023 0.00 0.00 UsedInCol(int (*) [25], int, int) 4.83 1970.24 104.21 425478951 0.00 0.00 isSafe(int (*) [25], int, int, int) 4.79 2073.51 103.27 1 0.10 2.17 SolveSudoku(int (*) [25]) 4.35 2167.39 93.89 1355081265 0.00 0.00 UsedInBox(int (*) [25], int, int, int) 0.01 2167.56 0.17 frame_dummy 0.00 2167.56 0.00 1 0.00 0.00 printGrid(int (*) [25])
Assignment 1: EasyBMP
EasyBMP Bitmap image library (Sample Program: Image to black and white renderer)
Library: http://easybmp.sourceforge.net/
| Sample code: |
|---|
/**/
#include "EasyBMP.h"
using namespace std;
int main(int argc, char* argv[]) {
// Create a new Bitmap image with EasyBMP
BMP Background;
Background.ReadFromFile(argv[1]);
BMP Output;
int picWidth = Background.TellWidth();
int picHeight = Background.TellHeight();
Output.SetSize(Background.TellWidth(), Background.TellHeight());
Output.SetBitDepth(1);
for (int i = 1; i < picWidth - 1; ++i) {
for (int j = 1; j < picHeight - 1; ++j) {
int col = (Background(i, j)->Blue + Background(i, j)->Green + 10 * Background(i, j)->Red) / 12;
if (col > 127) {
Output(i, j)->Red = 255;
Output(i, j)->Blue = 255;
Output(i, j)->Green = 255;
}
else {
Output(i, j)->Red = 0;
Output(i, j)->Blue = 0;
Output(i, j)->Green = 0;
}
}
}
Output.WriteToFile(argv[2]);
return 0;
}
/**/
|
The program was compiled using the following commands:
g++ -c -pg -g BW.cpp EasyBMP.cpp g++ -pg BW.o EasyBMP.o -o BW rm *.o
Attempted to run the program with a number of files (8K resolution):
| Flat profile (Cabin): |
|---|
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 31.38 1.74 1.74 33177600 0.00 0.00 BMP::FindClosestColor(RGBApixel&) 23.52 3.04 1.30 198921624 0.00 0.00 BMP::operator()(int, int) 9.95 3.59 0.55 2 0.28 0.28 BMP::SetSize(int, int) 7.60 4.01 0.42 41663472 0.00 0.00 BMP::GetColor(int) 6.87 4.39 0.38 main 5.43 4.69 0.30 74841076 0.00 0.00 IntPow(int, int) 3.62 4.89 0.20 74841072 0.00 0.00 BMP::TellNumberOfColors() 3.35 5.07 0.19 4320 0.00 0.00 BMP::Write1bitRow(unsigned char*, int, int) 2.53 5.21 0.14 124990416 0.00 0.00 IntSquare(int) 2.17 5.33 0.12 4320 0.00 0.00 BMP::Read24bitRow(unsigned char*, int, int) 1.63 5.42 0.09 2 0.05 0.05 BMP::~BMP() 0.90 5.47 0.05 GetEasyBMPwarningState() 0.72 5.51 0.04 1 0.04 0.04 _GLOBAL__sub_I_EasyBMPwarnings 0.18 5.52 0.01 2 0.01 0.01 BMP::TellWidth() 0.18 5.53 0.01 1 0.01 2.99 BMP::WriteToFile(char const*) 0.00 5.53 0.00 16 0.00 0.00 SafeFread(char*, int, int, _IO_FILE*) 0.00 5.53 0.00 6 0.00 0.00 IsBigEndian() 0.00 5.53 0.00 2 0.00 0.00 EasyBMPcheckDataSize() 0.00 5.53 0.00 2 0.00 0.00 BMP::TellHeight() 0.00 5.53 0.00 2 0.00 0.00 BMP::SetBitDepth(int) 0.00 5.53 0.00 2 0.00 0.00 BMP::BMP() 0.00 5.53 0.00 2 0.00 0.00 BMFH::BMFH() 0.00 5.53 0.00 2 0.00 0.00 BMIH::BMIH() 0.00 5.53 0.00 1 0.00 0.00 _GLOBAL__sub_I_main 0.00 5.53 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 5.53 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 5.53 0.00 1 0.00 0.40 BMP::ReadFromFile(char const*) 0.00 5.53 0.00 1 0.00 0.00 BMP::CreateStandardColorTable() |
| Flat profile (Lake): |
|---|
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 30.60 1.71 1.71 33177600 0.00 0.00 BMP::FindClosestColor(RGBApixel&) 21.12 2.89 1.18 198921624 0.00 0.00 BMP::operator()(int, int) 10.20 3.46 0.57 2 0.29 0.29 BMP::SetSize(int, int) 8.59 3.94 0.48 main 6.26 4.29 0.35 76982189 0.00 0.00 IntPow(int, int) 6.08 4.63 0.34 43804585 0.00 0.00 BMP::GetColor(int) 5.55 4.94 0.31 76982185 0.00 0.00 BMP::TellNumberOfColors() 3.76 5.15 0.21 4320 0.00 0.00 BMP::Write1bitRow(unsigned char*, int, int) 3.76 5.36 0.21 131413755 0.00 0.00 IntSquare(int) 2.15 5.48 0.12 4320 0.00 0.00 BMP::Read24bitRow(unsigned char*, int, int) 1.07 5.54 0.06 2 0.03 0.03 BMP::~BMP() 0.54 5.57 0.03 GetEasyBMPwarningState() 0.36 5.59 0.02 1 0.02 0.02 _GLOBAL__sub_I_EasyBMPwarnings 0.00 5.59 0.00 16 0.00 0.00 SafeFread(char*, int, int, _IO_FILE*) 0.00 5.59 0.00 6 0.00 0.00 IsBigEndian() 0.00 5.59 0.00 2 0.00 0.00 EasyBMPcheckDataSize() 0.00 5.59 0.00 2 0.00 0.00 BMP::TellHeight() 0.00 5.59 0.00 2 0.00 0.00 BMP::SetBitDepth(int) 0.00 5.59 0.00 2 0.00 0.00 BMP::TellWidth() 0.00 5.59 0.00 2 0.00 0.00 BMP::BMP() 0.00 5.59 0.00 2 0.00 0.00 BMFH::BMFH() 0.00 5.59 0.00 2 0.00 0.00 BMIH::BMIH() 0.00 5.59 0.00 1 0.00 0.00 _GLOBAL__sub_I_main 0.00 5.59 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 5.59 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 5.59 0.00 1 0.00 3.13 BMP::WriteToFile(char const*) 0.00 5.59 0.00 1 0.00 0.41 BMP::ReadFromFile(char const*) 0.00 5.59 0.00 1 0.00 0.00 BMP::CreateStandardColorTable() |
Assignment 1: Julia Set
This portion of the assignment focuses on Julia sets with the quadratic formula:
fc(z) = z^2 + c; Where c and z are complex numbers
Psuedo code
for(Pixel pix in image){
pix.color = colorFunction(escapeValue(pix.loc, julia));
}
escapeValue(Complex loc, Complex julia){
int cycles = 0;
while(|loc| <=2 && ++cycles < MAXCYCLES){
loc = loc * loc + julia;
}
return cycles;
}
| Julia.cpp |
|---|
/** * Julia.cpp * Vincent Terpstra * Feb 18 / 2019 * Functions to display a Mandlebrot set */ #include <iostream> #include <math.h> #include "Bitmap.h" #define MAXCYCLES 1000 #define ITER 1 #define PI 3.14159 void calcJulia(int* array, int width, int height, float jR, float jI); void createBMP(int* array, int width, int height); int main(int size, const char ** args) {
int height = (size > 1) ? atoi(args[1]) : 1000;
int width = height / 2 * 3;
int * array = new int[height * width];
float jI = -0.4f;
float jR = 0.6f;
float angle = 2.0f / ITER * PI;
float cosA = cos(angle);
float sinA = sin(angle);
for(int i = 0; i < ITER; i++){
calcJulia(array, width, height, jI, jR);
createBMP(array, width, height);
//rotate the Julia point
float tmp = jI;
jI = cosA * jI - sinA * jR;
jR = cosA * jR + sinA * tmp;
}
delete[] array;
return 0;
}
/**
* calcDepth
* finds the escape value of the Julia set
* inputs sR, sI: starting position on the map
* jR, jI: values of the julia set
* exits when |s| > 2 or reached MAXCYCLES
* return the
*/
int calcDepth(float sR, float sI, const float jR, const float jI){
int cycle = 0;
while(sR * sR + sI * sI <= 4 && ++cycle < MAXCYCLES){
// s(next) = s * s + j
float tmp = sR;
sR = sR * sR - sI * sI + jR;
sI = 2 * tmp * sI + jI;
}
return cycle;
}
/**
* calcJulia
* Function to calculate the values from (-1.5, 1.5),(-1, 1) in the Julia set
* saves the values onto the array
*/
void calcJulia(int * array, int width, int height, const float jR, const float jI){
float delta = 2 / (float)height;
float x, y = -1;
for(int i = 0; i < height; i++){
x = -1.5f;
for(int j = 0; j < width; j++){
*array++ = calcDepth(x, y, jR, jI);
x+=delta;
}
y += delta;
}
}
struct Pix {
float val;
int r, g, b;
Pix(float val, int r, int g, int b) :
val(val), r(r), g(g), b(b) {}
};
bool lerp(float clr, Pix& first, Pix& second, Bitmap & map); /**
* createBMP
* maps the values in the array to a .bmp file
* linear interpolates between color values
*/
void createBMP(int * array, int width, int height){
static int idx = 0;
char name[] = "julia000.bmp";
name[5] = (idx / 100) + '0';
name[6] = ((idx / 10) % 10) + '0';
name[7] = (idx % 10) + '0';
Bitmap map (name, width, height);
//idx++;
const int pix = width * height;
struct Pix
clr0(0, 20, 20, 30),
clr1(10, 20, 10, 100),
clr2(180, 20, 170, 205),
clr3(MAXCYCLES, 0, 0, 0);
const int * pMax = array + width * height;
while(array < pMax){
float clr = *array++;
bool draw =
lerp(clr, clr0, clr1, map) ||
lerp(clr, clr1, clr2, map) ||
lerp(clr, clr2, clr3, map);
}
}
/**
* Function to linearly interpolate color values and draw to the Bitmap
*/
bool lerp(float clr, Pix& first, Pix& second, Bitmap & map){
if(clr <= second.val){
float diff = (clr - first.val) / (second.val - first.val);
map << first.b + diff * (second.b - first.b);
map << first.g + diff * (second.g - first.g);
map << first.r + diff * (second.r - first.r);
return true;
}
return false;
}
|
To view the full c++ code github link
This code is tested using the parameters
Range R(-1.5, 1.5) I(-1, 1) Image height(1000) width(1500) MAXCYCLES 1000 Julia values = .72 * e(i θ): θ[0, 2π] : 100 intervals
Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ms/call ms/call name 91.82 80.04 80.04 calcJulia(int*, int, int, float, float) 2.28 82.03 1.99 450000000 0.00 0.00 Bitmap::operator<<(float) 2.12 83.87 1.85 197791886 0.00 0.00 lerp(float, Pix&, Pix&, Bitmap&) 0.29 84.12 0.25 createBMP(int*, int, int) 0.13 84.23 0.11 100 1.10 1.10 Bitmap::Bitmap(char const*, int, int) 0.00 84.23 0.00 100 0.00 0.00 generateBitmapImage(unsigned char*, int, int, char const*) 0.00 84.23 0.00 100 0.00 0.00 createBitmapFileHeader(int, int, int) 0.00 84.23 0.00 100 0.00 0.00 createBitmapInfoHeader(int, int) 0.00 84.23 0.00 100 0.00 0.00 Bitmap::~Bitmap() 0.00 84.23 0.00 1 0.00 0.00 _GLOBAL__sub_I_main
| Generated Image of Julia set at (-0.4, 0.6) |
|---|
|
|
