Informed optimisation

[Ernst Blofeld]

Just a little update,

I've implemented culling of objects and their calculations (and shadows separately) based on distance from the camera, a faster more 16 bit route for things won't cross the view plane , and I've implemented the the precalculating step that was explained in http://eab.abime.net/showthread.php?...66#post1259966 (which I wish I'd done earlier, but at least I was smart enough to design my objects to take advantage of it), and I've simplified some stuff (like, buildings and runways now can't have an arbitrary orientation).

The changes mean I can't give an fps comparision, but the code is definitely faster. It's also more complicated, as I calculate centre points before deciding if I need to calculate more, but the calculation phase is more clearly separated from the drawing phase, so pluses and minuses there.

There's still a bunch of work to do, the runway is glitching at points where I overflow, which is tomorrow's job, and I still need to add different levels of detail for the models. I'm not doing that right now because I want to optimise the drawing while everything is at its most complex, and also because designing objects is not what I'm best at.

The calculation phase still takes longer than the blitter takes to clear the screen, so I'll keep working on it, but now I want to start also optimising the drawing phase, which is where the bulk of the time is spent.

Apart from that I still need to see if I can reduce the use of 32 bit pointers in my data structures, as suggested (I think) by Jobbo. Not sure how I'll approach that.



Attached is an approx 1 minute clip, 250 frames at average 4.25fps. 3 planes, 3 tanks and a runway with stripes and a control tower.

[roondar]

That's a nice boost in performance!

[LaBodilsen]

Originally Posted by Ernst Blofeld

That's in the plan, to make at least one more version of the plane and the tank with less detail, and only use the current ones for extreme close ups.

But, making a decent looking model with less detail is a very hard thing to do.

I feel you. I've been looking at your model, and it is really hard to reduce it. But considering the resolution of the engine (320*256), you can get away with a lot.

Attached is an image and model where I reduced it to: 45 verts, 35 faces (+3 for wings underside)

the "Pal resolution" picture, is a faked picture, where I tried to simulate the low resolution 320*256. and I don't think you can tell the difference.

Canopy is reduced from 10 faces to 4.
Upper nose and Cockpit not reduced, but moved faces around to allow for nose and upper fuselage reduction
Upper Fuselage From 4 to 2
Lower nose and Cockpit from 6 to 4

[Ernst Blofeld]

Originally Posted by LaBodilsen

I feel you. I've been looking at your model, and it is really hard to reduce it. But considering the resolution of the engine (320*256), you can get away with a lot.

Attached is an image and model where I reduced it to: 45 verts, 35 faces (+3 for wings underside)

the "Pal resolution" picture, is a faked picture, where I tried to simulate the low resolution 320*256. and I don't think you can tell the difference.

Canopy is reduced from 10 faces to 4.
Upper nose and Cockpit not reduced, but moved faces around to allow for nose and upper fuselage reduction
Upper Fuselage From 4 to 2
Lower nose and Cockpit from 6 to 4

I think you're probably right, you can't tell the difference. I'll take your changes for the model used for most normal views, keeping mine for special cases, then I'll just need something for distant views before I move to just dots or lines.

But first, I need to fix my clipping code to work with the very large numbers that my runway creates.

[LaBodilsen]

Originally Posted by Ernst Blofeld

then I'll just need something for distant views before I move to just dots or lines..

How low do you want to go for that model?

I have one with 36 verts, 26 faces +3. (attached). at that distance, you might not even need the front wing at all, and save 4 verts and 4 faces.

[Ernst Blofeld]

Originally Posted by LaBodilsen

How low do you want to go for that model?

I have one with 36 verts, 26 faces +3. (attached). at that distance, you might not even need the front wing at all, and save 4 verts and 4 faces.

Difficult to say, it's not just the vertex and face count we need to minimise, it's also the unique x, y and z component values of the vertices, while keeping the faces planar (or planar enough with the splitting planes being exact), I reckon you probably can't go much lower.

[LaBodilsen]

Originally Posted by Ernst Blofeld

Difficult to say, it's not just the vertex and face count we need to minimise, it's also the unique x, y and z component values of the vertices, while keeping the faces planar (or planar enough with the splitting planes being exact), I reckon you probably can't go much lower.

For extreme distance, I tried going way to low. and I'm surprised it does not look all to bad at 320x256 (see extreme distance.png) 19 verts, 15 faces.

of course up close it looks very bad.

[Ernst Blofeld]

I am currently stuck with my polygon clipping code and handling very large polygons, such as my runway.

