Board index » delphi » optimal object searching in a large space

optimal object searching in a large space

I have been working on this problem for a few days, I have a couple ideas
but nothing solid yet.

If anyone wants a challenge then try to figure out this :-) and help me :-))

Here is the problem I have:

Say I have some number or triangles which are in some 2D space (a plane).
No 2 triangles in the plane overlap, but they can touch edges or be alone.
Basically giving clumps of triangles scattered throughout the 2D plane.

Now I must use these triangles or clumps to "cover" another triangle which
is behind the 2D layer of triangles.

****************
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.
****************

 

Re:optimal object searching in a large space


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

Re:optimal object searching in a large space


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

Re:optimal object searching in a large space


Quote
>****************
>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.
>****************

     Build a list of triangles sorted by some system (x, y, or perhaps
radius in a polar system).  For each triangle, store a "center"
point--minimize the maximum distance to a vertex.  Store the square of
this distance.

     To test, compute the same center&distance for the target
triangle.  Using the sorted list you can find a minimum and maximum
point in the list which needs to be tested.  Furthermore, when
testing, first compare the square of the distance to the sum of the
stored squares for the test and target triangle--if the square of the
distance is greater, there's no chance of overlap.  This greatly cuts
the number of cases for which expensive tests must be done.

Re:optimal object searching in a large space


:-)

Smiling because you so quickly came up with a solution that I had come up
with too but took me longer, I found that this would not work in my
situation because there are many "new" triangles to be added to the result.

I'll make a upper level post that descibes what I am doing...

I'll call it -- "What I am doing" :-)

Quote
Loren Pechtel <lorenpech...@hotmail.com> wrote in message

news:3b4b28f9.91775839@newsgroups.borland.com...
Quote
> >****************
> >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.
> >****************

>      Build a list of triangles sorted by some system (x, y, or perhaps
> radius in a polar system).  For each triangle, store a "center"
> point--minimize the maximum distance to a vertex.  Store the square of
> this distance.

>      To test, compute the same center&distance for the target
> triangle.  Using the sorted list you can find a minimum and maximum
> point in the list which needs to be tested.  Furthermore, when
> testing, first compare the square of the distance to the sum of the
> stored squares for the test and target triangle--if the square of the
> distance is greater, there's no chance of overlap.  This greatly cuts
> the number of cases for which expensive tests must be done.

Re:optimal object searching in a large space


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.

Re:optimal object searching in a large space


According to WE,

Quote
> 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.

If you assume that a triangle has a "front" and a "back", and only the front  
is ever shown (the "back" is always covered by other triangles), you can use
backface culling. Using this method, you can usually eliminate about 50% of
the triangles.

Putting more effort in eliminating triangles might not prove practical -
after you've eliminated 50% of the triangles you sometimes better go
painting the leftover ones, instead of trying to eliminate more using
expensive calculations. But if you really think you can make it better, try
it of course!

Matthijs

Re:optimal object searching in a large space


No triangles have backs so I cannot use backface culling. You either see
them or they are covered by other triangles.

I am not rendering to a video monitor either.  My output goes to a low
bandwidth vector output device. It would be impossible to do paint overs.

Re:optimal object searching in a large space


Quote
>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....

     Other than the use of rectangular instead of round bounding
edges, this is basically what I was suggesting.  Using rectangular
bounds you need to do 4 comparisons to test for a possible hit.  With
round boxes you need two additions, a multiplication and a comparison.
I think it would be about a wash.

Re:optimal object searching in a large space


Quote
>No triangles have backs so I cannot use backface culling. You either see
>them or they are covered by other triangles.

>I am not rendering to a video monitor either.  My output goes to a low
>bandwidth vector output device. It would be impossible to do paint overs.

     Ok, I see what you're doing--3D drawings to a plotter.

     How about this solution--memory intensive but O(n) runtime:

     Do the paintovers.

     In memory, draw the triangles.  Each triangle is drawn in a
different "color", and it's depth is stored in a separate buffer.
Note that you must draw all partial pixels around it's edge.  When a
collision occurs, use the depth table to resolve which ends up in
front and the pixel is painted that "color".  You also note that those
two triangles probably collide.  By the time you get done you've got a
list of all collisions that must be tested with only a few false
positives from touching or nearly touching triangles.

Re:optimal object searching in a large space


The roundies, Can you explain in a little more detail, I am not getting it.

This is why I am not getting it...

I think you are saying each triangle has a circle around it (based on the
center to minimize error), but in order to tell if one triangle may
intersect with another it seems I would still have to search the entire
"object space" because the distance in relation to the new object must be
calculated.  The problem: I still have to search the entire space.

Where am I loosing you if you think that I do not have to search the entire
space for each new triangle?

Quote
Loren Pechtel <lorenpech...@hotmail.com> wrote in message

news:3b4c971e.11064609@newsgroups.borland.com...
Quote
> >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....

>      Other than the use of rectangular instead of round bounding
> edges, this is basically what I was suggesting.  Using rectangular
> bounds you need to do 4 comparisons to test for a possible hit.  With
> round boxes you need two additions, a multiplication and a comparison.
> I think it would be about a wash.

Re:optimal object searching in a large space


Interesting, ....

I am not sure I follow you directly....

Quote
>>partial pixels

?

Ok, here is what I am getting from what you say.. me maybe changing it a
little or a lot because I don't follow you exactly.

Lets say I use regular windows drawing or even OpenGL (using hardware) to
draw onto bitmap. Each triangle could be drawn with a colored border and
fill color equal to the background color.  After all triangles are drawn
from depth back to front, then I will have all colored lines which should be
clipped perfectly.  I can take a second routine (which I already have) and
trace the lines and extract the vectors.

btw - I need to have these vector lists at a rate of 30fps.

Not quit a plotter but exactly the same concept.

Re:optimal object searching in a large space


Quote
>Ok, here is what I am getting from what you say.. me maybe changing it a
>little or a lot because I don't follow you exactly.

>Lets say I use regular windows drawing or even OpenGL (using hardware) to
>draw onto bitmap. Each triangle could be drawn with a colored border and
>fill color equal to the background color.  After all triangles are drawn

     No.  It's drawn in a pseudo-color that it's triangle number.
Otherwise, this is normal z-buffer drawing.

Quote
>from depth back to front, then I will have all colored lines which should be
>clipped perfectly.  I can take a second routine (which I already have) and
>trace the lines and extract the vectors.

     I wasn't figuring you could get exact clipping, but merely a
nearly exact list of what triangles hit what.  I'm assuming the vector
device has a higher resolution than any practical bitmap.

Quote
>btw - I need to have these vector lists at a rate of 30fps.

     Oh, boy!

Quote
>Not quit a plotter but exactly the same concept.

     Ok, what piece of hardware is it?  You've got me puzzled now!  A
laser tracing out images or something?

Re:optimal object searching in a large space


Quote
>The roundies, Can you explain in a little more detail, I am not getting it.

>This is why I am not getting it...

>I think you are saying each triangle has a circle around it (based on the
>center to minimize error), but in order to tell if one triangle may
>intersect with another it seems I would still have to search the entire
>"object space" because the distance in relation to the new object must be
>calculated.  The problem: I still have to search the entire space.

>Where am I loosing you if you think that I do not have to search the entire
>space for each new triangle?

     You only have to search those within a certain coordinate region.
I was proposing the circle because the calculation for possible
overlap is a bit simpler than for bounding boxes.

     From what you've said otherwise I think the other solution I
proposed would work better anyway.

Other Threads