gdalgorithms-list

Re: [Algorithms] Terrain Normals

[Pai-Hung C. <pa...@ac...>]

Hi,

How can your bilinear filtering method (as depicted below) be used with the
terrain layout (as depicted at bottom, the same as mine)?

Thank you,

Pai-Hung Chen


> I use a form of bilinear filtering to calculate my vertex normals, like
so:
>
> +-----+
> |\ 1 /|
> | \ / |
> |4 X 2|
> | / \ |
> |/ 3 \|
> +-----+
>
> Where the normal of vertex X is the average of the normals of triangles
> 1...4. Note that the above does _not_ represent the actual layout of my
> terrain mesh, which has the following (probably quite familiar) layout:
>
> +-----+
> | /| /|
> |/ |/ |
> +--+--+
> | /| /|
> |/ |/ |
> +-----+
>
> This seems to work when it comes to avoiding the gray bands you are
> referring to.
>
> Hope this helps,
>
> Jim Offerman
>
> Innovade
> - designing the designer
>
> ----- Original Message -----
> From: "Pai-Hung Chen" <pa...@ac...>
> To: <gda...@li...>
> Sent: Monday, August 14, 2000 8:22 AM
> Subject: [Algorithms] Terrain Normals
>
>
> > Hi,
> >
> > I've written a routine to read a bitmap heightfield and construct a
> terrain
> > mesh from it.  I partition each set of four pixels into two triangles
> along
> > the upper-right-to-lower-left diagonal line.  Therefore, for example, a
> 128
> > x 128 bitmap will produce (128-1) x (128-1) x 2 = 32258 triangles using
my
> > method.  For each triangle I caculate its unit face normal.  For each
> vertex
> > of a triangle, I calculate its vertex normal by adding and averaging the
> > face normals of all triangles that share the vertex (in my case a vertex
> can
> > be shared by at most six triangles and at least one triganle) and then
> > normalize the averaged normal, which is used in redering.  My problem is
> > that there are some *horizontal dimmed banding* effects along the
triangle
> > edges of the mesh when rendering in D3D with light cast on it.  Also,
> there
> > are very visible dimmed seams between triangles when light is cast on
it.
> > All these artifacts seem to manifest only when light is cast in large
> angles
> > (i.e. not directly).  Is it because the arrangement of triangles in my
> mesh
> > is too *uniform* (actually they are extremely uniform)?  Or is my
> > calculation of vertex normals incorrect?
> >
> > Thanks in advance,
> >
> > Pai-Hung Chen
> >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Terrain Normals

[Jim O. <j.o...@in...>]

Hi,

> How can your bilinear filtering method (as depicted below) be used with
the
> terrain layout (as depicted at bottom, the same as mine)?

A bit of flexible thinking I guess... Your (and my) terrain representation
is actually just an approximation of the 'actual' terrain (that is, there
are very few places to be found in the universe where a terrain is made up
of countless triangles in a regular grid). This 'flaw' can produce
unrealistic images (gray bands, for instance). By using a different method
to calculate the normals, I kinda masked the problem(*).

(*) I first used all eight surrounding triangles, but I found that using
only four gave nearly the same result, up to the point where it was no
longer visible.

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] normals in skeletal animation

[Vladimir K. <vka...@si...>]

Conor,

> You could always avoid using normals. Often you can use various tricks to
> get nice lighting without them.

Can you explain it a bit ?
But In any case I will need normals for cube- and bumpmapping.

Thanks
vlad

[Algorithms] normals in skeletal animation

[Vladimir K. <vka...@si...>]

Hi,

How to handle normals in skeletal animation?

Currently I use this way :
After loading model I take first frame and calculate all normals.
Then I use inverted bone matrices to transform normals into
some 'pretransformed' state and store it same as offset vectors
(every vertex has list of pre normals for affected bones)

At rendering time for every affected bone I transform this
normals using current bone matrix, multiply to the weight, sum it
and normalize.

In result I get something hm.. :)
In most cases it looks ok but sometimes it looks like some normals
was calculated using incorrect bones.

In any case I think should be much better way for this.
Can anybody recommend something?

Thanks
vlad

[Algorithms] OT: How to read a bitmap of arbitrary size?

[Pai-Hung C. <pa...@ac...>]

Hi,

I have been frustratingly bugged for hours and I decide to resort to the
list.  I want to read a 24-bit bitmap heightfield.  I can correctly read it
as long as the dimension of the bitmap file is in 2's power such as 4x4,
8x8, 16x16, etc.  (But 2x2 doesn't work?!)  In these _normal_ cases, the
*biSizeImage* field of the BITMAPINFOHEADER structure gives me the correct
size of image in bytes.  However, if I create a bitmap of non-2's-power
dimension such as 5x5, 6x6, 7x7, etc., the *biSizeImage* field gives me some
bogus number.  For example, 5x5 yields 80 bytes (5x5x3 = 75 bytes); 6x6
yields 120 bytes (6x6x3 = 108 bytes); 7x7 yields 168 bytes (7x7x3 = 147
bytes).  Could somebody tell me what happened?

Thanks in advance,

Pai-Hung Chen

Re: [Algorithms] OT: How to read a bitmap of arbitrary size?

[Klaus H. <k_h...@os...>]

For Windows BMP files, the pitch must be a multiple of 4 bytes. 5 pixels * 3
bytes = 15 bytes is not a multiple of 4! In such cases, the BMP format uses
the next higher value (that is multiple 4) as the pitch. In this specific
case, the next higher value that is a multiple of 4, is 16. Thus the Windows
BMP format uses a pitch of 16 bytes.
So for a 5x5 BMP you have 5 * (((3 * 5) + 3) & (~3)) = 5 * 16 = 80 bytes.
(Note, that the additional byte is unused).

In order to compute the pitch for a bit-count >= 8, you can use the
following formula:
pitch = ((bytes_per_pixel * pixels_per_row) + 3) & (~3)

biSizeImage then is: biSizeImage = pitch * num_pixel_rows

HTH,
Niki

----- Original Message -----
From: Pai-Hung Chen <pa...@ac...>
To: <gda...@li...>
Sent: Sunday, August 13, 2000 6:57 PM
Subject: [Algorithms] OT: How to read a bitmap of arbitrary size?


> Hi,
>
> I have been frustratingly bugged for hours and I decide to resort to the
> list.  I want to read a 24-bit bitmap heightfield.  I can correctly read
it
> as long as the dimension of the bitmap file is in 2's power such as 4x4,
> 8x8, 16x16, etc.  (But 2x2 doesn't work?!)  In these _normal_ cases, the
> *biSizeImage* field of the BITMAPINFOHEADER structure gives me the correct
> size of image in bytes.  However, if I create a bitmap of non-2's-power
> dimension such as 5x5, 6x6, 7x7, etc., the *biSizeImage* field gives me
some
> bogus number.  For example, 5x5 yields 80 bytes (5x5x3 = 75 bytes); 6x6
> yields 120 bytes (6x6x3 = 108 bytes); 7x7 yields 168 bytes (7x7x3 = 147
> bytes).  Could somebody tell me what happened?
>
> Thanks in advance,
>
> Pai-Hung Chen
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] OT: How to read a bitmap of arbitrary size?

[Pai-Hung C. <pa...@ac...>]

Hi,

That explains everything! :-)  Thanks a lot!  But could you explain what's
the meaning of ((bytes_per_pixel * pixels_per_row) + 3) & (~3), specifically
the ...+ 3) & (~3) part?

Thank you,

Pai-Hung Chen


> For Windows BMP files, the pitch must be a multiple of 4 bytes. 5 pixels *
3
> bytes = 15 bytes is not a multiple of 4! In such cases, the BMP format
uses
> the next higher value (that is multiple 4) as the pitch. In this specific
> case, the next higher value that is a multiple of 4, is 16. Thus the
Windows
> BMP format uses a pitch of 16 bytes.
> So for a 5x5 BMP you have 5 * (((3 * 5) + 3) & (~3)) = 5 * 16 = 80 bytes.
> (Note, that the additional byte is unused).
>
> In order to compute the pitch for a bit-count >= 8, you can use the
> following formula:
> pitch = ((bytes_per_pixel * pixels_per_row) + 3) & (~3)
>
> biSizeImage then is: biSizeImage = pitch * num_pixel_rows
>
> HTH,
> Niki
>
> ----- Original Message -----
> From: Pai-Hung Chen <pa...@ac...>
> To: <gda...@li...>
> Sent: Sunday, August 13, 2000 6:57 PM
> Subject: [Algorithms] OT: How to read a bitmap of arbitrary size?
>
>
> > Hi,
> >
> > I have been frustratingly bugged for hours and I decide to resort to the
> > list.  I want to read a 24-bit bitmap heightfield.  I can correctly read
> it
> > as long as the dimension of the bitmap file is in 2's power such as 4x4,
> > 8x8, 16x16, etc.  (But 2x2 doesn't work?!)  In these _normal_ cases, the
> > *biSizeImage* field of the BITMAPINFOHEADER structure gives me the
correct
> > size of image in bytes.  However, if I create a bitmap of non-2's-power
> > dimension such as 5x5, 6x6, 7x7, etc., the *biSizeImage* field gives me
> some
> > bogus number.  For example, 5x5 yields 80 bytes (5x5x3 = 75 bytes); 6x6
> > yields 120 bytes (6x6x3 = 108 bytes); 7x7 yields 168 bytes (7x7x3 = 147
> > bytes).  Could somebody tell me what happened?
> >
> > Thanks in advance,
> >
> > Pai-Hung Chen
> >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>

Re: [Algorithms] OT: How to read a bitmap of arbitrary size?

[John S. <jse...@ho...>]

That part is simply rounding up to the nearest 4.

John Sensebe
jse...@ho...
Quantum mechanics is God's way of ensuring that we never really know what's
going on.

Check out http://members.home.com/jsensebe to see prophecies for the coming
Millennium!


----- Original Message -----
From: "Pai-Hung Chen" <pa...@ac...>
To: <gda...@li...>
Sent: Sunday, August 13, 2000 1:31 PM
Subject: Re: [Algorithms] OT: How to read a bitmap of arbitrary size?


> Hi,
>
> That explains everything! :-)  Thanks a lot!  But could you explain what's
> the meaning of ((bytes_per_pixel * pixels_per_row) + 3) & (~3),
specifically
> the ...+ 3) & (~3) part?
>
> Thank you,
>
> Pai-Hung Chen
>
>
> > For Windows BMP files, the pitch must be a multiple of 4 bytes. 5 pixels
*
> 3
> > bytes = 15 bytes is not a multiple of 4! In such cases, the BMP format
> uses
> > the next higher value (that is multiple 4) as the pitch. In this
specific
> > case, the next higher value that is a multiple of 4, is 16. Thus the
> Windows
> > BMP format uses a pitch of 16 bytes.
> > So for a 5x5 BMP you have 5 * (((3 * 5) + 3) & (~3)) = 5 * 16 = 80
bytes.
> > (Note, that the additional byte is unused).
> >
> > In order to compute the pitch for a bit-count >= 8, you can use the
> > following formula:
> > pitch = ((bytes_per_pixel * pixels_per_row) + 3) & (~3)
> >
> > biSizeImage then is: biSizeImage = pitch * num_pixel_rows
> >
> > HTH,
> > Niki
> >
> > ----- Original Message -----
> > From: Pai-Hung Chen <pa...@ac...>
> > To: <gda...@li...>
> > Sent: Sunday, August 13, 2000 6:57 PM
> > Subject: [Algorithms] OT: How to read a bitmap of arbitrary size?
> >
> >
> > > Hi,
> > >
> > > I have been frustratingly bugged for hours and I decide to resort to
the
> > > list.  I want to read a 24-bit bitmap heightfield.  I can correctly
read
> > it
> > > as long as the dimension of the bitmap file is in 2's power such as
4x4,
> > > 8x8, 16x16, etc.  (But 2x2 doesn't work?!)  In these _normal_ cases,
the
> > > *biSizeImage* field of the BITMAPINFOHEADER structure gives me the
> correct
> > > size of image in bytes.  However, if I create a bitmap of
non-2's-power
> > > dimension such as 5x5, 6x6, 7x7, etc., the *biSizeImage* field gives
me
> > some
> > > bogus number.  For example, 5x5 yields 80 bytes (5x5x3 = 75 bytes);
6x6
> > > yields 120 bytes (6x6x3 = 108 bytes); 7x7 yields 168 bytes (7x7x3 =
147
> > > bytes).  Could somebody tell me what happened?
> > >
> > > Thanks in advance,
> > >
> > > Pai-Hung Chen
> > >
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> >
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] OT: How to read a bitmap of arbitrary size?

