#### Archived

This topic is now archived and is closed to further replies.

# Visibility Ordering in a Terrain Problem (screenshots of course)

This topic is 5103 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Aieee.. I am trying to obtain a visibility ordering from the triangle bintree structure used in ROAM implementations. The way I am currently doing it is: 1. Traverse tree and put pointers to nodes(triangles) that need to be rendered into a preallocated array. 2. For each node in the array, determine a relative distance from the centroid of each node/triangle to the camera position. Obtained use dRel = deltaX^2 + deltaY^2 + deltaZ^2. Deltas are simply centroidX - cameraX, etc.. 3. Sort the array based on the relative distances to achieve a near to far or far to near ordering. This works perfectly fine. I was informed by my professor, however, that this is not the correct method and should, in fact, fail. He mentioned that the correct method would be use the tree itself to derive an implicit ordering based on halfspace calculations. I have no idea what he meant in all honesty. I could only imagine checking which halfspace the camera lies in for each node''s hypotenuse and rendering the node which the camera is "in" before rendering the node that is "out". This is clearly not what he meant. If I do this, then that means that every single child of the "in" node will be rendered before the "out" node is even touched. This obviously does not give any sort of ordering. Here are the screenshots. The colouring of the faces is dependant upon their render order. Faces rendered earlier are lighter than faces rendered later. The screenshot is taken as I look directly down the shared border between the two root nodes. This emphasizes of the problem with my messed up interpretation of what he said. HalfSpace method Distance/Centroid method What am I doing wrong? How can I obtain an implicit ordering when I traverse the tree???? Any help would be EXTREMELY appreciated. He mentioned that my method should actually fail. Does anybody know why he would say this? It seems rock solid but I''m new to terrain. How could it ever fail?

##### Share on other sites
He is correct. It is very easy for the centroid of a triangle to be closer than the centroid of a triangle in front of it.
                      / \                    /  |  \                  /    |    \                /      |      \              /        |        \            /     A    |          \          /  \         |            \        /      \       |              \      /          \     |     C          \    /      B       \   |                  \  /                  \ |                    \/----------------------|----------------------\                    X
The centroid C is closer to X than A even though triangle C is behind triangle A from X''s point of view.

The way the "halfspace" method works is this: when you split a triangle into two triangles, the triangle and all its sub-triangles on the camera''s side of the split are always in front of the triangle and all its sub-triangles on the other side of the split. To render near-to-far, just traverse the tree depth-first rendering the sub-node on the camera''s side of the split first. To render far-to-near, render the sub-node on the other side of the split first.

##### Share on other sites
Thanks for the diagram. In fact, it looks quite similiar to the case at hand which I showed in the screenshots. Do you mean to say that I might actually have the correct ordering in the halfspace screenshot?

In your diagram since X lies within the halfspace with A/B. This means that every node within A/B would be processed, before considering the C side of the halfspace? Ignoring splitting for a second, if your node A was split into nodes A1 and A2.. then A1 and A2 would also be rendered before node C, correct???

Thanks for the help. Terminology is probably the source of my confusion here. I had been taking "near/far" to mean rendering the objects which are most literally near to the viewer first.

EDIT: My diagram wasn't quite so nice. Clipped.

[edited by - haro on March 6, 2004 3:41:22 AM]

##### Share on other sites
"near-to-far" is a misnomer. It is not really a question distance, rather of who is in front of who.

Since X is on the AB side of the AB/C split, AB and every sub-triangle of AB is guaranteed to be in front of C. Likewise, B and every sub-triangle of B is guaranteed to be in front of A because X is on the B side of the A/B split.

##### Share on other sites
Great, much thanks.