Coder Corner

Don’t claim your engine is “next gen” if you don’t even have those.

What is the most used feature of a level editor? I’ll tell you: object selection - a.k.a. picking. Point and click, point and click, all the time. So it would make sense to polish this part of the editor as much as possible, right? Yet I saw a number of in-house editors whose picking was surprisingly tedious to use. (Not that commercial editors are any better in that respect: 3DS MAX has probably the worst picking I’ve ever seen).

Good picking 101:

• make sure the ray is correctly computed
• make sure the picking code is fast
• make sure backface culling is properly handled
• make sure the picking code knows about your camera’s near plane

The two first ones are obvious so I’m not gonna cover that.

Backface culling should be obvious as well, but it’s not. The problem is that there are two different backface culling to consider: the one based on geometry, and the one based on materials. Geometric culling happens at the triangle level, without taking the triangle’s material into account. The triangle can be CW or CCW and the ray-vs-triangle code usually only works against one kind of triangles only - or it skips the test completely and considers the triangle double-sided. Now, regardless of this, a triangle can have a material whose culling render state (typically D3DRS_CULLMODE) is completely different from the triangle’s “natural” (geometric) culling. Needless to say, it wrecks havoc on the poor picking code, and it’s easy to end up with a visible triangle on screen that you just can’t select. For example it might be a CCW triangle with a CULL_NONE render state, failing to pass the geometric test. Or the opposite: a proper CW triangle with a CCW material, meaning the user can select a triangle he doesn’t see. Yes, it’s a mess. And yes, it happens. Often. Hence the rant. Fixing it is easy: the backface culling code has to consider both the triangle’s orientation (CW/CCW) and its rendering properties. It’s painful to do if you rely on an opaque physics engine to cast a ray through the scene for you, but that’s the price to pay for a good, solid picking experience.

But wait, there’s more. The most frustrating picking issue ever is when you clearly see an object in the viewport, you click it… and nothing happens. It just selects another object. It selects an object behind the camera. Or is it, really? What usually happens is that the camera’s near clip plane is not zero (zero is bad), and as a result any geometry located between the camera’s position and the near clip plane is not rendered. However, the raycast used to pick up objects typically starts directly from the camera’s position. In other words, the ray can hit objects that are not even rendered and visible to users. In a level editor where the camera is free to go everywhere, through walls and everything, this actually happens a lot! And it creates a lof of pain for the poor users. Fixing it is easy: if your near clip plane is set to N, start the raycast N units away from the camera’s position. That’s all!

I recently posted an article from last year, about the “sweep and prune” algorithm. I previously posted it on the Bullet forums but couldn’t upload it on CoderCorner for technical reasons.

Today, I finally found some time to put the source code together, extract it from ICE, and upload it as well. So, here it is. It’s an efficient implementation of an array-based sweep-and-prune. It should be fast. In my tests I found it faster than my previous version from OPCODE 1.3, and also slightly faster than the PhysX implementation. For technical details about this new version, please refer to the document above.

The library doesn’t support “multi-SAP” yet, I will need to find more time to seat and re-implement that in a releasable form. Oh well, later.

Click here to download

Re-inventing square wheels is a waste of time. On the other hand, using standard libraries makes your product look and feel like all the others. I don’t want to have a standard product. I want to crush the competition with bright polished shiny wheels that they don’t have.