gdalgorithms-list

RE: [Algorithms] Terrain Organization

[Tom F. <to...@mu...>]

Indeed - my goal for graphics systems is that when they are released, they
should be able to bring even the best existing machine down to sub-1Hz speed
if you turn all the detail levels up, and yet have perfectly acceptable
performance on five-year-old machines with the auto-LoD system on. That way
you know (a) you've done a good job of scaling stuff, (b) you're pretty sure
you can re-use the engine (or something derived from it) for the next
project, and (c) people will still play your game in five years - it won't
look sad. Oh yes, and (d) you might get some good bundling deals with new
graphics cards - and they're always welcome.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Jim Offerman [mailto:j.o...@in...]
> Sent: 31 July 2000 08:09
> To: gda...@li...
> Subject: Re: [Algorithms] Terrain Organization
> 
> 
> > As for not everyone having TnL cards, well, I thought that 
> any game which
> is
> > *now* in development will probably run on fast systems. By 
> fast I mean
> either
> > TnL, or on CPUs which are fast enough that regular cards 
> don't suffer too
> > much. Anyway, this is up to you, it depends on you budget 
> and a lot of
> other
> > things.
> 
> If you are going to implement some form of CLOD (this is 
> where Tom Forsyth
> would promote using VIPM - which is not a bad idea at all), I 
> think you
> should couple the runtime error calculations to your fps... 
> i.e. if your fps
> drops, crank down all lod levels in the game until the fps reaches an
> acceptable level. Your gime might be spitting out 100K tris 
> per second on a
> souped up PIII with GeForce2 GTS and pump through a humble 
> 15K on a PII with
> TNT PCI.
> 
> And, since you have tied your CLOD calculations to the fps you could
> (theoratically) also truly design your game for the future - 
> i.e. use models
> which by todays standards contain far to many triangles, the 
> CLOD will keep
> performance acceptable on today's high end hardware and 
> increase detail on
> tomorrow's hardware. Imagine playing Half-Life again, finding that the
> overall detail has increased by a factor ten.
> 
> Jim Offerman
> 
> Innovade
> - designing the designer

RE: [Algorithms] Terrain Organization

[Tom F. <to...@mu...>]

Yes, this is basically what a quadtree culling system does. Remember - there
are two separate (but linked) considerations:

(1) culling geometry that is out of view frustum.

(2) reducing visible geometry through some sort of level-of-detail system.

The two are often (and indeed, should be) interlinked, but they are separate
thing. The first is comparatively simple - quadtree and similar hierarchial
systems do it very well. The second is harder, and the subject of many
discussions on this list.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Mats Lundberg [mailto:ma...@al...]
> Sent: 30 July 2000 22:00
> To: gda...@li...
> Subject: Re: [Algorithms] Terrain Organization
> 
> 
> I've also thought of something similiar to what you proposed...
> 
>  Meanwhile I am planning to split the terrain up to several 
> _hierarchical_
>  chunks (with bounding boxes) and, for each frame, I test each chunk
> against the   current viewing frustum (VF) to _recursively_ 
> determine if it
> has to be
>  submitted to the transformation and rendering pipeline.  If an
> _upper-level_   chunk is rejected, there is no need to go down to the
> _lower-level_ chunks   inside it, which can quickly reject a 
> huge amount of
> geometry.
> 
> I don't se anything wrong with it. No fancy geometry calc:s, 
> just a simple
> recursive function that goes through a quad tree. I mean, how 
> much simpler
> can you make it?? It maybe crude but hey, it works. Right?? 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Terrain Organization

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

> As for not everyone having TnL cards, well, I thought that any game which
is
> *now* in development will probably run on fast systems. By fast I mean
either
> TnL, or on CPUs which are fast enough that regular cards don't suffer too
> much. Anyway, this is up to you, it depends on you budget and a lot of
other
> things.

