ポリゴンリダクションとは
3Dモデルのポリゴン数を削除する処理です。
左：ポリゴンリダクション前、右：ポリゴンリダクション後
ポリゴンリダクションの処理
ポリゴンリダクションは辺をマージして、１頂点にします。
上図においてlを削除すると
・lをマージして、P
・P1、P2を削除
・l1、l2を削除
・H1、H2を削除
ハーフエッジ構造
ポリゴンリダクションのためにはハーフエッジ構造を使うことが多いようです。
Swiftでポリゴンリダクションして、Metalで表示するプログラムを下記にアップロードしました。
https://github.com/fuziki/polygonReduction
モデルのロード
ModelIOを用いてobjファイルをロードします。
右回りにハーフエッジを取得するために、作成した法線とモデルの法線の向きが一致しているかチェックしています。
PolygonReduction.swift
class HalfEdgeStructure {
static func LoadModel(mtlEz: MetalEz, name: String, reduction: Int) -> Model {
print("load model")
let model = Model()
let bodyVtx = mtlEz.loader.loadMesh(name: name).vertexBuffers[0].buffer
let pOriBuffer = bodyVtx.contents().assumingMemoryBound(to: MeshPoint.self)
let vertexCount:Int = bodyVtx.length / MemoryLayout<MeshPoint>.size
print("set half edge", vertexCount)
for i in 0..<(vertexCount/3) {
let v0 = pOriBuffer.advanced(by: i * 3 + 0).pointee.point
var v1 = pOriBuffer.advanced(by: i * 3 + 1).pointee.point
var v2 = pOriBuffer.advanced(by: i * 3 + 2).pointee.point
let mynm = cross(float3(v1.x - v0.x, v1.y - v0.y, v1.z - v0.z), float3(v2.x - v0.x, v2.y - v0.y, v2.z - v0.z))
let ptnm = pOriBuffer.advanced(by: i * 3 + 0).pointee.normal
let asnm = dot(float3(ptnm.x, ptnm.y, ptnm.z), mynm)
if asnm < 0 {
print("chenge vertex")
let myv = v1
v1 = v2
v2 = myv
}
model.addPolygon(vertex0: float3(v0.x, v0.y, v0.z),
vertex1: float3(v1.x, v1.y, v1.z), vertex2: float3(v2.x, v2.y, v2.z))
}
print("update qem all")
model.updateQuadraticErrorMetricsAll()
print("reductioning")
model.polygonReduction(count: reduction)
return model
}
}
ハーフエッジ
次、前、ペアのハーフエッジに加えて、自身のハーフエッジを含むポリゴンとフルエッジにアクセスできるように情報を保持しています。
PolygonReduction.swift
extension HalfEdgeStructure {
class HalfEdge {
var vertex: float3 //始点となる頂点
private(set) var nextHalfEdge: HalfEdge! //次のハーフエッジ
private(set) var prevHalfEdge: HalfEdge! //前のハーフエッジ
var pairHalfEdge: HalfEdge? //稜線を挟んで反対側のハーフエッジ
var fullEdgeStatus: FullEdge.Status! //このハーフエッジを含むフルエッジ
var polygonStatus: Polygon.Status! //このハーフエッジを含む面
init(vertex v: float3) {
vertex = v
}
func repeatPrevHalfEdge(_ action:(HalfEdge) -> Void) {
var heCK = self.prevHalfEdge.pairHalfEdge!
repeat {
action(heCK)
heCK = heCK.prevHalfEdge.pairHalfEdge!
} while heCK !== self
}
func repeatNextHalfEdge(_ action:(HalfEdge) -> Void) {
var heCK = self.nextHalfEdge.pairHalfEdge!
repeat {
action(heCK)
heCK = heCK.nextHalfEdge.pairHalfEdge!
} while heCK !== self
}
}
}
フルエッジ
順方向のハーフエッジと、逆方向のハーフエッジを保持しています。
また、QEMの計算と自身がポリゴンリダクション可能かの判定をします。
PolygonReduction.swift
extension HalfEdgeStructure {
class FullEdge {
private(set) var uuid: String
private(set) var leftHalfEdge: HalfEdge! //順方向のハーフエッジ
private(set) var rightHalfEdge: HalfEdge? //逆方向のハーフエッジ
var quadraticErrorMetrics: Double = 0.0 //QEM
var candidateNewVertex = float3(0, 0, 0) //QEMを計算した頂点
init(left: HalfEdge, right: HalfEdge? = nil) {
uuid = NSUUID().uuidString
set(left: left)
if let right = right {
set(right: right)
setPairsEachOther()
}
}
func updateQuadraticErrorMetrics(polygons: inout [String: Polygon]) {
if self.isAbleToCollapse == false {
quadraticErrorMetrics = Double.infinity
return
}
var updatePolygonID = [String]()
leftHalfEdge.repeatPrevHalfEdge{halfEdge in updatePolygonID.append(halfEdge.polygonStatus.uuid)}
leftHalfEdge.repeatNextHalfEdge{halfEdge in updatePolygonID.append(halfEdge.polygonStatus.uuid)}
candidateNewVertex = (self.startVertex + self.endVertex) * 0.5
quadraticErrorMetrics = 0
for uuid in updatePolygonID.unique {
if let f = polygons[uuid] {
quadraticErrorMetrics += pow(f.distanceBy(point: candidateNewVertex), 2)
}
}
}
var isAbleToCollapse: Bool {
guard let leftHalfEdge = self.leftHalfEdge,
let rightHalfEdge = self.rightHalfEdge else { return false }
guard let heLT = leftHalfEdge.prevHalfEdge.pairHalfEdge,
let heRT = leftHalfEdge.nextHalfEdge.pairHalfEdge,
let _ = rightHalfEdge.nextHalfEdge.pairHalfEdge, /*heLB*/
let _ = rightHalfEdge.prevHalfEdge.pairHalfEdge /*heRB*/ else { return false}
var l_neighborhood = [float3]()
var r_neighborhood = [float3]()
var heCK: HalfEdge
heCK = heLT
repeat {
l_neighborhood.append(heCK.endVertex)
if heCK.prevHalfEdge.pairHalfEdge == nil { return false }
heCK = heCK.prevHalfEdge.pairHalfEdge!
} while heCK !== self.leftHalfEdge
heCK = heRT
repeat {
r_neighborhood.append(heCK.startVertex)
if heCK.nextHalfEdge.pairHalfEdge == nil { return false }
heCK = heCK.nextHalfEdge.pairHalfEdge!
} while heCK !== self.leftHalfEdge
var cnt: Int = 0
for l in l_neighborhood {
for r in r_neighborhood {
if l == r { cnt += 1 }
}
}
if cnt >= 3 { return false }
return true
}
}
}
ポリゴン
ハーフエッジは、ハーフエッジのみで、巡回できるので、所属するハーフエッジの１つだけを保持します。
PolygonReduction.swift
extension HalfEdgeStructure {
class Polygon {
private(set) var uuid: String
private(set) var halfEdge: HalfEdge //含むハーフエッジの１つ
struct Status {
var uuid: String
}
init(halfEdge h: HalfEdge) {
uuid = NSUUID().uuidString
halfEdge = h
var he = halfEdge
repeat {
he.polygonStatus = Status(uuid: self.uuid)
he = he.nextHalfEdge
} while he !== halfEdge
}
private var equation: float4 {
let v0 = halfEdge.vertex
let v1 = halfEdge.nextHalfEdge.vertex
let v2 = halfEdge.prevHalfEdge.vertex
let c = cross(v1 - v0, v2 - v0)
let d = -1 * dot(v0, c)
return float4(c.x, c.y, c.z, d)
}
func distanceBy(point: float3) -> Double {
return Double(dot(self.equation, point.toFloat4))
}
}
}
モデル
モデルを表示するためのポリゴンの辞書と、ポリゴンリダクション用のフルエッジの辞書を保持しています。
１回のポリゴンリダクション処理で、２つの面を削除するので、削除する面数の半分の回数だけポリゴンリダクションの処理をします。
PolygonReduction.swift
extension HalfEdgeStructure {
class Model {
private(set) var polygons: [String: Polygon]
private(set) var fullEdges: [String: FullEdge]
init() {
polygons = [String: Polygon]()
fullEdges = [String: FullEdge]()
}
func addPolygon(vertex0: float3, vertex1: float3, vertex2: float3) {
print("add polygon")
let he0 = HalfEdge(vertex: vertex0)
let he1 = HalfEdge(vertex: vertex1)
let he2 = HalfEdge(vertex: vertex2)
he0.setHalfEdge(next: he1, prev: he2)
he1.setHalfEdge(next: he2, prev: he0)
he2.setHalfEdge(next: he0, prev: he1)
let polygon = Polygon(halfEdge: he0)
polygons[polygon.uuid] = polygon
setPair(halfEdges: he0, he1, he2)
}
func updateQuadraticErrorMetricsAll() {
for (_, fullEdge) in fullEdges {
fullEdge.updateQuadraticErrorMetrics(polygons: &polygons)
}
}
private func collapse(fullEdge: FullEdge) {
print("edgeCollapse")
if fullEdge.isAbleToCollapse == false {
fullEdge.quadraticErrorMetrics = Double.infinity
return
}
guard let leftHalfEdge = fullEdge.leftHalfEdge,
let rightHalfEdge = fullEdge.rightHalfEdge else { return }
guard let heLT = leftHalfEdge.prevHalfEdge.pairHalfEdge,
let heRT = leftHalfEdge.nextHalfEdge.pairHalfEdge,
let heLB = rightHalfEdge.nextHalfEdge.pairHalfEdge,
let heRB = rightHalfEdge.prevHalfEdge.pairHalfEdge else { return}
var updatedHalfEdge = [String]()
leftHalfEdge.repeatPrevHalfEdge{halfEdge in
halfEdge.startVertex = fullEdge.candidateNewVertex
updatedHalfEdge.append(halfEdge.fullEdgeStatus.uuid)
}
leftHalfEdge.repeatNextHalfEdge{halfEdge in
halfEdge.endVertex = fullEdge.candidateNewVertex
updatedHalfEdge.append(halfEdge.fullEdgeStatus.uuid)
}
for id in [fullEdge.uuid, heRT.fullEdgeStatus.uuid, heLT.fullEdgeStatus.uuid,
heLB.fullEdgeStatus.uuid, heRB.fullEdgeStatus.uuid] {
fullEdges.removeValue(forKey: id)
updatedHalfEdge.remove(value: id)
}
let fe0 = FullEdge(left: heRT, right: heLT)
let fe1 = FullEdge(left: heLB, right: heRB)
fullEdges[fe0.uuid] = fe0
fullEdges[fe1.uuid] = fe1
updatedHalfEdge.append(fe0.uuid)
updatedHalfEdge.append(fe1.uuid)
polygons.removeValue(forKey: leftHalfEdge.polygonStatus.uuid)
polygons.removeValue(forKey: rightHalfEdge.polygonStatus.uuid)
self.updateQuadraticErrorMetrics(uuids: updatedHalfEdge.unique)
return
}
func polygonReduction(count: Int) {
for _ in 0..<(count / 2) {
let v = fullEdges.min(by: {a, b in a.value.quadraticErrorMetrics < b.value.quadraticErrorMetrics} )
if let f = v?.value {
collapse(fullEdge: f)
}
}
}
}
}