as it made sense to have the functionality at that level. It turns out it’s about 50% faster than the max version with about half the memory foot print… for anyone interested here it is…
#ifdef _WIN32
#pragma once
#endif
//*****************************************************************************************
//File: adjedges.h
#ifndef __VEDGE_H__
#define __VEDGE_H__
#include <max.h>
#include <vector>
#include <array>
#ifndef UNDEFINED
#define UNDEFINED 0xffffffff
#endif
//*****************************************************************************************
// return the side (0,1 or 2) of an edge from v1 to v2 in face verts vi
inline int get_edge_index(DWORD* vi, DWORD v1, DWORD v2)
{
int v1i = *vi == v1 ? 0 : *(vi+1) == v1 ? 1 : 2; // get the index of v1 in vi
int v2i = *vi == v2 ? 0 : *(vi+1) == v2 ? 1 : 2; // get the index of v2 in vi
return (2 * (v1i + v2i - 1)) % 3; // compute the side of the edge
}
//********************************************************************************************
// our version of medge
class vedge
{
public:
DWORD f[2], v[2];
int get_edge_index(Face* faces, int side) const { return ::get_edge_index(faces[f[side]].v, v[0], v[1]); }
int get_edge(Face* faces, int side) const { return f[side] * 3 + get_edge_index(faces,side); }
BOOL either_set_in(Face* faces, BitArray& edges) const{ return edges[get_edge(faces, 0)] || edges[get_edge(faces, 1)]; }
BOOL both_set_in(Face* faces, BitArray& edges) const { return edges[get_edge(faces, 0)] && edges[get_edge(faces, 1)]; }
DWORD get_other_vert(DWORD vert) const { return v[0] == vert ? v[1] : v[0]; }
DWORD get_other_face(DWORD face) const { return f[0] == face ? f[1] : f[0]; }
BOOL is_open() const { return f[1] == UNDEFINED; }
BOOL get_side(DWORD face) { return face == f[1]; }
};
typedef vector<int> ivector;
typedef vector<ivector> ivecvec;
typedef std::vector<vedge> vedge_vec;
#ifdef __CACHE_ADJ_FACES__
typedef std::array<int,3> triplet;
typedef std::vector<triplet> trplt_vec;
#endif
//********************************************************************************************
// our version of adjedgelist
class adj_edges
{
static const int reserve = 8;
public:
vedge_vec edges; // unique edges in the mesh
ivecvec vedg; // vert to edge lookup table
#ifdef __CACHE_ADJ_FACES__
trplt_vec fedg; // face to edge lookuo table
#endif
adj_edges(Mesh& mesh, const int rsrv = reserve) : vedg(mesh.numVerts)
#ifdef __CACHE_ADJ_FACES__
,fedg(mesh.numFaces)
#endif
{
for(int v = 0; v < vedg.size(); ++v) vedg[v].reserve(rsrv);
edges.reserve(mesh.numFaces * 3);
build(mesh);
}
void rebuild(Mesh& mesh)
{
edges.clear();
vedg.clear();
build(mesh);
}
void build(Mesh& mesh)
{
int numfaces = mesh.numFaces;
Face* faces = mesh.faces;
for(int f = 0; f < numfaces; ++f, ++faces)
{
DWORD* fverts = faces->v;
#ifdef __CACHE_ADJ_FACES__
fedg[f][0] = add_edge(f, fverts[0], fverts[1]);
fedg[f][1] = add_edge(f, fverts[1], fverts[2]);
fedg[f][2] = add_edge(f, fverts[2], fverts[0]);
#else
add_edge(f, fverts[0], fverts[1]);
add_edge(f, fverts[1], fverts[2]);
add_edge(f, fverts[2], fverts[0]);
#endif
}
}
void add_edge_to_vert(const DWORD v, const DWORD e) { vedg[v].push_back(e); }
DWORD get_num_edges() const { return edges.size(); }
DWORD get_num_verts() const { return vedg.size(); }
// adds an edge to the edges array if it's not already there
DWORD add_edge(const DWORD f, const DWORD v1, const DWORD v2)
{
DWORD ei = find_edge(v1, v2);
if(ei != UNDEFINED) // edge already exists we just need to add our face to the other side
{
vedge& edge = edges[ei];
edge.f[1] = f;
}
else // otherwise we need a new edge
{
ei = edges.size();
edges.push_back(vedge());
vedge& edge = edges.back();
edge.f[0] = f;
edge.f[1] = UNDEFINED; // it's open for now....
edge.v[0] = v1;
edge.v[1] = v2;
add_edge_to_vert(v1, ei);
add_edge_to_vert(v2, ei);
}
return ei;
}
// as long as we are below 128 edges per vert we are going to win vs binarysearh/set here, so keep away from those 128 sided fans ! :)
DWORD find_edge(const DWORD v1, const DWORD v2)
{
ivector& v1edges = vedg[v1];
for(int i = 0; i < v1edges.size(); ++i)
{
int ei = v1edges[i];
vedge& edge = edges[ei];
if(edge.v[0] == v2 || edge.v[1] == v2) return ei;
}
return UNDEFINED;
}
#ifdef __CACHE_ADJ_FACES__
void get_adjacent_faces(const int face, DWORD adjfaces[3])
{
triplet& fedges = fedg[face];
adjfaces[0] = edges[fedges[0]].get_other_face(face);
adjfaces[1] = edges[fedges[1]].get_other_face(face);
adjfaces[2] = edges[fedges[2]].get_other_face(face);
}
#endif
void get_adjacent_faces(Face* faces, const int face, DWORD adjfaces[3])
{
DWORD* fverts = faces[face].v;
adjfaces[0] = edges[find_edge(fverts[0], fverts[1])].get_other_face(face);
adjfaces[1] = edges[find_edge(fverts[1], fverts[2])].get_other_face(face);
adjfaces[2] = edges[find_edge(fverts[2], fverts[0])].get_other_face(face);
}
};
#endif
i’ve left in the preprocessor option to cache the adjacent face option though the routine without caching the data is only 1-2% slower. It’s hard to see why they needed a adjfacelist object given that it’s relatively quick to get it from a adjedgelist. I’ve also left it as a “h only file” also appologies for the latest c++ purists i need it to work on pretty ancient versions of max we aren’t all of legal drinking age so to speal :D. I think the biggest frustration working in the sdk for max is having to rewrite every fucking core routine because it’s usually slow and inadequate
a case in point is Mesh::FindOpenEdges , they might have a custom routine that trolls every face for open edges or the they may create a local adjacent edge list and use that. But the fastest way by far is to give the caller the option of passing a pre-calculate adjacency list which can can also be used else where say ElementFromFace or PolyFromFace or getAdjacentFaces. or TurnEdge It such a pain in the arse. If it carries on like this I’d have written my own 3d package, btw adding FindOpenEdges to the above code is a relatively trivial task along with getreverseEdge and the like but i leave that to you