"Bill Pragnell" <bil### [at] hotmailcom> wrote:
> The reason you're running out of memory is that every instance you use takes up
> the same memory as the original, so there's no advantage to instancing. Meshes,
> however, are stored just once. All mesh instances are actually just transforms,
> so they take up a minute amount of space.

To get a bit more into depth about what's going on:

There is a certain general per-object memory overhead that pertains to *all*
objects, whether it is a primitive, a CSG union, or even just a copy of a
#declared object.

With most primitives, this overhead greatly outweighs the actual memory
requirements for the pure geometry data; from the tests I did I'd expect
something like a 10:1 overhead for "bare metal" objects, i.e. with nothing but
the geometry data specified.

With meshes, this overhead can be arbitrarily low: If you have just a single
triangle, it will probably be in the 10:1 area, too. If you have ten triangles,
it will be more like 10:10. If you have 1k triangles, it will be something like
10:1k. And so on.

Now this alone wouldn't make meshes much of a memory-saver, as normally an
object will have to have many more triangles than a CSG representation of the
same shape.

However, as mentioned before, the overhead also pertains to copies of #declared
objects, while the geometry data of *some* primitives is *not* copied, and
instead just references the original's data, so costs *no* extra memory at all.
So e.g. 100 copies of a 1k-triangle mesh will have 100x the standard overhead,
but only 1x the triangle data costs.

The best known of these "bulk" objects is mesh (and its alter ego, mesh2).
Others are blob, height_field, lathe, polygon and prism.

The most important thing to know is that CSG unions (and merges and differences)
are *not* among these. If you copy a union comprised of 1000 primitives, you'll
not only pay the general object overhead, but also the costs for a copy of each
of the 1000 elements.

Post a reply to this message

"[GDS|Entropy]" <gds### [at] hotmailcom> wrote:
> Check this out (apologies for the horrific texture):
> I exported this from Bryce and converted with poseray.

>   Finite objects:       145243
> Peak memory used:         158859969 bytes

See? Roughly same number of primitives, yet they cover a much greater portion of
the object, and even cost less per object.

Post a reply to this message

"clipka" <nomail@nomail> wrote in message 
news:web.49b84af5d4fd5b28801985dd0@news.povray.org...
> "[GDS|Entropy]" <gds### [at] hotmailcom> wrote:
>>   Finite objects:      1013230
>> Peak memory used:        1414575125 bytes
>
> I reckon your memory issues are not *per se* due to using a bucketload of 
> CSG
> instead of a few meshes.
>
> I just did a quick test with 10k spheres, with a color-mapped pigment; the
> following might give you some hints how to improve performance:
>
> - With all spheres being generated on-the-fly as scene-level objects, I 
> get a
> peak mem of ~8 MB.
>
> - If I #declare the material first, and use that in my spheres "as is" (no
> translations, rotations or any modifications), peak mem reduces to ~6.5 
> MB.
>
> - If I place the spheres in a union and attach the material only to the 
> union,
> peak mem reduces to ~3.6 MB.
>
> - If I #declare the sphere first, and use translated copies, peak mem goes 
> *UP*
> again to ~6.4 MB!
>
> - Worst thing I got so far was #declare the sphere first with a material, 
> and
> use translated copies, giving me ~12 MB!
>
>
> Another thing I found was that first generating an array with object 
> locations,
> and then creating the objects in a separate pass, is more costly than 
> creating
> an array of objects right away.
>
>
> Still, here's the best advice:
>
>
> - If instead of generating 10000 spheres I #declare a mesh of 100 
> triangles,
> then generate a union of 100 translated copies of it, I get a peak mem of 
> lousy
> ~360 kB, which is just ~170 kB over my "baseline" peak mem. Even with 1000
> copies, I still need just ~1.4 MB peak.
>
> Given that you'll possibly need only one triangle per leaf to replace a 
> pair of
> cones (unless you want to do extreme close-ups - note that you can still
> simulate curvature using a smooth triangle), this should be a good enough 
> model
> to give you a rough estimate of how much memory you can save.
>

