Hi,
I created a bunch of cylinders with a while loop and the rand() function.
But some of the cylinders are overlapping like in this picture:
http://alien23.de/test4/cylinders.jpg

The code I used was this:

#declare  zufall_1= seed (1199);
#declare  zufall_2= seed (342);

#declare ab=.09;  /// abstand

#declare Loop_x =0;

#declare Loop_x_end =9;

union {
#while (Loop_x < Loop_x_end)
        #declare Loop_y =0;
        #declare Loop_y_end =9;
        #while (Loop_y < Loop_y_end)

 #if (even (Loop_y))
                object { cyl  translate
<-.08+Loop_x*ab+rand(zufall_1)/15+Loop_x*.05 ,
Loop_y*ab+rand(zufall_1)/15+Loop_y*.035 , 0>   }

           #else
              object { cyl  translate <.1+Loop_x*ab-rand(zufall_1)/1+Loop_x*.05
, Loop_y*ab+rand(zufall_1)/16+Loop_y*.025 , 0> }
           #end

        #declare Loop_y=Loop_y+1;
        #end

#declare Loop_x=Loop_x+1;
#end
}

------------------------------------------------------
By now I've spent hours trying out other values for the cylinders' translation.
But when I use other values together with rand() I can prevent the cylinders
from overlapping but then everything looks too orderly.

So I basically want the bunch of cylinders to look like in the picture just
without the 4 or 5 overlapping cylinders.

I know it might work with the trace function to check whether they overlap and
so I read through Jonathan Hunt's pebbles.pov where he uses this.
But I found it very difficult and I don't know how too adapt the trace function
to my scene.

Or maybe it is possible to put all the translation data into an output file, and
manually edit the overlapping cylinders and then reimport it? But I have no clue
how to do this either.


Best wishes,

Simone

Post a reply to this message

Simone <inf### [at] alienenterprisesde> wrote:
> So I basically want the bunch of cylinders to look like in the picture just
> without the 4 or 5 overlapping cylinders.

  Two possible solutions:

1) Develop a complicated algorithm in SDL which checks for the intersection
   of cylinders and which skips creating those cylinders which intersect
   with existing ones.

2) Since there are only a few intersecting cylinders, make a manual exception
   list in the form of hard-coded loop index values (in other words, when
   the loop counter reaches such a value, the coordinates of the cylinder
   are calculated as normal, but the cylinder itself will not be
   instantiated). You could use an array for this.

-- 
                                                          - Warp

Post a reply to this message

"Simone" <inf### [at] alienenterprisesde> wrote:

> Hi,
> I created a bunch of cylinders with a while loop and the rand() function.
> But some of the cylinders are overlapping like in this picture:
> http://alien23.de/test4/cylinders.jpg
>
>I've spent hours trying out other values for the cylinders' translation.
> But when I use other values together with rand() I can prevent the cylinders
> from overlapping but then everything looks too orderly.
>
> So I basically want the bunch of cylinders to look like in the picture just
> without the 4 or 5 overlapping cylinders.
>
> I know it might work with the trace function to check whether they overlap and
> so I read through Jonathan Hunt's pebbles.pov where he uses this.
> But I found it very difficult and I don't know how too adapt the trace function
> to my scene.
>
> Or maybe it is possible to put all the translation data into an output file, and
> manually edit the overlapping cylinders and then reimport it? But I have no clue
> how to do this either.

Hi Simone!

Can I suggest a different function than rand() for placing the cylinders - there
is a mathematical set of functions call low discrepancy sequences, and the
simplest one of those to implement in POV macros is a Halton Sequence. The
output looks like the output from rand(), but the positions don't overlap (the
positions it produces just fill in the spaces, so the points get more and more
closely packed).

The code is:

#macro halton( index, base )
 #local out = 0.0;
 #local fraction = 1.0 / base;
 #local i = index;
 #while( i > 0 )
  #local remainder = mod( i, base );
  #local out = out + (fraction * remainder);
  #local i = int(i / base);
  #local fraction = fraction / base;
 #end

 out
#end

and you call it with a integer value that simply increases - e.g. a loop counter
(1,2,3,4,5,6...) - and a prime number as the base (2, 3, 5 etc - the smaller
ones give more pleasing results for what you are wanting to do)

