Changeset 25027 for branches/pap/magic/remove/src/Line.c

Timestamp:

Aug 7, 2009, 4:08:25 PM (17 years ago)

Author:

Paul Price

Message:

Merging trunk (r25026) to get up-to-date on old branch.

Location:

branches/pap

Files:

• . (modified) (1 prop)
• magic (modified) (1 prop)
• magic/remove/src (modified) (1 prop)
• magic/remove/src/Line.c (modified) (5 diffs)

branches/pap/magic/remove/src

@@ +1 @@
+isdestreaked
 streaksremove
 streaksreplace
 streakscompare
 streaksrelease
+makefile

@@ +1 @@
+isdestreaked
 streaksremove
 streaksreplace
 streakscompare
 streaksrelease
+makefile

branches/pap/magic/remove/src/Line.c

@@ -16 +16 @@
 {
     double temp = *first;
+    *first = *second;
+    *second = temp;
+}
+
+/** Internal routine to swap integer values */
+
+void SwapInt (int* first, int* second)
+{
+    int temp = *first;
     *first = *second;
     *second = temp;
@@ -255 +264 @@
 }
 
-/** Map a line to an image for its specified width and store as a list
-    of pixel positions
+/** Clip the line between (minX,minY) and (maxX,maxY)
+
+    @param[in,out] line line to be clipped within the bounds
+    @param[in] minX minimum X (columns) for the line
+    @param[in] minY minimum Y (rows) for the line
+    @param[in] maxX maximum X (columns) for the line
+    @param[in] maxY maximum Y (rows) for the line
+    @return true if line overlaps the clip boundaries           */
+
+bool LineClipFull (Line *line, int minX, int minY, int maxX, int maxY)
+{
+    unsigned int i, found = 0;
+    Line boundLine, clipLine;
+    strkPt tuple1, tuple2, vertices[4];
+    vertices[0].x = minX; vertices[0].y = minY;
+    vertices[1].x = maxX; vertices[1].y = minY;
+    vertices[2].x = maxX; vertices[2].y = maxY;
+    vertices[3].x = minX; vertices[3].y = maxY;
+
+    for (i = 0; i < 4 && found < 2; ++i)
+    {
+        boundLine.begin = vertices[i];
+        boundLine.end   = vertices[(i + 1) % 4];
+        if (LineIntercept (line, &boundLine, &tuple1, &tuple2, false, true))
+        {
+            if (found == 0)
+            {
+                clipLine.begin = tuple1;
+                ++found;
+            }
+            else if (tuple1.x != clipLine.begin.x || 
+                     tuple1.y != clipLine.begin.y)
+            {
+                clipLine.end = tuple1;
+                ++found;
+            }
+        }
+    }
+    
+    // If two endpoints are found, clip the line
+    
+    if (found > 1)
+    {
+        if (clipLine.begin.x <= clipLine.end.x)
+        {
+            line->begin = clipLine.begin;
+            line->end   = clipLine.end;
+        }
+        else
+        {
+            line->begin = clipLine.end;
+            line->end   = clipLine.begin;
+        }
+    }
+    return found > 1;
+}
+
+/** Move a line by the specified X and Y offsets
+    @param[in,out] line Line to move by X and Y offsets
+    @param[in] xOffset X shift applied to both endpoints
+    @param[in] yOffset Y shift applied to both endpoints        */
+
+void LineMove (Line *line, double xOffset, double yOffset)
+{
+    line->begin.x += xOffset;
+    line->begin.y += yOffset;
+    line->end.x   += xOffset;
+    line->end.y   += yOffset;
+}
+
+/** Return the maximum bounds between the line endpoints and
+    current bounds
+    @param[in] line Line endpoints to compare
+    @param[in,out] xMin minimum X value to update
+    @param[in,out] xMax maximum X value to update
+    @param[in,out] yMin minimum Y value to update
+    @param[in,out] yMax maximum Y value to update               */
+
+void MaxBounds (Line *line, int *xMin, int *xMax,  int *yMin, int *yMax)
+{
+    if (line->begin.x < *xMin) *xMin = (int) floor (line->begin.x);
+    if (line->end.x   < *xMin) *xMin = (int) floor (line->end.x);
+    if (line->begin.y < *yMin) *yMin = (int) floor (line->begin.y);
+    if (line->end.y   < *yMin) *yMin = (int) floor (line->end.y);
+
+    if (line->begin.x > *xMax) *xMax = (int) ceil (line->begin.x);
+    if (line->end.x   > *xMax) *xMax = (int) ceil (line->end.x);
+    if (line->begin.y > *yMax) *yMax = (int) ceil (line->begin.y);
+    if (line->end.y   > *yMax) *yMax = (int) ceil (line->end.y);
+}
+
+/** Map a line to an image for its specified width and store as
+    a list of pixel positions
 
     @param[out] pixels list of PixelPos pointers corresponding
                        based on the line settings
-    @param[in] line Line to map to pixels                       */
-
-void PixelsFromLine (StreakPixels* pixels, Line *line)
-{
+    @param[in] line Line to map to pixels   
+    @param[in] numCols maximum X (columns) for the line
+    @param[in] numRows maximum Y (rows) for the line            */
+
+void PixelsFromLine (StreakPixels* pixels, Line *line, int numCols, int numRows)
+{
+    Line offsetLine;
     PixelPos *pixel;
-    double slope, xOffset, yOffset, xMid, yMid, xBegin, yBegin, xEnd, yEnd, x, y;
+    double slope, xOffset, yOffset, xMid, yMid;
+    int x, y, xBegin = numCols, yBegin = numRows, xEnd = 0, yEnd = 0;
 
     // Extract the endpoints
@@ -280 +384 @@
     double dr = sqrt (dx * dx + dy * dy);
     double halfWidth  = line->width / 2.0;
-    double halfWidth2 = halfWidth * halfWidth;
     if (!dr) return;
-    
+
+    // Compute the intercepts of line width bounds and determine maximum
+    // bounds in each axis
+
+    xOffset = -halfWidth * dy / dr;
+    yOffset =  halfWidth * dx / dr;
+
+    offsetLine = *line;
+    LineMove (&offsetLine, xOffset, yOffset);
+    if (LineClip (&offsetLine, numCols, numRows))
+        MaxBounds (&offsetLine, &xBegin, &xEnd, &yBegin, &yEnd);
+
+    offsetLine = *line;
+    LineMove (&offsetLine, -xOffset, -yOffset);
+    if (LineClip (&offsetLine, numCols, numRows))
+        MaxBounds (&offsetLine, &xBegin, &xEnd, &yBegin, &yEnd);
+
     // Step point by point based on the dominate axis
     
@@ -307 +426 @@
         // Compute the x and y offsets for the line width extent
 
-        xOffset = halfWidth * dy / dr;
-        yOffset = halfWidth * dr / dx;
-        yMid   = y1 + slope * (floor (x1 - xOffset) - x1);
-        xBegin = floor (x1 - xOffset);
-        xEnd   = ceil  (x2 + xOffset) + 1.0;
-
-        for (x = xBegin; x < xEnd; ++x)
-        {
-            yBegin = floor (yMid - yOffset);
-            yEnd   = ceil  (yMid + yOffset) + 1.0;
-            for (y = yBegin; y < yEnd; ++y)
-            {
-                if (DistanceSquared (line, x, y) <= halfWidth2)
+        if (xBegin > xEnd) 
+            SwapInt (&xBegin, &xEnd);
+        else
+            ++xEnd;
+        if (xBegin < 0) xBegin = 0;
+        if (xEnd > numCols) xEnd = numCols;
+
+        yMid = y1 + slope * (xBegin - x1);
+        yOffset = fabs (halfWidth * dr / dx);
+
+        for (x = xBegin; x != xEnd; ++x)
+        {
+            yBegin = (int) floor (yMid - yOffset);
+            yEnd   = (int) ceil  (yMid + yOffset) + 1;
+            for (y = yBegin; y != yEnd; ++y)
+            {
+                if (y >= 0 && y < numRows)
                 {
-                    if (x >=0 && y >= 0) {
-                        pixel = psAlloc (sizeof(PixelPos));
-                        pixel->x = (unsigned int) x;
-                        pixel->y = (unsigned int) y;
-                        psArrayAdd (pixels, 1024, pixel);
-                        psFree (pixel);
-                    }
+                    psImageSet(pixels, x, y, 1);
                 }
             }
@@ -354 +471 @@
         
         // Compute the x and y offsets for the line width extent
-        
-        xOffset = halfWidth * dr / dy;
-        yOffset = halfWidth * dx / dr;
-
-        xMid   = x1 + slope * (floor (y1 - yOffset) - y1);
-        yBegin = floor (y1 - yOffset);
-        yEnd   = ceil  (y2 + yOffset) + 1.0;
-        
-        for (y = yBegin; y < yEnd; ++y)
-        {
-            xBegin = floor (xMid - xOffset);
-            xEnd   = ceil  (xMid + xOffset) + 1.0;
-            for (x = xBegin; x < xEnd; ++x)
-            {
-                if (DistanceSquared (line, x, y) <= halfWidth2)
+
+        if (yBegin > yEnd)
+            SwapInt (&yBegin, &yEnd);
+        else
+            ++yEnd;
+        if (yBegin < 0) yBegin = 0;
+        if (yEnd > numRows) yEnd = numRows;
+
+        xMid = x1 + slope * (yBegin - y1);
+        xOffset = fabs (halfWidth * dr / dy);
+        
+        for (y = yBegin; y != yEnd; ++y)
+        {
+            xBegin = (int) floor (xMid - xOffset);
+            xEnd   = (int) ceil  (xMid + xOffset) + 1;
+            for (x = xBegin; x != xEnd; ++x)
+            {
+                if (x >=0 && x < numCols)
                 {
-                    if (x >=0 && y >= 0) {
-                        pixel = psAlloc (sizeof(PixelPos));
-                        pixel->x = (unsigned int) x;
-                        pixel->y = (unsigned int) y;
-                        psArrayAdd (pixels, 1024, pixel);
-                        psFree (pixel);
-                    }
+                    psImageSet(pixels, x, y, 1);
                 }
             }

@@ +1 @@
+isdestreaked
 streaksremove
 streaksreplace
 streakscompare
 streaksrelease
+makefile