Thread: [Algorithms] Terminology Questions

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Hi,

Could someone briefly explain what is "voxel" and "wavelet" in the context
of 3D graphics to get me started?

Thank you,

Pai-Hung Chen

www.flipcode.com just published a basic tutorial on the subject 
of voxel renderers. Worth a look. The exact link is:

http://www.flipcode.com/voxtut/

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Marcelo A. Camelo, Eng. <ca...@ep...> - Software Developer

Para facilitar a visualizasao em sistemas nao conformantes com a
norma iso-8859, este email nao utiliza caracteres de acentuacao.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=                        

On Wed, 23 Aug 2000, Pai-Hung Chen wrote:

> Hi,
> 
> Could someone briefly explain what is "voxel" and "wavelet" in the context
> of 3D graphics to get me started?
> 
> Thank you,
> 
> Pai-Hung Chen
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Hi ...

i got a question about glLockArraysEXT in OpenGl ... since its limited to
4096 indices i got a problem with my vertex-list ...

my vertex-list contains like 100.000 vertexes ...
Im drawing stuff with DrawElements ( ... )  using an compiled index-list for
every frame (created by an Octree ...)

now how can i handle the 4096 indice-limit of LockArrayEXT without spliting
my Vertex-List in THAT little pieces ...

sorry if i didnt explain it enough but i hope ... someone who worked with
that already can help me

bye

Maik

> Hi ...
>
> i got a question about glLockArraysEXT in OpenGl ... since its limited to
> 4096 indices i got a problem with my vertex-list ...
>
> my vertex-list contains like 100.000 vertexes ...
> Im drawing stuff with DrawElements ( ... )  using an compiled index-list
for
> every frame (created by an Octree ...)
>
> now how can i handle the 4096 indice-limit of LockArrayEXT without
spliting
> my Vertex-List in THAT little pieces ...
>
> sorry if i didnt explain it enough but i hope ... someone who worked with
> that already can help me
>
First of all, that is a vertex limit. Indices are generally unlimited.
Second of all, that limit is really only the limit at which the extension
"optimises" the array via locking. Otherwise, its just like calling a normal
vertex array call.

Conor Stokes

yup ... thats what i mean ...
but what do i do if my vertex array is tooo big?

an unaccelerated vertex array is way too slow in compare to the accelerated
version ...
I get a performance increase of 30 % using LockArrayEXT ...
without it ... vertex arrays are not even a real improvement to im-opengl

