![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
In article <38AD605D.D9C23B5A@peak.edu.ee>, Margus Ramst
<mar### [at] peak edu ee> wrote:
> Chris Huff wrote:
> >
> > Have you tried bounding in a tree-like structure?
>
> Any ideas how to construct such a tree structure in POV script?
> Let's say I have a set of points, which I would like to sort into
> distance-based
> subsets. How could I do this efficiently, i.e. without comparing every
> point to
> every other point? An oct-tree? But how?
A tree of unions is the eay I would do it:
union {
union {
union {
union {}
union {}
}
union {
union {}
union {}
}
}
union {
union {
union {}
union {}
}
union {
union {}
union {}
}
}
}
You might be able to make a macro which takes an array of objects as
well as an array of their center positions and sorts them out into this
tree structure. If you use MegaPOV, with min_extent and max_extent, the
second array would be unnecessary.
But there are probably better ways to do this. It isn't my idea, there
were some discussions in these newsgroups a while ago about it...
--
Chris Huff
e-mail: chr### [at] yahoo com
Web page: http://chrishuff.dhs.org/
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Yes, but construct such a tree I would still have to test all points against the
current one, no? I can't construct the tree at generation time, because
consequent points are not necessarily spatially close (I'm talking about an
actual case here).
Perhaps I could start recursively subdividing the points along a set of
planes... But then I would not end up with a constant number of points in a
subset. I would have constant-volume subsets. How could I achieve the former
goal?
Margus
Chris Huff wrote:
>
> You might be able to make a macro which takes an array of objects as
> well as an array of their center positions and sorts them out into this
> tree structure. If you use MegaPOV, with min_extent and max_extent, the
> second array would be unnecessary.
> But there are probably better ways to do this. It isn't my idea, there
> were some discussions in these newsgroups a while ago about it...
>
> --
> Chris Huff
> e-mail: chr### [at] yahoo com
> Web page: http://chrishuff.dhs.org/
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Many thanks, good idea .... I will give it a try
Looking at the Histogram is also most revealing.
What I am seeing is that reducing distant objects is not the only criteria
in speeding up the display.
Much time is also spent with surfaces that are quite close to the camera
especially where the height_field passes under, or around, the camera.
David
Disnel <Dis### [at] linux itam cas cz> wrote in message
news:38AC138C.A5645660@linux.itam.cas.cz...
>
> Instead of bounding, try use #if directive and cut off
> objects too distant from camera, something like:
>
> #declare MaximumDistance= something
>
> #declare CameraPos= <bla, bla, bla>
>
> #macro dist(v1, v2)
> #local dx=v2.x-v1.x;
> #local dy=v2.y-v1.y;
> #local dz=v2.z-v1.z;
> ( sqrt(dx*dx + dy*dy +dz*dz) )
> #end
>
> ...
>
>
> #declare Building1=
> object {
> ...
> }
> #declare Building1pos= <bla, bla, bla>
>
> #if (dist(CameraPos, Building1Pos) < MaximumDistance)
> object { Building1 translate Building1pos }
> #end
>
> Maybe I make some mistake in syntax, but idea is clear, hopefully
>
> Or you can enclose entire object definition in #if statement,
> you will then improve parsing time too.
>
> Disnel
>
> E-Mail: dis### [at] itam cas cz
> Homepage: http://www.itam.cas.cz/~disnel
> ICQ: 20126042
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
In article <38AD84F1.CF309BF6@peak.edu.ee>, Margus Ramst
<mar### [at] peak edu ee> wrote:
> Yes, but construct such a tree I would still have to test all points
> against the current one, no? I can't construct the tree at generation
> time, because consequent points are not necessarily spatially close
> (I'm talking about an actual case here).
> Perhaps I could start recursively subdividing the points along a set
> of planes... But then I would not end up with a constant number of
> points in a subset. I would have constant-volume subsets. How could I
> achieve the former goal?
I am not sure what you mean here...could you clarify?
--
Chris Huff
e-mail: chr### [at] yahoo com
Web page: http://chrishuff.dhs.org/
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Tue, 15 Feb 2000 15:43:29 -0500, Chris Huff
<chr### [at] yahoo com> wrote:
>> The bounding option does not appear to really help
>
>Have you tried bounding in a tree-like structure? Like, if you have a
>line of 8 objects, bound each half of it separately, and subdivide each
>half of it...ok, I am just really bad at explaining this. If you know
>something about programming, it is similar to a binary search tree.
>If you do this, make sure you change the settings so POV doesn't ignore
>your bounded_by statements.
An oct-tree is built recursively by splitting each bounding box in
eight smaller parts, right? How are the three splitting planes
determined? Is the midpoint of the bounding box used or is an adaptive
median approach used? The latter would yield a much more efficient
bounding scheme but the overhead in parse time would almost surely
render any benefits in render time unsibstantial. If this is
implemented in a POV script generating external program, such as
PlantStudio or TreeDesigner or a particle system this should not be
much of a problem.
Peter Popov
pet### [at] tag povray org
ICQ: 15002700
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Fri, 18 Feb 2000 19:44:17 +0200, Margus Ramst <mar### [at] peak edu ee>
wrote:
>Yes, but construct such a tree I would still have to test all points against the
>current one, no? I can't construct the tree at generation time, because
>consequent points are not necessarily spatially close (I'm talking about an
>actual case here).
Try this approach. Let's assume it's points we're working with though
things won't change much for objects:
1. Find the smallest box that encloses all points
2. Put all x-coords in an array and sort it. Do this for y and z as
well.
3. Get the middle point of each array (x,y and z) and form a vector
4. Divide the initial bounding box into eight bounding boxes using the
vector from point 3
5. Recursively repeat the procedure for each child of the parent
bounding box until a recursion limit is reached or no further
subdivision is pointless
Each parent will bound its children. Only the leafs of the oct-tree
will bound actual objects.
Does this make any sense to anyone?
Peter Popov
pet### [at] tag povray org
ICQ: 15002700
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Chris Huff wrote:
>
> I am not sure what you mean here...could you clarify?
>
Basically, what Peter suggests sound like it...
When I have some time I'll check it out and see.
Margus
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Interesting. Approximately what I had in mind. Perhaps weighed averaging
might give a more uniform distribution though... Did I just reinvent an
oct-tree? ;)
I'll have to check if this actually works.
Thanks.
Margus
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
In article <On+tOPJBpDTW19hVUhYU9Bh3Vtgf@4ax.com>, Peter Popov
<pet### [at] usa net> wrote:
> An oct-tree is built recursively by splitting each bounding box in
> eight smaller parts, right? How are the three splitting planes
> determined? Is the midpoint of the bounding box used or is an adaptive
> median approach used?
I wouldn't know, I know very little about bounding structures. I only
know what the most basic form of an oct-tree is.
> The latter would yield a much more efficient bounding scheme but the
> overhead in parse time would almost surely render any benefits in
> render time unsibstantial. If this is implemented in a POV script
> generating external program, such as PlantStudio or TreeDesigner or a
> particle system this should not be much of a problem.
Is this a disguised hint for a feature in my particle simulator? :-)
--
Chris Huff
e-mail: chr### [at] yahoo com
Web page: http://chrishuff.dhs.org/
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Sat, 19 Feb 2000 00:06:51 +0200, Margus Ramst <mar### [at] peak edu ee>
wrote:
>Interesting. Approximately what I had in mind. Perhaps weighed averaging
>might give a more uniform distribution though...
The median approach is used in color reduction (Adaptive Palette for
PhotoShop users). It is considered the best non-empirical algorithm
for the purpose. It might prove the best in bounding as well.
>Did I just reinvent an oct-tree? ;)
I have no idea, I myself have never seen one :)
>I'll have to check if this actually works.
>Thanks.
Keep us posted.
Peter Popov
pet### [at] usa net
ICQ: 15002700
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |