gdalgorithms-list

[Algorithms] Info about quadtree

[JB <ma...@sd...>]

Hi
I'm looking dor infos about quadtrees. It doesn't seem to be too complex,
but It would be fine if I could find some example... 
Thx
Mandor 

ma...@sd...
SDF Public Access UNIX System - http://sdf.lonestar.org

RE: [Algorithms] Smooth movement of camera along a path

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

I don't see how the lookattarget thing will solve the orientation problem.
You still need an 'up' vector, as you could be rotated any way around the
lookattarget vector.

While on the subject, as long as you are implementing splines for your
cameras, and these splines are to be modelled by artists, you may want to
think about having separate camera and target splines. We had this in a 3D
CAD driver I once worked on, and it was cool because you could do things
like have a whole number of keyframes on the target path, all sitting at an
interesting object, and then have the camera turn during it's 'flyby' to
focus on a specific area while maintaining it's speed.

Kim Pallister

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


> -----Original Message-----
> From: Robert Dibley [mailto:RD...@ac...]
> Sent: Wednesday, August 02, 2000 2:11 AM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Smooth movement of camera along a path
> 
> 
> Just a quick note to say that one way to solve the problem of 
> orientations
> is to not use them at all, but instead interpolate your 
> "target" along with
> your camera, so that you just build a camera that looks at 
> the target ...
> which you would then naturally avoid tilting.  Of course if you _want_
> tilting cameras this is no use whatsoever !
> 
> Rob
> 
> -----Original Message-----
> From: Peter Warden [mailto:Pet...@vi...]
> Sent: 01 August 2000 12:40
> To: gda...@li...
> Subject: RE: [Algorithms] Smooth movement of camera along a path
> 
> 
> I've done a couple of similar systems, and I've found the 
> problem to be
> deceptively tricky, a few things I ran across that weren't 
> obvious to me
> when I started;
> 
> -Whatever spline you pick to move the camera's position, 
> you'll need to be
> aware that changing the parameter to the spline isn't proportional to
> distance along the spline, eg a u parameter of 0.5 may 
> correspond to a point
> that's only 0.25 of the total distance along the spline. This 
> means that
> some compensation will be needed if you want the camera to move at a
> constant speed, or to accelerate and decelerate under your 
> control. One
> solution I used was to sample the spline at many points, and 
> construct a
> series of (very small) straight lines to represent the 
> spline. This let me
> do distance calculations and get smooth movement, at the cost 
> of being a bit
> inelegant. Advanced Animation and Rendering Techniques, 
> Watt&Watt, 15.3.2
> has a good discussion of this, and some other ways of solving 
> the problem.
> 
> -Splines will solve the movement problem, but not necessarily the
> orientation one. Interpolation between orientations is a big 
> subject, and
> took a lot more time than I expected!
> 
> -It's not just a maths problem, there's a lot of quirky human 
> stuff that
> needs to taken into account to get a camera moving in a way 
> that people will
> like. A good example of this is interpolating orientations, 
> it's very easy
> to end up with interpolated orientations that are tilted in 
> uncomfortable
> ways.
> 
> Having been a wet blanket with all this, I would say on the 
> positive side
> that adding extra keyframes so you aren't putting too much 
> strain on the
> interpolation code solves a lot of the problems, and most 
> others can be
> solved by working around them.
> 
> AA&RT, Watt and Watt, is an excellent source for info on the subject.
> 
> Peter Warden
> 
> > -----Original Message-----
> > From: Mark Wilczynski [mailto:mwi...@cy...]
> > Sent: Monday, July 31, 2000 11:04 PM
> > To: gda...@li...
> > Subject: [Algorithms] Smooth movement of camera along a path
> > 
> > 
> > I'm trying to write a fly-by sequence (similar to the Unreal
> > intro) for my 3d engine.  Can anyone tell me how to smoothly
> > move the camera along a set of predefined 3d points?
> > Ideally,  I would like a system where I manually move the
> > camera around the environment and record keyframes at
> > certain positions/orientations.  Then I would like the
> > system to automatically move the camera along a path
> > interpolated from these keyframes.  I'm guessing I need some
> > sort of spline or other curve to do the job?
> > 
> > -Mark
> > 
> > 
> > _______________________________________________
> > 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] Some N-Patch questions...

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

