gdalgorithms-list

Re: [Algorithms] texture-based fog idea

[Keith Z.L. <ke...@dr...>]

How about a link to the bitmap, I'd be interested in looking at it.
:-)

Keith
DreamForge

"Pallister, Kim" wrote:

> I have a couple bits to add:
>
> - Brian's got the right way to look at it. A texture is just a lookup table
> for a function. This can be useful for getting HW to do perpixel stuff with
> more complicated functions that add and modulate. e.g. put a sine wave into
> a texture, put noise into a texture.
>
> - I did an example of the above using the matrox g400 bumpenvmap, which is a
> texture dependant lookup (one texture influences the tex coords for the
> lookup of another texture. Feeding a noise texture as the bump map, and a 1D
> sine wave as the other texture, I was able to get something like:
>
> color = Sin(x + noise(x,y))
>
> Which looks like marble. I'm tempted to attach a bitmap to this
> mail(MUST...OBEY...CHARTER)
>
> - Anytime you are doing something with a 1D texture, think about what you
> could do with the other dimension if it were a 2D texture. There are some
> cases where they might be related or independant.
>
> An example: I recently did a test I'll call Kim's Cheezy Terrain Test. I was
> generating a heightfield with a number of octaves of noise, and wanted to do
> the typical 'mountain tops are white, below that is green, etc. Fine, put
> those color values in a 1D texture and that's it. It occurred to me that I
> could modulate that with a gradient on the other access, and do:
>
> vertex.tu = vertex.y * (scale factor)
> vertex.tv = ambient light + Dot product( vertex.normal, light vector)
>
> and I get vertex lighting modulating the terrain colors.
>
> (I know that's a bad example given that vertex lighting is so cheap,
> especially in HW, but I just wanted to make a point)
>
> Kim Pallister
>
> We will find a way or we will make one.
>                      - Hannibal
>
> > -----Original Message-----
> > From: Conor Stokes [mailto:cs...@tp...]
> > Sent: Thursday, July 06, 2000 9:56 AM
> > To: Algorithms List
> > Subject: Re: [algorithms] texture-based fog idea
> >
> >
> > > >One whacky idea I've been playing around with (and to some
> > > >good effect) is actually using a dither pattern built into the
> > > >fog texture. I found with some good dithering effects, the fog
> > > >looked much smoother
> > >
> > > Interesting idea.  How about a DirtyPunk's Column on this?
> > >
> > I'll probably put it in the techfile. I've got a column
> > update in the works
> > :) I know I keep saying that, but honestly I do :)
> >
> > Conor Stokes
> >
> >
> >
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> To unsubscribe from this list, send an e-mail to
> "do...@3d..." with the following body:
>
> leave algorithms
>
> Web Archives of this list can be found at:
> http://216.101.212.117/cgi/doweb.exe?list=algorithms
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Re: [Algorithms] Scale, camera, and world units and how it affects perception

[Stephen J B. <sj...@li...>]

On Fri, 14 Jul 2000, Kirk Hammond wrote:

> This has been something I have mulled for some time.  What _really_
> denotes scale in a 3D engine?  I currently run a ROAM based terrain
> engine with units like tanks, planes, yada yada.  Obviously the scale of
> objects moving by the viewer affects the perception of speed and size of
> a world unit.
> 
> So, this would lead one to believe that as long as you are consistent
> with your units (as I am), then everything would be fine.  And indeed,
> if I put a 2000 m cruiser in space and fly in a ship at 200 m/s it takes
> 10 sec to fly by the ship.  Fine and dandy.
 
Probiding you are utterly consistant and use the same units everywhere,
it doesn't matter what units you use.

> (e.g. if you have in the same 3D engine the view from an ant on the
> ground and a view from a human walking above...  aren't there viewport
> changes from the two vantages beyond moving the camera around and the
> fact that the camera is higher above the ground on the human?

Since you position the camera (and near/far clip planes) using the same
units that you use for drawing the scene, it won't matter.

> I mean,
> if the human stuck his eye on the ground level with the ant's viewpoint,
> doesn't the human still see more of the terrain than does the ant?)

No.  It seems that way because you physically can't get your head that
low - and your eyes won't focus that close (because they are so large).
But in OpenGL you don't have those nasty practical limitations - so it's
not a problem.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

[Algorithms] zone/portal partitioning

[Oskar L. <osk...@me...>]

Hi,

I've got a small problem regarding partitioning of polygons into
zones separated by portals.

Say, I have two sets of polygons of which one set contains the 
geometry and the other set contains portals. I want to partition
the geometry set into disjoint subsets, zones, to be connected by 
portals.

I guess this problem doesn't have a solution for the general case, 
but if I can assume some kind of continuity between the geometry-
polygons, i.e. the polygons might form one or a few meshes making
up rooms and corridors, there should be cases where this problem is
solvable.

This is what my current solution method looks like:
1) Build an adjacency graph of the geometry-polygons, i.e. each
   node is a polygon and graph-edges correspond to shared edges. 
