I read yours and have questions, then yesterday I came up with another

solution.

Answers to your question:

No polygons change, there points have already been converted into 2D and now

only have depth information with respect to other triangles... rules of the

system is that there are no circular overlapping (picture 3 long triangles

overlapping in a circle) and the last rule is that no triangles "punch

through" eachother.

Questions on yours:

Are you talking about a BSP tree? Are you talking about dividing the space

into nested quads? Does it allow something like one big triangle that

covers the whole screen? Do you split triangles so they do not go into

multiple quads?

I think it would be good to explain all that I am doing, I am creating a new

algorithm for hidden surface removal because I have not found one that is

very effecient or display independent.

My approach is this:

Rules:

a. The entire system must be made of triangles.

b. There cannot be any intersecting triangles (one punches through the other

I mean)

c. There cannot be any circluar overlapping.

(btw - a pre processor could correct any existing system to follow the above

rules)

Assumption:

When viewing 2 triangles, either they are next to eachother, or one overlaps

the other. So taking that, I can sort all triangles by depth. See rule c.

Answer:

The idea is that all triangles in lower depth (n, away from you) will be

clipped by traingles in higher depth (0, closer to you).

I start drawing from the closest triangle down to the farthest away triangle

and clip each new triangle as I add it to my result. Remember, it will only

be clipped one time because of the depth order.

The performance problem to solve was which triangles will clip the new

triangle, I wanted to find them without doing an exhustive search. Thus the

reason for this post...

My idea I had yesterday:

Take all triangles and imagine each being contained by a square, the square

would have topleft and bottomright coordinates. Then I would use a quick

sort algorithm so sort all triangles by Left then Right, then Top then

Bottom. Now my new triangle would also have a box, I would first find all

triangles whoes left side is Less than my new triangles right side, ....

wait this would be easier to read if I wrote psudo code....

AllTriangles is a sorted list of all triangles (Left, Right, Top, Bottom)

NewTriagle is the new one.

The subset of all triangles which could possibly intersect the new triangle

is this

SomeTriangle.Left < NewTriangle.Right;

SomeTriangle.Right > NewTriangle.Left;

SomeTriangle.Top < NewTriangle.Bottom;

SomeTriangle.Bottom > NewTriangle.Top;

Since all triangles are sorted in the order of Left, Right, Top, Bottom then

I should be able to create a very quick algorithm to select those triangles

that satisfy the above criteria.

This would at least narrow down how many triangles I have to check for

intersection and the size of the space an number of triangles should have

minumum impact on overhead I think.

##### Quote

Lord Crc <lord...@hotmail.com> wrote in message

news:g74kkt4crdn38j84usin0lheklekj7uboe@4ax.com...

##### Quote

> On Mon, 9 Jul 2001 15:28:10 -0400, "WE" <e...@eggcentric.com> wrote:

> >****************

> >The question is, what is the fastest way to find all triangles in the 2D

> >space that cover the other triangle? I do not want to do an exhaustive

> >search.

> >Even a rough estimate would be fine, I am just trying to avoid the

> >exhaustive search.

> >Pre Processing *one time on all triangles is acceptable.

> >****************

> Does any of the polygons on the plane change? Does the "other"

> triangle change?

> Either way, i think using a quad-tree should be fast. First find the

> quads the "other" triangle is in, then recurse, if the new quads

> intersects the triangle recurse further, if not, well, no need to

> check :)

> Its also fairly easy to add/remove the triangles from the tree.

> - Asbj?rn