If you are going to implement some form of CLOD (this is where Tom Forsyth
would promote using VIPM - which is not a bad idea at all), I think you
should couple the runtime error calculations to your fps... i.e. if your fps
drops, crank down all lod levels in the game until the fps reaches an
acceptable level. Your gime might be spitting out 100K tris per second on a
souped up PIII with GeForce2 GTS and pump through a humble 15K on a PII with
TNT PCI.

And, since you have tied your CLOD calculations to the fps you could
(theoratically) also truly design your game for the future - i.e. use models
which by todays standards contain far to many triangles, the CLOD will keep
performance acceptable on today's high end hardware and increase detail on
tomorrow's hardware. Imagine playing Half-Life again, finding that the
overall detail has increased by a factor ten.

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] Terrain Organization

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

In addition, you might consider using a preprocessed RTIN version of your
landscape to remove some triangles from the flat areas of your terrain.

Jim Offerman

Innovade
- designing the designer
----- Original Message -----
From: "Mats Lundberg" <ma...@al...>
To: <gda...@li...>
Sent: Sunday, July 30, 2000 11:00 PM
Subject: Re: [Algorithms] Terrain Organization


> I've also thought of something similiar to what you proposed...
>
>  Meanwhile I am planning to split the terrain up to several _hierarchical_
>  chunks (with bounding boxes) and, for each frame, I test each chunk
> against the   current viewing frustum (VF) to _recursively_ determine if
it
> has to be
>  submitted to the transformation and rendering pipeline.  If an
> _upper-level_   chunk is rejected, there is no need to go down to the
> _lower-level_ chunks   inside it, which can quickly reject a huge amount
of
> geometry.
>
> I don't se anything wrong with it. No fancy geometry calc:s, just a simple
> recursive function that goes through a quad tree. I mean, how much simpler
> can you make it?? It maybe crude but hey, it works. Right??
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

[Algorithms] Scorch marks on arbitrary geometry (was: Bullets on walls)

[Noel L. <ll...@ho...>]

So, after the interesting thread about putting bullets on
walls, I was wondering what people usually do to put
scorch marks (or any other decals) on arbitrary geometry.

It seems that most methods work well for regular or
"known" geometry: height fields, quads, etc.

The two ways I could think of so far are:
- Use projective textures. I haven't used this before. What kind
   of performance hit does it involve?

- Try to "face-map" the geometry we want to scorch to use
   texture coordinates from 0.0 to 1.0 in a regular way, and then
   draw it again with the scorched texture. This is particularly
   tricky if the geometry isn't face-mapped to start with, and especially
   if we want to do it without modifying the geometry at all (would need
   to find a texture transform that maps the original uvs into what we
   need).

How are people doing that today in games? Any recommendations
or ideas would be most welcome.
Cheers.


--Noel
ll...@ho...

Re: [Algorithms] Terrain Organization

[<Lea...@en...>]

> 1. A terrain with 5-10k polys in the scene is pretty weak. To have good
> detail up close, and have a large view distance (10,000 meters is a goal
> for me, although infinite yon clip with a spherical world would be even
> better) you end up with 100s of thousands of triangles in a single scene at
> full tessellation.

You can have a lot of detail up close, but you can quickly reduce the
amount of geometry sent to the card with things like basic lumigraphs,
reduced quad texture based geometry visualisation, etc... I've had our
terrain engine running at 35 km view distance and it looks nice... but
I haven't done any terrain stuff for a while now.

> 2. Not everyone has TnL capable machines, and it is generally a "good
> thing" if your engine can scale across systems with different geometry
> performance.

This is the difference -- we require TnL HW. I honestly believe that
ROAM is the way to go for CPU transformation engines, but not so for
HW TnL based engines... the best thing for people trying to support
both would be implement both -- but that's a lot more development.

> 3. You _can_ do continuous terrain LOD on a TnL card, but you are bound by
> the LOD calculation itself, and hence, CPU speed as you mention. However,
> things can and are being sped up greatly on this front, both with faster
> CPUs, and better split metrics.

As are expectations with 3D audio, physics, and in our case, AI... :)
 
> Now, that isn't to say that CLOD terrain is for everyone. Far from it. For
> small view areas and rather coarse tessellation of static terrain, just
> drawing a static LOD works quite well.

I agree that both methods have their benefits and audiences... it's a
matter of deciding at the start which suits your particular purpose.

Leathal.

Re: [Algorithms] Scaling Models

[<Lea...@en...>]

> The transpose(inverse) for normals slipped my mind. Oops. OpenGL does do
> the transpose(inverse) of course.

As your probably aware, OpenGL only takes the transpose of the 3x3
rotation matrix contained within the 4x4 transformation matrix if
the transformation calls were only rotations, translations... scales,
shears and the like cause the matrix inverse to be calculated and
then transposed.
 
> The transpose(inverse) operation only needs to be performed once when the
> matrix is loaded, and only if the API has state currently enabled that uses
> normals (directional lighting or spherical environment mapping). If these
> states are enabled after the fact, the matrix can be created when the state
> changes. In the case where it needs to do the computation, whether or not
> it checks for linearity depends on the expense of the check I guess. The
> driver writers are usually pretty good at doing minimal amounts of work to
> speed things up as best they can.

This is where I am going to advocate using the OpenGL API to do the
transformation work... there are a lot of coders who do the
glLoadMatrix() thing -- in which case it is hard for an API to know
whether the transformations are affine or not...

The way I am pretty positive the driver writers do things (not 100%
sure as they won't tell me... :) is something like:
	flag_t	affineMatrix;
	flag_t	isInverted;

	glLoadIdentity()
		affineMatrix = true;
		set values()

	glRotate()
		set values

	glScale()
		affineMatrix = false
		set values

When it comes to transformation, it's a matter of
	if (!affineMatrix)
		if (!isInverted)
			invert matrix
			isInverted = true

	transform pipeline

The actual pipeline could optimise that a lot, and bypass any
routines to ensure maximum performance... but that's just my
trying to demonstrate things clearly... :)

Has anybody actually noticed performance increases from the use
of glLoadMatrix()? The benefits of having your own matrices are
numerous, such as for grabbing view frustum parameters, being
able to transform BBoxes easily, etc... but I am thinking that
a _lot_ of objects would be faster to get across to the HW if you
could just send the the info with normal OpenGL calls.

Leathal.

Re: [Algorithms] Terrain Organization

[Relja M. <re...@in...>]

Tom, you are right about LOD being useful at 100K triangles. I thought the
original poster was talking about smaller terrains. 10K viewable triangles is
good enough for me, but everybody has different tastes, right...

As for not everyone having TnL cards, well, I thought that any game which is
*now* in development will probably run on fast systems. By fast I mean either
TnL, or on CPUs which are fast enough that regular cards don't suffer too
much. Anyway, this is up to you, it depends on you budget and a lot of other
things.

Greetings,
Relja Markovic

From: "Tom Hubina" <to...@3d...>
> At 01:03 PM 7/30/2000 +0200, you wrote:
> >want some extremely detailed stuff up front. Anyway, if your terrain has
5-10
> >K polys in an average scene, you could care less if you LOD it down to
2-5K
> >on a TnL card...
>
> I have a few problems with those assertions:
>
> 1. A terrain with 5-10k polys in the scene is pretty weak. To have good
> detail up close, and have a large view distance (10,000 meters is a goal

> 2. Not everyone has TnL capable machines, and it is generally a "good
> thing" if your engine can scale across systems with different geometry
> performance.

[Algorithms] FPS Questions

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

Hi,

(1) Is there a universally agreed way to calculate
Frame-Per-Second information?

(2) What is the acceptable FPS for today's 3D games?

Thanks,

Pai-Hung Chen

Re: [Algorithms] Terrain Organization

[Tom H. <to...@3d...>]

At 01:03 PM 7/30/2000 +0200, you wrote:
>Check the archives on this one, but I think someone (nVidia, perhaps?) said
>once that on TnL type cards it is more efficient to pump the polygons at the
>card than to spend too much time (ROAM) LODding on the CPU. If that is true
>(I for one think it makes sense), the recursive quadtree you described would
>work just fine. Apparently, terrain LOD has no future with TnL - unless you
>want some extremely detailed stuff up front. Anyway, if your terrain has 5-10
>K polys in an average scene, you could care less if you LOD it down to 2-5K
>on a TnL card...

I have a few problems with those assertions:

1. A terrain with 5-10k polys in the scene is pretty weak. To have good 
detail up close, and have a large view distance (10,000 meters is a goal 
for me, although infinite yon clip with a spherical world would be even 
better) you end up with 100s of thousands of triangles in a single scene at 
full tessellation.
2. Not everyone has TnL capable machines, and it is generally a "good 
thing" if your engine can scale across systems with different geometry 
performance.
3. You _can_ do continuous terrain LOD on a TnL card, but you are bound by 
the LOD calculation itself, and hence, CPU speed as you mention. However, 
things can and are being sped up greatly on this front, both with faster 
CPUs, and better split metrics.

Now, that isn't to say that CLOD terrain is for everyone. Far from it. For 
small view areas and rather coarse tessellation of static terrain, just 
drawing a static LOD works quite well.

Tom

Re: [Algorithms] Terrain Organization

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

> I've also thought of something similiar to what you proposed...
>
>  Meanwhile I am planning to split the terrain up to several
_hierarchical_
>  chunks (with bounding boxes) and, for each frame, I test each
chunk
> against the   current viewing frustum (VF) to _recursively_
determine if it
> has to be
>  submitted to the transformation and rendering pipeline.  If an
> _upper-level_   chunk is rejected, there is no need to go down
to the
> _lower-level_ chunks   inside it, which can quickly reject a
huge amount of
> geometry.
>
> I don't se anything wrong with it. No fancy geometry calc:s,
just a simple
> recursive function that goes through a quad tree. I mean, how
much simpler
> can you make it?? It maybe crude but hey, it works. Right??

Yes, it's both simple and efficient, I think.  I am just wondering
how efficient it compares to other more sophisticated techniques
such as BSP and ROAM in a _general_ manner.  I haven't seen any
article that compares the "plain vanilla" approaches to the
"fancy" ones in this respect.

Any comments?

Pai-Hung Chen

Re: [Algorithms] Scaling Models

[<Chr...@Pl...>]

Ron Levine wrote:
>A frightening demonstration of the folly of relying on spell checkers,
>rather than careful proof reading, in the wee small hours.

Sorry to be an off-topic smartass, but I cannot resist: that should be
*spelling* checker. A spell checker is something only a witch would use.

Christer Ericson
SCEA, Santa Monica

Re: [Algorithms] Terrain Organization

[Mats L. <ma...@al...>]

I've also thought of something similiar to what you proposed...

 Meanwhile I am planning to split the terrain up to several _hierarchical_
 chunks (with bounding boxes) and, for each frame, I test each chunk
against the   current viewing frustum (VF) to _recursively_ determine if it
has to be
 submitted to the transformation and rendering pipeline.  If an
_upper-level_   chunk is rejected, there is no need to go down to the
_lower-level_ chunks   inside it, which can quickly reject a huge amount of
geometry.

I don't se anything wrong with it. No fancy geometry calc:s, just a simple
recursive function that goes through a quad tree. I mean, how much simpler
can you make it?? It maybe crude but hey, it works. Right?? 

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

Roger.

> -----Original Message-----
> From: Conor Stokes [mailto:cs...@tp...]
> Sent: Sunday, July 30, 2000 9:04 AM
> To: gda...@li...
> Subject: Re: [Algorithms] 3d Lines Intersection
> 
> 
> Don't worry Steve, we've established Ron is a grumpy old man 
> :) But a useful
> grumpy old man. Occasionally people taste his acid tongue, 
> but it is worth
> it for the sweet bits he sometimes imparts.
> 
> Still, it would be nice if he didn't play Socrates when there 
> is no need. We
> don't need the production of a group of Plato's at the 
> inevitable execution
> he will face if he follows this path.
> 
> Conor Stokes
> 
> > Ron,
> >
> > Your post in this matter is off topic and is nothing but a personal
> > attack...especially since you could not find any fault with the math
> > (otherwise I presume you would have written a lengthy essay 
> on how you
> find
> > it incomplete).  I've forwarded the matter to this lists' 
> administrator.
> > You seem to have some problems that we can not help you 
> with.  This is an
> > algorithms list to learn and share algorithms, not play at 
> being a math
> cop
> > as you say you are.
> >
> > As to the math I shared...the people on this list don't 
> take everything
> for
> > granted, and I make mistakes. If you want to point out any 
> mistakes then
> > please do it elsewhere unless you want to work together to solve the
> > problem.
> >
> > If it builds it and only bugs come, but turns it into a bug 
> squasher then
> > it's,
> > Rockn-Roll
> >
> > > -----Original Message-----
> > > From: ro...@do... [mailto:ro...@do...]
> > > Sent: Saturday, July 29, 2000 10:53 PM
> > > To: gda...@li...
> > > Subject: Re: [Algorithms] 3d Lines Intersection
> > >
> > >
> > > Steve Wood  wrote:
> > >
> > >
> > > >Here is the math:
> > > >
> > >
> > > This is to advise the readers of this thread that they 
> need not fret
> > > if they could not follow the ensuing mess, and they ought 
> not waste
> > > any more time on it if they are still trying.  Whatever 
> it might look
> > > like at first glance, on close inspection it is certainly 
> not anything
> > > that could properly be called math.
> > >
> > >
> > >
> > > _______________________________________________
> > > 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] 3d Lines Intersection