2) For each portal, cut the graph at the edges that match those of
   the portal. 

This should result in a lot of subgraphs. The polygons of subgraphs
that are the result of portal cuts can easily be assigned to zones,
but what of the other subgraphs?

These subgraphs could be other geometry, that is no part of a 
continuous wall-ceiling-floor-mesh. How do I choose which zone 
these polygons should belong to? Polygons that intersect portals 
could be forbidden or maybe clipped and I guess I could do some kind 
of intersection testing between the volumes made up of the current 
zones and the unassigned polygons, but this seems rather untrivial.

Before trying to do this the hard way, I would like to know if there 
are any better or more general algorithms for this last part or for 
the entire problem.


Hälsningar,
  Oskar Linde

RE: [Algorithms] Particles system

[Matthew D. <MD...@ac...>]

Hi Kurt,

I'd had a quick look (as Im busy at the mo') for this program 'Universe' but
have not been able to find it.  Do you have a URL, perhaps?

Cheers,
Matt.


> -----Original Message-----
> From: Kurt Miller [mailto:ku...@fl...]
> Sent: Friday, July 14, 2000 17:40
> To: Algorithms List
> Subject: Re: [Algorithms] Particles system
> 
> 
> 
> >>to create textures for special effects (flares, explosions, 
> energy beans,
> >>Does someone know a good tool to create the textures? Or 
> some algoritm, so
> I
> >>can create then by myself?
> 
> You may want to check out a program called "Universe", which 
> is shareware.
> It makes the creation of flares, coronas, nebulae etc point-and-click
> simple, with plenty of parameters to alter.   You can run a search on
> hotfiles.com for the demo version.
> 
> As for explosions and sparks, I've seen a few CDs for sale, 
> with photo-
> realistic (ie, sampled from film) explosion animations and such.
> Perhaps you should search around for something like that.
> 
> HTH
> 
> 
> Kurt Miller
> 3D Coder/Enthusiast
> http://www.flipcode.com
> 
> 
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> To unsubscribe from this list, send an e-mail to
> "do...@3d..." with the following body:
> 
> leave algorithms
> 
> Web Archives of this list can be found at:
> http://216.101.212.117/cgi/doweb.exe?list=algorithms
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 

Re: [Algorithms] Octree leaf neighbours

[Martin G. <bz...@wi...>]

Sorry, it's my fault. I was addressing regular octrees and my point was that
implicit representation lets you avoid the parent links. Of course this does
not apply yo your case. Apologies :)

-----Original Message-----
From: Sam Kuhn <sa...@ip...>
To: gda...@li...
<gda...@li...>
Date: 16 Þëè 2000 ã. 22:40
Subject: Re: [Algorithms] Octree leaf neighbours


>>Martin Gladnishki wrote:
>>And in addition you can save much time if you hold the tree in an array.
>This
>>saves the parent links, too :)
>
>Erm, I mentioned this in my origional post... dont you have to store a 3d
>(i.e. *big*) hash table so you can hash to the neighbours in the array using
>the coordinates of the node you are in?
>How does it save the parent links then?
>
>sam
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] Scale, camera, and world units and how it affect s perception

[Pallister, K. <kim...@in...>]

> (e.g. if you have in the same 3D engine the view from an ant on the
> ground and a view from a human walking above...  aren't there viewport
> changes from the two vantages beyond moving the camera around and the
> fact that the camera is higher above the ground on the human?  I mean,
> if the human stuck his eye on the ground level with the ant's 
> viewpoint,
> doesn't the human still see more of the terrain than does the ant?)

Actually, the human will have a similar type view as that of the ant, from
ground level. An example that points this out is in both real car racing and
in car racing sims, where one of the views you can switch to in playback, or
that they occasionally show on TV is the
camera-by-the-side-of-the-wheel-well-real-close-to-the-ground. Being closer
the the pavement makes the perception of scale different, and thus the speed
is perceived as faster. You also get this if you go go-karting. Though I
wouldn't recommend standing up in a moving go kart to see if your perception
changes :-)

RE: [GDAlgorithms-List] Re: [Algorithms] Scale, camera, and world units and how it affects perception

[Pallister, K. <kim...@in...>]

Probably off-topic, but a neat little tidbit to add. If you are working with
stereo display devices, you can get people to perceive scale differently by
changing the distance between the position of the left & right view
frustums.

The place I saw this trick was in an IMAX movie where they showed you some
people in a boat, and then a miniture replica of the boat. When they zoomed
in on the miniature (which really did look like a 6" model) you saw people
moving and realized it was the same real boat.

The reason this happens is that you interpret the stereo image pair as
though the distance between the two viewpoints is the distance between your
two eyes. However, if they move the cameras a foot apart, your brain assumes
everything is like 1/4 scale More if you have eyes that are too close
together :-)

Kim Pallister

We will find a way or we will make one.
                     - Hannibal


> -----Original Message-----
> From: Patrick E. Hughes [mailto:hu...@tr...]
> Sent: Friday, July 14, 2000 1:38 PM
> To: Algorithms List
> Subject: [GDAlgorithms-List] Re: [Algorithms] Scale, camera, and world
> units and how it affects perception
> 
> 
> >fact that the camera is higher above the ground on the 
> human?  I mean,
> >if the human stuck his eye on the ground level with the 
> ant's viewpoint,
> >doesn't the human still see more of the terrain than does the ant?)
> 
> No.  You can realistically get your eye down to hound-dog 
> level though by
> laying flat out on the ground, ants way too low for a good example.
> 
> This is why all Hollywood special effects done with miniature 
> models work
> OK and the resulting shot doesn't look horribly out of place..
> 
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Octree leaf neighbours

[jason w. <jas...@po...>]

use a string of bits to name octree nodes: each bit indicates one halfspace
of a splitting plane in sequence, x, y z, somewhat like a kd-tree. So 3 bits
can name each child of an octree node. An int lets you name up to a 10 level
octree, 3 ints a 30 level tree. I'm sure you can see how you can use some
simple logical functions to generate the names of any adjacent cell of
interest.

then you can store a look up table that links named cells to a pointer, so
you'll only have 1 dereference. Somehow, I don't think any speed increase
would be worth the complication.

Re: [Algorithms] Octree leaf neighbours

[Thatcher U. <tu...@tu...>]

From: Thatcher Ulrich <tu...@tu...>
> [re finding a neighbor in an octree]
> It's an O(1) operation on average according to something I read somewhere
> (I think Hanan Samet proved this in one of his books but I don't have a
> reference handy).  The outline of the proof would be something like: half
> of the time, the neighbor is a child of the immediate parent (i.e. one
> generation from a common ancestor); a quarter of the time the neighbor is
> two generations from a common ancestor; an eighth of the time it's three
> generations away, etc.  So over a large number of random queries (N), the
> cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
> compute the average cost, and the sum approaches 1 as N approaches
> infinity.

Woah, I made a mess of the math there.  The expected number of pointer
dereferences in a recursive neighbor-finding query should be, on average:

sum(i=1-->infinity : 2*i / (2^i))

which works out to 4, not 1.  Still O(1), fortunately.

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Octree leaf neighbours

[Michael K. <neg...@ea...>]

Sam,

 Array traversal is actually just simple math using indexes.

 let me illustrate with a 3x3x3 array that is squashed down into a one
dimensional array.

bottom     middle            top
0 1 2   |    9 10 11    |   18 19 20
3 4 5   |   12 13 14   |   21 22 23
6 7 8   |   15 16 17   |   24 25 26


to get from the bottom layer to the middle layer you just have to add 9 to
the index, to go the right neighbor add 1, bottom neighbor add 3, left
neighbor subtract 1, etc.. I've used this in a quadtree terrain algorithm to
traverse from the top node all the way down to the lowest layer all within a
single array that was logically 256x256 and only using simple math. I'm sure
you can extend it into 3 dimensions, but it may not work for an octree very
well since it would require the octree to be fully divided, depending on
your reason for using an octree of course. You can also test if an index is
negative to traverse into neighboring arrays, usefull for patching terrain
together.


----- Original Message -----
From: Sam Kuhn <sa...@ip...>
To: <gda...@li...>
Sent: Sunday, July 16, 2000 12:29 PM
Subject: Re: [Algorithms] Octree leaf neighbours


> >Martin Gladnishki wrote:
> >And in addition you can save much time if you hold the tree in an array.
> This
> >saves the parent links, too :)
>
> Erm, I mentioned this in my origional post... dont you have to store a 3d
> (i.e. *big*) hash table so you can hash to the neighbours in the array
using
> the coordinates of the node you are in?
> How does it save the parent links then?
>
> sam
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] decompose onto non-orthogonal vectors

[Peter D. <pd...@mm...>]

> And further, it appears to me that if you don't already know that p is
> a linear combination of a and b, then the Gaussian elimination
> solution is somewhat shorter than your algorithm above.

To further beat this dead horse:

Yes, a coordinate-based solution may indeed be shorter algorithmically. The
method I presented wasn't meant to be the most efficient one. I wanted to
give the OP (Ben?) an idea how to proceed in situations like this.

When you have one vector equation with several scalar unknowns, as in this
case, the trick is to project the equation along several (linearly
independent) axes and solve the resulting linear system.

The axes usually chosen are the coordinate axes - this corresponds to
dotting the equation with the basis vectors.

This problem demonstrated a situation where a different set of axes proves
to be useful for the projection, namely the a and b vectors.

--
Peter Dimov
Multi Media Ltd.

Re: [Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

>Martin Gladnishki wrote:
>And in addition you can save much time if you hold the tree in an array.
This
>saves the parent links, too :)

Erm, I mentioned this in my origional post... dont you have to store a 3d
(i.e. *big*) hash table so you can hash to the neighbours in the array using
the coordinates of the node you are in?
How does it save the parent links then?

sam

Re: [Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

Thatcher,

Ta for the reasurance, I'll give it a go and see what kind of speed I get.

The thing is, at the moment I'm not actually "storing the tree". I'm just
traversing it.  I need to share vertices between neighbouring leaves, and if
the only way to do this is by physically storing the tree and "jumping
around" to find the neighbour, so be it.

Thanks,

Sam.



>
>On Sat, 15 Jul 2000, Sam Kuhn wrote:
>
>> I'm creating an octree, and need to maintain pointers between
neighbouring
>> *leaves*, and do it quick. The only way I can think of is to skip back up
>> the tree and down the neighbouring branches to locate each of the 6
>> neighbours. This doesn't seem very fast.
>
>It's an O(1) operation on average according to something I read somewhere
>(I think Hanan Samet proved this in one of his books but I don't have a
>reference handy).  The outline of the proof would be something like: half
>of the time, the neighbor is a child of the immediate parent (i.e. one
>generation from a common ancestor); a quarter of the time the neighbor is
>two generations from a common ancestor; an eighth of the time it's three
>generations away, etc.  So over a large number of random queries (N), the
>cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
>compute the average cost, and the sum approaches 1 as N approaches
>infinity.
>
>So while the traversal may *seem* slow when looking at the code, it
>probably isn't as slow as you think.
>
>--
>Thatcher Ulrich
>http://tulrich.com
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

John,

I'm sure I mean six. Above,Below,Left,Right,Forward and Back. (Don't care
about diagonals).

Yes I am recursing through the tree, and yes each node is "in play" during
the traversal. But I'm doing a "marching cubes" type of thing, I need to
share vertices between nodes. To do that I need to look at my neighbours,
see if they have been processed, and if so use their vertex instead of
generating a new one.

Yeah, If I store a pointer to parent I can traverse "up and round" to find
my neighbour. But whether this will save me any time over just generating
new vertices and not sharing. Time to suck it and see.

Thanks,

Sam.





-----Original Message-----
From: SHA...@ao... <SHA...@ao...>
To: gda...@li...
<gda...@li...>
Date: 16 July 2000 9:47 AM
Subject: Re: [Algorithms] Octree leaf neighbours


>In a message dated 15/07/00 20:59:35 !!!First Boot!!!, sa...@ip...
writes:
>
><< I'm creating an octree, and need to maintain pointers between
neighbouring
><< *leaves*, and do it quick. The only way I can think of is to skip back
up
><<the tree and down the neighbouring branches to locate each of the 6
><< neighbours. This doesn't seem very fast.
>
>Surely you mean 7 neighbours?
>
>
><< There is a method called "linear octrees" which supposedly let you use
the
><< so called "morton number" to directly hash a neighbour from is location
in
>3
><< space. But I believe you *have to subdivide the whole octree evenly* so
><< every leaf is stored and can be hashed properly. (i.e. a 3d array!). Fat
>use
><< since the reason i'm using an octree is to avoid a memory hungry grid in
>the
><< first place, or am I missing the point?
>
> Any insights would be appriciated!
>
> Sam.
>>>
>
>Looks like you need to provide a 'pointer to parent node' member in your
>structure to allow you to go back up a step and access the current nodes
>neighbours.
>
>In my original octree implimentation I had such a pointer but later found I
>didn't need it so I took it out.
>
>Why do you need access a parent nodes neighbours at this point?
>
>Your code should have dealt with that node when it was 'in play' during the
>recursive traversal procedure.
>
>You must know of course that when you are looking at a particular node you
>have access to all of it's children or as you call them, neighbours.
>
>Maybe I am missing something here, but isn't your octree traversal
recursive?
>
>Each node that you subdivide, are you subdividing it into 8 equal parts?
>
>
>And yes you are right, if you use a linear octree you will be creating many
>more nodes than you need.
>
>Regards,
>
>John.
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] C++ inherited constructors

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

