Sign in to follow this  

monte carlo for triangle

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi guys, anyone ever applied monte carlo approach for triangle? im trying to build a ray tracing using triangles as my scenes but havving problem trying to have the monte carlo approach. any idea? thanks in advance

Share this post


Link to post
Share on other sites
so im trying to create soft shadow effect, following the steps at devmaster. one way to create it is to have a random value in each grid from the light source. since their light source is a rectangle, it doesnt seem to be a problem to create such effect. but my light source is a triangle. i just dont know the way to do it.

here is the source the tutorial im following:
http://www.devmaster.net/articles/raytracing_series/part5.php

go down to the poker face and pimple part.


thanks in advance

Share this post


Link to post
Share on other sites
I stole this from a completely unrelated webpage, but it does illustrate the type of subdivision that you can use in a triangle:


If you have a hard time implementing this in code, I can try to write a little snippet, but I won't have time for it until tonight.

Share this post


Link to post
Share on other sites
if you want a purely random distribution, see ajas95's post in this thread: http://www.gamedev.net/community/forums/topic.asp?topic_id=433793

EDIT: I looked too fast, he doesn't give much details on the actual random parameters computation... you can try this:


float r0 = sqrt(random(0.0f, 1.0f));
float r1 = random(0.0f, 1.0f); // returns a random float between 0.0f and 1.0f
float u = 1.0f - r0;
float v = r0 * r1;
float w = r0 - v;

sample = v0 * u + v1 * v + v2 * w;




anyway, this will give you an uniform random distribution across your triangle face. the resulting sampling will be of lower quality than what alvaro suggested, especially if you randomply jitter the generated samples.

[Edited by - momotte on March 1, 2010 9:13:44 AM]

Share this post


Link to post
Share on other sites
Hmmm... Actually, I thought of a much easier way to generate a decent random pattern on a triangle. Consider a square divided into two triangles. Generate a decent random pattern on the square, and fold in the samples that fall outside of the desired triangle. You can then map that triangle to yours by an affine transform.

Point sample_in_triangle(Triangle T, int i) {
double x, y;

// load x and y with values between 0 and 1, following
// the code in that link you posted
sample_in_unit_square(i, &x, &y);

if (x>y)
swap(x,y);

return T.A + x*(T.B-T.A) + y*(T.C-T.B);
}


Is that clear enough? Is it clear why it would work?

This will not generate identical results to what I said before, but it will probably be good enough, and it's so much easier to implement.



Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
This will not generate identical results to what I said before, but it will probably be good enough, and it's so much easier to implement.


What's less-than-perfect about your solution? Hmmm... It looks like the expected value of the number samples in a given subset is a constant independent of the subset... and you're also guaranteed to get at least one point in each subdivision of the triangle. Granted, those subdivisions are half the size at the diagonal, but their preimages under the square->triangle map also have half the area, so the bit about expected value above still holds... I guess the upshot is that you expect samples to be more evenly distributed (i.e., "more evenly than random") around the diagonal than elsewhere... Ok, I see the issue. Seems very minor to me.

That said, I do find this "random sampling with deterministic subdivisions" a little interesting: This problem is not what I'd originally thought it was (At first I thought the poster just wanted iid samples uniformly distributed on the triangle, which is easy). It makes me wonder what sort of sampling theory there is on this subject, as Nyquist does not (obviously at least) apply... Any references on the subject?

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Original post by alvaro
This will not generate identical results to what I said before, but it will probably be good enough, and it's so much easier to implement.


What's less-than-perfect about your solution?


As you said, for the triangles on one edge (the diagonal of my square), it's the same distribution. For the rest, triangles are paired up (to form a sub-square, if you map through the inverse of the affine transform) and you'll get two samples in each region, but not necessarily one in each triangle (which was my original intention). Anyway, I doubt you'll be able to tell by looking at the rendered image.

Texts that deal with supersampling will often mention this method as "jitter". There is an apparently better method called something like "Poisson disc", but I never looked into the issue with enough interest to find out why it would be better. Google for `supersampling jitter poisson' and you'll get some explanations.

Share this post


Link to post
Share on other sites
hi,

i think there's a little bit misconception about what im asking here. i already able to pick random points from a triangle (using baycentric coordinate).

the problem is, as proposed by the article above, to guarantee the random value wont jitter at the same place over and over again, we split the triangle over and over again until we came up with a small enough triangles, and pick random numbers from those new and small triangles.

what im confused is the way to split the triangles equally. i already got the big picture, by the image above from alvaro, and i came up with code but did not manage to do it right. i did recursivelly. i dont have access to the code right now, but pretty soon. any algorithm would be very appreciated :)


thanks in advance :)

Share this post


Link to post
Share on other sites
Quote:
Original post by svnstrk
i think there's a little bit misconception about what im asking here.


No, I think we understood your question correctly. In the pseudo-code I posted, sample_in_unit_square() is supposed to be a working implementation of jittering for the square. Sorry I didn't make it more explicit...

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this