You can create another macro to output a 2D coord:

#macro halton2D( n )
 #local baseX = 2;
 #local baseY = 3;
 < halton( n, baseX ), halton( n, baseY ), 0 >
#end


then you could place the cylinders with something like this:

union {
#declare num_cylinders = 100;
#declare i = 0;
#while( i < num_cylinders )
 object { cyl  translate halton2D( i ) * some_scale_value }
 #declare i = i + 1;
#end
}


You can also place objects in full 3D space with a helper like:

#macro halton3D( n )
 #local baseX = 2;
 #local baseY = 3;
 #local baseZ = 5;
 < halton( n, baseX ), halton( n, baseY ), halton( n, baseZ ) >
#end


Cheers,
Edouard.

Post a reply to this message

On 15/08/2010 9:58 PM, Edouard wrote:
> Hi Simone!
>
> Can I suggest a different function than rand() for placing the cylinders - there
> is a mathematical set of functions call low discrepancy sequences, and the
> simplest one of those to implement in POV macros is a Halton Sequence. The
> output looks like the output from rand(), but the positions don't overlap (the
> positions it produces just fill in the spaces, so the points get more and more
> closely packed).
>
> The code is:
>

Thanks for that Edouard it looks very interesting.

--

Best Regards,
	Stephen

Post a reply to this message

Le 2010-08-15 14:24, Simone a écrit :
> Hi,
> I created a bunch of cylinders with a while loop and the rand() function.
> But some of the cylinders are overlapping like in this picture:
> http://alien23.de/test4/cylinders.jpg
>
> The code I used was this:
>
> #declare  zufall_1= seed (1199);
> #declare  zufall_2= seed (342);
>
> #declare ab=.09;  /// abstand
>
> #declare Loop_x =0;
>
> #declare Loop_x_end =9;
>
> union {
> #while (Loop_x<  Loop_x_end)
>          #declare Loop_y =0;
>          #declare Loop_y_end =9;
>          #while (Loop_y<  Loop_y_end)
>
>   #if (even (Loop_y))
>                  object { cyl  translate
> <-.08+Loop_x*ab+rand(zufall_1)/15+Loop_x*.05 ,
> Loop_y*ab+rand(zufall_1)/15+Loop_y*.035 , 0>    }
>
>             #else
>                object { cyl  translate<.1+Loop_x*ab-rand(zufall_1)/1+Loop_x*.05
> , Loop_y*ab+rand(zufall_1)/16+Loop_y*.025 , 0>  }
>             #end
>
>          #declare Loop_y=Loop_y+1;
>          #end
>
> #declare Loop_x=Loop_x+1;
> #end
> }
>
> ------------------------------------------------------
> By now I've spent hours trying out other values for the cylinders' translation.
> But when I use other values together with rand() I can prevent the cylinders
> from overlapping but then everything looks too orderly.
>
> So I basically want the bunch of cylinders to look like in the picture just
> without the 4 or 5 overlapping cylinders.
>
> I know it might work with the trace function to check whether they overlap and
> so I read through Jonathan Hunt's pebbles.pov where he uses this.
> But I found it very difficult and I don't know how too adapt the trace function
> to my scene.
>
> Or maybe it is possible to put all the translation data into an output file, and
> manually edit the overlapping cylinders and then reimport it? But I have no clue
> how to do this either.
>
>
> Best wishes,
>
> Simone
>
>
>
>
>
>
Yet another possibility:

First, you need to create two set of cylinders. One will be the one that 
is visible, the second will never be viewed and you never give it any 
texture.
The cylinders in the second set will be twice the radius of the first 
and slightly longer.

Next, as you create your cylinders, you make inside teste against the 
previour large cylinders. If the test is positive, it means that you 
have overlaping objects. Ignore that coordinate and chose another.

The extra computing should be acceptable in your case as you don't seem 
to have that many cylinders, 81 to 100 cylinders is still "small".

Then, you can also place the cylinders in a regular gird and jitter them 
somewhat. It can be acceptable if you have comparatively small cylinders 
in a large gird. Here, you only need to set the random displacement just 
large enough so that the cylinders can at most just touch.



Alain

Post a reply to this message

Stephen wrote:

> > ... simplest one of those to implement in POV macros is a Halton Sequence ...
>
> Thanks for that Edouard it looks very interesting.

Halton Sequences are really interesting and useful - I happened to be instant
messaging a friend in London a couple of weeks ago and mentioned that I used
them all the time, and he pointed to me to a sketch he did for SIGGraph on them!
Take a look if you are interested - it's the one entitled "Fast Object
Distribution" on this page: http://www.andrewwillmott.com/s2007

Until I looked at his sketch I hadn't realised the property that each subsequent
value in the sequence is guaranteed to be almost maximally distance from the
previous one, and that you can use that to drive variations like object colour
or size (so the same types of tree are close to each other, but big trees are
always interspersed with small trees, etc). Really fascinating stuff.

I'd love to find the time to write up an article in the Wiki on them for POVRay,
but it's hard finding time with two young kids :-)

Cheers,
Edouard.

Post a reply to this message

Thanks to all of you for the great advice!
I will consider all of it and try around a little to improve my poor POV-Ray
skills when it comes to things like arrays, macros and the like ...

The halton sequence is really a cool piece of code, I tried it and it renders
very quickly. I can imagine it's also useful for all kinds of things, like
abstract cityscapes, floating objects and things like that.
At first it seemed to me really miraculous how it worked, but I managed to put
the output values in a text object and now I slowly start to understand the
workings of macros a little, I hope.


Best wishes,

Simone

Post a reply to this message

"Edouard" <pov### [at] edouardinfo> schreef in bericht 
news:web.4c688dc1d03a138b20e671e70@news.povray.org...
> Until I looked at his sketch I hadn't realised the property that each 
> subsequent
> value in the sequence is guaranteed to be almost maximally distance from 
> the
> previous one, and that you can use that to drive variations like object 
> colour
> or size (so the same types of tree are close to each other, but big trees 
> are
> always interspersed with small trees, etc). Really fascinating stuff.

These are interesting thoughts indeed. I certainly shall have to experiment 
with this. Thank you!

>
> I'd love to find the time to write up an article in the Wiki on them for 
> POVRay,
> but it's hard finding time with two young kids :-)

True. Put them to work on POV-Ray candy ;-)

Thomas

Post a reply to this message

On 16/08/2010 2:00 AM, Edouard wrote:
> I'd love to find the time to write up an article in the Wiki on them for POVRay,
> but it's hard finding time with two young kids:-)
>

As Thomas said, this will require experimenting with. :-D

And if you can find time to make two young kids then doing a Wiki 
article will be a breeze ;-)


-- 

Best Regards,
	Stephen

Post a reply to this message

Simone wrote:

> At first it seemed to me really miraculous how it worked, but I managed to put
> the output values in a text object

Note that there is also a #debug directive for text stream output.

Post a reply to this message

Edouard wrote:
> Can I suggest a different function than rand() for placing the cylinders - there
> is a mathematical set of functions call low discrepancy sequences, and the
> simplest one of those to implement in POV macros is a Halton Sequence. The
> output looks like the output from rand(), but the positions don't overlap (the
> positions it produces just fill in the spaces, so the points get more and more
> closely packed).

At first I was really excited by this, but then I started looking it up, 
and there appears to be a lot of repetition in Halton point sets... I'll 
have to try the code you provided to see how well it distributes the points.

I usually just test new elements against all other elements and place a 
point where there is enough space by evaluating the radii. It's a slow 
method, but must only be performed once per-application if the points 
are saved to an .inc file.

Sam

Post a reply to this message

Christian Froeschlin wrote:
> Simone wrote:
> 
>> At first it seemed to me really miraculous how it worked, but I 
>> managed to put
>> the output values in a text object
> 
> Note that there is also a #debug directive for text stream output.

This feature should not be underestimated... I might still be staring 
confusedly into my monitor if not for the ability to #debug my code O_x

Post a reply to this message

stbenge <myu### [at] hotmailcom> wrote:
> Christian Froeschlin wrote:
> > Simone wrote:
> >
> >> At first it seemed to me really miraculous how it worked, but I
> >> managed to put
> >> the output values in a text object
> >
> > Note that there is also a #debug directive for text stream output.
>
> This feature should not be underestimated... I might still be staring
> confusedly into my monitor if not for the ability to #debug my code O_x


