quad trees and texture mapping

This is not strictly OpenGL question, but I’m hoping there are people here who can answer it.
Let’s say you have a bunch of 3d objects, and they are all texture mapped to some textures. Then you stick all those objects into quad tree - new objects are formed due to dissection of existing objects with division planes. Do you have to recalculate mapping coordinates for new vertices created as a result of the intersection ? If so, do you know of an article or a source code that would explain how to go about it ? If you have any helpful tips that would be great too.
Thank you,


You will have to specify the new mapping coordinates to OpenGL.

It should be pretty easy to find them :
Say you have an edge between 2 vertices Va-Vb (with textures coordinates Ta and Tb).
It gets cut at vertice VC to become Va-Vc-Vb.
The new texture coordinates will be something like :
Tc = (length(Va,Vc)*Tb+length(Vc,Vb)*Ta )/length(Va,Vb)

(search for barycentric computation)

Hope it helps.

Well, almost

Tc = (length(Va,Vc)*Tb+length(Vc,Vb)Ta )/(2length(Va,Vb))

Correction, I deleted my post since I missed the texture coords in the title.

Yep if you split you need to compute the new coords. It’s just a lerp along the edges. Infact yuo can simply use pythagoras to compute the edge lengths & use ratios to get the coordinate should give you the correct result for each edge.


should be equal to

(s2 - s1) / (s3 - s1)

should be equal to

(t2 - t1) / (t3 - t1)

Where the s1 s2 s3 t1 t2 t3 are texture coords for original vertices v1 & v2 and the new vertex v3, and the original lencth is the magnitude of v2 - v1 and the split length is the magnitude of v3 - v1.

Which is probably what zbuffer has been saying all along :slight_smile:

[This message has been edited by dorbie (edited 12-30-2003).]

hmm… if the faces are not very large, then, why to split them up at all?

Of course it depends on the size and kind of objects you have, but it does not have to be neccessary to split up an object into its atomic faces, and even less neccessary, to split up the faces themselves.

The result will be that the nodes of the tree will overlap a little (in the quad tree I wrote, first all objects get sorted into the tree, by splitting up planes in the middle, and after that, the real middle and size of a tree node is calculated), but I think this will not hurt much… in my terrain engine, one object is represented by one display list, so it cannot be split up at all (of course, alternatively one tree node can be represented by one display list).

But my main experience with quad trees is that they somehow seem not to be neccessary at all… let’s say, there are n objects. I did both, putting these objects into a tree and cull the tree, and alternatively, test each object separately for visibility, and there was no really significant difference… I was quite surprised, but the actual number of tests is not THAT different (about half as much in average), and also, the visibility test does not seem to take a lot of time. This resulted in deciding against quad trees at all, and the program is running fine.


[This message has been edited by JanHH (edited 12-30-2003).]