Informed optimisation

[Ernst Blofeld]

Originally Posted by LaBodilsen

Well it turns out someone already made an json exporter for blender some 8 years ago, but it does not work with the current version. So I forked the github page, and have updated it to work with the latest version of blender, and it does look like a better starting point, than the .ply exporter I was using before, so I am currently moving my progress over to this code tree.
Github page here: https://github.com/LaBodilsen/Blender-JSON-Exporter

Do you use a template for your import script, and could you share that?



I doubt that I'm better at Python. This is my first project in Python, but I have some experience from Godot's GDscript, which is close to python. Also my first blender scripting, but I was wanting to get into that anyway, so might as well start here.

I can share the importer script, just know that it's rough, and just reads a json file and dumps a bunch of c code to stdout which then needs to be carefully pasted into an actual .c file that includes other things.

The importer script:

import json

colour_numbers = { }

colour_numbers['COLOUR_BLACK'] = 0
colour_numbers['COLOUR_LIGHT_GREY'] = 1
colour_numbers['COLOUR_MEDIUM_DARK_GREY'] = 2
colour_numbers['COLOUR_DULL_RED'] = 3
colour_numbers['COLOUR_DARK_OCEAN_BLUE'] = 4
colour_numbers['COLOUR_DARK_WOODY_GREEN'] = 5
colour_numbers['COLOUR_DARK_GRASSY_GREEN'] = 6
colour_numbers['COLOUR_BRIGHT_YELLOW'] = 7
colour_numbers['COLOUR_DARK_GREY'] = 8
colour_numbers['COLOUR_WHITE'] = 9
colour_numbers['COLOUR_MEDIUM_GREY'] = 10
colour_numbers['COLOUR_RED'] = 11
colour_numbers['COLOUR_OCEAN_BLUE'] = 12
colour_numbers['COLOUR_WOODY_GREEN'] = 13
colour_numbers['COLOUR_GRASSY_GREEN'] = 14
colour_numbers['COLOUR_SKY_BLUE'] = 15

vertex_components = [ { }, { }, { } ]
vertices = []

bsp_tree_output = []

shadow_faces = []

def add_to_bsp_output(value):
    global bsp_tree_output

    bsp_tree_output.append(value)

def do_bsp_output():
    global bsp_tree_output

    print('static UWORD bspTree [] = {')
    i = 0
    for value in bsp_tree_output:
        if i == 0:
            print('    ', end = '')
        print(value, end = '')
        if i != 15:
            print(', ', end = '')
            i += 1
        else:
            print(',')
            i = 0
    print()
    print('};')

def process_vertices(input_vertices):
    global vertex_components

    for input_vertex in input_vertices:
        vertex = []
        for i in range(0, 3):
            c = input_vertex[i]

            if c == 0:
                vertex.append(-1)
                continue

            is_negative = c < 0
            if is_negative:
                c = -c

            if c in vertex_components[i]:
                j = vertex_components[i][c]
            else:
                j = len(vertex_components[i])
                vertex_components[i][c] = j
            
            j *= 12

            if (is_negative):
                j += 0x8000

            vertex.append(j)
                
        vertices.append(vertex)

def output_vertex_components():
    global vertex_components

    for t, i in {'X': 0, 'Y': 1, 'Z': 2}.items():
        print('static UWORD vertex' + t + 'Components [] = {')
        for c, j in vertex_components[i].items():
            print('    ' + str(c) + ',')
        print('};')
        print()

def output_vertices():
    global vertices

    print('static Vertex3D vertices [] = {')
    for vertex in vertices:
        print('    { ' + str(vertex[0]) + ', ' + str(vertex[1]) + ', ' + str(vertex[2]) + ' },')
    print('};')
    print()

def process_face(face):
    local_colour_name = face.get('colour')
    if local_colour_name:
        colour_name = colours[local_colour_name]
        if colour_name:
            colour_number = colour_numbers[colour_name]
    else:
        colour_number = 0

    num_vertices = len(face['vertices'])
    size_in_bytes = 2 * (2 + num_vertices)

    face['colour_number'] = colour_number
    face['num_vertices'] = num_vertices
    face['size_in_bytes'] = size_in_bytes

def output_face(face):
    add_to_bsp_output(face['colour_number'])
    add_to_bsp_output(face['num_vertices'])
    for vertex in face['vertices']:
        add_to_bsp_output(6 * vertex)

def output_splitting_plane_face(splitting_plane):
    add_to_bsp_output(splitting_plane['num_vertices'])
    for vertex in splitting_plane['vertices']:
        add_to_bsp_output(6 * vertex)

def process_region(region):
    num_faces = len(region['faces'])
    region['num_faces'] = num_faces
    size_in_bytes = 2
    for face_name in region['faces']:
        face = faces[face_name]
        size_in_bytes += face['size_in_bytes']
    region['size_in_bytes'] = size_in_bytes

def output_region(region):
    add_to_bsp_output(region['num_faces'])
    for face_name in region['faces']:
        face = faces[face_name]
        output_face(face)

def process_partition(partition):
    splitting_plane_face_name = partition.get('splittingPlane')
    splitting_plane_face = faces[splitting_plane_face_name]

    size_in_bytes = 2 * 5 + splitting_plane_face['size_in_bytes'] - 2

    above = partition.get('above')
    if above:
        partition['above_offset'] = size_in_bytes
        process_section(above)
        size_in_bytes += above['size_in_bytes']
    else:
        partition['above_offset'] = 0
    
    on_from_above = partition.get('onFromAbove')
    if on_from_above:
        partition['on_from_above_offset'] = size_in_bytes
        process_region(on_from_above)
        size_in_bytes += on_from_above['size_in_bytes']
    else:
        partition['on_from_above_offset'] = 0
    
    on_from_below = partition.get('onFromBelow')
    if on_from_below:
        partition['on_from_below_offset'] = size_in_bytes
        process_region(on_from_below)
        size_in_bytes += on_from_below['size_in_bytes']
    else:
        partition['on_from_below_offset'] = 0

    below = partition.get('below')
    if below:
        partition['below_offset'] = size_in_bytes
        process_section(below)
        size_in_bytes += below['size_in_bytes']
    else:
        partition['below_offset'] = 0
    
    partition['size_in_bytes'] = size_in_bytes

def output_partition(partition):
    add_to_bsp_output(0)
    add_to_bsp_output(partition['above_offset'])
    add_to_bsp_output(partition['on_from_above_offset'])
    add_to_bsp_output(partition['on_from_below_offset'])
    add_to_bsp_output(partition['below_offset'])

    splitting_plane_face_name = partition.get('splittingPlane')
    splitting_plane_face = faces[splitting_plane_face_name]

    output_splitting_plane_face(splitting_plane_face)

    above = partition.get('above')
    if above:
        output_section(above)
    
    on_from_above = partition.get('onFromAbove')
    if on_from_above:
        output_region(on_from_above)
    
    on_from_below = partition.get('onFromBelow')
    if on_from_below:
        output_region(on_from_below)

    below = partition.get('below')
    if below:
        output_section(below)

def process_section(section):
    if 'faces' in section:
        return process_region(section)
    else:
        return process_partition(section)

def output_section(section):
    if 'faces' in section:
        return output_region(section)
    else:
        return output_partition(section)

def process_bsp_tree(bsp_tree):
    process_section(bsp_tree)

def output_bsp_tree(bsp_tree):
    output_section(bsp_tree)
    do_bsp_output()

def output_shadow_faces():
    global shadow_faces

    print('')
    print('static UWORD shadowFaces [] = {')
    print('    ' + str(len(shadow_faces)) + ', ')
    for shadow_face in shadow_faces:
        vertices = shadow_face['vertices']
        print('    ' + str(len(vertices)) + ', ', end = '')
        for vertex in vertices:
            print(str(6 * vertex) + ', ', end = '')
        print('')
    print('};')
    print('')

with open('game-entities\\test.json') as json_file:
    model = json.load(json_file)

    global colours
    colours = model['colours']

    process_vertices(model['vertices'])
    output_vertex_components()

    output_vertices()

    global faces
    faces = model['faces']
    for name, face in faces.items():
        process_face(face)

    shadow_face_names = model['shadowFaces']
    for shadow_face_name in shadow_face_names:
        shadow_face = faces[shadow_face_name]
        shadow_faces.append(shadow_face)

    bsp_tree = model['bspTree']
    process_bsp_tree(bsp_tree)
    output_bsp_tree(bsp_tree)

    output_shadow_faces()

An example of its output:

static UWORD vertexXComponents [] = {
    5250,
    5500,
    5000,
    7000,
    4750,
    2250,
    9000,
    5515,
    6000,
    2514,
    4000,
    4375,
};

static UWORD vertexYComponents [] = {
    289,
    866,
    1155,
    447,
    550,
    577,
    1200,
    775,
    2000,
    5500,
    872,
    633,
};

static UWORD vertexZComponents [] = {
    500,
    737,
    1300,
    1600,
    1000,
    529,
    3500,
    711,
};

static Vertex3D vertices [] = {
    { -1, -1, -1 },
    { 32768, -1, -1 },
    { 32780, 32768, 32768 },
    { 32780, 32780, 32768 },
    { 32768, 32792, -1 },
    { 32792, 32780, 0 },
    { 32792, 32768, 0 },
    { 32792, 0, 0 },
    { 32792, 12, 0 },
    { 32768, 24, -1 },
    { 32780, 12, 32768 },
    { 32780, 0, 32768 },
    { 36, 32768, 32768 },
    { 48, 32804, 32780 },
    { 48, 32816, 32792 },
    { 48, -1, 32804 },
    { 36, 0, 32768 },
    { 48, 48, 32792 },
    { 36, 0, 32768 },
    { 48, 36, 32780 },
    { 60, 32768, 32816 },
    { 60, 0, 32816 },
    { 72, -1, -1 },
    { 36, 32828, -1 },
    { 36, 60, -1 },
    { 60, 32840, -1 },
    { 60, 32852, 32780 },
    { 60, 84, 32780 },
    { 60, 72, -1 },
    { 32852, -1, 32828 },
    { 32804, -1, 32840 },
    { 32864, -1, 32840 },
    { 32876, -1, 32852 },
    { 36, -1, -1 },
    { 24, 32864, -1 },
    { 48, 32864, -1 },
    { 12, -1, -1 },
    { 48, 96, -1 },
    { 24, 96, -1 },
    { 48, -1, -1 },
    { 32828, 32876, -1 },
    { 32888, 32876, -1 },
    { 32888, 108, -1 },
    { 32828, 108, -1 },
    { 48, 32888, -1 },
    { 132, 32900, 0 },
    { 120, 32840, 48 },
    { 132, 132, 0 },
    { 120, 72, 48 },
    { 48, 120, -1 },
    { 36, 32768, 0 },
    { 36, 0, 0 },
};

static UWORD bspTree [] = {
    0, 24, 58, 0, 76, 6, 18, 24, 30, 48, 54, 60, 2, 3, 6, 6,
    12, 18, 24, 30, 36, 3, 6, 6, 42, 48, 54, 60, 66, 1, 8, 6,
    18, 24, 30, 48, 54, 60, 0, 18, 342, 382, 422, 3, 198, 246, 252, 0,
    18, 0, 0, 218, 3, 168, 150, 126, 0, 18, 0, 0, 120, 3, 96, 120,
    114, 10, 0, 3, 72, 78, 84, 0, 3, 72, 84, 90, 0, 3, 72, 90,
    96, 0, 3, 90, 102, 108, 0, 3, 102, 114, 108, 0, 3, 78, 120, 84,
    0, 3, 84, 120, 90, 0, 3, 90, 120, 126, 0, 3, 90, 126, 102, 0,
    3, 102, 126, 114, 7, 1, 3, 72, 132, 138, 1, 3, 72, 96, 132, 1,
    3, 108, 144, 132, 13, 5, 72, 138, 150, 156, 78, 5, 3, 78, 156, 120,
    5, 3, 114, 126, 162, 13, 5, 108, 114, 162, 168, 144, 0, 20, 46, 0,
    60, 4, 18, 60, 126, 120, 2, 13, 4, 174, 180, 186, 192, 13, 4, 174,
    192, 186, 180, 1, 5, 4, 18, 60, 126, 120, 4, 13, 4, 18, 156, 150,
    24, 5, 3, 18, 120, 156, 5, 3, 60, 162, 126, 13, 4, 54, 168, 162,
    60, 3, 5, 4, 198, 204, 210, 216, 5, 4, 198, 216, 222, 228, 5, 5,
    234, 240, 246, 252, 258, 3, 1, 4, 198, 216, 210, 204, 1, 4, 228, 222,
    216, 198, 1, 5, 234, 258, 252, 246, 240, 0, 20, 88, 0, 122, 4, 270,
    282, 288, 276, 6, 10, 4, 138, 300, 270, 264, 1, 4, 270, 300, 306, 282,
    10, 4, 144, 294, 282, 306, 1, 3, 132, 300, 138, 1, 3, 132, 306, 300,
    1, 3, 132, 144, 306, 3, 8, 3, 264, 270, 276, 8, 4, 270, 282, 288,
    276, 8, 3, 282, 294, 288, 7, 10, 3, 150, 264, 276, 10, 3, 24, 150,
    276, 10, 3, 24, 276, 30, 1, 4, 30, 276, 288, 48, 10, 3, 168, 288,
    294, 10, 3, 54, 288, 168, 10, 3, 48, 288, 54, 
};

static UWORD shadowFaces [] = {
    47, 
    3, 72, 78, 84, 
    3, 72, 84, 90, 
    3, 72, 90, 96, 
    3, 90, 102, 108, 
    3, 102, 114, 108, 
    3, 78, 120, 84, 
    3, 84, 120, 90, 
    3, 90, 120, 126, 
    3, 90, 126, 102, 
    3, 102, 126, 114, 
    3, 72, 132, 138, 
    3, 72, 96, 132, 
    3, 108, 144, 132, 
    5, 72, 138, 150, 156, 78, 
    3, 78, 156, 120, 
    3, 114, 126, 162, 
    5, 108, 114, 162, 168, 144, 
    4, 174, 180, 186, 192, 
    4, 174, 192, 186, 180, 
    4, 18, 60, 126, 120, 
    4, 18, 156, 150, 24, 
    3, 18, 120, 156, 
    3, 60, 162, 126, 
    4, 54, 168, 162, 60, 
    6, 18, 24, 30, 48, 54, 60, 
    4, 198, 204, 210, 216, 
    4, 198, 216, 222, 228, 
    5, 234, 240, 246, 252, 258, 
    4, 198, 216, 210, 204, 
    4, 228, 222, 216, 198, 
    5, 234, 258, 252, 246, 240, 
    3, 264, 270, 276, 
    4, 270, 282, 288, 276, 
    3, 282, 294, 288, 
    3, 150, 264, 276, 
    3, 24, 150, 276, 
    3, 24, 276, 30, 
    4, 30, 276, 288, 48, 
    3, 168, 288, 294, 
    3, 54, 288, 168, 
    3, 48, 288, 54, 
    4, 138, 300, 270, 264, 
    4, 270, 300, 306, 282, 
    4, 144, 294, 282, 306, 
    3, 132, 300, 138, 
    3, 132, 306, 300, 
    3, 132, 144, 306, 
};

And after this is pasted into a .c file:

#include "../3d-engine/model.h"

<here>

Model3D eurofighterModel3D = {
    .numVertexComponents = { 12, 12, 8 },
    .vertexComponents = { vertexXComponents, vertexYComponents, vertexZComponents },
    .numVertices = 52,
    .vertices = vertices,
    .bspTreeRoot = (Section *) bspTree,
    .shadowFaces = (Face *) shadowFaces
};

I'm not sure why I never finished it to not need the copy paste step.

[Photon]

From your original post, profiling is a good step. Measure your resource hogs, and invent other ways of achieving the same thing. You have a bigger screen than pretty much all but 1 vector game on Amiga; polygons won't be tiny and you should measure if the Blitter beats the CPU on the target platform.

If you struggle to perform as in other games even though you have fewer polygons, it may be that C is your biggest resource hog. You can mitigate it, but only up to a point, and not without virtually turning into long lists of instructions forcing the compiler to produce the Assembler instructions that are the fastest you can manage - at some point C isn't worth it or basically becomes Assembler or you inline Assembler.

Originally Posted by Ernst Blofeld

The ground is done with the blitter, just one bitplane. The rest are done with the CPU, the asphalt of the runway and the shadows are also just one bitplane, as is the sun although that's a precalculated circle.

Objects that don't rotate around any axis can be sprites or bobs, especially if they are at a fixed priority behind everything else.

For LOD, you could start off with 1 object=a "particle": 1 disc of a certain color (Elite, Frontier), looking up details only when needed. Objects outside the frustum should be eliminated with an aggressive algorithm.

If you did this, the Sun could well be an object with LOD 0 and thus rendered as a disc, which requires efficient disc rendering (if you draw a circle and fill it, all gain is lost).

Originally Posted by Ernst Blofeld

To draw the polygons I go round the edges using Bresenham to populate an array of start and end points (anti clockwise so down is a start point and up is an end). I then go through this array, having remembered the y min and max to start and stop at, drawing horizontal lines one long word at a time. That last bit came from elsewhere, but I changed it to write longs rather than words.

Unify polygon vertex direction and normals on import - this makes it a simple list to draw in order, and you won't have to calculate normals from projected polygon corners, losing accuracy.

If you haven't, consider using a substructure in between vertices and polygons: edges. Embellish the edge structure, because it allows many things, not least an Eliminator function which can hide faces and the edges that belong to them, combine edges, and many other things before actual drawing takes place. It's very powerful, and can be used e.g. to eliminate joint edges to get only a shadow outline remaining that is quick to render.

In all this optimization, it's important to keep it a general-purpose 3D engine - too much special-casing, and it will be (needlessly) limited and may even render incorrectly, you just haven't been to that part of the world and looked that way.

[Ernst Blofeld]

Originally Posted by Photon

From your original post, profiling is a good step. Measure your resource hogs, and invent other ways of achieving the same thing. You have a bigger screen than pretty much all but 1 vector game on Amiga; polygons won't be tiny and you should measure if the Blitter beats the CPU on the target platform.

This is something that I seem to have forgotten. I'm already using different code depending on the distance of objects from the camera, I can test using the blitter for very close up objects, which will have the biggest polygons.

Originally Posted by Photon

If you struggle to perform as in other games even though you have fewer polygons, it may be that C is your biggest resource hog. You can mitigate it, but only up to a point, and not without virtually turning into long lists of instructions forcing the compiler to produce the Assembler instructions that are the fastest you can manage - at some point C isn't worth it or basically becomes Assembler or you inline Assembler.


Objects that don't rotate around any axis can be sprites or bobs, especially if they are at a fixed priority behind everything else.

For LOD, you could start off with 1 object=a "particle": 1 disc of a certain color (Elite, Frontier), looking up details only when needed. Objects outside the frustum should be eliminated with an aggressive algorithm.

Culling of objects outside the frustum and beyond the draw distance is already in there.

LOD is coming, with much of the code already done.

Originally Posted by Photon

If you did this, the Sun could well be an object with LOD 0 and thus rendered as a disc, which requires efficient disc rendering (if you draw a circle and fill it, all gain is lost).

The sun is already precalculated as a set of 21 raster start and end points.

Originally Posted by Photon

Unify polygon vertex direction and normals on import - this makes it a simple list to draw in order, and you won't have to calculate normals from projected polygon corners, losing accuracy.

I'm interested in this, particularly as I can see the accuracy problems occuring in my current visibility test using projected vertices. Could you go into more detail? I'm fine with the concept of pre-calculated normals, but, as far as I understand it, they need to go through the perspective transform, so adding a bunch more divides?

Originally Posted by Photon

If you haven't, consider using a substructure in between vertices and polygons: edges. Embellish the edge structure, because it allows many things, not least an Eliminator function which can hide faces and the edges that belong to them, combine edges, and many other things before actual drawing takes place. It's very powerful, and can be used e.g. to eliminate joint edges to get only a shadow outline remaining that is quick to render.

I have read up on a few algorithms that use edges, particularly for shadow casting and silhouettes, and have thought a lot about them, I know I could clip an edge only once if I had the concept of edges.

But then I get stuck. Beyond the fact that an edge refers to two vertices, which have an order (a head and tail), and a polygon then becomes just a bunch of edges, what else would I need? I guess I'd need to sort out the normals and new visibility test first, as I'll no longer be able to do anything that involves walking around the vertices again. And can I do this without it becoming a mess of pointers?

Originally Posted by Photon

In all this optimization, it's important to keep it a general-purpose 3D engine - too much special-casing, and it will be (needlessly) limited and may even render incorrectly, you just haven't been to that part of the world and looked that way.

[LaBodilsen]

Originally Posted by Ernst Blofeld

I can share the importer script, just know that it's rough, and just reads a json file and dumps a bunch of c code to stdout which then needs to be carefully pasted into an actual .c file that includes other things.

I'm not sure why I never finished it to not need the copy paste step.

The new blender json exporter, now outputs this for the typhoon in blender (with materials added for each face).

{
    "colours" : {
        "COLOUR_WOODY_GREEN" : [4, 5, 2],
        "COLOUR_DARK_WOODY_GREEN" : [3, 5, 2],
        "COLOUR_LIGHT_GREY" : [7, 7, 7],
        "COLOUR_MEDIUM_GREY" : [5, 5, 5],
        "COLOUR_DARK_GREY" : [3, 3, 3],
        "COLOUR_BLACK" : [0, 0, 0],
        "COLOUR_DULL_RED" : [6, 0, 0],
        "COLOUR_SKY_BLUE" : [0, 5, 11],
        "COLOUR_WHITE" : [13, 13, 13],
        "COLOUR_OCEAN_BLUE" : [0, 6, 13],
        "COLOUR_DARK_OCEAN_BLUE" : [0, 1, 3],
        "COLOUR_GRASSY_GREEN" : [1, 6, 0],
        "COLOUR_DARK_GRASSY_GREEN" : [0, 4, 0],
        "COLOUR_BRIGHT_YELLOW" : [14, 14, 3]
    },

    "bspTreeRoot" : "EurofighterObject",

    "vertices": [
        [9000, 0, 0],
        [7000, 577, 0],
        [4375, 633, 500],
        [7000, -289, 500],
        [7000, 289, 500],
        [-5250, -1154, 0],
        [2250, -1200, 0],
        [2250, 1200, 0],
        [4750, -871, 0],
        [4000, 1200, 1000],
        [4750, 871, 0],
        [4375, -633, 500],
        [4000, -1200, 1000],
        [7000, 0, 0],
        [5000, -2000, 0],
        [5500, 0, 0],
        [-4000, -5500, 0],
        [-4000, 5500, 0],
        [-2250, 5500, 0],
        [4750, -2000, 0],
        [4750, 2000, 0],
        [5000, 2000, 0],
        [4750, 0, 0],
        [-2250, -5500, 0],
        [-5000, -865, 500],
        [-5000, 865, 500],
        [2250, -774, -736],
        [2250, 774, -736],
        [-5500, -865, -500],
        [2250, 289, -1000],
        [-5514, 0, -528],
        [-7000, 0, -3500],
        [-6000, 0, -3500],
        [-2513, 0, -711],
        [4750, -446, -736],
        [7000, 289, -500],
        [7000, -577, 0],
        [7000, -289, -500],
        [4750, -550, -1299],
        [4750, 0, -1600],
        [4750, 550, -1299],
        [4750, 446, -736],
        [2250, -289, -1000],
        [-5250, 0, 0],
        [-5500, -289, -500],
        [-5000, -289, 500],
        [-5000, 289, 500],
        [-5250, 1154, 0],
        [-5500, 865, -500],
        [-5500, 289, -500]
    ],

    "faces" : {
        "face0" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [36, 3, 11, 8]
        },
        "face1" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [11, 3, 4, 2]
        },
        "face2" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [1, 10, 2, 4]
        },
        "face3" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [0, 3, 36]
        },
        "face4" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [0, 4, 3]
        },
        "face5" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [0, 1, 4]
        },
        "face6" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [6, 8, 12]
        },
        "face7" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [5, 6, 12]
        },
        "face8" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [5, 12, 24]
        },
        "face9" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [24, 12, 9, 25]
        },
        "face10" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [7, 9, 10]
        },
        "face11" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [47, 9, 7]
        },
        "face12" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [25, 9, 47]
        },
        "face13" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [8, 11, 12]
        },
        "face14" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [11, 2, 9, 12]
        },
        "face15" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [2, 10, 9]
        },
        "face16" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [13, 15, 19, 14]
        },
        "face17" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [21, 20, 15, 13]
        },
        "face18" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [22, 18, 17, 16, 23]
        },
        "face19" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [28, 5, 24, 25, 47, 48]
        },
        "face20" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [28, 26, 6, 5]
        },
        "face21" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [28, 42, 26]
        },
        "face22" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [48, 27, 29]
        },
        "face23" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [47, 7, 27, 48]
        },
        "face24" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [28, 48, 29, 42]
        },
        "face25" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [30, 33, 32, 31]
        },
        "face26" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [37, 0, 36]
        },
        "face27" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [37, 35, 0]
        },
        "face28" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [35, 1, 0]
        },
        "face29" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [37, 36, 6, 26, 34]
        },
        "face30" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [34, 26, 42]
        },
        "face31" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [41, 29, 27]
        },
        "face32" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [35, 41, 27, 7, 1]
        },
        "face33" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [37, 34, 38]
        },
        "face34" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [37, 38, 39]
        },
        "face35" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [37, 39, 35]
        },
        "face36" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [39, 40, 35]
        },
        "face37" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [40, 41, 35]
        },
        "face38" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [34, 42, 38]
        },
        "face39" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [38, 42, 39]
        },
        "face40" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [39, 42, 29]
        },
        "face41" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [39, 29, 40]
        },
        "face42" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [40, 29, 41]
        },
        "face43" : {
            "colour" : "COLOUR_DULL_RED",
            "vertices" : [43, 44, 28, 5, 24, 45]
        },
        "face44" : {
            "colour" : "COLOUR_DULL_RED",
            "vertices" : [43, 46, 25, 47, 48, 49]
        }
    },
}

Still need some work to get face names and material/color names(edit). And find a solution to create the BSP tree.

the Colour table at the top, is hardcoded in the exporter, so need a smart way to store that data in the blender file aswell.(edit2)

(updates a synced to the new githup repo LINK)

EDIT: Found an easy way to get material name, so use that as colour value.
EDIT2: Colour table is now generated from material names + rgb color of material, converted to srgb from blenders normalized rgb values.
EDIT3: Replaced cube with Typhoon export.

[Photon]

Originally Posted by Ernst Blofeld

This is something that I seem to have forgotten. I'm already using different code depending on the distance of objects from the camera, I can test using the blitter for very close up objects, which will have the biggest polygons.

Culling of objects outside the frustum and beyond the draw distance is already in there.

LOD is coming, with much of the code already done.

The sun is already precalculated as a set of 21 raster start and end points.

You may have done all these things, sorry - just some general points to avoid avoidable CPU filling/drawing.

The profiling point is the main one really - from this you find the priorities, and profiling may require some information not yet in the data structures, making you implement such useful information. (As an example, a flag signifying whether an object or polygon is partially on-screen can make you skip a clip call for all others.)

Originally Posted by Ernst Blofeld

I'm interested in this, particularly as I can see the accuracy problems occuring in my current visibility test using projected vertices. Could you go into more detail? I'm fine with the concept of pre-calculated normals, but, as far as I understand it, they need to go through the perspective transform, so adding a bunch more divides?

The main problem is
1. Visibility calc requires perspective projection
2. Perspective projection requires division
3. Visibility calc done from already projected vertices from word precision to word precision will yield a result with low precision around 0, just where you need it to be precise.

If the polygons are big or spinning fast, you can (to an extent) hack the precision and get away with it, but... by projecting the normals for just the Z sign, you get the sub-pixel precision you need to hide and show faces correctly with really not a lot of extra calculation.

If back-to-front poly rendering/scanline rendering, you only get intermittent edge lines. For light-sourced (the entire face will disappear when it shouldn't) and transparent vectors (the entire face gets the wrong color)... it removes a headache, and removes a hack as the engine grows.

Originally Posted by Ernst Blofeld

I have read up on a few algorithms that use edges, particularly for shadow casting and silhouettes, and have thought a lot about them, I know I could clip an edge only once if I had the concept of edges.

Yep, the shared edge (between typically only 2, no more, no less - rarely otherwise) polygons is clipped only once. And the price is not really more than the vertex lookup for a poly that you do now!

Originally Posted by Ernst Blofeld

But then I get stuck. Beyond the fact that an edge refers to two vertices, which have an order (a head and tail), and a polygon then becomes just a bunch of edges, what else would I need? I guess I'd need to sort out the normals and new visibility test first, as I'll no longer be able to do anything that involves walking around the vertices again. And can I do this without it becoming a mess of pointers?

Yep, an edge is simply a vertex pair! You can do anything you do now without a pointer mess. If you want, you can give the edges properties...

But yes. Edges are just a structure level in between polygons and vertices.

[Ernst Blofeld]

Originally Posted by Photon

If the polygons are big or spinning fast, you can (to an extent) hack the precision and get away with it, but... by projecting the normals for just the Z sign, you get the sub-pixel precision you need to hide and show faces correctly with really not a lot of extra calculation.

So, how do I project a normal? Or the normals for just the z sign? That's what I don't get and can't find any explanation for.

[Photon]

If you just want the sign, the normal must be perspective projected identically to the surface vertices it belongs to, but you can break out the projection to only do the product sums that affect Z sign (saving time).

If you need light sourcing not directly from between the eyes of the viewer or shadows not directly vertically below though, it becomes a full extra vertex (per poly) to calculate. It's a choice to make.

[LaBodilsen]

Originally Posted by LaBodilsen

The new blender json exporter, now outputs this for the typhoon in blender (with materials added for each face).

Still need some work to get face names and material/color names(edit). And find a solution to create the BSP tree.

the Colour table at the top, is hardcoded in the exporter, so need a smart way to store that data in the blender file aswell.(edit2)

(updates a synced to the new githup repo LINK)

EDIT: Found an easy way to get material name, so use that as colour value.
EDIT2: Colour table is now generated from material names + rgb color of material, converted to srgb from blenders normalized rgb values.
EDIT3: Replaced cube with Typhoon export.

New update: face names now comes from Face_maps names + face index

{
    "colours" : {
        "COLOUR_WOODY_GREEN" : [4, 6, 2],
        "COLOUR_DARK_WOODY_GREEN" : [3, 5, 2],
        "COLOUR_LIGHT_GREY" : [7, 7, 7],
        "COLOUR_MEDIUM_GREY" : [6, 6, 6],
        "COLOUR_DARK_GREY" : [3, 3, 3],
        "COLOUR_BLACK" : [0, 0, 0],
        "COLOUR_DULL_RED" : [7, 0, 0],
        "COLOUR_SKY_BLUE" : [0, 5, 11],
        "COLOUR_WHITE" : [14, 14, 14],
        "COLOUR_OCEAN_BLUE" : [0, 7, 13],
        "COLOUR_DARK_OCEAN_BLUE" : [0, 2, 4],
        "COLOUR_GRASSY_GREEN" : [2, 6, 0],
        "COLOUR_DARK_GRASSY_GREEN" : [1, 4, 0],
        "COLOUR_BRIGHT_YELLOW" : [15, 15, 3]
    },

    "bspTreeRoot" : "EurofighterObject",

    "vertices": [
        [9000, 0, 0],
        [7000, 577, 0],
        [4375, 633, 500],
        [7000, -289, 500],
        [7000, 289, 500],
        [-5250, -1154, 0],
        [2250, -1200, 0],
        [2250, 1200, 0],
        [4750, -871, 0],
        [4000, 1200, 1000],
        [4750, 871, 0],
        [4375, -633, 500],
        [4000, -1200, 1000],
        [7000, 0, 0],
        [5000, -2000, 0],
        [5500, 0, 0],
        [-4000, -5500, 0],
        [-4000, 5500, 0],
        [-2250, 5500, 0],
        [4750, -2000, 0],
        [4750, 2000, 0],
        [5000, 2000, 0],
        [4750, 0, 0],
        [-2250, -5500, 0],
        [-5000, -865, 500],
        [-5000, 865, 500],
        [2250, -774, -736],
        [2250, 774, -736],
        [-5500, -865, -500],
        [2250, 289, -1000],
        [-5514, 0, -528],
        [-7000, 0, -3500],
        [-6000, 0, -3500],
        [-2513, 0, -711],
        [4750, -446, -736],
        [7000, 289, -500],
        [7000, -577, 0],
        [7000, -289, -500],
        [4750, -550, -1299],
        [4750, 0, -1600],
        [4750, 550, -1299],
        [4750, 446, -736],
        [2250, -289, -1000],
        [-5250, 0, 0],
        [-5500, -289, -500],
        [-5000, -289, 500],
        [-5000, 289, 500],
        [-5250, 1154, 0],
        [-5500, 865, -500],
        [-5500, 289, -500]
    ],

    "faces" : {
        "exhaust43" : {
            "colour" : "COLOUR_DULL_RED",
            "vertices" : [43, 44, 28, 5, 24, 45]
        },
        "exhaust44" : {
            "colour" : "COLOUR_DULL_RED",
            "vertices" : [43, 46, 25, 47, 48, 49]
        },
        "canopy33" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [37, 34, 38]
        },
        "canopy34" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [37, 38, 39]
        },
        "canopy35" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [37, 39, 35]
        },
        "canopy36" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [39, 40, 35]
        },
        "canopy37" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [40, 41, 35]
        },
        "canopy38" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [34, 42, 38]
        },
        "canopy39" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [38, 42, 39]
        },
        "canopy40" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [39, 42, 29]
        },
        "canopy41" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [39, 29, 40]
        },
        "canopy42" : {
            "colour" : "COLOUR_BLACK",
            "vertices" : [40, 29, 41]
        },
        "upperNoseAndCockpit26" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [37, 0, 36]
        },
        "upperNoseAndCockpit27" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [37, 35, 0]
        },
        "upperNoseAndCockpit28" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [35, 1, 0]
        },
        "upperNoseAndCockpit29" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [37, 36, 6, 26, 34]
        },
        "upperNoseAndCockpit30" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [34, 26, 42]
        },
        "upperNoseAndCockpit31" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [41, 29, 27]
        },
        "upperNoseAndCockpit32" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [35, 41, 27, 7, 1]
        },
        "tail -double25" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [30, 33, 32, 31]
        },
        "upperFuselageTop24" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [28, 48, 29, 42]
        },
        "upperFuselageMain20" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [28, 26, 6, 5]
        },
        "upperFuselageMain21" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [28, 42, 26]
        },
        "upperFuselageMain22" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [48, 27, 29]
        },
        "upperFuselageMain23" : {
            "colour" : "COLOUR_WOODY_GREEN",
            "vertices" : [47, 7, 27, 48]
        },
        "fuselageRearFace19" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [28, 5, 24, 25, 47, 48]
        },
        "wingsLower -double16" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [13, 15, 19, 14]
        },
        "wingsLower -double17" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [21, 20, 15, 13]
        },
        "wingsLower -double18" : {
            "colour" : "COLOUR_DARK_WOODY_GREEN",
            "vertices" : [22, 18, 17, 16, 23]
        },
        "intake13" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [8, 11, 12]
        },
        "intake14" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [11, 2, 9, 12]
        },
        "intake15" : {
            "colour" : "COLOUR_DARK_GREY",
            "vertices" : [2, 10, 9]
        },
        "lowerFuselage6" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [6, 8, 12]
        },
        "lowerFuselage7" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [5, 6, 12]
        },
        "lowerFuselage8" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [5, 12, 24]
        },
        "lowerFuselage9" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [24, 12, 9, 25]
        },
        "lowerFuselage10" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [7, 9, 10]
        },
        "lowerFuselage11" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [47, 9, 7]
        },
        "lowerFuselage12" : {
            "colour" : "COLOUR_MEDIUM_GREY",
            "vertices" : [25, 9, 47]
        },
        "lowerNoseAndCockpit0" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [36, 3, 11, 8]
        },
        "lowerNoseAndCockpit1" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [11, 3, 4, 2]
        },
        "lowerNoseAndCockpit2" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [1, 10, 2, 4]
        },
        "lowerNoseAndCockpit3" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [0, 3, 36]
        },
        "lowerNoseAndCockpit4" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [0, 4, 3]
        },
        "lowerNoseAndCockpit5" : {
            "colour" : "COLOUR_LIGHT_GREY",
            "vertices" : [0, 1, 4]
        }
    },
}

[Ernst Blofeld]

Originally Posted by LaBodilsen

New update: face names now comes from Face_maps names + face index

Looking pretty cool.