Those are very interesting results, not all expected. Apparently, good 
programming concepts are not always good POV concepts... Unfortunately there 
appears to be a performance penalty for writing things extensibly using 
certian methods. :-(

At least this gives a clearer picture of how in any given circumstance to 
optimize for both reusability and efficient memory usage.

Do you (or anyone) have any ideas on how to perform an efficient inside() 
test on not just a single point, but an entire object? You can see the issue 
in my last image post, where even with an inside() test, the actual leaf 
objects occur partially within the cyl at certian points, even when the 
vector/normal reorient may not occur within the cyl.

At first glance it looks like a loop covering an array of vectors within 
min/max extent of whatever object A you are trying to determine may or may 
not occur within another object B is the only option (and then ditch 
creating the object at the vector which would produce such a coincident 
result), but that seems awfully crude. :-\

thanks!
ian

Post a reply to this message

"[GDS|Entropy]" <gds### [at] hotmailcom> wrote in message
> Do you (or anyone) have any ideas on how to perform an efficient inside() 
> test on not just a single point, but an entire object?

Addendum: I have been using things of the format:
  #if (((vectorArray[i].x <= vectorB.x) & (vectorArray[i].x >= vectorA.x)) & 
((vectorArray[i].y <= vectorB.y) & (vectorArray[i].y >= vectorA.y)) & 
((vectorArray[i].z <= vectorB.z) & (vectorArray[i].z >= vectorA.z)))  etc...

Where vector A and B are min/max extents of object being tested 
against...I'm just not sure that this is the best way...

ian

Post a reply to this message