welcome to the world of subdivision.

there was a zip file somewhere on the web.
the name of the actual file was sig99notes.pdf
there was a big presention done and they just wrapped all the "mini"
presenations into one big file.
_very_ handy.
the "booklet" goes from "begginer" material all the way to a closing
thoughts on surface subdivision with geri (pixars' model, the short can be
found in Bugs' Life). For some weird reason the file takes a long time to
"draw" the models. i never knew that adobe acrobat could load model data?
you will understand if you see the paper.

the lectures are
Denis Zorin
Tony DeRose (pixar)
Leif Kobbelt
Peter Schroder
Jos Stam
Joe Warren		http://www.cs.rice.edu/~jwarren/ (there should be a link at his
site. he has a lot of mathamteical represention material)

eric, you should add this to your site if it's not up there already :-)

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 Peter
Warden
Sent: Sunday, August 06, 2000 12:13 PM
To: gda...@li...
Subject: [Algorithms] Some N-Patch questions...


I've been following the discussion on N-Patches, and whilst I was at home
this weekend, I had a few ideas for modifications, and I thought I'd throw
them open for discussion.

I use the same method as ATI to calculate the 9 control points of the bezier
lines along each edge of each tri, except I change their 'divide projection
of edge onto plane by 3' into a multiplication by an arbitrary tangent scale
factor, which works best in the range 0 to 0.5.(*1)

We now have 9 control points effectively forming 3, 3D bezier lines along
each edge. I then use the bezier curve convex hull subdivision formula from
Watt&Watt, 3.4.1, page 81, to calculate the midpoint of each bezier
curve.(*2)

I use each of these midpoints as a new vertex to split the original triangle
into 4. To calculate the normals at each new vertex, I interpolate halfway
between the two adjacent original normals, eg
MidNorm=Cos(45)*Norm0+Sin(45)*Norm1.

I then keep doing this recursively on each of the four triangles, either to
a fixed level or until some heuristic is satisfied.

I've tried a test implementation, and it seems to give quite pretty results
on the single tetrahedron I've tried. It also tends towards a surface with
G1 continuity, I think, which ATI's patches don't.

One other nice thing about this scheme is that if information is only used
from a single edge in the 'should we split this edge' heuristic, you
automatically get no cracking since no per-face info is involved.

Thoughts? Does it make sense? I'm not on the DirectX beta, so I haven't seen
any discussion of N-patches apart from this list, and I'm just getting to
grips with subdivision surfaces, so if anyone can point me in the direction
of prior work on schemes like this, I'd be grateful.

Peter Warden

(*1) The tangent scale works a bit like a weight, a small value gives a
bevelled appearance, and it tends towards blobbyness as it increases. Out of
the range 0-0.5, you get some very weird and wonderful stuff!

(*2) This formula only involves additions, multiplies and divisions by 2, so
it's quite efficient. I always wanted to use it for something, since it is
so elegant, but those darn floating point units always made it faster to
calculate the full formula than use recursion on the machines I've
implemented beziers on.


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

[Algorithms] Some N-Patch questions...

[Peter W. <Pet...@vi...>]

I've been following the discussion on N-Patches, and whilst I was at home
this weekend, I had a few ideas for modifications, and I thought I'd throw
them open for discussion.

I use the same method as ATI to calculate the 9 control points of the bezier
lines along each edge of each tri, except I change their 'divide projection
of edge onto plane by 3' into a multiplication by an arbitrary tangent scale
factor, which works best in the range 0 to 0.5.(*1)

We now have 9 control points effectively forming 3, 3D bezier lines along
each edge. I then use the bezier curve convex hull subdivision formula from
Watt&Watt, 3.4.1, page 81, to calculate the midpoint of each bezier
curve.(*2)

I use each of these midpoints as a new vertex to split the original triangle
into 4. To calculate the normals at each new vertex, I interpolate halfway
between the two adjacent original normals, eg
MidNorm=Cos(45)*Norm0+Sin(45)*Norm1.

I then keep doing this recursively on each of the four triangles, either to
a fixed level or until some heuristic is satisfied.

I've tried a test implementation, and it seems to give quite pretty results
on the single tetrahedron I've tried. It also tends towards a surface with
G1 continuity, I think, which ATI's patches don't.

