Как сканировать конвертировать правые края и уклоны меньше одного?

Question

Я пишу программу, которая будет использовать преобразование сканирования на треугольниках для заполнения пикселей, содержащихся в треугольнике.

Одна вещь, которая меня смущает, это то, как определить приращение x для правого края треугольника или для наклонов, меньших или равных единице.

Вот код, который я должен обработать для левых краев с наклоном больше единицы (получено из Компьютерная графика: принципы и практика, второе издание ):

for(y=ymin;y<=ymax;y++)
{
    edge.increment+=edge.numerator;
    if(edge.increment>edge.denominator)
    {
        edge.x++;
        edge.increment -= edge.denominator;
    }
}

Числитель установлен из (xMax-xMin), а знаменатель установлен из (yMax-yMin) ..., что имеет смысл, так как представляет наклон линии. По мере продвижения вверх по линиям сканирования (представлены значениями y). X увеличивается на 1 / (знаменатель / числитель) ... что приводит к тому, что x имеет целую часть и дробную часть.

Если дробная часть больше единицы, то значение x нужно увеличить на 1 (как показано в файле edge.increment> edge.denominator).

Это прекрасно работает для любых левосторонних линий с уклоном, превышающим единицу, но у меня возникают проблемы с обобщением для любого края, и поиск в Google оказался бесплодным.

Кто-нибудь знает алгоритм для этого?

Answer 1

Существует 4 случая, которые необходимо учитывать: наклон> 1, наклон между 0 и 1, наклон между -1 и 0 и наклон менее -1. ​​

Вы кодировали для наклона> 1. Если у вас есть наклон <-1, вы можете определить это заранее, вычислить <code>increment, чтобы быть +1 или -1, и изменить x++ на x += increment.

Для случаев, когда наклон составляет от -1 до 1, вы можете иметь один и тот же цикл, только с заменой x и y.

РЕДАКТИРОВАТЬ: Похоже, что вы пытаетесь заполнить треугольник путем сканирования, конвертируя две ноги одновременно. Это особый случай, который вы можете использовать, но общий способ сканирования для преобразования выпуклого многоугольника (например, треугольника) состоит в том, чтобы поместить все точки в список, а затем для каждой линии сканирования нарисовать линию между столбцами min и max. Вот некоторый псевдокод для алгоритма:

// create a list of points that is the union of all segments
var points = ScanConvert(x1, y1, x2, y2)
             .Union(ScanConvert(x2, y2, x3, y3))
             .Union(ScanConvert(x1, y1, x3, y3));
// group the points by scan line, finding the leftmost and rightmost point on each line
var scanlines = from p in points
                group p by p.Y into scanline
                select new { y = scanline.Key,
                             x1 = scanline.Min(p => p.X),
                             x2 = scanline.Max(p => p.X) }
// iterate over the scan lines, drawing each segment
foreach (var scanline in scanlines)
    DrawLine(x1, y, x2, y);