Thomas de Groot wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht 
> news:4c6acef8@news.povray.org...
>> I haven't tried Edouard's code yet, though I did search for some examples 
>> with Google's image search. The repetition is often very noticeable, as 
>> seen in the following images:
>>
>> http://www.puc-rio.br/marco.ind/imagens/halton_2d.gif
>> http://www.mathworks.com/matlabcentral/fx_files/17457/1/halton.jpg
>> http://www.blitzcode.net/images/projects/project_150_big.png
>>
>> The first and second examples repeat completely in one diagonal direction, 
>> and partially in another. The third is a bit harder to tell, but there is 
>> definitely some partial repetition present, even with the low number of 
>> points.
> 
> What do you think of the image rendered with Edouard's code, I uploaded to 
> p.b.i.?

I think that gaining some speed isn't worth the result. Like the other 
Halton sequences I have seen, the one you rendered shows a lot of 
repetition. And there are numerous instances in which the particles line 
up unnaturally. In fact, they are so numerous that they cannot be 
misconstrued as mere coincidences.

Have you tried placing ten times the number of particles that you used 
for that example? With smaller particle sizes? Is so, do the particles 
ever overlap? I suppose that if you can use more particles, then the 
periodicity may not be much of an issue, but the diagonal alignment 
problem will still be present.

I've been thinking about just making some scripts to generate spaced 
point sets with min/max particle sizes, pigment-based distribution, and 
maybe even some macros for accessing the points.

Sam

Post a reply to this message

"stbenge" <myu### [at] hotmailcom> schreef in bericht 
news:4c6c1d8d@news.povray.org...
> I think that gaining some speed isn't worth the result. Like the other 
> Halton sequences I have seen, the one you rendered shows a lot of 
> repetition. And there are numerous instances in which the particles line 
> up unnaturally. In fact, they are so numerous that they cannot be 
> misconstrued as mere coincidences.

OK, yes, there are indeed repetitions, alignments and oriented gaps. I agree 
with you that this is not perfectly random.

> Have you tried placing ten times the number of particles that you used for 
> that example? With smaller particle sizes? Is so, do the particles ever 
> overlap? I suppose that if you can use more particles, then the 
> periodicity may not be much of an issue, but the diagonal alignment 
> problem will still be present.

See my third example in p.b.i. (red) compared to rand() in green.
>
> I've been thinking about just making some scripts to generate spaced point 
> sets with min/max particle sizes, pigment-based distribution, and maybe 
> even some macros for accessing the points.

That would be perfect, Sam :-)

We are putting you to work! ;-)

Thomas

Post a reply to this message

Thomas de Groot wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht 
> news:4c6c1d8d@news.povray.org...
>> I think that gaining some speed isn't worth the result. Like the other 
>> Halton sequences I have seen, the one you rendered shows a lot of 
>> repetition. And there are numerous instances in which the particles line 
>> up unnaturally. In fact, they are so numerous that they cannot be 
>> misconstrued as mere coincidences.
> 
> OK, yes, there are indeed repetitions, alignments and oriented gaps. I agree 
> with you that this is not perfectly random.

I'm probably just nitpicking :/

>> Have you tried placing ten times the number of particles that you used for 
>> that example? With smaller particle sizes? Is so, do the particles ever 
>> overlap? I suppose that if you can use more particles, then the 
>> periodicity may not be much of an issue, but the diagonal alignment 
>> problem will still be present.
> 
> See my third example in p.b.i. (red) compared to rand() in green.

They look a little better.

>> I've been thinking about just making some scripts to generate spaced point 
>> sets with min/max particle sizes, pigment-based distribution, and maybe 
>> even some macros for accessing the points.
> 
> That would be perfect, Sam :-)

I'm not sure that the time it takes to parse large sets is really worth 
it. See the image I posted in p.b.i.:
http://news.povray.org/povray.binaries.images/thread/%3C4c6d67d5%40news.povray.org%3E/

It took 23 minutes, 36 seconds to parse. Out of the 50,000 tests I gave 
it to perform, only a mere 3,065 succeeded. To me, this is unacceptable. 
If you were to populate a landscape with rocks or trees, you would need 
more points than that. To make matters worse, the parse time goes up 
with each new point added. I even used two optimizations. In one, a 
point stops trying to be placed after the first overlap. The other one 
bails out completely after failing to place a new random point n 
consecutive times. I didn't use the latter for that render. If I had, 
the parse time wouldn't have been as long, but there would have been 
fewer points. If, after all this you still want some code, I'll go ahead 
and finish the file-writing routines, which is the easy part.

Another method is to just code this in C++, using a bitmap-like array to 
test against. It's not as accurate, but it's much faster and you get to 
see the progress, and can bail out manually at any time, saving the 
successful points. I've already got a rough version, but I need to learn 
more about vector.h before I can finish it.

Post a reply to this message

<snip>
> I'm not sure that the time it takes to parse large sets is really worth 
> it. See the image I posted in p.b.i.:
>
http://news.povray.org/povray.binaries.images/thread/%3C4c6d67d5%40news.povray.org%3E/
>
> It took 23 minutes, 36 seconds to parse. Out of the 50,000 tests I gave it 
> to perform, only a mere 3,065 succeeded. To me, this is unacceptable. If 
> you were to populate a landscape with rocks or trees, you would need more 
> points than that. To make matters worse, the parse time goes up with each 
> new point added. I even used two optimizations. In one, a point stops 
> trying to be placed after the first overlap. The other one bails out 
> completely after failing to place a new random point n consecutive times. 
> I didn't use the latter for that render. If I had, the parse time wouldn't 
> have been as long, but there would have been fewer points. If, after all 
> this you still want some code, I'll go ahead and finish the file-writing 
> routines, which is the easy part.
>
> Another method is to just code this in C++, using a bitmap-like array to 
> test against. It's not as accurate, but it's much faster and you get to 
> see the progress, and can bail out manually at any time, saving the 
> successful points. I've already got a rough version, but I need to learn 
> more about vector.h before I can finish it.