One other nice thing about this scheme is that if information is only used
from a single edge in the 'should we split this edge' heuristic, you
automatically get no cracking since no per-face info is involved.

Thoughts? Does it make sense? I'm not on the DirectX beta, so I haven't seen
any discussion of N-patches apart from this list, and I'm just getting to
grips with subdivision surfaces, so if anyone can point me in the direction
of prior work on schemes like this, I'd be grateful.

Peter Warden

(*1) The tangent scale works a bit like a weight, a small value gives a
bevelled appearance, and it tends towards blobbyness as it increases. Out of
the range 0-0.5, you get some very weird and wonderful stuff!

(*2) This formula only involves additions, multiplies and divisions by 2, so
it's quite efficient. I always wanted to use it for something, since it is
so elegant, but those darn floating point units always made it faster to
calculate the full formula than use recursion on the machines I've
implemented beziers on.

Re: [Algorithms] OBBs

[Kent Q. <ken...@co...>]

I'm sorry. I don't have time right now to go back and dig up work from
two years ago. I was trying to be helpful and point out that a) a long
time ago, I had problems similar to those described, and b) I vaguely
remember someone pointing out that THEY had discovered a problem. 

I hoped it was helpful. If it's not helpful to you, ignore it. That's
all I can tell you right now.

Pierre Terdiman wrote:
> 
> I'm afraid I don't get it.
> 
> You told us about the matrix made of absolute values. That one actually is
> in the RAPID source, in the obb_disjoint function. And you said that taking
> the absolute values was too optimistic. So, why would it work within the
> RAPID code, if it doesn't work in theory according to you ?
> 
> Confusing.
> 
> ----- Original Message -----
> From: Kent Quirk <ken...@co...>
> To: <gda...@li...>
> Sent: Sunday, August 06, 2000 7:19 AM
> Subject: Re: [Algorithms] OBBs
> 
> > Because of the legal use restrictions I did not read the RAPID code, but
> > reconstructed my own code from the original paper. I was extremely
> > careful, and had the same problems described here -- certain
> > orientations of bounding boxes that were clearly intersecting would be
> > reported as disjoint. I even reconstructed it in a spreadsheet.
> >
> > I have not gone back to see if I could make it work.
> >
> > If you used the RAPID source, I believe it works properly.
> >
> > Kent
> >
> >
> > Pierre Terdiman wrote:
> > >
> > > 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
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> > --
> > -----------------------------------------------------------------------
> > Kent Quirk                   | CogniToy: Intelligent toys...
> > Game Architect               |           for intelligent minds.
> > ken...@co...      | http://www.cognitoy.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

-- 
-----------------------------------------------------------------------
Kent Quirk                   | CogniToy: Intelligent toys...
Game Architect               |           for intelligent minds.
ken...@co...      | http://www.cognitoy.com/     
_____________________________|_________________________________________

[Algorithms] Re: Some questions about N-Patches...

[Peter W. <pet...@ho...>]

This is just a correction for my last message on N-Patches. I just realised 
that the normal interpolation formula I gave was wrong. I used the formula 
NewNormal=Cos(45)*Normal0+Sin(45)*Normal1. This only works when the normals 
are perpendicular to each other (as in the case of my first test mesh).

I'll have to look at spherical interpolation for normals more closely, I 
have the feeling that I can take the cross-product of the two normals, use 
that as the axis of rotation to rotate around. I'm sure there are simpler 
approximations out there as well. Linearly interpolating between the two 
normals, eg NewNormal=0.5*Normal0+0.5*Normal1, and then renormalising to get 
back to unit length sounds good too.

Peter Warden
________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

Re: [Algorithms] Neighbors in quad and oct trees

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

From: Kelvin McDowell <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?

Didn't we just go through this?  I guess nobody posted actual code.  Here's
some code for quadtree neighbor-finding:

qsquare* GetNeighbor(int dir, const quadcornerdata& cd)
// Traverses the tree in search of the qsquare neighboring this
// square to the specified direction.  The directions are 0-3
// --> { E, N, W, S }.  Returns NULL if the neighbor doesn't
// exist.
//
// ChildIndex mapping:
// +-+-+
// |1|0|
// +-+-+
// |2|3|
// +-+-+
{
  // If we don't have a parent, then we don't have a neighbor.
  if (cd.Parent == 0) return 0;

  // Find the parent and the child-index of the square we want to locate.
  qsquare* p = 0;

  int index = cd.ChildIndex ^ 1 ^ ((dir & 1) << 1);
  bool SameParent = ((dir - cd.ChildIndex) & 2) ? true : false;

  if (SameParent) {
   p = cd.Parent->Square;
  } else {
   p = cd.Parent->Square->GetNeighbor(dir, *cd.Parent);

   if (p == 0) return 0;
  }

  qsquare* n = p->ChildLink[index];

  return n;
 }


--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] OBBs

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

I'm afraid I don't get it.

You told us about the matrix made of absolute values. That one actually is
in the RAPID source, in the obb_disjoint function. And you said that taking
the absolute values was too optimistic. So, why would it work within the
RAPID code, if it doesn't work in theory according to you ?

Confusing.

----- Original Message -----
From: Kent Quirk <ken...@co...>
To: <gda...@li...>
Sent: Sunday, August 06, 2000 7:19 AM
Subject: Re: [Algorithms] OBBs


> Because of the legal use restrictions I did not read the RAPID code, but
> reconstructed my own code from the original paper. I was extremely
> careful, and had the same problems described here -- certain
> orientations of bounding boxes that were clearly intersecting would be
> reported as disjoint. I even reconstructed it in a spreadsheet.
>
> I have not gone back to see if I could make it work.
>
> If you used the RAPID source, I believe it works properly.
>
> Kent
>
>
> Pierre Terdiman wrote:
> >
> > 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
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> --
> -----------------------------------------------------------------------
> Kent Quirk                   | CogniToy: Intelligent toys...
> Game Architect               |           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] OBBs

[Kent Q. <ken...@co...>]

Because of the legal use restrictions I did not read the RAPID code, but
reconstructed my own code from the original paper. I was extremely
careful, and had the same problems described here -- certain
orientations of bounding boxes that were clearly intersecting would be
reported as disjoint. I even reconstructed it in a spreadsheet.

I have not gone back to see if I could make it work.

If you used the RAPID source, I believe it works properly.

	Kent


Pierre Terdiman wrote:
> 
> 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
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

-- 
-----------------------------------------------------------------------
Kent Quirk                   | CogniToy: Intelligent toys...
Game Architect               |           for intelligent minds.
ken...@co...      | http://www.cognitoy.com/     
_____________________________|_________________________________________

Re: [Algorithms] fast triangle-segment test *with precomputation*

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

In a message dated 05/08/00 01:53:24 !!!First Boot!!!, 
Chr...@Pl... writes:

<< That only works as a conservative test, but not as an exact test.
 
 If the box, straddling the triangle plane, is just outside one of the
 vertices of the triangle, then both criteria are met, but there's no
 actual intersection. >>

I am currently doing a triangle/aabb test for an octree implimentation. This 
test is as near as exact as I can think of. It does 3 tests, each one more 
time consuming than the last...

1) Are any of the 3 tri vertices inside bbox...if so return true
2) Does any tri edge intersect bbox face...if so return true
3) Generate 8 lines, each one connects a corner of the aabb to it's diagonal 
opposite then test, does this line intersect tri face...if so return true
return false.

The last test is in case any corner of the aabb punches through the face of 
the tri, in which case the tri is technically inside the aabb.

How do you do yours??

John.

RE: [Algorithms] fast triangle-segment test *with precomputation*

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

Charles Bloom wrote:
>Urgh; of course you're right; boxes that are outside but
>near the corners are classified wrong.  I think you could
>probably detect that case and handle it from there; eg.
>when the box straddles two edge planes, look at the vertex
>those planes share, and then test whether the box is away
>or towards the center of the triangle relative to that vertex
>(or something).

I kinda seems that way, doesn't it, but it's not quite that
easy I'm afraid.

Consider all the relative orientations that the triangle and
the box can be in, and I think you'll find that what you'll end
up with is going to be equivalent to doing all the required
separating axis tests.

Let's see... 3 for the edges/face normals of the box, 1 triangle
face normal, 3 triangle edges, and 9 for combination of edges of
both, so 16 axes.

Christer Ericson
SCEA, Santa Monica