"[GDS|Entropy]" <gds### [at] hotmailcom> wrote:
> Those are very interesting results, not all expected. Apparently, good
> programming concepts are not always good POV concepts... Unfortunately there
> appears to be a performance penalty for writing things extensibly using
> certian methods. :-(

As a matter of fact, I'd partially blame it on POV. With a few changes to
interior design, I guess it should be possible to copy CSG objects, too,
without copying each and every of its components.

At the moment however, it seems to me that the design of the bounding box
mechanism prohibits this (requiring a dedicated bounding box per primitive, and
each box in turn referencing a dedicated primitive object), so changes would
have to be made there.


> Do you (or anyone) have any ideas on how to perform an efficient inside()
> test on not just a single point, but an entire object? You can see the issue
> in my last image post, where even with an inside() test, the actual leaf
> objects occur partially within the cyl at certian points, even when the
> vector/normal reorient may not occur within the cyl.
>
> At first glance it looks like a loop covering an array of vectors within
> min/max extent of whatever object A you are trying to determine may or may
> not occur within another object B is the only option (and then ditch
> creating the object at the vector which would produce such a coincident
> result), but that seems awfully crude. :-\

If I understand you correctly, you'd loop in 3D.

Here's a way to reduce this to 2D at least:

Loop over (or pick random points on) a sphere surface big enough to contain all
of your object A. (make sure you get a roughly homogenous distribution, and
don't waste too much time near the poles)

trace() a ray from each point to the object's bounding box center.

If you get an intersection point, test whether it is inside the other object B.

Repeat until you're confident that you've covered enough of object A's surface.

Note that this way you may miss surface areas in hollows; however, if the other
object is "convex enough", this should not be a problem. It will be a real
issue only if both objects have significant hollows.


Another approach - which should be able to cope with arbitrary hollows - would
be to actually test whether intersection{A B} contains anything. Note however
that this will again create another object. (Mental note for myself: Test
whether #undef frees the memory occupied by the assigned object.)


If you want to place a bucketload of identical objects, you may want to use the
former approach, but shoot the rays at the "unplaced" object and store them in
an array. When you then try to place a copy, you loop through the array,
transform the points according to the intended placement, and do the inside
test for each transformed point. You'd then add the transformed object only if
you're confident that it doesn't intersect. This spares you both a lot of
trace() invocations and some unnecessary instantiating of objects that turn out
to intersect.

Post a reply to this message

"clipka" <nomail@nomail> wrote in message 
news:web.49b92730d4fd5b28f708085d0@news.povray.org...
> As a matter of fact, I'd partially blame it on POV. With a few changes to
> interior design, I guess it should be possible to copy CSG objects, too,
> without copying each and every of its components.

Yup, and those interior design changes would be really nice. I haven't any 
idea how difficult that would be to code, because I've never tried to write 
a raytracer before, but I'm guessing that since no patches fix this, and 
that this has persisted across pov versions...that it ain't so easy. ;-)

> At the moment however, it seems to me that the design of the bounding box
> mechanism prohibits this (requiring a dedicated bounding box per 
> primitive, and
> each box in turn referencing a dedicated primitive object), so changes 
> would
> have to be made there.

Maybe in POV 4 then. :-)

> If I understand you correctly, you'd loop in 3D.

That is what I was thinking.

> Here's a way to reduce this to 2D at least:
>
> Loop over (or pick random points on) a sphere surface big enough to 
> contain all
> of your object A. (make sure you get a roughly homogenous distribution, 
> and
> don't waste too much time near the poles)

Thats still 3d though right?

> trace() a ray from each point to the object's bounding box center.

Ok, so a macro fills an array once with random positions on a sphere, then 
uses that array in a looped call to trace.
I thought trace() accepted only a point and an object? It can accept two 
points?

> If you get an intersection point, test whether it is inside the other 
> object B.

I'm a little fuzzy here...
Assuming I had you right in my sentence above, what result from that trace 
would go within the #if block that would initiate the call to 
inside(myPoint,objectB)?

> Repeat until you're confident that you've covered enough of object A's 
> surface.
>
> Note that this way you may miss surface areas in hollows; however, if the 
> other
> object is "convex enough", this should not be a problem. It will be a real
> issue only if both objects have significant hollows.

It is likely that in real world use hollows are to be expected. I'm trying 
to write this macro suite for use in any scene.

> Another approach - which should be able to cope with arbitrary hollows - 
> would
> be to actually test whether intersection{A B} contains anything. Note 
> however
> that this will again create another object. (Mental note for myself: Test
> whether #undef frees the memory occupied by the assigned object.)

So I would take the sphere position trace data and test that against the 
points in an intersection of every object A (the leaf for instance) with 
object B (column)?
Oh man...this is starting to sound like people won't be able to use these 
macros unless they have a spare Cray XT4 laying around... O_O

> If you want to place a bucketload of identical objects, you may want to 
> use the
> former approach, but shoot the rays at the "unplaced" object and store 
> them in
> an array. When you then try to place a copy, you loop through the array,
> transform the points according to the intended placement, and do the 
> inside
> test for each transformed point. You'd then add the transformed object 
> only if
> you're confident that it doesn't intersect. This spares you both a lot of
> trace() invocations and some unnecessary instantiating of objects that 
> turn out
> to intersect.

A bucket load of objects is to be expected.
Ok, so I perform the spherical trace/intersection test once, then 
reorient_trans() the object, test inside() against object B?

Gah! I hate word problems! ;-D

You watch...just as soon as I get all comfortable with SDL v3.7 (or v4) will 
drop and I'll have to relearn everything. lol!

ian

Post a reply to this message

"[GDS|Entropy]" <gds### [at] hotmailcom> wrote:
> "clipka" <nomail@nomail> wrote in message
> > trace() a ray from each point to the object's bounding box center.
>
> Ok, so a macro fills an array once with random positions on a sphere, then
> uses that array in a looped call to trace.

Or you could just do it on the fly.

> I thought trace() accepted only a point and an object? It can accept two
> points?

Trace takes an object id, a start point, a direction, and (optionally) a
previously-#declared vector in which it stores the surface normal at the point
found.

> > If you get an intersection point, test whether it is inside the other
> > object B.
>
> I'm a little fuzzy here...
> Assuming I had you right in my sentence above, what result from that trace
> would go within the #if block that would initiate the call to
> inside(myPoint,objectB)?

The aforementioned normal vector is set to <0,0,0> if the trace fails to hit
anything. Test the length of this vector using vlength().

Bill

Post a reply to this message

"[GDS|Entropy]" <gds### [at] hotmailcom> wrote:
> > Here's a way to reduce this to 2D at least:
> >
> > Loop over (or pick random points on) a sphere surface big enough to
> > contain all
> > of your object A. (make sure you get a roughly homogenous distribution,
> > and
> > don't waste too much time near the poles)
>
> Thats still 3d though right?

Yeah, what I meant was that I only have to loop over 2 variables (latitude and
longitude instead of 3 (X, Y and Z).

> > trace() a ray from each point to the object's bounding box center.
>
> Ok, so a macro fills an array once with random positions on a sphere, then
> uses that array in a looped call to trace.
> I thought trace() accepted only a point and an object? It can accept two
> points?

Um... sorry if I confused you. To be precise, I should have written "trace() a
ray from each point in the direction of the center" - whatever direction that
is for the particular point. It's easy to compute that direction from the point
P and the center C as (C-P).


> > If you get an intersection point, test whether it is inside the other
> > object B.
>
> I'm a little fuzzy here...
> Assuming I had you right in my sentence above, what result from that trace
> would go within the #if block that would initiate the call to
> inside(myPoint,objectB)?

You mean how to test whether trace() did find an intersection at all? Pass an
(initialized!) normal vector variable to the macro, and afterwards check
whether it is non-zero (i.e. check for vlength(myNormal) > 0).

> > Repeat until you're confident that you've covered enough of object A's
> > surface.
> >
> > Note that this way you may miss surface areas in hollows; however, if the
> > other
> > object is "convex enough", this should not be a problem. It will be a real
> > issue only if both objects have significant hollows.
>
> It is likely that in real world use hollows are to be expected. I'm trying
> to write this macro suite for use in any scene.

Sure, it's a trade-off between speed and quality. But in situations like your
vine macro, chances are the "entangled" object's walls are much thicker than a
leaf's total size, so this should be a non-issue for most cases, and in any
case better than not testing at all (and faster than an exhaustive test).

> > Another approach - which should be able to cope with arbitrary hollows -
> > would
> > be to actually test whether intersection{A B} contains anything. Note
> > however
> > that this will again create another object. (Mental note for myself: Test
> > whether #undef frees the memory occupied by the assigned object.)
>
> So I would take the sphere position trace data and test that against the
> points in an intersection of every object A (the leaf for instance) with
> object B (column)?
> Oh man...this is starting to sound like people won't be able to use these
> macros unless they have a spare Cray XT4 laying around... O_O

For POV, generating an intersection object isn't really such a big deal. The
only *possible* issue is that it requires memory that *might* not be freed when
no longer needed - I didn't test yet.

After all, behind the scenes, POV just basically creates a CSG container object
with references to the elements, and only performs any calculations on it when
trace() is called (or the object is rendered on the screen). And as it happens,
for CSG intersections POV actually uses an algorithm very similar to the one I
outlined before: It simply computes the itersections of the ray with each
component object, tests which of these are inside all other components, and
ultimately picks the closest of all these.

In a way, POV never really creates the intersection object - it just performs a
smart combination of ray-intersection- and inside-tests for all the primitives
involved.

> Ok, so I perform the spherical trace/intersection test once, then
> reorient_trans() the object, test inside() against object B?

Well, almost but not quite, so let's try get this more precise:

- You perform the spherical trace/intersection test once for object A (the one
you intend to place copies of)
- For each candidate placement...
-- you compute the transform { reorient_trans(...) translate ... } you intend to
use for the placement
-- you inside()-test the respective vtransform() of the points against object B
(the one near to which you intend to place the object A copies)
-- if you find that none of them is inside, you do the actual placement using
the transform {...} of the object to be placed.

> You watch...just as soon as I get all comfortable with SDL v3.7 (or v4) will
> drop and I'll have to relearn everything. lol!

Hopefully that one will be easier then ;)

Post a reply to this message