[Conor S. <cs...@tp...>]

Don't worry Steve, we've established Ron is a grumpy old man :) But a useful
grumpy old man. Occasionally people taste his acid tongue, but it is worth
it for the sweet bits he sometimes imparts.

Still, it would be nice if he didn't play Socrates when there is no need. We
don't need the production of a group of Plato's at the inevitable execution
he will face if he follows this path.

Conor Stokes

> Ron,
>
> Your post in this matter is off topic and is nothing but a personal
> attack...especially since you could not find any fault with the math
> (otherwise I presume you would have written a lengthy essay on how you
find
> it incomplete).  I've forwarded the matter to this lists' administrator.
> You seem to have some problems that we can not help you with.  This is an
> algorithms list to learn and share algorithms, not play at being a math
cop
> as you say you are.
>
> As to the math I shared...the people on this list don't take everything
for
> granted, and I make mistakes. If you want to point out any mistakes then
> please do it elsewhere unless you want to work together to solve the
> problem.
>
> If it builds it and only bugs come, but turns it into a bug squasher then
> it's,
> Rockn-Roll
>
> > -----Original Message-----
> > From: ro...@do... [mailto:ro...@do...]
> > Sent: Saturday, July 29, 2000 10:53 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] 3d Lines Intersection
> >
> >
> > Steve Wood  wrote:
> >
> >
> > >Here is the math:
> > >
> >
> > This is to advise the readers of this thread that they need not fret
> > if they could not follow the ensuing mess, and they ought not waste
> > any more time on it if they are still trying.  Whatever it might look
> > like at first glance, on close inspection it is certainly not anything
> > that could properly be called math.
> >
> >
> >
> > _______________________________________________
> > 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] Re: Posting Wrong Stuff

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

> > Deliberately posting wrong stuff is one thing, posting things that you
> > believe (and are pretty certain) are correct is another. After all, I do
> > this all the time. So does Ron, for that matter.

I realize that I was a bit unclear. What I meant was that your post falls in
the second category, not the first.

> Coming from a world of designers, I am taught to believe that every idea
is
> a good one, as bad ideas often lead to great ideas (I think that the most
> famous example is the yellow 'Post-It' note, which is actually the result
of
> a failed experiment).

And, in fact, it was your post that made me think about the solution I
posted.

--
Peter Dimov
Multi Media Ltd.

[Algorithms] Re: Posting Wrong Stuff

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

> Deliberately posting wrong stuff is one thing, posting things that you
> believe (and are pretty certain) are correct is another. After all, I do
> this all the time. So does Ron, for that matter.

