Image rotation - doesn't always work

This is a discussion on Image rotation - doesn't always work within the C Programming forums, part of the General Programming Boards category; I spent 2 hours last night trying to figure out why my rotation function isn't behaving properly with zoom values ...

  1. #1
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582

    Image rotation - doesn't always work

    I spent 2 hours last night trying to figure out why my rotation function isn't behaving properly with zoom values a multiple of 8. The generation of the image works properly, even with 64 used, but the rotation isn't. Can you find what's causing this? I've uploaded some screenshots to help explain.

    ZoomFactor is 3, no rotation - displays correctly
    ZoomFactor is 3, rotation used - displays correctly
    ZoomFactor is 8, no rotation - displays correctly
    ZoomFactor is 8, rotation used - very distorted when displayed
    ZoomFactor is 60, no rotation - displays correctly
    ZoomFactor is 60, rotation used - displays correctly
    ZoomFactor is 48, no rotation - displays correctly
    ZoomFactor is 48, rotation used - very distorted when displayed

    This is the code that generates the image. The one with the rotation is the one in focus:

    Code:
    // related globals
    unsigned char TerrainData[144000];
    unsigned char TerrainPreviewData[15360000];
    unsigned char TerrainRotatedImageData[15360000];
    
    FILE *FileHandle;
    
    void RotateTerrainImage(unsigned int Width, unsigned int Height) // width and height are the number of blocks
    {
    	unsigned char ImageRotateBlock[8]; // a block of 8x8 pixels
    	unsigned char ImageRotateBits[64];
    	unsigned int ArrayIndex = 0;
    	unsigned int SourceImageArrayIndex = 0;
    	unsigned int TargetImageArrayIndex = 0;
    	unsigned int Row = 0; // current row for the block
    	unsigned int Column = 0;
    	unsigned int DebugTest[16];
    	unsigned int LoopCount = 0;
    	unsigned int StartLoopCount = 9;
    	unsigned int StartArrayIndex = 0;
    	
    	Width /= 8; // for easier use of blocks - number of blocks wide
    
    	printf("Width %d\nHeight %d\n", Width, Height);
    	
    	while (Row < Height)
    	{
    		ArrayIndex = 0; // reset everything as needed
    		// first, read a block, going up - each row is an 8 wide by 1 high bunch of pixels
    		
    		while (ArrayIndex < 8)
    		{
    			ImageRotateBlock[ArrayIndex] = TerrainPreviewData[(Row+ArrayIndex)*Width+Column];
    			ArrayIndex++;
    		}
    		
    		// next, copy the bits of the block
    		ArrayIndex = 0;
    		
    		while (ArrayIndex < 8)
    		{
    			ImageRotateBits[ArrayIndex*8] = (ImageRotateBlock[ArrayIndex] & 128) / 128; // copies the bits of every block as a 0 or 1
    			ImageRotateBits[ArrayIndex*8+1] = (ImageRotateBlock[ArrayIndex] & 64) / 64;
    			ImageRotateBits[ArrayIndex*8+2] = (ImageRotateBlock[ArrayIndex] & 32) / 32;
    			ImageRotateBits[ArrayIndex*8+3] = (ImageRotateBlock[ArrayIndex] & 16) / 16;
    			ImageRotateBits[ArrayIndex*8+4] = (ImageRotateBlock[ArrayIndex] & 8) / 8;
    			ImageRotateBits[ArrayIndex*8+5] = (ImageRotateBlock[ArrayIndex] & 4) / 4;
    			ImageRotateBits[ArrayIndex*8+6] = (ImageRotateBlock[ArrayIndex] & 2) / 2;
    			ImageRotateBits[ArrayIndex*8+7] = (ImageRotateBlock[ArrayIndex] & 1) / 1;
    			
    			ArrayIndex++;
    		}
    		
    		// after that, write the output as bottom up as left to right
    		ArrayIndex = 0;
    		
    		while (ArrayIndex < 8)
    		{
    			// join the bits, reading what was left to right as bottom to top (which rotates it 90 degrees counterclockwise)
    			TerrainRotatedImageData[(ArrayIndex*(Height/8))+(Column*Height)+Row/8] = ImageRotateBits[0+ArrayIndex]*128 + ImageRotateBits[8+ArrayIndex]*64 + ImageRotateBits[16+ArrayIndex]*32 + ImageRotateBits[24+ArrayIndex]*16 + ImageRotateBits[32+ArrayIndex]*8 + ImageRotateBits[40+ArrayIndex]*4 + ImageRotateBits[48+ArrayIndex]*2 + ImageRotateBits[56+ArrayIndex]*1;
    			
    			ArrayIndex++;
    		}
    		
    		// lastly, the column (and row if at the end) should be incremented
    		Column++; // go to the next block column
    		
    		if (Column >= Width) // if at the end
    		{
    			Column = 0; // return to the far left
    			Row += 8; // but go up a row (8 because a block is 8x8, not 8x1)
    		}
    		
    		LoopCount++; // this is for debugging
    	}
    }
    
    void CheckTerrainHeights()
    {
    	unsigned int ArrayIndex = 0;
    	int CurrentHeight = 52; // you start here
    	int MaxHeightPx = CurrentHeight;
    	double MaxHeightFt = 0.0;
    	unsigned int MaxHeightLocation = 0;
    	int MinHeightPx = CurrentHeight;
    	double MinHeightFt = 0.0;
    	unsigned int MinHeightLocation = 0;
    	int Errors = 0;
    	double ImageTargetHeight = 0.0;
    	int ImageBaseTargetHeight = 0;
    	double ImageTerrainHeight = 0.0;
    	unsigned int BitPos = 0;
    	unsigned int ByteBlock = 0;
    	unsigned int ImageBaseArrayIndex = 0;
    	unsigned char Colors[8] = {48, 24, 16, 0, 0, 192, 96, 0}; // dark blue sky and green landscape
    	long Temp;
    	int ZoomFactor = 60; // sets the zoom factor value, or how much to shrink each side of the image by
    	unsigned int DebugStart;
    	BITMAPFILEHEADER TempFileHead;
    	BITMAPINFOHEADER TempInfoHead;
    	
    	FileHandle = fopen("C:\\My Documents\\My programs\\Terrain height test.bmp", "rb"); // first, read the data
    	fseek(FileHandle, 1078, SEEK_SET); // skip the header straight to the main data
    	fread(&TerrainData, 1, 144000, FileHandle);
    	fclose(FileHandle);
    	
    	/*
    	slope Y change - slope angle
    	0 - 0.000
    	5 - 4.764
    	11 - 10.389
    	16 - 14.931
    	22 - 20.136
    	28 - 25.017
    	35 - 30.256
    	42 - 34.992
    	50 - 39.806
    	60 - 45.000
    	72 - 50.194
    	86 - 55.098
    	104 - 60.018
    	129 - 65.056
    	165 - 70.017
    	224 - 75.005
    	340 - 79.992
    	*/
    	
    	TempInfoHead.biSize = 40;
    	TempInfoHead.biWidth = 7680/(long)ZoomFactor; // 7680 pixels wide (base image, high once rotated) at 1x zoom
    	TempInfoHead.biHeight = 144000/(long)ZoomFactor; // 144000 pixels high (base image, wide once rotated) at 1x zoom
    	TempInfoHead.biPlanes = 1; // must always be 1
    	TempInfoHead.biBitCount = 1; // monochrome bitmap
    	TempInfoHead.biCompression = BI_RGB; // no compression
    	TempInfoHead.biSizeImage = (DWORD)TempInfoHead.biWidth*(DWORD)TempInfoHead.biHeight/8; // the array size
    	TempInfoHead.biXPelsPerMeter = 2835; // this doesn't really matter what it is
    	TempInfoHead.biYPelsPerMeter = 2835;
    	TempInfoHead.biClrUsed = 2; // black and white only
    	TempInfoHead.biClrImportant = 2; // both possible are important
    	
    	TempFileHead.bfType = 19778; // fills out the structures // 19778 supposedly is "BM"
    	TempFileHead.bfSize = TempInfoHead.biSizeImage+62; // array length plus off bits (or 62)
    	TempFileHead.bfReserved1 = 0;
    	TempFileHead.bfReserved2 = 0;
    	TempFileHead.bfOffBits = 62;
    	
    	while ((ArrayIndex < 144000) && (TerrainData[ArrayIndex] != 0)) // loop until the end or unfinished areas are reached
    	{
    		if (TerrainData[ArrayIndex] == 203) { CurrentHeight -= 340; } // steepest downward slope
    		else if (TerrainData[ArrayIndex] == 251) { CurrentHeight -= 224; }
    		else if (TerrainData[ArrayIndex] == 48) { CurrentHeight -= 165; }
    		else if (TerrainData[ArrayIndex] == 72) { CurrentHeight -= 129; }
    		else if (TerrainData[ArrayIndex] == 96) { CurrentHeight -= 104; }
    		else if (TerrainData[ArrayIndex] == 120) { CurrentHeight -= 86; }
    		else if (TerrainData[ArrayIndex] == 143) { CurrentHeight -= 72; }
    		else if (TerrainData[ArrayIndex] == 167) { CurrentHeight -= 60; }
    		else if (TerrainData[ArrayIndex] == 191) { CurrentHeight -= 50; }
    		else if (TerrainData[ArrayIndex] == 215) { CurrentHeight -= 42; }
    		else if (TerrainData[ArrayIndex] == 239) { CurrentHeight -= 35; }
    		else if (TerrainData[ArrayIndex] == 32) { CurrentHeight -= 28; }
    		else if (TerrainData[ArrayIndex] == 56) { CurrentHeight -= 22; }
    		else if (TerrainData[ArrayIndex] == 80) { CurrentHeight -= 16; }
    		else if (TerrainData[ArrayIndex] == 104) { CurrentHeight -= 11; }
    		else if (TerrainData[ArrayIndex] == 128) { CurrentHeight -= 5; }
    		else if (TerrainData[ArrayIndex] == 151) { CurrentHeight += 0; }
    		else if (TerrainData[ArrayIndex] == 175) { CurrentHeight += 5; }
    		else if (TerrainData[ArrayIndex] == 199) { CurrentHeight += 11; }
    		else if (TerrainData[ArrayIndex] == 223) { CurrentHeight += 16; }
    		else if (TerrainData[ArrayIndex] == 247) { CurrentHeight += 22; }
    		else if (TerrainData[ArrayIndex] == 40) { CurrentHeight += 28; }
    		else if (TerrainData[ArrayIndex] == 64) { CurrentHeight += 35; }
    		else if (TerrainData[ArrayIndex] == 88) { CurrentHeight += 42; }
    		else if (TerrainData[ArrayIndex] == 112) { CurrentHeight += 50; }
    		else if (TerrainData[ArrayIndex] == 135) { CurrentHeight += 60; }
    		else if (TerrainData[ArrayIndex] == 159) { CurrentHeight += 72; }
    		else if (TerrainData[ArrayIndex] == 183) { CurrentHeight += 86; }
    		else if (TerrainData[ArrayIndex] == 207) { CurrentHeight += 104; }
    		else if (TerrainData[ArrayIndex] == 231) { CurrentHeight += 129; }
    		else if (TerrainData[ArrayIndex] == 255) { CurrentHeight += 165; }
    		else if (TerrainData[ArrayIndex] == 36) { CurrentHeight += 224; }
    		else if (TerrainData[ArrayIndex] == 84) { CurrentHeight += 340; } // steepest upward slope
    		else { Errors++; printf("Invalid color at location %d\n", ArrayIndex); } // error occurred!
    		
    		if (CurrentHeight > MaxHeightPx) { MaxHeightPx = CurrentHeight; MaxHeightLocation = ArrayIndex;} // logs minimums and maximums
    		if (CurrentHeight < MinHeightPx) { MinHeightPx = CurrentHeight; MinHeightLocation = ArrayIndex;}
    		
    		ImageTerrainHeight = CurrentHeight/(60.0*(double)ZoomFactor); // gives the height of the terrain in pixels
    		ImageBaseTargetHeight = (int)ImageTerrainHeight;
    		BitPos = (unsigned int)(ImageBaseTargetHeight) % 8; // gives offset for terrain data
    		
    		ByteBlock = 0;
    		
    		if (ArrayIndex % ZoomFactor == 0) // do only if the array index is a multiple of the zoom factor
    		{
    			while (ByteBlock < 960/ZoomFactor) // 256 bytes, 2048 pixels // each byte block is 26.4 feet
    			{
    				ImageTargetHeight = ((double)ByteBlock-1.0)*8.0; // /(double)ZoomFactor;
    				ImageBaseArrayIndex = ByteBlock+((960/ZoomFactor)*(ArrayIndex/ZoomFactor));
    				
    				if (ImageBaseTargetHeight < ImageTargetHeight) // if below, it should be all black
    				{
    					TerrainPreviewData[ImageBaseArrayIndex] = 0; // all 8 pixels are black
    				}
    				
    				else if (ImageBaseTargetHeight >= ImageTargetHeight+8.0) // if above the next step, it should be all white
    				{
    					TerrainPreviewData[ImageBaseArrayIndex] = 255; // all 8 pixels are white
    				}
    				
    				else
    				{
    					if (BitPos == 0) { TerrainPreviewData[ImageBaseArrayIndex] = 128; } // more white added for higher BitPos values
    					else if (BitPos == 1) { TerrainPreviewData[ImageBaseArrayIndex] = 192; }
    					else if (BitPos == 2) { TerrainPreviewData[ImageBaseArrayIndex] = 224; }
    					else if (BitPos == 3) { TerrainPreviewData[ImageBaseArrayIndex] = 240; }
    					else if (BitPos == 4) { TerrainPreviewData[ImageBaseArrayIndex] = 248; }
    					else if (BitPos == 5) { TerrainPreviewData[ImageBaseArrayIndex] = 252; }
    					else if (BitPos == 6) { TerrainPreviewData[ImageBaseArrayIndex] = 254; }
    					else if (BitPos == 7) { TerrainPreviewData[ImageBaseArrayIndex] = 255; }
    				}
    				
    				ByteBlock++;
    			}
    		}
    		
    		ArrayIndex++;
    	}
    	
    	while (ImageBaseArrayIndex < 15360000) // to fill the rest of the image as something odd to indicate incomplete areas
    	{
    		TerrainPreviewData[ImageBaseArrayIndex] = 9;
    		ImageBaseArrayIndex++;
    	}
    	
    	MaxHeightFt = (double)MaxHeightPx*0.055;
    	MinHeightFt = (double)MinHeightPx*0.055;
    	
    	RotateTerrainImage(TempInfoHead.biWidth, TempInfoHead.biHeight); // actual image dimensions passed to the function
    	
    	Temp = TempInfoHead.biWidth; // swap the width and height around
    	TempInfoHead.biWidth = TempInfoHead.biHeight;
    	TempInfoHead.biHeight = Temp;
    	
    	FileHandle = fopen("C:\\My Documents\\My programs\\Terrain height test heights.bmp", "wb"); // prepare to write a BMP file
    	fwrite(&TempFileHead.bfType, 2, 1, FileHandle); // it's only intended to run on my computer
    	fwrite(&TempFileHead.bfSize, 4, 1, FileHandle);
    	fwrite(&TempFileHead.bfReserved1, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfReserved2, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfOffBits, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biSize, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biWidth, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biHeight, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biPlanes, 2, 1, FileHandle);
    	fwrite(&TempInfoHead.biBitCount, 2, 1, FileHandle);
    	fwrite(&TempInfoHead.biCompression, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biSizeImage, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biXPelsPerMeter, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biYPelsPerMeter, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biClrUsed, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biClrImportant, 4, 1, FileHandle);
    	fwrite(&Colors, 1, 8, FileHandle); // the colors black then white
    	fwrite(&TerrainRotatedImageData, 1, TempInfoHead.biSizeImage, FileHandle); // writes the entire output image data (rotated)
    	
    	// fwrite(&TerrainPreviewData, 1, TempInfoHead.biSizeImage, FileHandle); // writes the entire output image data (nonrotated)
    	fclose(FileHandle);
    	printf("\n\nThe max height seen was %d (%6.3lf ft) at %d (%3.4lf mi).\nThe min height was %d (%6.3lf ft) at %d (%3.4lf mi).\nYou left off at %d (%3.4lf mi) and a height of %d (%6.3lf ft).\n\n", MaxHeightPx, MaxHeightFt, MaxHeightLocation, (double)MaxHeightLocation/1600.0, MinHeightPx, MinHeightFt, MinHeightLocation, (double)MinHeightLocation/1600.0, ArrayIndex, (double)ArrayIndex/1600.0, CurrentHeight, (double)CurrentHeight*0.055);
    }
    It's the rotation function in focus, not the bottom one that generates the terrain itself (the bottom one works just fine). Although integer division is involved, it's based on the width and height. In fact, the largest common multiple of the width and height is 1920* so anything in the ZoomFactor variable that is a multiple of 1920 would not cause rounding errors. 1920/8 is exactly 240. 1920/48 is exactly 40. I don't see why it's being shifted to the left 16 pixels when a multiple of 8 is used and otherwise random if a multiple of 16 and beyond are used.

    * These are the prime factors, those in common with both are multiplied (7 2's, a 3, and a 5 are common in both):

    7680
    2 2 2 2 2 2 2 2 2 3 5

    144000
    2 2 2 2 2 2 2 3 3 5 5 5

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    So at 8x and at 6 * 8x, the image goes buggy. I don't know an easy way to debug it, unfortunately.

    The x values appear good in the buggy images, but the y values are whacked. A breakpoint when the y value goes above the highest level of bright green AND the color is bright green, should help.

    Beyond that, just stepping through the code when the size is 8 and rotated, or 48 and rotated, seems best. I'd bet $$$ whatever's fouling up 8 is also the culprit at 6 * 8 size (rotated).

    Adak

  3. #3
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    I've filled the rotation stuff with nearly 200 lines' worth in debug-related stuff and I've been unable to find the cause. Although I do have a "Width /= 8" at the start, that's dividing the 7680 by 8 (taking 3 of the twos away, but that still makes the greatest common multiple as 960 and should still work with as high as 64). I could not find any other cause to this strange problem which is why I posted it here. The division by 8 at the start is to account for the fact that the image itself is 1-bit and dividing by 8 makes 8 pixels as a byte and I base it on the byte forming an 8x8 square. I've fixed all other bugs except this one.

    In the 8, I found that there is an offset of 16 pixels. That is, once it reaches the end of the 120-pixel area (7680/8/8), it seems to repeat 16 pixels per row. That is, for each row higher, the X positions of the pixels are offset to the left 16 pixels from the previous row. The bottom row, as far as I can tell, is correct.

    I don't know how to add break points and things in Visual C++ 2005 Express - I don't even know how to use the debugger either. This isn't a Windows program, rather, it's a command prompt program (hence the usage of printf). The only Windows elements used are for the bitmap file and the info header structs.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Talk about useless suggestions, but FileHandle doesn't have to be a global variable.

    Also, printf() doesn't have a &#37;lf format -- only scanf() does. printf() uses %f for floats and doubles.

    I'm sorry I can't help more . . . I never had much luck with rotation.

    [edit]
    I don't know how to add break points and things in Visual C++ 2005 Express - I don't even know how to use the debugger either. This isn't a Windows program, rather, it's a command prompt program (hence the usage of printf). The only Windows elements used are for the bitmap file and the info header structs.
    Almost anything you need for debugging can be found in the Debug or Run menu. I can't remember which, since I never use MSVC.
    [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    I was told in a thread like 2 months ago here that I needed to use &#37;lf for doubles. Then again, it was with sprintf() instead of printf.

    FileHandle is global because another related function also uses it, but only one function can use it as it is. I know that pointers (like the FILE element) can also be local, functions can return pointers and take them as parameters (if you've seen earlier messages, my LoadFile function used in my "The Interactive Animation" program takes multiple pointers as separate parameters.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    I was told in a thread like 2 months ago here that I needed to use &#37;lf for doubles. Then again, it was with sprintf() instead of printf.
    You mean here? Salem said not to use %d, nothing about %lf. %lf does not exist for *printf(). It's undefined behaviour. Anyway, that's almost certainly not one of your main problems.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    don't know how to add break points and things in Visual C++ 2005 Express - I don't even know how to use the debugger either. This isn't a Windows program, rather, it's a command prompt program (hence the usage of printf). The only Windows elements used are for the bitmap file and the info header structs.
    Now's a good time to learn how to use your debugger! They've been around since the stone-age of compilers, and have just gotten better. I use a very early pre-Windows Borland compiler many times, and always find it's debugger, incredibly valuable.

    Printf works fine with an IDE and debugger! Putchar() fails rather frequently in my Borland when I'm watching stuff, but printf - NEVER!

    Can you ID a specific point which should be dark staying dark blue, but is turning green instead, in the 8x and 48x rotated landscapes?

    Find that point, and that's your trail to follow, to fix this.

  8. #8
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    There is no determinable point where this happens. In a much simpler term, the effect seems to be like this:

    Code:
    4 8 C G K O S W // row 7
    3 7 B F J N R V // row 6
    2 6 A E I M Q U // row 5
    1 5 9 D H L P T // row 4
    4 8 C G K O S W // row 3
    3 7 B F J N R V // row 2
    2 6 A E I M Q U // row 1
    1 5 9 D H L P T // row 0
    It reads like this. A block is 8x8 pixels. When a byte is read, 8 pixels are read, from left to right starting on the bottom row - this due to the fact that the image is monochrome. For rotation to work properly, the width and height must be the same and thus an 8x8 block. I reduce the byte data into the individual bits as either zeros or ones. This data is stored in an array 64 long since a block is 64 bits. To rotate the image, the bits that were once read left to right are to be written bottom to top. This rotates the image counterclockwise. The bits are pieced back together again and the new output is written into the main array. The next block is then read which is 8 pixels further to the right, or pixels 8 through 15 and the process repeats again. Once it reaches the far right side of the image, it reads where the first pixels are, but 8 pixels up and it again continues to the right then up, like bitmap images are read. The output, however, is drawn bottom up which is not only a rotation, but a flip as well. This is where the usage of the greatest common multiple comes in. When the last block is processed, the loop becomes false and terminates.

    The image, "unzoomed" is 7680x144000 pixels, requiring 138,240,000 bytes to store (not including header data). With a zoom setting of 8, this reduces to 960x18000 pixels requiring just 15,360,000 bytes to store (not including header data). When run through my function, instead of the width being 960, it becomes 120 due to the division at the start, because there are 120 8x8 blocks spanning the width of the original image. Although integer division is involved in both cases, the results are exact so rounding errors aren't to blame. Yet, with the shift being 16 pixels, two blocks, it's even stranger than that. The division by 8 for the height is very similar - 18000 divided by 8 gives exactly 2250 (and with one two still to spare, it could still work for 16 and 48 zoom values). Even plugging values into the formulas for an array index doesn't yield anything as the results are as expected (referencing block 1, 4 (one block up from the bottom left and 4 blocks to the right (or in the area where coordinate (36, 12) is on a standard coordinate graph))):

    (Row+ArrayIndex)*Width+Column
    (8+4)*120+4 = 12*120+4 = 1440+4 = 1444

    (ArrayIndex*(Height/8))+(Column*Height)+Row/8
    (4*(18000/8))+(4*18000)+8/8 = (4*2250)+72000+1 = 9000+72000+1 = 81001

    Both of these are what is intended and all integer division comes out exactly on and correct without rounding errors. I see no reason at all why it would fail for 8 and 16. I would expect it to fail for 32 though due to the height, but not 8 or 16 (or 24 and 48 or 120 and 240).

    I spent two hours figuring just this out and this is as far as I can go.

    Another strange thing that occurred was when I flipped the image by referencing "143999-ArrayIndex" in the second function. Just by adding that, the file was reading zeros even though ArrayIndex wasn't changing and strangely enough, adding a simple printf statement fixed it. This is extremely bizarre and it makes no sense (unless there's a problem with the compiler itself).

  9. #9
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    "Strange behavior", or undefined behavior, quite often lurks in the places that you aren't looking, even given the fact that one assumes to know to likely culprits. When you've exhausted the likely culprits, start looking at code you "know" "should" be fine.

    Sometimes this gets into minutia, but such is the nature of bug hunting. Math in C sometimes differs from math on paper, so I might suggest looking there. Carefully watching array subscripting and being aware of issues might be another. A useful technique might also be to investigate assert.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I couldn't agree more with what Dave said, above.

    Even the smallest of things, should be checked out. Like this:

    Code:
    while (ArrayIndex < 8)
    		{
    			ImageRotateBlock[ArrayIndex] = TerrainPreviewData[(Row+ArrayIndex)*Width+Column];
    			ArrayIndex++;
    		}
    Does anything change if you change the Width + Column code above to:
    Code:
    TerrainPreviewData[(Row + ArrayIndex) * (Width + Column)];
    I'm quite leery of the Width+ Column not being enclosed in their own parenthesis, since Row + ArrayIndex are, and that is also just a simple addition.

    I've never seen a printf statement being added, fixing code. Yes, I'd say the compiler was knocked into a cocked hat, at that moment.

    Adak

  11. #11
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    Putting the "Width+Column" part in parentheses causes the array index referenced to always be the same. The width, the number of blocks wide the unrotated image is, is 120 with the zoom at 8. Bitmaps are read left to right, bottom to top. At the start, the row and array index are both zero. When ArrayIndex increases by 1, the next row up is read in the original. To successfully access it, the array index for TerrainPreviewData, the original data, must be increased by the width of the image divided by 8 (due to 1 bpp) which is 120. As it climbs up, it goes to that of 240, 360, 480, 600, 720, then 840. On the next round at this loop, Column has increased by 1 which would make the first element as 1. By enclosing Width+Column in parentheses, the area reference will always be the same. At first would it always access TerrainPreviewData[0] for all 8 times. When the column advances, it would reference 120 instead. This is problematic.

    I've messed around with the formulas and either it's distorted for all items or it works for everything but multiples of 8.

    I had more than twice as much code for debugging in the rotation function than actual code meant for the task and no matter what I use, I just don't see what the problem is.

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,453
    Since the actual size doesn't matter for the algorithm, why not post a much simplified implementation which rotates and scales say a 16x16 image (256 pixels, initialised with 0x00 to 0xff.

    Once you've got the algorithm to work, then try scaling it up to 800x600 or whatever.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    I found the problem. It's not my algorithm, it's the design of BMP files and the "zero padding". Using a 24x24 bitmap, and a loop to fill 72 bytes of the array (from 24*24/8), I was getting this odd effect with even a 24x24 image. Weirder yet, the top part of the image was all zeros when it should've been something else and the image itself was offset, even unrotated. I wasn't getting it, however, with 32x32. Bitmap images require that, if the number of bits per row is not a multiple of 32, extra bits must be filled (the "zero padding" as I refer to it as) to get the width a multiple of 32. Here's what's happening:

    The original, unzoomed image is 7680 pixels wide and 144000 pixels high, both multiples of 32. With a zoom set to 8, the image width is reduced to 960 and the image height is reduced to 18000. The width is okay, but when it comes to the height, however, the problem lies with the format of BMP images. The height is 18000. That is not a multiple of 32*. This explains the odd 16-pixel offset because half of 32 is 16 and the zero padding BMP requires if the width is not a multiple of 32, the extras at the end are ignored and this explains the shift. Because these extras are ignored and that it goes to the next 16 skipping over the important data. By adding the necessary padding, the problem should be resolved. The zoom of 4 works because the height of 36,000 is a multiple of 32*. Why the height instead of the width? The image is rotated which makes the width become the height and the height become the width. I've disliked this design of BMP.

    * An easy way to tell if it is or not is by the last 5 digits being a multiple of 32. Since the last 3 are zeros, the last two before them must be a multiple of 4 and 18 is not a multiple of 4. For the case of 36,000, 36 is a multiple of 4 making 36,000 a multiple of 32.

    Edit: algorithm, not code.
    Last edited by ulillillia; 05-03-2007 at 12:47 PM. Reason: algorithm, not code

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. image analysis theory: mapping a network
    By elninio in forum C++ Programming
    Replies: 5
    Last Post: 10-30-2008, 01:23 PM
  2. Yahoo's sign-in seal technology
    By George2 in forum Tech Board
    Replies: 12
    Last Post: 09-21-2006, 07:29 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Changing a treeview item's image
    By SMurf in forum Windows Programming
    Replies: 0
    Last Post: 01-14-2003, 06:08 PM
  5. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 11:39 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21