This is the exact problem I ran into when coding the same sort of thing.  My 
code works also but it has a very high miss rate, very low success rate and 
it also takes ages to parse.

I've parked my code for now anyway, I'm doing other stuff atm but one day 
I'll dig it up and see if there is anything that I can do about it...

Cheers Dre

Post a reply to this message

"stbenge" <myu### [at] hotmailcom> schreef in bericht 
news:4c6d6f17@news.povray.org...
>> OK, yes, there are indeed repetitions, alignments and oriented gaps. I 
>> agree with you that this is not perfectly random.
>
> I'm probably just nitpicking :/

No, I think you are quite right in putting the problem foreward. It forces 
us to rethink and being more critical. That said, and me being also lazy, I 
can live with the halton code because its weakness is not going to be too 
obvious in most of my scenes and it is an easy way out to mix different 
objects without too much overlapping problems. Obviously, the weakness is 
less visible to the observer in a 3D situation.

> I'm not sure that the time it takes to parse large sets is really worth 
> it. See the image I posted in p.b.i.:
>
http://news.povray.org/povray.binaries.images/thread/%3C4c6d67d5%40news.povray.org%3E/
>

Ideally, that is what we all should want of course :-)  It is the *perfect* 
result.

> It took 23 minutes, 36 seconds to parse. Out of the 50,000 tests I gave it 
> to perform, only a mere 3,065 succeeded. To me, this is unacceptable. If 
> you were to populate a landscape with rocks or trees, you would need more 
> points than that. To make matters worse, the parse time goes up with each 
> new point added. I even used two optimizations. In one, a point stops 
> trying to be placed after the first overlap. The other one bails out 
> completely after failing to place a new random point n consecutive times. 
> I didn't use the latter for that render. If I had, the parse time wouldn't 
> have been as long, but there would have been fewer points. If, after all 
> this you still want some code, I'll go ahead and finish the file-writing 
> routines, which is the easy part.

That seems indeed to be the trade-off of this method.  :-(

Thomas

Post a reply to this message

"Thomas de Groot" <tDOTdegroot@interDOTnlANOTHERDOTnet> wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht
> news:4c6d6f17@news.povray.org...
> >> OK, yes, there are indeed repetitions, alignments and oriented gaps. I
> >> agree with you that this is not perfectly random.
> >
> > I'm probably just nitpicking :/
>
> No, I think you are quite right in putting the problem foreward. It forces
> us to rethink and being more critical. That said, and me being also lazy, I
> can live with the halton code because its weakness is not going to be too
> obvious in most of my scenes and it is an easy way out to mix different
> objects without too much overlapping problems. Obviously, the weakness is
> less visible to the observer in a 3D situation.

I'm still struggling to find any time to write more about Halton sequences, but
I've been following you all in this thread, and the binary images posted as
well.

I've dumped a very simple bit of code at:
http://wiki.povray.org/content/User:Edouard

Cheers,
Edouard.

Post a reply to this message

Dre wrote:
> <snip>
>> I'm not sure that the time it takes to parse large sets is really worth 
>> it. See the image I posted in p.b.i.:
>>
http://news.povray.org/povray.binaries.images/thread/%3C4c6d67d5%40news.povray.org%3E/
>>
>> It took 23 minutes, 36 seconds to parse. Out of the 50,000 tests I gave it 
>> to perform, only a mere 3,065 succeeded.
> 
> This is the exact problem I ran into when coding the same sort of thing.  My 
> code works also but it has a very high miss rate, very low success rate and 
> it also takes ages to parse.

Yeah, it's really horrible. POV's SDL wasn't meant to be quick at 
everything...

So far, my C++ implementation is very fast, for not being coded with ASM 
and all. I was able to implement a few speedups, like not using 
sqrt(x*x+y*y) for *every pixel*, but instead making a 1/4 circle 2D 
array and picking from that.

But now I'm stuck on trying to convert an int to a char, and 
vice-versus. It always comes down to something like that with C :( To 
make a utility like this useful, the user need to be able to change 
certain settings... This one might take awhile.

Post a reply to this message

Thomas de Groot wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht 
>> It took 23 minutes, 36 seconds to parse. Out of the 50,000 tests I gave it 
>> to perform, only a mere 3,065 succeeded.
> 
> That seems indeed to be the trade-off of this method.  :-(

The C++ version works very well, and it's super-fast, but now I need to 
make a GUI...

Post a reply to this message

stbenge wrote:
> But now I'm stuck on trying to convert an int to a char, and 
> vice-versus. It always comes down to something like that with C :( To 
> make a utility like this useful, the user need to be able to change 
> certain settings... This one might take awhile.

Just in case somebody was going to reply to this... I can now use chars 
as integers, but I can't make it work for a text box. So far, my 
attempts to place a number as text into a text field produce nothing, 
though the code compiles...

Post a reply to this message

stbenge wrote:
> Just in case somebody was going to reply to this... I can now use chars 
> as integers, but I can't make it work for a text box. So far, my 
> attempts to place a number as text into a text field produce nothing, 
> though the code compiles...

Never mind, I think I've got it working now :\

Post a reply to this message