24 #elif defined(_MSC_VER)
44 #if defined(DEBUG_CONVEX_HULL) || defined(SHOW_ITERATIONS)
66 return (
x == 0) && (
y == 0) && (
z == 0);
71 return x *
b.x +
y *
b.y +
z *
b.z;
93 return (
x ==
b.x) && (
y ==
b.y) && (
z ==
b.z);
98 return (
x !=
b.x) || (
y !=
b.y) || (
z !=
b.z);
103 return (
x == 0) && (
y == 0) && (
z == 0);
118 return x *
b.x +
y *
b.y +
z *
b.z;
123 return x *
b.x +
y *
b.y +
z *
b.z;
170 #ifdef USE_X86_64_ASM
173 "addq %[bl], %[rl]\n\t"
174 "adcq %[bh], %[rh]\n\t"
176 :
"0"(
low),
"1"(
high), [bl]
"g"(
b.low), [bh]
"g"(
b.high)
187 #ifdef USE_X86_64_ASM
190 "subq %[bl], %[rl]\n\t"
191 "sbbq %[bh], %[rh]\n\t"
193 :
"0"(
low),
"1"(
high), [bl]
"g"(
b.low), [bh]
"g"(
b.high)
203 #ifdef USE_X86_64_ASM
205 "addq %[bl], %[rl]\n\t"
206 "adcq %[bh], %[rh]\n\t"
207 : [rl]
"=r"(
low), [rh]
"=r"(
high)
208 :
"0"(
low),
"1"(
high), [bl]
"g"(
b.low), [bh]
"g"(
b.high)
286 else if (numerator < 0)
298 m_denominator = (
uint64_t)denominator;
300 else if (denominator < 0)
303 m_denominator = (
uint64_t)-denominator;
313 return (sign < 0) && (m_denominator == 0);
318 return (sign == 0) && (m_denominator == 0);
343 this->numerator = value;
348 this->numerator = -value;
364 this->numerator = numerator;
368 this->numerator = -numerator;
370 int dsign = denominator.
getSign();
373 this->denominator = denominator;
378 this->denominator = -denominator;
444 #ifdef DEBUG_CONVEX_HULL
489 if (
src->lastNearbyFace)
493 for (
Face* f =
src->firstNearbyFace; f; f = f->nextWithSameNearbyVertex)
496 f->nearbyVertex =
this;
529 #ifdef DEBUG_CONVEX_HULL
558 if (
a->lastNearbyFace)
560 a->lastNearbyFace->nextWithSameNearbyVertex =
this;
564 a->firstNearbyFace =
this;
566 a->lastNearbyFace =
this;
575 template <
typename UWord,
typename UHWord>
594 static void shlHalf(
uint64_t& value)
614 static void shlHalf(
Int128& value)
621 static void mul(UWord
a, UWord
b, UWord& resLow, UWord& resHigh)
623 UWord p00 = mul(low(
a), low(
b));
624 UWord p01 = mul(low(
a), high(
b));
625 UWord p10 = mul(high(
a), low(
b));
626 UWord p11 = mul(high(
a), high(
b));
627 UWord p0110 = UWord(low(p01)) + UWord(low(p10));
643 class IntermediateHull
665 template <
typename T>
688 for (
int i = 0; i <
size; i++, o++)
690 o->next = (i + 1 <
size) ? o + 1 :
NULL;
696 template <
typename T>
701 PoolArray<T>* nextArray;
727 void setArraySize(
int arraySize)
729 this->arraySize = arraySize;
737 PoolArray<T>* p = nextArray;
744 p =
new (
btAlignedAlloc(
sizeof(PoolArray<T>), 16)) PoolArray<T>(arraySize);
750 freeObjects = o->next;
754 void freeObject(
T*
object)
757 object->next = freeObjects;
758 freeObjects = object;
764 Pool<Vertex> vertexPool;
773 int maxUsedEdgePairs;
775 static Orientation getOrientation(
const Edge*
prev,
const Edge*
next,
const Point32& s,
const Point32&
t);
776 Edge* findMaxAngle(
bool ccw,
const Vertex* start,
const Point32& s,
const Point64& rxs,
const Point64& sxrxs, Rational64& minCot);
781 void removeEdgePair(
Edge* edge)
790 n->prev =
edge->prev;
791 edge->prev->next = n;
792 r->target->edges = n;
796 r->target->edges =
NULL;
805 edge->target->edges = n;
812 edgePool.freeObject(edge);
813 edgePool.freeObject(
r);
817 void computeInternal(
int start,
int end, IntermediateHull&
result);
819 bool mergeProjection(IntermediateHull& h0, IntermediateHull& h1,
Vertex*& c0,
Vertex*& c1);
821 void merge(IntermediateHull& h0, IntermediateHull& h1);
842 Int128 a = negative ? -*this : *
this;
845 negative = !negative;
857 #ifdef USE_X86_64_ASM
865 bool negative =
a < 0;
872 negative = !negative;
884 #ifdef USE_X86_64_ASM
901 return sign -
b.sign;
910 #ifdef USE_X86_64_ASM
917 "movq %%rax, %[tmp]\n\t"
918 "movq %%rdx, %%rbx\n\t"
919 "movq %[tn], %%rax\n\t"
921 "subq %[tmp], %%rax\n\t"
922 "sbbq %%rbx, %%rdx\n\t"
924 "orq %%rdx, %%rax\n\t"
927 "shll $16, %%ebx\n\t"
928 :
"=&b"(
result), [tmp]
"=&r"(tmp),
"=a"(dummy)
929 :
"a"(m_denominator), [bn]
"g"(
b.m_numerator), [tn]
"g"(m_numerator), [bd]
"g"(
b.m_denominator)
946 return sign -
b.sign;
957 Int128 nbdLow, nbdHigh, dbnLow, dbnHigh;
961 int cmp = nbdHigh.
ucmp(dbnHigh);
996 return numerator.ucmp(denominator *
b) *
sign;
1002 Edge*
e = edgePool.newObject();
1003 Edge*
r = edgePool.newObject();
1006 e->copy = mergeStamp;
1007 r->copy = mergeStamp;
1013 if (usedEdgePairs > maxUsedEdgePairs)
1015 maxUsedEdgePairs = usedEdgePairs;
1020 bool btConvexHullInternal::mergeProjection(IntermediateHull& h0, IntermediateHull& h1,
Vertex*& c0,
Vertex*& c1)
1024 if ((v0->point.x ==
v1->point.x) && (v0->point.y ==
v1->point.y))
1034 v1 =
v1->edges->target;
1045 if ((v1n->point.x < v1p->point.x) || ((v1n->point.x == v1p->point.x) && (v1n->point.y < v1p->point.y)))
1056 if ((v1n->point.x > v1p->point.x) || ((v1n->point.x == v1p->point.x) && (v1n->point.y > v1p->point.y)))
1073 for (
int side = 0; side <= 1; side++)
1082 Vertex* w0 = side ? v0->next : v0->prev;
1086 int32_t dy0 = w0->point.y - v0->point.y;
1087 if ((dy0 <= 0) && ((dx0 == 0) || ((dx0 < 0) && (dy0 * dx <= dy * dx0))))
1090 dx = (
v1->point.x - v0->point.x) *
sign;
1099 int32_t dy1 = w1->point.y -
v1->point.y;
1101 if ((dxn > 0) && (dy1 < 0) && ((dx1 == 0) || ((dx1 < 0) && (dy1 * dx < dy * dx1))))
1122 int32_t dy1 = w1->point.y -
v1->point.y;
1123 if ((dy1 >= 0) && ((dx1 == 0) || ((dx1 < 0) && (dy1 * dx <= dy * dx1))))
1126 dx = (
v1->point.x - v0->point.x) *
sign;
1131 Vertex* w0 = side ? v0->prev : v0->next;
1135 int32_t dy0 = w0->point.y - v0->point.y;
1137 if ((dxn < 0) && (dy0 > 0) && ((dx0 == 0) || ((dx0 < 0) && (dy0 * dx < dy * dx0))))
1154 while (((
t = side ? w0->next : w0->prev) != v0) && (
t->point.x ==
x) && (
t->point.y <= y0))
1163 while (((
t = side ? w1->prev : w1->next) !=
v1) && (
t->point.x ==
x) && (
t->point.y >=
y1))
1188 if (h1.minXy->point.x < h0.minXy->point.x)
1190 h0.minXy = h1.minXy;
1192 if (h1.maxXy->point.x >= h0.maxXy->point.x)
1194 h0.maxXy = h1.maxXy;
1197 h0.maxYx = h1.maxYx;
1205 void btConvexHullInternal::computeInternal(
int start,
int end, IntermediateHull&
result)
1207 int n = end - start;
1218 Vertex*
v = originalVertices[start];
1220 if (
v->point !=
w->point)
1225 if ((dx == 0) && (dy == 0))
1227 if (
v->point.z >
w->point.z)
1248 if ((dx < 0) || ((dx == 0) && (dy < 0)))
1259 if ((dy < 0) || ((dy == 0) && (dx < 0)))
1282 Vertex*
v = originalVertices[start];
1298 Vertex*
v = originalVertices[start];
1312 int split0 = start + n / 2;
1313 Point32 p = originalVertices[split0 - 1]->point;
1314 int split1 = split0;
1315 while ((split1 < end) && (originalVertices[split1]->
point == p))
1319 computeInternal(start, split0,
result);
1320 IntermediateHull hull1;
1321 computeInternal(split1, end, hull1);
1322 #ifdef DEBUG_CONVEX_HULL
1323 printf(
"\n\nMerge\n");
1328 #ifdef DEBUG_CONVEX_HULL
1329 printf(
"\n Result\n");
1334 #ifdef DEBUG_CONVEX_HULL
1335 void btConvexHullInternal::IntermediateHull::print()
1354 if (
v->next->prev !=
v)
1356 printf(
" Inconsistency");
1367 minXy->copy = (minXy->copy == -1) ? -2 : -1;
1368 minXy->printGraph();
1372 void btConvexHullInternal::Vertex::printGraph()
1375 printf(
"\nEdges\n");
1384 }
while (
e != edges);
1388 if (
v->copy !=
copy)
1394 }
while (
e != edges);
1399 btConvexHullInternal::Orientation btConvexHullInternal::getOrientation(
const Edge*
prev,
const Edge*
next,
const Point32& s,
const Point32&
t)
1406 Point64 n =
t.cross(s);
1411 return (
dot > 0) ? COUNTER_CLOCKWISE : CLOCKWISE;
1413 return COUNTER_CLOCKWISE;
1425 btConvexHullInternal::Edge* btConvexHullInternal::findMaxAngle(
bool ccw,
const Vertex* start,
const Point32& s,
const Point64& rxs,
const Point64& sxrxs, Rational64& minCot)
1429 #ifdef DEBUG_CONVEX_HULL
1430 printf(
"find max edge for %d\n", start->point.index);
1432 Edge*
e = start->edges;
1437 if (
e->copy > mergeStamp)
1439 Point32
t = *
e->target - *start;
1440 Rational64 cot(
t.dot(sxrxs),
t.dot(rxs));
1441 #ifdef DEBUG_CONVEX_HULL
1442 printf(
" Angle is %f (%d) for ", (
float)
btAtan(cot.toScalar()), (
int)cot.isNaN());
1447 btAssert(ccw ? (
t.dot(s) < 0) : (
t.dot(s) > 0));
1452 if (minEdge ==
NULL)
1457 else if ((cmp = cot.compare(minCot)) < 0)
1462 else if ((cmp == 0) && (ccw == (getOrientation(minEdge,
e, s,
t) == COUNTER_CLOCKWISE)))
1467 #ifdef DEBUG_CONVEX_HULL
1472 }
while (
e != start->edges);
1481 Point32 et0 = start0 ? start0->target->point : c0->point;
1482 Point32 et1 = start1 ? start1->target->point : c1->point;
1483 Point32 s = c1->point - c0->point;
1484 Point64
normal = ((start0 ? start0 : start1)->target->point - c0->point).cross(s);
1486 btAssert(!start1 || (start1->target->point.dot(
normal) == dist));
1487 Point64 perp = s.cross(
normal);
1490 #ifdef DEBUG_CONVEX_HULL
1491 printf(
" Advancing %d %d (%p %p, %d %d)\n", c0->point.index, c1->point.index, start0, start1, start0 ? start0->target->point.index : -1, start1 ? start1->target->point.index : -1);
1494 int64_t maxDot0 = et0.dot(perp);
1497 while (e0->target != stop0)
1499 Edge*
e = e0->reverse->prev;
1500 if (
e->target->point.dot(
normal) < dist)
1505 if (
e->copy == mergeStamp)
1516 et0 =
e->target->point;
1520 int64_t maxDot1 = et1.dot(perp);
1523 while (e1->target != stop1)
1525 Edge*
e = e1->reverse->next;
1526 if (
e->target->point.dot(
normal) < dist)
1531 if (
e->copy == mergeStamp)
1542 et1 =
e->target->point;
1546 #ifdef DEBUG_CONVEX_HULL
1547 printf(
" Starting at %d %d\n", et0.index, et1.index);
1550 int64_t dx = maxDot1 - maxDot0;
1557 if (e0 && (e0->target != stop0))
1559 Edge* f0 = e0->next->reverse;
1560 if (f0->copy > mergeStamp)
1562 int64_t dx0 = (f0->target->point - et0).
dot(perp);
1563 int64_t dy0 = (f0->target->point - et0).
dot(s);
1564 if ((dx0 == 0) ? (dy0 < 0) : ((dx0 < 0) && (Rational64(dy0, dx0).compare(Rational64(dy, dx)) >= 0)))
1566 et0 = f0->target->point;
1567 dx = (et1 - et0).
dot(perp);
1568 e0 = (e0 == start0) ?
NULL : f0;
1574 if (e1 && (e1->target != stop1))
1576 Edge* f1 = e1->reverse->next;
1577 if (f1->copy > mergeStamp)
1579 Point32 d1 = f1->target->point - et1;
1584 int64_t dxn = (f1->target->point - et0).
dot(perp);
1585 if ((dxn > 0) && ((dx1 == 0) ? (dy1 < 0) : ((dx1 < 0) && (Rational64(dy1, dx1).compare(Rational64(dy, dx)) > 0))))
1588 et1 = e1->target->point;
1609 if (e1 && (e1->target != stop1))
1611 Edge* f1 = e1->prev->reverse;
1612 if (f1->copy > mergeStamp)
1614 int64_t dx1 = (f1->target->point - et1).
dot(perp);
1615 int64_t dy1 = (f1->target->point - et1).
dot(s);
1616 if ((dx1 == 0) ? (dy1 > 0) : ((dx1 < 0) && (Rational64(dy1, dx1).compare(Rational64(dy, dx)) <= 0)))
1618 et1 = f1->target->point;
1619 dx = (et1 - et0).
dot(perp);
1620 e1 = (e1 == start1) ?
NULL : f1;
1626 if (e0 && (e0->target != stop0))
1628 Edge* f0 = e0->reverse->prev;
1629 if (f0->copy > mergeStamp)
1631 Point32 d0 = f0->target->point - et0;
1636 int64_t dxn = (et1 - f0->target->point).
dot(perp);
1637 if ((dxn < 0) && ((dx0 == 0) ? (dy0 > 0) : ((dx0 < 0) && (Rational64(dy0, dx0).compare(Rational64(dy, dx)) < 0))))
1640 et0 = e0->target->point;
1655 #ifdef DEBUG_CONVEX_HULL
1656 printf(
" Advanced edges to %d %d\n", et0.index, et1.index);
1660 void btConvexHullInternal::merge(IntermediateHull& h0, IntermediateHull& h1)
1686 if (mergeProjection(h0, h1, c0, c1))
1688 Point32 s = *c1 - *c0;
1689 Point64
normal = Point32(0, 0, -1).cross(s);
1693 Edge*
e = c0->edges;
1701 if ((
dot == 0) && ((*
e->target - *c0).dot(
t) > 0))
1703 if (!start0 || (getOrientation(start0,
e, s, Point32(0, 0, -1)) == CLOCKWISE))
1709 }
while (
e != c0->edges);
1720 if ((
dot == 0) && ((*
e->target - *c1).dot(
t) > 0))
1722 if (!start1 || (getOrientation(start1,
e, s, Point32(0, 0, -1)) == COUNTER_CLOCKWISE))
1728 }
while (
e != c1->edges);
1731 if (start0 || start1)
1733 findEdgeForCoplanarFaces(c0, c1, start0, start1,
NULL,
NULL);
1736 c0 = start0->target;
1740 c1 = start1->target;
1744 prevPoint = c1->point;
1749 prevPoint = c1->point;
1755 bool firstRun =
true;
1759 Point32 s = *c1 - *c0;
1760 Point32
r = prevPoint - c0->point;
1761 Point64 rxs =
r.cross(s);
1762 Point64 sxrxs = s.cross(rxs);
1764 #ifdef DEBUG_CONVEX_HULL
1765 printf(
"\n Checking %d %d\n", c0->point.index, c1->point.index);
1767 Rational64 minCot0(0, 0);
1768 Edge* min0 = findMaxAngle(
false, c0, s, rxs, sxrxs, minCot0);
1769 Rational64 minCot1(0, 0);
1770 Edge* min1 = findMaxAngle(
true, c1, s, rxs, sxrxs, minCot1);
1773 Edge*
e = newEdgePair(c0, c1);
1784 int cmp = !min0 ? 1 : !min1 ? -1 : minCot0.compare(minCot1);
1785 #ifdef DEBUG_CONVEX_HULL
1786 printf(
" -> Result %d\n", cmp);
1788 if (firstRun || ((cmp >= 0) ? !minCot1.isNegativeInfinity() : !minCot0.isNegativeInfinity()))
1790 Edge*
e = newEdgePair(c0, c1);
1793 pendingTail0->prev =
e;
1799 e->next = pendingTail0;
1805 pendingTail1->next =
e;
1811 e->prev = pendingTail1;
1818 #ifdef DEBUG_CONVEX_HULL
1819 printf(
" Found min edges to %d %d\n", e0 ? e0->target->point.index : -1, e1 ? e1->target->point.index : -1);
1824 findEdgeForCoplanarFaces(c0, c1, e0, e1,
NULL,
NULL);
1827 if ((cmp >= 0) && e1)
1831 for (
Edge *
e = toPrev1->next, *n =
NULL;
e != min1;
e = n)
1842 toPrev1->link(pendingHead1);
1846 min1->prev->link(pendingHead1);
1847 firstNew1 = pendingHead1;
1849 pendingTail1->link(min1);
1850 pendingHead1 =
NULL;
1851 pendingTail1 =
NULL;
1858 prevPoint = c1->point;
1860 toPrev1 = e1->reverse;
1863 if ((cmp <= 0) && e0)
1867 for (
Edge *
e = toPrev0->prev, *n =
NULL;
e != min0;
e = n)
1878 pendingHead0->link(toPrev0);
1882 pendingHead0->link(min0->next);
1883 firstNew0 = pendingHead0;
1885 min0->link(pendingTail0);
1886 pendingHead0 =
NULL;
1887 pendingTail0 =
NULL;
1894 prevPoint = c0->point;
1896 toPrev0 = e0->reverse;
1900 if ((c0 == first0) && (c1 == first1))
1902 if (toPrev0 ==
NULL)
1904 pendingHead0->link(pendingTail0);
1905 c0->edges = pendingTail0;
1909 for (
Edge *
e = toPrev0->prev, *n =
NULL;
e != firstNew0;
e = n)
1916 pendingHead0->link(toPrev0);
1917 firstNew0->link(pendingTail0);
1921 if (toPrev1 ==
NULL)
1923 pendingTail1->link(pendingHead1);
1924 c1->edges = pendingTail1;
1928 for (
Edge *
e = toPrev1->next, *n =
NULL;
e != firstNew1;
e = n)
1935 toPrev1->link(pendingHead1);
1936 pendingTail1->link(firstNew1);
1952 return (p.
y < q.
y) || ((p.
y == q.
y) && ((p.
x < q.
x) || ((p.
x == q.
x) && (p.
z < q.
z))));
1959 const char*
ptr = (
const char*)coords;
1962 for (
int i = 0; i <
count; i++)
1964 const double*
v = (
const double*)
ptr;
1973 for (
int i = 0; i <
count; i++)
1975 const float*
v = (
const float*)
ptr;
1993 if (((medAxis + 1) % 3) !=
maxAxis)
2016 ptr = (
const char*)coords;
2019 for (
int i = 0; i <
count; i++)
2021 const double*
v = (
const double*)
ptr;
2025 points[i].x = (
int32_t)p[medAxis];
2028 points[i].index = i;
2033 for (
int i = 0; i <
count; i++)
2035 const float*
v = (
const float*)
ptr;
2039 points[i].x = (
int32_t)p[medAxis];
2042 points[i].index = i;
2048 vertexPool.setArraySize(
count);
2050 for (
int i = 0; i <
count; i++)
2052 Vertex*
v = vertexPool.newObject();
2054 v->point = points[i];
2056 originalVertices[i] =
v;
2062 edgePool.setArraySize(6 *
count);
2065 maxUsedEdgePairs = 0;
2069 IntermediateHull hull;
2070 computeInternal(0,
count, hull);
2072 #ifdef DEBUG_CONVEX_HULL
2073 printf(
"max. edges %d (3v = %d)", maxUsedEdgePairs, 3 *
count);
2077 btVector3 btConvexHullInternal::toBtVector(
const Point32&
v)
2088 return toBtVector(face->dir0).cross(toBtVector(face->dir1)).normalized();
2094 p[medAxis] =
v->xvalue();
2097 return p * scaling +
center;
2106 int stamp = --mergeStamp;
2113 Int128 hullCenterX(0, 0);
2114 Int128 hullCenterY(0, 0);
2115 Int128 hullCenterZ(0, 0);
2118 while (stack.
size() > 0)
2127 if (
e->target->copy != stamp)
2129 e->target->copy = stamp;
2132 if (
e->copy != stamp)
2134 Face* face = facePool.newObject();
2135 face->
init(
e->target,
e->reverse->prev->target,
v);
2136 faces.push_back(face);
2145 int64_t vol = (
v->point - ref).
dot((
a->point - ref).cross(
b->point - ref));
2148 hullCenterX += vol *
c.x;
2149 hullCenterY += vol *
c.y;
2150 hullCenterZ += vol *
c.z;
2165 }
while (
e !=
v->edges);
2175 hullCenter[medAxis] = hullCenterX.
toScalar();
2178 hullCenter /= 4 * volume.
toScalar();
2179 hullCenter *= scaling;
2181 int faceCount =
faces.size();
2183 if (clampAmount > 0)
2186 for (
int i = 0; i < faceCount; i++)
2201 amount =
btMin(amount, minDist * clampAmount);
2204 unsigned int seed = 243703;
2205 for (
int i = 0; i < faceCount; i++,
seed = 1664525 *
seed + 1013904223)
2210 for (
int i = 0; i < faceCount; i++)
2212 if (!shiftFace(
faces[i], amount, stack))
2223 btVector3 origShift = getBtNormal(face) * -amount;
2224 if (scaling[0] != 0)
2226 origShift[0] /= scaling[0];
2228 if (scaling[1] != 0)
2230 origShift[1] /= scaling[1];
2232 if (scaling[2] != 0)
2234 origShift[2] /= scaling[2];
2236 Point32 shift((
int32_t)origShift[medAxis], (
int32_t)origShift[maxAxis], (
int32_t)origShift[minAxis]);
2241 Point64
normal = face->getNormal();
2242 #ifdef DEBUG_CONVEX_HULL
2243 printf(
"\nShrinking face (%d %d %d) (%d %d %d) (%d %d %d) by (%d %d %d)\n",
2244 face->origin.x, face->origin.y, face->origin.z, face->dir0.x, face->dir0.y, face->dir0.z, face->dir1.x, face->dir1.y, face->dir1.z, shift.x, shift.y, shift.z);
2247 Point32 shiftedOrigin = face->origin + shift;
2250 if (shiftedDot >= origDot)
2257 Edge* startEdge = face->nearbyVertex->edges;
2258 #ifdef DEBUG_CONVEX_HULL
2259 printf(
"Start edge is ");
2261 printf(
", normal is (%lld %lld %lld), shifted dot is %lld\n",
normal.x,
normal.y,
normal.z, shiftedDot);
2263 Rational128 optDot = face->nearbyVertex->dot(
normal);
2264 int cmp = optDot.compare(shiftedDot);
2265 #ifdef SHOW_ITERATIONS
2270 Edge*
e = startEdge;
2273 #ifdef SHOW_ITERATIONS
2278 #ifdef DEBUG_CONVEX_HULL
2279 printf(
"Moving downwards, edge is ");
2281 printf(
", dot is %f (%f %lld)\n", (
float)
dot.toScalar(), (
float)optDot.toScalar(), shiftedDot);
2283 if (
dot.compare(optDot) < 0)
2285 int c =
dot.compare(shiftedDot);
2297 }
while (
e != startEdge);
2306 Edge*
e = startEdge;
2309 #ifdef SHOW_ITERATIONS
2314 #ifdef DEBUG_CONVEX_HULL
2315 printf(
"Moving upwards, edge is ");
2317 printf(
", dot is %f (%f %lld)\n", (
float)
dot.toScalar(), (
float)optDot.toScalar(), shiftedDot);
2319 if (
dot.compare(optDot) > 0)
2321 cmp =
dot.compare(shiftedDot);
2332 }
while (
e != startEdge);
2340 #ifdef SHOW_ITERATIONS
2341 printf(
"Needed %d iterations to find initial intersection\n", n);
2347 #ifdef SHOW_ITERATIONS
2350 while (
e->target->dot(
normal).compare(shiftedDot) <= 0)
2352 #ifdef SHOW_ITERATIONS
2360 #ifdef DEBUG_CONVEX_HULL
2361 printf(
"Checking for outwards edge, current edge is ");
2366 #ifdef SHOW_ITERATIONS
2367 printf(
"Needed %d iterations to check for complete containment\n", n);
2375 #ifdef SHOW_ITERATIONS
2380 #ifdef SHOW_ITERATIONS
2383 #ifdef DEBUG_CONVEX_HULL
2384 printf(
"Intersecting edge is ");
2392 #ifdef SHOW_ITERATIONS
2397 #ifdef SHOW_ITERATIONS
2400 if (
e->target->dot(
normal).compare(shiftedDot) >= 0)
2411 #ifdef SHOW_ITERATIONS
2412 printf(
"Needed %d iterations to advance intersection\n", n);
2416 #ifdef DEBUG_CONVEX_HULL
2417 printf(
"Advanced intersecting edge to ");
2419 printf(
", cmp = %d\n", cmp);
2422 if (!firstIntersection)
2433 Edge* prevFaceEdge = faceEdge;
2436 #ifdef SHOW_ITERATIONS
2441 #ifdef SHOW_ITERATIONS
2444 e =
e->reverse->prev;
2446 cmp =
e->target->dot(
normal).compare(shiftedDot);
2447 #ifdef DEBUG_CONVEX_HULL
2448 printf(
"Testing edge ");
2450 printf(
" -> cmp = %d\n", cmp);
2458 #ifdef SHOW_ITERATIONS
2459 printf(
"Needed %d iterations to find other intersection of face\n", n);
2468 removed->edges =
NULL;
2472 removed->edges =
e->prev;
2473 e->prev->link(
e->next);
2476 #ifdef DEBUG_CONVEX_HULL
2477 printf(
"1: Removed part contains (%d %d %d)\n", removed->point.x, removed->point.y, removed->point.z);
2482 int64_t m00 = face->dir0.dot(n0);
2483 int64_t m01 = face->dir1.dot(n0);
2484 int64_t m10 = face->dir0.dot(n1);
2485 int64_t m11 = face->dir1.dot(n1);
2490 Vertex*
v = vertexPool.newObject();
2491 v->point.index = -1;
2497 v->point.x = (
int32_t)
v->point128.xvalue();
2498 v->point.y = (
int32_t)
v->point128.yvalue();
2499 v->point.z = (
int32_t)
v->point128.zvalue();
2508 if (cmp || prevCmp || (prevIntersection->reverse->next->target !=
intersection->target))
2510 faceEdge = newEdgePair(prevIntersection->target,
intersection->target);
2513 faceEdge->link(prevIntersection->reverse->next);
2515 if ((prevCmp == 0) || prevFaceEdge)
2517 prevIntersection->reverse->link(faceEdge);
2527 faceEdge = prevIntersection->reverse->next;
2534 faceEdge->link(prevFaceEdge->reverse);
2536 else if (faceEdge != prevFaceEdge->reverse)
2539 while (faceEdge->next != prevFaceEdge->reverse)
2541 Vertex* removed = faceEdge->next->target;
2542 removeEdgePair(faceEdge->next);
2544 #ifdef DEBUG_CONVEX_HULL
2545 printf(
"2: Removed part contains (%d %d %d)\n", removed->point.x, removed->point.y, removed->point.z);
2551 faceEdge->face = face;
2556 firstFaceEdge = faceEdge;
2559 #ifdef SHOW_ITERATIONS
2560 printf(
"Needed %d iterations to process all intersections\n", m);
2565 firstFaceEdge->reverse->target = faceEdge->target;
2566 firstIntersection->reverse->link(firstFaceEdge);
2567 firstFaceEdge->link(faceEdge->reverse);
2569 else if (firstFaceEdge != faceEdge->reverse)
2572 while (firstFaceEdge->next != faceEdge->reverse)
2574 Vertex* removed = firstFaceEdge->next->target;
2575 removeEdgePair(firstFaceEdge->next);
2577 #ifdef DEBUG_CONVEX_HULL
2578 printf(
"3: Removed part contains (%d %d %d)\n", removed->point.x, removed->point.y, removed->point.z);
2587 #ifdef DEBUG_CONVEX_HULL
2588 printf(
"Removing part\n");
2590 #ifdef SHOW_ITERATIONS
2596 int end = stack.
size();
2600 #ifdef DEBUG_CONVEX_HULL
2603 bool deeper =
false;
2605 while ((removed = stack[
pos++]) !=
NULL)
2607 #ifdef SHOW_ITERATIONS
2610 kept->receiveNearbyFaces(removed);
2611 while (removed->edges)
2618 stack.
push_back(removed->edges->target);
2619 removeEdgePair(removed->edges);
2628 #ifdef SHOW_ITERATIONS
2629 printf(
"Needed %d iterations to remove part\n", n);
2633 face->origin = shiftedOrigin;
2640 int index = vertex->
copy;
2643 index = vertices.
size();
2644 vertex->
copy = index;
2646 #ifdef DEBUG_CONVEX_HULL
2647 printf(
"Vertex %d gets index *%d\n", vertex->
point.
index, index);
2676 original_vertex_index.resize(0);
2683 while (copied < oldVertices.
size())
2687 original_vertex_index.push_back(
v->point.index);
2698 int s = edges.size();
2699 edges.push_back(
Edge());
2700 edges.push_back(
Edge());
2701 Edge*
c = &edges[s];
2702 Edge*
r = &edges[s + 1];
2704 e->reverse->copy = s + 1;
2708 r->targetVertex = copied;
2709 #ifdef DEBUG_CONVEX_HULL
2710 printf(
" CREATE: Vertex *%d has edge to *%d\n", copied,
c->getTargetVertex());
2715 edges[
e->copy].next = prevCopy -
e->copy;
2719 firstCopy =
e->copy;
2723 }
while (
e != firstEdge);
2724 edges[firstCopy].next = prevCopy - firstCopy;
2729 for (
int i = 0; i < copied; i++)
2740 #ifdef DEBUG_CONVEX_HULL
2741 printf(
"Vertex *%d has edge to *%d\n", i, edges[
e->copy].getTargetVertex());
2743 faces.push_back(
e->copy);
2747 #ifdef DEBUG_CONVEX_HULL
2748 printf(
" Face *%d\n", edges[f->
copy].getTargetVertex());
2755 }
while (
e != firstEdge);
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble y1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei stride
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object for example to give variation to multiple instances of an object Point Retrieve information about points in a point cloud Retrieve the edges of an object as it appears to Cycles topology will always appear triangulated Convert a blackbody temperature to an RGB value Normal Generate a perturbed normal from an RGB normal map image Typically used for faking highly detailed surfaces Generate an OSL shader from a file or text data block Image Sample an image file as a texture Sky Generate a procedural sky texture Noise Generate fractal Perlin noise Wave Generate procedural bands or rings with noise Voronoi Generate Worley noise based on the distance to random points Typically used to generate textures such as or biological cells Brick Generate a procedural texture producing bricks Texture Retrieve multiple types of texture coordinates nTypically used as inputs for texture nodes Vector Convert a point
return(oflags[bm->toolflag_index].f &oflag) !=0
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
#define btAlignedFree(ptr)
#define btAlignedAlloc(size, alignment)
static int getVertexCopy(btConvexHullInternal::Vertex *vertex, btAlignedObjectArray< btConvexHullInternal::Vertex * > &vertices)
unsigned long long int uint64_t
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
SIMD_FORCE_INLINE const T & btMin(const T &a, const T &b)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
SIMD_FORCE_INLINE btScalar btAtan(btScalar x)
SIMD_FORCE_INLINE void btSwap(T &a, T &b)
static unsigned long seed
SIMD_FORCE_INLINE int maxAxis() const
Return the axis with the largest value Note return values are 0,1,2 for x, y, or z.
btVector3
btVector3 can be used to represent 3D points and vectors. It has an un-used w component to suit 16-by...
SIMD_FORCE_INLINE int minAxis() const
Return the axis with the smallest value Note return values are 0,1,2 for x, y, or z.
SIMD_FORCE_INLINE void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
SIMD_FORCE_INLINE int size() const
return the number of elements in the array
SIMD_FORCE_INLINE void pop_back()
SIMD_FORCE_INLINE void resize(int newsize, const T &fillData=T())
void quickSort(const L &CompareFunc)
SIMD_FORCE_INLINE void push_back(const T &_Val)
static void mul(UWord a, UWord b, UWord &resLow, UWord &resHigh)
Face * nextWithSameNearbyVertex
void init(Vertex *a, Vertex *b, Vertex *c)
int ucmp(const Int128 &b) const
Int128 operator+(const Int128 &b) const
Int128 operator*(int64_t b) const
Int128(uint64_t low, uint64_t high)
bool operator<(const Int128 &b) const
Int128 & operator+=(const Int128 &b)
Int128 operator-(const Int128 &b) const
btScalar toScalar() const
static Int128 mul(int64_t a, int64_t b)
int64_t dot(const Point64 &b) const
Point32(int32_t x, int32_t y, int32_t z)
Point32 operator-(const Point32 &b) const
int64_t dot(const Point32 &b) const
bool operator!=(const Point32 &b) const
Point64 cross(const Point64 &b) const
Point32 operator+(const Point32 &b) const
Point64 cross(const Point32 &b) const
bool operator==(const Point32 &b) const
Point64(int64_t x, int64_t y, int64_t z)
int64_t dot(const Point64 &b) const
PointR128(Int128 x, Int128 y, Int128 z, Int128 denominator)
btScalar toScalar() const
Rational128(const Int128 &numerator, const Int128 &denominator)
int compare(const Rational128 &b) const
Rational128(int64_t value)
bool isNegativeInfinity() const
btScalar toScalar() const
int compare(const Rational64 &b) const
Rational64(int64_t numerator, int64_t denominator)
Point32 operator-(const Vertex &b) const
Rational128 dot(const Point64 &b) const
void receiveNearbyFaces(Vertex *src)
void compute(const void *coords, bool doubleCoords, int stride, int count)
btVector3 getCoordinates(const Vertex *v)
btScalar shrink(btScalar amount, btScalar clampAmount)
bool operator()(const btConvexHullInternal::Point32 &p, const btConvexHullInternal::Point32 &q) const
SyclQueue void void * src
IconTextureDrawCall normal
ccl_gpu_kernel_postfix ccl_global float int int int int float bool reset
clear internal cached data and reset random seed
Intersection< segment > intersection
T dot(const vec_base< T, Size > &a, const vec_base< T, Size > &b)
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
SymEdge< T > * prev(const SymEdge< T > *se)
static RawVector< RawArray< int64_t, 0 > > arrays
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static void copy(bNodeTree *dest_ntree, bNode *dest_node, const bNode *src_node)
unsigned __int64 uint64_t
SymEdge< Arith_t > * next