June 7th, 2011
Loading… please wait.
As you can imagine, I will probably have slightly less time for other projects in the next few years 
March 14th, 2011
This is embarrassing, but there was a bug in the previously posted SAP code. Fetch the new version here:
http://www.codercorner.com/Code/SweepAndPrune3.rar
Thanks to Olli-Pekka Räsänen for reporting it!
February 9th, 2011
How clean your source code looks like is not as important as how clean your generated code looks like.
When supporting multiple platforms, your code not only has to work on the weakest machine. It also has to be compiled by the weakest compiler.
Don’t trust the compiler. No, it will not magically optimize your crap.
Faster convex-convex SAT: internal objects
January 24th, 2011
I noticed that I had a fairly low amount of posts in the “physics” category, for somebody working in physics & collision detection all day long. So let me try to increase the ratio a bit. Last time we talked about partial hulls, today I’ll present another optimization for the same problem.
The penetration depth between two convex polytopes can easily be computed using separating-axis tests. But the large number of edge-edge tests often makes this process very slow, and other algorithms such as EPA or Xenocollide are thus often chosen over SAT to compute the MTD between two convexes. There are however a large number of tricks to optimize the SAT version. One of the most efficient ones is to use simple “internal objects”, i.e. simple objects such as a sphere or a box embedded in the convex.
Recall that for each candidate axis we do something like:
bool testSepAxis(const btVector3& axis, const MyConvex& hull0, const MyConvex& hull1, float& dmin, Vector3& mtd)
{
// Project hull 0 on candidate axis
float Min0,Max0;
hull0.Project(axis, Min0, Max0);// Project hull 1 on candidate axis
float Min1,Max1;
hull1.Project(axis, Min1, Max1);// If the projected intervals don’t overlap, the candidate axis is a separating axis.
// In that case the hulls don’t overlap, we can early exit and return non penetration.
if(Max0<Min1 || Max1<Min0)
return false;// Else compute penetration depth (PD) = how much the intervals overlap
const float d0 = Max0 - Min1;
const float d1 = Max1 - Min0;
const float depth = d0<d1 ? d0:d1;// Then keep track of minimal PD. The axis for which the PD is minimal is the MTD.
if(d<dmin)
{
dmin = d;
mtd = axis;
}
return true;
}
So we’re looking for the minimal overlap, and the MTD is the axis for which the overlap is minimal. The idea, then, is to first project the simpler, internal objects on the candidate axis, and use the overlap results to skip the real hull projections if we can.
Say our internal objects are spheres (it could also be boxes, but for the sake of the argument let’s use spheres). Let hullOverlap(V) be the overlap value for the hulls on a given axis V, and sphereOverlap(V) be the one for the spheres on the same axis. Since spheres are embedded in the hulls, it should be clear that we always have:
hullOverlap(V) >= sphereOverlap(V) (1) (see Figure 1)
Now let minHullOverlap be our current best result, i.e. our current minimal penetration depth computed from real hull projections (not sphere projections). It should be obvious that thanks to (1) we have:
sphereOverlap(V) > minHullOverlap => hullOverlap(V) > minHullOverlap (2)
In other words, if sphereOverlap(V) is already bigger than our current best result, hullOverlap(V) will be bigger as well, and thus there is no need to compute it.
Figure 1
This is interesting since, of course, projecting a sphere is a lot faster than projecting a convex hull. Projecting a sphere is one dot product, projecting a hull is one dot product per vertex (plus, we don’t need to even access the vertex memory).
As Figure 1 shows, the embedded spheres don’t need to actually touch for this test to be useful - only the spheres’ projections on the candidate axis. In practice, this happens very often, and that single optimization sometimes culls away 90% of the actual hull projections. You can try out this demo for a proof-of-concept.
It is also a good idea to test the MTD from the previous frame first, to initialize minHullOverlap to a small value right from the start - discarding candidate axes as early as possible.
Finally a note about the internal shapes one should choose. A sphere might not be a great fit for long thin rods, in which case an embedded box might be better. But it might be easier to just use both, and at runtime choose whatever internal shape gives the best results. This is what I do in the above demo.
January 7th, 2011
Let me make a bold statement:
All functions taking a “const String&” parameter as input are bad.
…where String is either your own custom string class, or std::string, whatever. This is bad, of course, because it forces your users to have a String around. If they get the string from an external source (typically as “const char*”) you just forced them to create a temporary String just to call the function (or worse, the temporary will get created without them even noticing). Since you pass it as a const, you will not modify the text and there is no reason to force people using a String. The proper API just takes a “const char*” parameter.
(Yeah, yeah, I know, it ignores Unicode stuff and loses some minor optimizations when the String class caches the length of the text, whatever, you get the idea of the bold statement. And also, any const function in the String class is stupid, as an old classic GOTW entry showed eons ago).
January 7th, 2011
Just noticed this from http://89.151.96.106/forums/viewtopic.php?f=1&t=54587&start=25
There’s two topics haunting me on this forum:
This one, and a topic where I managed to write that OPCODE was messy code!
Pierre Terdiman commented on that, of course.
That was years ago, but I clearly remember it.
Looking at OPCODE now, of course I realise that it’s actually remarkably clean code!
All you people who complained about the coding style in OPCODE - you know who you are -, take that!
November 25th, 2010
Ok, time for a new KP release: www.codercorner.com/KonokoPayne_WIP_November_2010.rar
It contains the “Konoko HD” seen in the previous post, the Lara Croft character, tons of bug fixes and new content in the main game (that underground compound now has some 4000 meshes for a total of about 600.000 faces).
It takes me 26 to 28 minutes to “do everything” in the main game, and that’s when I skip all the dialogs and I know exactly what to do in what order. Still far from a real game but a lot better than previous releases. For now the game “ends” when you complete the side mission given by the scientist in the Xenolab (or, depending on what you did, it “ends” when you manage to reach the room directly above the “machine room”). Note that it doesn’t really “end”, you just reach the point where there’s nothing left to see/do in the level.
Stay tuned, there’s much more in the pipeline!
…if only it wouldn’t take years to work on that
EDIT: WTF, WTF, WTF! I’m tired of this BS. This probably falls again in the “Globat sucks” category. For some reason the link is broken and I have no idea why. I *did* download that file yesterday to make sure it was working. And today the link is broken. I can see the file in FileZilla, I re-uploaded it, I uploaded it to a different location, and still I can’t access it and I get a 404 trying to download it. WTF I hate internet. Sorry guys I have zero idea what’s going on. Any clue anybody?
November 3rd, 2010
The guys at Oni Central did it again… It takes a lot to impress me but I’m constantly baffled by what those people manage to pull out. Anyway this time one of them created a gorgeous HD version of Konoko. Check it out in the screenshots below! (click on thumbnails to load a larger image). In those pics you can also see some of the levels/rooms I’ve been working on recently.
Lockers room and fight in “depot 03″:
The new Xeno-biology lab:
Running lariat in the xeno-lab:
The new “machine room”:
Pistol disarm in the corridors:
Misc throws & weapons poses:
The day my heart stopped beating
October 26th, 2010
I woke up Saturday morning, one week ago, with a pain in my chest. I felt pretty bad, like I could not breathe, so I got up, and went to the window to get some fresh air. A big unusual warmth went to my head. I felt dizzy.
Next thing I know, I wake up on the ground, a cold and hard surface against my cheek, a huge pain in my face and neck, pieces of teeth in my mouth. Looks like I passed out.
What happened immediately afterwards remains fuzzy. It is enough to say that I made it to the hospital. I probably looked terrible because the lady at the entrance did not even try to make me wait, for once. Admittedly I had a pretty bad looking bump on my forehead, broken teeth and blood in my mouth, and when I mentioned chest pains it quickly finished to convince her she had to let me in, now.
They immediately started running some tests, one CT Scan for the neck, one ECG, and they plugged me to various devices to record what was happening. I was quite shaken and my neck hurt like crazy, but the initial tests did not reveal anything, to the point that they were ready to release me the same day, a couple of hours after my arrival.
But then, while waiting in the bed, still plugged to the machines, I passed out once again.
It is a very curious feeling. There was no chest pain this time. Just a rush of warmth going to the head, like a fever on steroids or something, and the dizziness again. And then black out. A few seconds later the image and sound came back at once. It took me some good 10 seconds though, to realize what was going on, where I was, and who the hell were all those panicked-looking people around me.
Curiously at that very moment I felt very good, like waking up from a long invigorating nap. No pain, nothing. I think a friend of mine was right on the money when he called that a “reboot”.
Nonetheless, doctors were all around me, and they told me my heart had stopped beating for 6 seconds. They showed me the nice graph freshly printed from the recording device. It felt slightly unreal. I could look at the evidence with my own eyes but still, at that moment I felt totally fine. And the doctors looked happy too, to have recorded something like this “live”.
Needless to say, after that, they refused to let me go anymore. They put me in the “monitoring room”, and kept me there for a week. They ran on me all the tests they had in stock. I had 3 CT Scans, 1 MRI, 2 ultrasound tests, countless ECGs, and a number of other tests I don’t even have names for. They took my blood 3 times, checked the blood pressure, the tension, the cholesterol, etc, etc.
And it all came back negative. Nothing. Nada. According to all their tests, the heart is “structurally correct” and the blood flow within is also working correctly. The CT Scan from the head didn’t reveal any tumors or head-related cause. The blood pressure is normal, everything is “desperately normal”. The first day they were already mentioning giving me a pacemaker. By the end of the week that option was off the table.
Both the Zürich doctors and my father (also a cardiologist) now think that I had a “vasovagal syncope“. They can not really pinpoint why it happened, but they all seem to think it is nothing too serious (or at least, not as bad as they thought it was). Best proof of this, I guess, is that they let me go.
So that’s the good news. The bad news, of course, is that they did not really “fix” anything, and this can apparently happen again, at any time. Still, it’s much better than any of the other nasty things it could have been.
Otherwise, I can also report that:
- some of those tests are very unpleasant. They inject you with slightly radioactive “constrast material” stuff that leaves an ugly metal taste in your mouth (even though it’s injected directly in the vein). I also hated the MRI. They strap you to the bed with heavy headphones so that you can follow the commands, and you are left for 40 minutes in that tube. It feels like a coffin, I hated it.
- the nurses driving the bed to the MRI got lost in the building! We ended up in some basement which looked more like a warehouse than a hospital (we crossed half a dozen forklift trucks on the way). At some point the nurses entered an elevator, started discussing/arguing about the directions (all in German, sorry)… and then we left the elevator without even using it. That’s when I started to suspect something was fishy. In the end they had to ask some guy for the proper direction. Oh dear.
- overall though, they’re very efficient and organized compared to, say, France. I’m glad this happened in Switzerland…
- doctors said it was not a consequence of drinking too much coffee
So that’s it. I’m back. Stuff like this certainly makes you appreciate the simple joy of being alive and breathing.