> This wouldn't solve the problem : When I create an instance of CThread
 or
> ...
> Aesthetic is not everything :)

A formal (aesthetic) solution *could* be to define a common base class for
both your thread an application class, say Process:

class Process {
    /* Pure virtual stuff here */
    Process() { }

    virtual void execute()    = 0;
};

class Thread : public Process {
    /* Thread stuff goes here */
    Thread() { /* Intialize thread here */ }

    void execute();
};

class App : Process {
    App() { /* Initialize app here */ }

    void execute();
}

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

I  wrote:

>Peter Dimov  wrote:
>
>>> >This works for any number of dimensions. Whenever a solution exists, the
>>(u,
>>> >v) pair determined by this approach will have the property u * a + v * b
>>=
>>> >p. (Easy to prove.)
>>>
>>> Agree that it works for any number of dimensions provided that p does
>>> indeed lie in the plane of a and b.  My point was that it will not
>>> detect the case that p does not lie in that plane, that is, will not
>>> detect the case that no solution exisits.
>>
>>Hmm, it must be my English. :)
>>
>>1. Find the (u, v) pair as above.
>>2. Check whether u * a + v * b = p.
>>3. If yes, this (u, v) pair is the solution.
>>4. If no, no solution exists.
>>
>
>OK, you've stated a more complete algorithm now, and I agree that it
>works.  
>
>In any case, as I stated previously, I think your solution is the best
>and have long used it myself.  The Gaussian elimination approach,
>however, is based more directly on the most basic and fundamental
>concepts of linear algebra, which is why I stressed it..  The dot
>product approach is based on somewhat more advanced ideas.
>

And further, it appears to me that if you don't already know that p is
a linear combination of a and b, then the Gaussian elimination
solution is somewhat shorter than your algorithm above.

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Peter Dimov  wrote:

>> >This works for any number of dimensions. Whenever a solution exists, the
>(u,
>> >v) pair determined by this approach will have the property u * a + v * b
>=
>> >p. (Easy to prove.)
>>
>> Agree that it works for any number of dimensions provided that p does
>> indeed lie in the plane of a and b.  My point was that it will not
>> detect the case that p does not lie in that plane, that is, will not
>> detect the case that no solution exisits.
>
>Hmm, it must be my English. :)
>
>1. Find the (u, v) pair as above.
>2. Check whether u * a + v * b = p.
>3. If yes, this (u, v) pair is the solution.
>4. If no, no solution exists.
>

OK, you've stated a more complete algorithm now, and I agree that it
works.  

In any case, as I stated previously, I think your solution is the best
and have long used it myself.  The Gaussian elimination approach,
however, is based more directly on the most basic and fundamental
concepts of linear algebra, which is why I stressed it..  The dot
product approach is based on somewhat more advanced ideas.

.   

Re: [Algorithms] Octree leaf neighbours

[Martin G. <bz...@wi...>]

And in addition you can save much time if you hold the tree in an array. This
saves the parent links, too :)

-----Original Message-----
From: Thatcher Ulrich <tu...@tu...>
To: gda...@li...
<gda...@li...>
Date: 16 Þëè 2000 ã. 16:49
Subject: Re: [Algorithms] Octree leaf neighbours


>
>On Sat, 15 Jul 2000, Sam Kuhn wrote:
>
>> I'm creating an octree, and need to maintain pointers between neighbouring
>> *leaves*, and do it quick. The only way I can think of is to skip back up
>> the tree and down the neighbouring branches to locate each of the 6
>> neighbours. This doesn't seem very fast.
>
>It's an O(1) operation on average according to something I read somewhere
>(I think Hanan Samet proved this in one of his books but I don't have a
>reference handy).  The outline of the proof would be something like: half
>of the time, the neighbor is a child of the immediate parent (i.e. one
>generation from a common ancestor); a quarter of the time the neighbor is
>two generations from a common ancestor; an eighth of the time it's three
>generations away, etc.  So over a large number of random queries (N), the
>cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
>compute the average cost, and the sum approaches 1 as N approaches
>infinity.
>
>So while the traversal may *seem* slow when looking at the code, it
>probably isn't as slow as you think.
>
>--
>Thatcher Ulrich
>http://tulrich.com
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] C++ inherited constructors

[Matt A. <de...@gm...>]

