I wrote my own adjacent edge list


#1

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 :smiley: 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, :confused: btw adding FindOpenEdges to the above code is a relatively trivial task along with getreverseEdge and the like but i leave that to you :slight_smile: