[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Rewrite Skyline code (issue 547980044 by address@hidden)

From: hanwenn
Subject: Rewrite Skyline code (issue 547980044 by address@hidden)
Date: Sun, 19 Apr 2020 14:43:26 -0700

Reviewers: ,

(this still needs some work, but the speedup might be worth an early

Rewrite Skyline code

With this change, Carver MSDM goes from 38 seconds to 32 seconds, a
15% improvement.

* Do not use contiguous buildings. Instead, Y=-infinity is represented
  by simply omitting the building. This reduces memory requirements
  (for example, an empty skyline needs no buildings at all.), and
  obviates the Skyline::normalize() call which takes ~1 % of CPU.

* Buildings store Y coordinate of the left edge, rather than the
  intercept at x==0.0.  This avoid excessive rounding problems when X
  is large, and lets us compute building.height_at(x[LEFT]) cheaply.

* Avoid using infinity and NaN. We only let the X coordinates at the
  be infinite (which is only necessary if a minimum height is

* Aggressively prune zero width
  buildings. Adjust input/regression/skyline-point-extent to match
  this behavior

* Simplify the merge code, using less nested if statements.

* Add a unittest for the Skyline code

* Debug output is produced with Lookup::segments_to_line_stencil()

Please review this at

Affected files (+716, -421 lines):
  M input/regression/
  A input/regression/
  M lily/
  M lily/include/lookup.hh
  M lily/include/skyline.hh
  M lily/
  M lily/
  M lily/
  M lily/

reply via email to

[Prev in Thread] Current Thread [Next in Thread]