# Manifold Extraction

_Feel free to modify or add anything that you consider relevant._

The goal of this project is ... TODO

## 09/28/2023
(following from last week)
- [ ] Triangle test cases (Yifei)
- [ ] Adapt existing test code to Trimesh data structure
- [ ] Extract boundary
- [ ] Detect non-manifold singularities
- [ ] Visualization w/ existing vtu writer
- [ ] Component extract_subset
- [ ] Create `std::vector<Tuple>` for all cells with the tag
- [ ] Iterate over all cells with tag and store vertices in a `std::vector<Simplex>`
- [ ] Sort and remove duplicates from Simplex vector
- [ ] Create a map from `Simplex` to vector index (`int`)
- [ ] Create new tet connectivity
- options:
- "embedding_dimension"
- "subset_dimension"

## 09/21/2023
- [ ] Triangle test cases (Yifei)
- [x] move code to tests/component instead of src
- [x] Create dummy component, pr to man-ext in the fork
- [x] Find simply connected components
- [x] Use Trimesh Data structure
- [ ] Extract boundary
- [ ] Detect non-manifold singularies
- [ ] Visualization, existing components in toolkit?
- [ ] Code for identifying degenerate star domains (Michael)
- [ ] reread Attene's paper (again)
- [ ] look through new version of toolkit to see if any data structures/navigation modules there would be helpful

## Future TODOs
- [ ] Do similar things for Tet test cases

## Related Work
- [On converting sets of tetrahedra to combinatorial and PL manifolds](https://www.sciencedirect.com/science/article/pii/S0167839609000703?ref=cra_js_challenge&fr=RR-1)
- [Bijective Projection in a Shell](https://cims.nyu.edu/gcl/papers/2020-BijectivePrism.pdf) (contains quadratic programming problem for geometry side)
- [A scalable data structure for three-dimensional non-manifold objects](https://diglib.eg.org/handle/10.2312/SGP.SGP03.072-082)

## Attene's paper notes

### Definitions

The star of A in K, $S(A, K)$, is the sub-complex of $K$ made of all simplices of $K$ having $A$ as a face plus all their faces.

The link of A in K $L(A, K)$ is the set of simplices in $S(A, K)$ whose intersection with $A$ is empty.

An edge $e$ is singular if $L(e)$ is not connected.

A vertex $v$ is singular if $L(v)$'s boundary contains more than one component (is not connected).

### Algorithms

TF(T) = faces of tetrahedron (4)
FT(F) = tets incident at a face (1 or 2)
FE(F) = edges of a face (3)
EV(E) = vertices of an edge (2)

FV(F) = EV(FE(F)) = vertices of a face (3)
TV(T) = FV(TF(T)) = vertices of a tetrahedron (4)

TE(T) = FE(TF(T)) = edges of a tetrahedron (6)

CreateEdgeLinksAndStars(Tetrahedrization T ){
    for each edge e in T
        L(e) := new empty edge list()
        T(e) := new empty tet list()
    for each tet t in T
        for each edge e in TE(t)
            e2 := the edge in TE(t) sharing no vertex with e
            Add e to L(e2) and t to T(e2)
}

//effectively creates a "ball" around each vertex, accessible by L(v)
CreateVertexLinks(Tetrahedrization T){
    for each vertex v in T
        L(v) := new empty face list
    for each tet t in T
        for each face f in TF(T)
            v := the vertex of TV(t) which is not in FV(f)
            Add f to L(v)
}

EditSingularVertex(Vertex v){
    1. Look for a connected component in L(v) which is a combinatorial 2-ball
    2. if there is such a component, let it be D
        3. Compute the set T of tets incident at v and having a face in D
        4. Create a new vertex w
        5. Remove all the tets in T from the tetrahedrization
        6. Create a new tet {w, w^i_1, w^i_2, w^i_3} for each face {w^i_1, w^i_2, w^i_3} in D
        7. Remove D from L(v)
    8. If L(v) has more than one component go to 1, else go to 15
    9. else (i.e. if there are no combinatorial 2-balls in L(v))
        10. Extract a boundary loop B of L(v)
        11. Compute the set D of faces incident at v and having an edge in B
        12. Create a new vertex w
        13. Create a new tet {w, w^i_1, w^i_2, v} for each face {w^i_1, w^i_2, v} in D
        14. Add all the faces {w, w^i_1, w^i_2} to L(v)
        15. If L(v) has more than one boundary component go to 10, else terminate
}

## Things to implement

CountConnectedComponents(Graph G){
    count = 0
    for v in G.Vertices:
        if v is unmarked:
            mark v
            count++
            unvisitedAdj = v.adj
            i = 0
            while i != len(unvisitedAdj):
                mark unvisitedAdj[i]
                append unvisitedAdj[i].adj to unvisitedAdj
                i++
    return count
}

DetectSingularEdges(Edges E){
    SingularEdges = []
    for e in E:
        if len(ConnectedComponents(L(e))) > 1:
            add e to SingularEdges
}

DetectSingularVertices(Vertices V){
    SingularVertices = []
    for v in V:
        if len(ConnectedComponents(boundary(L(v)))) > 1:
            add e to SingularVertices
}

EditSingularEdge(Edge e){
    
}

Notes from Nov 2

init everything as -1

every corner of every tri, get new id from counter, assign id to all corners in the connected component of this chosen corner

for every tri:
for every corner:
if its id != -1 continue;
else, get id from a counter
assign this id to all corners in the connect component of this chosen vertex.

reTopologize2D(Triangulation T){
    counter = 0
    for t in T:
        for v in V(T):
            
}