The runway starts as a small object as it's scaled down by 1024, so 1 is approx 1 metre, but as I get to the end of the calculation phase the numbers become 1 is 1 pixel so approx 1 milimetre. I don't currently see another way to do this.

When I get to my clipping stage, if you're looking at the runway the wrong way, it's possible to get polygon edges that cross the screen and which are very long. The standard calculation to clip those edges involves a multiplication which often overflows a long. and glitches out.

What to do?

I've tried a binary search type approach, bisecting the line until the intersection is found, which initially appeared to work, but at each bisection a rounding error is introduced and the result ends up out by several pixels.

I've tried swapping the start and end pixels over, so working out the distances from the other end. This sometimes works, but introduces inconsistencies as the direction of the rounding changes too, and I worry I might lose precision.

I've looked at how I can right shift the divisor and divisee parts of the equation, but I'm not sure quite how to work out how many bits to shift each part, and will I introduce more errors.

So, yeah, I'm a bit stuck.

[roondar]

You could try to have the runway be two or three objects rather than a single object perhaps? I believe quite a few older 3D games did this with larger objects.

[Ernst Blofeld]

Originally Posted by roondar

You could try to have the runway be two or three objects rather than a single object perhaps? I believe quite a few older 3D games did this with larger objects.

Or even just divide the long edges into multiple shorter ones. I'm not sure how to work out the maximum size of object or edge that I'd be safely allowed, but it could add up to a lot of extra vertices that have to be transformed.

[Ernst Blofeld]

Originally Posted by Ernst Blofeld

Or even just divide the long edges into multiple shorter ones. I'm not sure how to work out the maximum size of object or edge that I'd be safely allowed, but it could add up to a lot of extra vertices that have to be transformed.

Given a start point s = (s_x, s_y) and an end point p = (p_x, p_y), clipping against the right hand edge of c_r = 319, giving an intersection at r = (c_r, r_y):

r_y = s_y + (p_y - s_y) * (c_r - s_x) / (p_x - s_x)

(so (p_x - s_x) and (p_y - s_y) are the x and y deltas, and (c_r - s_x) is the x distance from the start point to the clipping edge)

And widening the question a bit more to not just avoiding overflow, but also fitting within efficient 68k divs operations...

we need:

- basically every single one of these numbers to fit into 16 bits

I have little control over s_x. If each chunk of runway was really its own object then I could make sure I've culled the bits where s_x might be too big, but I'm not in love with that idea - I'd need to divide a runway into around 50 chunks.

[Ernst Blofeld]

In the end I've fixed this by introducing some 64-bit maths. Works out around the same speed, or a tiny bit faster, as it's only used when very big things get very close to the camera, so only the runway at the moment, and it all happens inside one piece of assembly - three 32-bit numbers enter, one 32-bit number leaves.

Next problem?

EDIT:

Next problem is redesigning the data structures for my models to replace the pointers with indices for efficiency. It would be a mistake to not do this before I add all the lower detail models.

[roondar]

Cool! Very nice it's also not any slower

[Ernst Blofeld]

A: Other clipping algorithms:

• I don't spend much time in clipping but if I could at least choose an optimal order to clip edges against the clip rect I could reduce the rounding errors there (I'm working on this now, as I have a bounding box for the object I'm clipping, but it's not perfect).
• Or, if I could combine it with the polygon raterising I could limit the clipping to only inbound edges.
• If an edge is shared between two faces I end up clipping it twice (two multiplications and a big division).

B: Silhouette Edges:

• Making shadows more efficiently?
• Making cross sections for a physics engine (things like air resistance)?
• Special effects for heads up displays?
• Faces are related to their neighbours by their shared edges.

C: A + B => Do I need a rasterisation routine that can cope with complex polygons?

• Just chuck a bunch of unordered edges and have it rasterise and draw it?
• Or calculate its area for a cross section?

[Ernst Blofeld]

Also, how would I pack something like this into something that doesn't use pointers and the address of "&" everywhere? My guess is that I can't do it in C?

