-#if 1
-// fast way, using an edge hash
-#define TRIANGLEEDGEHASH 8192
-void Mod_BuildTriangleNeighbors(int *neighbors, const int *elements, int numtriangles)
-{
- int i, j, p, e1, e2, *n, hashindex, count, match;
- const int *e;
- typedef struct edgehashentry_s
- {
- struct edgehashentry_s *next;
- int triangle;
- int element[2];
- }
- edgehashentry_t;
- static edgehashentry_t **edgehash;
- edgehashentry_t *edgehashentries, *hash;
- if (!numtriangles)
- return;
- edgehash = (edgehashentry_t **)Mem_Alloc(tempmempool, TRIANGLEEDGEHASH * sizeof(*edgehash));
- // if there are too many triangles for the stack array, allocate larger buffer
- edgehashentries = (edgehashentry_t *)Mem_Alloc(tempmempool, numtriangles * 3 * sizeof(edgehashentry_t));
- // find neighboring triangles
- for (i = 0, e = elements, n = neighbors;i < numtriangles;i++, e += 3, n += 3)
- {
- for (j = 0, p = 2;j < 3;p = j, j++)
- {
- e1 = e[p];
- e2 = e[j];
- // this hash index works for both forward and backward edges
- hashindex = (unsigned int)(e1 + e2) % TRIANGLEEDGEHASH;
- hash = edgehashentries + i * 3 + j;
- hash->next = edgehash[hashindex];
- edgehash[hashindex] = hash;
- hash->triangle = i;
- hash->element[0] = e1;
- hash->element[1] = e2;
- }
- }
- for (i = 0, e = elements, n = neighbors;i < numtriangles;i++, e += 3, n += 3)
- {
- for (j = 0, p = 2;j < 3;p = j, j++)
- {
- e1 = e[p];
- e2 = e[j];
- // this hash index works for both forward and backward edges
- hashindex = (unsigned int)(e1 + e2) % TRIANGLEEDGEHASH;
- count = 0;
- match = -1;
- for (hash = edgehash[hashindex];hash;hash = hash->next)
- {
- if (hash->element[0] == e2 && hash->element[1] == e1)
- {
- if (hash->triangle != i)
- match = hash->triangle;
- count++;
- }
- else if ((hash->element[0] == e1 && hash->element[1] == e2))
- count++;
- }
- // detect edges shared by three triangles and make them seams
- if (count > 2)
- match = -1;
- n[p] = match;
- }
-
- // also send a keepalive here (this can take a while too!)
- CL_KeepaliveMessage(false);
- }
- // free the allocated buffer
- Mem_Free(edgehashentries);
- Mem_Free(edgehash);
-}
-#else
-// very slow but simple way
-static int Mod_FindTriangleWithEdge(const int *elements, int numtriangles, int start, int end, int ignore)
-{
- int i, match, count;
- count = 0;
- match = -1;
- for (i = 0;i < numtriangles;i++, elements += 3)
- {
- if ((elements[0] == start && elements[1] == end)
- || (elements[1] == start && elements[2] == end)
- || (elements[2] == start && elements[0] == end))
- {
- if (i != ignore)
- match = i;
- count++;
- }
- else if ((elements[1] == start && elements[0] == end)
- || (elements[2] == start && elements[1] == end)
- || (elements[0] == start && elements[2] == end))
- count++;
- }
- // detect edges shared by three triangles and make them seams
- if (count > 2)
- match = -1;
- return match;
-}
-
-void Mod_BuildTriangleNeighbors(int *neighbors, const int *elements, int numtriangles)
-{
- int i, *n;
- const int *e;
- for (i = 0, e = elements, n = neighbors;i < numtriangles;i++, e += 3, n += 3)
- {
- n[0] = Mod_FindTriangleWithEdge(elements, numtriangles, e[1], e[0], i);
- n[1] = Mod_FindTriangleWithEdge(elements, numtriangles, e[2], e[1], i);
- n[2] = Mod_FindTriangleWithEdge(elements, numtriangles, e[0], e[2], i);
- }
-}
-#endif
-