#229 Patch for edge list stuff

closed-accepted
5
2005-01-11
2004-12-10
Genva
No

There are two patch for edge list stuff:

EdgeList1.patch
    1\. New edge list build algorithm that can work with

any type mesh, include non-manifold mesh.
2. Optimize memory footprint of edge data, we only
save the data we exactly need.
3. Reorganize the code of shadow volume generate, now
the compiler can generate more efficiency code both
fast and small.

EdgeList2.patch
    Contain all thing as description in EdgeList1.patch,

plus sort and grouping the triangles in edge data by
vertex set, so we can access triangles belong to the
individual edge group more efficiency.

I make two patch, because sort and grouping the
triangles by vertex set should break a lot of thing
which you don't like it. So I given another patch you
can choose which one fit you need.

IMHO, The edge list build is so slowly because in debug
build, the edge data has log out to a file which is a
time-consuming operator. So, I think we can turn off
generate edge lists option by default for
OgreXMLConvert and OgreMeshUpgrader tools.

Ok, I say sorry for my bad English :)

Discussion

  • Genva

    Genva - 2004-12-10
     
  • Genva

    Genva - 2004-12-13

    Logged In: YES
    user_id=1142737

    I upload a new edge list patch (NewEdgeList.zip) which has
    following changes for CVS Hastur branch:
    1. Fixed bug for process triangle strips and triangle fans
    on edge list build
    2. Optimize triangle normal (It is a plane equation)
    calculate. Because we only use this plane equation for
    determinate the triangle light facing, we don't need to
    normalize it.
    3. A little optimize for shadow volume generate.
    4. Backfacing triangles never take into shadow volume generate.
    5. Build edge list in any case including non-manifold mesh,
    or triangles soup. As I explain in
    http://www.ogre3d.org/phpBB2/viewtopic.php?t=6999, we intent
    to build a valid shadow volume for the mesh, not the valid
    hull for the mesh.
    6. Dark cap calculate also OK, because the process is
    identical to that of computing the signed area of a polygon
    by constructing a fan, similar the explain in
    http://developer.nvidia.com/attach/6432, Figure 3. The hole
    inside the dark cap would be subtracted, the result is the
    original polygon with every part covered exactly once.

    Finally, I admit non-manifold meshes or polygon soup can not
    cast a 'proper' shadow, but I just leave this as is (The
    light can cast through the hole of the mesh, Is it?).

     
  • Genva

    Genva - 2004-12-13

    New edge list build and shadow volume generate patch

     
  • Steve Streeting

    Steve Streeting - 2004-12-29
    • assigned_to: nobody --> sinbad
     
  • Steve Streeting

    Steve Streeting - 2004-12-29

    Logged In: YES
    user_id=16123

    I've only tried this very quickly so far, and the first
    thing I get is when running the shadow demo in debug mode I
    get a stack corruption error at the end of
    EdgeListBuilder::buildTrianglesEdges, so it looks like
    there's a buffer overrun in there somewhere.

     
  • Genva

    Genva - 2004-12-30

    Logged In: YES
    user_id=1142737

    I've test the NewEdgeList patch for shadow demo a lot, with
    some tweak on mesh loading which free the exists edge list
    and rebuild them. It just working fine in debug and release
    mode. I only test this patch on Hastur branch, I think it's
    work on CVS HEAD also.

    Another problem: The dark cap generate may be incorrect in
    origin code and this patch. In the case of many edge groups,
    each group select a common vertex to build triangle fan for
    dark cap independently, if the common vertex for each fan
    isn't identical, the closed shadow volume should be
    incorrect. I think this can be fixed by add a vertex of the
    first edge group to other groups as the common vertex for
    dark cap generate.

     
  • Steve Streeting

    Steve Streeting - 2004-12-30

    Logged In: YES
    user_id=16123

    I'm not sure what compiler you tried this on, but VC7+ has
    additional runtime checks that other environments don't
    have, which help to catch leaks and overruns which would
    otherwise be missed until they randomly turned up at
    runtime. I applied your newst patch to the Hasur (0.15)
    branch and I immediately got "Stack corrupted" runtime
    errors in the edge list builder. In my experience these
    warnings are always right, and point to a problem you
    probably would have missed otherwise. So I'd guess your
    testing environment just hasn't spotted this error because
    by luck it didn't cause a crash (yet).

    Unfortunately I have so much to do, unless this patch works
    right out the box it's not going to be accepted for 1.0.0. I
    just don't have time to fix it up right now if it doesn't
    work flawlessly.

     
  • Genva

    Genva - 2004-12-31

    Logged In: YES
    user_id=1142737

    Ok, I using VC7.1 as my developement environment most time,
    compile with /RTC1 (both static frames and uninitialized
    variables check) and /GS (buffer security check) when debug
    build. I can not found any memory leak, stack corrupted when
    I run shadow demo from the OGRE samples with Hasur branch (I
    tweak Mesh::load() with a call to freeEdgeList(), and then
    set mAutoBuildEdgeLists to false after mesh load com, just
    for force edge list rebuild for testing my code). On my
    machine, there are some other modify of the Hasur branch,
    but I don't think they can affect the behavior of edge list
    builder.
    Any way, I will try to find the potential bug as I can.
    I upload a new patch (EdgeList_v2.zip) with optimize for
    vertex weld, now the edge list build more faster than the
    previous edition. The new patch consider as a replace with
    all previous patch. Please give a try with this patch.

     
  • Genva

    Genva - 2004-12-31

    edge list build v2

     
  • Genva

    Genva - 2005-01-10

    Logged In: YES
    user_id=1142737

    As I noticed in "Stencil shadow bugfix and optimize" patch, the
    'closed' mesh can be determinate by edge list builder, which
    just check the mEdgeMap is empty or not after edge list
    build. Only two lines code:

    At "OgreEdgeListBuilder.h", Add:
    bool mClosed;
    inside EdgeData class.

    At "OgreEdgeListBuilder.cpp" method EdgeListBuilder::build() Add
    mEdgeData->mClosed = mEdgeMap.empty();
    before:
    return mEdgeData;

    I am lazy to make a new patch, the work is very easy, so I
    leave it as is.

     
  • Genva

    Genva - 2005-01-11

    Logged In: YES
    user_id=1142737

    The new version (EdgeList_v3.zip) for fix a bug in VS.NET
    2002, "un-named union stack variable compile with /RTC1", As
    I talk about in
    http://www.ogre3d.org/phpBB2/viewtopic.php?t=7273

     
  • Genva

    Genva - 2005-01-11

    Bugfix version for VS.NET 2002 un-named union stack variable /RTC1 bug

     
  • Steve Streeting

    Steve Streeting - 2005-01-11

    Logged In: YES
    user_id=16123

    Thanks, this seems to work fine.

    The only problem with the mClosed is that this isn't stored
    in the binary format, and most meshes have the edge list
    prebuilt. It will require a change to the MeshSerializer to
    do this properly, and a new version of the mesh format. So I
    haven't done this yet.

     
  • Steve Streeting

    Steve Streeting - 2005-01-11
    • status: open --> closed-accepted
     

Log in to post a comment.