Rasterization Rules

People who have experience in graphics programming using graphics APIs such as DirectX, OpenGL, and OpenGL ES, must have been familiar with the term, "Rasterization". However, how many of you have heard about "rasterization RULES"? In other words, who do you know how hardware determines that a specific pixel on shared edge between two triangles belongs to which triangle? This could be a point of view from graphics hardware rather than programmer's because it is processed in driver software. Thereby, driver softwares should follow the rules up. As a result, programmers who develop the drivers should know how rasterization works. However, regardless that you are a graphics driver programmer or graphics software engineer using APIs, I believe that "understanding the basic theory" is always helpful and useful to learn other concepts as well as work in various environments. Today, I would like to go over "rasterization rules" in graphics.  As I briefly mentioned before, 1) two polygons could share their edges (i.e., a rectangle consisting of two triangles). Another case is that 2) two lines could share the point (i.e., a set of line segments). These are two cases for the rasterization rules.


1. Top-left rule:
A triangle rasterization rule (in Direct3D, OpenGL, GDI) defines how vector data is mapped into raster data. The raster data is snapped to integer locations that are then culled and clipped, and per-pixel attributes are interpolated before being passed to a pixel shader. Top-left rule ensures that adjacent triangles are drawn once.

The shared edge is the left edge of the Triangle (0,0, 5,0, 5,5). Thus pixels on the shared edge are included into the right triangle.  If we consider antialiasing or multisampling , it will be more complicated.


 
 
 
 
 
 
 

2. Diamond-exit rule:
This is a rasterization rule for line segments that share the end point. OpenGL uses a this rule to determine those fragments that are produce by rasterizing a line segment.
 

Hence, when rasterizing a series of connected line segments, shared end points will be produced only once. Then, the diamond regions where line segment exits cause rasterization to produce fragments. In the figure, two line segments share the end point that belongs to the green line based on the diamond-exit rule.

Add non-admin users to Developer Tools group on Mac