[Klaus H. <k_h...@os...>]

Well, this is where it gets very much off-topic :) So I'll try to answer
your question with a single mail. If you still don't get it, then please
mail me off-line.

First off, let's define:
bpr = bytes_per_pixel * pixels_per_row

Now assume that you want to round bpr *down* to the nearest 4, if and only
if bpr is not a multiple of 4. This can be done, by setting the two
least-significant bits of bpr to 0. Assuming that you use a postive 32-bit
integer, you can achieve this as follows:

bpr_rounded_down = bpr & (~3);
<=>
bpr_rounded_down = bpr & 0xFFFFFFFC;

However, in order to compute the pitch, you need to round *up* to the
nearest 4, if and only if bpr is not a multiple of 4. In order to do this,
we first add 3 to bpr, and call the result bpr'. Examples:

bpr = 16 => bpr' = bpr + 3 = 19
bpr = 17 => bpr' = bpr + 3 = 20
bpr = 18 => bpr' = bpr + 3 = 21
bpr = 19 => bpr' = bpr + 3 = 22
bpr = 20 => bpr' = bpr + 3 = 23

Now you use the above approach, and round bpr' *down* to the nearest 4
(which results in the pitch you are looking for):

bpr = 16 => pitch = bpr' & (~3) = 16
bpr = 17 => pitch = bpr' & (~3) = 20
bpr = 18 => pitch = bpr' & (~3) = 20
bpr = 19 => pitch = bpr' & (~3) = 20
bpr = 20 => pitch = bpr' & (~3) = 20

So the formula for the pitch is:
pitch = (bpr + 3) & (~3);

Another way to implement this would be:
pitch = (bpr + 3) - ((bpr + 3) % 4);
<=>
pitch = (bpr + 3) - ((bpr + 3) & 3);

HTH,
Niki

PS: I'm not going to answer the question, why you need to add 3, instead of
4 :)
PPS: Binary operations, like AND, OR, XOR, NOT, et cetera, are very useful,
and it makes a lot of sense to learn more about them.

----- Original Message -----
From: Pai-Hung Chen <pa...@ac...>
To: <gda...@li...>
Sent: Sunday, August 13, 2000 8:31 PM
Subject: Re: [Algorithms] OT: How to read a bitmap of arbitrary size?


> Hi,
>
> That explains everything! :-)  Thanks a lot!  But could you explain what's
> the meaning of ((bytes_per_pixel * pixels_per_row) + 3) & (~3),
specifically
> the ...+ 3) & (~3) part?
>
> Thank you,
>
> Pai-Hung Chen

Re: [Algorithms] Terrain Normals

[Klaus H. <k_h...@os...>]

----- Original Message -----
From: Pai-Hung Chen <pa...@ac...>
To: <gda...@li...>
Sent: Monday, August 14, 2000 11:55 PM
Subject: Re: [Algorithms] Terrain Normals


> > That's simply a greenish-blue alpha-polygon (no texture). It basically
is
> > one big square polygon that cuts through the whole terrain. The reason
why
> > that does not look too crappy is, because you see the lit terrain
beneath
> > the water.
>
> (1) Is it because "the terrain beneath the water is lit" that make the
water
> look good?

Yes, because it looks as if the lit terrain beneath the water adds
color-variations to the water surface. Normally, however, I'd use an
alpha-blended texture (probably animated) for the water surface. The only
reason why there's no texture in the screenshots is because I'm too lazy to
write a portable image file reader for OpenGL.

> The terrain is lit either with or without lightmap.  Does that
> make a difference?

Yes it does make a difference. Sometime ago, I also tried to use
Direct3D's/OpenGL's lighting engine to render *rough* non-LOD terrain mesh.
I wasn't able to get rid of those Gouraud shading artifacts (as I already
expected), even though the vertex normals were correct. Since then I'm using
pre-lit surface textures, which completely eliminate these artifacts. In
addition, you can use Phong shading and other nice lighting tricks. Also,
pre-lit textures can make the terrain look as if there was a very high
triangle count.

> (2) How do you make the terrain mesh?  It looks like ROAM.

It's not ROAM. It's an implementation of S. Röttger's "Real-Time Generataion
of Continuous Levels of Detail for Height Fields" algorithm. The
implementation is sort of stupid though, as it uses single triangle fans
(glVertex3f <g>) to render the mesh. I could have used a faster method, but
I intend to make the source code publicly available in order to show an
exact implementation of Röttger's paper, and things like vertex-buffered
indexed triangle lists would just destroy the purpose of the sample.

Which leads me to a question... Maybe someone can answer this off-line. Is
there a better *portable* timer than clock()?

HTH,
Niki

[Algorithms] VIPM Strips

[Charles B. <cb...@cb...>]

I just read the paper "Skip Strips" by El-Sana et.al.
which seems to be a much-overlooked work on VDPM.  I
found it as part of the course notes in the simplification
course on the Siggraph 2k CD.

It's an interesting read, though quite archaic.
They make some clever data structures to speed up the
inherently slow algorithm of VDPM.

Anyway, it gave me ideas about how to strip VIPM.  In
fact, it's so easy, it's ridiculous.  Generate your
vertices in collapse order.  Create an optimal Indexed
Triangle Strip over those vertices, using duplicated
vertex indices to make it one single strip over the
entire mesh.  When you do a collapse, do it just like
normal VIPM, except that rather than changing indices
in a list of indexed triangles, you're changing them
in a list of indexed strips; it's just the same operation: 
	IndexList[ vsplit->changeIndex ] = newVertIndex;
You also can't reduce the number of triangles by two,
because the two collapsed triangles may not be at the
end of the list, and their verts are needed to continue
the strip on either side.

After you collapse some number of verts, you switch down
to a new strip which is optimized on that number of
verts.  This takes a cue from Tom Forsyth, and something
like power-of-2 sets of triangle strips are recommended.
For example, a mesh with 5000 triangles at full LOD might
have strip lists for {5000,3000,2000,1000,500,250,125}
triangles.

Now note that the memory usage of this scheme is almost
identical to that of normal VIPM (!!).  If you use power-
of-2 triangle strip list changes, then you only duplicate
the number of indices stored, and by using strips instead
of lists, you roughly half the storage needed.

The disadvantage of this scheme is obvious : your triangle
count stays the same until you swap down to a shorter strip.
In that sence, it's a lot like discrete LOD.  The difference
is that you're still doing collapses one by one, and reducing the
vertex count one by one, and virtually eliminating popping.

Finally, what's the advantage?  I'm not sure.  This method
is surely faster than conventional VIPM.  On the other hand,
I'm not sure it compares terribly well to Tom's idea of
stripped prefixes and tri-list suffixes.

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

Re: [Algorithms] GJK

[Pierre T. <p.t...@wa...>]

> provided have been simplified already from cramer's rule.  I'm not seeing
> why the new "closest point in simplex to origin" is perpendicular to the
> affine combination of the points in simplex, so I've stopped at that point

Maybe this can help:
http://www.codercorner.com/gjk00.jpg
http://www.codercorner.com/gjk01.jpg

Feel free to correct possible little errors (Ron?).

Pierre

Re: [Algorithms] GJK

[Will P. <wi...@cs...>]

> > provided have been simplified already from cramer's rule.  I'm not seeing
> > why the new "closest point in simplex to origin" is perpendicular to the
> > affine combination of the points in simplex, so I've stopped at that point
> 
> Maybe this can help:
> http://www.codercorner.com/gjk00.jpg
> http://www.codercorner.com/gjk01.jpg

You have nice handwriting, and it's much better than mine. :)

Mathematically, it make sense.  It makes me wonder if there is any
intuition about it, or they just make that observation about
perpendicularity (is that a word?) for no particular reason.

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will