gdalgorithms-list

Re: [Algorithms] Quadtree / Octtree neighbors

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

Kelvin,

We had a bit of a discussion on exactly this a couple of weeks ago, check
the archive and see if you can find anything of use.

I *think* we established that other than using a cubic hash table (for the
octree case) indexed by position of a node in 3d, and using up tons of
memory, that the only way to achieve this is to jump back up the tree and
down neighbouring branches to find connectivity. But as Thatcher mentions,
this probably isn't as bad as it would seem, like half the time you are
jumping up one level, a quater of the time 2 levels, a 8th of the time 3
etc.. Check his post for more on this.

If you find anything else, I'd be interested in hearing it.

Regards,

Sam Kuhn
I!Play Ltd.
sa...@ip...



-----Original Message-----
From: Kelvin McDowell <ke...@re...>
To: 'gda...@li...'
<gda...@li...>
Date: 03 August 2000 8:52 PM
Subject: [Algorithms] Quadtree / Octtree neighbors


>I need to construct a graph which connects all the neighboring nodes of a
>quadtree and octree.  For each leaf node I need to determine all the other
>leaves that border on it.  Does anyone know of an elegant way of doing
this?
>
>Kelvin McDowell
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Return of the front clip plane

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

On Thu, 3 Aug 2000, Tom Forsyth wrote:

> Moving the near (and possibly far - depends on your app) clip planes
> dynamically works very well indeed. Yes, there is the slight artifact that
> walking past a tree affects the Z precision of the far-off building that
> you're actually looking at, but then it's pretty hard to think of any system
> that will do it any better, apart from the Z-partition trick (which is
> expensive in some cases - though dead easy for flight sims).
 
I think you want to limit the maximum value for Z near too - and doing that
at some reasonable distance (like 3 feet say) should minimise the effect
of walking past a tree.  You could also only pull the range in closer
when the object that's about to be clipped is inside the field-of-view.

At any rate, the need to not clip out the ground you are standing on
limits the maximum Z-near that you can achieve.

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

RE: [Algorithms] Bicubic normals for a bicubic world

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

I was under the impression that interpolating normals of an order-n
polynomial surface only required an (n-1) order polynomial, i.e. a
biquadratic Bezier patch in this case. But it's entirely possible I was
wrong.

Even if it's not strictly correct, I bet it would make a superb
approximation in most cases.

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

> -----Original Message-----
> From: John Sensebe [mailto:jse...@ho...]
> Sent: 04 August 2000 01:02
> To: gda...@li...
> Subject: [Algorithms] Bicubic normals for a bicubic world
> 
> 
> Hi! I'm new to this list, but already I'm asking questions... ;-)
> 
> Does anyone here know how I can approximate the normals 
> across a bicubic
> surface (i.e.: a Bezier patch) using another bicubic? I want 
> to use normals
> for backface removal, and a simpler interpolation doesn't 
> help much. On the
> other hand, an exact biquintic solution would be too 
> expensive to compute.
> 
> Thanks.
> 
> 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!
> 
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

[Algorithms] vipm instancing

[Paul F. <pa...@ar...>]

> You can do it by having a list of faces per object (faces can't be shared).
> Each object will use the same vertex buffer and the same vsplit list, but
> each object is in a different state, with different VB_Len and
> CurrentVsplit.
> This needs memory but if you have a 64k polys object you only need 64K*2
> bytes per object, which isn't very much.

This is how I'm doing it currently, the trouble is that every instance uses
the same amount of memory which is a huge waste if I have many
instances at a high distance.

Its annoying because if this idea worked and you could have instances with
almost 0 memory waste you could have crazy numbers of polys in your
scene.

I thought of maybe using some kind of linked triangle list with the extra
tris being paged in, stuck in a different chunk of ram then linked to the
last chunk. Bad fragmentation and cache trouble I fear, though...

Cheers, Paul.

RE: [Algorithms] Collisions with VIPM

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

Most people use completely separate data structures for collision and
rendering. The data you need for collision is usually very different to that
you need for rendering. For example, collision doesn't care about bumpmaps
or material data, and rendering doesn't (usually) care about connectivity
and convex/concave edges. So it's usually more cache-efficient (i.e. faster)
to have separate data structures.

In addition, most people have a rendering thread and a physics thread, and
the two are rarely in sync. Which means that sharing the data is going to
cause problems whatever you do.

Separating the data also means you can have completely different-shaped
collision data compared to your rendering data. If you're using VIPM, you
could easily have 5k poly models for things like people. For collision
meshes, 5k polys is way over the top.

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

> -----Original Message-----
> From: Oscar Blasco [mailto:tr...@te...]
> Sent: 03 August 2000 23:24
> To: 'gda...@li...'
> Subject: [Algorithms] Collisions with VIPM
> 
> 
> Hi,
> 
> How can be done fast collision detection with VIPM when it's always
> changing its morphology?, using an static version of the mesh with all
> desired polys?
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Return of the front clip plane

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

Hmmmm... I like the idea in principle - only the very near stuff (which is
hopefully quite rare) gets the extra clipping stuff, and even when it does
happen, the normal and far distance stuff isn't affected. Unfortunately, any
clipping imprecision is going to be very obvious since the objects are so
close to the camera. It might be better to move the near clip plane a bit
further away in these cases, so that any imprecision is moved further away
from the camera.

So under normal circumstances, your NCP is, say, 10m away. If anything comes
closer than 10m, you do the clipping to a plane 50m away and do Hamilton's
two-frustum trick. Maybe that'll result in fewer possible tears along the
clip lines.

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

> -----Original Message-----
> From: Feltman, Hamilton [mailto:Fe...@se...]
> Sent: 03 August 2000 21:26
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Return of the front clip plane
> 
> 
> 
> So how does this sound:
> 
> - Create a frustum which matches your graphics API's frustum
> with the exception of the near plane; for this, use the minimum
> near plane you can handle.
> 
> - Clip world geometry (or a bounding version) to this frustum
> manually just like the good old days.
> 
> - Use the closest clipped point of "whatever is left after clipping"
> to the eye plane as the distance for the near plane for a new
> frustum, send this frustum to the graphics API, and draw the
> world geometry for this frame.
> 
> I'm sure it would work; is this the way you did it?
> 
> Hamilton Feltman
> SEGA AMUS/ARCADE
> www.sega.com/alienfront
> 
> > -----Original Message-----
> > From:	Tom Forsyth [SMTP:to...@mu...]
> > Sent:	Thursday, August 03, 2000 12:46 PM
> > To:	gda...@li...
> > Subject:	RE: [Algorithms] Return of the front clip plane
> > 
> > Moving the near (and possibly far - depends on your app) clip planes
> > dynamically works very well indeed. Yes, there is the 
> slight artifact that
> > walking past a tree affects the Z precision of the far-off 
> building that
> > you're actually looking at, but then it's pretty hard to 
> think of any
> > system
> > that will do it any better, apart from the Z-partition 
> trick (which is
> > expensive in some cases - though dead easy for flight sims).
> > 
> > Tom Forsyth - Muckyfoot bloke.
> > Whizzing and pasting and pooting through the day.
> > 
> > > -----Original Message-----
> > > From: Steve Wood [mailto:Ste...@im...]
> > > Sent: 03 August 2000 20:09
> > > To: 'gda...@li...'
> > > Subject: RE: [Algorithms] Return of the front clip plane
> > > 
> > > 
> > > > -----Original Message-----
> > > > From: Jason Zisk [mailto:zi...@n-...]
> > > > 
> > > > Another solution is to just make your player's bounding 
> > > > volume larger so you can't get close enough to stuff to
> > > > clip into it, this works okay but I find that you have 
> > > > to keep the player from getting closer than 3 units with 
> > > > a 1 unit clip because of viewport rotation (just keeping the 
> > > > player 1 unit away is fine if you are staring straight at a 
> > > > wall but as soon as you rotate the edges of your viewport 
> > > > will clip it).
> > > > 
> > > 
> > > For my FPS I used a wall that I walked up to then looked up 
> > > and down, then
> > > adjusted my collision detection to prevent the player's view 
> > > from clipping
> > > the wall simply because of the view angle.  It seems to 
> work fine...I
> > > wouldn't want to get into changing the viewport dimensions 
> > > cause wouldn't it
> > > distort the scene?  I'd reserve changing viewport dimensions 
> > > for special
> > > effects like underwater wooziness.
> > > 
> > > R&R
> > > 
> > > _______________________________________________
> > > 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] Return of the front clip plane

[Robert D. <RD...@ac...>]

You could just apply real world stuff to it....

look up, you head tilts back, so your eyes will pull away from the wall.

look down, when standing with your nose against a wall and you hit the wall,
so you either collide and can't look down when against a wall or if thats
going to upset people either IK your body so the head is touching the wall,
or move the body back.

either way, in real life you cannot look down with your eyeball touching the
wall, because you aren't built that way, so applying similar limitations in
a game is not unreasonable.

