> 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

> Alain wrote:

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

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