About Store Forum Documentation Contact



Post Reply 
MeshBase subdivision algorithm
Author Message
Chris Offline
Member

Post: #1
MeshBase subdivision algorithm
Hi,

I need to subdivide my MeshBase for a special algorithm: I need to ensure that each vertex has neighbours (e.g. by an edge) which are all less than Flt SomeThresholdDistance;

This means doing some subdivision. I just wan't basic subdivision without creating smooth features. Pseudo-code of what I need to do:

Flt SomeThreshold = ..;

for all MeshBase.tri
while any (tri.edge.length > SomeThreshold)
subdivide tri;

Please could you help me achieve this in EE? I don't understand the MeshTris system enough to do this.

Thanks,
Chris
01-17-2012 09:46 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #2
RE: MeshBase subdivision algorithm
Hi,

could you be more specific about which part you don't understand?

Thanks
01-21-2012 12:51 PM
Find all posts by this user Quote this message in a reply
Chris Offline
Member

Post: #3
RE: MeshBase subdivision algorithm
Hi,

The main problem i'm facing is trying to remove the edges from the triangle. Here was my attempt (I added ...? where I was confused).

Code:
FREPA(base.tri) {
        C VecI   tri_ref  = base.tri.ind(i);
        
        C VecI2  edg_ref1 = VecI2(tri_ref.x, tri_ref.y); // edge: x to y
        C VecI2  edg_ref2 = VecI2(tri_ref.y, tri_ref.z); // edge: y to z
        C VecI2  edg_ref3 = VecI2(tri_ref.z, tri_ref.x); // edge: z to x

        C Edge   edg_1 = Edge( base.vtx.pos(edg_ref1.x),base.vtx.pos(edg_ref1.y) );
        C Edge   edg_2 = Edge( base.vtx.pos(edg_ref2.x),base.vtx.pos(edg_ref2.y) );
        C Edge   edg_3 = Edge( base.vtx.pos(edg_ref3.x),base.vtx.pos(edg_ref3.y) );

        if (edg_1.length() > threshold || edg_2.length() > threshold || edg_3.length() > threshold) {
            
            // compute the medial triangle as three new vertices inside the triangle
            C Vec new_vtx1 = edg_1.lerp(0.5f);
            C Vec new_vtx2 = edg_2.lerp(0.5f);
            C Vec new_vtx3 = edg_3.lerp(0.5f);

            base.addVtx(new_vtx1);
            C Int new_vtx_ref1 = base.vtxs()-1;

            base.addVtx(new_vtx2);
            C Int new_vtx_ref2 = base.vtxs()-1;

            base.addVtx(new_vtx3);
            C Int new_vtx_ref3 = base.vtxs()-1;
            
            // remove the three edges in the triangle
            base.removeEdge( ...? ); base.removeEdge( ...? ); base.removeEdge( ...? );

            // add 9 new edges (6 for the outside) and (3 for the inside medial triangle)
            base.addEdge(VecI2(tri_ref.x, new_vtx_ref1));
            base.addEdge(VecI2(new_vtx_ref1, tri_ref.y));
            base.addEdge(VecI2(tri_ref.y, new_vtx_ref2));
            base.addEdge(VecI2(new_vtx_ref2, tri_ref.z));
            base.addEdge(VecI2(tri_ref.z, new_vtx_ref3));
            base.addEdge(VecI2(new_vtx_ref3, tri_ref.x));

            base.addEdge(VecI2(new_vtx_ref1, new_vtx_ref2));
            base.addEdge(VecI2(new_vtx_ref2, new_vtx_ref3));
            base.addEdge(VecI2(new_vtx_ref3, new_vtx_ref1));

            // add 4 new triangles (3 corner triangles) and (1 inside medial triangle)
            base.addTri(VecI(tri_ref.x, new_vtx_ref1, new_vtx_ref3)); // bottom left
            base.addTri(VecI(new_vtx_ref1, tri_ref.y, new_vtx_ref2)); // top
            base.addTri(VecI(new_vtx_ref3, new_vtx_ref2, tri_ref.z)); // bottom right

            base.addTri(VecI(new_vtx_ref1, new_vtx_ref2, new_vtx_ref3)); // medial triangle
        }
    }

Also, is there any faster/more optimized way of doing this in EE?

Thanks
01-21-2012 02:03 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #4
RE: MeshBase subdivision algorithm
if you have a 3D model, then you don't need to setup edges (they are used only for some 2D meshes, or some custom processing)

each 'addTri' reallocates tri array container and puts new value - slow for many calls

more efficient is to use:
Memc<SomeVtx> vtxs;
Memc<VecI> tris;
fill those arrays (placing new elements into Memc is faster than addTri)
and then create the new MeshBase from both containers
MeshBase::create(Int vtxs, Int edges, Int tris, Int quads, UInt flag=0 ) and setup all values
01-24-2012 11:53 AM
Find all posts by this user Quote this message in a reply
Post Reply