Rob

-----Original Message-----
From: Jason Zisk [mailto:zi...@n-...]
Sent: 03 August 2000 23:32
To: gda...@li...
Subject: Re: [Algorithms] Return of the front clip plane


Well this is the same thing as just making the player's collision radius
smaller.  You'd still get too close to the wall and clip it out if you
looked up/down.  Maybe not left/right though, which might be where the
thought came from.  :)

I could just not let the player look up and down, doom got away with it
right?  ;)

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Robert Dibley" <RD...@ac...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 5:28 PM
Subject: RE: [Algorithms] Return of the front clip plane


> a completely mad idea, but if this is first person, then make it really
> first person ... attach the camera to the front of the viewing persons
head,
> and when they turn around the camera stays on the front of the head, and
> hence moves away from the wall.  For a real life comparison, walk up to a
> wall and turn around when you are touching it.  You will now have your
head
> a long way from the wall.  Just because people are not used to their
> characters in games behaving like real world ones doesn't mean they
> shouldn't, and maybe this is one case where if they did it would be
better.
>
> Rob
>
> -----Original Message-----
> From: Jason Zisk [mailto:zi...@n-...]
> Sent: 03 August 2000 21:08
> To: gda...@li...
> Subject: Re: [Algorithms] Return of the front clip plane
>
>
> Its wierd, for a wall this method works fine.  But for something smaller
> like a tree it "feels" wrong, like you are colliding too early.  I guess
its
> because you can see the stuff around the tree so you have a frame of
> reference?
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
> ----- Original Message -----
> From: "Steve Wood" <Ste...@im...>
> To: <gda...@li...>
> Sent: Thursday, August 03, 2000 3:09 PM
> Subject: RE: [Algorithms] Return of the front clip plane
>
>
> > > -----Original Message-----
> > > From: Jason Zisk [mailto:zi...@n-...]
> > >
> > > Another solution is to just make your player's bounding
> > > volume larger so you can't get close enough to stuff to
> > > clip into it, this works okay but I find that you have
> > > to keep the player from getting closer than 3 units with
> > > a 1 unit clip because of viewport rotation (just keeping the
> > > player 1 unit away is fine if you are staring straight at a
> > > wall but as soon as you rotate the edges of your viewport
> > > will clip it).
> > >
> >
> > For my FPS I used a wall that I walked up to then looked up and down,
then
> > adjusted my collision detection to prevent the player's view from
clipping
> > the wall simply because of the view angle.  It seems to work fine...I
> > wouldn't want to get into changing the viewport dimensions cause
wouldn't
> it
> > distort the scene?  I'd reserve changing viewport dimensions for special
> > effects like underwater wooziness.
> >
> > R&R
> >
> > _______________________________________________
> > 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


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

Re: [Algorithms] Bicubic normals for a bicubic world

[Angel P. <ju...@bi...>]

> Hi! I'm new to this list, but already I'm asking questions... ;-)
> 
> Does anyone here know how I can approximate the normals across a bicubic
> surface (i.e.: a Bezier patch) using another bicubic? I want to use normals
> for backface removal, and a simpler interpolation doesn't help much. On the
> other hand, an exact biquintic solution would be too expensive to compute.

What about creating another patch with control points displaced one unit
along the normal ( Easy to do with the control points at the corners, but what
about the other control points? This is very easy with DX8 N-Patches).
Then the normal can be computed like this:
Normal( U,V ) = P2( U,V ) - P1( U,V )

Re: [Algorithms] Bicubic normals for a bicubic world

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

I'm doing an adaptive subdivision, so I have no idea how far I'm going to be
subdividing going in.


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: "Akbar A." <sye...@ea...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 10:16 PM
Subject: RE: [Algorithms] Bicubic normals for a bicubic world


> hmm,
> if you know what your going to be subdividing too, what about a
precalculate
> lookup method for the normal data? then once you hit a certain subdivision
> level, you just look up the normal in the precalculate array?
>
> i guess you have to make one of those trade off decisions. lots of memory
> versus cpu cycles in the real time sector.
>
> isn't it acm's job to keep track of the siggraph papers?
>
> peace.
> akbar A.
>
> "We want technology for the sake of the story, not for its own sake. When
> you look back, say 10 years from now, current technology will seem quaint"
> Pixars' Edwin Catmull.
>

[Algorithms] Neighbors in quad and oct trees

[Kelvin M. <to...@nu...>]

I need to construct graphs that connect all the leaf nodes with thier
neighbors in quad and oct trees.  Is there a well-worn algorithm that given
a leaf can return all of its neighbors?


Kelvin

RE: [Algorithms] Bicubic normals for a bicubic world

[Akbar A. <sye...@ea...>]

hmm,
if you know what your going to be subdividing too, what about a precalculate
lookup method for the normal data? then once you hit a certain subdivision
level, you just look up the normal in the precalculate array?

i guess you have to make one of those trade off decisions. lots of memory
versus cpu cycles in the real time sector.

isn't it acm's job to keep track of the siggraph papers?

peace.
akbar A.

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


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of John
Sensebe
Sent: Thursday, August 03, 2000 9:09 PM
To: gda...@li...
Subject: Re: [Algorithms] Bicubic normals for a bicubic world


Well, I'm trying to avoid five cross products (one per point generated -
forty multiplies and twenty subtracts total) at every patch subdivision, not
to mention that I don't have the Bezier control points once I start
subdividing (using central diffrencing).

I just want an approximation better than linear, so the threshold value the
normals are compared against to determine backfaces can be as small as
possible.

A technique to approximate the normals with a bicubic is supposedly
described the the Proceedings of SIGGRAPH '82, but since that's so old, I
can't seem to get it anywhere.

Somehow, I think finding the Holy Grail would be easier... ;-)

Thanks again.

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: "Akbar A." <sye...@ea...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 8:21 PM
Subject: RE: [Algorithms] Bicubic normals for a bicubic world


> hello john,
> expensive?
>
> calculate the tangent vectors, compute cross products at each corner of
> patch.
>



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

Re: [Algorithms] Bicubic normals for a bicubic world

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

Well, I'm trying to avoid five cross products (one per point generated -
forty multiplies and twenty subtracts total) at every patch subdivision, not
to mention that I don't have the Bezier control points once I start
subdividing (using central diffrencing).

I just want an approximation better than linear, so the threshold value the
normals are compared against to determine backfaces can be as small as
possible.

A technique to approximate the normals with a bicubic is supposedly
described the the Proceedings of SIGGRAPH '82, but since that's so old, I
can't seem to get it anywhere.

Somehow, I think finding the Holy Grail would be easier... ;-)

Thanks again.

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: "Akbar A." <sye...@ea...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 8:21 PM
Subject: RE: [Algorithms] Bicubic normals for a bicubic world


> hello john,
> expensive?
>
> calculate the tangent vectors, compute cross products at each corner of
> patch.
>

RE: [Algorithms] Bicubic normals for a bicubic world

[Akbar A. <sye...@ea...>]

hello john,
expensive?

calculate the tangent vectors, compute cross products at each corner of
patch.

lamens;
calculate normals to the parametric surface at the patch corners and assign
these values to the relevant surfaces

>interpolation doesn't help much
you where probably just assigning the plane normals to the triangles,
instead of doing the method above. this should improve your results.

doesn't dx8 have some high level code that does this ??

watt and watt, "advanced animation and rendering techniques"
has a wonderful section on this topic.
page 83

hope this helps, if you need more details please ask.

peace.
akbar A.

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


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of John
Sensebe
Sent: Thursday, August 03, 2000 7:02 PM
To: gda...@li...
Subject: [Algorithms] Bicubic normals for a bicubic world


Hi! I'm new to this list, but already I'm asking questions... ;-)

Does anyone here know how I can approximate the normals across a bicubic
surface (i.e.: a Bezier patch) using another bicubic? I want to use normals
for backface removal, and a simpler interpolation doesn't help much. On the
other hand, an exact biquintic solution would be too expensive to compute.

Thanks.

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!




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

Re: [Algorithms] Collisions with VIPM

[Oscar B. <tr...@te...>]

I'm thinking on terrain and level (map) collision, not in small objects
collision, something I will do with an octree for static and non-static object
(for moving ones I may try another stratregy...). The hardest part is terrain
collision, we can subdivide our terrain in chunks but if they have many polys,
it isn't a good idea to use the current mesh directly. At the moment, I only can
imagine to use a mesh with fewer polys and skip chunks that can be touched using
an octree and portals (these two things can be used to fast visibility skips )
but this can fail in some specific tasks. I ask if there's another way to do
this....

Mark Wayland wrote:

> The OBB tree is used for coarse collision detection - a single OBB may even
> be enough, depending on the shape of your object ... it depends what form of
> collision detection you need - do you need polygon level or just rough OBB ?
>
> Perhaps you could maintain a convex hull generated from the VIPM mesh every
> so often, which may be good enough for your needs ?  I believe Stan Melax
> has done some work on dynamic reduction of the convex hull too ... check out
> his site (sorry, don't have the link at the mo').
>
> Mark
>
> ----- Original Message -----
> From: "Oscar Blasco" <tr...@te...>
> To: <gda...@li...>
> Sent: Friday, August 04, 2000 9:06 AM
> Subject: Re: [Algorithms] Collisions with VIPM
>
> > Ok, when I said *desired polys* I was thinking on fewer polys, but it can
> > cause object to collide with nothing (aka air...). I'm not sure what you
> > want to say with using OBB's... divide the VIPMesh in subchunks and make a
> > tree of OBB's to quickly skip parts of the model?
> >
> > Charles Bloom wrote:
> >
> > > Or, even better, using a static version of the mesh with *fewer*
> > > polys.  Better still, use a sphere-tree or OBB-tree fit to
> > > the mesh with roughly 100 spheres and/or OBB's.
> > >
> > > At 12:24 AM 8/4/2000 +0200, you wrote:
> > > >Hi,
> > > >
> > > >How can be done fast collision detection with VIPM when it's always
> > > >changing its morphology?, using an static version of the mesh with all
> > > >desired polys?
> > > >
> > > >
> > > >_______________________________________________
> > > >GDAlgorithms-list mailing list
> > > >GDA...@li...
> > > >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > > >
> > > >
> > > --------------------------------------
> > > Charles Bloom           www.cbloom.com
> > >
> > > _______________________________________________
> > > 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] OBBs

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

Are you sure about the fact it's invalid ? I would be very interested to
know if this is true or not. This is weird because I've used Rapid without
any problem.

----- Original Message -----
From: Kent Quirk <ken...@co...>
To: <gda...@li...>
Sent: Friday, July 21, 2000 2:33 PM
Subject: Re: [Algorithms] OBBs


> Nik...@ao... wrote:
> > I recently finished writing a collision detection system for my engine
(using
> > OBBs); however I have been having trouble with the system not always
> > detecting collisions.  I tested all of the functions separately to
confirm
> > their accuracy; yet this brought no avail.  I decided to work backwards
to
> > find the bug, and I used a function from the RAPID library which tests
for
> > disjointedness between two boxes.  Here is the description of the
function:
> >
> > This is a test between two boxes, box A and box B.  It is assumed that
> > the coordinate system is aligned and centered on box A.  The 3x3
> > matrix B specifies box B's orientation with respect to box A.
> > Specifically, the columns of B are the basis vectors (axis vectors) of
> > box B.  The center of box B is located at the vector T.  The
> > dimensions of box B are given in the array b.  The orientation and
> > placement of box A, in this coordinate system, are the identity matrix
> > and zero vector, respectively, so they need not be specified.  The
> > dimensions of box A are given in array a.
> >     obb_disjoint(double B[3][3], double T[3], double a[3], double b[3]);
> >
> > I set up a situation in Max using two boxes, in which the collision
detection
> > failed, and I then entered the box data in by hand.  The result was that
> > after putting box 2 in box 1's coordinate system, the matrix B was a 128
> > degree rotation around the Z axis (or Max's Y axis).  The location of
box 2
> > in relation to box 1 was:
> >     T[0]= -5.853f;
> >     T[1]= -2.173f;
> >     T[2]= 3.842f;
> > And the dimensions (half-lengths) were:
> >     Bd[0]= 2;  Bd[1]= 4; Bd[2]= 4.5;
> >     Ad[0]= 4;  Ad[1]= 1; Ad[2]= 7.5;
> > If you set this situation up in Max, it is obvious that the two boxes
> > intersect (make sure to switch the Y & Z coordinates because of the
> > difference in D3D and Max's CS, and multiply the half-lengths by 2 to
get the
> > actual dimensions).  Yet, RAPID's function reports that the boxes are
> > disjoint.  Any help would be appreciated.
>
> I too struggled with this for a long time.
>
> After I had given up, and gone to another collision system, someone else
> reported that RAPID's OBB intersection algorithm (as documented) is too
> optimistic in its use of absolute value. There is a matrix in the code
> that gets built as the absolute values of another matrix, thereby saving
> some steps...but that's an invalid savings.  Sadly, I can't find the
> reference. But I hope this points you in the right direction, or perhaps
> someone else has a better memory.
>
> Kent
>
> --
> -----------------------------------------------------------------------
> Kent Quirk                   | CogniToy: Intelligent toys...
> Game Designer                |           for intelligent minds.
> ken...@co...      | http://www.cognitoy.com/
> _____________________________|_________________________________________
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Collisions with VIPM

[Mark W. <mwa...@to...>]

The OBB tree is used for coarse collision detection - a single OBB may even
be enough, depending on the shape of your object ... it depends what form of
collision detection you need - do you need polygon level or just rough OBB ?

Perhaps you could maintain a convex hull generated from the VIPM mesh every
so often, which may be good enough for your needs ?  I believe Stan Melax
has done some work on dynamic reduction of the convex hull too ... check out
his site (sorry, don't have the link at the mo').

Mark

----- Original Message -----
From: "Oscar Blasco" <tr...@te...>
To: <gda...@li...>
Sent: Friday, August 04, 2000 9:06 AM
Subject: Re: [Algorithms] Collisions with VIPM


> Ok, when I said *desired polys* I was thinking on fewer polys, but it can
> cause object to collide with nothing (aka air...). I'm not sure what you
> want to say with using OBB's... divide the VIPMesh in subchunks and make a
> tree of OBB's to quickly skip parts of the model?
>
> Charles Bloom wrote:
>
> > Or, even better, using a static version of the mesh with *fewer*
> > polys.  Better still, use a sphere-tree or OBB-tree fit to
> > the mesh with roughly 100 spheres and/or OBB's.
> >
> > At 12:24 AM 8/4/2000 +0200, you wrote:
> > >Hi,
> > >
> > >How can be done fast collision detection with VIPM when it's always
> > >changing its morphology?, using an static version of the mesh with all
> > >desired polys?
> > >
> > >
> > >_______________________________________________
> > >GDAlgorithms-list mailing list
> > >GDA...@li...
> > >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > >
> > >
> > --------------------------------------
> > Charles Bloom           www.cbloom.com
> >
> > _______________________________________________
> > 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

[Algorithms] Virtual vertices in Butterfly scheme

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

Hi,

Here I go again with a question about the virtual vertices in the modified
Butterfly scheme. Here's an excerpt from Sig'96 paper:

"Edges which are not on the boundary but which have a vertex which is on the
boundary are subdivided as before while any vertices in the stencil which
would be on the other side of the boundary are replaced with "virtual"
vertices."

Let's examine two cases. In all of them we are in the situation described
above.

1) The boundary vertex has a valence of 4:

