1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// SPDX-FileCopyrightText: 2023 Erin Catto
// SPDX-License-Identifier: MIT
#pragma once
#include "container.h"
#include <stdbool.h>
#include <stdint.h>
typedef struct b2Contact b2Contact;
typedef struct b2Joint b2Joint;
typedef struct b2World b2World;
// Cached contact data stored in the island for fast contiguous iteration.
// Avoids touching b2Contact during union-find in b2SplitIsland.
typedef struct b2ContactLink
{
int contactId;
int bodyIdA;
int bodyIdB;
} b2ContactLink;
b2DeclareArray( b2ContactLink );
// Cached joint data stored in the island for fast contiguous iteration.
typedef struct b2JointLink
{
int jointId;
int bodyIdA;
int bodyIdB;
} b2JointLink;
b2DeclareArray( b2JointLink );
// Deterministic solver
//
// Collide all awake contacts
// Use bit array to emit start/stop touching events in defined order, per thread. Try using contact index, assuming contacts are
// created in a deterministic order. bit-wise OR together bit arrays and issue changes:
// - start touching: merge islands - temporary linked list - mark root island dirty - wake all - largest island is root
// - stop touching: increment constraintRemoveCount
// Persistent island for awake bodies, joints, and contacts.
// Contacts are touching.
// Contacts and joints may connect to static bodies, but static bodies are not in the island.
// https://en.wikipedia.org/wiki/Component_(graph_theory)
// https://en.wikipedia.org/wiki/Dynamic_connectivity
typedef struct b2Island
{
// index of solver set stored in b2World
// may be B2_NULL_INDEX
int setIndex;
// island index within set
// may be B2_NULL_INDEX
int localIndex;
int islandId;
// Keeps track of how many contacts have been removed from this island.
// This is used to determine if an island is a candidate for splitting.
int constraintRemoveCount;
// I tried using a stack array for this but the data pointer goes out of
// sync when the world island array grows.
b2Array( int ) bodies;
// Contacts and joints that belong to this island. May connect to static
// bodies not in the island.
// Each link has the two body ids so that b2SplitIsland's union-find pass
// never needs to touch b2Contact/b2Joint.
b2Array( b2ContactLink ) contacts;
b2Array( b2JointLink ) joints;
} b2Island;
b2DeclareArray( b2Island );
// This is used to move islands across solver sets
typedef struct b2IslandSim
{
int islandId;
} b2IslandSim;
b2DeclareArray( b2IslandSim );
b2Island* b2CreateIsland( b2World* world, int setIndex );
void b2DestroyIsland( b2World* world, int islandId );
// Link contacts into the island graph when it starts having contact points
void b2LinkContact( b2World* world, b2Contact* contact );
// Unlink contact from the island graph when it stops having contact points
void b2UnlinkContact( b2World* world, b2Contact* contact );
// Link a joint into the island graph when it is created
void b2LinkJoint( b2World* world, b2Joint* joint );
// Unlink a joint from the island graph when it is destroyed
void b2UnlinkJoint( b2World* world, b2Joint* joint );
void b2SplitIsland( b2World* world, int baseId );
void b2SplitIslandTask( void* context );
void b2ValidateIsland( b2World* world, int islandId );