This wouldn't solve the problem : When I create an instance of CThread ( or
if one is created by using containment )
the constructor is also called and therefore a new thread is created which I
dont want.
Yes and I don't want to create the instance by malloc() but by new or by
containment, which automatically call the constructor.
Anyway, since there's no way to suppress the constructor call, I chose a
workaround.
Aesthetic is not everything :)
Thanks for all the answers to this topic,
Matt

----- Original Message -----
From: Will Portnoy <wi...@cs...>
To: <gda...@li...>
Sent: Saturday, July 15, 2000 9:52 PM
Subject: Re: [Algorithms] C++ inherited constructors


> I don't completely understand your problem, but it might be solvable by
> using containment rather than inheritance, i.e. a process *has* a thread
> rather than *is* a thread.  I think it would allow for the semantics you
> want.  You could pass in an external thread for the process/main loop to
> "have" through a constructor argument, or you could just have the
> process/main loop create a thread through it's default argumentless
> constructor.
>
> The same goes with your main loop class: it has a thread, not is a
> thread.
>
> It's an idea, anyway. :)
>
> Will
>
> ----
> Will Portnoy
> http://www.cs.washington.edu/homes/will
>
> On Sat, 15 Jul 2000, Matt Adams wrote:
>
> > I need this for aesthetic reasons :)
> > I've got an abstract CThread class. If a want to create a new thread, I
> > build my process class and inherit CThread, which creates a new thread
by
> > construction.
> > Now I want my main-threadloop-class to inherit CThread, too, to provide
all
> > the thread functionality to my main thread. But that thread already
exists
> >  created by compiler ), and shouldn't be created again by CThread.
> > Of course I can put CThread () and ~CThread () in functions like
Create()
> > and Destroy() and leave the constructor / destructor empty. But it'd be
> > nicer if it could be done in another way...
> >
> > ----- Original Message -----
> > From: Favnir
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 1:32 PM
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> > The only way you can do this is to define a (preferably) protected
> > do-nothing constructor for the base class, and inherit it in the
subclass
> > constructor.
> >
> > But, why in the world would you need to do this, in the first place?
> >
> > Are,
> > F
> >
> > ----- Original Message -----
> > From: Matt Adams
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 12:22 PM
> > Subject: [Algorithms] C++ inherited constructors
> >
> >
> > Hi,
> >
> > I got a question about the C++ class hierarchy.
> >
> > class a
> > {
> >     a () {...}; // constr a
> > };
> >
> > class b : a
> > {
> >     b () {...}; // constr b
> > };
> >
> > b instance;
> >
> > When creating an instance of b, constructors for both class a and class
b
> > are called.
> > Is there a way to suppress the automatic calling of constructor a ?
> > Or something like 'overloading' the old constructor by a new one ?
> > I couldn't find anything like that in the compiler docs.
> >
> > Any help appreciated,
> > Matt
> >
> >
> > _______________________________________________
> > 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] Octree leaf neighbours

[Thatcher U. <tu...@tu...>]

On Sat, 15 Jul 2000, Sam Kuhn wrote:

> I'm creating an octree, and need to maintain pointers between neighbouring
> *leaves*, and do it quick. The only way I can think of is to skip back up
> the tree and down the neighbouring branches to locate each of the 6
> neighbours. This doesn't seem very fast.

It's an O(1) operation on average according to something I read somewhere
(I think Hanan Samet proved this in one of his books but I don't have a
reference handy).  The outline of the proof would be something like: half
of the time, the neighbor is a child of the immediate parent (i.e. one
generation from a common ancestor); a quarter of the time the neighbor is
two generations from a common ancestor; an eighth of the time it's three
generations away, etc.  So over a large number of random queries (N), the
cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
compute the average cost, and the sum approaches 1 as N approaches
infinity.

So while the traversal may *seem* slow when looking at the code, it
probably isn't as slow as you think.

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] C++ inherited constructors

[Peter D. <pd...@mm...>]

> You can't call virtual functions from constructors.  Doing so is
> undefined in C++.  (MSVC will call the local instantiation, even when
> there's an overloaded one, for instance.)

Actually you can, and it's well defined. The problem is that in the
constructor the static and the dynamic type of "this" are the same.

#include <iostream>

struct A
{
    virtual void f() const { std::cout << "A::f()\n"; }
};

void g(A const & a)
{
    a.f();
}

struct B: A
{
    B() { g(*this); }
    virtual void f() const { std::cout << "B::f()\n"; }
};

struct C: B
{
    virtual void f() const { std::cout << "C::f()\n"; }
};

int main()
{
    C c;
    return 0;
}

--
Peter Dimov
Multi Media Ltd.

Re: [Algorithms] decompose onto non-orthogonal vectors

[Peter D. <pd...@mm...>]

> >This works for any number of dimensions. Whenever a solution exists, the
(u,
> >v) pair determined by this approach will have the property u * a + v * b
=
> >p. (Easy to prove.)
>
> Agree that it works for any number of dimensions provided that p does
> indeed lie in the plane of a and b.  My point was that it will not
> detect the case that p does not lie in that plane, that is, will not
> detect the case that no solution exisits.

Hmm, it must be my English. :)