RE: [Algorithms] fast triangle-segment test *with precomputation*

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

Urgh; of course you're right; boxes that are outside but
near the corners are classified wrong.  I think you could
probably detect that case and handle it from there; eg.
when the box straddles two edge planes, look at the vertex
those planes share, and then test whether the box is away
or towards the center of the triangle relative to that vertex
(or something).

At 06:51 PM 8/4/2000 -0700, you wrote:
>
>
>
>
>Charles Bloom wrote:
>>Ok, you have a good point, but isn't it even simpler than that?
>>
>>I have one plane for the triangle, and 3 planes through the edges that
>>are perpendicular to the plane of the triangle.
>>
>>To test for bbox-triangle do :
>>
>>1. bbox must intersect the plane of the triangle.
>>2. bbox must be intersect or behind all 3 edge planes.
>>
>>That's it !  Four tests, all of them providing great quick-rejection.
>>This is simpler, I guess, because my BBox is not moving, and I guess
>>you're doing moving-BBox tests like Quake.
>
>That only works as a conservative test, but not as an exact test.
>
>If the box, straddling the triangle plane, is just outside one of the
>vertices of the triangle, then both criteria are met, but there's no
>actual intersection.
>
>
>Christer Ericson
>SCEA, Santa Monica
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

RE: [Algorithms] fast triangle-segment test *with precomputation*

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

Charles Bloom wrote:
>Ok, you have a good point, but isn't it even simpler than that?
>
>I have one plane for the triangle, and 3 planes through the edges that
>are perpendicular to the plane of the triangle.
>
>To test for bbox-triangle do :
>
>1. bbox must intersect the plane of the triangle.
>2. bbox must be intersect or behind all 3 edge planes.
>
>That's it !  Four tests, all of them providing great quick-rejection.
>This is simpler, I guess, because my BBox is not moving, and I guess
>you're doing moving-BBox tests like Quake.

That only works as a conservative test, but not as an exact test.

If the box, straddling the triangle plane, is just outside one of the
vertices of the triangle, then both criteria are met, but there's no
actual intersection.


Christer Ericson
SCEA, Santa Monica

RE: [Algorithms] fast triangle-segment test *with precomputation*

[Ignacio C. <i6...@ho...>]

Charles Bloom wrote:
> Ok, you have a good point, but isn't it even simpler than that?
>
> I have one plane for the triangle, and 3 planes through the edges that
> are perpendicular to the plane of the triangle.
>
> To test for bbox-triangle do :
>
> 1. bbox must intersect the plane of the triangle.
> 2. bbox must be intersect or behind all 3 edge planes.
>
> That's it !  Four tests, all of them providing great quick-rejection.
> This is simpler, I guess, because my BBox is not moving, and I guess
> you're doing moving-BBox tests like Quake.

yes, i'm calculating the intersection between triangles and moving bboxes, for that reason i need
the axis aligned planes so that the box slides over triangle vertexes. The good thing of this
algorithm is that you clip the movement segment, and for this reason you don't have to iterate and
test for intersection recursively. Also the axis aligned planes allow me to do fast rejection of the
segment, so at the end the only added cost is the antiplane, that is the last check, and usually
doesn't happen.


Ignacio Castano
ca...@cr...

Re: [Algorithms] 3d Lines Intersection

[Eric H. <er...@ac...>]

Albert_J wrote:

> Is there a good algo for finding a point of intersection between two *3D lines*?
> The lines is specified by their point (x,y,z) and their direction (dx,dy,dz)
>
> I've searched the web, but all of them seems to explain about 2D lines intersection only.

An answer (but not online, unfortunately): Goldman, Intersection of Two Lines in Three-Space,
Graphics Gems, p. 304.

I looked it up on my 3D objects intersection page: http://www.realtimerendering.com/int/. I
really need to find time to put down actual algorithms and code on this page (anyone want to
give me a grant? ;^> ).

Anyway, for two lines P1 _ V1*t and P2 + V2*s, where V1 and V2 are the direction vectors and
P1 & P2 some points on the lines, the answer is:

    s = Determinant{(P2-P1),V1,V1 X V2} / | V1 X V2 |^2