[Source: http://idtechnology.blogspot.com/2010/10/add-user-to-developer-tools-group.html]

To add a user to “Developer Tools” group:
dseditgroup -o edit -u {admin_user} -t user -a {user_name} _developer

Ray Traced Games in the Cloud using MIC

Ray Traced Games in the Cloud using MIC

Steve Jobs talks iOS 5 at WWDC 2011

WWDC 2011 liveblog: Steve Jobs talks iOS 5, OS X Lion, iCloud and more

Bit Operation #9

Print out odd numbers from 1 to 100

void printOddNumber()
{
    for (int i = 1; i <= 100; ++i)
    {
        if (i & 0x01)
            cout << i << \n;
    }
}

Bit Operation #8

100000
100000
------
011111

000000
000000
------
000000

100000
000000
------
000000

000100
000100
------
111011

100100
100100
------
011011

100100
000100
------
111011

010101
101010
------
000000

111111
111111
------
000000

// A function using bitwise operators for above results. 
unsigned int f(unsigned int a, unsigned int b)
{
    if (a & b)
    {
        return ~(a & b); 
    }
    return 0;
}

Bit Operation #7

Find the largest possible integer

int largestInt()
{
    return ~0;
}

Bit Operation #6

Extract a single bit from a character.

int extractBit(char byte, unsigned int pos) 
{
    assert(pos < 8);

    return ((byte >> pos) & 1);
}

Extract a range of bits from a character.

char extractBitRange(char byte, unsigned int startPos, unsigned int offset) 
{
   assert((startPos + offset) < 8);
   return (byte >> startPos) & ~(0xfe << offset);
}

Bit Operation #5

How can we check whether a particular bit is ON (1) or OFF (0)?

bool checkBitOn(unsigned int num, unsigned int i)
{
   return (num & (1 << i));
}

How can we turn OFF a particular bit in a number?

unsigned int turnBitOff(unsigned int num, unsigned int i)
{
    return (num & (~(1 << i)));
}

For example, num = 00010111 and i = 4. (1<<4)==00010000 and ~(1<<4)==11101111. Hence, num&(~(1<<4))==00010111 & 11101111==00000111.

Then, how can we turn ON a particular bit in a number?

unsigned int turnBitOn(unsigned int num, unsigned int i)
{
    return (num | (1 << i));
}

Bit Operation #4

Let's think about how we can count the bit set to 1 in an integer?

 

int bitCount(unsigned int a)
{
    int count = 0;
    while (a != 0)
    {
        count += a & 0x01;
        a >>= 1;
    }
    return count;
}

Then, how can we optimize the process to work with several integers?

Bit Operation #3

Input parameter a is a 4 bits integer (e.g., "1100" or "1000").

int f(int a)
{
    int b = 0;
    while (a >>= 1)
    {
       b++;
    }
    return b;
}

case1> 1100 (b==0)->0110 (b==1)->0011 (b==2)->0001 (b==3)->0000 : return 3
case 2> 1000 (b==0)->0100 (b==1)->0010 (b==2)->0001 (b==3)->0000 : return 3

This function returns the position of the leftmost '1' bit in input a.

Now, let's consider when 'while' statement can be infinite. Zero, with no non-zero bit, returns 0. A negative number throws the computer into an infinite loop. See below.

Signed 4bits integer
+7 : 0111
+6 : 0110
+5 : 0101
+4 : 0100
+3 : 0011
+2: 0010
+1 : 0001
+0: 0000
0 : n/a
-0 : 1111
-1 : 1000
-2 : 1001
-3 : 1011
-4 : 1100
-5 : 1101
-6 : 1110
-7 : 1111

Unsigned 4 bits integer
+15 : 1111
:
+7 : 0111
:
+1 : 0001
+0 : n/a
0 : 0000

Bit Operation #2

Let's think about simple examples again.

Input: 4 bits integer x (e.g., 1010)

int f(unsigned int x)
{
    return !(x & (x-1));
}

We know that (x & (x-1)) operation erases the rightmost 1 bit in x. Now, consider an integer that is a power of two has exactly one bit that is '1'. Hence, if x contains only one bit that is '1', (x & (x-1)) will be zero (0000). After applying 'logical not' operation (!), a value of 0 becomes 1 and a value other than 0 becomes 0.

Therefore, this function returns whether an integer is a power of two. Consider one case where the input x is zero (0000). Then, this function returns 1 saying x is a power of two although zero is not a power of two. Hence, we have to modify this function as below.

int f(unsigned int x)
{
    return x && !(x & (x-1));
    // same to (x != 0) && !(x & (x-1));
}

Bit Operation #1

Bit operation is very often asked in job interviews and can be very tricky. Here, I am going to brush up bit operation problems that can be expected in my future job interviews.

Input: 4 bits integer x (e.g., 1010)

int f(unsigned int x)
{
    int a = 0;
    while (x != 0)
    {
        x = x & (x-1);
        ++a;
    }
    return a;
}

Let's think of what (x-1) is in the case of x = 1010. (x-1) is 1001 because the rightmost bit of 1 in x is changed to 0 and all 0 bits to the right are changed to 1. Look at this details.
1 0 1 0
      |  |
      v  v
1 0 0 1

We can easily get the result after applying & operation for x and (x-1).
    1 0 1 0
& 1 0 0 1
-----------
    1 0 0 0

Hence, the result of & operation in while statement shows that the rightmost 1 bit of x turns to 0. Finally, if we do this operation until x become zero (0000), the variable 'a' will count the number of 1 bit in x.

Converting iPhone apps to iPad

OpenGL and OpenGL ES Tessellator

Tessellators and Quadrics
Polygon Tessellation In OpenGL
OpenGL Tessellation

GLU ES for OpenGL ES 1.x (for Win32)

iGLU: GLU for OpenGL ES 1.1 (for iPhone)
gluTessellator on iPhone

Anti-aliased line with Texture

How to Render Anti-Aliased Lines with Textures in iOS 4

Sharing custom data between two iPhone applications

In my iPhone application work, recently one issue came up. It is separating an iPhone application that I am developing into two applications while sharing custom data (i.e., images and text files) between two applications. So, I googled several forums with this issue. Here is my findings.

1) Using a server as a storage
2) Using a URL scheme
3) Using the pasteborad (UIPasteboard)
3) Using an "Address book" area

None of these was appropriate for my project where I need to share several images (1600x1200) and text files on a device without connection to a server. So, at this moment, I conclude that there is no way to share custom data between two iPhone applications.

[Reference 1] [Reference 2] [Reference 3] [Reference 4]

Code Sign Error after reinstalling provisioning profile

Sometimes Xcode project file easily gets messed up. For example, when I try to rebuild my application that worked well with my previous provisioning file yesterday, however I reinstall my provisioning file today. In this case, following error message can be show up;

"Code Sign Error: Provisioning Profile (long string) can't be found."

Here is an easy solution.

1) Open the project file in a text editor:
The .xcodeproj file is actually not a file but a directory, like an application bundle. So, you can right click it in Finder to open. Then, select "package contents". Now, you will see several files. The actual project file is "project.pbxproj". Open it in a text editor.

2) Search provisioning profile setting and manually erase the lines. Save the project file:
They will look like these;
PROVISIONING_PROFILE = "xxxxxx.....xxxxx";
"PROVISIONING_PROFILE[sdk=iphoneos*]" = "xxxxxx.....xxxxx";

3) Reopen the project in Xcode and go to the settings to reselect your new provisioning profile.

Android on the iPhone

Refer this blog

Using camera in your iPhone Application

Here are some of cool stuffs that can be referred for iPhone application development using build-in camera.

1. iPhone Camera Overlay App With Custom Button Example
2. Custom camera applications development using iPhone SDK
3. Custom UIImagePickerController camera view