Posts

Showing posts from 2010

Minimum Bounding Sphere for Frustum

Image
I was in need to create a minimum bounding sphere for a frustum (truncated pyramid). The easiest way is to find the "center" of this pyramid. I got it by calculating the middle point of "the center of the near plane" and "the center of the far plane". The radius will be the length between this middle point and one of the vertices of the far plane. This works however, this is not an optimal bounding sphere for frustum.

I sat down and tried to figure out this problem. It turns out there is a simple way of doing this. Since the frustum is created with perspective projection in mind, this frustum is symmetrical. Furthermore, if we temporarily forget about the aspect ratio, the problem can be reduced into 2D problem: "Given an isosceles trapezoid, find the circumscribed circle".

I got the image from http://mathcentral.uregina.ca/QQ/database/QQ.09.09/h/abby1.html. The first thing to realize is that the center of the enclosing circle is the intersectio…

Generating Alternating 0 and 1

Once upon a time, a friend of mine gave some of us a challenge. It's not exactly the same but quite similar ;) Anyway, think of ways you can generate alternating 0 and 1. If you have an Update() loop, the first time you call update it will generate 0 and the next time will be 1, and then 0,1,0,1,.. you get the idea. I found 3 ways to do this (assuming initial value of i is 0).

Math + Bit
i = (i+1) & 1; // You might think of this i = (i+1) % 2. Simple Math
i = 1 - i; Bits Operations
i = i ^ 1; Can you come up with more ways?

Avoiding Branch in Shader

Depending on which platform and target hardware, it can be a good idea to eliminate branches in shader. Here's two techniques with samples.

Lerp
Lerp, a.k.a. linear interpolation, is a useful function to select between two things. If you have two vectors v1, v2 and you want to select one of them based on some condition, lerp can be used. Make sure that the result of the condition (conditionMask)  is always 0 or 1.  You can then do this:
result = lerp(v1, v2, conditionMask); If your condition is 0, it will return v1. If your condition is 1, it will return v2.

Min/Max
Min and max is very useful in some cases. For example, let say you want to have one shader to switch between lit and not-lit. Typically, we will multiply the lighting value with color. For instance:
light = CalcLighting(); color *= light; So, the condition would be, if there's no lighting return 1; otherwise return the lighting value. We can easily do this with Lerp.
light = lerp(1, CalcLighting(), isLit); color *= l…

Simple XML parsing with Python

There are many ways to read/parse XML with Python.  I found at least 2 methods: DOM and SAX. Document Object Model (DOM) is a cross-language API from W3C for accessing or modifying XML; whereas SAX stands for Simple API for XML.

Most of the time, we don't need to understand the whole XML vocabularies; and most of the time we want to parse simple stuff like:
<root> <person name="somebody"></person> <person name="otherguy"></person> </root>
I think the simplest way to go is to use python minidom implementation that looks like this:
from xml.dom import minidom # parse the xml theXml = minidom.parse('data.xml') # iterate through the root rootList = theXml.getElementsByTagName('root') for root in rootList: # you can get the element name by: root.localName # iterate through person personList = root.getElementsByTagName('person') for person in personList: # get the attribute…

C# BitConverter

Missing the flexibility of C/C++ way in interpreting bits? In C/C++, you can reinterpret the bits by simply casting it. For example if you have an int and you want to reinterpret it as float, you can do the following:
int i = 1234; float f = *( (float*) &i ); The question is how can we do this in C#? It turns out there's a class in C# to do this. Meet BitConverter class.
int i = 1234; float f = BitConverter.ToSingle( BitConverter.GetBytes(i), 0 ); With this class, you can reinterpret bits from primitive data types. Which should be enough. The only problem is that the class is not suitable to be called every frames. Why? Using Reflector.NET, you can easily tell that BitConverter.GetBytes() is actually allocating memory!
public static unsafe byte[] GetBytes(int value) { byte[] buffer = new byte[4]; fixed (byte* numRef = buffer) { *((int*) numRef) = value; } return buffer; } One solution is just to keep in mind not to call this every frame. If you …