> I have a blob created out of a list of circles of various colors. The

> information is present in a file structure like this:

> <centerX> <centerY> <centerZ> <radius> <color>

That doesn't make much sense. There is no clearly defined 'circle'

with a given 3D center and radius. You either have to specify the

direction of the plane the circle is meant to lie in, or you must mean

spheres, not circles. If you really meant circles, the problem

translates into a 2D simplified version, directly, if you are talking

about the screen image of the blob.

Quote:> A trivial way to solve this is to scan-fill each and every circle.

> Pixels that belong to several circles can be allotted to the one that's

> center is closest to it.

If you're speaking about the 3D case, that doesn't make much sense:

you cannot see the interior of spheres anyway, and the surface will

only have isolated mathematically-precise points that belong to more

than one sphere surface. Those can generally be ignored.

For the 2D case, you'ld have to store the circle number it was

previously filled by, for each pixel, so you can later check wether

the center of another circle covering the same pixel is closer or not.

Quote:> This approach would be of order(n), n = number of circles. I would like

> something that makes it dependent on the area of the final image, and

> not on the number of circles present. I.e., I would like the processing

> to be image order, instead of object order.

Actually, your given approach already *is* image order, as well as

object order. The algorithm is O(N) with N the sum of numbers of

pixels covered by all circles, actually, not just O(n), i.e. if you

increase the resolution of the output image (or the radii of all

circles, by a common factor, equivalently), your circle scan

conversions will create more pixels, and increase time consumption.

This means the O(N) translates into an O(n*r^2), with r the resolution

of the output image.

Unless you make assumptions like in the usual z-buffer complexity

analysis (i.e. the more triangles there are, the smaller they'll

'obviously' be, which makes the number of covered pixels independent

of the number of triangles), I don't think you can ever get an

algorithm that is not object-order, as you call it, i.e. whose runtime

only depends on the output size, not on the number of circles in the

input. Every pixel of the output images can possibly be covered by all

input circles, so they all have to be tested. That means worst-case

complexity will always be O(n), at least.

--

Even if all the snow were burnt, ashes would remain.