How does p2p work when both computers are behind NAT?

I am wondering how can it be when there are just when there are just 2 users in a room that they can have a direct connection between them that clearly does not go through the server. If one of those computers would accept inbound I would understand, but for 2 computers behind NAT like all of us (the IPv4 ones at least), how can the two computers directly connect without server intermediation?

The protocol is called ICE which use several techniques to make sure a successful connection is established, including fallback to a relay(turnserver) when this is not possible.
To do a direct communication between two peers that are behind NAT a third server is used to discover the ip address and port, which also opens that port for incoming connections and in case of not strict firewall rules that connection is established between the two peers.