peltOverlapCmd.cpp

//-
// ==========================================================================
// Copyright 1995,2006,2008 Autodesk, Inc. All rights reserved.
//
// Use of this software is subject to the terms of the Autodesk
// license agreement provided at the time of installation or download,
// or which otherwise accompanies this software in either electronic
// or hard copy form.
// ==========================================================================
//+

//
// peltOverlapCmd.cpp
//
// This plugin checks and returns the overlapping faces in pairs for a given
// list of shading groups. The faces can be from the same mesh or different meshes, i.e.
//
// 1) Return the first overlapping faces associated to "shadingGroupName1"
// peltOverlap "shadingGroupName1";
//
// 2) Return the first 100 overlapping faces associated to "shadingGroupName1" 
//       and the first 100 overlapping faces associated to "shadingGroupName2".
// peltOverlap -exitAfterNthError 100 "shadingGroupName1" "shadingGroupName2";
//

#include <maya/MIOStream.h>
#include <maya/MFnPlugin.h>
#include <maya/MString.h>
#include <maya/MFloatArray.h>
#include <maya/MArgList.h>

#include <maya/MPxCommand.h>
#include <maya/MSyntax.h>
#include <maya/MArgDatabase.h>

#include <maya/MGlobal.h>
#include <maya/MDagPath.h>
#include <maya/MItSelectionList.h>
#include <maya/MSelectionList.h>
#include <maya/MItMeshPolygon.h>

#include <maya/MFnDependencyNode.h>
#include <maya/MFnSet.h>
#include <maya/MPlugArray.h>
#include <maya/MPlug.h>

#include <math.h>

#define kExitFlag       "-ea"
#define kExitFlagLong   "-exitAfterNthPairs"

//
// Command class declaration
//
class peltOverlap : public MPxCommand
{
public:
                         peltOverlap();
        virtual         ~peltOverlap(); 

        MStatus         doIt( const MArgList& args );

        static MSyntax  newSyntax();
        static void*    creator();

private:

        MStatus         parseArgs( const MArgList &args );
        void            createBoundingCircle(const MStringArray &flattenFaces, MFloatArray &center, MFloatArray &radius);
        bool            createRayGivenFace(const MString &face, MFloatArray &orig, MFloatArray &vec);
        float           area(const MFloatArray &orig);
        unsigned int    checkCrossingEdges(MFloatArray &face1Orig, 
                                           MFloatArray &face1Vec, 
                                           MFloatArray &face2Orig, 
                                           MFloatArray &face2Vec);
        void            numOverlapUVFaces(const MString &shadingGroup, MStringArray &flattenFaces);

        unsigned int    fNthPairs;
        MStringArray    fShadingGroups;
};

peltOverlap::peltOverlap()
        : fNthPairs (1)
{}

peltOverlap::~peltOverlap() {}

void* peltOverlap::creator()
{
        return new peltOverlap;
}

MSyntax peltOverlap::newSyntax()
{
         MSyntax syntax;
         syntax.addFlag(kExitFlag, kExitFlagLong, MSyntax::kUnsigned);
         syntax.setObjectType(MSyntax::kStringObjects);
         return syntax;
}

MStatus peltOverlap::parseArgs( const MArgList& args )
{
        MStatus         status = MS::kSuccess;
        MArgDatabase    argData(syntax(), args);

        if (argData.isFlagSet(kExitFlag)) {
            status = argData.getFlagArgument(kExitFlag, 0, fNthPairs);
            if (status != MS::kSuccess) {
                MGlobal::displayError("-ea/exitAfterNthPairs is missing an int argument");
                return status;
            }
        }

        status = argData.getObjects(fShadingGroups);
        if (status != MS::kSuccess || fShadingGroups.length() < 1) {
                MGlobal::displayError("Missing shading group(s) input");
                status = MS::kFailure;
        }

        return status;
}

MStatus peltOverlap::doIt( const MArgList& args )
//
// Description
//     Return the overlapping faces in pairs for given shading groups.
//
{
        MStatus status = parseArgs ( args );
        if ( !status ) return status;

        // Iterate over shading groups
        for (unsigned int i = 0; i < fShadingGroups.length(); i++ ) 
        {
            // Get a list of faces through mel because it's so much easier this way.
            // It should be fine because this is not performance critical.
            MStringArray faces, flattenFaces;
            MGlobal::executeCommand("sets -q " + fShadingGroups[i], faces, false, false);
            MGlobal::clearSelectionList();
            for(unsigned int j = 0; j < faces.length(); j++) 
            {
                MString nodeType = MGlobal::executeCommandStringResult("nodeType " + faces[j]);
                if (nodeType == "mesh") {
                    MGlobal::selectByName(faces[j]); // add to list
                }
            }
            MGlobal::executeCommand("ConvertSelectionToFaces");
            MGlobal::executeCommand("ls -sl -flatten", flattenFaces, false, false);

            numOverlapUVFaces(fShadingGroups[i], flattenFaces);
        }
        return MS::kSuccess;
}

