# Triangle sees triangle?

## Recommended Posts

Tree Penguin    262
Hi, lets say i have a scene built up out of a few hundred triangles and i want to know if a triangle 1 'sees' triangle 2 (like there is a way to cast a ray from any point on triangle 1 to any point on triangle 2 that's not intersected by any other triangle). Is there an easy / fast way to determine it? I thought of casting rays and if one isn't intersected mark as true, if all (lets say 512 rays total) are intersected mark as false. The problem with that method is that it will be SLOW. So, any suggestions ?

##### Share on other sites
'triangle see triangle' = general problem because it's basically if any point of the first triangle can see any point of the secocnd triangle.

You can render scene with camera placed on the first traingle and looking at the second traingle and then if you rendertarget contains white pixels then second traignle is visible.

I think orthogonal projection would do he trick

##### Share on other sites
Tree Penguin    262
Quote:
 Original post by tomek_zielinski'triangle see triangle' = general problem because it's basically if any point of the first triangle can see any point of the secocnd triangle.You can render scene with camera placed on the first traingle and looking at the second traingle and then if you rendertarget contains white pixels then second traignle is visible.I think orthogonal projection would do he trick

Nah, that will be even slower then casting rays i think.
The problem is that i will have to do the test like 5000 times. It may take one or two hours total, that's no problem.

##### Share on other sites
Guest Anonymous Poster
Hi,
It's the base of the radiosity lighting method, you can check all the links which exists on that subject...

##### Share on other sites
Tree Penguin    262
Quote:
 Original post by Anonymous PosterHi,It's the base of the radiosity lighting method, you can check all the links which exists on that subject...

Thanks! It is for a rendering engine so that will probably be what i'm looking for.

##### Share on other sites
I described the method used in hardware accelerated radiosity, so no - It wouldn't be slower that CPU-only radiosty

##### Share on other sites
Tree Penguin    262
Nope, it's not.
I will explain it a bit further:

I just finished the diffuse lighting part of m rendering engine and i am now thinking of ways to implement reflections.

I want them to be as accurate as possible (so no ugly noise appears).
As i am working with lightmaps (not with pixels on the screen or anything, every triangle has its own lightmap) i thought of just casting rays from every texel of triangle 1 to every texel of triangle 2, which is slow and kind of related to radiosity.
The other solution would be casting rays from every reflective texel to see where it ends up (which isn't so accurate and maybe not even faster).
Anyway, as i think that first one is the only good solution and it's pretty slow. As there are probably only a few triangles that 'see' the reflective ones i would like to know if there's any accurate and fast way to see if they do.

##### Share on other sites
Quote:
 which is slow and kind of related to radiosity.

There is no way to do it in realtime that will be especially fast...the only ray tracers that are out there that both look nice and run fast must be run on super computers (there was a thing on NeHe that implements quake3 graphics using 100% accurate ray tracers, and requires something in the realm of a 12GHz procesdsor equivalent to be able to run).

So, basically, why not just do it in compile mode, let it be slow, and just save the results? That's how the regular lightmap is done anyway.

EDIT:
you could still use tomek's suggestion to 'cull' triangles. Look into the extension occlusion query (it's traditionally used to determine if rendering portals are visible or not...i.e in the doom3 alpha if you hit the button that shows portals, they are only activated (turn green) when the portal has at least some of its pixels visible to the eyepoint).

##### Share on other sites
Tree Penguin    262
Quote:
 Original post by shadow12345So, basically, why not just do it in compile mode, let it be slow, and just save the results? That's how the regular lightmap is done anyway.

What do you mean by compile time? The engine renders seperate frames of an animation, it get's the scene, the textures and everything else is calculated when the program runs.
As the data is only used once it's probably faster to calculate it when you need it (no loading and hd-space required).

Quote:
 Original post by shadow12345you could still use tomek's suggestion to 'cull' triangles. Look into the extension occlusion query (it's traditionally used to determine if rendering portals are visible or not...i.e in the doom3 alpha if you hit the button that shows portals, they are only activated (turn green) when the portal has at least some of its pixels visible to the eyepoint).

I have thought of excluding triangles that face the other way and excluding triangles that are behind the texels. Anyway i suddenly came up with the stupid simple idea of first testing the triangles using their bounding circles and then doing the point-in-triangle test.

##### Share on other sites
Tree Penguin    262
Quote:
 Original post by tomek_zielinski'triangle see triangle' = general problem because it's basically if any point of the first triangle can see any point of the secocnd triangle.You can render scene with camera placed on the first traingle and looking at the second traingle and then if you rendertarget contains white pixels then second traignle is visible.I think orthogonal projection would do he trick

False, parts visible on one texel might not be visible on another texel because of angles and such, what you see with one eye might not be visible with the other.

##### Share on other sites
Quote:
Original post by Tree Penguin
Quote:
 Original post by tomek_zielinski'triangle see triangle' = general problem because it's basically if any point of the first triangle can see any point of the secocnd triangle.You can render scene with camera placed on the first traingle and looking at the second traingle and then if you rendertarget contains white pixels then second traignle is visible.I think orthogonal projection would do he trick

False, parts visible on one texel might not be visible on another texel because of angles and such, what you see with one eye might not be visible with the other.

I've got the impression that you want to tell me that I don't have brain. So let's see.. Your first post was:
Quote:
 Hi, lets say i have a scene built up out of a few hundred triangles and i want to know if a triangle 1 'sees' triangle 2 (like there is a way to cast a ray from any point on triangle 1 to any point on triangle 2 that's not intersected by any other triangle).Is there an easy / fast way to determine it?I thought of casting rays and if one isn't intersected mark as true, if all (lets say 512 rays total) are intersected mark as false. The problem with that method is that it will be SLOW.So, any suggestions ?

You didn't write that you have lightmaps etc, only "let's say that". So I answered you what came to my mind... If I had known that you want to do lightmaps things I wouldn't have recommended this. Of course you are right that orthogonal projction for the entire triangle wouldn't be a proper solution but how could I know that earlier before you said sth more?

I'm doing similar thing(I mean lightmapping). Just visit my site.

##### Share on other sites
Eelco    301
im still not entirely sure what you want to archieve.

full radiosity is hard and slow. but you mention reflections. reflections are dead-easy. just cast another reflected ray from a surface youve hit. noise isnt a factor, your reflections will be crisp as can be, if you have the vector reflection formula handy, which google will kindly provide and explain to you.

##### Share on other sites
nmi    978
So if I understand you right, you have two triangles A and B. Now you want to figure out if there are points P and Q in those triangles, so that the connection of P and Q does not intersect with another triangle.

My suggestion would be to create a (imaginary) prism with A on top and B on the bottom. Then check if all other triangles split this prism into two parts. If this is the case, there is no line of sight.

You can do this check by just testing if the three connection line between A and B hit the other triangles inside. If one of those lines does not intersect in any of those triangles, you found a line of sight.

##### Share on other sites
Tree Penguin    262
Quote:
 Original post by tomek_zielinski[I've got the impression that you want to tell me that I don't have brain.

I didn't, and my qustion has nothing to do with lightmaps except that the points i want to test are texels of a lightmap which is just like any other point on the triangle.

Anyway i have done a few things unneccesserily complicating and slowing down the rendering, that's why i was concerned about the speed. I fixed it now so i have no more questions.
Thanks anyway!

## Create an account

Register a new account