1. Find the (u, v) pair as above.
2. Check whether u * a + v * b = p.
3. If yes, this (u, v) pair is the solution.
4. If no, no solution exists.

So it does indeed detect whether p lies in the plane formed by a and b.
Whenever p lies in that plane, an (u, v) pair such that p = u * a + v * b
must exist, and vice versa.

(I'm deliberately assuming that this plane is unique. Nevertheless, the
method "works" even if a and b are collinear, or one of them is zero.)

A more "formal" proof:

First, assume that a solution does exist, i.e. there exists an (u0, v0) pair
such that u0 * a + v0 * b = p. Such a pair must satisfy the linear system of
equations I gave, and therefore can be determined by solving that system. If
this pair is unique (the case we are interested in,) it will be the only
solution of this system (*), and therefore will have the property u * a + v
* b = p.

Now, assume that no solution exists, i.e. no (u, v) pair satisfies u * a + v
* b = p. In this case, obviously, whatever the solution of the system, it
cannot have this property.

QED?

--
Peter Dimov
Multi Media Ltd.

(*) The determinant is zero when a.a * b.b = a.b * b.a, i.e. when a and b
are collinear.

P.S. I'm inclined to note that this method does not even mention
coordinates, relying only on the fact that multiplication, addition, and dot
product are defined on a, b, and p, and therefore you must like it, by
definition. :)

Re: [Algorithms] C++ inherited constructors

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

> Why not have your base class constructor call a virtual private member
> function and overload that function in the derived class?

I wouldn't rely on such a thing - vtable's tend to have a nasty habbit of
not being properly initialized in the constructor and desctructor. I once
spend far to much time hunting a bug which turned out to be a pure virtual
call in one of my inline destructors...

I'd either stick to Adam's good advise, or use the protected constructor
trick (note that this doesn't have to be the default constructor... I use a
Thread::Thread(bool doNotInitialize) internally).

Jim Offerman

Innovade
- designing the designer
----- Original Message -----
From: "Aaron Drew" <ri...@ho...>
To: <gda...@li...>
Sent: Sunday, July 16, 2000 9:41 AM
Subject: RE: [Algorithms] C++ inherited constructors


>
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...]On Behalf Of Matt
> > Adams
> > Sent: Saturday, July 15, 2000 9:19 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> >
> >
> > I need this for aesthetic reasons :)
> > I've got an abstract CThread class. If a want to create a new thread, I
> > build my process class and inherit CThread, which creates a new thread
by
> > construction.
> > Now I want my main-threadloop-class to inherit CThread, too, to
> > provide all
> > the thread functionality to my main thread. But that thread already
exists
> >  created by compiler ), and shouldn't be created again by CThread.
> > Of course I can put CThread () and ~CThread () in functions like
Create()
> > and Destroy() and leave the constructor / destructor empty. But it'd be
> > nicer if it could be done in another way...
> >
> > ----- Original Message -----
> > From: Favnir
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 1:32 PM
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> > The only way you can do this is to define a (preferably) protected
> > do-nothing constructor for the base class, and inherit it in the
subclass
> > constructor.
> >
> > But, why in the world would you need to do this, in the first place?
> >
> > Are,
> > F
> >
> > ----- Original Message -----
> > From: Matt Adams
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 12:22 PM
> > Subject: [Algorithms] C++ inherited constructors
> >
> >
> > Hi,
> >
> > I got a question about the C++ class hierarchy.
> >
> > class a
> > {
> >     a () {...}; // constr a
> > };
> >
> > class b : a
> > {
> >     b () {...}; // constr b
> > };
> >
> > b instance;
> >
> > When creating an instance of b, constructors for both class a and class
b
> > are called.
> > Is there a way to suppress the automatic calling of constructor a ?
> > Or something like 'overloading' the old constructor by a new one ?
> > I couldn't find anything like that in the compiler docs.
> >
> > Any help appreciated,
> > Matt
> >
> >
> > _______________________________________________
> > 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] C++ inherited constructors

[Timur D. <ti...@3d...>]

Because base constructor will not call member method virtually, it will call
base class method.

_______________________
 Timur Davidenko.
 3Dion Inc. (www.3dion.com)
 e-mail: ti...@3d...