How many virtual vertices am I supposed to create? Until now, I've alwayd
blindly created enough virtual vertices to transform the vertex into a
regular one (valence = 6), but this is not explicitely written in Zorin's
paper.

What if I just use the extraordinary scheme for valence = 4, without
creating virtual vertices?

2) The boundary vertex has a valence of more than 6, say 7:

Here's the case I'm having a lot of trouble with. Actually that's why I'm
suddenly writing this message. I recently found that one is a particular
mesh, and my code crashed. Because, of course, I tried to create enough
virtual vertices to reach valence 6, ie "-1" vertex. Err... What ?!

Here, the only correct behaviour looks like using the standard extraordinary
scheme for valence = 7, without creating virtual vertices. But if this is
the case, why shouldn't I just do the same in 1)....? And if this is not the
correct behaviour, what is it? Am I supposed to create virtual vertices in
that case? How many and how ?


Puzzled again.


/*
Pierre Terdiman       *   Home: p.t...@wa...
Software engineer    *   Zappy's Lair:  www.codercorner.com
*/

[Algorithms] Bicubic normals for a bicubic world

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

Hi! I'm new to this list, but already I'm asking questions... ;-)

Does anyone here know how I can approximate the normals across a bicubic
surface (i.e.: a Bezier patch) using another bicubic? I want to use normals
for backface removal, and a simpler interpolation doesn't help much. On the
other hand, an exact biquintic solution would be too expensive to compute.

Thanks.

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!

Re: [Algorithms] Collisions with VIPM

[Oscar B. <tr...@te...>]

Ok, when I said *desired polys* I was thinking on fewer polys, but it can
cause object to collide with nothing (aka air...). I'm not sure what you
want to say with using OBB's... divide the VIPMesh in subchunks and make a
tree of OBB's to quickly skip parts of the model?

Charles Bloom wrote:

> Or, even better, using a static version of the mesh with *fewer*
> polys.  Better still, use a sphere-tree or OBB-tree fit to
> the mesh with roughly 100 spheres and/or OBB's.
>
> At 12:24 AM 8/4/2000 +0200, you wrote:
> >Hi,
> >
> >How can be done fast collision detection with VIPM when it's always
> >changing its morphology?, using an static version of the mesh with all
> >desired polys?
> >
> >
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDA...@li...
> >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> >
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Collisions with VIPM

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