Yes, thanks.
I have used this once, when I didn't know the size of some chess pieces and
where they are. But it took me some time before I understood that #debug is the
right thing for this because it sounded to me like the program should repair
some bugs ... :) , but obviously it's used for many other things.

"... but must only be performed once per-application if the points
are saved to an .inc file."

Do you use the #debug feature for this too? Or how do I tell pov-ray to put such
points into an include file?

Best wishes,

Simone

Post a reply to this message

On 16/08/2010 8:49 PM, Simone wrote:
> Do you use the #debug feature for this too? Or how do I tell pov-ray to put such
> points into an include file?
>

Have a read of the help section, "3.2.2.3  File I/O Directives".
And section "3.2.1.7.3  String Functions".

A lot to take in but ask if you need help.


-- 

Best Regards,
	Stephen

Post a reply to this message

"stbenge" <myu### [at] hotmailcom> schreef in bericht 
news:4c697734@news.povray.org...
> At first I was really excited by this, but then I started looking it up, 
> and there appears to be a lot of repetition in Halton point sets... I'll 
> have to try the code you provided to see how well it distributes the 
> points.

How can you tell that, Sam? My tests appear not to overlap but I have no way 
(yet) to really be sure. What I am pretty sure about is that an additional 
collision test is necessary if number and size of the objects become too 
large for a given space, though. Otherwise, the bare locations seem not to 
repeat themselves within a given sequence, but I may be totally wrong of 
course.

>
> I usually just test new elements against all other elements and place a 
> point where there is enough space by evaluating the radii. It's a slow 
> method, but must only be performed once per-application if the points are 
> saved to an .inc file.

Yes, that is slow, but it works :-)

Thomas

Post a reply to this message

Thomas de Groot wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht 
> news:4c697734@news.povray.org...
>> At first I was really excited by this, but then I started looking it up, 
>> and there appears to be a lot of repetition in Halton point sets... I'll 
>> have to try the code you provided to see how well it distributes the 
>> points.
> 
> How can you tell that, Sam? My tests appear not to overlap but I have no way 
> (yet) to really be sure. What I am pretty sure about is that an additional 
> collision test is necessary if number and size of the objects become too 
> large for a given space, though. Otherwise, the bare locations seem not to 
> repeat themselves within a given sequence, but I may be totally wrong of 
> course.

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.

I typically test for pattern repetition by crossing my eyes at an image 
and seeing if the two images "lock in." Anybody can beat those "how many 
differences can you spot?" picture games in seconds if they would just 
cross their eyes... but what would be the fun in that? :)

>> I usually just test new elements against all other elements and place a 
>> point where there is enough space by evaluating the radii. It's a slow 
>> method, but must only be performed once per-application if the points are 
>> saved to an .inc file.
> 
> Yes, that is slow, but it works :-)

And it works well. It can handle circles of varying radii with 
absolutely no overlaps. I have tried a similar method in raster space, 
which works pretty well and allows for different shapes (like rotated, 
scaled rectangles), but the accuracy goes down because of the granularity.

Sam

Post a reply to this message

Stephen <mca### [at] aolDOTcom> wrote:
> On 16/08/2010 8:49 PM, Simone wrote:
> > Do you use the #debug feature for this too? Or how do I tell pov-ray to put such
> > points into an include file?
> >
>
> Have a read of the help section, "3.2.2.3  File I/O Directives".
> And section "3.2.1.7.3  String Functions".
>
> A lot to take in but ask if you need help.
>
>
> --
>
> Best Regards,
>  Stephen

File I/O Directives ... that's it. Thanks!

Best wishes

Simone

Post a reply to this message

"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.?

Thomas

Post a reply to this message

How should I write a gaussian distribution using halton (in 2D and 3D)? I 
tried a couple of things but it is not right.

Thomas

Post a reply to this message

"Thomas de Groot" <tDOTdegroot@interDOTnlANOTHERDOTnet> wrote:
> How should I write a gaussian distribution using halton (in 2D and 3D)? I
> tried a couple of things but it is not right.

