Twiddling - Revision history

Cooljerk at 12:53, 18 July 2025

2025-07-18T12:53:49Z

BBHoodsta: /* How and why the Dreamcast uses Twiddling */

2024-08-19T21:57:12Z

How and why the Dreamcast uses Twiddling

← Older revision		Revision as of 21:57, 19 August 2024
Line 223:		Line 223:
	One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.		One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.

	Interestingly, it has been discovered that applying the twiddle operation ~~two~~ times in succession on a twiddled texture can effectively untwiddle it.		Interestingly, it has been discovered that applying the twiddle operation three times in succession on a twiddled texture can effectively untwiddle it.

	A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.		A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.

BBHoodsta: /* How and why the Dreamcast uses Twiddling */

2024-08-19T21:50:21Z

How and why the Dreamcast uses Twiddling

← Older revision		Revision as of 21:50, 19 August 2024
Line 223:		Line 223:
	One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.		One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.

	Interestingly, it has been discovered that applying the twiddle operation ~~three~~ times in succession can effectively untwiddle ~~a texture~~.		Interestingly, it has been discovered that applying the twiddle operation two times in succession on a twiddled texture can effectively untwiddle it.

	A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.		A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.

BBHoodsta: /* How and why the Dreamcast uses Twiddling */

2024-08-19T18:34:00Z

How and why the Dreamcast uses Twiddling

← Older revision		Revision as of 18:34, 19 August 2024
Line 222:		Line 222:

	One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.		One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.

			Interestingly, it has been discovered that applying the twiddle operation three times in succession can effectively untwiddle a texture.

	A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.		A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.

Cooljerk: added info on why the DC does twiddling and what uses it has

2024-08-12T11:34:09Z

added info on why the DC does twiddling and what uses it has