so i guess there is no other way than splitting the vertex array : (?

-----Ursprüngliche Nachricht-----
Von: gda...@li...
[mailto:gda...@li...]Im Auftrag von
Conor Stokes
Gesendet: Donnerstag, 24. August 2000 18:01
An: gda...@li...
Betreff: Re: [Algorithms] OpenGL LockArrayEXT ... workaround

> Hi ...
>
> i got a question about glLockArraysEXT in OpenGl ... since its limited to
> 4096 indices i got a problem with my vertex-list ...
>
> my vertex-list contains like 100.000 vertexes ...
> Im drawing stuff with DrawElements ( ... )  using an compiled index-list
for
> every frame (created by an Octree ...)
>
> now how can i handle the 4096 indice-limit of LockArrayEXT without
spliting
> my Vertex-List in THAT little pieces ...
>
> sorry if i didnt explain it enough but i hope ... someone who worked with
> that already can help me
>
First of all, that is a vertex limit. Indices are generally unlimited.
Second of all, that limit is really only the limit at which the extension
"optimises" the array via locking. Otherwise, its just like calling a normal
vertex array call.

Conor Stokes

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Maik Gerth wrote:
> yup ... thats what i mean ...
> but what do i do if my vertex array is tooo big?
>
> an unaccelerated vertex array is way too slow in compare to the accelerated
> version ...
> I get a performance increase of 30 % using LockArrayEXT ...
> without it ... vertex arrays are not even a real improvement to im-opengl
>
> so i guess there is no other way than splitting the vertex array : (?

Splitting the your vertex arrays just before locking them can be very tedious, since you have test
triangle of the element array, so that no triangle get splitted and no index references a vertex of
the wrong buffer. It's much easier to do that in an early stage of the rendering pipeline, for
example, for curves it's easy to split them at tesselation time so that the number of vertexes keeps
lower than your desired number. You could also build your characters and objects using different
meshes, instead of a single one.

For gf cards the best workaround for that problem is using vertex array ranges to DMA-copy your data
and overcome CVAs restrictions.

however i think this discussions belongs to the OpenGL gamedev list instead to this one.

Ignacio Castano
ca...@cr...

Conor Stokes wrote:
> First of all, that is a vertex limit. Indices are generally unlimited.
> Second of all, that limit is really only the limit at which the extension
> "optimises" the array via locking. Otherwise, its just like calling a normal
> vertex array call.

are you sure 4096 is the maxium size for optimized compiled vertex arrays?
I just though it was 1024, since q3 uses 1K vertex buffers (according to Brian Sharp's conference).

Ignacio Castano
ca...@cr...

> are you sure 4096 is the maxium size for optimized compiled vertex arrays?
> I just though it was 1024, since q3 uses 1K vertex buffers (according to Brian
> Sharp's conference).
Hi,

I wrote a little test app to find this out.
And at least on my G4 with an ATI Rage128, the maximum size depends on the
vertex data you use.
The buffer seems to be 64kb big.
So if you pass 2 TextureUV and one Vertex with 3 floats you get
65536 / (4*(3+2+2)) = 2340 vertices.

bye joe

you wrote:
> > are you sure 4096 is the maxium size for optimized compiled vertex arrays?
> > I just though it was 1024, since q3 uses 1K vertex buffers (according to
>Brian Sharp's conference).

My conference?

Any information I have on Q3A is pretty much hearsay from Brian Hook.  Or 
maybe you're referring to Brian Hook, not Brian Sharp?  We're more 
different than our last names: I never worked for id. ;-)

At 11:30 AM 8/25/00 +0800, you wrote:
>It depends on the accelerator generally. Remember Brian worked on the 3dfx
>ogl drivers, which may mean his 1k number was based on those, rather than
>other drivers. I think most of the T&L cards are 4/8k.

So first of all, I don't see any actual defined limit (in the 
EXT_compiled_vertex_array spec) to the number of vertices you can 
lock.  The original poster should have no problem locking 100,000 
vertices.  If it's an issue of what implementations optimize for, that's 
kind of lame to write to that, especially because that's totally volatile 
and will probably change in most drivers before you ship.

In the existing 3dfx driver, at least, it'll optimize whatever you throw at 
it.  Sure, that's transformation happening on the CPU, but it guarantees 
that you don't end up retransforming verts.

The downside to that is the hypothetical case where someone locks a 30 
million vert array, and the driver allocates a ton of memory.  It can't be 
any more than the app already has allocated, but it's nonetheless potential 
for a lot of memory allocation.  So for future work it's being donw a 
different way, but it won't "not optimize" the arrays if they're over some 
size.

I'm not really sure what the motivation would be for a driver to not 
optimize arrays over a certain size.  I mean, they could only pretransform 
a set number and treat any more as regular verts to be 
transformed.  Hmm.  Especially if it's a hardware T&L implementation, where 
you'd obviously want to have a tiered caching system in the driver already, 
capable of locked arrays on the host bigger than your hardware cache.  I'm 
confused.

So, what was the original poster asking about?  Why couldn't he lock all 
his verts?  A driver crash?  A slowdown?  A spec misreading?

-Brian
==========
GLSetup, Inc.

didnt you say its off topic to speak about that opengl stuff : )

but anyway .... i was just askin if theres a "common way ..." to get the
full performance boost out of the LockArrayEXT optimization ....

even the latest nvidia - drivers (at least for my tnt2) dont optimize
anything if your vertex-array-size is over a special value ... --> you got
to split your vertex-arrays in little pieces (4096 vectors in my case ) or
you WONT get the performance boost of ... 25%
with a vertex-array-size over that its kinda useless to use this function on
a TNT2 ...

thats the problem ...

but as some people said ... there is no other way to get full performance
boost than splitting the one huge vertex array in alot of little ones ...

so i guess this  topic is finished =)

-----Ursprungliche Nachricht-----
Von: gda...@li...
[mailto:gda...@li...]Im Auftrag von
Brian Sharp
Gesendet: Freitag, 25. August 2000 05:58
An: gda...@li...
Betreff: Re: [Algorithms] OpenGL LockArrayEXT ... workaround

you wrote:
> > are you sure 4096 is the maxium size for optimized compiled vertex
arrays?
> > I just though it was 1024, since q3 uses 1K vertex buffers (according to
>Brian Sharp's conference).

My conference?

Any information I have on Q3A is pretty much hearsay from Brian Hook.  Or
maybe you're referring to Brian Hook, not Brian Sharp?  We're more
different than our last names: I never worked for id. ;-)

At 11:30 AM 8/25/00 +0800, you wrote:
>It depends on the accelerator generally. Remember Brian worked on the 3dfx
>ogl drivers, which may mean his 1k number was based on those, rather than
>other drivers. I think most of the T&L cards are 4/8k.

So first of all, I don't see any actual defined limit (in the
EXT_compiled_vertex_array spec) to the number of vertices you can
lock.  The original poster should have no problem locking 100,000
vertices.  If it's an issue of what implementations optimize for, that's
kind of lame to write to that, especially because that's totally volatile
and will probably change in most drivers before you ship.