If the lines are parallel, the denominator is 0. If the lines are skew (don't intersect), s
and t represent the parameters of the points of closest approach - measure the distance
between these two points and you'll know how far apart they are.

Eric

Re: [Algorithms] Quadtree / Octtree neighbors

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

How do you mean "big gain in footprint"?
memory footprint?

Say you subdivide and octree down about 7 levels thats (64*64*64*SizeOfNode)
or (16384*SizeOfNode) of memory. Which I guess is not too bad, if the node
size is fairly small.

However if you subdivide an octree down 10 levels thats
(512*512*512*SizeOfNode) or (134217728*SizeOfNode), which is horrendous.

Ither way, this method is surely taking more memory.

Also I don't know if it will be any more cache friendly, because you are
still jumping about considerably in memory (Expecially reading "up and
down").

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

-----Original Message-----
From: Leigh McRae <lei...@ro...>
To: gda...@li...
<gda...@li...>
Date: 04 August 2000 8:47 PM
Subject: Re: [Algorithms] Quadtree / Octtree neighbors


>  If your Octree or Quad tree has static nodes then you can use an array of
>nodes.  I use a Static Octree and Quadtrees that have all the nodes
>subdivided equally.   This makes finding neighbours easy.  This could also
>be a big gain in footprint.  Might even be better for locality of memory
>(cache) but I am not sure.
>
>Leigh McRae
>
>----- Original Message -----
>From: Kelvin McDowell <ke...@re...>
>To: <gda...@li...>
>Sent: Friday, August 04, 2000 2:58 PM
>Subject: RE: [Algorithms] Quadtree / Octtree neighbors
>
>
>> Thanks, i'd forgotten about that thread even though I'd read it.
>>
>> I was thinking of implementing a method where you figured out the tree
>> transversal of of your six neighbors *as if* your octree was subdivided
>> equally.  Then transversing down the actual tree for each 'potential'
>> neighbor.  If you can't reach it then you've found a neighbor and add it
>to
>> your neighbor list.  If you reach it but it's not a leaf node then
>countinue
>> transvering down the relavanet directions only (ie: if you're searching
>for
>> the north bordering node then transverse down all the south (southeast,
>> southwest, etc.) nodes until you reach leave nodes.  Add the leaves.
>>
>> The method you describe below seems to be simular except I start
>transversal
>> at the root and go down where as you go up and then down.
>>
>> I noticed in the 'octree leaf neighbors' thread is was mentioned that you
>> have 6 neighbors.   Isn't this number is variable?
>>
>>
>> -----Original Message-----
>> From: Sam Kuhn [mailto:sa...@ip...]
>> Sent: Friday, August 04, 2000 5:40 AM
>> To: gda...@li...
>> Subject: Re: [Algorithms] Quadtree / Octtree neighbors
>>
>>
>> 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
>>
>>
>> _______________________________________________
>> 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] fast triangle-segment test *with precomputation*

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

Ok, you have a good point, but isn't it even simpler than that?

I have one plane for the triangle, and 3 planes through the edges that
are perpendicular to the plane of the triangle.

To test for bbox-triangle do :

1. bbox must intersect the plane of the triangle.
2. bbox must be intersect or behind all 3 edge planes.

That's it !  Four tests, all of them providing great quick-rejection.
This is simpler, I guess, because my BBox is not moving, and I guess
you're doing moving-BBox tests like Quake.

At 07:15 PM 8/4/2000 +0200, you wrote:
>
>Hi,
>for box-triangle test i use an algorithm similar to the one used to test
convex volumes via plane
>shifting. I simply take the plane of the triangle, the antiplane, the edge
bevels and the axis
>aligned bevels to build a 'fake' convex volume. Then shift the planes of
the volume depending on the
>distance of the plane to the center of the box and last clip the movement
segment against the
>volume. I have found this algorithm to be the fastest, however it
requieres a lot of precomputation,
>and is in many cases a waste of space.
>
>
>Ignacio Castano
>ca...@cr...
>
>
>Charles Bloom wrote:
>> Ok, so the Moller+Haines triangle-segment test is about
>> as good as it gets without any precomputation.  The
>> question is, how fast can you get with arbitrary
>> precomputation?  For example, I can precompute the
>> plane of the triangle, and the three perpendicular
>> planes which go through the edges.  Then the intersections
>> are all rays that hit the plane of the triangle and
>> whose intersection point is inside the three planes.
>> (BTW I don't care about computing the barycentric
>> coordinates).
>>
>> Oh, BTW I also don't have the ray normal, so the 'd' used
>> in Moller+Haines requires a sqrt() for me to find, so
>> that's quite bad.  I think I could probably get the sqrt
>> out of there and push the length-squared of the ray through
>> the math to help it a bit.
>>
>> The application here is when I have one triangle and I'm
>> about to do thousands of segment-triangle intersection tests
>> (actually, lots of bbox-triangle tests, but that requires
>> a segment-triangle test).
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] vipm instancing

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

At 10:57 AM 8/4/2000 +0100, you wrote:
>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...

Why do you say that?  You could have a chunk of ram, say 2 MB, which you
reserve for all your VIPM index lists.  Then you could write your own,
simple memory manager for the VIPM index lists.  You actually wouldn't need
linked lists, you could implement a "pushing" manager where you moved other
lists around to make room for you to just grow your list linearly.

I think this use of instanced VIPM, along with compressed VB's like I
describe on my web page, and the optimized prefixes that Tom has just
recently mentioned, can combine to be the golden ratio of the year,
as it were.  Using all that, you could really push 10 MTris/frame of
real useful geometry on X-Box, for example.

--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] Quadtree / Octtree neighbors

