Sorry I took so long to do this! After the last update I got submerged in a huge pile of work, which got me to stop working on the bsp viewer. And after I got my free time back my interest in this project had faded quite a bit.
Anyway, here it is:
http://code.google.com/p/hxbsplib/
I am not going to continue working on this project for a while, but I do have a new and exciting project I'm working in which I'll be posting about sooner or later.
It now renders lightmapped textures! Try it here.
I'm rendering the textures and the lightmaps on two separate buffers, then blending them together using Multiply blend mode. Unfortunately this requires rendering all triangles twice and since the drawing calls are the main bottleneck this results in almost halved performance.
Also, since I'm not doing any gamma adjustments the map ends up being displayed quite darker than in the quake 3 engine.
Also also, some textures are missing, I replace them with a plain white textures.
This is a mayor update to the flash Quake 3 BSP viewer I've been working on.
Current features:
Whats next:
And after that?
Bsps are really nice for static scenes, but they are too expensive for dynamic data. I have a few ideas in mind which would allow me to mix traditionally sorted models with the rendering of the bsp. I might implement that in the future.
If you have tried to implement 3D stuff in flash without using some already made library out there then its likely that you are using Utils3D.projectVectors somewhere in your code. This function takes 3d vertexes packed in a single Vector<Float> and outputs them on a second Vector<Float> instance applying a projection and transformation defined by a 4x4 Matrix
class Projector
{
public var m : Matrix4A;
public var focusDistance : Float;
public function new()
{
focusDistance = 1000;
}
public inline function projectVecList(
src : flash.Vector < Float > ,
dstVerts : flash.Vector < Float > ) : Void
{
var sindex = 0;
var dindex = 0;
var n = src.length;
while ( sindex < n ) {
var srcx = src[sindex++];
var srcy = src[sindex++];
var srcz = src[sindex++];
var zInv = focusDistance /
(srcx*m.m13 + srcy*m.m23 + srcz*m.m33 + m.m43);
dstVerts[dindex++] =
(srcx*m.m11 + srcy*m.m21 + srcz*m.m31 + m.m41) * zInv;
dstVerts[dindex++] =
(srcx*m.m12 + srcy*m.m22 + srcz*m.m32 + m.m42) * zInv;
}
}
}
So granted, this isn't exactly what Utils3D projection function is doing.
Utils3D.projection uses the Flash 10 Matrix3D class, which is a full 4x4 matrix ( without the constraint of being affine ). This makes it slower but also gives it a bit of extra power, since it can express projection information inside. I'm not completely in touch with the mathemagics of homogenous coordinates, but I think there are some other useful tricks in there that might make 4x4 matrices worth it in some cases.
What my projector class is doing is first transforming the vertexes using its matrix, and then divide the resulting x and y coords by the resulting z multiplied by focusDistance.
I timed how long it takes to project a vector filled with 100k vertexes with both Utils3D.projectVectors and how long it takes using the Projector class:
Utils3D.projectVectors: 1031ms
Projector.projectVecList: 755ms
Projector is faster than the native function! You might say that this shows nothing since it is not doing exactly the same stuff as Utils3D, but the point is that the same projection algorithm implemented in C/C++ should beat my projector by far.
Also, as Andre Michelle has pointed out in this blog entry, the Utils3D.projectVector api could use a few changes. If the api isnt really faster than writing it yourself then that means that there's no reason to wait for adobe to implement such changes.
Anyway, I never really liked having the vertices packed in a Float vector like required by the Utils3D.projectVectors function. Since I was going to be using my own projection now, I decided to see how performance would be affected if I used Vector<Vec3D> instead of Vector<Float> ( packed vertexes ) as the source vertexes of the projection.
Utils3D.projectVectors: 1031ms
Projector.projectVecList Vector<Float>: 755ms
New time is:
Projector.projectVecList Vector<vec3f>: 631ms
From now own I'll manually project the vertices, and I'll do it by receiving a Vector of Vertices and not a Vector of Floats with vertices packed in them.
Update:
Made some tests using HaXes flash.Memory api. I pack source vertexes in a ByteArray in a similar way to how they are packed in the Vector<Float> version.
I tested storing the vertex components as Double (8 bytes) and as Float ( 4 Bytes ). The result with the Double storage was a bit faster than the Vector<Float> implementation but slower than the Vector<Vec3D> one.
Storing the components as Float turned out to be faster than any of the other methods, although the difference between it and the Vector<Vec3D> was very small and a lot of precision is lost by this conversion.
Utils3D.projectVectors: 1071
Projector Vector<Float>: 766
Projector Vector<Vec3D>: 642
ByteArray Double: 733
ByteArray Float: 599
I think I'll stay with the Vector<Vec3D> implementation for now, since I'm not very keen on sacrificing numeric precision or usability for such a small increase in performance.
Inspired by Alternativa3Ds great performance, I am writing this quake 3 bsp loader and viewer in HaXe. And I'm pretty happy with the results so far:
I might release the source code later after some polishing and optimizations.
I have run some test about haXe iterators. Iterators provide a very nice abstraction but their speed when used in for loops was a big disappointment.
I tested it by creating many different ways to calculate the fibonacci series
Infinite Fibonacci Iterator:
class FibIter1 {
var val : UInt;
var nextVal : UInt;
public function new() {
val = 0;
nextVal = 1;
}
public inline function hasNext() : Bool {
return true;
}
public inline function next() : UInt {
var tmpVal = val;
val = nextVal;
nextVal = tmpVal + val;
return tmpVal;
}
}
Bounded Fibonacci Iterator:
class FibIter2 {
var val : UInt;
var nextVal : UInt;
var count : UInt;
public function new( count : UInt ) {
val = 0;
nextVal = 1;
this.count = count;
}
public inline function hasNext() : Bool {
return count != 0;
}
public inline function next() : UInt {
var tmpVal = val;
val = nextVal;
nextVal += tmpVal;
count--;
return tmpVal;
}
}
Test code:package ;
import flash.Lib;
import org.flashdevelop.utils.FlashConnect;
class Main
{
inline static var Test = 5;
static function main() {
var startTime = Lib.getTimer();
var acc = 0;
for ( i in 0...99999 ) {
if ( Test == 1 ) {
// ********************************
// Test 1
// Infinite Iterator + Manual Break
// ********************************
var count : UInt = 99;
for ( a in new FibIter1() ) {
if ( count-- == 0 ) break;
acc += a;
}
}else if ( Test == 2 ) {
// ********************************
// Test 2
// Bounded iterator
// ********************************
for ( a in new FibIter2(99) ) {
acc += a;
}
}else if ( Test == 3 ) {
// ********************************
// Test 3
// Manual algorithm using while
// ********************************
var val : UInt = 0;
var nextVal : UInt = 1;
var count : UInt = 99;
while ( count-- != 0 ) {
acc += val;
var tmpVal = val;
val = nextVal;
nextVal += tmpVal;
}
}else if ( Test == 4 ) {
// ********************************
// Test 4
// Manual algorithm using for
// ********************************
var val : UInt = 0;
var nextVal : UInt = 1;
for ( i in 0...99 ) {
acc += val;
var tmpVal = val;
val = nextVal;
nextVal += tmpVal;
}
}else if ( Test == 5 ) {
// ********************************
// Test 5
// Bounded iterator using while
// ********************************
var iter = new FibIter2(99);
while ( iter.hasNext() ) {
acc += iter.next();
}
}
}
FlashConnect.trace(acc);
var endTime = Lib.getTimer();
FlashConnect.trace( "Test " + Test + ": " + (endTime - startTime) );
}
}
Results (In haXe 2.05):
Test 1: 5893ms
Test 2: 5692ms
Test 3: 125ms
Test 4: 131ms
Test 5: 136ms
Conclusions:
After being disappointed by the results of the for expression I decided to check the generated bytecode: apparently the haXe compiler wont inline iterator methods in a for loop. The test 5 shows that the iterator class can be pretty fast if it is correctly inlined.
I can't think of a good reason why the compiler shouldn't be able to inline the iterator methods, which can be a good thing, because if there is no good reason then maybe in future versions of haxe for will inline too.
When the condition of an if is constant the compiler can decide to remove the condition and body from the generated bytecode. This reduces space and (possibly) improves execution performance.
I set out to test the haXe and flex compilers, to see if any of them would apply such optimizations. To do so I used hxswfml, a tool which lets you convert swf files to xml or hx files that represent the bytecode in a very readable manner.
Flex SDK 4:
package
{
import org.flashdevelop.utils.FlashConnect;
import flash.display.Sprite;
import flash.events.Event;
public class Main extends Sprite
{
private static const a : uint = 1;
public function Main():void
{
if ( a == 0 ) {
FlashConnect.trace( "Test A" );
}
const b : uint = 1;
if ( b == 0 ) {
FlashConnect.trace( "Test B" );
}
var c : uint = 1;
if ( c == 0 ) {
FlashConnect.trace( "Test C" );
}
if ( false ) {
FlashConnect.trace( "Test D" );
}
}
}
}
The result was that only Test D was optimized away from the bytecode.
HaXe 2.05 Compiler:package ;
import flash.Lib;
import org.flashdevelop.utils.FlashConnect;
class Main
{
static inline var b = 1;
static inline var c = 0;
static function main()
{
var a = 1;
if ( a == 0 ) {
FlashConnect.trace("Test A");
}
if ( b == 0 ) {
FlashConnect.trace("Test B");
}
if ( b == c ) {
FlashConnect.trace("Test C");
}
if ( false ) {
FlashConnect.trace("Test D");
}
}
}
Tests B to D were removed, Test A remained.
Both as3 and haxe provide means for conditional compilation, however they both require you to define the preprocessor variables outside of the sourcecode. HaXe's inline variables allow configuration of the source compilation in a less powerful but less tedious way.
I was disappointed that haXe didn't optimize away all cases though.