In the existing 3dfx driver, at least, it'll optimize whatever you throw at
it.  Sure, that's transformation happening on the CPU, but it guarantees
that you don't end up retransforming verts.

The downside to that is the hypothetical case where someone locks a 30
million vert array, and the driver allocates a ton of memory.  It can't be
any more than the app already has allocated, but it's nonetheless potential
for a lot of memory allocation.  So for future work it's being donw a
different way, but it won't "not optimize" the arrays if they're over some
size.

I'm not really sure what the motivation would be for a driver to not
optimize arrays over a certain size.  I mean, they could only pretransform
a set number and treat any more as regular verts to be
transformed.  Hmm.  Especially if it's a hardware T&L implementation, where
you'd obviously want to have a tiered caching system in the driver already,
capable of locked arrays on the host bigger than your hardware cache.  I'm
confused.

So, what was the original poster asking about?  Why couldn't he lock all
his verts?  A driver crash?  A slowdown?  A spec misreading?

-Brian
==========
GLSetup, Inc.

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Hi all,

I have a problem that I don't understand. I have the following line of
source in my implementation of Woo's "Fast Ray-Box Intersection":

hitpoint[i] = rayOrg[i] + maxT[whichPlane] * rayDir[i];

hitpoint, rayOrg, maxT, and rayDir are all arrays with three floating-point
values (indices 0 to 2). Now here are some values:

i = 2 (which is a valid index)
whichPlane = 0 (also a valid index)
rayOrg[i] = -2
maxT[whichPlane] = 2.82843
rayDir[i] = 0.707107

These are all very valid values, and the result should now be:
hitpoint[i] = -2 + 2.82843 * 0.707107 = 2.65201e-06

However, the debugger says, that
hitpoint[i] = -6.8457097e-008

Okay, so I thought that maybe this is a precision problem. I tried doubles,
but I got the same wrong value. Then I thought, that there might be
something wrong hitpoint[i], so I replaced that with a local double
variable, but the result is still wrong.

Why? I cannot believe that 2.65201e-06 is too small to be represented as a
double-precision floating-point value. Can someone explain this to me? Or do
you see a bug in the above C line? If you don't believe me, then I'm very
well willing to upload the code (very small), and you can step through it,
and see for yourselves.

Niki

Never mind... The VC+ 6 Debugger just displayed a completely wrong
floating-point value. A simple printf() displayed the correct one. The
helped me to make the code work... finally. Just had to subtract/add a small
epsilon from/to the AABB's min/max points.

Niki

----- Original Message -----
From: Klaus Hartmann <k_h...@os...>
To: <gda...@li...>
Sent: Saturday, August 26, 2000 8:25 AM
Subject: [Algorithms] Problem with Woo's "Fast Ray-Box Intersection"