[Leigh M. <lei...@ro...>]

  If your Octree or Quad tree has static nodes then you can use an array of
nodes.  I use a Static Octree and Quadtrees that have all the nodes
subdivided equally.   This makes finding neighbours easy.  This could also
be a big gain in footprint.  Might even be better for locality of memory
(cache) but I am not sure.

Leigh McRae

----- Original Message -----
From: Kelvin McDowell <ke...@re...>
To: <gda...@li...>
Sent: Friday, August 04, 2000 2:58 PM
Subject: RE: [Algorithms] Quadtree / Octtree neighbors


> Thanks, i'd forgotten about that thread even though I'd read it.
>
> I was thinking of implementing a method where you figured out the tree
> transversal of of your six neighbors *as if* your octree was subdivided
> equally.  Then transversing down the actual tree for each 'potential'
> neighbor.  If you can't reach it then you've found a neighbor and add it
to
> your neighbor list.  If you reach it but it's not a leaf node then
countinue
> transvering down the relavanet directions only (ie: if you're searching
for
> the north bordering node then transverse down all the south (southeast,
> southwest, etc.) nodes until you reach leave nodes.  Add the leaves.
>
> The method you describe below seems to be simular except I start
transversal
> at the root and go down where as you go up and then down.
>
> I noticed in the 'octree leaf neighbors' thread is was mentioned that you
> have 6 neighbors.   Isn't this number is variable?
>
>
> -----Original Message-----
> From: Sam Kuhn [mailto:sa...@ip...]
> Sent: Friday, August 04, 2000 5:40 AM
> To: gda...@li...
> Subject: Re: [Algorithms] Quadtree / Octtree neighbors
>
>
> 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
>
>
> _______________________________________________
> 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] Quadtree / Octtree neighbors

[Kelvin M. <ke...@re...>]

Thanks, i'd forgotten about that thread even though I'd read it.

