MeshBase subdivision algorithm

Chris · 01-17-2012 09:46 PM

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

**Esenthel** · 01-21-2012 12:51 PM

Hi,

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

Thanks

Chris · 01-21-2012 02:03 PM

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

**Esenthel** · 01-24-2012 11:53 AM

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

MeshBase subdivision algorithm
Author	Message