----- Original Message -----
From: "Aaron Drew" <ri...@ho...>
To: <gda...@li...>
Sent: Sunday, July 16, 2000 9:41 AM
Subject: RE: [Algorithms] C++ inherited constructors


> Why not have your base class constructor call a virtual private member
> function and overload that function in the derived class?
>
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...]On Behalf Of Matt
> > Adams
> > Sent: Saturday, July 15, 2000 9:19 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> >
> >
> > I need this for aesthetic reasons :)
> > I've got an abstract CThread class. If a want to create a new thread, I
> > build my process class and inherit CThread, which creates a new thread
by
> > construction.
> > Now I want my main-threadloop-class to inherit CThread, too, to
> > provide all
> > the thread functionality to my main thread. But that thread already
exists
> >  created by compiler ), and shouldn't be created again by CThread.
> > Of course I can put CThread () and ~CThread () in functions like
Create()
> > and Destroy() and leave the constructor / destructor empty. But it'd be
> > nicer if it could be done in another way...
> >
> > ----- Original Message -----
> > From: Favnir
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 1:32 PM
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> > The only way you can do this is to define a (preferably) protected
> > do-nothing constructor for the base class, and inherit it in the
subclass
> > constructor.
> >
> > But, why in the world would you need to do this, in the first place?
> >
> > Are,
> > F
> >
> > ----- Original Message -----
> > From: Matt Adams
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 12:22 PM
> > Subject: [Algorithms] C++ inherited constructors
> >
> >
> > Hi,
> >
> > I got a question about the C++ class hierarchy.
> >
> > class a
> > {
> >     a () {...}; // constr a
> > };
> >
> > class b : a
> > {
> >     b () {...}; // constr b
> > };
> >
> > b instance;
> >
> > When creating an instance of b, constructors for both class a and class
b
> > are called.
> > Is there a way to suppress the automatic calling of constructor a ?
> > Or something like 'overloading' the old constructor by a new one ?
> > I couldn't find anything like that in the compiler docs.
> >
> > Any help appreciated,
> > Matt
> >
> >
> > _______________________________________________
> > 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] C++ inherited constructors

[Michael H. <he...@po...>]

You can't call virtual functions from constructors.  Doing so is
undefined in C++.  (MSVC will call the local instantiation, even when
there's an overloaded one, for instance.)

mike

----- Original Message -----
From: "Aaron Drew" <ri...@ho...>
To: <gda...@li...>
Sent: Sunday, July 16, 2000 12:41 AM
Subject: RE: [Algorithms] C++ inherited constructors


> Why not have your base class constructor call a virtual private
member
> function and overload that function in the derived class?
>
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...]On Behalf Of
Matt
> > Adams
> > Sent: Saturday, July 15, 2000 9:19 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> >
> >
> > I need this for aesthetic reasons :)
> > I've got an abstract CThread class. If a want to create a new
thread, I
> > build my process class and inherit CThread, which creates a new
thread by
> > construction.
> > Now I want my main-threadloop-class to inherit CThread, too, to
> > provide all
> > the thread functionality to my main thread. But that thread
already exists
> >  created by compiler ), and shouldn't be created again by CThread.
> > Of course I can put CThread () and ~CThread () in functions like
Create()
> > and Destroy() and leave the constructor / destructor empty. But
it'd be
> > nicer if it could be done in another way...
> >
> > ----- Original Message -----
> > From: Favnir
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 1:32 PM
> > Subject: Re: [Algorithms] C++ inherited constructors
> >
> > The only way you can do this is to define a (preferably) protected
> > do-nothing constructor for the base class, and inherit it in the
subclass
> > constructor.
> >
> > But, why in the world would you need to do this, in the first
place?
> >
> > Are,
> > F
> >
> > ----- Original Message -----
> > From: Matt Adams
> > To: gda...@li...
> > Sent: Saturday, July 15, 2000 12:22 PM
> > Subject: [Algorithms] C++ inherited constructors
> >
> >
> > Hi,
> >
> > I got a question about the C++ class hierarchy.
> >
> > class a
> > {
> >     a () {...}; // constr a
> > };
> >
> > class b : a
> > {
> >     b () {...}; // constr b
> > };
> >
> > b instance;
> >
> > When creating an instance of b, constructors for both class a and
class b
> > are called.
> > Is there a way to suppress the automatic calling of constructor a
?
> > Or something like 'overloading' the old constructor by a new one ?
> > I couldn't find anything like that in the compiler docs.
> >
> > Any help appreciated,
> > Matt
> >
> >
> > _______________________________________________
> > 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
>
>