I was thinking of implementing a method where you figured out the tree
transversal of of your six neighbors *as if* your octree was subdivided
equally.  Then transversing down the actual tree for each 'potential'
neighbor.  If you can't reach it then you've found a neighbor and add it to
your neighbor list.  If you reach it but it's not a leaf node then countinue
transvering down the relavanet directions only (ie: if you're searching for
the north bordering node then transverse down all the south (southeast,
southwest, etc.) nodes until you reach leave nodes.  Add the leaves.

The method you describe below seems to be simular except I start transversal
at the root and go down where as you go up and then down.

I noticed in the 'octree leaf neighbors' thread is was mentioned that you
have 6 neighbors.   Isn't this number is variable?


-----Original Message-----
From: Sam Kuhn [mailto:sa...@ip...]
Sent: Friday, August 04, 2000 5:40 AM
To: gda...@li...
Subject: Re: [Algorithms] Quadtree / Octtree neighbors


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


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

RE: [Algorithms] fast triangle-segment test *with precomputation*

[Ignacio C. <i6...@ho...>]

Hi,
for box-triangle test i use an algorithm similar to the one used to test convex volumes via plane
shifting. I simply take the plane of the triangle, the antiplane, the edge bevels and the axis
aligned bevels to build a 'fake' convex volume. Then shift the planes of the volume depending on the
distance of the plane to the center of the box and last clip the movement segment against the
volume. I have found this algorithm to be the fastest, however it requieres a lot of precomputation,
and is in many cases a waste of space.


Ignacio Castano
ca...@cr...


Charles Bloom wrote:
> Ok, so the Moller+Haines triangle-segment test is about
> as good as it gets without any precomputation.  The
> question is, how fast can you get with arbitrary
> precomputation?  For example, I can precompute the
> plane of the triangle, and the three perpendicular
> planes which go through the edges.  Then the intersections
> are all rays that hit the plane of the triangle and
> whose intersection point is inside the three planes.
> (BTW I don't care about computing the barycentric
> coordinates).
>
> Oh, BTW I also don't have the ray normal, so the 'd' used
> in Moller+Haines requires a sqrt() for me to find, so
> that's quite bad.  I think I could probably get the sqrt
> out of there and push the length-squared of the ray through
> the math to help it a bit.
>
> The application here is when I have one triangle and I'm
> about to do thousands of segment-triangle intersection tests
> (actually, lots of bbox-triangle tests, but that requires
> a segment-triangle test).

RE: [Algorithms] vipm instancing

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

That's pretty much the one I suggested, but you lose the whole
continuousness, which is rather the point of VIPM - if you wanted discrete
levels, just precompute them and use static LoD, which is even faster. I was
suggesting you have some precompiled "base" triangle counts (e.g. a 300 tri
one), and then just the extra few replicated for each instance to work up to
the desired precise tri count (i.e. another 23 to get to 323 tris, which is
what the error metric says you should have).

It's a little more complex than that (because existing tris get modified by
adding new tris, so those can't actually be in the precompiled chunk), but
that's the essence.

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

> -----Original Message-----
> From: Thatcher Ulrich [mailto:tu...@tu...]
> Sent: 04 August 2000 15:04
> To: gda...@li...
> Subject: Re: [Algorithms] vipm instancing
> 
> 
> 
> On Fri, 4 Aug 2000, Paul Firth wrote:
> 
> > > 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.
> 
> How about: have a table of (say) ten vipm instances, which 
> are then shared
> by all visible instances of that model.  You'd have some kind 
> of voting or
> averaging scheme for deciding what the poly count should be 
> for each of
> the ten actual vipm instances.  This would hurt the 
> continousness of the
> LOD scheme when more than 10 instances are visible, but then you could
> make whole giant forests of vipm'd trees without killing memory.
> 
> -Thatcher
> tulrich.com
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] vipm instancing

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

On Fri, 4 Aug 2000, Paul Firth wrote:

> > 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.

How about: have a table of (say) ten vipm instances, which are then shared
by all visible instances of that model.  You'd have some kind of voting or
averaging scheme for deciding what the poly count should be for each of
the ten actual vipm instances.  This would hurt the continousness of the
LOD scheme when more than 10 instances are visible, but then you could
make whole giant forests of vipm'd trees without killing memory.

-Thatcher
tulrich.com

Re: [Algorithms] Bicubic normals for a bicubic world

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

Actually, an (n-1) order polynomial can describe the tangent vectors in one
direction, so the normals would be the cross product of two (n-1) order
polynomials, one being the tangents in u and one in v.

Approximating the normals of a bicubic with a single quadratic would lead to
problems, however. Consider the 2D case, where a bicubic curve can make an
'S' shape, but a quadratic can't.

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: "Tom Forsyth" <to...@mu...>
To: <gda...@li...>
Sent: Friday, August 04, 2000 5:35 AM
Subject: RE: [Algorithms] Bicubic normals for a bicubic world


> 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
> >
>
> _______________________________________________
> 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...>]

I've experimented with this, but as you've indicated, the closeness of the
approximation hinges on the two approximated (middle) points. If someone
could give me some help determining where those points should be, I'd
certainly appreciate it. ;-)

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: "Angel Popov" <ju...@bi...>
To: <gda...@li...>
Sent: Friday, August 04, 2000 4:19 AM
Subject: Re: [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.
>
> 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 )
>