Fantasy cartoon movie with "Native American"-ish theme from the '90

Question

I watched this film like 5 times when I was 10 and I've been struggling for two years now to find it. I remember it being rather bloody and gory, and the animation style I believe can be described as explicit, somehow realistic.

I think it was a story about native-Americans, a tribal vibe nonetheless. I remember the opening scene, a river, grass, next to a forest. I remember cannibalism scenes, some neanderthal-like creatures with black eyes that creeped me out, flesh of dead animals hanging from trees and lots of blood. I think the main character was fighting the aforementioned humanoids. The whole thing had a fantasy, demonish feel to it (for a 10 year old, I guess).

I also think it was created after 1990 and before 2004.

Answer 1

The dead flesh hanging from the tree made me think of this cartoon version of the Population Vuh, the Mayan creation myth. I saw it on public television in the early 1990s.

A few minutes in, the first true humans, One Hunter and Seven Hunter, are murdered by the ogrish demons of the underworld and hung up in a tree.