В общем, делается так.
Пусть фигура задана набором треугольных граней с известной ориентацией. В каждом ребре сходится чётное число граней (возможна, например, фигура из двух тетраэдров, склеенных по ребру), и при обходе любого ребра ориентации граней, сходящихся в нём, чередуются (например, идут грани ABC, BAD, ABE, BAF). Даже если в исходной модели таких странных рёбер нет, они могут возникнуть на промежуточном этапе.
Выбираем любые две грани со следующими свойствами:
- у них есть общее ребро AB;
- при обходе этого ребра они являются последовательными
- внутренний угол между этими гранями меньше 180 гр.
Такие грани найдутся всегда. Пусть это ABC и BAD.
Рассмотрим тетраэдр ABCD. Проверим, нет ли у него внутри других вершин. Если нет - заменим грани ABC и BAD на CAD и BCD (вырезав, тем самым, ABCD из модели). Если есть - возьмём ту вершину E из них, которая ближе всего к грани ABC, и заменим грань ABC на три грани ABE, AEC, EBC.
После этого просмотрим грани, и если оказалось, что какая-то грань встречается дважды с противоположными ориентациями (ABC и ACB) - выбрасываем обе копии.
Процесс повторяем, пока все грани не исчезнут.
Всё.