← Older revision		Revision as of 11:34, 12 August 2024
Line 216:		Line 216:

	You would repeat until we have a single pixel. Once we have the last pixel, our new twiddled index should be the running sum '''s''' (16 + 2 + 0 == 18)		You would repeat until we have a single pixel. Once we have the last pixel, our new twiddled index should be the running sum '''s''' (16 + 2 + 0 == 18)

			== How and why the Dreamcast uses Twiddling ==

			Twiddling is used on the Dreamcast for two major purposes, both owing to the same mechanism. Inside the Dreamcast, there exists a form of hardware compression in the PVR called [https://en.wikipedia.org/wiki/Vector_quantization#L135 Vector Quantization], or VQ for short. VQ works by taking an image, and splitting the image up into tiles made of 2x2 pixel patterns. Each pattern is stored in a special bit of memory on the Dreamcast known as the VQ Dictionary. The VQ dictionary contains enough space to hold 1024 of these 2x2 pixel patterns. The purpose of this tiling is to reduce the ultimate size in memory of the original textured image, as the new texture, instead of containing RGB values for each texel, instead stores a single index value that references the VQ dictionary for every 4 texels. This is considered a form of [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch*L136 Lempel Ziv Welch compression].

			One can use VQ to compress textures in two ways. Firstly, one can do basic image compression as described above. However, the Dreamcast has a secondary use for the same VQ hardware, which allows it to mimic dynamic palettes of older game consoles. In this case, the original textured image is treated as though it was scaled up, so each texel comprises a 2x2 pixel region. When this is done, the VQ dictionary entries become 2x2 pixel patterns of solid color. This effectively maps single texel colors in the original texture, to VQ 2x2 solor color entries, like a palette. By changing the definition of a VQ dictionary 2x2 pixel pattern to a different solid color, you can alter every texel in the texture which references that color index. In this palette mode, 1024 entries is broken up into two formats which can be selected by the user. The first divides the palette up into sixty-four banks of 16 colors each, which makes the original texture behave like a [https://en.wikipedia.org/wiki/Color_depth#L137 4-bits per pixel] image. The other format divides the palette up into four 256 color banks, which is an 8bpp texture format.

			A last, side benefit of Twiddling on the Dreamcast is that is provides the precise pixels needed to do a 2x2 area Anti-Alaiasing filter in hardware at no extra cost.

	== DISCLAIMER ==		== DISCLAIMER ==

Unknown user: /* Conceptualizing Twiddling */

2023-05-14T06:22:19Z

Conceptualizing Twiddling

← Older revision		Revision as of 06:22, 14 May 2023
Line 20:		Line 20:

	So if we are given index '''i''' from an untwiddled image and wished to find the twiddled index, then its a process of recursively narrowing down what part of the twiddled image that pixel now lives in.		So if we are given index '''i''' from an untwiddled image and wished to find the twiddled index, then its a process of recursively narrowing down what part of the twiddled image that pixel now lives in.

			Example:

			Original: Twiddled:

			0 1 2 3 0 2 8 A
			4 5 6 7 1 3 9 B
			8 9 A B 4 6 C E
			C D E F 5 7 D F
			G H I J G I O Q
			K L M N H J P R
			O P Q R K M S U
			S T U V L N T V
			W X Y Z W Y % &
			~ ! # $ X Z ^ *
			% ^ & * ~ # ( _
			( ) _ + ! $ ) +

	== Look-up Table Hack ==		== Look-up Table Hack ==

Unknown user: /* Protofall's Implementation */

2023-05-14T06:22:00Z

Protofall's Implementation

← Older revision		Revision as of 06:22, 14 May 2023
Line 139:		Line 139:
	== Protofall's Implementation ==		== Protofall's Implementation ==

	How to generated the twiddled index from an untwiddled texture		How to generated the twiddled index from an untwiddled texture:

	~~Lets start with a small example~~:

	Original: Twiddled:		Original: Twiddled:

Unknown user: /* Look-up Table Hack */

2023-05-14T06:19:58Z

Look-up Table Hack

← Older revision		Revision as of 06:19, 14 May 2023
Line 61:		Line 61:

	unsigned short x; // Interleave bits of x and y, so that all of the		unsigned short x; // Interleave bits of x and y, so that all of the

	unsigned short y; // bits of x are in the even positions and y in the odd;		unsigned short y; // bits of x are in the even positions and y in the odd;

	unsigned int z; // z gets the resulting 32-bit Morton Number.		unsigned int z; // z gets the resulting 32-bit Morton Number.

	z = MortonTable256[y >> 8] << 17 \|		z = MortonTable256[y >> 8] << 17 \|

	MortonTable256[x >> 8] << 16 \|		MortonTable256[x >> 8] << 16 \|

	MortonTable256[y & 0xFF] << 1 \|		MortonTable256[y & 0xFF] << 1 \|

	MortonTable256[x & 0xFF];</syntaxhighlight>		MortonTable256[x & 0xFF];</syntaxhighlight>

Unknown user at 06:19, 14 May 2023

2023-05-14T06:19:18Z

Show changes

Unknown user at 05:07, 14 May 2023

2023-05-14T05:07:56Z

← Older revision		Revision as of 05:07, 14 May 2023
Line 47:		Line 47:
	Here are my steps:		Here are my steps:
	* We first need to start by figuring out the "Biggest-Order Inverted-N" ('''BOIN''') that fits in this image.		* We first need to start by figuring out the "Biggest-Order Inverted-N" ('''BOIN''') that fits in this image.
	* Now if our starting image was a square, then the BOIN is the same size as the image		* Now if our starting image was a square, then the BOIN is the same size as the image
	* For rectangles like this, we have to find the smallest side first (width) then our BOIN is width * width		* For rectangles like this, we have to find the smallest side first (width) then our BOIN is width * width
	* If we start off with a rectangle, then we need to do an extra step that squares can skip.		* If we start off with a rectangle, then we need to do an extra step that squares can skip.
	* Notice how we can completely encapsulate the whole image with '''(bigger_side / smaller_side) == 3''' BOINs? Our first step is to determine which of these BOINs our index '''i''' belongs in.		* Notice how we can completely encapsulate the whole image with '''(bigger_side / smaller_side) == 3''' BOINs? Our first step is to determine which of these BOINs our index '''i''' belongs in.
	* We can take advantage of a quirk I mentioned earlier. Notice how the first BOIN contains the first 1/3 of the original pixels, the 2nd BOIN contains the next 1/3 and the 3rd BOIN contains the last 1/3.		* We can take advantage of a quirk I mentioned earlier. Notice how the first BOIN contains the first 1/3 of the original pixels, the 2nd BOIN contains the next 1/3 and the 3rd BOIN contains the last 1/3.
	* Therefore using the formula '''k = floor(i / (BOIN area == 4 * 4 = 16)) == 1''' we can determine that our twiddled index is somewhere in the middle/2nd BOIN (Since '''k''' is of the set '''{0,1,2}''')		* Therefore using the formula '''k = floor(i / (BOIN area == 4 * 4 = 16)) == 1''' we can determine that our twiddled index is somewhere in the middle/2nd BOIN (Since '''k''' is of the set '''{0,1,2}''')
	* Note the index where our BOIN starts according to the original texture. The first index in the 2nd BOIN is "16". Keep track of this value, lets call it '''d'''		* Note the index where our BOIN starts according to the original texture. The first index in the 2nd BOIN is "16". Keep track of this value, lets call it '''d'''
	* Also keep track of the index where our BOIN starts according to the twiddled texture, this is also '''16''' in this case. Lets add this to a running sum '''s'''		* Also keep track of the index where our BOIN starts according to the twiddled texture, this is also '''16''' in this case. Lets add this to a running sum '''s'''
	* Forget about the other two BOINs and subtract '''d''' from the indexes in our new BOIN as well as '''i'''		* Forget about the other two BOINs and subtract '''d''' from the indexes in our new BOIN as well as '''i'''

	So now we have:		So now we have:
Line 69:		Line 69:
	* So we determine how many pixels are in each quadrant (4 per quadrant here, '''== a'''), Then calculate '''k = floor(i / a) == 2''' to know its in the 3rd quadrant ('''k''' is in the set '''{0,1,2,3}''').		* So we determine how many pixels are in each quadrant (4 per quadrant here, '''== a'''), Then calculate '''k = floor(i / a) == 2''' to know its in the 3rd quadrant ('''k''' is in the set '''{0,1,2,3}''').
	* That means its in the top right. So we need to set '''d = a * k'''), add our new '''s''' value to the running sum, discard the other quadrants, then subtract '''i''' and the new BOIN's indexes by '''d'''		* That means its in the top right. So we need to set '''d = a * k'''), add our new '''s''' value to the running sum, discard the other quadrants, then subtract '''i''' and the new BOIN's indexes by '''d'''
	* The easy way to calculate the new part of '''s''' is that:		* The easy way to calculate the new part of '''s''' is that:
	* top left quadrant is '''0'''		** top left quadrant is '''0'''
	* top right quad is '''BOIN-width / 2'''		** top right quad is '''BOIN-width / 2'''
	* bottom left is '''BOIN-width * (BOIN-height / 2)'''		** bottom left is '''BOIN-width * (BOIN-height / 2)'''
	* bottom right is '''(BOIN-width * (BOIN-height / 2)) + (BOIN-width / 2)'''		** bottom right is '''(BOIN-width * (BOIN-height / 2)) + (BOIN-width / 2)'''

	Now we have:		Now we have: