[Bf-committers] viewport bug #27979

Matthias Fauconneau matthias.fauconneau at gmail.com
Thu Aug 18 00:15:52 CEST 2011

Hi,
Nice to see this issue finally tackled.
I'm not a blender coder but here are my two cents.

- Distance
It seems you're computing the distance to the origin (zero) of object space.
It would be better to use the center of the object bounding box (which
I think is stored with object, not sure if they are world axis aligned
though).
Besides, You're using a full matrix multiplication, while you'd only
need to transform the object position.

- Sort
I have trouble understanding your sort but it seems really inefficient (O(n*n))
Since the objects will most probably be sorted the same way on each
redraw, you could keep the sorted list (or directly sort the original
list if nothing depends on its order) and use insertion sort (very
simple to implement) which would run O(n+d). n being the number of
elements and d the number of swaps (e.g 0 if it is already sorted!).

- Draw
selected/edit mode objects are drawn last so that they overlay
unselected objects and you probably broke that ;)

PS: while you're at it, you could frustum cull your objects for
improved performance.

Here is pseudo code to frustum cull bounding boxes:

/// Compute view frustum planes (only once!)
mat4 m = projection*view;
vec4 planes;
planes = vec4( m(3,0) + m(0,0), m(3,1) + m(0,1), m(3,2) + m(0,2),
m(3,3) + m(0,3) );
planes = vec4( m(3,0) - m(0,0), m(3,1) - m(0,1), m(3,2) - m(0,2),
m(3,3) - m(0,3) );
planes = vec4( m(3,0) - m(1,0), m(3,1) - m(1,1), m(3,2) - m(1,2),
m(3,3) - m(1,3) );
planes = vec4( m(3,0) + m(1,0), m(3,1) + m(1,1), m(3,2) + m(1,2),
m(3,3) + m(1,3) );
planes = vec4( m(2,0), m(2,1), m(2,2), m(2,3) );
planes = vec4( m(3,0) - m(2,0), m(3,1) - m(2,1), m(3,2) - m(2,2),
m(3,3) - m(2,3) );
vec3 signs;
for(int i=0;i<6;i++) { planes[i]=normalize(planes[i]);
signs[i]=sign(planes[i].xyz()); }

foreach( objects ) {
vec3 A,B = corners of axis aligned bounding box.
object.center=(A+B)/2;
object.extent=abs(B-A)/2;

// Optimization: First, check first with the plane that culled last time
int shortcut=object->planeIndex;
if( dot(object->center+object->extent*signs[shortcut],
planes[shortcut].xyz())+planes[shortcut].w < 0 ) goto cull;

// Otherwise check all 6 view frustum planes
for(int i=0;i<6;i++) {
if( dot(object->center+object->extent*signs[i],
planes[i].xyz())+planes[i].w < 0 ) {
object->planeIndex=i; //store the plane to use fast path next time
goto cull;
}
}

{ Insert object in depth sorted list here }

cull: //label to skip drawing (can't use continue; in nested loop)
}

You can also probably look at BGE for inspiration.