I'd try rejection sampling - create a function that gives the gaussian
probability distribution, then rand() to compare against the function and reject
the halton value if that test fails.

Cheers,
Edouard.

Post a reply to this message

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

"stbenge" <myu### [at] hotmailcom> schreef in bericht 
news:4c6ee306$1@news.povray.org...
> 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...

Come on, Sam! You can do it! You rule!  :-)

Thomas

Post a reply to this message

Thomas de Groot wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht 
> news:4c6ee306$1@news.povray.org...
>> 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...
> 
> Come on, Sam! You can do it! You rule!  :-)

It's getting close... got the (simple) GUI, now I need to tackle 
vector.h, which will probably be the easy part. Thanks for the 
encouragement! :)

Post a reply to this message

Le 2010-08-20 16:14, stbenge a écrit :

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

What's the fastest? sqrt(x*x+y*y) or sqrt(x^2+y^2)
In POV-Ray SDL, the second, as sqrt(pow(x,2)+pow(y,2)), is faster. Don't 
know how it compare in C/C++ or other compiled languages.

May be worth testing.



Alain

Post a reply to this message

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

You're doing a radius comparison, right? You probably don't need to take 
a square root.

  - Slime

Post a reply to this message

Slime wrote:
>> 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.
> 
> You're doing a radius comparison, right? You probably don't need to take 
> a square root.

No, I'm setting specific radii (in pixels) and testing against a 2D 
array using a brute-force method. In POV I was doing radius comparisons. 
At any rate, I'm only having to do the sqrt(x*x+y*y) calculation 128*128 
times when the program starts, to fill an array. It's like 1/4 of a 
cylindrical pigment, and is the maximum circle radius. It's a drop in 
the bucket, really.