> Hi all,
>
> I have a problem that I don't understand. I have the following line of
> source in my implementation of Woo's "Fast Ray-Box Intersection":
>
> hitpoint[i] = rayOrg[i] + maxT[whichPlane] * rayDir[i];
>
> hitpoint, rayOrg, maxT, and rayDir are all arrays with three
floating-point
> values (indices 0 to 2). Now here are some values:
>
> i = 2 (which is a valid index)
> whichPlane = 0 (also a valid index)
> rayOrg[i] = -2
> maxT[whichPlane] = 2.82843
> rayDir[i] = 0.707107
>
> These are all very valid values, and the result should now be:
> hitpoint[i] = -2 + 2.82843 * 0.707107 = 2.65201e-06
>
> However, the debugger says, that
> hitpoint[i] = -6.8457097e-008
>
> Okay, so I thought that maybe this is a precision problem. I tried
doubles,
> but I got the same wrong value. Then I thought, that there might be
> something wrong hitpoint[i], so I replaced that with a local double
> variable, but the result is still wrong.
>
> Why? I cannot believe that 2.65201e-06 is too small to be represented as a
> double-precision floating-point value. Can someone explain this to me? Or
do
> you see a bug in the above C line? If you don't believe me, then I'm very
> well willing to upload the code (very small), and you can step through it,
> and see for yourselves.
>
> Niki
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

something might bite you later on in that book

before you check out something in it, make sure you test it against this
http://www.acm.org/pubs/tog/GraphicsGems/Errata.GraphicsGems

here's the raybox code if anyone is currently working on it ;)
it has the fix
http://www.acm.org/tog/GraphicsGems/gems/RayBox.c

entire listing from the series in a -listed fashion
http://www.acm.org/tog/GraphicsGems/gems.html

peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Klaus
Hartmann
Sent: Saturday, August 26, 2000 1:26 AM
To: gda...@li...
Subject: [Algorithms] Problem with Woo's "Fast Ray-Box Intersection"

Hi all,

I have a problem that I don't understand. I have the following line of
source in my implementation of Woo's "Fast Ray-Box Intersection":

hitpoint[i] = rayOrg[i] + maxT[whichPlane] * rayDir[i];

hitpoint, rayOrg, maxT, and rayDir are all arrays with three floating-point
values (indices 0 to 2). Now here are some values:

i = 2 (which is a valid index)
whichPlane = 0 (also a valid index)
rayOrg[i] = -2
maxT[whichPlane] = 2.82843
rayDir[i] = 0.707107

These are all very valid values, and the result should now be:
hitpoint[i] = -2 + 2.82843 * 0.707107 = 2.65201e-06

However, the debugger says, that
hitpoint[i] = -6.8457097e-008

Okay, so I thought that maybe this is a precision problem. I tried doubles,
but I got the same wrong value. Then I thought, that there might be
something wrong hitpoint[i], so I replaced that with a local double
variable, but the result is still wrong.

Why? I cannot believe that 2.65201e-06 is too small to be represented as a
double-precision floating-point value. Can someone explain this to me? Or do
you see a bug in the above C line? If you don't believe me, then I'm very
well willing to upload the code (very small), and you can step through it,
and see for yourselves.

Niki

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

For interested people, I put a modified version of Andrew Woo's Ray-AABB
intersection test here:

http://www.codercorner.com/RayAABB.cpp

Apparently it is faster than the original code (~20-30% on my machine) and
now even more robust thanks to Niki. Nothing really great, I just rewrote it
slightly, in order for it to be Intel-processor-friendly (yeah Steve, I know
:)

Maybe it can be useful to some of you.

Pierre

I spent a while optimizing this test.
Generally you're going to test a ray against many AABBs.
Instead of doing the divides each time you test a box, just do them once,
and multiply instead.  This is much quicker.
Watch out for axis aligned rays.  One or two of the deltas can be zero, but
luckily this is a special case and you don't even need to do the divide.
For example, if delta.x==0, all you want is: min.x <= origin.x <= max.x.
I do this by swapping to a slower routine if one or more of the delta
components is zero.

Andrew.

At 10:21 PM 8/27/00 +0200, you wrote:
>I got this from nvidia site:
>
>"There is an optimal size for vertex buffers - a fact which is not intuitively obvious.
>You should aim for around 2000 vertices per buffer or for around 64K of RAM used."