Or, even better, using a static version of the mesh with *fewer*
polys.  Better still, use a sphere-tree or OBB-tree fit to
the mesh with roughly 100 spheres and/or OBB's.

At 12:24 AM 8/4/2000 +0200, you wrote:
>Hi,
>
>How can be done fast collision detection with VIPM when it's always
>changing its morphology?, using an static version of the mesh with all
>desired polys?
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] Return of the front clip plane

[Jason Z. <zi...@n-...>]

Well this is the same thing as just making the player's collision radius
smaller.  You'd still get too close to the wall and clip it out if you
looked up/down.  Maybe not left/right though, which might be where the
thought came from.  :)

I could just not let the player look up and down, doom got away with it
right?  ;)

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Robert Dibley" <RD...@ac...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 5:28 PM
Subject: RE: [Algorithms] Return of the front clip plane


> a completely mad idea, but if this is first person, then make it really
> first person ... attach the camera to the front of the viewing persons
head,
> and when they turn around the camera stays on the front of the head, and
> hence moves away from the wall.  For a real life comparison, walk up to a
> wall and turn around when you are touching it.  You will now have your
head
> a long way from the wall.  Just because people are not used to their
> characters in games behaving like real world ones doesn't mean they
> shouldn't, and maybe this is one case where if they did it would be
better.
>
> Rob
>
> -----Original Message-----
> From: Jason Zisk [mailto:zi...@n-...]
> Sent: 03 August 2000 21:08
> To: gda...@li...
> Subject: Re: [Algorithms] Return of the front clip plane
>
>
> Its wierd, for a wall this method works fine.  But for something smaller
> like a tree it "feels" wrong, like you are colliding too early.  I guess
its
> because you can see the stuff around the tree so you have a frame of
> reference?
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
> ----- Original Message -----
> From: "Steve Wood" <Ste...@im...>
> To: <gda...@li...>
> Sent: Thursday, August 03, 2000 3:09 PM
> Subject: RE: [Algorithms] Return of the front clip plane
>
>
> > > -----Original Message-----
> > > From: Jason Zisk [mailto:zi...@n-...]
> > >
> > > Another solution is to just make your player's bounding
> > > volume larger so you can't get close enough to stuff to
> > > clip into it, this works okay but I find that you have
> > > to keep the player from getting closer than 3 units with
> > > a 1 unit clip because of viewport rotation (just keeping the
> > > player 1 unit away is fine if you are staring straight at a
> > > wall but as soon as you rotate the edges of your viewport
> > > will clip it).
> > >
> >
> > For my FPS I used a wall that I walked up to then looked up and down,
then
> > adjusted my collision detection to prevent the player's view from
clipping
> > the wall simply because of the view angle.  It seems to work fine...I
> > wouldn't want to get into changing the viewport dimensions cause
wouldn't
> it
> > distort the scene?  I'd reserve changing viewport dimensions for special
> > effects like underwater wooziness.
> >
> > R&R
> >
> > _______________________________________________
> > 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

[Algorithms] Collisions with VIPM

[Oscar B. <tr...@te...>]

Hi,

How can be done fast collision detection with VIPM when it's always
changing its morphology?, using an static version of the mesh with all
desired polys?

RE: [Algorithms] Return of the front clip plane

[Robert D. <RD...@ac...>]

a completely mad idea, but if this is first person, then make it really
first person ... attach the camera to the front of the viewing persons head,
and when they turn around the camera stays on the front of the head, and
hence moves away from the wall.  For a real life comparison, walk up to a
wall and turn around when you are touching it.  You will now have your head
a long way from the wall.  Just because people are not used to their
characters in games behaving like real world ones doesn't mean they
shouldn't, and maybe this is one case where if they did it would be better.

Rob

-----Original Message-----
From: Jason Zisk [mailto:zi...@n-...]
Sent: 03 August 2000 21:08
To: gda...@li...
Subject: Re: [Algorithms] Return of the front clip plane


Its wierd, for a wall this method works fine.  But for something smaller
like a tree it "feels" wrong, like you are colliding too early.  I guess its
because you can see the stuff around the tree so you have a frame of
reference?

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Steve Wood" <Ste...@im...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 3:09 PM
Subject: RE: [Algorithms] Return of the front clip plane


> > -----Original Message-----
> > From: Jason Zisk [mailto:zi...@n-...]
> >
> > Another solution is to just make your player's bounding
> > volume larger so you can't get close enough to stuff to
> > clip into it, this works okay but I find that you have
> > to keep the player from getting closer than 3 units with
> > a 1 unit clip because of viewport rotation (just keeping the
> > player 1 unit away is fine if you are staring straight at a
> > wall but as soon as you rotate the edges of your viewport
> > will clip it).
> >
>
> For my FPS I used a wall that I walked up to then looked up and down, then
> adjusted my collision detection to prevent the player's view from clipping
> the wall simply because of the view angle.  It seems to work fine...I
> wouldn't want to get into changing the viewport dimensions cause wouldn't
it
> distort the scene?  I'd reserve changing viewport dimensions for special
> effects like underwater wooziness.
>
> R&R
>
> _______________________________________________
> 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] Return of the front clip plane

[Feltman, H. <Fe...@se...>]

So how does this sound:

- Create a frustum which matches your graphics API's frustum
with the exception of the near plane; for this, use the minimum
near plane you can handle.

- Clip world geometry (or a bounding version) to this frustum
manually just like the good old days.

- Use the closest clipped point of "whatever is left after clipping"
to the eye plane as the distance for the near plane for a new
frustum, send this frustum to the graphics API, and draw the
world geometry for this frame.

I'm sure it would work; is this the way you did it?

Hamilton Feltman
SEGA AMUS/ARCADE
www.sega.com/alienfront

> -----Original Message-----
> From:	Tom Forsyth [SMTP:to...@mu...]
> Sent:	Thursday, August 03, 2000 12:46 PM
> To:	gda...@li...
> Subject:	RE: [Algorithms] Return of the front clip plane
> 
> Moving the near (and possibly far - depends on your app) clip planes
> dynamically works very well indeed. Yes, there is the slight artifact that
> walking past a tree affects the Z precision of the far-off building that
> you're actually looking at, but then it's pretty hard to think of any
> system
> that will do it any better, apart from the Z-partition trick (which is
> expensive in some cases - though dead easy for flight sims).
> 
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
> 
> > -----Original Message-----
> > From: Steve Wood [mailto:Ste...@im...]
> > Sent: 03 August 2000 20:09
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] Return of the front clip plane
> > 
> > 
> > > -----Original Message-----
> > > From: Jason Zisk [mailto:zi...@n-...]
> > > 
> > > Another solution is to just make your player's bounding 
> > > volume larger so you can't get close enough to stuff to
> > > clip into it, this works okay but I find that you have 
> > > to keep the player from getting closer than 3 units with 
> > > a 1 unit clip because of viewport rotation (just keeping the 
> > > player 1 unit away is fine if you are staring straight at a 
> > > wall but as soon as you rotate the edges of your viewport 
> > > will clip it).
> > > 
> > 
> > For my FPS I used a wall that I walked up to then looked up 
> > and down, then
> > adjusted my collision detection to prevent the player's view 
> > from clipping
> > the wall simply because of the view angle.  It seems to work fine...I
> > wouldn't want to get into changing the viewport dimensions 
> > cause wouldn't it
> > distort the scene?  I'd reserve changing viewport dimensions 
> > for special
> > effects like underwater wooziness.
> > 
> > R&R
> > 
> > _______________________________________________
> > 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] Return of the front clip plane

[Jason Z. <zi...@n-...>]

Its wierd, for a wall this method works fine.  But for something smaller
like a tree it "feels" wrong, like you are colliding too early.  I guess its
because you can see the stuff around the tree so you have a frame of
reference?

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Steve Wood" <Ste...@im...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 3:09 PM
Subject: RE: [Algorithms] Return of the front clip plane


> > -----Original Message-----
> > From: Jason Zisk [mailto:zi...@n-...]
> >
> > Another solution is to just make your player's bounding
> > volume larger so you can't get close enough to stuff to
> > clip into it, this works okay but I find that you have
> > to keep the player from getting closer than 3 units with
> > a 1 unit clip because of viewport rotation (just keeping the
> > player 1 unit away is fine if you are staring straight at a
> > wall but as soon as you rotate the edges of your viewport
> > will clip it).
> >
>
> For my FPS I used a wall that I walked up to then looked up and down, then
> adjusted my collision detection to prevent the player's view from clipping
> the wall simply because of the view angle.  It seems to work fine...I
> wouldn't want to get into changing the viewport dimensions cause wouldn't
it
> distort the scene?  I'd reserve changing viewport dimensions for special
> effects like underwater wooziness.
>
> R&R
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list