Don't we all. And I don't think that there is anyone on this list who will
deliberately post something that is wrong.

Coming from a world of designers, I am taught to believe that every idea is
a good one, as bad ideas often lead to great ideas (I think that the most
famous example is the yellow 'Post-It' note, which is actually the result of
a failed experiment). We don't need some cop (and I mean this in general, I
don't want to start a personal attack on Ron or anyone else) to track down
and hunt posters of wrong ideas, we really don't. I'd rather see a wrong
idea feul the discussion that leads to a right idea.

Jim Offerman

Innovade
- designing the designer

"The road to success is learned from one's failures."

RE: [Algorithms] Terrain Organization

[Tom F. <to...@mu...>]

As well as those methods mentioned (ROAM, CLOD, quadtree, BSPd, just drawing
everything), VIPM is very useful for LoD in terrains, and indeed for LoD in
most things. It is especially efficient when combined with a quadtree style
of texturing and paging.

Probably the best tutorial for all things VIPM is Charles Bloom's site
http://208.55.130.3/3d/ - check the sixth link down. There is also a terrain
VIPM demo there.

There is also tons of discussion on the various terrain styles in the
archives (assuming they are up and running now).

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Relja Markovic [mailto:re...@in...]
> Sent: 30 July 2000 12:04
> To: gda...@li...
> Subject: Re: [Algorithms] Terrain Organization
> 
> 
> Check the archives on this one, but I think someone (nVidia, 
> perhaps?) said
> once that on TnL type cards it is more efficient to pump the 
> polygons at the
> card than to spend too much time (ROAM) LODding on the CPU. 
> If that is true
> (I for one think it makes sense), the recursive quadtree you 
> described would
> work just fine. Apparently, terrain LOD has no future with 
> TnL - unless you
> want some extremely detailed stuff up front. Anyway, if your 
> terrain has 5-10
> K polys in an average scene, you could care less if you LOD 
> it down to 2-5K
> on a TnL card...
> 
> Relja
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Terrain Organization

[Relja M. <re...@in...>]

Check the archives on this one, but I think someone (nVidia, perhaps?) said
once that on TnL type cards it is more efficient to pump the polygons at the
card than to spend too much time (ROAM) LODding on the CPU. If that is true
(I for one think it makes sense), the recursive quadtree you described would
work just fine. Apparently, terrain LOD has no future with TnL - unless you
want some extremely detailed stuff up front. Anyway, if your terrain has 5-10
K polys in an average scene, you could care less if you LOD it down to 2-5K
on a TnL card...

Relja

Re: Posting Wrong Stuff (was Re: [Algorithms] 3d Lines Intersection)

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

> > Which is no license to post wrong stuff..
>
> Nope.
>
> BUT one of my reasons for posting my algorithm is that there is bound to
be

[...]

You know, I didn't realize that your algorithm is wrong immediately when I
read it. It took me about a day of "background thinking" to see that it
doesn't work.

Deliberately posting wrong stuff is one thing, posting things that you
believe (and are pretty certain) are correct is another. After all, I do
this all the time. So does Ron, for that matter.

--
Peter Dimov
Multi Media Ltd.

Re: [Algorithms] 3d Lines Intersection

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

[Jim Offerman's algorithm snipped]

> Unfortunately, there is no logical basis for it and it is quite wrong.

It is clearly wrong, but it does have logical basis.

If the lines intersect, there exists a plane where their projections
intersect at the same point (in the {s, t} sense.)

The problem is that the XY and XZ coordinate planes may not have this
property.

A plane that does have this property is the plane formed by the two
direction vectors, d1 and d2 (in fact they describe a family of planes, any
of them will do.)

So, given the equation

p1 + t * d1 = p2 + s * d2

we "project" it onto the (d1, d2) plane by dotting with d1 and d2,
respectively:

p1 . d1 + t * (d1 . d1) = p2 . d1 + s * (d2 . d1)
p1 . d2 + t * (d1 . d2) = p2 . d2 + s * (d2 . d2)

and solve the linear system for (s, t).

If p1 + t * d1 = p2 + s * d2, the lines intersect at (s, t). Otherwise, p1 +
t * d1 and p2 + s * d2 are the two closest points.

(Unless of course d1 = a * d2, in which case the lines are parallel or
overlapping.)

Another application of the "find some vectors in the problem statement and
dot the equation with them, then conjure up a fake explanation of the
mathematical basis of the solution by using the word 'projection' a lot"
approach to vector equations with scalar unknowns. No Ron Levine skill level
needed - you can do it, too! :)

--
Peter Dimov
Multi Media Ltd.

Posting Wrong Stuff (was Re: [Algorithms] 3d Lines Intersection)

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

Ron,

> > (I am not a math guy...),
>
> Which is no license to post wrong stuff..

Nope.

BUT one of my reasons for posting my algorithm is that there is bound to be
a math guy like you who will open my eyes and tell me I am wrong - hence
turning this into a learning experience for myself. And, of course, there is
always a slight chance that what I post is *nearly* right and some other
clever guy on the list (of which there are quite a few) comes up with a fix
which makes the algorithm right in all cases...

In any case, I *never* post something if I know before hand that what I will
be posting is wrong. In this particular case, the faulty algorithm produced
quite convincing results when I used it (quite a while ago) - however,
looking back, the situation you used to sketch the flaws in the algorithm
never occured while I was using the algorithm. Sadly, if a flawed algorithm
works for you, it can lead you to believe that it might be correct after
all.

I contribute to this list in order to help people (and whether believe it or
not, if my post is the first in a chain of posts which will uncover a fault
in some algorithm, this also helps people to avoid my mistakes) and not to
be flamed. In the end, Ron, you have received the seemingly unwanted supreme
authority when math are concerned, and have a considerable respect for your
extensive knowledge of the area.

However, I will challenge thy knowledge when I see fit, for I learn from my
mistakes.

Having said that, can we kiss 'n make up and get on with the regular
discussion of this list?

Thanks,

Jim Offerman

Innovade
- designing the designer

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

Ron,

Your post in this matter is off topic and is nothing but a personal
attack...especially since you could not find any fault with the math
(otherwise I presume you would have written a lengthy essay on how you find
it incomplete).  I've forwarded the matter to this lists' administrator.
You seem to have some problems that we can not help you with.  This is an
algorithms list to learn and share algorithms, not play at being a math cop
as you say you are.

As to the math I shared...the people on this list don't take everything for
granted, and I make mistakes. If you want to point out any mistakes then
please do it elsewhere unless you want to work together to solve the
problem.

If it builds it and only bugs come, but turns it into a bug squasher then
it's,
Rockn-Roll

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> Sent: Saturday, July 29, 2000 10:53 PM
> To: gda...@li...
> Subject: Re: [Algorithms] 3d Lines Intersection
> 
> 
> Steve Wood  wrote:
> 
> 
> >Here is the math:
> >
> 
> This is to advise the readers of this thread that they need not fret
> if they could not follow the ensuing mess, and they ought not waste
> any more time on it if they are still trying.  Whatever it might look
> like at first glance, on close inspection it is certainly not anything
> that could properly be called math.
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Terrain Organization

[<SHA...@ao...>]

Hi,

I agree with you on ROAM...far too complicated for us mere mortals and best 
left to the gurus :)

I would suggest using a recursive QuadTree algorithm...lots of resources for 
this on the net and works pretty much as you describe

<<
 Meanwhile I am planning to split
the terrain up to several _hierarchical_ chunks (with bounding
boxes) and, for each frame, I test each chunk against the current
viewing frustum (VF) to _recursively_ determine if it has to be
submitted to the transformation and rendering pipeline
>>

John.

Re: [Algorithms] 3d Lines Intersection

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

Steve Wood  wrote:


>Here is the math:
>

This is to advise the readers of this thread that they need not fret
if they could not follow the ensuing mess, and they ought not waste
any more time on it if they are still trying.  Whatever it might look
like at first glance, on close inspection it is certainly not anything
that could properly be called math.