Bug 350 - triangle -> trapezoid decomposition logic error in Render
Summary: triangle -> trapezoid decomposition logic error in Render
Alias: None
Product: xorg
Classification: Unclassified
Component: Server/General (show other bugs)
Version: unspecified
Hardware: x86 (IA32) Linux (All)
: high normal
Assignee: Keith Packard
QA Contact:
Whiteboard: closeme 09/09
Depends on:
Reported: 2004-03-18 16:20 UTC by Stephen McCamant
Modified: 2011-10-15 17:21 UTC (History)
1 user (show)

See Also:
i915 platform:
i915 features:

C program to demonstrate Render triangle bug (1.74 KB, text/plain)
2004-03-18 16:21 UTC, Stephen McCamant
no flags Details
Proposed patch to mitri.c (4.04 KB, patch)
2004-03-21 15:22 UTC, Stephen McCamant
no flags Details | Splinter Review

Description Stephen McCamant 2004-03-18 16:20:33 UTC
The Render extension tries to draw triangles by effectively sorting the        
three points by their Y coordinates, and drawing two degenerate trapezoids 
that meet at the horizontal line passing through the middle point.  
(see miRasterizeTriangle() in xserver/render/mitri.c) 
The tricky part of this technique is figuring out which edge of the triangle is 
the left edge of the trapezoid and which is the right. The current code does 
this by comparing the X coordinates of the two non-top points, but this doesn't 
work in general: there are cases where the non-top points have the same X 
coordinate, but which edge of the triangle is left and which is right depends 
on the X coordinate of the top point. I think the "two cases" described in 
a comment should really be whether the three points, in top-down order, go 
around the triangle clockwise or counterclockwise. (Which could be determined 
for instance by looking at the sign of cross-product of two edge vectors of    
the triangle).

I'll attach a C program that demonstrates this bug (for me using Xsdl from
last night's CVS, but I think the problem is hardware independent). The 
program's expected behavior is to draw two symmetric triangles (making a
downward-pointing chevron), but only the right triangle draws correctly;
the left one fills in only an area to the left of what should be the left edge
of the top half (trapezoid) of the triangle.

(Also reported to XFree86 as their bug #1275)
Comment 1 Stephen McCamant 2004-03-18 16:21:50 UTC
Created attachment 157 [details]
C program to demonstrate Render triangle bug
Comment 2 Stephen McCamant 2004-03-21 15:22:03 UTC
Created attachment 160 [details] [review]
Proposed patch to mitri.c

This proposed patch implements the modified algorithm I referred to above.
It fixes the supplied test case and deals correctly with a number of other
triangles I tried.
Comment 3 Keith Packard 2004-03-21 20:40:49 UTC
Cool.  Thanks for the fix.  As you might have guessed,  the triangle code hasn't
seen a lot of testing.  And, we've also proved that the trapezoid spec is
broken, so we'll be reimplementing that at some point.  So many bugs, so little

I'll see if I can't manage to get this patch tested and committed in the next
couple of days.
Comment 4 Rolf Leggewie 2007-01-23 23:27:10 UTC
Has this been resolved?
Comment 5 Rolf Leggewie 2008-01-31 23:55:44 UTC
(In reply to comment #4)
> Has this been resolved?

Either that or it is of no bother to anyone any more.  Setting to REMIND status.
Comment 6 Adam Jackson 2008-02-24 18:23:46 UTC
Mass reopen.  The "REMIND" resolution is lame, I'm deleting it.  Consider yourself reminded.
Comment 7 Rolf Leggewie 2008-08-08 18:22:11 UTC
will close as invalid in September unless somebody speaks up
Comment 8 Adam Jackson 2009-04-14 07:16:12 UTC
This looks like it was resolved when Keith rewrote the trap rendering code:

commit 196aafb19a3cfdc8c21f9bf75814cf0d84ff4446
Author: Keith Packard <keithp@keithp.com>
Date:   Fri Aug 6 23:42:10 2004 +0000

    Add RenderAddTraps. Rewrite trapezoid rendering code.

At any rate the testcase given here renders correctly in in xserver 1.6.

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.