Of course, with today's computers I can afford to be so wasteful. Not 
that my program is running at record speeds or anything. Maybe if I knew 
assembly language... :(

Post a reply to this message

Alain wrote:
> Le 2010-08-20 16:14, stbenge a écrit :
>> 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.
> 
> What's the fastest? sqrt(x*x+y*y) or sqrt(x^2+y^2)
> In POV-Ray SDL, the second, as sqrt(pow(x,2)+pow(y,2)), is faster. Don't 
> know how it compare in C/C++ or other compiled languages.
> 
> May be worth testing.
> 
> Alain

Hmm, I was not aware that pow(n,2) was faster than n*n. I'll keep it in 
mind next time the issue comes up. In my program, sqrt(x*x+y*y) is only 
called at the very beginning to fill a small array.

Post a reply to this message

> No, I'm setting specific radii (in pixels) and testing against a 2D
> array using a brute-force method. In POV I was doing radius comparisons.
> At any rate, I'm only having to do the sqrt(x*x+y*y) calculation 128*128
> times when the program starts, to fill an array. It's like 1/4 of a
> cylindrical pigment, and is the maximum circle radius. It's a drop in
> the bucket, really.

Oh, OK. So you're creating an actual image and filling it with circles?

FWIW, you still probably don't need the sqrt. You probably have 
something like

if ( sqrt( x*x + y*y ) < radius )

which can just be

radiusSquared = radius * radius;
...
if ( x*x + y*y < radiusSquared )

>
> Of course, with today's computers I can afford to be so wasteful. Not
> that my program is running at record speeds or anything. Maybe if I knew
> assembly language... :(

Knowing assembly language isn't really the key to making faster 
programs. I mean, if you're an expert at assembly, then you can probably 
push your program's speed a little bit, but modern compilers do a pretty 
good job already. You're more likely to improve your program's speed in 
other ways. For instance, by learning how to avoid cache misses by 
keeping commonly accessed data close together or by changing your 
algorithm to avoid jumping around in memory. Also, if there's any chance 
that there's a better algorithm for what you're trying to do (and it 
seems there always is), then it would be better to spend your time 
finding it than rewriting the current algorithm in assembly.

  - Slime

Post a reply to this message

"stbenge" <myu### [at] hotmailcom> schreef in bericht 
news:4c6ff729$1@news.povray.org...
> It's getting close... got the (simple) GUI, now I need to tackle vector.h, 
> which will probably be the easy part. Thanks for the encouragement! :)

It's worth the while, isn't it?

Thomas

Post a reply to this message

Le 2010-08-21 20:28, stbenge a écrit :
> Alain wrote:
>> Le 2010-08-20 16:14, stbenge a écrit :
>>> 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.
>>
>> What's the fastest? sqrt(x*x+y*y) or sqrt(x^2+y^2)
>> In POV-Ray SDL, the second, as sqrt(pow(x,2)+pow(y,2)), is faster.
>> Don't know how it compare in C/C++ or other compiled languages.
>>
>> May be worth testing.
>>
>> Alain
>
> Hmm, I was not aware that pow(n,2) was faster than n*n. I'll keep it in
> mind next time the issue comes up. In my program, sqrt(x*x+y*y) is only
> called at the very beginning to fill a small array.

If you only use it a few times, the speed gain is low. If you use it a 
LOT, like in the function of an isosurface, then the difference get very 
appreciable.
It's faster because every time you need the value of a variable, you 
have to search for it and retreive it's value. Also, evaluating an 
integer power is almost as quick as doing a multiplication.


Alain

Post a reply to this message

Le 2010-08-21 20:41, Slime a écrit :
>
>> No, I'm setting specific radii (in pixels) and testing against a 2D
>> array using a brute-force method. In POV I was doing radius comparisons.
>> At any rate, I'm only having to do the sqrt(x*x+y*y) calculation 128*128
>> times when the program starts, to fill an array. It's like 1/4 of a
>> cylindrical pigment, and is the maximum circle radius. It's a drop in
>> the bucket, really.
>
> Oh, OK. So you're creating an actual image and filling it with circles?
>
> FWIW, you still probably don't need the sqrt. You probably have
> something like
>
> if ( sqrt( x*x + y*y ) < radius )
>
> which can just be
>
> radiusSquared = radius * radius;
> ...
> if ( x*x + y*y < radiusSquared )
>
>>
>> Of course, with today's computers I can afford to be so wasteful. Not
>> that my program is running at record speeds or anything. Maybe if I knew
>> assembly language... :(
>
> Knowing assembly language isn't really the key to making faster
> programs. I mean, if you're an expert at assembly, then you can probably
> push your program's speed a little bit, but modern compilers do a pretty
> good job already. You're more likely to improve your program's speed in
> other ways. For instance, by learning how to avoid cache misses by
> keeping commonly accessed data close together or by changing your
> algorithm to avoid jumping around in memory. Also, if there's any chance
> that there's a better algorithm for what you're trying to do (and it
> seems there always is), then it would be better to spend your time
> finding it than rewriting the current algorithm in assembly.
>
> - Slime

Many times, assembly can be slower that compiled. The reason is that 
compiler can do optimisations based on the prehemptive nature of any 
modern CPU and the concurent nature of the FPU, taking into acount the 
effective timing of every opcode. Then, whenever you use the FPU, you 
need to take into acount it's own pipe and timing and cram operation 
that don't need the results to fill up the wait time.
To beat a decent compiler, you need to be a crack assembler. To beat a 
good compiler, you need to be a genius with an excellent understanding 
of all the subtelties of your CPU and FPU.


Alain

Post a reply to this message

Thomas de Groot wrote:
> "stbenge" <myu### [at] hotmailcom> schreef in bericht 
> news:4c6ff729$1@news.povray.org...
>> It's getting close... got the (simple) GUI, now I need to tackle vector.h, 
>> which will probably be the easy part. Thanks for the encouragement! :)
> 
> It's worth the while, isn't it?

One way or another, it is :) I 'm learning some new things, so that's a 
plus. Hopefully it will be a useful tool when I'm finished. I've got the 
file-writing stuff down; it was as easy as I thought it might be... But 
it seems projects like these are never as close to being finished as 
they appear. There's also the POV-end to consider. I've written some 
POV-code for dynamically choosing items from an arbitrarily-sized object 
array based on the diameter of the circles. This should make it possible 
to easily make transitions between, say, grass to shrubs to oaks to 
conifers. Now I need to implement an option to use an image for input in 
my C code. If I can't get it to work, I'll just make a poor 
implementation in POV and release it as-is.

Post a reply to this message