void peltOverlap::createBoundingCircle(const MStringArray &flattenFaces, MFloatArray &center, MFloatArray &radius)
//
// Description
//     Represent a face by a center and radius, i.e.
//     center = {center1u, center1v, center2u, center2v, ... }
//     radius = {radius1, radius2,  ... }
//
{
        center.setLength(2 * flattenFaces.length());
        radius.setLength(flattenFaces.length());
        for(unsigned int i = 0; i < flattenFaces.length(); i++) {
                MSelectionList selList;
                selList.add(flattenFaces[i]);
                MDagPath dagPath;
                MObject  comp;
                selList.getDagPath(0, dagPath, comp);
                MItMeshPolygon iter(dagPath, comp);

                MFloatArray uArray, vArray;
                iter.getUVs(uArray, vArray);
                // Loop through all vertices to construct edges/rays
                float cu = 0.f;
                float cv = 0.f;
                unsigned int j;
                for(j = 0; j < uArray.length(); j++) {
                        cu += uArray[j];
                        cv += vArray[j];
                }
                cu = cu / uArray.length();
                cv = cv / vArray.length();
                float rsqr = 0.f;
                for(j = 0; j < uArray.length(); j++) {
                        float du = uArray[j] - cu;
                        float dv = vArray[j] - cv;
                        float dsqr = du*du + dv*dv;
                        rsqr = dsqr > rsqr ? dsqr : rsqr;
                }
                center[2*i]   = cu;
                center[2*i+1] = cv;
                radius[i]  = sqrt(rsqr);
        }
}

bool peltOverlap::createRayGivenFace(const MString &face, MFloatArray &orig, MFloatArray &vec)
//
// Description
//     Represent a face by a series of edges(rays), i.e.
//     orig = {orig1u, orig1v, orig2u, orig2v, ... }
//     vec  = {vec1u,  vec1v,  vec2u,  vec2v,  ... }
//
//     return false if no valid uv's. 
{
        MSelectionList selList;
        selList.add(face);
        MDagPath dagPath;
        MObject  comp;
        selList.getDagPath(0, dagPath, comp);
        MItMeshPolygon iter(dagPath, comp);

        MFloatArray uArray, vArray;
        iter.getUVs(uArray, vArray);

        if (uArray.length() == 0 || vArray.length() == 0) return false;

        orig.setLength(2 * uArray.length());
        vec.setLength( 2 * uArray.length());

        // Loop through all vertices to construct edges/rays
        float u = uArray[uArray.length() - 1];
        float v = vArray[vArray.length() - 1];
        for(unsigned int j = 0; j < uArray.length(); j++) {
                orig[2*j]   = uArray[j];
                orig[2*j+1] = vArray[j];
                vec[2*j]    = u - uArray[j];
                vec[2*j+1]  = v - vArray[j];
                u = uArray[j];
                v = vArray[j];
        }
        return true;
}

float peltOverlap::area(const MFloatArray &orig)
{
        float sum = 0.f;
        unsigned int num = orig.length() / 2;
        for (unsigned int i = 0; i < num; i++) {
                unsigned int idx  = 2 * i;
                unsigned int idy  = (i + 1 ) % num;
                idy = 2 * idy + 1;
                unsigned int idy2 = (i + num - 1) % num; 
                idy2 = 2 * idy2 + 1;
                sum += orig[idx] * (orig[idy] - orig[idy2]);
        }
        return fabs(sum) * 0.5f;
}

