Thread: [Algorithms] Q3 and Collision

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Do you think Q3 is still using bsp plane shifting for collision detection?

P.S: one BSP and runtime plane shifting.
______________________________
Cem UZUNLAR tu...@an...

Cem UZUNLAR wrote:
> Do you think Q3 is still using bsp plane shifting for collision detection?
>
> P.S: one BSP and runtime plane shifting.

Q3 still uses brushes and plane shifting for collision detection, curves are aproximated with a set
of convex volumes. There's a cvar, that displays them for debuging purpouses.

Ignacio Castano
cas...@ya...

Hi all,

Thanks for taking time to read and answer my questions.  I am playing
around with understanding Hoppe's and Bloom's papers on Progressive Meshes
and I have a few questions.

1. For VIPM, is it worth it to write your own implementation, or should I
just use the interfaces that come with D3D?  I imagine this is not a
simple question to answer but probably depends on the situations, so as an
aside which problems do the D3D implementations work best on and which
should be specialized?

2. I am trying to play around with terrain generators (seems like a lot of
newbies often begin here).  I think I like the idea of VIPM or VDPM when
it comes to terrains b/c you are not restricted to height fields and can
have overhangs and caves and the likes.   Which makes me lean away from
ROAM.  But what am I going to give up going V*PM over ROAM?  

3. Also, what is the general consensus on breaking up the terrain into
multiple VIPMs and rendering each at different LoD compared to trying some
VDPM method? (I haven't seen too much on VDPM if anyone has any references
I would appreciate that, the archives don't have too much).  I have seen
tons on the chunked VIPM and I think that it might be worth it, but I'd
like to get your opinions.

4. I guess this question depends on the answer to (1), if I should write
my own VIPM.  I read some emails about improvements to VIPM using
skipstrips or sliding windows.  Has there been anymore talk about these?
I have been thinking about the sliding window and it seems for some things
(trees, rocks, animals) which have many instances it should be a big win.
What have others seen?  

Again, thanks in advance for your help.

Chris

Chris and All,

A couple of (hopefully non-religious :) points come to mind
(hint, I tend to be on the ROAM side of the argument...):

1) Much of the discussion on VIPM isn't really concerned
with edge-collapse progressions so much as efficient ways
to use vertex arrays, index lists and AGP memory for *any*
flavor of progression.  The vertex-array ideas work well
with RTIN/Triangle Bintree hierarchies such as the
one in the ROAM paper.

2) The triangle bintree hierachy has a very easy way to walk
the tree to get one generalized strip, which is ideal for
maximizing vertex-cache coherence on a GPU.  This doesn't mean
that this order of vertices/triangles will agree with the
progression you had in mind for the vertex arrays.
It seems you are doomed to some kind of tradeoff here
(same story I believe with edge-collapse progressions and
strips).  Tom, Charles: have you come up with any clever
ways to side-step this tradeoff?

3) The bintree doesn't need all the "structure" data
of the edge-collapse or other more free-form hierarchies,
meaning you can compute a lot of things quickly as needed
or compress well when reading/paging geometry in.

4) Nesting of bounds is a lot tighter, since coarse
partitions exactly align with fine partitions.  This is
especially slick for frustum culling using per-frustum-plane
flags, but should also work great for collision detection.

5) The fastest "split only" optmizer I've written, measuring
just the triangle creation and not the sending to the graphics
hardware, cranks out >10meg tris per second without and use of
coherence on a 450MHz Pentium 3, without any blocking (that is,
when optimizing individual triangles).  If you replace each
triangle by a block of "ROAM read-only progressive index+vertex
arrays" then you get 100-1000x speedups with a few percent
degradation in quality over the fine-grained optimizer.  At this
point of course you are sending triangles in the "Bloom/Forsyth-
recommended optimal form," i.e. using AGP memory for geometry
where the CPU doesn't touch that information at all from frame to
frame (except to swap in/out a few percent of the blocks each
frame).

6) As Lucas noted, we are happily using ROAM-like hierarchies
on arbitrary manifolds.  I've got some examples generated
using a subdivision-surface tool, with some notes on the
format (plus a *really* rough draft of some working notes
for a future ROAM help page) at
    http://www.cognigraph.com/ROAM_homepage/
The subdivision-surface code is part of the LibGen distribution
(IRIX/Linux) of libraries and tools:
    http://www.cognigraph.com/LibGen
See LibGen/Surftools/Mesh/.  A short paper showing some
industrial-strength shrink-wrapping of complex surfaces
into subdivision-surface form is at:
    http://muldoon.cipic.ucdavis.edu/~hvm00/program.html
The .pdf file is at:
    http://muldoon.cipic.ucdavis.edu/~hvm00/abstracts/duchaineau.pdf

7) Note that the VIPM discussions are centered on the
low-level details of what happens within a block, not on good
general algorithms for how to make optimal decisions about
the collection of output blocks.  In a world where you have
a collection of objects in space, that is fine.  But in a more
general setting the issues of blocking up large objects,
dealing with seams, maximizing coherence, and performing the
global optimization in a time budget each frame are hard
problems.  The ROAM dual-queue, frustum culling, priority deferal
and stop-when-time-is-up ideas play well here.