Slime wrote:
> 
>> No, I'm setting specific radii (in pixels) and testing against a 2D
>> array using a brute-force method. In POV I was doing radius comparisons.
>> At any rate, I'm only having to do the sqrt(x*x+y*y) calculation 128*128
>> times when the program starts, to fill an array. It's like 1/4 of a
>> cylindrical pigment, and is the maximum circle radius. It's a drop in
>> the bucket, really.
> 
> Oh, OK. So you're creating an actual image and filling it with circles?

Yes, though I'm not testing the image, as that would be slow, but rather 
am only writing to it for display purposes.

> FWIW, you still probably don't need the sqrt. You probably have 
> something like
> 
> if ( sqrt( x*x + y*y ) < radius )

Actually, it's like this:

  if(circular[abs(x)][abs(y)]<csize)

Where "circular" is the precalculated array.

> which can just be
> 
> radiusSquared = radius * radius;
> ...
> if ( x*x + y*y < radiusSquared )

Ah yes, that would work, and would save a heap of unnecessary 
calculations from being performed.

>> Of course, with today's computers I can afford to be so wasteful. Not
>> that my program is running at record speeds or anything. Maybe if I knew
>> assembly language... :(
> 
> Knowing assembly language isn't really the key to making faster 
> programs. I mean, if you're an expert at assembly, then you can probably 
> push your program's speed a little bit, but modern compilers do a pretty 
> good job already. You're more likely to improve your program's speed in 
> other ways. For instance, by learning how to avoid cache misses by 
> keeping commonly accessed data close together or by changing your 
> algorithm to avoid jumping around in memory. Also, if there's any chance 
> that there's a better algorithm for what you're trying to do (and it 
> seems there always is), then it would be better to spend your time 
> finding it than rewriting the current algorithm in assembly.

Hmm, I'll have to investigate more fully what it means to keep 
commonly-accessed data "close together." I don't have many pointers, and 
my (one) vector is well-accounted for...

I guess I was thinking back to the (not so distant) past when I saw some 
incredible QBasic demos running at impossible speeds. They used ASM, of 
course, since there was no way of doing those things with normal 
interpretive language techniques.

Post a reply to this message

> Hmm, I'll have to investigate more fully what it means to keep
 > commonly-accessed data "close together." I don't have many pointers, and
 > my (one) vector is well-accounted for...

Well, that sounds fairly simple. I don't really understand what your 
algorithm is, but if you posted it we could probably help find room for 
improvement.

Post a reply to this message

"stbenge" <myu### [at] hotmailcom> schreef in bericht 
news:4c716c76$1@news.povray.org...
> One way or another, it is :) I 'm learning some new things, so that's a 
> plus. Hopefully it will be a useful tool when I'm finished. I've got the 
> file-writing stuff down; it was as easy as I thought it might be... But it 
> seems projects like these are never as close to being finished as they 
> appear. There's also the POV-end to consider. I've written some POV-code 
> for dynamically choosing items from an arbitrarily-sized object array 
> based on the diameter of the circles. This should make it possible to 
> easily make transitions between, say, grass to shrubs to oaks to conifers. 
> Now I need to implement an option to use an image for input in my C code. 
> If I can't get it to work, I'll just make a poor implementation in POV and 
> release it as-is.

Thinking about plant distribution, there is always some clumpiness leaving 
gaps, crowding trees or shrubs together and so on.

Thomas

Post a reply to this message

Simone wrote:
> Hi,
> I created a bunch of cylinders with a while loop and the rand() function.
> But some of the cylinders are overlapping like in this picture:
> http://alien23.de/test4/cylinders.jpg

If you are still open to other options, I have released a program to 
generate sets of non-overlapping circles: 
http://news.povray.org/povray.binaries.utilities/thread/%3Cweb.4c7453bd99210acbf151112e0%40news.povray.org%3E/

Sam

Post a reply to this message

There are two simple methods I use:

1) Use regular grid positions with random perturbation offsets.
    You can guarantee non-overlap by simply making the offset range
    less than the grid spacing. This works better for objects of
    similar size.

2) Use a mask bitmap (stencil). This takes more memory and more coding,
    but basically you record the placement of objects in the mask, and
    then consult the mask when placing more objects. Fortunately, the
    mask only needs to be 1-bit per pixel.

Ray

Post a reply to this message