July 17, 2010

Showcase of some work I did for WinMo6 using .Net + GapiDraw

Parts of a prototype I developed in Dec'08-Jan'09. The target was the HTC Diamond (Windows Mobile 6).

The main requirement was to "make it look nice like on the iPhone", which meant swiping, shaking, and smooth animations. Despite Windows Mobile's Big Suck Factor, this was made possible thanks to the use of the GapiDraw 4 library, for which I created a .Net wrapper. The result displayed at 60fps.

The phone's light sensor was used to alter the pace of an animation used to showcase the hybrid car's aircon system.

December 08, 2009

Frustum culling: Sphere-Cone test with no squareroot

I crossposted this article at GameDev.

I've found a method for checking if a sphere is partially or totally included inside a cone without using a square root, as the square root has a big overhead on some FPUs, especially on mobile platforms (e.g., on the VFP11 and NEON units of the armv6 and armv7 processors).

Original algorithm

I started with Charles Bloom's algorithm as presented in the second part of this document:

V = sphere.center - cone.apex_location
a = dotProduct(V, cone.direction_normal)
b = a * cone.tan
c = sqrt( dotProduct(V,V) - a² )
d = c - b
e = d * cone.cos

now, if ( e >= sphere.radius ):
    cull the sphere (return 0)
else, if ( e <=-sphere.radius ):
    totally include the sphere (return 1)
    the sphere is partially included (return -1)

What's going on in this cone-sphere test? Basically,
I'm trying to find 'e' which is the shortest distance
from the center of the sphere to the surface of the cone.
You can draw some pictures and see what's going on.
'a' is how far along the ray of the cone the sphere's
center is. 'b' is the radius of the cone at 'a'. 'c' is
the distance from the center of the sphere to the axis
of the cone, and 'd' is the distance from the center of
the sphere to the surface of the cone, along a line
perpendicular to the axis of the cone (which is not the
closest distance).

Simplified form

The algorithm can be simplified and turned into the following:

V = sphere.center - cone.apex_location
a = dotProduct(V, cone.direction_normal)
x = cone.cos * sqrt(dotProduct(V,V) - a²) - a*cone.sin
if abs(x)>sphere.radius:
    if x<0, totally include the sphere (return 1)
    else,   cull the sphere (return 0)
else the sphere is partially included (return -1)

sqrt() must die!

Using squared inequalities, this in turn leads to the following sqrt-free formulation:

V = sphere.center - cone.apex_location
a = dotProduct(V, cone.direction_normal)
p = a*cone_sin
q = cone_cos² * dotProduct(V, V) - a²
r = q - sphere_radius²
if (p<sphere_radius) || (q>0):
    if (r < 2 * sphere_radius * p):
        the sphere is partially included (return -1)
    else if q<0:
        the sphere is totally included (return 1)
        cull the sphere (return 0)
    if ( -r < 2 * sphere_radius * p):
        the sphere is partially included (return -1)
    else if q<0:
        the sphere is totally included (return 1)
        cull the sphere (return 0)

Source code

Here is the source of the two methods: Charles Bloom's and mine.

December 06, 2009

Fast sine/cosine for ARMv7+NEON

I also posted this on StackOverflow so people could test it on real hardware.

Here is a function I wrote to compute sines and cosines really fast on the NEON vector FPU (iPhone 3GS, Pandora, BeagleBoard, …). I used a method described by Nicolas Capens and the fact that cos(x)=sin(x+90deg). Nils Pipenbrinck was kind enough to time it on his BeagleBoard and produced these results. Your mileage may vary.

September 06, 2009

Preserving aspect ratio, the pure CSS way...

When dealing with elastic layouts, web designers have to face the harsh reality of CSS styling: there is no way to enforce an aspect ratio on a certain HTML element, nor to somehow link its height to its width. Not without relying on Javascript.

At least there wasn't. Until now. I came up with a solution involving giant transparent images. The GIF files are only 2KB large, so it has no impact on the loading times.

The <IMG> tag has always been a bit special: web browsers try to maintain pictures aspect ratio. And since a container will adapt to its content's size, a <IMG> in a <DIV> should provide a way to enforce a fixed ratio between the dimensions of the latter! That was the general idea, and I implemented it in the two following pages:

June 05, 2009

What do those scripting Web2.0 languages cost?

We see a lot of people coding their services in Ruby or in PHP, users not really caring about it, and tech journalists finding those new tech like Ruby on rails really cool! But when I read these benchmarks, it made me think...

