knuckleheaded code in bsptree.cc

[m-7761]

https://github.com/zturtleman/mm3d/blob/53b0d1b33412bddacd65559f41d5511b9050a27a/src/libmm3d/bsptree.cc#L127-L188

You can see this is doing some form of iterative search. Below is equivalent code. Note, "abc" and "d" are the normal and plane-distance for that node. And below that I went ahead and uploaded the results of a cleanup pass I did last night. I will say it seems to do double-duty by allocating the Node and Poly objects separately when in fact they're the same objects.

double BspTree::Poly::intersection(double *p1, double *p2, double *po)
{
	double *abc = norm(), p2_p1[3];

	for(int i=3;i-->0;) p2_p1[i] = p2[i]-p1[i];

	double t = (d-dot_product(abc,p1))/dot_product(abc,p2_p1);

	lerp3(po,p1,p2,t); return t;
}

https://github.com/mick-p1982/mm3d/blob/widgets95-ui/src/libmm3d/bsptree.cc

[m-7761]

Working with this more (I'm doing a transparency sorting project for my game engine project) it looks like its implementation is fundamentally incorrect because it only splits triangles that are compared to the inserted triangle along its insertion path.

Instead it should split every triangle with respect to all triangles' planes and then sort them by plane. I'll post a follow-up reply after I've implemented something.

EDITED: https://github.com/GerardMT/BSP-Tree/blob/master/src/bsp_tree.cpp has some code. It looks like it might help to section the polygons into half-spaces as an optimization, but I'm pretty sure that's not what the bsptree.cc code is accomplishing because I've drawn its cuts as a wireframe and it's way more irregular than that, and I can't see how it would work from any vantage point to produce sorted transparency. Although I admit I haven't seen any glitches with my own eyes yet.

[m-7761]

Follow-up: https://github.com/mick-p1982/mm3d/blob/widgets95-ui/src/libmm3d/bsptree.cc now shows code that uses a linked-list to store polygons inside the BSP nodes. An added benefit is coplanar polygons should all end up in the same node together. I think it's correct.

Edited: The code that sets it up is in model.cc. It calls addTriangles on each group with transparent effects, and then partition.