unsigned int peltOverlap::checkCrossingEdges(
MFloatArray &face1Orig, 
MFloatArray &face1Vec, 
MFloatArray &face2Orig, 
MFloatArray &face2Vec
)
// Check if there are crossing edges between two faces. Return true 
// if there are crossing edges and false otherwise. A face is represented
// by a series of edges(rays), i.e. 
// faceOrig[] = {orig1u, orig1v, orig2u, orig2v, ... }
// faceVec[]  = {vec1u,  vec1v,  vec2u,  vec2v,  ... }
{
        unsigned int face1Size = face1Orig.length();
        unsigned int face2Size = face2Orig.length();
        for (unsigned int i = 0; i < face1Size; i += 2) {
                float o1x = face1Orig[i];
                float o1y = face1Orig[i+1];
                float v1x = face1Vec[i];
                float v1y = face1Vec[i+1];
                float n1x =  v1y;
                float n1y = -v1x;
                for (unsigned int j = 0; j < face2Size; j += 2) {
                        // Given ray1(O1, V1) and ray2(O2, V2)
                        // Normal of ray1 is (V1.y, V1.x)
                        float o2x = face2Orig[j];
                        float o2y = face2Orig[j+1];
                        float v2x = face2Vec[j];
                        float v2y = face2Vec[j+1];
                        float n2x =  v2y;
                        float n2y = -v2x;

                        // Find t for ray2
                        // t = [(o1x-o2x)n1x + (o1y-o2y)n1y] / (v2x * n1x + v2y * n1y)
                        float denum = v2x * n1x + v2y * n1y;
                        // Edges are parallel if denum is close to 0.
                        if (fabs(denum) < 0.000001f) continue;
                        float t2 = ((o1x-o2x)* n1x + (o1y-o2y) * n1y) / denum;
                        if (t2 < 0.00001f || t2 > 0.99999f) continue;

                        // Find t for ray1
                        // t = [(o2x-o1x)n2x + (o2y-o1y)n2y] / (v1x * n2x + v1y * n2y)
                        denum = v1x * n2x + v1y * n2y;
                        // Edges are parallel if denum is close to 0.
                        if (fabs(denum) < 0.000001f) continue;
                        float t1 = ((o2x-o1x)* n2x + (o2y-o1y) * n2y) / denum;

                        // Edges intersect
                        if (t1 > 0.00001f && t1 < 0.99999f) return 1;
                }
        }
        return 0;
}

void peltOverlap::numOverlapUVFaces(const MString& shadingGroup, MStringArray& flattenFaces)
//
// Description
//     Return overlapping faces in pairs for given a shading group and its associated faces.
//
{
        MFloatArray  face1Orig, face1Vec, face2Orig, face2Vec, center, radius;
        // Loop through face i
        unsigned int numOverlap = 0;
        createBoundingCircle(flattenFaces, center, radius);
        for(unsigned int i = 0; i < flattenFaces.length() && numOverlap < fNthPairs; i++) {
                if(!createRayGivenFace(flattenFaces[i], face1Orig, face1Vec)) continue;
                const float cui  = center[2*i];
                const float cvi  = center[2*i+1];
                const float ri  = radius[i];
                // Exclude the degenerate face
                // if(area(face1Orig) < 0.000001) continue;
                // Loop through face j where j != i
                for(unsigned int j = i+1; j < flattenFaces.length() && numOverlap < fNthPairs; j++) {
                        const float &cuj = center[2*j];
                        const float &cvj = center[2*j+1];
                        const float &rj  = radius[j];
                        float du = cuj - cui;
                        float dv = cvj - cvi;
                        float dsqr = du*du + dv*dv;
                        // Quick rejection if bounding circles don't overlap
                        if (dsqr >= (ri+rj)*(ri+rj)) continue;

                        if(!createRayGivenFace(flattenFaces[j], face2Orig, face2Vec)) continue;
                        // Exclude the degenerate face
                        // if(area(face2Orig) < 0.000001) continue;
                        if (checkCrossingEdges(face1Orig, face1Vec, face2Orig, face2Vec)) {
                                numOverlap++;
                                appendToResult(flattenFaces[i]);
                                appendToResult(flattenFaces[j]);
                                continue;
                        }
                }
        }
}


//
// The following routines are used to register/unregister
// the command we are creating within Maya
//
MStatus initializePlugin( MObject obj )
{
        MStatus   status;
        MFnPlugin plugin( obj, PLUGIN_COMPANY, "3.0", "Any");

        status = plugin.registerCommand( "peltOverlap",
                                         peltOverlap::creator,
                                         peltOverlap::newSyntax);
        if (!status) {
                status.perror("registerCommand");
                return status;
        }

        return status;
}

MStatus uninitializePlugin( MObject obj)
{
        MStatus   status;
        MFnPlugin plugin( obj );

        status = plugin.deregisterCommand( "peltOverlap" );
        if (!status) {
                status.perror("deregisterCommand");
                return status;
        }

        return status;
}