In practice, you most likely won't notice any huge performance difference between web services written in any scripting language and in good old C/C++, since most will be limited by network latency/bandwidth and/or the quality of their cache strategies.

However, if you took the CPU load into account, as it accounts a lot when you RENT some cloud services like Google App Engine, Amazon Elastic Compute Cloud or maybe Yahoo Sherpa if they finally release it someday, then it would translate into vast amounts of money.

According to those aforementioned benchmarks, C++ performs 90 times better than Ruby, and it seems to mean that you would pay for 90 times more CPU hours if your web service were written in Ruby than for the same service written in C++.

Also, wouldn't C++ be more eco-friendly than Ruby because of its putting lower stress on the hardware translating in a lower carbon footprint? With the current Green trend, will we see more services written in C/C++ then?

PS: on a side note, I find it a shame that C/C++ is still the only available choice in 2009 when you want performance. I would be very happy to refrain myself from using any advanced dynamic features from Python, Ruby, et al. if the guys behind those cute languages provided me with a native compiler producing code as fast as C/C++.

PS-2: C++ quietly continues to evolve behind the scripting teens Web2.0 scene, and now provides some really neat high-performance networking features, like ASIO for instance, which allows for writing AJAX/Web2.0 services almost as easily as you would do with PHP.

UPDATE: Wt, pronounced [wit-ty], is a high-performance C++ Web Toolkit for building rich web apps. It will make use of AJAX if the browser supports it but will also degrade nicely if Javascript is not available. It has a nice signal/slot mechanism inspired by Qt that makes it far more productive than JavaEE. Building a web app with Wt is thus just like building a desktop application. Check it out at http://www.webtoolkit.eu/.

UPDATE: Pion is a nice C++ platform for implementing lightweight HTTP services, built on Boost and the ASIO asynchronous I/O library mentioned above. It is being actively developed (latest version was released only a few days ago).

I would really be interested in hearing your thoughts about this, so don't be shy and drop me a line on Twitter! I am @jcayzac.

February 22, 2009

Please update your bookmarks

I have changed my blog URL from blog.brainlex.com to blog.julien.cayzac.name, so if you have subscribed to my feeds, please update accordingly.

October 02, 2008

Arc and distance between two points on Earth surface

The following C++ snippet computes the arc (in radians) and the distance (in meters) between two positions on Earth using the law of haversines.

It assumes a Position class exists, with two public members for the longitude and the latitude (resp. "lon" and "lat").

/// @brief The usual PI/180 constant
static const double DEG_TO_RAD = 0.017453292519943295769236907684886;
/// @brief Earth's quatratic mean radius for WGS-84
static const double EARTH_RADIUS_IN_METERS = 6372797.560856;

/** @brief Computes the arc, in radian, between two WGS-84 positions.
  * The result is equal to <code>Distance(from,to)/EARTH_RADIUS_IN_METERS</code>
  *    <code>= 2*asin(sqrt(h(d/EARTH_RADIUS_IN_METERS )))</code>
  * where:<ul>
  *    <li>d is the distance in meters between 'from' and 'to' positions.</li>
  *    <li>h is the haversine function: <code>h(x)=sin²(x/2)</code></li>
  * </ul>
  * The haversine formula gives:
  *    <code>h(d/R) = h(from.lat-to.lat)+h(from.lon-to.lon)+cos(from.lat)*cos(to.lat)</code>
  * @sa http://en.wikipedia.org/wiki/Law_of_haversines
double ArcInRadians(const Position& from, const Position& to) {
    double latitudeArc  = (from.lat - to.lat) * DEG_TO_RAD;
    double longitudeArc = (from.lon - to.lon) * DEG_TO_RAD;
    double latitudeH = sin(latitudeArc * 0.5);
    latitudeH *= latitudeH;
    double lontitudeH = sin(longitudeArc * 0.5);
    lontitudeH *= lontitudeH;
    double tmp = cos(from.lat*DEG_TO_RAD) * cos(to.lat*DEG_TO_RAD);
    return 2.0 * asin(sqrt(latitudeH + tmp*lontitudeH));

/** @brief Computes the distance, in meters, between two WGS-84 positions.
  * The result is equal to <code>EARTH_RADIUS_IN_METERS*ArcInRadians(from,to)</code>
  * @sa ArcInRadians
double DistanceInMeters(const Position& from, const Position& to) {
    return EARTH_RADIUS_IN_METERS*ArcInRadians(from, to);