static Face lowerFuselageLeftFrontFace = { .name = "Lower Fuselage, Left Front Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 3, .vertices = { 25, 44, 46 } };
static Face lowerFuselageLeftMiddleFace = { .name = "Lower Fuselage, Left Middle Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 3, .vertices = { 4, 25, 46 } };
static Face lowerFuselageLeftRearFace = { .name = "Lower Fuselage, Left Rear Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 3, .vertices = { 4, 46, 5 } };
static Face lowerFuselageBottomFace = { .name = "Lower Fuselage, Bottom Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_COLOUR, .numVertices = 4, .vertices = { 5, 46, 48, 8 } };
static Face lowerFuselageRightFrontFace = { .name = "Lower Fuselage, Right Front Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 3, .vertices = { 28, 48, 49 } };
static Face lowerFuselageRightMiddleFace = { .name = "Lower Fuselage, Right Middle Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 3, .vertices = { 9, 48, 28 } };
static Face lowerFuselageRightRearFace = { .name = "Lower Fuselage, Right Rear Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 3, .vertices = { 8, 48, 9 } };

static Region lowerFuselageSection =  {
    .type = REGION,
    .name = "Lower Fuselage Section",
    .faces = {
        &lowerFuselageLeftFrontFace, &lowerFuselageLeftMiddleFace, &lowerFuselageLeftRearFace,
        &lowerFuselageBottomFace,
        &lowerFuselageRightFrontFace, &lowerFuselageRightMiddleFace, &lowerFuselageRightRearFace,
        NULL
    }
};

static Face cockpitLowerLeftFace = { .name = "Cockpit, Lower Left Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 4, .vertices = { 23, 50, 45, 44 } };
static Face cockpitLowerFace = { .name = "Cockpit, Lower Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_COLOUR, .numVertices = 4, .vertices = { 45, 50, 51, 47 } };
static Face cockpitLowerRightFace = { .name = "Cockpit, Lower Right Face", .colour = EUROFIGHTER_FUSELAGE_LOWER_SIDES_COLOUR, .numVertices = 4, .vertices = { 24, 49, 47, 51 } };
static Face noseLowerLeftFace = { .name = "Nose, Lower Left Face", .colour = EUROFIGHTER_NOSE_LOWER_COLOUR, .numVertices = 3, .vertices = { 22, 50, 23 } };
static Face noseLowerFace = { .name = "Nose, Lower Face", .colour = EUROFIGHTER_NOSE_LOWER_COLOUR, .numVertices = 3, .vertices = { 22, 51, 50 } };
static Face noseLowerRightFace = { .name = "Nose, Lower Right Face", .colour = EUROFIGHTER_NOSE_LOWER_COLOUR, .numVertices = 3, .vertices = { 22, 24, 51 } };

static Region lowerNoseAndCockpitSection = {
    .type = REGION,
    .name = "Lower Nose and Cockpit Section",
    .faces = {
        &cockpitLowerLeftFace, &cockpitLowerFace, &cockpitLowerRightFace,
        &noseLowerLeftFace, &noseLowerFace, &noseLowerRightFace,
        NULL
    }
};

static Face Canopy_Base = { .name = "(invisible) Canopy Base Face", .colour = INVISIBLE_COLOUR, .numVertices = 3, .vertices = { 16, 20, 19 } };
static Face Bulkhead = { .name = "(invisible) Bulkhead Face", .colour = INVISIBLE_COLOUR, .numVertices = 3, .vertices = { 28, 25, 21 } };
static Face XY_Plane = { .name = "(invisible) XY Plane Face", .colour = INVISIBLE_COLOUR, .numVertices = 3, .vertices = { 33, 41, 42 } };

static Partition inFrontOfBulkheadSection = {
    .name = "In Front of Bulkhead Section",
    .splittingPlane = &Canopy_Base,
    .above = (Section *) &canopySection,
    .below = (Section *) &upperNoseAndCockpitSection
};

[hooverphonique]

Originally Posted by Ernst Blofeld

Also, how would I pack something like this into something that doesn't use pointers and the address of "&" everywhere? My guess is that I can't do it in C?

Are you talking about ensuring correctness, maintainability, or performance when you mention you would like to get rid of pointers?

[Ernst Blofeld]

Originally Posted by hooverphonique

Are you talking about ensuring correctness, maintainability, or performance when you mention you would like to get rid of pointers?

Performance, making things relative to a central point with word offsets or indexes rather than 32 bit pointers linking structures. I haven't fully thought it through and it may be the wrong tree to bark at.

For instance, if I drop the name strings, which are just debugging info, all the face data is just words, so I could just pack it all together, but I would need to know where each face starts to create an index into the array, because there's no way I can count them by hand.

[Ernst Blofeld]

Originally Posted by Ernst Blofeld

For instance, if I drop the name strings, which are just debugging info, all the face data is just words, so I could just pack it all together, but I would need to know where each face starts to create an index into the array, because there's no way I can count them by hand.

This is the best idea I've come up with so far. It's incredibly tedious and still error prone, so I'm still looking for better ideas before I commit to it.

I'll have an array of words for my faces:

static WORD faceData [] = {

#define LEFT_EXHAUST_FACE 0
#define _LEFT_EXHAUST_FACE_NUM_VERTICES 6
#define _AFTER_LEFT_EXHAUST_FACE LEFT_EXHAUST_FACE + 2 * (2 + _LEFT_EXHAUST_FACE_NUM_VERTICES)
    EXHAUST_COLOUR, _LEFT_EXHAUST_FACE_NUM_VERTICES, 1, 2, 3, 4, 5, 6,

#define RIGHT_EXHAUST_FACE _AFTER_LEFT_EXHAUST_FACE
#define _RIGHT_EXHAUST_FACE_NUM_VERTICES 6
#define _AFTER_RIGHT_EXHAUST_FACE RIGHT_EXHAUST_FACE + 2 * (2 + _RIGHT_EXHAUST_FACE_NUM_VERTICES)
    EXHAUST_COLOUR, _RIGHT_EXHAUST_FACE_NUM_VERTICES, 1, 7, 8, 9, 10, 11,

#define CANOPY_FRONT_LEFT_LOWER_FACE _AFTER_RIGHT_EXHAUST_FACE
#define _CANOPY_FRONT_LEFT_LOWER_FACE_NUM_VERTICES 3
#define _AFTER_CANOPY_FRONT_LEFT_LOWER_FACE CANOPY_FRONT_LEFT_LOWER_FACE + 2 * (2 + _CANOPY_FRONT_LEFT_LOWER_FACE_NUM_VERTICES)
    CANOPY_COLOUR, _CANOPY_FRONT_LEFT_LOWER_FACE_NUM_VERTICES, 12, 13, 14

// ...

};

And I'll have another array of words for my BSP tree:

static WORD sectionData [] = {

#define EXHAUST_SECTION 0
#define _EXHAUST_SECTION_NUM_FACES 2
#define _AFTER_EXHAUST_SECTION EXHAUST_SECTION + 2 * (2 + _EXHAUST_SECTION_NUM_FACES)
    REGION,
    LEFT_EXHAUST_FACE, RIGHT_EXHAUST_FACE,
    END,

#define CANOPY_SECTION AFTER_EXHAUST_SECTION
#define _CANOPY_SECTION_NUM_FACES 10
#define _AFTER_CANOPY_SECTION CANOPY_SECTION +  2 * (2 + _CANOPY_SECTION_NUM_FACES)
    REGION,
    CANOPY_FRONT_LEFT_LOWER_FACE, CANOPY_FRONT_LEFT_UPPER_FACE, CANOPY_FRONT_FACE, CANOPY_FRONT_RIGHT_UPPER_FACE, CANOPY_FRONT_RIGHT_LOWER_FACE,
    CANOPY_REAR_LEFT_LOWER_FACE, CANOPY_REAR_LEFT_UPPER_FACE, CANOPY_REAR_FACE CANOPY_REAR_RIGHT_UPPER_FACE, CANOPY_REAR_RIGHT_LOWER_FACE,
    END,

#define IN_FRONT_OF_BULKHEAD_SECTION _AFTER_CANOPY_SECTION
#define _AFTER_IN_FRONT_OF_BULKHEAD_SECTION _IN_FRONT_OF_BULKHEAD_SECTION + SIZE_OF_PARTITION
    PARTITION,
    CANOPY_BASE_PLANE,
    CANOPY_SECTION, NONE, NONE, UPPER_NOSE_AND_COCKPIT_SECTION,

#define BEHIND_BULKHEAD_SECTION _AFTER_IN_FRONT_OF_BULKHEAD_SECTION
#define _AFTER_BEHIND_BULKHEAD_SECTION BEHIND_BULKHEAD_SECTION + SIZE_OF_PARTITION
    PARTITION,
    UPPER_FUSELAGE_TOP_FACE,
    TAIL_SECTION, UPPER_FUSELAGE_TOP_SECTION, NONE, UPPER_FUSELAGE_MAIN_SECTION

// ...

};

I've used #defines to do my counting for me, but it still seems like to much work and repetition. If it's possible to make it smarter with macros, I don't know how.

[DanScott]

Why do you need all those defines ?

Surely, you just need raw data to define vertices, edges + faces etc...

Imagine you have 50 different objects, and you have to make changes to every object etc..

[Ernst Blofeld]

Originally Posted by DanScott

Why do you need all those defines ?

Because I'm not very good at counting. I need to know where in the faceData array each face starts, and where in the sectionData array each section starts.