8) On dynamic geometry: a good mix of methods for
the "hard" cases is the ROAM dual-queues for the global
optimization, and read-only index and vertex arrays within a
block, with the option to "unblock" certain regions where you
need to add a little detail so objects don't float or
interpenetrate a terrain, for example, or where some local
terrain dynamics happen.  Typically you would want to
be "unblocked" like this only so long as things are changing
a lot, and the "recompile" blocks as soon as things are coherent
enough that this pays off.  In any case the update to the
hierarchy for local geometry changes is about as simple and
fast as you can get for a fine-to-coarse approach.  The fastest
possible dynamic "edits" are the so-call *output-sensitive*
algorithms, which work coarse-to-fine just as needed.  A treatment
of this in the context of wavelet transforms/hierarchical
splines and sculpting operators is at
    http://graphics.cs.ucdavis.edu/~duchaine/dyadic.html

9) Textures can be easily laid out on a surface once it has been
shunk-wrapped for a triangle-bintree hierarchy.  I'm writing up
a paper now on how texture paging/fine-grained LOD optimization
works out very nicely for this.

10) This all ties in to some fast new wavelet compression schemes
for arbitrary surfaces:
    http://graphics.cs.ucdavis.edu/pdf/bertram-vis00-final.pdf

Cheers,

--Mark D.

Christopher Husband wrote:
> 
> Hi all,
> 
> Thanks for taking time to read and answer my questions.  I am playing
> around with understanding Hoppe's and Bloom's papers on Progressive Meshes
> and I have a few questions.
> 
> 1. For VIPM, is it worth it to write your own implementation, or should I
> just use the interfaces that come with D3D?  I imagine this is not a
> simple question to answer but probably depends on the situations, so as an
> aside which problems do the D3D implementations work best on and which
> should be specialized?
> 
> 2. I am trying to play around with terrain generators (seems like a lot of
> newbies often begin here).  I think I like the idea of VIPM or VDPM when
> it comes to terrains b/c you are not restricted to height fields and can
> have overhangs and caves and the likes.   Which makes me lean away from
> ROAM.  But what am I going to give up going V*PM over ROAM?
> 
> 3. Also, what is the general consensus on breaking up the terrain into
> multiple VIPMs and rendering each at different LoD compared to trying some
> VDPM method? (I haven't seen too much on VDPM if anyone has any references
> I would appreciate that, the archives don't have too much).  I have seen
> tons on the chunked VIPM and I think that it might be worth it, but I'd
> like to get your opinions.
> 
> 4. I guess this question depends on the answer to (1), if I should write
> my own VIPM.  I read some emails about improvements to VIPM using
> skipstrips or sliding windows.  Has there been anymore talk about these?
> I have been thinking about the sliding window and it seems for some things
> (trees, rocks, animals) which have many instances it should be a big win.
> What have others seen?
> 
> Again, thanks in advance for your help.
> 
> Chris
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Mark,
> 2) The triangle bintree hierachy has a very easy way to walk
> the tree to get one generalized strip, which is ideal for
> maximizing vertex-cache coherence on a GPU.
I am highly interested in how to create this one strip, specifically how to
create this one generalized strip incrementally ?

Thanks in advance
bye joe

Maybe I will have time someday to write a paper on the wonderful
properties of bintrees, but I dont think that day will be soon.
So in the mean time here are a couple useful features that help get an
efficient Bintree based CLOD scheme:

Implicit iteration:

To answer Joe's question:
Iterating over all the triangles in a crack free bintree is easy if you
index
your tree correctly, assuming you use implicit bintrees and the array index
is your triangle index.   Each level N of the bintree starts at index 2^N.

Eg. lets start from the top you have a signle triangle with index
 1
if it gets split you have
(2 3)
if 2 gets split you have
((4 5) 3)
If 5 gets split you have
((4 (10 11)) 3)
Note that this is impossible since you can only have one of
difference between neighbouring triangles.  So to avoid a crack
you will have split 3 as well to produce:
((4 (10 11)) (6 7))
To render this bintree you simply descend from 1 until you
find the 1st 'active' triangle, then increment the index until
the neighbour is not 'active' in which case you need to either
descend one level (index *=2) or ascend one level
(index /= 2) and continue until you reach the other end of the bintree.
Draw it on paper (as I did) and you will see it works, it took me a while to
come
up with. I didn't know others had already discovered this neat property
of bintrees, sadly it is not possible to render as a tri strip (unless you
include
degenerate triangles).  I used a little MRU cache to track the last 10
vertices
and got about as many triangles as vertices which I found acceptable.

High Level LOD or Free detail:

There is another useful property of bintrees.  If you have a mesh M which
is a crack free bintree, you can split every triangle in M and produce M'
which
will have twice as many triangles, but is not crack free.  However if you
split
M' to get M", you will have 4 times the original number of triangles and M"
is also guaranteed to be crack free.
This means you can do you LOD at the level of M and over render by a factor
4 or 16 or 64 etc.  This is what DDG does, when I render 16000 triangles I
only
perform LOD on 1000 of them.  I am trading off extra LOD calculations on the
CPU for extra triangles on the GPU.   A trade that is well worth it.

Alex Pfaffe

----- Original Message -----
From: "Joe Ante" <Jo...@Ti...>
To: <gda...@li...>; "Mark Duchaineau"
<duc...@ll...>
Sent: Tuesday, March 06, 2001 6:11 AM
Subject: Re: [Algorithms] VIPM, VDPM, ROAM questions

> Mark,
> > 2) The triangle bintree hierachy has a very easy way to walk
> > the tree to get one generalized strip, which is ideal for
> > maximizing vertex-cache coherence on a GPU.
> I am highly interested in how to create this one strip, specifically how
to
> create this one generalized strip incrementally ?
>
> Thanks in advance
> bye joe
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

my 2c is that VIPM doesn't really allow for mesh modification 
(because of fixed collapse order), which is definetly doable in 
ROAM (local edit & error update).

> 2. I am trying to play around with terrain generators (seems like a
> lot of newbies often begin here).  I think I like the idea of VIPM or
> VDPM when it comes to terrains b/c you are not restricted to height
> fields and can have overhangs and caves and the likes.   Which makes
> me lean away from ROAM.  But what am I going to give up going V*PM
> over ROAM?  

fyi, as noted in the original ROAM paper, in evaluation criteria #12, 
"Although our motivating application and implimentation focuses on 
terrain (in the form of a height field), ROAM's mesh structure applies 
to manifolds of arbitrary genus with boundary."

ROAM can be, and is (at LLNL for example), used for arbitrary 
multires geometry CLOD.  it is not a trivial extension, but it makes 
ROAM extremely flexible.

-Lucas

There's an implementation + description of the "strips" VIPM on
my web site, at http://www.cbloom.com/3d/

At 11:50 PM 3/3/2001 -0600, you wrote:
>4. I guess this question depends on the answer to (1), if I should write
>my own VIPM.  I read some emails about improvements to VIPM using
>skipstrips or sliding windows.  Has there been anymore talk about these?
>I have been thinking about the sliding window and it seems for some things
>(trees, rocks, animals) which have many instances it should be a big win.
>What have others seen?

----------------------------------------------------
Charles Bloom    cb...@cb...    www.cbloom.com

Can anyone recommend books or online tutorials that teach how to do shadows
for those of use that just know how to display a polygon?  In otherwords,
shadows for dummies?

Thanks..

Are the bevel planes included with the brushes?

______________________________
Cem UZUNLAR tu...@an...

>-----Original Message-----
>From: gda...@li...
>[mailto:gda...@li...]On Behalf Of
>Ignacio Castano
>Sent: Sunday, March 04, 2001 2:20 AM
>To: gda...@li...
>Subject: RE: [Algorithms] Q3 and Collision
>
>
>Cem UZUNLAR wrote:
>> Do you think Q3 is still using bsp plane shifting for collision 
>detection?
>>
>> P.S: one BSP and runtime plane shifting.
>
>Q3 still uses brushes and plane shifting for collision detection, 
>curves are aproximated with a set
>of convex volumes. There's a cvar, that displays them for debuging 
>purpouses.
>
>
>Ignacio Castano
>cas...@ya...
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Cem UZUNLAR wrote:
> Are the bevel planes included with the brushes?

yes, they are.

Ignacio Castano
cas...@ya...

In q3 brushes,

which is true solidness test for walk-able areas?
CONTENTS_SOLID
or
SURF_NONSOLID

Thanks.
______________________________
Cem UZUNLAR tu...@an...

>-----Original Message-----
>From: gda...@li...
>[mailto:gda...@li...]On Behalf Of
>Ignacio Castano
>Sent: Monday, March 05, 2001 12:50 AM
>To: gda...@li...
>Subject: RE: [Algorithms] Q3 and Collision
>
>
>Cem UZUNLAR wrote:
>> Are the bevel planes included with the brushes?
>
>yes, they are.
>
>
>Ignacio Castano
>cas...@ya...
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Cem UZUNLAR wrote:
> which is true solidness test for walk-able areas?
> CONTENTS_SOLID
> or
> SURF_NONSOLID

I just do this:

if(!(r_shaderrefs[brush->shaderref].content_flags & mask)) return false;

where mask is usually:
#define MASK_PLAYERSOLID (CONTENTS_SOLID|CONTENTS_PLAYERCLIP|CONTENTS_BODY)

note that for monster, misiles, etc. it may be different. The appropiate definitions are in the
public quake3 source code.

i recommend you writing a trace function, that returns a trace_t struct that would be something like
this:

typedef struct {
    bool  allsolid;
    bool  startsolid;
    float  fraction;
    Vec3  endpos;
    Plane  plane;
    int   surfaceFlags;
    int   contents;
} trace_t;

there you return the the fraction of the movement, the end position, the plane that you have colided
with, and the surface and of the content flags.

The surface flags are used for footsteps, and some physic effects.

Ignacio Castano
cas...@ya...