First off, the 64k limit is just because 16-bit indices are used for vertices,
and that's a hard limit to stay for quite some time, I imagine.  As for that 2k
vertices per buffer, that was an anomaly of old GeForce drivers, and has been
removed.  Hey NVidia, you need to make a new document on how to optimize for T&L
that doesn't dwell so much on the oddities of the GeForce (which really does
have odd performance characterics which are not typical of Radeon and other
future T&L products, like NV20 presumably).

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com

Charles Bloom wrote:
> First off, the 64k limit is just because 16-bit indices are used for vertices,
> and that's a hard limit to stay for quite some time, I imagine.  As for that 2k
> vertices per buffer, that was an anomaly of old GeForce drivers, and has been
> removed.  Hey NVidia, you need to make a new document on how to optimize for T&L
> that doesn't dwell so much on the oddities of the GeForce (which really does
> have odd performance characterics which are not typical of Radeon and other
> future T&L products, like NV20 presumably).

no, you are right, i took that info from the old document, there's a new one, in which no limit was
mentioned, or if it was, i didn't notice it.

Ignacio Castano
ca...@cr...

I believe that this limit was DMA related, rather than index addressing
related.
I am also under the impression that this limitation is no longer in effect
if using the
latest drivers (and perhaps DX8) ... and yes, the document should be updated
:)

> First off, the 64k limit is just because 16-bit indices are used for
vertices,
> and that's a hard limit to stay for quite some time, I imagine.  As for
that 2k
> vertices per buffer, that was an anomaly of old GeForce drivers, and has
been
> removed.  Hey NVidia, you need to make a new document on how to optimize
for T&L
> that doesn't dwell so much on the oddities of the GeForce (which really
does
> have odd performance characterics which are not typical of Radeon and
other
> future T&L products, like NV20 presumably).

I could be wrong, though ... search DirectX list archives for confirmation
(I think Richard Huddy from nVidia mentioned the fix).

Mark

It depends on the accelerator generally. Remember Brian worked on the 3dfx
ogl drivers, which may mean his 1k number was based on those, rather than
other drivers. I think most of the T&L cards are 4/8k.

Conor Stokes

> Conor Stokes wrote:
> > First of all, that is a vertex limit. Indices are generally unlimited.
> > Second of all, that limit is really only the limit at which the
extension
> > "optimises" the array via locking. Otherwise, its just like calling a
normal
> > vertex array call.
>
> are you sure 4096 is the maxium size for optimized compiled vertex arrays?
> I just though it was 1024, since q3 uses 1K vertex buffers (according to
Brian Sharp's conference).
>
>
> Ignacio Castano
> ca...@cr...
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

By the way, I just realized that this is on the algorithms list.  This 
should be moved to the Ope...@fa... list, in the interest 
of actually keeping lists' meanings intact.  Off-topic threads cause the 
kind of traffic volumes that inspire me to delete all the messages instead 
of read them.  Speaking purely hypothetically; my silence in the past few 
months is totally unrelated.  I swear.  ;-)

-Brian
==========
GLSetup, Inc.

Brian Sharp wrote:
> My conference?
>
> Any information I have on Q3A is pretty much hearsay from Brian Hook.  Or
> maybe you're referring to Brian Hook, not Brian Sharp?  We're more
> different than our last names: I never worked for id. ;-)

hoops, sorry, you are completely right, i meant Brian Hook :-)

> ...
>
> I'm not really sure what the motivation would be for a driver to not
> optimize arrays over a certain size.  I mean, they could only pretransform
> a set number and treat any more as regular verts to be
> transformed.  Hmm.  Especially if it's a hardware T&L implementation, where
> you'd obviously want to have a tiered caching system in the driver already,
> capable of locked arrays on the host bigger than your hardware cache.  I'm
> confused.

yes, that's what happens on the geforce, that has a limit of 65536 vertexes, because indexes must be
lower than that.

I got this from nvidia site:

"There is an optimal size for vertex buffers - a fact which is not intuitively obvious.
You should aim for around 2000 vertices per buffer or for around 64K of RAM used."

"GeForce products require indices to not exceed 65535. If more indices are
necessary, break the object into smaller parts."

PD: i will send this message also to the OpenGL Gamedev list, so if you want to continue this
thread, do it there.

Ignacio Castano
ca...@cr...