2014年3月12日水曜日

boost::polygon self intersection problem 顛末

この前のポストの問題ですが、面白い事がわかったので、顛末を書きます。 OpenGLES では、描画が float 精度までで、データは double 精度で保持しておりました。 これを boost::polygon にて、trapezoid にかけて台形化処理するのですが、その時に double から float に static_cast で精度を落とします。そうすると、自己交差の無い simple な図形が精度変換の過程で自己交差を持つ図形に変身するケースがあると判明しました。  じゃあ事前に float 精度に落として 自己交差のある状態の図形は float 精度で自己交差を解消した simple な状態にしてから double に戻せば問題無いだろうと思って、やってみましたが、何故かうまく行かない。詳しく突っ込んで調べていないですが、もしかしたら CPU に依存する話なのかもしれません。  余計な事をすると遅くなるので、なんとかしたかったですが、アプリが落ちてしまっては、元も子もありません。もう少し無駄な計算は省こうという事で、こんな感じで落ち着きました。
    void to_simple( Polygon& polygon ) {
      size_t len = polygon.self_.coords_.size();
      Point ss = polygon.self_.coords_[len-1];
      for( size_t i = 0; i < len-2; ++i ) {
        Point se = polygon.self_.coords_[i];
        Point es = polygon.self_.coords_[i+1];
        for( size_t j = i + 2; j < len; ++j ) {
          Point ee = polygon.self_.coords_[j];
          if( i != j ) {
            if( 
                 (ss.x() == es.x() && ss.y() == es.y() )
              || (ss.x() == ee.x() && ss.y() == ee.y() )
              || (se.x() == es.x() && se.y() == es.y() )
              || (se.x() == ee.x() && se.y() == ee.y() )
            ) {
            } else {
              double xx, yy;
              if( k_4t_close( xx, yy, ss.x(), ss.y(), se.x(), se.y(), es.x(), es.y(), ee.x(), ee.y() ) ) {
                se = Point( xx, yy );
                ee = Point( xx, yy );
                //if( i < j ) { // i < j は自明でしたねorz
                  polygon.self_.coords_.insert( polygon.self_.coords_.begin() + j, ee );
                  polygon.self_.coords_.insert( polygon.self_.coords_.begin() + i, se );
                //} else {
                //  polygon.self_.coords_.insert( polygon.self_.coords_.begin() + i, se );
                //  polygon.self_.coords_.insert( polygon.self_.coords_.begin() + j, ee );
                //}
                len += 2;
              }
            }
          }
          es = ee;
        }
        ss = se;
      }
    }

0 件のコメント: